TD2

Exercice 1

On souhaite paralléliser l'algorithme suivant 

y := 2∗((a+b)/(c−d)+e∗f)+(a+b)∗(c−d)

Les instructions s'exécutant en parallèle pourront être mises dans un bloc commençant par parbegin et finissant par parend. Par exemple le code suivant indique que A et B s'exécutent en parallèle. 

parbegin
A
B
parend
  1. Construire un algorithme équivalent de parallélisme maximal.
  2. Dessiner un graph représentant l'exécution de cet algorithme dans lequel les noeuds seront les taches et les arrêtes indiqueront une dépendance

Exercice 2(Condition de Bernstein)

La notion de graph de dépendance permet de décrire les types de dépendance entres données et d'extraire le meilleur parallélisme possible d'un programme. Il existe une condition suffisante d’indépendance entre différentes instructions ou parties de code. Cette condition est connue sous le nom de condition de Bernstein et s’appuie sur les notions de variables lues et de variables modifiées. Soit S une séquence d’instructions. On définit L(S) comme l’ensemble des variables utilisées en lecture dans le code S, et M(S) l’ensemble des variables qui subissent une affectation dans le code S.

  1. Calculez L(S) et M(S) pour le code a[i] = 2*b[i] + c

La condition de Bernstein s’ énonce ainsi. Deux instructions S1 et S2 (ou plus généralement, 2 séquences de code symbolisées par 2 taches) peuvent être exécutées dans un ordre quelconque, ou en parallèle (cad qu’elles n’interfèrent pas), sans modifier

le résultat obtenu dès lors que l’on a les trois conditions suivantes.

  1. Explicitez en français ces conditions et indiquez pourquoi les taches ne peuvent s'exécuter en parallèle quand elles ne sont pas respectées

Exercice 3 (Parallélisation d'un algorithme)

On considère l'algorithme suivant : 

a[0] = 0
sp[0] = a[0]
for i=1 to n−1 do
   a[i]  = 2 ∗ i
   sp[i] = a[i] + sp[i − 1] 
end for
  1. Que calcule cet algorithme ?
  2. On veut faire du parallélisme de données. En vous servant de la condition de Bernstein, montrez que la parallélisation de la boucle for avec cette stratégie est impossible.
  3. Modifiez l'algorithme pour permettre une parallélisation.

Exercice 4 (Parallélisation d'un algorithme, 2)

Refaire l'exercice précédent sur l'algorithme suivant 

for i = 1 to n do 
  a[i]=2∗i 
  sp[i] = a[i]
end for
for i=1 to n−1 do
  sp[i]=a[i]+sp[i+1] 
end for