MUSIC: Architektur

Für eine Beschreibung der Architektur verweisen wir auf [MuArchi].

Performance eines Prozessors

Algorithmen der linearen Algebra haben zu einem grossen Teil das gleiche Schema für den Datenzugriff:

• pro Element werden zwei Operationen ausgeführt
• es werden zwei Operanden benötigt und ein Resultat abgespeichert
• jedes Element wird nur einmal berechnet

Dies bedeutet, das für zwei Floating Point Operations drei Speicherzugriffe nötig sind. Typische Algorithmen, die diese Bedingungen erfüllen, sind zum Beispiel der SAXPY und der SGEMM, die die innersten Schleifen von SGEFA bzw. SGETRF bilden.
Der DSP 96002 von Motorola, der im MUSIC verwendet wird, arbeitet mit 40 MHz. Er kann eine 32 bit Floatingpoint (single precision) Multiplikation, Addition und Subtraktion plus zwei Speicherzugriffe in einem Befehl (2 Zyklen) ausführen. Für den SAXPY und den SGEMM Algorithmus würde dies eine Performance in der innersten Schleife von 20 Mflop/s bedeuten. Durch die Einschränkung, dass die parallelen Speicherzugriffe über zwei verschiedene Speicherports (X und Y-Memory) erfolgen müssen, erhalten wir eine Performance von 13.3 Mflop/s. Dies kann jedoch umgangen werden, indem ein Operand vorher in den prozessorinternen Speicher kopiert wird. So sind wieder theoretische 20 Mflop/s erreichbar. Liegen jedoch ein Operand und das Resultat im dynamischen Speicher, benötigt der DSP 96002 drei Zyklen für den Speicherzugriff. Somit erhalten wir wiederum nur 13.3 Mflop/s Performance in der innersten Schleife. Siehe auch 8.2.3 auf Seite

 
Tabelle 4.1: LINPACK und LAPACK Performance in Mflop/s auf einem DSP 96002. Optimierte Version ohne Kommunikationsoverhead. 

Tabelle 4.1 zeigt unsere Performance-Messungen für die LINPACK Routine SGEFA und die LAPACK Routine SGETRF. Die innersten Schleifen (SAXPY bzw. SGEMM) sind in Assembler geschrieben.
Tabelle 4.1 zeigt auch den Vergleich zwischen LINPACK und LAPACK: Für kleinere Gleichungssysteme ist der LAPACK-Algorithmus überlegen, für grössere eignet sich LINPACK besser. Diese Aussage lässt sich jedoch nicht auf andere Prozessoren übertragen, sie wird im wesentlichen durch die Speicherarchitektur bestimmt. Ein System mit Cache oder nur einem Speicherport würde sich ganz anders verhalten. Beim LINPACK Algorithmus können die in den internen Speicher kopierten Daten länger verwendet werden, deshalb lohnt sich das Umkopieren für grössere Systeme mehr.

Kommunikation

Für eine ausführliche Beschreibung der Kommunikationsarchitektur siehe [MuArchi] und [MuTutor].
Die intelligente Kommunikation erlaubt es, bis zu dreidimensionale Datenfelder neu zu verteilen. Die Kommunikation erfolgt mit einer Latenzzeit von ca. 100 und einer Bandbreite von 5 MHz mal 32 bit = 20 MByte/s. Die Kommunikation kann parallel zur Rechnung erfolgen und belastet den Prozessor nicht.
Bei der SGEFA Routine tauscht derjenige Prozessor, der die aktuelle Zeile hat, diese mit demjenigen, der das Pivot hat, aus. Diese Kommunikation lässt sich effizient auf alle Kommunikationsstrukturen abbilden. Die Routine SGETRF hingegen sendet eine Spalte an jeweils alle Prozessoren (broadcast to all). Diese Kommunikationsart ist bei einem Messagepassingsystem sehr ineffizient, da die Latenzzeit der Kommunikation proportional zur Anzahl Prozessoren ist. Bei der MUSIC-Architektur hingegen ist die Kommunikationsdauer unabhängig von der Anzahl Adressaten. Tabelle 4.2 zeigt eine Zusammenstellung von Kommunikationsbandbreite und Latenzzeit für einige System.

 
Tabelle 4.2: Latenzzeit und Kommunikationsbandbreite verschiedener Systeme.  

 

Load Balancing

Unter Load Balancing versteht man die Verteilung der Arbeit auf die einzelnen Prozessoren. Ziel ist es, die Arbeit so zu verteilen, dass alle Prozessoren regelmässig ausgelastet sind, und die Rechenzeit damit minimiert werden kann. Für viele Berechnungen ist es nicht sinnvoll, ein Datenfeld einfach entlang den Spalten oder Zeilen aufzuteilen. Anstelle einer fortlaufenden Verteilung ist es oft sinnvoll, die Daten zum Beispiel versetzt zu verteilen (wrap genannt). Dies kann mit der MUSIC-Kommunikationsarchitektur für ein zweidimensionales Datenfeld einfach durch die Einführung der dritten Dimension erfolgen. Sind die Daten dann allerdings dreidimensional verteilt, ist es schwer, sie wieder zweidimensional umzuverteilen, da für jeden Kommunikationszyklus die Anzahl der produzierten Elemente in einer Dimension gleich der Anzahl der konsumierten in dieser Dimension sein muss. Bei einer Kommunikation Host-MUSIC hingegen muss nur die totale Anzahl Elemente übereinstimmen. Wird also eine -Matrix als verteilt, sind DimZ Kommunikationszyklen nötig um wieder zu ``entwrappen''.