Parallelisierende Übersetzung durch load-time scheduling für eine superskalare Prozessorfamilie

von Michael Hußmann, 2004

Das betrachtete Szenario umfaßt ein Eingebettetes System mit einem PowerPC-Prozessor, welcher die Zielmaschine für einen Übersetzer der Sprache C darstellt. Die Art und Anzahl der Funktionseinheiten ist zur Übersetzungszeit nicht genau bekannt. Daher werden neben dem Maschinencode zusätzliche Annotationen erzeugt, welche die im Programm vorhandene feinkörnige Parallelität beschreiben. Zur Vereinfachung wird angenommen, daß sich die Prozessoren nur in der Art und Anzahl der vorhandenen Funktionseinheiten unterscheiden. Nach dem Übersetzungsvorgang werden der Maschinencode und die Annotationen in einer Objektdatei zum Eingebetteten System geschickt. Vor der ersten Ausführung paßt ein Scheduler das Programm zur Ladezeit mit Hilfe der Annotationen an die tatsächliche Zielmaschine an. Dabei werden im wesentlichen die Instruktionen unter Ausnutzung der feinkörnigen Parallelität neu angeordnet, um eine möglichst hohe Ausführungsgeschwindigkeit zu erreichen. Auch die Registerzuteilung erfolgt zum Teil erst zur Ladezeit und wird durch Beschreibungen der Lebensdauern aller im Programm vorkommenden Werte in den Annotationen unterstützt.

Der load-time scheduler erzielt mittels der Annotationen im Durchschnitt Laufzeitgewinne von 6,5% gegenüber einem herkömmlichen Übersetzer. In Einzelfällen kann die Ausführungszeit sogar um bis zu 20% verkürzt werden. Weiter erreicht der Ansatz in einigen Fällen eine kürzere oder zumindest vergleichbare Ausführungszeit wie List Scheduling Verfahren zur Übersetzungszeit. Darüberhinaus besitzt der Algorithmus des load-time schedulers im Unterschied zum List Scheduling Algorithmus eine lineare Laufzeit. Folglich ist das entwickelte Verfahren speziell für den zeitkritischen Einsatz zur Ladezeit eines Programms geeignet.

Impressum | Webmaster | Letzte Änderungen am : 16.10.2013