Parallelprogrammierung mit der TPL und.NET 4.0 Bernd Marquardt – bm@go-sky.de

Parallelprogrammierung mit der TPL und .NET 4.0

Bernd Marquardt – bm@go-sky.de

Agenda

EinführungSchleifen parallelisierenCode-Bereiche parallelisierenAufgaben parallelisierenWeitere spezielle Themen

PLINQ, Exceptions, Cancelation, Containerklassen

Testen und DebuggenWindows und ParallelprogrammierungZusammenfassung

Einführung

Bisher:Alle 2-3 Jahre wurden die CPU‘s doppelt so schnell

Davon haben unsere Programme automatisch etwasDeutlich sichtbar bei mathematischen Berechnungen, weniger sichtbar bei UI-Angelegenheiten

Einführung

Intel Clock SpeedQuelle: Intel, Wikipedia

Einführung

Prozessor-Takt bleibt bei 3 – 4 GHz stehen

Mehr geht nicht: Kühlung wird schwierigEigentlich müssten unsere CPU‘s jetzt ca. 100 GHz können

Anzahl der Transistoren auf einem Chip steigt aber weiter an

Resultat: Multi-Core CPU‘s kommen immer stärkerMehrere CPU‘s auf einem Chip

Einführung

Programmierung für Multi-Core CPU‘s Multi-Processing (gibt uns das Betriebssystem)Multi-Threading (müssen wir im Moment noch selbst programmieren)

Wir müssen unsere Programme anpassen, sonst haben wir nichts von dem Multi-Core CPU‘s in einer Anwendung

EinführungAndere Parallelisierungs-Technologien:

Multithreading, ThreadpoolManaged und unmanaged Code

OpenMP (C, C++)Managed und unmanaged Code

MPI (Message Passing Interface) (C, C++, FORTRAN)

Jetzt auch managed für .NET MPI.NET

NEU: Parallel Extensions for .NET (TPL)Eine Erweiterung für C# und VB.NETNur managed Code

NEU: Parallel Pattern Library (PPL)Eine Erweiterung für C++ in VS 2010Nur native Code

Einführung

ACHTUNG:

Normale Multithread-Programmierung ist NICHT einfach!

Höherer AufwandDebuggingFehlersucheTestingSynchronisierungPlanung

(1-P

)P

Tse

rial

(1-P

)

P/2n = number of processorsn = number of processors

Tparallel = {(1-P) + P/n} Tserial

Speedup = Tserial / Tparallel

0.5 + 0.25

1.0/0.75 = 1.33

n = 2n = ∞

P/∞

…

0.5 + 0.0

1.0/0.5 = 2.0

Sequentieller Code begrenzt das Speedup!

+ O

Einführung – Amdahls Gesetz

Einführung – Amdahls Gesetz

Dies bedeutet, dass die parallelen Arbeitseinheiten groß genug sein müssenAnsonsten dauert die Thread-Initialisierung länger, als die Parallelisierung einbringt

Installation

Nur Visual Studio 2010/.NET 4.0 NICHT mit VS 2008 (CLR 4 wird benötigt)

Betriebssysteme:Windows Server 2003/2008/2008 R2Windows XPWindows VistaWindows 7

Einführung

Die TPL nutzt Threads aus dem .NET-ThreadPoolThreads aus dem ThreadPool bedeutet:

Schnelle Bereitstellung von ThreadsDadurch sind auch kleinere Aufgaben gut zu parallelisierenDie Threads müssen aber an den Pool zurückgegeben werden

TestThreadPool

demo

Parallelerweiterungen für LinqEs gibt zwei Möglichkeiten:

System.Linq.ParallelEnumerable-KlasseAsParallel-Erweiterungsmethode

Ziel: Parallele Datenabfragen mit LinqSehr einfachWAS-Programmierung statt WIE-Programmierung

Demo 3, ParallelBabyNames

demo

Schleifen parallelisieren

Wichtige Klasse:System.Threading.Tasks.Parallel

Schleifen werden aufgeteilt auf mehrere Threads aus dem ThreadPoolDas geht nur, wenn die einzelnen Schleifendurchläufe unabhängig voneinander sind

Problem z.B.: a[i] = a[i – 1] * 2

Schleifen parallelisieren

WICHTIG:„Nach“ der Schleife werden alle Threads synchronisiert, welche die Schleife abgearbeitet habenIn der Schleife können Variablen deklariert werden, die „thread-local“ sindDie Laufvariable darf nicht als lokale Variable deklariert werden

Demo 4, Demo 5, Demo 6

demo

Schleifen parallelisieren

Auch foreach-Schleifen können parallelisiert werdenDie Reihenfolge der Schleifendurchläufe ist nicht deterministisch

Demo 4A

demo

Schleifen parallelisieren

Achtung: Bei „unausgewogenen“ Schleifen muss etwas mehr in der Bibliothek passierenBeispiel:

for(int i = 0; i < 1000; i++){ if(i < 500) { DoLongCalculation(); } else { DoShortCalculation(); }}

Schleifen parallelisieren

Diese Schleife wird nicht „halbiert“Es werden kleine Arbeitseinheiten gemachtSobald ein Thread mit einer Arbeitseinheit fertig ist, bekommt er die nächste, bis die Arbeit komplett erledigt ist Schleifen-PartitionierungDas implementierte Standard-Verfahren ist sehr leistungsfähig

Schleifen: Eigene Partitionierung

Man kann eigene Partitionierungsverfahren implementierenInteressant, bei Schleifen mit…

…sehr kleinem Schleifen-Body…extrem unausgewogenen Schleifen

Performance ist abhängig von einer vernünftigen Schleifen-Partitionierung

Partitioner

demo

Probleme mit Schleifen

Achtung bei schreibendem Zugriff auf Klassenvariablen oder statischen Variablen

Keine Fehlermeldungen (vom Compiler, Runtime)Ergebnisse sind falsch ( „Data Race“)

REGEL: Es darf nur ein Thread gleichzeitig schreibend zugreifenGgf. synchronisieren, d.h., schreibende Zugriffe werden nacheinander abgewickeltAchtung: Performance!

Probleme mit Schleifen

Schleifendurchläufe sind nicht unabhängig voneinanderD.h., in Schleifendurchlauf #i wird auf Daten zugegriffen, die im Schleifendurchlauf #j berechnet werden, wobei gilt: i != jZ.B.: a[i] = a[i-1] + 1Abhilfe: Den Algorithmus ändern

Werte, die in der Schleife benötigt werden, möglichst aus dem Index berechnen

Aggregationen

Zusammenfassen von ErgebnissenAchtung: Meistens ist Locking erforderlichTypischer Anwendungsfall:double dSum = 0.0;

for(int i = 0; i < 1000; i++){ dSum += Math.Sqrt(i);}

Aggregationen

Zwischenwerte werden über den sog. ThreadLocalState weitergegebenAblauf:

Vor der Schleifenabarbeitung: LocalState initialisierenSchleifenteil abarbeiten: Im Thread rechnen, LocalState benutzenNach der Abarbeitung der Teilschleife: Aggregation (Zusammenfassung) der Ergebnisse (Achtung: Locking!!!)

Aggregationen

Das Ziel ist, möglichst WENIG Locking-Operationen durchzuführenMöglichkeit #1: In jedem Schleifendurchlauf beim Zugriff (Addition) auf dSum findet ein Lock stattMöglichkeit #2: Zwischensumme einer Arbeitseinheit ermitteln, Zwischensumme mit Locking zu dSum addieren

Aggregationen

int iSum = 0;

Parallel.For(0, 1000, // From, To () => 0, // Init// (Laufvariable, ParallelLoopState, ThreadLocalState) (i, pls, tls) => { // Loop body tls += i; return tls; }, (partSum) => { // Aggregation Interlocked.Add(ref iSum, partSum); });

Agg1, Agg2

demo

Schleifen abbrechen

Wenn mehrere Threads für die Schleife parallel laufen, dann müssen alle Threads beendet werdenKlasse ParallelLoopResult benutzen

Berechnung beendet?

Klasse ParallelLoopState enthält Break-Methode und eine Stop-Methode

Alle Threads werden beendet

LoopBreakTest

demo

Tipps und Tricks

Parallel.For und Parallel.ForEach:(Anzahl der Durchläufe * Dauer) muss groß genug sein

Nicht vergessen: Amdahl‘s Gesetz!Möglichst wenig Synchronisierung verwenden

Beispiele und PerformanceInnere und äußere SchleifeSchleifendurchläufe mit stark unterschiedlicher DauerMatrixmultiplikationPrimzahlen berechnen

InnerOuter, MatMult,PrimeSeq, PrimePar

demo

Performance MatMult (2 Core)Größe Sequentiell

Parallel5 0.0017 0.0223 ms10 0.0111 0.0254 ms25 0.1687 0.1830 ms50 1.3953

1.2970 ms100 11.207 9.300 ms250 185.41 94.81 ms500 1950.8 978.0 ms

Anzahl der Threads

Die Anzahl der zu verwendenden Threads wird mit der ParallelOptions–Klasse definiertMaxDegreeOfParallelism = -1 Alle Kerne und Prozessoren werden ausgenutztIn bestimmten Fällen kann es auch sinnvoll sein, die Anzahl der benutzten Threads auf > Kerne * Prozessoren zu setzen

Demo2010_1

demo

Codeblöcke parallelisieren

Unabhängiger Code kann parallel ausgeführt werdenHäufigstes Problem: Gleichzeitiger Zugriff auf die gleichen Daten (schreibend)Ohne Nachdenken geht da gar nichts!Wichtige Methode: Parallel.InvokeAuch hier: Unterschiedliche

Schreibweisen möglich…

Demo 7, Demo 8

demo

Die Klasse Task

Die Task-Klasse wird benötigt, um erweiterte Parallelisierungprobleme zu lösenVergleichbar mit der ThreadPool-Klasse:

…ist ähnlich wie:

ThreadPool.QueueUserWorkItem(delegate { … });

Task.Factory.StartNew(delegate { … });

Tasks

Die TPL benutzt nun den .NET ThreadPool als Standard-SchedulerDer ThreadPool hat mehrere Vorteile:

Work-stealing queues werden intern in der TPL benutztHill-climbing-Methoden, wurden eingeführt, um die optimale Thread-Anzahl zu ermittelnSynchronisierungsmechanismen (wie SpinWait und SpinLock) werden intern verwendet

Tasks: WSQ

Die Klasse Task

Wichtige Features:Synchronisierung von parallelen Ausführungseinheiten

Task.Wait(), WaitAll(), WaitAny()

Abbrechen von Ausführungseinheiten Cancelation Framework

Demo 10, Demo 11

demo

Tasks und Parameter

Übergabe von Parametern im Funktionsaufruf möglichAchtung: Seiteneffekte, wenn man es falsch machtÜbergabe der Parameter mit Parametern der Lambda-Funktion

Demo 12_Falsch, Demo 12_Correct

demo

Task-Parameter

Tasks können kontrolliert werden……Created…WaitingForActivation…WaitingToRun…RanToCompletion…Canceled…Faulted…WaitingForChildrenToComplete

Tasks in Schleifen

Tasks sind gut in sehr unausgewogenen Schleifen

for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++) { for(int k = 0; k < i; k++) { for(int l = 0; l < k; l++) { // Do Work… } } }}

Tasks in Schleifen

Lösung 1: Schleife (außen) mit Parallel.For parallelisierenAchtung: Die Schleifendurchläufe werden zum Schluss immer länger

Der Scheduler kann die Teilschleifen nur schlecht aufteilen, so dass alle Prozessoren gleichmäßig ausgelastet sind

Lösung: Schleifen „rückwärts“ laufen lassen und Tasks benutzen (Task mit dem beiden inneren Schleifen)

MuchLoops, MuchLoopsTask

demo

Die Klasse Task<TResult>

Die Klasse ermöglicht die asynchrone Berechnung von Daten

Wenn später dann die berechneten Daten weiter benutzt werden sollen, wird geprüft, ob die Berechnung bereits abgeschlossen istSonst wird gewartet…. = Synchronisierung

Kann man Task<TResult>-Variablen in Anwendungen mit einer Benutzerschnittstelle benutzen?

Demo 13, Demo 14, FutureWinForms, …WPF,FutureWinForms2, …LINQ

demo

Concurrent Exceptions

In normalen, sequentiellen Anwendungen kann zu einer bestimmten Zeit maximal EINE Exception geworfen werdenBei parallelen Anwendungen können auch mehrere Exceptions zu einem Zeitpunkt geworfen werdenOft werden die Exceptions dann auch noch in einem anderen Thread verarbeitet, als in dem Thread, in dem sie geworfen wurden

Concurrent Exceptions

Paralleler Code:Reihenfolge, mehrere Exceptions!!

Darum gibt es einen anderen Exception-Mechanismus in den Parallel Extensions Wenn eine Exception im Parallel-Code auftritt, werden alle Threads - so schnell wie möglich - angehaltenAchtung: In dieser Zeit können eventuell noch weitere Exceptions auftreten!

Concurrent Exceptions

Alle aufgetretenen Exceptions werden in einem Objekt der Klasse System.Threading.AggregateException eingesammeltWenn alle Threads angehalten sind, dann wird die AggregateException neu geworfen und kann bearbeitet werdenDie einzelnen Exceptions können über das Property InnerExceptions abgefragt werden (eine Collection der aufgetretenen Exceptions)

Concurrent Exceptions

Welche Klassen werfen AggregateException-Objekte?

Die Parallel-KlasseDie Task-KlasseDie Task<TResult>-KlasseParallel LINQ (Abfragen)

Demo 15

demo

Synchronisierung

Die Synchronisierung soll den Zugriff auf begrenzte Resourcen des Rechners steuern, wenn mehrere Threads gleichzeitig darauf zugreifen wollen

Variablen (RAM)CodeteileLPT-, COM- und USB-Schnittstellen

Synchronisierung

Eine Synchronisierung beinhaltet immer die Gefahr eines „Deadlocks“

Thread A wartetauf dieResource

Thread B hat dieResource inBenutzung

Thread B wartetauf Thread A

Synchronisierung

Allgemeine Regeln:

Nicht zu viel synchronisieren LangsamNicht zu wenig synchronisieren FalschDie richtige Sychronisierungsmethode wählenKeine eigenen Synchronisierungselemente programmieren Schwierig

Synchronisierung

Standard-Synchronisierungsmechanismen:

Monitor, lock (C#)Interlocked-KlasseMutexWaitHandle

Synchronisierung

BarrierCountDownEventLazyInit<T>ManualResetEventSlimSemaphoreSlimSpinLockSpinWaitWriteOnce<T>Collections (Stack, Queue, Dictionary)

ConcurQueue

demo

TPL + UI

Die goldene Regel gilt natürlich auch hier!WPF oder WinForms laufen im STASie dürfen nur aus dem Thread auf Controls zugreifen, im dem Sie die Controls erzeugt habenAb Framework 2.0: Exception im Debug-Modus

TestWinForms

demo

TPL + UI

WindowsForms:Benutzung von InvokeRequired zum Test, ob der richtige ThreadBenutzung von BeginInvoke zum Umschalten in den richtigen Thread

Windows Presentation Foundation:Benutzung von Dispatcher.VerifyAccess oder Dispatcher.CheckAccess zum Test, ob der richtige ThreadBenutzung von Dispatcher.Invoke zum Umschalten in den richtigen Thread

TestTPLWinForms

demo

Erweiterung der Tasks

Erweiterungen zusätzlich zu ContinueWith:ContinueWhenAllContinueWhenAnyLeistungsfähiges Konzept für die Fortführung der Arbeit, wenn bestimmte Teilaufgaben erledigt sind

TaskScheduler

Die alte Klasse TaskManager wurde ersetzt durch die TaskScheduler-Klasse

Neue WorkStealing-Queues im ThreadPool

TaskScheduler ist eine abstrakte Basisklasse

Man kann davon ableiten und eigene TaskScheduler‘s programmierenInteressant für spezielle Szenarien

Z.B.: spezielle Prioritätsverwaltung

TaskSchedulerTest

demo

TaskScheduler

Ein weiteres spezielles Szenario für die Benutzung eines TaskScheduler‘s:Zugriff auf das User Interface

Die alte Regel gilt immer noch…

Ablauf:Asynchrone Berechnung im TaskFortführung mit ContinueWith (z.B. Ergebnisausgabe) – aber im korrekten Thread-Kontext ( im UI-Thread)

Früher: Benutzung von Invoke

Demo2010_Scheduler

demo

Cancellation

Einfaches „Abschießen“ (Kill) von Threads ist keine gute Lösung

Offene Dateien???Locks???Schreibende Zugriffe???Genutzte Resourcen???…???

Cancellation

Das Beenden von Threads muss kooperativ erfolgen

Der Thread kann nur an bestimmten Stellen beendet werdenDer Thread kann selbst entscheiden, wann er beendet wirdAbhängige Threads werden ebenfalls beendet

Gutes Beispiel: BackgroundWorker-Control (ab .NET Framework 2.0)

Cancellation

Anlegen eines CancellationTokenSource-ObjektesDas CancellationToken-Objekt wird an alle Threads übergeben, die über das eine Source-Objekt beendet werden könnenIn den Threads wird das Token-Objekt über das Property IsCancellationRequested abgefragtAlle Threads des Source-Objekts werden über die Cancel-Methode des Source-Objektes beendet

Cancellation

Ggf. wird dann aufgeräumtNach dem Aufräumen wird aus dem Thread eine OperationCanceledException geworfenDiese kann im aufrufenden (Main-) Thread eingefangen und verarbeitet werden

CancelTest1, TaskCancel

demo

Testen und Debuggen

…ist in parallelen Programmen gar nicht so einfachParallelprogrammierung hat meistens einen Grund: Performance-SteigerungMessgrößen sind also:

Richtigkeit des ErgebnissesAusführungszeit

Testen und Debuggen

Häufiges Problem:Die Anwendung skaliert nicht mehr mit Erhöhung der Prozessoranzahl

0

2

4

6

8

10

12

1 2 3 4 5 6 7 8 9 10 11 12

Zeit

Testen und DebuggenPerformance-Tests mit Visual Studio

Visual Studio: TestPerf

demo

Debugging

Es gibt zwei neue Debugging-Fenster in Visual Studio 2010

Fenster: Parallel TasksFenster: Parallel Stacks

Für native und für managed CodeDie Fenster können geöffnet werden, wenn ein Breakpoint angelaufen wurdeDebug > Windows > Parallel TasksDebug > Windows > Parallel Stacks

Debugging

Parallel Tasks-Fenster:Unterstützung des Task-basierten ProgrammierensAuflistung aller Tasks

Waiting, Running, Scheduled,…

Ausgaben können konfiguriert und gruppiert werden

Debugging

Parallel Stacks-Fenster:In modernen Anwendungen laufen oft mehrere Threads gleichzeitigDas Fenster zeigt die hierarchische Aufrufreihenfolge von Threads an

…siehe Call-Stack (ohne Threading-Info‘s)

Ausgaben können in unterschiedlicher Weise dargestellt werden

TopDown, BottomUp, Zooming, Panning,…

Visual Studio: TestDebug

demo

Debugging

Suche nach Deadlocks ist mit dem VS-Debugger möglichBenutzung des Parallel-Tasks-Fensters

Visual Studio: TestDead

demo

Debugging

Ausgaben werden meistens mit Console.WriteLine(…) gemachtProblem: Console.WriteLine(…) blockiert alle Threads, damit die Ausgabe auch lesbar sindDadurch wird natürlich das „laufende“ Threading stark beeinflusst und es können nicht erwünschte Zustände entstehenLösung: Console-Ausgabe entkoppeln

ConsoleEx

demo

DataBinding mit ThreadingEigentlich sollte DataBinding mit MultiThreading Schwierigkeiten machenD.h., die Business-Logik läuft in einem anderen Thread, als das User InterfaceDas ist auch so – bis einschließlich .NET Framework 2.0

Siehe Beispiel

WPF-DataBinding mit ThreadingBei WPF hat Microsoft etwas weiter gedacht… Vor der Ausführung des Bindings wird geprüft, ob der richtige Thread benutzt wird

Wenn nicht, wird mit Dispatcher.Invoke umgeschaltet

DataBinding mit WPF und MultiThreading ist also kein großes Problem…ab einschl. .NET Framework 3.0Funktioniert nicht bei Windows Forms!

Test_Binding_WPF

demo

Zusammenfassung

Es gibt neue Möglichkeiten, um Code zu parallelisierenWir müssen keine Threads mehr explizit erzeugenSchleifen sind einfach zu parallelsierenCode ist besser zu lesen, als mit einzelnen ThreadsAuch Codeblöcke kann man einfach paralellisieren

Zusammenfassung

Trotzdem gibt es Fälle, bei denen eine Parallelisierung nichts bringt

Testen, Prototyp erstellenGgf. seriellen Code verwenden

Die Klassen Task und Task<T> ermöglichen die präzisere Steuerung des parallelen CodesParallel Linq bietet einfachere Möglichkeiten der parallelen Programmierung, als die bisherige Anwendung von normalen Threads

WeitereInfo‘s

Links:

OpenMP: http://www.openmp.orgMPICH2: http://www.mcs.anl.gov/research/projects/mpich2/

Parallel Extensions for the .NET Framework (Juni CTP): http://www.microsoft.com/downloads/details.aspx?FamilyID=e848dc1d-5be3-4941-8705-024bc7f180ba&displaylang=en

FRAGEN?