Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 12
Parallélisation des programmes
Année 2002-2003

Suite N°1...

12.3 UN EXEMPLE

On définit un traitement d'image différent du précédent. Cet exemple est simple tout en étant relativement complet. Il est classique et éprouvé et assez bien adapté aux fins de la deuxième partie du cours d'architectures parallèles pour le traitement du signal. On le trouve sous une forme très semblable dans [CUL97].

L'opération faite sur les valeurs portées par les points de la grille est définie selon le point d'application par :

• les points sur les frontières sont inchangés;
• la valeur de tout autre point est remplacée par la moyenne arithmétique de l'ancienne valeur et de la valeur courante des quatre voisins.

Le processus se termine quand la différence entre la valeur courante et celle de l'itération précédente est en tout point inférieure à un seuil.

À cette occasion, le lecteur prendra aisément conscience que nous sommes ici encore plus éloignés d'avoir une solution unique que dans le domaine séquentiel.

NOTE : Tous les programmes ci-après sont insérés sous forme d'images pour garder l'indentation de leurs lignes dans toutes les versions de notes de cours.

Remarque : Le traitement du tableau se fait ici par ce que l'on nomme une fenêtre glissante en traitement d'images. On examinera plus complètement les conséquences de ce choix dans le § 12.2.1. Toutefois, on peut dès maintenant observer que cette façon de procéder qui a l'avantage de la simplicité, mélange des valeurs de l'itération précédente à des valeurs de l'itération en cours pendant la prise de moyenne pour chaque point.

Une autre façon de résoudre le problème est de construire deux tableaux. L'un d'eux contient les valeurs acquises soit au chargement initial, soit au cours de la dernière itération terminée, l'autre contient les valeurs en cours de calcul. La consommation de mémoire est bien sur doublée. Les exercices à venir seront tous basés sur cette construction. On la nommera 'itération séparée'.

Exercice 1 : Écrire, toujours en pseudocode le programme séquentiel correspondant à l'itération séparée.

12.3.1 La décomposition

Le plus simple est de commencer par la structure de boucle, comme on le fait habituellement pour les programmes ainsi structurés. On examine chaque boucle pour voir s'il y a possibilité de parallélisation.

Examinons la boucle qui commence à la ligne 15. Elle opère sur la totalité (hors frontières) du tableau. Il n'y a manifestement pas indépendance puisqu'une nouvelle itération reprend les valeurs de la précédente.

Examinons la boucle qui commence ligne 17, sans les lignes où diff intervient et plus précisément la boucle pour commençant à la ligne 18. Chacune de ses itérations lit la valeur (i,j-1) écrite par la précédente. Il s'agit d'une boucle séquentielle. Cette analyse sommaire montre que ces boucles ne portent pas de possibilités de parallélisme.

On ne peut que revenir à l'algorithme de principe, sans tenir compte de son expression séquentielle. Dès lors que le calcul progresse de gauche à droite et de haut en bas, il y a dépendance dans le calcul d'une image vis-à-vis de points à gauche et au dessus comme montré ci-dessous :

On y observe que les éléments d'une antidiagonale n'ont pas de dépendance entre eux et donc peuvent être calculés en parallèle, alors même qu'ils dépendent de l'antidiagonale précédente.

Supposons que nous décidions de décomposer le travail en tableaux de points individuels, tels que la mise à jour d'un seul tableau soit une tâche. On va pouvoir exploiter une telle simultanéité de plusieurs façons.

• Nous pouvons en premier lieu laisser telle quelle la structure de boucle du programme et insérer des synchronisations point à point de telle sorte que l'on soit sur que le tableau sera fourni avant d'être utilisé par les suivants. Ainsi différentes boucles pourront être en cours de calcul simultanément pour autant que les relations de dépendance ne sont pas violées.
• En second lieu nous pouvons changer la structure de boucle, ayant pour première boucle celle de la ligne 17 sur les antidiagonales, et une boucle intérieure sur les éléments de l'antidiagonale. La boucle intérieure peut alors être exécutée complètement en simultanéité, moyennant une synchronisation globale entre les itérations de la boucle externe. La communication sera faite de façon très différente dans ces deux cas et en particulier si c'est une communication explicite.

Exercice 2 : Reprendre les raisonnements précédents en partant des résultats de l'exercice 1 à itérations séparées.

• Une autre solution (hors exercices précédents), est d'utiliser la connaissance que l'on a du problème lui-même, sans plus se préoccuper de la façon dont la solution séquentielle a été construite. La méthode de lissage que nous examinons est au départ isotrope. Le choix fait dans les boucles du programme séquentiel est une simple commodité. L'image n'a pas à être parcourue plus de gauche à droite que de droite à gauche et plus de haut en bas que de bas en haut. Il est donc possible de parcourir l'image dans le sens que nous voulons pourvu que tous les points soient traités. La seule différence sera que si l'on utilise exclusivement les valeurs de l'itération précédente, le lissage sera plus lent... peut-être.

Le calcul va donc être décomposé en deux phases :

• le calcul de tous les points d'un type, blancs par exemple;
• le calcul de tous les points de l'autre type, donc noirs.

Exercice 3 : Écrire le programme séquentiel et un programme parallèle utilisant la méthode des points noirs et blancs.

• Enfin, on peut le plus simplement ne tenir aucun compte des dépendances entre points selon les itérations et écrire un programme parallèle pour un nombre quelconque de processus, tous exécutant la même tâche :

La boucle pour_tous..faire analogue à la boucle pour..faire s'applique simultanément à tous les processus. Une seule synchronisation implicite existe en fin de boucle tant_que.

Exercice 4 : Analyser les variantes en itération séparée et écrire un programme leur correspondant.

12.3.2 L'affectation

L'option la plus simple est celle de l'affectation statique où chaque processeur a la charge d'un bloc de lignes parallèles.

La ligne i est affectée au processeur dont le numéro est partie entière de i/p. Une autre affectation statique est l'affectation cyclique où l'on entrelace les lignes : le processeur i reçoit les lignes i, i+p, i+2p etc.

On peut aussi envisager une affectation dynamique où chaque processeur prend en charge une ligne supplémentaire non encore traitée dès qu'il est disponible. Pour notre part nous continuerons à mettre en œuvre le modèle statique de blocs. Deux observations sont possibles dès maintenant :

• l'affectation statique a réduit le degré de parallélisme de n à p;
• en corollaire, la communication nécessaire pour affecter des lignes consécutives au même processeur est diminuée par l'affectation de blocs.