Analyse de Résultats de Simulation Cours Pierre-Yves Gueniffey – Julien Roux InfoTronique

Analyse de Résultats de Simulation

Cours

Pierre-Yves Gueniffey – Julien Roux

InfoTronique

2

Plan

• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression de l’état transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

3

Introduction

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

La simulation : outil incontournable

Objectifs de la simulation ?

Qu’est-ce qu’on demande à un modèle de simulation ?

Développement d’un modèle de simulation :

• Vérification du modèle de simulation

• Validation du modèle de simulation

4

Introduction

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

Deux questions essentielles :

• Combien de temps la simulation doit-elle fonctionner ?

• Quand est-ce que le modèle a atteint un état stable ?

Efficacité du modèle :

• Estimation de la variance

• Réduction de la variance

5

Plan

• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression de l’état transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

6

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Vérification = débogage

– S’assurer que le modèle fait ce qu’il est censé faire

• Beaucoup de techniques dans la littérature

– Nous allons en décrire quelques unes

7

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Création modulaire et hiérarchique

– Les modèles de simulation sont de très gros programmes

– Modularité : Le modèle doit être constitué de modules qui communiquent entre eux par des interfaces bien définies

– Hiérarchie : Chaque module du programme est divisé récursivement en modules plus petits jusqu’à obtenir des modules faciles à déboguer

8

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Création modulaire et hiérarchique

– Exemple : Etude de congestion d’un réseau

Modèle Système

9

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Création modulaire et hiérarchique

– Exemple : Etude de congestion d’un réseau

10

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Antibugging

– Ajout de vérifications et de messages dans le programme qui détectent les bugs.

– Exemple dans un réseau :

Nb paquets sources = Nb paquets reçus + Nb paquets perdus

11

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Parcours structuré

– Le développeur explique chaque ligne de son code à une autre personne

– Ceci permet souvent de détecter des bugs

12

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Modèles déterministes

– Pas de variables aléatoires

– Permettre à l’utilisateur de spécifier n’importe quelle distribution

– Ainsi il peut calculer les variables de sortie et déboguer

13

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Exécuter des cas simples

– Assez complexes pour être analysés sans simulation

– Exemples dans un réseau :• Un seul paquet

• Une seule source

• Un seul nœud intermédiaire

14

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Trace

– Liste temporelle d’évènements et de variable

– Ajoute des appels processeur

– Doit pouvoir être désactivé

15

Techniques de vérification de modèles

InfoTronique

• Trace– Exemple dans un réseau :

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

16

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Affichage graphique

– Longue durée des simulations

– L’affichage graphique permet à l’utilisateur de savoir où en est le programme

– Plus compréhensible que les traces

17

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Test de continuité

– Exécuter plusieurs fois la simulation avec de petits changements

– Petits changements dans les entrées du modèle

– Impliquent généralement de petits changements dans les sorties

18

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Test de continuité

– Exemple dans un réseau :

Nombre de sources Nombre de sources

Sortie Sortie

Courbe avant vérification Courbe après vérification

19

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Tests de dégénérescence

– Test des cas extrêmes

– Exemples dans un réseau :• Aucune source

• Aucun routeur

• Routeurs avec des temps de service nuls

20

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Tests de consistance

– Test avec des paramètres d’entrée différents qui ont les mêmes effets

– Exemple dans un réseau :• 2 sources avec 100 paquets / s et 4 sources avec 50 paquets / s

21

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Indépendance de « germe »

– Les germes utilisés pour la génération de nombres aléatoires ne doivent pas affecter le résultat final

– Exécuter la simulation avec différentes valeurs de germes

22

Techniques de vérification de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Questions

23

Plan

• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

24

Techniques de validation de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

Qu’est-ce que la validation de modèle ?

Trois aspects essentiels pour valider un modèle :

• la validation des hypothèses émises au départ

• la validation des valeurs mises en entrée

• la validation des valeurs de sortie

25

Techniques de validation de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

Validation des trois aspects par :

• (1) Avis d’experts

• (2) Des mesures effectuées auprès d’un système réel

• (3) Des résultats théoriques

26

Techniques de validation de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(1) Avis d’experts

Principe

Le choix des experts

Comment les experts procèdent ?

27

Techniques de validation de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(2) Mesures effectuées auprès d’un système réel

Principe

Méthode peu utilisée car :

• Souvent le système réel n’existe pas

• Coût élevé des mesures

28

Techniques de validation de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Résultats théoriques

Principe

Les résultats théoriques sont utilisés pour des cas complexes

29

Techniques de validation de modèles

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

Un modèle n’est jamais parfaitement modélisé

30Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Questions

Techniques de validation de modèles

31

Plan

• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression de l’état transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

32

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Définitions :

– Comportement à l’état uniforme :Comportement lorsque le système a atteint un état stable

– Etat transitoire :Partie initiale de la simulation, avant l’état stable

33

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Dans la plupart des simulations, on ne s’intéresse qu’au comportement à l’état final

• Dans ce cas l’état transitoire ne doit pas être inclus dans le programme final

• Il faut le supprimer• Méthodes empiriques

– Nous allons les décrire

34

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Longues exécutions

– Simulations assez longues pour s’assurer que les conditions initiales n’affectent pas les résultats

– Nécessite des ressources

– Difficile de savoir si la durée d’exécution est suffisamment longue

– Méthode non recommandée

35

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Initialisation appropriée

– Démarrer la simulation dans un état proche de l’état uniforme

– Réduction de la durée de la période transitoire

– Exemple :• Une simulation d’exécution CPU doit démarrée avec des tâches en

attente

36

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Troncation– n observations

– On ignore les l premières observations

– On calcule le minimum et le maximum des n-l observations restantes

– On répète l’opération jusqu’à ce que l’observation l+1 ne soit ni le maximum ni le minimum

37

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Troncation– Exemple :

Numéro de l’observation

Valeur

Intervalle transitoire

38

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Suppression des données initiales

– Réplications : Exécution de la simulation sans changer les paramètres d’entrée mais en changeant les germes des nombres aléatoires

– m réplications de taille n

– xij : la jéme observation de la ième réplication

39

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Suppression des données initiales1. Calcul de la moyenne :

2. Assigner 1 à l

3. Supposer que l’état transitoire dure seulement l, supprimer les l premières observations

40

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Suppression des données initiales4. Calcul du changement relatif

Changement relatif =

5. Répéter les actions 3 et 4 en variant l de 1 à n-1. Après une certaine valeur de l, le graphe se stabilise. Cette valeur de l est la durée de l’état transitoire

41

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Suppression des données initiales– Exemple :

42

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Déplacer la moyenne de réplications indépendantes

– Similaire à la méthode précédente

– Utilisation d’une fenêtre de temps mouvante

43

Suppression de l’état transitoire

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Lots de Moyennes

– Similaire aussi

– Très longues simulations divisées en parties de durée égale

– Calcul de la variance

44Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Questions

Suppression de l’état transitoire

45

Plan

• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression de l’état transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

46

Simulations terminales

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Cas des simulations qui n’atteignent jamais un état final

• Dans ce cas, étude de l’état transitoire

• Exemples : – Transfert de petits fichiers sur un réseau

– Systèmes qui s’éteignent chaque jour à 17h

47Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Questions

Simulations terminales

48

Plan

• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

49

Critère de fin : Estimation de la variance

x

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

Bien choisir la durée de simulation

Rappel :

• La simulation est découpée en échantillons

• Moyenne d’un échantillon :

• Variance de la moyenne d’un échantillon pour n observations indépendantes :

n

xVarxVar

)()(

50

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

Trois méthodes pour calculer correctement la variance :

• (1) Réplications indépendantes

• (2) Méthode des sous échantillons

• (3) Méthode de régénération

51

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(1) Réplications indépendantes

Repose sur la technique de réplication

Le principe :

• m réplications de taille n + n0

(avec n0 la longueur de la phase de transition)

52Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(1) Réplications indépendantes

Calcul de la moyenne pour chaque réplication:

Critère de fin : Estimation de la variance

53Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(1) Réplications indépendantes

Calcul d’une moyenne générale pour toutes les réplications:

Critère de fin : Estimation de la variance

54Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(1) Réplications indépendantes

Calcul de la variance de la moyenne répliquée :

Critère de fin : Estimation de la variance

55Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(1) Réplications indépendantes

Intervalle de confiance pour la réponse moyenne :

Critère de fin : Estimation de la variance

56

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(2) Méthode des sous échantillons

Le principe :

• simulation de (N + n0) observations

• n0 : nombre d’observations dans la phase de transition

• On ignore les n0 observations

• Les observations restantes sont divisées en m lots :

n

Nm

57Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(2) Méthode des sous échantillons

Calcul de la moyenne pour chaque lot :

Critère de fin : Estimation de la variance

58Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(2) Méthode des sous échantillons

Calcul de la moyenne générale :

Critère de fin : Estimation de la variance

59

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(2) Méthode des sous échantillons

Calcul de la variance des moyennes du lot :

60

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(2) Méthode des sous échantillons

Intervalle de confiance pour la réponse moyenne :

61

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(2) Méthode des sous échantillons

Meilleure méthode que les réplications indépendantes

Calcul de la covariance pour optimiser l’intervalle de confiance :

62

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(2) Méthode des sous échantillons

Autocovariance et variance pour des tailles de lots différentes

Taille des lots Auto covariance

Variance

63

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Le principe :

• Simulation régénérative

• Points de régénération :

64

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Considérons la simulation régénérative suivante :

• m cycles de tailles n1,…,nm

65

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Moyennes d’un cycle :

66

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Procédure pour calculer la moyenne générale et son intervalle de confiance :

67

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Calcul des sommes de cycle :

68

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Calcul de la moyenne générale :

69

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Calcul de la différence entre les sommes de cycles attendus et observés :

70

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Calcul de la variance des différences :

71

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Calcul de la longueur d’un cycle moyen :

72

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Intervalle de confiance pour la réponse moyenne :

73

Critère de fin : Estimation de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

(3) Méthode de régénération

Avantage de cette méthode :

• Tient compte de la phase de transition

Inconvénient de cette méthode :

• Temps de simulation ??

• Point de régénération ??

• Application des méthodes de réduction de variance ??

74Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Questions

Critère de fin : Estimation de la variance

75

Plan

• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

76

Réduction de la variance

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

77Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

• Questions

Réduction de la variance

78

Conclusion

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique

Réaliser une simulation c’est déjà bien…

Mais ce n’est pas tout…

Il faut aussi la valider et l’analyser.

Nous avons vu plusieurs méthodes pour cela

Pour être sûr de s’approcher des cas réels

Il faut les appliquer toutes

Bon courage …

79

Questions

Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux

InfoTronique