Algorithme parallèle - Parallel algorithm

En informatique , un algorithme parallèle , par opposition à un algorithme sériel traditionnel , est un algorithme qui peut effectuer plusieurs opérations dans un temps donné. C'est une tradition de l' informatique de décrire des algorithmes en série dans des modèles de machines abstraits , souvent celui connu sous le nom de machine à accès aléatoire . De même, de nombreux chercheurs en informatique ont utilisé une machine dite parallèle à accès aléatoire (PRAM) comme machine abstraite parallèle (mémoire partagée).

De nombreux algorithmes parallèles sont exécutés simultanément - bien qu'en général, les algorithmes simultanés soient un concept distinct - et donc ces concepts sont souvent confondus, avec quel aspect d'un algorithme est parallèle et lequel est simultané n'est pas clairement distingué. En outre, les algorithmes non parallèles et non simultanés sont souvent appelés « algorithmes séquentiels », par opposition aux algorithmes concurrents.

Parallélisabilité

Les algorithmes varient considérablement dans leur degré de parallélisation, allant de facilement parallélisables à complètement non parallélisables. De plus, un problème donné peut accueillir différents algorithmes, qui peuvent être plus ou moins parallélisables.

Certains problèmes sont faciles à diviser en morceaux de cette manière – on les appelle des problèmes parallèles embarrassants . Les exemples incluent de nombreux algorithmes pour résoudre les Rubik's Cubes et trouver des valeurs qui aboutissent à un hachage donné .

Certains problèmes ne peuvent pas être divisés en portions parallèles, car ils nécessitent les résultats d'une étape précédente pour passer efficacement à l'étape suivante - on les appelle problème intrinsèquement sériel s. Les exemples incluentles méthodes numériquesitératives, telles quela méthode de Newton, les solutions itératives au problème àtrois corpset la plupart des algorithmes disponibles pour calculerpi(π). Certains algorithmes séquentiels peuvent être convertis en algorithmes parallèles à l'aide dela parallélisation automatique.

Motivation

Les algorithmes parallèles sur des appareils individuels sont devenus plus courants depuis le début des années 2000 en raison des améliorations substantielles apportées aux systèmes multiprocesseurs et de l'essor des processeurs multicœurs . Jusqu'à la fin de 2004, les performances des processeurs monocœur ont rapidement augmenté via la mise à l'échelle de la fréquence , et il était donc plus facile de construire un ordinateur avec un seul cœur rapide qu'un ordinateur avec de nombreux cœurs plus lents avec le même débit , de sorte que les systèmes multicœurs étaient plus limités. utilisation. Depuis 2004, cependant, la mise à l'échelle des fréquences s'est heurtée à un mur et les systèmes multicœurs se sont donc répandus, rendant les algorithmes parallèles d'une utilisation plus générale.

Problèmes

la communication

Le coût ou la complexité des algorithmes sériels est estimé en termes d'espace (mémoire) et de temps (cycles de processeur) qu'ils prennent. Les algorithmes parallèles doivent optimiser une ressource supplémentaire, la communication entre les différents processeurs. Les processeurs parallèles communiquent de deux manières, la mémoire partagée ou la transmission de messages.

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

Le traitement du passage des messages utilise des canaux et des boîtes de message, mais cette communication ajoute une surcharge de transfert sur le bus, un besoin de mémoire supplémentaire pour les files d'attente et les boîtes de message et une latence dans les messages. Les conceptions de processeurs parallèles utilisent des bus spéciaux comme la barre transversale afin que la surcharge de communication soit faible, mais c'est l'algorithme parallèle qui décide du volume du trafic.

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

L'équilibrage de charge

Un autre problème avec les algorithmes parallèles est de s'assurer qu'ils sont correctement équilibrés en charge , en s'assurant que la charge (travail global) est équilibrée, plutôt que la taille d'entrée étant équilibrée. Par exemple, vérifier tous les nombres de un à cent mille pour la primalité est facile à répartir entre les processeurs ; cependant, si les nombres sont simplement répartis uniformément (1 à 1 000, 1 001 à 2 000, etc.), la quantité de travail sera déséquilibrée, car les nombres plus petits sont plus faciles à traiter par cet algorithme (plus facile à tester pour la primalité), et ainsi, certains processeurs auront plus de travail que d'autres, qui resteront inactifs jusqu'à ce que les processeurs chargés soient terminés.

Algorithmes distribués

Un sous-type d'algorithmes parallèles, les algorithmes distribués , sont des algorithmes conçus pour fonctionner dans des environnements informatiques en grappes et informatiques distribués , où des problèmes supplémentaires dépassant le cadre des algorithmes parallèles « classiques » doivent être résolus.

Voir également

Les références

Liens externes