Exemple

Considérons l'exemple suivant de la figure 3.9. Les buffers sont disposés conformément à la disposition présentée dans le graphe de Kahn[1] de la figure 3.10.

Figure 3.9: Exemple

Figure 3.10: Graphe de Kahn[1] de l'exemple

La figure 3.11 explicite le calcul de $C(b_{1}, b_{2})$, les contraintes de buffer vide de $b_{2}$ sont tracées et on incrémente progressivement la capacité de $b_{1}$ jusqu'à ce qu'il n'y ait plus de circuits. On obtient finalement :

$$C(b_{1}, b_{2}) = (\Delta(b_{1} \geq 4) \wedge (\Delta(b_{2} \geq 1)$$

Figure 3.11: Calcul de $C(b_{1}, b_{2})$

En faisant de même en permutant les rôles des deux buffers (figure 3.12), on obtient l'expression

$$C(b_{2}, b_{1}) = (\Delta(b_{2} \geq 1) \wedge (\Delta(b_{1} \geq 1)$$

Figure 3.12: Calcul de $C(b_{2}, b_{1})$

Nous allons procéder de façon analogue pour $C(b_{1}, b_{3})$, mais en fixant $\Delta(b_{3})$ à $1$. La figure 3.13 nous montre qu'il faut dans ce cas fixer $\Delta(b_{1})$ à une valeur supérieure ou égale à $4$.

Figure 3.13: Calcul de $C(b_{1}, b_{3})$ avec $\Delta (b_{3})=1$

Figure 3.14: Calcul de $C(b_{1}, b_{3})$ avec $\Delta (b_{3})=2$

Figure 3.15: Calcul de $C(b_{1}, b_{3})$ avec $\Delta (b_{3})=3$

Figure 3.16: Calcul de $C(b_{1}, b_{3})$ avec $\Delta (b_{3})=4$

Les figures 3.13, 3.14, 3.15 et 3.16 nous montrent que :

$$C(b_{1}, b_{3}) = ((\Delta(b_{1} \geq 4) \wedge (\Delta(b_{3}... ...q 1)) \vee ((\Delta(b_{1} \geq 4) \wedge (\Delta(b_{3} \geq 2))$$

$$\vee ((\Delta(b_{1} \geq 2) \wedge (\Delta(b_{3} \geq 3)) \vee ((\Delta(b_{1} \geq 1) \wedge (\Delta(b_{3} \geq 4))$$

Figure 3.17: Calcul de $C(b_{3}, b_{1})$ avec $\Delta (b_{1})=1$

Figure 3.18: Calcul de $C(b_{3}, b_{1})$ avec $\Delta (b_{1})=2$

Figure 3.19: Calcul de $C(b_{3}, b_{1})$ avec $\Delta (b_{1})=3$

On déduit des figures 3.17, 3.18 et 3.19 que :

$$C(b_{3}, b_{1}) = ((\Delta(b_{3} \geq 4) \wedge (\Delta(b_{1}... ...q 1)) \vee ((\Delta(b_{3} \geq 3) \wedge (\Delta(b_{1} \geq 2))$$

$$\vee ((\Delta(b_{3} \geq 1) \wedge (\Delta(b_{1} \geq 3))$$

Figure 3.20: Calcul de $C(b_{2}, b_{3})$ avec $\Delta (b_{1})=1$

Figure 3.21: Calcul de $C(b_{2}, b_{3})$ avec $\Delta (b_{3})=2$

Figure 3.22: Calcul de $C(b_{2}, b_{3})$ avec $\Delta (b_{3})=3$

De même les figures 3.20, 3.21 et 3.22 nous montrent que :

$$C(b_{2}, b_{3}) = ((\Delta(b_{2} \geq 2) \wedge (\Delta(b_{3}... ...q 1)) \vee ((\Delta(b_{2} \geq 2) \wedge (\Delta(b_{3} \geq 2))$$

$$\vee ((\Delta(b_{2} \geq 1) \wedge (\Delta(b_{3} \geq 3))$$

Figure 3.23: Calcul de $C(b_{3}, b_{2})$ avec $\Delta (b_{2})=1$

Figure 3.24: Calcul de $C(b_{3}, b_{2})$ avec $\Delta (b_{2})=2$

Et enfin :

$$C(b_{3}, b_{2}) = ((\Delta(b_{3} \geq 3) \wedge (\Delta(b_{2}... ...q 1)) \vee ((\Delta(b_{3} \geq 1) \wedge (\Delta(b_{2} \geq 2))$$

d'après les figures 3.23 et 3.24.

Les conditions nécessaires et suffisantes de non-blocage associées à cet exemple sont donc :

$\left\lbrace\begin{array}{l} C(b_{1}, b_{2}) = (\Delta(b_{1} \geq 4) \wedge (\D... ...)) \vee ((\Delta(b_{3} \geq 1) \wedge (\Delta(b_{2} \geq 2)) \end{array}\right.$