Algoritmo de Substituição de Páginas 3P:
Acrescentando Adaptatividade ao Clock
Hugo Henrique Cassettari
Edson Toshimi Midorikawa
EPUSP - Escola Politécnica da Universidade de São Paulo
PCS - Departamento de Engenharia de Computação e Sistemas Digitais
Objetivo
Apresentar o 3P:
Um algoritmo adaptativo para substituição de páginas
plenamente online, que procura aliar a eficiência de
implementação do algoritmo Clock à eficiência de
substituição do algoritmo LRU-WAR
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Apresentação
• Algoritmos de substituição de páginas
- Algoritmos adaptativos
- Algoritmo LRU-WAR
- Soluções online
• Algoritmo 3P
- Esquema operacional
- Pontos de substituição
- Custo de implementação
- Avaliação de desempenho
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Memória Virtual com Paginação
Área de Swap (Disco)
Problema da
Substituição: Qual
página deve ser
retirada da memória
principal?
Memória
Principal
Algoritmo de
Substituição
de Páginas
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Algoritmos Adaptativos de Substituição
• Adaptam seu comportamento em uma execução
• Atuam de acordo com as características de acesso à
memória detectadas
• Exemplos:
- SEQ (1997)
- EELRU – Early Eviction LRU (1999)
- DEAR – DEtection-based Adaptive Replacement (1999)
- AFC – Application/File-level Characterization (2000)
- UBM – Unified Buffer Management (2000)
- LRFU – Least Recently/Frequently Used (2001)
- LIRS – Low Inter-reference Recency Set (2002)
- ARC – Adaptive Replacement Cache (2003)
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Algoritmo LRU-WAR (Working Area Restriction)
• “LRU com Confinamento da Área de Trabalho” (2004 – I WSO)
• Procura detectar padrões de acesso seqüenciais
- Muitas faltas de página e baixa reutilização
• Área de trabalho:
Posições onde páginas foram acessadas desde a última falta de página
Área de Trabalho (Working Area )
Página MRU
Página LRU
...
W
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Fila LRU representando a memória principal
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Algoritmo LRU-WAR (Working Area Restriction)
• Utiliza LRU ou MRU-n
• Diferencia reuso imediato de localidade temporal
Estado de execução
Tendência Original (LRU)
Tendência Seqüencial
Operação Seqüencial
ALGORITMO LRU-WAR
Tamanho da Área de
Critério de
Trabalho
Substituição
LRU
Maior que L
LRU
Menor ou igual a L
MRU-n
Menor ou igual a L e estável
Ponto de Substituição
(Posição na Fila LRU)
M
M
W+1
Região Protegida
L
Região Seqüencial
1
2
3
Fila LRU
4
5
6
7
8
Região LRU
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Soluções Online
• Algoritmo Clock, ou Algoritmo do Relógio (1969)
C
Ponteiro CLOCK
...
C
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Fila circular representando a memória principal
• Algumas variações:
- GClock – Generalized Clock (1978)
- WSClock (1981)
- Two-Handed Clock (1982)
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Propostas Adaptativas Online
• CAR – Clock with Adaptive Replacement (2004)
- Versão aproximada do algoritmo ARC, inspirado no 2Q
- Páginas recentemente reutilizadas são isoladas das demais
• CART – CAR with Temporal filtering (2004)
- Variação do algoritmo CAR
- Bit adicional para identificar páginas com reutilização constante
• Clock-Pro (2005)
- Versão aproximada do algoritmo LIRS
- Diferencia páginas “quentes” e “frias” através de bits adicionais
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Algoritmo 3P
• “3 Ponteiros” – 3 Pointers
• Inspirado nos algoritmos Clock (implementação) e
LRU-WAR (detecção de acessos seqüenciais)
C
A
0
Ponteiro CLOCK
ÁREA JOVEM = 7 posições
neste exemplo
Ponteiro ANTECIPADO
Ponteiro APAGADOR
A
1
2
3
4
5
0
6
7
8
9
C
...
10 11 12 13 14 15 16 17 18 19 20
Fila circular representando a memória principal
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Algoritmo 3P
• Utiliza três ponteiros que se movimentam em conjunto
- CLOCK: Ponteiro para substituição Clock (pseudo-LRU)
- ANTECIPADO: Ponteiro para substituição precoce (pseudo-MRU)
- APAGADOR: Ponteiro para apagar bits de acesso (filtro de
reuso imediato)
C
A
0
Ponteiro CLOCK
ÁREA JOVEM = 7 posições
neste exemplo
Ponteiro ANTECIPADO
Ponteiro APAGADOR
A
1
2
3
4
5
0
6
7
8
9
C
...
10 11 12 13 14 15 16 17 18 19 20
Fila circular representando a memória principal
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Algoritmo 3P
• “Área Jovem”
- Contém páginas recém-carregadas em período de teste de
reutilização (não necessariamente)
- Somente páginas não referenciadas em tal período podem ser
substituídas pelo ponteiro ANTECIPADO
C
A
0
Ponteiro CLOCK
ÁREA JOVEM = 7 posições
neste exemplo
Ponteiro ANTECIPADO
Ponteiro APAGADOR
A
1
2
3
4
5
0
6
7
8
9
C
...
10 11 12 13 14 15 16 17 18 19 20
Fila circular representando a memória principal
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Algoritmo 3P
• Três estados de execução, como o LRU-WAR
ALGORITMO 3P
Estado de execução
Condições
(A = ANTECIPADO, C = CLOCK,
Período de
Carência
Zerado
Diminui
Aumenta
PC = Período de Carência)
ABIT = 0 e ABIT_JOVEM = 1 e PC = 0
Fora de Operação Seqüencial e CBIT = 0
Fora de Operação Seqüencial e CBIT = 1
Operação Seqüencial
Tendência Seqüencial
Tendência Original (LRU)
C
A
0
Ponteiro CLOCK
Ponto de Substituição
(Ponteiro)
MRU-n
LRU
LRU
ANTECIPADO
CLOCK
CLOCK (após movimento)
ÁREA JOVEM = 7 posições
neste exemplo
Ponteiro ANTECIPADO
Ponteiro APAGADOR
A
1
Critério Teórico
de Substituição
2
3
4
5
0
6
7
8
9
C
...
10 11 12 13 14 15 16 17 18 19 20
Fila circular representando a memória principal
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Algoritmo 3P
• Custo de implementação extremamente baixo
- Complexidade computacional de substituição equivalente à do
Clock, variando de uma ordem O(1) a uma ordem O(n)
- Menor custo de implementação dentre todos os algoritmos
adaptativos para substituição de páginas conhecidos
C
A
0
Ponteiro CLOCK
ÁREA JOVEM = 7 posições
neste exemplo
Ponteiro ANTECIPADO
Ponteiro APAGADOR
A
1
2
3
4
5
0
6
7
8
9
C
...
10 11 12 13 14 15 16 17 18 19 20
Fila circular representando a memória principal
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Avaliação de Desempenho
• 1041 simulações realizadas com 16 programas
Arquivo
Espresso
GCC
Gnuplot
Grobner
GS
Lindsay
P2C
2_Pools
CPP
CS
GLI
Multi1
Multi2
Multi3
PS
Sprite
Tamanhos de
Memória
Simulados
10, 11, 12, ..., 73, 74, 75
10, 15, 20, ..., 445, 450, 455
100, 200, 300, ..., 7500, 7600, 7700
10, 11, 12, ..., 63, 64, 65
10, 15, 20, ..., 545, 550, 555
10, 15, 20, ..., 510, 515, 520
10, 15, 20, ..., 120, 125, 130
100, 200, 300, ..., 9700, 9800, 9900
50, 100, 150, ..., 1100, 1150, 1200
50, 100, 150, ..., 1300, 1350, 1400
50, 100, 150, ..., 2400, 2450, 2500
50, 100, 150, ..., 2500, 2550, 2600
100, 200, 300, ..., 5400, 5500, 5600
100, 200, 300, ..., 7200, 7300, 7400
50, 100, 150, ..., 2950, 3000, 3050
100, 200, 300, ..., 6800, 6900, 7000
Número
Intervalo
de
entre
Tamanhos Simulações
66
1
90
5
77
100
56
1
110
5
103
5
25
5
99
100
24
50
28
50
50
50
52
50
56
100
74
100
61
50
70
100
1041
Aumento percentual médio no número de faltas de
página em relação ao caso ótimo
LRU-WAR
3P
CART
CAR
Clock
66,88%
80,60%
114,98% 114,14% 102,99%
79,26%
82,13%
84,74%
86,00%
86,06%
0,47%
0,71%
60,87%
65,75%
65,72%
139,20% 139,34% 118,21% 108,06% 125,40%
55,75%
59,33%
66,21%
72,45%
66,15%
32,80%
32,80%
51,07%
45,02%
44,05%
148,63% 148,18% 136,32% 130,71% 136,50%
59,00%
58,81%
58,04%
57,95%
58,79%
12,27%
13,89%
7,05%
7,40%
15,40%
3,92%
10,44%
99,26%
98,64%
100,06%
6,72%
8,00%
26,94%
28,08%
35,12%
42,10%
17,91%
38,40%
38,12%
53,46%
34,79%
18,39%
19,94%
24,66%
37,55%
34,01%
22,62%
22,22%
27,53%
35,65%
1,54%
9,42%
22,96%
28,42%
33,20%
21,36%
25,13%
26,27%
23,68%
18,67%
44,55%
42,43%
58,84%
62,84%
65,79%
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Avaliação de Desempenho
• Melhores e piores resultados médios (algoritmos online)
Arquivo
Espresso
GCC
Gnuplot
Grobner
GS
Lindsay
P2C
2_Pools
CPP
CS
GLI
Multi1
Multi2
Multi3
PS
Sprite
Tamanhos de
Memória
Simulados
10, 11, 12, ..., 73, 74, 75
10, 15, 20, ..., 445, 450, 455
100, 200, 300, ..., 7500, 7600, 7700
10, 11, 12, ..., 63, 64, 65
10, 15, 20, ..., 545, 550, 555
10, 15, 20, ..., 510, 515, 520
10, 15, 20, ..., 120, 125, 130
100, 200, 300, ..., 9700, 9800, 9900
50, 100, 150, ..., 1100, 1150, 1200
50, 100, 150, ..., 1300, 1350, 1400
50, 100, 150, ..., 2400, 2450, 2500
50, 100, 150, ..., 2500, 2550, 2600
100, 200, 300, ..., 5400, 5500, 5600
100, 200, 300, ..., 7200, 7300, 7400
50, 100, 150, ..., 2950, 3000, 3050
100, 200, 300, ..., 6800, 6900, 7000
Número
Intervalo
de
entre
Tamanhos Simulações
66
1
90
5
77
100
56
1
110
5
103
5
25
5
99
100
24
50
28
50
50
50
52
50
56
100
74
100
61
50
70
100
1041
Aumento percentual médio no número de faltas de
página em relação ao caso ótimo
LRU-WAR
3P
CART
CAR
Clock
66,88%
80,60%
114,98% 114,14% 102,99%
79,26%
82,13%
84,74%
86,00%
86,06%
0,47%
0,71%
60,87%
65,75%
65,72%
108,06% 125,40%
139,34% 118,21%
139,20%
55,75%
59,33%
66,21%
72,45%
66,15%
32,80%
32,80%
51,07%
45,02%
44,05%
130,71% 136,50%
148,63% 148,18% 136,32%
59,00%
58,81%
58,04%
57,95%
58,79%
12,27%
13,89%
7,05%
7,40%
15,40%
3,92%
10,44%
99,26%
98,64%
100,06%
6,72%
8,00%
26,94%
28,08%
35,12%
42,10%
17,91%
38,40%
38,12%
53,46%
34,79%
18,39%
19,94%
24,66%
37,55%
34,01%
22,62%
22,22%
27,53%
35,65%
1,54%
9,42%
22,96%
28,42%
33,20%
21,36%
25,13%
26,27%
23,68%
18,67%
44,55%
42,43%
58,84%
62,84%
65,79%
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Avaliação de Desempenho
• Diferenças de desempenho mais significativas
Arquivo
Espresso
GCC
Gnuplot
Grobner
GS
Lindsay
P2C
2_Pools
CPP
CS
GLI
Multi1
Multi2
Multi3
PS
Sprite
Tamanhos de
Memória
Simulados
10, 11, 12, ..., 73, 74, 75
10, 15, 20, ..., 445, 450, 455
100, 200, 300, ..., 7500, 7600, 7700
10, 11, 12, ..., 63, 64, 65
10, 15, 20, ..., 545, 550, 555
10, 15, 20, ..., 510, 515, 520
10, 15, 20, ..., 120, 125, 130
100, 200, 300, ..., 9700, 9800, 9900
50, 100, 150, ..., 1100, 1150, 1200
50, 100, 150, ..., 1300, 1350, 1400
50, 100, 150, ..., 2400, 2450, 2500
50, 100, 150, ..., 2500, 2550, 2600
100, 200, 300, ..., 5400, 5500, 5600
100, 200, 300, ..., 7200, 7300, 7400
50, 100, 150, ..., 2950, 3000, 3050
100, 200, 300, ..., 6800, 6900, 7000
Número
Intervalo
de
entre
Tamanhos Simulações
66
1
90
5
77
100
56
1
110
5
103
5
25
5
99
100
24
50
28
50
50
50
52
50
56
100
74
100
61
50
70
100
1041
Aumento percentual médio no número de faltas de
página em relação ao caso ótimo
LRU-WAR
3P
CART
CAR
Clock
66,88%
80,60%
114,98% 114,14% 102,99%
79,26%
82,13%
84,74%
86,00%
86,06%
0,47%
0,71%
60,87%
65,75%
65,72%
108,06% 125,40%
139,34% 118,21%
139,20%
55,75%
59,33%
66,21%
72,45%
66,15%
32,80%
32,80%
51,07%
45,02%
44,05%
130,71% 136,50%
148,63% 148,18% 136,32%
59,00%
58,81%
58,04%
57,95%
58,79%
12,27%
13,89%
7,05%
7,40%
15,40%
3,92%
10,44%
99,26%
98,64%
100,06%
6,72%
8,00%
26,94%
28,08%
35,12%
42,10%
17,91%
38,40%
38,12%
53,46%
34,79%
18,39%
19,94%
24,66%
37,55%
34,01%
22,62%
22,22%
27,53%
35,65%
1,54%
9,42%
22,96%
28,42%
33,20%
21,36%
25,13%
26,27%
23,68%
18,67%
44,55%
42,43%
58,84%
62,84%
65,79%
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Gráficos de Desempenho (3P versus Clock)
• Melhor desempenho médio obtido com o 3P: CS
Diferenças Percentuais de Desempenho - CS
10,00%
Diferença % (faltas de página)
0,00%
-10,00%
-20,00%
-30,00%
-40,00%
-50,00%
-60,00%
Clock
-70,00%
3P
13
50
12
50
11
50
10
50
95
0
85
0
75
0
65
0
55
0
45
0
35
0
25
0
15
0
50
-80,00%
Tamanho da memória
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Gráficos de Desempenho (3P versus Clock)
• Melhor desempenho médio obtido com o 3P: CS
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Gráficos de Desempenho (3P versus Clock)
• Pior desempenho médio obtido com o 3P: Sprite
Diferenças Percentuais de Desempenho - SPRITE
25,00%
Diferença % (faltas de página)
Clock
3P
20,00%
15,00%
10,00%
5,00%
0,00%
13
00
16
00
19
00
22
00
25
00
28
00
31
00
34
00
37
00
40
00
43
00
46
00
49
00
52
00
55
00
58
00
61
00
64
00
67
00
70
00
-5,00%
Tamanho da memória
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Gráficos de Desempenho (3P versus Clock)
• Pior desempenho médio obtido com o 3P: Sprite
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Gráficos de Desempenho (3P versus Clock)
• Exemplo de caso médio: Grobner
Diferenças Percentuais de Desempenho - GROBNER
10,00%
Diferença % (faltas de página)
5,00%
0,00%
-5,00%
-10,00%
-15,00%
-20,00%
-25,00%
-30,00%
-35,00%
Clock
-40,00%
3P
44
42
40
38
36
34
32
30
28
26
24
22
20
-45,00%
Tamanho da memória
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Gráficos de Desempenho (3P versus Clock)
• Exemplo de caso médio: Grobner
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Resultados Importantes
• O desempenho do 3P foi igual ou superior ao do Clock
em 844 simulações (81,1% do total)
• O desempenho do 3P foi significativamente melhor que o
do Clock – acima de 10% – em 356 simulações (34,2%)
• O desempenho do 3P foi significativamente pior que o do
Clock – abaixo de 10% – em apenas 16 simulações (1,5%)
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Conclusão
• Algoritmo 3P
- Alternativa simples e viável
- Muito eficiente quando acessos seqüenciais predominam
- Picos negativos aceitáveis
- Custo de implementação extremamente baixo
• Trabalhos futuros
- Implementação prática do algoritmo em um sistema operacional
- Adaptação para outros tipos de memória cache
• Agradecimentos
- Scott Kaplan e Yannis Smaragdakis
- Song Jiang
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Contato
• Hugo Henrique Cassettari:
[email protected]
• Edson Toshimi Midorikawa: [email protected]
• ESCOLA POLITÉCNICA DA USP
Departamento de Engenharia de Computação e Sistemas Digitais
Laboratório de Arquitetura e Computação de Alto Desempenho
Av. Prof. Luciano Gualberto, travessa 3, 158, Cidade Universitária
CEP: 05508-900, São Paulo-SP
www.lasb.pcs.poli.usp.br
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP