Éval de perf, TD4: Analyse du comportement d’un cache à l'aide de chaînes de Markov

Illustration de l'utilisation du package markovchain

library(markovchain)
weatherStates <- c("sunny", "cloudy", "rain")
byRow <- TRUE
weatherMatrix <- matrix(data = c(0.7, 0.2, 0.1, 0.3, 0.4, 0.3, 0.2, 0.45, 0.35), 
    byrow = byRow, nrow = 3, dimnames = list(weatherStates, weatherStates))
mcWeather <- new("markovchain", states = weatherStates, byrow = byRow, transitionMatrix = weatherMatrix, 
    name = "Weather")
show(mcWeather)
## Weather 
##  A  3 - dimensional discrete Markov Chain with following states 
##  sunny cloudy rain 
##  The transition matrix   (by rows)  is defined as follows 
##        sunny cloudy rain
## sunny    0.7   0.20 0.10
## cloudy   0.3   0.40 0.30
## rain     0.2   0.45 0.35
initialState <- c(0, 1, 0)
after2Days <- initialState * (mcWeather * mcWeather)
after7Days <- initialState * (mcWeather^7)
after2Days
##      sunny cloudy  rain
## [1,]  0.39  0.355 0.255
library(igraph)
mcIgraph <- as(mcWeather, "igraph")
plot(mcIgraph)

plot of chunk unnamed-chunk-3

steadyStates(mcWeather)
##       sunny cloudy   rain
## [1,] 0.4636 0.3182 0.2182

Politique Move-to-front

Commençons par définir notre chaîne de Markov.

N = 8
a = 0.3
b = (1 - a)/(N - 1)

trans = seq(from = 0, to = 0, length.out = N * N)

trans[1] = a
for (i in 2:N) {
    trans[i + N * (i - 1)] = (i - 1) * b
    trans[1 + N * (i - 1)] = a
    trans[i + N * (i - 2)] = (N - i + 1) * b
}

States <- as.character(1:N)
byRow <- TRUE
MTFMatrix <- matrix(data = trans, byrow = byRow, nrow = N, dimnames = list(States, 
    States))
mcMTF <- new("markovchain", states = States, byrow = byRow, transitionMatrix = MTFMatrix, 
    name = "Move to front")
show(mcMTF)
## Move to front 
##  A  8 - dimensional discrete Markov Chain with following states 
##  1 2 3 4 5 6 7 8 
##  The transition matrix   (by rows)  is defined as follows 
##     1   2   3   4   5   6   7   8
## 1 0.3 0.7 0.0 0.0 0.0 0.0 0.0 0.0
## 2 0.3 0.1 0.6 0.0 0.0 0.0 0.0 0.0
## 3 0.3 0.0 0.2 0.5 0.0 0.0 0.0 0.0
## 4 0.3 0.0 0.0 0.3 0.4 0.0 0.0 0.0
## 5 0.3 0.0 0.0 0.0 0.4 0.3 0.0 0.0
## 6 0.3 0.0 0.0 0.0 0.0 0.5 0.2 0.0
## 7 0.3 0.0 0.0 0.0 0.0 0.0 0.6 0.1
## 8 0.3 0.0 0.0 0.0 0.0 0.0 0.0 0.7

À quoi cette chaîne ressemble-t-elle ?

mcIgraph <- as(mcMTF, "igraph")
plot(mcMTF)
## Loading required package: Matrix

plot of chunk unnamed-chunk-6

Et le régime permanent ?

ssMTF = steadyStates(mcMTF)
ssMTF
##        1      2     3     4       5    6     7        8
## [1,] 0.3 0.2333 0.175 0.125 0.08333 0.05 0.025 0.008333

Politique Move-ahead

Commençons par définir notre chaîne de Markov.

trans = seq(from = 0, to = 0, length.out = N * N)

trans[1] = a + (N - 2) * b
for (i in 2:N) {
    trans[i + N * (i - 1)] = (N - 2) * b
    trans[i - 1 + N * (i - 1)] = a
    trans[i + N * (i - 2)] = b
}
trans[N * N] = (N - 1) * b

States <- as.character(1:N)
byRow <- TRUE
MAMatrix <- matrix(data = trans, byrow = byRow, nrow = N, dimnames = list(States, 
    States))
mcMA <- new("markovchain", states = States, byrow = byRow, transitionMatrix = MAMatrix, 
    name = "Move Ahead")
show(mcMA)
## Move Ahead 
##  A  8 - dimensional discrete Markov Chain with following states 
##  1 2 3 4 5 6 7 8 
##  The transition matrix   (by rows)  is defined as follows 
##     1   2   3   4   5   6   7   8
## 1 0.9 0.1 0.0 0.0 0.0 0.0 0.0 0.0
## 2 0.3 0.6 0.1 0.0 0.0 0.0 0.0 0.0
## 3 0.0 0.3 0.6 0.1 0.0 0.0 0.0 0.0
## 4 0.0 0.0 0.3 0.6 0.1 0.0 0.0 0.0
## 5 0.0 0.0 0.0 0.3 0.6 0.1 0.0 0.0
## 6 0.0 0.0 0.0 0.0 0.3 0.6 0.1 0.0
## 7 0.0 0.0 0.0 0.0 0.0 0.3 0.6 0.1
## 8 0.0 0.0 0.0 0.0 0.0 0.0 0.3 0.7

À quoi cette chaîne ressemble-t-elle ?

mcIgraph <- as(mcMA, "igraph")
plot(mcMA)

plot of chunk unnamed-chunk-9

Et le régime permanent ?

ssMA = steadyStates(mcMA)
ssMA
##           1      2       3      4        5        6         7         8
## [1,] 0.6668 0.2223 0.07409 0.0247 0.008232 0.002744 0.0009146 0.0003049

Comparaison des deux stratégies

Pour chacune des deux stratégies, la probabilité d'avoir un défaut de page de la page \( A \) quand le cache peut contenir \( M \) pages s'écrit \( p(M)=\sum_{i>M} \pi_i \).

Donc pour MTF on a:

1 - cumsum(ssMTF)
## [1] 0.700000 0.466667 0.291667 0.166667 0.083333 0.033333 0.008333 0.000000

Et pour MA, on a:

1 - cumsum(ssMA)
## [1] 0.3332317 0.1109756 0.0368902 0.0121951 0.0039634 0.0012195 0.0003049
## [8] 0.0000000

La probabilité d'avoir un défaut de la page A est donc bien plus faible avec MA qu'avec MTF, quelle que soit la taille du cache.

Mais ce qui nous intéresse, c'est la probabilité de défaut de cache d'une page quelconque.

Après un peu de travail, on peut montrer que \( p_g(M) = 1-Mb-(a-b)\sum_{i=1}^M \pi_i \)

Donc pour MTF on a:

1 - (1:N) * b - (a - b) * cumsum(ssMTF)
## [1] 8.400e-01 6.933e-01 5.583e-01 4.333e-01 3.167e-01 2.067e-01 1.017e-01
## [8] 5.551e-17

Et pour MA, on a:

1 - (1:N) * b - (a - b) * cumsum(ssMA)
## [1] 7.666e-01 6.222e-01 5.074e-01 4.024e-01 3.008e-01 2.002e-01 1.001e-01
## [8] 5.551e-17

Une fois encore, les probabilités de défaut de pages sont plus faibles pour MA que pour MTF. D'autre part, la probabilité d'avoir un défaut de cache ne diminue pas très rapidement avec la taille du cache.

Ceci dit, on a un modèle franchement naïf. Il serait probablement plus intéressant de considérer qu'on a plusieurs pages populaires comme la page A, et éventuellement que la popularité de ces pages est décroissante.

D'autre part, cette analyse se base sur la stationnarité et donc sur le fait que l'on a bien convergé vers l'état stationnaire. Le temps de convergence est lié à la valeur de la seconde plus grande valeur propre. Pour MTF, on a:

eigen(mcMTF@transitionMatrix, only.values = T)$values
## [1] 1.000e+00 6.000e-01 5.000e-01 4.000e-01 3.000e-01 2.000e-01 1.000e-01
## [8] 1.805e-15
eigen(mcMA@transitionMatrix, only.values = T)$values
## [1] 1.0000 0.9200 0.8449 0.7326 0.6000 0.4674 0.3551 0.2800

Donc avec MTF, le temps de convergence vers l'état stationnaire est en \( 0.6^n \) alors qu'avec MA, le temps de convergence vers l'état stationnaire est en \( 0.92^n \), soit bien plus lentement. Moralité, si MA est plus efficace du point de vue des défauts de cache, il est moins clair qu'il ait le temps d'atteindre le régime permanent. Si les fréquences d'accès au page ne sont pas assez stables dans le temps, il n'est donc pas si clair que MA soit plus efficace que MTF…