Also, was wir machen wollen ist Folgendes.
Wir nehmen mal an, dass wir eine Anzahl von Prozessoren haben.
Und wir haben hier so einen Vektor.
Und die Parallelrechnung werden wir so machen, dass wir jedem Vektor
sagen, wir hätten vier Prozessoren.
Dann kriegt jeder einen Abschnitt von diesem Vektor, nämlich genau ein
Viertel.
Wenn das nicht genau teilbar ist, dann müssen wir noch darauf achten.
Wenn das nicht durch vier dividierbar ist, dann ist natürlich hier
dieser letzte Abschnitt nicht ganz so lang wie die anderen, aber das
können wir jetzt nicht ändern.
Und damit hätten wir auch die Arbeit schon einigermaßen geschickt
aufgeteilt, nämlich jeder bis auf den letzten hat genau gleich viel
Arbeit.
Wir werden dann eine Variable nutzen, die sagt Schritte pro Faden.
Das ist die Länge eines solchen Teilvektors.
Wir werden also jeder einzelne Faden für sich genommen, zum Beispiel
der Nullte hier, läuft durch diesen ersten Abschnitt durch,
sequenziell und fasst einfach die Paare zusammen und schreibt das
Ergebnis in den Vektor C.
A und B, A i plus B i wird gespeichert in C.
Und Faden Nummer eins nimmt den hier, der beginnt an Position Schritte
pro Faden minus eins.
Entschuldigung, der erste Abschnitt geht von Null bis Schritte pro
Faden minus eins.
Nullte Faden sollte ich sagen.
Der erste Faden beginnt bei Schritte pro Faden und geht bis zweimal
Schritte pro Faden minus eins.
Im Allgemeinen wird es so sein, dass wir uns die Schritte pro Faden so
ausrechnen, dass der Beginn immer ein gerades Multiplikatives von
Schritte pro Faden ist.
Und dann ist klar, wenn der Nächste auch zum Beispiel bei i mal
Schritte pro Faden beginnen, dann wird der Nächste auf i plus eins
Schritte pro Faden beginnen, das heißt wir dürfen dann maximal bis i
plus eins mal Schritte pro Faden eins weniger rechnen.
Das ist eigentlich die ganze Geschichte, die wir uns überlegen müssen,
was den Parallelalgorithmus betrifft.
Das Programmieren hierfür ist jetzt ein bisschen aufwendiger, das
werden Sie jetzt gleich sehen, da müssen wir ziemlich viel
hinschreiben, damit das geht.
Aber die Grundidee ist ausgedrückt in dieser Run-Methode, nämlich
diese Run-Methode hier, die addiert Teilvektoren im Segment von links
bis rechts.
Wir geben also dieser Run-Methode, wenn wir einen Faden starten, immer
die Grenzen.
Dann sehen Sie, hier läuft eine Schleife, die addiert A-Is und B-Is in
ein Element C-I für Is von links bis kleiner als rechts.
Das rechte Element ist ausgenommen, das heißt den werden wir also
starten mit i mal Schritte pro Faden bis i plus eins mal Schritte pro
Faden, weil er das letzte nicht mehr mitrechnet.
Das müssen wir also gar nicht weiter überlegen.
Na gut, wie setzen wir das auf?
Wir wissen ja, wir haben ein Runnable zu erzeugen, also wir nennen das
Klasse Arbeiter, Implements Runnable, da haben wir die berühmte
Mischung.
Wenn wir hier dieses Run laufen lassen wollen, braucht die Methode
natürlich das Links, das Rechts, das A, das B und das C.
Na gut, dann bauen wir uns einen Konstruktor, der kriegt das alles
geliefert als Konstruktorparameter und wir merken uns das in diesen
Variablen.
Den Code brauchen wir hier nicht durchlesen, wir wissen wie das geht.
So, eigentlich sind wir dann schon fertig.
Wir müssen jetzt nur noch die Verwaltungsarbeit machen, dass wir
ausrechnen können, wer was macht.
Wir haben hier nichts anderes als ein Arbeitgeber, Arbeitnehmer
Situation, Master Slave auf deutsch, der sagt, ich teile Arbeit aus
und warte dann, wenn sie fertig ist.
So, also wir haben A und B, das sind unsere Vektoren, das ist jetzt im
Hauptprogramm, den muss ich natürlich irgendwo anlegen, dann gibt es
hier das C, das mache ich genauso lang wie das A und ich überprüfe mit
einer Zusicherung, ob das A und das B gleich lang sind, sonst gibt es
einen Fehler, kann ich ja nicht rechnen.
So, dann sage ich mir, ich gebe mir eine Konstante hier in diesem
Falle vor, das ist die Anzahl der Fäden, die ich brauche, nehmen wir
mal 10.
In der Praxis wird das anders sein, in der Praxis wird hier eine Zahl
sein, die sie abgreifen aus dem Betriebssystem.
Da sagen sie, wie viele Prozessoren hast du denn, lieber Prozessor,
liebe Maschine, und dann nehme ich diese Anzahl und multipliziere sie
mit zwei.
Das ist so eine Faustregel, das hat mich letztes Mal schon jemand
gefragt, wie viele Fäden soll ich denn anlegen.
Na ja, so eine Faustregel ist etwa zweimal so viel, wie sie
Prozessoren haben, auch virtuelle Prozessoren, also solche, die durch
diverse Registersätze pro Prozessor implementiert sind.
Es kann sein, dass sie dann schon das Optimum haben, es kann sein,
dass sie das Optimum, müssen sie vielleicht noch ein bisschen
rumpromieren, vielleicht reicht auch 1,6 mal.
Aber das ist schon mal ein guter Wert, also das wäre ich für eine
Maschine mit fünf Prozessoren.
Wir merken uns das M, die Länge des Vektors in N, damit ich da nicht
immer A Punkt Denk schreiben muss, und dann rechnen wir Schritte pro
Faden aus.
Schritte pro Faden müssen wir natürlich ausrechnen, wir nehmen das N
her, dividieren durch die Anzahl der Fäden, ja wunderbar, geht
natürlich nicht immer auf, also machen wir es erst zu einer
Gleitkommazahl, nämlich ein Doppel und berechnen uns die Klauskammer
nach oben.
Sie können sich überlegen, warum Ceiling und nicht Floor.
Floor funktioniert nicht richtig, aber das dürfen Sie selbst
ausprobieren, warum das so ist.
Das sind also Schritte pro Faden, aber wir müssen noch darauf achten,
dass natürlich für den allerletzten die Schritte pro Faden etwas
weniger sein können.
Zum Beispiel nur eins, also da müssen wir drauf achten.
Und jetzt können wir das Programm schreiben, aber ignorieren Sie
erstmal den Text da oben, das können Sie sich nachher beim
Nacharbeiten durchlesen, das geht mir erstmal hier um das Programm.
Wir brauchen jetzt eine Mannschaft.
Das ist die Anzahl von Fäden.
Und wie viele?
Anzahl Fäden, natürlich.
Wir speichern uns die ganzen Fäden in eine Variable, die nennt jetzt
einfach die Mannschaft.
Das sind die Arbeiterfäden.
Was muss ich jetzt machen?
Na ja, jetzt muss ich den Faden starten, so viele wie ich haben will
und Ihnen die Run-Methode übergeben.
Nun, das wissen wir jetzt, wir können links und rechts ausrechnen.
Links ist I mal Schritte pro Faden, also 0 beginnt mit 0, der erste
beginnt mit Schritte pro Faden, Nummer 2 beginnt mit 2 mal Schritte
pro Faden und so weiter.
Und rechts ist jetzt auch Schritte pro Faden mal I plus 1, das kennen
wir schon, aber wir müssen darauf achten, dass wir nicht mehr haben
als N, also machen wir das Minimum aus dem Ausdruck und dem N.
Jetzt sind wir auf der sicheren Seite, für den Fall, dass der Vektor
eben nicht durch 10 dividierbar ist in der Länge.
So, gut, dann sind wir eigentlich schon fertig, machen genau das, was
wir kennen, nämlich wir erzeugen einen neuen Faden mit einem Instanz
unseres Runnable, nämlich dem Arbeiter, geben im ABC links und rechts.
Speichern das Ergebnis ab im I, Mannschaft I, wenn wir 10 Fäden haben,
habe ich jetzt Fäden von 0 bis 9, dann müssen wir nur noch eins
machen, Start aufrufen.
Ich könnte hier auch in einer Zeile schreiben, indem ich das
Startpunktstart hier einfach hinten dran hänge, Punktstart hinschreibe
und schon läuft die Geschichte los.
Na gut, dann laufen die jetzt parallel, die haben ihr Wissen, wo A, B
und C sind und so weiter und ihre Grenzen und jetzt brauchen wir nur
noch einen Threadpunktjoin aufrufen, auch wieder der Hauptfaden, der
mit Main gestartet wurde, der wartet jetzt auf die Fäden, bis sie
enden, wie macht er das?
Naja, er muss ja auf 10 Stück warten, 10 Stück hat er erzeugt, also
muss er 10 Stück bewarten, dann nehmen wir eine Schleife her, die über
die Mannschaft iteriert, die Reihenfolge ist uns eigentlich egal, aber
dieser Iterator wird es wahrscheinlich in der Reihenfolge 0 bis 9
nehmen, wenn der 0.
erst als letzter fertig wird, ist es auch egal.
Also wir müssen auf alle 10 warten und das passiert im Try-Catch-Block
und er sagt hier, die Interrupted Exception, die passieren kann, ist
unerwartete Unterbrechung beim Warten auf Arbeiter.
Okay, das war's.
Fertig.
Ist gar nicht schwer.
Da muss ich nur klar sein, ich brauche ein Runnable, das macht einen
Teil der Arbeit und ich muss so viele Instanzen dieses Runnables
erzeugen, einem Thread, einem Faden übergeben, damit die Sache
losläuft.
Und am Schluss warte ich mit einem Join.
Es gibt noch eine andere Alternative, die werden wir heute wohl nicht
mehr packen, aber man kann das auch mit einer Barriere machen.
Barriere ist ein bisschen komplizierter, aber auch nicht zu wild.
Ich kann also hier unten das Ergebnis benutzen.
So, das war also ein erstes Programm.
Ich habe noch mehr, mehr Beispiele, kompliziertere.
Aber jetzt möchte ich erst noch mal auf eine Bibliothek hinweisen,
nämlich das java.util.concurrent.
Da stehen einige wichtige Grunddatentypen, die sich bei
Parallelprogrammen gut einsetzen lassen.
Das Arbeiten mit expliziten Sperren ist nämlich doch oft
fehleranfällig oder ist nicht so richtig schnell.
Hier gibt es im java.util.concurrent gibt es mengenwertige
Implementierungen, die für Parallelverarbeitung vorbereitet sind, zum
Beispiel ein Concurrent Hashmap.
Ein Hashmap, das normalerweise, das Sie haben, ist ja für sequentielle
Programme, das kommt total durcheinander, wenn Sie das mit mehreren
Thäden bearbeiten.
Dann nehmen Sie einfach den Concurrent Hashmap, das ist eine schnelle
Implementierung und sorgt dafür, dass ja kein falsches Ergebnis daraus
kommt.
Also, es gibt Mengen, Englisch Collections, Konstrukte zur asynchronen
Ausführung, gibt es auch noch sogenannte Threadpools, da können Sie
mehrere Fäden anlegen.
Der Hintergrund dafür ist, natürlich können Sie jede Zeit, wenn Sie
einen Faden brauchen, ihn auch erzeugen.
Mit New Thread und einem Runnable, das können wir.
Nur, diese Faden erzeugen erst relativ teure Operationen.
Weil Sie da ein Betriebssystem reinmüssen, ein Betriebssystem sagen
müssen, legen wir einen neuen Faden an, suchen wir einen Prozessor, wo
es laufen kann, lege die Register an, lege den Hauptspeicher, alles
dieses Zeug, ein Keller muss dafür angelegt werden.
Darum behilft man sich, indem man sagt, ich nehme ein Reservoir von
Fäden, die ich einmal angelegt habe, und jedes Mal, wenn ich einen
brauche, dann nehme ich ihn aus diesem Fadenreservoir.
Und wenn kein zusätzlicher mehr da ist, wenn Sie alle gerade laufen,
dann gehe ich implizit in eine Wartesituation und bekomme aber den
nächsten freien Faden, also bekommen Sie damit eine schöne
Fadenverwaltung.
Das macht zum Beispiel der Threadpool.
Dann gibt es Synchronisierer.
Also, was gibt es da?
Mengen Typen.
Concurrent HashMap hatte ich schon erwähnt.
Concurrent Linked Queue, da können Sie gleichzeitig hinten und vorne
anhängen.
Es gibt Copy-on-Write ArrayLists.
Was ein ArrayList ist, wissen Sie ja.
Das Copy-on-Write bedeutet, das benutzt man dann, wenn man zwar öfters
liest, aber relativ selten schreibt, weil jedes Mal beim Schreiben
eine Kopie dieser Liste angelegt wird.
Das macht man, um zu vermeiden, dass jemand anderer, der gerade durch
die alte Liste läuft, abgebrochen wird aus irgendeinem komischen
Zustand oder dass Sie warten müssen, bis der Ablaufende aus dieser
Liste raus ist.
Copy-on-Write ist so ein typischer Parallelitätstreck, den gibt es in
anderen Stellen auch, zum Beispiel in Betriebssystemen, dass man erst
dann kopiert, wenn man muss.
Nämlich die ganze Datenstruktur, wenn sie verändert wird.
Das macht also Copy-on-Write ArrayList und Copy-on-Write ArraySet.
Dann gibt es noch einen sogenannten Volatile Modifizierer.
Volatile heißt also so etwas wie flüchtig.
Den Modifizierer können Sie Variablen-Deklarationen vorstellen, und
zwar nur primitiven Variablen, Int und Float und so etwas.
Wenn Sie eine Variable als Volatile deklarieren, dann garantiert der
Rechner dafür, dass jedes Mal, wenn die aktualisiert wird, dass sie in
allen Caches auch aktualisiert wird.
Also gewissermaßen für frei verteilt wird.
Genau genommen wird eben an anderen Stellen die entsprechende
Volatilvariable, wenn sie in der Kopie im Cache vorliegt, als Invalide
markiert, sodass sie beim nächsten Zugriff geholt werden muss.
Und das ist dann die neue Kopie.
Das löst nicht alle Probleme, aber wenn Sie zum Beispiel folgendes
machen.
Sie schreiben eine Schleife, die wartet auf eine Bullshit-Variable.
Nennen wir diese Bullshit-Variable fertig.
Sie schreiben also eine Schleife, die sagt, while not fertig, also
verneint fertig, nichts tun.
Also Sie benutzen kein Synchronized, sondern Sie benutzen eine
sogenannte Ad-Hoc-Synchronisation.
Sagen Sie, ich kann das selber programmieren.
Ich brauche diesen teuren Monitor nicht, denn in den meisten Fällen
bin ich eh der Einzige.
Diese Variable ist schon bereit, in den meisten Fällen muss ich eh
nicht warten, da will ich kein Monitor einsetzen.
Also ich prüfe einfach nach, ob eine Variable gesetzt ist auf while
und wenn sie while ist, dann arbeite ich weiter.
Andernfalls, ja, dann iteriere ich halt und ich hoffe, dass ich nicht
so lange warten muss.
So, diese Variable fertig, kann jetzt in einem anderen Faden auf einen
anderen Prozessor gesetzt werden.
Nämlich von while, von falsch auf while, von 0 auf 1.
Und auf das wartet ja der andere Prozessor.
Dieser andere Prozessor im Java, wenn Sie die Variable nicht als
Volatil deklarieren, kriegt diese Änderung nicht mit.
Ich kann also lokal diese Variable verändern, solange ich sie nicht
als Volatil markiert habe, sitzt der andere drüben und wartet in
Ewigkeit darauf, dass sich diese Variable ändert.
Normalerweise bei nicht-volatilen Variablen.
Wenn Sie Volatil davor schreiben, dann funktioniert das so, dass die
Aktualisierung sofort stattfindet.
Also sehr praktisch, aber wohlgemerkt, geht nur für eine einzelne
Variable jeweils und nicht für große Datenstrukturen.
Aktualisiert also.
Dann gibt es noch etwas Schönes, nämlich die blockierenden Schlangen.
Die blockierende Schlange ist nichts weiter als das, was wir schon
gesehen haben, nämlich den Puffer.
Letztes Mal, der ein Erzeuger und ein Verbraucher hat, der Produzent
und der Konsument, die gehen über diese blockierende Schlange und die
gibt es, die Blocking Queue heißt die.
Zunächst als Schnittstelle, die blockierenden Methoden heißen Put und
Take, der Erzeuger muss blockieren, es gibt mehrere Varianten davon
und es gibt auch zeitlich beschränkte Blockierungen möglich, da
blockieren sie und wenn die Zeit abgelaufen ist, ohne dass sie
entblockiert wurden, dann kriegen sie eine Reaktion zurück, dass sie
jetzt wieder weiterarbeiten, aber nicht erfolgreich waren.
Es ist schwer damit zu programmieren, aber man kann es machen.
Und zwar gibt es die Array Blocking Queue, Delay Queue, die Linked
Blocking Queue, das ist die verkettete Liste, Priority Blocking Queue
und Synchronous Queue.
Also das hier, die funktionieren alle so, wie ich es Ihnen gesagt
habe.
Die Synchronous Queue ist interessant, die hat nämlich, das ist ein
Puffer mit Länge 0, da können sie überhaupt nichts ablegen.
Das heißt wiederum, dass wenn sie,
wenn der Erzeuger Put aufruft, dann kann er eigentlich nichts ablegen,
sondern wartet.
Und auf was wartet er?
Er wartet auf das Ereignis, dass der Verbraucher Take aufruft.
Das heißt, es gibt einen Moment, wo beide gleichzeitig sich anmelden
an diese Datenstruktur und das nennt man ein Rendezvous.
Die müssen sich beide gleichzeitig im gleichen Zeitraum an dieser
Synchronous Queue treffen.
Wenn einer zuerst kommt, muss er natürlich warten, aber irgendwann
muss der andere kommen und dann wird die Daten automatisch
ausgetauscht und beide laufen weiter.
Ein letztes wichtiges Beispiel ist das sogenannte Semaphore oder die
Semaphore.
Semaphore ist ein älteres Wort, das kommt aus der Eisenbahnwelt,
beziehungsweise auch aus den Signalen.
Sie wissen vielleicht, wie Napoleon seine Telegramme geschickt hat, er
hatte einzelne Türme mit Zeigern drauf, die in großem Abstand, aber in
Sichtweite standen, mit denen man Signale übertragen konnte.
Natürlich kann diese Zeiger dann bestimmte Codierungen angeben und die
nannte man, glaube ich, auch Semaphore.
Ein Semaphore ist also eine Synchronisationsvariable mit einer
Warteschlange.
Nein, ich sollte sagen Wartemenge, es ist keine Reihenfolge
impliziert.
Der interessante Trick dabei ist, dass diese Synchronisierungsvariable
mit einer Anzahl Genehmigungen initialisiert wird.
Sagen wir mit 10, zum Beispiel, oder auch mit 1, oder auch mit 0.
Wenn es mit einer Anzahl Genehmigung initialisiert ist, dann kann ich
so oft Aquire aufrufen, wie diese Zahl ist.
Wenn ich zum Beispiel mit 1 initialisiere, dann kann ein Faden einmal
Aquire aufrufen, dann wird diese Semaphore heruntergezählt auf 0 und
alle weiteren Aufrufe blockieren.
Wenn er dann mit seiner Arbeit fertig ist und dann ein Release
ausführt, wird diese Anzahl wieder um 1 hochgesetzt und einer der
wartenden Fäden kann weitermachen, kommt dann gewissermaßen durch
dieses Aquire durch.
Damit kann ich also mit den Semaphoren auch einen kritischen Abschnitt
schützen.
Ich könnte also das anstelle von Synchronize benutzen, indem ich
Semaphore benutze, die mit dem Wert 1 initialisiert sind.
Die erlauben genau einen rein, wenn er rausgeht, wird wieder die 1
erzeugt.
Ansonsten ist es blockiert.
Hier wäre eine einfache Implementierung ohne zeitliche Ordnung der
wartenden Fäden.
Aquire throws interrupted exception, hier ist dieser Zähler.
Er sagt jetzt einfach, while count kleiner 0, wait.
Das kennen wir schon.
Das wait in einer Warteschlange, das sagt, solange dieser count
kleiner gleich 0 ist, warte ich.
Andernfalls zähle ich runter, das macht das Aquire, das geht also
durch, sobald der Zähler auf 1 oder auf einen höheren Wert springt und
das Release setzt wieder hoch und ruft dann ein NotifyAll auf.
Und beide dieser Methoden sind synchronized.
Und die Initialisierung ist im Konstrukt.
Semaphore hier mit einer Kapazität wird initialisiert, das ist auch
ganz einfach.
Eine Implementierung ist tatsächlich vorhanden, java.util.concurrent.
Ich sagte Ihnen schon, dass ich die Semaphore jetzt benutzen kann, um
gegenseitigen Ausschluss zu verwirklichen, also kritische Abschnitte,
ähnlich wie synchronized.
Aber wozu den Wert höher setzen?
Sagen wir auf 10.
Den Wert höher setzen kann ich zusätzlich benutzen, um Größe des
Puffers abzubilden, zum Beispiel.
Wenn ich einen Puffer habe mit 10, dann habe ich ein Semaphore, das
nenne ich freie Plätze.
Diese freien Plätze initialisiere ich zu 10.
Und jedes Mal, wenn ich in diesen Puffer etwas einschreiben möchte,
rufe ich zuerst ein Aquire freie Plätze auf.
Wenn noch welche da sind, komme ich durch diesen Aufruf hindurch.
Und dann rufe ich Aquire für den gegenseitigen Ausschluss auf, das ist
die zweite Variable.
Die ist immer auf 1 initialisiert.
Und wenn ich frei bin, rufe ich zweimal Release auf.
Ich muss dann auch noch für den Verbraucher zählen, der muss nämlich
sagen, wie viele volle Pufferplätze gibt es.
Dafür nenne ich auch eine Semaphore.
Die wird zunächst auf 0 initialisiert und jedes Mal beim Ablegen um 1
erhöht.
Kann ich also die gesamte Steuerung, die wir vorhin so mühsam gemacht
hatten mit dem Wait und Notify und wissen, wer welche Signale kriegt
und was dann alles passiert und Eintritt und Austritt, kann ich alles
erledigen, indem ich sage, einmal Aquire den Zähler für freie Puffer,
einmal Aquire kritische Abschnitt und entsprechende Release Operation
am Schluss.
Ich muss also gar nicht über Synchronize und sowas nachdenken.
Ist recht praktisch.
Letzter Punkt hier ist in diesem Abschnitt, Cyclic Barrier, eine
zyklische Barriere.
Es gibt auch eine einfache Barriere, die ist nicht zyklisch, die ist
gefährlich.
Wenn man mehrmals durchgeht, dann kommt die in einem schlechten,
dummen Zustand, ist aber schneller.
Aber das erkläre ich jetzt nicht.
So, ich sagte Ihnen vorhin, statt dem Join könnte man einen Await
aufrufen.
Eine Barriere benutzen, das geht mit dieser Await-Methode.
Jeder der beteiligten Fäden an einer Barriere, die ich übrigens mit
der Anzahl der beteiligten Fäden initialisieren muss, ruft ein Await
auf, mit dem Effekt, dass diese Fäden dann, sobald alle da sind, alle
sich angemeldet haben an der Barriere, weiterlaufen können.
Warten wir mal, bis alle da sind, dann ist die Barriere da.
Wenn alle da sind, dann können auch alle weiterlaufen.
Ich kann dann natürlich auch hier hinterher keinen Code mehr haben und
dann hören alle auf.
Dann gibt es noch eine Runnable-Methode, die können Sie der Barriere
mitgeben.
Die wird einfach aufgerufen, wenn alle da sind.
Das kann ich zum Beispiel zum Abschluss eines Parallellaufes benutzen.
Und wie gesagt, kann ich zum Start des Joins benutzen.
Interessanter ist es natürlich eher, wenn die Barriere ist eigentlich
eher dafür gedacht, dass Sie eine zyklische Verarbeitung haben, die
Sie wiederholen, aber an einer bestimmten Stelle mittendrin irgendwann
mal synchronisieren müssen.
Ich habe jetzt meine Sachen gemacht, seid ihr alles soweit, seid ihr
alles soweit, seid ihr alles soweit?
Wenn ja, dann fangen wir wieder von vorne an.
Dazu benutze ich die Barriere.
Join kann ich diese Wiederholung nicht machen, denn bei Join ist der
Faden bereits beendet.
Und Join zurückkehrt.
So, wo gibt es das?
Java Tutorial gibt es natürlich, Java Dokumentation ebenfalls, und ein
Buch gibt es auch dafür.
Aber wir haben dann noch ein paar mehr Beispiele, die zeige ich Ihnen
gleich, aber das in der nächsten Präsentation.
Okay, gibt es zu diesen Beispielen Anregungen, gibt es dazu Fragen?
Okay, ich sehe keine.
Dann schauen wir uns noch ein paar interessantere Algorithmen an,
Parallelalgorithmen.
Die sind am Anfang auch noch ganz einfach.
Jetzt noch etwa zwölf Minuten.
Also, ich werde nicht bei diesen allen Dingen jetzt den Code für Sie
vorlesen.
Ich denke, das können Sie zu Hause besser als hier in der Vorlesung.
Aber wir schauen uns erst mal einfach nur mal Matrix-Vektor
-Multiplikationen an und dann im Prinzip die Matrix-Matrix-Matrixen
-Multiplikationen.
Die numerische Integration, die lasse ich zum Schluss für Sie zum
Selbststudium.
Dann haben wir noch ein Beispiel zur Dateiindizierung und dann noch
einige drei Formeln zur Bewertung von Parallelalgorithmen.
Man möchte natürlich wissen, wie auch im O-Kalkül, was gilt hier
eigentlich für Parallelalgorithmen.
Wie schnell sind sie?
Gut, also schauen wir uns einfach mal an.
Wir haben eine N-mal-M-Matrize und einen Vektor und wollen dann
einfach eine Matrize mit Vektor multiplizieren.
Dann kommt das hier raus.
Sie nehmen also das Y und I her, nehmen das entsprechende Zeile dazu
und multiplizieren das auf und summieren die einzelnen Komponenten.
Das heißt also, Sie nehmen diesen Vektor B hier, in Gedanken legen Sie
ihn hier über die Matrize drüber, multiplizieren elementweise und
addieren das Ganze auf.
Und dann machen Sie das mit der nächsten Zeile und der nächsten Zeile.
Und ist klar, das ginge auch parallel.
Ich könnte natürlich hergehen, diesen Vektor hier allen Prozessoren
geben, das macht mein Cache automatisch, da brauche ich gar nichts
machen.
Dann kriegt jeder Prozessor eine Zeile und macht eine Multiplikation
aller Elemente.
Ich habe also dann die Arbeit hier zeilenweise aufgeteilt.
Das hier ist das Programm, aber ich zeige Ihnen noch ein paar
Alternativen.
Ich könnte es natürlich auch anders machen.
Ich könnte die Aufgabe spaltenweise aufteilen.
Das heißt also, wenn da hier drei Spalten bearbeitet werden, von drei
Prozessoren, dann müssen alle drei hier in diese Variable schreiben.
Und das wäre schlecht, denn das erfordert ein hintereinander schalten
mit einer Synchronisation, das heißt mit einem Synchronized.
Das würde die Leistung dieser parallelen Algorithmus total in den
Keller schicken.
Sie sehen, drei Prozessoren, jeder kriegt ein BI hier, ein B0, B1 und
B2.
Alle drei machen die Multiplikation gleichzeitig, das ist noch in
Ordnung, aber dann müssen sie das Zeug aufaddieren, das heißt sie
müssen ihren Wert hier drauf addieren, den muss ich dann mit 0
initialisieren, dann kommt der und dann kommt der.
Alles läuft sequenziell, bis auf die Multiplikation.
Die riefen natürlich parallel, aber dann kommt alles wieder zum
Stehen, weil wir synchronisieren müssen.
Darum ist die zahlenweise Aufspaltung schlauer.
Die zahlenweise Aufspaltung sieht so aus, sagen wir mal, es wären drei
Prozessoren gleichzeitig, an der Reihe, der hier würde die
Multiplikation durchführen und die Addition der Elemente und das
Ergebnis hier reinschreiben, und zwar nur hier, und der hier würde
sein Ergebnis da reinschreiben und der hier sein Ergebnis da.
Das heißt, es gibt dann keinen Konflikt und ich muss nicht
synchronisieren, was viel ausmacht.
Also wir hätten hier wieder einen Algorithmus gefunden, der ohne jede
Synchronisierung und ohne das Waiten und Signalisieren auskommt, nur
eben am Schluss eine Wartepunktion und natürlich am Anfang die Fäden
zu starten.
Das ist dann schon sehr geschickt.
Das haben wir schon mal gelernt.
Natürlich ist es so, dass Sie in der Regel, wo das interessant ist,
wesentlich mehr Zeilen haben als Prozessoren.
Sie können nicht einen Prozessor pro Zeile anlegen.
Nehmen Sie, Sie gehen in den LINPACK und da haben Sie, ich weiß nicht,
eine Million Zeilen und natürlich haben Sie vielleicht nicht so viele
Prozessoren.
Ich jedenfalls nicht.
Also was machen Sie?
Sie weisen natürlich den einzelnen Prozessoren ganze Streifen zu.
Also in diesem Beispiel geht es gerade so auf, dass ich acht Zeilen
habe, vier Prozessoren, also kriegt jeder zwei.
Diese Aufteilung ist genau die gleiche, wie wir bei der Vektoraddition
hatten, nur eben jetzt auf Zeilen bezogen.
Nichts dahinter, können wir sofort machen.
Sie beide, Sie quatschen.
Sie quatschen zu laut.
Sie stören mich schon die ganze Zeit.
Es gibt auch eine blockweise Aufteilung.
Ach nee, ich brauche eine andere Aufteilung.
Also schauen Sie sich mal diese Aufteilung an.
Wer sagt, dass ich immer mit Index 0 beginnen muss?
Ich kann diese Addition, also das Skalarprodukt, das hier gebildet
wird, hier mit 0 beginnen, hier mit 2 beginnen, hier mit 4 beginnen,
hier mit 8 beginnen und hier mit 10.
Dann hat das den Vorteil, dass der hier diesen Vektor von vornherein
durchstreift, während der hier bereits mit Element 2 beginnt und der
dritte eben mit Element 6 beginnt oder 5 und so weiter.
Das heißt also, Sie greifen auf diesen Vektor B gestaffelt zu.
Das ist in unserem Fall für Maschinen mit gemeinsamen Speichern nicht
so furchtbar wichtig, aber wenn dieser Vektor hier zum Beispiel auf
einer großen Maschine verteilt ausgelegt wird mit einem verteilten
Speicher, das heißt ich müsste, um diese Daten zu bekommen, immer eine
Botschaft schicken.
Wenn alle jetzt gleichzeitig mit dem Index 0 beginnen, ist der arme
Prozessor, der dieses Stückchen von B hat, von allen anderen
überlastet, weil er ihnen das B0 schicken muss und das B1.
Das vermeide ich, indem ich sage, jeder fangt an einer
unterschiedlichen Stelle an, muss dann natürlich am Schluss hier
rumwickeln und von vorne beginnen bis zu seinem Startpunkt.
Das wir keine Daten vergessen, aber damit hätten wir zum Beispiel
vermieden, dass Sie in einer Maschine, die die Daten erst verschicken
muss, alle gleichzeitig das gleiche Datum anfordern und das wollen Sie
nicht.
Das erfordert nämlich wieder eine Sequenzialisierung und sobald Sie
sequenzialisieren, ist Ihr Programm langsam.
Okay, ist das verstanden?
Ich gehe mal die Animation durch, damit Sie sehen, was passiert, dann
kommen die nächsten zwei, das heißt der greift da, der greift da, der
greift hier durch, dann wandert das nach unten und dann fangen wir
irgendwann mal, sind alle durch.
So, das hier ist der Code, der Code ist für Sie selbst zum Studieren,
da kommt auch eine Barriere drin vor, damit Sie ein Beispiel dafür
haben.
Hier ist noch ein Ausdruck, ist alles fertig hingeschrieben.
Da ist das Barriere Await, wie ich Ihnen schon sagte, wartet bis alle
Fäden diese Barriere erreicht haben.
Hier ist die Ausrechnung, hier ist das innere Produkt, das
Skalarprodukt, mein A mal das B, IJ mal BJ, das sind die ganzen
Zeilen, nicht gestaffelt.
Hier übrigens ist die Anzahl Fäden angegeben für die Cyclic Barrier,
die man anlegt und so weiter.
Bitte durchlesen, hier finde ich im Vorlesen, Code durchzulesen ist
ungeschickt, weil ich permanent hin und her blättern muss und Sie mir
sowieso nicht folgen, so richtig.
Und hier kommt ein Beispiel.
Verteilung auf vier Prozessoren, das ist das normale Rechner aus
meinem, mit nur zwei.
Matrizenmultiplikation.
Fragen zu dem Beispiel.
Matrizen, Vektormultiplikation.
Irgendwelche Fragen.
Anzahl Fäden haben wir geklärt, ungefähr doppelt so viele wie Sie
Prozessoren haben.
Barriere kommt drin vor, können Sie nachschauen, wie ich das
bearbeite.
So, jetzt machen wir etwas leicht komplexer, nämlich die
Matrizenmultiplikation.
Das ist im Prinzip nichts anderes, als was Sie gerade gemacht haben,
nämlich wir müssen Balkenvektoren der zweiten Matrize mit allen Zeilen
der ersten Matrize multiplizieren, zur Erinnerung.
Und da gibt es ein Haufen Algorithmen, die das können, da ist nämlich
die Möglichkeit, die Arbeit aufzuteilen, ziemlich unterschiedlich.
Da gibt es einen sogenannten IJK-Algorithmus, einen KIJ-Algorithmus,
einen IKJ-Algorithmus, also was ist das eigentlich alles?
Also hier zur Erinnerung, der sequentielle Algorithmus geht her, nimmt
eine Zeile hier, eine Spalte hier und bildet das Skalarprodukt.
So weit, so gut.
Das könnten wir jetzt parallelisieren, indem wir jedem sagen, du
nimmst das einem dieses hier an, wir machen das Skalarprodukt von den
Zeilen, alles gleichzeitig.
Und dann arbeiten wir uns halt durch das B sequentiell durch, das
würde ich so machen, wenn ich nicht sehr viele Prozessoren hätte.
Wenn ich aber sehr viele Prozessoren hätte, gibt es vielleicht eine
bessere Aufteilung.
Das gibt es in der Tat.
Dazu muss ich aber erst das Parallelprogramm hier anschauen.
Also jetzt müssen wir erst nochmal sequentiell arbeiten.
Also, Matrizenmultiplikation geht so, dass ich für alle Zeilen und
alle Spalten etwas mache, nämlich das Skalarprodukt von Zeile I mal
Spalte J.
Dieses Skalarprodukt steht hier, das Ergebnis ist dort, nämlich das
Skalarproduktergebnis kommt in Cij rein und das ist einfach die Zeile
A und die Spalte J.
Und das K ist in der Innerschleife variierend, also wir können das
vielleicht demnächst im Schlaf hinschreiben, diese Form der Iteration,
das ist nämlich nichts anderes als diese Formel umgesetzt.
Da steht genau das Gleiche, das Cj ist die Summe aller Produkte, Zeile
Ai und der Spalte Bj.
Was sollte ich jetzt da noch anders machen?
Was Sie noch anders machen können, ist, dass Sie die Reihenfolge
ändern können, ähnlich wie wir das vorhin gesehen hatten, wo wir
gestaffelt begonnen haben.
Aber da gibt es noch ein paar andere Tricks.
Also wir rechnen zum Beispiel das mal dem und bekommen als Ergebnis
das hier hinten.
Das ist aber blöd.
Warum ist das blöd?
Dieser Algorithmus ist sequenziell und läuft langsam.
Warum?
Denken Sie mal an die Cache-Ausnutzung.
Wir iterieren hier durch und hier durch.
Diese Elemente hier sitzen nicht hintereinander, denn diese Matrix ist
zeilenweise abgelegt.
Das heißt also, hier kommt noch ein Element, dann kommen die alle und
dann kommt erst wieder das nächste Element von dieser Spalte.
Das heißt, das fällt, wenn die Zahlen lang genug sind, garantiert aus
dem Cache raus.
Das heißt, ich muss für jedes einzelne Element einen Cache-Aussetzer
verkraften, was ja ziemlich lange dauert, im Vergleich zu dem, wie es
sein könnte, wenn die Daten im Cache sitzen würden.
Aber geht das überhaupt?
Kann ich das überhaupt schaffen?
Und interessanterweise ist die Antwort, ja, das geht.
Ich kann die Reihenfolge der Addition ändern.
Und das erfordert jetzt ein bisschen Gehirnakrobatik.
Entschuldigung, wir sind ja schon drüber, oder?
Nein, ich zeige es Ihnen noch schnell.
Gehirnakrobatik, wie hält der nach Sie?
Und zwar, also hier haben wir die IJK-Schleifenschachtelung, wie Sie
sehen.
Es ist jetzt möglich, diese Reihenfolge zu ändern.
Und zwar die Umordnung, die IJK-Schleife.
Ich tue nichts anderes, als diese Schleife, die vorher hier drin
stand, nach oben ziehen.
Dann fragen Sie, funktioniert das noch?
Interessanterweise funktioniert das noch.
Da gibt es noch eine kleine wiederholbenutzte Variable, die wird hier
rausgenommen, ein Register.
Kann vielleicht der Compiler selbst optimieren.
Aber was hier passiert, ist folgendes, dass ich immer ein A festhalte.
Und dieses A mit allen Spaltenelementen von B multipliziere.
Denn das muss ich irgendwann mal, mal kommt es bei der Spalte, mal bei
der Spalte, das ist immer das Element hier an dieser Position.
Und die Ergebnisse gehören natürlich jeweils zum Beispiel, dass das da
mal dem vierten müsste hier abgelegt werden.
Und zwar drauf addiert.
Also gehe ich einfach her und multipliziere das durch und lege die
Ergebnisse hier im C ab, additiv.
Das heißt, ich addiere immer ein Teilelement dazu.
Das heißt, ich mache nicht ein komplettes inneres Produkt, sondern ich
mache immer punktweise das innere Produkt für verschiedene Vektoren
auf der rechten Seite, nämlich von den B-Vektoren, und addiere das
Ergebnis gleich in das C rein.
Und wenn ich die alle durch habe, dann ist diese Iteration fertig.
Und siehe da, jetzt greife ich sowohl auf das B in der Reihenfolge der
Cache zu.
Das heißt, ich muss vielleicht jedes 50.
oder 20.
Element aus einem Cache-Aussetzer verkraften, bei C genauso.
Und das A-Element bleibt immer für diese ganze Iteration erstmal das
gleiche.
Das steht natürlich auch im Cache, wird dann in den Register geladen
und geht dann super schnell.
Und dann wechsle ich zum nächsten und mache das mit der Zeile und
Ergebnis.
Das ist die IKJ-Variante.
Und die eignet sich dann übrigens auch zur Paralysierung, aber das
machen wir dann nächstes Mal.
Vielen Dank.