PROPOSITION D’UNE NOUVELLE TECHNIQUE « RETIMING MULTIDIMENSIONNEL DÉCALÉ »

PROPOSITION D’UNE NOUVELLE TECHNIQUE «RETIMING MULTIDIMENSIONNEL DÉCALÉ »

 Limites des techniques du retiming multidimensionnel existantes

Les techniques de retiming multidimensionnel consistent à transformer les structures des GFDMs dans le but de minimiser la période du cycle. Cette transformation entraîne une modification de l’algorithme correspondant à l’application multidimensionnel. Donc, elle affecte la taille du code et le temps d’exécution de l’implémentation finale. Nous décrivons dans le premier paragraphe l’ordre d’évolution de ces caractéristiques en fonction du retiming multidimensionnel. Puis, nous dégageons les paramètres influant sur la modification de ces grandeurs.

Evolution de la taille du code et du temps d’exécution

La démarche du retiming multidimensionnel consiste à décaler l’ordre d’exécution des instructions. Elle procède à distribuer les nœuds appartenant à un même chemin de délai nul dans différentes itérations. Cette modification entraîne l’exécution d’un ensemble d’occurrences des nœuds en dehors des boucles affectés par le retiming. Une fonction de retiming multidimensionnel , …, boucle tel que consiste à décaler les nœuds appartenant à la 0.

Si est appliqué sur un ensemble de nœuds l’exécution d’un ensemble d’occurrences des nœuds , elle implique en amont de la boucle , intitulé prologue. De même, un ensemble d’occurrences des nœuds tel que sont exécuté en aval de la boucle , intitulé épilogue. Ces nœuds correspondent à l’ajout de blocs de codes en dehors des structures itératives. De ce fait, ils requièrent un ensemble de périodes de cycles supplémentaires pour leurs exécutions.

En outre, la démarche de retiming multidimensionnel vise à augmenter le niveau de parallélisme des traitements itératifs, et non pas au niveau des traitements en amont et en aval des boucles. Par conséquent, le nombre des cycles nécessaires pour l’exécution du prologue et d’épilogue est souvent plus important que le nombre des cycles nécessaires pour l’exécution d’une seule itération. Cette augmentation est proportionnelle à celle du temps d’exécution total.

On déduit que le retiming multidimensionnel implique une augmentation considérable du nombre de périodes de cycles nécessaires pour l’exécution de l’application multidimensionnel. De plus, la transformation due au retiming multidimensionnel affecte l’intervalle des itérateurs des structures itératives. Les valeurs minimales et maximales de ces intervalles dépendent du vecteur d’ordonnancement utilisé lors de l’exécution de l’application.

Il s’avère donc indispensable d’ajouter des instructions pour le re-calcul des nouvelles valeurs des itérateurs. Ces instructions correspondent à un temps d’exécution et une taille du code supplémentaires de l’implémentation finale. En fait, l’évolution des caractéristiques temporelles et du code varient en fonction de deux critères qui sont : la valeur de la fonction du retiming multidimensionnel, et le nombre des fonctions appliquées. 

Impact de la fonction du retiming multidimensionnel

Le nombre des instructions décalées en prologue et épilogue dépend des valeurs des indices de la fonction du retiming multidimensionnel , , …, . Chaque indice renseigne sur la taille de l’ensemble des instructions à décaler en dehors de la structure itérative ; i.e., Si est appliqué sur un ensemble de nœuds et 0, alors | | occurrences des nœuds sont décalées en amont de la boucle (prologue). De même, un ensemble de | | occurrences des nœuds , tel que , sont exécuté en aval de la même boucle (épilogue). Nous constatons que plus l’indice | | est petit, plus la taille du code décalé est moins importante.

Un indice | | 0 permet de maintenir la structure de la boucle et ainsi une taille minimale du code correspondant à cette boucle. Pour le cas du GFDM du filtre numérique d’ondelette, un décalage des instructions dans l’ordre des lignes avec la fonction 0,1 ou dans l’ordre des colonnes avec la fonction 1,0 génère une taille d’algorithme inférieure à celle de l’algorithme généré après le décalage des mêmes nœuds en utilisant l’ordre des deux dimensions avec la fonction 1,1 [4]. Pour remédier à cet inconvénient, les techniques du retiming multidimensionnel visent à choisir des fonctions permettant de générer le minimum de décalage d’instructions.

Les techniques incrémentale et enchaînée procèdent à choisir des vecteurs d’ordonnancement . , . tel que la somme | . | | . | est minimale, puis à sélectionner une fonction de retiming sous la forme de . , . . Le formalisme des GFDMs implique que les vecteurs d’ordonnancement augmentent de valeurs en fonction des retimings multidimensionnels appliqués. Dans ce contexte, la technique enchaînée procède à utiliser itérativement la premier fonction déduite du premier vecteur, afin de réduire les effets du prologue et d’épilogue.

Dans ce même objectif, la technique SPINE teste successivement les vecteurs d’ordonnancement (0,1), (1,0) et (1,1) pour en déduire un retiming légal. Dans le cas contraire, elle sélectionne une fonction de retiming multidimensionnel tel que décrit dans les techniques progressive et enchaînée. Nous tenons à signaler qu’il n’existe aucun travail de recherche décrivant une démarche de sélection de vecteur d’ordonnancement et de fonction de retiming multidimensionnel aboutissant à une implémentation optimale.