Einsatz von algorithmischen Skeletten im
Scheduling massiv paralleler Systeme
Dissertation
Schriftliche Arbeit zur Erlangung des Doktorgrades des Fachbereichs
Mathematik/Informatik an der Universit¨
at Gesamthochschule Paderborn
Bodo Kalthoff
Paderborn, den 15. Oktober 2002
Vorwort
Die vorliegende Arbeit entstand in wesentlichen Teilen w¨
ahrend meiner T¨
a-
tigkeit als wissenschaftlicher Mitarbeiter an der Universit¨
at-Gesamthoch-
schule Paderborn.
Ich m¨
ochte Herrn Prof. Dr. F. J. Rammig f¨
ur seine Unterst¨
utzung und zahl-
reichen Anregungen danken, die es mir erm¨
oglichten, diese Arbeit parallel zu
meiner sp¨
ateren beruflichen T¨
atigkeit zu Ende zu f¨
uhren.
Herrn Prof. Dr. W. Hauenschild danke ich f¨
ur die ¨
Ubernahme des Zweitre-
ferates und das damit bekundete Interesse an dieser Arbeit.
Ferner danke ich Herrn Andreas Steffen f¨
ur seine Hilfe bei der Implementie-
rung der algorithmischen Skelette und den Mitarbeitern der AG Rammig f¨
ur
viele lebhafte Diskussionen.
Mein besonderer Dank gilt meiner Familie, insbesondere meiner Frau Antje
f¨
ur Ihre Geduld und Ihr Verst¨
andnis, ohne die diese Arbeit nie entstanden
w¨
are.
Inhaltsverzeichnis
1 Einleitung 1
1.1 Strukturierung der Arbeit . . . . . . . . . . . . . . . . . . . . 2
2 Effiziente Parallelverarbeitung 5
2.1 Single-Programming . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Speedup als Maß f¨
ur Effizienz . . . . . . . . . . . . . . 5
2.1.2 Effizientes Single-Programming auf Parallelrechnern . 6
2.1.3 Grenzen des Single-Programming . . . . . . . . . . . . 6
2.2 Paralleles Scheduling . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Effizienz und andere Ziele . . . . . . . . . . . . . . . . 7
Auslastung ........................ 8
Maximierter Durchsatz . . . . . . . . . . . . . . . . . . 9
Verbesserung der mittleren Terminierungszeit . . . . . 10
2.2.2 Klassifikation von Jobs . . . . . . . . . . . . . . . . . . 11
Jobs mit festem Prozessorbedarf . . . . . . . . . . . . . 11
Jobs mit variablem Prozessorbedarf . . . . . . . . . . . 11
Jobs mit skalierbarem Prozessorbedarf . . . . . . . . . 12
reskalierbare Jobs . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Methoden des Schedulings . . . . . . . . . . . . . . . . 12
Partitionierung . . . . . . . . . . . . . . . . . . . . . . 13
Time-Slicing ....................... 13
Remapping ........................ 14
3 Scheduling paralleler Applikationen 17
3.1 Stand der Technik . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.1 Jobs mit festem Prozessorbedarf und variable Partitio-
nierung .......................... 17
3.1.2 Jobs mit festem Prozessorbedarf und Gang-Scheduling 18
3.1.3 Skalierbare Jobs und adaptive Partitionierung . . . . . 18
3.1.4 Reskalierbare Jobs und Repartitionierung . . . . . . . . 19
3.1.5 Theoretische Modelle . . . . . . . . . . . . . . . . . . . 19
III
IV INHALTSVERZEICHNIS
Shelf Scheduling . . . . . . . . . . . . . . . . . . . . . . 19
PBI-Scheduling . . . . . . . . . . . . . . . . . . . . . . 20
Dynamic Equipartitioning . . . . . . . . . . . . . . . . 23
3.1.6 Scheduling in der Praxis . . . . . . . . . . . . . . . . . 24
EASY-Loadleveler . . . . . . . . . . . . . . . . . . . . 24
Der PC2Scheduler.................... 25
Gang-Scheduling am LLNL . . . . . . . . . . . . . . . 28
4 Algorithmische Skelette 33
4.1 Motivation............................. 33
4.2 Algorithmische Skelette . . . . . . . . . . . . . . . . . . . . . . 34
4.3 Abstraktion durch Programmklassen . . . . . . . . . . . . . . 35
4.4 Stand der Technik . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4.1 Allgemeine Programmierskelette . . . . . . . . . . . . . 36
Cole: Algorithmic Skeletons . . . . . . . . . . . . . . . 36
Higher Order Functions (HOF) . . . . . . . . . . . . . 36
4.4.2 Spezialskelette . . . . . . . . . . . . . . . . . . . . . . . 38
Algorithmische Skelette f¨
ur mathematisch-technische
Anwendungen . . . . . . . . . . . . . . . . . . 38
N-Graphen f¨
ur Transputernetzwerke . . . . . . . . . . 38
PCN............................ 39
P3L............................ 40
SCL ............................ 41
4.5 Algorithmischen Skeletten im Scheduling . . . . . . . . . . . . 43
5 Scheduling mit Skeletten 45
5.1 Skelett f¨
ur Divide & Conquer . . . . . . . . . . . . . . . . . . 46
5.1.1 Spezifikation des D&C-Skelettes . . . . . . . . . . . . . 46
5.1.2 Eigenschaften des Skelettes . . . . . . . . . . . . . . . . 47
Skalierbarkeit ....................... 47
Dynamisches Remapping . . . . . . . . . . . . . . . . . 48
5.2 Skelett f¨
ur Iterative Combination . . . . . . . . . . . . . . . . 50
5.2.1 Spezifikation des ic-Skelettes . . . . . . . . . . . . . . . 50
5.2.2 Eigenschaften des Skelettes . . . . . . . . . . . . . . . . 52
Skalierbarkeit ....................... 52
Dynamisches Remapping . . . . . . . . . . . . . . . . . 53
5.3 Skelett f¨
urFarming........................ 54
5.3.1 Spezifikation des Farming-Skelettes . . . . . . . . . . . 54
5.3.2 Eigenschaften des Farming-Skelettes . . . . . . . . . . 55
Skalierbarkeit ....................... 55
Dynamisches Remapping . . . . . . . . . . . . . . . . . 55
INHALTSVERZEICHNIS V
5.4 Optimierung von Schedules . . . . . . . . . . . . . . . . . . . 57
5.4.1 Speedup-Prognose skelettbasierter Programme . . . . . 57
Konservative Rechenzeitsch¨
atzung . . . . . . . . . . . . 57
Laufzeitprognose mittels Programmklassen . . . . . . . 59
5.4.2 Einsatz vordefinierter Datentypen . . . . . . . . . . . . 59
Exakte Programmanalyse . . . . . . . . . . . . . . . . 59
Effizienzverbesserung von Schedules mit grobgranula-
rer Laufzeitprognose . . . . . . . . . . . . . . 60
5.4.3 Optimierung durch Reskalierung . . . . . . . . . . . . . 62
5.4.4 Einfluß skalierbarer Applikationen . . . . . . . . . . . . 63
5.5 Dynamisches Remapping von Prozessoren . . . . . . . . . . . 66
5.5.1 Integration von nicht skelettbasierten Programmen . . 66
5.5.2 Horizontales Remapping . . . . . . . . . . . . . . . . . 67
5.5.3 Vertikales Remapping . . . . . . . . . . . . . . . . . . . 67
5.6 Das Kostenmodell f¨
ur das Scheduling . . . . . . . . . . . . . . 71
5.7 Optimierung mittels Back-Filling . . . . . . . . . . . . . . . . 72
6 Scheduling mit PCN 75
6.1 Einf¨
uhrunginPCN........................ 75
6.1.1 Programmierung in PCN . . . . . . . . . . . . . . . . . 76
6.1.2 Die Basis-Mechanismen . . . . . . . . . . . . . . . . . . 76
6.1.3 Datentypen und Variablen . . . . . . . . . . . . . . . . 78
6.1.4 Kommunikation und Synchronisation . . . . . . . . . . 80
6.1.5 Prozeß-Mapping . . . . . . . . . . . . . . . . . . . . . . 82
6.1.6 Das Ausf¨
uhrungsmodell von PCN . . . . . . . . . . . . 84
6.2 Implementierung der Skelette . . . . . . . . . . . . . . . . . . 85
6.2.1 Das d&c-Skelett . . . . . . . . . . . . . . . . . . . . . . 85
H-Baum Einbettung . . . . . . . . . . . . . . . . . . . 85
Realisierung der Einbettungen . . . . . . . . . . . . . . 86
6.2.2 Das ic-Skelett....................... 90
Implementierung . . . . . . . . . . . . . . . . . . . . . 90
Test&Select-Phase . . . . . . . . . . . . . . . . . 91
Combine-Phase . . . . . . . . . . . . . . . . . . 91
Internes Remapping . . . . . . . . . . . . . . . . . . . 92
6.2.3 Das Farming-Skelett . . . . . . . . . . . . . . . . . . . 93
Integration von Prozessoren w¨
ahrend der Berechnung . 94
Freigabe von Prozessoren . . . . . . . . . . . . . . . . . 95
6.2.4 Das Fixed-Sized Skelett . . . . . . . . . . . . . . . . . 95
6.3 Wahl des Scheduling Verfahrens . . . . . . . . . . . . . . . . . 98
6.4 nichtpreemtives 2-Phasen Scheduling . . . . . . . . . . . . . . 99
6.4.1 Initiales Scheduling . . . . . . . . . . . . . . . . . . . . 99
Loading more pages...