Aufgabe 2
.tar.gz)
Bevor die Parallelisierung des Problems angegangen wird, sollte betrachtet
werden, wie die Lösung des sequentiellen Problems beschleunigt werden
kann. Denn Grundlage einer schnellen parallelen Implementierung ist meist
eine schnelle sequentielle Implementierung. Wie bereits erwähnt ist
das einzige technische Problem die Zählung der Nachbarn einer Zelle.
Gegenüber dem naiven Ansatz, zu jeder einzelnen Zelle alle acht Nachbarzellen abzuklappern und das Leben in ihnen zu zählen, ergibt sich ein hohes Optimierungspotential. So erkennt man in der nebenstehenden Grafik, daß bei zwei benachbarten Zellen vier Nachbarn (schwarz) identisch sind. Geht man von links nach rechts vor, so ist bei der Bestimmung der Nachbarn von Cell auch der Zustand von pCell bekannt, d.h. es müssen nur die Zustände der drei rechten Nachbarn neu abgefragt werden.
Die Grafik enthält bereits die im Programm verwendete Nomenklatur:
Cell
nCell
prevCol
Cell in der linken Spalte
thisCol
Cell in dieser Spalte, d.h. direkt
über und unter Cell; die Zelle selbst gehört ja
nicht zu ihrer eigenen Nachbarschaft
nextCol Cell in
der rechts folgenden Spalte, exklusive der Zelle in der gleichen
Zeile (nCell)
Mit dieser Bezeichnung berechnet sich die Anzahl der Nachbarn der Zelle
Cell einfach als
Nachbarn = prevCol + thisCol + nextCol + nCellBei der einmaligen Berechnung der Nachbarn ist bislang noch nichts gewonnen. Gespart wird erst, wenn die Berechnung weiter nach rechts fortgesetzt wird. Denn die Werte der meisten obigen Parameter im Folgezustand sind bereits bekannt:
Cell[i+1] = nCell[i]
prevCol[i+1] = thisCol[i]+Cell[i]
thisCol[i+1] = nextCol[i]
Lediglich die Werte von nextColi+1 und
nCelli+1 müssen neu bestimmt werden, was genau
drei Zugriffen auf die Speichermatrix entspricht, und damit gegenüber
8 Zugriffen ein deutlicher Gewinn ist.
Doch sogar diese drei Zugriffe lassen sich anhand der Kenntnis über den Aufbau der Bitmatrix weiter optimieren. Ein Zugriff auf eine Zelle erfolgt, indem ein Speicherwert geladen und mit einer bestimmten Bitmaske verknüpft wird, um das einzelne Bit als Zustand der Zelle zu isolieren. Ein naiver Algorithmus würde für jeden einzelnen Zugriff die Speicheradresse berechnen und die Bitmaske neu berechnen, was einem schrecklichen Haufen arithmetischer Operationen inklusive Multiplikationen entspricht, z.B. mit folgenden Makros zum Setzen, Löschen und Abfragen eines Bits an der Position (x,y) in der Matrix f:
#define BsSetCell(f,x,y) \ (*((f) + (y) * thesize.lofl + ((x)>>3)) |= (0x01 << ((x) & 0x07))) #define BsResetCell(f,x,y) \ (*((f) + (y) * thesize.lofl + ((x)>>3)) &= ~(0x01 << ((x) & 0x07))) #define BsGetCell(f,x,y) \ (!!(*((f) + (y)*thesize.lofl + ((x)>>3)) & (0x01 << ((x) & 0x07))))Wiederum läßt sich das Verfahren für den Fall, daß horizontal von links nach rechts vorgegangen wird, optimieren. Betrachten wir den Zugriff auf die Zellen
Cell und nCell
der obigen Grafik.
nCell die um
eine Position nach links geshiftete Bitmaske von Cell.
Falls sich nCell auf einer Bytegrenze befindet, so müßte
die Bitmaske neu auf 0x01 initialisiert werden.
nCell) identisch, nur die Speicherposition
ist verschieden.
Bei jeder Berechnung von nextCol und nCell werden
gegenüber obigem BSGetCell Makro drei Multiplikationen,
sechs Additionen und fünf (6-1) Bitshifts eingespart. In einer
(x,y)-Matrix, in der diese Werte über den Daumen gepeilt auch x*y
mal benötigt werden, zahlt sich die Optimierung in erheblich
verbesserter Laufzeit aus.
Wiederum wird nach dem Master-Slave-Prinzip vorgegangen, d.h. die Verteilung und Steuerung der Aufgaben findet in einem spezialisierten Master statt, während alle Berechnungen von möglichst dummen, identischen Slaves ausgeführt werden.
Zwar könnte der Master bei der Übertragung der Matrix an die Slaves jeweils eine überlappende Zeile verschicken, doch auch dies verschiebt das Problem nur um einen Berechnungsschritt. Denn nach dem ersten Schritt hat sich die Zeile 34 in Prozeß 2 verändert, und diese Veränderung muß wiederum an Prozeß 1 übertragen werden bevor der zweite Berechnungsschritt beginnen kann.
Nach jedem einzelnen Berechnungsschritt muß deshalb die letzte Zeile eines jeden Prozesses an den Nachfolger übermittelt werden, und die erste Zeile eines jeden Prozesses an den Vorgänger.
Weiterhin ist nach jedem Berechnungsschritt die Teilmatrix eines jeden Slaves an den Master zu übertragen. Gerade diese Datenmenge sollte auch einen kürzstmöglichen Weg laufen, wofür eine unidirektionale Verbindung zum Master benötigt wird. Da Prozesse andererseits auch individuelle Befehle des Masters erhalten können, wie z.B. die Festlegung der Größe einer Teilmatrix, wird die direkte Slave-Master-Kopplung ebenfalls bidirektional ausgelegt.
Unsere gewünschte Kommunikationsstruktur sieht mit dem Master M und den drei Slaves S0, S1 und S2 wie folgt aus:
cdlc.c geschrieben, welches zu einer gewünschten Anzahl von Prozessen eine fertig kompilierbare CDL-Datei erzeugt. Das Ergebnis für obiges Beispiel mit 3 Slaves sieht folgendermassen aus:
component A[i] { code master.z;
puid /Cluster/00;
streams , , , ,
<| rlo{0}, >| rli{0},
<| rli{i}, >| rlo{i},
<| mao{0}, >| mai{0},
<| mao{1}, >| mai{1},
<| mao{2}, >| mai{2}
;
}
component B[i] { code slave.z;
streams <| rli{i}, >| rlo{i}, , ,
<| rlo{i+1}, >| rli{i+1},
<| mai{i}, >| mao{i}
;
}
A{$1} [i < $1] ^^ B{i}
Komponente A repräsentiert den Master, die replizierten Komponenten B die Slaves. In der Taskforce werden keine Kommunikationsstrukturen definiert; alle Kanäle sind benannt und in den Komponentendeklarationen angegeben. Die Slaves sind von 0 bis n-1 (mit n=3) numeriert. In der Grafik sind bereits die Namen und Filedeskriptoren der Kanäle eingetragen.
Übrigens ist die Komponentendeklaration B der Slaves unabhängig von deren Anzahl. Genaugenommen tut der CDL-Generator nichts weiter als die entsprechende Anzahl Zeilen mit mai{i} und mao{i} Kanälen zur direkten Kommunikation des Masters mit dem jeweiligen Slave zur Definition der Komponente A hinzuzufügen.
Beim Anblick der Grafik fällt auch auf, daß die Kanäle vom Master zum ersten bzw. zum letzten Slave doppelt vorhanden sind. Dank der zusätzlichen Kanäle sehen die Filedeskriptoren für alle Slaves gleich aus; ansonsten müßten für den ersten und den letzten Slave Ausnahmen gemacht werden. Da in dieser Implementation die dummen Slaves noch nicht einmal wissen, ob sie die ersten oder letzten sind, werden die vier Kanäle gerne geopfert.
typedef struct {
int command; /* Typ des Kommandos */
int prozessor; /* Prozessoren-Zähler */
int steps; /* Anzahl der Berechnungsschritte */
int SurviveMin; /* Überlebensregeln des Game of Life */
int SurviveMax;
int BirthMin;
int BirthMax;
} comm;
command kann die folgenden drei Werte annehmen:
prozessor vom
Master auf 0 initialisiert. Jeder Slave merkt sich das Feld als
eigene Identifikation (auch wenn diese nirgends verwendet wird) und
erhöht das Feld um 1. Wenn der Master das Paket am rechten
Ende des Rings empfängt, enthält prozessor
die Anzahl der Prozesse im System. Dieser Befehl wird nicht nur am
Anfang verschickt; er wird gleichzeitig zur Re-Initialisierung
verwendet, d.h. nach diesem Befehl erwartet ein Slave eine neue Bitmap.
steps enthält
die Anzahl von durchzuführenden Schritten, und
SurviveMin etc. enthalten die Spielregeln, anhand derer
das Game of Life durchgeführt werden soll. Jeder Slave muß
das Paket natürlich weiterschicken, bevor er die Berechnung
startet.
Nach Abarbeitung eines GO-Befehls kann ein Slave jeden der drei Befehle empfangen. Ein weiterer GO-Befehl führt die Berechnung weiter, QUIT beendet den Slave, und COUNT stößt eine Re-Initialisierung an, in deren Verlauf der Slave auch eine neue Bitmap vom Master erhält. Dieses Prinzip enthält schon die gewünschte Optimierung, daß die Bitmap nur genau einmal vom Master zum Slave übertragen wird.
typedef struct {
int xsize;
int ysize;
int yoffs;
int length;
int lofl;
} bmsize;
Dabei enthalten xsize und ysize die Größe der Teilmatrix des jeweiligen Prozesses. yoffs enthält die vertikale Anfangsposition der Teilmatrix. In dem bereits erwähnten Beispiel mit 100 Zeilen und 3 Prozessen ist für den ersten Prozess yoffs=0, für den zweiten yoffs=34 und für den dritten yoffs=67. Dieser Wert ist für den Slave völlig uninteressant, doch wird ein identisches Paket für jeden Slave im Master gespeichert, der den Wert zur Positionierung der Teilmatrix auf dem Bildschirm braucht.
length ist die Länge der Bitmap für diesen Prozess in Bytes, d.h. die Anzahl an Bytes, die jeweils übertragen werden muß. lofl ist ein verwandter Wert für die Länge einer einzelnen Zeile in Bytes, benötigt beim Ringupdate. Beide Werte sind im Prinzip redundant, denn lofl=(xsize+7)/8, und length=lofl*ysize. Doch da die Übertragung von 12 halbwegs überflüssigen Bytes zeitlich nahezu kostenlos ist, wurde hier auf Bytediät verzichtet.
Nach Übertragung dieses Paketes allokiert der Slave genügend Speicherplatz und empfängt die Matrix.
Bei der Rückübertragung nach jedem Berechnungsschritt wird auf das Senden des "Informationspaketes" verzichtet, da sich der Master die Größe der Bitmap jedes einzelnen Slaves gemerkt hat.
Übrigens werden bei der Übertragung der Bitmaps an die Slaves (oder zurück) keine überlappenden Zeilen verschickt, dies wird durch ein direkt auf die Übertragung folgendes Ringupdate viel bequemer erschlagen.
Zum Schluß noch ein Wert: Bei dem Beispiel einer Matrix der Kantenlänge 100 Pixel, die auf 3 Slaves aufgeteilt wird, erhält jeder Slave eine Teilmatrix mit 33 (bzw. 34) Zeilen; jede zu verschickende Teilbitmap enthält 3432 (bzw. 3536) Bits beziehungsweise 429 (bzw. 442) Bytes. Die anfallende Datenmenge hält sich also in Grenzen.
Gerade bei dem Ringupdate hat es sich gezeigt, daß neben guten Algorithmus auch ein paar gute Überlegungen die Laufgeschwindigkeit und Effizienz deutlich verbessern können. Doch betrachten wir zunächst eine naheliegende Möglichkeit des Ringupdates.
Auch wenn dies noch nicht die optimale Version des Ringupdates ist, soll sie hier genau beschrieben werden. Einerseits, weil der Text schon geschrieben war als sich die Verbesserungen ergaben, und andererseits, damit der Text später auch ohne allzu viel Text noch verständlich ist.
Das Ringupdate wird abgewickelt, indem zunächst die erste Zeile eines jeden Prozesses in rechter Richtung1 durch den Ring geschickt wird, und anschließend läuft die letzte Zeile eines jeden Prozesses in linker Richtung zurück. Bildlich dargestellt spielt der Master Tischtennis mit sich selbst: Der Ball in Form einer Matrixzeile wird in den Ring geschmettert, durchfliegt alle Slaves, und bei der Wiederankunft im Master am rechten Ende des Rings wird das Datenpaket retourniert. Stören an diesem Bild tut nur, daß sich der Ball auf jedem Punkt seiner Reise ändert, schließlich schickt jeder Slave eine andere erste/letzte Zeile weiter.
Für den Slave genügen zur Abwicklung des so spezifizierten Ringupdates vier Schritte:
rlin) wird die letzte Zeile des vorherigen Slaves gelesen
rlin+1)
herausgeschrieben
rlon+1) wird die erste Zeile
des Nachfolgers gelesen
rlon)
herausgeschrieben.
Global gesehen sieht das Ringupdate wie folgt aus:
rli0) in den Ring hinein, wo diese vom
ersten Slave als letzte Zeile des Vorgängers gelesen wird.
rlin) die letzte Zeile des letzten Slaves
(und vergißt sie - sie wird nicht gebraucht). Alle Slaves
warten laut obigem "Regelwerk" jetzt vor Punkt 3.
rlon), wo sie vom letzten Slave als
erste Zeile des Nachfolgers gelesen wird.
rlo0) die erste Zeile des ersten Slaves
(und vergißt sie). Das Ringupdate ist beendet.
Das ganze hört sich wahrscheinlich noch komplizierter an als es ist. In Programmzeilen gegossen sieht der Prozeß wie folgt aus:
RECV (RING_LIN, /* letzte Zeile des Vorgängers empfangen */
BFieldCurrentAddress, /* Pointer auf 0. Zeile der Teilmatrix */
thesize.lofl, /* Länge einer Zeile in Bytes */
return 1);
SEND (RING_ROUT, /* eigene letzte Zeile nach rechts raus */
BFieldCurrentAddress+(thesize.ysize*thesize.lofl),
thesize.lofl,
return 1);
RECV (RING_RIN, /* erste Zeile des Nachfolgers empfangen */
BFieldCurrentAddress + (thesize.ysize + 1) * thesize.lofl,
thesize.lofl,
return 1);
SEND (RING_LOUT, /* eigene erste Zeile nach links raus */
BFieldCurrentAddress + thesize.lofl,
thesize.lofl,
return 1);
SEND (RING_LI0, empty_line, lofl, exit (1)); /* leere Zeile nach links raus */ RECV (RING_LII, trash, lofl, exit (1)); /* rechts zeile lesen und vergessen */ SEND (RING_LOI, empty_line, lofl, exit (1)); /* leere Zeile nach rechts raus */ RECV (RING_LO0, trash, lofl, exit (1)); /* links Zeile lesen und vergessen */Die Makros SEND und RECV machen übrigens nichts weiter als die entsprechende Funktion in PsxIO aufzurufen und zu testen, ob ein Fehler aufgetreten ist; im Fehlerfall wird eine Fehlermeldung ausgegeben und ein Befehl ausgeführt.
Es zeigt sich, daß das hin und her tatsächlich durch eine einfach Änderung des Updateprotokolls vermieden werden kann. In der folgenden Version "antwortet" jeder Slave sofort seinem linken Nachbarn mit der Ausgabe der eigenen ersten Zeile, bevor die letzte Zeile weitergeschickt wird. Das mag sich verworren anhören; im Zeitdiagramm sieht das veränderte Ringupdate folgendermassen aus:
Dieser Zustand läßt sich verbessern, indem die starre Sequentialisierung von Ringupdate und Übertragung der Bitmaps aufgegeben wird. Wird die Übertragung der Bitmap in die Mitte des Ringupdates eines jeden Slaves gestellt, ergibt sich folgende Tabelle.
Das mag sich bei drei Slaves noch nicht allzu dramatisch anhören, doch bei jedem weiteren Prozessor werden zwei zusätzliche Zeiteinheiten gewonnen. Um einen Wert zu nennen: bei dem späteren Beispiel einer Bitmap von 640x400 auf 16 Prozessoren ergibt sich eine Effizienzsteigerung von 84.2% auf 93.4%, d.h. die Menge der zu 100% fehlenden Effizienz wurde mehr als halbiert. Dafür, daß nur einige wenige Programmzeilen verschoben worden sind, ist diese Leistungssteigerung ziemlich beeindruckend.
mp-life> und das Programm wartet darauf, daß der Benutzer ein Kommando eingibt. Kommandos bestehen aus einem Namen, der optional von Parametern gefolgt wird.
help
exit
read dateiname
Dateiname sollte der Name einer Bitmapdatei im XBM Format sein. Solche Dateien haben oft die Erweiterung .xbm; diese muß mit angegeben werden! Eine schier endlose Zahl solcher Bitmaps finden sich im Verzeichnis /usr/include/X11/bitmaps. Alternativ kann man sich auch welche mit dem Programm bitmap selbst zeichnen, oder mit dem Programm xv bestehende Grafiken in das Format wandeln.
random Breite Höhe {Belegung | - }
Random erzeugt ebenfalls ein Grundbild für Life mit der Breite Breite und der Höhe Hoehe. Belegung ist ein Maß dafür, welcher Anteil der Pixel gesetzt sein soll (in Prozent, zulässig sind Werte von 0 bis 100). Gibt man statt dessen - an, so werden etwa die Hälfte aller Pixel gesetzt.
seed {Wert|-}
random verwendeten Zufallsgenerators. Dabei kann für Wert eine beliebige Ganzzahl angegeben werden. Gibt man statt dessen - ein, so wird der hoffentlich einigermaßen zufällige aktuelle Wert der Systemuhr verwendet. Nach Aufruf dieses Kommandos mit einem konstanten Wert liefert random stets die gleiche Bitmap, was zu Testzwecken sehr nützlich ist.
scale X-Skalierung Y-Skalierung
. X-Skalierung stellt die Vergrößerung in horizontaler, Y-Skalierung die Vergrößerung in vertikaler Richtung ein. Beide Werte müssen zwischen 1 und 8 liegen.
display {text|x11|off}
text erfolgen die Ausgaben auf dem Terminal, bei off werden (zur Messung der Berechnungsgeschwindigkeit) die Ausgaben ganz abgeschaltet. Der Parameter x11 schließlich veranlaßt Life dazu, die Ausgaben in einem X11 Fenster unter Benutzung von Remote X11 (RX11) vorzunehmen.
delay Verzoegerung
Verzoegerung wird die Wartezeit in Millisekunden angegeben. Ein Wert größer Null erweist sich allerdings bei größeren Bitmaps als unnötig, da die Berechnungen für genügend Verzögerung sorgen.
rules BirthMin BirtMax SurviveMin SurviveMax
BirthMin
und <= BirthMax
Nachbarzellen lebendig, so wird die Zelle geboren,
d.h. sie wird im nächsten Iterationsschritt lebendig
sein.
SurviveMin
und <= SurviveMax
Nachbarzellen lebendig, so wird die Zelle lebendig bleiben
(überleben), andernfalls wird sie für tot
erklärt.
BirthMin=3, BirthMax=3, SurviveMin=2 und SurviveMax=3 gesetzt.
run Schritte
RXReadXbmFile() liest eine XBM Datei und liefert die darin enthaltenen Daten im X11 Bitmap Format. Mit RXScaleBitmapData() können dann derartige Bitmapdaten vergrößert und mittels RXCopyBitmap() in das Ausgabefenster kopiert werden.
display off seed 42 random 640 400 - run 100 exitTrotz der abgeschalteten Ausgabe wurden die Ergebnisbitmaps immer noch brav nach jedem Einzelschritt an den Master übertragen, so daß die Ergebnisse nicht allzu realitätsfern sind. Alle Messungen fanden auf der Architektur 4x4 statt. Der Master wird auf dem Rootprozessor plaziert, die Anordnung der Slaves wurde vollständig Helios überlassen.
| Prozessoren | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Laufzeit | 560.9 | 281.2 | 188.6 | 141.4 | 113.5 | 95.2 | 82.4 | 71.8 | 64.4 | 58.0 | 53.2 | 49.0 | 45.0 | 42.2 | 39.5 | 37.5 |
| Speed-Up | 1 | 1.99 | 2.97 | 3.97 | 4.94 | 5.89 | 6.81 | 7.82 | 8.71 | 9.67 | 10.6 | 11.4 | 12.4 | 13.3 | 14.2 | 14.9 |
| Effizienz | 1 | 0.997 | 0.992 | 0.992 | 0.988 | 0.98 | 0.97 | 0.98 | 0.97 | 0.97 | 0.96 | 0.95 | 0.96 | 0.95 | 0.95 | 0.93 |
Gleichzeitig sollte nicht nur der Speedup des Programms gelobt werden. Schließlich ist auch eine hundertprozentige Effizienz ziemlich zwecklos, wenn die Grundgeschwindigkeit, gegenüber der die Effizienz gemessen wird, zum weglaufen ist. Doch auch in diesem Sinne braucht sich das parallele Programm nicht zu verstecken, das mit genügend Prozessoren unter dem Hintern auch mit einer unfair schnellen Maschine wie der Sun mithalten kann; mit der vorgegebenen sequentiellen Implementation in sunlife.c allemal. Bei großen Bitmaps erweist sich einzig die Übertragung der X11-Bitmaps vom Transputer zum X-Server als Bremse, was sich allerdings nicht in Software beheben läßt.
Ein weiterer Pluspunkt, der noch erwähnt werden sollte, ist, daß der Speicherverbrauch der Gesamtmatrix auf die Einzelprozesse aufgeteilt ist. Zwar ist dies noch nicht implementiert, doch prinzipiell bräuchte der Master nur den Speicherplatz eines Slaves zum Empfangen und Weiterleiten einer Teilmatrix. Zusammen mit dem geringen Speicherverbrauch der Bitmaps lassen sich astronomisch große Spielfelder simulieren. Jeder Slave benötigt zur Pufferung zwei Felder (ließe sich bei Bedarf auf ein einziges reduzieren), d.h. bei 2 MB pro Prozessor lassen sich mindestens 620 kB für ein Feld allokieren. Auf 16 Prozessoren stünden 9.7 Megabytes zur Verfügung, was einem quadratischen Feld mit einer Kantenlänge von 9000 Pixeln entspricht. Der Forderung der Aufgabenstellung, möglichst große Felder zu ermöglichen, sollte damit Genüge getan sein.
| Modul | Funktion | Beschreibung |
|---|---|---|
main.c
| main ()
| Startpunkt des Masters. Macht nichts weiter als die Eingabeschleife aufzurufen. |
gui.c
| MainLoop ()
| Haupteingabeschleife mit Eingabe des Benutzers. Aufgerufen
vom main() des Masters.
|
Run ()
| Beginn einer Berechnung. Die Bildschirmausgabe wird
initialisiert, und master.c:Calc() aufgerufen.
| |
master.c
| Calc ()
| Berechnungsschleife. Die Prozessoren werden gezählt, die Bitmap aufgeteilt und verschickt. Anschließend sammelt eine Schleife so oft wie vom Benutzer gewünscht die Ergebnisse ein. |
RingUpdate ()
| Wie der Name schon sagt. Ein Ringupdate (des zweiten Typs)
wird durchgeführt. Das optimierte Ringupdate befindet
sich in Calc()
| |
slave.c
| main ()
| Der komplette Slave. |
lifecalc.c
| BsNewGeneration ()
| Berechnung der nächsten Generation. Wird vom Slave aus aufgerufen. |
clcdl.c
| Erzeugung einer entsprechenden CDL-Datei. |
Frank Pilhofer <fp -AT- fpx.de> Back to the Homepage Last modified: Sat Sep 16 16:03:00 2000