Programmation Parallèle

Soit pour des problèmes de puissance pour du calcul intensif soit pour permettre des interactions utilisateurs, clavier et souris, en même temps que l’exécution de programmes, l’exécution en parallèle est un besoin nécessaire dans le monde d’aujourd’hui… Cela est d’autant plus vrai que la majorité des processeurs sont multicœurs de nos jours. Parlons de programmation parallèle !

Un peu d’histoire sur la programmation parallèle

Au commencement

Les premiers ordinateurs programmables ont été conçus en 1938 par Konrad Zuse et bien que ceux-ci calculent plus vite qu’un humain ils ne calculaient pas assez vite pour résoudre tous les problèmes. Dans les années 50, les scientifiques ont commencé à travailler à la décomposition des problèmes en plusieurs sous-problèmes pour les exécuter sur plusieurs ordinateurs en même temps. C’est le début de la programmation parallèle.

Le principe est d’essayer de finir les tâches plus tôt comme aux caisses d’un supermarché. Supposons que nous ayons 8 clients qui attendent de passer à la caisse avec leurs articles et que le temps moyen de passage est de 15mn :

Si une seule caisse est ouverte, il faudra 8x15mn pour que tous les clients passent
Si deux caisses sont ouvertes, chaque caisse pourra traiter 4 clients et donc il ne faudra que 4x15mn pour traiter tous les clients
Si 4 caisses sont ouvertes, chaque caisse traitera 2 clients et les clients passeront en 2x15mn.

Au début, le calcul parallèle n’avait d’autre but que de faire du calcul intensif. Et rapidement on a défini la performance des ordinateurs en flops : nombre d’opérations en virgule flottante par seconde que l’ordinateur peut effectuer. Le but de chaque fabricant/pays est de faire toujours plus de calculs dans le moins de temps possible lançant ainsi une course à la puissance.

Les grandes dates de la recherche

Cette liste de dates n’a pas vocation à être exhaustive mais juste faire ressortir les découvertes importantes qui ont permis de faire avancer la programmation de ces super-calculateurs.

1962
- C. A. Petri publie ses travaux sur les réseaux et la description des systèmes concurrents.
1964
- D. Slotnick lance une proposition pour une machine massivement parallèle : le projet STAR 100 est lancé et sera finalisé par l’ILLIAC IV entre 1972 et 1982.
- Le CDC 6600 est un supercalculateur qui est une véritable réussite tant commerciale que technique.
1965
- Edsger Dijkstra invente la notion de section critique.
- James W. Cooley et John W. Tukey inventent l’algorithme de la transformation rapide de Fourier.
1966
- Michael Flynn publie sa taxinomie.
1968
- Dijkstra décrit les sémaphores et le problème du dîner des philosophes.
1969
- La société Compass commence l’écriture d’un compilateur Fortran parallèle pour l’ILLIAC IV.
1979
- Publication du BLAS 1 (Basic Linear Algebra Subprograms). Ces fonctions utilitaires (des opérations vectorielles) sont optimisées sur chaque ordinateur pour tirer au mieux parti du hardware (vectorisation ou parallélisme en fonction de l’architecture matériel).
1983
- Le langage Ada est publié : la communication entre tâche et la synchronisation par rendez-vous est proposée.
- Publication du langage SISAL (Streams and Iterations in a Single-Assignment Language) issu des langages à flots de données.
Entre 1984 et 1986
- Publication du BLAS 2 (opérations matrice-vecteur)
Entre 1987 et 1988
- Publication du BLAS 3 (opérations matrice-matrice)
1990
- Pour permettre la création de grilles de calculs avec des ordinateurs hétérogènes, le projet Parallel Virtual machine (PVM) est lancé.
1993
- Message Passing Interface (MPI) est définit pour synchroniser des processus distants via l’envoi de messages.
1995
- Création de la norme des thread POSIX
1997
- Publication d’OpenMP pour Fortran. La version C++ n’a été publié qu’en 1998.

L’API BLAS est aujourd’hui proposée sur toutes les architectures matérielles et souvent par le constructeur lui-même en partenariat avec les chercheurs : je me souviens que mon professeur de mathématiques appliquées, en 1^ère année de l’ENSEEIHT, travaillait sur les écritures des BLAS pour des constructeurs. Aujourd’hui, pour les PC classiques, Intel propose une API optimisée (MKL) pour ses processeurs qui propose le BLAS ainsi que LAPACK en une version optimisée. Le constructeur AMD n’est pas en reste avec la librairie BLIS. Mais l’on peut aussi trouver des implémentations libres comme ATLAS (Automatically Tuned Linear Algebra Soft) mais qui semble ne plus être maintenu.

Taxonomie de Flynn

Les techniques de programmation pour améliorer les performances des programmes ont évolué avec les architectures hardware. Très rapidement, il a été nécessaire de différencier les méthodologies logicielles en fonction de l’architecture et des objectifs/applications du programme. En 1966, Michel Flynn a défini une des premières classifications des ordinateurs. On les classe suivant les flux de données et les flux d’instructions.

SISD : Single Instruction Single Data
C’est le standard de tous les ordinateurs personnels jusque dans les années 90. Une seule instruction sur une seule donnée est exécutée à la fois.
SIMD : Single Instruction Multiple Data
Une instruction qui s’exécute sur de multiples données : cela s’appelle de la vectorisation. Cela s’est traduit chez Intel par l’apparition des instructions MMX.
MISD : Multiple Instruction Single Data
Une donnée est traitée simultanément par plusieurs instructions. On l’utilise notamment pour la redondance dans les systèmes critiques ou dans les réseaux neuronaux.
MIMD : Multiple Instruction Multiple Data
Plusieurs instructions s’exécutent en simultanées sur des données différentes. On en distingue deux catégories :
- les MIMD à mémoire partagée (l’implémentation de l’hyperthreading dans les processeurs Intel par exemple). La communication entre les unités de calculs s’effectue via la mémoire.
- les MIMD à mémoire distribuée :
  chaque unité de calcul a sa propre mémoire et son OS. Il faut une API via un middleware pour la synchronisation et la communication.

L’efficacité du parallélisme (programmation parallèle)

Dans le cas idéal en doublant le nombre d’unités de calcul on devrait diviser le temps d’exécution par 2. Malheureusement ce cas arrive peu dans la réalité. Gene Amdahl, en 1960, formula une loi empirique qui décrit le gain de la parallélisation. Soit p le pourcentage du temps d’exécution de toute la partie parallélisable. Soit n le nombre de fil d’exécution. Alors l’accélération du code s’écrit :

Supposons que 100% du temps d’exécution est parallélisable et que l’on n’ait 10 fils d’exécution alors l’accélération sera A=n/1=10 (au sens de 10 fois plus rapide).
Si seulement 50% du temps d’exécution est parallélisable et que l’on n’ait 10 fils d’exécution alors l’accélération sera A=(0.5+0.05)^-1= 1,81 (moins de deux fois plus rapide).

On en déduit que le parallélisme n’est pas une panacée. Il permet une accélération des performances mais uniquement sur des portions de code. Et avoir une grande quantité de temps d’exécution parallélisable est plutôt lié aux problèmes mathématiques comme l’algèbre linéaire (opérations sur les matrices et les vecteurs). D’autres chercheurs ont proposé, par la suite, d’autres formules comme la loi de Gustafson (optimiste) ou la métrique de Karp-Flatt qui est plus précise que les deux autres mais plus complexe.

Pipeline vectoriel

Exemple de l’addition de flottants

Pour additionner deux nombres flottants, il faut passer par plusieurs étapes :

On doit comparer les exposants
On ajuste ensuite les exposants
On additionne les mantisses
On normalise le résultat

Il faut donc 4 « cycles » pour faire une addition. Supposons que je doive additionner 2 vecteurs contenant chacun 8 valeurs : il faudra donc 8×4 cycles pour finaliser l’opération. Lorsque les deux premières valeurs en sont au cycle de la normalisation les circuits logiques effectuant les 3 premières étapes ne font rien.

Pipeline

L’idée est d’utilisé en continu tous les « étages » du cycle de calculs. Il faudra 4 cycles pour que « A(0)+B(0) » soit calculé, au cinquième cycle « A(1)+B(1) », au sixième « A(2)+B(2) » et ainsi de suite : on aura effectué les 8 additions en 11 cycles au lieu des 32.

Implémentation

Aujourd’hui les processeurs courants ont de nombreux pipelines vectoriels tant pour les calculs entiers que pour les calculs flottants. Voici l’exemple de l’architecture interne d’un Intel Core i7-6700K (source Intel) :

Les pipelines permettent d’accélérer les performances dès lors que l’on travaille sur des vecteurs de données contiguës en mémoire (afin de minimiser les défauts de page dans le cache du processeur) et bien alignées.

Cette complexité (d’architecture des processeurs) est une des raisons qui fait qu’un développeur a peu de chance d’écrire un code assembleur qui pourrait être aussi efficace que le code généré par un compilateur. Organisé les instructions pour utiliser au mieux les calculateurs en parallèle est une tâche extrêmement complexe.

Conclusion

La programmation parallèle est le résultat de plus de 70 ans de recherche pour calculer de plus en plus vite afin de résoudre les problèmes d’aujourd’hui : calcul météorologique, simulation numérique, etc… Si de grandes avancées ont eu lieu, il reste encore beaucoup à faire notamment pour rendre accessible les méthodes au plus grand nombre de développeurs.

Dans la seconde partie de cet article sur la programmation parallèle, nous aborderons les techniques permettant de représenter les algorithmes parallèles afin de les rendre accessible et d’en trouver les éventuelles failles. En attendant la suite pour plus d’article Python rendez-vous sur notre blog !