Operationsparallel arbeitende Prozessoren - Moderne Prozessorarchitekturen: Prinzipien und ihre Realisierungen - page 215

eine Veröffentlichung von Joseph Fisher Anfang der 80er Jahre populär geworden
ist, in der der Autor ein Verfahren zur statischen Maximierung der Operationsparal-
lelität in entsprechend realisierten Prozessoren beschrieb - nämlich das sog. Trace
Scheduling [45, 101] 1 .

Zur Vorgehensweise: Zunächst analyisert man statisch oder dynamisch, z.B. durch
Anfertigung eines sog. Profiles, das Laufzeitverhalten eines zu optimierenden Pro-
gramms, und wählt entsprechend der gewonnenen Erkenntnisse einen zyklenfreien
Teilpfad (also eine Befehlsfolge) aus, der möglichst häufig zur Ausführung gelangt
(trace). Durch Verschieben der Sprungoperationen und Sprungmarken zu den Enden
des Teilpfads wird dafür gesorgt, dass sich die verbleibenden Operationen unter
Beachtung der Datenabhängigkeiten umordnen lassen. Dabei werden unabhängige
Operationen so verschoben, dass sie in den Befehlen parallel codierbar sind. Wegen
der im Vergleich zum ursprünglichen Programm deutlich größeren Anzahl von für
die Optimierung verfügbaren Operationen lässt sich so das erreichbare Maß an Ope-
rationsparallelität steigern.

Bild 3.25a bis c verdeutlicht die Vorgehensweise beim Trace-Scheduling. Zunächst
zeigt Bild 3.25a, wie sich eine bedingte Sprungoperation in drei Schritten verschie-
ben und die in dieser Weise neu angeordneten Operationen parallelisieren lassen. Im
ersten Schritt wird der zu optimierende Programmpfad A bis E (trace) separiert (im
Bild grau unterlegt), wobei zur bedingten Sprungoperation C nur das wahrscheinli-
chere, z.B. durch Messungen ( profiling ) ermittelte Sprungziel, berücksichtigt wird.
Anschließend werden die Operationen A und B in die auf die bedingte Sprungopera-
tion folgenden Pfade kopiert und so die Sprungoperation C an den Anfang des sepa-
rierten Programmpfads verschoben. Dies ist nur möglich, wenn C keine Abhängig-
keiten zu A oder B aufweist, was hier jedoch angenommen werden soll.

Weil verzweigende Sprungoperationen komplizierter zu verarbeiten sind als nicht-
verzweigende Sprungoperationen, wird C außerdem in seiner Wirkung invertiert, so
dass eine Verzweigung innerhalb des separierten Programmpfads nicht mehr erfor-
derlich ist (Bild 3.25a Mitte). Im letzten Schritt werden schließlich die auf die Ver-
zweigung folgenden Operationen paarweise vertauscht, und zwar in der Weise, dass
aufeinander folgende Operationen möglichst keine Abhängigkeiten zueinander auf-
weisen. Die gebildeten Gruppen lassen sich schließlich in Befehlen parallel codie-
ren. So sind nach diesem Schritt die Operationen A und D sowie B und E parallel
ausführbar, was zu Beginn der Optimierung nicht möglich gewesen ist.

In Bild 3.25b ist exemplarisch dargestellt, wie sich eine Sprungmarke zum Ende
eines separierten Programmpfads verschieben lässt. Dabei werden zuerst die Opera-
tionen C und D jeweils in die von A und X ausgehenden Teilpfade kopiert und der
transformierte Programmpfad anschließend so umgeordnet, dass sich die hier als
unabhängig angenommenen Operationen A, C und D parallel in einem Befehl
codieren lassen. Im Prinzip ist es möglich, auch C' und D' in dem von X ausgehen-
den Programmpfad als parallel ausführbar zu codieren. Dies ist jedoch unnötig,
wenn die entsprechende Operationsfolge nur selten ausgeführt wird.

1. Das Verfahren wurde zuvor bereits zur Optimierung von Mikroprogrammen verwendet [44].