vignette|redresse|Un éléments de Blue Gene L cabinet, l'un des supercalculateurs massivement parallèles les plus rapides des années 2000.
En informatique, le parallélisme est la caractéristique des architectures d'électronique numérique qui leur permet de traiter des informations de manière simultanée, ainsi que les algorithmes spécialisés pour celles-ci. Ces techniques ont pour but de réaliser le plus grand nombre d'opérations en un temps le plus petit possible.
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. 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.
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 de manière théorique et sur des superordinateurs, qui étaient à une période les seuls à compter de nombreux processeurs, mais sont de plus en plus volontiers utilisées par les développeurs de logiciel du fait de l'omniprésence de telles architectures.
Certains types de calculs se prêtent particulièrement bien à la parallélisation : la dynamique des fluides, les prédictions météorologiques, la modélisation et simulation de problèmes de dimensions plus grandes, le traitement de l'information et l'exploration de données, le décryptage de messages, la recherche de mots de passe, le traitement d'images ou la fabrication d'images de synthèse, tels que le lancer de rayon, l'intelligence artificielle et la fabrication automatisée. Initialement, c'est dans le domaine des supercalculateurs que le parallélisme a été utilisé, à des fins scientifiques.
Principes Les premiers ordinateurs étaient séquentiels, exécutant les instructions l'une après l'autre. Le parallélisme se manifeste actuellement de plusieurs manières : en juxtaposant plusieurs processeurs séquentiels ou en exécutant simultanément des instructions indépendantes.
Différents types de parallélisme : la taxonomie de Flynn +Tableau récapitulatif de la taxonomie de Flynn Une seule instruction Plusieurs instructions Donnée unique SISD MISD Plusieurs données SIMD MIMD
La taxonomie de Flynn, proposée par l'Américain Michael J. Flynn, est l'un des premiers systèmes de classification des ordinateurs créés. 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 : ces systèmes sont dits « séquentiels ». Ce type de fonctionnement était prédominant pour les ordinateurs personnels jusqu'à la fin des années 1990. On parle d'architectures SISD (Single Instruction, Single Data). Les systèmes traitant 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. Les systèmes utilisant plusieurs processeurs ou un processeur multi-cœur sont plus polyvalents et pleinement parallèles, ce sont des MIMD (). 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 en réseau systolique est un type d'architecture MISD.
Selon David A. Patterson et John L. Hennessy,
Cette approche montre clairement deux types de parallélismes différents : le parallélisme par flot d'instructions, également nommé parallélisme de traitement ou de contrôle, où plusieurs instructions différentes sont exécutées simultanément, qui correspond au MIMD, et le parallélisme de données, où les mêmes opérations sont répétées sur des données différentes, le SIMD.
Efficacité du parallélisme vignette|upright=1.4|Représentation 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 × 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. Cependant, très peu de programmes peuvent prétendre à de telles performances. Dans les années 1960, Gene Amdahl formula une loi empirique restée célèbre, à laquelle il donna son nom.. 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 tout programme 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 le ratio de code parallélisable 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. Plus optimiste, elle prend quant à elle en compte le cas où il est possible d'augmenter la quantité de données sur lesquelles des calculs sont effectués en parallèle : une augmentation du nombre d'unités de calcul permet alors de traiter plus de données en un temps équivalent, alors que la loi d'Amdahl fixe une limite d'efficacité à quantité de données égale.
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écution des instructions qui mettent en œuvre le parallélisme.
Plus simplement, Jean Ichbiah montrait qu'en supposant un overhead même léger pour le lancement de chaque processus, il existe un degré optimal de parallélisme, au-delà duquel il est inefficace. Le temps d'exécution est alors du style T(n) = a + b*n + (T(1)-a)/n. Avec T(1)=1, a =0,1 et b=0,005 il vient T(n)= 0,1+0,005n+0,9/n, minimal pour n valant 13 ou 14.
Autres considérations empiriques vignette|upright=1.4|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 , cette observation est appelée la loi de Moore.. En dépit de problèmes de consommation énergétique, la loi de Moore est toujours valable en 2010 (c'est moins vrai en 2020). Les transistors supplémentaires, toujours plus petits, permettent de créer plusieurs unités de calcul, appelées cœurs, au sein du même processeur.
Historique vignette|upright=1|L'ILLIAC IV, : .
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 soient les mêmes que celui produit par un programme séquentiel ou plus précisément un programme est séquentiellement cohérent si ..
1962 : première tentative de rationalisation d'accès cohérent à la mémoire, 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. 1964 : le CDC 6600, premier double cœur et premier ordinateur à structure parallèle. Début des années 1970 : la théorie du flot de données permet de mettre en œuvre les architectures à flots de données. 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. Fin des années 1970 : les algèbres de processus telles que Calculus of Communicating Systems et Communicating sequential processes en 1978 sont développées pour permettre de modéliser l'interaction des processus dans un système. 1982 : conception du Cray X-MP, deux Cray-1 mis en parallèle. 1986 : premier ordinateur massivement parallèle avec processeurs. Début des années 1990 : le Pi-calcul permet 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 concurrents. 2005 : apparition des microprocesseurs multicœurs pour les ordinateurs personnels. 2010 : Intel produit un microprocesseur avec 128 cœurs.
Les programmes Un programme parallèle est divisé en plusieurs tâches séquentielles s'exécutant simultanément, habituellement appelées processus et peuvent être de plusieurs types selon le système d'exploitation ou la machine virtuelle.
Un tel parallélisme de tâche correspond à une architecture MIMD. En anglais, on parle de TLP ().
Certains processus sont dits légers, les anglophones utilisant plutôt le mot Thread, qui peut se traduire par fil d'exécution. Les threads plus légers encore utilisés par certaines architectures sont appelés fibers en anglais, c'est-à-dire fibres en français.
Les synchronisations
Des processus différents peuvent s'exécuter sur des processeurs différents. Plusieurs défis ont donc dû être relevés par la programmation de système parallèle, par exemple celui de traiter des informations sur des processeurs indépendants.
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. Ils découlent des interactions entre les processus (échange de données, attente...), qui peuvent causer des erreurs ou des blocages si le programmeur les gère mal.
Dans le problème « producteur-consommateur », des processus dits « producteurs » produisent des données qui sont posées dans une file d'attente, une ressource bornée, ces données sont consommées par les processus dits « consommateurs ». Le fait que la ressource soit bornée 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.