Vorwort | 5 |
Inhaltsverzeichnis | 5 |
I Grundlagen der parallelen Programmierung | 13 |
1 Einführung | 16 |
1.1 Paradigmenwechsel in der Softwareentwicklung | 17 |
1.2 Anwendungsbereiche | 18 |
1.3 Parallelität in der Hardware | 18 |
1.3.1 Prozessorarchitektur | 19 |
1.3.2 Multicore-Prozessoren und Multiprozessorsysteme | 22 |
1.4 Parallelität in der Software | 26 |
1.4.1 Prozesse und Threads | 26 |
1.4.2 Virtualisierung | 30 |
1.4.3 Parallelisierende Compiler | 31 |
1.4.4 Parallele Bibliotheken | 32 |
1.4.5 Amdahl'sches Gesetz | 33 |
2 Threads | 36 |
2.1 Arbeiten mit Threads | 36 |
2.1.1 Erzeugung und Beendigung | 36 |
2.1.2 Datenaustausch | 37 |
2.1.3 Threadpools | 40 |
2.2 Scheduling | 41 |
2.2.1 Lastverteilung | 42 |
2.2.2 Affinitäten und Prioritäten | 43 |
2.3 Speicherzugriff | 43 |
2.3.1 Speichermodelle | 44 |
2.3.2 Speicherhierarchie | 50 |
3 Synchronisation | 54 |
3.1 Konflikte | 54 |
3.1.1 Entstehung | 55 |
3.1.2 Kritische Abschnitte | 56 |
3.2 Synchronisationsmechanismen | 58 |
3.2.1 Mutexe | 59 |
3.2.2 Scoped Locking | 63 |
3.2.3 Monitore | 64 |
3.2.4 Lese-/Schreibsperren | 65 |
3.2.5 Semaphore | 67 |
3.2.6 Bedingungsvariablen | 69 |
3.2.7 Barrieren | 74 |
3.2.8 Einmalige Ausführung | 77 |
3.2.9 Atomare Operationen | 79 |
3.2.10 Spinlocks | 82 |
3.3 Fallstricke und Richtlinien | 84 |
3.3.1 Konflikterkennung | 84 |
3.3.2 Verklemmungen | 86 |
3.3.3 Nichtdeterminismus | 89 |
3.3.4 Fairness | 90 |
3.3.5 Skalierbarkeit | 91 |
3.3.6 Threadsicherheit und Wiedereintrittsfähigkeit | 93 |
3.3.7 Schnittstellenentwurf | 94 |
4 Task- und Datenparallelität | 98 |
4.1 Taskparallelität | 98 |
4.1.1 Erzeugung und Synchronisation von Tasks | 100 |
4.1.2 Parallelisierung rekursiver Algorithmen | 102 |
4.1.3 Taskgruppen | 106 |
4.1.4 Spekulation | 108 |
4.1.5 Implementierung eines Task-Schedulers | 111 |
4.1.6 Programmierrichtlinien | 114 |
4.2 Datenparallelität | 115 |
4.2.1 Schleifen ohne Datenabhängigkeiten | 116 |
4.2.2 Reduktionen | 119 |
4.2.3 Präfixberechnungen | 124 |
4.2.4 Partitionierung und Abbildung | 128 |
5 Datenstrukturen | 140 |
5.1 Threadsicherer Zugriff | 140 |
5.1.1 Grobgranulare Synchronisation | 142 |
5.1.2 Feingranulare Synchronisation | 145 |
5.1.3 Optimistische Synchronisation | 147 |
5.1.4 Nichtblockierende Synchronisation | 150 |
5.1.5 Weitere Optimierungen | 152 |
5.2 Auswahl der richtigen Datenstruktur | 152 |
5.2.1 Kriterien | 153 |
5.2.2 Listen | 156 |
5.2.3 Vektoren | 157 |
5.2.4 Assoziative Felder | 158 |
5.2.5 Warteschlangen und Stacks | 158 |
5.2.6 Multimengen | 160 |
6 Entwurfsmuster | 162 |
6.1 Zugriff auf gemeinsame Daten | 164 |
6.1.1 Grundlegende Synchronisationsmuster | 164 |
6.1.2 Threadlokaler Speicher | 166 |
6.1.3 Futures | 170 |
6.1.4 Synchronisationsproxy | 172 |
6.1.5 Active Object | 174 |
6.2 Zerlegung in parallel bearbeitbare Teilprobleme | 178 |
6.2.1 Grundlegende Zerlegungsmuster | 178 |
6.2.2 Master-Slave | 180 |
6.2.3 Erzeuger-Verbraucher | 182 |
6.2.4 Aktoren | 184 |
6.2.5 Reihenfolgebewahrender Threadpool | 187 |
6.3 Fließbandverarbeitung | 194 |
6.3.1 Pipelines | 195 |
6.3.2 Pipelines mit parallelen Stufen | 198 |
6.3.3 Parallele Pipelines | 199 |
7 Architektur paralleler Software | 204 |
7.1 Entwurf paralleler Algorithmen | 204 |
7.2 Entwurf paralleler Architekturen | 206 |
II Sprachen und Bibliotheken | 216 |
8 Threads und Synchronisation in C/C++ | 218 |
8.1 POSIX-Threads | 218 |
8.1.1 Threads | 219 |
8.1.2 Synchronisationsmechanismen | 221 |
8.1.3 Threadlokaler Speicher und Speicherallokation | 223 |
8.2 Windows-Threads | 224 |
8.2.1 Threads | 224 |
8.2.2 Synchronisationsmechanismen | 225 |
8.2.3 Threadlokaler Speicher und Speicherallokation | 228 |
8.2.4 Threadpools | 228 |
8.3 C++11 | 229 |
8.3.1 Lambda-Funktionen | 229 |
8.3.2 Threads | 230 |
8.3.3 Synchronisationsmechanismen | 234 |
8.3.4 Threadlokaler Speicher und Speicherallokation | 242 |
8.3.5 Speichermodell | 242 |
9 OpenMP | 244 |
9.1 Threads | 246 |
9.1.1 Parallele Bereiche | 246 |
9.1.2 Arbeitsteilung | 247 |
9.1.3 Speicherzugriff | 248 |
9.1.4 Threadlokaler Speicher | 249 |
9.2 Synchronisationsmechanismen | 250 |
9.2.1 Kritische Abschnitte | 250 |
9.2.2 Mutexe | 251 |
9.2.3 Barrieren | 251 |
9.2.4 Einmalige Ausführung | 252 |
9.2.5 Atomare Operationen | 253 |
9.3 Taskparallelität | 253 |
9.3.1 Parallelisierung rekursiver Algorithmen | 254 |
9.3.2 Variablenzugriff | 254 |
9.3.3 Suspendierung | 256 |
9.4 Datenparallelität | 257 |
9.4.1 Schleifen ohne Datenabhängigkeiten | 257 |
9.4.2 Reduktionen | 260 |
9.4.3 Partitionierung und Abbildung | 262 |
9.5 Speichermodell | 263 |
10 Threading Building Blocks | 266 |
10.1 Synchronisationsmechanismen | 268 |
10.1.1 Sperren | 268 |
10.1.2 Atomare Operationen | 271 |
10.2 Taskparallelität | 272 |
10.2.1 Parallele Funktionsaufrufe | 272 |
10.2.2 Taskgruppen | 273 |
10.2.3 Task Scheduler | 274 |
10.3 Datenparallelität | 274 |
10.3.1 Schleifen ohne Datenabhängigkeiten | 275 |
10.3.2 Reduktionen | 280 |
10.3.3 Präfixberechnungen | 282 |
10.4 Datenstrukturen | 283 |
10.4.1 Assoziative Felder und Mengen | 284 |
10.4.2 Warteschlangen | 287 |
10.4.3 Vektoren | 288 |
10.5 Algorithmen und Entwurfsmuster | 289 |
10.5.1 Sortieren | 290 |
10.5.2 Fließbandverarbeitung | 290 |
10.5.3 Flussgraphen | 292 |
10.6 Threadlokaler Speicher | 295 |
10.7 Speicherallokation | 296 |
10.8 Ausnahmen und Abbruch | 297 |
11 Parallele Programmierung mit Java | 300 |
11.1 Threads | 301 |
11.1.1 Threaderzeugung | 301 |
11.1.2 Threadpools | 302 |
11.1.3 Threadlokaler Speicher | 304 |
11.2 Synchronisationsmechanismen | 305 |
11.2.1 Sperren | 305 |
11.2.2 Spezielle Synchronisationsmechanismen | 309 |
11.2.3 Atomare Operationen | 311 |
11.3 Taskparallelität | 312 |
11.3.1 Tasks und Futures | 312 |
11.3.2 Starten von Tasks | 313 |
11.3.3 Rekursive Tasks | 314 |
11.3.4 Blockierende Operationen in Tasks | 316 |
11.4 Datenparallelität | 316 |
11.5 Datenstrukturen | 317 |
11.6 Speichermodell | 318 |
12 Parallele Programmierung mit .NET | 322 |
12.1 Threads | 322 |
12.1.1 Threaderzeugung | 322 |
12.1.2 Threadpools | 324 |
12.1.3 Threadlokaler Speicher | 326 |
12.2 Synchronisationsmechanismen | 327 |
12.2.1 Sperren | 327 |
12.2.2 Spezielle Synchronisationsmechanismen | 332 |
12.2.3 Atomare Operationen | 332 |
12.2.4 Einmalige Ausführung | 333 |
12.3 Taskparallelität | 334 |
12.3.1 Tasks und Futures | 335 |
12.3.2 Fortsetzungstasks | 337 |
12.4 Datenparallelität | 339 |
12.4.1 Schleifen ohne Datenabhängigkeiten | 339 |
12.4.2 Parallele Aggregation | 341 |
12.4.3 PLINQ | 343 |
12.5 Datenstrukturen | 344 |
12.6 Ausnahmen und Abbruch | 345 |
12.7 Speichermodell | 346 |
13 Blick über den Tellerrand | 350 |
13.1 Funktionale Sprachen | 351 |
13.2 Aktorbasierte Programmierung | 353 |
13.3 Transaktionsbasierter Speicher | 355 |
Literaturverzeichnis | 360 |
Index | 364 |