close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Futures, Scheduling und Work Distribution - ShareLaTeX

EinbettenHerunterladen
Ein Draft
Christian Deckert
Magic University
1
Contents
1 Einleitung
1
2 Analyzing Parallelism
2
3 Realistic Multiprocessor Scheduling
5
4 Work Distribution
6
5 Work-Strealing Dequeues
7
2
1
Einleitung
Der folgende Text beschftigt sich mit der Zerlegung von bestimmten Aufgaben
in Teilaufgaben, die parallel ausgefhrt werden knnen. Es wird das Konzept eines
Futures eingefhrt, die Art des Schduling auf User und System Ebene besprochen,
sowie ein Ansatz zur Arbeitsverteilung vorgestellt. ...
Im Folgenden wird gezeigt wie Aufgaben in Teilaufgaben zerlegt und dann
von mehreren Threads erledigt werden knnen. Die Auswahl des optimalen Zerlegungsmodells hngt dabei von der Art der Aufgabe ab. Einige Aufgaben lassen
sich natrlich in mehrere Threads zerlegen. Beispielsweise sind Webserver prdestiniert dazu pro Request einen eigenen Thread zu starten. Wiederum andere
Probleme tendieren dazu sich einfach in Consumer und Producer einteilen zu
lassen. In diesem Text sollen Aufgaben betrachtet werden, denen eine Parallelisierbarkeit innewohnt, aber bei denen eine einfache Lsung nicht offensichtlich
ist. Als Beispiel fr eine solche Aufgabe soll die Berechnung einer Finbonacci Zahl
nach dem in Abbildung 1 beschriebenen Code dienen.
output : f ibvonXinput : (X)IF X > 1Returnf ib(X−1)+F ib(X−2)ElseReturn1
Der folgende Text beschftigt sich mit der Zerlegung von Problemen in einzelne
Komponenten, die parallel ausgefhrt werden knnen. Dabei werden die daraus
entstehenden Herausforderungen und Lsungen aufgezeigt.
Bei der Parallelisierbarkeit von Programmen lsst sich grob zwischen drei
Arten von Problemen unterscheiden. (1) Probleme, die sich natrlich in einzelne
Threads aufteilen. Zu diesen zhlen beispielsweise Web-Server, die pro Request
einen eigenen Thread starten knnen. (2) Producer-Consumer-Probleme bei
denenen Ergebnisse von einem Producer generiert werden und von einem Konsumenten verarbeitet werden. Im folgenden Text konzentrieren wir uns auf
Probleme, deren Mglichkeit zur Parallelisierung in ihnen selbst innewohnt.
Das Ziel bei der Parallelsierung von Inhalten ist es nicht nur das Programm
in einzelnen parallelsierbare Teile aufzuteilen, sondern dies auch auf einem effektivem Weg zu tun und dabei die entstehenden Threads zu managen.
Als Beispiel fr ein solches Problem ist die Multiplikation von Matrizen.
(C) =∑
(A) * (B)
ci j = k = 0n−1 ai k ∗ bk j
Die einfachste Mglichkeit dieses Problem zu parallelisieren ist es fr jedes
einzelne Ergebnis ci jeineneigenenT hreadzustarten.
Eine solche Implementierung ist jedoch wenig ideal, vergleichweise viele kurzlebige Threads mssen gestartet und wieder beendet werden. Dadurch tritt
nicht nur beim Schedulen der einzelnen Threads, da jeder Thread eine bestimmte Resourcen bentigt wie beispielsweise Arbeitsspeicher, Zeit zum Setup
und Teardown eines Thread sowie Scheduler overhead.
Dadurch entsteht eine ungnstiges Verhltnis zwischen zu leistender Arbeit
und damit verbundenem Overhead.
Um das Verhltnis zwischen Overhead und eigentlich zu leistender Arbeit zu
reduzieren, knnen Task-Pools eingesetzt werden.
Ein ansatz um ein solches Problem zu lsen ist die erstellung sog. Task
pools. Mehrere kurzlebige Tasks werden in diesen Pool bergeben. Einzelne
1
Worker bedienen sich aus diesem Pool und liefern die berechneten Ergebnisse
zurck. Ein weiterer Benefit dieses Systems ist, dass sie unabhngig von externen
Faktoren wie uni-core, small-scale und large scale Multiprocessoren verarbeitet
werden knnen. Je nach gegebenem Umfeld kann die optimale Anzahl an workern
gestartet werden, die wiederum tasks abarbeiten.
Diese Thread pools werden in Java executor service genannt. Tasks die keine
Ergebnisse zurckliefern werden als Runnable objects gespeichert und durchgefhrt
indem die methode run() aufgerufen wird. Tasks die ein ergebnis zurckliefern
werden als Callables implementiert. Diese Services werden per call aufgerufen.
Und knnen sig fucture¡t¿s zurckliefern. Ein solches Future ist das Versprechen,
dass ein gewisses Resultat asynchron geliefert wird, wenn es berechnet wurde.
Das Vertrauen, dass ein solches Versprechen eingehalten wird, kann uU enttuscht werden. Diese Objekte beinhalten eine get() Methode, die das resultat
zurckliefern. Ausserdem beinhaltet ein solches Future auch eine Methode um
eine task abzubrechen. Das Submitten einer Runnable task retuniert ebenfalls
ein Fucture. Das ausfhren eines futures garantiert nicht, dass eine task auch
tatschlich parallel ausgefhrt wird. Diese methoden sind ”advisory”. Sie erhlen
den darunterliegenden Exectuoren, dass sie vielleicht parallel ausgefhrt werden
knnte.
Im falle der Matritzen multiplikation werden die partitzen in n/2 by n/2
submatrizen gespeichert. Das geisst in Java backed. Diese reflektieren das
orginal.
Die Jobs werden parallel durchgefhrt. Jede dieser matritzen kann weiter
gespatet werden und dann wieder in einen pool bergeben werden.
Fibunacci beispiel.
2
Analyzing Parallelism
Im folgenden Abschnitt werden basierend auf der Arbeit von Blumofe ein Modell
zur Multithreading Berechnung, drei fundameltale Parameter von Multithreading, Arbeit, Berechnungstiefe und Aktivierungstiefe, und darauf basierende Theoreme eingefhrt.
Blumofe geht in seiner Arbeit XY davon aus, dass einzelne Aufgaben in
eigenen Threads ausgefhrt werden. Es handelt sich somit nicht um ein XY sondern um ein YX System, wobei die grundlegende Erkenntnis nicht durch die
von Blumofe gewhlte Technik beeintrchtigt ist. Eine Multithreading Berechnung besteht aus einer Menge von Aufgaben. Jede dieser Aufgaben besteht aus
untergeordneten Teilaufgaben, die in aufeinander folgender Reihenfolge durch
beispielsweise einen Thread ausgefhrt werden. Sobald alle Teilaufgaben erledigt
sind, gilt auch die Aufgabe als erledigt. In Abbildung 1 ist sind solche Aufgaben
grau hinterlegt dargestellt. Einzelne Teilaufgaben sind als Kreise dargestellt. Sie
mssen in sequenzieller Reihenfolge (von links nach rechts) ausgefhrt werden, was
durch sog. fortfahrenden Kanten dargestellt wird. Whrend des Ausfhrens einer
solchen Aufgabe ist es mglich, dass andere Aufgaben generiert werden, die parallel zur bestehenden Aufgabe ausgefhrt werden knnen. Diese werden als Kinder
2
einer Aufgabe bezeichnet. Bei der Erstellung einer solchen Kind-Aufgabe wird
im Arbeitsspeicher eine gewisse Menge an Platz reserviert, der als AktivierungsDatenblock bezeichnet wird. Dieser wird erst wieder freigegeben sobald Zur
Berechnung einer Aufgabe ist es mglich, dass Ergebnisse der Kinder-Aufgaben
herangezogen werden sog. Daten-Abhngigkeitskanten. In Abbildung 1 ist die
Erstellung einer solchen Kind-Aufgabe und das zurckliefen eines Ergebnisses
zwischen den Knoten X1 und X2 bzw. X3 und X4 durch einen Pfeil gekennzeichnet. Eine Teilaufgabe bzw. Aufgabe ist erst dann bereit fertiggestellt zu
werden, falls alle vorherigen (Teil-)Aufgaben bereits beendet wurden. Eine
Ausfhrungsreihenfolge der einzelnen Aufgaben, die dies sicherstellt wird als korrekte Ausfhrungsreihenfolge bezeichnet.
Basierend auf diesem Baum knnen die verschiedenen Parameter eines Mutlithreading Programms (Arbeit, Berechnungstiefe und Aktivierungstiefe) beschrieben
werden. Zuerst wird der Begriff der Arbeit und Berechnungstiefe eingefhrt.
Beide Begriffe stehen in Beziehung zur eigentlichen Ausfhrungszeit, danach kontentieren wir uns auf die Aktivierungstiefe, die mit dem bentigten Speicher in
Beziehung steht.
Die Parameter Arbeit und Berechnungstiefe basieren auf dem bereits dargestellten Graphstruktur einer Multithread-Berechnung. Basierend auf den Abhngigkeiten zwischen den Teilaufgaben und den Teilaufgaben selbst kann ein
azyklischer gerichterter Graph gebildet werden (Abbildung 2). Als Arbeit wird
in einem solchen Graphen die Gesamtanzahl aller Teilaufgaben bezeichnet. Sie
entspricht der Anzahl der Berechnungsschritte, die durch einen einzelnen Prozessor bentigt wird. Die Anzahl der Teilaufgaben auf dem lngsten gerichteten Pfad
(kritischer Pfad) wird als Berechnungstiefe bezeichnet.
Die Zeit, die zur Ausfhrung eines Programmes bentigt wird, lsst sich quantifizieren durch die Ausfhrungszeit auf P -Prozessoren. Wobei ein Prozessor
genau eine Aufgabe gleichteitig durchfhren kann. Daher sei die Zeit, die zur
Berechnung einer Aufgabe von P Prozessoren bentigt wird
TP = minx TP (X).
Da bei der Berechnung auf nur einem Prozessor T1 in jedem Zeitabschnitt nur
eine Aufgabe abgearbeitet werden kann, wird T1 auch als A rbeitb ezeichnet.DadieDauerderBerechnungauf
Prozessoren durch den kritischen Pfad bestimmt ist, wird T∞ auch als Berechnungstiefe bezeichnet.
Einige Werte von T werden speziell bezeichnet. So wird T1 , die Zeit zur
Berechnung von allen Teilaufgaben auf einem einzelnen Prozessor auch als Arbeit bezeichnet. Sie ist, wenn man vereinfacht von einer konstanzen Zeit fr
jede Berechnung ausgeht, gleich der Anzahl der Berechnungsschritte. In einem
Zeitschritt knnen P Prozessoren maximal P Berechnungsschritte durchfhren so
gilt: TP >= T1 /P
Ein anderes Beispiel fr eine solche Zahl ist der kritische Pfad der auch als...
bezeichnet wird.
Der Speedup auf P Prozessoren wird als Ratio aus T1 /TP . Dabei hat eine
Berechnung einen linearen Speedup falls T1 /TP = O(P ) ist. Der maximal erreichbare speedup ist T1 /T∞
Wie bereits zuvor beschrieben knnen Aufgaben eines Multithreading Pro3
gramms abhngig von anderen Aufgaben sein. XY schlgt daher vor Multithreading Prgramme als gerichteten azyklischen Graphen (GAG) zu betrachten. Jede
Aufgabe wird in einem solchen Graphen als Knoten dargestellt. Die mglichen
Abhngigkeiten zwischen einzlnen Aufgaben werden als Kanten dargestellt. Dabei
knnen mehrere Aufgaben je ein Successor bzw. Predessesor fr eine andere Task
sein.
Eine Aufgabe kann nur dann gestartet werden, wenn auch alle Successoren
fr diese Task bereits ausgefhrt wurden.
Um die Analyse eines parallelisierungsproblems zu vereinfachen wird im folgenden davon ausgegangen, dass jede Aufgabe genau gleich lange dauert und
ein Prozessor aus genau einem Kern besteht.
Basieren auf einem solchen Graph knnen diverse Werte ermittelt werden, die
zur Analyse des Parallelisierungsproblems bentigt werden.
Die Durchlaufzeit (engl. ) bezeichnet die Anzahl der Schritte die ben
Multithreaded computation can als directed acyclic graph (DAG) betrachtet
werden. Dabei ist jede task ein Node. Diese nodes sind durch Kanten miteinander verbunden und representieren auf der einen seite den Predessor und auf der
anderen den Successor einer tasks. Der successor hngt von dem Resultat des
Predessesors ab. zB ist die conventinal Threads nur eine chain von Nodes wo
jeder Node von einem anderen abhngt. Im gegensatz dazu hngt eine solche task
von mehreren Subtasks ab.
Einige Berechnungen lassen sich inherrently mehr parallelisieren als andere.
Preziesergesagt nehmen wir an, dass alle indivual berechnungsschritte diese
selbe Zeit dauern. Das wird als basis Masstatb genutzt. Sei also
TP
die minimale Zeit die bentigt wird um die Ausfhrung eines programms
durchzufhren. Dabei Sei P die menge der dedizierten Prozessoren.
TP
gibt somit die Latency an, also die Zeit die es dauert von start bis ende zu
laffen. Diese Zeit ist von einem aussenstehenden zu messen. Diese ausfhrung
kann limitiert sein zB durch die limitierung des Speichers.Einige values von T
sind so wichtig, dass sie einen speziellen Namen haben
T1 ,
die numer des Schritts needed um das programm auf einem einzelenen processor auszufhren ist die Brechnungs WORK. Work ist auch die gesamte anzahl
an schritten die in einer berechnung bentig werden.
Dann gilt Tp >= T1 /P
Ein anderes Extrem ist Ti nf, dieanzahlderschrittedesP rogrammsistunendlich.Daswirdcritical−
path−lengthgenanntweillendlicheResourcennichtbesserseinknnenalsunendlicheRessourcen.TP >=
Ti nf.
Der Speedup von P processors ist diese Ratio T1 /TP
Sagen wir mal eine Berechnung speedup linear wenn T1 /TP = O(P )
. Der maximale mgliche SPeedup von Parallelism ist
T1 /Ti nf.
Diese Daten werden anhalt des Matrizenproblems erklrt. Sei AP (N )dieanzahlderschrittediebentigtwerd
Die Work fr A1 (n) = A1 (n) = 4A1(n/2) + O(1) = O(n2 )
4
Das ist die selbe Arbeit wie notwendig ist bei einem Doppel-Loop.
Die kritische Pfadlnge ist gegeben durch
Ai f (n) = Ai nf (n/2) + O(1) = O(logn).
Sei also MP (n)dieanzahlderscrhittediezurM ultiplikationvonzweinxnmatritzennotwendigsindauf P pr
also sei M1 (n) = 8M1 (n/2) + 4A1 (n)
M1 (n) = 8M1 (n/2) + O(n2 ) = O(n3 )
Diese arbeit ist die gleiche wi bei einer conventionallen 3-nested loop implementierung. Die halb grssen Multiplikation kann gleichzeitig stattfinden daher
ist der kritische pfad
Mi nf (n) = Mi nf (n/2) + Ai nf (n)
= Mi f (n/2) + O(logn) = O(log 2 n)
Die parallesierung fr eine Matrix multiplikation ist gegeben durch M1 (n)/Mi nf (n) =
O(n3 /log 2 n)
Zur verdeutlichung wird nun eine 1000 x 1000 matrixen gewhlt. Hier kann
man bei n3 = 109 auf konventionellemundlog1000wasca10istausgehen.Andersgesagtderwahrscheinlichew
107 ist.Dasistungef hrgesprochenso : DieBerechnungknnteeineM illionenprozessorenbusyhalten.Dasistn
Man sollte nicht vergessen, dass es sich hierbei um einen Stark idealisierten
Fall handelt. Beispielsweise wurden Idle threads nicht wirklich betrachtet. Darberhinaus handelt es sich um ein programm, das mehr prozessor als memory
bentigt. dadurch performt es besser weil weniger page faults entstehen. Die
eigentliche performance of multithreaded computations bleibt auch weiterhin
ein komplexes thema. Aber iese art von Analye kann helfen das problem zu
lsen.
3
Realistic Multiprocessor Scheduling
Dieser Abschnitt beschftigt sich mit den in der Realitt austretenden Herausforderungen, die bei der Implementierung eines Multi-Thread Programms entstehen.
In unserer Analyse von Multi-Thread-Programmen wurde bisher davon ausgegangen, dass jedes Programm auf P dedizierten Prozessoren ausgefhrt wird.
Dies entspricht nicht der Realitt. Multi-Thread-Programme werden in der Regel
in Umgebungen ausgefhrt in denen weitere Programme ablaufen. Es ist zu jedem beliebigen Zeitpunkt mglich, dass weitere Programme ausgefhrt werden
und Prozessoren belegen. Programme knnen durch das System unterbrochen
werden, auf andere Ressourcen wie Festplatten waren mssen. Um diese externen Einflsse zu verwalten werden User-Level Threads, also Threads die durch
den User gestartet werden, mit Hilfe von Porgrammzhlern und stapeln verhwaltet. Die eigentliche Verteilung auf Prozesse geschieht durch System-Kernel
Scheduler. Das Programm selbst hat keinen Einfluss wann und auf welchem
Prozessor ein Thread ausgefhrt wird. Die Brcke zwischen einer Aufgabe und
dem Prozessor selbst, wird bei der Verwendung eines Multi-Thread-Programms
unter der Verwendung von Aufgaben Pools auf drei Ebenen geschlagen. Wie in
Abbildung 2 zu erkennen, werden Aufgaben aus einem Aufgaben-Pool per UserLevel Scheduler an Threads verteilt. Diese Threads werden durch das System
5
selbst wiederum mit Hilfe von Kernel-Level Scheduler auf Prozessoren verteilt.
Trotz dessen, dass eine optimale Anzahl an Threads (ein Thread pro Prozessor)
erzeugt wird, kann nicht sichergestellt werden, dass auch die selbe Anzahl an
Prozessoren dauerhaft mit der Bearbeitung dieser beschftigt ist. Daher kann
nur mit einer ∑
Durchschnittlichen Anzahl an Prozessoren gerechnet werden:
PA = 1/T (T − 1)(i = 0)pi
Um der Realtit rechnung zu tragen, sollte ein User-Level-Scheduler so designet sein, dass er keine P -Fold Speedup sondern einen PA fold speedup erreicht. Ein schdule wird als greedy bezwichnet falls die Anzahl der Programm
Schritte, das Minimum pi also die anzahl der Prozessor auslastet. In anderen
Worten wenn das Programm so viele Schritte ausfhrt, wie auch zur ausfhrung
bereit stehen.
Theorem 16.3.1
4
Work Distribution
Wie bereits im vorherigen Kapitel festgestellt, kann ein Thread whrend der
Ausfhrung unterbrochen werden, eine Aufgabe lnger bentigen. Somit kann im
Vorhinein nicht sichergestellt werden, dass alle Threads optimal mit Aufgaben
ausgelastet sind. Um dieses Problem zu lsen, mssen Aufgaben zur Laufzeit
neu verteilt werden. Im Folgenden wird der Ansatz des Work-Stealings zur
Umverteilung von Aufgaben zwischen Threads vorgestellt und mit dem naheliegenden Verfahren des Work-Dealing verglichen.
Ein naheliegender Ansatz Aufgaben zwischen Threads zu verteilen ist es
jedem Thread die Mglichkeit eigene Aufgaben an weniger oder nicht ausgelastete Threads zu deligieren. Hierzu unterbricht ein Thread die Berechnung
seiner Aufgabe und prft ob andere Threads nicht ausreichend ausgelastet sind.
Falls ein solcher Thread gefunden wurde, werden eigene Aufgaben an diesen
Thread weitergegeben. Somit kann sichergestellt werden, dass ein Thread, der
alle eigene Aufgaben bearbeitet hat auch weiterhin mit Arbeit versorgt wird.
Dieses Push-Verfahren ist jedoch wenig Ressourcen schonend. Ein bereits ausgelasteter Thread muss sich neben seiner eigentlichen Aufgabe auch noch mit
der Verteilung von Aufgaben beschftigen, whrend ein anderer Thread, der bereits alle Aufgaben bearbeitet hat, auf die Zuteilung neuer Aufgaben wartet. Es
ist offensichtlich, dass in diesem Falle die Ressourcen der Threads nicht effizient
genutzt werden.
Um die Effizienz zu erhhen und die Arbeitskraft optimal zu utilitariesieren
werden beim Work-Stealing Verfahren Aufgaben durch den Arbeitslosen Thread
bei Arbeitenden Threads abgeholt. Die bereits arbeitenden Threads werden
durch dieses Verfahren nicht von ihrer eigentlichen Arbeit abgehalten und ein
arbeitsloser Thread kann sich Aufgaben selbst zuteilen auf die er im WorkDealing Verfahren warten msste.
Konkret wird ein solcher Work-Stealing Algorithmus durch eine DoubleEndling-Queue (DEQueue) realisiert. JedemThread ist eine solche DEQueue
zugeordnet. Auf diese aknn der Thread mit den Methoden push-top, um Auf-
6
gaben der Queue auf einer Seite und push-bottom um Aufgaben auf der anderen Seite der Queue hinzuzufgen zugreifen. Ebenfalls gibt es die Mglichkeit
Aufgaben sowohl von der einen Seite per pop-top als auch von der anderen Seite
per pop-bottom aus der Queue abzurufen. Wird eine Aufgabe einer DEQueue
hinzugefgt so geschieht dies per push-bottom. Aufgaben die durch den eigenen
Thread abgerufen werden, werden per popBottom abgerufen. Aufgaben, die
durch andere Threads abgerufen werden, werden per popTop abgerufen.
//HIER ALGORITHMUS EINFGEN
Wie in Codebeispeil 1 in Zeile 12-16 zu sehen, whlt ein arbeitsloser Thread
zufllig einen anderen Thread aus, um dort, falls mglich, eine Aufgabe zu stehlen
und selbst zu bearbeiten. Der Beispiel-Code bietet keinen Abbruchbeding an.
Eine solche kann beispielsweise genutzt werden aus XY Buch (Kapitel 17.6).
Wie bereits zuvor bemerkt, kann es durch die Kombination von kurzlebigen
Aufgaben, die auf verschiedene Threads verteilt werden, die wiederum durch
das System auf Prozessoren verteilt werden dazu kommen, dass ein Thread trotz
vorhandener Arbeit durch Das System angehalten wird. Um diesem Problem zu
entgehen wird der Befehl yield() in jedem Thread implementiert und direkt vor
dem Stehlen einer Aufgabe ausgefhrt. So wird sichergestellt, dass der Thread
vom Betriebssystem behandelt wird und so weiterarbeiten kann.
5
Work-Strealing Dequeues
7
Document
Kategorie
Technik
Seitenansichten
1
Dateigröße
50 KB
Tags
1/--Seiten
melden