Sonderforschungsbereich 376 Sonderforschungsbereich 376
Die automatische Parallelisierung von Programmen ist eine zugleich herausfordernde wie auch lohnenswerte Aufgabe. Allgemein erfolgreich ist sie nur im Umfeld eingeschränkter Programmklassen und Zielmaschinen durchführbar. Vertreter aus der Klasse der regulären Programme sind weitestgehend aus ineinander geschachtelten Schleifen und Feldzugriffen mit affinen Indexfunktionen zusammengesetzt. Sie sind anspruchsvollen Analysetechniken parallelisierender Übersetzer zugänglich und lassen effiziente Syntheseergebnisse zu. Zugleich stellen sie Lösungsverfahren für Problemstellungen aus den Anwendungsgebieten der Technik, Biologie, Chemie und Physik bereit, wodurch sie große Bedeutung im umfassenden Bereich des wissenschaftlichen Rechnens erlangt haben. Bei den parallelen Zielmaschinen sind fundamentale Unterschiede in der Speicherorganisation, den Verbindungstopologien und Verbindungstechnologien anzutreffen. Dieser Diversität entziehen sich Cache-Speicher, die in allen modernen Zielmaschinen Verwendung finden und deren Ausprägungen sich nur in wenigen Parametern voneinander unterscheiden. Im Zentrum dieser Arbeit stehen Analyse- und Transformationstechniken, die auf die automatische Parallelisierung regulärer Programme abzielen. Sie sind für Parallelrechner mit gemeinsamen Speicher konzipiert, deren Prozessoren über Cache-Speicher vom restlichen Speichersystem entkoppelt sind.
Achtung, der nachfolgende Text stammt in unveränderter Form aus einer längeren Arbeit und wird in Kürze WWW-gerecht aufbereitet!
Die in den bisher veröffentlichten Arbeiten beschriebenen Verfahren greifen auf Modellierungen zurück, die Eigenschaften und Effekte von Cache-Speichern und Zugriffsfolgen nur angenähert erfassen. Cache-Speicher sind dafür bekannt, besonders heftig auf kleine Unstimmigkeiten zu reagieren. Der Vorteil der geringeren algorithmischen Komplexität von Approximationen ist in ihrem Umfeld deshalb häufig nutzlos und verhindert gute Transformationsergebnisse. Diese Arbeit verfolgt daher das Ziel, Eigenschaften von Cache-Speichern und Zugriffsfolgen an allen vertretbaren Stellen des Übersetzungsvorgangs exakt zu erfassen. Approximationen werden nur an nicht vermeidbaren Stellen und innerhalb von zeitlich spät angesiedelten Transformationsschritten zugelassen. In diesem Sinne grenzt sich die vorliegende Arbeit von den bisher bekannt gewordenen Arbeiten ab.
Die im Verlauf dieser Arbeit beschriebenen Übersetzertechniken wirken auf der Ebene von Schleifenstrukturen und Datenvereinbarungen. Dieser Ansatz ist durch die Beobachtung motiviert, daß Schleifentransformationen die Ausführungsreihenfolge von Schleifenrümpfen verändern und damit der Parallelisierung und Umordnung von Zugriffsfolgen dienen. Datentransformationen erhöhen hingegen die für Cache-Speicher so wichtige Lokalität, die durch Parallelisierung verlorengegangen ist oder im Originalprogramm nur schwach ausgeprägt war. Jede Gruppe ist für sich allein in der Lage, signifikante Wirkung zu erzielen, in der Kombination liegt aber das Potential für allgemein gute Transformationsergebnisse. Zugleich lassen sich beide Gruppen in einem einheitlichen geometrischen Modell behandeln, indem Schleifenschachteln und Felder als konvexe Polytope und Transformationen als Abbildungen auf diesen Polytopen aufgefaßt werden. Im Umfeld der automatischen Parallelisierung ergänzen sich Schleifen- und Datentransformationen damit auf außerordentlich wirkungsvolle Weise.
Die Analyse geht der Transformation voraus und extrahiert zunächst von der Zielarchitektur unabhängige Programmeigenschaften. Dazu zählen die Iterationsräume der Schleifen, Indexfunktionen der Feldzugriffe sowie deren Datenabhängigkeiten untereinander. Sie ergänzt diese durch Ergebnisse, die von der gewählten Zielmaschine abhängen und in dieser Arbeit auf die Parameter der verwendeten Cache-Speicher spezialisiert sind. Sie lassen sich in weiten Teilen als konvexe Polytope und linear beschränkte Verbände über den ganzen Zahlen kodieren, ergänzend kommen affine Funktionen auf mehrdimensionalen Polytopen und Verbänden hinzu. Wichtige Fragen zielen dann auf die Anzahl der ganzzahligen Punkte in diesen geometrischen Objekten. In einfachen Fällen ist die Existenz mindestens eines Punktes, in allgemeineren Fällen deren exakte Anzahl gefragt. Zwecks Beurteilung von Programmeigenschaften sind also Verfahren erforderlich, die aus Programmeigenschaften diese Punktemengen ableiten und auszählen. Sie stellen grundlegende Primitiven für die Beantwortung von Auswahlfragen in nachfolgenden Transformationsphasen dar.
Von ganz besonderer Bedeutung sind Analyseergebnisse zum Zugriffsverhalten regulärer Programme. Das herausragende Maß erfaßt die Anzahl der Zugriffe auf den Cache-Speicher, die dieser nicht durch Zugriffe auf seinen schnellen Pufferspeicher beschleunigen kann. Diese als {\em Misses} bezeichneten Zugriffe stellen innerhalb des Zeitfensters fehlgeschlagene Wiederverwendungen dar und gehen mit überdurchschnittlich langen Zugriffszeiten auf Speicherstellen einher. Ein Miss ist damit ein Synonym für eine ungünstige Situation, die vermieden werden sollte. Analyseinformationen zu Misses lassen sich ebenso als geometrische Objekte kodieren. Die überaus dynamischen Effekte von Zugriffsfolgen auf Cache-Speichern gehen so in statische Beschreibungen über. Zugriffsfolgen werden in dieser Arbeit hinsichtlich der von ihnen ausgelösten Misses bewertet. Eine Zugriffsfolge ist in diesem Sinne genau dann besser als eine andere Zugriffsfolge, wenn sie weniger Misses als diese auslöst. Bei parallelen Zielmaschinen mit lokalem Speicher ist ein Miss auf einer lokalen Speicherzelle günstiger zu bewerten, als ein Miss auf einer entfernten Speicherzelle. Maschinenparameter zur Netzwerktopologie und Verbindungstechnologie haben hier starken Einfluß, ebenso die Zuordnung von Speicherzellen zu Knoten. Diese Arbeit verzichtet darauf, derart vielfältige Parameter zu erfassen und in eine schwer handzuhabende Kostenfunktion einzuarbeiten. Stattdessen finden sich an geeigneten Stellen Hinweise auf Erweiterungsmöglichkeiten und Anknüpfungspunkte für ergänzende Optimierungen.
Die Transformationsphase setzt auf den Analyseergebnissen auf, um eine Folge von Transformationen auszuwählen und anzuwenden. Die Eigenschaften aller Feldzugriffe einer Schleifenschachtel überlagern sich und das beste Transformationsergebnis korrespondiert mit einem Kompromiß bezüglich der Optimierung einzelner Zugriffe. Die Menge der insgesamt verfügbaren Transformationen ist zu groß, als das sie sich bei der Herstellung des Kompromisses berücksichtigen ließe. Die in dieser Arbeit beschriebene Transformationsphase beschränkt sich auf eine kleine Teilmenge, die gerade groß genug ist, um allgemein gute Transformationsergebnisse erzielen zu können. Der Leitgedanke bei der Auswahl folgt der einfachen Beobachtung, daß sich einzelne Zugriffe gegenseitig stören, da sie gleiche Cache-Ressourcen beanspruchen, oder aber voneinander profitieren, da sie nutzbare Wiederverwendung implizieren. Daraus ergeben sich Empfehlungen, zwei Zugriffe in einer identischen Schleife oder aber in zwei voneinander verschiedenen Schleifenrümpfen zu plazieren um so ihre Zugriffsfolgen zu verweben oder voneinander zu trennen. In der Auswahl sind zusätzliche Transformationen enthalten, die auf die Reihenfolge der Ausführung einzelner Schleifenrümpfe wirken und damit Zugriffe innerhalb von Zugriffsfolgen umordnen.
In ihrem praktischen Teil wendet sich die vorliegende Arbeit der Beschreibung eines prototypischen Übersetzers für reguläre Algorithmen zu. Sie weist an praxisnahen Beispielen nach, daß die beschriebenen Analyse- und Transformationsschritte in einen automatisch parallelisierenden Übersetzer integriert werden können und dort signifikante Verbesserungen erzielen. Neben den beschriebenen Verbesserungen des Cache-Verhaltens sind viele weitere Optimierungen denkbar und wünschenswert. Zeitlich vorauslaufende Zugriffe auf Speicherstellen mit nicht vermeidbaren Misses eröffnen die Möglichkeit, lange Zugriffszeiten zu verdecken und stellen eine solche weiterführende Optimierung dar. Die Arbeit endet mit einer zusammenfassenden Beurteilung der erzielten Ergebnisse und diskutiert Anknüpfungspunkte für ergänzende Optimierungen.
