these

Informations

• Publié par: Methong
• Nombre de lectures: 35
• Langue: Français

Extrait

Æ
INSTITUT NATIONAL POLYTECHNIQUE DE GRENOBLE
N attribué par la bibliothèque
|_/_/_/_/_/_/_/_/_/_/
THÈSE
pour obtenir le grade de
DOCTEUR DE L’INPG
Spécialité : “Informatique : Systèmes et Communications”
préparée au Laboratoire Informatique et Distribution
dans le cadre de l’école Doctorale “Mathématiques, Sciences et Technologies de
l’Information”
présentée et soutenue publiquement
par
Anne Benoit
le 18 Juin 2003
Méthodes et algorithmes pour l’évaluation des performances des
systèmes informatiques à grand espace d’états
Directeur de thèse : Brigitte Plateau
JURY
M. ANDRZEJ DUDA , Président
MME SUSANNA DONATELLI , Rapporteur
M. JEAN-MICHEL FOURNEAU ,
MME BRIGITTE PLATEAU , Directeur de thèse
M. WILLIAM J. STEWART , Examinateur..
Stochastique. Selon le Grand Dictionnaire d’Oxford, le mot fut créé en 1662, et il est
maintenant rarement utilisé,oupérimé. N’en croyez rien. C’est le Grand Dictionnaire
d’Oxford qui est périmé, et non la stochastique, car ce terme perd chaque jour de son
archaïsme. Son sens primitif est “objectif”, ou “but à atteindre”, d’où les Grecs ont fait
dériver un verbe signifiant “viser une cible” et, par extension métaphorique “réfléchir,
penser”. Il passa dans la langue anglaise, d’abord comme une manière fantaisiste de
condenser “moyens propres à conjecturer”, ainsi que le prouve la réflexion de Whitefoot au
sujet de sir Thomas Browne en 1712 : “Bien qu’il n’eût point de don de prophétie... il
excellait pourtant dans une connaissance qui y touche de fort près, je veux dire la
stochastique, grâce à quoi il se trompait rarement au sujet d’événements futurs.”
Extrait de l’homme stochastique, roman de R. Silverberg.Remerciements
Je tiens tout d’abord à remercier Brigitte Plateau, sans qui ces travaux n’auraient pu
avoir lieu. Jonglant habilement entre son travail de directeur de laboratoire, de professeur et
de chercheur, elle a su néanmoins trouver le temps nécessaire pour me guider et me motiver
dans ma recherche.
Merci aux membres de mon jury, Andrzej Duda, Susanna Donatelli et Jean-Michel
Fourneau pour avoir accepté d’en faire partie. Leurs conseils avisés m’ont permis d’éclairer
certains points de la thèse.
J’ai eu le plaisir de travailler avec Billy Stewart et Paulo Fernandes, d’écrire des articles
en commun avec eux, et les échanges ont toujours été source d’enrichissement. Grâce à
Billy, j’ai de plus découvert quelques subtilités de la langue anglaise, et amélioré la qualité
de mon anglais. Merci aussi aux thésards et stagiaires de l’équipe E3 du laboratoire ID, avec
lesquels j’ai toujours pu échanger sur divers problèmes.
Dans le cadre du projet Decore, Jean-Marc Vincent et Stéphane Mocanu ont proposé des
séminaires très intéressant, et j’ai souvent pu discuter avec eux sur des problèmes un peu
techniques, merci pour leur grande disponibilité et leurs nombreux conseils ! J’ai aussi été
amenée à être responsable d’un axe de ce projet, et nous avons pu obtenir des financements
sans lesquels ces recherches n’auraient pas pu avoir lieu. J’adresse donc un immense merci
au projet Decore.
Merci aux chercheurs que j’ai eu la chance de rencontrer durant ma thèse, et avec qui
l’échange a été très constructif : Oleg Gusak qui m’a initié aux concepts de "lumpability",
Mathieu Le Coz et son interface graphique pour PEPS, et surtout Gianfranco Ciardo et
Susanna Donatelli, dont j’ai eu l’honneur de faire la connaissance pour échanger des idées
et lancer des projets de collaboration sur nos sujets de recherche très proches.
Il y en a bien d’autres, rencontrés au hasard des cours, des écoles et des conférences. Les
rencontres permettent toujours un enrichissement des réflexions personnelles et je remercie
donc tous ceux qui ont discuté avec moi et m’ont donné ainsi matière à avancer.
Je tiens également à remercier toute la joyeuse équipe du laboratoire Informatique et
Distribution qui ont permis un travail dans une ambiance fort sympathique, avec une atten-
tion particulière à tous les "coincheurs" (je ne les cite pas, ils se reconnaîtront sans peine !),
sans qui la digestion aurait été un peu plus pénible...
Mes pensées vont enfin et surtout vers tous ceux qui m’ont soutenu moralement, et
qui ont su accepter mon caractère pas toujours facile à vivre, parfois ma mauvaise humeur
pendant certaines périodes un peu difficiles de ma thèse. Je tiens donc à adresser notamment
un grand merci à ma famille, et à tous mes amis musiciens, montagnards, et coincheurs.
J’ai sûrement oublié de citer certains d’entre vous qui m’ont grandement aidé dans mon
travail, mais au fond de mon coeur je vous remercie chaleureusement.6Table des matières
1 Introduction 11
I Processus de modélisation . . . ......................... 13
II Formalismes de .... 14
III Les méthodes de résolution . ......................... 16
IV Plan de la thèse . ......... 17
IV.1 Modélisation à l’aide de réseaux d’automates stochastiques . . . . . 17
IV.2 Résolution numérique de modèles SAN . . .............. 19
IV.3 Conclusions et perspectives . . ......... 21
2 Les Réseaux d’Automates Stochastiques - SANs 23
I Algèbre tensorielle . ............................... 23
I.1 Produit tensoriel ....... 23
I.2 Somme tensorielle . . . ......................... 27
II Présentation informelle des SANs . . .... 28
II.1 Automates et événements........................ 29
II.2 Automate équivalent . ........ 32
II.3 Descripteur Markovien.................... 34
III Formalisme des réseaux d’automates stochastiques... 37
III.1 Définitions générales ......................... 37
III.2 SAN à temps continu... 38
III.3 SAN à temps discret . ......................... 44
IV Exemples de modélisation . .... 53
IV.1 Partage de ressources : RS . . . .................... 53
IV.2 Réseau de files d’attente : QN .... 56
IV.3 File d’attente à temps discret : FD ................... 62
V Conclusion ........................ 63
3 Réseaux d’automates stochastiques avec réplication 65
I Définition des SANs avec réplication . . .................... 67
I.1 SANs composés d’un seul répliqua ........ 67
I.2 SANs avec plusieurs répliquas . .................... 69
I.3 Comment détecte-t-on les répliquas ? ....... 71
II Agrégation de SANs avec réplication . .................... 71
II.1 Exemple d’agrégation ........ 72
II.2 Conditions ........................ 73
II.3 Expression tensorielle de la matrice de la chaîne de Markov agrégée . 788
III Les bénéfices de l’agrégation ......................... 82
III.1 Résultats théoriques ..... 82
III.2 Exemples pratiques..................... 84
IV Conclusion . . . ........... 86
4 Multiplication Vecteur-Descripteur 87
I L’algorithme du shuffle “classique” : E-Sh ................... 91
I.1 Cas sans éléments fonctionnels ...... 92
I.2 Traitement des dépendances fonctionnelles ............... 97
I.3 Conclusion.................103
II Amélioration de la complexité en temps d’exécution : PR-Sh.........104
II.1 Structures de données......................104
II.2 Algorithme PR-Sh .....107
II.3 Complexité ...........................115
III Optimisation de la place mémoire utilisée : FR-Sh ........117
III.1 Structures de données .....................117
III.2 Algorithme FR-Sh . .........118
III.3 Complexité......................120
IV Optimisation algorithmique : réordonnancement des automates . . . ....123
IV.1 Permutation de vecteurs . . . .................124
IV.2 Algorithmes de multiplication vecteur-descripteur....127
V Conclusion . . . ............................129
5 Résultats numériques 131
I PEPS 2003 ....................................131
I.1 Interface .132
I.2 Le logiciel PEPS 2003..........................135
II Multiplication vecteur-descripteur . .136
II.1 Conditions des mesures.........................136
II.2 Présentation des résultats . . .136
II.3 RS1-1 . . ................................137
II.4 RS2 . . .141
II.5 QN1 . . . ................................144
II.6 Conclusion .....145
III Agrégation de SANs avec réplication .....................147
6 Conclusions et perspectives 149
I . . . ................................149
I.1 Abstraction .....149
I.2 Résolution ................................150
II Perspectives . . .151
II.1 Réseaux d’automates stochastiques . . . ...............151
II.2 Comparaison avec d’autres formalismes .154
II.3 Domaines connexes . ..........................1559
Glossaire 157
Table des figures