Vektorarchitektur - Was einen Vektorrechner ausmacht

Einleitung:

Zukünftige CPU-Generationen werden nicht mehr die Leistungssteigerung erbringen, die man bisher aufgrund des „Gesetzes” von Gordon Moore („Moore’s Law“) auf Anwenderseite gewohnt war. Gleichzeitig steigt der Stromverbrauch wissenschaftlicher Großrechner, und ein Ende dieser Entwicklung ist nicht absehbar. Das führt zu einer Stagnation, teilweise gar Reduktion der Taktfrequenzen der Prozessoren, denn die Leistungsaufnahme steigt überproportional mit der Taktfrequenz.

Ähnlich wie in den 1970er Jahren, als der Stromverbrauch und die Kühlung der Systeme eine große Herausforderung darstellten und nicht zuletzt deshalb in den USA und in Japan Vektorrechner entwickelt wurden, hier sind besonders die Pioniere Seymour Cray [1] und Tadashi Watanabe [2] zu nennen, bedarf es heute wieder der Op-timierung der Architektur von Prozessoren, um ein Maximum an Rechenleistung für die verfügbare Chip-Technologie bei gleichzeitig hoher Energieeffizienz zu erzielen. Deshalb ist in den letzten Jahren das Konzept der Vektorisierung wieder vermehrt realisiert worden.

Datenparallelität

Vektorisierung beruht auf der Datenparallelität, welche in den meisten technisch-wissenschaftlichen Anwendungen vorliegt. Diese bringt zum Ausdruck, dass die gleiche Operation für viele unabhängig vorliegende Daten zur Erzeugung voneinander nicht abhängender Resultate durchgeführt werden muss:

Abb. 1 datenparallele Schleife in FORTRAN

Eine solche einfache Struktur mag artifiziell erscheinen, ist sie aber nicht. Viele wissenschaftliche Programme beruhen auf einer mathematischen Beschreibung eines Problems durch diskretisierte partielle Differentialgleichungen, d.h. die physikalischen Zusammenhänge werden auf allen Gitterpunkten individuell berechnet, eventuell unter Einbeziehung einer beschränkten Umgebung, und ein neuer Zustand der Variablen wird anschließend auf dem Gitter erzeugt. Letztendlich zeigt sich hier die Lokalität der Naturgesetze.

Als Resultat erhält man deshalb Schleifen, bei denen die Reihenfolge der Schleifendurchläufe mit unterschiedlichem „i“ wie in obigem Beispiel irrelevant ist: einzelne Iterationen hängen nicht voneinander ab, jede Permutation der Indizes führt zu demselben Ergebnis. Das ist „Datenparallelität“.

Pipelining

Die Berechnung beispielsweise einer Multiplikation ist nicht trivial in einem Takt zu bewerkstelligen. Stattdessen bedarf es mehrerer Schritte, sogenannter Segmente, die hintereinander durchzuführen sind. Die Anzahl der Segmente ist dabei abhängig von der Implementation.

Abb. 2 schematische Darstellung einer Recheneinheit

In einem Diagramm, beim welchem die horizontale Koordinate den Prozessortakten entspricht, die vertikale dem Segment in einer Pipeline, sieht eine Verarbeitung ohne Pipelining unter der Annahme, dass äußere Schleifeniterationen präpariert sind und nicht zu zusätzlichen Takten führen, wie folgt aus:

Abb. 3 zeitlicher Verlauf der Nutzung der Segmente

Wenn verschiedene Operationen vorliegen, das ist auch innerhalb einer Schleife möglich, kann man von der Parallelität in den Segmenten Gebrauch machen, z.B. etwas komplexer mit einer Mischung von Addition und Multiplikationen wie in folgendem Beispiel:

Abb. 4 etwas komplexere Schleife mit besserer Nutzung der Pipelines

Die beiden Multiplikationen können also, wenn alle Daten in Registern verfügbar sind, innerhalb eines Schleifendurchlaufs überlappen, während die Addition, die normalerweise in einem separaten Rechenwerk abgearbeitet wird, auf die Ergebnisse der Multiplikationen warten muss.

Abb. 5 das Zeit-Segment-Diagramm mit besserer Nutzung der Pipelines

Jedes weiße Quadrat in der Grafik stellt ungenutzte Rechenleistung und damit Energieverbrauch ohne Mehrwert dar. Offenbar ist diese Form der Abarbeitung der Schleife also nicht optimal.

Fließbandverarbeitung

Naheliegend kann man nun versuchen, unterschiedliche Schleifeniterationen so in die Pipeline zu leiten, dass die Segmente besser genutzt werden, ähnlich zur Fließbandverarbeitung in der Automobilindustrie. Schon seit vielen Jahren nutzt die Compiler-Technologie deshalb das sogenannte „Loop-Unrolling“. Für die obige Schleife wird unter der vereinfachenden Annahme, dass „N“ eine gerade Zahl ist, folgende Transformation des Codes durchgeführt, ein „Unrolling der Tiefe 2“:

Abb. 6 dieselbe Schleife mit „Unrolling der Tiefe 2“

Schematisch ergibt sich folgende Nutzung der Rechenwerke:

Abb. 7 verbesserte Auslastung der Rechenwerke

Leider wird diese vergleichsweise gute Auslastung realistisch nicht zu erreichen sein. Erstens bedarf es zusätzlicher Operationen für jeden Schleifendurchlauf, um überhaupt die Rechenwerke nutzen zu können, und zweitens werden meist nicht genügend Daten in den Registern verfügbar sein. Speziell die Bandbreite zwischen Speicher und Prozessor ist seit Jahrzehnten das dominierende Thema im Supercomputing.

SIMD

Um eine schnellere Rechenleistung und bessere Energieeffizienz zu erzielen, kann man nun eine Hardware-Architektur ebenfalls inhärent parallel entwerfen und entsprechende Instruktionen generieren, welche mehrere Schleifendurchläufe auf einmal abbilden und durch parallele Rechenwerke die notwendigen Operationen gleichzeitig abarbeiten. Natürlich benötigt dieses Vorgehen auch Register, die so viele Daten gleichzeitig enthalten können, wie es der Parallelität der Rechenwerke entspricht.

Abb. 8 zweifach parallele Pipeline mit entsprechenden Registern

Der Vorteil liegt in der Tatsache, dass viele zusätzliche Operationen, wie beispielsweise die Verwaltung von Adressregistern, Aktualisierung von Iterationszählern etc., nur einmal für mehrere Rechenoperationen anfallen. Zusätzlich müssen für jede Rechenoperation die Datenpfade des Prozessors so konfiguriert werden, dass die Input-Daten von Registern zur Recheneinheit und die Resultate in Ergebnisregister geleitet werden. Diese Maßnahmen kosten Zeit und Energie. Wenn die eigentliche Berechnung also parallel für mehrere Schleifeniterationen durch eine Instruktion durchgeführt werden kann, so reduziert sich in der Aufwand pro Iteration.

Naheliegend nennt man diese Parallelisierung SIMD, „single instruction multiple data“. Die Multiplizität der parallelen Operationen in der Hardware wird auch als „SIMD-Breite“ bezeichnet. Diese liegt bei den heutigen Mikroprozessoren typisch im Bereich zwischen zwei und acht Operationen, bei bekannten Grafikprozessoren im Bereich von 32, bei heutigen Vektorrechnern bei 256.

Prinzip des Vektorrechners

Der entscheidende Unterschied zwischen SIMD-Instruktionen skalarer Architekturen und einem wirklichen Vektorrechner ist das sogenannte Vektorregister, eine Hardware, welche über einen bestimmte Anzahl von Prozessortakten ein Datum, oder je nach Architektur parallel eine gleichbleibende Menge von Daten, pro Takt an die Rechenwerke senden bzw. von diesen empfangen kann. Die Analogie zur Fertigungsstraße in der Automobilindustrie drängt sich einmal mehr auf. Im Vergleich dazu enthalten SIMD-Register skalarer Architekturen eine bestimmte geringe Anzahl von Daten, können diese aber nur zu einem Zeitpunkt aufnehmen oder zur Verfügung stellen. Die Auslastung der Rechenwerke wird durch die Vektorisierung verbessert:

Abb. 9 Zeit-Segment Diagramm bei Nutzung eines Vektorregisters

In diesem Beispiel beträgt die Länge des Vektorregisters 32. Die zusätzlich auftretenden, unvermeidbar zu jeder Schleife gehörenden und oben erwähnten zusätzlichen Operationen sind parallel während der Aktivität des Rechenwerkes leicht zu bewältigen. Dies ist ein nicht immer beachteter Vorteil einer Vektorarchitektur: es gibt hinreichend Zeit bzw. Prozessortakte, bestimme Dinge zu verstecken, sozusagen die „Administration“ der Schleife, während die gewünschten Fließkommaoperationen ausgeführt werden.

Moderne Vektorsysteme beherrschen natürlich auch das dynamische Umordnen von Operationen abhängig von der Verfügbarkeit der Ressourcen wie Register und Rechenwerke. Diese besondere Eigenschaft wurde in der Vergangenheit besonders vom japanischen Entwickler Tadashi Watanabe in Vektorrechnern implementiert. Ebenso ist es durchaus möglich, schon im Zielregister verfügbare Resultate für weitere Berechnungen an eine andere Recheneinheit weiterzuleiten, bevor dieses Zielregister vollständig von der laufenden Vektorinstruktion gefüllt worden ist, das sogenannte „Chaining“, welches von Steve Chen [3] für die Cray X-MP erstmalig implementiert wurde.

Wie in dem Zeitschema deutlich zu erkennen ist, führt die „Latenz“ der Pipeline von in diesem Beispiel sechs Takten noch zu ungenutzten Segmenten. Auch dieses kann vermieden werden, indem weitere Vektorbefehle schon abgesetzt werden, zum Beispiel im gegeben Fall der nächste Schleifendurchgang von 32 Iterationen, bevor die vorherige Vektoroperation beendet ist.

Die beiden Methoden der Hardware-Unterstützung für Datenparallelität können kombiniert werden, indem Vektorregister mehr als ein Datum pro Takt zur Verfügung stellen oder aufnehmen können, dieses über eine bestimmte Anzahl von Prozessortakten und durch eine einzige Instruktion gesteuert, und die Rechenwerke entsprechend mehrfach ausgelegt werden, ähnlich wie bei den heutigen skalaren Architekturen.

Um eine datenparallele Schleife auf eine Vektorarchitektur abbilden zu können, wird die Schleife in Stücke der Länge des Vektorregisters VL zerlegt, man nennt das „Stripmining“:

Abb. 10 schematische Darstellung der vektoriellen Ausführung in FORTRAN

Dabei wird der kursiv notierte Teil des Codes auf einzelne Vektorbefehle abgebildet, die inneren Schleifeniterationen finden nur in der Hardware statt. Während die Vektoroperationen durchgeführt werden, kann die CPU den nächsten Durchgang vorbereiten. Hier wird der Vorteil der Vektorisierung erneut deutlich: Es sind weniger Instruktionen notwendig, und diese können sehr gut zeitlich überlappen. Wenn man auf einer Vektormaschine ein Programm optimiert, dann wird die Rechenleistung gemessen in Fließkommaoperationen pro Sekunde verbessert, gleichzeitig nimmt aber mit zunehmender Vektorisierung die Anzahl der Instruktionen pro Sekunde ab!

Vergleiche

Dieses Faktum adressiert teilweise den oft gehörten Vorwurf, dass ein Vektorprozessor auf skalarem Code vergleichsweise schwach agiert. Zunächst ist das richtig, die Steuerung des Prozessors muss zu jedem Zeitpunkt alle Ressourcen überwachen, deren Verfügbarkeit überprüfen und entsprechend umordnen, und das eben nicht nur für die ebenfalls vorhandenen skalaren Register und Pipelines. Der Aufwand dazu ist groß, und der „skalare Teil“ eines Vektorprozessors ist kein für skalaren Code optimierter Prozessor. Das Rechenwerk der kommerziell verfügbaren Vektorarchitektur, der NEC SX-Aurora TSUBASA, ist 32-fach parallel. Die für eine vergleichbare Rechenleistung notwendigen Alternativen wären eine skalare CPU mit extrem hohem Takt, welcher mit heutiger Technologie nicht realisiert werden kann, oder ein Grafikprozessor, der ein ähnliches Maß an Parallelität realisiert, dabei aber besondere Programmierparadigmen benötigt.

Code-Strukturen

Der Nutzer muss also seinen Code vektorisieren. Das sollte er aber heutzutage für eine effiziente Nutzung anderer Architekturen ebenso. Dabei muss die Vektorlänge der Schleifen die Vektorregister der Länge 256 auch zumindest einigermaßen ausnutzen, man braucht also im Vergleich zu den heute vorrangig vertretenen „skalaren Architekturen mit SIMD-Instruktionen“, ein Oxymoron übrigens, längere Schleifen. Das führt unmittelbar zu der Frage, ob die wissenschaftliche Problemstellung eine entsprechende Dimensionierung erlaubt.

Heutige Problemstellungen im technisch-wissenschaftlichen Bereich sind mehrdimensional und schlicht groß, d.h. die zugrundeliegenden Gitter enthalten viele Gitterpunkte oder es werden viele finite Elemente benutzt. Zunächst ist damit die Voraussetzung für eine effiziente Vektorisierung, die Existenz langer vektorisierbarer Schleifen, strukturell vorhanden. Viele moderne Codes enthalten allerdings kurze innere Schleifen in Schleifennestern, z.B. für Diskretisierungsverfahren hoher Ordnung. Jedoch sind äußere Schleifen, die sich über ganze Gitter oder eine große Anzahl finiter Elemente oder Volumen erstrecken, dann ebenfalls existent.

Die heutigen typischen Codestrukturen spiegeln oft auch eine Cache-Optimierung wider. Die kurzen Schleifen, welche Nachbarschaftsbeziehungen ausdrücken, ermöglichen eine gute Cache-Nutzung. Diese kann man aber auch anders erzielen, und zunehmend ist es ohnehin notwendig, zum Zwecke optimaler Leistung für einen Vektorrechner notwendige Umstrukturierungen auch für heutige skalare Architekturen in Betracht zu ziehen.

Konzeptionell ist dies die bekannte Thematik, ob man ein „Array of Structures“ bearbeitet oder den dem hardware-nahen SIMD-Gedanken mehr entsprechenden Weg der „Structure of Arrays“ verfolgt. Selbst in Optimierungskursen für skalare Architekturen wird letzteres empfohlen.

• Skalares Denken: Es gibt einen Gitterpunkt, finites Volumen oder Element, ein Teilchen. Welche Operation ist darauf anzuwenden?
• Vektor-Denken: Es gibt eine auszuführende Operation. Auf welche Gitterpunkte, auf welches finite Volumen, Element oder Teilchen kann diese Operation unabhängig angewandt werden?

Auf dem Vektor-Denken basieren letztlich auch zahlreiche neuere Initiativen, „Domain-Specific Languages“ zu entwickeln. Dabei kommt ja gerade zum Ausdruck, dass man z.B. den Gradienten eines physikalischen Feldes ausrechnen will und eben nicht den Gradienten an einem Gitterpunkt. Es sind die Gitter und die auf diesen definierten Variablen, die die diskretisierte Abstraktion der in der mathematischen Beschreibung auftretenden physikalischen Felder darstellen. Der Gitterpunkt selbst und der auf diesem vorliegende Wert einer Variablen hat in diesem Sinne keine Bedeutung.

In vielen Fällen können moderne Compiler die fast immer vorhandenen, durch „moderne Programmiertechniken“ aber oft nicht leicht erkennbaren, äußeren Schleifen für eine Vektorisierung nutzen. Die Code-Struktur kann also für eine gute Vektorisierung angepasst werden. Das setzt aber manchmal vertiefte Kenntnisse des Codes und der Verfahren voraus. Anwender haben diese Kenntnisse immer, Computerhersteller selten und nur eingeschränkt.

Schlussfolgerung

Aufgrund der derzeitigen Stagnation der Leistungsfähigkeit einzelner Rechenkerne gängiger CPU-Architekturen ergibt sich die Notwendigkeit, jegliche in der Problemstellung vorhandene Parallelität effizient zu nutzen, speziell auch die feingranulare Datenparallelität. Vektorisierung als Programmierungsparadigma und Vektorarchitekturen als eine Hardwarerealisation gewinnen deshalb zunehmend an Bedeutung. Ein Programm durch Veränderung der Strukturen, auch der Datenstrukturen, effizient zu vektorisieren und so eine hervorragende Leistung der einzelnen Prozesse zu erreichen, ist vergleichsweise einfach, wenngleich nicht immer ohne Aufwand zu erzielen.

Referenzen

1. https://de.wikipedia.org/wiki/Seymour_Cray
2. https://de.wikipedia.org/wiki/Tadashi_Watanabe
3. https://en.wikipedia.org/wiki/Steve_Chen_(computer_engineer)

Autor & Copyright

Rudolf Fischer
NEC Deutschland GmbH,
Fritz-Vomfelde-Straße 14, 40547 Düsseldorf
E-Mail

© Springer-Verlag Berlin Heidelberg 2018