Optimisation par synthèse architecturale des méthodes de partitionnement temporel pour les circuits reconfigurables, Optimizing the methods of temporal partitioning by architectural synthesis for reconfigurable circuits

Ting Liu

Description

Sous la direction de Serge Weber
Thèse soutenue le 13 mai 2008: Nancy 1
Les travaux de recherche présentés se situent dans le contexte des méthodologies d’aide à l’implémentation d’algorithmes graphe flot de données sur architectures reconfigurables dynamiquement de type RSoC (Reconfigurable System on Chip) à base de technologie FPGA. La stratégie visée consiste à mettre en œuvre une approche de conception basée simultanément sur la reconfiguration dynamique (RD) et la synthèse architecturale (SA) en vue d’atteindre la meilleur Adéquation Algorithme Architecture (A3). La méthodologie consiste à identifier et extraire les parties d’une application décrite sous forme d’un GFD afin de les implanter soit par partie successivement reconfigurées (PT), soit par la SA ou bien en combinant les deux méthodes. Pour développer notre solution dans un but d’optimisation et de juste compromis entre les deux approches RD et SA, nous avons défini un paramètre permettant une évaluation du degré inter-partition de mise en œuvre d’unités fonctionnelles partagées. Afin de valider la stratégie méthodologique proposée, nous présentons les résultats de l’application de notre approche sur deux applications temps réel. Une analyse comparative en terme de résultats d’implémentation illustre l’intérêt et la capacité d’optimisation de cette méthode pour l’implémentation en reconfiguration dynamique d’applications complexes sur RSoC.
-FPGA
-Partitionnement Temporel
AThe research work presented in the context of methodologies is to assist the implementation of data flow graph algorithms on dynamically reconfigurable RSoC (Reconfigurable System on Chip)-based FPGA architectures.The main strategy consists in implementing a design approach based on simultaneously both the dynamic reconfiguration (DR) and synthesis architecture (SA) in order to achieve a best Adequacy Algorithm Architecture (A3). The methodology consists in identifying and extracting the parts of an application which is described in form of DFG in order to implement either by successively partial reconfiguration (TP), or by the AS or by combining the two approaches.To develop our solution with a view of optimizing and suitable compromise between the two approaches RD and SA, we propose a parameter in order to evaluate the degree of the inter-partition implementation based on functional units shared. In order to validate the proposed methodological strategy, we present the results of the implementation of our approach on two real-time applications. A comparative analysis with the respecting of the implementation results illustrates the interest and the optimisation ability of our method, which is also for dynamic reconfiguration implementation of the complex applications on RSoC.
Source: http://www.theses.fr/2008NAN10013/document

Sujets

• Circuit logique programmable

Informations

• Publié par: Thesee
• Nombre de lectures: 82
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.

Toute contrefaçon, plagiat, reproduction illicite encourt une
poursuite pénale.


➢ Contact SCD Nancy 1 : [e-mail]




LIENS


Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm U.F.R. Sciences et Techniques, Math´ematiques, Informatiques, Automatique
´Ecole Doctorale Informatique Automatique Electronique Electrotechnique Math´ematiques
´ ´D´epartement de formation Doctorale Electronique Electrotechnique
Optimisation par synth`ese architecturale des m´ethodes
de partitionnement temporel pour les circuits
reconfigurables
`THESE
pr´esent´ee et soutenue publiquement le 13 Mai 2008
pour l’obtention du
Doctorat de l’Universit´e Henri Poincar´e – Nancy 1
´(sp´ecialit´e Instrumentation et Micro-Electronique)
par
Ting LIU
Composition du jury
Rapporteurs : M.Elbey Bourennane Professeur, Universit´e de Bourgogne
M.Jean Philippe Diguet Charg´e de Recherche CNRS (HDR), Lab-STICC,
Universit´e de Bretagne Sud
Examinateurs : M.Fabrice Monteiro Professeur, Universit´e de Metz
M.Serge Weber Professeur, Universit´e Henri Poincar´e, Nancy I
M.Camel Tanougast Maˆıtre de Conf´erences, Universit´e Henri Poincar´e, Nancy I
´Laboratoire d’Instrumentation Electronique de Nancy
Facult´e des Sciences - 54506 Vandoeuvre-l`es-NancyRemerciements
J’adressemessinc`eresremerciementsa`MonsieurElbeyBOURENNANE,Professeura`l’Uni-
versit´e de Bourgogne ainsi qu’`a Monsieur Jean Philippe DIGUET, Charg´e de recherche CNRS
au Lab-STICC `a l’Universit´e de Bretagne Sud, qui m’ont fait l’honneur de juger cette th`ese en
qualit´e de rapporteurs.
J’adresseaussimesremerciementsa`MonsieurFabriceMONTEIRO,Professeur`al’Universit´e
de Metz d’avoir accept´e d’examiner ce travail et de participer au jury.
Je tiens a` remercier Monsieur Mustapha NADI, Professeur `a l’Universit´e Henri Poincar´e de
Nancy et ancien directeur du Laboratoire LIEN, de m’avoir accueilli au cours de sa direction au
sein du Laboratoire LIEN.
Je tiens a` remercier Monsieur Serge WEBER, Professeur a` l’Universit´e Henri Poincar´e de
Nancy, de m’avoir accueilli au sein de l’´equipe “ Architecture ” qu’il dirige et d’avoir accept´e
d’ˆetre mon directeur de th`ese.
Je souhaite remercier particuli`erement Monsieur Camel TANOUGAST de m’avoir encadr´e
durant cette th`ese sur un sujet tr`es int´eressant, mais aussi pour ses qualit´es scientifiques, sa
disponibilit´e et son soutien.
Toute ma sympathie et mes remerciements vont ´egalement `a l’ensemble des chercheurs et
techniciens du laboratoire.
Ting LIU
F´evrier 2008
iiiJe d´edie cette th`ese `a mon p`ere :
Gaulle.
iiiivTable des mati`eres
R´esum´e 1
Table des figures 7
Glossaire 11
Chapitre 1 Introduction g´en´erale 13
1.1 Historique et contexte g´en´eral :“Le Calcul Reconfigurable” . . . . . . . . . . . . 13
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Probl´ematique de l’´etude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Plan de m´emoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
´Chapitre 2 Approches M´ethodologiques d’Impl´ementation : Etat de l’Art et
Analyse Comparative 21
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Approches m´ethodologiques d’impl´ementation . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Synth`ese Architecturale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1.1 Principe g´en´eral . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1.2 Flot de conception par synth`ese architecturale . . . . . . . . . . 23
2.2.1.2.1 Analyse-Traductionengrapheflotdedonn´ees/contrˆole
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.1.2.2 Ordonnancement
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.1.2.3 Allocation - Assignation - Optimisation
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.1.3 Un Outil de Synth`ese architecturale : GAUT . . . . . . . . . . . 29
vTable des mati`eres
2.2.2 Reconfiguration Dynamique par Partitionnement Temporel . . . . . . . . 34
2.2.2.1 Principe G´en´eral . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.2.2 Consid´erations pour la mise en œuvre de la Reconfiguration Dy-
namique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.2.3 Flot de conception pour l’exploitation de la RD par partitionne-
ment temporel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.2.4 M´ethodesdePartitionnementtemporelpoursyst`emesreconfigu-
rables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.2.4.1 M´ethodologiedepartitionnementtemporelparapproche
it´erative
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.2.4.2 M´ethodologiedepartitionnementtemporelparapproche
constructive
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.2.4.3 M´ethodologiedepartitionnementtemporelconstructive
par estimation et raffinement
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.2.5 Outils de partitionnement et d’exploration : D.A.G.A.R.D . . . 45
2.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4 Analyse comparative : L’apport de la SA et de la RD. . . . . . . . . . . . . . . . 49
2.5 M´ethodologies combinant le partitionnement temporel et la synth`ese architectu-
rale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Chapitre 3 M´ethodologie de Partitionnement temporel optimis´ee par Synth`ese
architecturale 57
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Formulation g´en´erale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.1 Partitionnement temporel et contraintes . . . . . . . . . . . . . . . . . . . 58
3.2.2 Synth`esearchitecturalebas´eesurunit´esfonctionnellespartag´eesetcontraintes 68
3.2.3 Optimisation d’un partitionnement temporel par Synth`ese Inter-partition 71
3.2.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.2.3.2 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.2.3.3 Formalisation:objectifsetconditionsd’unesynth`eseinter-partition 72
3.2.3.4 Consid´erations de mise en œuvre d’une synth`ese inter-partition . 74
vi3.2.4 Le taux de ressemblance mutuelle . . . . . . . . . . . . . . . . . . . . . . 74
3.2.5 Algorithme d’identification et d’extraction d’unit´es fonctionnelles factori-
sables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.2.6 M´ethodologie de partitionnement temporel optimis´ee par synth`ese archi-
tecturale inter-partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.2.6.1 Principe m´ethodologique . . . . . . . . . . . . . . . . . . . . . . 89
3.2.6.2 Flot de conception d’un partitionnement temporel optimis´e par
IPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Chapitre 4 Application et Validation 103
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.2 Application I : D´etection de contour d’images . . . . . . . . . . . . . . . . . . . . 104
4.2.1 Pr´esentation g´en´erale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.2.2 Partitionnement temporel initial . . . . . . . . . . . . . . . . . . . . . . . 106
4.2.2.1 Mod´elisation et caract´erisation technologique . . . . . . . . . . . 107
4.2.2.2 Caract´erisation et annotation du GFD. . . . . . . . . . . . . . . 111
4.2.2.3 Estimation performances et ressources . . . . . . . . . . . . . . . 112
4.2.2.4 Partitionnement temporel initial . . . . . . . . . . . . . . . . . . 112
4.2.3 Optimisation par synth`ese architecturale inter-partiti