Die Multiplikation von Matrizen ist Bestandteil vieler Algorithmen zur Lösung komplexerer Problemstellungen. So wird diese zur Berechnung der Pfadlänge in Graphen genutzt oder zur Bestimmung erreichbarer Knoten verwendet. Hierbei wird die Multiplikation häufig mehrmals ausgeführt, sodass es ein Bestreben ist, die Laufzeit für die Multiplikation zu verringern. Zusätzlich werden Datensätze immer größer, beispielsweise Abhängigkeitsgraphen zwischen Nutzern sozialer Plattformen, wodurch die Größe der Matrizen wächst und effizientere Algorithmen benötigt werden. Neben der Möglichkeit, Algorithmen mit besserer Komplexität zu entwickeln, kann die Multiplikation parallel, also auf mehreren Prozessoren gleichzeitig, ausgeführt werden. Ein Beispiel hierfür ist die Matrizenmultiplikation nach Cannon, entwickelt von Lynn Elliot Cannon.

Algorithmen

Bearbeiten

Fox-Algorithmus

Bearbeiten

Der Fox-Algorithmus, benannt nach Geoffrey C. Fox, ist ein Algorithmus zur parallel, auf p Prozessoren gleichzeitig ausgeführten Matrizenmultiplikation. In der Entwicklung des Algorithmus wurde eine Topologie genutzt, in der die Prozessoren in einem Hyperwürfel angeordnet sind. Als Speichermodell wird das Modell des verteilten Speicher genutzt. Hierbei hat jeder Prozessor seinen eigenen privaten Adressraum und die Kommunikation zwischen Prozessoren ist nachrichtenbasiert. Der Anspruch bei der Entwicklung war es einen effizienten und einfach einzusetzenden Algorithmus, zur Nutzung in wissenschaftlichen Berechnungen, zu erstellen. Des Weiteren war es ein Bestreben einen Algorithmus zu entwickeln, der auch für zukünftige Maschinen mit vielen Prozessoren skaliert. Essentiell für den Algorithmus sind Systolische Arrays. Dieses bezeichnet ein Pipe-Netzwerk, durch welches Datenströme hindurchgetaktet werden.[1]

Beschreibung

Bearbeiten
Das Video zeigt den schematischen Ablauf des Fox-Algorithmus.

Es werden zwei  -Matrizen A und B multipliziert. Hierbei sind A und B vollbesetzte Matrizen. Die Elemente der Matrizen werden mit Hilfe der i- und j-Koordinaten in der Matrix auf die Prozessoren, die ebenfalls eine i- und j-Koordinate innerhalb des Hyperwürfel besitzen, verteilt. Somit hat zu Begin der Berechnung jeder Prozessor ein Element der Matrix A und ein Element der Matrix B.[2] Für Matrizen, bei denen gilt   erhält jeder Prozessor einen Eintrag der Matrix A und einen Eintrag der Matrix B. Für Matrizen, bei denen gilt   erhält jeder Prozessor eine Teilmatrix der Größe   von A und B.[3] Im Fall der Teilmatrizen führt jeder Prozessor eine eigene Matrizenmultiplikation der Teilmatrizen durch.

Während des Algorithmus werden die Elemente der Matrix A mittels Broadcast in den Prozessorreihen, also allen Prozessoren mit gleicher j-Koordinate, verteilt. Die Elemente der Matrix B werden an den darüber liegenden Prozessor weitergegeben. Bei Prozessoren am oberen Rand werden die Elemente an den Prozessor am unteren Ende weitergegeben.

Bei initialer Startkonfiguration hält jeder Prozessor das Element der Matrix A und B, das die gleichen Werte für die Koordinaten i und j besitzt, wie der Prozessor selbst im Hyperwürfel.

Der Algorithmus besteht aus folgenden Schritten:

  1. Broadcast der Elemente auf der Diagonalen der Matrix A an die Prozessoren mit gleicher j-Koordinate. Anschließend halten alle Prozessoren in der ersten Reihe das Element  , alle Prozessoren in der zweiten Reihe das Element  . Dieses Muster setzt sich für alle Prozessoren fort.
  2. Multiplikation des empfangenen Elements der Matrix A mit dem derzeit im Prozessor vorhandenen Element der Matrix B.
  3. Alle Prozessoren reichen ihr derzeitiges Element der Matrix B an den Prozessor in der gleichen Spalte, eine Stelle über sich, weiter. Die Prozessoren am Rand übergeben ihr Element an die Prozessoren am unteren Rand.
  4. Broadcast der Elemente auf der 'Diagonalen + 1' der Matrix A an die Prozessoren mit gleicher j-Koordinate. Anschließend halten alle Prozessoren in der ersten Reihe das Element  , alle Prozessoren in der zweiten Reihe das Element  . Dieses Muster setzt sich für alle Prozessoren fort.
  5. Multiplikation des empfangenen Elements der Matrix A mit dem derzeit im Prozessor vorhandenen Element der Matrix B und anschließende Addition des Ergebnisses mit dem Ergebnis aus der vorherigen Multiplikation.

Dieses Muster setzt sich fort, bis die Elemente von B wieder in der Ausgangsstellung sind und alle Nebendiagonalen von A verwendet wurden.[4]

Pseudocode

Bearbeiten

In Pseudocode kann der Algorithmus wie folgt implementiert werden:

FOX(A, B):
1 //Prozessoreinheit(i,j)
2  
3  
4  
5 for   {
6    PE  broadcasts a to PE(i,j) for  
7     
8    concurrently {
9        send b to PE 
10   } with {
11       receive b' from PE 
12   }
13    
14 }

Sollen zwei Matrizen der Größe   mittels   Prozessoren multipliziert werden. So erhält jeder Prozessor zwei Teilmatrizen der Größe  .

Das Muster Broadcast-Multiplikation-Rotation wiederholt sich  -mal, bis das Ergebnis feststeht.

Insgesamt hat der Algorithmus eine Berechnungszeit von  

Diese setzt sich zusammen aus den einzelnen Teilschritten:

1. Broadcast der Submatrizen der Matrix A:  
2. Rotation der Submatrizen der Matrix B um die j-Achse:  
3. Multiplikation der Submatrizen und Addition zum vorherigen Teilergebnis:  

Hierbei ist   die Zeit, um eine Gleichkommazahl zwischen Prozessoren zu übertragen,   die Startzeit um die Pipeline zu befüllen und   die Zeit für eine Multiplikation oder Addition von Gleichkommazahlen.

Die Analyse gilt für alle Maschinen, die der flynnsche Klassifikation MIMD zugeordnet werden können und das Speichermodell des verteilten Speichers haben.[5]

Ein Nachteil des Algorithmus ist die Skalierbarkeit für die Multiplikation von zwei  -Matrizen. Es können höchstens   Prozessoren benutzt werden, womit die Laufzeit in   liegt, da es   Operationen im seriellen Algorithmus sind.[6]

DNS-Algorithmus

Bearbeiten
 
Die Grafik zeigt die Matrix A, die rot eingefärbt wurde für eine bessere Wiedererkennung im Video zum Ablauf des DNS-Algorithmus.

Der DNS-Algorithmus, benannt nach Elizier Dekel, David Nassimi und Sartaj Sahni, wurde 1981 von diesen veröffentlicht. Der Algorithmus wurde entwickelt für die parallele Multiplikation von Matrizen auf general purpose Prozessoren. Der Algorithmus richtet sich an parallele Computer die der flynnsche Klassifikation SIMD zugeordnet werden können. Diese Computer haben gemeinsam, dass sie aus p verarbeitenden Elementen (processing elements) PE bestehen. Jedes dieser verarbeitenden Elemente kann die Standard arithmetischen und logischen Operationen durchführen.[7] Insgesamt können bis zu   Prozessoren benutzt werden. Diese sind hierbei in einem dreidimensionalen Hyperwürfel angeordnet. Bei   skalaren Multiplikationen folgt daraus, dass jeder Prozessor eine skalare Multiplikation durchführen muss.

Der Algorithmus wurde vor allem entwickelt, um Probleme der Graphentheorie zu lösen, beispielsweise das Finden des kürzesten Weges zwischen allen All-Pairs Shortest Path oder das bestimmen von Radius, Durchmesser und Mittelpunkt eines Graphen.[8]

Beschreibung

Bearbeiten

Es werden zwei  -Matrizen, A und B multipliziert. Diese sind vollbesetzte Matrizen. Konkret werden bei diesem Algorithmus   und damit   Prozessoren genutzt, die in einem Würfel angeordnet sind. Die Elemente der Matrizen werden mittels der i- und j-Koordinate den Prozessoren mit passenden Koordinaten innerhalb des dreidimensionalen Hyperwürfels zugeordnet. Die Multiplikation soll dann auf  -Matrizen durchgeführt werden. Die Einträge der Matrizen sind wiederum Matrizen mit der Größe  . Hierbei soll   ein Teiler von   sein.

 
Die Grafik zeigt die Matrix B, die zur besseren Wiedererkennung im Video zum Ablauf des DNS-Algorithmus gelb eingefärbt wurde.

Um Prozessoren zu adressieren, nutzen wir die Schreibweise  . Der initiale Zustand kann daher ausgedrückt werden durch  . Es befinden sich die Elemente der Matrix A auf den Prozessoren auf der Vorderseite des Hyperwürfels und die Elemente der Matrix B auf der linken Seitenfläche des Hyperwürfels. Die Prozessoren der linken vorderen Kante haben somit bereits ein Element der Matrix A und ein Element der Matrix B. Dies ist die initiale Startkonfiguration.

Der Algorithmus besteht aus folgenden Schritten:

  1. Broadcast der Matrizen A und B über die   Prozessoren. Hierbei werden die Elemente der Matrix A (befindet sich auf der Vorderseite des Würfels) entlang der j-Dimension nach hinten gesendet. Die Elemente der Matrix B (befindet sich auf der linken Außenfläche des Würfels) werden entlang der k-Dimension nach rechts gesendet. Nach Abschluss des Broadcast hält jeder Prozessor 1 Element der Matrix A und ein Element der Matrix B.
  2. Nun führt jeder Prozessor die Multiplikation der vorhandenen Elemente durch.
  3. In der letzten Phase wird die Summe der Einzelergebnisse gebildet. Dies geschieht, indem von oben nach unten die Teilergebnisse gesendet und auf dem Weg addiert werden. Nach Abschluss dieser Operation befindet sich die Ergebnismatrix auf der Bodenfläche des Hyperwürfels.

Pseudocode

Bearbeiten

Eine Implementierung in Pseudocode könnte wie folgt aussehen.

DNS(A, B):
1 store   in PE 
2 store   in PE 
3 PE  broadcasts   to PEs  for  
4 PE  broadcasts   to PEs  for  
5 compute   on PE 
6 PEs  foreach   compute   to PE 
Das Video zeigt den schematischen Ablauf des DNS-Algorithmus auf Prozessoren, angeordnet in einem Hyperwürfel.

Angenommen es sollen zwei Matrizen der Größe   mittels   und damit   Prozessoren multipliziert werden. Es gilt die Anzahl Prozessoren  .

Insgesamt hat der Algorithmus hat eine Berechnungszeit von[9]:

   
    steht für die Startup Time. Diese wird benötigt, um eine Nachricht im Sendeprozessor zu handhaben. Hierbei ist die Zeit mitinbegriffen, die benötigt wird um die Nachricht zu erstellen, den Routing-Algorithmus durchzuführen und eine Verbindung zwischen beiden Prozessoren zu etablieren.
    steht für die Transferzeit pro Wort. In diesem Fall beispielsweise die Dauer für die Übertragung eines Fließkommazahl.

Die Berechnungszeit setzt sich zusammen aus[9]:

  1 Die Broadcastoperation ausgeführt für beide Matrizen:  
  2 Die Reduktion für die Ergebnismatrix C:  
  3 Multiplikation der Teilmatrizen:  

Hieraus ergibt sich[9]:

    

Durch einsetzen der obigen Bedingung   erhält man die obige Berechnungszeit[9]:

    

Der Algorithmus ist für   oder   kostenoptimal.[10]


Bearbeiten

Einzelnachweise und Anmerkungen

Bearbeiten
  1. G.C Fox, S.W Otto, A.J.G Hey: Matrix algorithms on a hypercube I. Matrix multiplication. In: Parallel Computing. Nr. 17, 1987, S. 1.
  2. G.C Fox, S.W Otto, A.J.G Hey: Matrix algorithms on a hypercube I. Matrix multiplication. In: Parallel Computing. Nr. 1, 1987, S. 18.
  3. Vipin Kumar: Introduction to parallel computing: design and analysis of algorithms. Benjamin/Cummings Pub. Co., Minnesota 1994, ISBN 0-8053-3170-0, S. 173.
  4. G.C Fox, S.W Otto, A.J.G Hey: Matrix algorithms on a hypercube I. Matrix multiplication. In: Parallel Computing. Nr. 1, 1987, S. 19.
  5. G.C Fox, S.W Otto, A.J.G Hey: Matrix algorithms on a hypercube I. Matrix multiplication. In: Parallel Computing. Nr. 1, 1987, S. 19–21.
  6. Vipin Kumar: Introduction to parallel computing: design and analysis of algorithms. Benjamin/Cummings Pub. Co., Minnesota 1994, ISBN 0-8053-3170-0, S. 174.
  7. Eliezer Dekel, David Nassimi, Sartaj Sahni: Parallel Matrix and Graph Algorithms In: SIAM Journal on Computing Nr. 4, 1981, S. 657.
  8. Eliezer Dekel, David Nassimi, Sartaj Sahni: Parallel Matrix and Graph Algorithms In: SIAM Journal on Computing Nr. 4, 1981, S. 660.
  9. a b c d Vipin Kumar: Introduction to parallel computing: design and analysis of algorithms. Benjamin/Cummings Pub. Co., Minnesota 1994, ISBN 0-8053-3170-0, S. 177.
  10. Vipin Kumar: Introduction to parallel computing: design and analysis of algorithms. Benjamin/Cummings Pub. Co., Minnesota 1994, ISBN 0-8053-3170-0, S. 178.