Aller au contenu

Méthodologie de Parallélisation

Méthodologie de parallélisation La méthodologie de parallélisation est essentielle pour optimiser l'exécution des programmes en décomposant les tâches en unités plus petites et indépendantes. Cet article explore les concepts fondamentaux de cette méthodologie, y compris la notion de système de tâches, le graphe de précédence et l'ordonnancement des tâches.

D'après le document Méthodologie de Parallélisation

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

Document source

Méthodologie de Parallélisation

Computer Science - Task Scheduling and Parallel Computing · PDF · 107 pages

Afficher l'aperçu du document

Consulter le document original →

Méthodologie de parallélisation

La méthodologie de parallélisation est essentielle pour optimiser l'exécution des programmes en décomposant les tâches en unités plus petites et indépendantes. Cet article explore les concepts fondamentaux de cette méthodologie, y compris la notion de système de tâches, le graphe de précédence et l'ordonnancement des tâches. Chaque section fournit des définitions claires et des exemples pratiques pour aider les étudiants à comprendre ces concepts.

Notion de système de tâches

Un système de tâches est défini comme un ensemble de tâches, noté S = (T1,…,Tn, <<), où << représente une relation d'ordre partiel. Cela signifie que pour deux tâches Ti et Tj, l'exécution de Tj ne peut commencer que si Ti a terminé son exécution. La décomposition d'un programme en tâches n'est pas unique et dépend de la granularité demandée, c'est-à-dire de la taille des tâches à paralléliser.

Définition de la tâche

Une tâche est une unité indivisible, définie par les propriétés suivantes :

  • Ei : les entrées de la tâche Ti
  • Si : les sorties de la tâche Ti
  • Fi : opérateur sur Ti
  • Θi : coût de Ti (nombre d’opérations élémentaires)

La tâche est représentée par (Ei, Si, Fi, Θi). Il est important de noter que la tâche ne peut s’exécuter que sur un seul processeur et que son exécution est non préemptive.

Relation de Bernstein

Deux tâches Ti et Tj sont considérées comme indépendantes si les ensembles d'entrées et de sorties ne se chevauchent pas, ce qui est exprimé par la relation de Bernstein :

Si ∩ Sj = Si ∩ Ej = Ei ∩ Sj = Ø

C'est une condition nécessaire mais non suffisante pour que les deux tâches puissent s’exécuter en parallèle.

Graphe de précédence

Le graphe de précédence (GP) est un outil visuel utilisé pour représenter les relations d'ordre entre les tâches. Pour construire le GP, il est nécessaire d'éliminer les redondances du graphe de tâches (GT).

Construction du graphe de précédence

Pour chaque programme, on associe un graphe de tâches qui est un graphe orienté mais non cyclique. Par exemple, si T1 << T4, T2 << T4, T2 << T5, et T3 << T5, alors le GP peut être représenté comme suit :

T1
|
T4
|
T2
| \
T5  T3

Il est crucial de supprimer les arcs transitifs pour obtenir le GP, ce qui permet de simplifier les relations entre les tâches.

Matrice d’adjacence

La matrice d’adjacence est un moyen de représenter le GP. Pour un système de tâches S = (T1,…,Tn, <<), la matrice d’adjacence d’ordre n est définie par :

aij = 1 si et seulement si Ti << Tj

Cette matrice est souvent creuse, ce qui signifie qu'elle contient de nombreux zéros.

Ordonnancement des tâches

L'ordonnancement est le processus de planification des tâches sur les processeurs. Il est défini par :

ORD : (tdb(Ti), Proc(Ti))

où tdb(Ti) est le temps de début d’exécution de Ti et Proc(Ti) est le processeur qui va exécuter Ti. L'objectif est de minimiser le temps d'exécution total, noté Tp, qui est donné par :

Tp = maxi[tdb(Ti) + θi]

Temps au plus tôt et au plus tard

Pour chaque tâche, il est important de déterminer le temps au plus tôt (tet) et le temps au plus tard (teT). Par exemple, dans un cas où il n'y a pas de dépendances, les temps peuvent être calculés comme suit :

  • T1 : θ1 = 3, tet1 = 0, teT1 = 3
  • T2 : θ2 = 4, tet2 = 0, teT2 = 2
  • T3 : θ3 = 6, tet3 = 0, teT3 = 0

Dans le cas général, lorsque des dépendances existent entre les tâches, il est nécessaire de déterminer Topt et de calculer tet et teT pour chaque tâche afin de définir l'ordonnancement optimal.

Points clés à retenir

Voici les principaux concepts abordés dans cet article :

  • La décomposition d'un programme en tâches dépend de la granularité.
  • Un système de tâches est défini par une relation d'ordre partiel.
  • Le graphe de précédence permet de visualiser les dépendances entre les tâches.
  • La matrice d’adjacence représente les relations d'ordre entre les tâches.
  • L'ordonnancement des tâches vise à minimiser le temps d'exécution total.

Questions fréquentes

Qu'est-ce qu'un système de tâches ?

Un système de tâches est un ensemble de tâches organisé selon une relation d'ordre partiel, où certaines tâches doivent être exécutées avant d'autres.

Comment construire un graphe de précédence ?

Pour construire un graphe de précédence, il faut d'abord établir les relations d'ordre entre les tâches, puis éliminer les redondances pour obtenir un graphe orienté sans cycles.

Qu'est-ce que l'ordonnancement des tâches ?

L'ordonnancement des tâches est le processus de planification des tâches sur des processeurs, avec l'objectif de minimiser le temps d'exécution total.

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