Le but de ce cours est de donner une idée de la programmation, algorithmique
et sémantique de systèmes parallèles et distribués.
Pour y arriver, on utilise un biais dans un premier temps, qui nous permettra d'aborder les
principaux
thèmes du domaine. On va utiliser le système de ``threads''
de JAVA pour simuler des processus parallèles et distribués.
Plus tard, on utilisera d'autres fonctionnalités de JAVA, comme les RMI, pour
effectuer véritablement des calculs en parallèle sur plusieurs machines.
Les ``threads'' en tant que tels sont une première approche du parallélisme
qui peut même aller jusqu'au ``vrai parallélisme'' sur une machine
multi-processeurs. Pour avoir un panorama un peu plus complet du parallélisme
et de la distribution, il faut être capable de faire travailler plusieurs
machines (éventuellement très éloignées l'une de l'autre; penser à
internet) en même temps. On en fera une approche, soit par simulation par
des threads, soit par le mécanisme de RMI.
Dans les sections 3.2.1 et 3.2.3, on présente d'abord le modèle
de threads de JAVA (communication par mémoire partagée) et la façon
dont on peut créer et contrôler un minimum les threads utilisateurs.
On voit un peu plus en détail
à la section 3.2.2 le fonctionnement de la JVM
en présence de threads. On donne des éléments plus avancés de contrôle
des threads JAVA à la section 3.3, en particulier en ce qui concerne
le cycle de vie des threads, les groupes de processus, les priorités, et
l'ordonnancement.
Dans le chapitre suivant on s'intéresse au très classique et important problème
de l'accès concurrent aux variables partagées. En effet la machine JVM sous-jacente
n'est pas une P-RAM CRCW mais ressemble plus à une CREW
(voir le chapitre 4 ainsi que [Rob00]).
Il faut donc faire très attention à verrouiller les accès, au moins
au moment de l'écriture comme on le verra à la section
5.1. Pour ce faire on utilisera essentiellement le mot clé
synchronized introduit à la section
5.2. On en profitera pour voir un peu de sémantique très minimaliste
dans la section
5.4.2. En effet le premier problème que l'on rencontre, et que l'on
n'a pas dans le monde séquentiel, est le problème de point mort ou
étreinte fatale (deadlock en anglais). On commence à le rencontrer
en section 5.4.2 mais ce sera toujours un thème récurrent.
A partir de synchronized on peut implémenter les mécanismes de synchronisation
et d'exclusion mutuelle typiques que l'on rencontre sous une forme ou une autre
dans tout langage parallèle. On commence par les moniteurs [Hoa74], section
5.3, puis les sémaphores binaires [Dij68], section
5.4.1 et les sémaphores plus généraux, dits à compteur,
section 5.4.5,
qui sont d'ailleurs implémentables à partir des sémaphores binaires
[Dij68]. En fait, synchronized n'est jamais qu'un sémaphore
binaire (ou verrou, ou mutex) associé à une méthode ou à un bout de code.
On en profite aussi dans la section 5.5
pour donner une implémentation des barrières de synchronisation,
très utilisées dans des programmes parallèles à gros grain, par exemple
fonctionnant sur cluster de PC.
Quand on ne veut pas mettre des barrières de synchronisation partout, mais
que l'on veut ordonnancer ces processus plus mollement (on peut alors gagner
en efficacité car l'ordonnancement a plus de degrés de liberté)
de façon à ce que l'état global
du système reste ``cohérent'' en un certain sens, on tombe sur les problèmes
classique de séquentialisation. On en donne quelques exemples, très classiques
en bases de données distribuées, et on développe
le protocole le plus connu permettant d'assurer cette cohérence dans ce cadre,
le protocole 2PL (``2-Phase Locking'') ou protocole à deux phases, en section
5.6. On se reportera au cours de S. Abiteboul, [Abi00],
pour
plus de détails et de références.
On voit enfin au chapitre 6 les grands classiques des algorithmes
permettant de programmer l'exclusion mutuelle (le synchronized) sur
des machines à mémoire partagée, sous certaines hypothèses. Cela peut
paraître assez académique mais est un excellent moyen de s'habituer à
raisonner sur des programmes parallèles se coordonnant par lecture et écriture
en mémoire partagée, et cela n'est pas si facile. Cela permet également
de se familiariser aux preuves de programmes parallèles.
Il existe des compilateurs qui parallélisent automatiquement des codes séquentiels. On en
présente les principes théoriques au chapitre 7. L'optimisation
effectuée par ces compilateurs consiste à transformer le code de telle façon à y trouver
``plus de parallélisme''.
Dans une deuxième partie, on passe du parallélisme à la distribution en partant
des architectures des machines distribuées, et des différentes topologies de communication
(chapitre 8). On voit au chapitre 9.3 comment programmer effectivement un algorithme distribué
sur un réseau de stations.
Au chapitre 10 on passe
en revue quelques algorithmes distribués classiques, permettant de faire de l'algèbre
linéaire élémentaire. C'est un bon exercice pour comprendre comment être
vraiment efficace. Il faut en particulier avoir un recouvrement optimal des calculs
et des communications, et équilibrer les charges au mieux. On verra à cette occasion
que dans un cadre hétérogène, c'est-à-dire quand les machines utilisées n'ont pas
la même puissance de calcul, il est souvent très difficile d'arriver à un équilibrage
correct.
Enfin, au chapitre 11, on complique encore un peu le jeu. Il s'agit maintenant d'écrire
des algorithmes qui en plus, sont ``tolérants aux pannes'', c'est-à-dire que même si
certains processeurs du système distribué tombent en panne en cours de calcul, les autres doivent
pouvoir terminer leur partie de calcul, de façon correcte. On a pris ici le parti
de montrer un petit bout de la théorie sous-jacente, plutôt que de parler extensivement
des algorithmes encore une fois.
Références
Pour des compléments, ou des applications du parallélisme au calcul scientifique,
on pourra se reporter à [GNS00].
Ces notes sont encore très préliminaires et on trouvera en particulier dans
[RL03] nombre de compléments. On se reportera aussi au
complément de D. Rémy [Rem00]
pour tout ce qui concerne l'orienté objet. Le livre
[Ray97] apportera au lecteur toutes les précisions voulues sur les
algorithmes vus au chapitre 6. Le lecteur trouvera enfin des compléments
sur l'algorithmique distribuée, tolérante aux pannes en particulier dans le très
encyclopédique [Lyn96]. Pour aller plus loin, en particulier en ce qui concerne la
sémantique et les modèles du parallélisme, on pourra se reporter aux notes de cours du Master
Parisien de Recherche en Informatique:
http://amanite.ens.fr/MPRI/bin/view/WebSite/C-2-3
Enfin, je remercie Matthieu Martel et Sylvie Putot d'avoir
relu ce polycopié. Les erreurs qui restent
sont néanmoins les miennes!