Parallélisme (informatique)

Pour les articles homonymes, voir parallèle.

Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000

En informatique, le parallélisme consiste à implémenter des architectures d'électronique numérique et les algorithmes spécialisés pour celles-ci, permettant de traiter des informations de manière simultanée. Le but de ces techniques est d'effectuer, avec une machine, le plus grand nombre d'opérations dans le plus petit temps possible. Pour ce faire, les opérations doivent être faites en parallèle, c'est-à-dire simultanément au sein de plusieurs unités de traitement. La tâche à effectuer est décomposée en de multiples sous-tâches qui sont exécutées en même temps et qui composent chacune des architectures parallèles. Le parallélisme en informatique, comme défini ici, s'applique à de multiples types de traitements, mais sans spécification il s'agit de paralléliser les unités de calcul. Dans les autres cas comme pour le standard RAID 0, le terme d'agrégation est privilégié.

Pour être efficaces, les méthodes utilisées pour la programmation des différentes tâches qui constituent un programme sont spécifiques à ce mode de calcul, c'est-à-dire que les programmes doivent être réalisés avec cette optique. Ces méthodes ont initialement été développées sur des machines sophistiquées, des superordinateurs qui comptent de nombreux processeurs.

Par ailleurs, les architectures parallèles sont devenues le paradigme dominant pour tous les ordinateurs depuis les années 2000. En effet, la vitesse de traitement qui est liée à l'augmentation de la fréquence des processeurs connait des limites en raison d'une augmentation de la production thermique qui provoque des erreurs de calculs. C'est aussi la raison pour laquelle depuis longtemps déjà l'augmentation de la vitesse de calcul passait par une architecture comportant de nombreuses unités de calcul. La création de processeurs multi-cœurs, traitant plusieurs instructions en même temps au sein du même composant, résout ce dilemme pour les machines de bureau depuis le milieu des années 2000. Parallèlement à ce phénomène, les développeurs de logiciels utilisent plus volontiers sur ces machines le type de programmation spécialisé appelée programmation concurrente, qui est souvent plus efficace mais plus compliquée à mettre en place que la programmation traditionnelle dite séquentielle.

Les ordinateurs parallèles peuvent être grossièrement classés selon le niveau auquel le matériel prend en charge le parallélisme. D'une part, il y a les machines communes que ce soit avec multi-cœurs ou les machines multiprocesseurs et d'autre part les architectures en grappe de serveurs, les machines massivement parallèles et les structures formées à partir de grilles informatiques c'est-à-dire de milliers de simples ordinateurs, non dévolus à cette tâche en particulier et reliés par un réseau.

Principes

Les premiers ordinateurs étaient séquentiels, c'est-à-dire que leur processeur exécutait les instructions l'une après l'autre, passant éventuellement d'un processus à un autre via des interruptions en simulant le multitâche. Les machines parallèles exécutant des programmes parallélisés ne se contentent pas d'exécuter des applications indépendantes en parallèle. Le système d'exploitation, via son ordonnanceur, ou l'intergiciel doit répartir les calculs de manière à optimiser l'utilisation des unités de calcul. C'est un problème général en informatique connu sous le nom répartition de charge. Pour que ce soit efficace, il faut que les applications soient écrites de telle façon que les algorithmes soient constitués de tâches, c'est-à-dire écrits par « tranches » dont les exécutions pourront se faire de manière relativement indépendante les unes des autres sur les différentes unités de calcul. Pour que ceci soit possible le programme doit être écrit suivant le paradigme de la programmation concurrente, une méthode de programmation utilisant des mécanismes formalisés. Ceci accélère le traitement dans la plupart des situations même si certaines tâches doivent attendre la résolution d'une autre, concurrente sur une ressource par exemple, pour continuer à s'effectuer.

Il s'avère dans la pratique que la multiplication du nombre d'unités de calcul ne divise pas spontanément le temps d'exécution des programmes, même lorsque le programme utilise les mécanismes de la programmation concurrente. De nombreuses autres considérations entrent en jeu, comme la perte de temps pour l'attente de données calculées par une autre tâche. Concrètement, deux soucis se posent lorsqu'un centre informatique choisit d'utiliser cette méthode de calcul : éviter d'utiliser une machine trop puissante, car cela a un coût, et écrire le meilleur programme qui soit. Techniquement, les limites de puissance de calcul sont indissociables des problèmes de dispersion thermique des processeurs.

La réalisation de programmes adéquats sur des architectures prévues à cet effet se traduit par des économies dans presque tous les domaines du calcul, incluant : la dynamique des fluides, les prédictions météorologique, la modélisation et simulation de problèmes de dimensions plus grandes, le traitement de l'information et l'exploration de données, le traitement d'images ou la fabrication d'images de synthèse, tels que le lancer de rayon, (avec les fermes de rendu), l'intelligence artificielle et la fabrication automatisée. En fait, la plupart des systèmes de calcul de haute performance (aussi appelés superordinateurs ou supercalculateurs) qui ont été conçus au cours des dernières années ont une architecture parallèle.

Elle permet aussi de traiter des problèmes nouveaux, d'apporter des solutions globales à des problèmes qui étaient abordés plus partiellement auparavant.

La taxinomie de Flynn

Tableau récapitulatif de la taxonomie de Flynn

	Unique instruction	Multiple instructions
Donnée unique	SISD	MISD
Plusieurs données	SIMD	MIMD

La Taxinomie de Flynn, proposée par l'américain Michael J. Flynn est l'un des premiers systèmes de classification des ordinateurs créé. Il évalue tant le matériel que le logiciel. Les programmes et les architectures sont classés selon le type d'organisation du flux de données et du flux d'instructions. Les machines les plus simples traitent une donnée à la fois et en même temps, ces systèmes SISD sont dits « séquentiels ». Ce type de fonctionnement était prédominant pour les ordinateurs personnels jusqu'à la fin des années 1990. Le type MISD a été beaucoup plus rarement utilisé, il semble néanmoins adapté à certains problèmes comme les réseaux neuronaux et aux problèmes temps-réel liés. L'architecture appelée Systolic array est un type d'architecture MISD. Les systèmes traitants de grandes quantités de données d'une manière uniforme ont intérêt à être des SIMD, c'est typiquement le cas des processeurs vectoriels ou des unités de calcul gérant le traitement du signal comme la vidéo ou le son ; c'est par exemple le cas des machines traitant les instructions AltiVec. Les systèmes utilisant plusieurs processeurs ou un processeur multi-cœur sont plus polyvalents et pleinement parallèle, ce sont des MIMD.

Selon David A. Patterson et John L. Hennessy, « Certaines machines sont des hybrides de ces catégories, bien sûr, mais cette classification traditionnelle a survécu parce qu'elle est simple, facile à comprendre, et donne une bonne première approximation. C'est aussi, peut-être en raison de son intelligibilité, le schéma le plus utilisé. »^[1]

Cette approche montre clairement deux types de parallélismes différents, le parallélisme par flot d'instructions également nommé parallélisme de traitements ou de contrôle, dans l'optique d'opérations simultanées et le parallélisme de données en multipliant le même traitement sur un grand nombre de données.

Efficacité du parallélisme

Representation graphique de la loi d'Amdahl. L'accélération du programme par la parallélisation est limitée par le nombre d'exécutions parallèles possible au sein de l'algorithme. Par exemple, si un programme peut être parallélisé à 90 %, l'accélération maximale théorique sera de x 10, quel que soit le nombre de processeurs utilisés.

De façon idéale, l'accélération due à la parallélisation devrait être linéaire, en doublant le nombre d'unités de calcul, on devrait réduire de moitié le temps d'exécution, et ainsi de suite. Malheureusement très peu de programmes peuvent prétendre à de telles performances. Dans les années 1960, Gene Amdahl formula une loi empirique éponyme restée célèbre^[2], elle aussi fut développée par d'autres auteurs. La loi d'Amdahl affirme que la petite partie du programme qui ne peut être parallélisée limite la vitesse globale du programme. Or tous les programmes d'ingénierie ou toute résolution mathématique contient nécessairement des parties parallélisables et des parties séquentielles non parallélisables. Cette loi prévoit, qu'une fois optimisé, il existe au sein du programme une relation entre ration de code parallélisé et la vitesse globale d'exécution du programme. Dans la pratique, cette approximation est utilisée pour fixer une limite à la parallélisation des architectures matérielles ou à l'optimisation de la programmation pour résoudre un problème.

La loi de Gustafson est assez analogue. Également empirique, elle prédit que le gain de vitesse obtenu est proportionnel à la fois au taux que représente la partie non-parallélisable et au nombre de processeurs.

La métrique de Karp-Flatt proposée en 1990 est plus complexe et efficace que les deux autres lois. Elle intègre le coût lié au temps d'exécutions des instructions qui mettent en œuvre le parallélisme.

Autres considérations empiriques

Croissance du nombre de transistors dans les microprocesseurs Intel par rapport à la loi de Moore. En vert, la fausse hypothèse voulant que ce nombre double tous les 18 mois

Une autre thèse veut que tout problème pouvant être résolu sur un ordinateur séquentiel raisonnable en utilisant un espace de taille polynomiale peut être résolu en temps polynomial par un ordinateur parallèle raisonnable et vice versa.

La thèse de l'invariance est une thèse complémentaire qui supporte, du moins de façon approximative, la définition d'une notion d'ordinateur raisonnable. Elle s'énonce comme suit: Des machines raisonnables peuvent se simuler entre elles avec au plus un accroissement polynomial en temps et une multiplication constante de l'espace. Une manière de construire des modèles « raisonnables » est de considérer la classe des machines raisonnables incluant la machine de Turing.

Depuis les années 1960, la densité des transistors dans un microprocesseur double tous les 18 à 24 mois, cette observation est appelée la loi de Moore^[3]. En dépit de problèmes de consommation énergétique, la loi de Moore est toujours valable en 2010. Les transistors supplémentaires, toujours plus petits, permettent de créer plusieurs unités de calcul, appelé cœurs, au sein du même processeur.

Les programmes

Les tâches d'un programme parallèle sont habituellement appelés processus et peuvent être de plusieurs types selon le système d'exploitation ou la machine virtuelle. Certains processus sont dits légers, les anglophones utilisent plutôt Thread ce qui peut se traduire par fil. Les threads, plus léger encore, utilisés par certaines architectures sont appelés fibers en anglais, c'est-à-dire fibres en français.

Les synchronisations

Articles détaillés : Programmation pour l'architecture distribuée et programmation concurrente.

Plusieurs défis ont dû être relevé par la programmation de système parallèle, par exemple celui de traiter des informations sur des processeurs indépendants, chacun ayant peu d'information sur son voisin, y compris lorsqu'une partie de l'architecture est indisponible. Des langages de programmation concurrente, des interfaces de programmation spécialisées et des algorithmes modèles ont été créés pour faciliter l'écriture de logiciels parallèles et résoudre ces problèmes. La plupart des problèmes de concurrence sont des variantes des problèmes rencontrés dans les modèles appelés producteur-consommateur, lecteur-rédacteur ou Dîner des philosophes. Dans le problème « producteur-consommateur », des processus dit « producteurs » produisent des données qui sont posées dans une file d'attente, une ressource bornée, ces données sont consommés par les processus dit « consommateurs ». Le fait que la ressource soit bornés implique que les producteurs doivent attendre que la file se vide pour pouvoir en produire une nouvelle, et elle implique que le consommateur patiente quand cette liste est vide. Un mécanisme d'avertissement entre les producteurs et les consommateurs peut être mis en place pour assurer un meilleur fonctionnement au système. Dans le modèle « lecteur-rédacteur », spécialisé dans le traitement des flux c'est-à-dire du filtrages, les débits respectifs de l'un et l'autre peuvent causer, une famine du fait de la lenteur du lecteur, l'obsolescence du fait de la lenteur du rédacteur ou d'une manière plus particulière encore du fait de la mise à jour des données. La principale difficulté du programmeur est d'écrire des algorithmes qui produisent des débits comparables pour les uns et les autres. Enfin, le modèle du « Dîner des philosophes » est le modèle le plus fréquent car les cas où l'échange d'information entre processus peut se faire par simple accès à des données via une zone mémoire partagée sont rares et les données, lorsque cette manière est faire est utilisée, doivent n'avoir soit aucun rapport entre elles soit n'avoir pas besoin d'être mis à jour sans quoi des problèmes de compétition surgissent. Ainsi, plusieurs mécanismes adaptés à des échanges plus polyvalent ont donc été inventés, répondant chacun au mieux à un problème spécifique, comme les tubes anonymes adaptés aux filtrage ou les files d'attente de message permettant de diminuer l'attente active dans le modèle producteur-consommateur.

Le choix du mécanisme d'échange de données dépend aussi de type d'architecture matériel pour lequel le langage, l'interface ou l'algorithme est destiné. Autrement dit, un programme destiné à s'exécuter sur une architecture à mémoire partagée ne serait pas identique à celui destiné à une architecture à mémoire distribuée où sur une architectures mixtes. Les programmes s'exécutant sur les architectures partagées vont pouvoir simplement partager des zones mémoires, les systèmes à mémoire distribué vont devoir échanger des messages via un bus ou un réseau. POSIX Threads et OpenMP sont, en 2010, les deux Message Passing Interface, c'est-à-dire les deux librairie spécialisée gérant ce protocoles de passage de messages, les plus utilisés^[4]. Ces protocoles ont pour objectif de rendre transparent ces échanges.

Ces problèmes dit de « synchronisation » et même plus généralement ceux de communication inter-processus dont ces derniers dépendent, rendent pratiquement toujours la programmation plus difficile malgré la volonté des programmeurs à produire un code source « Threadsafe ».

En outre, le nombre de techniques à mettre en œuvre pour la gestion des échecs matériels ou logiciels se sont particulièrement développées avec l'avènement des architectures distribuées.

Les modèles de programmation parallèle

• parallélisme de donnée
• parallélisme de tâche
  • parallélisme de flux
  • parallélisme de contrôle

Le partage des données

Articles détaillés : Mémoire partagée, mémoire distribuée et Parallel random access machine.

Au sein des ordinateurs parallèles, la mémoire vive peut être soit partagée, soit distribuée. Dans le premières l'échange de donnée est plus simple mais nécessite dans la plupart des cas l'usage de mécanismes logiciels particuliers difficiles à programmer efficacement et un bus mémoire à large bande passante. Pour le second cas la bande passante est moins cruciale autrement dit les répercussions d'un flux important sur la vitesse de traitement globale sont plus faibles, mais nécessite l'appel à un système de transmission des données explicite plus lourd.

Dépendance des données

La connaissance des dépendances entre les données est fondamentale dans la mise en œuvre d'algorithmes parallèles. Puisqu'un calculs qui dépend du résultat d'un calcul préalable doit être exécuté séquentiellement, aucun programme ne peut s'exécuter plus vite que l'exécution du plus long des enchainements de calculs, c'est-à-dire le chemin critique. Un des gains de performance dû au parallélisme se trouve donc dans l'exécution de calculs indépendants et des chemins non-critiques en simultané. Les conditions de Bernstein^[5] permettent de déterminer lorsque deux parties de programme peuvent êtres exécutées en parallèle. Ceci se formalise ainsi :

Soit P_i et P_j deux fragments de programme. Pour P_i, avec I_i les variables d'entrées et O_i les variables de sorties, et de même façon pour P_j. P _i et P_j sont indépendants s'ils satisfont les conditions suivantes :

• $I_j \cap O_i = \varnothing, \,$
• $I_i \cap O_j = \varnothing, \,$
• $O_i \cap O_j = \varnothing. \,$

La violation de la première de ces conditions implique une dépendance des flux, c'est-à-dire le premier  fragment  ⇔  statement produit un résultat utilisé par le second. La seconde condition est une condition d'« anti-dépendance », le premier fragment écrase (i.e. remplace) une variable utilisée par le second. La dernière condition est une condition sur les sorties, lorsque les deux fragments écrivent une même donnée, la valeur finale est celle produite par le fragment exécuté en dernier^[6].

Considérons les fonctions suivantes, qui démontrent plusieurs sortes de dépendances :

1: function Dep(a, b) 2: c := a·b 3: d := 2·c 4: end function	L'opération 3 dans Dep (a, b) ne peut pas être exécutée avant (ni même en parallèle avec) l'opération 2, car l'opération 3 utilise un résultat d'exploitation 2. Il viole la condition 1, et introduit ainsi une dépendance de flux.
1: function NoDep(a, b) 2: c := a·b 3: d := 2·b 4: e := a+b 5: end function	Dans cet exemple, il n'y a pas de dépendances entre les instructions, de sorte qu'elles peuvent être exécutées en parallèle.

Les conditions de Bernstein ne permettent pas de gérer l'accès à la mémoire entre différents processus. Pour ce faire il faut utiliser des outils logiciels comme les moniteurs, les barrières de synchronisation ou toute autre méthode de synchronisation.

L'accès aux données

Leslie Lamport est le premier à avoir défini la cohérence séquentielle.

Article détaillé : cohérence.

Pour accélérer les traitements effectués par les différentes unités de calcul, il est efficace de multiplier les données, c'est typiquement le cas lors de l'utilisation des caches. Ainsi l'unité de calcul travaille à partir d'une mémoire, spécialisée si possible, qui n'est pas la mémoire partagée par l'ensemble des unités de calculs. Lorsque le programme modifie une donnée dans ce cache, le système doit en fait la modifier dans l'espace commun et répercuter cette modification au sein de tous les caches où cette donnée est présente. Des mécanismes sont mis en place pour que les données restent cohérentes. Ces mécanismes peuvent être décrits par de complexes modèles d'algèbres de processus et ces derniers peuvent être décrits de plusieurs manières au sein de divers langages formels. Le mécanisme à mémoire transactionnelle logicielle est le plus courant des modèles de cohérence, il emprunte à la théorie des systèmes de gestion de base de données la notion de transactions atomiques et les applique aux accès mémoire.

En outre, certaines ressources ne peuvent être disponibles en même temps que pour un nombre restreint de tâches. C'est typiquement le cas pour l'accès en écriture sur un fichier sur disque par exemple. Alors que celui-ci est disponible pour théoriquement un nombre infini en lecture seule, le fichier n'est disponible que pour une seule tache en lecture-écriture, toute lecture par un autre processus est alors proscrite. La réentrance est le nom de la propriété du code lorsque celui-ci peut être utilisable simultanément par plusieurs tâches.

Situation de compétition

Les processus ont souvent besoin d'actualiser certaines variables communes sur lesquelles ils travaillent. Les accès à ces variables se font d'une manière indépendante, et ces accès peuvent occasionner des erreurs.

Compétition de deux threads sur une donnée

Thread A	Thread B	Dans l'illustration ci-contre, le résultat d'exécution n'est pas prévisible, du fait que vous ne pouvez savoir quand les Thread A et B s'exécutent, cela dépend en effet de la manière dont les exécutions se chevauchent. Dans l'hypothèse la plus simple ou les thread A et B s'exécutent une fois, l'ordre d'exécution des instructions peut être par exemple : Lire, Lire, Add, Add, Écrire, Écrire ou bien Lire, Add, Écrire, Lire, Add, Écrire. Le résultat dans ces deux hypothèses n'est pas le même puisque au final dans le second cas la variable est augmentée de deux alors qu'elle n'est augmentée que de un dans le premier.
1A: Lire variable V	1B: Lire variable V
2A: Add 1 à la variable V	2B: Add 1 à la variable V
3A: Écrire la variable V	3B: Écrire la variable V

Ce phénomène est connu sous le nom de situation de compétition. Pour résoudre ce genre de problème, le système doit permettre au programmeur d'utiliser un verrou d'exclusion mutuelle, c'est-à-dire de pouvoir bloquer, en une seule instruction, tous les processus tentant d'accéder à cette donnée, puis, que les autres processus puissent y accéder lorsque le verrou est libéré. Les tâches attendant la levée du verrou sont « mise en sommeil ». Ces opérations de verrouillage en une instruction sont dites « atomiques », du grec ancien ατομος (atomos), qui signifie « que l'on ne peut diviser^[7] ».

Solution pour protéger l'accès à une donnée

Il existe concrètement plusieurs techniques pour obtenir des verrous et des sections critiques où l'accès aux données est « sécurisé » comme ci-contre mais ce genre de mécanismes est source potentielle de bug informatique.	Thread A	Thread B
	1A: Verrouiller la variable V	1B: Verrouiller la variable V
	2A: Lire la variable V	2B: Lire la variable V
	3A: Add 1 à la variable V	3B: Add 1 à la variable V
	4A: Écrire la variable V	4B: Écrire la variable V
	5A: déverrouiller la variable V	5B: déverrouiller la variable V

Un fort couplage augmente le risque de bugs, aussi il est recommandé au programmeur de les minimiser. En effet si deux tâches doivent chacune lire et écrire deux variables et qu'elles y accèdent en même temps, cela doit être fait avec précaution. Si la première tâche verrouille la première variable pendant que la seconde tâche verrouille la seconde, alors les deux tâches seront mise en sommeil. Il s'agit là d'un cas d'interblocage, autrement appelé d'« étreinte mortelle » ou « étreinte fatale ».

Certaines méthodes de programmation cherchent à éviter d'utiliser ces verrous, appelées Non-blocking synchronization, elles sont encore plus difficiles à mettre en œuvre et nécessitent la mise en place de structures de données très particulières. La mémoire transactionnelle logicielle en est une.

Efficacité et limites

Articles détaillés : Extensibilité et speedup.

D'une manière générale, plus le nombre de tâches est élevé dans un programme, plus ce programme passe son temps à effectuer des verrouillages et plus il passe son temps à échanger des messages entre tâches. Autrement lorsque le nombre de tâches augmente trop, la programmation concourante ne permet plus d'augmenter la vitesse d'exécution du programme ou plus précisément de diminuer la durée de son chemin critique car le programme passe son temps à mettre en sommeil les taches qui le composent et à écrire des informations qui permettent l'échange d'information entre tâches. Ce phénomène est appelé le ralentissement parallèle.

D'ailleurs les applications sont souvent classées en fonction de la fréquence à laquelle ses tâches dialoguent ou se synchronisent. Les applications ayant beaucoup d'échanges ou de synchronisations entre ses sous-tâches sont dites fine-grained (à grain fin), celles qui ont au contraire peu d'échanges et de synchronisations sont dites coarse-grained c'est-à-dire à gros grain. L'algorithme est dit Embarrassingly parallel, c'est-à-dire de « parallélisme embarrassant » s'il n'y a aucun contact entre les sous-tâches. Ce dernier est le plus simple à programmer.

Algorithmique

Les programmes aujourd'hui, sauf exception, sont écrits ou compilés de manière à ce que l'adressage interne soit relatif, c'est-à-dire qu'un ensemble d'instruction peu s'exécuter convenablement quel que soit l'emplacement mémoire ou il est stocké. Le code peut donc être dupliqué. L'exécution simultanée d'un même code en plusieurs exemplaires ne pose donc aucun problème.

En revanche, si certains problèmes sont simplement divisibles en multiple sous-problèmes exécutables par différents processus ce n'est pas le cas de tous les problèmes. Par exemple, s'il est simple de paralléliser la recherche de la liste des nombres premiers en attribuant à chaque processeur une liste de nombre et en regroupant les résultats à la fin, il est plus difficile de le faire par exemple pour le calcul de π puisque les algorithmes habituels, bâtis sur le calcul de séries, évaluent cette valeurs par approximation de plus en plus précise à partir du résultat précédent. Le calcul des séries, les méthodes itératives, comme la méthode de Newton et le problème des trois corps, les algorithmes récursifs comme celui de l'algorithme de parcours en profondeur des graphes sont par conséquent très difficiles à paralléliser.

Problématique des boucles

Article détaillé : parallélisation de boucle.

Outre la problématique liée à l'accès aux variables comme la concurrence où la réentrance, pour des raisons de performances, les compilateurs doivent prendre en compte la mise en cache de la séquence d'instruction à exécuter lorsqu'il contient des boucles. À chaque exécution d'un saut, le cache qui contient les instructions doit être vidé et de nouveau rempli. Cette action est lente, les compilateurs vont donc chercher à minimiser cet impact.

Problématique sériel ou temporel

Lors de calcul de fonctions récursives, une dépendance est créée au sein d'une boucle, l'exécution de celle-ci ne peut s'effectuer que lorsque la précédente s'est effectuée. Ceci rend le parallélisme impossible. Le calcul de la suite de Fibonacci en est un cas d'école, comme l'illustre le pseudo-code suivant :

le Tri fusion est un tri bien adapté à la parallélisation

1:    PREV1 := 0
2:    PREV2 := 1
4:    do:
5:       CUR := PREV1 + PREV2
6:       PREV1 := PREV2
7:       PREV2 := CUR
8:    while (CUR < 10)

Ce n'est cependant pas le cas de tous les algorithmes récursifs, lorsque chaque fonction a un traitement suffisant à effectuer, ils peuvent même être plus efficace que des algorithmes composés de boucle en raison de leur nature : « diviser pour régner ». C'est par exemple le cas pour deux algorithmes de tri récursifs, le Tri rapide et plus particulièrement le Tri fusion. En outre ces deux algorithmes ne créent pas de situation de compétition et il n'est donc pas nécessaire de synchroniser les données.

Si l'algorithme permet de créer une liste de n taches par p processeurs en un temps moyen $\mathcal{O}(n)$, et si les p effectue les tris dans un temps moyen $\textstyle\mathcal{O}\left(\frac{n}{p} \log\frac{n}{p}\right)$, alors l'accélération est optimum. Dans ce cas, une augmentation du nombre de processeurs, n'accélérerait pas le traitement.

Les patrons de conceptions de synchronisation

Barrière de synchronisation • Futex • Moniteur • Mutex • Sémaphore • Spinlock • Algorithme de Peterson • Algorithme de Dekker • Algorithme du banquier

Problématiques logicielles

Article détaillé : Communication inter-processus.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

Le modèle de passage de messages est un modèle de communication entre ordinateurs. Il ne sert pas que pour le calcul parallèle, comme c'est le cas pour les JavaBeans.

• Un des concepts utilisé dans la programmation concurrente est le concept de  Futures and promises (en)  ⇔  merci d’apporter votre expertise, et de préciser, une tache promet à une autre qu'elle délivrera la donnée fournie.
• Influence des compilateurs. Cf Explicitly Parallel Instruction Computing, parallélisation automatique

Mécanisme sous-jacent au parallélisme

Plusieurs mécanismes ont été mis en place pour permettent d'exécuter des programmes en utilisant le paradigme du parallélisme. Certains sont liés à la création d'algorithmes parallèles, d'autres sont matériels.

Le Parallélisme au sein du processeur

Séquençage des instructions dans un processeur doté d'un pipeline à 5 étages. Il faut 9 cycles pour exécuter 5 instructions. À t = 5, tous les étages du pipeline sont sollicités, et les 5 opérations ont lieu en même temps.

Un programme informatique est, par essence, un flux d'instructions exécuté par un processeur. Chaque instruction nécessite plusieurs cycles d'horloge, l'instruction est exécutée par autant d'étapes que de cycles nécessaires. Les microprocesseurs séquentiels exécutent l'instruction suivante lorsqu'ils ont terminé la première. Dans le cas du parallélisme d'instruction, le microprocesseur peut traiter plusieurs de ces étapes en même temps, pour plusieurs instructions différentes car elles ne mobilisent pas les mêmes ressources internes. Autrement dit, le processeur exécute en parallèle des instructions qui se suivent à différents stades d'achèvement. Cette file d'exécution s'appelle une pipeline. Ce mécanisme a été implémenté la première fois dans les années 1960 par IBM.

Les processeurs plus évolués exécutent en même temps autant d'instructions qu'ils ont de pipelines, à la condition que les instructions de tous les étages soient indépendantes c'est-à-dire que l'exécution de chacune ne modifie pas le résultat du calcul d'une autre. Les processeurs de ce types sont appelés superscalaires. Le premier ordinateur à être équipé de ce type de processeur était le Seymour Cray CDC 6600 en 1965. L'Intel Pentium est le premier des processeurs superscalaires pour compatible PC. Ce type de processeur s'est imposé pour les machines grand public à partir des années 1980 et jusqu'aux années 1990^[8].

L'exemple canonique de ce type de pipeline est celui d'un processeur RISC, en cinq étapes. L'Intel Pentium 4 dispose de 35 étages de pipeline^[9]. Un compilateur optimisé pour ce genre de processeur fournira un code plus rapide.

Aujourd'hui, les concepteurs de processeur ne cherchent pas simplement à exécuter plusieurs instructions indépendantes en même temps, ils cherchent à optimiser le temps d'exécution de l'ensemble des instructions. Par exemple le processeur peut trier les instructions de manière à ce que tous ces étages contiennent des instructions indépendantes. Ce mécanisme développé par IBM s'appelle l'exécution out-of-order.

Pour éviter une perte de temps liée à l'attente de nouvelles instructions et surtout le délai de rechargement du contexte entre chaque changement de threads, les fondeurs ont ajouté à leurs processeurs des techniques pour que les threads puissent partager les pipelines, caches et registres. Cette technique, appelée Simultaneous Multi Threading, a été mise au point dans les années 1950. Par contre, pour obtenir une accélération, les compilateurs doivent prendre en compte cette spécificité, il faut donc recompiler les programmes pour ces types de processeurs. Intel a commencé à produire, début des années 2000, des processeurs de technologie SMT à deux voies. Ces processeurs, les Pentium 4, peuvent exécuter simultanément deux Threads qui partagent les mêmes Pipelines, caches et registres. Intel a appelé sa technologie SMT à deux voies : l’Hyperthreading. Le Super-threading est une technologie SMT où plusieurs threads partagent aussi les mêmes ressources, mais ces threads ne s'exécutent que l'un après l'autre et non pas en même temps.

architecture du 486DX2 avec son FPU.

Depuis longtemps déjà, existait l'idée de faire cohabiter plusieurs processeurs au sein du même composant comme par exemple les System on Chip. Cela consistait par exemple à ajouter au processeur, un coprocesseur arithmétique, un DSP, un contrôleur comme celui qui gère l'HyperTransport pour les x86 à partir de l'Opteron d'AMD en 2003, voir un cache mémoire ou même à l'intégralité des composants que l'on trouve sur une carte mère. Le premier processeur de la gamme x86 à intégrer un Floating-point unit est le 486 DX début 1989. Des processeurs utilisant deux ou quatre cœurs, pas forcément symétrique comme les cell, sont donc apparus comme par exemple le POWER4 d'IBM sorti en 2001. Ils disposent des technologies citées préalablement. Les ordinateurs qui disposent de ce type de processeurs coûtent moins cher que les ordinateurs qui disposent de plusieurs processeurs, cependant en comparaison, les performances sont plus ou moins honorables en fonction du type de problème traité. Si, en comparaison d'un système à multiprocesseur, le partage du cache favorise la vitesse, le partage du bus mémoire en revanche la diminue. Des API spécialisées ont été développées afin de tirer parti au mieux de cette technologie, comme le Threading Building Blocks d'Intel.

Les systèmes à plusieurs processeurs

Le Blue Gene L disposent seize cartes-nœuds (à gauche) pour un total de 440 cœurs organisés suivant le schéma de droite

L'idée de faire cohabiter deux processeurs dans la même machine date également des années 1960, le D825 de Burroughs Corporation commercialisé en 1962 est le premier ordinateur multi-processeur, mais ce système n'était pas parallèle^[10]. Il a fallu attendre 1969 pour que Honeywell produise le premier ordinateur qui dispose de processeurs fonctionnant réellement en parallèle. Les huit processeurs^[11] de cette machine de la série Honeywell 800 fonctionnaient de manière symétrique^[12] (ou SMP), c'est-à-dire que tous les processeurs ont la même fonction et les mêmes capacités. Ce ne fut pas le cas de toutes les machines, DEC et le MIT ont développé dans les années 1970 une technologie asymétrique, mais elle a été abandonnée dans les années 1980. Peu de machines ont utilisé ce principe, même si certaines ont eu du succès comme les VAX.

Dans un système symétrique les processeurs se synchronisent et échangent des données via un bus^[13].Historiquement, ces systèmes étaient limités à 32 processeurs^[14], en effet au delà, les contentions de bus deviennent ingérables. Cependant « Grâce à la petite taille des processeurs et à la réduction significative des exigences en bande passante du bus obtenue par la taille importante des caches, les systèmes à multiprocesseurs symétriques sont d'un excellent rapport coût-efficacité, à condition toutefois qu'il existe une bande passante mémoire suffisante »^[13]. Les architectures NUMA sont un exemple de solution. NUMA est un système où les zones mémoires sont accessibles par l'intermédiaire de différents bus, c'est-à-dire que chaque zone mémoire est réservée à un ou quelques processeurs seulement et que les données qui y sont stockées ne sont disponibles que via un passage de message analogue à celui mis en place pour les mémoires distribuées. Dans tous les cas, les temps d'accès diffèrent en fonction des processeurs et des zones mémoires visées. Ce système peut être vue comme une étape entre le SMP et le clustering.

Système à plusieurs machines

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

Les machines du TOP500 sont des machines de ce type.

• Grille informatique
• Grappe de serveurs

Technologie

Trois facteurs principaux ont contribué à la forte tendance actuelle en faveur du traitement parallèle.

Coût du matériel

Il a décru de manière constante, de sorte qu'il est aujourd'hui possible de construire des systèmes à multiprocesseurs à moindre coût.

Intégration à très grande échelle

La technologie des circuits a progressé à un tel point qu'il est devenu possible de fabriquer des systèmes complexes nécessitant des millions de transistors sur une seule puce.

On peut alors doubler ou tripler, voire davantage, quelques circuits de calcul sur cette même puce en la munissant de circuits de contrôle veillant à répartir les calculs entre eux, ainsi qu'à éviter les collisions que pourrait impliquer ce parallélisme.

Vitesse de traitement des ordinateurs

La vitesse des traitements séquentiels traditionnels, basés sur le modèle de von Neumann, semble s'approcher de la limite physique au-delà de laquelle il n'est plus possible d'accélérer. On peut en revanche disposer de :

• plusieurs processeurs dans la même puce,
• plusieurs puces sur la même carte mère,
• plusieurs cartes mères dans le même châssis.

C'est sur la combinaison de ces principes que sont construits les ordinateurs les plus puissants du moment (Roadrunner 2008).

Autres considérations plus nébuleuses

En gestion de projet, la parallélisation n'est pas toujours possible si certaines tâches doivent obligatoirement précéder d'autres. Par exemple, pour la construction d'une maison, on montera un mur avant d'essayer de le peindre. Ces deux tâches ne sont donc pas parallélisables.

À l'inverse, certaines tâches peuvent facilement être réparties sur un grand nombre de processeurs. Par exemple, la composition d'une image de synthèse peut se subdiviser en autant de sous-tâches que de pixels à l'écran. On parle alors de répartition "massivement parallèle".

Historique

L'un des premiers modèles de cohérence pour la programmation concourante est celui de Leslie Lamport, c'est celui de la cohérence séquentielle. Il implique que les données produites par un programme concurrent soit les mêmes que celui produit par un programme séquentiel ou plus précisément un programme est séquentiellement cohérent si « les résultats de toute exécution est le même que si les opérations de tous les processeurs sont exécutées dans un ordre séquentiel, et les opérations de chaque processeur individuelles apparaissent dans cette séquence dans l'ordre indiqué par son programme »^[15].

• 1962 Première tentative de rationalisation d'accès cohérent à la mémoire l'a été par Carl Adam Petri dans sa thèse sur les réseaux de Petri.
• 1962 le D825 de Burroughs Corporation est le premier ordinateur multi-processeur, mais un système non parallèle^[10].
• 1964 le CDC 6600, premier double core et premier a ordinateur structure parallèle.
• Début des années 1970, la théorie du flot de données à rapidement permet de mettre en œuvre les Architecture Dataflow qui implémente cette théorie.
• En 1969, la société Honeywell lance son premier système Multics, un système à multiprocesseur symétrique capable de gérer jusqu'à huit processeurs en parallèle.
• À partir de la fin des années 1970, l'algèbre de processus de processus tels que celle du Calculus of Communicating Systems et du Communicating sequential processes en 1978 ont été développés pour permettre de modéliser l'interaction des processus dans un systèmes.
• 1982 Cray X-MP, deux Cray I mis en parallèle.
• 1986, premier ordinateur massivement parallèle avec 16 000 processeurs.
• Début des années 1990 l'algèbre de calcul comme celle du Pi-calcul permettent de raisonner sur des typologies dynamiques. La logique modale de Lamport, appelée TLA+ et d'autres modélisations, comme les théories des traces et du modèle d'acteur, ont également été développés pour décrire le comportement des systèmes concurrent.
• 2005, apparition des microprocesseurs multicoeur pour les ordinateurs personnels
• 2010, Intel produit un microprocesseur avec 128 cœurs

Notes et références

1. ↑ (Computer Organization and Design, p. 748)
2. ↑ Amdahl, G., The validity of the single processor approach to achieving large-scale computing capabilities, AFIPS Press, coll. « In Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J. », Avril 1967, pp. 483–85 p. 
3. ↑ Cramming more components onto integrated circuits, Electronics Magazine, 1965. Consulté le 2006-11-11
4. ↑ (en)Le Sidney Fernbach Award given to MPI inventor Bill Gropp faisant référence à MPI comme le the dominant HPC communications interface c'est-à-dire l'interface de communication HPC dominant
5. ↑ Bernstein, A. J. (October 1966). "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers". EC-15, pp. 757–62.
6. ↑ Roosta, Seyed H. (2000). "Parallel processing and parallel algorithms: theory and computation". Springer, p. 114. ISBN 0-387-98716-9.
7. ↑ Définitions lexicographiques et étymologiques de « atome » du CNRTL.
8. ↑ (Culler et al, p. 15)
9. ↑ Patt, Yale (April 2004). "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? (wmv). Distinguished Lecturer talk at Carnegie Mellon University. Retrieved on November 7, 2007.
10. ↑ ^{a et b} Enslow, Philip H., Jr., "Multiprocessor Organization - A Survey", Computing Surveys, Vol. 9, March 1977, pp.103-129.
11. ↑ http://ctbp.ucsd.edu/pc/html/intro4.html
12. ↑ http://www.feb-patrimoine.com/PROJET/honeywell200/h-200.htm
13. ↑ ^{a et b} (Patterson et all, 1998, p. 549)
14. ↑ (Patterson et all, 1998, p. 719)
15. ↑ Lamport, Leslie (September 1979). "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Transactions on Computers, C-28,9, pp. 690–91.

Voir aussi

Bibliographie

• (en) Patterson, David A. et John L. Hennessy, Computer Organization and Design, Morgan Kaufmann Publishers, 1998 (réimpr. Second Edition) (ISBN 1558604286) .
• Culler, David E.; Jaswinder Pal Singh and Anoop Gupta (1999)., Parallel Computer Architecture - A Hardware/Software Approach, Morgan Kaufmann Publishers (ISBN 1558603433) .

Articles connexes

Logiciels

• BOINC!

Sujets généraux

• Carte mère
• Programmation concurrente, Théorie de la complexité des algorithmes
• Allocation de ressources
• Very Long Instruction Word
• Compilation matérielle
• Automate cellulaire
• Hypercube

Langages de programmation

• Ada
• Ateji PX - Programmation parallèle Java
• Erlang
• Alpha
• C
• UPC
• Fortran
• Linda
• Occam
• Parsec
• Sisyc
• C# (C Sharp), VB.Net (Visual Basic .NET), J# (J Sharp), F# (F Sharp) avec la nouvelle Bibliothèque Parallèle de Tâches (Task Parallel Library) et l'évolution vers le parallélisme de LINQ en PLINQ de la plate-forme .Net version 4.0

Bibliothèque de programmation

• Message Passing Interface
• PVM
• MapReduce

Liens externes

• (en) Internet Parallel Computing Archive
• (en) IEEE Distributed systems online
• (en) HPCC Grand Challenges
• (en) Nan's Parallel Computing Page
• (fr) Cours d'Université belge sur la programmation concurrente en Java, avec quelques considérations matériels.
• (fr) Bibliothèque parallèle de tâches (Task Parallel Library).
• (fr) PLINQ.
• (en) OpenHMPP, New Standard for Manycore