GRAPHE DE FLOT DE DONNÉES MULTIDIMENSIONNEL ET TECHNIQUES DE PARALLÉLISME

Formalisme graphique des nids de boucles 

Graphe flot de données multidimensionnel

Un GFDM est une extension du graphe flot de données acyclique. Son formalisme est adéquat à la représentation des algorithmes contenant des structures répétitives et récursives imbriquées. Ce graphe est modélisé sous la forme de 0  +, 1, ), 2 tels que + est l’ensemble des nœuds, 1 est l’ensemble des arcs, )3 est le délai multidimensionnel de l’arc 3 tel que 3 4 1, et 25  est le temps d’exécution du nœud 5 , tel que 5 4 + [31, 32, 109]. Pour un algorithme donné, chaque instruction est modélisée par un nœud et chaque dépendance de donnée est modélisée par un arc. Chaque GDFM est caractérisé par une dimension  qui correspond au nombre de boucles imbriquées. Les dépendances de données sont schématisées par des délais qui représentent des vecteurs d’étiquetage des arcs. Pour un GFDM de  dimensions, un arc 3:  @ 5 est étiqueté par un délai sous la forme d’un vecteur de  entiers tel que ).Chaque paramètre 6 indique l’ordre d’exécution du nœud d’arrivée par rapport au nœud de départ. La valeur de ce paramètre représente la différence entre le numéro de l’itération exécutant 5 et le numéro de l’itération exécutant  par rapport à la boucle d’indice . Prenons l’exemple du filtre numérique d’ondelettes dont l’algorithme illustré dans la figure 3.1(b) est composé par deux boucles imbriquées. Sa représentation graphique correspond à un graphe flot de données bidimensionnel tel que schématisé dans la figure 3.1(a). Chaque arc est étiqueté par un délai sous la forme d’un vecteur de deux indices )3  ). 9, ). :, dont « ). 9 » et « ). : » correspondent respectivement à la différence des itérations par rapport à la boucle externe et à la boucle interne. Un arc 3:  @ 5 tel que )3  0,0, appelé délai nul, correspond à l’exécution des nœuds  et 5 dans la même itération de la boucle externe que la boucle interne, tel que les arcs 3>: % @ T, 3 : T @  et 3 : T @ B du GFDM de la figure 3.1(a). Pour un arc 3 :  @ 5, un délai )3  0, 9 indique que les nœuds  et 5 sont exécutés dans une même itération par rapport à la boucle externe. Pour la boucle interne, si le nœud  est exécuté dans l’itération , le nœud 5 est exécuté dans l’itération  . 9. Par exemple, le délai )34  1, 1 allant du nœud  à % signifie que le nœud  est exécuté une itération avant le nœud %, par rapport à la boucle externe, et que le nœud  est exécuté une itération après le nœud %, par rapport à la boucle interne. Figure 3.1 Filtre numérique d’ondelettes : (a) le GFDM, (b) l’algorithme Un chemin de données  est défini comme étant une succession de nœuds liés par des dépendances de données, noté par : 5 ]h ij 5k ]hlm innj … ]o @ 5 ou 5 p q 5 . Les extrémités d’un chemin doivent être impérativement des nœuds de calcul, ce qui implique que le nombre des nœuds excède le nombre des dépendances de données par une seule unité. Le temps d’exécution 2 d’un chemin : 5 ]h ij … ]o @ 5 est la somme des temps d’exécution des nœuds de ce chemin, tel que 2  ∑ 25   . De même, le vecteur de délais ) d’un chemin  est la somme des vecteur des délais des arcs appartenant au chemin tel que Deux nœuds interconnectés par un arc de délais nuls sont exécutés dans la même itération, et ainsi exécutés dans la même période de cycle. La période d’un cycle B0 d’un graphe GFDM est égale à la valeur maximale des temps d’exécution des chemins  ayant )  0, … ,0, tel que indiquée dans l’équation 3.1 [7]. B0  st9u2, )  0, … ,0v (3.1) Dans le cas du GFDM de la figure 3.1(a), la période de cycle est calculée en se référant au chemin : % ]w @ T ]m @  ou : % ]w @ T ]x @ B, dont les arcs 3 , 3 et 3y ont des délais nuls. Dans le cas où les temps d’exécution des nœuds sont 2T  2  2B  2%  1, la valeur de la période de cycle est B0  3, tel que illustré dans l’ordonnancement statique de la figure 3.2.

Les graphes d’ordonnancement des GFDMs

L’ordonnancement d’un algorithme dépend principalement des dépendances de données inter-itérations et intra-itérations. De ce fait, l’espace des itérations permet de représenter graphiquement les différentes itérations du nid de boucles ainsi que toutes les occurrences des instructions et les dépendances de données. Nous illustrons dans la figure 3.3(a) l’espace d’itérations du GFDM de la figure 3.1(a). C’est une représentation cartésienne sous la forme d’une grille à deux axes, dont l’axe vertical correspond à la boucle interne et l’axe horizontal à la boucle externe. Chaque partition de la grille représente une itération englobant tous les nœuds qui sont exécutés dans la même itération de l’algorithme. Chaque itération est étiquetée par un vecteur indiquant les numéros d’itérations par rapport aux boucles. On note que l’itération (0,0) est la première à être exécutée. Dans l’exemple rapporté par la figure 3.3, on se limite à schématiser 3  3 itérations. L’espace d’itérations total peut être directement déduit de la séquence illustrée dans la figure 3.3(a). Les dépendances intra-itérations sont représentées avec des arcs discontinus, et les dépendances inter-itérations par des arcs continus. Les instances des arcs 3> et 3A du GFDM sont représentées respectivement par des arcs des extrémités vides et des arcs des extrémités remplies. Le sens des dépendances B @ % indique l’incrémentation des indices de l’itération par rapport à la boucle externe et la boucle interne. Figure 3.2 Ordonnancement des itérations du filtre numérique d’ondelettes Figure 3.3 Filtre numérique d’ondelettes : (a) espace d’itérations, (b) graphe de dépendance de cellules Le Graphe de Dépendance de Cellules (GDC) est une représentation déduite de l’espace des itérations, permettant de schématiser uniquement les dépendances de données interitérations du GFDM dont les délais sont non-nuls. pour le cas du filtre numérique d’ondelettes, le GDC n’assure la représentation que des arcs 3> et 3A, tel que affiché dans la figure 3.3(b).  De ce fait, il est formé par un ensemble de cellules représentant chacune une itération, et des arcs représentant les dépendances des données entre les itérations. Un modèle mathématique pour le graphe de dépendance des données peut être présenté sous la forme d’un n-uplets, % avec  est l’ensemble des indices des cellules, et D est une matrice contenant tous les vecteurs des délais inter-itérations. Pour le nid de boucles schématisé dans la figure 3.3 avec m=30 et n=30, le graphe de dépendances de cellule est décrit par le couple  , % dont les structures sont décrites respectivement dans l’ensemble (3.2) et la matrice (3.3).   u, =: 0    30, 0  =  30v (3.2) %  { 1 1 1 1| (3.3)

Vecteur d’ordonnancement

Le graphe de dépendances de données est utilisé pour déterminer un ordre d’exécution des itérations, permettant un déroulement adéquat du nid de boucles et ainsi vérifiant une exécution cohérente de l’application. Cet ordre d’exécution doit garantir qu’une itération n’est exécutée que si les données en provenance des autres itérations (acheminer par des arcs de délais non nuls) ont été bien exécutées. Si cet ordre d’exécution existe alors le GFDM 0  +, 1, ), 2 est qualifié réalisable. Un formalise mathématique a été proposé par [2] permettant de vérifier cette caractéristique. Il consiste à prouver l’existence d’un vecteur d’ordonnancement } du graphe de dépendance de cellules tel que )  } F 0 pout tout ) 4 0. Un vecteur d’ordonnancement } représente un vecteur normal à tout les hyper-plans représentant les arcs de délais non-nuls. L’ordre d’exécution correspondant au vecteur } ne doit entraîner aucun cycle entre les cellules du GDC. Un vecteur assurant un ordre d’exécution des cellules du graphe de dépendances de données, est un vecteur qui respecte l’exécution de 0. Le GFDM du filtre numérique d’ondelettes peut être exécuté suivant le vecteur d’ordonnancement }  0,1. Cet ordre signifie que les itérations peuvent être exécutées en incrémentant le compteur de la boucle interne. Par contre, on peut facilement constater à partir du graphe de dépendances des cellules que le vecteur d’ordonnancement }  1,0 ne permet pas d’obtenir un GDFM réalisable, vue la dépendance de données  @ %. On note que pour deux vecteurs bidimensionnels Y  Y. 9, Y. : et ~  ~. 9, ~. :, l’addition des deux vecteurs est égale à Y . ~  Y. 9 . ~. 9, Y. : . ~. :, et le produit scalaire est égal à Y. ~  Y. 9  ~. 9 . Y. :  ~. :. Ce vecteur est déterminé en fonction des délais non nul du GFDM. L’ensemble de tous les vecteurs d’ordonnancement possibles à un GFDM est intitulé sous espace d’ordonnancement tel que décrit dans la définition 3.1. Définition 3.1. [1, 2] Un sous espace d’ordonnancement S d’un GFDM réalisable 0  +, 1, ), 2 est la région de l’espace où il existe des vecteurs d’ordonnancement qui maintiennent un ordonnancement réalisable de G, i.e., si le vecteur } 4 / donc )3  } F 0 pout tout 3 4 1. L’espace d’ordonnancement peut être schématisé par l’intersection d’un ensemble d’hyperplans dont chacun correspond à un délai non-nul du graphe. Prenons le cas du filtre numérique d’ondelettes initial dont l’espace d’ordonnancement est coloré en gris dans figure 3.4. Les dépendances de données 3> et 3A définissent un demi-plan, respectivement limité par les droites pointillées. Les équations de ces droites sont déterminées à partir des délais des arcs. Chaque hyperplan contient l’ensemble des vecteurs } dont les résultats de leurs multiplications  avec les délais sont supérieurs ou égaux à zéro. A partir du sous espace d’ordonnancement, le GFDM de la figure 3.1(a) peut être ordonnancé en suivant le vecteur.