Hassna

reconnaissance e envers mes plus proches coll`gues Gamal Attiya, Pierre Niang, Cederic Sibade, Benoˆ e ıt Kaufmann, Fabiane Delazuna et Eric Lorens, Laurant Perroton et envers tous les autres membres du laboratoire A2 SI pour l’aide qu’ils m’ont apport´ au cours de ces ann´es. e e Ces remerciements ne seraient pas complets sans mes pens´es pour les ˆtres qui me e e sont les plus chers : mes parents, qui m’ont beaucoup appris, et qui, surtout, ont cru en moi qu’ils trouvent ici l’expression de ma reconnaissance.

Linda KAOUANE D´cembre 2004, e Paris, France.

iii

R´sum´ e e

AAA (Algorithme Ad´quation Architecture) est une m´thodologie d´velopp´e pour e e e e le prototypage rapide d’applications d´di´es et temps r´el. Bas´e sur un formalisme e e e e de graphes et un flot de conception unifi´ sans rupture, cette m´thodologie aide le e e d´veloppeur a implanter et optimiser l’implantation d’algorithmes de traitements de e ` signal et d’image sur des architectures multicomposants en supportant toutes les ´tapes e du d´veloppement depuis la sp´cification algorithmique jusqu’au choix de l’implantation e e e e qui respecte les contraintes temps r´el et l’ex´cution du code correspondant dans les composants. Toutefois le flot de l’implantation actuellement support´ par cette m´thodologie est e e limit´ aux composants cibles de types processeurs. Et comme l’ex´cution temps r´el de e e e nos applications cibles exige souvent une utilisation conjointe de composants processeurs et de composants circuits sp´cialis´s, la contribution de ce travail consiste a ´tendre e e ` e ´ la m´thodologie AAA vers des architectures circuits. Etape jug´e indispensable pour e e utiliser pleinement la m´thodologie AAA pour faire la conception conjointe o` la cible e u multiprocesseurs coop`re avec une cible cˆbl´e. e a e Dans cette th`se, nous nous sommes donc int´ress´s a l’extension de la m´thodologie e e e ` e AAA pour le support des implantations sur de composants circuits reconfigurables. Nous avons d´fini et formalis´ une m´thodologie et un flot de prototypage rapide supportant e e e cette extension depuis la sp´cification algorithmique sous forme de graphe factoris´ et e e conditionn´ de d´pendances de donn´es (GFCDD) jusqu’` la g´n´ration du code RTL e e e a e e d´crivant l’architecture circuit de l’implantation mat´rielle. e e Ce flot a ´t´ implant´ dans SynDEx-IC, logiciel d’aide au prototypage rapide sp´cialement ee e e d´velopp´ a partir du noyau de l’environnement SynDEx supportant l’AAA-multiprocesseurs e e` pour supporter cette extension d’AAA. Mots-cl´s : Ad´quation Algorithme-Architecture, Syst`mes temps r´el, Prototypage rapide, e e e e

Synth`se de circuits, Optimisation, Transformations de graphes, G´n´ration automatique de e e e code.

iv

Abstract

The AAA (Algorithm-Architecture Adequation) is a methodology developed for rapid prototyping of dedicated real-time applications. Based upon formal graph model and unified seamless flow, this methodology helps the designer to implement and optimize signal and images processing algorithms onto multicomponent architectures. It supports all the design steps from algorithm specification until the choice of the optimized implementation that satisfy the real-time constraints and code execution on the components. However the flow supported by this methodology is currently limited to multiprocessor componenents. And Since the real-time execution of our applications often demands a joint use of processors components and specialized circuits components, the contribution of this work is to extend the AAA methodology for the use of circuits architectures. Essential step to fully use the AAA methodology to do codesign where the multiprocessors components cooperates with the dedicated ones. In this thesis, we are interested in the extension of the AAA methodology for the support of the implementation onto reconfigurables circuits components. We so defined and formalized a methodology and a design flow of rapid prototyping supporting this extension since the algorithmic specification in term of a factorized and conditioned data dependency graph (GFCDD) to the generation of the RTL code describing the circuit architecture. This flow has been implemented in SynDEx-IC, a CAD software tool, that has been developed from the kernel of the SynDEx environment which support the AAAmultiprocessors. Keywords : Algorithm-Architecture Adequacy, Real-time systems, Rapid prototyping, Circuits synthesis, Optimizations, Graph transformations, Automatique code generation.

v

Table des Mati`res e

Liste des tableaux Liste des figures 1 Introduction 1.1 Contexte : Syst`mes r´actifs temps r´el embarqu´s . . . . . . . . . . . . . . . . e e e e 1.2 Cadre de l’´tude : La m´thodologie AAA d’ad´quation algorithme-architecture e e e 1.3 Motivations et objectifs : Extension d’AAA vers le Co-design . . . . . . . . . . 1.4 Structure de la th`se . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 2 La conception conjointe de syst`mes mixtes mat´riel/logiciel e e 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 La conception conjointe mat´riel/logiciel . . . . . . . . . . . . . . . . . . . . e 2.2.1 Motivation et avantages de la conception conjointe mat´riel/logiciel e 2.2.2 Domaines d’application de la conception conjointe mat´riel/logiciel . e 2.2.3 Principales ´tapes de la conception conjointe mat´riel/logiciel . . . . e e 1.2.3.1 Sp´cification et mod´lisation . . . . . . . . . . . . . . . . . . e e 1.2.3.2 Implantation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3.3 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Syst`mes de conception conjointe mat´riel/logiciel . . . . . . . . . . . . . . e e 2.3.1 Ptolemy/PtolemyII . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Cosyma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Vulcan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Polis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.5 Cosmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.6 CoWare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.7 GrapeII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Caract´ristiques d´sirables des syst`mes de conception conjointe . . . . . . e e e 2.5 Bilan sur les syst`mes de conception conjointe . . . . . . . . . . . . . . . . . e 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 La m´thodologie AAA d’ad´quation algorithme-architecture e e 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 M´thodologie AAA . . . . . . . . . . . . . . . . . . . . . . . . . . e 3.3 Mod`le d’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . e 3.4 Mod`le d’architecture . . . . . . . . . . . . . . . . . . . . . . . . e 3.5 Mod`le d’implantation . . . . . . . . . . . . . . . . . . . . . . . . e 3.6 Optimisation de l’implantation : Ad´quation . . . . . . . . . . . e 3.7 G´n´ration d’ex´cutifs distribu´s temps r´el . . . . . . . . . . . . e e e e e 3.8 Logiciel de CAO niveau syst`me SynDEx . . . . . . . . . . . . . e 3.9 Extension d’AAA aux circuits int´gr´s sp´cifiques . . . . . . . . . e e e vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x xi 1 2 4 5 8 10 11 11 12 13 14 15 16 18 19 19 21 22 22 24 24 25 26 29 33 34 35 36 38 40 42 43 43 45 45

3.10 Conclusion

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47