Algorithme parallèle

informatique , un algorithme parallèle , par opposition à un algorithme séquentiel classique , est un algorithme capable d'effectuer plusieurs opérations dans un même laps de temps. Il est courant en informatique de décrire les algorithmes séquentiels à l'aide de modèles de machines abstraites , souvent celle appelée machine à accès aléatoire . De même, de nombreux chercheurs en informatique ont utilisé une machine à accès aléatoire parallèle (PRAM) comme modèle de machine abstraite parallèle (à mémoire partagée).

De nombreux algorithmes parallèles sont exécutés simultanément – bien que les algorithmes concurrents constituent généralement un concept distinct – et ces concepts sont donc souvent confondus, sans que l'on distingue clairement ce qui est parallèle et ce qui est concurrent dans un algorithme. De plus, les algorithmes non parallèles et non concurrents sont souvent qualifiés d'« algorithmes séquentiels », par opposition aux algorithmes concurrents.

parallélisables de façon embarrassante . Par exemple, de nombreux algorithmes permettent de résoudre le Rubik's Cube et de trouver les valeurs qui produisent un hachage donné .les méthodes numériques, telles quela méthode de Newton, les solutions itératives duproblème des trois corpset la plupart des algorithmes disponibles pour calculerpi(π).Certains algorithmes séquentiels peuvent être convertis en algorithmes parallèles grâce àla parallélisation automatique.

Dans de nombreux cas, la mise au point d'un algorithme parallèle efficace pour résoudre une tâche nécessite le développement de nouvelles idées et méthodes qui ne sont pas nécessaires à la conception d'un algorithme séquentiel pour résoudre le même problème. À titre d'exemples, on peut citer les problèmes d'importance pratique que sont la recherche d'un élément cible dans une structure de données et l'évaluation d'une expression algébrique.

Motivation

L'exécution d'algorithmes parallèles sur des dispositifs individuels s'est généralisée depuis le début des années 2000 grâce aux progrès considérables réalisés dans les systèmes multiprocesseurs et à l'essor des processeurs multicœurs . Jusqu'à fin 2004, les performances des processeurs monocœurs augmentaient rapidement grâce à l'augmentation de leur fréquence . Il était donc plus simple de concevoir un ordinateur doté d'un seul cœur rapide qu'un ordinateur équipé de plusieurs cœurs plus lents offrant le même débit , ce qui limitait l'utilisation des systèmes multicœurs. Depuis 2004, cependant, l'augmentation de la fréquence a atteint ses limites, et les systèmes multicœurs se sont largement répandus, rendant les algorithmes parallèles plus largement applicables.

Problèmes

Communication

Le coût ou la complexité des algorithmes séquentiels est estimé en fonction de l'espace mémoire (mémoire) et du temps (cycles processeur) qu'ils occupent. Les algorithmes parallèles doivent optimiser une ressource supplémentaire : la communication entre les différents processeurs. Il existe deux modes de communication entre les processeurs parallèles : la mémoire partagée et l'échange de messages.

Le traitement en mémoire partagée nécessite un verrouillage supplémentaire des données, impose une surcharge liée à des cycles processeur et bus supplémentaires, et sérialise également une partie de l'algorithme.

Le traitement par passage de messages utilise des canaux et des boîtes de messages, mais cette communication engendre une surcharge de transfert sur le bus, des besoins en mémoire supplémentaires pour les files d'attente et les boîtes de messages, ainsi qu'une latence dans la transmission des messages. Les processeurs parallèles utilisent des bus spéciaux, comme les bus crossbar, afin de minimiser cette surcharge de communication ; toutefois, c'est l'algorithme parallèle qui détermine le volume du trafic.

Si la surcharge de communication des processeurs supplémentaires l'emporte sur l'avantage d'ajouter un autre processeur, on rencontre un ralentissement parallèle .

Équilibrage de charge

équilibrage de charge adéquat , c'est-à-dire un équilibre de la charge totale (travail global) plutôt que de la taille des entrées. Par exemple, la vérification de la primalité de tous les nombres de un à cent mille est facile à répartir entre les processeurs. Cependant, si les nombres sont simplement répartis équitablement (1–1 000, 1 001–2 000, etc.), la charge de travail sera déséquilibrée. En effet, les petits nombres sont plus faciles à traiter par cet algorithme (leur primalité est plus facile à vérifier), et certains processeurs auront donc plus de travail que d'autres, qui resteront inactifs jusqu'à ce que les processeurs les plus sollicités aient terminé.

Algorithmes distribués

Les algorithmes distribués , un sous-type d'algorithmes parallèles , sont des algorithmes conçus pour fonctionner dans des environnements de calcul en grappes et de calcul distribué , où des problématiques supplémentaires, au-delà du champ d'application des algorithmes parallèles « classiques », doivent être prises en compte.

Les algorithmes distribués sont conçus pour s'exécuter sur un réseau d'ordinateurs interconnectés communiquant par mémoire partagée ou par échange de messages. Contrairement aux algorithmes parallèles classiques, ils doivent fonctionner sous des contraintes supplémentaires telles que des connaissances locales limitées, des délais de communication, l'absence d'état global et la possibilité de défaillances de nœuds.

Les algorithmes distribués s'intéressent aux problèmes de coordination qui surviennent dans les systèmes distribués, notamment l'élection d'un leader , l'exclusion mutuelle et le consensus (informatique) . Ces problèmes sont étudiés dans le cadre de différents modèles de systèmes avec des hypothèses variables, par exemple si le système est synchrone ou asynchrone et s'il existe des défaillances, telles que des pannes par plantage ou des défaillances byzantines .

Les algorithmes distribués ont de nombreuses applications pratiques dans les bases de données distribuées, les systèmes de tolérance aux pannes et les applications en réseau à grande échelle.