DM2
T.Lemaire
March 9, 2017
knitr::opts_chunk$set(echo = TRUE)Source : Corrigé du TD associé au sujet (2017 et 2016)
1 Simulation
Mêmes paramêtres que pour LRU
on initialise le cache avec la même proba que les autres pour a, afin de voir de quel manière ‘a’ va se déplacé vers la gauche du cache.
set.seed(42)
N = 100
a = 0.1
b = (1-a)/(N-1)
K = 20
T = 1000
access = sample(c(1:N), T, prob=c(a,rep(b,N-1)), replace=TRUE)
cache = sample(c(1:N), K, prob=c(rep(b,N)), replace=FALSE) # Un cache initial
#head(access)
#plot.ts(access)
#hist(access,breaks=N)Simulation
modification de l’aglo, en gardant tout les indicateurs dans le code.
miss=c()
missA=c()
posA=c();
for(obj in access) {
if(obj %in% cache) {
pos = (1:K)[cache==obj];
if(pos!=1){ #si obj n'est pas déja tout a gauche on le swap avec son voisin de gauche.
tmp = cache[pos];
cache[pos]=cache[(pos-1)];
cache[pos-1]=tmp;
}
miss=c(miss,0);
missA=c(missA,0);
} else {
cache = c(cache[-K],obj) #on place l'objet en position K, après avoir retirer du cache le précédent K.
miss=c(miss,1);
if(obj == 1) {
missA=c(missA,1);
} else {
missA=c(missA,0);
}
}
if(1 %in% cache) {
posA = c(posA, (1:K)[cache==1]);
} else {
posA = c(posA, NA);
}
}
#head(posA)
sum(miss)## [1] 733sum(missA)## [1] 2plot.ts(posA)
On observe que a est rapidement descendu en position vers la gauche du cache, ensuite a est repassé en 2ème position de temps en temps avant de remonté en 1.
On vois également que ‘a’ à fait 2 défaut de cache. Après être rentré dans le cache en dernière position, il est resortie un 1ère fois suite à un défaut de cache consécutif, et à du refaire une entrée avant de finallement “monté”.
2 Chaine de Markov
On représente dans les différents états la position de a dans le cache. La chaine comporte donc 21 états (K+1), pour les 20(k) positions possibles dans le cache et un état “out”. les déplacement se font ici de proche en proche, il n’y a pas de “saut” en première position comme dans le LRU.
options(width=160)
genere_mat<-function(N=N,K=K){
M=matrix(rep(0,(K+1)*(K+1)),nrow=(K+1));
for(i in 1:K) {
if(i!=1){
M[i,i-1] = a; # proba de bougé "à gauche", a
M[i,i] = (1-(a+b)); # proba de rester sur place, 1 - proba de bougé à droit (b) ou a gauche (a)
}else{
M[i,i] = (1-b); # proba de rester sur place pour dans l'état 1, 1 - proba de bougé à droit (b).
}
M[i,i+1] = b; # proba de bougé "à droite", proba du voisin de droite donc b.
}
M[(K+1),(K+1)] = (1-a); # proba de rester en dehors du buffer
M[(K+1),(K)] = a; # proba de rentrer dans le buffer.
return(M)
}
M=genere_mat(N,20) # chaine pour un cache de 20
options(digits=3); # Restreignons nous à 3 digits
M[1:10,1:11] #début de la chaine## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
## [1,] 0.991 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
## [2,] 0.100 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
## [3,] 0.000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
## [4,] 0.000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
## [5,] 0.000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000
## [6,] 0.000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000
## [7,] 0.000 0.00000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000
## [8,] 0.000 0.00000 0.00000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000
## [9,] 0.000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000
## [10,] 0.000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909M[11:(K+1),10:(K+1)] #fin de la chaine## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
## [1,] 0.1 0.891 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
## [2,] 0.0 0.100 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
## [3,] 0.0 0.000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
## [4,] 0.0 0.000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
## [5,] 0.0 0.000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000 0.00000
## [6,] 0.0 0.000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000 0.00000
## [7,] 0.0 0.000 0.00000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000 0.00000
## [8,] 0.0 0.000 0.00000 0.00000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000 0.00000
## [9,] 0.0 0.000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909 0.00000
## [10,] 0.0 0.000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.10000 0.89091 0.00909
## [11,] 0.0 0.000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.10000 0.90000On cherche les vecteurs propres (copié collé du corrigé de 2016 …)
E=head(eigen(t(M)))
head(E$values)## [1] 1.000 0.951 0.949 0.945 0.941 0.935On récupère la 1ère colonne (en suivant le corrigé du TD pour LRU…)
ssp=E$vectors[,1];
ssp = Re(ssp/(sum(ssp)))
options(digits=7);
ssp## [1] 9.090909e-01 8.264463e-02 7.513148e-03 6.830135e-04 6.209213e-05 5.644739e-06 5.131581e-07 4.665074e-08 4.240976e-09 3.855433e-10 3.504939e-11 3.186310e-12
## [13] 2.896640e-13 2.633322e-14 2.393894e-15 2.176360e-16 1.978279e-17 1.798998e-18 1.634177e-19 1.488163e-20 1.349004e-21On obtient donc π.M, on observe que la probabilité que soit en première position est très importante, beaucoup plus que sur (LRU), puis décroit progressivement pour les position suivante. cela parait cohérent.
On calcule la probabilité que ‘a’ reste dans le cache
sum(ssp[1:K])## [1] 1On dépasse les capacité de calcul en float ? Essaions sur les première positions seulement.
sum(ssp[1:5])## [1] 0.9999938On vois donc que la probabilité d’éviction du cache est extrèmement faible, comme nous le montrait la courbe de la position sur la simmulation. étant donné sa probabilité a monte en première position et n’en bouge presque pas.
Pour les défaut de cache de a
errA = sd(missA)/sqrt(length(missA));
mean(missA);## [1] 0.002mean(missA) - 2*errA;## [1] -0.0008270111mean(missA) + 2*errA;## [1] 0.004827011ssp[(K+1)]*a # cas ou a est à l'éxterieur et qu'on le demande## [1] 1.349004e-22les données de la simmulation ne semble vraiment pas significatifs. les résultats peuvent être faussé par les 2 défaut de cache résultant du choix pour l’initialisation du cache.
D’après la 4ème valeur, la proba de sortir du cache est minime.
Calcule du défaut de cache général
err = sd(miss)/sqrt(length(miss));
mean(miss)## [1] 0.733mean(miss)-2*err;## [1] 0.7050067mean(miss)+2*err## [1] 0.7609933sum(ssp[1:K])*(1-(a+(K-1)*b)) + (ssp[(K+1)])*(1-(K*b)) # la valeur exacte!## [1] 0.7272727Probabilité du défaut de cache en fonction de la taille du buffer.
pmiss=c();
for(K in 1:N) {
M=genere_mat(N,K)
E=head(eigen(t(M)))
head(E$values)
ssp=E$vectors[,1];
ssp = Re(ssp/(sum(ssp)))
pmiss[K] = sum(ssp[1:K])*(1-(a+(K-1)*b)) + sum(ssp[(K+1)])*(1-(K*b)) # la valeur exacte!
}
library(ggplot2)
ggplot(data=data.frame(size=(1:N),pmiss=pmiss), aes(x=size,y=pmiss)) +
geom_point() + theme_bw() + xlab("Taille du cache") +
ylab("Probabilité de défaut de cache")
3 Comparaison “Move-Ahead” et “Move-to-front/LRU”
Récupération des données de LRU du TP :
options(width=160)
M=matrix(rep(0,N*N),nrow=N);
for(i in 1:N) {
M[i,i] = (i-1)*b;
M[i,1] = a;
if(i<N) M[i,i+1] = 1-sum(M[i,]); # et oui,... c'est quand même plus simple comme formule ;)
}
E=head(eigen(t(M)))
ssp=E$vectors[,1];
ssp = Re(ssp/(sum(ssp)))
pmissLRU=c();
for(K in 1:N-1) {
pmissLRU[K] = sum(ssp[1:K])*(1-(a+(K-1)*b)) + sum(ssp[(K+1):N])*(1-(K*b)) # la valeur exacte!
}
pmissLRU[N] = sum(ssp[1:N])*(1-(a+(N-1)*b)) + sum(ssp[N])*(1-(N*b)) On peut maintenant tracer les 2 courbes pour comparer.
df <- rbind(data.frame(size=(1:N),pmiss=pmiss,algo="MA"),data.frame(size=(1:N),pmiss=pmissLRU,algo="LRU"))
library(ggplot2)
ggplot(data=df, aes(x=size,y=pmiss,colour=algo)) +
geom_point() + theme_bw() + xlab("Taille du cache") +
ylab("Probabilité de défaut de cache")
On observe une répartition simmilaire quand le cache deviens grand, en revanche quand le cache est petit Move-Ahead provque moins de défaut de cache.
Cela se comprend car Move-Ahead “retiens” mieux dans le buffer notre objet a quand le cache est petit, étant donné sa probabilité très élévé par raport au autres événement, cela réduit les défaut de cache sur a par rapport à LRU qui fait sortir a plus facilement d’un petit cache.
4 Simulation avec loi de puissance
On crée un vecteur pour les probabilitée de demandes
P = c()
for(i in 1:N){
P=c(P,0.5^i)
}
plot.ts(P)
sum(P)## [1] 1On n’a plus qu’a refaire les simulations, étant donné la loi de puissance utilisé, on réduit la taille du cache pour s’assurer d’avoir quelques défaut de cache. On effectue la simulation sur 10 taille de cache différentes, dans les même conditions (contenue du cache et accès)
N2 = 10 #pas vraiment besoin de faire l'expérience jusqu'a N grand, les défaut de cache disparraissent dans les 2 cas.
access = sample(c(1:N), T, prob=P, replace=TRUE)
set.seed(33)
copiecache = sample(c(1:N), N2, prob=P, replace=FALSE) #sauvegarde pour effectué la deuxième simmulation dans les mêmes conditions
countMissMA = c()
countMissLRU = c()
for(K in 1:N2){
cache = copiecache[1:K];
missMA=c() #miss pour move-ahead
for(obj in access) {
if(obj %in% cache) {
pos = (1:K)[cache==obj];
if(pos!=1){ #si obj n'est pas déja tout a gauche on le swap avec son voisin de gauche.
tmp = cache[pos];
cache[pos]=cache[(pos-1)];
cache[pos-1]=tmp;
}
missMA=c(missMA,0);
} else {
cache = c(cache[-K],obj) #on place l'objet en position K, après avoir retirer du cache le précédent K.
missMA=c(missMA,1);
}
}
countMissMA = c(countMissMA, sum(missMA))
cache = copiecache[1:K];
missLRU=c() #miss pour LRU
for(obj in access) {
if(obj %in% cache) {
pos = (1:K)[cache==obj];
cache = c(obj,cache[-pos])
missLRU=c(missLRU,0);
} else {
cache = c(obj,cache[-K])
missLRU=c(missLRU,1);
}
}
countMissLRU = c(countMissLRU, sum(missLRU))
}
df <- rbind(data.frame(size=(1:N2),countmiss=countMissMA,algo="MA"),data.frame(size=(1:N2),countmiss=countMissLRU,algo="LRU"))
library(ggplot2)
ggplot(data=df, aes(x=size,y=countmiss,colour=algo)) +
geom_point() + theme_bw() + xlab("Taille du cache") +
ylab("Probabilité de défaut de cache")
On observe encore une fois un avantage (léger) pour Move-Ahead quand le cache est très petit.
En conclusion on ebserve bien que les simulations avec des probabilités d’apparition moins grossière, montre la même tendance que les même modèles théoriques sur des probabilitées d’apparition “grossières”.