Gut, da ich ebenfalls Sephis Raetsel geloest hab (ich durfte nicht ins Forum sehen weil er schon die loesung gepostet hatte), ich einen Beweis durch vollstaendige Induktion dazu gelegt habe (wenn interesse besteht, poste ich ihn gerne) und es eine Freirunde ist, bin ich so frei, ein Raetsel zu stellen ...
Frage: Warum laeuft der folgende C Code bei echter Parallelisierung auf einem Zwei-Prozessor-System mit Shared Memory unterschiedlich schnell, je nachdem, wie die Schleife (z.B. vom Programmierer) auf die Prozessoren aufgeteilt wird ?
Tipp: Wenn Prozessor1 alle geraden Indizes und Prozessor2 die ungeraden Indizes bearbeitet anstatt Prozessor1 die Indizes von 0 bis SomeBigNum/2-1 und Prozessor2 von SomeBigNum/2 bis SomeBigNum-1 ist der Code um teilweise mehr als Faktor 10 langsamer.
Tipp 2: Das selbe Problem aus einer aehnlichen Ursache kann auch bei seriellem Single-Prozessor-Code auftreten, wenn man mit zweidimensionalen Arrays arbeitet und die beiden Schleifen-Indizes vertauscht.
Sorry, ich verstehe die Antwort nicht.
Das sollte schon etwas ausfuehrlicher sein, denn wieso sollten groessere Spruenge in der Addresse ein Problem sein bzw das Problem beheben ?
Ich bin mir nicht sicher wie genau eine solche Schleife bei Parallelisierung auf einem 2-CPU-System abgearbeit wird, aber mein Tipp wäre, daß es bei der abwechselnden Variante (1 Prozessor ungerade, der andere die geraden Indizes) zur Überlappung beim Speicherzugriff kommt, da aufgrund des Shared Memorys beide Prozessoren denselben Speicherbereich bearbeiten.
Das Problem hierbei ist:
Wenn Prozessor1 gerade den Wert von A[i] in den Speicher schreibt kann Prozessor2 zurselben Zeit nicht den Wert von A[i+1] auslesen und muss warten bis Prozessor1 mit dem Schreiben fertig ist. (Da Prozessor1 die "Leitung" zum RAM blockiert)
Arbeiten beide CPUs auf einem jeweils festem Bereich des Arrays ist es vorstellbar, daß der C-Compiler entsprechend optimiert und die zu bearbeitenden Segmente des Arrays jeweils in großen Brocken im Cache des Prozessors zwischengespeichert werden. Dadurch können beide Prozessoren gleichzeitig große Teile des Arrays bearbeiten ohne sich beim Speicherzugriff in den Weg zu kommen.
Beim Einkernprozessor ist es vermutlich ebenso die fehlende Optimierung über den Cache die zu einer minimalen Verlangsamung führt, da die CPU bei jedem durchlauf zwischen "lesen" und "schreiben" hin und herschalten muss anstatt einmal einen großteil in den Cache laden und später einmal große Datenmengen aus dem Cache in den RAM schreiben.
Bei einem sehr großen Array kann sich dieser minmale Zeitverlust vermutlich zu bemerkbaren Verzögerungen aufsummieren.
Diese Antwort lasse ich als richtig gelten. Magor ist dran.
Hier die genaue Aufloesung:
Prozessoren greifen nicht direkt auf den RAM zu, sondern haben idR zwei Cache Level, ueber die sie gehen. Das heisst, will man ein einzelnes Byte aus dem RAM holen, so wird zuerst ein grosser RAM Block (Eine sogenannte Cache Line) in den Second Level Cache geladen. Ein kleiner Ausschnitt daraus wird dann in den First Level Cache geladen, und das einzelne Byte von dort in ein Register der CPU. Brauch man nun das Byte neben dem zuvor geladenen Speicher, so befindet es sich bereits im Cache und kann schnell geladen werden. Das hat entscheidende Geschwindigkeitsvorteile, denn ein Zugriff auf den L1 Cache kann in ca 10 Prozessorcycles erfolgen, Zugriff auf L2 dauert bereits etwa 100 Zyklen und direkter Zugriff auf den RAM laesst die CPU auch schon mal gerne 1000 Zyklen warten.
Warum nun also die Verzoegerung auf dem Zweiprozessorsystem ? Ganz einfach: Jede der zwei CPUs hat mindestens einen einzigen L1 Cache. Im Fall das der eine gerade und der andere ungerade Indices bearbeitet passiert folgendes. Beide Prozessoren kopieren zu begin den selben Speicherinhalt in ihren Cache. Der erste Prozessor 1 (P1) liest nun seine Speicheraddresse und veraendert ihren Inhalt. P2 tut das selbe, muss aber feststellen, das P1 schon Daten in der selben Cache Line geaendert hat, also muss er die Cach Line aus dem Cache von P1 erst in den Cache von P2 kopieren, seinen Index laden und veraendern. Nun sieht aber P1 das die Cache Line veraendert wurde, usw ...
Im Falle des Einprozessorsystems und der falschen Schleifenanordnung ist es sehr aehnlich: nehmen wir folgenden einfachen C-Code:
C speichert mehrdimensionale Arrays zeilenweise ab. Das heisst, das im Speicher zuerst alle Elemente fuer y=0 stehen, danach die Elemente fuer y=1 usw. (In Fortran ist es z.B. genau andersrum). Dadurch das aber y in der inneren Schleife steht, muss jedes Mal eine andere Zeile in den Cache kopiert werden. Allein durch das Vertauschen der beiden Schleifen kann der Code bis zu acht mal schneller ausgefuehrt werden, da dann die Elemente jeder Zeile bereits im Cache stehen und auch verwendet werden koennen.
dead_orc: Ich habe die Diskussion zu dieser Aussage mal hierhin ausgelagert.
Zitieren
