Multicore-Software

Urs Gleim ist Diplom-Informatiker und war in seiner ber uflichen Laufbahn als Entwickler, Software- und Systemarchitekt, Projektleiter und technischer Berater tätig. Heute arbeitet er bei der Siemens Corporate Technology, der zentralen Forschung und Entwicklung von Siemens. Dort leitet er ein Team, das Softwarearchitekturen für Multicore-Systeme ent wickelt und existierende Anwendungen parallelisiert.

Dr. Tobias Schüle war nach seinem Studium der Informatik mehrere Jahre in Forschung und Lehre auf dem Gebiet des Entwurfs und der Verifikation eingebette ter Systeme tätig. Heute ist er ebenfalls Mitarbeiter bei Siemens Corporate Technology. Sein Hauptinteresse gilt neben parallelen Programmiermodellen der Architektur und Implementierung von Multicore-Software.

Urs Gleim · Tobias Schüle

Multicore-Software

Grundlagen, Architektur und Implementierung in C/C++, Java und C#

Urs Gleim
urs.gleim@siemens.com

Tobias Schüle
tobias.schuele@siemens.com

Lektorat: Dr. Michael Barabas
Copy-Editing: Annette Schwarz, Ditzingen
Herstellung: Birgit Bäuerlein
Umschlaggestaltung: Helmut Kraus, www.exclam.de
Druck und Bindung: M.P. Media-Print Informationstechnologie GmbH, 33100 Paderborn

Bibliografische Information der Deutschen Nationalbibliothek
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.

ISBN:
Buch 978-3-89864-758-8
PDF 978-3-86491-080-7
ePub 978-3-86491-081-4

1. Auflage 2012
Copyright © 2012 dpunkt.verlag GmbH
Ringstraße 19 B
69115 Heidelberg

Die vorliegende Publikation ist urheberrechtlich geschützt. Alle Rechte vorbehalten. Die Verwendung der Texte und Abbildungen, auch auszugsweise, ist ohne die schriftliche Zustimmung des Verlags urheberrechtswidrig und daher strafbar. Dies gilt insbesondere für die Vervielfältigung, Übersetzung oder die Verwendung in elektronischen Systemen.
Es wird darauf hingewiesen, dass die im Buch verwendeten Soft- und Hardware-Bezeichnungen sowie Markennamen und Produktbezeichnungen der jeweiligen Firmen im Allgemeinen warenzeichen-, marken- oder patentrechtlichem Schutz unterliegen.
Alle Angaben und Programme in diesem Buch wurden mit größter Sorgfalt kontrolliert. Weder Autor noch Verlag können jedoch für Schäden haftbar gemacht werden, die in Zusammenhang mit der Verwendung dieses Buches stehen.

5 4 3 2 1 0

Vorwort

Warum dieses Buch?

Multicore-Prozessoren verändern die Softwareentwicklung. Diese Aussage ist zurzeit vielfach zu hören. Es gibt Diskussionen über neue oder wiederentdeckte Programmiermodelle bzw. -sprachen, und Hersteller von Entwicklungswerkzeugen suchen nach höheren Abstraktionsebenen für Parallelität. Auch die in der Softwareentwicklung bereits etablierten Sprachen erhalten mit jeder neuen Version zusätzliche Funktionen und Spracherweiterungen, die dem »parallelen Zeitalter« geschuldet sind. Obwohl zurzeit niemand sagen kann, welche Ansätze sich langfristig durchsetzen werden, besteht weitgehende Einigkeit darin, dass kein Weg an Parallelität vorbeiführt. Mit diesem Buch möchten wir dem Leser die Grundlagen der Entwicklung paralleler Software an die Hand geben, die es ihm ermöglichen, die richtigen Entwurfs- und Implementierungsentscheidungen zu treffen.

An wen richtet sich das Buch?

Das Buch richtet sich an Informatiker, Softwarearchitekten und -entwickler, die einen Einblick in die Programmierung von Multicore-Systemen bekommen oder bereits vorhandene Kenntnisse vertiefen möchten. Es werden keine Vorkenntnisse über parallele Programmierung oder Multicore-Systeme vorausgesetzt. Der Leser sollte jedoch mit mindestens einer objektorientierten Programmiersprache vertraut sein und über Erfahrung in der Softwareentwicklung verfügen.

Aufbau des Buches

Der erste Teil des Buches behandelt die Grundlagen und deckt die wesentlichen Aspekte paralleler Systeme ab. Wir beginnen mit einem kurzen Streifzug durch die Architektur paralleler Prozessoren und gehen anschließend auf Threads und Synchronisationsmechanismen, die klassischen Konzepte paralleler Programmierung, ein. Im Kapitel über Task- und Datenparallelität beschreiben wir spezielle Programmiermodelle, die zunehmend Einzug in die gängigen Sprachen und Bibliotheken halten. Es folgt eine Betrachtung der für die parallele Programmierung wichtigsten Datenstrukturen und deren Synchronisationsstrategien. Im Anschluss geben wir einen Überblick über gängige Entwurfsmuster für die Entwicklung paralleler Software und schließen den ersten Teil mit einem Kapitel über die Besonderheiten beim Entwurf paralleler Architekturen.

Der zweite Teil gibt einen kompakten Einstieg in die parallele Programmierung mit C/C++, Java und .NET. Im Kapitel über C/C++ beschreiben wir zunächst die grundlegenden Schnittstellen von Windows und Unix-basierten Systemen für die Programmierung mit Threads. Außerdem gehen wir auf die entsprechenden Mechanismen im aktuellen C++-Standard aus dem Jahr 2011 ein. Es folgt ein Überblick über die Spracherweiterung OpenMP und die C++-Bibliothek TBB. Sowohl Java als auch C# bieten in den neuesten Versionen neben den bekannten Threadschnittstellen viele Erweiterungen für die parallele Programmierung an, auf die wir in den nachfolgenden Kapiteln eingehen. Abschließend werfen wir einen Blick auf funktionale Sprachen, aktorbasierte Programmierung und transaktionsbasierten Speicher.

Ziel des zweiten Teils ist es, einen Überblick über die verfügbaren Mittel für die parallele Programmierung zu vermitteln. Wie konzentrieren uns auf die wesentlichen Konzepte und verzichten auf eine detaillierte Behandlung aller Funktionen. Dieses Buch ersetzt daher nicht die Dokumentation zu den vorgestellten Schnittstellen.

Danksagungen

Wir danken unseren Kollegen und Studenten für die vielen Diskussionen über die Inhalte dieses Buches. Herauszuheben sind Thomas Henties und Andreas Wilhelm für zeitaufwendiges Korrekturlesen und viele hilfreiche Kommentare. Aufseiten des dpunkt.verlags gilt unser Dank insbesondere Michael Barabas und allen Mitarbeitern, die zur Entstehung des Buches beigetragen haben. Außerdem danken wir Annette Schwarz für das Lektorat und Johannes Link für die konstruktiven Verbesserungsvorschläge.

Im Besonderen bedanken wir uns bei unseren Familien für die Unterstützung und die Geduld an den vielen langen Abenden und Wochenenden, an denen dieses Buch entstanden ist.

Urs Gleim und Tobias Schüle
München, November 2011

http://www.multicore-software.de

Inhaltsverzeichnis

I    Grundlagen der parallelen Programmierung

1

Einführung

1.1

Paradigmenwechsel in der Softwareentwicklung

1.2

Anwendungsbereiche

1.3

Parallelität in der Hardware

1.3.1

Prozessorarchitektur

1.3.2

Multicore-Prozessoren und Multiprozessorsysteme

1.4

Parallelität in der Software

1.4.1

Prozesse und Threads

1.4.2

Virtualisierung

1.4.3

Parallelisierende Compiler

1.4.4

Parallele Bibliotheken

1.4.5

Amdahl’sches Gesetz

2

Threads

2.1

Arbeiten mit Threads

2.1.1

Erzeugung und Beendigung

2.1.2

Datenaustausch

2.1.3

Threadpools

2.2

Scheduling

2.2.1

Lastverteilung

2.2.2

Affinitäten und Prioritäten

2.3

Speicherzugriff

2.3.1

Speichermodelle

2.3.2

Speicherhierarchie

3

Synchronisation

3.1

Konflikte

3.1.1

Entstehung

3.1.2

Kritische Abschnitte

3.2

Synchronisationsmechanismen

3.2.1

Mutexe

3.2.2

Scoped Locking

3.2.3

Monitore

3.2.4

Lese-/Schreibsperren

3.2.5

Semaphore

3.2.6

Bedingungsvariablen

3.2.7

Barrieren

3.2.8

Einmalige Ausführung

3.2.9

Atomare Operationen

3.2.10

Spinlocks

3.3

Fallstricke und Richtlinien

3.3.1

Konflikterkennung

3.3.2

Verklemmungen

3.3.3

Nichtdeterminismus

3.3.4

Fairness

3.3.5

Skalierbarkeit

3.3.6

Threadsicherheit und Wiedereintrittsfähigkeit

3.3.7

Schnittstellenentwurf

4

Task- und Datenparallelität

4.1

Taskparallelität

4.1.1

Erzeugung und Synchronisation von Tasks

4.1.2

Parallelisierung rekursiver Algorithmen

4.1.3

Taskgruppen

4.1.4

Spekulation

4.1.5

Implementierung eines Task-Schedulers

4.1.6

Programmierrichtlinien

4.2

Datenparallelität

4.2.1

Schleifen ohne Datenabhängigkeiten

4.2.2

Reduktionen

4.2.3

Präfixberechnungen

4.2.4

Partitionierung und Abbildung

5

Datenstrukturen

5.1

Threadsicherer Zugriff

5.1.1

Grobgranulare Synchronisation

5.1.2

Feingranulare Synchronisation

5.1.3

Optimistische Synchronisation

5.1.4

Nichtblockierende Synchronisation

5.1.5

Weitere Optimierungen

5.2

Auswahl der richtigen Datenstruktur

5.2.1

Kriterien

5.2.2

Listen

5.2.3

Vektoren

5.2.4

Assoziative Felder

5.2.5

Warteschlangen und Stacks

5.2.6

Multimengen

6

Entwurfsmuster

6.1

Zugriff auf gemeinsame Daten

6.1.1

Grundlegende Synchronisationsmuster

6.1.2

Threadlokaler Speicher

6.1.3

Futures

6.1.4

Synchronisationsproxy

6.1.5

Active Object

6.2

Zerlegung in parallel bearbeitbare Teilprobleme

6.2.1

Grundlegende Zerlegungsmuster

6.2.2

Master-Slave

6.2.3

Erzeuger-Verbraucher

6.2.4

Aktoren

6.2.5

Reihenfolgebewahrender Threadpool

6.3

Fließbandverarbeitung

6.3.1

Pipelines

6.3.2

Pipelines mit parallelen Stufen

6.3.3

Parallele Pipelines

7

Architektur paralleler Software

7.1

Entwurf paralleler Algorithmen

7.2

Entwurf paralleler Architekturen

II    Sprachen und Bibliotheken

8

Threads und Synchronisation in C/C++

8.1

POSIX-Threads

8.1.1

Threads

8.1.2

Synchronisationsmechanismen

8.1.3

Threadlokaler Speicher und Speicherallokation

8.2

Windows-Threads

8.2.1

Threads

8.2.2

Synchronisationsmechanismen

8.2.3

Threadlokaler Speicher und Speicherallokation

8.2.4

Threadpools

8.3

C++11

8.3.1

Lambda-Funktionen

8.3.2

Threads

8.3.3

Synchronisationsmechanismen

8.3.4

Threadlokaler Speicher und Speicherallokation

8.3.5

Speichermodell

9

OpenMP

9.1

Threads

9.1.1

Parallele Bereiche

9.1.2

Arbeitsteilung

9.1.3

Speicherzugriff

9.1.4

Threadlokaler Speicher

9.2

Synchronisationsmechanismen

9.2.1

Kritische Abschnitte

9.2.2

Mutexe

9.2.3

Barrieren

9.2.4

Einmalige Ausführung

9.2.5

Atomare Operationen

9.3

Taskparallelität

9.3.1

Parallelisierung rekursiver Algorithmen

9.3.2

Variablenzugriff

9.3.3

Suspendierung

9.4

Datenparallelität

9.4.1

Schleifen ohne Datenabhängigkeiten

9.4.2

Reduktionen

9.4.3

Partitionierung und Abbildung

9.5

Speichermodell

10

Threading Building Blocks

10.1

Synchronisationsmechanismen

10.1.1

Sperren

10.1.2

Atomare Operationen

10.2

Taskparallelität

10.2.1

Parallele Funktionsaufrufe

10.2.2

Taskgruppen

10.2.3

Task Scheduler

10.3

Datenparallelität

10.3.1

Schleifen ohne Datenabhängigkeiten

10.3.2

Reduktionen

10.3.3

Präfixberechnungen

10.4

Datenstrukturen

10.4.1

Assoziative Felder und Mengen

10.4.2

Warteschlangen

10.4.3

Vektoren

10.5

Algorithmen und Entwurfsmuster

10.5.1

Sortieren

10.5.2

Fließbandverarbeitung

10.5.3

Flussgraphen

10.6

Threadlokaler Speicher

10.7

Speicherallokation

10.8

Ausnahmen und Abbruch

11

Parallele Programmierung mit Java

11.1

Threads

11.1.1

Threaderzeugung

11.1.2

Threadpools

11.1.3

Threadlokaler Speicher

11.2

Synchronisationsmechanismen

11.2.1

Sperren

11.2.2

Spezielle Synchronisationsmechanismen

11.2.3

Atomare Operationen

11.3

Taskparallelität

11.3.1

Tasks und Futures

11.3.2

Starten von Tasks

11.3.3

Rekursive Tasks

11.3.4

Blockierende Operationen in Tasks

11.4

Datenparallelität

11.5

Datenstrukturen

11.6

Speichermodell

12

Parallele Programmierung mit .NET

12.1

Threads

12.1.1

Threaderzeugung

12.1.2

Threadpools

12.1.3

Threadlokaler Speicher

12.2

Synchronisationsmechanismen

12.2.1

Sperren

12.2.2

Spezielle Synchronisationsmechanismen

12.2.3

Atomare Operationen

12.2.4

Einmalige Ausführung

12.3

Taskparallelität

12.3.1

Tasks und Futures

12.3.2

Fortsetzungstasks

12.4

Datenparallelität

12.4.1

Schleifen ohne Datenabhängigkeiten

12.4.2

Parallele Aggregation

12.4.3

PLINQ

12.5

Datenstrukturen

12.6

Ausnahmen und Abbruch

12.7

Speichermodell

13

Blick über den Tellerrand

13.1

Funktionale Sprachen

13.2

Aktorbasierte Programmierung

13.3

Transaktionsbasierter Speicher

Literaturverzeichnis

Index

Teil I

Grundlagen der parallelen Programmierung

1 Einführung

Parallele Programmierung ist nichts Neues. Sie beschäftigt die Informatik schon seit den 1960er-Jahren. Hauptanwendung war lange Zeit das Lösen von numerischen Problemen auf Parallelrechnern im wissenschaftlichen Umfeld. Mit kommerziell nutzbaren Anwendungen, vorwiegend aus dem Bereich der Simulation, fand das parallele Rechnen weite Verbreitung. Einsatzbereiche dafür sind unter anderem die Baustatik, Strukturberechnungen im Maschinenbau, Crashtestsimulationen im Fahrzeugbau, Strömungssimulationen in der Luft- und Raumfahrttechnik und die Wettervorhersage. Heutzutage sind wir alle zumindest indirekt Anwender parallel arbeitender Systeme. So nutzen wir Suchmaschinen im Internet, unsere Kontobewegungen werden von den Datenbanksystemen der Banken verwaltet, und wenn wir in den Urlaub fliegen, sind bei der Buchung und der gesamten Logistik des Flugbetriebs ebenfalls entsprechende Systeme im Einsatz.

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!