Move Ahead

Simulation d’un cache “Move Ahead”

Question 1

On se place dans le meme cas que le TD modélisation de cache LRU. On dispose donc d’un cache de taille K, d’un objet A ayant une probalité forte d’être demandé (par exemple la page de notre cours !) et 99 autres éléments ayant une probabilité faible d’être demandé. La simulation s’établira sur 1000 tentative d’accès. Le début de ce DM étant vraiment similaire au TD, on ne pourra que constater que le début de ce code en est largement inspiré.

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

Maintenant on va générer une séquence d’accès et vérifier si elle semble aléatoire et correctement distribuée.

set.seed(42)
acces = sample(1:N,T,replace=T,prob=c(a,rep(b,N-1)))
plot(acces)

hist(acces,breaks=100)

length((1:1000)[acces==1])

## [1] 108

On constate que la séquence est effectivement plutôt bien distribuée même si on se serait attendu à voir l’objet A un peu moins souvent (ce “problème”" se corrigerait avec un échantillon plus grand).

Passons maintenant à la simulation d’un cache MoveAhead (je réutilise votre structure du code de simulation de cache LRU). Les différences avec votre code sont l’initialisation du cache. En effet avec Move Ahead, on “améliore” un cache existant donc on ne peut pas partir d’un cache vide. Les autres modifications sont la gestion du swapping des données du cache et l’écrasement de la derniere valeur du cache par une nouvelle qui rentre dans le cache.

cache=(1:K);     # cache avec les vingts premiers éléments à l'origine.
miss=c();        # pour compter les défauts de caches
missA=c();       # pour compter les défauts de caches de A
posA=c();        # position de l'objet A
for(v in acces) {
    if(v %in% cache) {
        where = (1:K)[cache==v];
        if(where!=1) {
            tmp=cache[where-1];
            cache[where-1]=cache[where]; #j'avance la valeur dans le cache d'une case
            cache[where]=tmp;
            
        }
        miss=c(miss,0);
    } else {
        cache[K]=v;
        miss=c(miss,1);  
        if(v==1) {
            missA=c(missA,1);
        } else {
            missA=c(missA,0);
        }
    }
    if(1 %in% cache) {
        posA  = c(posA,((1:K)[!is.na(cache) & cache==1]));
    } else {
        posA  = c(posA,NA);
    }
}

Maintenant regardons les défauts de cache au début de la simualtion et à la fin.

sum(head(miss,100))

## [1] 76

sum(tail(miss,100))

## [1] 64

On remarque que le nombre de défaut de cache est plus faible après que le cache est “appris”. Cependant le nombre de défaut reste élevé. Je pense que le cache serait meilleur si nous avions une distribution diférente des objets avec par exemple 10 objets récurrents et d’autres. On reviendras sur ce point à la question 4.

plot(posA)

On voit que notre A reste quasiment tout le temps en position 1 et quelque fois en position 2.

Calculons le taux de défaut de cache

err = sd(miss)/sqrt(length(miss));
mean(miss)-2*err;

## [1] 0.7008748

mean(miss)+2*err;

## [1] 0.7571252

Ce n’est pas fou comme estimation , passons à la question 2 et modélisons cela par une chaine de MArvov

Question 2

Modélisation de la chaine de markov associé au cache Move-ahead

options(width=160)
M=matrix(rep(0,(K+1)*(K+1)),nrow=K+1)
for(i in 1:K){
  M[i,i]=(K-2)*b;
  M[i,i+1]=b;
  M[i+1,i]=a
}
M[1,1]=a+(K-2)*b;
M[K+1,K+1]=1-a;
options(digits=3);

A partir de là je ne sais pas trop ce que je peux déduire de ma matrice, sachant que je ne suis même pas sur de sa justesse.

Question 3

Maintenant réécrivons nos caches sous formes de fonctions. (Le cache LRU est issus de votre cours.)

X=1 #Nb objet particuliers

moveAhead <- function(N,K,T){
  
  set.seed(42)
  acces = sample(1:N,T,replace=T,prob=c(rep(a,X),rep(b,N-X)))
  
 
  
  cache=(1:K);     # cache avec les vingts premiers éléments à l'originE
  miss=c();        # pour compter les défauts de caches
  missA=c();       # pour compter les défauts de caches de A
  posA=c();        # position de l'objet A
  for(v in acces) {
      if(v %in% cache) {
          where = (1:K)[cache==v];
          if(where!=1) {
              tmp=cache[where-1];
              cache[where-1]=cache[where]; #j'avance la valeur dans le cache d'une case
              cache[where]=tmp;
          }
          miss=c(miss,0);
      } else {
          cache[K]=v;
          miss=c(miss,1);  
      }
  }
  
  
  return(sum(miss))
}

lru <- function(N,K,T){
  
  set.seed(42)
  acces = sample(1:N,T,replace=T,prob=c(rep(a,X),rep(b,N-X)))
  
 
  
  cache=(1:K);     # cache avec les vingts premiers éléments à l'origine.
  miss=c();        # pour compter les défauts de caches
  missA=c();       # pour compter les défauts de caches de A
  posA=c();        # position de l'objet A
  for(v in acces) {
      if(v %in% cache) {
          where = (1:K)[cache==v];
        if(where!=1) {
            if(where==K) {
                cache = c(v,cache[1:(where-1)]); # attention, les () sont obligatoires dans les ranges (":").
            } else {
                cache = c(v,cache[1:(where-1)],cache[(where+1):(length(cache))]);
            }
        }
        miss=c(miss,0);
    } else {
        cache = c(v,cache[1:(length(cache)-1)]);
        miss=c(miss,1);  
        if(v==1) {
            missA=c(missA,1);
        } else {
            missA=c(missA,0);
        }
    }
    if(1 %in% cache) {
        posA  = c(posA,((1:K)[!is.na(cache) & cache==1]));
    } else {
        posA  = c(posA,NA);
    }
  }
  
  return(sum(miss))
}

Maintenant comparons les défauts de cache de nos deux caches en fonction de la taille du cache avec 100 objets pour 1000 tentative, puis pour 10000.

kvec = c(1:10)*10;

moveAheadResult = c()
lruResult = c()

moveAheadResultLarge = c()
lruResultLarge = c()

for(k in kvec ){
   moveAheadResult= c(moveAheadResult, moveAhead(100, k, 1000 ))
   moveAheadResultLarge= c(moveAheadResultLarge, moveAhead(100, k, 10000 ))
   lruResult= c(lruResult, lru(100, k, 1000 ))
   lruResultLarge= c(lruResultLarge, lru(100, k, 10000 ))
}
 
plot(kvec, moveAheadResult, type="l")
lines(kvec, lruResult, col = "blue")
lines(kvec, moveAheadResult, col = "red")

plot(kvec, lruResultLarge, type="l")
lines(kvec, lruResultLarge, col = "blue")
lines(kvec, moveAheadResultLarge, col = "red")

Pour l’instant rien de transcendant. On va maintenant interragir sur le nombre d’élement, on choisit un cache de taille 50.

nvec = c(1:10)*100;

moveAheadResult = c()
lruResult = c()

moveAheadResultLarge = c()
lruResultLarge = c()

for(n in nvec ){
   moveAheadResult= c(moveAheadResult, moveAhead(n, 50, 1000 ))
   moveAheadResultLarge= c(moveAheadResultLarge, moveAhead(n, 50, 10000 ))
   lruResult= c(lruResult, lru(n, 50, 1000 ))
   lruResultLarge= c(lruResultLarge, lru(n, 50, 10000 ))
}
 
plot(kvec, moveAheadResult, type="l")
lines(kvec, lruResult, col = "blue")
lines(kvec, moveAheadResult, col = "red")

plot(kvec, lruResultLarge, type="l")
lines(kvec, lruResultLarge, col = "blue")
lines(kvec, moveAheadResultLarge, col = "red")

La encore, on s’apercoit que les différences sont minimes. Cela s’explique par la simulation qui laisse peu de place à l’émergence d’une “qualité de cache”. Comme on a qu’un seul élément de valeurs, qu’on le ramène en tete ou qu’on le fasse remonter au fur et à mesure, l’élément sera quasiment toujours en tête du cache

Bonus question 3

Simulation avec un environment différents. 20 objets -> la moitié des demandes.

X=20
a = 0.04
b = (1-a*X)/(N-X)

kvec = c(1:10)*10;

moveAheadResult = c()
lruResult = c()

moveAheadResultLarge = c()
lruResultLarge = c()

for(k in kvec ){
   moveAheadResult= c(moveAheadResult, moveAhead(100, k, 1000 ))
   moveAheadResultLarge= c(moveAheadResultLarge, moveAhead(100, k, 10000 ))
   lruResult= c(lruResult, lru(100, k, 1000 ))
   lruResultLarge= c(lruResultLarge, lru(100, k, 10000 ))
}
 
plot(kvec, moveAheadResult, type="l")
lines(kvec, lruResult, col = "blue")
lines(kvec, moveAheadResult, col = "red")

plot(kvec, lruResultLarge, type="l")
lines(kvec, lruResultLarge, col = "blue")
lines(kvec, moveAheadResultLarge, col = "red")

Ici on s’aperçoit que le cache Move-Ahead commence à devenir meilleur que le cache LRU. ### Question 4

Définissons la fonction de puissance de la façon suivante :

  lambda = 0.5
  pvec = c()
  pi = lambda
  for (i in 1:N ){
    pvec = c(pvec,pi)
    pi = pi*lambda 
  }

  
  sum(pvec)

## [1] 1

On constate que l’on obtient 1 en sommant de P(1) à P(N) donc on a une distribution de probabilité d’objet cohérente. (En réalité la somme ne fait pas 1 mais est trop proche pour que R s’en rende compte).

On génere la nouvelle séquence d’accès

  N=100;
  K=5;

  acces = sample(1:N,T,replace=T,prob=pvec)

  cache=(1:K);     
  miss=c();        # pour compter les défauts de caches
  missA=c();       # pour compter les défauts de caches de A
  posA=c();        # position de l'objet A
  for(v in acces) {
      if(v %in% cache) {
          where = (1:K)[cache==v];
          if(where!=1) {
              tmp=cache[where-1];
              cache[where-1]=cache[where]; #j'avance la valeur dans le cache d'une case
              cache[where]=tmp;
              
          }
          miss=c(miss,0);
      } else {
          cache[K]=v;
          miss=c(miss,1);  
          if(v==1) {
              missA=c(missA,1);
          } else {
              missA=c(missA,0);
          }
      }
      if(1 %in% cache) {
          posA  = c(posA,((1:K)[!is.na(cache) & cache==1]));
      } else {
          posA  = c(posA,NA);
      }
  }
  
  sum(miss)

## [1] 43

Dans la simulation présente avec un cache de seulement 5 cases, on obtient de bien meilleurs résultats qu’avec un cache move ahead de 100 cases dans la situation initiale.