Sujet 1 - Politiques de cache

Question 1 - Étudiez de la même façon (en simulation) la politique “Move-Ahead”. Comme pour LRU, on suppose que notre cache est trié par date d’accès. Si un objet est déjà présent dans le cache, on le décale d’un cran vers la gauche. Si un objet n’est pas présent dans le cache, on le ramène en position K.

(reprise et modification du code donné en TD, code écrit par Arnaud Legrand disponible sur son site

N = 100
a = 0.1
b = (1-a)/(N-1)
K = 20
T = 10000

access = sample(c(1:N), T, prob=c(a,rep(b,N-1)), replace=TRUE)
head(access)
## [1] 60 92 70 58 93 57
cache = sample(c(1:N), K, prob=c(a,rep(b,N-1)), replace=FALSE) # Un cache initial 
cacheTFront = cache 



posA = c() ;
missA = c() ; 
miss = c()
  for(obj in access) {
      if(obj %in% cache) {
        pos = (1:K)[cache==obj];
        if(pos != 1 ){
          tmp = cache[pos]
          cache[pos] = cache [pos-1]
          cache[pos-1] = tmp 
        }
        #cache = c(obj,cache[-pos])
        miss=c(miss,0);
        
        if(1 %in% cache) {
          posA  = c(posA,((1:K)[!is.na(cache) & cache==1]));
        } else {
          posA  = c(posA,NA);
      }
      } else {
          cache = c(cache[-K],obj)
          miss=c(miss,1);
          if(obj==1) {
            missA=c(missA,1);
          } else {
            missA=c(missA,0);
        }
      }
  }


head(cache)
## [1]  1 65 46 64 72 16
head(posA)
## [1] 7 6 6 6 6 6
head(miss)
## [1] 1 1 1 1 1 1
head(miss)
## [1] 1 1 1 1 1 1
plot(posA); lines(posA);

err = sd(miss)/sqrt(length(miss));
mean(miss)-2*err;
## [1] 0.7192008
mean(miss)+2*err
## [1] 0.7369992

Question 2 - Construisez une chaîne de Markov (spécifique à la taille du cache cette fois-ci, à la différence de ce qu’on a fait pour LRU) et retrouvez les probabilités précédentes (probabilité d’éviction de l’élément A et taux de défauts de cache).

on va considerer un élement e situé à la ième position du cache et soit p sa probabilité d’apparition dans access ( donc p = a si e = 1 sinon p = b )

si i > k :

la position de e dans le cache sera k avec une probabilité de p et sera i+1 avec une probabilité 1-p

si 1< i <= k :

Soit l’élement courant c qui est en position j

  • si j > i+1 : la position de e dans le cache sera i-1 avec un proba p et restera i autrement

  • si j <= i+1 : la position de e dans le cache sera i-1 avec une probabilité p et i+1 si j et en position i+1.

  • si i = 1 : la position de e restera 1 sauf si c est en deuxième position alors e sera en deuxième position ( avec une probabilité 1-p )

markov=matrix(rep(0,N*N),nrow=N);

markov[1,1] = 1-b;
markov[1,2] = b 

for(i in 2:(N-1)) {
  if(i<K){
    markov[i,i-1] = a ;
    markov[i,i+1] = b
    markov[i,i]= 1-b-a 
  }
  if(i>K){
    markov[i,K] = a ; 
    markov[i,i]= 1-a ; 
  }
}


options(digits = 2)
E=head(eigen(t(markov)))
head(E$values)
## [1] 1.00 0.95 0.95 0.94 0.94 0.93
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
##   [6] 5.644739e-06 5.131581e-07 4.665074e-08 4.240976e-09 3.855433e-10
##  [11] 3.504939e-11 3.186308e-12 2.896644e-13 2.633311e-14 2.393906e-15
##  [16] 2.176143e-16 1.976959e-17 1.783718e-18 1.486355e-19 1.351232e-21
##  [21] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [26] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [31] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [36] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [41] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [46] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [51] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [56] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [61] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [66] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [71] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [76] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [81] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [86] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [91] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
##  [96] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00

puis on calucule la probabilité de A d’être dans le cache :

sum(ssp[1:K])
## [1] 1

On arrive a une probabilité très proche de 1.

Question 3 - Comparez “Move-Ahead” à “Move-to-front/LRU” en fonction de la taille du cache.

missTFront=c()
missATFront=c()
posATFront=c();
for(obj in access) {
    if(obj %in% cacheTFront) {
        pos = (1:K)[cacheTFront==obj];
        cacheTFront = c(obj,cacheTFront[-pos])
        missTFront=c(missTFront,0);
        missATFront=c(missATFront,0);
    } else {
        cacheTFront = c(obj,cacheTFront[-K])
        missTFront=c(missTFront,1);
        if(obj == 1) {
           missATFront=c(missATFront,1);
        } else {
           missATFront=c(missATFront,0);
        }
    }
    if(1 %in% cacheTFront) {
        posATFront = c(posATFront, (1:K)[cacheTFront==1]);
    } else {
        posATFront = c(posATFront, NA);
    }
}

on compare ensuite les deux façon de faire :

nombre de miss sur le move ahead

sum(miss) 
## [1] 7281
sum(missA)
## [1] 0

nombre de miss sur le move to front

sum(missTFront)
## [1] 7357
sum(missATFront)
## [1] 90

  • On peut voir que le nombre de miss total est très proche, ce qui est normal car il y’a beacoup d’élément pour une taille de cache assez petite.

  • Pour les miss d’un élément fréquent ( a ) on voit que move ahead est bien plus efficace car l’élement à plus de chance de rester dans le cache et on peut voir que la position de A est souvent dans les premiers élement du cache pour le move ahead (voir au deussus )

sum(missATFront) - sum(missA)
## [1] 90
plot(posATFront); lines(posATFront)