Analyse d'algorithmes parallèles - Analysis of parallel algorithms

En informatique, l'analyse des algorithmes parallèles est le processus consistant à trouver la complexité de calcul des algorithmes exécutés en parallèle - la quantité de temps, de stockage ou d'autres ressources nécessaires pour les exécuter. À bien des égards, l' analyse d'algorithmes parallèles est similaire à l' analyse d'algorithmes séquentiels , mais est généralement plus complexe car il faut raisonner sur le comportement de plusieurs threads d'exécution coopérants. L'un des principaux objectifs de l'analyse parallèle est de comprendre comment l'utilisation des ressources d'un algorithme parallèle (vitesse, espace, etc.) change à mesure que le nombre de processeurs change.

Contexte

Un cadre dit de temps de travail (WT) (parfois appelé profondeur de travail ou durée de travail) a été introduit à l'origine par Shiloach et Vishkin pour conceptualiser et décrire des algorithmes parallèles. Dans le cadre WT, un algorithme parallèle est d'abord décrit en termes de tours parallèles. Pour chaque tour, les opérations à effectuer sont caractérisées, mais plusieurs problèmes peuvent être supprimés. Par exemple, le nombre d'opérations à chaque tour n'a pas besoin d'être clair, les processeurs n'ont pas besoin d'être mentionnés et toute information pouvant aider à l'affectation des processeurs aux tâches n'a pas besoin d'être prise en compte. Deuxièmement, les informations supprimées sont fournies. L'inclusion des informations supprimées est guidée par la preuve d'un théorème d'ordonnancement dû à Brent, qui est expliqué plus loin dans cet article. Le cadre WT est utile car bien qu'il puisse grandement simplifier la description initiale d'un algorithme parallèle, l'insertion des détails supprimés par cette description initiale n'est souvent pas très difficile. Par exemple, le cadre WT a été adopté comme cadre de présentation de base dans les livres d'algorithmes parallèles (pour le modèle PRAM de machine à accès aléatoire parallèle ) et, ainsi que dans les notes de cours. L'aperçu ci-dessous explique comment le cadre WT peut être utilisé pour analyser des algorithmes parallèles plus généraux, même lorsque leur description n'est pas disponible dans le cadre WT.

Définitions

Supposons que les calculs soient exécutés sur une machine qui a p processeurs. Soit T _p le temps qui s'écoule entre le début du calcul et sa fin. L'analyse du temps d'exécution du calcul porte sur les notions suivantes :

• Le travail d'un calcul exécuté par p processeurs est le nombre total d'opérations primitives que les processeurs effectuent. En ignorant le surcoût de communication de la synchronisation des processeurs, celui-ci est égal au temps utilisé pour exécuter le calcul sur un seul processeur, noté T ₁ .
• La profondeur ou l' étendue est la longueur de la plus longue série d'opérations qui doivent être exécutées séquentiellement en raison des dépendances de données (le chemin critique ). La profondeur peut également être appelée la longueur du chemin critique du calcul. Minimiser la profondeur/l'étendue est important dans la conception d'algorithmes parallèles, car la profondeur/l'étendue détermine le temps d'exécution le plus court possible. Sinon, la durée peut être définie comme le temps T _∞ passé calcul en utilisant une machine idéalisée avec un nombre infini de processeurs.
• Le coût du calcul est la quantité pT _p . Cela exprime le temps total passé, par tous les processeurs, à la fois en calcul et en attente.

Plusieurs résultats utiles découlent des définitions du travail, de la portée et du coût :

• Droit du travail . Le coût est toujours au moins le travail: pT _p ≥ T ₁ . Ceci résulte du fait que p processeurs peuvent effectuer au plus p opérations en parallèle.
• Loi de l'envergure . Un nombre fini p de processeurs ne peut surpasser un nombre infini, de sorte que T _p ≥ T _∞ .

En utilisant ces définitions et lois, les mesures de performance suivantes peuvent être données :

• Speedup est le gain en vitesse faite parexécutionparallèlerapport àexécution séquentielle: S _p = T ₁ / T _p . Lorsque l'accélération est Ω( n ) pour la taille d'entrée n (en utilisant la grande notation O ), l'accélération est linéaire, ce qui est optimal dans les modèles de calcul simples car la loi de travail implique que T ₁ ∕ T _p ≤ p ( accélération super-linéaire peut se produire dans la pratique en raison d'effets de hiérarchie de mémoire ). La situation T ₁ ∕ T _p = p est appelée accélération linéaire parfaite. Un algorithme qui présente une accélération linéaire est dit évolutif .
• L' efficacité est l'accélération par processeur, S _p / p .
• Le parallélisme est le rapport T ₁ ∕ T _∞ . Il représente l'accélération maximale possible sur n'importe quel nombre de processeurs. Par la loi de portée, le parallélisme limite le gain de vitesse: si p > T ₁ / T _∞ , alors:

${\displaystyle {\frac {T_{1}}{T_{p}}}\leq {\frac {T_{1}}{T_{\infty }}}<p}$ .

• Le relâchement est T ₁ / ( pT _∞ ) . Un jeu inférieur à un implique (par la loi de span) qu'une accélération linéaire parfaite est impossible sur p processeurs.

Exécution sur un nombre limité de processeurs

L'analyse des algorithmes parallèles est généralement effectuée en supposant qu'un nombre illimité de processeurs est disponible. C'est irréaliste, mais ce n'est pas un problème, puisque tout calcul pouvant s'exécuter en parallèle sur N processeurs peut être exécuté sur p < N processeurs en laissant chaque processeur exécuter plusieurs unités de travail. Un résultat appelé loi de Brent indique que l'on peut effectuer une telle "simulation" en temps T _p , borné par

${\displaystyle T_{p}\leq T_{N}+{\frac {T_{1}-T_{N}}{p}},}$

ou, moins précisément,

${\displaystyle T_{p}=O\gauche(T_{N}+{\frac {T_{1}}{p}}\droite).}$

Un énoncé alternatif de la loi délimite T _p au-dessus et au-dessous par

${\displaystyle {\frac {T_{1}}{p}}\leq T_{p}\leq {\frac {T_{1}}{p}}+T_{\infty }}$.

montrant que la durée (profondeur) T _∞ et le travail T ₁ fournissent ensemble des limites raisonnables sur le temps de calcul.

Les références