Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

02.09.1983 - 

Software-Pipelining spart Rechenzeit:

Compiler unterstützt Arithmetik Prozessor

Bei Echtzeitrechnungen kommt es ebenso wie im Zeichen maximaler Ressourcenausnützung darauf an. daß eine vorhandene Hardware ihre Arbeit so schnell wie möglich erledigt. Dabei, und das sei hier am Beispiel des Arithmetik-Prozessors FPS-164 des US-Herstellers Floating Point Systems geschildert, spielt der Compiler eine entscheidende Rolle: Je besser er ein Quellprogramm zu optimieren imstande ist, desto mehr Leistung wird aus der Maschine herausgeholt.

Der optimierende Cross-Compiler APFTN-64 übersetzt Fortran-77-Programme in Objektcode für den FPS-164. Dabei berücksichtigt er besonders die Architektur des FPS-Computers, die durch eine zweistufige (Pipeline-)Additions- und eine dreistufige Multiplikationseinheit gekennzeichnet ist. Beide arbeiten mit 64-Bit-Gleitkommazahlen.

Je nach der gewählten Optimierungsstufe wird das Fortran-Quellprogram mit mehr oder weniger großem Aufwand optimiert. Dabei bearbeiten die Optimierungsroutinen elementare Programmblöcke, die aus der anfänglichen Übersetzung des Quellprogramms in eine compiler-interne Darstellung resultieren.

Auf allen Optimierungsstufen werden zunächst einmal "lokale Optimierungen" ausgeführt, wobei lokal sich auf je einen elementaren Programmblock bezieht. Dabei werden beispielsweise Ausdrücke mit konstanten Operanden schon beim Kompilieren berechnet und nur das Resultat weiterverwendet. N = 3 + 7 wird zu N = 10. Ferner werden durch Einsatz interner Register unnötige Speicherzugriffe vermieden, wie etwa im Falle der beiden Statements X = Y + Z und A = X, die so behandelt werden, daß der Wert von Y + Z einmal in X und einmal in A abgelegt wird.

Diese Optimierungen sind übrigens nicht etwa auf Sakrale beschränkt.

Schneller wird der Programmlauf auch, wenn der Compiler alle Divisionen durch ganzzahlige Potenzen von 2 (beispielsweise 64, 256 etc.) als Register-Schiebe-Operationen ausführt, wenn der Ausdruck A2 (rascher) als A mal A berechnet wird und wenn Divisionen durch reelle Konstanten in Multiplikationen mit deren Kehrwert umgewandelt werden. Von der Annahme ausgehend, daß Code innerhalb von Schleifen öfters abgearbeitet wird als Code außerhalb, befördern die Schleifen Optimierungen, wo immer es geht, den inneren Code nach draußen in einen Schleifen-Vorspann.

Statt in einer Schleife öfters die Wurzel von A errechnen zu lassen wird diese Berechnung vom Compiler nach außerhalb verlagert und bloß das Resultat in der Schleife weiterverwendet.

A muß dabei Schleifen-invariant sein, darf also beim mehrfachen Durchlauf nicht verändert werden. A braucht aber kein Skalar zu sein. Weitere Optimierungen betreffen die Behandlung von Ganzzahl-Variablen in Schleifen, die bei jedem Durchlauf um einen konstanten Betrag verändert werden, etwa die Schleifenindex-Variable selbst.

Der Compiler "bemüht" sich, alle Speicheroperationen in einer Schleife durch schnellere Registeroperationen zu ersetzen. Er hält über mehrere Basis-Blöcke des Programms hinweg skalare Variablen und Konstanten, die zu einer Schleife gehören, in Registern fest. Beim Verlassen der Schleife werden lediglich jene Register-Inhalte wieder in den Speicher transferiert, die weiterhin benötigt werden.

Software-Pipeline

Mit Software-Pipelining wird eine Optimierungstechnik bezeichnet die sich speziell die Parallel- und Pipeline-Architektur des Zielrechners zunutze macht. Dabei wird Code dergestalt (aus dem Quellcode) abgeleitet, daß die Operationen, die zu einer Iteration innerhalb einer Schleife gehören, mit Operationen anderer Iterationen überlappend ausgeführt werden. Damit kann man die "Software-Pipeline" als analoges Gegenstück der bekannten, in Hardware ausgeführten Pipelines bezeichnen, die ja auch Operationen in Teilschritten, gewissermaßen auf den einzelnen Stationen eines Fließbandes, nacheinander ausführen.

Auch Nachteile

In der Praxis sind nicht alle Fortran-Schleifen in Fließbandtechnik abzuarbeiten. So sind beispielsweise keine Aufrufe arithmetischer Unterprogramme ("Wurzel aus...") und keine Exponenten (außer 2) erlaubt Rekursionen sind jedoch zulässig Mit dem Stichwort "Rekursionen" rückt zugleich das Problem der Datenabhängikeit zwischen aufeinanderfolgenden Iterationen beim Durchlaufen der Software-Pipeline ins Blickfeld. Denn solche Abhängigkeiten können der vollen Nutzung der Pipeline, die ja simultan auf grundsätzlich voneinander unabhängigen Werten arbeitet, bestimmte Restriktionen auferlegen.

Welche Maßnahmen im Einzelfall ergriffen werden müssen, bedarf einer exakten Problemanalyse, die vom Compiler unterstützt wird.

Software-Pipelining kann nicht bloß das Arbeiten des Computers beschleunigen, es kann in gewissen Fällen auch Nachteile bringen: Arithmetische Operationen auf "nicht definierten" Daten werden beispielsweise denkbar, und ihnen muß man mit entsprechenden Vorsichtsmaßnahmen begegnen. Außerdem kann der Platz, den das Programm benötigt, durch das Pipelining größer werden und die Ausführungszeit von Schleifen mit nur wenigen Iterationen kann sich gegenüber herkömmlich optimierten Programmen verlängern.

Aber das bleibt wohl die Ausnahme, denn gegenüber früheren Versionen ohne Software-Pipelining beschleunigte sich die Verarbeitung großer Benchmark-Programme um rund zehn bis (in der Spitze) fast 90 Prozent, sagt FPS über den Nutzeffekt der neuen Compiler-Version.