Erweiterte Suche

Datenparallele algorithmische Skelette

Erweiterungen und Anwendungen der Münster Skelettbibliothek Muesli

Die Arbeit thematisiert den datenparallelen Bestandteil der Münster Skelettbibliothek Muesli und beschreibt neben einer Reihe implementierter Erweiterungen auch mit Muesli parallelisierte Anwendungen. Eine der wichtigsten Neuerungen ist die Unterstützung von Mehrkernprozessoren durch die Verwendung von OpenMP, infolgedessen mit Muesli entwickelte Programme auch auf Parallelrechnern mit hybrider Speicherarchitektur skalieren. Eine zusätzliche Erweiterung stellt die Neuentwicklung einer verteilten Datenstruktur für dünnbesetzte Matrizen dar. Letztere implementiert ein flexibles Designkonzept, was die Verwendung benutzerdefinierter Kompressions- sowie Lastverteilungsmechanismen ermöglicht. Darüber hinaus werden mit dem LM OSEM-Algorithmus und den ART 2-Netzen zwei Anwendungen vorgestellt, die mit Muesli parallelisiert wurden. Neben einer Beschreibung der Funktionsweise sowie der Eigenschaften und Konzepte von MPI und OpenMP wird darüber hinaus der aktuelle Forschungsstand skizziert.

Titel: Datenparallele algorithmische Skelette
Untertitel: Erweiterungen und Anwendungen der Münster Skelettbibliothek Muesli
Verfasser: Ciechanowicz, Philipp GND
Gutachter: Kuchen, Herbert
Organisation: European Research Center for Information Systems (ERCIS)
FB 04: Wirtschaftswissenschaftliche Fakultät
Dokumenttyp: Dissertation/Habilitation
Medientyp: Text
Erscheinungsdatum: 2010
Publikation in MIAMI: 07.12.2010
Datum der letzten Änderung: 07.06.2016
Reihe Wissenschaftliche Schriften der WWU Münster / Reihe IV ; 2
Schlagwörter: algorithmische Skelette; Datenparallelität; Muesli; MPI; OAL; OpenMP; Skelettbibliothek
Fachgebiete: Datenverarbeitung; Informatik; Wirtschaft
Sprache: Deutsch
Anmerkungen: Auch im Buchhandel erhältlich: Datenparallele algorithmische Skelette / von Philipp Ciechanowicz. - Münster : Monsenstein und Vannerdat, 2010. - XXIV, 313 S. (Wissenschaftliche Schriften der WWU Münster : Reihe IV ; Bd. 2), ISBN 978-3-8405-0029-9, Preis: 19,90 EUR
Format: PDF-Dokument
ISBN: 978-3-8405-0029-9
URN: urn:nbn:de:hbz:6-65489628556
Permalink: https://nbn-resolving.org/urn:nbn:de:hbz:6-65489628556
Onlinezugriff:
Inhalt:
1 Einführung 1
1.1 Algorithmische Skelette . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Zielsetzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Grundlagen der parallelen Programmierung 11
2.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Klassifikation von Parallelrechnern . . . . . . . . . . . . . . . 12
2.2.1 Rechnerarchitekturen . . . . . . . . . . . . . . . . . . . 12
2.2.1.1 Single instruction, single data . . . . . . . . 13
2.2.1.2 Single instruction, multiple data . . . . . . . 13
2.2.1.3 Multiple instruction, single data . . . . . . . 13
2.2.1.4 Multiple instruction, multiple data . . . . . 14
2.2.2 Speicherarchitekturen . . . . . . . . . . . . . . . . . . 14
2.2.2.1 Gemeinsamer Speicher . . . . . . . . . . . . 15
2.2.2.2 Verteilter Speicher . . . . . . . . . . . . . . . 16
2.2.2.3 Hybrider Speicher . . . . . . . . . . . . . . . 17
2.3 Das Message Passing Interface MPI . . . . . . . . . . . . . . . 17
2.3.1 Konzepte . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1.1 Prozesse . . . . . . . . . . . . . . . . . . . . . 19
2.3.1.2 Puffer . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1.3 Datentypen . . . . . . . . . . . . . . . . . . . 20
2.3.1.4 Gruppen . . . . . . . . . . . . . . . . . . . . 20
2.3.1.5 Kommunikatoren . . . . . . . . . . . . . . . 22
2.3.1.6 Fehlercodes und Fehlerklassen . . . . . . . . 23
2.3.2 Paarweise Kommunikationsfunktionen . . . . . . . . . 24
2.3.3 Kollektive Kommunikationsfunktionen . . . . . . . . . 28
2.3.3.1 MPI_Bcast . . . . . . . . . . . . . . . . . . . 30
2.3.3.2 MPI_Gather . . . . . . . . . . . . . . . . . . 30
2.3.3.3 MPI_Allgather . . . . . . . . . . . . . . . . . 31
2.3.3.4 MPI_Reduce . . . . . . . . . . . . . . . . . . 32
2.3.3.5 MPI_Allreduce . . . . . . . . . . . . . . . . 33
2.4 Die Open Multi-Processing API OpenMP . . . . . . . . . . . 34
2.4.1 Konzepte . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4.1.1 Threads . . . . . . . . . . . . . . . . . . . . . 35
2.4.1.2 Inkrementelle Parallelisierung . . . . . . . . 36
2.4.1.3 Fork-Join-Prinzip . . . . . . . . . . . . . . . 36
2.4.2 Direktiven . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4.2.1 parallel . . . . . . . . . . . . . . . . . . . . . 38
2.4.2.2 for . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4.2.3 critical . . . . . . . . . . . . . . . . . . . . . . 40
2.4.3 Klauseln . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.3.1 private . . . . . . . . . . . . . . . . . . . . . . 41
2.4.3.2 reduction . . . . . . . . . . . . . . . . . . . . 42
2.4.3.3 schedule . . . . . . . . . . . . . . . . . . . . . 42
2.4.4 Laufzeitbibliothek . . . . . . . . . . . . . . . . . . . . . 44
2.4.4.1 omp_get_max_threads . . . . . . . . . . . 44
2.4.4.2 omp_get_thread_num . . . . . . . . . . . . 44
2.4.4.3 omp_set_num_threads . . . . . . . . . . . . 44
2.4.5 Effiziente Parallelisierung . . . . . . . . . . . . . . . . 45
2.5 Laufzeitmessung . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.6 Stand der Forschung . . . . . . . . . . . . . . . . . . . . . . . 49
2.6.1 ASSIST . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.6.2 Calcium . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6.3 CO2P3S . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6.4 DatTeL . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.6.5 Eden . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.6.6 eSkel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.6.7 FastFlow . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.6.8 HDC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.6.9 HOC-SA . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.6.10 JaSkel und YaSkel . . . . . . . . . . . . . . . . . . . . 57
2.6.11 Lithium . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.6.12 MALLBA . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.6.13 muskel . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.6.14 P3L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.6.15 PAS, SuperPAS und EPAS . . . . . . . . . . . . . . . 62
2.6.16 QUAFF . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.6.17 SBASCO . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.6.18 SCL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.6.19 Skandium . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.6.20 SKElib . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.6.21 SkeTo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.6.22 SkIE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.6.23 Skil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.6.24 SKIPPER . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.6.25 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3 Die Münster Skelettbibliothek Muesli 75
3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.2 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.2.1 Parallelisierung durch Partitionierung . . . . . . . . . 78
3.2.2 Parametrischer Polymorphismus . . . . . . . . . . . . 79
3.2.3 Funktionen höherer Ordnung . . . . . . . . . . . . . . 81
3.2.4 Partielle Applikation und Currying . . . . . . . . . . . 81
3.2.5 Serialisierung . . . . . . . . . . . . . . . . . . . . . . . 83
3.3 Verteilte Datenstrukturen . . . . . . . . . . . . . . . . . . . . 85
3.3.1 DistributedArray . . . . . . . . . . . . . . . . . . . . . 85
3.3.2 DistributedMatrix . . . . . . . . . . . . . . . . . . . . 86
3.3.3 DistributedSparseMatrix . . . . . . . . . . . . . . . . . 87
3.4 Datenparallele Skelette . . . . . . . . . . . . . . . . . . . . . . 87
3.4.1 count . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.4.2 fold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.4.3 map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.4.4 permute . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.4.5 zip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.5 Erweiterungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.5.1 Unterstützung von Mehrkernprozessoren . . . . . . . 91
3.5.2 Die OpenMP-Abstraktionsschicht OAL . . . . . . . . 94
3.5.3 Kollektive, serialisierte Kommunikationsfunktionen . 96
3.5.3.1 broadcast . . . . . . . . . . . . . . . . . . . . 98
3.5.3.2 allgather . . . . . . . . . . . . . . . . . . . . . 99
3.5.3.3 allreduce . . . . . . . . . . . . . . . . . . . . 100
3.5.4 Diverses . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.5.4.1 DistributedDataStructure . . . . . . . . . . . 101
3.5.4.2 Header- und Quelldateien . . . . . . . . . . . 102
3.5.4.3 Muesli . . . . . . . . . . . . . . . . . . . . . . 104
3.5.4.4 Serialisierung . . . . . . . . . . . . . . . . . . 104
3.6 Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.7 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4 Eine verteilte Datenstruktur für dünnbesetzte Matrizen 111
4.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.2 Konzepte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.2.1 Lastverteilung . . . . . . . . . . . . . . . . . . . . . . . 113
4.2.2 Kompression . . . . . . . . . . . . . . . . . . . . . . . . 115
4.2.3 Parametrischer Polymorphismus . . . . . . . . . . . . 116
4.3 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.3.1 Distribution . . . . . . . . . . . . . . . . . . . . . . . . 116
4.3.1.1 BlockDistribution . . . . . . . . . . . . . . . 119
4.3.1.2 ColumnDistribution . . . . . . . . . . . . . . 120
4.3.1.3 RoundRobinDistribution . . . . . . . . . . . 120
4.3.1.4 RowDistribution . . . . . . . . . . . . . . . . 120
4.3.2 Submatrix . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.3.2.1 CrsSubmatrix . . . . . . . . . . . . . . . . . 127
4.3.2.2 BsrSubmatrix . . . . . . . . . . . . . . . . . 128
4.3.3 RowProxy . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.3.4 DistributedSparseMatrix . . . . . . . . . . . . . . . . . 132
4.3.4.1 Verteilung . . . . . . . . . . . . . . . . . . . . 135
4.3.4.2 Submatrizen . . . . . . . . . . . . . . . . . . 137
4.3.4.3 Indexoperator . . . . . . . . . . . . . . . . . 141
4.3.4.4 Konstruktoren . . . . . . . . . . . . . . . . . 142
4.3.5 Datenparallele Skelette . . . . . . . . . . . . . . . . . . 144
4.3.5.1 count . . . . . . . . . . . . . . . . . . . . . . 146
4.3.5.2 combine . . . . . . . . . . . . . . . . . . . . . 148
4.3.5.3 map . . . . . . . . . . . . . . . . . . . . . . . 152
4.3.5.4 fold . . . . . . . . . . . . . . . . . . . . . . . 154
4.3.5.5 zip . . . . . . . . . . . . . . . . . . . . . . . . 157
4.4 Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.5 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5 Medizinische Bildrekonstruktion mit LMOSEM 167
5.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.2 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5.2.1 Erfassung der Rohdaten . . . . . . . . . . . . . . . . . 169
5.2.2 Der LMOSEM-Algorithmus . . . . . . . . . . . . . . . 171
5.2.3 Dekompositionsstrategien . . . . . . . . . . . . . . . . 171
5.3 Implementierungen . . . . . . . . . . . . . . . . . . . . . . . . 173
5.3.1 Sequenziell . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.3.2 Taskparallel . . . . . . . . . . . . . . . . . . . . . . . . 175
5.3.3 Datenparallel (ISD) . . . . . . . . . . . . . . . . . . . . 179
5.3.4 Datenparallel (PSD) . . . . . . . . . . . . . . . . . . . 181
5.3.5 MPI und OpenMP . . . . . . . . . . . . . . . . . . . . 183
5.3.6 MPI und TBB . . . . . . . . . . . . . . . . . . . . . . 185
5.4 Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
5.5 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
6 Paralleles Training für neuronale ART 2-Netze 193
6.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
6.2 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
6.2.1 Künstliche neuronale Netze . . . . . . . . . . . . . . . 195
6.2.1.1 Arbeitsweise . . . . . . . . . . . . . . . . . . 196
6.2.1.2 Vernetzungsstruktur . . . . . . . . . . . . . . 197
6.2.1.3 Lernverfahren . . . . . . . . . . . . . . . . . . 198
6.2.2 Adaptive Resonanztheorie . . . . . . . . . . . . . . . . 199
6.2.3 ART2-Netze . . . . . . . . . . . . . . . . . . . . . . . . 201
6.3 Paralleler Algorithmus . . . . . . . . . . . . . . . . . . . . . . 206
6.4 Implementierungen . . . . . . . . . . . . . . . . . . . . . . . . 209
6.5 Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
6.6 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7 Schlussbetrachtungen 213
7.1 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.2 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
7.2.1 C++0x und OpenMP 3.0 . . . . . . . . . . . . . . . . 216
7.2.2 Kollektive, serialisierte Kommunikationsfunktionen für
Mehrkernprozessoren . . . . . . . . . . . . . . . . . . . 217
7.2.3 Taskparallele Skelette für Mehrkernprozessoren . . . . 219
7.2.4 GPGPU und OpenCL . . . . . . . . . . . . . . . . . . 219
7.2.5 Neuimplementierung von Muesli mit Java . . . . . . . 220
7.3 Schlussfazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
A Hilfsklassen 225
A.1 EventPacket . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
A.2 Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
A.3 Integer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
A.4 MatrixIndex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232