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

Télécharger le fichier pdf d’un mémoire de fin d’études

Optimisation des nids de boucles

Optimisation Vs Niveau de conception

Les concepteurs sont de plus en plus confrontés au difficile problème de déterminer les implémentations qui respectent les contraintes de conception. Cet objectif nécessite le recours à des approches d’optimisation assurant l’explorati on des espaces de solutions, afin de trouver une adéquation entre l’architecture et l’application développée. L’exploration peut intervenir à tous les niveaux d’abstraction du flot de conception.
L’optimisation à bas niveau de conception nécessite la mise en œuvre d’un flot de synthèse ou de compilation complet de l’application sur chacune des architectures à comparer. Ce niveau de conception assure l’obtention des mesures de performance très précises. Cependant, la synthèse met en jeu des algorithmes complexes et requiert des outils matériels et logiciels de synthèse pour chaque architecture. De ce fait, l’exploration à ce niveau est caractérisée par un temps et un coût important. Parconséquent, le concepteur est dans l’obligation de se limiter à un espace de solutions restreint.
L’optimisation à haut niveau de conception s’appuie sur l’exploration de la spécification algorithmique des solutions. Dans ce cas, les étapes de synthèse ou de compilation sont remplacées par des algorithmes de faible complexitéet plus rapides que ceux utilisés lors de la synthèse. Par conséquent, elle permet d’explorerun nombre plus important de solutions. Les performances estimées peuvent être peu précises, mais la précision n’est pas le critère essentiel pour le cas de comparaison des différentes solutions. Il est par contre indispensable d’assurer une erreur relative constante pour garantir un choix fiable des résultats.
D’après [106], plus l’approche d’optimisation est appliquée à un haut niveau, plus l’espace d’exploration est plus grand, ce qui perme t généralement de sélectionner une solution plus optimale, tel que formulé dans la figure 2.3. Donc, il s’avère indispensable d’appliquer des techniques d’optimisation à haut niveau pour re specter les contraintes temporelles. Dans ce travail, nous nous intéressons à l’optimisation des nids de boucles au niveau algorithmique de conception.

Optimisation au niveau algorithmique : le parallélisme

Le principe de l’optimisation est de modifier la spécification algorithmique dans l’objectif de minimiser les caractéristiques temporelles. Dans le cas des nids de boucles, l’optimisation consiste à explorer, d’une part l’as pect répétitif au niveau de l’algorithme, et d’autre part les potentialités offertes par l’architecture, pour augmenter le niveau du parallélisme des nids de boucles [81]. La modification de la structure algorithmique est dans l’impératif de conserver les mêmes résultats que algorithmel’ initial. Le parallélisme décrit une démarche de ré-ordonnancement des structures itératives, permettant de sélectionner les traitements indépendants pouvant être exécutés dansle même espace temporel. Le parallélisme est traduit par la duplication des blocs de code correspondant aux traitements à exécuter en parallèle, et ainsi par l’allocation des ressources matérielles nécessaires pour les exécuter. Par conséquent, le parallélisme améliores temps d’exécution des nids de boucles en dépit d’une augmentation des ressources matérielles.
Le parallélisme engendre une augmentation proportionnelle en matière de coût, de consommation et de portabilité des implémentations finales. Cependant, plusieurs implémentations à base de nid de boucles sont soumises à des contraintes à la fois de temps réel et d’embarquabilité. Cette classe d’applications temps réel embarquées, principalement ciblées par nos activités de recherche, occupe uneplace de plus en plus importante dans le monde qui nous entoure. On les trouve maintenant aussi bien dans les produits grand public (téléphonie, automobile, appareil photo, équipements hifi et audio…) que dans les équipements industriels lourds (chaine de fabrication, ferroviaire, avionique, aérospatial …). D’où, la sélection des traitements à paralléliser est contrainte par les ressources matérielles nécessaires à leurs exécutions. Donc, il s’avère important de prendre en considération les contraintes de temps d’exécution et des ressources matérielles lors du choix du parallélisme.

Concepts de base du parallélisme

Démarche du parallélisme

Le parallélisme des nids de boucles se base principalement sur l’exploration des dépendances des données, dans l’objectif d’identifier les instructions à exécuter en parallèle.
Il s’avère difficile d’identifier les dépendances à partir des appels et des affectations des variables dans les instructions. La complexité de cette tâche augmente avec la taille des instructions et des chemins de données. D’une part, ce point est un facteur limitant pour définir un ordonnancement parallèle des instruction. D’autre part, le nombre des solutions de parallélisme est restreint.
Dans ce contexte, les concepteurs procèdent à représenter les nids de boucles par un modèle formel. Ce modèle doit garantir la représentation de toutes les caractéristiques algorithmiques du nid de boucles tel que les dépendances des données, les opérateurs de calcul, les intervalles des itérateurs, etc. De plus, la structure du modèle doit offrir les potentialités nécessaires pour appliquer le parallélisme, dont l’algorithme ne le permet. Un modèle de représentation est indépendant de la structure du nid de boucles à représenter, tel que soit son traitement de calcul. De plus, la structure du modèle permet un retour adéquat vers la structure algorithmique de l’application.
Par la suite, le parallélisme est formulé par une émarched d’exploration du modèle pour sélectionner les traitements indépendants, puis parune transformation de la structure du modèle. Cette transformation doit préserver les fonctionnalités initiales du nid de boucles. Chaque technique de parallélisme est caractérisée arp la granularité des composantes à paralléliser, dont nous distinguons trois types :
– Parallélisme au niveau des instructions [1, 2, 4, 51, 52, 53, 54, 55] : les approches visent à réduire la taille des chemins de données ppartenant à une même itération, dont l’exécution est effectuée dans un le même espace temporel. Elles procèdent à décaler des séquences des chemins dans le but d’atteindre une exécution parallèle des opérations.
– Parallélisme au niveau des itérations [5, 9, 56, 57, 58, 59, 79]: la réduction du nombre des cycles consiste à réduire le nombre d’itérations des boucles appartenant au chemin critique. Les approches procèdent ainsi à la modification des structures des boucles dans le but de paralléliser l’exécution d’un ensemble d’itérations.
– Utilisation conjointe des deux niveaux de parallélisme [10, 8, 6, 3, 31] : la démarche consiste à prédire l’apport de chaque parallélisme dans l’objectif de choisir le(s) parallélisme(s) offrant une meilleur amélioration esd performances et des ressources matérielles des implémentations finales.

Contrainte des dépendances de données

L’analyse des dépendances des données est primordiale pour le choix du parallélisme. Pour le cas des nids de boucles sans dépendance inter-itération, les instructions du corps de la boucle interne peuvent être réordonnancer en utilisant les techniques de retiming ou de pipeline des graphes flot de données acycliques [24, 93]. De plus, les techniques de déroulage des boucles permettent de réordonnancer les itérations du nid de boucles sur unités de calcul tel que [90, 91, 92]. Le parallélisme maximal consiste à allouer chaque itération à une unité de calcul. Ces deux niveaux de parallélismes peuvent être utilisés conjointement. De ce fait, les nids de boucles sans dépendances de données inter-itérations offrent un espace important de solution de parallélisme, ce qui permet au concepteur de choisir l’implémentation adéquate aux contraintes du temps d’exécution et de ressources matérielles.
Pour le cas des nids de boucles avec des dépendances inter-itérations, autres techniques ont été présentées pour assurer le parallélisme.usieursPl d’entre elles ont été proposées pour le parallélisme des instructions d’une seule boucle du nid. Certaines techniques sont appliquées à un niveau spécifique de boucle tel quela boucle interne [7, 23] ou la boucle externe [21]. D’autres techniques consistent à choi sir le niveau de boucle dont le parallélisme assure une meilleure amélioration des performances [16]. Cependant, l’apport de ces techniques est limité au parallélisme d’un seul niveau de boucle.
Un nombre restreint de techniques adressent le parallélisme à travers des boucles imbriquées. Pour le cas du parallélisme au niveau esd instructions, les techniques procèdent à décaler les instructions dans des itérations différentes à celles initiales, afin les exécuter en parallèle [20, 22, 1, 2]. Pour le parallélisme au niveau des itérations, les techniques regroupes les itérations indépendantes dans l’objectif de lesexécuter en parallèle [5, 9, 14]. En présence des dépendances inter-itérations, les deux types d’ordonnancement parallèle engendrent un décalage des blocs de codes en amont et en aval desboucles imbriquées [1, 2, 9, 11], ce qui requiert plus de ressources matérielles pour l’implémentation. De ce fait, proposer une implémentation avec un rapport adéquat en « temps ’exécutiond » et en « ressources matérielles » est un chalenge pour les concepteurs des systèmes embarqués temps réel [17]. Dans ce manuscrit, on s’intéresse aux techniques du parallélisme à travers les niveaux du nid de boucles ayant des dépendances inter-itérations.

Nombre des unités de calcul

L’ordonnancement du nid de boucles consiste à explo rer le modèle de représentation pour identifier les traitements à exécuter en parallèle . De ce fait, chaque traitement doit être exécuté sur une unité de calcul (CPU ou GPU). Chaque démarche de parallélisme consiste à augmenter les traitements parallèles. Cependant, ce parallélisme est contraint par le nombre des unités disponible dans l’architecture. D’où, plusieurs techniques de parallélisme procèdent à réordonnancer le nid de boucles en respectant une contrainte de nombre maximal d’unités de calcul.

Mémoire

Les mémoires assurent la collecte et l’échange desdonnées entre les unités de calcul, suivant l’ordonnancement du traitement exigé par lecompilateur. Vue les différents types de dépendances de données, l’utilisation de la mémoirediffère d’une application à une autre.
Dans ce contexte, les concepteurs ont proposé des architectures à plusieurs unités de calcul, dont les structures diffèrent selon la stratégie derépartition de la mémoire. L’architecture à mémoire partagée est adéquate pour le cas d’échangeintensif de données générées par les traitements parallèles des processeurs. En contraste, l’architecture à mémoire dédiée est utilisée dans le cas où les traitements affectés aux processeurs sont proportionnellement indépendants. Plusieurs autres architectures de réseaux de processeurs sont générées, combinant l’utilisation des mémoires dédiées et partagées, en se basant sur les caractéristiques d’exécution d’une famille d’application bien spécifiques. Par conséquent, les démarches d’optimisation sont dans l’impératif de choisir la hiérarchie de mémoire adéquate dans l’objectif d’améliorer les performances de l’implémentation.

Taille du code

Les techniques de parallélisme entraînent une augmentation de la taille du code du nid de boucles. Le parallélisme au niveau des itérations ngendre la duplication du code itératif des corps de boucles, ce qui correspond à une duplicati on similaire en ressources matérielles. De plus, pour le cas des nids de boucles avec dépendances inter-itérations, les techniques de parallélisme impliquent l’ajout des blocs de code de prologue et d’épilogue à travers les structures des boucles. Ces instructions engendrent une utilisation importante des registres pour le stockage des variables de l’itération en aval. Par conséquent, la taille du code du nid de boucles est similaire à l’utilisation des ressou rces matérielles de l’architecture.

Techniques du parallélisme

Parallélisme au niveau des instructions

La technique « Outer Loop Pipelining »

Cette technique procède à réordonnancer le nid des boucles de la boucle interne à la boucle externe [21]. Ce travail affirme que l’inconvénient du pipeline logiciel est le temps d’exécution des instructions en prologue et épilogue, surtout dans le cas des latences réduites des itérations. La première étape consiste à appliquer le parallélisme au niveau des itérations de la boucle interne. La deuxième assure le parallélisme des prologues et des épilogues due au premier parallélisme.
Le temps du corps de la boucle interne est représenté sous la forme d’une latence exprimée en unité de périodes de cycle. Le parallélisme consiste à appliquer le pipeline aux périodes de cycle des itérations de la boucle interne. Prenons l’exemple du nid de boucles de la figure 2.8(a), dont la boucle interne est composée de 2 itérations. Pour le cas où la latence de l’itération est égale à 4, le pipeline décale l’exécution des itérations de la boucle interne par un seul cycle. Cette ordonnancement est répartie enun corps de boucle incluant cycles de chaque itération, limité par un prologue et un épilogue, tel que affiché dans la figure 2.8(b). Par la suite, elle vise à réduire leurs temps de calcul en exécutant en parallèle l’épilogue appartenant.1 à l’itération de la boucle externe avec le prologue appartenant à l’itération

Synthèse des modèles de représentation des nids deboucles

Critères de classification des modèles de représenta ion

Après avoir passé en revue les plus importants modèles de représentation des nids de boucles et leurs techniques d’optimisation, nous avons jugé indispensable de rappeler les principales exigences et caractéristiques que doit disposer un modèle de représentation, avant de dresser leur bilan comparatif. Une telle liste pourrait servir à indiquer les défis actuels ainsi que les degrés d’efficacité de ces modèles. Ces cactéristiques portent sur plusieurs aspects de la spécification algorithmique :
– Dimension du nid de boucles : indique le nombre des boucles imbriquées du nid.Ce paramètre est de plus en plus primordial en vue de l’augmentation de la complexité des applications en matière de traitement itératif.Un modèle présentant explicitement la dimension du nid permet d’augmenter le nombre des scénarios du parallélisme et ainsi de choisir une solution plus optimale.
– Occurrences des itérations des boucles :représente le nombre des itérations de chaque boucle. Ce paramètre est indispensable lors du choix du parallélisme, vue la contrainte de décalage d’un nombre d’itérations en dehors desstructures des boucles.
– Granularité au niveau des itérations :indique la représentation explicite de chaque itération des boucles. Ce paramètre renseigne principalement sur les caractéristiques de chaque itération tel que le vecteur d’itérations, le temps d’exécution, etc.
– Granularité au niveau des instructions : informe sur les caractéristiques des instructions appartenant au nid de boucles en matière de type de calcul et de temps d’exécution.
– Dépendances des données inter-itérations indique: la représentation des dépendances des données à travers deux itérations différentes.
– Dépendances des données intra-itérations représente: la formulation des dépendances de données entre deux instructions d’une même itération. Ce critère reflète l’ordre d’exécution des instructions ainsi que les différents chemins de données appartenant à une même itération. Ce paramètre est nécessaire pour définir le nombre des unités de traitement nécessaires pour l’exécution d’une seuleitération.

Technique du « retiming itérationnel »

Cette technique procède au parallélisme des itérations en deux étapes : la première consiste à répartir les itérations en groupes similaires; la deuxième étape consiste à paralléliser l’exécution des itérations du même groupe [13, 76]Cette. technique vise à réduire le temps moyen d’exécution d’une itération du nid de boucles.
Dans ce contexte, elle explore les dépendances de données de l’espace d’itérations. Les partitions sont définies en se basant sur vecteurs, tel que est la dimension du nid de boucles. Chaque vecteur d’une boucle indique le sens de regroupement des itérations de la boucle. Pour le cas de l’espace d’itération de la figure 3.7, les partitions sont encadrées par des traits pointillés. L’espace d’itération 0,1 est répartie 2, 2 en groupe dont les vecteurs de la boucle externe et interne sont respectivement et . La répartition est faite de façon qu’il n’existe pas de boucle de dépendances entre deux partitions, afin de permettre une exécution cohérente. Les dépendances des données inter-itérations peuvent impliquer l’exécution d’un ensemble d’itérations 0,0 0,1 en dehors 1,0 des groupes, sous la forme de prologue et d’épilogue, tel que les itérations , et de la figure 3.7.
Par la suite, les itérations appartenant à la mêmepartition sont représentées dans un graphe intitulé « Graphe de Flot d’Itérations (GFI)» dont les nœuds représentent des itérations et les arcs représentent les dépendancesdes données inter-itérations. Ces dépendances de données sont étiquetées par des délais indiquant l’ordre d’exécution des itérations. Chaque partition de l’espace des itérations de la figure 3.7 est modélisée par le GFI de la figure 3.8. La démarche de retiming itérationel fait recours au retiming des graphes synchrones [24] pour exécuter en parallèle tout lesitérations d’une même partition.
L’augmentation du niveau de parallélisme consiste à augmenter le nombre des itérations dans chaque groupe. Cependant, un niveau de parallélisme élevé engendre l’augmentation du nombre des itérations à exécuter en prologue et en épilogue. Cette technique a été étendue dans [76] en décrivant la façon de répartir les itérations dans l’objectif de réduire le temps d’accès à la mémoire cache et ainsi d’améliorer laperformance de l’implémentation.

Retiming multidimensionnel progressif

Cette technique vise à atteindre une exécution totalement parallèle des instructions du corps de la boucle interne [2]. Elle procède à sélectionner et appliquer itérativement le retiming multidimensionnel telle que décrit dans les théorèmes 3.1 et 3.2. Elle débute par identifier les premières instructions exécutées dans le corps de la boucle pour décaler leurs exécutions. Dans cet objectif, elle identifie tous les nœuds du GFDM ayant des arcs entrant de délais non-nuls. Puis, elle sélectionne un vecteur d’ordonnancement tel que ƒ pour l’appliquer est minimale et en déduire une fonction de retiming multidimensionnel ƒ } |/d| . |/[| délais ƒ „ critiques en retirant lesaux nœuds [2, 3]. Cette transformation réduit les tailles des chemins € nœuds . Cette modification entraîne que les nœuds successeurs ont des arcs entrants de ƒ non-nuls et des arcs sortants de délais nuls. De ce fait, ils représentent les nœuds à exécuter en premier dans le corps de la boucle. D’où, la technique progressive procède à sélectionner un deuxième vecteur d’ordonnancement et en déduire une fonction de retiming multidimensionnel pour l’appliquer aux nœuds . La technique progressive } applique itérativement ces étapes, en balayant progressivement le GFDM dans l’ordre des € „ dépendances des données jusqu’à atteindre un parallélisme maximal. Nous illustrons dans les graphes de la figure 3.12 le GFDM du filtre numérique d’ondelettes généré par la technique € 0,1 % € du retiming multidimensionnel progressive. La première étape consiste à appliquer la fonction 1, 3 sur le T . Le parallélisme total est atteint en appliquant la fonction nœud sur le nœud .
En fait, les nouvelles valeurs des délais impliquent l’augmentation des vecteurs 3.1, plus l’ordre 1,0 3,1 d’ordonnancement. Pour le cas du filtre numérique d’ondelettes, le vecteur d’ordonnancement initial est égal à tandis que le deuxième est égal à . En se basant sur le théorème « ). 9 » « ). : » € ).9,).: est d’application une fonction de ret iming multidimensionnel plus grand, plus les valeurs des indices et sont importants.

Table des matières

CHAPITRE 1 : INTRODUCTION GÉNÉRALE
1.1 Domaine d’intérêt
1.2 Contexte
1.3 Problématique
1.4 Contribution
1.5 Plan de la thèse
CHAPITRE 2 : PARALLÉLISME DES NIDS DE BOUCLES
2.1 Introduction
2.2 Nid de boucles
2.2.1 Structure d’une boucle
2.2.2 Nid de boucles
2.3 Dépendances de données
2.4 Caractéristiques temporelles des nids de boucles
2.4.1 Temps d’exécution des nids de boucles
2.4.2 Implémentation temps réel des nids de boucles
2.5 Optimisation des nids de boucles
2.5.1 Optimisation Vs Niveau de conception
2.5.2 Optimisation au niveau algorithmique : le parallélisme
2.6 Concepts de base du parallélisme
2.6.1 Démarche du parallélisme
2.6.2 Contrainte des dépendances de données
2.7 Modèle de représentation des nids de boucles
2.7.1 Graphe factorisé et conditionné de dépendances de données
2.7.2 Graphe flot de données multidimensionnel
2.7.3 Modèle polyédrique
2.8 Contraintes d’optimisation
2.8.1 Contraintes temporelles
2.8.1.1 Temps d’exécution
2.8.1.2 Accélération
2.8.1.3 Période d’itération [4]
2.8.2 Contraintes matérielles
2.8.2.1 Nombre des unités de calcul
2.8.2.2 Mémoire
2.8.2.3 Taille du code
2.9 Techniques du parallélisme
2.9.1 Parallélisme au niveau des instructions
2.9.1.1 La technique « Outer Loop Pipelining »
2.9.1.2 La technique « Polyhedral Bubble Insertion »
2.9.1.3 L’approche du « Retiming Multidimensionnel »
2.9.2 Parallélisme au niveau des itérations
2.9.2.1 La technique « loop striping »
2.9.2.2 La technique « Loop tiling »
2.10 Synthèse des modèles de représentation des nids de boucles
2.10.1 Critères de classification des modèles de représentation
2.10.2 Bilan des modèles de représentations des nids de boucles
2.11 Conclusion
CHAPITRE 3 : GRAPHE DE FLOT DE DONNÉES MULTIDIMENSIONNEL ET TECHNIQUES DE PARALLÉLISME
3.1 Introduction
3.2 Formalisme graphique des nids de boucles
3.2.1 Graphe flot de données multidimensionnel
3.2.2 Les graphes d’ordonnancement des GFDMs
3.2.3 Vecteur d’ordonnancement
3.3 Parallélisme au niveau des itérations
3.3.1 Principe
3.3.2 Les techniques de parallélisme
3.3.2.1 Loop striping
3.3.2.2 Technique du « retiming itérationnel »
3.4 Parallélisme au niveau des instructions
3.4.1 Principe
3.4.1 Sélection de la fonction du retiming multidimensionnel
3.4.2 Les techniques du retiming multidimensionnel
3.4.2.1 Retiming multidimensionnel progressif
3.4.2.2 Retiming multidimensionnel enchaîné
3.4.2.3 La technique SPINE
3.4.3 Contraintes du retiming multidimensionnel
3.5 Application conjointe des niveaux du parallélisme
3.6 Synthèse des techniques de parallélisme des GFDMs
3.7 Conclusion
CHAPITRE 4 : PROPOSITION D’UNE NOUVELLE TECHNIQUE « RETIMING MULTIDIMENSIONNEL DÉCALÉ »
4.1 Introduction
4.2 Limites des techniques du retiming multidimensionnel existantes
4.2.1 Evolution de la taille du code et du temps d’exécution
4.2.2 Impact de la fonction du retiming multidimensionnel
4.2.3 Impact du nombre des fonctions du retiming multidimensionnel
4.3 Motivation et principes
4.3.1 Exemple de motivation
4.3.2 Principes du retiming multidimensionnel décalé
4.4 Sélection des chemins de données
4.4.1 Propriétés du temps d’exécution et des dépendances de données du GFDM
4.4.2 Sélection des chemins de données
4.5 Retiming multidimensionnel pour un chemin de données
4.6 Technique du retiming multidimensionnel décalé
4.6.1 Démarche
4.6.2 Identification des chemins
4.6.3 Algorithme du retiming multidimensionnel décalé
4.7 Extension de la technique de retiming multidimensionnel décalé
4.7.1 Utilisation multiple d’une fonction de retiming
4.7.2 Démarche
4.7.3 Génération du graphe flot de données multidimensionnel étiqueté
4.7.4 Algorithme de l’extension du retiming multidimensionnel décalé
4.8 Résultats expérimentaux
4.8.1 Principe
4.8.2 Validation de la technique du retiming multidimensionnel décalé
4.9 Conclusion
CHAPITRE 5 : IMPLÉMENTATION TEMPS RÉEL EMBARQUÉES DES GFDMs
5.1 Introduction
5.2 Respect de contrainte de temps d’exécution par retiming multidimensionnel décalé
5.2.1 Exemple de motivation
5.2.2 Principes
5.2.3 Estimation du temps d’exécution
5.2.3.1 Temps d’exécution du MDFG uniforme
5.2.3.2 Temps d’exécution après une fonction du retiming multidimensionnel
5.2.3.3 Temps d’exécution après plusieurs retiming multidimensionnel
5.2.4 L’algorithme de l’approche d’optimisation
5.3 Respect de contrainte de temps d’exécution et utilisation minimale de code par retiming
multidimensionnel décalé et le loop striping
5.3.1 Contexte
5.3.2 Principes
5.3.3 Ordre d’utilisation des techniques de parallélisme
5.3.4 Choix des techniques de parallélisme
5.3.5 Calcul des fonctions du coût
5.3.5.1 Principes du calcul des fonctions du coût
5.3.5.2 Algorithmes des fonctions de coût
5.3.6 Résultats expérimentaux
5.3.6.1 Principes
5.3.6.2 Respect de la contrainte du temps d’exécution
5.3.6.3 Minimisation des tailles des codes
5.4 Conclusion
CHAPITRE 6 : CONCLUSION GÉNÉRALE ET PERSPECTIVES
6.1 Conclusion
6.2 Perspectives
BIBLIOGRAPHIE

Télécharger le rapport complet