IMPLÉMENTATION TEMPS RÉEL EMBARQUÉES DES GFDMs

IMPLÉMENTATION TEMPS RÉEL EMBARQUÉES DES GFDMs

Introduction

Les techniques de parallélisme sont généralement utilisées pour la conception des systèmes temps réel embarquées. Ces systèmes nécessitent une implémentation qui respecte les contraintes de temps d’exécution, tout en utilisant le minimum de ressources matérielles. Cet objectif consiste à explorer les différentes solutions offertes par les techniques d’optimisation dont le choix du parallélisme se base principalement sur les améliorations qu’elles proposent en matière de performance et ressources matérielles. De ce fait, une étape d’estimation s’avère indisponsable pour vérifier le respect des contraintes. Cependant, les techniques de parallélisme des GFDMs procèdent à augmenter progressivement le niveau de parallélisme, sans pour autant vérifier si les performances sont déjà atteintes. De plus, la taille du code augmente en fonction du parallélisme. Donc, le niveau de paralléisme achevé par ces techniques d’optimisation est inadéquat pour le cas des implémentations temps réel embarquées. Dans ce chapitre, nous utilisons des démarches de parallélisme des GFDMs pour générer des implémentations qui respectent une contrainte de temps d’exécution tout en utilisant une taille minimale de code. En premier lieu, nous utilisons la technique du retiming multidimensionnel décalé pour la réalisation de cet objectif. Nous détaillons la théorie d’estimation du temps en fonction du parallélisme choisi par le retiming multidimensionnel décalé. Puis, nous décrivons une démarche d’optimisation qui applique itérativement le retiming multidimensionnel dans l’objectif d’atteindre la contrainte de conception. Une deuxième partie est consacrée à l’utilisation conjointe du parallélisme au niveau des instructions et du parallélisme au niveau des itérations, dont le choix des techniques de parallélisme est basé sur leurs apports en matière de temps d’exécution et de taille de code. 5.2 Respect de contrainte de temps d’exécution par retiming multidimensionnel décalé 5.2.1 Exemple de motivation Le retiming multidimensionnel décalé applique un parallélisme au niveau des instructions du nid de boucles dans le but d’atteindre la période de cycle minimale [1, 2, 4, 10]. Ce parallélisme entraîne une diminution dans le temps d’exécution de l’implémentation, en dépit d’une augmentation de la taille du code. Vu que la technique augmente le niveau du parallélisme itérativement, le temps d’exécution de l’application diminue à plusieurs reprises. Cette augmentation du niveau de parallélisme se poursuit indépendamment de la valeur du temps d’exécution réalisée. Cependant, le code des boucles imbriquées augmente considérablement en fonction du niveau du parallélisme. Nous procédons à étudier l’évolution du temps d’exécution et de la taille du code en fonctions du retiming multidimensionnel pour le cas du filtre à Réponse Impulsionnelle Infinie (RII). Dans le cas où 2#d   2†T[§  1, la technique du retiming multidimensionnel décalée applique 4 transformations de retiming multidimensionnel pour générer l’implémentation finale du filtre. Après chaque transformation, nous générons le GFDM et nous déduisons le code dans le but de calculer son temps d’exécution et sa taille, dont les valeurs sont illustrées dans la courbe de la figure 5.1. L’implémentation ordonnancée avec la période d’horloge minimale est exécutée en 632 unités de temps, avec une taille de code de 402 instructions. Par conséquent, même si le GFDM ordonnancée avec la période d’horloge minimale respecte la contrainte de temps d’exécution, il nécessite des ressources matérielles importantes pour l’implémenter. Nous proposons d’implémenter le filtre à RII en imposant une contrainte de temps d’exécution égale à 900 unités de temps. En se basant sur les valeurs présentées dans la figure 5.1, l’implémentation générée par la troisième transformation de retiming multidimensionnel requiert un temps d’exécution égal représentant ainsi une amélioration de 35.82% par rapport à l’implémentation parallèle. D’où, la solution générée après la contrainte du temps d’exécution l’implémentation ordonnancé ave Figure 5.1 Evolution du temps d’exécution de la taille du code du fit

Principes

Nous avons conclu de l’exemple précédent que, même si l’implémentation ordonnancée avec la période d’horloge minimale respecte la contrainte de temps d’exécution, elle nécessite des ressources matérielles importantes. Il s’avère donc parallélisme permettant de respecter la contrainte d présentons une nouvelle approche d’optimisation permettant d’utiliser la technique de retiming multidimensionnel décalé pour déterminer le niveau du parallélisme minimale assurant le respect de la contrainte de temps l’implémentation résultat est inférieure ou égale à celle de l’implémentation ayan de cycle minimale. La démarche GFDM après chaque fonction fonction de retiming suivante d’exécution ou bien atteindre la période de cycle minimale la figure 5.2. Ce travail consiste à prédire l’évolution du temps d’exécution en fonction des transformations du retiming multidimensionnel. De le temps d’exécution à haut niveau de conception, à partir de la spécification algorithmique. Elle explore le GFDM et les paramètres de la fonction d l’objectif de prétendre la valeur du temps d’exécution. Nous décrivons dans le paragraphe 5.2.3 la théorie de l‘estimation du temps d’exécution d’un GFDM après  l’implémentation générée par la troisième transformation de retiming multidimensionnel on égal à 861. De plus, la taille du code est de 258 représentant ainsi une amélioration de 35.82% par rapport à l’implémentation , la solution générée après la troisième fonction de re d’exécution et utilise une taille de code inférieure par rapport à l’implémentation ordonnancé avec la période de cycle minimale. Evolution du temps d’exécution de la taille du code du fitre à RII en fonction du retiming multidimensionnel Nous avons conclu de l’exemple précédent que, même si l’implémentation ordonnancée avec la période d’horloge minimale respecte la contrainte de temps d’exécution, elle nécessite térielles importantes. Il s’avère donc bénéfique de se limiter au parallélisme permettant de respecter la contrainte du temps. Dans ce contexte, nous présentons une nouvelle approche d’optimisation permettant d’utiliser la technique de ultidimensionnel décalé pour déterminer le niveau du parallélisme minimale assurant le respect de la contrainte de temps d’exécution. De ce fait, la taille du code ’implémentation résultat est inférieure ou égale à celle de l’implémentation ayan La démarche de cette approche procède à vérifier le temps d’exécution du GFDM après chaque fonction du retiming : si la contrainte n’est pas encore respectée, la fonction de retiming suivante est appliquée, jusqu’à atteindre la con d’exécution ou bien atteindre la période de cycle minimale, telle que modélisé Ce travail consiste à prédire l’évolution du temps d’exécution en fonction des transformations du retiming multidimensionnel. De ce fait, notre approche procède à estimer le temps d’exécution à haut niveau de conception, à partir de la spécification algorithmique. Elle explore le GFDM et les paramètres de la fonction du retiming multidimensionnel eur du temps d’exécution. Nous décrivons dans le paragraphe 

la théorie de l‘estimation du temps d’exécution d’un GFDM

après  l’implémentation générée par la troisième transformation de retiming multidimensionnel à 861. De plus, la taille du code est de 258 instructions représentant ainsi une amélioration de 35.82% par rapport à l’implémentation totalement retiming respecte la et utilise une taille de code inférieure par rapport à re à RII en fonction du retiming Nous avons conclu de l’exemple précédent que, même si l’implémentation ordonnancée avec la période d’horloge minimale respecte la contrainte de temps d’exécution, elle nécessite bénéfique de se limiter au niveau de temps. Dans ce contexte, nous présentons une nouvelle approche d’optimisation permettant d’utiliser la technique de ultidimensionnel décalé pour déterminer le niveau du parallélisme minimale a taille du code de ’implémentation résultat est inférieure ou égale à celle de l’implémentation ayant la période le temps d’exécution du si la contrainte n’est pas encore respectée, la , jusqu’à atteindre la contrainte de temps modélisée dans le flot de Ce travail consiste à prédire l’évolution du temps d’exécution en fonction des ce fait, notre approche procède à estimer le temps d’exécution à haut niveau de conception, à partir de la spécification algorithmique. multidimensionnel dans eur du temps d’exécution. Nous décrivons dans le paragraphe 5.2.3 la théorie de l‘estimation du temps d’exécution d’un GFDM après l’application du  retiming. Par la suite, nous présentons dans la partie 5.2.4 la démarche de notre approche d’optimisation en décrivant les algorithmes et leurs complexités. Même si le formalisme est décrit pour le cas des graphes bidimensionnels, il est directement extensible au cas général des boucles imbriquées. Nous tenons à signaler que le temps d’exécution est composé en deux parties : le temps de calcul et le temps de communication [38, 39]. Cette dernière correspond au temps nécessaire à l’ordonnancement des données et à l’accès mémoire, dont les valeurs dépendent de la technologie des processeurs et de l’hiérarchie de la mémoire. Dans ce travail, nous nous contentons de prendre en considération le temps de calcul.