7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois




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 : theses.sciences@scd.uhp-nancy.fr




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-partitions . . . . . . . . . . 114
4.2.3.1 Taux de ressemblance mutuelle . . . . . . . . . . . . . . . . . . . 114
4.2.3.2 Optimisation par synth`ese architecturale inter-partition . . . . . 115
4.2.3.3 Discussion et analyse . . . . . . . . . . . . . . . . . . . . . . . . 117
4.3 Application II : Algorithme de chiffrement de donn´ee“ AES ” . . . . . . . . . . 120
4.3.1 Pr´esentation g´en´erale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.3.2 Partitionnement temporel initial . . . . . . . . . . . . . . . . . . . . . . . 126
4.3.2.1 Caract´erisation et annotation du GFD. . . . . . . . . . . . . . . 126
4.3.2.2 Partitionnement initial du GFD . . . . . . . . . . . . . . . . . . 128
4.3.3 Optimisation par synth`ese architecturale inter-partition . . . . . . . . . . 132
4.3.3.1 Taux de ressemblance mutuelle . . . . . . . . . . . . . . . . . . . 132
4.3.3.2 Synth`ese architecturale Inter-partition . . . . . . . . . . . . . . . 134
4.3.4 Bilan et discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Chapitre 5 Conclusion G´en´erale et Perspectives 141
vii