Théorie et pratique du parallélisme algorithmique

Ce texte traite de la théorie et de la pratique du parallélisme algorithmique, un domaine essentiel en informatique pour améliorer les performances des programmes en exploitant plusieurs processeurs simultanément. Il s’adresse aux étudiants et chercheurs en informatique, notamment ceux qui souhaitent comprendre comment concevoir, analyser et optimiser des algorithmes parallèles.

La question

Le travail aborde le problème fondamental de la parallélisation des algorithmes : comment découper un algorithme séquentiel en tâches pouvant être exécutées en parallèle, puis comment ordonnancer ces tâches sur plusieurs processeurs afin de minimiser le temps total d’exécution. Cette question est cruciale car elle permet d’exploiter efficacement les architectures parallèles modernes, mais elle est complexe en raison des dépendances entre tâches, des contraintes matérielles et des coûts de communication.

Concepts de base

Pour comprendre la parallélisation algorithmique, plusieurs notions clés sont nécessaires :

Notion de tâche

Une tâche est une unité indivisible de traitement caractérisée par ses entrées, sorties, instructions et temps d’exécution. Ce temps comprend généralement le calcul et les communications nécessaires. Les tâches peuvent être liées par des dépendances qui imposent un ordre d’exécution séquentiel, ou être indépendantes et donc exécutables en parallèle.

Granularité

La granularité désigne la taille des tâches dans la décomposition d’un algorithme. Par exemple, dans un produit matriciel C = A * B :

• Granularité fine : chaque opération élémentaire C(i,j) = C(i,j) + A(i,k)*B(k,j) est une tâche.
• Granularité moyenne : chaque tâche calcule un élément de la matrice C.
• Granularité grosse : chaque tâche calcule une ligne ou une colonne entière du produit.

Le choix de la granularité dépend du nombre de processeurs, du rapport entre temps de communication et de calcul, des accès mémoire, etc. C’est un compromis important pour optimiser les performances.

Système de tâches et relation de précédence

Un système de tâches S = (T1, …, Tn, <<) est un ensemble de tâches muni d’une relation d’ordre partiel << qui exprime les contraintes de précédence : Ti << Tk signifie que la tâche Ti doit être terminée avant que Tk ne commence. Deux tâches sont indépendantes si elles ne modifient aucune variable commune, sinon elles sont dépendantes. Le système de précédence traduit les contraintes d’exécution séquentielle et le parallélisme possible.

Graphe de précédence

Le graphe de précédence G associé à un système de tâches est un graphe orienté acyclique (DAG) où les sommets sont les tâches et les arcs représentent les relations de précédence entre tâches consécutives. Ce graphe permet de visualiser et d’analyser les contraintes d’ordonnancement.

Ordonnancement des tâches

L’ordonnancement consiste à affecter à chaque tâche une date d’exécution et un processeur, en respectant les contraintes de précédence et les ressources matérielles. L’objectif principal est souvent de minimiser le temps total d’exécution (makespan). Ce problème est difficile, surtout quand le nombre de processeurs est limité et que les tâches ont des durées variables.

Complexité des algorithmes parallèles

La complexité est une mesure clé de performance, évaluée par :

• Le temps d’exécution total.
• Le nombre de processeurs utilisés.
• Le coût de l’algorithme, défini comme le produit du temps d’exécution par le nombre de processeurs.

Un algorithme est dit optimal s’il s’exécute en temps minimal parmi toutes les versions possibles. L’efficacité asymptotique mesure la qualité d’un algorithme parallèle quand la taille du problème tend vers l’infini.

Décomposition en niveaux et largeur du graphe

Le graphe de tâches peut être décomposé en niveaux, chaque niveau regroupant des tâches pouvant être exécutées en parallèle. La hauteur H(G) est la longueur du plus long chemin dans le graphe (le chemin critique). La largeur L(D) d’une décomposition est la taille maximale d’un niveau. La largeur minimale L(G) parmi toutes les décompositions correspond au nombre minimal de processeurs nécessaires pour atteindre le temps optimal.

Approche

La méthode proposée pour paralléliser un algorithme sur une machine donnée se déroule en plusieurs étapes :

1. Partitionner l’algorithme en tâches, qui peuvent être des instructions ou groupes d’instructions. Ce partitionnement peut être automatique ou manuel.
2. Construire le graphe de précédence pour définir les contraintes temporelles et identifier les tâches indépendantes susceptibles d’être exécutées en parallèle.
3. Ordonnancer les tâches sur les processeurs en respectant les contraintes de dépendance et les ressources matérielles.

Différentes versions parallèles d’un même algorithme peuvent exister selon le découpage, l’accès aux données, l’affectation des tâches aux processeurs, etc. Le choix de la meilleure version dépend des performances sur la machine ciblée.

Résultats

Le travail présente plusieurs résultats importants :

• Avec un nombre illimité de processeurs, le temps d’exécution optimal topt est égal à la durée du plus long chemin dans le graphe de tâches, c’est-à-dire la hauteur H(G) du graphe.
• Le nombre minimal de processeurs popt nécessaires pour réaliser cet algorithme en temps topt est égal à la largeur L(G) du graphe, c’est-à-dire la taille minimale maximale d’un niveau dans une décomposition en niveaux.
• Des décompositions en niveaux différentes existent (par prédécesseur, par successeur, ou autres), chacune donnant lieu à un ordonnancement parallèle avec des largeurs et donc des nombres de processeurs différents.
• Le problème d’ordonnancement avec un nombre fixé de processeurs est reconnu comme difficile et reste ouvert.

Limitations et questions ouvertes

Le texte souligne que :

• Le modèle utilisé suppose une architecture MIMD à mémoire partagée idéalisée, négligeant les temps de transfert des données, ce qui peut limiter la précision des résultats dans des architectures réelles.
• Le problème d’ordonnancement optimal avec un nombre fixé de processeurs est complexe et non résolu de manière générale.
• Le choix de la granularité optimale dépend de nombreux facteurs liés à la machine et au problème, ce qui rend la parallélisation adaptée à chaque contexte.

Glossaire

• Tâche : unité indivisible de traitement dans un algorithme parallèle.
• Granularité : taille des tâches dans la décomposition d’un algorithme.
• Système de tâches : ensemble de tâches avec une relation d’ordre partiel exprimant les dépendances.
• Relation de précédence (<<) : contrainte indiquant qu’une tâche doit être terminée avant une autre.
• Graphe de précédence : graphe orienté acyclique représentant les dépendances entre tâches.
• Ordonnancement : affectation des tâches à des processeurs et à des moments précis.
• Makespan : temps total d’exécution d’un ensemble de tâches ordonnancées.
• Hauteur du graphe (H(G)) : longueur du plus long chemin dans le graphe de tâches.
• Largeur du graphe (L(G)) : taille minimale maximale d’un niveau dans une décomposition en niveaux.
• Algorithme optimal : algorithme s’exécutant en temps minimal possible.
• Efficacité asymptotique : mesure de la performance d’un algorithme parallèle quand la taille du problème tend vers l’infini.