ABSTRACT
High performance computing are more needed in research and
industry. It is objective is to execute an application in the fastest manner.
Nowadays, it is easy for us to buy a personnal computer that have high
performance more cheaper. A method by putting computing nodes together could
provide considerable performance to compute a parallel application.This is the
parallelism. It is therefore important to subdivide the application into tasks,
to find the processors on which we will execute them and the date of their
execution this is the problem of scheduling. This problem is well known and
many works have been done on that subject. Most of them have been done on
homogeonous clusters consisting of identical nodes of computing interconnected
with an homogeonous network. On the other hands, the nodes and links can have
no identical caracteristics. In this case, we speaking about heterogeonous
clusters. Although they facilitate to have many resources of computing,
heteregeonous clusters get tasks scheduling difficult in the sense that tasks
have to communicate each others. For instance, two adjacents nodes with
different performance will deal differently the reception of a message. So if
tasks are scheduled randomly, the system can be affected in performance. The
problem of scheduling in these conditions is NP-Complete. It is therefore too
difficult to find a polynomial algorithm as a solution. Our work is to propose
a heuristic of scheduling in heterogeonous clusters and evaluate it on an
application.
Keywords Application, graph, task, scheduling, clusters,
heterogeneous, homogeonous, parallelism.
Table des matières
Table des figures xi
Introduction générale 1
I CALCUL PARALLELE ET ARCHITECTURE DES GRAPPES
4
1 Calcul parallèle 4
1.1 Motivations et principes 4
1.2 Programmation parallèle 5
1.2.1 Objectifs de la programmation parallèle 5
1.2.2 Classes d'applications parallèles 6
1.2.3 Modèle de la programmation parallèle 6
2 Taxonomie des machines parallèles 8
2.1 Architecture SISD 8
2.2 Architecture MISD 9
2.3 Architecture SIMD 10
2.4 Architecture MIMD 11
2.4.1 Exemple d'application des quatre classes principales
14
3 Grappes d'ordinateurs 15
3.1 Origine et évolution de grappes 15
3.1.1 Les supercalculateurs 15
3.1.2 les réseaux de station de travail 15
3.1.3 Les grappes de PC 16
3.1.4 Les architectures actuelles 17
3.2 Caractéristiques des grappes 19
3.2.1 Accès aux ressources 19
3.2.2 Sécurité 20
3.2.3 Tolérances aux fautes 20
3.3 Infrastructures matérielles des grappes 20
3.3.1 Architectures matérielles des grappes 20
3.4 Infrastructures logicielles des grappes 21
4 Analyse des performances d'une architecture multiprocesseurs
22
4.1 Modèles de Calcul 22
4.1.1 Modèle à durée égale 22
4.1.2 Modèle de calcul parallèle avec des parties
séquentielles 23
4.2 Un argument pour les architectures parallèles 25
4.2.1 Loi d'Amdahl 25
4.2.2 Loi de gustafson 26
II CONCEPTS D'ORDONNANCEMENT 28
1 Modélisation d'une application 28
1.1 Graphe de précédence 28
1.2 Graphe de flots de données 29
1.3 Graphe de tâches 32
2 Les Modèles classiques d'ordonnancement 33
2.1 Modèles à coût de communications nul
33
2.2 Modèle délai 34
2.3 Les modèles LogP et BSP 35
3 Modèles d'exécution et ordonnancement 36
3.1 Le modèle PRAM 36
3.2 Les modèles avec délai de communications
37
3.2.1 Modèle UET 38
3.2.2 Modèle UET-UCT 39
3.2.3 Modèle UET-LCT 39
3.2.4 Modèle SCT 41
3.3 Le modèle LogP 41
3.4 Le modèle BSP 42
III GRAPPES HETEROGENES et ORDONNANCEMENT 46
1 Eléments de coût 46
1.1 Les stations de travail 46
1.2 Les équipements réseau 46
1.2.1 Les commutateurs 47
1.2.2 Les concentrateurs 49
1.2.3 Les routeurs 49
1.3 Technologie réseau 49
1.4 Système d'exploitation et pile réseau 49
2 Proposition d'un modèle d'ordonnancement sur les grappes
hétérogènes 51
2.1 Modélisation de l'architecture
hétérogène 51
2.2 Graphe de tâches. 52
2.3 L'ordonnancement 52
2.4 Modéle des communications 52
2.5 Idée Générale 53
IV EVALUATION DU MODELE SUR UNE APPLICATION
54
1 Présentation de l'architecture de notre grappe 54
2 Calcul des caractéristiques des noeuds du graphe de
grappe 55
2.1 Les surcoûts engendrés par la pile réseau
relatifs à chaque station de travail . 55
2.2 Tableau récapitulatif et discussion 58
3 Calcul des caractéristiques des arcs du graphe de grappe
58
3.1 Evaluation des latences 58
3.2 Evaluation des débits des liens 61
3.2.1 Discussion 61
4 Programmation de l'application 61
4.1 Algorithme 61
4.2 Code 61
5 Ordonnancement sur la grappe 63
5.1 Résultats et discussion 64
Conclusion générale et perspectives
68
A Annexe 71
1 CONFIGURATION DE NOTRE GRAPPE 71
1.1 Configuration logicielle 71
1.1.1 OAR: gestionnaire de tâches 71
1.1.2 MPICH2 : bibliothèque de communications 73
1.1.3 Serveur NFS : Network file system 74
1.1.4 Serveur NIS : Network information service 75
2 Code séquentiel du produit d'une matrice par un vecteur
76
Bibliographie 77
LISTE DES ABBREVIATIONS
API : Application Program Interface
ARP : Address Resolution Protocol BSP : Bulk
Synchronous Parallel
CESDIS : Center of Excellence in Space Data and
Information Sciences
CM : Connection Machine
CONDOR: Open Grid Computing
COTS: Commodity Off The Shelf
CRAY: Supercomputer Company ( Name of the father
of Supercomuting : Seymour Cray)
CRC : Cyclic Redondancy Control
CRCW : Concurrent Read Concurrent Write
CREW: Concurrent Read Exclusive Write
EREW : Exclusive Read Exclusive Write FTP :
File Transfer Protocol
GNU: GNU is Not Unix
HPC : High Personal Computing HTC
: High Throughput Computing HTTP : Hypertext Transfer
Protocol IBM: International Business Machine
IBM SP : International Business Machine Scalable
Power
ICL DAP : International Computer LTds
Distributed Array Processor
IPC : InterProcess Communication LAN
: Local Area Network
LCT : Large Communication Time MAC
: Media Access Control
MFLOPS : Mega Floatting Operations Per Second
MIMD : Multiple Instruction Multiple Data
MISD : Multiple Instruction Single Data MPI :
Message Passing Interface
MPICH : Message Passing Interface Chameleon
MPMD : Mutiple Programs Multiple Data MVP :
Model View Presenter
NEC : Network Enterprise Center
NFS : Network File System
NIS : Network Information System NOW
: Network Of Workstations
NP : Non Polynomial
NUMA : Non Uniform Access
OAR: Resource Manager
OSI : Open Systems International
PC : Personal Computer
PRAM : Parallel Random Access Machine
PVM : Parallel Virtual Machine
SAN: System Area Network
SCT : Small Communication Time SGI
: Silicon Graphics Image
SISD : Single Instruction Single Data
SIMD : Single Instruction Multiple Data SMP :
Symmetric Multiprocessing SMTP : Simple Mail Transfer Protocol
SPMD : Single Program Multiple data SSH :
Secure Socket Shell
SSI : Single System Image
TFLOPS : Tera Floatting Operations Per Second
UET : Unit Execution Time
UCT : Unit Communication Time
Table des figures
I.1 Architecture SISD 8
I.2 Architecture SIMD 9
I.3 Architecture MIMD 9
I.4 Modèle d'architecture SIMD 10
I.5 Les deux schémas SIMD 11
I.6 Architecture à mémoire partagée et
Architecture de passage de messages 12
I.7 Un réseau de stations de travail 16
I.8 Une grappe de PC 16
I.9 Une grappe de grappes faiblement couplées 17
I.10 Une grappe multiplement câblée (avec des
partitions) 18
I.11 Segments de programme 23
I.12 Modèle Amdahl 26
II.1 Exemple de Programme 29
II.2 Un graphe de précédence pour le programme. Les
tâches sont représentées par des cercles et les arcs
représentent les précédences. 30
II.3 Un graphe de flots de données pour le programme. Les
tâches sont représentées par des
cercles. Les données à transférer dans un
rectangle 31
II.4 Graphe de précédence G 31
II.5 Exemple de graphe de tâche du programme. Les chiffres
en bleu représentent les coûts de chaque tâches. Ceux en
noir représentent le volume des données à
transférer d'une
tâche à l'autre par unité de temps. 32
II.6 Le modèle LogP 35
II.7 A gauche nous avons une représentation de
l'ensemble des processeurs : P=8, L=6, g=4,
o=2 et à droite l'activité de chaque processeur dans le
temps. Le nombre montré pour chaque noeud est le temps auquel chaque
processeur a reçu les données et peut
commencer à envoyer. 36
II.8 Le modèle PRAM pour le calcul parallèle
37
II.9 Exécution dans le modèle UET 39
II.10 Exécution dans le modèle UET-UCT sans et avec
duplication 40
II.11 Exécution dans le modèle UET-LCT sans et avec
duplication 40
II.12 Exécutions dans le modèle SCT sans et avec
duplication 41
II.13 Exemple des paramètres LogP 42
II.14 Ordonnancement sous le modèle LogP 43
II.15 Schéma d'exécution dans le modèle BSP
44
III.1 Trame ethernet 47
III.2 Un message classique tel qu'il transite sur le
réseau 51
IV.1 Notre grappe 55
IV.2 Courbe représentant l'accélération de
l'algorithme parallèle 66
IV.3 Courbe représentant l'efficacité de
l'algorithme parallèle 67
| 
