9.4 Résultats.

Nous allons donc maintenant chercher à illustrer les performances que nous obtenons pour les deux procédures décrites précédemment (Par.10.3).

9.4.1 Reconstruction par rétroprojection filtrée.

9.4.1.1 rétroprojection.

Nous donnons Fig.10.13,une représentation de la loi de Amdahl pour la procédure en question. Ces courbes sont obtenues par utilisation de l'outil ATEXPERT de CRAY [23]. La procédure apparaît au niveau de l'exécution comme étant 100% parallèle, par conséquent en l'absence d'overhead, on devrait s'attendre sur 16 processeurs à aller 16 fois plus vite. C'est ce qu'illustre la courbe en pointillé (Loi de Amdahl idéale) sur la Fig.10.13. En revanche, la deuxième courbe (trait plein) montre le facteur d'accélération tel qu'il est décrit Par.10.2.5. Autrement dit, c'est le le temps d'exécution sur $1$ processeur rapporté au temps sur $N$ processeurs. L'écart entre la courbe idéale et cette courbe attendue provient principalement de l'overhead.

Figure: Loi de Amdahl idéale (pointillé) et attendue (trait plein) pour la rétroprojection.

Comme cet overhead provient de différents facteurs, on donne Fig.10.14, la répartition de l'overhead pour 2 nombres de processeurs différents. Sur ces figures, on donne les temps d'overhead en nombre de période d'horloge et le pourcentage de chaque type d'overhead . La signification des overhead les plus importants est la suivante:

• bp représente le temps que le maître prend pour initialiser l'exécution parallèle lorsqu'on entre dans une région parallèle.
• sa représente le temps pour que le premier processus esclave réponde à l'appel lancé par le processus maître.
• cv représente le temps pour que tous les processeurs disponibles se mettent à résoudre le problème (temps décompté depuis sa).
• it représente le temps supplémentaire pour l'exécution des itérations lorsque celles ci sont faites de manière simultanée. Dans cet overhead sont inclus de manière cachée les différents conflits mémoires.
• li (Load Imbalance) correspond au temps de travail qui ne peut pas être distribué sur tous les processeurs. D'une manière générale, cet overhead existe dès que le nombre d'itérations n'est pas un multiple du nombre de processeurs.

  Figure: Overhead pour la rétroprojection lorsque 14 ou 15 processeurs sont utilisés.

  [$N=14$]

  

  [$N=15$]

  

Ainsi, plus l'écart entre la courbe idéale et la courbe attendue est grand, plus l'overhead est important. Cet écart peut traduire deux choses, soit une répartition de charge qui n'est pas optimale, soit une granularité du problème trop faible. Il faut savoir que, mis à part l'overhead lié à la répartition du travail, les autres valeurs d'overhead sont plus ou moins fixées, et on ne peut pas faire grand chose si ce n'est essayer d'augmenter la granularité du problème. La granularité étant fixée par notre souci de paralléliser la boucle la plus externe de la rétroprojection, il s'agit de comparer la valeur du Load Imbalance par rapport aux autres sources d'overhead, et notamment au temps nécessaire à la mise en place de la parallélisation (bp+cv+sa). Dans notre cas, lorsque nous utilisons 14 processeurs nous voyons que la charge à plus de mal à se répartir (li représente 31% de l'overhead) que sur 15 processeurs (li représente 5.3%). Notons toutefois que c'est principalement une boucle comprenant $N_{x}$ itérations qui est parallélisée. C'est pourquoi, la répartition du taux de charge et donc la valeur de li est fortement liée à la dimension de notre image. Quoiqu'il en soit, dans le pire des cas, nous voyons que l'overhead représente 1.3% du temps nécessaire à l'exécution de la boucle sur 1 seul processeur. Ceci correspond à une très bonne parallélisation de notre code.

Afin de donner une idée des performances vectorielles de notre algorithme de rétroprojection, nous nous sommes intéressés au nombre d'opérations sur des flottants par seconde, exprimé en millions (Mflops). Nous avons accès à ces données par l'utilisation de l'outil JUMPTRACE et JUMPVIEW de CRAY [23]. Nous constatons alors que notre algorithme exécute 47.2 Mflops. Ce chiffre correspond à une performance médiocre quand on compare au 200 Mflops que l'on peut obtenir en crête. Pour modérer notre propos, il ne faut pas oublier que ce chiffre représente une valeur moyenne sur l'ensemble de la procédure de rétroprojection.

D'autre part, les accès mémoires étant pénalisant dans des procédures vectorisées, nous avons tout intérêt dans les parties vectorielles à faire un minimum de référence mémoire pour un maximum d'opérations vectorielles. C'est pourquoi, nous donnons également la valeur de l'intensité calculatoire (IC), qui représente le ratio du nombre d'opérations au nombre de références mémoire. On cherche un ratio supérieur à 1, puisque cela correspond à exécuter plus d'opérations que de références mémoire. Pour notre algorithme de rétroprojection, cette intensité IC vaut 1.69. Cette valeur correspond à un algorithme efficace.

Dans notre procédure de rétroprojection, on pourrait songer à améliorer le nombre d'opérations effectuées par seconde, toutefois il vaut mieux auparavant, regarder le poids de la rétroprojection sur l'intégralité de la reconstruction.

9.4.1.2 reconstruction complète.

A ce niveau, nous envisageons uniquement la rétroprojection filtrée. On suppose que les vues manquantes ont déjà été estimées et intégrées au sinogramme que nous reconstruisons. Nous donnons Fig.10.15 la représentation de la loi de Amdahl idéale et attendue de notre reconstruction.

Figure: Loi de Amdahl idéale (pointillé) et attendue (trait plein) pour la reconstruction.

Sur cette figure, la diagonale représente le gain de temps que nous pourrions observer pour notre reconstruction en l'absence de partie séquentielle et d'overhead. La courbe en pointillé correspond à la loi de Amdahl idéale. Elle nous renseigne sur l'influence des parties de code s'exécutant de manière séquentielle. La différence entre la courbe en trait pointillé et celle en trait plein, comme précédemment, nous renseigne sur l'influence de l'overhead. Nous voyons qu'il existe une partie de notre reconstruction, exécutée de manière séquentielle, qui freine considérablement notre parallélisation. Cette partie correspond principalement au chargement de notre sinogramme depuis le disque dur. On ne peut pas agir sur cette partie, la lecture sur disque étant principalement une opération séquentielle. Autrement dit, après la parallélisation de la rétroprojection et le gain de temps qui en découle, la reconstruction est principalement freinée par la lecture du sinogramme. La rétroprojection n'est plus la partie pénalisante de notre reconstruction. Cela explique également pourquoi nous n'avons pas cherché à mieux optimiser le nombre d'opérations effectuées par seconde lors de la rétroprojection. L'effort que cela représente n'aurait pas conduit à des résultats significativement plus efficaces. En effet, grâce à la seule parallélisation, le temps pour une rétroprojection filtrée n'est plus prohibitif.

9.4.2 Performance de la reconstruction algébrique.

9.4.2.1 Produit matriciel $\mathbf{H}^{t}\mathbf{Hf}$.

De même que précédemment, nous donnons les lois de Amdahl idéale et attendue (Fig.10.16) pour la procédure de calcul matriciel tel que nous l'avons décrite (Par.10.3.2.5).

Figure: Loi de Amdahl idéale (pointillé) et attendue (trait plein) pour le calcul de $\mathbf{H}^{t}\mathbf{H}$.

Le taux de parallélisme obtenu est excellent, puisque les deux courbes sont proches l'une de l'autre. Peu d'overhead vient freiner le facteur d'accélération. Sur 16 processeurs, nous pouvons nous attendre à ce que le produit matriciel soit effectué 14.6 fois plus rapidement.

9.4.2.2 reconstruction complète.

Si nous avons choisi de présenter cette procédure, c'est parce qu'elle correspond à plus de 90% du temps lors d'une reconstruction algébrique de type gradient conjugué. Cela se traduit de manière indirecte par une loi de Amdahl sur l'ensemble de la reconstruction (Fig.10.17) fort similaire à celle obtenue pour la simple procédure de calcul matriciel. La part s'effectuant de manière séquentielle dans le programme reste limitée. Le poids de l'overhead conduit donc à une courbe attendue proche dans la forme à celle illustrée Fig.10.16. La parallélisation nous permet pour l'algorithme de reconstruction algébrique un facteur d'accélération supérieur à 13 (le programme va 13 fois plus vite !)

Figure: Loi de Amdahl idéale (pointillé) et attendue (trait plein) pour la reconstruction algébrique par gradient conjugué.

. Il reste à voir si les performances vectorielles suivent ! La procédure de calcul de produit matriciel telle que nous l'avons décrite Par.10.3.2.5 s'effectue à 60 Mflops. D'autre part, la valeur de IC est de 0.66. Nous avons plus de références mémoires que de calculs dans la partie vectorielle de notre procédure. 60 Mflops, c'est mieux que dans le cas de la rétroprojection, mais nous sommes toujours loin de la valeur crête. Dans ce cas précis, on ne peut accepter cette valeur, car même une fois ce calcul parallélisé, il représente toujours la partie prédominante de la reconstruction et le temps de reconstruction reste long. Dans l'algorithme de base (Alg.11), c'est la boucle sur $k$, boucle la plus interne qui va être vectorisée. Pour améliorer ses performances, nous proposons deux astuces:

• Afin de diminuer les conflits mémoires, nous allons retourner notre volume $\mathbf{f}$ et le résultat $\mathbf{H}^{t}\mathbf{Hf}$ afin de mieux présenter les données. Dans ce cas, les $N_{z}$ éléments $k$ que nous devons sommer se trouvent principalement dans des bancs mémoires différents.
• Nous allons dérouler la boucle sur les $k$ à la main de sorte que nous augmentions le nombres d'opérations effectuées au sein de la boucle vectorielle par rapport aux accès mémoire.

Ceci nous conduit à l'algorithme Alg.12

. Pour cet algorithme nous obtenons alors une performance moyenne de 137.8 MFlops. Nous avons donc plus que doublé le nombre d'opérations par seconde et minimisé le nombre de références mémoires par rapport aux opérations de calcul, puisque IC vaut maintenant 1.32. Nous avons donc ici, du fait de la vectorisation accéléré notre produit matriciel par un facteur bien supérieur à 2.

9.4.3 Temps des différents algorithmes.

Afin de conclure sur la partie optimisation, nous allons donner pour les principaux programmes utilisés, les temps observés dans une configuration standard. Nous utilisons les sinogrammes provenant de la caméra ECAT HR+ dont les dimensions sont $[N_{r},N_{s},N_{\theta },N_{\phi }]=[288,63,144,5]$ avant rebinning. Le sinogramme rebinné ne comporte plus qu'un seul segment de dimensions $[N_{r},N_{s},N_{\theta }]=[288,63,144]$. Les volumes reconstruits ou utilisés pour la projection sont ceux habituellement reconstruits par la caméra, dont les dimensions sont $[N_{x},N_{y},N_{z}]=[128,128,63]$ pour un voxel faisant $2.025\times 2.025\times 2.425\, cm^{3}$. Nous résumons Tab.10.1 les performances des principaux algorithmes que nous avons implémentés sur le CRAY. Les temps mentionnés correspondent à chaque programme dans son intégralité (lecture/écriture des volumes de données incluse). La lecture du sinogramme présentant les dimensions précédemment énoncées prend 50 secondes. Nous avons déjà vu l'effet que cela pouvait avoir lorsque sur la loi de Amdahl pour la reconstruction par rétroprojection filtrée. Pour l'algorithme de rebinning FOSA qui comprend la lecture complète du sinogramme et la réécriture d'un unique segment, nous avons déjà $\approx 60s$ pour la lecture/écriture des données. Cela signifie que le coeur de l'algorithme ne requiert que $10s$. Nous donnons également les places mémoires que requièrent tous nos algorithmes exprimées en millions de mots machine (rappelons que le mot machine sur CRAY correspond à 8 octets). Nous pouvons voir que grâce aux hypothèses envisagées, la taille mémoire inhérente à une reconstruction algébrique est inférieure à celle d'une reconstruction standard par rétroprojection filtrée 3D. Il me semble important de le préciser!

Table: Résultats des différents algorithmes.

Algorithme	Temps total. (s)	Temps CPU Total (s)	MIPS	Mflops	Max. Mémoire utilisée (Mw)
Projection 1	1506	21535	26.81	10.8	20.7
Projection 2 (Bres)	462	4842	7.07	2.27	19.1
Vues Manquantes	275	2252	27.3	10.4	32.5
FORE	96	166	23.3	25.3	62
FOSA	74	166	45.78	15.2	25.5
FBP3D	183	445	16.6	55	25.9
FBP2D	20	89	18.0	49.5	9.1
GCSQ	1331 (43 itérations)	17252	18.1	102	22.2

Dans l'ensemble, les procédures sont bien parallélisées, car pour les procédures impliquant des projections, nous avons un facteur d'accélération proche de 10. En revanche, nous pourrions nettement améliorer les performances vectorielles de ces algorithmes (Notamment la projection de type Bresenham effectuant seulement 2.27 MFlops).