Diskussion:Loop unrolling/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Loop unrolling/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Loop_unrolling/Archiv/1#Thema_1

Fragen

1. Wer nimmt diese Optimierung vor?

Der Compiler sollte genannt und verlinkt werden.

2. Das "vollständige Entrollen" sollte imo zuerst genannt werden, vor dem "teilweise Entrollen" - es ist einfacher zu verstehen.

3. "Schleifenbedingung" sollte verlinkt sein.

--arilou (Diskussion) 12:07, 22. Aug. 2012 (CEST)

Zu 1) Das ist unerheblich. Die Optimierung kann von Hand geschehen oder durch einen Compiler. Heutzutage dürften wohl alle gängigen Compiler Loop-Unrolling unterstützen.

Zu 2) Das teilweise Entrollen ist der Zwischenschritt bis zum vollständigen Entrollen. M.E. ist diese Reihenfolge sinnvoll und beizubehalten.

Zu 3) Naja, ob der Weg von "Schleife" zu "Schleifenbedingung" so weit ist?

-- Plankton314 (Diskussion) 13:10, 22. Aug. 2012 (CEST)

1. "Wer": Wenn es praktisch immer der Compiler macht, könnt' man ihn doch nennen, oder? Meine WP:OmA denkt sonst, es wär' 'ne gute Idee, das in ihrem neuesten C-Programm von Hand zu machen... und so ein Satz "Die Optimierung kann von Hand geschehen oder durch einen Compiler." ist ja schnell cut-and-past'ed...
2. "Abfolge Ganz/Teilweise": Erst kommt der Leser, dann die Logik. Was einfacher zu verstehen ist (ohne [2*i+1] usw.), soll man zuerst präsentieren. Außerdem ist ein "teilweise Entrollen" nicht "der [logische] Zwischenschritt bis zum vollständigen Entrollen". Logisch ist doch zunächst mal, immer komplett zu entrollen, wenn möglich. Erst zusätzliche Bedingungen/Einschränkungen/... führen dazu, dass man das teilweise Entrollen dem kompletten vorzieht. Ich halte eine Argumentation à la

• ursprüngliche Schleife
• komplett entrollte Schleife spart Zähler und Rechenzeit
• teilweise entrollte, wenn x, y, z oder w gegen das komplette Entrollen spricht

für ziemlich logisch und für den Leser leichter verständlich.

3. "Link 'Schleifenbedingung'": Meine OmA hat schon halbwegs verstanden, dass 'ne Schleife dazu führt, dass etwas mehrmals passiert. Aber was ist eine "Schleifenbedingung" ??? (Genau genommen denk' ich meist nicht an meine OmA, sondern an meinen 10-jährigen Neffen, der mit seinem Lego Mindstorms rumhantiert...)

--arilou (Diskussion) 13:35, 22. Aug. 2012 (CEST)

Zu 1) Ich halte das für redundant, aber ein einzelner Satz wird wohl auch keinen großen Schaden anrichten.

Zu 2) Um eine Schleife vollständig zu entrollen, muss sie zwangsläufig n mal teilweise abgerollt werden. Ich wüsste nicht, wie es ohne diesen Zwischenschritt funktionieren soll - es sei denn man geht bereits vom Endergebnis aus. Ich persönlich bin auch dagegen in so einem kleinen Artikel das Ergebnis vorweg zu präsentieren und dann die Zwischenschritte hinterherzuschieben.

Zu 3) Naja, ob man bei einer speziellen Optimierungstechnik für Schleifen nochmal beginnen muss eine Schleife selbst zu erklären, zweifle ich stark an. Zumal gleich im ersten Satz ein Link auf den Artikel Schleifen steht. Genauso wie ich nicht glaube, dass jemand eine Schleife kennt bzw. verstanden hat ohne mit dem Begriff Schleifenbedingung etwas anfangen zu können. Und selbst wenn, ist im Artikel "Schleife" ein Link auf "Laufbedingung" und dort einer zu Aussagenlogik.

-- Plankton314 (Diskussion) 14:34, 22. Aug. 2012 (CEST)

1) erledigt.

2) "Um eine Schleife vollständig zu entrollen, muss sie zwangsläufig n mal teilweise abgerollt werden" - ähm, nein? Ich schreib' den Schleifenkörper einfach n Mal nacheinander hin, hau' nach jedem der n Abschnitte das rein, was hinter dem zweiten Strichpunkt im Schleifenkopf steht, und fertig? (Bin mir ziemlich sicher, dass Loop-unrolling im Compiler genau so angefangen hat - nur für for-Schleifen mit fest vorgegebenen Grenzen.) Ich seh' nicht, was daran "n mal teilweise abgerollt" wäre - oder meinst du dasselbe wie ich hier gerade geschrieben hab?

2b) Je nach Argumentationsweise (s.o.) ist das teilweise-Abrollen kein Zwischenschritt, sondern eine Erweiterung der einfachen komplett-Abrollen-Vorgehensweise (wenn diese sich nicht durchführen lässt).

3) Schleife-Erklären: Hm, ok, überzeugt.

--arilou (Diskussion) 15:31, 22. Aug. 2012 (CEST)

Zu 2) Ja, ich meine etwa das, was du auch geschrieben hast.

Natürlich sagt man sich als Mensch "okay, ich schreib das jetzt n mal hin", aber wenn man diesen Vorgang beschreiben bzw. in Teilschritte zerlegen soll, gelangt man m.E. nur über das teilweise Entrollen dorthin. So wie du schreibst: man schreibt den Schleifenrumpf einmal hin und reduziert dann die Anzahl der Durchläufe entsprechend.

Streng genommen müsste man noch bei jedem teilweisen Entrollen prüfen, wie groß der "Verschnitt" ist (siehe Duff's Device).

Aber mal andersherum gefragt, was würdest du denn umbauen/ändern wollen (bzgl. der Reihenfolge teilweise/vollständig Entrollen)? -- Plankton314 (Diskussion) 15:45, 22. Aug. 2012 (CEST)

So wie jetzt die aktuelle Version (24.9.2012) ist. --arilou (Diskussion) 15:05, 24. Sep. 2012 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 15:05, 24. Sep. 2012 (CEST)

Beispiel

Die Beispiel-Schleife

for (int i=0; i<8; ++i)
   dest[i] = src[i];

wird im Artikel ersetzt durch selbige:

for (int i=0; i<4; ++i) {
   dest[2*i]   = src[2*i];
   dest[2*i+1] = src[2*i+1];
}

Es könnte aber durchaus auch folgendes sein:

for( i=0 ; i<8 ; ) {
   dest[i] = src[i];
   i = i+1 ;
   dest[i] = src[i];
   i = i+1 ;
}

Gibt es Belege, welche Variante reale Compiler tatsächlich durchführen? Imo bedeutet zweite Variante deutlich weniger Rechenoperationen, oder? Außerdem halte ich sie für leichter verständlich für den Leser... --arilou (Diskussion) 13:44, 22. Aug. 2012 (CEST)

Ja, das ist im Grunde richtig. Ich weiß nicht, ob du den Artikel beobachtest, aber ich habe genau diese (deine zweite) Version vor kurzem herausgenommen und durch die Erste ersetzt.

Grund war, dass bei der Letzteren eine Datenabhängigkeit durch den Index i entsteht und die Optimierung so nichts bewirkt bzw. ineffizienter ist - oder aber ein Optimierer (Programmierer oder Compiler) zuvor das Inkrement wegoptimieren muss.

Die Idee bei dem Snippet (so wie es jetzt dasteht), war auch zu zeigen, dass die Schleife statt acht- nur noch viermal durchlaufen wird.

-- Plankton314 (Diskussion) 14:25, 22. Aug. 2012 (CEST)

Was hältst du davon, beide Versionen zu nennen - die "einfache" für's leichtere Verständnis für den Leser, die zweite mit Begründung "Datenabhängigkeit" (da musst' ich erst mal 'n paar Augenblicke nachdenken, was du damit meinst, und warum das die Geschwindigkeit reduzieren soll...) ?

--arilou (Diskussion) 15:45, 22. Aug. 2012 (CEST)

PS: Ich erlaub' mir auch gleich, "mein" Beispiel etwas zu ent-C-en...

Ja, klingt sinnvoll und könnte beim Verständnis für den Einsteiger helfen. Hier ist jetzt wieder schwierig abzugrenzen, was noch enzyklopädisch und was schon Erklärbär ist. Ich prophezeihe aber, dass in ein paar Monaten einer kommt und es rausmacht mit dem Vermerk doppelt/überflüssig -- Plankton314 (Diskussion) 15:53, 22. Aug. 2012 (CEST)

Hab's jetzt mal komplett neu formuliert. --arilou (Diskussion) 10:27, 23. Aug. 2012 (CEST)

Gut schauts aus. Hab noch ein paar Kleinigkeiten umformuliert. -- Plankton314 (Diskussion) 13:33, 23. Aug. 2012 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 15:07, 24. Sep. 2012 (CEST)

Pipelining

Mir ist gerade beim Einarbeiten eines Gegenbeispiels aufgefallen, dass im Artikel ein m. E. wesentlicher Punkt zu kurz kommt: Durch das Unrolling können Instruktionen gepipelined und dann parallel ausgeführt werden. Das bringt den eigentlichen Geschwindigkeitsvorteil auf heutigen Prozessoren. -- Plankton314 (Diskussion) 21:08, 20. Nov. 2012 (CET)

Heutige Branch-Prediction liegt in (deutlich) >90% der Fälle richtig, womit auch eine nicht-entrollte Schleife "gut pipelinen" sollte. Damit ist "Das bringt den eigentlichen Geschwindigkeitsvorteil" erst mal TF und nicht mehr soooo sicher; und wenn's nicht mehr "offenkundig richtig" ist, braucht's einen Beleg. Dann aber: gerne!

--arilou (Diskussion) 10:41, 21. Nov. 2012 (CET)

Die Branch-Prediction hat ja nichts mit dem Pipelining zu tun.

Der Vorteil ist, dass z. B. eine 2-fach abgerollt Schleife - wenn es gut läuft - in halben Zeit wie zuvor ausgeführt werden kann. -- Plankton314 (Diskussion) 11:11, 21. Nov. 2012 (CET)

"Die Branch-Prediction hat ja nichts mit dem Pipelining zu tun." - Ähm, hä? Lies erst mal Sprungvorhersage, dann nimmst' mal schnell diese Aussage wieder zurück. Wenn das Loop Unrolling (bei einer sehr kleinen Schleife) zu andauernden Branch Prediction Faults führt, war das 'n Schuss ins Knie.

--arilou (Diskussion) 13:59, 21. Nov. 2012 (CET)

Gut, das war nicht richtig ausgedrückt.

Was ich meinte war, dass bei einer ausgerollten Schleife zwei oder mehrere Befehle in der Pipeline parallel ausgeführt werden können. Und die Sprungvorhersage hat nichts mit einer parallelen Ausführung zu tun, sondern nur die Pipeline möglichst voll zu halten. -- Plankton314 (Diskussion) 18:36, 21. Nov. 2012 (CET)

Wenn die Sprungvorhersage stimmt, bleibt die Pipeline auch bei einer nicht-ausgerollten Schleife schön gefüllt, und es können Maschinenbefehle parallel ausgeführt werden. Daher ergibt sich beim Schleifen-Ausrollen nicht zwangsläufig eine "Parallelisierungs-Verbesserung"; diese Eigenschaft kann sich bessern, dass dies genereller immer geschiet, ist aber erst mal TF.

Insgesamt sehe ich diese Optimierungen "Latency Hiding", "Vermeidung von Datenabhängigkeiten" usw. eher als unabhängig vom Loop Unrolling. Ein Entrollen der Schleife kann diese Optimierungen erleichtern, muss aber nicht.

--arilou (Diskussion) 09:22, 22. Nov. 2012 (CET)

Nein, das ist leider falsch.

Da die Schleifenbedingung geprüft werden muss, findet hier ein bedingter Sprung statt. Das ist eine Kontrollflussabhängigkeit bzw. -konflikt. Genau dann, muss der Prozessor nämlich warten, bis die Sprungbedingung ausgeführt wurde und kann erst danach mit der Ausführung fortfahren. (Das bedeutet, dass eine Anweisung nach einem bedingten Sprung nicht mehr parallel [zur vorherigen] ausgeführt werden kann.)

Ja, diese Eigenschaft ist ein "kann", aber das sind alle erhofften Verbesserungen beim Abrollen.

Natürlich sind die besagten anderen Optimierungen auch unabhängig anwendbar, es ist aber das erklärte Ziel des Unrolling, dass diese Optimierungen eben genau dann auf den abgerollten Rumpf angewandt werden können. -- Plankton314 (Diskussion) 11:43, 22. Nov. 2012 (CET)

(Intel Core-i "Sandy Bridge":) "Branch predictions are queued slightly ahead of instruction fetch so that the stalls for a taken branch are usually hidden, [...]" ( http://www.realworldtech.com/sandy-bridge/3/ ); also (siehe Dynamische Sprungvorhersage): "Sprünge im Programmcode zurück sind in der Regel Schleifen, die oft mehrfach durchlaufen werden, sodass bei dieser prophylaktisch die Pipeline mit dem zurückliegenden Code gefüllt wird."

D.h. wenn ein Schleifen-Rücksprung korrekt vorhergesagt wird, kann die Pipeline unterbrechungsfrei und full-speed weiterarbeiten.

Zu anderen Prozessoren hab' ich nicht recherchiert.

Dein Kommentar "Nein, das ist leider falsch." hätte ich für aktuelle Prozessoren gerne belegt, da es (zumindest auch) anders sein kann.

--arilou (Diskussion) 16:25, 22. Nov. 2012 (CET)

Nun, jetzt gelangen wir langsam ans Lehrbuch-Wissen, das nicht zwingend belegt werden muss.

Es gibt kein Mittel gegen Kontrollflussabhängigkeiten, sofern es nicht gestattet ist das Programm (zumindest teilweise) umzustrukturieren.

Es wäre im Grunde möglich - und wird wahrscheinlich auch kommen -, dass man beide Branches im voraus abarbeitet. Ich bin nicht auf dem neuesten Stand der Prozessortechnik, denke aber das ist bis jetzt nicht der Fall.

Insofern wäre hier eher zu belegen, dass es Ausnahmen zur Standard-Annahme gibt.

Um nochmal klarzustellen, wir reden hier ja über die Latenzverdeckung (Latency Hiding). Das widerspricht sich nicht mit dem von dir vorgetragenen, dass die Pipeline - trotz Branch - voll ist. Es verhindert nur, dass Anweisungen vor und nach dem Branch (quasi-)gleichzeitig ausgeführt werden. -- Plankton314 (Diskussion) 19:54, 22. Nov. 2012 (CET)

In jedem Fall sollte der Fokus weg von der Reduzierung der Kontrollanweisungen und dahin, dass durch das Abrollen generell verschiedene weitere Optimierungstechniken angewandt werden können. Das ist eine allgemeingültige und belegbare Aussage und trifft den Kern der Sache besser. -- Plankton314 (Diskussion) 21:59, 22. Nov. 2012 (CET)

Zu letzterem stimme ich zu: Es kann ruhig erwähnt werden (wie du's ja aktuell bereits gemacht hast), dass das Loop Unrolling neben dem (evtl. teilweisen) Wegfall von Schleifen-Bedingungs-Prüfen noch andere Optimierungen ermöglichen oder erleichtern kann. Soweit d'accord.

Wir könnten noch lange von Prozessorarchitektur reden, aber da wird wohl kein Beitrag zum Artikel mehr draus. Hier erst mal Ende? --arilou (Diskussion) 14:17, 23. Nov. 2012 (CET)

Jepp, wie unten erwähnt würde ich noch gerne was zu Latency Hiding/Instruction Level Parallelism und Conditional Branching erwähnen. Darüber können wir dann im Einzelfall diskutieren. -- Plankton314 (Diskussion) 15:23, 23. Nov. 2012 (CET)

Wenn ich mir den Artikel anschaue, so finde ich die Struktur und Kausalität, die er angenommen hat etwas irreführend.

Die beschriebenen Vor- und Nachteile stimmen natürlich, kommen aber gegenüber dem Abschnitt Idee etwas zu kurz.

Der Abschnitt "Idee" vermittelt m. E. den Eindruck, die Hauptmotivation für Loop Unrolling sei, das Verhältnis von Kontrollanweisungen [der Schleife] zum Schleifenrumpf zu optimieren. Aspekte wie Latency Hiding, Pipelining und alle möglichen Cache-Aspekte fallen komplett unter den Tisch.

Mein Vorschlag:

• den Abschnitt "Idee" etwas eindampfen, d. h. ein paar Erläuterungen raus, um es auf die Idee zu reduzieren.
• dagegen die Abschnitte "Vorteile/Nachteile" etwas ausbauen.

Ich hab mal als Lektüre die Handbücher von Intel und AMD in die Literatur/Weblinks aufgenommen. -- Plankton314 (Diskussion) 11:56, 21. Nov. 2012 (CET)

Loop Unrolling gibt's nicht nur in C/Assembler, auch Hochsprachen machen das.

Eine Parallelisierung im Prozessor, Out-of-Order-Spielchen u.ä. sind imo erst ein zweiter Schritt.

Ich stimme zu, dass diese Aspekte, wie auch z.B. Auto-Parallelisierung, ruhig auch im Artikel erwähnt werden dürften. Aber: Wir sollten dabei aufpassen, nicht dahin abzugleiten, nun alle möglichen mehr oder weniger Prozessor-nahen Optimierungen durchzuhecheln. Nur das, was direkt mit Loop Unrolling zu tun hat, und auch das eher in Stichworten und Links.

Den Abschnitt "Idee" zu verkürzen ~hm~ eher nein. Wir dürfen die WP:OmA nicht außer Acht lassen. Andere Bereiche ausbauen - gerne!

--arilou (Diskussion) 13:59, 21. Nov. 2012 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 11:38, 29. Nov. 2012 (CET)

Abschnitt "Manuelles Entrollen"

Ist tatsächlich

sum += sum + x[i][j] * (i*i + j*j);

gemeint? Also

sum = sum + sum + x[i][j] * (i*i + j*j);

? --arilou (Diskussion) 19:39, 24. Nov. 2012 (CET)

Nein, das ist mein Fehler. Ich wollte eigentlich die C-Schreibweise mit "+=", hab aber dann vergessen das sum rauszunehmen. -- Plankton314 (Diskussion) 14:19, 25. Nov. 2012 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 11:38, 29. Nov. 2012 (CET)