Embed Size (px)
Citation preview
Probabilites et Informatique: du modele a l’algorithme
Nicolas Gast
Inria, Grenoble, France
Nicolas Gast – 1 / 19
Modeles
probabilistes
pour les grands systemes
Objectifs des modeles:
Dimensionner le systeme
Predire la performance
Controler le systeme
Nicolas Gast – 2 / 19
Modeles probabilistes pour les grands systemes
Objectifs des modeles:
Dimensionner le systeme
Predire la performance
Controler le systeme
Nicolas Gast – 2 / 19
Ces systemes sont-ils aleatoires?
Les systemes informatiques sont a priori deterministes mais:
Parfois le hasard sert a modeliser ce qu’on ne connaıt pas exactement.
Parfois, le hasard est introduit intentionnellement
Nicolas Gast – 3 / 19
Ces systemes sont-ils aleatoires?
Les systemes informatiques sont a priori deterministes mais:
Parfois le hasard sert a modeliser ce qu’on ne connaıt pas exactement.
Parfois, le hasard est introduit intentionnellement
Nicolas Gast – 3 / 19
On est amene a construire un modele de notre systemeModele = systeme a evenements discrets
But de ces modeles : comprendre, dimensionner, optimiser.Outils : Simulations / Solutions analytiques Nicolas Gast – 4 / 19
Outline
1 Un peu d’histoire : le Modele d’Erlang
2 Methodes asymptotiques
3 Conclusion
Nicolas Gast – 5 / 19
Le modele d’Erlang [1909]
Modele des arrivees: Processus de Poisson
P [Un appel pendant dt] = λdt + o(dt).
Independance temporel.
Temps de traitement d’un appel = 1 unite detemps.
Nicolas Gast – 6 / 19
Modelisation par des files d’attente
Exemple: file d’attente.
(Source: http://www.cs.cmu.edu/~harchol/PerformanceModeling/)
Nicolas Gast – 7 / 19
La formule de Lindley [1952]Tn le temps entre les instants d’arrivee des clients n − 1 et nWn le temps d’attente du nieme client.
Wn+1 = max(0,Wn + 1− Tn+1)
0 1 2 3 4 5 6
Temps
0.0
0.5
1.0
1.5
2.0
Tra
vail
rest
ant
à f
air
e
W1 = 0
T1=1.2 T2=0.7 T3=2.5 T4=1.3
W2 = max(0, 1− 0.7) = 0.3
W3 = max(0, 1.3− 2.5) = 0
Nicolas Gast – 8 / 19
La formule de Lindley [1952]Tn le temps entre les instants d’arrivee des clients n − 1 et nWn le temps d’attente du nieme client.
Wn+1 = max(0,Wn + 1− Tn+1)
0 1 2 3 4 5 6
Temps
0.0
0.5
1.0
1.5
2.0
Tra
vail
rest
ant
à f
air
e
W1 = 0
T1=1.2 T2=0.7 T3=2.5 T4=1.3
W2 = max(0, 1− 0.7) = 0.3
W3 = max(0, 1.3− 2.5) = 0
Nicolas Gast – 8 / 19
La formule de Lindley [1952]Tn le temps entre les instants d’arrivee des clients n − 1 et nWn le temps d’attente du nieme client.
Wn+1 = max(0,Wn + 1− Tn+1)
0 1 2 3 4 5 6
Temps
0.0
0.5
1.0
1.5
2.0
Tra
vail
rest
ant
à f
air
e
W1 = 0
T1=1.2 T2=0.7 T3=2.5 T4=1.3
W2 = max(0, 1− 0.7) = 0.3
W3 = max(0, 1.3− 2.5) = 0
Nicolas Gast – 8 / 19
Les modeles deterministes et stochastiques sont differents
Arrivees Deterministe Arrivees selon un proc. de Poisson
Une arrivee toutes les 1.25 secondes Poisson (λ = 0.8)
0 10 20 30 40 50
Temps
0
1
2
3
4
5
6
7
Tra
vail
rest
ant
à f
air
e
0 10 20 30 40 50
Temps
0
1
2
3
4
5
6
7
Tra
vail
rest
ant
à f
air
e
Aucune attente : E [Wn] = 0
E [Wn] =λ
2(1− λ)= 2
Nicolas Gast – 9 / 19
Les modeles deterministes et stochastiques sont differents
Arrivees Deterministe Arrivees selon un proc. de Poisson
Une arrivee toutes les 1.25 secondes Poisson (λ = 0.8)
0 10 20 30 40 50
Temps
0
1
2
3
4
5
6
7
Tra
vail
rest
ant
à f
air
e
0 10 20 30 40 50
Temps
0
1
2
3
4
5
6
7
Tra
vail
rest
ant
à f
air
e
Aucune attente : E [Wn] = 0 E [Wn] =λ
2(1− λ)= 2
Nicolas Gast – 9 / 19
Si le temps de service n’est pas deterministe, le tempsd’attente est liee a la variabiliteFormule de Pollaczek–Khinchine [1930] https://en.wikipedia.org/wiki/Pollaczek-Khinchine_formula
Les clients arrivent selon un processus de Poisson d’intensite λ
Le temps pour servir un client a une variance V (et est de moyenne 1)
On note W le temps d’attente moyen. On a:
W =λ
2(1− λ)(1 + V ).
Remarque: W tend vers l’infini si λ→ 1 ou V → 1.
Nicolas Gast – 10 / 19
Les reseaux de file d’attenteDeveloppements dans les annees 50-90
A.K. Erlang (1909)
D. Kendall (53) – theorie des files d’attente (notation de Kendall)
L. Kleinrock (60s-70s)
”Basically, what I did for my PhD research in 1961–1962 was toestablish a mathematical theory of packet networks...”
(methodes analytiques, analyse complexe).
Methodes analytiques (encore aujourd’hui utilisees : formules d’Erlang).
Nicolas Gast – 11 / 19
Outline
1 Un peu d’histoire : le Modele d’Erlang
2 Methodes asymptotiques
3 Conclusion
Nicolas Gast – 12 / 19
Probleme: passage a l’echelle des modeles
K-Computer, 88 128 processeurs(credit : http://edition.cnn.com/2012/03/29/tech/super-computer-exa-flop/)
P [X1 = i1 . . .Xk = ik ] 6= P [X1 = i1] . . .P [Xk = ik ]
Nicolas Gast – 13 / 19
Certains systemes se simplifient quand leur taille grandit.
Systeme stochastique
N objets
Comportement aleatoire
N →∞Systeme dynamique (equationdifferentielle ordinaire)
Comportement deterministe
Exemples: physique statistique, reactions chimiques, reseauxinformatiques, propagation de virus, etc.
https://fr.wikipedia.org/wiki/Algorithme_de_colonies_de_fourmis
Condition: Interactions localisee et anonymes.
Nicolas Gast – 14 / 19
Certains systemes se simplifient quand leur taille grandit.
Systeme stochastique
N objets
Comportement aleatoire
N →∞Systeme dynamique (equationdifferentielle ordinaire)
Comportement deterministe
Exemples: physique statistique, reactions chimiques, reseauxinformatiques, propagation de virus, etc.
https://fr.wikipedia.org/wiki/Algorithme_de_colonies_de_fourmis
Condition: Interactions localisee et anonymes.Nicolas Gast – 14 / 19
Exemple: modele de vol de travail
Proc.1
Proc. N
(4, 2, 5, 1, 3, 4, 2, 1, 0, 5, 1, 0, 3)
steal
Nicolas Gast – 15 / 19
Exemple: modele de vol de travail
Proc.1
Proc. N
steal
(4, 2, 5, 1, 3, 4, 2, 1, 0, 5, 1, 0, 3)→ (4, 2, 5, 1, 3, 2, 1, 0, 3, 1, 2, 3)
Nicolas Gast – 15 / 19
Exemple: modele de vol de travail
Proc.1
Proc. N
(4, 2, 5, 1, 3, 4, 2, 1, 0, 5, 1, 0, 3)→ (4, 2, 5, 1, 3, 2, 1, 0, 3, 1, 2, 3)
0 21 3 4 5
steal0 21 3 4 5
Steal
(2, 3, 2, 1, 2, 2)→ (1, 3, 3, 2, 2, 1)
Empirical measure : MN
Nicolas Gast – 15 / 19
Exemple: modele de vol de travail
temps
MN
temps
MN
temps
MN
50 procs 1000 ODE (N → ∞)
E[MN
]= m +
c
N+ O
( 1
N2
)
Nicolas Gast – 16 / 19
Autre exemple d’application : Prediction pour les velib
0 5 10 15 20 25time of the day
0
2
4
6
8
10
arriva
l ra
te o
f use
rs (
even
t/hour)
day of the weekweek-end
P[≥ 1 velo dispo dans 1h
a la station x| #velos dispo
]
Nicolas Gast – 17 / 19
Outline
1 Un peu d’histoire : le Modele d’Erlang
2 Methodes asymptotiques
3 Conclusion
Nicolas Gast – 18 / 19
Conclusion
Prendre en compte l’aleatoire est important pour comprendre dessystemes a priori deterministes.
Applications de l’equipe : calcul haute performance, optimisationenergetique, reseaux sans fils.
Autres exemple d’application : graphes, reseaux sociaux.
https://team.inria.fr/polaris/
Nicolas Gast – 19 / 19
