Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


40. Parallele Algorithmen



Systolische Felder

Ein Problem beim perfekten Mischen besteht darin, daß die für die Zusammenschaltung verwendeten Leitungen lang sind. Außerdem existieren viele Kreuzungen von Leitungen: Bei einem Mischen mit N Leitungen tritt eine zu N2 proportionale Anzahl von Kreuzungen auf. Es erweist sich, daß diese beiden Eigenschaften Schwierigkeiten hervorrufen, wenn tatsächlich eine Maschine für das perfekte Mischen hergestellt wird: Lange Leitungen führen zu zeitlichen Verzögerungen, und Kreuzungen bewirken, daß die Verdrahtung teuer und unzweckmäßig wird.

Ein natürlicher Weg zur Vermeidung dieser beiden Probleme ist, dafür zu sorgen, daß Prozessoren nur mit Prozessoren verbunden sind, die physikalisch benachbart sind. Wie oben sollen die Prozessoren synchron arbeiten: Bei jedem Schritt liest jeder Prozessor Eingabedaten von seinen Nachbarn ein, führt eine Berechnung aus und übermittelt Ausgabedaten an seine Nachbarn. Es erweist sich, daß dies nicht unbedingt eine einschränkende Forderung ist, und tatsächlich zeigte H. T. Kung 1978, daß Felder solcher Prozessoren, die er systolische Felder (systolic arrays) nannte (da die Art des Datenflusses in ihnen an das Schlagen eines Herzens erinnert), eine sehr effiziente Verwendung der Prozessoren für einige grundlegende Probleme ermöglichen.

Als eine typische Anwendung untersuchen wir die Benutzung systolischer Felder für die Multiplikation einer Matrix mit einem Vektor. Betrachten wir als konkretes Beispiel die Matrizenoperation

Formel

Diese Berechnung soll mittels einer aus einfachen Prozessoren bestehenden Zeile ausgeführt werden, von denen jeder drei Leitungen für die Eingabe und zwei Leitungen für die Ausgabe besitzt, wie Abbildung 40.6 zeigt. Es werden fünf Prozessoren verwendet, da wir, wie nachfolgend beschrieben, in einer zeitlich sorgfältig abgestimmten Weise die Eingabedaten zur Verfügung stellen und die Ausgabedaten lesen wollen.

Abbildung 40.6
Abbildung 40.6 Ein systolisches Feld.

In jedem Schritt liest jeder Prozessor ein Eingabeelement von links, eins von oben und eins von rechts ein, führt eine einfache Berechnung aus und gibt ein Ausgabeelement nach links und ein Ausgabeelement nach rechts aus. Dabei erhält der rechte Ausgang jeweils die Eingabe von links eingegeben wurde, und der linke Ausgang erhält das Ergebnis der Berechnung, in der das linke und das obere Eingabeelement miteinander multipliziert werden und das rechte Eingabeelement hinzuaddiert wird. Ein entscheidendes Merkmal der Prozessoren ist, daß sie stets eine dynamische Transformation von Eingabedaten in Ausgabedaten vornehmen; sie müssen sich niemals berechnete Werte »merken«. (Dies trifft auch für die Prozessoren in der Maschine für das perfekte Mischen zu.) Dies ist eine Grundregel, die sich aus Einschränkungen auf der unteren Ebene der Hardware-Entwicklung ergibt, da das Hinzufügen einer zum »Speicher«-Fähigkeit (vergleichsweise) sehr teuer sein kann.

Der vorangegangene Absatz beschreibt das »Programm« für die systolische Maschine; um die Beschreibung der Berechnung zu vervollständigen, müssen wir noch genau erklären, wie die Eingabedaten eingegeben werden. Diese zeitliche Abstimmung ist ein wesentliches Merkmal der systolischen Maschine, was ein deutlicher Unterschied zu der Maschine für das perfekte Mischen ist, bei der alle Eingabedaten gleichzeitig eingegeben werden und alle Ausgangswerte zu einem späteren Zeitpunkt zur Verfügung stehen.

Das allgemeine Schema besteht darin, die Matrix über die oberen Eingänge der Prozessoren einzugeben, in einer an der Hauptdiagonale gespiegelten und um fünfundvierzig Grad gedrehten Gestalt, und den Vektor über den linken Eingang des Prozessors A, von dem aus er dann zu den anderen Prozessoren übertragen wird. Zwischenergebnisse werden im Feld von rechts nach links weitergegeben, wobei die Ausgabedaten letztendlich am linken Ausgang des Prozessors A erscheinen. Die spezielle zeitliche Abstimmung für unser Beispiel ist in Abbildung 40.7 dargestellt.

Abbildung 40.7
Abbildung 40.7 Multiplikation einer Matrix mit einem Vektor mit Hilfe eines systolischen Feldes.

Der einzugebende Vektor wird über den linken Eingang des Prozessors A in den Schritten 1, 3 und 5 eingegeben und in den nachfolgenden Schritten nach rechts zu den anderen Prozessoren übertragen. Die einzugebende Matrix wird, beginnend in Schritt 3, über die oberen Eingänge der Prozessoren eingegeben. Dabei wird sie so gedreht, daß in aufeinanderfolgenden Schritten die von rechts nach links verlaufenden Diagonalen der Matrix eingegeben werden. Der auszugebende Vektor erscheint in den Schritten 6, 8 und 10 am linken Ausgang des Prozessors A. (Im Schema erscheint dieser als der rechte Eingang eines links von A befindlichen imaginären Prozessors, der die Lösung sammelt.)

Die tatsächliche Berechnung läßt sich nachvollziehen, indem man die rechten Eingabedaten (linken Ausgabedaten) verfolgt, die sich von rechts nach links durch das Feld bewegen. Bis zu Schritt 3 liefern alle Berechnungen das Ergebnis null; nach Schritt 3 hat Prozessor C den Wert 1 als linken Eingabewert und 1 als oberen Eingabewert, so daß er das Ergebnis 1 berechnet, welches als rechter Eingabewert des Prozessors B für Schritt 4 weitergegeben wird. In Schritt 4 sind alle drei Eingabewerte des Prozessors B von null verschieden, und er berechnet den Wert 16, der dann in Schritt 5 von Prozessor A zu verarbeiten ist. Währenddessen berechnet Prozessor D einen Wert 1, den in Schritt 5 Prozessor C zu benutzen hat. In Schritt 5 berechnet dann Prozessor A den Wert 8, der in Schritt 6 als erster Ausgabewert ausgegeben wird; C berechnet den Wert 6, den B in Schritt 6 zu benutzen hat, und E berechnet seinen ersten von null verschiedenen Wert (-1) zur Verwendung durch D in Schritt 6. Die Berechnung des zweiten Ausgabewertes wird in Schritt 6 durch B vervollständigt, und der Wert wird über A zur Ausgabe in Schritt 8 weitergegeben; die Berechnung des dritten Ausgabewertes wird in Schritt 7 durch C vervollständigt, und der Wert wird über B und A zur Ausgabe in Schritt 10 weitergegeben.

Nachdem der Prozeß nun detailiert beschrieben wurde, läßt sich das Verfahren besser verstehen, wenn man es von einem etwas höheren Standpunkt aus betrachtet. Die Zahlen im mittleren Teil der Abbildung 40.7 (in Rechtecken) sind einfach eine Kopie der eingegebenen Matrix, nachdem diese gedreht und gespiegelt wurde, wie dies für die Eingabe über die oberen Eingänge der Prozessoren erforderlich ist. Wenn wir die Zahlen in den entsprechenden linken Eingängen der Prozessoren betrachten, die die Matrix empfangen, so finden wir drei Kopien des eingegebenen Vektors, die sich genau zu den richtigen Zeitpunkten an den richtigen Positionen befinden, um mit den Zeilen der Matrix multipliziert zu werden. Dann zeigen die linken Ausgänge der Prozessoren die Zwischenergebnisse für jede Multiplikation des eingegebenen Vektors und jede Matrixzeile. Zum Beispiel erfordert die Multiplikation des eingegebenen Vektors und der mittleren Zeile der Matrix die Zwischenberechnungen 1 * 1 = 1, 1 +1 * 5 = 6 und 6 + (-2) * 2 = 2, und diese Werte erscheinen als Einträge 1 6 2 (wenn man diagonal liest, einen Schritt unterhalb der mittleren Zeile der Matrix 1 1 -2). Mit der systolischen Maschine gelingt es, eine solche zeitliche Abstimmung zu realisieren, daß jedes Element der Matrix das richtige Element des eingegebenen Vektors und das richtige Zwischenergebnis bei dem Prozessor, bei dem es eingegeben wurde, »trifft«, so daß es in das Zwischenergebnis einbezogen werden kann.

Das Verfahren läßt sich in offensichtlicher Weise auf die Multiplikation einer Matrix der Dimension N x N mit einem N-Vektor unter Verwendung von 2N - 1 Prozessoren in 4N - 2 Schritten verallgemeinern. Dies kommt der idealen Situation nahe, daß jeder Prozessor in jedem Schritt eine nützliche Operation ausführt; ein quadratischer Algorithmus wird unter Benutzung einer linearen Anzahl von Prozessoren auf einen linearen Algorithmus reduziert.

Wie zuvor haben wir nur ein allgemeines Verfahren der parallelen Berechnung beschrieben. Viele Einzelheiten des logischen Entwurfs müssen ausgearbeitet werden, ehe eine solche systolische Maschine hergestellt werden kann. Aus diesem Beispiel kann man jedoch bereits ersehen, daß systolische Felder einfach und leistungsfähig zugleich sind. Fast wie durch Zauberhand erscheint am Rand der Vektor der Ausgabedaten! Doch dabei führt jeder einzelne Prozessor nur die oben beschriebene einfache Berechnung aus; der Trick liegt in der Zusammenschaltung und der zeitlich abgestimmten Eingabe der Eingangsgrößen.

Systolische Felder können, wie Maschinen für das perfekte Mischen, bei vielen verschiedenen Problemen angewandt werden, einschließlich Matching von Zeichenfolgen, Matrizenmultiplikation u. a. Ebenfalls wie bei Maschinen für das perfekte Mischen haben einige Spezialisten sogar die Verwendung dieses Musters der Zusammenschaltung für »universelle« parallele Maschinen vorgeschlagen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]