Influência dos Parâmetros de Controle no
Desempenho de Algoritmos Adaptativos de
Substituição de Páginas
Edson Toshimi Midorikawa
Ricardo Leandro Piantola
Hugo Henrique Cassettari
EPUSP - Escola Politécnica da Universidade de São Paulo
PCS - Departamento de Engenharia de Computação e Sistemas Digitais
Objetivo
Apresentar um estudo do comportamento e do respectivo
desempenho de algoritmos adaptativos de substituição de
páginas, segundo a variação de seus parâmetros.
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Apresentação
- Algoritmos adaptativos
- Parâmetros de Controle
- Algoritmo LRU-WAR
- Descrição dosTraces
- Análises dos parâmetros C e L do LRU-WAR
- Conclusão e trabalhos futuros
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - 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
Tradicionais: FIFO, MRU, LRU, LFU
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Algoritmos Adaptativos de Substituição
• Atuam de forma dinâmica, adaptando seu comportamento
de acordo com o padrão de acesso à memória em tempo de
execução.
• Modificam seu comportamento de acordo com as
características de acesso à memória detectadas.
• Exemplos:
- SEQ (1997)
- EELRU – Early Eviction LRU (1999)
- LRFU – Least Recently/Frequently Used (2001)
- LIRS – Low Inter-reference Recency Set (2002)
- ARC – Adaptive Replacement Cache (2003)
- FPR – Fuzzy Page Replacement (2006)
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Parâmetros de controle
Algoritmo Parâmetro
L
SEQ
M
N
E
EELRU
L
LIRS
Lhirs
C
LRU-WAR
L
Descrição Resumida
Tamanho mínimo de uma seqüência para que possa abrigar um ponto de substituição.
Posição do ponto de substituição em potencial de uma seqüência (posição MRU-M).
Quantidade de páginas consideradas para se verificar a taxa de crescimento de uma seqüência.
Ponto referencial de substituição antecipada (early eviction point).
Ponto referencial de substituição LRU (late eviction point)
Número porcentual máximo de páginas HIRs residentes em relação ao tamanho da memória.
Tamanho da região protegida, sendo C+1 o tamanho mínimo de uma área de trabalho.
Tamanho da região seqüencial
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - 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
c
1
2
3
Fila LRU
4
5
Região LRU
w
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Traces utilizados nas análises
Trace
Descrição
Origem
Total de
páginas
gnuplot
Trace relativo à geração de um gráfico em postscript.
VMTrace
7718
grobner
Programa para reorganização de fórmulas baseado em funções base
de Grobner.
VMTrace
67
sprite
Proveniente do sistema de arquivos de rede Sprite. Contém
requisições a um servidor de arquivos a partir de várias estações de
trabalho cliente em um período de dois dias.
LIRS
7075
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Gnuplot
GNUPLOT
Número de faltas de página
23.000
21.000
19.000
17.000
15.000
ÓTIMO
13.000
LRU
11.000
LRU-WAR
9.000
7.000
500
1500
2500
3500
4500
5500
Tamanho da memória
6500
7500
• Padrões de acessos bem definidos:
- Um conjunto de páginas com forte localidade temporal.
- Um padrão de acessos seqüencial.
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Grobner
GROBNER
80.000
ÓTIMO
Número de faltas de página
70.000
LRU
60.000
LRU-WAR
50.000
40.000
30.000
20.000
10.000
0
10
15
20
25
30
35
Tamanho da memória
• Padrão seqüencial intercalado com outros padrões de
acesso à memória.
• Acessos a poucas páginas com forte localidade temporal.
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
40
Sprite
SPRITE
13.000
Número de faltas de página
ÓTIMO
12.000
LRU
LRU-WAR
11.000
10.000
9.000
8.000
7.000
1.000
2.000
3.000
4.000
5.000
6.000
7.000
Tamanho da memória
• Grande conjunto de páginas que são acessadas com uma
certa freqüência.
• Não apresenta um padrão destacado.
• Intervalos irregulares, baixa localidade temporal.
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Gráficos de Desempenho (Gnuplot)
GNUPLOT - variação do L
23.000
23.000
21.000
21.000
Número de faltas de página
Número de faltas de página
GNUPLOT - variação de C
19.000
17.000
C=1
15.000
C=5
C=9
13.000
11.000
9.000
7.000
500
C=13
C=35
Ótimo
17.000
L=25
15.000
L=50
L=100
13.000
L=200
11.000
L=400
ÓTIMO
9.000
LRU
1.500
19.000
2.500
3.500
4.500
5.500
Tamanho da memória
6.500
7.500
7.000
500
LRU
1500
2500
3500
4500
5500
Tamanho da memória
6500
7500
• As variações do L não apresentaram desempenho significativo.
• Para valores de C maiores que 50 LRU-WAR se iguala ao LRU.
• Aproximação do Ótimo quando C=35 (23 faltas de páginas).
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Gráficos de Desempenho (Grobner)
GROBNER - variação do C
80.000
GROBNER - variação do L
80.000
60.000
Número de faltas de página
Número de faltas de página
L=2
C=1
C=5
C=9
C=13
ÓTIMO
40.000
LRU
20.000
L=5
60.000
L=50%
L=9
C=1 L=2
40.000
C=1 L=5
C=1 L=9
ÓTIMO
20.000
LRU
0
0
10
20
30
40
50
Tamanho da memória
60
70
10
20
30
40
50
Tamanho da memória
60
70
• Quanto menor o valor de C, mais rápido é detectada o padrão
seqüencial.
• Ganhos de até 24% em relação ao LRU e 15% em relação ao LRUWAR com parâmetros padrão.
• Valores baixos de L não apresentam melhora.
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Gráficos de Desempenho (Sprite)
SPRITE - variação de C
SPRITE - variação de L
13.000
15.000
L=25
C=5
13.000
C=20
C=44
ÓTIMO
11.000
LRU
9.000
7.000
1.000
2.000
3.000
4.000
5.000
Tamanho da memória
6.000
7.000
Número de faltas de página
Número de faltas de página
C=1
L=50
L=100
11.000
L=200
L=400
L=800
Ótimo
9.000
7.000
1.000
LRU
2.000
3.000
4.000
5.000
Tamanho da memória
6.000
7.000
• O valor ótimo de C para esse trace é 44.
• Quanto maior o valor de C, LRU-WAR mais próximo do LRU
• Quanto maior o valor de L melhor é o desempenho, porém não é
possível se aproximar do LRU.
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Conclusão
• Influência dos Parâmetros de Controle
-É possível modificar o comportamento dos algoritmos adaptativos
de substituição de páginas para situações específicas
- Ajustar os parâmetros em execução pode melhorar
significativamente o desempenho
- Melhoria de até 15% em relação aos parâmetros padrão LRU-WAR
- O algoritmo LRU-WAR com parâmetros padrão tem bom
desempenho. Porém o desempenho pode melhorar ajustando-se os
parâmetros de controle
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Trabalhos futuros
- Conduzir este mesmo estudo para um conjunto maior de aplicações
- Desenvolver um algoritmo dinâmico de ajuste dos parâmetros de
controle em execução
- Analisar a influência dos parâmetros de controle usando o LRUWAR com uma política de substituição global
- Estudo comparativo com outros algoritmos adaptativos
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Contato
• Edson Toshimi Midorikawa: [email protected]
• Ricardo Leandro Piantola:
[email protected]
• Hugo Henrique Cassettari: [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
http://regulus.pcs.usp.br/~lahpc/
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Gnuplot
GNUPLOT
Tamanho Memória
Número de Faltas de Página (NPF)
C=1
C=5
C=9
C=13
Ótimo
LRU
500
22195
22216
22241
22265
22151
23139
1000
21195
21216
21241
21265
21151
23139
1500
20195
20216
20241
20265
20151
23139
2000
19195
19216
19241
19265
19151
23139
2500
18195
18216
18241
18265
18151
23139
3000
17195
17216
17241
17265
17151
23139
3500
16195
16216
16241
16265
16151
23139
4000
15195
15216
15241
15265
15151
23139
4500
14195
14216
14241
14265
14151
23139
5000
13195
13216
13241
13265
13151
23139
5500
12195
12216
12241
12265
12151
23139
6000
11195
11216
11241
11265
11151
23139
6500
10195
10216
10241
10265
10151
23139
7000
9195
9216
9241
9265
9151
23139
7500
8195
8216
8241
8265
8151
23139
8000
7718
7718
7718
7718
7718
7718
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Grobner
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Sprite
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP