“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 188 — #198
i
i
i
i
i
i
i
i
188
4
• La programmation concurrente dataflow
L’ordre causal des pas d’exécution
Pour un programme donné, tous les pas d’exécution forment un
ordre partiel qui s’appelle l’ordre causal. Un pas d’exécution arrive
avant un autre pas si dans toutes les exécutions possibles du programme il est avant l’autre. Il en va de même pour un pas d’exécution qui arrive après un autre. Parfois un pas n’est ni avant ni
après un autre pas. Dans ce cas, nous disons que les deux pas sont
concurrents.
Dans un programme séquentiel, tous les pas d’exécution sont dans un ordre total. Il
n’y a pas de pas concurrents. Dans un programme concurrent, tous les pas d’exécution
de chaque fil sont dans un ordre total. Les pas d’exécution de tout le programme sont
dans un ordre partiel. Deux pas dans cet ordre partiel auront un lien causal si (1) ils
sont dans le même fil, ou (2) le premier lie une variable dataflow et le deuxième a
besoin de la valeur de cette variable ou (3) il y a un pas intermédiaire qui a un lien de
causalité avec les deux (transitivité).
La figure 4.2 montre la différence entre les exécutions séquentielles et concurrentes.
La figure 4.3 donne un exemple qui montre quelques exécutions qui correspondent à
un même ordre causal. L’ordre causal a deux fils, T1 et T2, où T1 a deux opérations (I 1
et I 2 ) et T2 a trois opérations (I a , I b et I c ). Quatre exécutions possibles sont montrées.
Chaque exécution respecte l’ordre causal, c’est-à-dire que toutes les instructions en
ordre causal ont le même ordre dans l’exécution. Combien d’exécutions sont possibles
en tout ? Indice : Il n’y en a pas beaucoup dans cet exemple.
un pas de calcul
Fil T1
T3
T2
T4
T5
ordre dans un fil
ordre entre des fils
(ordre partiel)
(ordre total)
Exécution séquentielle
Exécution concurrente
Figure 4.2 Les ordres causaux des exécutions séquentielle et concurrente.
Le non-déterminisme
Une exécution est dite non-déterministe s’il existe un état d’exécution dans lequel
plusieurs fils peuvent s’exécuter. Il faut donc choisir quel fil fera le pas suivant. Ce
i
i
i
i
i
i
i
i
188
4
• La programmation concurrente dataflow
L’ordre causal des pas d’exécution
Pour un programme donné, tous les pas d’exécution forment un
ordre partiel qui s’appelle l’ordre causal. Un pas d’exécution arrive
avant un autre pas si dans toutes les exécutions possibles du programme il est avant l’autre. Il en va de même pour un pas d’exécution qui arrive après un autre. Parfois un pas n’est ni avant ni
après un autre pas. Dans ce cas, nous disons que les deux pas sont
concurrents.
Dans un programme séquentiel, tous les pas d’exécution sont dans un ordre total. Il
n’y a pas de pas concurrents. Dans un programme concurrent, tous les pas d’exécution
de chaque fil sont dans un ordre total. Les pas d’exécution de tout le programme sont
dans un ordre partiel. Deux pas dans cet ordre partiel auront un lien causal si (1) ils
sont dans le même fil, ou (2) le premier lie une variable dataflow et le deuxième a
besoin de la valeur de cette variable ou (3) il y a un pas intermédiaire qui a un lien de
causalité avec les deux (transitivité).
La figure 4.2 montre la différence entre les exécutions séquentielles et concurrentes.
La figure 4.3 donne un exemple qui montre quelques exécutions qui correspondent à
un même ordre causal. L’ordre causal a deux fils, T1 et T2, où T1 a deux opérations (I 1
et I 2 ) et T2 a trois opérations (I a , I b et I c ). Quatre exécutions possibles sont montrées.
Chaque exécution respecte l’ordre causal, c’est-à-dire que toutes les instructions en
ordre causal ont le même ordre dans l’exécution. Combien d’exécutions sont possibles
en tout ? Indice : Il n’y en a pas beaucoup dans cet exemple.
un pas de calcul
Fil T1
T3
T2
T4
T5
ordre dans un fil
ordre entre des fils
(ordre partiel)
(ordre total)
Exécution séquentielle
Exécution concurrente
Figure 4.2 Les ordres causaux des exécutions séquentielle et concurrente.
Le non-déterminisme
Une exécution est dite non-déterministe s’il existe un état d’exécution dans lequel
plusieurs fils peuvent s’exécuter. Il faut donc choisir quel fil fera le pas suivant. Ce