memoire.dvi

Description

• cours - matière potentielle : redaction

UNIVERSITE DE TECHNOLOGIE DE COMPIEGNE CONTRIBUTIONS A L'OPTIMISATION COMBINATOIRE POUR L'EMBARQUE : DES AUTOCOMMUTATEURS CELLULAIRES AUX MICROPROCESSEURS MASSIVEMENT PARALLELES THESE D'HABILITATION A DIRIGER DES RECHERCHES presentee et soutenue publiquement par M. Renaud Sirdey Ingenieur-chercheur au Commissariat a l'Energie Atomique le 29 novembre 2011 a l'Institut de Physique Theorique devant le jury compose de : M. Walid Ben-Ameur, Professeur a l'Institut Telecom (rapporteur) M. Jacques Carlier, Professeur a l'Universite de Technologie de Compiegne (president) M. Philippe Chretienne, Professeur a l'Universite Pierre et Marie Curie (rapporteur) M. Vincent David, Professeur a l'Institut National des Sciences et Techniques Nucleaires M. Dritan

• routage de reseaux de processus
• caractere incertain des temps d'execution
• algorithme de resolution
• execution en memoire bornee
• configuration internet public
• ordonnancement pour le prechargement des donnees
• processus de compilation
• memoire

Sujets

• Redaction
• Christianisme
• Dubrulle

Informations

• Publié par: olli0
• Nombre de lectures: 63
• Poids de l'ouvrage: 1 Mo

Extrait

´ `UNIVERSITE DE TECHNOLOGIE DE COMPIEGNE
`CONTRIBUTIONS A L’OPTIMISATION COMBINATOIRE POUR
´L’EMBARQUE : DES AUTOCOMMUTATEURS CELLULAIRES AUX
`MICROPROCESSEURS MASSIVEMENT PARALLELES
` `THESE D’HABILITATION A DIRIGER DES RECHERCHES
pr´esent´ee et soutenue publiquement
par
M. Renaud Sirdey
´Ing´enieur-chercheur au Commissariat `a l’Energie Atomique
le 29 novembre 2011
`a l’Institut de Physique Th´eorique
devant le jury compos´e de :
M. Walid Ben-Ameur, Professeur `a l’Institut T´el´ecom (rapporteur)
M. Jacques Carlier, Professeur `a l’Universit´e de Technologie de Compi`egne (pr´esident)
M. Philippe Chr´etienne, Professeur `a l’Universit´e Pierre et Marie Curie (rapporteur)
M. Vincent David, Professeur a` l’Institut National des Sciences et Techniques Nucl´eaires
M. Dritan Nace, Professeur a` l’Universit´e de Technologie de Compi`egne
M. Marc Sevaux, Professeur `a l’Universit´e de Bretagne Sud (rapporteur)Cette page est intentionnellement blanche!`A Delphine, Benoˆıt, Cl´ement et Marion.Cette page est intentionnellement blanche!Remerciements
Je tiens `aexprimer mesplus sinc`eres remerciements `aMessieurs Jacques Car-
lier et Dritan Nace, tous les deux Professeurs `a l’Universit´e de Technologie de
Compi`egne, pour notre collaboration scientifique qui perdure depuis 2003 ainsi
que pour avoir coordonn´e ma th`ese d’Habilitation `a Diriger des Recherches.
Mes remerciements vont ensuite `a Messieurs Walid Ben-Ameur, Professeur `a
l’Institut T´el´ecom, Philippe Chr´etienne, Professeur `a l’Universit´e Pierre et Marie
Curie, et Marc Sevaux, Professeur a` l’Universit´e de Bretagne Sud, qui m’ont fait
l’honneur d’accepter de rapporter la pr´esente th`ese.
Je remercie ´egalement Monsieur Vincent David, Professeur `a l’Institut Na-
tional des Sciences et Techniques Nucl´eaires, qui dirige le Laboratoire Syst`emes
TempsR´eelEmbarqu´esainsiqueMessieurs Jean-Ren´eL`equepeys etThierryCol-
lette, chefs successifs du D´epartement Architectures, Conception de Circuits et
´Logiciels Embarqu´es du Commissariat `a l’Energie Atomique.
Je tiens `a remercier l’ensemble des membres de l’´equipe “Calcul intensif em-
barqu´e”, en particulier Messieurs Pascal Aubry, Lo¨ıc Cudennec, Paul Dubrulle,
Franc¸ois Gal´ea, Thierry Goubier et St´ephane Louise. Cela n’a pas tous les jours
´et´e facile, mais nous avons bel et bien r´eussi en moins de trois ans et `a partir de
rien `a faire exister une nouvelle technologie de programmation parall`ele, compi-
lateur et support d’ex´ecution inclus, ainsi qu’`a amorcer son transfert industriel.
Merci ´egalement `a mes doctorants : Sergiu Carpov, d´esormais docteur, qui a
travaill´e en ordonnancement, Oana Stan (tous les deux co-encadr´es avec Jacques
et Dritan), qui travaille en optimisation sous incertitude, et Simon Fau (co-
encadr´e avec G. Gogniat, Professeur `a l’UBS, et C. Fontaine, cryptologue `a
l’ENSTB) qui consacre sa th`ese aux syst`emes de chiffrement homomorphiques.
Je suis aussi redevable envers Simon Bliudze, Sergiu Carpov, Paul Dubrulle,
ThierryGoubieretOanaStanquiontbienvoulureliredespartiesdecem´emoire.
Je remercie aussi Madame Sandrine Schlutig, physicienne au synchrotron So-
leil, pour une passionnante visite de cet ´equipement le matin de la soutenance.
Enfin, j’exprime tout mon amour “plus haut que la derni`ere hauteur du mon-
de” `a mon ´epouse, Delphine, et aux trois merveilleux soleils de notre vie, Benoˆıt,
Cl´ement et Marion. Chacun avec leur sp´ecialit´e : les tours de Hano¨ı (il y a l`a un
petit effet “papa combinatoricien”), la g´en´eration de mots de passe al´eatoires (et
color´es) et les œuvres d’art (tr`es color´ees) sur manuscrit en cours de r´edaction...
56 REMERCIEMENTSTable des mati`eres
Remerciements 5
Introduction 11
I Probl´ematiques d’affectation de ressources dans les
autocommutateurs pour la t´el´ephonie cellulaire 15
1 Une s´election de probl`emes d’affectation de ressources 19
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2 Configuration optimale de cellule radio . . . . . . . . . . . . . . . 20
1.2.1 Pr´eliminaires . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2.2 Fonction ´economique . . . . . . . . . . . . . . . . . . . . . 21
1.2.3 M´ethode de r´esolution . . . . . . . . . . . . . . . . . . . . 22
1.3 Gestion d’une interface PCM . . . . . . . . . . . . . . . . . . . . 23
1.3.1 Pr´eliminaires . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3.2 M´ethode de r´esolution . . . . . . . . . . . . . . . . . . . . 24
1.3.3 L’analogie “parlementaire” . . . . . . . . . . . . . . . . . . 26
1.4 Maximisation d’une dur´ee de vie sur batterie . . . . . . . . . . . . 26
1.4.1 Pr´eliminaires . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.2 Le probl`eme du sac `a dos max-min . . . . . . . . . . . . . 28
1.4.3 Algorithme de r´esolution . . . . . . . . . . . . . . . . . . . 30
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2 Ordonnancement de migrations de processus 33
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Premiers r´esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
´2.2.1 Enonc´e du probl`eme, complexit´e . . . . . . . . . . . . . . . 34
2.2.2 Cas particuliers polynomiaux . . . . . . . . . . . . . . . . 34
2.3 R´esolution exacte . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.1 Un algorithme de branch-and-bound . . . . . . . . . . . . 36
2.3.2 Approche poly`edrale . . . . . . . . . . . . . . . . . . . . . 37
2.4 R´esolution approch´ee . . . . . . . . . . . . . . . . . . . . . . . . . 38
7`8 TABLE DES MATIERES
2.4.1 R´esolution par recuit simul´e . . . . . . . . . . . . . . . . . 38
2.4.2 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Synchronisation d’horloges 41
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Pr´eliminaires sur les horloges . . . . . . . . . . . . . . . . . . . . 43
3.2.1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . 43
´3.2.2 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Une approche par programmation lin´eaire . . . . . . . . . . . . . 44
3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.2 Formulation lin´eaire . . . . . . . . . . . . . . . . . . . . . 45
3.3.3 Aspects syst`emes . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 R´esultats exp´erimentaux . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.1 Configuration WAN priv´e . . . . . . . . . . . . . . . . . . 47
3.4.2 Configuration Internet public . . . . . . . . . . . . . . . . 49
3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
II Compilation pour les architectures de processeurs
massivement parall`eles 51
4 Compilation flot de donn´ees 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Un mod`ele de programmation parall`ele . . . . . . . . . . . . . . . 56
4.2.1 Mod`eles de calcul flot de donn´ees . . . . . . . . . . . . . . 56
4.2.2 Le langage ΣC . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3 Cadencement par un temps logique . . . . . . . . . . . . . . . . . 62
4.3.1 Rappels sur la th´eorie des ensembles ordonn´es . . . . . . . 62
4.3.2 Encodage vectoriel d’un ordre partiel d’ex´ecution . . . . . 63
4.3.3 Illustration du fonctionnement syst`eme . . . . . . . . . . . 64
4.4 Processus de compilation . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.1 Parseur et g´en´eration de code . . . . . . . . . . . . . . . . 66
4.4.2 Compilation du parall´elisme . . . . . . . . . . . . . . . . . 66
4.4.3 Affectation de ressources . . . . . . . . . . . . . . . . . . . 67
4.4.4 G´en´eration de runtime et construction des binaires . . . . 68
5 Placement et routage de r´eseaux de processus 69
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2 Partitionnement de r´eseaux de processus . . . . . . . . . . . . . . 69
´5.2.1 Enonc´e et complexit´e du probl`eme . . . . . . . . . . . . . 69
´5.2.2 Etat de l’art et positionnement . . . . . . . . . . . . . . . 70
5.2.3 Notion d’affinit´e relative . . . . . . . . . . . . . . . . . . . 71`TABLE DES MATIERES 9
5.2.4 Un algorithme par construction progressive . . . . . . . . . 72
5.2.5 Diversification par randomisation . . . . . . . . . . . . . . 73
5.2.6 R´esultats exp´erimentaux . . . . . . . . . . . . . . . . . . . 74
5.3 G´en´eralisation au partitionnement stochastique . . . . . . . . . . 77
5.3.1 Sur le caract`ere incertain des temps d’ex´ecution . . . . . . 78
5.3.2 L’approche par sc´enarios revisit´ee . . . . . . . . . . . . . . 79
5.3.3 Lien avec la th´eorie des tests d’hypoth`eses . . . . . . . . . 81