Vergleich von Message Passing und Distributed Shared Memory

Transcrição

Eidgenössische Technische Hochschule Zürich
Institut für Computersysteme
Vergleich von Message Passing und
Distributed Shared Memory unter Windows NT
SendAsync
SendSync
success/
pending/
error
RecvSync
success/
pending/
error
no
success/
error
Zero Copy Layer
Ready?
CheckRequests
CallBack
pending/
error
Send
List
yes
Recv
List
Ready
yes
no
yes
Ready?
no
Norm?
AsyncRecv
success/
pending/
error
SendDone
NwCheckRequests
done
Sending List
Request
Reply
Controll
Network Layer
NwSendSync
success/
pending/
error
SyncRecv
Eine Diplomarbeit
von Roman Roth
WS 1998/99
Professor: Prof. Thomas M. Stricker
Assistent:
Christian Kurmann
Seite 2
ETH Zürich
Diplomarbeit von Roman Roth
ETH Zürich
Zusammenfassung
Immer leistungsfähigere PCs und Workstations und immer schnellere Netzwerke ermöglichen
immer breitere Einsatzgebiete für PC-Clusters. Doch sehr oft leidet die Performance der Hardware
unter der eingeschränkten Leistung der Software. Diverse Studien haben gezeigt, dass meist die
Kopiervorgänge, die in konventionellen Kommunikationsmodellen vorkommen, für die schlechte
Leistung der Software verantwortlich sind. Gefordert ist also sogenannte Zero-CopyKommunikation, das Senden von Datenpaketen aus dem Speicher des Senders direkt in den
Speicher des Empfängers also.
Zero-Copy ist jedoch nur dann möglich, wenn Hardware und Betriebssystem dies aktiv
unterstützen. Auf seiten der Hardware müssen Techniken wie Direct-Memory-Access oder DeviceSpeicher vorhanden sein. Diese Techniken müssen durch das Betriebssystem effizient eingesetzt
werden können. Eine Untersuchung der Kernel-Strukturen von Microsoft Windows NT 4.0 hat
gezeigt, dass dieses Betriebssystem alle Funktionalitäten bietet, die eine effiziente Implementation
von Zero-Copy-Kommunikation fordert.
Diese Arbeit sollte eigentlich auf einem Myrinet-Netzwerk unter Windows NT basieren. Um das
aufwendige Schreiben von Kernel-Mode-Treibern zu umgehen, wollte man auf das GM-API von
Myricom aufgebauen. Leider stand im Verlaufe der Arbeit keine lauffähige Version zur Verfügung.
Deshalb wurde die Zero-Copy-Kommunikation zuerst in der Theorie betrachtet. Das eigentliche
Senden und Empfangen wird von der Hardware bzw. von Software wie GM übernommen. Das
Problem liegt viel mehr in der Frage, wohin wird empfangen? Grundsätzlich können zwei
unterschiedliche Kommunikationsarten zum Einsatz kommen:

Der Empfänger stellt immer genügend Speicher für den Empfang zur Verfügung, so dass der
Sender jederzeit senden kann. Diese Kommunikationsart eignet sich nur für kleinere Pakete.

Der Empfänger teilt dem Sender seine Empfangsbereitschaft für jedes Datenpaket mit. Es wird
also synchronisiert. Dies lohnt sich nur für grössere Pakete.
Diese beiden Kommunikationsarten sind in einem sogenannten Zero-Copy-Layer implementiert
worden. Dieser Layer wurde netzwerktechnologieunabhängig entwickelt. Zwischen den Layer und
dem Netzwerktreiber oder -API wurde ein Netzwerk-Layer geschoben, der die netzwerkabhängigen
Teile der Zero-Copy-Kommunikation enthält. Mangels einer lauffähigen GM-Version wurden zwei
Netzwerk-Layer implementiert, die an sich nichts mit Zero-Copy zu tun haben, jedoch stabile und
(im ersten Fall) lokal ebenso schnelle Kommunikation erlauben: Es handelt sich um Named-Pipes
und Windows Sockets.
Diese Arbeit hat gezeigt, dass sich unterschiedliche Kommunikationsmodelle wie MessagePassing und Distributed-Shared-Memory durchaus auf einen solchen Zero-Copy-Layer aufbauen
lassen. Die Differenzen der Anforderungen der beiden Modelle an die Schnittstelle zum Zero-CopyLayer sind äusserst gering, so dass eine Schnittstelle definiert werden kann, die von beiden
Modellen benutzt werden kann.
Dies beweisen die Implementation von zwei Prototypen, die im Rahmen dieser Arbeit entwickelt
wurden. Für das Message-Passing wurde eine Minimalimplementation von MPI erstellt. Diese
enthält sowohl blockierendes wie nicht-blockierendes Senden und Empfangen, sowie eine Barrier.
Studien haben gezeigt, dass die kollektiven Kommunikationsformen von MPI durchaus auf den
implementierten Punkt-zu-Punkt-Funktionen effizient aufbauen können.
Als Schnittstelle für einen Distributed-Shared-Memory-Prototypen wurden Teile von OpenMP
verwendet. Der Prototyp enthält einen lauffähigen Memory-Manager, der nach dem Prinzip der
Lazy-Release-Consistency von TreadMarks funktioniert. Auf Multi-Writer-Funktionalität, wie sie
TreadMarks enthält, wurde auf Grund von Widersprüchlichkeit mit der Zero-Copy-Kommunikation
verzichtet.
Messungen der Bandbreiten und Latenzzeiten (über Named-Pipes) haben gezeigt, dass der ZeroCopy-Layer durchaus eine leistungsfähige Variante für echte Zero-Copy-Kommunikation sein kann.
Zwei konkrete Applikationen, die für die beiden Prototypen geschrieben wurden, zeigen, dass der
MPI-Prototyp vernünftig einsetzbar ist. Der OpenMP-Prototyp jedoch ist für gewisse Probleme zu
wenig mächtig. Die Leistungsfähigkeit liesse sich durch entsprechende Erweiterungen jedoch
erheblich steigern.
Seite 3
Seite 4
ETH Zürich
ETH Zürich
Inhaltsverzeichnis
1 Einleitung.........................................................................................................................9
2 Zero-Copy-Kommunikation .........................................................................................11
2.1 Die unsynchronisierte Kommunikation kleiner Pakete ......................................11
2.2 Die synchronisierte Kommunikation grosser Pakete.........................................12
2.3 Der Zero-Copy-Layer in der Theorie .................................................................12
2.4 Ein alternativer Ansatz für Zero-Copy-Kommunikation .....................................14
2.4.1 Fehlende Unterstützung durch Windows NT .......................................14
2.4.2 Fehlende Unterstützung durch höhere Layer ......................................14
3 Zero-Copy unter Windows NT 4.0 ...............................................................................17
3.1 Die Windows NT 4.0 Kernel-Architektur............................................................17
3.2 Das Windows NT Interruptmodell......................................................................18
3.3 Die Windows NT-Treibermodelle.......................................................................18
3.3.1 Das generische Treibermodell .............................................................18
3.3.2 Das NDIS-Modell..................................................................................20
3.3.3 Beurteilung aus der Sicht von Zero-Copy ............................................21
3.4 Das Speichermanagement von Windows NT 4.0..............................................21
3.4.1 Datenstrukturen und System-Threads .................................................21
3.4.2 Beurteilung aus der Sicht von Zero-Copy ............................................23
4 Die Schnittstellen zum Message-Passing- und DSM-Layer .....................................27
4.1 Die Schnittstelle zwischen Message-Passing- und Zero-Copy-Layer...............27
4.1.1 Punkt-zu-Punkt-Kommunikation...........................................................27
4.1.2 Kollektive Kommunikation ....................................................................29
4.1.3 Synchronisation....................................................................................30
4.1.4 Die Schnittstelle....................................................................................30
4.2 Die Schnittstelle zwischen DSM- und Zero-Copy-Layer ...................................31
4.2.1 Der Page-Request................................................................................31
4.2.2 Der Page-Reply....................................................................................32
4.2.3 Synchronisation....................................................................................32
4.2.4 Die Schnittstelle....................................................................................33
4.3 Ein Vergleich der Schnittstellen.........................................................................33
5 Der Zero-Copy-Layer ....................................................................................................35
5.1 Die Requests .....................................................................................................35
5.2 Die Abläufe ........................................................................................................36
5.2.1 Initialisieren der Layer und Erstellen der Verbindungen ......................36
5.2.2 Call-Back-Funktion ...............................................................................36
5.2.3 Asynchrones Senden und Empfangen.................................................37
5.2.4 Synchrones Senden und Empfangen ..................................................37
5.2.5 Die Zero-Copy-Layer-Variante für OpenMP ........................................39
5.3 Die Schnittstellen...............................................................................................40
5.3.1 Die Requests........................................................................................40
5.3.2 Der Status ............................................................................................41
5.3.3 Die obere Schnittstelle des Netzwerk-Layers ......................................41
5.3.4 Die untere Schnittstelle des Zero-Copy-Layers ...................................43
5.3.5 Die obere Schnittstelle des Zero-Copy-Layers ....................................44
5.4 Die Implementation der beiden Layer ...............................................................47
6 Der OpenMP-Prototyp ..................................................................................................49
6.1 Die Konzepte des OpenMP-Prototyps ..............................................................49
6.1.1 Kommunikation.....................................................................................49
6.1.2 Threading .............................................................................................49
6.1.3 Distributed-Shared-Memory .................................................................50
6.1.4 Private Memory ....................................................................................56
Seite 5
ETH Zürich
6.2 Das API des OpenMP-Prototypen .................................................................... 57
6.2.1 OMP_INIT / OMP_EXIT ...................................................................... 57
6.2.2 OMP_ALLOC / OMP_ALLOC_NEW_PAGE ....................................... 59
6.2.3 OMP_PARALLEL / OMP_END_PARALLEL ....................................... 60
6.2.4 OMP_DO / OMP_END_DO................................................................. 61
6.2.5 OMP_SECTIONS / OMP_END_SECTIONS....................................... 63
6.2.6 OMP_MASTER / OMP_END_MASTER ............................................. 64
6.2.7 OMP_BARRIER .................................................................................. 65
6.2.8 OMP_PRIVATE / OMP_FIRSTPRIVATE / OMP_LASTPRIVATE ...... 65
6.2.9 OMP_GET_NUM_THREADS.............................................................. 66
6.2.10 OMP_GET_MAX_THREADS ............................................................ 66
6.2.11 OMP_GET_THREAD_NUM .............................................................. 66
6.2.12 OMP_GET_xxx_NODES / OMP_GET_NODE_NUM ....................... 67
6.2.13 OMP_LOCK / OMP_UNLOCK .......................................................... 67
6.3 Im Prototypen nicht enthaltene Funktionalität .................................................. 68
6.4 Mögliche Erweiterungen und Verbesserungen................................................. 68
6.5 Die Anwendung des OpenMP-Prototypen........................................................ 69
7 Der MPI-Prototyp .......................................................................................................... 71
7.1 Die Konzepte des MPI-Prototypen ................................................................... 71
7.1.1 Threading............................................................................................. 71
7.1.2 Kommunikation.................................................................................... 72
7.1.3 Synchronisation ................................................................................... 73
7.2 Das API des MPI-Prototypen............................................................................ 73
7.2.1 MPI_Register_routine.......................................................................... 74
7.2.2 MPI_Run.............................................................................................. 75
7.2.3 MPI_Init................................................................................................ 75
7.2.4 MPI_Finalize ........................................................................................ 75
7.2.5 MPI_Send ............................................................................................ 75
7.2.6 MPI_Isend............................................................................................ 76
7.2.7 MPI_Recv ............................................................................................ 76
7.2.8 MPI_Irecv............................................................................................. 76
7.2.9 MPI_Test ............................................................................................. 77
7.2.10 MPI_Testall........................................................................................ 77
7.2.11 MPI_Wait ........................................................................................... 77
7.2.12 MPI_Waitall........................................................................................ 77
7.2.13 MPI_Get_count.................................................................................. 77
7.2.14 MPI_Barrier ....................................................................................... 78
7.2.15 MPI_Comm_size ............................................................................... 78
7.2.16 MPI_Comm_rank............................................................................... 78
7.3 Die Anwendung des MPI-Prototypen................................................................ 78
8 Performancemessungen ............................................................................................. 79
8.1 Bandbreitenmessungen über Sockets.............................................................. 79
8.1.1 Die Windows Sockets als Basis .......................................................... 79
8.1.2 Der Zero-Copy-Layer........................................................................... 81
8.1.3 Der MPI-Prototyp................................................................................. 82
8.1.4 Der OpenMP-Prototyp ......................................................................... 83
8.2 Profiling über Sockets....................................................................................... 84
8.2.1 MPI-Prototyp und Zero-Copy-Layer .................................................... 84
8.2.2 OpenMP-Prototyp und Zero-Copy-Layer ............................................ 87
8.3 Messungen über Named-Pipes ........................................................................ 88
8.3.1 Latenzmessung ................................................................................... 88
8.3.2 Bandbreitenmessung........................................................................... 88
8.3.3 Profiling................................................................................................ 90
9 Die Applikationen ......................................................................................................... 93
9.1 Quick-Sort ......................................................................................................... 93
9.1.1 Quick-Sort mit MPI .............................................................................. 93
9.1.2 Quick-Sort mit OpenMP....................................................................... 93
9.1.3 Die Performance.................................................................................. 94
Seite 6
ETH Zürich
9.2 Gauss-Elimination .............................................................................................95
9.2.1 Gauss-Elimination mit MPI...................................................................95
9.2.2 Gauss-Elimination mit OpenMP ...........................................................95
9.2.3 Die Performance ..................................................................................96
9.3 Bessere Testapplikationen ................................................................................96
A Messresultate ...............................................................................................................97
A.1 Bandbreitenmessungen über Sockets ..............................................................97
A.1.1 100 mbit Ethernet.................................................................................97
A.1.2 GigaBit Ethernet...................................................................................98
A.1.3 Lokale Loopback-Messung..................................................................99
A.1.4 Myricom GM-Sockets ........................................................................100
A.2 Bandbreitenmessungen über Named-Pipes ...................................................101
A.3 Profiling-Informationen über Named-Pipes.....................................................102
A.3.1 Asynchrone Kommunikation ..............................................................102
A.3.2 Synchrone Kommunikation................................................................103
B Aufgabenstellung .......................................................................................................105
C Quellenverzeichnis.....................................................................................................107
Seite 7
Seite 8
ETH Zürich
ETH Zürich
1 Einleitung
PCs werden Monat für Monat leistungsfähiger und noch schneller fallen ihre Preise. Moderne
Netzwerke weisen respektable Bandbreiten und immer kleinere Latenzzeiten auf. Die logische
Folge dieser beiden Tendenzen ist der vermehrte Einsatz von PC-Clustern anstelle von
Hochleistungsrechnern.
Schnelle Hardware alleine sagt jedoch noch nichts über die Leistungsfähigkeit solcher verteilter
Systeme aus. Nur wenn die Software diese Performance auszunützen vermag, sind solche
Systeme auch wirklich brauchbar. Sowohl das Betriebssystem wie auch die
Kommunikationsmodelle müssen sich den neuen Anforderungen stellen.
Im Rahmen dieser Arbeit wurden zwei Kommunikationsmodelle betrachtet: Message-Passing ist
ein relativ einfacher und verständlicher Ansatz. Distributed-Shared-Memory ist wesentlich
komplexer, aber deswegen nicht uninteressanter. Denn beide Systeme definieren im wesentlichen
nur ein Frontend. Erst die Implementation entscheidet über die Brauchbarkeit der Systeme.
Traditionelle Kommunikationsmodelle orientierten sich häufig am OSI-Protokoll-Stack. Zu
versendende Daten werden im Stack nach unten gereicht, empfangene nach oben. Ein oder gar
mehrmaliges Kopieren der Daten von einem Puffer in den nächsten sind in solchen Stacks die
Regel. Dabei entstehen beträchtliche Performanceeinbussen. Es muss nach anderen Modellen
gesucht werden. Insbesondere muss diese Kopiererei umgangen werden: Zero-Copy also.
Kapitel 2 dieser Dokumentation befasst sich mit der Theorie zur Zero-Copy-Kommunikation, denn
so simpel, wie es sich anhört, ist es nicht. Es gibt klare Regeln, wie eine solche Kommunikation
abzulaufen hat.
Doch mit einem Kommunikationsmodell und dem Wissen um Zero-Copy ist es noch nicht getan.
Diese Art Kommunikation ist ganz wesentlich auf die Unterstützung des Betriebssystems
angewiesen. Im Rahmen dieser Arbeit wurde Microsoft Windows NT 4.0 eingesetzt. Ein intensives
Studium der internen Abläufe und Strukturen war notwendig. Insbesondere interessierten die
Handhabung von Hardwareressourcen, die Treibermodelle und das Speichermanagement. Kapitel
3 gibt einen kurzen Abriss der im Zusammenhang mit Zero-Copy wichtigen Eigenschaften von
Windows NT.
Die Brauchbarkeit von Zero-Copy hängt auch davon ab, wie gut bestehende höhere
Kommunikationsmodelle wie Message-Passing und Distributed-Shared-Memory auf das ZeroCopy-Modell aufbauen können. Kapitel 4 bespricht die Schnittstellen zwischen diesen drei
Modellen.
Die Verneinung des OSI-Protokoll-Stack heisst nicht, dass die Kommunikation nicht durch ein
Schichtenmodell dargestellt werden könnte.
Dies beweist der im Laufe dieser Arbeit
implementierte und in Kapitel 5 vorgestellte Zero-Copy-Layer. Er beinhaltet die in Kapitel 2
vorgestellten Kommunikationsmuster. Dank eines weiteren Layers, der zwischen den Zero-CopyLayer und die verwendete Netzwerktechnologie geschoben wurde, konnte der Zero-Copy-Layer
weitgehend unabhängig vom Netzwerk implementiert werden.
Dieser Zero-Copy-Layer bildet die Grundlage für die nächsten Layer. Denn die beiden erwähnten
Frontends wurden als Prototypen implementiert. Dabei beschränkte man sich jeweils auf die
wichtigsten Primitiven.
Das Distributed-Shared-Memory-Modell wurde in Form eines OpenMP-Prototypen implementiert.
Die Programmierschnittstelle des Prototypen wurde so weit als möglich an die Vorgaben des
OpenMP-Standards angelehnt. Für die Implementation mussten jedoch weitere Techniken, wie sie
beispielsweise in TreadMarks enthalten sind, zugezogen werden. Kapitel 6 erläutert die
verwendeten Techniken und beschreibt das API des Prototypen.
Fast schon unproblematisch war die Implementation des MPI-Prototypen, der das MessagePassing-Modell verwendet. Beschrieben wird die Implementation und das API in Kapitel 7.
Die Theorie ist das eine, die Praxis das andere. Die Leistungsfähigkeit der implementierten
Schichten wird in Kapitel 8 betrachtet, und praktische Anwendungen der beiden Prototypen sind in
Kapitel 9 vorgestellt.
Seite 9
Seite 10
ETH Zürich
ETH Zürich
2 Zero-Copy-Kommunikation
Die Hardware im PC-Bereich ist in den letzten Jahren immer leistungsfähiger und preiswerter
geworden. Nicht nur die PCs wurden schneller, auch die Netzwerktechnologien, die diese PCs
verbinden, haben an Bandbreite zugelegt und an Latenzzeit verloren. Messungen zeigen heute
jedoch, dass die Software diese Spitzenleistungen nicht mehr auszunützen vermag. Nicht zuletzt
sind
dafür
fehlende
Betriebssystemunterstützung
und
nicht
mehr
zeitgemässe
Kommunikationsmodelle verantwortlich. Viele dieser Modelle basieren auf den Überlegungen des
OSI-Referenz-Modells. Zu kommunizierende Daten werden Schicht für Schicht den Protokoll-Stack
herunter und beim Empfänger wieder heraufgereicht. In den meisten Fällen ist dieser Vorgang mit
mindestens einem, wenn nicht sogar mit mehreren Kopiervorgängen belastet. Dieses Kopieren
stellt einen wesentlichen Grund für die Ineffizienz klassischer Modelle dar. Es müssen also neue
Modelle her.
Ein zentrales Thema dieser Arbeit ist daher die Zero-Copy-Kommunikation. Das heisst, das
Verschieben von Information direkt aus dem Speicher des Senders in den Speicher des
Empfängers ohne aufwendiges Kopieren in Zwischenspeicher.
Das Verwenden von Puffern hat neben dem Nachteil des Kopierens jedoch auch einen grossen
Vorteil: Das Zwischenspeichern in Sender und/oder Empfänger entkoppelt die Sende- und
Empfangsfunktion. Das heisst im wesentlichen, dass der Sender praktisch jederzeit Senden kann,
ohne Rücksicht darauf nehmen zu müssen, ob der Empfänger bereit zum Empfangen ist oder
nicht.
Ganz
anders
verhält
sich
Zero-CopyKommunikation. Es gibt zwei wesentliche
Grundsätze, die Zero-Copy-Kommunikation zu
befolgen hat:

Der Empfänger ist dafür verantwortlich, dass
immer
genug
Empfangsspeicher
zur
Verfügung steht.
Der Sender darf erst senden, wenn der
Empfänger Speicher für den Empfang zur
Verfügung gestellt hat.
Kleine Pakete
Senden
Grosse Pakete
Bereit zum Empfangen
Senden
Auf den ersten Blick scheinen diese beiden
Aussagen ungefähr das selbe zu bedeuten, doch
es gibt gewichtige Unterschiede, die zwei ganz
Sender
Empfänger
verschiedene Kommunikationsarten mit Vor- und
Nachteilen mit sich ziehen.
Abb. 2.1: Zwei Kommunikationsarten
2.1 Die unsynchronisierte Kommunikation kleiner Pakete
Die erste der obigen Aussagen verlangt vom Empfänger, immer genügend Speicher für den
Empfang zur Verfügung zu stellen (siehe Abbildung 2.1, obere Darstellung). Doch was ist
genügend? Und wie gross müssen bzw. dürfen diese Empfangspuffer sein? Speicher ist auch
heute noch eine begrenzte Ressource. Daher ist es zwingend, dass sowohl Grösse wie auch
Anzahl beschränkt sind. Zudem muss Speicher, der für den Empfang zur Verfügung gestellt wird,
durch das System „gelocked“ werden. Das heisst, der mit dem Puffer verbundene physische
Speicher wird dem Memory-Manager quasi entzogen. Wird zu viel Speicher gelocked, dann kann
das massive Auswirkungen auf die Performance der Applikationen und des Systems bedeuten.
Diese Art der Kommunikation eignet sich also nur für kleinere Pakete. Die Anzahl solcher kleiner
Puffer hängt von der Reaktionszeit ab, die ein System aufweist, um bei Knappheit weitere Puffer
zur Verfügung stellen zu können. Grundsätzlich sollten es nur so viele wie unbedingt nötig sein.
Neben der Grössenbeschränkung hat diese Kommunikationsart noch einen weiteren Nachteil: Mit
dem Empfangen kann nicht gewartet werden, bis die Applikation eine Empfangsfunktion aufruft.
Die Puffer müssen also vom System und nicht von der Applikation zur Verfügung gestellt werden.
Eine Applikation hat also nicht die Möglichkeit, selbst zu bestimmen, wohin sie die Daten ablegen
möchte. Für die Applikation bieten sich dann nur zwei Möglichkeiten: Entweder sie gibt sich mit
Seite 11
ETH Zürich
dem Puffer des Systems zufrieden, oder sie kopiert die Daten aus dem Puffer in den gewünschten
Speicher.
Grosser Vorteil: Der Sender braucht sich nicht um die Empfangsbereitschaft der
Empfängerapplikation zu kümmern. Er kann jederzeit einfach drauflossenden. Dies entkoppelt die
beiden Applikationen. Zudem muss der Empfänger sich nicht festlegen, von wem er Daten
empfangen möchte. Es reicht, wenn ihm das System nach dem Empfang mitteilen kann, wer der
Absender war.
Eine mögliche Schnittstelle einer solchen Kommunikationsart könnte folgendermassen aussehen:
Send([in] int nRecvID, [in] void* pBuffer, [in] int nLength);
Recv([out] int& nSendID, [out] void*& pBuffer, [out] int& nLenght);
Die Sendefunktion definiert den Empfänger und gibt Position und Länge des Sendepuffers an. Die
Empfangsfunktion gibt eine Senderidentifikation sowie Position und Länge des Empfangspuffers
zurück. nLength ist natürlich beschränkt auf die maximale Grösse der Empfangspuffer.
Diese unsynchronisierte Kommunikationsart kleiner Pakete wird in diesem Dokument oft auch mit
asynchronem Senden und Empfangen bezeichnet.
2.2 Die synchronisierte Kommunikation grosser Pakete
Die zweite der oben gemachten Aussagen legt die Verantwortung für den korrekten Empfang in die
Hände des Senders. Dieser darf nicht einfach drauflossenden, sondern muss solange warten, bis
er vom Empfänger die Bestätigung bekommen hat, dass er bereit ist für den Empfang. Sender und
Empfänger werden als bewusst synchronisiert (siehe Abbildung 2.1, untere Darstellung).
Der Nachteil liegt auf der Hand: Ein zusätzliches, kleines Paket, das natürlich unsynchronisiert
verschickt werden muss, ist notwendig, um dem Sender die Bereitschaft des Empfängers
mitzuteilen. Bei grossen Latenzzeiten kann dies eine erhebliche Performanceeinbusse bedeuten.
Deshalb kann eine solche Kommunikationsart auch nur für grosse Pakete vorteilhaft sein, so dass
die zusätzliche Latenzzeit nicht mehr ins Gewicht fällt.
Doch nicht nur die Latenz ist ein Nachteil der Synchronisation, sondern auch der Umstand, dass
der Empfänger sich beim Aufruf der Empfangsfunktion bereits im klaren sein muss, von wem er
Daten empfangen möchte.
Wenn man im Zusammenhang mit synchronisierter Kommunikation überhaupt von Vorteilen
sprechen kann, dann ist das die Möglichkeit des Empfängers, festzulegen, wohin er die Daten
empfangen möchte. Als kleiner Pluspunkt kann zusätzlich erwähnt werden, dass durch die
Synchronisierung erreicht wird, dass auch grosse Pakete verschickt werden können, ohne das
System durch viele, grosse Puffer (wie dies die unsynchronisierte Kommunikation tun würde) zu
belasten.
Eine mögliche Schnittstelle einer synchronisierten Kommunikationsart könnte folgendermassen
aussehen:
Send([in] int nRecvID, [in] void* pBuffer, [in] int nLength);
Recv([in] int nSendID, [in] void* pBuffer, [in/out] int& nLenght);
Der Sendefunktion wird der Empfänger sowie die Position und die Länge des Sendepuffers
mitgegeben. Die Empfängerfunktion definiert den Sender wie auch die Position und Grösse des
Empfangspuffers und gibt nach dem Empfang die Grösse des gebrauchten Teils des
Empfangspuffers in nLength zurück.
2.3 Der Zero-Copy-Layer in der Theorie
Ein allgemeines Zero-Copy-System beruht also auf zwei Kommunikationsarten mit ganz
unterschiedlichen Eigenschaften:
Seite 12
ETH Zürich
Eigenschaft
Synchronisation ist notwendig
Absender muss im voraus bestimmt werden
Empfangspuffer kann selber bestimmt werden
Paketgrösse ist beschränkt
Tab. 2.1: Eigenschaften der beiden Kommunikationsarten
unsynchronisiert
synchronisiert
nein
nein
nein
ja
ja
ja
ja
*)
nein
*) nur durch Speichergrösse
Soll ein solches System implementiert werden, dann muss irgendwann die maximale Grösse der
unsynchronisierten Pakete festgelegt werden. Dabei spielen Werte wie die Grösse des
physikalischen Speichers und die Bandbreiten und Latenzzeiten der beiden Kommunikationsarten
eine wesentliche Rolle. Je nach Gesamtsystem dürfte die resultierende Grösse zwischen 8 und 64
kB liegen.
Die Anzahl der Puffer ergibt sich aus Puffer- und Speichergrösse sowie der Rechenleistung und
der erwarteten Belastung des Systems. Unter Umständen kann es sinnvoll sein, die gesamte
Kommunikation in einen Thread (eventuell mit erhöhter Priorität) zu verpacken, der dafür zuständig
ist, dass immer genügend Empfangspuffer zur Verfügung stehen.
Grundsätzlich lässt sich die beschriebene Zero-Copy-Kommunikation gut in einen
Kommunikationslayer verpacken. Ein solcher Layer würde folgende Aufgaben wahrnehmen:

Er alloziert den Speicher für den Empfang von kleinen, unsynchronisierten Paketen und ist
dafür verantwortlich, dass immer genügend freie Puffer zur Verfügung stehen.

Er meldet die Bereitschaft des Empfängers an den Sender von synchronisierten Paketen.

Er verzögert das Senden von synchronisierten Paketen bis die Bereitschaft des Empfängers
bestätigt wurde.
Ein solcher Layer könnte als Netzwerktreiber direkt auf einem Netzwerkadapter aufbauen, oder im
User-Space auf einen Netzwerktreiber oder ein Netzwerk-API zurückgreifen. Wichtig ist nur, dass
sowohl die Hardware, wie auch allfällige Software Zero-Copy unterstützen. Im Bereich Hardware
heisst das, dass der Netzwerk-Adapter über Direct-Memory-Access (DMA) und eventuell über
Device-Speicher verfügen muss. Der Treiber oder das API müssen ungefähr folgende Funktionen
anbieten können:

LockMemoryForRecv(void* pBuffer, int nLength);
Der Layer übergibt mit dieser Funktion dem Treiber/API einen Speicherbereich, der für den
Empfang von unsynchronisierten Paketen verwendet werden kann.

Send(int nRecvID, void* pBuffer, int nLength);
Mit dieser Sendefunktion verschickt der Layer kleine unsynchronisierte Pakete an einen
bestimmten Empfänger. Für den Empfang wird irgend ein mit LockMemoryForRecv
freigegebener Puffer verwendet.

LockMemoryForRecvDirect(void* pBuffer, int nLength);
Speicherbereiche, die für den Empfang von synchronisierten Paketen vorgesehen sind,
werden mit dieser Funktion für den Empfang freigegeben.

SendDirect(int nRecvID, void* pSource, void* pTarget, int nLength);
Sendet einen bestimmten, durch pSource und nLength definierten Speicherbereich direkt an
die durch pTarget definierte Stelle im Speicher der Empfängerapplikation. Der
Speicherbereich des Empfängers muss zuvor mit LockMemoryForRecvDirect freigegeben
worden sein.
Ein API, das eine solche Schnittstelle anbietet, ist GM von Myricom [15]. Mit den Funktionen
gm_dma_malloc, gm_dma_free, gm_register_memory, gm_deregister_memory, gm_send
und gm_directed_send kann die oben beschriebene Schnittstelle (bzw. deren Funktionalität)
zwischen API und Zero-Copy-Layer realisiert werden.
Eine konkrete Implementation eines solchen Zero-Copy-Layers ist in Kapitel 5 ausführlich
beschrieben.
Seite 13
ETH Zürich
2.4 Ein alternativer Ansatz für Zero-Copy-Kommunikation
Die soeben vorgestellte Form der Zero-Copy-Kommunikation geht von einer ganz wichtigen
Annahme aus: Aller Speicher, der für den Empfang von Meldungen verwendet werden soll, wird
von der Applikation (bzw. vom Zero-Copy-Layer) alloziert und dem empfangenden Treiber oder
API zur Verfügung gestellt. Ein Top-Down-Verfahren sozusagen.
Man könnte sich
jedoch auch den
ALLOC
FREE
FREE
umgekehrten Weg
vorstellen: Der für
den
Empfang
Applikation
User-Mode
Treiber
Kernel-Mode
verantwortliche
Treiber alloziert den
nötigen
Speicher
FREE
ALLOC
und stellt diesen der
Applikation
zur
NIC
NIC
Verfügung. Dieses
Bottom-Up-Verfahren
Top-Down-Verfahren
Bottom-Upwäre
Verfahren
Abb. 2.2: Die zwei Verfahren für die Allokation des Empfangspuffers
eigentlich
der
natürlichste Weg zur Zero-Copy-Kommunikation. Durch ein Remapping könnte der
Empfangsspeicher des Treibers in den virtuellen Adressraum der Applikation eingeblendet werden,
ohne dass kopiert werden muss. Doch es gibt zwei gewichtige Punkte, die gegen einen solchen
Ansatz sprechen.
2.4.1 Fehlende Unterstützung durch Windows NT
Vorab: Leser, die mit den internen Abläufen von Windows NT nicht oder nur wenig vertraut sind,
wird empfohlen, sich zuerst mit Kapitel 3 auseinanderzusetzen oder allenfalls auf das Buch „Inside
Windows NT“ von David A. Solomon [8] zurückzugreifen.
In modernen Systemen wird der Empfang von Daten in der Regel durch einen (Hardware-)Interrupt
signalisiert. Für Windows NT bedeutet dies, dass der Empfang von Daten auf dem Interrupt-Level
DIRQL oder nach dem Aufruf einer DpcForIsr-Routine auf DISPATCH_LEVEL behandelt wird. Da
die zentralen Funktionen des Memory-Managers ebenfalls auf DISPATCH_LEVEL laufen, ist die
Allokation von Speicher (im Paged-Pool) nur unterhalb dieses Levels möglich. Das heisst dann,
dass Speicherallokation während der Interruptbehandlung nicht möglich ist.
Der Speicher müsste also vorgängig und ohne das Wissen über die Grösse der zu empfangenden
Nachrichten auf PASSIVE_LEVEL vorgenommen werden. Da alle Threads (auch die im UserMode) auf PASSIVE_LEVEL laufen, kommt dieses Vorgehen dem Top-Down-Verfahren gleich.
Eine Möglichkeit, ein Bottom-Up-Verfahren unter Windows NT doch zu realisieren, wäre auf
Interrupts zu verzichten und statt dessen zu pollen. Ein System-Thread (ein Thread also, der
ausschliesslich im Kernel-Mode existiert), könnte das Polling übernehmen. Dieser Thread arbeitet
garantiert immer unterhalb des DISPATCH_LEVEL. Daher sollte auch die Speicherallokation kein
Problem darstellen. Genaueres zu System-Threads kann im Buch „The Windows NT Device Driver
Book“ von Art Baker [9] in Kapitel 14 nachgelesen werden. Auf Grund des Pollings und der nötigen
Synchronisation des System-Threads mit den User-Threads ist es zu bezweifeln, dass auf diesem
Wege eine effiziente Implementation möglich ist.
2.4.2 Fehlende Unterstützung durch höhere Layer
Kommunikationsprotokolle, die mit Kopiervorgängen behaftet sind, verwenden fast ausnahmslos
das Top-Down-Verfahren. Der Treiber empfängt die Daten in einen Puffer, welcher später in den
durch die Applikation zur Verfügung gestellten Speicherbereich kopiert wird. Aufbauend auf solche
Kommunikationsprotokolle sind höhere Layer entstanden, die naturgemäss ebenfalls das TopDown-Verfahren anwenden. MPI kann hier als klassisches Beispiel genannt werden. Einem
MPI_Recv wird ein Pointer auf einen Applikationsspeicher und dessen Grösse mitgeteilt. Ist der
Seite 14
ETH Zürich
Empfang vollständig, dann erwartet die MPI-Applikation, dass die Daten in diesem Speicherbereich
abgelegt sind.
Für ein Bottom-Up-Verfahren müsste die Signatur der Empfangsfunktion geändert werden, denn
der Pointer und die Länge sind nicht länger Input für die Funktion, sondern deren Output. Zudem
ist es nicht mehr Sache der Applikation, den Speicher zu allozieren, sondern die des Treibers.
Solche Layer – insbesondere deren Schnittstellen – und alle darauf basierenden Applikationen
müssten umgeschrieben werden. Im Namen der Performance wäre dies zwar wünschenswert,
doch werden diese Massnahmen wohl kaum auf Akzeptanz stossen.
Ein Verändern der Schnittstellen-Signaturen muss also umgangen werden. Ein verführerischer
Ansatz könnte der folgende sein: Eine Applikation alloziert Speicher für den Empfang von Daten
und übergibt Pointer und Grösse des Speicherbereichs an den Treiber. Dieser dealloziert den
Speicher wieder und mapped statt dessen seinen Empfangsspeicher an die selbe Stelle. Das
Problem dieser Variante ist jedoch, dass der Speicher seitenweise und nicht byteweise verwaltet
wird. Man könnte zwar die Speicherallokation so gestalten, dass die Speicherbereiche immer
page-aligned sind. Doch niemand kann einer Applikation vorschreiben, die Daten auch an den
Anfang des allozierten Speichers empfangen zu müssen. Empfängt der Treiber Daten nach dem
Aufruf der Receive-Funktion, dann könnte er zwar auf die Verschiebung reagieren, indem die erste
und letzte Speicherseite speziell behandelt werden. Im umgekehrten Fall (zuerst der Empfang,
dann erst die Receive-Funktion) ist dies jedoch unmöglich. Mit diesem Ansatz könnten die
Signaturen zwar belassen werden, doch müssten genaue Richtlinien für die Speicherverwendung
beim Empfangen gelten.
Eine befriedigende Lösung für dieses Problem scheint es nicht zu geben. Es muss hier jedoch
gesagt werden, dass nicht alle höheren Layer dieses Problem aufweisen. Ein DSM-System zum
Beispiel könnte durchaus auf ein solches Bottom-Up-Verfahren aufgebaut werden, vorausgesetzt,
der DSM-Layer kann bestimmen, an welche virtuelle Adresse eine empfangene Speicherseite
gemapped werden soll.
Damit ist die Zero-Copy-Kommunikation auf theoretischer Ebene charakterisiert. Wenn in den
folgenden Kapiteln von Kommunikation gesprochen wird, dann sind immer die in den Kapiteln 2.1
und 2.2 beschriebenen Formen gemeint, es sei denn, es wird ausdrücklich auf eine andere Form
verwiesen.
Seite 15
Seite 16
ETH Zürich
ETH Zürich
3 Zero-Copy unter Windows NT 4.0
Das im vorhergehenden Kapitel vorgestellte Kommunikationsmodell mit synchronisierten, grossen
und unsynchronisierten, kleinen Paketen ist zwar ein wichtiges Konzept was Zero-Copy betrifft,
doch es ist eigentlich nur die oberste Schicht. Alle Komponenten darunter, insbesondere Hardware
und allfällige Treiber- und API-Software muss ebenso auf Zero-Copy-Kommunikation ausgerichtet
sein. Das kann jedoch nur realisiert werden, wenn das Betriebssystem entsprechende
Unterstützung bietet. In diesem Kapitel wird deshalb versucht, den Kernel von Microsoft Windows
NT 4.0 etwas zu durchleuchten und auf Zero-Copy-Unterstützung hin zu prüfen.
3.1 Die Windows NT 4.0 Kernel-Architektur
Einführend wird hier eine Übersicht über die
Kernel-Komponenten von Windows NT 4.0
(Abbildung
3.1)
aufgezeigt
und
deren
Funktionen kurz erläutert:
Executive
I/OManager
Virtual
Memory
Manager
Cache
Manager
Process
Threads
Security

HAL: Der Hardware-Abstraction-Layer ist
eine schmale Schicht direkt über der
Drivers
Kernel
Hardware. Sie soll eine abstrakte Sicht der
Hardware (insbesondere Ports, Interrupts
Hardware Abstraction Layer (HAL)
und DMAs) gewährleisten, um möglichst
hardwareunabhängigen Code schreiben zu Abb. 3.1: Kernel-Architektur
können.

Kernel: Der Kernel enthält allen plattformabhängigen Code. Windows NT ist heute auf drei
Plattformen lauffähig: Intel 486 und höhere Prozessoren, Compaq (vormals Digital) Alpha und
MIPS. Plattformabhängig ist im wesentlichen alles, was prozessorabhängig ist. Dazu zählen
Teile des Schedulers (Thread-Kontext) und des Memory-Managers (Translation-LookasideBuffer, Page-Faults, u.s.w.).

Drivers: Windows NT kennt neben einem generischen Device-Driver-Modell eine Vielzahl von
spezialisierten Treibermodellen für Grafikkarten, Netzwerkkarten, Mass-Storage-Controller,
File-Systeme, Multimedia-Devices, Drucker usw. Die meisten dieser Modelle unterstützen
sogenannte Miniport-Treiber: Das heisst, Windows NT bietet ein Framework, das ein Grossteil
der gängigen Funktionen übernimmt, so dass der Treiber nur noch die hardwarespezifische
Funktionalität implementieren muss.

I/O-Manager: Der I/O-Manager organisiert und sequenzialisiert I/O-Anfragen aus dem UserMode und Kernel-Mode. Da es pro Device nur eine Queue gibt, in der pendente Anfragen
zwischengespeichert werden, und auch nur eine Anfrage zur gleichen Zeit bearbeitet werden
kann, unterstützt Windows NT von Haus aus nur halbduplex Input/Output. Für allfällige
Fullduplex-Kommunikation müssen Treiber selber eine zweite Queue unterhalten.

Virtual Memory Manager: Der VMM übernimmt die Abbildung des virtuellen Adressraums auf
die physisch vorhandenen Speicher (RAM, Disk).

Cache Manager: Windows NT verfügt über einen bewusst allgemein gehaltenen Cache, der
mit beliebigen File-System-Treiber und Network-Redirectors zusammenarbeiten kann und die
Cachegrösse dynamisch durch den Memory-Manager zugeteilt bekommt.

Process/Threads: Verwaltung von Process- und Threadinformationen, Scheduling, Context
Switching.

Security Manager: Jedes Objekt (wie z.B. Prozesse, Files, u.s.w.) hat ein Token, das
beschreibt, zu welchem Sicherheitskontext es gehört. Nur autorisierte Benutzer, die in diesem
Kontext die entsprechenden Zugriffsberechtigungen besitzen, wird der Zugriff gewährt.

Executive: Executive ist ein Pool von Funktionalität, die hardware- und plattformunabhängig
ist. Insbesondere enthält diese Komponente auch die (undokumentierte) Schnittstelle zwischen
Kernel-Mode und der NTDLL.DLL im User-Mode.
Seite 17
ETH Zürich
3.2 Das Windows NT Interruptmodell
Die Ausführung von User- und Kernel-Code ist stark abhängig vom Interruptmodell. Windows NT
4.0 kennt verschiedene sogenannte Interrupt-Request-Levels (IRQL). Jedes Stück Code läuft auf
einem solchen Level. Ausgeführt wird immer gerade das Stück, das den höchsten Level hat und
Ready-to-run ist. Software- und Hardwareinterrupts können asynchron neuen Code zur Ausführung
bringen, der den Interrupt behandeln soll. Hat dieser Code (bzw. der auslösende Interrupt) einen
höheren Level, als der gerade ausgeführte, dann wird der aktuelle unverzüglich unterbrochen, und
dem neuen Code die Kontrolle übergeben. Erst wenn alle Interruptbehandlungen mit höheren
Levels beendet oder in den Wait-Zustand übergegangen sind, wird der unterbrochene Code
weitergeführt.
Software
Hardware
Welche Interrupt-Request-Levels es gibt, und welche wichtigen Tasks auf diesen Levels laufen, ist
in Tabelle 3.1 zusammengefasst:
IRQL
Tasks
HIGHEST_LEVEL
Rechner-Checks und Busfehler
POWER_LEVEL
Power-Fail Interrupt
IPI_LEVEL
Interprocessor Doorbell für Multiprozessorsysteme
CLOCK2_LEVEL
Interval Clock 2
CLOCK1_LEVEL
Interval Clock 1 (auf i386 Systemen nicht gebraucht)
PROFILE_LEVEL
Profiling Timer
DIRQL
Plattformabhängige Anzahl von Interrupt-Levels für I/O-Devices
DISPATCH_LEVEL
Thread-Scheduler, Page-Fault-Handling, Deferred-ProcedureCalls (DPC)
APC_LEVEL
Asynchronous-Procedure-Calls (APC)
PASSIVE_LEVEL
User-Mode- und Kernel-Mode-Threads
Tab. 3.1: Interrupt-Request-Levels (von oben nach unten nimmt die Priorität der Levels ab)
Die Positionierung des Thread-Schedulers auf DISPATCH_LEVEL hat zur Konsequenz, dass alle
Interruptbehandlungsroutinen, die auf dem selben oder höherem Level laufen, im Kontext des
Threads (und Prozesses) ausgeführt werden, der zur Zeit aktiv ist. Zudem dürfen solche Routinen
keine Page-Faults verursachen, da diese erst behandelt würden, wenn die aktuelle Routine
beendet ist, was sofort zu einem Deadlock (bzw. Blue Screen) führen würde.
3.3 Die Windows NT-Treibermodelle
Wie bereits oben angetönt, unterhält Windows NT neben einem generischen Modell für DeviceTreiber eine beschränkte Anzahl von spezialisierten Treibermodellen. Speziell betrachtet werden
soll hier neben dem generischen nur das Modell für Netzwerktreiber, genannt NDIS.
3.3.1 Das generische Treibermodell
Das generische Treibermodell erlaubt das Schreiben von beliebigen I/O-Treibern, die das gesamte
Set von Funktionen, welches Executive, Kernel und HAL zur Verfügung stellen, vollumfänglich
gebrauchen können.
Zentrale Funktion eines Treibers ist DriverEntry. Dies ist die einzige Funktion, die zwingend
diesen Namen tragen muss. Sie wird beim Laden des Treibers aufgerufen. Die Aufgaben dieser
Routine sind, dem System weitere Routinen für die Behandlung von User-Requests und Interrupts
bekannt zu geben und die zu kontrollierenden Devices zu initialisieren und nach aussen bekannt
zu machen.
Für den User-Mode-Programmierer sind die Device-Treiber quasi ein Teil des Filesystems.
Deshalb werden solche Treiber auch mit den selben Win32-Funktionen angesprochen. Mit
Seite 18
ETH Zürich
CreateFile(„\\\\.\\DeviceX“,..) wird ein Handler auf ein Device erzeugt. Dabei kann ein
Treiber synchron oder asynchron geöffnet werden, je nach dem, ob Requests blockierend oder
nicht-blockierend abgearbeitet werden sollen. Innerhalb des Treibers wird beim Öffnen eine zuvor
bekanntgegebene Routine aufgerufen, die auf PASSIVE_LEVEL im Kontext des aufrufenden
Prozesses läuft und die nötigen Initialisierungen und Allokationen vornimmt.
Mit ReadFile, WriteFile und DeviceIoControl können Requests an den Treiber geschickt
werden (Abbildung 3.2). Diese Requests werden vorerst vom I/O-Manager abgefangen. Dieser ist
dafür verantwortlich, dass die dem Treiber übergebenen Speicherbereiche entweder gelocked
(Direct-I/O) oder in den Kernel-Mode kopieren (Buffered-I/O) werden. Danach wird die zugehörige
Dispatch-Routine aufgerufen und ihr ein I/O Request Packet (IRP), das den Request beschreibt,
mitgegeben.
HardwareInterrupt
User-Request
Success
I/O-Manager
IRP
IRP
IRP
IRP
DispatchRoutine
I/O-StartRoutine
Interrupt
Service
Routine
DpcForIsr
PASSIVE_LEVEL
DISPATCH_LEVEL
DIRQL
DISPATCH_LEVEL
Abb. 3.2: Ein möglicher Ablauf eines User-Requests
Anders als der Name vermuten liesse, läuft die Dispatch-Routine im Kontext des aufrufenden
Prozesses auf PASSIVE_LEVEL. Dies ist oft die letzte Gelegenheit, Speicher zu allozieren oder zu
locken. Falls das für den Request benötigte Device gerade durch einen anderen Request belegt
ist, wird das IRP mit dem Status STATUS_PENDING dem I/O-Manager zurückgegeben, um es in
eine Queue zu hängen, anderenfalls kann direkt die I/O-Start-Routine aufgerufen werden.
Die I/O-Start-Routine ist sehr oft dafür verantwortlich, das Device für den Datentransfer
vorzubereiten und den Transfer zu starten. So kann zum Beispiel ein DMA-Transfer ausgelöst
werden. Diese Routine läuft bereits auf DISPATCH_LEVEL. Es kann also nicht mehr davon
ausgegangen werden, dass man sich im Kontext des aufrufenden Prozesses befindet und vor
allem dürfen keine Page-Faults ausgelöst werden. In vielen Fällen wird diese Routine beendet,
ohne dass der Request vollständig abgearbeitet wurde. Der Grund kann darin liegen, dass auf
einen Interrupt vom Device gewartet werden muss. Deshalb wird auch nach dieser Routine das
IRP mit Status STATUS_PENDING an den I/O-Manager zurückgegeben.
Trifft der Interrupt ein, wird eine zuvor registrierte Interrupt-Service-Routine (ISR) aufgerufen. Diese
hat zuerst zu klären, ob das von ihr kontrollierte Device den Interrupt ausgelöst hat oder nicht. Falls
ja, ist es die wichtigste Aufgabe dieser Routine, den aktuellen Status des Device auszulesen und
zwischenzuspeichern. Da die ISR auf dem Level DIRQL läuft, ist es sehr wichtig, dass nur die
wichtigste Arbeit in dieser Routine vorgenommen wird, um andere Routinen nicht zu lange zu
blockieren. Deshalb wird häufig das IRP an den I/O-Manager zurückgegeben mit der Bitte, bald
möglichst eine DpcForIsr-Routine aufzurufen.
Diese Deferred-Procedure-Calls (DPC) sind Routinen, die auf DISPATCH_LEVEL laufen, und so
Interrupts anderer Devices nicht blockieren. Eine DPC-Routine sollte, wenn immer möglich, die
eigentliche Interruptbehandlung vornehmen. Falls der Request nun beendet ist, wird der IRP mit
Status STATUS_SUCCESS (oder allenfalls mit einem Fehlercode) dem I/O-Manager
zurückgegeben. Falls nicht, kann auf dem Device ein neuer Transfer gestartet und wiederum auf
einen Interrupt gewartet werden, indem der IRP mit Status STATUS_PENDING zurückgegeben
wird.
Dieser Ablauf ist nicht für jeden Treiber zwingend. So muss es nicht unbedingt eine ISR oder eine
DpcForIsr geben. Auch das Queuing von pendenten Requests muss nicht zwingend durch den I/OManager erfolgen. Fullduplex-Treiber – Treiber also, die gleichzeitig Senden und Empfangen
Seite 19
ETH Zürich
können – müssen eine zweite Queue implementieren, da der I/O-Manager pro Device nur einen
aktiven Request verwaltet. Alle anderen Requests werden nach der Dispatch-Routine solange
gequeued, bis der aktive einen Status ungleich STATUS_PENDING zurückgeliefert hat.
Ein Win32 CloseHandle schliesst den Handle auf das Device und löst im Treiber eine CloseRoutine aus. Zusätzlich kann der Treiber je eine Routine enthalten, die das Entladen des Treibers
ermöglicht oder beim Shutdown die Devices in einen Grundzustand zurücksetzt.
3.3.2 Das NDIS-Modell
Nachdem nun das generische Modell vorgestellt wurde, ist die Frage gerechtfertigt, wieso es noch
zusätzliche, spezielle Treibermodelle braucht. Welche Vorteile können solche Modelle bringen?

Spezielle Modelle können optimiert sein und so eine höhere Leistungsfähigkeit aufweisen.

Das System kann dem Treiber ein Framework zur Verfügung stellen, das Routinen enthält, die
jeder Treiber dieser Klasse implementieren müsste. So kann sich der Treiberprogrammierer
auf die hardwareabhängigen Teile konzentrieren.

Ein solches Framework kann die Plattformunabhängigkeit steigern.

Es kann eventuell sogar betriebssystemneutraler Source geschrieben werden.
Kurz: Performance und Portabilität können gesteigert und der Programmieraufwand gesenkt
werden. Ein aus kommerzieller Sicht durchaus sinnvolles Konzept also.
An dieser Stelle soll nur auf das NDISModell
(Network-Driver-InterfaceSpecification) eingegangen werden.
NetBios-Emulator Socket-Emulator
NetBios-Emulator Socket-Emulator
LAN Protocols
NDIS Interface
NDIS bietet ein oben erwähntes
Framework, in welches verschiedene
Treiber eingebettet werden können
(vgl. Abbildung 3.3). Den Treibern wird
eine Vielzahl von Funktionen zur
Verfügung gestellt.
Die
Treiber
existieren quasi in einer Sandbox. Es
ist NDIS-Treibern nicht gestattet, auf
andere als auf NDIS-Funktionen
zuzugreifen. Dadurch wird eine
Portabilität erreicht, durch die nicht nur
Plattformunabhängigkeit möglich ist,
sondern theoretisch auch der Einsatz
unter anderen Windows-Systemen wie
Windows 95/98 möglich sein sollte.
User-Mode-Client
User-Mode
Kernel-Mode
Transport Driver
Interface (TDI)
LAN Media Type
NDIS Intermediate
Native Media Type
NDIS Miniport
Network Interface Card (NIC)
LAN-Protocol-Treiber
Der
implementiert das Transport-DriverAbb. 3.3: NDIS-Treiber-Modell
Interface (TDI). Dieser Treiber ist
verantwortlich für die Umwandlung des Datenstroms einer Applikation in Pakete und umgekehrt.
Unterstützt werden jedoch nur gängige Paketformate wie sie beispielsweise Ethernet, Token-Ring
oder FDDI verwenden.
NDIS-Miniport-Treiber übernehmen alle hardwareabhängigen Funktionalitäten und bieten nach
oben ein klar definiertes Interface an. Sie sind verantwortlich für das Senden und Empfangen von
Datenpaketen. Das Format dieser Pakete ist im Prinzip beliebig.
Falls der Miniporttreiber keines der oben erwähnten Standardpaketformate verwendet, kann ein
NDIS-Intermediate-Treiber dazwischen geschaltet werden, um das proprietäre Format in ein
unterstütztes umzusetzen. Dabei verhält sich der Intermediate-Treiber nach oben wie ein
Miniporttreiber.
Welche zentralen Aufgaben übernimmt nun aber das NDIS-Framework eigentlich?
Seite 20
ETH Zürich

Alle notwendige Synchronisation und Sequenzialisierung (insbesondere auf Maschinen mit
mehreren Prozessoren) wird durch NDIS vorgenommen. Die Treiber brauchen sich nicht
darum zu kümmern.

NDIS übernimmt das Binding zwischen den Treibern der verschiedenen Schichten, sorgt also
dafür, dass ein Paket den richtigen Weg durch die Treiber findet.

NDIS ermöglicht Full-Duplex-Kommunikation (was ja, wie oben erwähnt, durch den I/OManager nicht direkt unterstützt wird).

NDIS übernimmt das Loopback bei Kommunikation zwischen Prozessen auf der selben
Maschine.

NDIS bietet den Treibern eine vollständige Funktionsbibliothek an, so dass sie unabhängig von
Kernel, Executive und HAL entwickelt werden können, und deshalb portabel sind.
3.3.3 Beurteilung aus der Sicht von Zero-Copy
Es überrascht natürlich nicht, dass das generische Modell grundsätzlich für die Implementation
eines Treiber für die Unterstützung von Zero-Copy-Kommunikation geeignet ist, da es dem
Programmierer die grösst möglichen Freiheiten lässt. Das Modell an sich ist also durchaus
verwendbar.
NDIS jedoch kann für Zero-Copy-Kommunikation, trotz seiner Vorteile, nicht verwendet werden.
Der Grund liegt darin, dass mehrere Protokolle verwendet werden. Der Datenstrom der Applikation
wird im LAN-Protocol-Layer in Pakete aufgeteilt, mit zusätzlicher Protokollinformation versehen und
an den nächst tieferen Treiber weitergeleitet. Dieses Vorgehen ist zwingend mit Kopierarbeit
verbunden, was der Zero-Copy-Anforderung widerspricht.
3.4 Das Speichermanagement von Windows NT 4.0
Ein kurzer Abriss des Speichermanagements von Windows NT 4.0 soll helfen, die nachfolgenden
Ausführungen zur Zero-Copy-Unterstützung besser zu verstehen. Eine ausführliche Beschreibung
ist Kapitel 5 des Buchs „Inside Windows NT“ von David A. Solomon [8] zu entnehmen.
3.4.1 Datenstrukturen und System-Threads
Der virtuell adressierbare Speicherraum ist unter Windows NT
(Workstation) in zwei je 2 GB grosse Teile unterteilt (siehe Abb.
3.4). Der untere Teil, der User-Space, steht jedem Prozess zur
Verfügung. Der obere Teil, der Kernel-Space, ist dem
Betriebssystem vorbehalten. Wichtiges Detail am Rande: Auch
der Kernel arbeitet mit virtuellen Adressen.
Cache,
Paged pool,
Nonpaged pool
FFFFFFFF
C0800000
Page Tables
C0000000
Kernel, Executive,
Der
Kernel-Space
enthält
neben
dem
Kernel-Code
HAL, Drivers
(NTOSKRNL.EXE, HAL.DLL, Device-Treiber,...), den Page-Tables
80000000
7FFFFFFF
(siehe unten) und dem Cache zwei wichtige Regionen, die
Paged-Pool bzw. Nonpaged-Pool genannt werden. Bei beiden
handelt es sich um Kernel-Mode-Heaps, die, wie die Namen
2 GB per process
bereits andeuten, auslagerbar (paged) bzw. fest im
user space
physikalischen Speicher verankert (nonpaged) sind. Wichtig ist
der Nonpaged-Pool vor allem für Routinen, die auf
DISPATCH_LEVEL oder höher laufen, da dies der einzige
00000000
Speicher ist, der garantiert zugreifbar ist, ohne dass er explizit
gelockt werden müsste. Auf der anderen Seite sollte dieser
Speicher sehr zurückhaltend verwendet werden, um dem Rest Abb. 3.4: Virtueller Adressraum
des System nicht zu viel physischer Speicher zu entziehen.
Die Abbildung von virtuellen auf physikalische Adressen übernimmt der Virtual-Memory-Manager
(VMM). Dieser nutzt eine Reihe von Datenstrukturen (wie in der Übersicht in Abbildung 3.5
dargestellt), um den Zustand des virtuellen und physischen Speichers festzuhalten.
Seite 21
Virtual Address
ETH Zürich
10 bit
10 bit
12 bit
Page frame
Page frame
Page Directory
Page tables
Physical Memory
Page Frame Database
VAD
Zeroed List
per process
VAD
Free List
VAD
Standby List
VAD
VAD
Virtual Address Descriptors
Prototype
Page Table
Modified List
Abb. 3.5: Datenstrukturen des VMM
Der VMM von Windows NT benutzt eine zweistufige Page-Table für die Auflösung von virtuellen
Adressen in ihre physikalischen. Die obersten 10 Bits der virtuellen Adresse werden als Index im
sogenannten Page-Directory benützt. Das Page-Directory enthält 1024 Einträge. Jeder von diesen
Einträgen verweist auf eine Speicherseite, die die zugehörige Page-Table enthält. Page-Tables
werden jedoch nur dann alloziert, wenn sie auch wirklich Einträge enthalten.
Die zweiten 10 Bits werden als Index in dieser Page-Table verwendet. Der Eintrag verweist im
Normalfall auf einen Page-Frame im physikalischen Speicher. Im Falle von Shared-Memory zeigen
die Einträge der Page-Tables aller beteiligten Prozesse nicht direkt auf den Page-Frame, sondern
in eine Prototype-Page-Table, die dann ihrerseits auf den Page-Frame verweist. Diese zusätzliche
Indirektion hat den Vorteil, dass Zustandsinformationen nur an einem Ort verändert werden
müssen.
Die restlichen 12 Bits stellen den Offset innerhalb des 4 kB grossen Page-Frames dar.
Ein Baum von Virtual-Address-Descriptors (VAD) hält für jeden Prozess fest, welche virtuellen
Adressbereiche bereits vergeben sind. Windows NT unterstützt ein zweistufiges Allozieren von
Speicher. Speicherbereiche können reserviert werden. Das heisst, der entsprechende virtuelle
Adressbereich gilt als gebraucht, er wird jedoch noch nicht mit physischem Speicher hinterlegt und
kann dementsprechend auch noch nicht zugegriffen werden. Mit einem Commit kann dem
reservierten Speicherbereich, oder auch nur einem oder mehreren beliebigen Teilen davon,
physikalischer Speicher (ein beliebiges File oder das Page-File und nach einem Page-Fault auch
RAM) zugeordnet werden. Dieses Verfahren erlaubt es, grosse, virtuell zusammenhängende
Speicherbereiche zu reservieren und nach Bedarf mit Speicher zu hinterlegen.
Für die Verwaltung der physikalischen Speicherseiten (Page-Frames genannt) gibt es die PageFrame-Database, die für jede Speicherseite deren Zustand festhält. Die Einträge dieser Datenbank
können durch Pointer verkettet sein, falls sie zu einer speziellen Liste von Seiten gehören. Es gibt
vier solche Listen, die nennenswert sind:

Standby-List: Windows NT bemüht sich, das Working-Set eines jeden Prozesses klein zu
halten. Prozesse, die keine Page-Faults produzieren, sind Kandidaten, um Speicherseiten zu
requirieren. Wenn einem Prozess eine unveränderte Seite weggenommen wird, bleibt diese
eine Zeit in der Standby-List, von wo sie ohne grossen Aufwand dem Prozess zurückgegeben
werden könnte. Scheint der Prozess an der Seite nicht mehr interessiert zu sein, wird sie nach
einiger Zeit in die Free-List eingefügt.
Seite 22
ETH Zürich

Modified-List: Diese Liste enthält, wie die Standby-List, Seiten, die einem Prozess
weggenommen wurden. Diese Seiten wurden jedoch verändert und müssen deshalb vom
Modified-Page-Writer-Thread ins Page-File geschrieben werden.

Free-List: Seiten, die aus den obigen beiden Listen entfernt wurden, werden in die Free-List
gesetzt.

Zeroed-List: An Prozesse im User-Mode werden aus Sicherheitsgründen (C2-Zertifizierung)
nur Seiten abgegeben, die mit Nullen initialisiert wurden. Diese Liste enthält solche
vorbereiteten Seiten.
Neben diesen Datenstrukturen gibt es eine ganze Reihe von System-Threads, die für das
Management zuständig sind:

Balance-Set-Manager: Dieser Thread ist zuständig für die Trimmung der Working-Sets der
Threads.

Swapper: Die Working-Sets von Threads, die längere Zeit im Wait-Zustand verbracht haben,
werden ins Page-File ausgelagert bzw. beim Reaktivieren des Threads wieder eingelesen.

Modified-Page-Writer / Mapped-Page-Writer: Diese beiden Threads schreiben die
veränderten Speicherseiten der Modified-List ins Page-File bzw. ins entsprechende MappedFile.

Zero-Page-Thread: Wenn die Seiten in der Zeroed-List knapp werden, wird der Zero-PageThread Seiten aus der Free-List entfernen, diese mit Nullen initialisieren und in die Zeroed-List
einfügen.
Die Komplexität der Datenstrukturen, sowie die Vielzahl von Threads, die auf diesen Strukturen
operieren und dementsprechend auch synchronisiert werden müssen, verbietet es quasi von
selbst, diese Strukturen dem Programmierer von Device-Treibern offenzulegen. Vielmehr wird eine
Art Kernel-Programming-Interface zur Verfügung gestellt, das unter anderem Operationen auf der
Speicherverwaltung erlaubt. An dieser Stelle wird darauf jedoch nicht im Detail eingegangen. Der
Leser wird dazu auf das Microsoft Windows NT 4.0 DDK [13] verwiesen.
3.4.2 Beurteilung aus der Sicht von Zero-Copy
Nach dieser Einführung in den Memory-Manager von Windows NT wird der Fokus wieder mehr auf
Zero-Copy gelegt. Wie schon erwähnt, gibt es zwei wichtige, hardwareunterstützte Techniken im
Zusammenhang mit Zero-Copy: Memory-Mapping und Direct-Memory-Access. Was diese beiden
Techniken so auszeichnet, ist die Möglichkeit, dass Speicherinhalt ohne Kopieren, sprich ohne
CPU-Einsatz, verschoben werden kann – Zero-Copy eben. Beide Techniken werden von Windows
NT unterstützt.
3.4.2.1 Mapping von Device-Memory
Netzwerkkarten (wie zum Beispiel die Myrinet-Karten von Myricom [16]) können über einen
eigenen Speicher verfügen. Es kann durchaus interessant sein, diesen Speicher direkt in den
virtuellen Adressraum des entsprechenden Prozesses zu mappen.
Diese Möglichkeit gibt es unter Windows NT tatsächlich. Beim Laden des Treibers wird der DeviceSpeicher vorerst in den Nonpaged-Pool des Kernel-Space eingeblendet. Die DriverEntryRoutine müsste folgende Funktionen enthalten:

IoQueryDeviceConfigurationData: Mit dieser Funktion werden Informationen zu einer
Karte in einem bestimmten Slot auf einem bestimmten Bus ermittelt, insbesondere die
busspezifische Adresse des Device-Speichers.

HalTranslateBusAddress: Übersetzt die busspezifische Adresse in eine systemweite,
logische Adresse.

MmMapIoSpace: Die Funktion mapped den Device-Speicher in den virtuellen Adressraum des
Kernels, genauer gesagt in den Nonpaged-Pool.
Seite 23
ETH Zürich
Beim Öffnen eines Device durch einen Prozess (mit CreateFile) oder durch eine Kontrollroutine
(mit DeviceIoControl) könnte der gesamte oder ein Teil des Device-Speichers in den
Adressraum eines Prozesses gemapped werden:

IoAllocateMdl:
Diese
Funktion
alloziert
eine
Start Virtual Address
Memorysogenannte
Byte Offset
Descriptor-List (MDL). MDLs
Byte Count
sind Strukturen, deren Inhalt
Size
zwar undokumentiert ist, die
Process
aber über spezielle Funktionen
zugreifbar sind. Eine MDL
Mapped System VA
enthält die zu einem virtuellen
Physical Address 1
Adressbereich
gehörenden
…
physikalischen
SeitenVirtual Space
Physical Address N
nummern.
Mit
IoAllocateMdl wird der
Memory Descriptor List
MDL die virtuelle KernelSpace-Adresse
des Abb. 3.6: Memory-Descriptor-List [9]
gemappten Device-Speichers
und dessen Grösse mitgegeben.
Physical Memory

MmBuildMdlForNonPagedPool: Mit dieser Funktion werden der MDL die physikalischen
Adressen hinzugefügt, die den gewünschten virtuellen Adressbereich aus dem Nonpaged-Pool
enthalten.

MmMapLockedPages: Schliesslich können mit dieser Funktion die durch die MDL
beschriebenen physikalischen Speicherseiten in den virtuellen Speicherbereich des Prozesses
eingeblendet werden. Die Funktion liefert eine virtuelle Adresse zurück.
Es ist darauf zu achten, dass diese Funktionen nur bei IRQL < DISPATCH_LEVEL aufgerufen
werden dürfen, weil sie im Kontext des aufrufenden Prozesses abgearbeitet werden müssen!
Es ist zwar nicht dokumentiert, wie das Mapping von MmMapLockedPages funktioniert, doch kann
davon ausgegangen werden, dass die bei Shared-Memory ebenfalls verwendeten Prototype-PageTables zum Einsatz kommen.
Der umgekehrte Weg, das heisst das Unmapping, ist mit den Funktionen MmUnmapLockedPages,
IoFreeMdl und MmUnmapIoSpace zu begehen.
3.4.2.2 Direct-Memory-Access (DMA)
Direct-Memory-Access erlaubt es, ohne CPU-Belastung Daten zwischen dem Speicher und einem
Device zu verschieben. Theoretisch wären auch das Verschieben von Device zu Device möglich,
Windows NT unterstützt diese Möglichkeit jedoch nicht.
Der Hardware-Abstraction-Layer von Windows NT abstrahiert die DMA-Controller in sogenannten
Adapter-Objects, die mit dem Aufruf der Funktion HalGetAdapter durch einen Treiber lokalisiert
werden können. Will ein Treiber einen DMA-Kanal benutzen, dann muss er mit
IoAllocateAdapterChannel diesen temporär für sich reservieren lassen.
Die bereits oben erwähnten Memory-Descriptor-Lists (MDL) spielen auch beim DMA eine zentrale
Rolle, da DMA-Controller nicht mit virtuellen Adressen programmiert werden können. Es ist also
wichtig, dass man vom gewünschten virtuellen Speicherbereich eine MDL hat, die die Verweise auf
die entsprechenden physikalischen Seiten enthält. Um von einem Speicher im Kernel-Space eine
MDL zu bekommen kann MmCreateMdl oder MmBuildMdlForNonPagedPool verwendet
werden. User-Space durch eine MDL abzubilden, ist etwas komplizierter, da der Aufbau der MDL
im Kontext des aufrufenden Prozesses geschehen muss. Zudem ist es wichtig, dass der
verwendete Speicher gelockt und allenfalls in den System-Space gemapped wird. Handelt es sich
um einen Direct-I/O-Treiber, dann wird der I/O-Manager den vom User übergebenen
Speicherbereich automatisch locken und eine entsprechende MDL generieren. Möchte man
anderen Speicher verwenden, dann muss zuerst mit IoAllocateMdl eine MDL alloziert und der
Speicher mit MmProbeAndLockPages gelocked werden. Mit MmGetSystemAddressForMdl
Seite 24
ETH Zürich
kann der Speicher, falls gewünscht, in den Kernel-Space gemapped werden, wo er unabhängig
vom aktuellen Thread-Kontext zugreifbar ist.
Ein wesentliches Problem beim DMA-Transfer ist die Tatsache, dass zusammenhängender
virtueller Speicher nicht unbedingt auch zusammenhängender physischer Speicher sein muss. Die
meisten DMA-Controller erlauben lediglich die Programmierung einer physischen Startadresse und
einer Länge, manche Controller können mehrere solche Paare aufnehmen. Bei sehr grossen
Speicherbereichen wird es jedoch wegen Fragmentierung unweigerlich mehrere DMA-Transfers
brauchen. Es wäre deshalb nützlich, gezielt physisch zusammenhängender Speicher allozieren zu
können. Windows NT erlaubt durch die Funktion MmAllocateContiguousMemory die Allokation
von zusammenhängendem Speicher im Nonpaged-Pool des Kernel-Space. Je grösser der
gewünschte Speicherbereich ist und je später die Funktion aufgerufen wird, desto
unwahrscheinlicher wird es, dass das System dem Wunsch entsprechen kann. Deshalb wird
empfohlen, diese Funktion bereits in der DriverEntry-Routine aufzurufen.
Ein wichtiges Detail sind die Caches. Da ein DMA-Transfer ohne Kontrolle des CPUs abläuft,
müssen Cache-Einträge, die zum betroffenen, physischen Speicher gehören, vor dem Transfer
geleert werden, um sicher zu gehen, dass der Speicher die neusten Daten enthält.
KeFlushIoBuffers übernimmt diese Funktion.
Beim eigentlichen Transfer spielt die Funktion IoMapTransfer eine zentrale Rolle. Diese
Funktion bestimmt aus der übergebenen MDL einen physisch zusammenhängenden
Speicherbereich und ermittelt die Adresse und die Länge des Bereichs. Handelt es sich beim DMAController um einen Slave-DMA-Controller (auf dem Motherboard), dann programmiert
IoMapTransfer diesen Controller automatisch und startet den Transfer. Ist der DMA-Contoller
jedoch ein Master-DMA-Controller (auf einem Device), dann gibt IoMapTansfer die Adresse und
Länge zurück, und der Treiber muss den Controller selber programmieren. Danach stellt der
Treiber seine Arbeit ein und wartet auf den Interrupt, der das Ende des Transfers signalisiert. Bei
fragmentiertem, physischem Speicher muss IoMapTransfer natürlich mehrmals aufgerufen
werden.
Am Ende des oder der Transfers muss mit IoFreeAdapterChannel der DMA-Kanal wieder
freigegeben werden.
Ausführliche Informationen über DMA unter Windows NT 4.0 können im „The Windows NT Device
Driver Book“ von Art Baker [9] Kapitel 12 „DMA Drivers“ nachgelesen werden.
Seite 25
Seite 26
ETH Zürich
ETH Zürich
4 Die Schnittstellen zum Message-Passing- und DSM-Layer
Auf die Zero-Copy-Kommunikation sollen zwei
unterschiedliche
Modelle
der
parallelen
Programmierung aufbauen: Message-Passing
und Distributed-Shared-Memory (DSM). Deren
oberen Schnittstellen sind durch gängige
Definitionen festgelegt: Für Message-Passing
wird MPI [7], für Distributed-Shared-Memory
OpenMP [2] angenommen.
MPI
OpenMP
Message Passing
Distributed
Shared Memory

ó
Zero-Copy-Communication
Network
Zwei so unterschiedliche Modelle sollen auf
einem Kommunikationslayer aufbauen. Dieses Abb. 4.1: Die inneren Schnittstellen
Kapitel klärt ab, wie die Schnittstellen zwischen
den beiden Modellen und einem Zero-Copy-Layer (Abbildung 4.1) auszusehen haben, welche
Anforderungen gestellt werden, sowie welche Übereinstimmungen bzw. Differenzen zwischen den
Schnittstellen bestehen.
Grundsätzlich muss jedoch von den beiden Zero-Copy-Kommunikationsarten bzw. deren
Schnittstellen ausgegangen werden. Auf Grund der folgenden Analyse kann es jedoch sein, dass
diese Schnittstellen etwas erweitert werden müssen.
4.1 Die Schnittstelle zwischen Message-Passing- und Zero-Copy-Layer
Die zu betrachtende Schnittstelle definiert sich einerseits durch die Zero-Copy-Aspekte,
andererseits durch die MPI-Funktionalitäten, die der Message-Passing-Layer nicht implementieren
kann. Die folgende Betrachtung beschränkt sich auf die Kommunikationsaspekte des MPI-Paketes.
Dabei können im wesentlichen drei Typen unterschieden werden:

Punkt-zu-Punkt-Kommunikation: MPI bietet Senden und Empfangen in vielen Varianten an:
blockierend oder nicht-blockierend, gepuffert oder synchronisiert.

Kollektive Kommunikation (Punkt-zu-mehr-Punkt, mehr-Punkt-zu-mehr-Punkt): Neben dem
Broadcast sind diverse Varianten von Scatter, Gather und AllToAll vorhanden.

Synchronisation: Die Barrier als einziges Synchronisationsobjekt ist ein Spezialfall der
kollektiven Kommunikation.
4.1.1 Punkt-zu-Punkt-Kommunikation
Die Punkt-zu-Punkt-Kommunikation ist die einfachste Kommunikationsart. Paarweise treten je eine
Sende- und eine Empfangsfunktion folgender Art auf:
MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm);
MPI_Recv(void* buf, int count, MPI_Datatype datatype, int dest, int tag,
MPI_Comm comm, MPI_Status *status);
Dieses Funktionspaar gibt es blockierend und nicht-blockierend. Zudem werden verschiedene
Modi unterstützt: Buffered ist ein unsynchronisierter Modus. Die Meldung wird
zwischengespeichert, falls der Empfänger nicht empfangsbereit ist. Der Synchronous-Modus
synchronisiert Sender und Empfänger bevor gesendet wird. Im Ready-Modus ist Senden nur dann
erfolgreich, wenn der Empfänger bereit ist.
Das Vorhandensein von nicht-blockierenden MPI-Funktionen zieht automatisch nach sich, dass
auch die Funktionen der betrachteten Schnittstelle nicht-blockierend sein müssen (es sei denn, die
Kommunikation wird in zusätzlichen Threads untergebracht). Blockierende MPI-Funktionen können
ohne weiteres auf die nicht-blockierenden Funktionen und MPI_Wait aufgebaut werden.
MPI kennt eine Thread-zu-Thread-Kommunikation (Abbildung 4.2). Jeder MPI-Thread wird mit
einem Rank, einer eindeutigen Nummer, identifiziert. Untere Schichten der Kommunikation werden
mit diesem Rank kaum etwas anfangen können. Deshalb muss innerhalb des Message-PassingLayers eine Abbildung vorgenommen werden. An der Schnittstelle wird also nicht ein Rank,
sondern eine von den unteren Schichten verstandene Adressform übergeben. Im folgenden
Seite 27
ETH Zürich
werden diese Adressen mit SendID und
RecvID bezeichnet. Erlauben die unteren
Schichten nur eine Knoten-zu-KnotenKommunikation (wie z.B. GM), dann kann
von diesen bestenfalls der Knoten des
Absenders identifiziert werden. Ohne
zusätzliche Information im Datenpaket
kann weder der exakte Absender-Thread,
noch der gewünschte Empfänger-Thread
ermittelt werden.
Thread-zu-Thread
Knoten-zu-Knoten
Abb. 4.2: Zwei unterschiedliche Kommunikationsmuster
4.1.1.1 Der Buffered-Modus (MPI_Bsend)
Dieser Modus widerspricht der Zero-Copy-Kommunikation eigentlich von Grund auf, denn gepuffert
soll ja nicht mehr werden, da dies in der Regel Kopiervorgänge nach sich zieht.
Grundsätzlich kann dieser Modus mittels der unsynchronisierten Kommunikationsart des ZeroCopy-Layers implementiert werden. Die beiden Nachteile dieser Kommunikationsart müssen
jedoch uneingeschränkt an die MPI-Schnittstelle weitergegeben werden:

Unsynchronisierte Datenpakete unterliegen einer maximalen Grösse. Diese Beschränkung
muss daher auch für MPI-Meldungen, die im Buffered-Modus verschickt werden, gelten.

Der Zero-Copy-Layer ist zuständig für die Empfangspuffer. Es wird also nicht direkt in den
Speicherbereich der MPI-Applikation empfangen. Daher ist Kopieren beim Empfänger
unumgänglich.
Auch auf Senderseite ist Kopieren notwendig, da die eigentliche Meldung und das Tag nicht
zwingend in einem zusammenhängenden Speicherbereich plaziert sein müssen. Bei Knoten-zuKnoten-Kommunikation muss dem Datenpaket zudem eine Sender- und Empfängeridentifikation
mitgegeben werden. Nach dem Kopieren könnte eine Meldung folgendermassen aussehen:
SendID
RecvID
Tag
Data 0
...
Data Len-1
Würde über klassische Protokolle kommuniziert, dann müsste diese Meldung im Header noch die
Länge des nachfolgenden Datenblocks (Len) enthalten. Bei Zero-Copy-Kommunikation ist das
nicht notwendig. Jede Meldung muss ja in einen separaten Empfangspuffer abgelegt werden. Das
heisst also, dass die unteren Schichten verantwortlich sind, die Länge des Paketes zu verwalten.
Diese Länge wird beim Recv den oberen Schichten mitgeteilt. Aus dieser Länge minus der Grösse
des Headers errechnet sich Len.
Die Schnittstelle müsste ungefähr folgende Funktionen enthalten. Diese decken sich vollständig mit
den Funktionen des unsynchronisierten Sendens, wie es in Kapitel 2 vorgestellt wurde:
SendAsync(int nRecvID, void* pBuffer, int nLen);
RecvAsync(int& nSendID, void*& pBuffer, int& nLen);
Von Zero-Copy kann bei diesem Modus nicht mehr gesprochen werden. Doch da die Meldungen
sowieso grössenmässig beschränkt sind, ist der Performanceverlust durch das Kopieren nicht all
zu tragisch.
4.1.1.2 Der Synchronous-Modus (MPI_Ssend)
Dieser Modus entspricht vollständig der synchronisierten Kommunikationsart des Zero-CopyLayers: Es wird erst dann gesendet, wenn der Empfänger bereit ist. Die Synchronisation wird durch
den Zero-Copy-Layer übernommen. Der Empfangsbereitschaftsmeldung müssen jedoch ein paar
Daten mitgegeben werden: Neben der virtuellen Adresse des Empfangspuffers (und
sicherheitshalber dessen Grösse) muss auch das Tag und bei Knoten-zu-Knoten-Kommunikation
eine
Identifikation
des
Senders
und
Empfängers
enthalten
sein.
Die
Empfangsbereitschaftsmeldung hat also folgenden Aufbau:
Seite 28
ETH Zürich
Adresse des Empfangspuffer
Grösse des Empfangspuffer
Tag
SendID
RecvID
Diese Daten müssen der Empfangsfunktion mitgegeben werden. Auch die Sendefunktion verlangt
das Tag und eventuell die Sender- und Empfängeridentifikation. Im Zero-Copy-Layer können so
die Informationen der Sendefunktion mit denen der Empfangsfunktion verglichen werden. Stimmen
alle Daten überein, dann ist die Empfangsbereitschaft für eine bestimmte Meldung bestätigt, und
es kann gesendet werden.
Die Funktionen der Schnittstelle (der erste Parameter ist nur bei Knoten-zu-Knoten-Kommunikation
notwendig):
SendSync(int nSendID, int nRecvID, int nTag, void* pBuffer, int nLen);
RecvSync(int nRecvID, int nSendID, int nTag, void* pBuffer, int& nLen);
Damit ist der eigentliche Transport der Meldung realisierbar, und in den meisten Fällen würde dies
auch genügen. Nur wenn die Empfangsfunktion mit den Wildcards MPI_ANY_SOURCE oder
MPI_ANY_TAG verwendet wird, gibt es
MPI_Ssend
MPI_Recv
ein Problem: Welchem Sender soll
eine Empfangsbestätigung gesendet
SendID
RecvID
werden? Und welches Tag hat nun die
SendAsync
RecvAsync
Tag
empfangene Meldung? Gelöst wird
Len
dieses Problem, indem der MessageSendID
Passing-Layer des Senders eine
RecvID
SendSync
RecvSync
Tag
kleine
Meldung
an
den
Address
Len
entsprechenden
Empfänger-Layer
schickt, die seine Sendeabsichten und
das Tag enthalten (Abbildung 4.3).
Message
Nun kennt der Empfänger den
Absender und das Tag und kann seine
Abb. 4.3: Kommunikationsmuster von MPI_Ssend
Empfangsbereitschaft mitteilen.
4.1.1.3 Der Ready-Modus (MPI_Rsend)
Der Ready-Modus ist wie MPI_Ssend eine synchronisierte Variante. Die Bereitschaft des
Empfängers muss jedoch bereits bestätigt sein, bevor die Sendefunktion aufgerufen wird, sonst ist
der Sendevorgang fehlerhaft. Das heisst dann aber auch, dass der Empfänger nicht mit Wildcards
arbeiten kann. Deshalb muss auch keine Sendeabsicht an den Empfänger geschickt werden.
Das bedeutet für den Zero-Copy-Layer, dass es zwei Varianten der synchronisierten
Kommunikation gibt: Eine, die das Senden verzögert, bis die Empfangsbereitschaft signalisiert
wird, und eine, die nur sendet, wenn die Bereitschaft bereits signalisiert ist und sonst mit einer
Fehlermeldung zurückkehrt.
Die Schnittstelle erweitert sich also leicht:
SendSync(int nSendID, int nRecvID, int nTag, void* pBuffer, int nLen, BOOL fWait);
RecvSync(int nRecvID, int nSendID, int nTag, void* pBuffer, int& nLen);
Für den Synchronous-Modus ist fWait gleich TRUE, für den Ready-Modus FALSE.
Die allgemeine MPI_Send-Funktion kann gemäss Spezifikation auf eine dieser Modi zurückgreifen.
4.1.2 Kollektive Kommunikation
Als MPI-Funktionen für die kollektive Kommunikation gelten MPI_Bcast, MPI_Scatter,
MPI_Gather, MPI_Alltoall und Varianten davon. Es ist unschwer einzusehen, dass all diese
Seite 29
ETH Zürich
Funktionen mittels den oben besprochenen (nicht-blockierenden) Punkt-zu-Punkt-Funktionen
emuliert werden können, so dass die Schnittstelle nicht verändert werden müsste. Der MessagePassing-Layer wäre dann für die Implementation dieser Funktionen auf der bestehenden
Schnittstelle verantwortlich. Aber ist das auch sinnvoll?
4.1.2.1 MPI_Bcast
Viele lokale Netzwerktechnologien bauen auf sogenannten Broadcast-Medien auf. Verschiedene
Kommunikationsprotokolle können auch Broadcast-Funktionen anbieten. Doch das Problem ist,
dass ein MPI-Broadcast kein netzweiter Broadcast sein muss. Eine MPI-Applikation muss noch
lange nicht auf allen Rechnern des Netzwerks laufen. Es müsste also von einer unteren Schicht
eine Art Multicast angeboten werden, was leider nur all zu selten der Fall ist, und hier deshalb nicht
weiter betrachtet wird. Es wird also der Aufbau auf den Punkt-zu-Punkt-Funktionen empfohlen.
4.1.2.2 MPI_Scatter, MPI_Gather, MPI_Alltoall
Diese drei Funktionen (und alle Varianten von diesen) erscheinen bei flüchtigem hinsehen als
Multicast-Funktionen. Dem ist aber nicht so, denn es wird nicht ein Paket an mehrere geschickt,
sondern mehrere verschiedene Pakete an verschiedene Empfänger. Allfällige Multicast-Funktionen
der unteren Schichten können also nicht ausgenutzt werden. So bleibt eigentlich nur der Aufbau
auf den Punkt-zu-Punkt-Funktionen. Es fällt nur noch eine Diskrepanz ins Auge: Die kollektiven
Funktionen benutzen kein Tag. Das Tag kann deshalb dafür verwendet werden, dem Empfänger
mitzuteilen, dass die empfangene Meldung nicht durch MPI_Send verschickt wurde, sondern durch
eine kollektive Form. Dies bedingt jedoch, dass einige Tags reserviert werden, und damit dem
Benutzer nicht mehr zur Verfügung stehen. Doch das ist kein Problem, da MPI mit MPI_TAG_UB
eine Obergrenze für Tags kennt, die implementationsabhängig sein kann.
Kurz: Alle kollektiven Kommunikationsformen werden auf den Punkt-zu-Punkt-Funktionen
aufgebaut. Die bereits definierte Schnittstelle wird nicht erweitert. Einzig die Tags werden
eingeschränkt, doch das ist eine Sache der (oberen) MPI-Schnittstelle.
4.1.3 Synchronisation
Als explizites Synchronisationselement existiert in MPI nur
die sogenannte Barrier. Sie ist eigentlich nur ein
Spezialfall einer kollektiven Kommunikation: Entweder ist
eine Barrier eine spezielle MPI_Alltoall-Funktion, die
allen mitteilt, dass der Sender an der Barrier angelangt ist
und gleichzeitig darauf wartet, dass er von allen anderen
die selbe Mitteilung erhält (dezentale Variante). Oder es
MPI_Alltoall
MPI_Gather
wird mittels MPI_Gather die Ankunft an der Barrier
MPI_Scatter
einem dedizierten Koordinator mitgeteilt und danach mit
MPI_Scatter darauf gewartet, dass der Koordinator die Abb. 4.4: Dezentrale bzw. zentrale
Barrier-Variante
Ankunft aller Knoten bestätigt (zentrale Variante).
Da an Synchronisationspunkten sowieso immer Wartezeiten auftreten, lohnt sich eine Optimierung
an dieser Stelle nicht. Eine Barrier wird also auf den kollektiven MPI-Funktionen bzw. auf den
Punkt-zu-Punkt-Funktionen aufbauen, wobei wiederum ein Tag für diesen Zweck reserviert werden
muss.
4.1.4 Die Schnittstelle
Zusammenfassend kann also folgende Schnittstelle zwischen Message-Passing-Layer und ZeroCopy-Layer definiert werden:

SendAsync([in] int nRecvID, [in] void* pBuffer, [in] int nLen);
Es wird ein durch pBuffer und nLen definiertes Datenpaket an den Empfänger nRecvID
unsynchronisiert verschickt. Die Grösse des Paketes ist beschränkt.

RecvAsync([out] int& nSendID, [out] void*& pBuffer, [out] int& nLen);
Empfängt ein unsynchronisiert verschicktes Datenpaket von einem beliebigen Sender. Neben
dem Pointer auf das Datenpaket (pBuffer) und dessen Länge (nLen) wird auch der
Seite 30
ETH Zürich
Absender (nSendID) identifiziert. Bei Knoten-zu-Knoten-Kommunikation identifiziert nSendID
jedoch nur den Knoten. Allfällige weitere Informationen über Absender und Empfänger müssen
im Datenpaket enthalten sein.

SendSync([in] int nSendID, [in] int nRecvID, [in] int nTag,
[in] void* pBuffer,[in] int nLen, [in] BOOL fWait);
Synchronisiertes Senden eines Datenpaketes (pBuffer, nLen). Gesendet wird das Paket,
wenn eine Empfangsbereitschaftsmeldung mit übereinstimmenden Parametern empfangen
wurde. fWait bestimmt, ob auf eine Bestätigung gewartet wird, oder ob bei fehlender
Bestätigung mit einer Fehlermeldung reagiert wird. nSendID ist nur bei Knoten-zu-KnotenKommunikation notwendig.

RecvSync([in] int nRecvID, [in] int nSendID, [in] int nTag,
[in] void* pBuffer, [in/out] int& nLen);
Diese Funktion sendet eine Empfangsbereitschaftsmeldung mit allen Parametern an den
Sender (nSendID). Danach wird auf den Empfang gewartet. nRecvID ist nur bei Knoten-zuKnoten-Kommunikation notwendig.
4.2 Die Schnittstelle zwischen DSM- und Zero-Copy-Layer
Distributed-Shared-Memory ist zwar ein ganz anderes Modell als Message-Passing. Da jede
Netzwerktechnologie eine Art von Message-Passing darstellt, bleibt jedoch nichts anderes übrig,
als die anfallende Kommunikation auf ein Message-Passing-Modell abzubilden. Es ist deshalb
vorteilhaft, bereits an der zu betrachtenden Schnittstelle auf Message-Passing aufzubauen.
Grundsätzlich würde das heissen, dass die in Kapitel 4.1 definierte Schnittstelle zwischen ZeroCopy-Layer und Message-Passing-Layer verwendet werden könnte. Eine genauere Betrachtung
soll jedoch abklären, ob allenfalls Vereinfachungen möglich sind, oder ob durch Veränderungen
der Schnittstelle eine grössere Performance resultieren könnte.
Was Zero-Copy-Kommunikation betrifft, kann ein DSM-System gegenüber Message-Passing mit
zwei Vorteilen aufwarten. Erstens: Die Kommunikation ist nur sehr lose mit der DSM-Schnittstelle
(z.B. OpenMP) gekoppelt. Der DSM-Layer kann also optimal auf die Zero-Copy-Direktiven
eingestellt werden. Und zweitens: Obwohl ein DSM-System durchaus mit mehreren lokalen
Threads arbeiten kann, ist in vielen Fällen nur Knoten-zu-Knoten-Kommunikation notwendig.
Zusätzliche Sender- und Empfängeridentifikation ist also nicht unbedingt notwendig. Es wird jedoch
davon ausgegangen, dass der Empfänger den Absenderknoten identifizieren kann.
Je nach Implementation kennt ein DSM-System drei typische Kommunikationsmuster, die genauer
betrachtet werden müssen:
4.2.1 Der Page-Request
Mit dem Page-Request kann ein Knoten eine gültige Kopie einer Speicherseite bei einem
entfernten Knoten anfordern. Identifiziert wird die gewünschte Seite durch eine Nummer. Diese
Nummer und die lokale, virtuelle Adresse, an der diese Seite positioniert ist, müssen dem
entfernten Knoten mitgeteilt werden. Da diese Mitteilung als Signalisation der
Empfangsbereitschaft aufgefasst werden kann, könnte der Page-Request in einen RecvSync und
damit Nummer und Adresse in die Empfangsbereitschaftsmeldung verpackt werden. Auf eine
Länge kann verzichtet werden, da diese immer der Grösse einer Speicherseite entspricht. Dieses
Paket hätte also den folgenden Aufbau:
Adresse der Speicherseite
Nummer der Speicherseite
Der Page-Request würde mit der folgenden Funktion ausgelöst:
RecvSync(int nSendID, int nPageNo, void* pPageAddr);
Der in Kapitel 2 kurz beschriebene Zero-Copy-Layer hat die Eigenschaft, dass
Empfangsbereitschaftsmeldungen nur innerhalb des Layers existieren, also nicht an obere Layer
weitergegeben werden. Dies würde bedeuten, dass der DSM-Layer nicht über den Page-Request
Seite 31
ETH Zürich
informiert würde. Eine Modifikation des Zero-Copy-Layers ist also notwendig: Die
Empfangsbereitschaftsmeldung ist eigentlich nichts anderes als ein unsynchronisiert verschicktes
Datenpaket mit speziellem Inhalt. Dieses Paket könnte ohne grossen Aufwand an den oberen
Layer propagiert werden. Der obere Layer benutzt dann eine ganz gewöhnliche RecvAsyncFunktion, um das Paket zu empfangen:
4.2.2 Der Page-Reply
Auf einen empfangenen Page-Request muss ein entsprechender Page-Reply erfolgen: Eine
Speicherseite des lokalen Knotens muss an die entsprechende Stelle im entfernten System
transportiert werden. Da der Page-Request bereits die Empfangsbereitschaft signalisiert und die
Empfangsadresse dem Zero-Copy-Layer mitgeteilt hat, kann die Seite über einen SendSync
verschickt werden. Die entsprechende Funktion kann folgendermassen aussehen:
SendSync(int nRecvID, int nPageNo, void* pSourcePageAddr);
Mittels nRecvID und nPageNo würde die bereits empfangene Empfangsbereitschaftsmeldung und
damit auch die Zieladresse auf dem entfernten System identifiziert.
Da mit der Empfangsbereitschaftsmeldung auch die Zieladresse an den DSM-Layer propagiert
wurde, könnte auch folgende Variante angewendet werden:
SendSync(int nRecvID, void* pSourcePageAddr, void* pTargetPageAddr);
Damit könnte ein Zwischenspeichern der Empfangsbereitschaftsmeldung im Zero-Copy-Layer
vermieden werden.
Allgemeine DSM-Systeme kennen verschiedene Synchronisationsdirektiven. Dabei können beide
in Kapitel 4.1.3 beschriebenen Varianten (zentral oder dezentral) zum Einsatz kommen. Bei vielen
dieser Direktiven werden auch zusätzliche Information mitgeschickt.
Stellvertretend soll hier eine Barrier betrachtet werden, die zusätzlich die Nummern der durch
einen Knoten veränderten Speicherseiten enthalten soll. Wenn die mitgeschickten Daten den
Umfang eines unsynchronisierten Paketes nicht übersteigen, dann wird vorteilhaft unsynchronisiert
Kommuniziert. Eine ID muss das Datenpaket als Barrier identifizieren. Danach kommen die
Seitennummern.
SyncID
PageNo
...
PageNo
Dieses Paket wird über ein normales SendAsync/RecvAsync-Funktionspaar gesendet bzw.
empfangen:
SendAsync(int nRecvID, void* pBuffer, int nLen);
Da auch die propagierten Page-Requests durch RecvAsync empfangen werden, muss die SyncID
so gewählt werden, dass diese keine gültige Speicherseite darstellt.
Grössere Pakete können entweder durch mehrere unsynchronisierte Pakete oder aber
synchronisiert verschickt werden:
SendSync(int nRecvID, int nSyncID, void* pBuffer, int nLen);
RecvSync(int nSendID, int nSyncID, void* pBuffer, int& nLen);
Da beim Page-Request die Empfangsbereitschaftsmeldung an den DSM-Layer propagiert wird,
würde dies auch hier geschehen. Ein solches Paket könnte vom DSM-Layer ignoriert werden. Es
muss jedoch darauf geachtet werden, dass SyncID keine gültige Seitenadresse darstellt, damit
eine propagierte Empfangsbereitschaftsmeldung eines Page-Request von einer Barrier
unterschieden werden könnte.
Seite 32
ETH Zürich
4.2.4 Die Schnittstelle
Zusammenfassend kann also folgende Schnittstelle für ein DSM-System empfohlen werden:

SendSync([in] int nRecvID, [in] int nPageNo,
[in] void* pSourcePageAddr);
Page-Reply: Eine Speicherseite wird an ein entferntes System geschickt.

RecvSync([in] int nSendID, [in] int nPageNo,
[in] void* pTargetPageAddr);
Page-Request: Es wird eine Speicherseite von einem entfernten System verlangt. Die
Empfangsbereitschaftsmeldung enthält nPageNo und pTargetPageAddr und wird an den
DSM-Layer propagiert.

Synchronisationsdirektiven wie Barriers verwenden vorteilhaft ein (oder mehrere)
unsynchronisierte Datenpakete. Das Paket muss eine ID zur Erkennung tragen.

Empfängt entweder die Pakete von Synchronisationsdirektiven oder die propagierten Pakete
des Page-Requests.
4.3 Ein Vergleich der Schnittstellen
Betrachtet man die beiden Schnittstellen, dann gibt es einen grossen Unterschied: Während
Message-Passing eine Thread-zu-Thread-Kommunikation benötigt, gibt sich das DSM-System mit
Knoten-zu-Knoten-Kommunikation zufrieden. Falls das unter dem Zero-Copy-Layer liegende
Kommunikationssystem Thread-zu-Thread-Kommunikation anbietet (zum Beispiel in Form von
Ports), dann kommt dieser Unterschied nicht wirklich zum Tragen. Falls dies nicht der Fall ist, dann
müssen beim Message-Passing-Modell zusätzliche Sender- und Empfängeridentifikationen
kommuniziert werden. Da diese Arbeit auf Myricom-GM aufbaut bzw. aufbauen wollte, wird vom
zweiten Fall ausgegangen.
Zwei Spezialbehandlungen unterscheiden die beiden Systeme desweiteren: Das DSM-System wird
aus Performancegründen die Empfangsbereitschaftsmeldung des RecvSync an den oberen Layer
propagieren. Das Message-Passing-System erwartet beim SendSync ein Flag, das aussagt, ob auf
eine Empfangsbereitschaftsmeldung gewartet werden soll oder nicht. Diese beiden Spezialfälle
lassen sich jedoch leicht beim Initialisieren des Zero-Copy-Layers aktivieren bzw. deaktivieren.
Eine gemeinsame Schnittstelle könnte in etwa folgende Funktionen enthalten:

Verschickt ein Datenpaket beschränkter Grösse auf unsynchronisierte Art. Der Header des
Datenpaketes wird eine Identifikation (Tag/SyncID) und eventuell Sender- und
Empfängerinformationen enthalten.

Empfängt ein unsynchronisiert verschicktes Datenpaket von einem beliebigen Sender. Neben
dem Pointer auf das Datenpaket (pBuffer) und dessen Länge (nLen) wird auch der
Absender (nSendID) identifiziert. Bei Knoten-zu-Knoten-Kommunikation identifiziert nSendID
jedoch nur den Knoten. Eine Identifikation des Inhalts und allfällige weitere Informationen über
Absender und Empfänger müssen im Datenpaket enthalten sein.

SendSync([in] int nSendID, [in] int nRecvID, [in] int nID,
[in] void* pBuffer,[in] int nLen, [in] BOOL fWait);
Synchronisiertes Senden eines Datenpakets (pBuffer, nLen). Gesendet wird das Paket,
wenn eine Empfangsbereitschaftsmeldung mit übereinstimmenden Parametern empfangen
wurde. nID ist eine Identifikation des Datenpaketes (Tag/PageNo). fWait bestimmt, ob auf
eine Bestätigung gewartet wird, oder ob bei fehlender Bestätigung mit einer Fehlermeldung
reagiert wird. nSendID ist nur im Message-Passing-Layer unter Verwendung von Knoten-zuKnoten-Kommunikation relevant.
Seite 33

ETH Zürich
RecvSync([in] int nRecvID, [in] int nSendID, [in] int nID,
[in] void* pBuffer, [in/out] int& nLen);
Diese Funktion sendet eine Empfangsbereitschaftsmeldung mit allen Parametern an den
Sender (nSendID). Danach wird auf den Empfang gewartet. nID ist eine Identifikation des
gewünschten Datenpaketes (Tag/PageNo). nRecvID ist nur im Message-Passing-Layer unter
Verwendung von Knoten-zu-Knoten-Kommunikation relevant.
Eine gemeinsame Schnittstelle für die beiden Systeme Message-Passing und DSM ist also sehr
gut möglich. DSM hat eventuell etwas unnötigen Overhead: Sender-/Empfängeridentifikation sowie
die Paketlänge, die beim DSM konstant die Grösse einer Page ist, wären beim synchronisierten
Senden und Empfangen nicht notwendig. Da sich diese Informationen jedoch auf die
Empfangsbereitschaftsmeldung der RecvSync-Funktion beschränken, kann dieser Overhead ohne
Bedenken in Kauf genommen werden.
Die eigentlichen Kommunikationsfunktionen der Schnittstelle wurden soeben ausführlich
besprochen. Ein vollständig implementierter Layer dürfte über einige weitere Funktionen verfügen.
Ein Aspekt, der bisher noch nicht betrachtet wurde, ist die Deallokation der Puffer für
unsynchronisierten Empfang. Die Puffer werden ja nicht von der Applikation, sondern vom ZeroCopy-Layer alloziert. Über die Funktion RecvAsync gelangen diese jedoch in den Besitz der
Applikation. Entweder wird die Applikation für die Deallokation verantwortlich gemacht, oder besser
noch, es gibt eine Funktion, mittels welcher die Applikation den Puffer dem Layer zurückgeben
kann:
ReleaseAsyncBuffer(void* pBuffer);
Welche weiteren Funktionen nötig sein können, kann der konkreten Implementation, beschrieben
im folgenden Kapitel, entnommen werden.
Seite 34
ETH Zürich
5 Der Zero-Copy-Layer
In Kapitel 2 wurde ein Kommunikationsmuster vorgestellt, das auf unsynchronisierten kleinen und
synchronisierten grossen Paketen beruht (siehe Abbildung 2.1). Dieses Konzept wurde im ZeroCopy-Layer realisiert, der sowohl vom MPI- wie auch vom OpenMP-Prototypen (siehe Kapitel 6
und 7) verwendet wird. Die beschriebene Schnittstelle wurde jedoch nicht vollständig und aus
praktischen Gründen in einer etwas variierten Form implementiert.
Der Zero-Copy-Layer ist unabhängig von der verwendeten Netzwerktechnologie. Die abhängigen
Teile wurden im darunterliegenden Netzwerk-Layer implementiert.
SendAsync
SendSync
success/
pending/
error
success/
pending/
error
no
pending/
error
CheckRequests
success/
error
Zero Copy Layer
Ready?
CallBack
RecvSync
Send
List
yes
Recv
List
Ready
yes
no
yes
Ready?
no
Norm?
AsyncRecv
success/
pending/
error
SendDone
NwCheckRequests
done
Sending List
Request
Reply
Controll
Network Layer
NwSendSync
success/
pending/
error
SyncRecv
Abb. 5.1: Schema der Request-Verwaltung im Zero-Copy-Layer
Die Abbildung 5.1 zeigt deutlich, dass dieses Konzept in Wirklichkeit deutlich komplexer ist, als
dies Abbildung 2.1 erahnen liesse. Deshalb werden hier die Abläufe und Schnittstellen etwas
genauer erklärt.
5.1 Die Requests
Senden und Empfangen ist immer mit Informationen wie Sender- und Empfängeridentifikation,
Datenidentifikation (Tag), Länge der Daten und den Daten selbst verbunden. All diese
Informationen werden in sogenannte Requests verpackt. Für asynchrone Kommunikation enthält
der Request die eigentlichen Daten, für synchrone Kommunikation nur einen Pointer auf die Daten.
Applikationen, die über den Zero-Copy-Layer senden oder empfangen wollen, müssen zuerst
einen Request mit den nötigen Daten initialisieren und dem Zero-Copy-Layer übergeben. Dieser
kann den Request entweder sofort bearbeiten, oder zurückstellen. Im zweiten Fall bleibt der
Request solange im Besitz des Zero-Copy-Layers, bis er bearbeitet und über die Call-BackFunktion (siehe unten) an die Applikation zurückgegeben wurde.
Für jede Operation gibt es einen Request: Für asynchrones Senden (Async-Send) und Empfangen
(Async-Recv), für synchrones Senden (Sync-Send) und Empfangen (Sync-Recv), sowie für das
Synchronisieren (Ready).
Der konkrete Aufbau der Requests ist in Kapitel 5.3.1 dargestellt.
Seite 35
ETH Zürich
5.2 Die Abläufe
Der Zero-Copy-Layer kann auf Netzwerktechnologien mit den verschiedensten Eigenschaften
aufbauen. Während das Empfangen zwangsläufig nicht-blockierend sein muss, kann das Senden
sowohl blockierend wie auch nicht-blockierend sein. Je nach Netzwerk-Layer kann die Applikation
durch Pollen feststellen, ob Daten empfangen oder (nicht-blockierend) gesendet wurden, oder es
wird ihr durch einen anderen Mechanismus (z.B. Asynchronous-Procedure-Calls) ohne Polling
mitgeteilt.
5.2.1 Initialisieren der Layer und Erstellen der Verbindungen
Egal, ob die unter dem Netzwerk-Layer liegende Netzwerkarchitektur verbindungsorientiert arbeitet
oder nicht, eine Applikation, die den Zero-Copy-Layer benutzt, hat zu jedem Knoten eine
„Verbindung“ aufzubauen. Für das Aufbauen der Verbindung (falls notwendig) ist der NetzwerkLayer zuständig. Spätestens nach dem Verbindungsaufbau muss der Netzwerk-Layer
Empfangsbereitschaft garantieren können. Das heisst unter anderen auch, dass bereits genügend
Empfangspuffer für den asynchronen Empfang bereitgestellt wurden. Falls die Schicht unter dem
Netzwerk-Layer nicht verbindungsorientiert arbeitet, kann die Empfangsbereitschaft auch bereits
beim Initialisieren des Layers erstellt und der Wunsch nach Verbindungsaufbau ignoriert, sprich die
entsprechende Funktion leer gelassen werden.
5.2.2 Call-Back-Funktion
In jedem Fall hat die
Applikation dem ZeroApplikation
Zero-Copy-Layer
Netzwerk-Layer
Copy-Layer den Pointer
RegisterCallBack
auf eine Call-BackFunktion
mitzuteilen,
CheckRequests
CheckRequests
welche
vom
Layer
aufgerufen wird, wenn
für jedes unsynchronisiert
AsyncRecv
CallBackFunc
empfangene Paket
Daten empfangen bzw.
für jedes synchronisiert
versendet wurden. Zu
SyncRecv
empfangene Paket
welchem
Zeitpunkt
für jedes nicht-blockierend
SendDone
diese
Call-Backverschickte Paket
Funktion
aufgerufen
CheckRequests
wird, hängt von der
Implementation
des
Netzwerk-Layers
ab.
Abb. 5.2: Empfangen von Requests durch Pollen
Muss gepollt werden,
dann hat die Applikation
regelmässig die CheckRequests-Funktion aufzurufen. Innerhalb dieser Funktion wird für jedes
empfangene bzw. versendete Paket einmal die Call-Back-Funktion aufgerufen (Abbildung 5.2).
Applikation
Zero-Copy-Layer
Netzwerk-Layer
Betriebssystem
RegisterCallBack
WaitForSingleObjectEx
CallBackFunc
Kernel
AsyncRecv
RecvDoneAPC
SyncRecv
SendDone
SendDoneAPC
Abb. 5.3: Empfangen von Requests durch APCs
Anders verhalten sich die erwähnten Asynchronous-Procedure-Calls (APC). Ein APC ist im
wesentlichen nur ein Aufruf einer Funktion. Der Aufruf geschieht jedoch nicht unbedingt sofort,
sondern nur dann, wenn sich der entsprechende Thread in einem sogenannten Alertable Wait
Seite 36
ETH Zürich
State befindet. Ein solcher Zustand kann mit WaitForSingleObjectEx oder SleepEx erreicht
werden. APCs können wohl im User-Mode mit QueueUserAPC ausgelöst werden, werden jedoch
häufig von Kernel-Mode-Treibern verwendet, um das Ende einer nicht-blockierenden Transaktion
zu signalisieren. Windows NT stellt für solche Transaktionen die beiden Win32-Funktionen
ReadFileEx und WriteFileEx zur Verfügung. Diese APCs sind also eine Möglichkeit, das
aufwendige Polling zu umgehen.
5.2.3 Asynchrones Senden und Empfangen
Der Netzwerk-Layer ist dafür verantwortlich, dass jederzeit kleinere Datenpakete empfangen
werden können. Er hat allenfalls genügend Empfangspuffer zur Verfügung zu stellen. Dies erlaubt
ein sofortiges versenden von solchen Paketen. Wie Abbildung 5.1 zeigt, ist beim Senden innerhalb
des Zero-Copy-Layers keine Verarbeitung notwendig. Ein Aufruf von SendAsync wird also direkt
dem Netzwerk-Layer weitergereicht.
Dieser ist dafür verantwortlich, das Paket so bald als möglich zu versenden. Tut er dies sofort und
blockierend, dann gibt er nach erfolgter Kommunikation den Status Success bzw. Error zurück.
Erfolgt das Senden zu einem späteren Zeitpunkt, dann gibt er Pending zurück und muss das Paket
in eine von ihm zu verwaltende Queue einfügen. Sobald das Paket versendet ist, muss dieses
mittels SendDone dem Zero-Copy-Layer und damit der Applikation wieder zurückgeben werden.
SENDER
CallBackFunc
Application
SendAsync
SendDone
SendAsync
SendDoneAPC
WriteFileEx
Wait
Zero-Copy-Layer
Network-Layer
Operating System
Network
Time
Operating System
ReadFileEx
Wait
Init
RecvDoneAPC
Init
AsyncRecv
Network-Layer
Zero-Copy-Layer
Application
CallBackFunc
RECEIVER
Abb. 5.4: Der nicht-blockierende, asynchrone Sende- und Empfangsvorgang mit APC
Auf Empfängerseite muss das Paket im Netzwerk-Layer in einen Puffer aufgefangen werden.
Dieser Puffer wird durch AsyncRecv via Zero-Copy-Layer und Call-Back-Funktion der Applikation
übergeben.
5.2.4 Synchrones Senden und Empfangen
Etwas komplexer ist das synchrone Senden und Empfangen. Teilt eine Applikation die
Empfangsbereitschaft via RecvSync dem Zero-Copy-Layer mit, dann wird ein asynchrones
Datenpaket (Ready-Request genannt) generiert, das neben den Headerinformationen die virtuelle
Seite 37
ETH Zürich
Adresse und die Grösse des Empfangspuffer enthält. Dieses Paket wird durch das asynchrone
Senden des Netzwerk-Layers an den Sender der synchronen Kommunikation geschickt. Dort wird
geprüft, ob ein entsprechendes SendSync bereits aufgerufen wurde (Abbildung 5.5, rechts). Wenn
AsyncRecv
ReadyRequest ?
CallBackFunc
no
SendSync
yes
Check
SendList
not found
Enter Request
into SendList
Check
SendList
Enter Request
into SendList
Zero-Copy-Layer
found
found
SendSync
not found
Network-Layer
SendSync
Abb. 5.5: Der Aufruf von SendSync durch eine Applikation bzw.
der Aufruf von AsyncRecv beim Empfang eines Async-Recv- oder Ready-Requests.
ja wird das entsprechende Paket sofort versendet. Wenn nein, wird sich der Zero-Copy-Layer die
Empfangsbereitschaft in einer Liste merken.
Auf Senderseite kann das SendSync
jederzeit aufgerufen werden. Es wird
dann geprüft, ob der Empfänger seine
Bereitschaft bereits mitgeteilt hat
(Abbildung 5.5, links). Wenn ja, wird
das Paket sofort verschickt. Wenn
nein, wird das Versenden solange
aufgeschoben,
bis
die
Empfangsbereitschaft mitgeteilt wird.
Das in Abbildung 5.5 auftretende
Check SendList wird in Abbildung 5.6
genauer dargestellt. Im wesentlichen
wird geprüft, ob Absender, Empfänger,
Tag und Grösse des aktuellen
Requests mit einem Request in der
Liste übereinstimmen. Mit Legal Buffer
Size ist in diesem Zusammenhang
gemeint, dass die Grösse des
Empfangspuffers mindestens so gross
sein muss, wie die Grösse der zu
versendenden Daten.
Get First Request
Is
Null ?
Get Next Request
No RequestFound
no
no
Same
SendID ?
yes
no
Same
RecvID ?
yes
no
Ist die Empfangsbereitschaft bestätigt,
dann
kann
NwSendSync
des
Netzwerk-Layers aufgerufen werden,
um das Datenpaket endgültig zu
versenden.
yes
Same
Tag ?
yes
no
Legal
Buffersize
?
Wird dann auf Empfängerseite ein
yes
synchrones Paket empfangen, dann
muss der Netzwerk-Layer dies durch
Request Found
SyncRecv dem Zero-Copy-Layer und
der Applikation mitteilen.
Abb. 5.6: Ablauf eines Check-RecvList
Seite 38
ETH Zürich
5.2.5 Die Zero-Copy-Layer-Variante für OpenMP
Zero-Copy wird in OpenMP dazu verwendet, Speicherseiten des Distributed-Shared-Memory von
einem Knoten zu einem anderen zu verschicken. Knoten A schickt einen Page-Request an Knoten
B, der die Speicherseite zurückschickt. Wie Abbildung 5.7 zeigt, müsste A zuerst einen Recv-SyncRequest generieren, um die Empfangsbereitschaft zu signalisieren. Dann hat er einen AsyncRequest an B zu schicken, der sagt, welche Seite er wünscht. Daraufhin macht B einen SendSync-Request, der die Speicherseite versendet. Kompliziert und viel Kommunikation, nicht?
OpenMP A
Request
Reply
Zero-Copy-Layer
RecvSync
Network
Zero-Copy-Layer
Ready
OpenMP B
Ready
Async
Async
Request
RecvSync
SendSync
Reply
Abb. 5.7: OpenMP-Page-Request und -Reply ohne Modifikation
OpenMP A
Zero-Copy-Layer
Request
RecvSync
Reply
RecvSync
Network
Zero-Copy-Layer
Ready
OpenMP B
Async
Request
SendSync
Reply
Ready
Abb. 5.8: OpenMP-Page-Request und -Reply mit Modifikation
Eine kleine Modifikation des bestehenden Zero-Copy-Layers macht alles viel einfacher (siehe
Abbildung 5.8). Ein Recv-Sync-Request generiert ja einen Ready-Request, mittels welchem die
Empfangsbereitschaft signalisiert wird. Diesem Request könnte auch gleich beigefügt werden,
welche Speicherseite gewünscht wird. Damit kann ein Request gespart werden. Konkret könnte
das Tag des Ready-Requests die Nummer der gewünschten Speicherseite enthalten.
Normalerweise würde dieser Ready-Request für die Empfängerapplikation niemals sichtbar
werden, sondern würde nur innerhalb des Zero-Copy-Layers existieren. Beim modifizierten Layer
(Abbildung 5.9) wird ein Ready-Request wie ein normaler Async-Request behandelt und via CallBack-Funktion an die Applikation weitergereicht.
SendAsync
success/
pending/
error
SendSync
RecvSync
success/
pending/
error
CallBack
pending/
error
success/
error
success/
pending/
error
success/
pending/
error
SyncRecv
SendDone
NwCheckRequests
done
Sending List
Request
Reply
Controll
Network Layer
NwSendSync
Zero Copy Layer
Recv
List
Ready
AsyncRecv
CheckRequests
Abb. 5.9: Modifizierter Zero-Copy-Layer für OpenMP
Seite 39
ETH Zürich
Die Tatsache, dass RecvSync garantiert vor dem entsprechenden SendSync aufgerufen wird,
macht auch die komplizierte Buchführung rund um die SendList unnötig.
5.3 Die Schnittstellen
Um die Schnittstellen der beiden eben beschriebenen Layer besser verstehen zu können, müssen
vorerst einige Datenstrukturen, insbesondere die sogenannten Requests, erläutert werden.
5.3.1 Die Requests
Entsprechend den beiden Kommunikationsarten (synchron und asynchron) gibt es auch zwei
wesentliche Request-Typen:

Async-Request: Ein Async-Request behandelt das
Senden
bzw.
Empfangen
von
kleinen,
unsynchronisierten Paketen. Er beinhaltet als
Headerinformation
die
Senderund
Empfängeridentifikation, ein Tag sowie die Länge des
nachfolgenden Body.
Sender ID
Receiver ID
Tag
Len
0
Jede Sender- bzw. Receiver-ID ist zweigeteilt: Die
oberen 16 Bits enthalten die ID des Knotens, die
unteren eine applikationsabhängige ID.
Die Grösse des Bodies ist beschränkt. Bei der
vorliegenden
Implementation
auf
ZCL_ASYNC_BUFFER_SIZE Bytes.
N-1
Async Request
Sender ID
Receiver ID
Tag
Len
Source Ptr
Target Ptr
Sync Request
Abb. 5.10: Request-Datenstrukturen
Eine Applikation kann jederzeit einen Async-Request
vom Zero-Copy-Layer anfordern und den Body mit
Daten füllen. Übermittelt wird beim Senden der Header, sowie die ersten Len Bytes des
Bodies.
Als Spezialfall eines Async-Requests kann der Ready-Request erwähnt werden. Er wird zum
Versenden der Empfangsbereitschaft verwendet und enthält als Body nur die 4-Byte-Adresse
des Empfangspuffers und dessen Grösse. Erkennen kann man einen Ready-Request
innerhalb des Zero-Copy-Layers am gesetzten most-significant-bit des Tags. Bei AsyncRequests darf demnach dieses Bit nicht gesetzt sein.

Sync-Request: Der Sync-Request behandelt das synchronisierte Senden und Empfangen. Er
enthält dieselben Headerinformationen wie der Async-Request. Zusätzlich enthält er je einen
Source- und Targetpointer. Übermittelt wird jedoch nicht der Request, sondern der Inhalt des
Speicherbereichs, der durch Sourcepointer und Länge definiert wird.
Diese beiden Request-Typen werden in einen allgemeinen Request verpackt, der folgende Struktur
hat:
struct ZCL_REQUEST
{
int nType;
ZCL_STATUS Status;
union
{
void* pRequest;
PZCL_ASYNC_REQUEST pAsync;
PZCL_SYNC_REQUEST pSync;
PZCL_REQUEST_HEAD pHead;
};
};
Seite 40
Typ des Requests
Status und Fehlercode des Requests
Pointer zum Sync-/Async-Request
Pointer zum Async-Request
Pointer zum Sync-Request
Pointer zum Request-Header
ETH Zürich
Es gibt die folgenden Request-Typen:
Typ
Beschreibung
ZCL_SYNC_SEND
Sync-Request für synchrones Senden
ZCL_SYNC_RECV
Sync-Request für synchrones Empfangen
ZCL_ASYNC_SEND
Async-Request für asynchrones Senden
ZCL_ASYNC_RECV
Async-Request für asynchrones Empfangen
ZCL_SYNC_READY
Sync-Request. Existiert nur im Zero-Copy-Layer.
Empfangsbereitschaft eines entfernten Knotens.
ZCL_ASYNC_READY
Ready-Request. Teilt einem entfernten Knoten mit, dass der lokale
Knoten für den Empfang eines synchron verschickten Paketes bereit ist.
ZCL_ERROR_RECV
Signalisiert einen Fehler beim Empfangen von Paketen. Bei diesem
Request-Typ haben die Pointer den Wert NULL.
Signalisiert die
Tab. 5.1: Request-Typen
5.3.2 Der Status
Eine spezielle Struktur enthält den Status eines Requests oder einer Funktion:
struct ZCL_STATUS
{
int nStatus;
int nErrorCode;
}
nStatus kann folgende Werte enthalten:
Status
Beschreibung
ZCL_SUCCESS
Der Request wurde erfolgreich verarbeitet.
ZCL_ERROR
Der Request konnte auf Grund eines Fehlers im Zero-Copy-Layer nicht
verarbeitet werden (nErrorCode enthält einen Fehlercode).
ZCL_NW_ERROR
Der Request konnte auf Grund eines Fehlers im Netzwerk-Layer nicht
verarbeitet werden (nErrorCode enthält einen Fehlercode).
ZCL_PENDING
Der Request ist noch nicht vollständig bearbeitet.
Tab. 5.2: Request-Stati
5.3.3 Die obere Schnittstelle des Netzwerk-Layers
Die obere Schnittstelle des Netzwerk-Layers muss folgende Funktionen zur Verfügung stellen. Sie
ist in der Datei NWLINTERFACE.H definiert. Es müssen alle Funktionen implementiert werden. Sie
können je nach Netzwerktechnologie jedoch leer sein.
ZCL_STATUS NWL_Init();
Initialisiert den Netzwerk-Layer, dessen Datenstrukturen und die eventuell darunterliegenden
Layer. Zurückgegeben wird der Status der Initialisierung (ZCL_SUCCESS oder ZCL_NW_ERROR)
und im Fehlerfall ein Fehlercode. Die Funktion wird vom Zero-Copy-Layer als erste Funktion
aufgerufen.
ZCL_STATUS NWL_Exit();
Diese Funktion ist das Gegenstück zu NWL_Init. Sie bringt das Netzwerk in einen Grundzustand
zurück und baut alle internen Datenstrukturen ab. Die Funktion wird vom Zero-Copy-Layer als
letzte Funktion aufgerufen.
Seite 41
ETH Zürich
char* NWL_NetworkName();
Diese Funktion gibt einen Pointer auf eine Zeichenkette zurück, die die durch den Layer
verwendete Netzwerktechnologie beschreibt, z.B. „Myrinet GM“.
BOOL NWL_NeedPolling();
Ist der durch diese Funktion zurückgegebene Wert TRUE, dann ist Polling notwendig. Das heisst,
die Applikation muss regelmässig via Zero-Copy-Layer prüfen, ob nicht-blockierend zu
versendende Pakete verschickt, oder ob neue Pakete empfangen wurden (siehe
NWL_CheckRequests und ZCL_CheckRequests).
ZCL_STATUS NWL_ReadNodeInfo(int nNodeID, char* pcSection);
Liest die Datei ZEROCOPY.CFG aus. Diese Datei enthält Sektionen von folgendem Format:
[Node<ID>]
HostName = <Name>
Für jeden Knoten existiert eine Sektion in der Datei. Die Sektion ist mit [Node<ID>]
gekennzeichnet, wobei <ID> eine Nummer darstellt. Der Zero-Copy-Layer liest alle Knoten
beginnend mit 0 und aufsteigend, bis eine ID nicht gefunden wurde. HostName = <Name> wird
ebenfalls vom Zero-Copy-Layer gelesen. Für jeden Netzwerk-Layer können weitere Informationen
hinzugefügt werden, die der Netzwerk-Layer in der Funktion NWL_ReadNodeInfo zu lesen hat.
Gelesen wird mit den folgenden Win32-Funktionen:
GetPrivateProfileInt(pcSection, <Key>, <Default>, ".\\zerocopy.cfg");
GetPrivateProfileString(pcSection, <Key>, <Default>, cBuffer, nBufferSize,
".\\zerocopy.cfg");
<Key> ist dabei der Schlüssel des zu lesenden Eintrags. <Default> ein Standardwert, der
verwendet werden soll, wenn der Eintrag nicht gefunden wurde.
Dies ist ein Beispiel einer gültigen Sektion in ZEROCOPY.CFG. SocketIP und SocketPort sind
spezielle Einträge für den Socket-Netzwerk-Layer:
[Node3]
HostName = CS-ZZ13
SocketIP = 129.132.13.221
SocketPort = 800
ZCL_STATUS NWL_Connect(int nNodeID);
Falls die verwendete Netzwerktechnologie verbindungsorientiert arbeitet, dann müssen die
Verbindungen in dieser Funktion aufgebaut werden. Der Funktion wird die ID des Knotens
übergeben, zu dem eine Verbindung gewünscht wird. Falls für den Verbindungsaufbau weitere
Informationen (z.B. IP-Adresse) notwendig sind, dann müssen diese in der Datei ZEROCOPY.CFG
enthalten sein (siehe NWL_ReadNodeInfo).
ZCL_STATUS NWL_Disconnect(int nNodeID);
Aufgebaute Verbindungen müssen in dieser Funktion wieder abgebaut werden.
int NWL_SendAsync(PZCL_REQUEST pRequest);
Asynchrones Versenden von Paketen wird in dieser Funktion implementiert. Wird der Request
sofort blockierend versendet, dann muss die Funktion den Status des Requests auf ZCL_SUCCESS
setzen und ZCL_SUCCESS zurückgeben. Im Fehlerfall wird der Status des Request auf
ZCL_NW_ERROR und ein Fehlercode gesetzt und ZCL_ERROR zurückgegeben. Wird der Request
nicht-blockierend verschickt, dann gibt die Funktion ZCL_PENDING zurück.
int NWL_SendSync(PZCL_REQUEST pRequest);
Implementiert das Versenden von synchronen Requests. Das Verhalten ist das selbe wie bei
NWL_SendAsync.
Seite 42
ETH Zürich
void NWL_CheckRequests();
Falls NWL_NeedPolling den Wert TRUE zurückliefert, muss die Applikation regelmässig die
Funktion ZCL_CheckRequests aufrufen, die ihrerseits diese Funktion aufruft. Diese Funktion
prüft, ob nicht-blockierende Requests verschickt, und ob neue Requests empfangen wurden. Sie
wird diese Requests über die untere Schnittstelle des Zero-Copy-Layers nach oben weiterreichen
(siehe ZCL_HandleSendDone,
ZCL_HandleSyncRecv,
ZCL_HandleAsyncRecv
und
ZCL_HandleErrorRecv).
void* NWL_Alloc(int nSize);
Wird vom Zero-Copy-Layer verwendet, um Speicher für Async-Requests zu allozieren. Diese
Funktion kann ein normales malloc enthalten. Falls von der Netzwerktechnologie jedoch
spezieller Speicher gebraucht oder zur Verfügung gestellt wird, dann kann diese Funktion
speziellen Code enthalten.
void NWL_Free(void* pBuffer);
Gibt durch NWL_Alloc allozierter Speicher wieder frei.
void NWL_RegisterMemory(void* pBuffer, int nSize);
Innerhalb von ZCL_RecvSync wird diese Funktion aufgerufen, um dem Netzwerk-Layer die
Möglichkeit zu geben, den Speicherbereich für den Empfang vorzubereiten, z.B. durch Locken des
Speicherbereichs.
void NWL_DeregisterMemory(void* pBuffer, int nSize);
Nach dem Empfang, innerhalb der ZCL_HandleSyncRecv, wird diese Funktion aufgerufen, um
einen mit NWL_RegisterMemory behandelten Speicherbereich wieder in den ursprünglichen
Zustand zurückzusetzen.
5.3.4 Die untere Schnittstelle des Zero-Copy-Layers
Die untere Schnittstelle des Zero-Copy-Layers ist in der Datei ZCLLOWER.H definiert. Sie kann vom
Netzwerk-Layer verwendet werden.
void ZCL_HandleAsyncRecv(PZCL_REQUEST pRequest);
Wird vom Netzwerk-Layer ein Async-Request empfangen, dann kann dieser Request durch diese
Funktion an den Zero-Copy-Layer weitergereicht werden. Der Status des Requests muss
ZCL_SUCCESS sein.
void ZCL_HandleSyncRecv(void* pBuffer, int nLen);
Wird vom Netzwerk-Layer ein Sync-Request empfangen, dann kann mit dieser Funktion dem ZeroCopy-Layer mitgeteilt werden, wohin (pBuffer) der Inhalt des Requests empfangen wurde und
wie lang (nLen) der Inhalt ist.
void ZCL_HandleSendDone(PZCL_REQUEST pRequest);
Wenn eine der Funktionen NWL_SendAsync oder NWL_SendSync mit ZCL_PENDING zurückkehrt,
dann wird nicht-blockierend versendet. Wenn das Senden beendet ist, muss der Netzwerk-Layer
diese Funktion aufrufen. Der Status des Requests muss zuvor entweder auf ZCL_SUCCESS oder
im Fehlerfall auf ZCL_NW_ERROR gesetzt sein.
void ZCL_HandleErrorRecv(PZCL_STATUS pStatus);
Falls während dem Empfangen im Netzwerk-Layer ein Fehler auftritt, kann der entsprechende
Status (ZCL_NW_ERROR) und Fehlercode dem Zero-Copy-Layer weitergereicht werden.
Seite 43
ETH Zürich
BOOL ZCL_ProtectMemory(void* pBuffer, int nLen);
Diese Funktion ist wichtig für Netzwerk-Layer, die nicht mit DMA arbeiten. Da Applikationen wie
OpenMP die Zugriffsrechte von Speicherseiten manipulieren, muss der Netzwerk-Layer diese Seite
vor dem Empfangen mit Schreibrechten versehen. Das hätte jedoch zur Folge, dass die Threads
der Applikation auf die Seiten zugreifen könnten. Um das zu verhindern, müssen alle Threads
vorübergehend schlafen gelegt werden (siehe auch ZCL_RegisterThread). Die Funktion gibt
TRUE zurück, wenn Threads schlafen gelegt werden mussten, ansonsten FALSE.
BOOL ZCL_UnprotectMemory();
Setzt die Zugriffsrechte der Speicherseiten zurück auf den alten Wert und weckt alle schlafen
gelegten Threads wieder auf. Die Funktion gibt TRUE zurück, wenn Threads aufgeweckt wurden,
ansonsten FALSE (siehe auch ZCL_ProtectMemory).
PZCL_REQUEST ZCL_GetAsyncRequest(int nType);
Wird vom Netzwerk-Layer ein Async-Request benötigt, dann kann er über diese Funktion einen
anfordern. nType muss entweder ZCL_ASYNC_RECV oder ZCL_ASYNC_SEND sein.
int ZCL_ReleaseAsyncRequest(PZCL_REQUEST pRequest);
Wird vom Netzwerk-Layer ein Async-Request, den er mit ZCL_GetAsyncRequest angefordert
hat, nicht mehr benötigt, dann kann er mit dieser Funktion wieder zurückgegeben werden. Um
dauerndes Allozieren und Freigeben von Speicherbereichen zu verhindern, wird eine gewisse
Anzahl von Async-Requests rezykliert.
PZCL_REQUEST ZCL_GetSyncRequest(int nType);
Wird vom Netzwerk-Layer ein Sync-Request benötigt, dann kann er über diese Funktion einen
anfordern. Der Typ muss entweder ZCL_SYNC_RECV oder ZCL_SYNC_SEND sein.
int ZCL_ReleaseSyncRequest(PZCL_REQUEST pRequest);
Wird vom Netzwerk-Layer ein Sync-Request, den er mit ZCL_GetSyncRequest angefordert hat,
nicht mehr benötigt, dann wird er mit dieser Funktion wieder zurückgegeben. Auch die
Speicherbereiche von Sync-Requests werden rezykliert.
int ZCL_GetLocalNodeID();
Nachdem NWL_ReadNodeInfo aufgerufen wurde, kann mit dieser Funktion die lokale Knoten-ID
gelesen werden.
int ZCL_GetNumNodes();
Gibt die Anzahl in der Konfigurationsdatei definierten Knoten zurück.
char* ZCL_GetHostName(int nNodeID);
Gibt den Rechnernamen eines bestimmten Knotens zurück.
5.3.5 Die obere Schnittstelle des Zero-Copy-Layers
Die obere Schnittstelle des Zero-Copy-Layers wird den Applikationen zur Verfügung gestellt. Sie ist
in der Datei ZCLUPPER.H definiert.
ZCL_STATUS ZCL_Init(BOOL fForwardReadyRequests,
PZCL_REQUEST_CALL_BACK pCallBack);
Eine Applikation, die den Zero-Copy-Layer verwenden will, muss diese Funktion als erstes
Aufrufen. Sie initialisiert den Layer. Mit fForwardReadyRequests kann entschieden werden, ob
die normale Variante (FALSE) oder die spezielle OpenMP-Variante (TRUE) verwendet werden soll.
Seite 44
ETH Zürich
Zudem muss dieser Routine ein Funktions-Pointer übergeben werden, der auf die Call-BackFunktion der Applikation zeigt. Diese Call-Back-Funktion hat folgende Signatur:
int CallBackFunc(PZCL_REQUEST pRequest);
Der Name der Funktion spielt natürlich keine Rolle. Die Funktion gibt ZCL_SUCCESS zurück, wenn
sie den Request verarbeitet hat, ZCL_ERROR falls nicht. Im ersten Fall geht der Request in den
Besitz der Applikation über. Sie ist daher auch Verantwortlich, dass der Request irgendwann
gelöscht
wird
(siehe
ZCL_ReleaseSyncRequest,
ZCL_ReleaseAsyncRequest,
ZCL_ReleaseErrorRequest).
ZCL_STATUS ZCL_Exit();
Als letzte Funktion hat die Applikation diese aufzurufen, um alle aufgebauten Datenstrukturen
sauber abbauen zu können.
ZCL_STATUS ZCL_ReadNodeInfo();
Wie bereits bei NWL_ReadNodeInfo erwähnt, sind die Informationen zu den Knoten in der Datei
ZEROCOPY.CFG untergebracht. Diese Funktion öffnet diese Konfigurationsdatei und liest daraus für
jeden Knoten den Rechnernamen. Danach wird für jeden Knoten die Funktion
NWL_ReadNodeInfo aufgerufen, welche netzwerkabhängige Informationen lesen kann.
Auf Grund des lokalen Rechnernamens wird die lokale Knoten-ID ermittelt. Falls in der
Konfigurationsdatei mehrere Einträge mit dem lokalen Rechnernamen übereinstimmen, wird der
Benutzer nach dem gewünschten Knoten gefragt.
int ZCL_GetLocalNodeID();
Nachdem ZCL_ReadNodeInfo aufgerufen wurde, kann mit dieser Funktion die lokale Knoten-ID
gelesen werden.
int ZCL_GetNumNodes();
Gibt die Anzahl in der Konfigurationsdatei definierten Knoten zurück.
int ZCL_RegisterThread(HANDLE hThread);
Falls die Applikation mit Speicherbereichen arbeitet, die nicht mit Schreibzugriffsrechten versehen
sind und in solchen Speicher Daten empfangen will, dann müssen alle Threads ausser dem
Kommunikationsthread
beim
Zero-Copy-Layer
registriert
werden
(siehe
auch
ZCL_ProtectMemory).
BOOL ZCL_NeedPolling();
Über diese Funktion kann die Applikation abfragen, ob Polling über ZCL_CheckRequests
notwendig ist, oder ob die Call-Back-Funktion „automatisch“ aufgerufen wird. Falls statt Polling
APCs verwendet werden, dann muss der Kommunikationsthread der Applikation regelmässig die
Win32-Funktionen WaitForSingleObjectEx oder SleepEx aufrufen.
char* ZCL_NetworkLayer();
Gibt eine Informationszeichenkette zurück, die den Netzwerk-Layer beschreibt: z.B. „Myricom GM“.
ZCL_STATUS ZCL_Connect(int nNodeID);
Egal welchen Netzwerk-Layer verwendet wird, diese Schnittstelle des Zero-Copy-Layers ist
verbindungsorientiert. Das heisst, vor dem ersten Senden oder Empfangen muss zu allen
gewünschten Knoten eine Verbindung aufgebaut werden. Die übergebene Knoten-ID muss
zwischen 0 und ZCL_GetNumNodes-1 liegen und darf nicht die eigene ID sein.
Seite 45
ETH Zürich
ZCL_STATUS ZCL_Disconnect(int nNodeID);
Vor dem Beenden der Applikation müssen alle mit ZCL_Conntect aufgebauten Verbindungen
wieder abgebaut werden.
int ZCL_SendSync(PZCL_REQUEST pRequest);
Sendet den durch einen Sync-Request beschriebenen Speicherbereich an einen
Empfängerknoten. pRequest muss ein gültiger Sync-Request sein, wobei pSourceBuffer auf
den zu versenden Speicherbereich zeigt und nLen die Länge des Bereichs angibt.
Diese Funktion gibt entweder ZCL_SUCCESS zurück, was bedeutet, dass der Request erfolgreich
versendet wurde. ZCL_PENDING heisst, dass der Request noch nicht verschickt werden konnte.
Der Request geht dann in den Besitz des Zero-Copy-Layers über. Das heisst, die Applikation darf
ihn so lange nicht mehr verändern, bis sie ihn über die Call-Back-Funktion zurück bekommt.
ZCL_ERROR wird im Fehlerfall zurückgegeben.
int ZCL_SendAsync(PZCL_REQUEST pRequest);
Sendet den Async-Request an einen Empfängerknoten. pRequest muss ein gültiger AsyncRequest sein. Es werden der Header des Requests plus die ersten nLen-Bytes des Bodies
versendet.
Die zurückgegebenen Werte entsprechen denen von ZCL_SendSync.
int ZCL_RecvSync(PZCL_REQUEST pRequest);
Bestätigt die Empfangsbereitschaft. pTargetBuffer des Sync-Requests muss auf einen gültigen
Speicherbereich zeigen, in den Empfangen werden soll. nLen gibt die Grösse des
Empfangspuffers an.
Zurückgegeben wird entweder ZCL_PENDING oder im Fehlerfall ZCL_ERROR.
int ZCL_CheckRequests();
Falls die Funktion ZCL_NeedPolling TRUE retourniert, muss die Applikation regelmässig diese
Funktion aufrufen. Für jeden beendeten Sendevorgang (der ZCL_PENDING zurücklieferte) und für
jeden abgeschlossenen Empfangsvorgang wird einmal die Call-Back-Funktion der Applikation
aufgerufen.
Die Funktion liefert die Anzahl der Aufrufe der Call-Back-Funktion zurück.
PZCL_REQUEST ZCL_GetAsyncRequest(int nType);
Mittels dieser Funktion kann eine Applikation beim Zero-Copy-Layer einen Async-Request
anfordern. Der Typ kann entweder ZCL_ASYNC_SEND oder ZCL_ASYNC_RECV sein.
void ZCL_ReleaseAsyncRequest(PZCL_REQUEST pRequest);
Ein Async-Request muss mit dieser Funktion bei Nichtgebrauch wieder zurückgegeben werden.
Um ständiges Allozieren und Freigeben von Speicher zu vermeiden, wird eine gewisse Anzahl von
Requests rezykliert.
PZCL_REQUEST ZCL_GetSyncRequest(int nType);
Mittels dieser Funktion kann eine Applikation beim Zero-Copy-Layer einen Sync-Request
anfordern. Der Typ kann entweder ZCL_SYNC_SEND oder ZCL_SYNC_RECV sein.
void ZCL_ReleaseSyncRequest(PZCL_REQUEST pRequest);
Ein Sync-Request muss mit dieser Funktion bei Nichtgebrauch wieder zurückgegeben werden. Um
ständiges Allozieren und Freigeben von Speicher zu vermeiden, wird eine gewisse Anzahl von
Requests rezykliert.
Seite 46
ETH Zürich
void ZCL_ReleaseErrorRequest(PZCL_REQUEST pRequest);
Ein in der Call-Back-Funktion erhaltener Request vom Type ZCL_ERROR_RECV kann mit dieser
Funktion dem Zero-Copy-Layer zurückgegeben werden.
void ZCL_GetProfileInfo(PZCL_PROFILE_INFO pInfo);
Der Zero-Copy-Layer merkt sich die Anzahl versendeter und empfangener Requests in einer
Struktur mit folgendem, selbsterklärendem Aufbau:
struct ZCL_PROFILE_INFO
{
// number of requests sent or received
int nSendSync;
int nSendAsync;
int nSendReady;
int nRecvSync;
int nRecvAsync;
int nRecvReady;
// number of bytes included in the requests
LONGLONG nSendSyncBytes;
LONGLONG nSendAsyncBytes;
LONGLONG nSendReadyBytes;
LONGLONG nRecvSyncBytes;
LONGLONG nRecvAsyncBytes;
LONGLONG nRecvReadyBytes;
}
Durch den Aufruf dieser Funktion wird der aktuelle Stand dieser Struktur kopiert. pInfo muss also
auf eine gültige Instanz von ZCL_PROFILE_INFO zeigen.
void ZCL_ResetProfileInfo();
Mittels dieser Funktion werden alle Werte der Profiling-Struktur auf Null zurückgesetzt.
5.4 Die Implementation der beiden Layer
Die Implementation des Zero-Copy-Layers enthält beide Versionen (gemäss Abbildungen 5.1 und
5.9). Folgende Dateien enthalten den nötigen Source-Code:
Datei
Inhalt
ZEROCOPYLAYER.C
Source-Code des Zero-Copy-Layers
ZEROCOPYLAYER.H
Header-Datei mit allgemeinen Definitionen
ZCLUPPER.H
Definition der oberen Schnittstelle
ZCLLOWER.H
Definition der unteren Schnittstelle
ZCLHELPER.H
Definitionen von allgemeinen Routinen (z.B. Listenverwaltung)
ZCLINTERNAL.H
Definitionen von ausschliesslich intern verwendeten Routinen und
Datenstrukturen
RESOURCE.H
Header-Datei der Ressourcen
ZEROCOPYLAYER.RC
Ressourcen
Tab 5.3: Source-Dateien des Zero-Copy-Layers
Seite 47
ETH Zürich
Der Zero-Copy-Layer und jeweils ein Netzwerk-Layer
sind in einer Bibliothek namens ZEROCOPY.DLL
enthalten. Da es vom Netzwerk-Layer mehrere Version
gibt, gibt es auch mehrere Version der DLL. Die
Eigenschaften der DLL geben Auskunft über den
Netzwerk-Layer (siehe Abbildung 5.11).
Sämtlicher Source der beiden Layer ist mit Microsoft
Visual C++ 5.0 erstellt, kompiliert und gelinkt worden.
Alle nötigen Einstellung für Kompilation und Linken
sind im Projekt mit dem Namen ZEROCOPY.DSP
enthalten.
Entschieden, welcher Netzwerk-Layer beim Erstellen
der DLL verwendet werden soll, wird in der Datei
NWLSELECT.H. Für jede Version des Layers enthält
diese Datei ein auskommentiertes Define. Es sollte vor
dem Kompilieren jeweils das Define aktiviert werden,
dessen Layer man integrieren möchte.
Die Netzwerk-Layer werden in den folgenden SourceAbb. 5.11: Eigenschaften von ZEROCOPY.DLL
Dateien definiert und implementiert:
Datei
Inhalt
NWLSELECT.H
In dieser Datei kann ausgewählt werden, welcher Netzwerk-Layer bei der
nächsten Kompilation verwendet werden soll.
NWLINTERFACE.H
Definiert die obere Schnittstelle des Netzwerk-Layers
NWLSOCKPIPE.H
Definitionen für den Socket- und Pipe-Netzwerk-Layer
NWLSOCKPIPE.C
Source-Code des Socket- und Pipe-Netzwerk-Layers
NWLGM.H
Definitionen für den GM-Netzwerk-Layer
NWLGM.C
Source-Code des GM-Netzwerk-Layers
Tab 5.4: Source-Dateien der Netzwerk-Layer
Wie die obige Tabelle zeigt, gibt es drei verschiedene Netzwerk-Layer:

Named-Pipes: Dieser Layer benutzt Named-Pipes für die Kommunikation und ist damit
besonders für lokale Tests geeignet. Bei jedem NWL_Connect wird eine Pipe zwischen zwei
Knoten aufgebaut. Der Named-Pipe-Netzwerk-Layer benutzt APCs, es ist also kein Pollen
notwendig.

Windows Sockets: Der Socket-Netzwerk-Layer ist vom Code her weitgehend identisch mit
dem Named-Pipe-Netzwerk-Layer. Es wird ebenfalls mit APCs gearbeitet. Unterschiedlich ist
eigentlich nur der Verbindungsaufbau. Wird dieser Layer verwendet, dann ist die Reihenfolge
des Aufbaus der Verbindungen wesentlich:
for(i = nNumNodes-1; i > nLocalNodeID; i--)
ZCL_Connect(i);
for(i = 0; i < nLocalNodeID; i++)
ZCL_Connect(i);

Myricom GM: Dieser Layer ist vorbereitet, jedoch nicht vollständig lauffähig. Die zeitlich (zu)
späte Freigabe des neusten GM-Beta-Release (0.18) durch Myricom, zahlreiche,
undokumentierte Randbedingungen und die unvollständige Freigabe von Kernel-DeviceObjekten durch die GM-Treiber haben eine erfolgreiche Implementation im Rahmen dieser
Arbeit verhindert.
Die beiden ersten Netzwerk-Layer-Implementationen dürften etwas überraschen, da sowohl
Named-Pipes wie auch Sockets überhaupt nichts mit Zero-Copy zu tun haben. Implementiert
wurden diese aus zweierlei Gründen: Erstens boten diese eine stabile und einfache Möglichkeit,
den Zero-Copy-Layer und die beiden Prototypen lokal und über Netzwerk zu testen. Zweitens
erlauben vor allem die Sockets den Zero-Copy-Layer und die Prototypen über ein fast beliebiges
Netzwerk (falls ein Treiber vorhanden ist) zu verwenden.
Seite 48
ETH Zürich
6 Der OpenMP-Prototyp
OpenMP [2] ist ein Standard, der bestehende Compiler um ein API erweitert. Dieses API enthält
die notwendigen Funktionen und Direktiven, um ein Programm auf einem Mehr-Prozessor-SharedMemory-System laufen zu lassen. Das API übernimmt das Management des Shared-Memory, die
Aufteilung des Programms an verschiedene, parallel arbeitende Prozessoren und die
Synchronisation des Programmablaufs.
Da sich diese Diplomarbeit auf Distributed-Shared-Memory-Systeme stützt, müssen diesem API
Funktionalitäten hinterlegt werden, die im Shared-Memory-System weitgehend von der Hardware
übernommen würden. Dabei standen vor allem Techniken, wie sie TreadMarks [4] verwendet, im
Vordergrund.
Der Prototyp implementiert den wichtigsten Teil des OpenMP-APIs. Das API, wie es in OpenMP
Fortran Application Program Interface 1.0 [2] definiert wird, ist eine Fortran-Compiler-Erweiterung.
Da für die Implementation Microsoft Visual C++ 5.0 zur Verfügung stand, versteht es sich von
selbst, dass eine Compilererweiterung nicht in Frage kommt. Es wurde deshalb versucht, mittels
Precompiler-Direktiven (in OPENMP.H) und einer Funktionsbibliothek (OMPLIB.DLL) die
ausgewählten OpenMP-Direktiven so gut als möglich nachzubilden.
Das folgende Unterkapitel geht nun ausführlich auf die Konzepte, die im Prototypen zur
Anwendung kommen, ein. Danach wird das implementierte API dokumentiert.
6.1 Die Konzepte des OpenMP-Prototyps
Den Konzepten, die im OpenMP-Prototyp zur Anwendung gekommen sind, liegen zwei
Basiskonzepte zu Grunde:

Wichtigstes Konzept ist die Zero-Copy-Kommunikation. Das heisst im wesentlichen, dass so
viel Kommunikation wie möglich ohne zusätzliches Kopieren, sei es im Sender oder im
Empfänger, auskommen sollte. Insbesondere das Verschieben von Speicherseiten im
Distributed-Shared-Memory sollte ohne Kopieren von statten gehen.

Grundlegend sollten auch die Techniken von TreadMarks [4], insbesondere Multiple-Writer und
Lazy-Release-Consistency, sein.
Wie die folgenden Ausführungen zeigen, lassen sich diese Konzepte nicht vollständig unter einen
Hut bringen.
6.1.1 Kommunikation
Anders als OpenMP baut dieser Prototyp auf einem Netzwerk von Workstations auf. Eine der
wichtigsten Komponenten eines solchen verteilten Systems ist die Kommunikation. Die vorgehend
ausführlich dokumentierten Studien zur Zero-Copy-Kommunikation und der Zero-Copy-Layer als
Resultat daraus, kommen in diesem Prototypen zu ihrem ersten praktischen Einsatz. Der Prototyp
wird also auf die obere Schnittstelle (ZCLU PPER.H) des Zero-Copy-Layers aufgebaut. Damit lässt
sich der Prototyp über alle Netzwerke betreiben, die durch den Zero-Copy-Layer bzw. durch einer
seiner Netzwerk-Layer unterstützt werden.
6.1.2 Threading
OpenMP versucht die zur Verfügung stehende Rechenleistung zu nutzen, indem parallelisierbare
Programmteile von mehreren Prozessoren abgearbeitet werden. Dazu werden dynamisch Threads
gestartet und beendet.
Eine solche Dynamik hätte den Rahmen eines Prototypen gesprengt, zumal die Threads nicht auf
einem System, sondern auf vielen, verteilten und vernetzten Systemen hätten zur Ausführung
gebracht werden müssen. Ein NT-Service, der auf jedem System im Hintergrund läuft und bei
Bedarf Prozesse und Threads startet, wäre die aufwendige Konsequenz gewesen.
Der Benutzer hat daher auf jeder Maschine (im folgenden Knoten genannt) das selbe Programm
zu starten. Da diese Maschinen über mehrere Prozessoren verfügen können, ist es sinnvoll, dass
Seite 49
ETH Zürich
mehrere Threads pro Knoten parallel laufen können. Lokal implementiert der Prototyp also ein
Shared-Memory-System, über die Grenzen eines Knotens hinweg jedoch ein Distributed-SharedMemory-System.
Nach dem Starten eines OpenMP-Prozesses wird der Hauptthread das System initialisieren, die
eigentlichen OpenMP-Threads starten und selber als Kommunikations-Thread agieren.
Kommunikations-Thread
Zero-Copy-Layer
OpenMP
Thread 5
OpenMP
Thread 4
OpenMP
Thread 3
OpenMP
Thread 2
Knoten 1
OpenMP
Thread 1
OpenMP
Thread 0
Knoten 0
Zero-Copy-Layer
Abb. 6.1: Thread-Modell des OpenMP-Prototypen
Während der Kommunikations-Thread aufbauend auf dem Zero-Copy-Layer für sämtliche
Kommunikation zwischen den Knoten (nicht zwischen den Threads) verantwortlich ist, führen die
OpenMP-Threads das OpenMP-Programm aus, und zwar alle das selbe. Gesteuert von Direktiven
im Programm werden einzelne Programmteile jedoch nicht von allen Threads ausgeführt, sondern
gezielt auf die einzelnen Threads verteilt. Welcher Thread welche Teile des Programms ausführt,
ist im Programm durch die OpenMP-Direktiven fixiert. Dynamische Verteilung, die zusätzliche
Kommunikation zur Folge hätte, wurde bewusst nicht in den Prototypen aufgenommen.
Die OpenMP-Threads werden durch zwei Numerierungssysteme identifiziert. Innerhalb eines
Knotens hat jeder Thread eine lokale Nummer, die von Null aufwärts gezählt wird. Der Thread mit
der lokalen Nummer 0 wird als lokaler Master bezeichnet.
Global werden die Nummern zwischen 0 und N-1 verteilt, wobei N die Summe der Threads auf
allen Knoten ist. Beim Starten der OpenMP-Applikation auf einem Knoten werden dieser so viele
fortlaufende Nummern fest zugeteilt, wie diese OpenMP-Threads haben soll. Analog zum lokalen
Master trägt der Thread mit der globalen Nummer 0 die Bezeichnung globaler Master.
Auf Grund der lokalen und globalen Nummer bestimmen die Threads, welche Teile des
Programms sie abarbeiten müssen.
6.1.3 Distributed-Shared-Memory
Noch wichtiger und wesentlich komplexer als das Thread-Modell ist die Speicherverwaltung des
OpenMP-Prototypen. Diese basiert auf dem Konzept des Distributed-Shared-Memory . Alle
OpenMP-Threads sollen einen einzigen, grossen, globalen Speicher zur Verfügung haben, auf den
sie quasi parallel zugreifen können.
Physisch gibt es natürlich keinen gemeinsamen Speicher. Jeder Knoten hat zu jedem Zeitpunkt nur
einen Teil des konzeptuell gemeinsamen Speichers in seinem lokalen, physischen Speicher – ein
Working-Set sozusagen. Wird eine Speicherseite ausserhalb dieses Sets adressiert, dann
entspricht das einem Page-Fault. Dieser kann aufgelöst werden, indem ermittelt wird, welcher
Knoten eine gültige Kopie der Seite hat und diese kommuniziert wird.
Seite 50
ETH Zürich
Welche Probleme hinter einem solchen Distributed-Shared-Memory-System stecken, wird schnell
klar: Was passiert, wenn zwei Knoten eine gültige Kopie einer Seite haben und diese gleichzeitig
beschreiben? Wie wird ermittelt, wer eine gültige Kopie besitzt? Wann wird mitgeteilt, dass sich der
Inhalt einer Seite verändert hat und die eigene Kopie der Seite somit ungültig ist? Hochgradige
Parallelität, relativ langsame Kommunikation und grobgranulare Unterteilung des Speichers in
Seiten (von 4 kB auf i386-Systemen) lassen die Implementation zu einer wahren Herausforderung
werden. Folgende Unterkapitel sollen die Mechanismen und Strukturen, die im Prototypen
eingebaut wurden, aufzeigen:
6.1.3.1 Initialisieren des Distributed-Shared-Memory
Der Distributed-Shared-Memory (im folgenden nur noch SHARED-Speicher genannt) ist in
Wirklichkeit ein grosser, virtueller Speicherbereich, der in jedem Knoten beim Initialisieren des
Systems reserviert wird. Alle Threads eines Knotens teilen sich einen SHARED-Speicher. Nur ein
kleiner Teil dieses reservierten, virtuellen Speicherbereichs wird zu Beginn tatsächlich mit
physischem RAM oder Diskspeicher hinterlegt (in der Windows NT-Terminologie heisst das
commited), der Rest bleibt lediglich reserviert.
In einer Liste wird für jede Speicherseite im SHARED-Speicher deren Zustand festgehalten.
Folgende Zustände sind möglich:
Status
Beschreibung
Zugriffsrechte
OMP_PAGE_RESERVED
Die Seite ist reserviert, es ist aber kein
physischer Speicher damit verbunden.
no access
OMP_PAGE_VALID
Die Seite ist gültig. Sie enthält gültige
Information, die gelesen (und nach dem
Übergang in den Modified-Status auch
beschrieben) werden kann.
read only
OMP_PAGE_INVALID
Die Seite ist ungültig. Bevor gelesen oder
geschrieben werden kann, muss eine gültige
Kopie von einem anderen Knoten angefordert
werden.
no access
OMP_PAGE_MODIFIED
Die Seite ist gültig und wurde modifiziert.
read / write
OMP_PAGE_SEND
Die Seite ist gültig, wird aber gerade an einen
anderen Knoten gesendet und kann daher
temporär nur lesend zugegriffen werden.
read only
OMP_PAGE_RECV
Die Seite ist ungültig, wird aber gerade von
einem anderen Knoten angefordert.
no access
Tab. 6.1: Zustände der Speicherseiten im SHARED-Speicher
Betrachtet man das Diagramm der
Zustandsübergänge in Abbildung 6.2, dann
dürfte eventuell der direkte Übergang von
Reserved in Valid erstaunen. Dies hat mit
einer Eigenschaft von Windows NT zu tun:
Wann
immer
im
User-Mode
eine
Speicherseite angefordert wird, dann ist
diese aus Sicherheitsgründen mit Nullen
initialisiert. Das heisst, die Speicherseiten
in allen Knoten haben nach dem Commit
den selben – also auch gültigen – Inhalt.
Reserved
Decommit
Invalid
Barrier
Commit
Write
Valid
Modified
Barrier
Recv in
progress
Recv
Send in
progress
Send
WinNT: Sowohl für das Reservieren wie
auch für das Hinterlegen mit
Abb. 6.2: Zustandsübergänge einer Speicherseiten
Speicher ist unter Windows NT
die
Win32-Funktion
VirtualAlloc zuständig. Gegenstück dazu ist die Funktion VirtualFree. Eine
weitere wichtige Funktion ist VirtualProtect, welche die Zugriffsrechte einer oder
mehrerer Seiten setzt. Diese drei Funktionen und ein Exception-Handler (__try {...}
Seite 51
ETH Zürich
__except(GetExceptionInformation()) {...}) genügen im wesentlichen, um
ein Distributed-Shared-Memory System unter NT auf die Beine zu stellen.
6.1.3.2 Allozieren von Speicherbereichen im SHARED-Speicher
Teile des initialisierten SHARED-Speichers
müssen nun den Threads zur Verfügung gestellt
werden. Dabei muss sichergestellt werden, dass
alle Threads die selbe Sicht des Speichers haben.
Das heisst im wesentlichen, dass auf allen Knoten
alle Allokationen in der selben Reihenfolge
durchgeführt werden müssen (dafür ist der
OpenMP-Programmierer zuständig), und dass
trotz mehrerer lokaler Threads, die selbe
Allokation nur einmal ausgeführt wird.
Mit OMP_ALLOC kann ein Programm Speicher
(fast) beliebiger Grösse allozieren. Grundsätzlich
wird Speicher fortlaufend in eine Richtung alloziert
und, falls nötig, weiterer physischer Speicher dem
reservierten Bereich hinterlegt (commited).
OMP_ALLOC_NEW_PAGE
alloziert nicht
nur
Speicher, sondern garantiert auch, dass er am
Anfang einer Speicherseite beginnt.
Reserved
Commited
OMP_ALLOC_NEW_PAGE
unused
OMP_ALLOC
OMP_ALLOC
OMP_ALLOC
Abb. 6.3: Der SHARED-Speicher
Da pro Knoten mehrere Threads parallel arbeiten
können, muss dafür gesorgt werden, dass pro OMP_ALLOC nur ein Thread realer Speicher alloziert.
Die anderen erhalten lediglich den Pointer auf den entsprechenden Speicherbereich zurück.
Der aktuelle Allokationsstatus wird
durch eine zyklische, einfach
Pointer: 0x00000000
Threads: 0
verkettete Liste repräsentiert, deren
Elemente neben dem Pointer auf
Pointer: 0x00000000
Pointer: 0x3b800000
den allozierten Speicherbereich
Threads: 0
Threads: 1
auch die Anzahl der lokalen
Threads, die diese Allokation noch
Pointer: 0x3b800600
Pointer: 0x3b800400
nicht ausgeführt haben, enthalten.
Threads: 4
Threads: 3
Jeder Thread kennt das Element,
das er für die nächste Allokation
verwenden
soll.
Ist
die
Threadanzahl gleich Null, dann
Thread 0
Thread 1
Thread 2
Thread 3
Thread 4
handelt es sich um eine neue
Alloc(256)
Alloc(512)
Alloc(512)
Alloc(1024)
Allokation, ansonsten wird nur die
Alloc(256)
Alloc(256)
Alloc(512)
Alloc(256)
Speicheradresse zurückgegeben.
Initial enthält diese Kette nur ein
Abb. 6.4: Kette der pendenten Allokationen
Element mit der Threadanzahl Null.
Mit jeder neuen Allokation kommt ein Element dazu, es sei denn, es existiert bereits ein Element,
das inzwischen wieder die Threadanzahl Null erreicht hat.
6.1.3.3 Allozierter Speicher existiert in einem Scope
Wer mit der Allokation von Speicher zu tun hat, muss sich automatisch auch mit der Deallokation
befassen, schliesslich ist der Speicher eine begrenzte Ressource. In erster Linie stellt sich die
Frage, wer die Deallokation übernimmt: Gibt es eine explizite Deallokation durch den OpenMPProgrammierer? Oder übernimmt das System die Deallokation implizit?
Die explizite Version hätte zur Folge, dass der SHARED-Speicher als Heap funktionieren müsste.
Die Konsequenzen wären eine aufwendige Buchführung der benutzten bzw. freien
Speicherbereiche und eine zunehmende Fragmentierung des SHARED-Speichers.
WinNT: Win32 bietet eine Reihe von Funktionen, die für den Programmierer einen oder mehrere
Heaps implementieren und unterhalten. Mit HeapCreate bzw. HeapDestroy lässt sich
ein Heap erzeugen bzw. auflösen, mit HeapAlloc bzw. HeapFree kann Speicher
alloziert bzw. dealloziert werden. Es gibt noch weitere Heap-Funktionen. Leider ist nicht
Seite 52
ETH Zürich
dokumentiert, wo diese Heap-Funktionen die nötigen Verwaltungsstrukturen ablegen. Da
sich für OpenMP diese Strukturen unter keinen Umständen im eigentlichen SHAREDSpeicher befinden dürfen, wurde von der Verwendung dieser Funktionen abgesehen.
Der OpenMP-Prototyp verwendet die
implizite Variante: Der SHARED-Speicher
funktioniert dabei nicht als Heap, sondern
als Stack. Jedes OMP_ALLOC reserviert
Speicher on top of stack und lässt den
Stack wachsen.
OMP_DO
OMP_END_DO
OMP_INIT/OMP_EXIT,
OMP_PARALLEL/OMP_END_PARALLEL,
OMP_PARALLEL
OMP_END_PARALLEL
OMP_DO/OMP_END_DO
und
OMP_SECTIONS/OMP_END_SECTIONS
definieren sogenannte (geschachtelte)
OMP_EXIT
OMP_INIT
Scopes (Abbildung 6.5). Am Beginn jedes
Scopes wird eine neuer Stack-Frame
Abb. 6.5: Stack-Frames verschiedener Scopes
angelegt. Innerhalb des Scopes kann nun
beliebig Speicher alloziert werden. Am Ende des Scopes wird der aktuelle Stack Frame, dass
heisst, aller innerhalb des Scopes allozierter Speicher, wieder freigegeben (decommited).
6.1.3.4 Synchronisation des SHARED-Speicher
Bevor die in Abbildung 6.2 dargestellten Zustandsübergänge beschrieben werden können, müssen
an dieser Stelle einige Worte über Synchronisation verloren werden.
Auf Grund der geographischen Verteilung des Systems und den damit verbundenen (grossen)
Latenzzeiten bei der Kommunikation zwischen den verschiedenen Knoten wäre es nicht effizient,
jede einzelne Veränderung im SHARED-Speicher sofort an die anderen Knoten weiterzuleiten. Es
werden also mehrere Modifikationen zu einem Paket zusammengefasst und dann als ganzes
verschickt. Genauer gesagt, werden im OpenMP-Programm implizit oder explizit
Synchronisationspunkte, sogenannte Barriers, definiert. Sobald ein Thread an eine Barrier gelangt,
wird dieser Schlafen gelegt. Sind alle Threads eines Knotens an einer Barrier angekommen, wird
der Kommunikations-Thread allen anderen Knoten mitteilen, welche Speicherseiten seine Threads
verändert haben. Wenn der Knoten von allen anderen die Veränderungen empfangen hat, kann er
sich lokal errechnen, welcher Knoten welche gültigen Seiten besitzt. Erst dann werden die Threads
ihre Arbeit wieder aufnehmen.
Wie bei TreadMarks kommt also auch bei diesem Prototypen das sogenannte Lazy-ReleaseConsistency-Verfahren zum Zuge: Das heisst, bei der Synchronisation wird nicht der Inhalt der
veränderten Speicherseiten kommuniziert, sondern nur eine Liste der Nummern aller modifizierten
Speicherseiten. Erst wenn ein Thread auf eine Speicherseite zugreift, die ein anderer Thread vor
der letzten Synchronisation verändert hat, wird diese angefordert.
Dieses Verfahren ist jedoch mit äusserster Vorsicht zu geniessen: Auf Grund der
Netzwerktopologie kann ein Knoten die Barrier bereits verlassen und neue Page-Faults generiert
haben, bevor die anderen Knoten alle Modifikationsmitteilungen erhalten haben. Treffen zu diesem
Zeitpunkt Page-Requests solcher „schneller“ Knoten ein, so müssen diese unbedingt
zurückgehalten werden, bis der eigene Knoten die Barrier verlassen kann!
Die bisherigen Ausführungen zur Synchronisation implizieren quasi, dass zwischen zwei Barriers
nur immer ein Knoten auf eine Speicherseite schreibend zugreifen darf. Auf Grund der groben
Unterteilung des Speichers in Speicherseiten (4kB!) kann das für den OpenMP-Programmierer
sehr problematisch werden, da er sicherstellen muss, dass die einzelnen Threads (auf
verschiedenen Knoten) nur Variablen schreibend benutzen, die auch in verschiedenen
Speicherseiten liegen.
In TreadMarks wurde ein Multiple-Writer-Verfahren verwirklicht, das mehreren Threads erlaubt, auf
verschiedene Stellen der selben Seite zuzugreifen. Konkret wurde also die Granularität verkleinert.
Für einen Thread, der auf eine ungültige Seite zugreift heisst das, dass er unter Umständen bei
mehreren Knoten nachfragen muss, welche Änderungen vorgenommen wurden, um aus all diesen
Informationen wieder eine gültige Seite zusammenzustellen. Dieses Verfahren kann zwar die
kommunizierte Datenmenge reduzieren, lässt sich jedoch auf keine Art und Weise mit der im
Seite 53
ETH Zürich
Prototypen geforderten Zero-Copy-Kommunikation vereinbaren, da die Speicherseite bei den
Sendern auseinandergenommen und beim Empfänger wieder zusammengesetzt werden muss.
Deshalb wurde bewusst auf diese Multiple-Writer-Funktion verzichtet. Dem Programmierer wurde
jedoch mit OMP_ALLOC_NEW_PAGE eine Funktion in die Hand gegeben, mit der er die Plazierung
der Variablen im SHARED-Speicher besser kontrollieren kann. Zusätzlich kontrolliert jeder Knoten
nach einer Barrier, ob ihm mehrere Knoten die Modifikation der selben Seite gemeldet haben und
gibt in diesem Fall eine Fehlermeldung aus.
Für die Synchronisierung des SHARED-Speichers sind zwei Listen notwendig, die hier kurz
vorgestellt werden sollen:

Modified-List: Diese Liste enthält die Nummern der Speicherseiten, die seit der letzten
Synchronisation lokal verändert wurden. Diese Liste liesse sich zwar auch aus der
Zustandstabelle der Speicherseiten ermitteln, wird im Prototypen aus Performancegründen
jedoch zur Laufzeit aufgebaut und kann beim Erreichen der Barrier sofort verschickt werden.

Owner-List: Diese Liste enthält für jede Speicherseite die Nummer des Knotens, der zuletzt
(vor der letzten Synchronisation) diese Seite modifiziert hat und damit eine gültige Kopie der
Seite besitzt.
Welche Vorgänge werden im Prototypen nun konkret ausgelöst, wenn die Threads eines Knotens
an eine Barrier gelangen:

Die Ausführung der lokalen OpenMP-Threads wird an der Barrier unterbrochen. Wenn alle
lokalen Threads an der Barrier angelangt sind, wird...

... die Modified-List an alle Knoten (inklusive an sich selbst) geschickt

... von allen Knoten eine Modified-List empfangen

... mittels dieser Modified-Listen die Owner-List aktualisiert

... jeder Speicherseite im Zustand Modified den neuen Zustand Valid zugeteilt

... jede Speicherseite, die durch einen entfernten Thread modifiziert wurde, in den Zustand
Invalid versetzt

... allfällige Kopien von Speicherseiten (siehe unten) wieder freigegeben

Die Ausführung der lokalen OpenMP-Threads wird weitergeführt.

Page-Requests, die nach dem Empfang der Modified-List eines Knotens empfangen wurden,
werden bis zu diesem Zeitpunkt verzögert.
Auf Grund von Zero-Copy hat diese Art von Barrier im Prototypen noch eine kleine Modifikation
erfahren: Der Zero-Copy-Kommunikation liegen asynchrone, kleine Pakete und synchrone, grosse
Pakete zu Grunde. Die Modified-List wird in einem kleinen Paket verschickt. Wegen der
begrenzten Grösse kann es theoretisch vorkommen, dass mehr Seiten verändert werden, als in
einem Paket Platz finden. Hat die Modified-List die Grösse eines Paketes erreicht, dann wird es
unmittelbar verschickt (also nicht auf eine Barrier gewartet) und eine neue, leere Liste wird
angelegt. Im Header des Paketes, das eine Modified-List enthält, teilt ein Flag mit, ob der Knoten
an einer Barrier angelangt ist, oder ob einfach die Liste voll war. Dieses Verfahren bedingt jedoch,
dass jeder Knoten zwei Owner-Lists unterhält: Eine aktuelle, und eine, die fortlaufend aus den
empfangenen Modified-Lists aufgebaut und bei der nächsten Barrier mit der aktuellen
verschmolzen wird.
Auf Grund des Single-Writer-Verfahrens ist die Grösse des verwendeten Speichers oft abhängig
von der Anzahl der Knoten, da Speicherseiten gleichzeitig nur durch einen Knoten beschrieben
werden dürfen. Ein Knoten wird jedoch sehr oft nur auf einem kleinen Teil des SHARED-Speichers
arbeiten. Um das Working-Set gezielt klein zu halten, könnte den Seiten, die den Zustand Invalid
haben, der physische Speicher entzogen (decommit) werden. Erst bevor eine gültige Seite
angefordert wird, würde dieser Seite wieder Speicher zugeordnet (commit). Dieses Verfahren ist im
Prototypen implementiert, wenn die Precompiler-Variable OMP_DECOMMIT_INVALID beim
Kompilieren der OpenMP-Bibliothek gesetzt ist (siehe OMPLIB.H).
Zu erwähnen ist hier noch, dass die einzelnen Threads eines Knotens untereinander nicht
synchronisiert werden müssen, da sie auf den selben lokalen SHARED-Speicher zugreifen. Das
heisst im wesentlichen, dass für alle lokalen Threads eine lokale Speichermodifikation sofort
Seite 54
ETH Zürich
sichtbar wird. Es ist deshalb auch erlaubt, dass mehrere lokale Threads die selbe Speicherseite
modifizieren. Es muss dem Programmierer jedoch bewusst sein, dass danach ein lokaler Thread
eine andere Sicht der entsprechenden Seite hat, als ein entfernter, da dieser erst nach der
nächsten Barrier von der Modifikation erfährt!
WinNT: Trotzdem ist natürlich auch lokal viel Synchronisation nötig, um den SHARED-Speicher
und die erwähnten Listen in einem konsistenten Zustand zu halten. Windows NT bietet
dafür eine Vielzahl von Synchronisationsobjekten an: Events stellen ein Signal dar, auf
welches ein Thread warten kann. Mutex erlauben exklusiven Zugriff auf Codestücke und
die darin modifizierten Daten. Semaphoren erlauben einer beschränkten Anzahl Threads
den Zugriff auf Code bzw. Daten. Folgende Win32-Funktionen stehen im Zusammenhang
mit diesen Synchronisationsobjekten: CreateEvent, SetEvent, ResetEvent,
CreateMutex,
ReleaseMutex,
CreateSemaphore,
ReleaseSemaphore,
WaitForSingleObject, WaitForSingleObjectEx, WaitForMultipleObjects,
CloseHandle.
6.1.3.5 Eine gültige Speicherseite wird beschrieben
Was passiert nun, wenn ein Thread eine gültige Speicherseite (Zustand Valid) beschreibt? Laut
Diagramm wird diese Seite in den Zustand Modified übergehen. Genauer gesagt passiert
folgendes:

Eine Seite im Zustand Valid verfügt nur über Lesezugriff. Auf Grund des Schreibzugriffs wird
der Exception-Handler aufgerufen.

Dieser ändert den Zustand der Seite in Modified und fügt die Seitennummer in die Modified-List
ein.

Der Speicherseite wird das Recht für Schreib-/Lese-Zugriff zugeteilt.

Wenn dieser Knoten laut Owner-List der Knoten mit der gültigen Seite ist, dann muss von
dieser Seite eine Kopie angefertigt werden, um anderen Knoten, die eine gültige Seite
anfordern, den Zustand bei der letzten Barrier liefern zu können. Dies ist der einzige Fall im
Prototypen, wo Zero-Copy nicht erfüllt wird!
Tests mit konkreten OpenMP-Anwendungen (siehe Kapitel 9) haben gezeigt, dass diese
Kopiervorhänge nicht nur zeitraubend und ineffizient, sondern dass sie bei Algorithmen mit hohem
Parallelisierungsgrad (d.h. Datenbereiche werden über einen längeren Zeitraum ausschliesslich
von ein und demselben Thread gelesen und beschrieben) auch unnötig sind. Aus diesem Grund
wurde ein sogenannter Lock-Mechanismus eingebaut. Mit OMP_LOCK können durch einen Thread
einer oder mehreren Speicherseiten dauerhaft Read/Write-Zugriffsrechte zugeteilt werden, ohne
dass eine Kopie der Daten angelegt würde. Dieser Lock-Zustand bleibt auch über Barriers hinaus
bestehen. Threads auf entfernten Knoten haben nach einem Lock keinerlei Zugriffsrechte auf
gesperrte Seiten. Mit OMP_UNLOCK können gesperrte Seiten wieder freigegeben werden.
Der implementierte Lock-Mechanismus ist sehr einfacher Natur. Insbesondere wird den entfernten
Knoten nicht mitgeteilt, dass Seiten gesperrt wurden. Der OpenMP-Programmierer ist selber
verantwortlich, dass nur der Thread, der die Seiten gesperrt hat, auf diese Seiten zugreift.
Fehlerhaft agierende OpenMP-Programme können Fehlermeldungen auslösen, müssen jedoch
nicht.
6.1.3.6 Auf eine ungültige Speicherseite wird zugegriffen
Eine Speicherseite, die ausserhalb des Knotens modifiziert wurde, ist im Zustand Invalid. Bei der
letzten Synchronisation wurde zwar mitgeteilt, welcher Knoten die gültige Kopie der Seite besitzt,
der Inhalt wurde aber bewusst noch nicht übermittelt. Sobald der erste lokale Thread nun auf diese
Seite zugreift, wird der Exception-Handler aufgerufen, da die Seite über keine Zugriffsrechte
verfügt. Dieser hat folgendes zu tun:

Die Seite wird in den Zustand Recv versetzt, um anderen lokalen Threads mitzuteilen, dass die
Seite zwar immer noch ungültig ist, jedoch bereits von einem Thread angefordert wird.

Der Kommunikations-Thread wird gebeten, eine gültige Kopie der entsprechenden Seite zu
besorgen.
Seite 55
ETH Zürich

Der Thread wird schlafen gelegt, bis der Kommunikations-Thread die gültige Kopie empfangen
hat. Falls inzwischen weitere Threads auf diese Seite zugreifen, werden diese ebenfalls
schlafen gelegt.

Wurde die Seite aktualisiert, dann wird der erste Thread aufgeweckt. Falls auf die Seite lesend
zugegriffen wurde, wird der Zustand der Seite auf Valid gesetzt und mit den Rechten für
Lesezugriff versehen. Falls geschrieben wurde, dann wird obiges Szenario ausgeführt.

Alle Threads, die auf Grund des Recv-Zustandes schlafen gelegt wurden, werden aufgeweckt.
6.1.3.7 Ein entfernter Thread fordert eine Speicherseite an
Eine Anfrage eines entfernten Threads um eine gültige Kopie einer Speicherseite wird vollständig
vom Kommunikations-Thread bearbeitet, kann jedoch nicht in jedem Fall ohne Nebenwirkungen für
die OpenMP-Threads über die Bühne gehen. Folgendes passiert, wenn ein Page-Request
empfangen wird:

Falls die Seite den Zustand Valid hat, wird sie vorübergehend in den Zustand Send versetzt,
um anderen lokalen Threads mitzuteilen, dass die Seite zwar immer noch gültig ist, zur Zeit
jedoch nicht schreibend darauf zugegriffen werden darf. Schreibende Threads werden in
diesem Fall schlafen gelegt.

Der Kommunikations-Thread versendet die Seite. Falls die Seite den Zustand Modified
aufweist, wird die Kopie der Seite verschickt.

Falls die Seite im Zustand Send ist, wird sie auf Valid zurückgesetzt.

Alle Threads, die auf Grund des Send-Zustandes schlafen gelegt wurden, werden wieder
geweckt.
6.1.4 Private Memory
Die Realisation des PRIVATE-Speichers ist keine besonders komplexe Angelegenheit, doch die
fehlende Compilerunterstützung fordert doch einige Kniffe, um eine vernünftige Implementation zu
erreichen.
Um was geht es überhaupt? Neben dem global zugreifbaren SHARED-Speicher hat jeder Thread
noch einen privaten Speicherbereich, auf den nur er zugreifen kann. Grundsätzlich lässt sich
Speicher nur auf dem SHARED-Speicher allozieren. Doch Speicherbereiche im SHARED-Speicher
können „privatisiert“ werden, indem mit OMP_PRIVATE ein Speicherbereich der selben Grösse im
PRIVATE-Speicher alloziert, und der Pointer der Variable auf diesen neuen Bereich umgebogen
wird. An dieser Stelle ist zu erwähnen, dass OpenMP-Variablen (in diesem Prototypen) immer
Pointer sind, die entweder auf den SHARED- oder den PRIVATE-Speicher zeigen.
Auch private Variablen existieren nur in dem Scope, in dem
OMP_PRIVATE aufgerufen wurde. Wird der Scope
verlassen, dann werden auch die privaten Variablen
gelöscht und der Variablenpointer wieder zurück auf den
entsprechenden SHARED-Speicher gebogen.
Pointer to pointer
Auch der PRIVATE-Speicher ist als Stack implementiert.
Jedes mal, wenn ein neuer Scope eröffnet wird, wird ein
Pointer to shared
Frame-Mark auf den Stack geschrieben. Der Aufruf von
Lastprivate ?
OMP_PRIVATE reserviert nicht nur den für die Variable
Size of variable
nötigen Speicherbereich, sondern speichert auch alle
Informationen, um beim Verlassen des Scope den aktuellen
Stack-Frame wieder abzubauen. Zu diesen Informationen
Content of
gehören die Grösse des allozierten Speicherbereichs, die
the variable
Adresse des entsprechenden Bereichs im SHAREDSpeicher, die Adresse der Pointervariable, sowie ein Flag
Frame Mark
das anzeigt, ob der Inhalt des PRIVATE-Bereichs beim
Verlassen des Scopes in den SHARED-Bereich kopiert
Abb. 6.6: PRIVATE-Speicher
werden soll (OMP_LASTPRIVATE) oder nicht.
Seite 56
ETH Zürich
Beim Verlassen eines Scopes wird Variable für Variable inklusive den Zusatzinformationen
ausgelesen, eventuell der Inhalt der PRIVATE-Variable in den SHARED-Speicher
zurückgeschrieben und der Variablenpointer auf den SHARED-Bereich zurückgebogen. Das wird
solange getan, bis ein Frame-Mark erkannt wird.
6.2 Das API des OpenMP-Prototypen
Dieses Unterkapitel beschreibt das API des Prototypen, wie es angewendet wird, und welche
Einschränkungen gegenüber dem originalen OpenMP Fortran API [2] bestehen.
Alle OpenMP-Direktiven und Run-time-Library-Routinen sind als #define in der C-Headerdatei
OPENMP.H implementiert und greifen auf die Funktionsbibliothek OMPLIB.DLL zu. Ein um OpenMPFunktionalität erweitertes C-Programm muss OMPLIB.LIB mitlinken, um Zugriff auf die Funktionen in
der DLL zu bekommen.
Folgendes kleines Beispiel zeigt ein Programm, das die Summe aller Zahlen zwischen 1 und
10‘000 verteilt auf mehrere Threads berechnet:
OMP_INIT
OMP_INIT_DECLARE
int* x = OMP_ALLOC(sizeof(int));
int* z = OMP_ALLOC(sizeof(int));
OMP_INIT_END_DECLARE
OMP_PARALLEL(TRUE)
OMP_PARALLEL_DECLARE
int i;
int *y[OMP_GET_MAX_THREADS];
OMP_PARALLEL_END_DECLARE
for(i = 0; i < OMP_GET_NUM_THREADS; i++)
y[i] = OMP_ALLOC_NEW_PAGE(sizeof(int));
*(y[OMP_GET_THREAD_NUM]) = 0;
OMP_DO
OMP_DO_DECLARE
OMP_PRIVATE(x, sizeof(int))
OMP_DO_END_DECLARE
DO(x, 1, 10000, 1)
*(y[OMP_GET_THREAD_NUM]) += *x;
OMP_END_DO
OMP_MASTER
*z = 0;
for(*x = 0; *x < OMP_GET_NUM_THREADS; (*x)++)
*z += *(y[*x]);
printf("Summe = %i\n", *z);
OMP_END_MASTER
OMP_END_PARALLEL
OMP_EXIT
Die Tatsache, dass der Prototyp ohne Complierunterstützung auskommen muss, lässt die
Programmierung von OpenMP-Anwendungen etwas kompliziert erscheinen. Welche
Einschränkungen gelten und was sonst noch beachtet werden muss, wird bei der Beschreibung
der einzelnen Direktiven genauer erläutert.
6.2.1 OMP_INIT / OMP_EXIT
Original:
-
Prototyp:
OMP_INIT
OMP_INIT_DECLARE
{declaration}
block
OMP_EXIT
Seite 57
ETH Zürich
Jedes OpenMP-Programm, das den Prototypen verwendet, muss mit der OMP_INIT-Direktive
beginnen. Jeder OpenMP-Thread bearbeitet das Programm zwischen OMP_INIT und OMP_EXIT,
gesteuert von den Direktiven dazwischen. OMP_EXIT ist die letzte Direktive im Programm.
Innerhalb der beschriebenen Direktiven sind keine Subroutinen erlaubt. Sollten Subroutinen nötig
sein, dann sind diese entweder vor OMP_INIT zu plazieren oder nach OMP_EXIT, wobei diese
dann in einer Headerdatei deklariert sein müssen. Es ist verboten, innerhalb von Subroutinen
OpenMP-Direktiven zu verwenden, die einen neuen Scope eröffnen! Grundsätzlich wird auf Grund
der fehlenden Compilerunterstützung empfohlen, auf Subroutinen zu verzichten.
Da die Sprache C die Variablendeklaration nur am Anfang eines Blockes erlaubt, müssen diese in
einem OpenMP-Programm ganz zu Beginn eines neuen Scopes vorgenommen werden. Deshalb
wurden die nicht zum Standard gehörenden Direktiven OMP_INIT_DECLARE und
OMP_INIT_END_DECLARE eingeführt. Zwischen den beiden Direktiven werden alle Variablen
deklariert, die im SHARED-Speicher von OpenMP plaziert werden und über die gesamte Laufzeit
(auch über die Grenzen von PARALLEL-Blöcken hinweg) verfügbar sein sollen. Declaration weisst
folgendes Format auf:
pointer_type var [= OMP_ALLOC[_NEW_PAGE](size)];
Es können grundsätzlich nur Pointer verwendet werden, so dass das OpenMP-System die
Möglichkeit hat, den Pointer umzubiegen (z.B. beim Aufruf von OMP_PRIVATE, um den Pointer
vom SHARED-Speicher in den PRIVATE-Speicher umzuplazieren). Der Programmierer sollte
diese Variablen aber nicht als Pointer betrachten, sondern als normale Instanzen eines bestimmten
Typs. Zugriffe auf die Variablen sind dann auch immer in dereferenzierter Form vorzunehmen, wie
in Beispiel 1 gezeigt.
Beispiel 1:
OMP_INIT
OMP_INIT_DECLARE
int* y = OMP_ALLOC_NEW_PAGE(2 * sizeof(int));
OMP_PARALLEL(TRUE)
*x = 0;
y[0] = 15;
y[1] = *x;
OMP_END_PARALLEL
OMP_EXIT
Der Programmbereich zwischen OMP_INIT_END_DECLARE und dem ersten OMP_PARALLEL wird
nur vom globalen Master-Thread ausgeführt, alle anderen Threads überspringen diesen Bereich.
Die Angabe von OMP_INIT_DECLARE und OMP_INIT_END_DECLARE ist zwingend, auch wenn
keine Deklarationen vorgenommen werden!
Differenzen zum Standard:
All diese Direktiven existieren im Standard nicht. Da Standard-OpenMP eine Compilererweiterung
ist, würden alle nötigen Initialisierungs- und Aufräumarbeiten vom Compiler automatisch eingefügt.
Implementation:
#define OMP_INIT
Seite 58
int main( int argc, char *argv[ ], char *envp[ ] )\
{\
OMP_Init(argc, argv, _OpenMPThreadFunc);\
OMP_Run();\
OMP_Exit();\
return 0;\
}\
DWORD WINAPI _OpenMPThreadFunc(LPVOID _pVoid)\
{\
int _nThreadNum = (int)_pVoid;\
__try\
{
ETH Zürich
OMP_Init() initialisiert die internen Datenstrukturen und baut die Kommunikation auf.
OMP_Run() startet dann die lokalen OpenMP-Threads und sichert die Kommunikation solange
diese laufen. OMP_Exit() beendet die Kommunikation und baut die internen Datenstrukturen
wieder ab. _nThreadNum enthält die lokale Thread-Nummer.
#define OMP_EXIT
}\
}\
__except(OMP_ExceptionFilter(_nThreadNum,\
GetExceptionInformation()))\
{\
OMP_Abort(“Unhandled exception”);\
}\
OMP_PostThreadTermination(_nThreadNum);\
return 0;\
}
Für den gesamten Programmbereich übernimmt OMP_ExceptionFilter() das ExceptionHandling. Fehler, die korrekt aufgelöst werden können (Page-Faults), werden ohne sichtbare
Anzeichen für den Betrachter behandelt, alle anderen Fehler führen zum sofortigen Abbruch des
Prozesses durch OMP_Abort(). Die bevorstehende Termination des Threads wird OMP_Run()
durch OMP_PostThreadTermination() mitgeteilt.
#define OMP_INIT_DECLARE
#define OMP_INIT_END_DECLARE
if (OMP_GetThreadNum(_nThreadNum) == 0)\
{
6.2.2 OMP_ALLOC / OMP_ALLOC_NEW_PAGE
Original:
-
Prototyp:
pointer = OMP_ALLOC( size );
pointer = OMP_ALLOC_NEW_PAGE( size );
Um den deklarierten Variablen einen Speicherbereich aus dem SHARED-Speicher zuzuweisen,
können die beiden Funktionen OMP_ALLOC / OMP_ALLOC_NEW_PAGE verwendet werden. Beide
Funktionen nehmen als Parameter die Grösse des zu allozierenden Speicherblocks in Bytes
entgegen und geben einen Pointer zum entsprechenden Speicherbereich zurück (siehe Beispiel 1).
OMP_ALLOC alloziert den Speicher unmittelbar angrenzend an den letzten allozierten Bereich. Im
Gegensatz dazu alloziert OMP_ALLOC_NEW_PAGE den gewünschten Speicherbereich garantiert in
der nächsten Speicherseite. Da dieser Prototyp Multiple-Writer-Funktionalität nicht unterstützt, ist
dies nützlich, wenn auf zwei Variablen gleichzeitig aus zwei (auf verschiedenen Maschinen
laufenden) Threads zugegriffen werden soll.
Der allozierte Speicherbereich steht nur im aktuellen Scope zur Verfügung. Im Bereich
OMP_INIT_DECLARE / OMP_END_INIT_DECLARE allozierter Speicher hat maximalen Scope, was
heissen will, dass der Speicher während der ganzen Laufzeit verfügbar ist, auch über die grenzen
von PARALLEL-Blöcken hinweg.
Diese beiden Funktionen sind nicht Bestandteil des OpenMP-Standards. Die Speicherallokation
würde standardgemäss durch den Compiler geregelt.
Implementation:
#define OMP_ALLOC(size)
OMP_Alloc(_nThreadNum, size, FALSE)
#define OMP_ALLOC_NEW_PAGE(size)
OMP_Alloc(_nThreadNum, size, TRUE)
OMP_Alloc() alloziert einen Speicherblock der gewünschten Grösse entweder fortlaufend oder
page-aligned. Realer Speicher wird jedoch nur durch den ersten lokalen Thread, der diese
Funktion aufruft, alloziert, alle anderen Threads erhalten lediglich den Pointer auf den bereits
allozieren Bereich zurück.
Seite 59
ETH Zürich
6.2.3 OMP_PARALLEL / OMP_END_PARALLEL
Original:
!$OMP PARALLEL [clause {[,] clause}]
block
!$OMP END PARALLEL
Prototyp:
OMP_PARALLEL(logical_expression)
{declaration}
{clause}
block
OMP_END_PARALLEL
Programmcode zwischen OMP_PARALLEL und OMP_END_PARALLEL wird von allen OpenMPThreads ausgeführt, wenn das nicht durch andere Direktiven innerhalb des PARALLEL-Blocks
eingegrenzt wird.
OMP_PARALLEL öffnet einen neuen Scope. Alle Variablen, die im globalen Scope deklariert
wurden, sind auch im neuen Scope sichtbar. Variablen, die zwischen OMP_PARALLEL_DECLARE
und OMP_PARALLEL_END_DECLARE deklariert, und Speicher, der dazwischen alloziert wird, ist nur
innerhalb dieses Scopes gültig. Declaration entspricht der obigen Definition.
Folgende clause sind vom Standard übernommen und im Prototypen implementiert worden:

DEFAULT(SHARED): Alle Variablen, die im äusseren
standardmässig im neuen Scope als SHARED weiter.

PRIVATE(list)ist implementiert in OMP_PRIVATE.

FIRSTPRIVATE(list)ist implementiert in OMP_FISTPRIVATE.

IF(scalar_logical_expression) ist in logical_expression von OMP_PARALLEL enthalten.
Scope
existieren,
existieren
Logical_expression ist ein boolscher Ausdruck. Der parallele Bereich wird nur dann ausgeführt,
wenn der Ausdruck wahr ist.
Der Bereich zwischen OMP_END_PARALLEL und dem nächsten OMP_PARALLEL bzw. OMP_EXIT
wird ausschliesslich durch den globalen Master-Thread ausgeführt.
Weder OMP_PARALLEL_DECLARE noch OMP_PARALLEL_END_DECLARE gehören zum Standard.
Da die OpenMP-Threads nicht dynamisch gestartet werden, sind verschachtelte PARALLELBlöcke, wie es der OpenMP-Standard erlaubt, nicht möglich.
Folgende clause sind nicht oder nur unvollständig implementiert:

SHARED(list) ist default, das heisst, alle Variablen existieren im SHARED-Speicher, wenn sie
nicht explizit als PRIVATE deklariert werden.

DEFAULT(PRIVATE | NONE): DEFAULT(PRIVATE) dürfte ohne Compilerunterstützung nur
mit erheblichem Aufwand zu implementieren sein, da dem System immer alle Variablen
bekannt sein müssten.

REDUCTION({operator|intrinsic}:list): Auch dieser Ausdruck ist ohne Compilerunterstützung
nur mit grossem Aufwand zu implementieren, da Typenerkennung nötig wird.

COPYIN(list) bezieht sich auf Fortran-Common-Blocks, die C nicht unterstützt.
Implementation:
#define OMP_PARALLEL(ifexp)
Seite 60
}\
if (ifexp)\
{\
OMP_EnterParallel(_nThreadNum);\
{
ETH Zürich
Ausgeführt wird der PARALLEL-Bereich nur, wenn der boolsche Ausdruck ifexp einen wahren
Wert ergibt. OMP_EnterParallel() synchronisiert alle OpenMP-Threads mit einer globalen
Barrier und eröffnet einen neuen Scope sowohl im SHARED- wie auch im PRIVATE-Speicher.
#define OMP_END_PARALLEL
}\
OMP_LeaveParallel(_nThreadNum);\
}\
{
OMP_LeaveParallel() synchronisiert zuerst die Threads mit einer Barrier, danach wird aller im
aktuellen Scope allozierter Speicher freigegeben und der Scope gelöscht.
#define OMP_PARALLEL_DECLARE
#define OMP_PARALLEL_END_DECLARE
6.2.4 OMP_DO / OMP_END_DO
Original:
!$OMP DO [clause {[,] clause}]
do_loop
[!$OMP END DO [NOWAIT]]
Prototyp:
OMP_DO
OMP_DO_DECLARE
{declaration}
{clause}
OMP_DO_END_DECLARE
DO(pointer, from, to, step)
block
OMP_END_DO({ WAIT | NOWAIT })
Ein paralleler Loop, wie er durch OMP_DO / OMP_END_DO implementiert wird, kann nur innerhalb
von OMP_PARALLEL / OMP_END_PARALLEL existieren.
OMP_DO eröffnet einen neuen Scope für Variablen. Alle Variablen, die in einem äusseren Scope
deklariert wurden, sind auch im neuen Scope sichtbar. Zwischen OMP_DO_DECLARE und
OMP_DO_END_DECLARE können Variablen deklariert und Speicher alloziert werden, die
ausschliesslich innerhalb dieses Scopes existieren.
Folgende clause werden vom Standard übernommen und implementiert:

LASTPRIVATE(list)ist implementiert in OMP_LASTPRIVATE.

SCHEDULE(STATIC,1): Die einzelnen Iterationen werden im Round-Robin-Verfahren auf die
einzelnen Threads aufgeteilt.
OMP_FIRSTPRIVATE und OMP_LASTPRIVATE lassen sich nur auf Variablen aus dem äusseren
Scope sinnvoll anwenden. Die LASTPRIVATE-Variablen werden von dem Thread zurückkopiert,
der die letzte Iteration durchgeführt hat.
Die eigentliche Schleife wird durch DO implementiert. Der Parameter pointer ist ein Pointer auf eine
Variable im PRIVATE-Bereich (also nicht dereferenzieren!). Der Pointer zeigt auf die zu
verwendende Iterationsvariable, die von einem gültigen Integer-Typ sein muss. DO würde in C etwa
folgendermassen aussehen, wobei die einzelnen Iterationen auf die Threads verteilt werden:
for(*pointer = from; *pointer <= to; *pointer += step)
Wie auch im OpenMP-Standard vorgeschrieben, sind verschachtelte, parallelisierte Schleifen nicht
erlaubt. Es können jedoch normale for- oder while-Schleifen in parallele Schleifen eingebaut
werden.
Seite 61
ETH Zürich
Mit WAIT bzw. NOWAIT kann entschieden werden, wie die Threads sich nach Beendigung der
Schleife verhalten sollen. WAIT impliziert eine globale Barrier, das heisst, alle Threads und der
Status des SHARED-Speichers werden synchronisiert. Mit NOWAIT werden nur die lokalen
Threads synchronisiert. Dies ist nötig, damit alle lokalen Threads den gleichen Scope aufweisen.
Weder OMP_DO_DECLARE noch OMP_DO_END_DECLARE gehören zum Standard.
Folgende clause sind in diesem Prototypen nicht implementiert worden:

REDUCTION ({operator|intrinsic}:list): siehe OMP_PARALLEL.

SCHEDULE(type[,chunk]): Die Implementation von anderen Typen als STATIC und anderen
Chunk-Grössen als 1 liesse sich zum Teil durch einfaches verändern der DO-Implementation
realisieren. Typen wie DYNAMIC jedoch bedürfen zusätzlicher Kommunikation und
Synchronisation.

ORDERED: Könnte nur durch entsprechende Kommunikation und Synchronisation implementiert
werden. Damit zusammenhängend sind auch die Direktiven !$OMP ORDERED und !$OMP END
ORDERED nicht implementiert.
Implementation:
#define OMP_DO
OMP_EnterBlock();\
OMP_PrivatePush(_nThreadNum, NULL, 0, FALSE, FALSE);\
{
OMP_EnterBlock() eröffnet einen neuen Scope im SHARED-Speicher. OMP_PrivatePush()
tut das selbe im PRIVATE-Speicher.
#define DO(px,from,to,step)
{\
int _nLast = ( ((to-from+1)/step) -\
(((to-from+1)%step)?0:1) ) %\
OMP_GetNumThreads();\
for(*px = (from +\
(OMP_GetThreadNum(_nThreadNum) * step));\
*px <= to;\
*px += (step * OMP_GetNumThreads()) )\
{
_nLast beschreibt, welcher OpenMP-Thread das Recht hat, den Inhalt von allfälligen
LASTPRIVATE-Variablen in den SHARED-Speicher zurückzuschreiben. Die for-Schleife
überspringt alle Iterationen, die nicht durch den aktuellen Thread ausgeführt werden sollen.
#define OMP_END_DO(wait)
}\
OMP_ReleasePrivate(_nThreadNum, _nLast ==\
OMP_GetThreadNum(_nThreadNum));\
OMP_Barrier(_nThreadNum, (wait == NOWAIT), TRUE);\
}\
}
OMP_RelaesePrivate() kopiert allenfalls die LASTPRIVATE-Variablen zurück in den SHAREDSpeicher und gibt den aktuellen Scope im PRIVATE-Speicher frei. OMP_Barrier() implementiert
je nach wait eine lokale oder eine globale Barrier und gibt den aktuellen Scope auf dem
SHARED-Speicher frei.
#define OMP_DO_DECLARE
#define OMP_DO_END_DECLARE
Seite 62
ETH Zürich
6.2.5 OMP_SECTIONS / OMP_END_SECTIONS
Original:
!$OMP SECTIONS [clause {[,] clause}]
[!$OMP SECTION]
block
[!$OMP SECTION
block]
...
!$OMP END SECTIONS [NOWAIT]
Prototyp:
OMP_SECTIONS
OMP_SECTIONS_DECLARE
{declaration}
{clause}
OMP_SECTIONS_END_DECLARE
block
{OMP_SECTION([ FIRST | NEXT | thread-number ])
block }
OMP_END_SECTIONS([ WAIT | NOWAIT ])
Die SECTIONS-Direktiven teilen mehrere Codestücke verschiedenen Threads zur Bearbeitung zu.
OMP_SECTIONS markiert den Beginn eines solchen Bereichs. Wie bereits bei OMP_PARALLEL und
OMP_DO beschrieben, öffnet auch OMP_SECTIONS einen neuen Scope für Variablen. So können
zwischen OMP_SECTIONS_DECLARE und OMP_SECTIONS_END_DECLARE Variablen deklariert und
Speicher alloziert werden, die nur bis OMP_END_SECTIONS Gültigkeit haben.
Folgende clause werden vom Prototypen implementiert:

LASTPRIVATE(list)ist implementiert in OMP_LASTPRIVATE.
OMP_FIRSTPRIVATE und OMP_LASTPRIVATE lassen sich nur auf Variablen aus dem äusseren
Scope sinnvoll anwenden. Die LASTPRIVATE-Variablen werden von dem Thread zurückkopiert,
der die lexikographisch letzte SECTION ausgeführt hat.
Der erste Block wird vom globalen Master-Thread ausgeführt. Die weiteren Blöcke sind durch
OMP_SECTION voneinander getrennt. FIRST als Parameter bewirkt die Ausführung des nächsten
Blocks durch den globalen Master-Thread. NEXT lässt den folgenden Block durch den Thread
ausführen, der die nächst höhere globale Threadnummer hat als der Thread des vorgängigen
Blocks. Es kann auch explizit eine Threadnummer angegeben werden.
OMP_END_SECTIONS schliesst die SECTION ab. Mit WAIT wird eine globale Barrier eingerichtet,
die alle Threads und den SHARED-Speicher synchronisiert. NOWAIT synchronisiert nur die lokalen
Threads, um keine Probleme mit den Scopes zu bekommen.
Weder OMP_SECTIONS_DECLARE noch OMP_SECTIONS_END_DECLARE gehören zum Standard.
Folgende clause sind in diesem Prototypen nicht implementiert worden:

REDUCTION ({operator|intrinsic}:list): siehe OMP_PARALLEL.
Die Möglichkeit, OMP_SECTION eine Threadnummer zu übergeben, ist im Standard nicht enthalten,
sie ermöglicht es dem Programmierer jedoch, die Ressourcen gezielter einzusetzen.
Seite 63
ETH Zürich
Implementation:
#define OMP_SECTIONS
{\
int _nSection = 0;\
OMP_EnterBlock();\
OMP_PrivatePush(_nThreadNum, NULL, 0, FALSE, FALSE);\
{
_nSection numeriert die Sektionen. OMP_EnterBlock() und OMP_PrivatePush() eröffnen
den neuen Scope.
#define OMP_SECTIONS_DECLARE
#define OMP_SECTIONS_END_DECLARE
if (OMP_GetThreadNum(_nThreadNum) == _nSection)\
#define OMP_SECTION(x) }\
if ( OMP_GetThreadNum(_nThreadNum) ==\
((_nSection = ((x == NEXT) ? _nSection+1 : x)) %\
OMP_GetNumThreads()) )\
{
Auf Grund von _nSection wird entschieden, ob ein Thread eine Sektion auszuführen hat oder
nicht.
#define OMP_END_SECTIONS(wait)
}\
OMP_ReleasePrivate(_nThreadNum, (_nSection %\
OMP_GetNumThreads()) ==\
OMP_GetThreadNum(_nThreadNum));\
OMP_Barrier(_nThreadNum, (wait == NOWAIT), TRUE);\
}\
}
OMP_ReleasePrivte() kopiert die LASTPRIVATE-Variablen zurück und schliesst den aktuellen
Scope im PRIVATE-Speicher. OMP_Barrier() synchronisiert nur die lokalen (NOWAIT) bzw. alle
Threads (WAIT) und gibt den aktuellen Scope im SHARED-Speicher frei.
6.2.6 OMP_MASTER / OMP_END_MASTER
Original:
!$OMP MASTER
block
!$OMP END MASTER
Prototyp:
OMP_MASTER
block
OMP_END_MASTER
OMP_LOCAL_MASTER
block
OMP_END_LOCAL_MASTER
Innerhalb eines PARALLEL-Blocks kann erzwungen werden, dass ein Codestück nur durch den
globalen Master-Thread ausgeführt wird. Alle anderen Threads überspringen diesen Code.
Nicht im Standard enthalten, auf Grund der Differenzierung von lokalen und globalen Threads
jedoch nützlich, sind die Direktiven OMP_LOCAL_MASTER / OMP_END_LOCAL_MASTER. Der darin
enthaltene Code wird nur von den lokalen Master-Threads ausgeführt.
Es ist zu beachten, dass OMP_MASTER wie auch OMP_LOCAL_MASTER keine neuen Scopes
eröffnen.
Implementation:
#define OMP_MASTER
{
#define OMP_END_MASTER
}
#define OMP_LOCAL_MASTER
if (_nThreadNum == 0)\
{
#define OMP_END_LOCAL_MASTER
}
Seite 64
ETH Zürich
6.2.7 OMP_BARRIER
Original:
!$OMP BARRIER
Prototyp:
OMP_BARRIER
OMP_BARRIER stellt eine globale Barrier dar. Jeder Thread wird solange angehalten, bis alle
Threads bei der Barrier angelangt sind. Bei dieser Gelegenheit wird auch der SHARED-Speicher
synchronisiert, das heisst, es werden Informationen ausgetauscht, wer welche Speicherseite
verändert hat.
Implementation:
#define OMP_BARRIER
OMP_Barrier(_nThreadNum, FALSE, FALSE);
6.2.8 OMP_PRIVATE / OMP_FIRSTPRIVATE / OMP_LASTPRIVATE
Original:
!$OMP PRIVATE(list)
!$OMP FIRSTPRIVATE(list)
!$OMP LASTPRIVATE(list)
Prototyp:
OMP_PRIVATE(pointer, size)
OMP_FIRSTPRIVATE(pointer, size)
OMP_LASTPRIVATE(pointer, size)
Allozierter Speicher existiert grundsätzlich im SHARED-Speicher und ist für jeden OpenMP-Thread
les- und (unter Berücksichtigung des Single-Writer-Prinzips) schreibbar.
Alle OMP_xxxPRIVATE-Funktionen allozieren einen Speicherbereich im PRIVATE-Speicher. Der
Funktion wird dabei ein Pointer auf den SHARED-Speicherbereich und dessen Grösse übergeben.
Wenn die Funktion zurückkehrt, ist der gewünschte Speicherbereich im PRIVATE-Speicher
alloziert und der Pointer auf den entsprechenden Bereich umgebogen. Der allozierte
Speicherbereich ist nicht initialisiert, enthält also einen undefinierten Inhalt.
Der Speicherbereich im PRIVATE-Speicher ist nur im aktuellen Scope gültig. Wird der Scope
verlassen, dann wird automatisch der Speicher freigegeben und der Pointer wieder auf den
ursprünglichen SHARED-Bereich zurückgebogen.
Es können nur Variablen in den PRIVATE-Speicher verlegt werden, die sich bisher im SHAREDSpeicher befunden haben, das heisst insbesondere, dass eine Variable nicht zweimal mit einer
OMP_PRIVATE Funktion behandelt werden darf.
Zusätzlich zur beschriebenen Funktionalität bietet OMP_FIRSTPRIVATE die Möglichkeit, den
Speicherinhalt des entsprechenden SHARED-Bereiches in den PRIVATE-Bereich zu kopieren. Die
umgekehrte Funktionalität bietet die Funktion OMP_LASTPRIVATE, die beim Verlassen des Scopes
vom PRIVATE- in den SHARED-Bereich kopiert. Dabei kommt jedoch nur ein OpenMP-Thread
zum Zuge. Welcher das ist, hängt vom aktuellen Scope ab.
Im Gegensatz zum OpenMP-Standard können die OMP_PRIVATE-Funktionen nur jeweils eine
Variable als PRIVATE deklarieren. Sollen mehrere Variablen deklariert werden, dann muss die
Funktion mehrmals aufgerufen werden.
Implementierung:
#define OMP_PRIVATE(px, size)
#define OMP_FIRSTPRIVATE(px, size)
#define OMP_LASTPRIVATE(px, size)
OMP_DeclarePrivate(_nThreadNum, &px, size,
FALSE, FALSE);
TRUE, FALSE);
FALSE, TRUE);
OMP_DeclarePrivate() alloziert einen Bereich im PRIVATE-Speicher für den Inhalt der
Variable und für alle Informationen, die notwendig sind, um am Ende des aktuellen Scope, den
Seite 65
ETH Zürich
Speicherbereich automatisch wieder freizugeben und den Pointer wieder zurück auf den alten
Bereich zu biegen.
6.2.9 OMP_GET_NUM_THREADS
Original:
SUBROUTINE OMP_GET_NUM_THREADS()
Prototyp:
int OMP_GET_NUM_THREADS
int OMP_GET_NUM_LOCAL_THREADS
OMP_GET_NUM_THREADS gibt die Anzahl der Threads zurück, die den aktuellen PARALLEL-Block
bearbeiten. Es ist ein Wert zwischen 1 und OMP_GET_MAX_THREADS.
Ausserhalb
des
Standards
bietet
der
Prototyp
zusätzlich
OMP_GET_NUM_LOCAL_THREADS, die angibt, wieviele Threads lokal arbeiten.
die
Funktion
Implementation:
#define OMP_GET_NUM_THREADS
OMP_GetNumThreads()
#define OMP_GET_NUM_LOCAL_THREADS
OMP_GetNumLocalThreads()
6.2.10 OMP_GET_MAX_THREADS
Original:
SUBROUTINE OMP_GET_MAX_THREADS()
Prototyp:
const int OMP_GET_MAX_THREADS
OMP_GET_MAX_THREADS gibt die maximale Anzahl Threads zurück, die einen PARALLEL-Block
bearbeiten können. Dies ist eine Konstante.
Implementation:
#define OMP_GET_MAX_THREADS
(OMP_MAX_LOCAL_THREADS * OMP_MAX_GLOBAL_NODES)
6.2.11 OMP_GET_THREAD_NUM
Original:
SUBROUTINE OMP_GET_THREAD_NUM()
Prototyp:
int OMP_GET_THREAD_NUM
int OMP_GET_LOCAL_THREAD_NUM
OMP_GET_THREAD_NUM gibt die globale Nummer des aufrufenden Threads zurück. Der Wert liegt
zwischen 0 und OMP_GET_NUM_THREADS-1. 0 kennzeichnet den globalen Master-Thread.
Ausserhalb
des
Standards
bietet
der
Prototyp
zusätzlich
die
Funktion
OMP_GET_LOCAL_THREAD_NUM, die die lokale Nummer des aufrufenden Threads zurückgibt.
Dieser Wert liegt zwischen 0 (lokaler Master) und OMP_GET_NUM_LOCAL_THREADS-1.
Implementation:
#define OMP_GET_THREAD_NUM
OMP_GetThreadNum(_nThreadNum)
#define OMP_GET_LOCAL_THREAD_NUM
_nThreadNum
Seite 66
ETH Zürich
6.2.12 OMP_GET_xxx_NODES / OMP_GET_NODE_NUM
Original:
-
Prototyp:
int OMP_GET_MAX_NODES
int OMP_GET_NUM_NODES
int OMP_GET_NODE_NUM
Diese drei Funktionen sind nicht im OpenMP-Standard enthalten, sie können jedoch sehr nützlich
sein. Sie beschreiben, wieviele Knoten maximal auftreten können (OMP_GET_MAX_NODES),
wieviele Knoten aktuell vorhanden sind (OMP_GET_NUM_NODES), und welche Nummer der aktuelle
Knoten hat (OMP_GET_NODE_NUM). Die Numerierung der Knoten folgt der globalen
Threadnumerierung: Der Knoten, der Thread 0 enthält, ist Knoten 0. Der Knoten, der den Thread
enthält, der die nächst grössere Nummer hat als der letzte Thread des vorhergehenden Knotens,
erhält die nächst grössere Knotennummer.
Beispiel:
Zero-Copy-Layer
Node ID
Globale
Threadnummern
Logische
Knotennummer
0
1
2
3, 4, 5, 6
0, 1, 2
7, 8, 9
1
0
2
Tab. 6.2: Die logischen Knotennummern
Implementation:
#define OMP_GET_MAX_NODES
(OMP_MAX_GLOBAL_NODES)
#define OMP_GET_NUM_NODES
OMP_GetNumNodes()
#define OMP_GET_NODE_NUM
OMP_GetNodeNum()
6.2.13 OMP_LOCK / OMP_UNLOCK
Original:
-
Prototyp:
OMP_LOCK(pointer, size)
OMP_UNLOCK(pointer, size)
Mit OMP_LOCK können Speicherseiten für den exklusiven Zugriff durch den aufrufenden Thread
reserviert werden. Alle Seiten, die durch den Speicherbereich (pointer, size) belegt werden, sind
betroffen. Die Speicherseiten erhalten Read/Write-Zugriffsrechte. Von Threads auf entfernten
Knoten dürfen diese Seiten nicht mehr gelesen oder beschrieben werden. OMP_UNLOCK gibt die
gesperrten Seiten wieder frei.
Die Implementation des Lock-Mechanismus wurde so simpel wie möglich gelöst. Daher kann ein
korrekter Programmablauf nur gewährleistet werden, wenn OMP_LOCK unmittelbar nach,
OMP_UNLOCK unmittelbar vor einer Barrier plaziert sind.
Beispiel:
OMP_BARRIER
OMP_LOCK(a, 4096);
...
OMP_UNLOCK(a, 4096);
OMP_BARRIER
Beide Funktionen sind in dieser Form nicht im OpenMP-Standard enthalten.
Seite 67
ETH Zürich
Implementation:
#define OMP_LOCK(px, l)
OMP_Lock((char*)px, l)
#define OMP_UNLOCK(px, l)
OMP_Unlock((char*)px, l)
6.3 Im Prototypen nicht enthaltene Funktionalität
Der OpenMP-Prototyp beinhaltet längst nicht alle Funktionalität, die der Standard anbieten würde.
Einzelne Direktiven wurden, wie bereits erwähnt, nur unvollständig implementiert, andere
vollständig weggelassen. Die folgende Liste beschreibt, welche Direktiven gänzlich nicht
implementiert wurden:

SINGLE: Diese Direktive beschränkt die Ausführung von Code auf den Thread, der als erstes
bei der Direktive angelangt ist. Die Implementation würde zusätzliche Kommunikation und
Synchronisation erfordern.

CRITICAL implementiert eine Critical-Section. Auch hier wäre zusätzliche Kommunikation und
Synchronisation nötig.

ATOMIC: Erlaubt atomares Lesen und Schreiben einer Variable, entspricht also im
wesentlichen einer minimalen Critical-Section.

FLUSH: Flush wurde nicht implementiert, da es sich um eine sehr fortranspezifische Direktive
handelt.

ORDERED: Garantiert die sequentielle Ausführung von Code in einer DO-Schleife. Entspricht im
wesentlichen einer Critical-Section mit zusätzlicher Spezifikation, was die Reihenfolge der
eintretenden Threads betrifft.

THREADPRIVATE: Fortranspezifische Version von PRIVATE.
Neben diesen Direktiven wurden folgende Funktionen weggelassen:

OMP_SET_NUM_THREADS: Die Anzahl Threads ist im Prototypen statisch.

OMP_GET_NUM_PROCS: Für den Prototypen unwichtig.

OMP_GET_DYNAMIC / OMP_SET_DYNAMIC: Die Anzahl der Threads ist statisch.

OMP_GET_NESTED / OMP_SET_NESTED: Die Anzahl der Threads ist statisch. Verschachtelte
PARALLEL-Bereiche sind nicht erlaubt.
Zudem definiert der OpenMP-Standard eine Reihe von Lock-Routinen, die einen exklusiven Zugriff
implementieren. Diese Funktionen wurden im Prototypen nicht aufgenommen. Lokal können solche
Locks mit Win32 Mutex implementiert werden. Für global exklusiven Zugriff ist zusätzliche
Kommunikation nötig.
6.4 Mögliche Erweiterungen und Verbesserungen
Grundsätzlich könnten die in den beiden vorherigen Unterkapiteln erwähnten, noch nicht
implementierten OpenMP-Direktiven und -Funktionen hinzugefügt werden. Zusätzlich beschreibt
die folgende Liste kurz mögliche Veränderungen am bestehenden Prototypen, die zu
Verbesserungen oder Erweiterungen führen könnten. Bei diesen Vorschlägen handelt es sich zum
Teil nur um Ideen, die jedoch weiterer Abklärungen bedürfen, um konkrete Aussagen über den
Nutzen machen zu können.

Zusätzliche Synchronisation: Jeder Thread (nicht Knoten, wie bei der globalen Barrier) schickt
eine Meldung dem Master-Knoten, wenn er an einen Synchronisationspunkt angelangt ist. Der
Kommunikations-Thread des Masters wäre dafür verantwortlich, diese Meldungen
entgegenzunehmen und den einzelnen Threads mit einer weiteren Meldung mitzuteilen, wann
sie den Synchronisationspunkt verlassen dürfen. Durch eine Variation der Reihenfolge, in
welcher die Threads weiterarbeiten dürfen, könnten Direktiven wie SINGLE, CRITICAL und
ORDERED implementiert werden.
Seite 68
ETH Zürich

Es wäre abzuklären, in wie fern sich ein Multi-Writer-Verfahren, wie es in TreadMarks
verwirklicht ist, auf Kosten von Zero-Copy doch lohnen könnte. Die einzelnen Knoten sind
grundsätzlich fähig, bei einer Barrier zu erkennen, wie viele Knoten eine Seite verändert
haben. So könnte dynamisch Zero-Copy eingesetzt werden, wenn nur ein Knoten die Seite
verändert hat und ein Multi-Writer-Verfahren anderenfalls.

Das Win32-API bietet mit der Funktion VirtualLock die Möglichkeit, eine beschränkte
Anzahl von Speicherseiten zu locken, also vor dem Auslagern ins Page-File zu schützen. Ein
gezielter Einsatz dieser Funktion (zum Beispiel auf Seiten im aktuellen Scope, oder auf
modifizierte Seiten) könnte unter Umständen die Performance erhöhen. Eventuell muss mit
SetProcessWorkingSetSize die Grösse des Working-Sets verändert werden.

Im Prototypen wird bei einem Page-Fault (auf Grund des Invalid-Zustandes) nur immer die
entsprechende Seite von einem entfernten Rechner geholt. Falls die Seiten unmittelbar vor
bzw. nach der kommunizierten Seite ebenfalls den Zustand Invalid haben und die
entsprechenden, gültigen Seiten beim gleichen, entfernten Rechner liegen, dann könnten
diese Seiten miteinander übertragen werden (Pre-Fetching). So könnten die Pakete
vergrössert und die Anzahl der Übertragungen verkleinert werden, mit dem kleinen Nachteil,
dass eventuell mehr Seiten kommuniziert werden als wirklich benötigt.

Das Versenden der Modified-List ist nicht optimal gelöst: Da der Zero-Copy-Layer nichtblockierendes Senden unterstützt, wird pro Empfängerknoten ein Async-Request alloziert und
die Modified-List hineinkopiert. Wenn die Modified-List von Anfang an im Body eines AsyncRequest gehalten würde und dem Request eine Liste von Empfängern mitgegeben werden
könnte, könnte diese „Kopiererei“ vermieden werden. Erst wenn das Senden an alle
Empfänger abgeschlossen ist, würde der Request mit der Modified-List wieder freigegeben.

Im aktuellen Prototypen tauschen die Threads nur die Nummern der Seiten aus, die sie seit der
letzten Barrier modifiziert haben. Es könnte unter Umständen interessant sein, auch die
Nummern der Seiten zu kommunizieren, die ein Knoten seit der letzten Barrier von einem
anderen angefordert hat. Wenn mehrere Knoten eine gültige Version einer Seite haben, dann
macht es durchaus Sinn, dass andere Knoten die Last verteilen, indem sie eine gültige Seite
nicht zwingend beim ursprünglichen Knoten abholen, sondern eventuell bei einem anderen.
6.5 Die Anwendung des OpenMP-Prototypen
Der OpenMP-Prototyp ist in den Source-Dateien OPENMP.H, OMPLIB.H und OMPLIB.C
implementiert. Das Microsoft Visual C++ 5.0 Projekt OMPLIB.DSP enthält alle notwendigen
Einstellungen für Kompilation und Linken.
Ein OpenMP-Programm muss ein #Include <OpenMP.H> enthalten und mit OMPLIB.LIB gelinkt
werden. Um lauffähig zu sein, müssen sowohl die Funktionsbibliothek des Zero-Copy-Layers
(ZEROCOPY.DLL) wie des OpenMP-Prototypen (OMPLIB.DLL) auf allen Systemen verfügbar sein.
Zudem muss die oben bereits erklärte ZEROCOPY.CFG vorhanden sein.
Für die Konfiguration der OpenMP-Prototypen muss der OpenMP-Applikation der Name einer
weiteren Konfigurationsdatei mitgegeben werden:
z.B.: TestOmp.Exe TestOmp.Cfg
Diese Konfigurationsdatei enthält für jeden zu verwendenden Knoten eine Sektion von folgendem
Format:
[Node<ID>]
FirstThread = <Num1>
LastThread = <Num2>
Im Knoten mit der ID <ID> werden so viele OpenMP-Threads gestartet, wie Nummern zwischen
der <Num1> und <Num2> (Randnummern inklusive) liegen. Alle Sektionen zusammen müssen
lückenlos alle Nummern zwischen 0 und dem grössten <Num2> abdecken, ohne dass eine
Nummer doppelt vergeben wird.
Seite 69
ETH Zürich
Beispiel:
[Node2]
FirstThread = 0
LastThread = 3
[Node0]
FirstThread = 4
LastThread = 6
[Node3]
FirstThread = 7
LastThread = 8
Seite 70
ETH Zürich
7 Der MPI-Prototyp
Vom Konzept her bereits wesentlich einfacher als OpenMP ist das Message-Passing-Interface
(MPI). Dementsprechend ist auch die Implementation eines Prototypen wesentlich einfacher.
Zudem wurde die Anzahl der implementierten Funktionen auf die wichtigsten beschränkt. Konkret
wurden eigentlich nur Senden und Empfangen plus eine Barrier implementiert. Basierend auf
diesen Funktionen lässt sich ein grosser Teil der von MPI definierten Kommunikationsfunktionen
(Scatter, Gather u.s.w.) nachbilden.
7.1 Die Konzepte des MPI-Prototypen
Dieser kleine Funktionsumfang beinhaltet jedoch ein paar Probleme, die durchdacht und gelöst
werden müssen.
7.1.1 Threading
Standardgemäss würden MPI-Applikationen durch einen MpiRun-Prozess auf dem lokalen wie
auch auf entfernten Systemen gestartet. Dieser praktische aber aufwendige Mechanismus hätte
einen NT-Service zur Folge. Diese Technik wurde nicht in den Prototypen aufgenommen. Statt
dessen muss auf jedem Knoten eine MPI-Applikation von Hand gestartet werden. Der Hauptthread
muss nun dem lokalen System alle in der Applikation enthaltenen MPI-Routinen mitteilen und dann
die Funktion MPI_Run aufrufen:
int Routine1()
{
MPI_Init();
...
MPI_Finalize();
return 0;
}
int Routine2()
{
MPI_Init();
...
MPI_Finalize();
return 0;
}
int main( int argc, char *argv[ ], char *envp[ ] )
{
MPI_Register_routine("Routine1", Routine1);
MPI_Register_routine("Routine2", Routine2);
MPI_Run(argc, argv);
return 0;
}
MPI_Run liest dann eine der Applikation mitgegebene Konfigurationsdatei und startet gemäss den
darin enthaltenen Angaben einen oder mehrere MPI-Threads, die jeweils eine der registrierten
Routinen abarbeiten. Der Hauptthread selber wird zum sogenannten Kommunikationsthread,
welcher auf dem Zero-Copy-Layer aufbaut und für die Kommunikation zwischen den Knoten
verantwortlich ist.
Es wurde auch versucht, eine MPI-Implementation ohne Kommunikationsthread zu erreichen. Dies
wäre grundsätzlich möglich. Wird der vorliegende Zero-Copy-Layer verwendet, ergeben sich
jedoch Probleme:

Da die Socket- und Pipe-Netzwerk-Layer mit APCs arbeiten, wird das Empfangen immer im
Kontext des Threads durchgeführt, der ReadFileEx aufgerufen hat. Konkret heisst das, dass
immer der selbe Thread für das Empfangen verantwortlich ist. Ist dieser Thread längere Zeit
mit lokalen Berechnungen beschäftigt, dann ist kein Empfangen möglich, auch für die anderen
Threads nicht.

Bei der GM-Implementation ist es wichtig, dass jederzeit Empfangspuffer zur Verfügung
stehen. Sind alle Threads mit lokalen Berechnungen beschäftigt, dann kann es sein, dass
diese Puffer ausgehen.
Seite 71
ETH Zürich
Was GM betrifft, bleibt nur die Lösung eines zusätzlichen Threads. Werden Sockets oder Pipes
eingesetzt, so müsste der Zero-Copy-Layer so umgeschrieben werden, dass er nicht Knoten-zuKnoten-Kommunikation unterstützt, sondern Thread-zu-Thread. Das würde heissen, dass von
jedem Thread zu jedem nicht-lokalen Thread eine Verbindung bestehen müsste. So könnten die
ReadFileEx jeweils im Kontext des empfangenden Threads aufgerufen werden.
Zero-Copy-Layer
MPI
Thread 5
MPI
Thread 4
MPI
Thread 3
MPI
Thread 2
Knoten 1
MPI
Thread 1
MPI
Thread 0
Knoten 0
Zero-Copy-Layer
Abb. 7.1: Das Threadmodell des MPI-Prototypen
7.1.2 Kommunikation
Das grösste Problem, die Kommunikation nämlich, wurde bereits gelöst. Wie bereits erwähnt
basiert der MPI-Prototyp auf dem Zero-Copy-Layer. Sämtliche Kommunikation zwischen den
Knoten (nicht zwischen den Threads!) wird über diesen Layer abgewickelt.
Dabei muss ein Problem erwähnt werden, das nicht befriedigend gelöst werden konnte: Das
Problem liegt in der Tatsache, dass der Zero-Copy-Layer zwei Arten der Kommunikation (synchron
und asynchron) anbietet. Für kleine Meldungen eignet sich die asynchrone Art besser, für grosse
Meldungen die synchrone. So wurde der Prototyp auch implementiert. Eine Empfängerapplikation
muss jedoch nicht in jedem Fall wissen, wie gross die Meldung ist, die ihr eine entfernte Applikation
schickt. Sie wird deshalb einen genügend grossen Empfangspuffer zur Verfügung stellen. Ist dieser
grösser als die kritische Grösse für asynchrone Kommunikation, so wird eine synchrone
Übertragung erwartet. Wenn der Sender jedoch nur eine kleine Meldung verschicken will, so wird
diese asynchron verschickt. Die Empfängerapplikation wird das Paket zwar erhalten, doch der
synchrone Recv-Request bleibt hängig und würde bei der nächsten grossen Meldung
fälschlicherweise verwendet und der zugehörige Puffer überschrieben werden. Dieses Problem
lässt sich auf Grund von Latenzzeiten und (im Falle von Myrinet) Fullduplex-Kommunikation nicht
befriedigend lösen. Jede Form von Cancel-Requests oder anderen Lösungsversuchen, der
entfernten Applikation mitzuteilen, dass die erhaltene Empfangsbereitschaft nicht mehr gültig ist,
kann zu spät kommen und bleibt wirkungslos.
Um diesem Problem wenigstens etwas entgegenzutreten und dem Benutzer des MPI-Prototypen
die Möglichkeit zu geben, Meldungen zu empfangen, von derer Grösse nur eine obere Schranke
bekannt ist, kann bei MPI_Send, MPI_Isend, MPI_Recv und MPI_Irecv eine negative
Puffergrösse angegeben werden und so eine synchrone Kommunikation (unabhängig von der
Grösse) erzwungen werden. Es versteht sich, dass diese Massnahme nicht dem MPI-Standard
entspricht.
Wie bereits erwähnt, wird der Zero-Copy-Layer nur dann verwendet, wenn zwischen zwei Knoten
kommuniziert werden muss. Für lokale Kommunikation zwischen den Threads wäre diese Art viel
zu umständlich und in keiner Hinsicht leistungsfähig. Deshalb wurde für die lokale Kommunikation
nicht nur der Zero-Copy-Layer umgangen, sondern auch gleich der Kommunikationsthread. Der
Seite 72
ETH Zürich
Sender prüft zuerst die Bereitschaft des Empfängers. Ist dieser bereit, dann wird der Sendepuffer
in den Empfangspuffer kopiert. Ist er nicht bereit, dann wird ihm lediglich die Sendebereitschaft
mitgeteilt. Umgekehrt prüft der Empfänger zuerst die Bereitschaft des Senders. Ist dieser bereits
bereit, dann wird die Meldung kopiert, ansonsten dem Sender die Empfangsbereitschaft mitgeteilt.
Auch bei der lokalen Kommunikation wäre es schön, es könnte das Kopieren umgangen werden,
bzw. es müsste nur bei Bedarf kopiert werden – Copy-On-Write sozusagen. Zwar liesse sich unter
Windows NT mittels Shared-Memory (vgl. Win32 CreateFileMapping, OpenFileMapping und
MapViewOfFileEx) ein solches System theoretisch realisieren, jedoch nur mit grossen
Einschränkungen oder Änderungen gegenüber dem MPI-Standard. Doch wenn lokal schon mit
Shared-Memory gearbeitet werden soll, dann macht es wenig Sinn, dies in ein Message-PassingModell zu zwängen. Da die lokalen Threads innerhalb des selben Prozesses existieren, ist SharedMemory implizit vorhanden. Wieso dies also nicht in seiner natürlichsten und schnellsten Form
benutzen? Statt ganze Speicherbereiche via MPI zu kommunizieren, könnte für die lokale
Kommunikation auch nur der Pointer des Speicherbereichs gesendet und empfangen werden:
char* pBuffer = malloc(10000);
MPI_Send(&pBuffer, 1, MPI_INT, ...);
char* pBuffer;
MPI_Recv(&pBuffer, 1, MPI_INT, ...);
Dies erfordert vom MPI-Programmierer zwar, dass er sich der Lokalität der einzelnen Threads
bewusst ist, dafür wird er mit der einer leistungsfähigen, lokalen Kommunikation belohnt.
Im vorliegenden MPI-Prototypen gibt es nur ein Synchronisationselement, die Barrier. Alle lokalen
Threads, die an der Barrier angelangt sind, werden schlafen gelegt. Sobald der letzte, lokale
Thread die Barrier erreicht hat, schickt der Kommunikationsthread dem Master-Knoten (er enthält
den Thread mit dem Rank 0) eine Meldung, die das erreichen der Barrier signalisiert. Hat der
Master-Knoten von allen anderen Knoten diese Meldung bekommen, dann schickt er allen eine
Bestätigung. Sobald ein Knoten diese Bestätigung erhält, weckt er alle Threads wieder auf.
Dank dem lokalen Sammeln der Threads muss nicht jeder Thread das erreichen der Barrier
signalisieren, sondern nur jeder Knoten. So kann unter Umständen einiges an Kommunikation
gespart werden.
7.2 Das API des MPI-Prototypen
Das API des MPI-Prototypen ist einerseits durch den Funktionsumfang beschränkt, andererseits
weisen auch die implementierten Funktionen Einschränkungen auf. Dieses Unterkapitel beschreibt,
welche Teile implementiert sind, und welche Unterschiede zum Standard [6] existieren.
Applikationsbeispiel:
int SendRoutine()
{
MPI_Init();
MPI_Send(“This is a message.”, 18, MPI_CHAR, 1, 34, MPI_COMM_WORLD);
MPI_Finalize();
return 0;
}
int RecvRoutine()
{
MPI_Status status;
char buf[1000];
MPI_Init();
MPI_Recv(buf, 1000, MPI_CHAR, 0, 34, MPI_COMM_WORLD, &status);
printf(buf);
MPI_Finalize();
return 0;
}
Seite 73
ETH Zürich
int main( int argc, char *argv[ ], char *envp[ ] )
{
MPI_Register_routine("Send", SendRoutine);
MPI_Register_routine("Recv", RecvRoutine);
MPI_Run(argc, argv);
return 0;
}
Die Datei MPI.H enthält alle notwendigen Definitionen. Unter anderem auch die folgende Struktur,
die den Status eines MPI_Recv dokumentiert:
struct MPI_Status
{
int MPI_SOURCE;
int MPI_TAG;
int MPI_ERROR;
int MPI_LEN;
Rank des Absenders
Tag der Meldung
MPI_SUCCESS oder einen Fehlercode
Länge der empfangenen Meldung
}
MPI definiert eine ganze Reihe von Fehlercodes. Da der Prototyp keine Prüfung der Argumente
vornimmt, sondern von einer korrekten MPI-Applikation ausgeht, werden nur wenige der
Fehlercodes verwendet:
MPI_SUCCESS
MPI_ERR_PENDING
MPI_ERR_INTERN
Kein Fehler aufgetreten
Bearbeitung des Requests ist noch nicht abgeschlossen
Ein interner Fehler ist aufgetreten.
Beim Versenden von Meldungen geht MPI nicht zwingend von Characters oder Bytes aus. Die
Länge einer Meldung hängt vom Datentyp und der Anzahl Elemente ab. Folgende Datentypen sind
definiert:
MPI_CHAR
MPI_UNSIGNED_CHAR
MPI_BYTE
MPI_SHORT
MPI_UNSIGNED_SHORT
MPI_INT
MPI_UNSIGNED
MPI_LONG
MPI_UNSIGNED_LONG
MPI_FLOAT
MPI_DOUBLE
MPI_LONG_DOUBLE
MPI_LONG_LONG_INT
1 Byte
1 Byte
1 Byte
2 Bytes
2 Bytes
4 Bytes
4 Bytes
4 Bytes
4 Bytes
4 Bytes
8 Bytes
16 Bytes
8 Bytes
Letzte wichtige Definition ist die Obergrenze der verwendbaren Tags. Es sind grundsätzlich Tags
zwischen 0 und MPI_TAG_UB erlaubt. Im Prototypen ist die Obergrenze 0x7FFFFFFD.
Folgende MPI-Funktionen sind implementiert:
7.2.1 MPI_Register_routine
Original:
-
Prototyp:
int MPI_Register_routine(CHAR* pcName,
PMPI_ROUTINE pMpiRoutine)
Diese Funktion ist nicht im MPI-Standard enthalten. Sie verbindet eine MPI-Routine mit einem
Namen. Auf Grund dieses Namen werden Routinen identifiziert und gestartet (siehe Kapitel 7.1.1).
Diese MPI-Routinen müssen folgende Signatur aufweisen:
int MpiRoutine()
Der Name ist natürlich beliebig. Die Routine kann einen beliebigen Wert zurückgeben.
Seite 74
ETH Zürich
7.2.2 MPI_Run
Original:
-
Prototyp:
int MPI_Run(int argc, char *argv[])
Diese Funktion ist nicht im MPI-Standard enthalten. Sie ersetzt die MpiRun-Applikation, die die
einzelnen MPI-Applikationen starten soll. Der Funktion wird die Anzahl der Argumente und ein
Pointer auf die Argumente übergeben. Im Prinzip werden einfach die beiden ersten Argumente der
main-Funktion weitergereicht.
MPI_Run startet alle notwendigen MPI-Threads und übernimmt selbst die Aufgabe des
Kommunikationsthreads.
7.2.3 MPI_Init
Original:
int MPI_Init(int *argc, char ***argv)
Prototyp:
int MPI_Init()
MPI_Init initialisiert die nötigen MPI-Strukturen eines MPI-Threads. Diese Funktion muss als
erste MPI-Funktion aufgerufen werden. Im Prototypen enthält diese Funktion lediglich eine Barrier,
um den Start der Routinen zu synchronisieren.
7.2.4 MPI_Finalize
Original:
int MPI_Finalize(void)
Prototyp:
int MPI_Finalize(void)
Diese Funktion baut alle aufgebauten Datenstrukturen wieder ab. Sie ist die letzte MPI-Funktion,
die aufgerufen werden darf. Konkret enthält sie nur eine Barrier.
7.2.5 MPI_Send
Original:
int MPI_Send(void* buf, int count, MPI_Datatype datatype,
int dest, int tag, MPI_Comm comm);
Prototyp:
int MPI_Send(void* buf, int count, MPI_Datatype datatype,
int dest, int tag, MPI_Comm comm);
Blockierendes Senden wird durch MPI_Send implementiert. Gesendet werden count *
datatype Bytes des Puffers, auf den buf zeigt. dest ist der Rank des Empfängers, tag das Tag.
Der Wert von comm wird ignoriert.
Wenn count * datatype <= MPI_SMALL_PACKET_SIZE ist, wird die Meldung asynchron
versendet, ansonsten synchron. Wenn count einen negativen Wert hat, dann wird der absolute
Wert davon verwendet und synchrones Senden erzwungen.
Seite 75
ETH Zürich
7.2.6 MPI_Isend
Original:
int MPI_Isend(void* buf, int count, MPI_Datatype datatype,
int dest, int tag, MPI_Comm comm,
MPI_Request* request);
Prototyp:
int MPI_Isend(void* buf, int count, MPI_Datatype datatype,
int dest, int tag, MPI_Comm comm,
Nicht-blockierendes Senden wird durch MPI_Isend erreicht. Gesendet werden count *
datatype Bytes des Puffers, auf den buf zeigt. dest ist der Rank des Empfängers, tag das Tag.
Der Wert von comm wird ignoriert. request ist ein Pointer auf eine MPI_Request Datenstruktur.
Sie wird gebraucht, um anschliessend mit einer Test- oder Wait-Funktion den Status des Sendens
zu prüfen.
versendet, ansonsten synchron. Wenn count einen negativen Wert hat, dann wird der absolute
Wert davon verwendet und synchrones Senden erzwungen.
7.2.7 MPI_Recv
Original:
int MPI_Recv(void* buf, int count, MPI_Datatype datatype,
int source, int tag, MPI_Comm comm,
MPI_Status* status);
Prototyp:
int MPI_Recv(void* buf, int count, MPI_Datatype datatype,
Blockierendes Empfangen wird durch MPI_Recv implementiert. Empfangen werden maximal
count * datatype Bytes in den Puffer, auf den buf zeigt. source ist der Rank des Senders,
tag das Tag. Es sind keine Wildcards wie MPI_ANY_RANK oder MPI_ANY_TAG erlaubt. Der Wert
von comm wird ignoriert. status enthält Statusinformationen wie Absender, Tag, Fehlercode und
Länge der empfangenen Meldung.
empfangen, ansonsten synchron. Wenn count einen negativen Wert hat, dann wird der absolute
Wert davon verwendet und synchrones Empfangen erzwungen.
7.2.8 MPI_Irecv
Original:
int MPI_Irecv(void* buf, int count, MPI_Datatype datatype,
Prototyp:
int MPI_Irecv(void* buf, int count, MPI_Datatype datatype,
int source, int tag, MPI_Comm comm
Nicht-blockierendes Empfangen wird durch MPI_Irecv erreicht. Empfangen werden maximal
count * datatype Bytes in den Puffer, auf den buf zeigt. source ist der Rank des Senders,
tag das Tag. Es sind keine Wildcards wie MPI_ANY_RANK oder MPI_ANY_TAG erlaubt. Der Wert
von comm wird ignoriert. status enthält Statusinformationen wie Absender, Tag, Fehlercode und
Länge der empfangenen Meldung. request ist ein Pointer auf eine MPI_Request Datenstruktur.
Sie wird gebraucht, um anschliessend mit einer Test- oder Wait-Funktion den Status des
Empfangens zu prüfen.
empfangen, ansonsten synchron. Wenn count einen negativen Wert hat, dann wird der absolute
Wert davon verwendet und synchrones Empfangen erzwungen.
Seite 76
ETH Zürich
7.2.9 MPI_Test
Original:
int MPI_Test(MPI_Request* request, int* flag,
Prototyp:
int MPI_Test(MPI_Request* request, int* flag,
Wird nicht-blockierend kommuniziert, dann kann mit dieser Testfunktion der Status eines Requests
überprüft werden. request ist eine zuvor an MPI_Isend oder MPI_Irecv übergebene RequestDatenstruktur. Ist nach dem Aufruf dieser Funktion das flag gleich TRUE, dann ist der Request
beendet und status enthält den Status des Requests. Ansonsten ist er noch im Gange.
7.2.10 MPI_Testall
Original:
int MPI_Testall(int count, MPI_Request* array_of_request,
int* flag, MPI_Status* array_of_status);
Prototyp:
int MPI_Testall(int count, MPI_Request* array_of_request,
int* flag, MPI_Status* array_of_status);
Wird nicht-blockierend kommuniziert, dann kann mit dieser Testfunktion der Status mehrerer
Requests überprüft werden. array_of_request sind count zuvor an MPI_Isend oder
MPI_Irecv übergebene Request-Datenstrukturen. Ist nach dem Aufruf dieser Funktion das flag
gleich TRUE, dann sind alle Requests beendet und array_of_status enthält die Stati der
Requests. Ist flag gleich FALSE, dann ist mindestens ein Request noch im Gange.
7.2.11 MPI_Wait
Original:
int MPI_Wait(MPI_Request* request, MPI_Status* status);
Prototyp:
int MPI_Wait(MPI_Request* request, MPI_Status* status);
Diese Funktion entspricht MPI_Test. Sie legt den laufenden Thread jedoch solange schlafen, bis
der angegebene Request beendet wurde.
7.2.12 MPI_Waitall
Original:
int MPI_Waitall(int count, MPI_Request* array_of_request,
MPI_Status* array_of_status);
Prototyp:
int MPI_Waitall(int count, MPI_Request* array_of_request,
MPI_Status* array_of_status);
Diese Funktion entspricht MPI_Testall. Sie legt den laufenden Thread jedoch solange schlafen,
bis alle angegebenen Requests beendet wurden.
7.2.13 MPI_Get_count
Original:
int MPI_Get_count(MPI_Status* status,
MPI_Datatype datatype, int* count);
Prototyp:
int MPI_Get_count(MPI_Status* status,
MPI_Datatype datatype, int* count);
Wurde eine Meldung erfolgreich empfangen, dann kann mit MPI_Get_count die Anzahl Elemente
eines Datentyps ermittelt werden, die die Meldung enthält. status ist dabei der Status von
MPI_Recv oder einer Test- oder Wait-Funktion.
Seite 77
ETH Zürich
7.2.14 MPI_Barrier
Original:
int MPI_Barrier(MPI_Comm comm);
Prototyp:
int MPI_Barrier(MPI_Comm comm);
MPI_Barrier implementiert ein Synchronisationspunkt. Alle Threads werden solange schlafen
gelegt, bis alle Threads diesen Punkt erreicht haben. comm wird ignoriert.
7.2.15 MPI_Comm_size
Original:
int MPI_Comm_size(MPI_Comm comm, int* size);
Prototyp:
int MPI_Comm_size(MPI_Comm comm, int* size);
Gibt die Anzahl global arbeitender MPI-Threads zurück. comm wird ignoriert.
7.2.16 MPI_Comm_rank
Original:
int MPI_Comm_rank(MPI_Comm comm, int* rank);
Prototyp:
int MPI_Comm_rank(MPI_Comm comm, int* rank);
Gibt den Rank des aufrufenden Threads zurück. comm wird ignoriert.
7.3 Die Anwendung des MPI-Prototypen
Nachdem nun ausführlich auf Theorie und Schnittstelle eingegangen wurde, zeigt dieses
Unterkapitel die konkrete Anwendung des MPI-Prototypen auf.
Eine MPI-Applikation, die den Prototypen verwenden will, muss ein #include „Mpi.H“ enthalten
und mit der Datei MPILIB.LIB gelinkt werden. Alle Applikationen müssen Zugriff auf MPILIB.DLL,
ZEROCOPY.DLL und ZEROCOPY.CFG haben.
Jeder Applikation muss als Argument der Name einer Konfigurationsdatei mitgegeben werden.
Diese Datei enthält Angaben, auf welchem Knoten welche Threads laufen, und welche Routinen
diese abarbeiten. Für jeden Rank gibt es eine Sektion von folgendem Format:
[Rank<Num>]
NodeID = <ID>
Routine = <RoutineName>
<Num> ist eine Zahl von 0 an aufsteigend. Es werden so viele Sektionen gelesen, bis eine nicht
mehr gefunden wird. <ID> sagt auf welchem Knoten dieser Rank laufen soll. <RoutineName>
entspricht dem Namen einer Routine, die mit MPI_Register_routine im System registriert
wurde.
Beispiel:
[Rank0]
NodeID = 3
Routine = Producer
[Rank1]
NodeID = 0
Routine = Consumer2
[Rank2]
NodeID = 1
Routine = Consumer1
Seite 78
ETH Zürich
8 Performancemessungen
In den vorangegangenen Kapiteln sind nun zwei Prototypen besprochen worden, die beide auf
dem sogenannten Zero-Copy-Layer aufbauen. Theorie, Technologie und Implementation wurden
ausführlich dokumentiert. Dieses Kapitel bespricht nun den praktischen Einsatz, indem
verschiedene Messungen durchgeführt werden, die die Performance der Layer und Prototypen
aufzeigen soll.
8.1 Bandbreitenmessungen über Sockets
Von allem Anfang dieser Arbeit an waren Hochgeschwindigkeits-Netzwerke wie Myrinet oder
GigaBit-Ethernet als Basistechnologie ins Auge gefasst worden. Hohe Bandbreiten und kleine
Latenzzeiten zeichnen solche Netzwerke aus. Verschiedene Bandbreitenmessungen sollen nun
aufzeigen, wieviel der durch diese Netzwerke zur Verfügung gestellten Performance durch die
Layer und Prototypen ausgenutzt werden kann.
8.1.1 Die Windows Sockets als Basis
Da zum Zeitpunkt der Messungen weder das GM-API für Myrinet noch ein Zero-Copy-Protokoll für
das GigaBit-Ethernet verfügbar waren, mussten als Ausgangspunkt der Messungen wohl oder übel
die Windows Sockets hinhalten. Diese sind natürlich alles andere als Zero-Copy. Doch geht man
von der Performance der Sockets aus, so können doch erste Aussagen über die Leistungsfähigkeit
der Layer bzw. der Prototypen gemacht werden.
Als Testplattform standen zwei Dell Optiplex GX1 (Pentium II, 350 MHz, 64 MB RAM) zur
Verfügung. Verbunden waren diese über ein 100 mbit Ethernet (NIC: DEC DE500, Switch: Bay
Networks Bay Stock 100 Base-T Hub), sowie über ein direkt verkabeltes (ohne Switch) GigaBitEthernet (Packet Engine G-NIC II).
Je zwei Messreihen über jedes Netzwerk soll die Performance der Sockets, und damit die
Ausgangslage für alle anderen Testresultate, liefern:

Die erste Messung verwendet blockierende Sockets. Zwischen den beiden Rechnern wird eine
TCP-Verbindung (Stream-Sockets) aufgebaut. Danach wird auf einem Rechner mit send
gesendet, auf dem anderen mit recv empfangen.

Die zweite Messung verwendet nicht-blockierende Sockets. Es werden ebenfalls TCPVerbindungen verwendet. Für das Senden und Empfangen werden jedoch die Funktionen
WriteFileEx und ReadFileEx verwendet, wie sie auch im Socket-Netzwerk-Layer
eingesetzt werden. Es werden maximal 100 Pakete bzw. eine maximale Summe der
Paketgrössen von 3 MB beim Start des Tests sofort an die Sockets zum Versenden gegeben.
Danach wird erst wieder gesendet, wenn die Sockets das erfolgreiche Versenden eines
Paketes gemeldet haben.
i
Getestet werden Paketgrössen zwischen 4 Bytes und 2 MB, wobei Paketgrossen von 2 und
i
sqrt(2)*2 Bytes verwendet werden. Alle Messungen werden 3 mal durchgeführt, um eventuelle
Schwankungen zu erkennen. Die genauen Resultate befinden sich im Anhang A in den Tabellen
A.1 bis A.4.
Die Einstellungen der Sockets werden gegenüber den Standardwerten leicht verändert. Die Sendeund Empfangspuffer werden auf je 64 kB erhöht. Zudem wird die Option TCP_NODELAY
eingeschaltet, die verhindert, dass kleine Pakete verzögert verschickt werden. Zudem werden die
Keep-Alive-Meldungen unterdrückt.
Die Resultate der Messreihen, wie sie in Abbildung 8.1 und 8.2 dargestellt sind, zeigen deutlich,
dass Kommunikationsformen, die während dem Kommunikationsvorgang die Daten ein oder gar
mehrmals Kopieren, auf leistungsfähigen Netzwerken nicht mehr genügen, um diese auszulasten.
Immerhin vermögen die Sockets das 100 mbit Ethernet maximal zu 70% auszulasten
(Protokolloverhead nicht berücksichtigt). Ganz anders sieht das Resultat beim GigaBit-Ethernet
aus: Lediglich 11% der Leistung konnten genutzt werden. Das ist zwar viel zu wenig, ist jedoch
nicht verwunderlich, da auch die lokale Kommunikation nicht sehr gut abschneidet (max. 25 % der
Kopierbandbreite). Myrinet kann immerhin etwa 30% der GM-Performance ausnutzen.
Seite 79
ETH Zürich
Bandbreiten mit Windows Sockets (blockierend)
100’000’000
Datendurchsatz [Bytes/s]
10’000’000
1’000’000
100’000
10’000
1
10
100
1’000
10’000
100’000
1’000’000
10’000’000
Paketgrösse [Bytes]
100 mbit Ethernet
GigaBit Ethernet
lokal
Myrinet
Abb. 8.1: Resultate der Bandbreitenmessungen mit blockierenden Windows-Sockets
Bandbreiten mit Windows Sockets (nicht-blockierend)
100’000’000
10’000’000
1’000’000
100’000
10’000
1
10
100
1’000
10’000
100’000
1’000’000
10’000’000
100 mbit Ethernet
GigaBit Ethernet
lokal
Myrinet
Abb. 8.2: Resultate der Bandbreitenmessungen mit nicht-blockierenden Windows-Sockets
Während die Kurven der Messungen mit blockierenden Sockets einen sehr typischen Verlauf
darstellen, zeigen nicht-blockierenden Sockets einige Schwankungen. Auffallend ist der
Performanceverlust bei Paketgrössen über 64 kB. Es scheint, dass das Versenden von Paketen,
die grösser als die Sende- bzw. Empfangspuffer sind, mit zusätzlichem Aufwand behaftet sind (ev.
zusätzliches Kopieren).
Eine zweite, auffällige Irregularität ist beim nicht-blockierenden Versenden über GigaBit-Ethernet
bei Paketgrössen um 724 Bytes zu erkennen. Zufällig kann dieses „Loch“ nicht entstanden sein, da
die Kurve stetig aus dem Loch heraussteigt. Doch zu erklären ist dies ohne genaue Kenntnis der
Treiber und deren Zusammenarbeit mit dem restlichen System, insbesondere mit NDIS, nur sehr
schwer.
Seite 80
ETH Zürich
Entgegen der Erwartungen entpuppten sich die nicht-blockierenden Sockets (oder die
Implementation der Win32-Funktionen WriteFileEx und ReadFileEx) nicht als vorteilhaft. Über
weite Bereiche hinweg liegt der Datendurchsatz deutlich unter den blockierenden Varianten.
Trotzdem wurden diese Funktionen in den Socket-Netzwerk-Layer eingebaut, mit dem Vorteil, nicht
pollen zu müssen.
Die Beurteilung der Leistung der Windows Sockets steht hier jedoch nicht im Vordergrund.
Vielmehr sollen die darauf aufbauenden Schichten betrachtet werden. Als Basis für die folgenden
Tests sollen deshalb die beiden Messreihen mit nicht-blockierenden Sockets herangezogen
werden.
8.1.2 Der Zero-Copy-Layer
Da der Netzwerk-Layer sehr stark mit dem Zero-Copy-Layer zusammenhängt, wurde auf eine
separate Messung verzichtet. Doch die Implementation dieses Layers kann die Performance stark
beeinflussen. Beim Socket-Netzwerk-Layer enthält ein asynchrones Senden einen Aufruf von
WriteFileEx. Synchrones Senden braucht deren zwei, um einen Header zu versenden und
anschliessend den Datenbereich. Das Empfangen braucht in jedem Fall zwei Aufrufe von
ReadFileEx.
Der Zero-Copy-Layer sollte beim asynchronen Versenden eigentlich keine grossen Einbussen
verbuchen. Synchrones Senden ist jedoch entsprechend Aufwendig, da zusätzlich eine
Empfangsbereitschaftsmeldung verschickt werden muss. Abbildung 8.3 und 8.4 zeigen, welche
Auswirkungen diese beiden Schichten mit sich bringen.
Bandbreiten mit dem Zero-Copy-Layer über 100 mbit Ethernet
10’000’000
1’000’000
100’000
10’000
1
10
100
1’000
10’000
100’000
1’000’000
10’000’000
Sockets Non-Blocking
Zero-Copy Async
Zero-Copy Sync
Abb. 8.3: Resultate der Bandbreitenmessungen mit dem Zero-Copy-Layer über 100 mbit Ethernet
Die Resultate der Messung über das 100 mbit Ethernet überraschen kaum. Die asynchrone
Kommunikationsform scheint keine wesentliche Einbussen gegenüber den nicht-blockierenden
Sockets hinnehmen zu müssen. Anders die synchrone Form: Die (für Sockets eigentlich unnötige)
Synchronisation ist erst ab Paketgrössen von etwa 4 kB nicht mehr relevant. Überraschend hoch
ist der Datendurchsatz bei Paketen zwischen 64 kB und 1 MB. Die Mischung von kleinen (Header)
und grossen Paketen scheint das System zu stimulieren.
Seite 81
ETH Zürich
Bandbreiten mit dem Zero-Copy-Layer über GigaBit Ethernet
100’000’000
10’000’000
1’000’000
100’000
10’000
1
10
100
1’000
10’000
100’000
1’000’000
10’000’000
Sockets Non-Blockingt
Zero-Copy Async
Zero-Copy Sync
Abb. 8.4: Resultate der Bandbreitenmessungen mit dem Zero-Copy-Layer über 100 mbit Ethernet
In ungefähr das gleiche Bild zeigt das GigaBit-Ethernet: Die asynchrone Kommunikation
überzeugt, die synchrone naturgemäss erst ab einer Paketgrösse von etwa 4 kB. Überraschend ist
nur der Bereich zwischen 724 Bytes und etwa 4 kB. Ich vermute, dass die Anzahl der offenen
Send-Requests (oder deren Gesamtgrösse) einen Einfluss auf die Leistung haben kann.
Die Leistung des Zero-Copy-Layers scheint mir akzeptabel zu sein. Eine gute Ausgangslage für
Applikationen wie die beiden Prototypen, die darauf aufbauen.
Auf Grund der soeben vorgestellten Messresultate wurde auch die obere Grenze für asynchron
versendete Pakete festgelegt. Für alle folgenden Messungen liegt diese bei 12 kB. Pakete die
grösser sind, müssen synchron verschickt werden.
8.1.3 Der MPI-Prototyp
Für die Messung der Bandbreite des MPI-Prototypen wurden die blockierenden Funktionen
MPI_Send und MPI_Recv verwendet. Die Abbildungen 8.5 und 8.6 stellen die Resultate
verglichen mit dem Zero-Copy-Layer dar.
Pakete bis zu einer Grösse von 12 kB werden asynchron versendet. Dieser Vorgang beinhaltet je
einen zusätzlichen Kopiervorgang beim Sender und Empfänger. Dies und die Verwendung eines
dedizierten Kommunikationsthreads mindern die Leistung des Prototypen bei kleinen Paketen. Der
Knick nach der 12 kB-Grenze rührt von der plötzlichen Verwendung der synchronen
Kommunikationsart her.
Seite 82
ETH Zürich
Bandbreiten mit dem MPI-Prototypen über 100 mbit Ethernet
10’000’000
1’000’000
100’000
10’000
1
10
100
1’000
10’000
100’000
1’000’000
10’000’000
MPI
Zero-Copy Async
Zero-Copy Sync
Abb. 8.5: Resultate der Bandbreitenmessungen mit dem MPI-Prototypen über 100 mbit Ethernet
Bandbreiten mit dem MPI-Prototypen über GigaBit Ethernet
100’000’000
10’000’000
1’000’000
100’000
10’000
1
10
100
1’000
10’000
100’000
1’000’000
10’000’000
MPI
Zero-Copy Async
Zero-Copy Sync
Abb. 8.6: Resultate der Bandbreitenmessungen mit dem MPI-Prototypen über GigaBit-Ethernet
Über das GigaBit-Ethernet zeigt sich im wesentlichen das selbe Bild, so dass lange Kommentare
überflüssig sind.
8.1.4 Der OpenMP-Prototyp
Beim OpenMP-Prototypen ist es etwas schwieriger einen Bandbreitentest durchzuführen, da
Speicher immer seitenweise (4 kB) verschickt wird. Trotzdem wurde mit folgendem Programm
versucht, einen solchen Test durchzuführen. Auf zwei Maschinen läuft je ein OpenMP-Thread.
Beide Threads allozieren 16 MB im SHARED-Speicher. Der eine Thread modifiziert zuerst alle
Seiten. Nach einer Barrier modifiziert der zweite Thread diese Seiten und misst die Zeit, die er
braucht, um die gültigen Kopien aller Seiten zu erhalten.
Seite 83
ETH Zürich
#define SIZE (16*1024*1024)
OMP_PARALLEL(TRUE)
LARGE_INTEGER lStart;
LARGE_INTEGER lEnd;
int i;
char* pBuf = OMP_ALLOC(SIZE);
OMP_SECTIONS
OMP_SECTIONS_DECLARE
OMP_SECTIONS_END_DECLARE
OMP_SECTION(0)
for(i = 0; i < SIZE; i += PAGE_SIZE)
p[i] = 1;
OMP_BARRIER
OMP_BARRIER
OMP_SECTION(1)
OMP_BARRIER
QueryPerformanceCounter(&lStart);
for(i = 0; i < SIZE; i += PAGE_SIZE)
p[i] = 0;
QueryPerformanceCounter(&lEnd);
OMP_BARRIER
printf("Time %I64i\n", lEnd.QuadPart - lStart.QuadPart);
OMP_END_SECTIONS(WAIT)
OMP_END_PARALLEL
Für diese 16 MB Speicher hat das Testsystem über das 100 mbit Ethernet durchschnittlich 4.393
Sekunden gebraucht. Dies ergibt einen Durchsatz von etwa 3.64 MB/s. Im Vergleich dazu erreicht
der MPI-Prototyp bei einer Paketgrösse von 4 kB und synchronem Senden und Empfangen einen
Durchsatz von ungefähr 3.96 MB/s, also knapp 8% mehr. Verwendet man unter MPI jedoch
asynchrone Kommunikation, was bei solch kleinen Paketen durchaus sinnvoll ist, so werden 7.64
MB/s erreicht, was mehr als das Doppelte des DSM-Systems ist.
8.2 Profiling über Sockets
Die eben geschilderten Bandbreitenmessungen haben verschiedene Spekulationen mit sich
gezogen, in welchen Teilen des Systems Zeit verloren gegangen sein könnte. Die folgenden
Profile-Messungen sollen Aufschluss geben.
Dabei wird der Ablauf einer einzelnen Kommunikation so genau wie möglich ausgemessen. An
wichtigen Stellen im Kommunikationsablauf wird die aktuelle Zeit gemessen und gespeichert. Die
Differenzen aus diesen Zeiten zeigen auf, wo viel und wo wenig Zeit verbraucht wird. Damit
können allfällige Problemstellen lokalisiert werden.
WinNT: Für solche Zeitmessungen stellt Windows NT (oder besser gesagt der Pentium
Prozessor) einen sogenannten Performance Counter zur Verfügung. Dieser arbeitet (bei
den verwendeten Maschinen von Dell) mit einer Frequenz von 1‘193‘182 Hz. Mit jedem
Takt wird der Counter um eins erhöht. Der aktuelle Stand kann mit
QueryPerformanceCounter ausgelesen werden. Übrigens: Die Frequenz ist
prozessorabhängig. Sie kann mit QueryPerformanceFrequency ermittelt werden.
Jede Messung beeinflusst das vermessene System. Deshalb ist es wichtig vorher die
Auswirkungen
der
Messung
zu
verstehen.
Zwei
Aufrufe
der
Funktion
QueryPerformanceCounter unmittelbar hintereinander bringen Aufschluss darüber. Resultat:
Eine Messung verbraucht mindestens 5 Ticks (1 Tick = 1 / 1‘193‘182 Sekunden).
8.2.1 MPI-Prototyp und Zero-Copy-Layer
Ein MPI_Send auf der einen Maschine, ein MPI_Recv auf einer anderen. Dieser Ablauf einer
Kommunikation wurde ausgemessen. Dabei wurden folgende Messpunkte gesetzt:
Seite 84
ETH Zürich
Aufruf von MPI_Send
Übergabe des MPI-Requests an den Kommunikationsthread (in Queue)
Übernahme des MPI-Requests durch den Kommunikationsthread (aus Queue)
Aufruf der Zero-Copy-Layer-Funktion ZCL_SendXxxx
Aufruf der Netzwerk-Layer-Funktion NWL_SendXxxx
Aufruf der Win32-Funktion WriteFileEx im Netzwerk-Layer
Asynchonous Procedure Call (Ende der Übertragung)
Aufruf von ZCL_HandleSendDone
Kommunikationsthread signalisiert die Beendigung des MPI-Requests (SetEvent)
MPI_Wait wird verlassen
Abbildung 8.7 zeigt, wieviel Zeit
zwischen
den
Messpunkten
verbraucht wurde. Jede Messung
wurde 10 mal wiederholt. Die
verwendeten Werte bilden den
Durchschnitt dieser Messungen.
Um die Zeiten innerhalb der Layer
deutlicher darstellen zu können,
wurde
die
eigentliche
Kommunikationszeit (5 – 6) in der
Grafik weggelassen.
Die vier Messungen wurden mit
unterschiedlichen
Paketgrössen
durchgeführt:

Async Small: 32 Byte

Async Big: 8 kB

Sync Small: 16 kB

Sync Big: 1MB
Zeitaufwände des Sendevorganges
250
200
8-9
7-8
Zeit [Ticks]
8.2.1.1 Senden
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
6-7
150
4-5
3-4
2-3
100
1-2
0-1
50
0
Async Small
Async Big
Sync Small
Sync Big
Die genauen Resultate können der Abb. 8.7: Zeitaufwände des Sendevorgangs
Tabelle 8.1 entnommen werden.
Achtung: Diese Werte enthalten den durch die Messung verursachten Mehraufwand!
Async Small
Async Big
Sync Small
Sync Big
0-1
1-2
2-3
3-4
39.8
34.9
35.0
36.2
30.0
28.9
29.0
29.5
9.3
78.5
9.2
9.0
6.4
6.3
8.6
9.2
4-5
5-6
6-7
7-8
8-9
9.4 146.3
9.6 264.3
9.0 482.8
9.3 11399.9
6.9
7.3
6.6
16.4
18.0
15.9
17.7
24.5
32.8
37.0
33.9
49.1
Tab. 8.1: Durchschnittliche Zeitaufwände des Sendevorgangs in Ticks
Neben dem eigentlichen Versenden (5 – 6) sind vor allem die Kontextwechsel (1 – 2 und 8 – 9)
und das Aufbereiten des Requests (0 – 1), verursacht durch ein Mutex, zeitintensiv. Die im ZeroCopy-Layer und im Netzwerk-Layer verbrauchte Zeit ist praktisch vernachlässigbar, insbesondere,
wenn man die Zeit für die Messungen selber (je ca. 5 Ticks) noch abzieht.
Auffällig ist jedoch der Wert von Async Big/2 – 3: Asynchrones Versenden mit MPI bedingt ein
Kopiervorgang (bei Verwendung von Sockets eigentlich unnötig, beim Gebrauch einer echten
Zero-Copy-Technologie wie GM jedoch unerlässlich!). Welchen ungeheuren Aufwand diese
Kopiererei mit sich bringt zeigt die Grafik ganz deutlich.
8.2.1.2 Empfangen
0: Aufruf von MPI_Recv
1: Übergabe des MPI-Requests an den Kommunikationsthread (in Queue)
2: Übernahme des MPI-Requests durch den Kommunikationsthread (aus Queue)
3: Aufruf der Zero-Copy-Layer-Funktion ZCL_RecvSync
4: Asynchonous Procedure Call NWL_RecvBodyComplete (Ende der Übertragung)
Seite 85
ETH Zürich
5: Aufruf von ZCL_HandleXxxxRecv
6: Kommunikationsthread signalisiert die Beendigung des MPI-Requests
7: MPI_Wait wird verlassen
Auch hier soll eine Grafik (Abbildung
8.8) die Werte der Tabelle 8.2
verdeutlichen.
250
200
6-7
Zeit [Ticks]
Beim asynchronen Empfangen mit
MPI wird dem Kommunikationsthread die Empfangsabsicht nicht
mitgeteilt.
Wurde
ein
Paket
empfangen, dann wird in der Queue
des Empfängers nachgeschaut, ob
er bereits empfangsbereit ist. Falls
nicht, wird das Paket in seine Queue
eingefügt. Das ist der Grund, wieso
keine Werte für 1 – 2 und 2 – 3
existieren.
Zeitaufwände des Empfangvorgangs
5-6
150
4-5
2-3
1-2
100
0-1
50
Da der Empfang asynchron erfolgt,
kann nicht ermittelt werden, wann
der
Empfang
genau
beginnt.
Deshalb wurden auch die Werte 3 4 nicht gemessen.
Auch in diesen Werten sind die
Mehraufwände durch die Messung
enthalten!
Async Small
Async Big
Sync Small
Sync Big
0
Async Small
Async Big
Sync Small
Sync Big
Abb. 8.8: Zeitaufwände des Empfangvorgangs
0-1
1-2
2-3
3-4
4-5
5-6
6-7
38.2
35.4
33.9
36.4
32.0
33.7
9.0
8.0
-
6.6
7.0
8.1
9.8
32.9
92.5
30.1
42.6
56.4
59.9
52.9
58.8
Tab. 8.2: Durchschnittliche Zeitaufwände des Empfangvorgangs in Ticks
Das selbe Schema wie beim Senden: Aufwände beim Requestaufbau (0 – 1) und beim
Kontextswitch (1 – 2 und 6 –7). Aufwand jedoch auch beim Auswerten des empfangenen Paketes
und zuordnen zu einem Request (5 – 6). Hier sind wieder Mutex und beim Async Big
Kopiervorgänge im Spiel.
Da Kontextswitches und Synchronisation mittels Mutex zu den grössten Zeitverbrauchern gehören,
wurde mit folgenden kleinen Programmen versucht, den effektiven Verbrauch zu messen:
WaitForSingleObject(hMutex, INFINITE);
ReleaseMutex(hMutex);
Die Differenz zwischen lEnd und lStart ergibt auf den Testmaschinen einen durchschnittlichen
Wert von 23 Ticks (Messung inklusive).
Thread 1
Thread 2
Sleep(1000);
SetEvent(hEvent);
Sleep(1000);
WaitForSingleObject(hEvent, INFINITE);
Die Messung eines Kontextswitches zwischen zwei Threads ergab Werte um 24 Ticks.
Abgesehen von diesen Elementen sind die Verluste eher gering, der MPI-Prototyp und die
Kommunikationslayer also durchaus brauchbar.
Seite 86
ETH Zürich
8.2.2 OpenMP-Prototyp und Zero-Copy-Layer
Beim OpenMP-Prototypen wurde versucht, das Senden und Empfangen einer Speicherseite,
ausgelöst durch einen Page-Fault zu vermessen. Dazu wurde auf einem System eine
Speicherseite vorgängig verändert, so dass diese Seite auf der anderen Maschine nicht mehr
gültig ist. Nach einer Barrier wird auf der zweiten Maschine die selbe Seite verändert. Dies löst die
Kommunikation aus, die Vermessen werden soll.
Folgende Messpunkte wurden auf den beiden Maschinen eingerichtet:
Request:
0:
1:
2:
3:
4:
5:
6:
7:
8:
Exception-Handler bemerkt Zugriff auf ungültige Speicherseite
Übergabe des Page-Requests an den Kommunikationsthread (in Queue)
Übernahme des Page-Requests durch den Kommunikationsthread (aus Queue)
Aufruf der Zero-Copy-Layer-Funktion ZCL_RecvSync
Asynchonous Procedure Call NWL_RecvBodyComplete (Ende der Übertragung)
Aufruf von ZCL_HandleSyncRecv
Kommunikationsthread signalisiert die Beendigung des Page-Requests
Exception-Handler fährt mit der Arbeit fort
Exception-Handler wird verlassen
Reply:
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
Empfang eines Page-Requests
Aufruf der Zero-Copy-Layer-Funktion ZCL_SendSync
Aufruf der Netzwerk-Layer-Funktion NWL_SendSync
Aufruf der Win32-Funktion WriteFileEx im Netzwerk-Layer
Asynchonous Procedure Call (Ende der Übertragung)
Aufruf von ZCL_HandleSendDone
Freigeben der Speicherseite und wecken schlafen gelegter Threads
Request beendet
Die Abbildung 8.9 und die Tabelle
8.3 geben Auskunft über die
Messresultate.
Zeitaufwände der OpenMP-Kommunikation
200
Wie bei den vorangegangenen
Messungen enthalten diese Werte
den zusätzlichen Aufwand der
Messung.
180
8-9
160
7-8
6-7
140
5-6
120
Zeit [Ticks]
Die Messwerte der eigentlichen
Kommunikation
stellen
den
grössten Aufwand dar. Diese
Zeiten wurden aus der Betrachtung
und aus der Abbildung entfernt, um
die restlichen Zeiten genauer
Darstellen zu können.
4-5
3-4
100
2-3
1-2
80
0-1
60
40
20
0
Page Request
Page Reply
Abb. 8.9: Zeitaufwände im OpenMP-Prototypen
Page Request
Page Reply
0-1
1–2
2-3
3-4
4-5
5-6
6–7
7–8
8–9
22.3
25.7
13.1
-
17.9 1180.2
6.4
36.7
8.2
9.1
388.4
46.0
6.6
30.7
6.6
16.3
Tab. 8.3: Durchschnittliche Zeitaufwände der OpenMP-Kommunikation in Ticks
Beim Page-Request sind die Zeitaufwände zwischen den Messpunkten 6 und 8 am grössten.
Dieser Aufwand geht mehrheitlich auf Kosten eines Kontextswitches und eines Mutex.
Seite 87
ETH Zürich
Ungewöhnlich hoch ist die Messung 4-5. Diese Messpunkte befinden sich innerhalb des ZeroCopy-Layers. Die entsprechenden Messungen mit dem MPI-Prototypen haben wesentlich bessere
Werte ans Licht geführt. Cache-Misses oder Page-Fault könnten Antworten sein.
8.3 Messungen über Named-Pipes
Leider haben die Messungen über die Sockets gezeigt, dass diese keines Falls die Leistungen
ausnützen können, die das darunterliegende Netzwerk bieten würde. Deshalb sind die Messungen
des Zero-Copy-Layers bzw. der Prototypen nicht unbedingt aussagekräftig. Aus diesem Grunde
wurde eine zweite Messreihe gestartet. Dieses mal wurde lokal über Named-Pipes gemessen.
Verwendet wurde ein Dell Precision 410 (400 MHz Dual-Pentium II, 256 MB 100 MHz RAM) und
ein Dell GX1 (350 MHz Pentium II, 64 MB RAM).
In zwei Prozessen laufen je ein Thread, die über eine Named-Pipe verbunden sind. Sende- und
Empfangspuffer wurden auf 64 kB festgelegt. Grundsätzlich wurden nicht-blockierende Funktionen
zum Senden (WriteFileEx) und Empfangen (ReadFileEx) verwendet.
8.3.1 Latenzmessung
Für die Latenzmessung wurde ein Ping-Pong-Verfahren verwendet. Genauer gesagt, wurden die
Zeiten für 100'000 Ping-Pong-Meldungen mit jeweils 1 Byte Payload gemessen. Folgende
Resultate wurden erreicht:
1 CPU
2 CPUs
Named-Pipes
0.125 ms
0.103 ms
Zero-Copy-Layer, Async
0.191 ms
0.171 ms
Zero-Copy-Layer, Sync
0.404 ms
0.313 ms
Tab. 8.4: Latenzzeiten (Zeit für ein Ping-Pong)
Auf Grund der grösseren Datenpakete (16 Byte Header + 1 Byte Payload) und zusätzlicher
Verarbeitungsaufwand ist die Latenz bei den asynchronen Paketen via Zero-Copy-Layer rund 50
bis 60% grösser, was sich vor allem bei kleinen Paketen auswirken wird. Nicht überraschend ist die
Latenz bei synchronen Paketen: Sie liegt um den doppelten Wert der asynchronen, da ein PingPong mit synchronen Paketen im wesentlichen zwei Ping-Pongs mit asynchronen Paketen
entspricht.
8.3.2 Bandbreitenmessung
Noch wichtiger als die Latenz sind die Resultate der Bandbreitenmessungen. Um die Systeme
jederzeit so weit wie möglich auszulasten, wurden jeweils nicht nur ein WriteFileEx aufgerufen,
sondern immer mehrere pendent gehalten. Genauer gesagt, waren immer bis zu 10 Aufrufe (mit
zusammen maximal 10 MB Paketspeicher) zur gleichen Zeit aktiv.
Seite 88
ETH Zürich
100’000’000
10’000’000
1’000’000
100’000
10’000
1
10
100
1’000
Pipes
10’000
Async
100’000
1’000’000
10’000’000
Sync
Abb. 8.10: Bandbreiten über Named-Pipes mit 1 CPU
Die genauen Resultate können in der Tabelle A.5 im Anhang A nachgelesen werden. Die
Abbildungen 8.10 und 8.11 veranschaulichen die Resultate:
100’000’000
10’000’000
1’000’000
100’000
10’000
1
10
100
1’000
Pipes
10’000
Async
100’000
1’000’000
10’000’000
Sync
Abb. 8.11: Bandbreiten über Named-Pipes mit 2 CPUs
Deutlich zu sehen sind die Auswirkungen der grösseren Latenzzeiten bei den Paketen mit Grössen
unterhalb von ca. 16 kB. Bei grösseren Paketen gleichen sich alle drei Kurven an. Sogar die
synchronisierte Kommunikation kann mithalten. Bei Grössen über 128 kB wird etwa 95% der
Leistung der Pipes erreicht.
Interessant ist der Kreuzungspunkt der Async- und Sync-Kurve auf der Dual-CPU-Maschine bei
etwa 45 kB. Pakete, die grösser sind, lassen sich offensichtlich über die synchrone
Kommunikationsart effizienter verschicken. Gründe dafür können in Page-Faults, Cache-Misses
und Konkurrenzverhalten der beiden Prozessoren vermutet werden.
Seite 89
ETH Zürich
8.3.3 Profiling
Ähnlich, wie in Kapitel 8.2 wurden auch bei den Messungen über Named-Pipes ProfilingInformationen gesammelt, um allfällige Schwachstellen in den Layern zu lokalisieren. 10 mal
wurden die Etappen eines Sende- bzw. Empfangvorgangs ausgemessen. Der Durchschnitt dieser
Werte, korrigiert um die Verfälschung durch die Messung, sind in den Tabellen 8.5 und 8.6
dargestellt. Die vollständigen Tabellen sind in Angang A (Tabellen A.6 bis A10) abgedruckt.
1
2
3
4
5
6
7
1 CPU
7.5
1.0
4.5
1.7
2.1
1.6
3.2
2 CPU
5.0
0.5
2.4
0.5
1.3
0.7
1.8
Tab. 8.5: Zeitaufwände für das asynchrone Senden und Empfangen in µs
Legende:
1:
2:
3:
4:
5:
6:
7:
Senden – Allozieren und Aufbereiten des Send-Requests
Senden – Zeit im Zero-Copy-Layer
Senden – Zeit im Netzwerk-Layer
Senden Call-Back – Zeit im Netzwerk-Layer
Senden Call-Back – Zeit im Zero-Copy-Layer
Empfangen Call-Back – Zeit im Netzwerk-Layer
Empfangen Call-Back – Zeit im Zero-Copy-Layer
Messungen dieser Art sind auf Grund von Störungen aus dem System (Cache, Interrupts, SystemThreads, Services und Server-Prozesse) mit sehr viel Vorsicht zu interpretieren. Vergleicht man
diese Werte mit den gemessenen Latenzzeiten, auf welche sicherlich mehr Verlass ist, dann
erscheinen diese Werte als eher zu klein: Rechenbeispiel für das Dual-CPU-System:
Ping-Pong-Latenz Zero-Copy-Layer Asynchron:
Ping-Pong-Latenz Named-Pipes:
Latenz-Differenz Ping-Pong (= 2 x Send/Recv)
Latenz-Differenz für ein Send/Recv
171 µs
103 µs
68 µs
34 µs
Geht man davon aus, dass der Sende-Call-Back sowie der Empfangs-Call-Back parallel ablaufen
können, dann kommt man auf eine maximale Summe aus Tabelle 8.5 von etwa 10 µs. Entweder
sind diese Werte zu klein geraten, oder die Störungen durch das System wirken sich auf Dauer
mehr aus, als diese Zahlen aussagen können.
Die Werte als absolut hinzunehmen wäre gewagt, doch relativ zueinander könnten sie durchaus
aussagekräftig sein: So sind die hohen Werte von 1 und 3 sehr wohl erklärbar: 1 resultiert aus der
Allokation von Speicher, 3 aus dem Aufbereiten des Sende-Requests. Unverständlich dagegen
sind die eher hohen Werte in 5 und 7, denn in diesen beiden Abschnitten wird so gut wie nichts
getan.
Trotz dieser Schwierigkeiten in der Interpretation ist es bemerkenswert, dass die Zahlen aus den
Messungen auf zwei unterschiedlichen Systemen die selben Grössenordnungen aufweisen.
Deshalb soll hier auf die Werte der Messungen mit synchroner Kommunikation nicht verzichtet
werden:
1
2
3
4
5
6
7
8
9
10
1 CPU
1.9
1.8
1.9
0.9
1.8
3.0
50.5
0.7
1.9
2.3
2 CPU
0.7
1.3
1.5
0.5
0.9
1.6
52.1
0.1
1.2
1.4
Tab. 8.6: Zeitaufwände für das synchrone Senden und Empfangen in µs
Legende:
Seite 90
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
Empfangen – Zeit im Zero-Copy-Layer (Teil 1)
Empfangen – Zeit im Netzwerk-Layer
ETH Zürich
Auffälligster Wert ist die Nummer 7, das Versenden des Paketes, das die Empfangsbereitschaft
signalisieren soll. Verglichen mit dem asynchronen Versenden von Paketen ist dieser Wert
aussergewöhnlich hoch. Konkrete Gründe fehlen jedoch.
Seite 91
Seite 92
ETH Zürich
ETH Zürich
9 Die Applikationen
Die bisherigen Messungen beschränken sich auf das Ermitteln von charakteristischen Werten wie
Bandbreite oder Latenz. Praktische Applikationen haben jedoch nur selten ein so extremes
Verhalten wie diese Tests. Die gemessenen Werte sind daher nicht unbedingt aussagekräftig was
die Leistungsfähigkeit eines Systems betrifft. Deshalb wurden zwei Anwendungen geschrieben, die
diese Systeme (bzw. die Prototypen) im praktischen Einsatz untersuchen sollen.
9.1 Quick-Sort
Die erste Applikation ist der klassische und weitverbreitete Quick-Sort [17]. Da dieses
Sortierverfahren nach dem Prinzip „Teile und Herrsche“ funktioniert, ist es auf einfache Weise
parallelisierbar, indem die entstandenen Teile von verschiedenen Threads weiter behandelt
werden.
So wie sich die beiden Prototypen in ihren Eigenschaften sehr stark unterscheiden, so
unterscheiden sich auch die beiden Implementationen.
9.1.1 Quick-Sort mit MPI
Die MPI-Variante entspricht weitgehend der klassischen Implementation. In einem grossen Array in
Thread 0 befinden sich die zu sortierenden (Integer-)Elemente. Thread 0 partitioniert diesen Array
nun gemäss Quick-Sort in zwei Teile. Das grössere Teil behält Thread 0 für die
Weiterverarbeitung, das kleinere schickt er an Thread 1. Beide Threads teilen ihr Teilstück
wiederum in zwei Teile, behalten das Grössere und leiten das Kleinere an einen nächsten Thread
weiter. Dabei ist klar festgelegt, welcher Thread an welche Threads delegieren kann:
Thread...
...delegiert an...
0
1
2
4
8
1
-
3
5
9
2
-
-
6
10
3
-
-
7
11
4
-
-
-
12
5
-
-
-
13
6
-
-
-
14
7
-
-
-
15
Tab. 9.1: Delegationsschema bei 15 Threads
Sobald alle Threads ein Stück des gesamten Arrays erhalten haben, werden diese Teile lokal
mittels Quick-Sort sortiert, also nicht mehr weiter delegiert. Klassischerweise würden nun die
sortierten Teile den hierarchischen Weg entlang zurück zum Thread 0 geschickt. Im Beispiel von
Tabelle 9.1 würde Thread 11 sein Teil an Thread 3 schicken, dieser würde das erhaltene Teil und
sein Teil an Thread 1 schicken und von dort zu Thread 0 gelangen. Um Kommunikationsaufwand
einzusparen, wird der hierarchische Weg umgangen und die Teile direkt an Thread 0 geschickt.
9.1.2 Quick-Sort mit OpenMP
Etwas komplizierter ist die Implementation mit OpenMP. Das Problem liegt in der Eigenschaft von
OpenMP, dass eine Speicherseite nur immer von einem Thread gleichzeitig beschrieben werden
kann. Leider kann beim Partitionieren des Quick-Sort-Algorithmus nicht festgelegt werden, wo
geteilt wird. Im allgemeinen ist die Teilung irgendwo innerhalb einer Speicherseite. Dies hat zur
Folge, dass die beiden Teile nicht parallel weiterbearbeitet werden können. Nur Teile, die nicht
unmittelbar aneinander angrenzen, können parallel bearbeitet werden.
Um entscheiden zu können, welche Teile bearbeitet werden, und welche nicht, wird im MasterThread eine Liste aller Teile geführt. Nachdem ein Thread ein Teil partitioniert hat, werden diese
Seite 93
ETH Zürich
beiden Teile am Ende der Liste angefügt. So entsteht eine Liste, die am Anfang die eher Grossen
und am Ende die kleinen Teile enthält.
Aus dieser Liste werden nun von links nach rechts Teile an die Threads verteilt. Dabei wird immer
geprüft, dass die Teile keine gemeinsamen Speicherseiten aufweisen. In Abbildung 9.1 ist ein
möglicher Ablauf abgebildet.
Abb. 9.1: 5 Durchgänge eines Partitionierungsablaufs (Grau: Wird bearbeitet, Weiss: Bleibt in der Liste)
Der Ablauf des Quick-Sort-Algorithmus hat in OpenMP also etwa folgende Struktur:
Solange nicht vollständig sortiert
{
OMP_MASTER
Gehe durch die Liste und weise jedem Thread ein Teil zu.
OMP_END_MASTER
OMP_BARRIER
Die Threads partitionieren das erhaltene Teil in zwei Teile.
OMP_BARRIER
OMP_MASTER
Die entstandenen Teile werden in die Liste eingefügt.
OMP_END_MASTER
}
Es wäre theoretisch möglich, dieses Partitionieren solange durchzuführen, bis jedes Teil nur noch
aus einem Element bestünde. Spätestens dann wäre der Array sortiert. Dieses Verfahren wäre
jedoch ineffizient. Deshalb existieren zwei Kriterien, die das weitere Partitionieren (und damit auch
die aufwendige Listenführung) unterbinden:

Wenn ein Teil kleiner als eine obere Schranke ist, dann wird es nicht mehr partitioniert,
sondern durch einen Thread lokal vollständig mittels Quick-Sort sortiert. Dieses Teil ist dann zu
Ende bearbeitet und wird nicht mehr in die Liste eingefügt.

Wenn mindestens doppelt so viele Teile in der Liste sind, wie es Threads gibt, dann wird auch
nicht mehr weiter geteilt, sondern die Teile in den nächsten Durchgängen durch die Threads
vollständig sortiert. Es müssen doppelt so viele Teile sein, weil in einem Durchgang ja nur
jedes zweite Teil bearbeitet werden kann.
Kommunikation und damit Zeit kann gespart werden, indem die Zuteilung der Teile auf die Threads
etwas intelligent gestaltet wird: Nachdem ein Teil durch einen Thread partitioniert wurde, werden
die beiden Teile in die Liste eingefügt. Diese Listeneinträge enthalten nicht nur die Randpositionen
der Teile, sondern auch, welcher Thread diese Teile zuletzt bearbeitet hat. Beim Verteilen der Teile
auf die Threads wird versucht, jedes Teil dem Thread zuzuteilen, welcher dieses Teil zuletzt
bearbeitet hat. Dadurch können Page-Faults und damit Kommunikation gespart werden.
Um die aufwendige Behandlung beim ersten Beschreiben von Speicherseiten nach einer Barrier zu
umgehen, wurde der Lock-Mechanismus des OpenMP-Prototypen angewendet.
9.1.3 Die Performance
Um die Leistungsfähigkeit wenigstens grössenordnungsmässig einzuschätzen, wurden die beiden
Implementationen auf folgender Testanordnung ausgemessen:
Testrechner:
Kommunikation:
Applikationen:
Testgrösse:
Seite 94
300 MHz Pentium II, Intel 440LX Chipset, 128 MB Speicher
Zero-Copy-Layer mit Named-Pipes
MPI- bzw. OpenMP-Applikationen, 2 Prozesse mit je 2 Threads
40 MB gefüllt mit 32-bit Integer-Werten
ETH Zürich
Die Resultate (Durchschnitte aus mehreren Messungen):
MPI:
14.7 sec
OpenMP ohne Lock: 24.5 sec
OpenMP mit Lock: 20.9 sec
9.2 Gauss-Elimination
Als zweite Applikation wurde die Gauss-Elimination mit partiellem Pivotieren [17] implementiert. Die
Spalten einer Matrix A werden dabei round-robin an die einzelnen Threads verteilt. Von links nach
rechts ist jeweils ein Thread für die Suche des Pivotelements in einer Spalte verantwortlich.
Danach bearbeiten alle Threads die ihnen zugeteilten Spalten gemäss dem Pivotelement.
9.2.1 Gauss-Elimination mit MPI
Die Implementation mit MPI ist eigentlich unproblematisch. Der Master-Thread initialisiert die
Matrix. Danach sendet er round-robin die Spalten der Matrix an die einzelnen Threads. Thread 0
sucht anschliessend in der Spalte 0 das Pivotelement, ordnet um und teilt die Elemente der Spalte
durch das Pivotelement. Dann wird die Position des Pivotelements, sowie die errechnete
Pivotspalte an alle Threads (inkl. sich selbst) geschickt. Parallel wird nun umgeordnet und die
Spalten neu errechnet. Danach sucht Thread 1 das Pivotelement in der Spalte 1, u.s.w.
So einfach die Implementation ist, so effizient scheint der Algorithmus zu funktionieren.
9.2.2 Gauss-Elimination mit OpenMP
Auf den ersten Blick scheint die Implementation mit OpenMP noch einfacher als mit MPI, denn es
sind keine expliziten Sende- und Empfangsfunktionen notwendig. Für den optimalen Ablauf des
Algorithmus kommen jedoch zwei kleine Tricks zum Zuge, die aus einer TreadMarksImplementation übernommen wurden.
Da der OpenMP-Prototyp nur Single-Writer-Funktionalität aufweist, muss darauf geachtet werden,
dass die Daten der Matrix etwas intelligent im Speicher abgelegt werden. Da jede Spalte einem
Thread zugeteilt wird, müssen die Daten jeder Spalte in separaten Speicherseiten liegen.
Für den korrekten Ablauf des Algorithmus wären eigentlich zwei Barriers notwendig. Es kann
jedoch eine eingespart werden, wenn die Position des gefundenen Pivotelements
abwechslungsweise in zwei Variablen gespeichert wird. Daher die folgenden Zeilen im Code:
if (cur_pivot & 0x01)
*pivot_odd = pivot_col;
else
*pivot_even = pivot_col;
und
pivot_col = (cur_pivot & 0x01) ? *pivot_odd : *pivot_even;
Obwohl der Algorithmus sehr elegant aussieht, arbeitet er im OpenMP-Prototypen nur sehr träge.
Der Grundablauf des Algorithmus sieht etwa folgendermassen aus:
Für jede Spalte
{
Pivotelement suchen
Barrier
Parallel die Spalten bearbeiten
}
Parallel die Spalten bearbeiten heisst, dass die Speicherseiten beschrieben und damit
vom Read-Only- in den Read/Write-Zustand übergehen. Bei der Barrier werden die Seiten dann
wieder in den Read-Only-Zustand zurückgesetzt. Bei einer 1024x1024-Matrix passiert dies über
500'000 mal! Dies ist insofern tragisch, weil der Besitzer der Seite selbst die Seite beschreibt und
daher jedesmal eine Kopie der unveränderten Seite angelegt wird, was unheimlich viel Zeit
beansprucht.
Seite 95
ETH Zürich
Diese Tatsache war der Auslöser, warum der Lock-Mechanismus in den OpenMP-Prototypen
eingebaut wurde.
9.2.3 Die Performance
Auch diese Messungen zeigen höchstens eine Grössenordnung der Leistungsfähigkeit der
Prototypen. Sie zeigen jedoch sehr deutlich, welche Auswirkung der nachträglich eingebaute LockMechanismus hat.
Testrechner:
Kommunikation:
Applikationen:
Testgrösse:
300 MHz Pentium II, Intel 440LX Chipset, 128 MB Speicher
Zero-Copy-Layer mit Named-Pipes
MPI- bzw. OpenMP-Applikationen, 2 Prozesse mit je 2 Threads
2000x2000 / 3000x3000 Matrix gefüllt mit Werten vom Typ Float
Die Resultate (Durchschnitte aus mehreren Messungen):
MPI:
183 sec / 627 sec
OpenMP ohne Lock: 606 sec / 1950 sec
OpenMP mit Lock: 214 sec / 703 sec
9.3 Bessere Testapplikationen
Die beiden vorgestellten Applikationen haben eine Gemeinsamkeit: Die Daten werden in Arrays
gespeichert. Diese Tatsache bevorzugt den MPI-Prototypen. Man kann sich jedoch Applikationen
ausdenken, die auf komplexeren Datenstrukturen wie Listen, Bäume oder anderen Graphen
operieren. Bei solchen Applikationen könnte OpenMP unter Umständen besser abschneiden als
MPI. Der Grund liegt darin, dass OpenMP-Applikationen im Distributed-Shared-Memory problemlos
mit Pointern arbeiten können und zwar auch über die Grenzen eines Knotens hinweg. Für einen
problemlosen Einsatz wären jedoch weitere Synchronisationselemente im OpenMP-Prototypen
vorteilhaft. Bei MPI müssten solche Datenstrukturen durch aufwendiges Verpacken in einen
serialisierten Zustand gebracht und auf Empfängerseite wieder Entpackt werden.
Seite 96
ETH Zürich
A Messresultate
A.1 Bandbreitenmessungen über Sockets
A.1.1 100 mbit Ethernet
Rechner:
2 x Dell Optiplex GX1 (350 MHz Pentium II, 64 MB RAM)
Netzwerkkarte: DEC DE500
Switch:
Bay Networks Bay Stock 100 Base-T Hub
Paketgrösse
[Bytes]
4
5
8
11
16
22
32
45
64
90
128
181
256
362
512
724
1’024
1’448
2’048
2’896
4’096
5’792
8’192
11’585
16’384
23’170
32’768
46’340
65’536
92’681
131’072
185’363
262’144
370’727
524’288
741’455
1’048’576
1’482’910
2’097’152
Socket
Blocking
54’996
69’553
111’077
152’562
221’022
304’448
445’758
636’350
907’777
1’270’907
1’725’678
2’768’770
3’782’779
8’828’678
9’134’447
9'270'441
9’053’752
8’697’981
8’699’449
8’721’846
8’734’019
8’762’111
8’764’561
8’758’396
8’749’764
8’752’116
8’741’652
8’770’333
8’766’105
8’714’285
8’497’871
8’411’002
8’362’823
8’279’703
8’370’618
8’375’549
8’234’623
8’469’755
8’394’041
Socket
Non-Blocking
43’991
55’855
88’319
120’500
174’482
239’543
346’929
487’052
697’995
974’084
1’379’231
1’926’642
2’630’690
3’615’504
5’680’973
8’690’872
8’711’161
8’260’175
8’523’320
8’593’647
8’608’574
8’663’228
8’664’225
8’685’240
8’714’030
8'724'075
8’710’182
8’669’397
8’594’386
7’333’465
6’808’069
7’369’514
7’553’335
7’474’567
7’175’932
7’119’991
6’535’936
7’089’308
6’425’269
Zero-Copy
Async
45’620
56’069
76’445
109’667
158’037
208’096
304’819
456’954
629’421
833’165
1’398’431
2’065’401
2’665’605
4’220’873
5’691’109
7’027’627
7’998’514
8’667’363
8’607’324
8’616’200
8’616’452
8’651’595
8’665’482
8'751'107
8’705’709
8’705’502
8’650’490
8’624’518
7’069’033
6’927’434
8’455’402
7’218’192
Zero-Copy
Sync
12’434
15’606
25’030
34’348
49’972
68’856
98’622
138’130
196’560
277’633
393’561
555’980
808’846
1’194’788
1’723’022
2’429’465
3’454’251
4’877’635
5’948’409
7’955’021
8’345’502
8’308’915
8’415’849
8’518’676
8’732’694
8’627’624
8'756'837
8’702’907
8’651’562
8’659’903
8’562’302
8’332’272
8’119’009
8’049’844
7’809’689
7’548’803
6’486’514
7’094’128
5’881’529
Mpi
21’946
27’365
43’905
60’380
87’997
121’041
176’280
248’992
350’897
496’461
738’345
1’117’500
1’646’003
2’332’924
3’551’672
4’425’116
5’419’019
6’607’070
7’599’277
8’331’399
8’013’159
8’759’176
8'976'373
8’789’947
6’590’648
7’106’404
7’328’175
7’643’936
7’815’323
7’892’926
8’044’789
8’072’678
8’117’108
8’128’147
8’219’072
8’066’383
7’873’492
7’004’607
6’439’751
Tab. A.1: Bandbreitenmessungen über 100 mbit Ethernet (in Bytes/Sec)
Seite 97
ETH Zürich
A.1.2 GigaBit Ethernet
Rechner:
Netzwerkkarte: Packet Engine G-NIC II
Switch:
Paketgrösse
[Bytes]
4
5
8
11
16
22
32
45
64
90
128
181
256
362
512
724
1’024
1’448
2’048
2’896
4’096
5’792
8’192
11’585
16’384
23’170
32’768
46’340
65’536
92’681
131’072
185’363
262’144
370’727
524’288
741’455
1’048’576
1’482’910
2’097’152
Socket
Blocking
123’456
167’887
246’429
337’289
489’790
674’815
1’133’563
1’460’136
1’915’571
2’684’673
3’835’174
5’427’085
10’385’595
11’336’790
11’980’283
12’482’601
13’121’088
13’406’839
13’616’559
13’708’318
13’492’677
13’413’438
13’334’689
13’532’189
13’644’530
14’210’219
13’807’020
14’289’500
14'291'537
13’880’918
13’245’427
12’826’451
12’536’804
12’163’420
12’092’416
11’679’429
11’469’509
11’405’639
11’925’728
Socket
Non-Blocking
83’581
105’028
167’338
228’468
332’897
458’856
662’752
919’690
1’311’137
1’836’212
2’591’043
3’576’135
5’586’733
8’006’402
9’442’800
6’114’055
6’840’167
7’937’970
9’124’591
10’120’700
11’022’321
11’561’090
11’864’915
12’316’523
12’596’374
12’456’501
12’822’442
12’457’813
12'870'325
12’388’551
9’450’743
11’870’490
9’737’235
10’974’841
9’740’687
11’563’440
11’345’653
9’833’229
8’517’249
Zero-Copy
Async
85’273
106’590
166’477
228’872
334’015
462’121
660’569
922’704
1’283’190
1’727’749
2’353’300
3’135’071
4’101’161
5’283’993
6’644’383
8’209’358
10’066’012
12’511’533
12’551’758
13'132'723
12’303’803
12’076’869
11’949’819
12’420’237
12’238’128
12’562’554
12’321’238
13’114’506
12’234’753
11’950’349
11’718’438
11’638’225
Zero-Copy
Sync
17’843
22’778
36’608
49’562
72’534
99’831
148’499
206’562
294’486
410’055
586’763
807’709
1’159’375
1’650’326
2’289’405
3’194’758
4’596’783
6’072’338
8’248’959
10’951’334
12’918’575
12’411’887
11’947’817
11’699’524
11’800’447
12’170’834
12’295’229
12’262’920
12'659'866
12’487’098
12’132’009
11’920’650
11’676’760
10’526’484
11’397’756
11’842’487
11’340’470
7’724’370
8’477’555
Mpi
26’254
32’884
52’590
72’311
104’968
143’935
209’716
293’809
418’672
595’213
859’430
1’254’300
1’991’939
2’985’255
3’869’643
4’856’160
5’948’175
7’130’927
8’961’900
9’980’248
10’773’456
12’442’085
12'801'603
13’094’493
8’696’633
9’872’468
10’529’675
11’228’145
11’375’866
12’222’666
11’869’551
11’998’598
11’884’766
11’357’897
11’358’641
11’813’222
11’199’140
9’599’318
8’336’891
Tab. A.2: Bandbreitenmessungen über GigaBit Ethernet (in Bytes/Sec)
Seite 98
ETH Zürich
A.1.3 Lokale Loopback-Messung
Rechner:
1 x Dell Percision 410 (2 x 400 MHz Pentium II, 256 MB RAM)
Netzwerkkarte: Switch:
Paketgrösse
[Bytes]
4
5
8
11
16
22
32
45
64
90
128
181
256
362
512
724
1’024
1’448
2’048
2’896
4’096
5’792
8’192
11’585
16’384
23’170
32’768
46’340
65’536
92’681
131’072
185’363
262’144
370’727
524’288
741’455
1’048’576
1’482’910
2’097’152
Socket
Blocking
102’096
126’980
202’728
320’870
467’630
566’252
869’472
1’195’194
1’988’722
3’123’465
4’605’912
4’798’344
7’494’059
10’482’579
11’554’861
12’791’992
15’973’089
15’972’702
23’343’592
24’006’862
23’506’675
23’718’184
23’459’579
23’924’787
24'665'376
24’140’012
24’544’301
23’853’738
23’472’457
21’916’876
24’304’191
20’302’224
19’670’955
17’871’444
18’783’060
18’450’868
21’154’379
19’403’937
20’664’569
Socket
Non-Blocking
58’426
73’413
115’948
157’210
232’330
268’334
376’826
517’129
761’221
1’068’847
1’518’304
2’135’814
3’051’671
4’857’138
6’659’764
8’367’622
11’257’291
11’409’087
13’844’567
16’770’418
19’160’965
23’345’382
23’212’652
23’355’591
23'646'629
22’253’477
22’026’579
22’812’896
22’090’936
18’104’906
16’221’008
17’170’430
15’955’291
16’260’570
12’833’012
12’119’947
11’328’433
10’233’315
9’386’002
Tab. A.3: Lokale Bandbreitenmessungen über Sockets (in Bytes/Sec)
Seite 99
ETH Zürich
A.1.4 Myricom GM-Sockets
Rechner:
Netzwerkkarte:
Switch:
Software:
Paketgrösse
[Bytes]
4
5
8
11
16
22
32
45
64
90
128
181
256
362
512
724
1’024
1’448
2’048
2’896
4’096
5’792
8’192
11’585
16’384
23’170
32’768
46’340
65’536
92’681
131’072
185’363
262’144
370’727
524’288
741’455
1’048’576
1’482’910
2’097’152
Myrinet (SAN)
16-Port Myrinet Switch
Myricom GM Release 0.18
Socket
Blocking
50’530
67’235
122’057
175’914
296’948
464’112
770’696
1’160’087
1’712’456
2’023’826
2’937’631
3’584’414
5’168’109
7’376’160
15’755’391
15’773’333
14’852’353
15’350’975
15’455’699
15’658’666
20’749’355
19’839’824
20’464’463
16’483’654
22’109’863
18’609’099
22’674’253
23'594'215
22’635’857
15’811’072
19’808’889
14’776’908
18’037’170
13’855’838
17’533’567
14’038’727
16’744’369
14’599’650
15’454’516
Socket
Non-Blocking
37’758
48’474
82’172
118’999
183’150
282’901
443’207
694’106
1’016’697
1’722’522
2’523’175
2’713’326
3’088’539
3’642’270
4’782’396
6’726’356
14’814’945
15’359’717
15’310’634
15’635’848
10’207’354
13’089’804
13’697’461
16’379’383
13’178’060
17’937’893
18’297’073
18'504'174
17’641’722
6’589’520
9’187’608
9’518’756
7’286’451
9’139’805
6’105’283
7’055’626
5’071’128
5’119’171
5’015’582
Tab. A.4: Bandbreitenmessungen über GM-Sockets (in Bytes/Sec)
Seite 100
ETH Zürich
A.2 Bandbreitenmessungen über Named-Pipes
Rechner:
Dell Percision 410 (2 x 400 MHz Pentium II, Intel 440BX, 256 MB RAM)
Netzwerkkarte: Switch:
Paketgrösse
4
5
8
11
16
22
32
45
64
90
128
181
256
362
512
724
1’024
1’448
2’048
2’896
4’096
5’792
8’192
11’585
16’384
23’170
32’768
46’340
65’536
92’681
131’072
185’363
262’144
370’727
524’288
741’455
1’048’576
1’482’910
2’097’152
2’965’820
4’194’304
Pipes
98’615
122’800
197’572
271’684
396’429
543’064
797’689
1’119’691
1’578’044
2’222’874
3’171’192
4’478’139
6’022’945
8’414’524
11’405’972
15’540’611
20’517’070
26’856’172
32’659’801
42’097’984
47’971’779
49’111’268
55’057’993
59’406’194
68’483’262
60’738’994
60’792’587
61’750’378
63’141’766
63’292’750
63'375'716
58’040’674
56’988’153
57’974’799
53’239’343
54’517’855
54’613’485
54’799’311
54’156’070
55’219’568
55’426’418
1 CPU
Async
62’310
78’115
124’785
171’291
248’704
343’355
498’445
690’126
985’278
1’377’521
1’972’087
2’785’146
3’743’694
5’171’897
7’231’577
9’885’083
13’055’473
17’050’653
20’073’940
25’699’699
32’709’022
38’532’175
43’439’881
46’636’312
51’250’790
54’383’781
55’441’593
55’686’311
56’490’590
56’832’676
57'104'851
56’951’159
55’668’442
52’193’870
Sync
Pipes
24’378
30’408
48’698
67’058
97’279
134’083
194’931
274’562
391’354
546’812
778’124
1’099’850
1’526’303
2’140’388
3’016’747
4’258’159
5’901’445
8’174’477
10’721’284
14’762’244
19’159’218
23’417’030
29’894’493
35’034’064
41’744’493
48’406’003
53’897’599
56’551’538
59’089’945
60’828’272
62'908'964
61’535’786
57’815’080
53’686’176
53’695’578
53’976’238
53’974’596
54’446’954
54’642’376
55’006’411
55’278’100
130’857
163’206
261’581
359’234
521’993
718’722
1’045’359
1’463’785
2’069’533
2’898’890
4’051’137
5’671’765
7’755’867
10’751’080
14’969’783
20’258’248
27’377’094
34’099’792
37’141’765
44’764’172
54’364’284
61’177’733
67’841’896
73’738’747
72’592’267
75’866’878
90'399'667
89’921’865
86’621’218
87’964’562
87’913’770
82’120’846
72’533’257
69’157’783
62’424’659
63’971’643
63’488’071
63’232’111
61’193’706
55’732’203
56’796’690
2 CPU
Async
67’218
84’345
134’794
185’209
269’018
370’838
539’393
751’709
1’070’124
1’499’173
2’119’756
2’978’591
4’065’839
5’603’773
7’779’323
10’734’784
14’627’115
18’669’172
18’820’610
24’091’137
32’574’340
39’132’068
54’603’349
59’301’363
71’382’235
71'532'729
67’659’454
69’217’898
60’318’997
61’590’077
62’666’723
62’823’215
62’507’161
60’702’029
Sync
32’077
39’854
63’943
87’962
127’332
175’339
250’096
351’269
486’177
678’732
950’360
1’338’408
1’754’683
2’430’329
3’403’342
4’780’559
6’671’145
9’204’635
12’254’291
16’502’088
21’953’098
27’342’968
32’912’618
39’553’245
47’376’082
54’626’586
61’435’035
67’257’425
72’888’940
76’495’211
78'118'880
77’984’317
71’695’879
64’441’829
62’365’431
61’346’869
61’193’291
60’590’641
60’565’491
55’112’342
56’070’456
Tab. A.5: Bandbreitenmessungen lokal über Named-Pipes (in Bytes/Sec)
Seite 101
ETH Zürich
A.3 Profiling-Informationen über Named-Pipes
Rechnertyp
1 CPU
2 CPUs
Dell Optiplex GX1
Dell Precision 410
CPU-Taktrate
350 MHz
400 MHz
Speicher
64 MB
256 MB
Performance Counter Frequenz
1‘193‘182 Hz
398‘790‘000 Hz
Verbrauch der Messung
min. 5 Takte
min. 550 Takte
Tab. A.6: Angaben zu den Rechnern und den Performance-Countern
A.3.1 Asynchrone Kommunikation
1
2
3
4
5
6
7
54
9
9
9
9
10
9
10
9
11
6
6
7
7
6
6
6
5
7
6
14
9
10
9
13
9
9
10
11
10
7
9
6
7
7
7
7
6
7
7
7
7
8
7
8
7
7
8
9
7
7
6
7
7
7
7
7
7
7
7
9
9
8
9
9
10
9
9
8
8
13.9
6.2
10.4
7.0
7.5
6.9
8.8
8.9
1.2
5.4
2.0
2.5
1.9
3.8
Zeit [µs]
7.5
1.0
4.5
1.7
2.1
1.6
Tab. A.7: Gemessene Profilingwerte bei 1 CPU in Takten (bzw. µs)
3.2
Serie 1
Serie 2
Serie 3
Serie 4
Serie 5
Serie 6
Serie 7
Serie 8
Serie 9
Serie 10
Durchschnitt
Korrigiert
Legende:
Seite 102
1
2
3
4
5
6
7
Serie 1
Serie 2
Serie 3
Serie 4
Serie 5
Serie 6
Serie 7
Serie 8
Serie 9
Serie 10
14'713
1'368
1'207
1'145
1'148
1'227
1'089
1'033
1'196
1'193
825
766
770
708
725
748
746
735
707
745
3'141
1'478
1'342
1'270
1'228
1'416
1'204
1'224
1'288
1'435
1'069
728
728
708
724
696
696
732
737
724
1'223
1'078
951
926
1'032
1'056
1'239
1'002
1'053
1'079
1'123
815
720
819
788
857
817
799
816
783
1'610
1'262
1'225
1'190
1'249
1'294
1'268
1'218
1'273
1'234
Durchschnitt
2'531.9
747.5 1'502.6
754.2 1'063.9
833.7 1'282.3
Korrigiert
1'981.9
197.5
204.2
283.7
732.3
Zeit [µs]
5.0
0.5
2.4
0.5
1.3
0.7
Tab. A.8: Gemessene Profilingwerte bei 2 CPUs in Takten (bzw. µs)
1.8
1:
2:
3:
4:
5:
6:
7:
952.6
513.9
ETH Zürich
A.3.2 Synchrone Kommunikation
1
2
3
4
5
6
7
8
9
10
Serie 1
Serie 2
Serie 3
Serie 4
Serie 5
Serie 6
Serie 7
Serie 8
Serie 9
Serie 10
10
7
8
7
7
7
6
7
8
6
7
7
6
7
7
7
8
7
7
8
7
7
8
7
7
8
7
8
7
7
6
6
6
6
6
6
6
6
6
7
8
7
7
7
7
8
7
7
7
6
9
8
8
8
8
9
9
9
9
9
80
74
79
74
74
78
73
73
76
71
6
6
5
6
5
7
5
6
6
6
7
8
7
7
7
8
9
7
7
6
8
8
8
8
8
8
7
7
7
8
Durchschnitt
7.3
7.1
7.3
6.1
7.1
8.6
75.2
5.8
7.3
7.7
Korrigiert
2.3
2.1
2.3
1.1
2.1
3.6
60.2
0.8
2.3
2.7
Zeit [µs]
1.9
1.8
1.9
0.9
1.8
3.0
Tab. A.9: Gemessene Profilingwerte bei 1 CPU in Takten (bzw. µs)
50.5
0.7
1.9
2.3
1
2
3
4
5
6
7
8
9
10
Serie 1
Serie 2
Serie 3
Serie 4
Serie 5
Serie 6
Serie 7
Serie 8
Serie 9
Serie 10
1'457
777
736
720
935
768
759
754
770
787
1'275
1'055
1'022
976
1'148
955
1'000
1'047
1'048
980
1'706
1'073
1'018
1'031
1'299
1'106
1'052
992
998
1'089
942
731
753
685
684
698
735
699
699
735
939
923
876
972
889
928
925
902
994
880
1'600
1'212
1'162
1'114
1'313
1'082
1'191
1'252
1'011
1'056
25'182
23'980
25'082
23'942
22'057
20'630
21'239
20'968
20'423
20'738
602
577
562
567
568
567
567
567
567
567
1'183
979
943
959
1'115
1'035
973
997
1'007
1'021
1'168
1'046
1'067
1'051
1'280
1'107
1'049
1'074
1'043
1'074
Durchschnitt
846.3 1'050.6 1'136.4
736.1
922.8 1'199.3
22'424
Korrigiert
296.3
186.1
372.8
649.3
20'774
21.1
471.2
545.9
Zeit [µs]
0.7
1.3
1.5
0.5
0.9
1.6
Tab. A.10: Gemessene Profilingwerte bei 2 CPUs in Takten (bzw. µs)
52.1
0.1
1.2
1.4
Legende:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
500.6
586.4
571.1 1'021.2 1'095.9
Empfangen – Zeit im Netzwerk-Layer
Seite 103
Seite 104
ETH Zürich
ETH Zürich
B Aufgabenstellung
Abb. B.1: Aufgabenstellung, Seite 1
Seite 105
ETH Zürich
Abb. B.2: Aufgabenstellung, Seite 2
Seite 106
ETH Zürich
C Quellenverzeichnis
[1]
Honghui Lu, Sandhya Dwarkadas, Alan L. Cox, Willy Zwaenepoel:
Message Passing Versus Distributed Shared Memory on Networks of Workstations
Rice University, 1995
[2]
OpenMP Architecture Review Board:
OpenMP Fortran Application Program Interface 1.0
Oktober 1997
[3]
OpenMP: A Proposed Industry Standard API for Shared Memory Programming
Oktober 1997
[4]
Cristiana Amza, Alan L. Cox, Sandhya Dwarkadas, Pete Keleher, Honghui Lu, Ramakirshnan
Rajamony, Weimin Yu, Willi Zwaenepoel:
TreadMarks: Shared Memory Computing on Networks of Workstations
Rice University, 1996
[5]
Willi Zwaenepoel:
TreadMarks Shared Memory Computing on a Network of PCs
Rice University
[6]
Message Passing Interface Forum:
MPI: A Message-Passing Interface Standard
Juni 1995
[7]
Message Passing Interface Forum:
MPI-2: Extensions to the Message-Passing Interface
Juli 1997
[8]
David A. Solomon:
Inside Windows NT, Second Edition
Microsoft Press, 1998
[9]
Art Baker:
The Windows NT Device Driver Book
Prentice Hall PTR, 1997
[10] Peter G. Viscarola, W. Anthony Mason:
Windows NT Device Driver Development
MaxMillan Technical Publishing, 1998
[11] Rajeev Nagar:
Windows NT File System Internals
O’Reilly, September 1997
[12] Win32 Software Development Kit
Microsoft, 1996
[13] Windows NT Version 4.0 Device Driver Kit
Microsoft, 1996
[14] Christopher A. L. Vinckier:
Distributed Shared Memory with Myrinet
University of Ghent, 1998
[15] Myricom:
The GM Message Passing System
http://www.myri.com/gm/doc/gm.pdf, 1998
[16] Myricom:
Myrinet: A Gigabit-per-Second Local-Area Network
http://www.myri.com/research/publications/hot.ps, 1995
[17] Robert Sedgewick:
Algorithmen in C++
Addison-Wesley, 1992
Seite 107