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
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.
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.
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
for
avec cette stratégie est impossible. 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