Aller au contenu

Algorithmes parallèles : principes et schémas de tâches

Algorithmes parallèles cours Ce cours sur les algorithmes parallèles aborde les principes fondamentaux de la parallélisation, le graphe de tâches, l'ordonnancement et la complexité des algorithmes. Les étudiants apprendront à partitionner des algorithmes en tâches, à établir des relations de précédence, et à optimiser l'exécution sur des architectures parallèles.

D'après le document Algorithmes parallèles : principes et schémas de tâches

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

Algorithmes parallèles : principes et schémas de tâches

Programming, Math, Parallel Algorithms · PDF · 33 pages

Afficher l'aperçu du document

Consulter le document original →

Algorithmes parallèles cours

Ce cours sur les algorithmes parallèles aborde les principes fondamentaux de la parallélisation, le graphe de tâches, l'ordonnancement et la complexité des algorithmes. Les étudiants apprendront à partitionner des algorithmes en tâches, à établir des relations de précédence, et à optimiser l'exécution sur des architectures parallèles. Des exemples pratiques et des exercices corrigés sont fournis pour illustrer chaque concept.

Principes de la parallélisation

La parallélisation d'un algorithme sur une machine donnée se fait en plusieurs étapes :

  1. Partitionner l'algorithme en tâches (instructions ou groupes d'instructions) : ce partitionnement peut être réalisé automatiquement par programme ou manuellement.
  2. Élaborer le graphe de précédence qui définit les contraintes temporelles pour l'exécution des tâches 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 contraintes matérielles liées à l'architecture de la machine.

Il est important de noter qu'un même algorithme peut conduire à plusieurs versions parallèles différentes selon :

  • l'accès aux données,
  • le découpage en tâches,
  • l'affectation des tâches aux processeurs.

Le choix de la version la plus performante dépendra de plusieurs facteurs, notamment l'architecture de l'ordinateur utilisé.

Exemple de parallélisation

Considérons un algorithme simple de multiplication de matrices. Pour paralléliser cet algorithme, nous pourrions partitionner les calculs en tâches qui effectuent chacune une opération élémentaire de la matrice. Cela permettrait d'exécuter plusieurs multiplications en parallèle, réduisant ainsi le temps d'exécution global.

Graphe de tâches

Le graphe de tâches est un outil essentiel pour visualiser les dépendances entre les différentes tâches d'un algorithme. Une tâche est définie comme une unité de traitement indivisible, caractérisée par son comportement extérieur, ses entrées, ses sorties, ses instructions et son temps d'exécution.

Notion de tâche

Le temps d'exécution d'une tâche est généralement la somme de deux termes : le temps de calcul et le temps de communication. L'étude des dépendances entre les tâches permet de construire un système de précédence qui traduit le parallélisme interne à l'algorithme.

Notion de granularité

La granularité d'une décomposition peut varier. Par exemple, pour le produit matriciel C = A * B :

  • Si les tâches sont les opérations élémentaires, la granularité est fine.
  • Si chaque tâche est le calcul d'un élément de C, la granularité est moyenne.
  • Si chaque tâche correspond au calcul d'une ligne ou d'une colonne, la granularité est grosse.

Le choix de la meilleure décomposition dépend des temps d'exécution des tâches et de l'architecture de la machine.

Système de tâches

Un système de tâches S = (T1,…,Tn, <<) est un ensemble de tâches avec une relation d'ordre partiel. Deux tâches Ti et Tk sont indépendantes si elles ne modifient aucune variable commune. Elles sont consécutives si aucune autre tâche n'existe entre elles dans l'ordre d'exécution.

Graphe de précédence

Le graphe de précédence G associé à un système de précédence est défini par l'ensemble des tâches et les relations de dépendance entre elles. Les contraintes de précédence forment un graphe de connexion sans circuit (DAG : Directed Acyclic Graph).

Ordonnancement de tâches

Dans un contexte informatique, ordonnancer des tâches revient à affecter à chaque tâche une date d'exécution et un processeur, sous contraintes de ressources. Le problème de l'allocation des tâches à un ensemble de processeurs est complexe.

Modèle de référence

Les tâches sont caractérisées par une durée d'exécution et éventuellement par une date au plus tôt ou au plus tard. La préemption n'est pas autorisée, ce qui signifie qu'une tâche ne peut pas être interrompue une fois commencée.

Objectif de l'ordonnancement

L'objectif principal est de minimiser le temps d'exécution total, également appelé makespan. Par exemple, un ordonnancement peut être représenté par un diagramme de Gantt qui montre comment les tâches sont réparties sur les processeurs.

Exemple d'ordonnancement

T1            T2
Processeurs
T3            T4            T5
P3             T5     T7
T6            T7
P2    T2     T4     T6
Temps libre
(temps d’inactivité)
P1    T1     T3               T8

Complexité des algorithmes parallèles

La complexité est une mesure cruciale de la performance d'un algorithme. L'analyse de la complexité permet de mesurer l'efficacité des algorithmes parallèles et de les comparer.

Définitions fondamentales

Le problème fondamental de la parallélisation est de trouver un ordonnancement optimal pour affecter les tâches aux processeurs tout en respectant le graphe de précédence. Cela doit être fait de manière à ce que l'algorithme s'exécute en temps minimal.

Théorèmes sur la complexité

Avec un nombre illimité de processeurs, le temps d'exécution optimal d'un algorithme est égal au temps d'exécution du plus long chemin du graphe des tâches. Le nombre minimal de processeurs nécessaires pour réaliser un algorithme en temps optimal est égal à la largeur du graphe des tâches.

Exemple de complexité

Considérons un graphe de tâches avec 8 tâches. Si le plus long chemin a un temps d'exécution de 4, alors le temps optimal est 4. Chaque décomposition en niveaux correspond à un algorithme parallèle.

Points clés à retenir

  • La parallélisation permet d'améliorer les performances des algorithmes.
  • Le graphe de tâches est essentiel pour visualiser les dépendances.
  • L'ordonnancement doit minimiser le temps d'exécution total.
  • La complexité est une mesure clé de l'efficacité des algorithmes.

Glossaire des termes clés

  • Parallélisation : Processus de décomposition d'un algorithme en tâches exécutables simultanément.
  • Graphe de tâches : Représentation des dépendances entre les tâches d'un algorithme.
  • Ordonnancement : Affectation des tâches à des processeurs en respectant les contraintes de précédence.
  • Complexité : Mesure de la performance d'un algorithme en fonction du temps d'exécution et des ressources utilisées.

Questions fréquentes

Qu'est-ce que la parallélisation d'un algorithme ?

La parallélisation d'un algorithme consiste à décomposer l'algorithme en plusieurs tâches qui peuvent être exécutées simultanément, ce qui permet d'améliorer l'efficacité et de réduire le temps d'exécution.

Comment fonctionne un graphe de tâches ?

Un graphe de tâches représente les dépendances entre les différentes tâches d'un algorithme. Chaque tâche est un nœud, et les arcs indiquent les relations de précédence, permettant de visualiser l'ordre d'exécution.

Quels sont les objectifs de l'ordonnancement des tâches ?

L'objectif principal de l'ordonnancement est de minimiser le temps d'exécution total des tâches sur les processeurs, tout en respectant les contraintes de dépendance et de ressources.

Comment évaluer la complexité d'un algorithme parallèle ?

La complexité d'un algorithme parallèle peut être évaluée en analysant le temps d'exécution et le nombre de processeurs nécessaires pour exécuter l'algorithme, ainsi que le coût total qui est le produit du temps d'exécution et du nombre de processeurs.

Quel est un exemple d'algorithme parallèle ?

Un exemple classique d'algorithme parallèle est le produit matriciel, où les opérations de multiplication et d'addition peuvent être effectuées simultanément sur différentes parties des matrices, réduisant ainsi le temps de calcul global.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions