L'application N

Il est nécessaire pour exécuter les algorithmes d'utiliser une application $N$ de $\mathcal{O}$ dans $\mbox{I\hspace{-.15em}N}$. $N(o_{i}^{p})=(k-1)$ signifie que $o_{i}^{p}$ est la $k$-ème opération à être effectuée par $T_{i}$ sur $b(o_{i}^{p})$. Il est nécessaire pour rendre les parcours de graphes les plus efficaces possible de pouvoir utiliser ce que j'appelle dans mon code inversedN, c'est-à-dire la réciproque de $N$.

Comme $N$ n'est pas injective, on définit une application injective $N^{\prime}$ de $\mathcal{O}$ dans $\mbox{I\hspace{-.15em}N}\times \mathcal{B} \times \mathcal{T}$ telle que $N^{\prime}(o_{i}^{p})=((k-1), b_{k}, T_{i})$ signifie que $o_{i}^{p}$ est la $(k-1)$-ème opération à être effectuée par $T_{i}$ sur $b_{k}$. Sa réciproque est une application $(N^{\prime})^{-1}$ de $\mbox{I\hspace{-.15em}N}\times \mathcal{B} \times \mathcal{T}$ dans $\mathcal{O}$ telle que $(N^{\prime})^{-1}((k-1), b_{k}, T_{i}) = o_{i}^{p}$ signifie que $o_{i}^{p}$ est la $k$-ème opération à être effectuée par $T_{i}$ sur $b(o_{i}^{p})$, sachant que $b_{k}=b(o_{i}^{p})$.

Soit une tâche active $T_{i}$, et un buffer $b_{k} \in \mathcal{B}_{ji}$. Chaque opération de lecture $o_{i}^{p}$ vérifiant $b(o_{i}^{p}) = b_{k}$ est contrainte par une opération d'écriture $b(o_{j}^{q})$ telle que $N(o_{i}^{p}) = N(o_{j}^{q})$; $b(o_{j}^{q})$ devra s'exécuter avant $b(o_{i}^{p})$. L'expression graphique de ces contraintes forme l'ensemble $\mathcal{E}_{2}$ des arcs $(o_{j}^{q}, o_{i}^{p})$. Ce sont les contraintes de buffers vides. On peut retrouver $o_{j}^{q}$ à partir de $o_{i}^{p}$ avec l'égalité

$$(N^{\prime})^{-1}(N(o_{i}^{p}), b(o_{i}^{p}), T_{j}) = o_{j}^{q}$$

où $T_{j}$ est la tâche passive de $o_{i}^{p}$.

Soit une tâche active $T_{i}$, et un buffer $b_{k}\in \mathcal{B}_{ij}$. Pour toute opération d'écriture $o_{i}^{p}$, si $b(o_{i}^{p}) = b_{k}$ et $N(o_{i}^{p}) - \Delta(b_{k}) \geq 0$, alors il existe une opération de lecture $b(o_{j}^{q})$ sur la tâche passive $T_{j}$ telle que $N(o_{i}^{p}) = N(o_{j}^{q}) + \Delta(b_{k})$. L'expression graphique de ces contraintes forme l'ensemble $\mathcal{E}_{3}$ des contraintes de buffers pleins $(o_{i}^{p}, o_{j}^{q})$. On peut de même retrouver $b(o_{j}^{q})$ à l'aide de l'égalité

$$(N^{\prime})^{-1}((N(o_{i}^{p}) - \Delta(b_{k})), b(o_{i}^{p}), T_{j}) = o_{j}^{q}$$

où $T_{j}$ est la tâche passive de $o_{i}^{p}$.