Algorithme du calcul

Notre application a pour but de réaliser l'algorithme suivant:

$$B = 2[(P_x-V_x)D_x+(P_y-V_y)D_y+(P_z-V_z)D_z]$$

$$C = (P_x-V_x)^2+(P_y-V_y)^2+(P_z-V_z)^2-r^2$$

$$\Delta = B^2-4C$$

$$L_1 = -\frac{1}{2}(B+\sqrt{\Delta^2})$$

$$L_2 = -\frac{1}{2}(B-\sqrt{\Delta^2})$$

$$\lambda = min(L_1,L_2)$$

$$X_x,X_y,X_z = Px+\lambda.D_x,Py+\lambda.D_y,Pz+\lambda.D_z$$

$$N_x,N_y,N_z = \frac{(X_x-V_x)}{r},\frac{(X_y-V_y)}{r},\frac{(X_z-V_z)}{r},$$

La valeur résultat à transmettre à l'extérieur est $\lambda$. Elle doit donc être disponible dans les registres de l'interface à la fin du calcul. C'est dans ces conditions que nous avons réfléchi pour mettre en adéquation le temps d'exécution et les coûts³ afin de respecter le cahier des charges.

Nous avons donc dressé un premier bilan des opérateurs nécessaires:

• 1 additionneur (2 entrées - 1 sortie)
• 1 soustracteur (2 entrées - 1 sortie)
• 1 opérateur minimum (2 entrées - 1 sortie)
• 1 multiplieur (2 entrées - 1 sortie)
• 1 opérateur racine carrée (1 entrée - 1 sortie)

Dans un souci de clareté, et afin d'éviter une multiplication intempestives de modules, nous avons regroupé l'additionneur, le soustracteur et l'opérateur minimum en un seul module: l'Unité Arithmétique et Logique ou UAL. Au cours du déroulement du programme nous nous sommes rendus compte, pour des raisons d'implantations qu'un soustracteur inversé⁴ s'avérait nécessaire. De plus, pour simplifier, nous avons décidé que, comme au début du calcul $P_x$ et $P_y$ sont toujours à zéro, nous allions intégrer l'opération $0-x$⁵. Ces deux dernières opérations ont donc aussi été incluses dans l'UAL.

Mais cette implantation exige aussi que l'on n'exécute qu'une opération de l'UAL à la fois, qu'une multiplication et qu'un seul traitement par racine carrée. Cela fait apparaître la nécessité de stocker temporairement des données dans des registres⁶.

L'étude du graphe-flot fournis dans le sujet, nous permet de dire que les variables temporaires suivantes devront être stockées:

$$\begin{array}{lll} X=P_x-V_x & B=Q_3+Q_4 & C_1=B^2 \\ Y=P_... ... Q_4=Q_1+Q_2 & C=S_3+S_4 & \lambda=min(L_1,L_2)\\ \end{array}$$