![[*]](../icons/foot_motif.gif){kind=icon}
figés ou FPGA reconfigurables,
plus lourds à mettre en oeuvre mais plus performants).
Participants :
Thierry Grandpierre, Rémy Kocik, Christophe Lavarenne, Yves Sorel, Annie Vicard.
Mots clés : contrôle, commande, traitement du signal, traitement d'images, prototypage rapide, co-design, CAO système, langages synchrones, multiprocesseur, parallèle, distribué, temps réel, embarqué .
Nos recherches concernent la programmation efficace de systèmes informatiques pour des applications de commande et de traitement du signal et des images, soumises à des contraintes temps réel et d'embarquabilité, comme on en rencontre dans les domaines du transport (avionique, automobile), des télécommunications etc...
Dans ces applications, le système programmé commande son environnement en
produisant, par l'intermédiaire d'actionneurs, une commande qu'il calcule à
partir de son état interne et de l'état de l'environnement, acquis par
l'intermédiaire de capteurs. Une analyse mathématique du système de commande
et de son environnement permet de déterminer d'une part une borne supérieure
sur le délai qui s'écoule entre deux échantillons (cadence), et d'autre part
une borne supérieure sur la durée du calcul (latence) entre une détection de
variation d'état de l'environnement (stimulus) et la variation induite de la
commande (réaction). C'est en ce sens qu'on parle de systèmes réactifs
[BB91] : la commande est
calculée en réaction à chaque stimulus. En plus de ces
contraintes temps réel, l'application est soumise à des contraintes
technologiques d'embarquabilité et de coût, qui incitent à
minimiser les ressources matérielles (architecture) nécessaires
à sa réalisation. Pour satisfaire les contraintes temps réel,
et/ou pour rapprocher les ressources de calcul le plus près possible des
capteurs et des actionneurs, l'architecture doit souvent être
multicomposant, parallèle, répartie, distribuée,
composée de plusieurs processeurs et de circuits spécialisés
(Asic figés ou FPGA reconfigurables,
plus lourds à mettre en oeuvre mais plus performants).
La complexité des applications visées, au niveau des algorithmes, de l'architecture matérielle et des interactions avec l'environnement sous contraintes temps réel, nécessite des méthodes pour réduire la durée du cycle de développement, depuis la conception jusqu'à la mise au point, autant des prototypes que des ``produits finis'' qui en dérivent. Afin d'éviter toute rupture entre les différentes phases du cycles de développement et pour permettre des vérifications formelles et des optimisations, notre méthode ``Adéquation Algorithme Architecture'' ( AAA) de prototypage rapide optimisé est fondée sur une approche globale, formalisant l'algorithme, l'architecture et l'implantation, à l'aide d'un modèle unifié de graphes factorisés. L'intérêt principal de ce modèle réside dans sa capacité à exprimer tout le parallélisme, concrètement décrit sous la forme de schémas-blocs, non seulement dans le cas de l'algorithme (graphe flot de données : exemple Simulink) et de l'architecture (interconnexion de composants : exemple VHDL structurel), mais aussi dans le cas de l'implantation de l'algorithme sur l'architecture (distribution et ordonnancement des calculs et des communications, codés sous la forme d'un exécutif et de ``net-lists''). Tout cela simplifie la conception conjointe logiciel/matériel (``co-design'').
Un algorithme tel que défini par Turing et Post est une séquence (ordre total) finie d'opérations directement exécutable par une machine à états finie. Cette définition doit être étendue afin de permettre d'une part la prise en compte du parallélisme disponible dans les architectures distribuées, composées de plusieurs machines à états finies interconnectées, et d'autre part la prise en compte de l'interaction infiniment répétitive de l'application avec son environnement. Pour cela notre modèle d'algorithme est un graphe de dépendances factorisé : c'est un hypergraphe orienté acyclique ( DAG) [SH86], dont les sommets sont des opérations (une entrée booléenne en conditionne l'exécution) partiellement ordonnées [Pra86] (parallélisme potentiel) par leurs dépendances de données (hyperarcs orientés pouvant avoir plusieurs extrémités pour une seule origine, ``diffusion''). Les opérations nécessaires au calcul des événements de sortie pour les actionneurs, à partir des événements d'entrée acquis par les capteurs, sont exécutées à chaque interaction avec l'environnement. L'algorithme est donc modélisé par un graphe de dépendances, infiniment large mais périodique, réduit par factorisation à son motif répétitif [LS97], appelé graphe flot de données. Il peut être soit directement spécifié comme tel, ou bien déduit d'une spécification séquentielle ou CSP (Communicating Sequential Processes de Hoare) par analyse de dépendances, ou encore produit par les compilateurs des langages synchrones (Esterel, Lustre, Signal, à travers leur format commun `` DC'') [Hal93] qui présentent l'intérêt de faire des vérifications formelles en termes d'ordre sur les événements.
Les modèles les plus utilisés pour spécifier des architectures parallèles ou distribuées sont les PRAM (``Parallel Random Access Machines'') et les DRAM (``Distributed Random Access Machines'') [Zom96]. Le premier modèle correspond à un ensemble de processeurs communicant par mémoire partagée alors que le second correspond à un ensemble de processeurs communicant par mémoire distribuée avec passage de messages. Si ces modèles sont suffisants pour décrire, sur une architecture homogène, la distribution et l'ordonnancement des opérations de calcul de l'algorithme, ils ne permettent pas de prendre en compte des architectures hétérogènes ni de décrire précisément la distribution et l'ordonnancement des opérations de communication inter-processeurs qui sont souvent critiques pour les performances temps réel.
Pour cela notre modèle d'architecture multicomposant hétérogène est un hypergraphe non orienté, dont les sommets sont des machines à états finies [Gec86] (séquenceurs d'opérations de calcul ou séquenceurs d'opérations de communication) que nous appelons opérateurs, et dont les hyperarcs sont des ressources partagées entre séquenceurs (mémoires Ram ou Fifo, y compris leurs bus et leurs arbitres) que nous appelons médias. L'hétérogénéité ne signifie pas seulement que les opérateurs et les médias peuvent avoir chacun des caractéristiques différentes (durée d'exécution des opérations et taille mémoire des dépendances de données), mais aussi que certaines opérations ne peuvent être exécutées que par certains opérateurs, ce qui permet de décrire aussi bien des composants programmables (processeurs) que des composants spécialisés ( ASIC ou FPGA) [[24]].
En termes plus concrets, notre modèle d'architecture est une extension du modèle classique RTL (``Register Transfer Level'', niveau transfert de registres) [MC80], que nous qualifions de Macro- RTL. Une opération du graphe de l'algorithme est une macro-instruction (une séquence d'instructions ou un circuit combinatoire) ; une dépendance de données est un macro-registre (des cellules mémoire contiguës). Ce modèle encapsule les détails liés au jeu d'instructions, aux micro-programmes, au pipe-line, au cache, et lisse ainsi ces caractéristiques délicates à prendre en compte lors de l'optimisation. Il présente une complexité réduite adaptée aux algorithmes d'optimisation rapides tout en permettant des résultats d'optimisation relativement (mais suffisamment) précis.
Une implantation d'un algorithme sur une architecture est une distribution et un ordonnancement des opérations de l'algorithme sur les opérateurs de calcul de l'architecture, ainsi que des opérations de communication, qui découlent de la distribution, sur les opérateurs de communication.
La distribution consiste d'une part à affecter chaque opération de l'algorithme à un opérateur de calcul capable de l'exécuter (ce qui conduit à une partition du graphe de l'algorithme), et d'autre part, pour chaque dépendance de données inter-opérateur (c'est-à-dire entre opérations affectées à des opérateurs différents), à choisir une route entre les deux opérateurs (chemin dans le graphe de l'architecture), à créer et insérer, entre les deux opérations de l'algorithme, autant d'opérations de communication qu'il y a d'opérateurs de communication sur la route, et à affecter chacune de ces opérations de communication à l'opérateur de communication correspondant. L'ordonnancement consiste, pour chaque opérateur, à linéariser (rendre total) l'ordre partiel entre les opérations qui lui ont été affectées, c'est-à-dire à ajouter au graphe de l'algorithme des dépendances d'ordonnancement.
Une implantation est donc le graphe résultat d'une transformation du graphe de l'algorithme (ajout des opérations de communication et des dépendances d'ordonnancement), influencée par le graphe de l'architecture. Elle est formalisée comme une composition de trois relations, le routage, la distribution et l'ordonnancement, chacune d'elles s'appliquant à un couple de graphes (algorithme, architecture) [[28]]. Etant donnés un graphe d'algorithme et un graphe d'architecture, il existe un nombre fini, mais qui peut être très grand, d'implantations possibles, chacune avec des performances (latences, cadences) différentes. Ces performances sont obtenues par calculs de chemins critiques (latences) et de boucles critiques (cadences) sur le graphe de l'implantation étiqueté par les durées d'exécution caractéristiques des opérateurs de l'architecture.
L'adéquation entre un algorithme et une architecture soumis à des contraintes temps-réel et d'embarquabilité, est en général un problème d'optimisation complexe où, pour aboutir à une implantation optimisée à partir d'une spécification initiale, l'algorithme peut subir des transformations plus profondes que celles présentées ci-dessus (changement de granularité ... reformulation complète), et où de plus l'architecture peut aussi subir des transformations (changement du nombre et/ou des caractéristiques des composants).
Le problème d'optimisation qui fait l'objet de nos recherches est celui de la minimisation de ressources matérielles sous contraintes temps réel et technologiques. L'algorithme, les composants de l'architecture, et les contraintes temps réel, d'embarquabilité et de coût, sont supposés avoir été déterminés au préalable.
Le problème d'optimisation que nous avons formalisé [LS93,Sor94], et dont nous avons automatisé la résolution approchée dans le logiciel SynDEx qui supporte la méthode AAA, se limite au cas de l'adéquation entre un algorithme et une architecture donnés, y compris dans leur granularité et leur topologie. Même ainsi réduit, ce problème est reconnu NP-complet, et le nombre d'implantations possibles pour l'algorithme et l'architecture d'une application réaliste rend prohibitive toute tentative de recherche exhaustive de la solution optimale, c'est pourquoi on utilise des heuristiques pour trouver des solutions approchées. De plus, l'objectif de prototypage rapide nous a fait étudier plus particulièrement des heuristiques gloutonnes rapides [LC93].
L'heuristique que nous avons développée est de type ``list-scheduling'' améliorée pour prendre en compte les communications inter-opérateurs (avec leur distribution et leur ordonnancement sur les routes, donc tenant compte avec précision des routes parallèles et des conflits d'accès aux ressources partagées), l'hétérogénéité des opérateurs et des médias, et le conditionnement des opérations.
Un exécutif pour processeurs [[31]], comme une ``net-list'' pour circuit, est un codage d'une implantation suivant le modèle macro-RTL de l'architecture. La séquence d'opérations sur chaque opérateur est codée par une séquence de macro-instructions ; sur un circuit les macro-instructions sont des composants de bibliothèque VHDL, mis en pipeline. Les dépendances d'ordonnancement, qui ne sont nécessaires que pour les processeurs, sont implicites dans l'ordre de codage. Chaque dépendance de donnée est codée par un macro-registre passé en argument d'une part à la macro-instruction productrice (à l'origine de la dépendance) et d'autre part aux macro-instructions consommatrices (aux extrémités de la dépendance). L'alternance d'accès à un macro-registre (précédence écriture-lectures intra-itération, et précédence lectures-écriture inter-itération), si elle est trivialement respectée par la mise en séquence sur un même processeur des macro-opérations dépendantes, doit être imposée par l'intermédiaire de macro-opérations de synchronisation lorsque les macro-opérations dépendantes sont exécutées par des opérateurs différents, ce qui est toujours le cas des circuits. Le générateur d'exécutifs du logiciel SynDEx transforme donc le graphe flot de données de l'implantation en graphe flot de contrôle, codé par un exécutif et des ``net-lists'' en VHDL structurel.
Un exécutif est généré dans plusieurs fichiers source, un pour chaque mémoire programme (qui peut être partagée entre plusieurs opérateurs). Chaque fichier est un code intermédiaire composé d'une liste d'appels de macros qui seront traduites par un macro-processeur dans le langage source préféré pour chaque opérateur. Les macros peuvent être classées en deux ensembles. Le premier ensemble est un jeu extensible de macro-instructions spécifiques à l'application, réalisant les opérations de l'algorithme. Le second ensemble, que nous appelons noyau générique d'exécutif, est un jeu fixe de macros système qui supportent le chargement initial des mémoires programmes, la gestion mémoire (allocation statique, copies et fenêtres glissantes de macro-registres), le séquencement (sauts conditionnels et itération), les transferts de données inter-opérateurs (macro-opérations de communication transférant le contenu de macro-registres), les synchronisations inter-séquences (assurant l'alternance entre écriture et lectures de chaque macro-registre partagé entre séquence de calcul et séquences de communication), et le chronométrage (pour permettre la mesure des caractéristiques des opérations de l'algorithme et des performances de l'implantation).