Embed Size (px)
Citation preview
Influência dos Parâmetros de Controle no Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Desempenho de Algoritmos Adaptativos de
Substituição de PáginasSubstituição de Páginas
Edson Toshimi MidorikawaRicardo Leandro PiantolaHugo Henrique Cassettari
EPUSP - Escola Politécnica da Universidade de São PauloPCS - 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
Problema da Substituição: Qual
página deve ser retirada da memória
principal?
Algoritmo de Substituição 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
Memória Principal
Área de Swap (Disco)
Tradicionais: FIFO, MRU, LRU, LFU
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
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Algoritmo Parâmetro Descrição Resumida L Tamanho mínimo de uma seqüência para que possa abrigar um ponto de substituição. M Posição do ponto de substituição em potencial de uma seqüência (posição MRU-M). SEQ N Quantidade de páginas consideradas para se verificar a taxa de crescimento de uma seqüência. E Ponto referencial de substituição antecipada (early eviction point).
EELRU L Ponto referencial de substituição LRU (late eviction point)
LIRS Lhirs Número porcentual máximo de páginas HIRs residentes em relação ao tamanho da memória. C Tamanho da região protegida, sendo C+1 o tamanho mínimo de uma área de trabalho.
LRU-WAR L Tamanho da região seqüencial
Algoritmo LRU-WAR (Working Area Restriction)
• Utiliza LRU ou MRU-n
• Diferencia reuso imediato de localidade temporal
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
Tendência Original (LRU) Maior que L LRU MTendência Seqüencial Menor ou igual a L LRU MOperação Seqüencial Menor ou igual a L e estável MRU-n W+1
Tamanho da Área de Trabalho
ALGORITMO LRU-WAR
Estado de execução Critério de Substituição
Ponto de Substituição (Posição na Fila LRU)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Fila LRU M = 20
Região Protegida
L
Região Seqüencial Região LRU
c w
Traces utilizados nas análises
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
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
Gnuplot
• 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
GNUPLOT
7.000
9.000
11.000
13.000
15.000
17.000
19.000
21.000
23.000
500 1500 2500 3500 4500 5500 6500 7500Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
ÓTIMO
LRU
LRU-WAR
Grobner
• 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
GROBNER
0
10.000
20.000
30.000
40.000
50.000
60.000
70.000
80.000
10 15 20 25 30 35 40
Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
ÓTIMO
LRU
LRU-WAR
Sprite
• 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
SPRITE
7.000
8.000
9.000
10.000
11.000
12.000
13.000
1.000 2.000 3.000 4.000 5.000 6.000 7.000
Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
ÓTIMO
LRU
LRU-WAR
Gráficos de Desempenho (Gnuplot)
• 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
GNUPLOT - variação de C
7.000
9.000
11.000
13.000
15.000
17.000
19.000
21.000
23.000
500 1.500 2.500 3.500 4.500 5.500 6.500 7.500Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
C=1
C=5
C=9
C=13
C=35
Ótimo
LRU
GNUPLOT - variação do L
7.000
9.000
11.000
13.000
15.000
17.000
19.000
21.000
23.000
500 1500 2500 3500 4500 5500 6500 7500Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
L=25
L=50
L=100
L=200
L=400
ÓTIMO
LRU
Gráficos de Desempenho (Grobner)
• 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 LRU-WAR 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
GROBNER - variação do C
0
20.000
40.000
60.000
80.000
10 20 30 40 50 60 70Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
C=1
C=5
C=9
C=13
ÓTIMO
LRU
GROBNER - variação do L
0
20.000
40.000
60.000
80.000
10 20 30 40 50 60 70Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
L=2
L=5
L=50%
L=9
C=1 L=2
C=1 L=5
C=1 L=9
ÓTIMO
LRU
Gráficos de Desempenho (Sprite)
• 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
SPRITE - variação de C
7.000
9.000
11.000
13.000
15.000
1.000 2.000 3.000 4.000 5.000 6.000 7.000
Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
C=1
C=5
C=20
C=44
ÓTIMO
LRU
SPRITE - variação de L
7.000
9.000
11.000
13.000
1.000 2.000 3.000 4.000 5.000 6.000 7.000
Tamanho da memória
Nú
mer
o d
e fa
ltas
de
pág
ina
L=25
L=50
L=100
L=200
L=400
L=800
Ótimo
LRU
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 LRU-WAR 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 USPDepartamento de Engenharia de Computação e Sistemas DigitaisLaboratório de Arquitetura e Computação de Alto DesempenhoAv. Prof. Luciano Gualberto, travessa 3, 158, Cidade UniversitáriaCEP: 05508-900, São Paulo-SPhttp://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
IV WSO / 2007 – Influência dos Parâmetros de Controle no Desempenho de Algoritmos Adaptativos de Substituição de Páginas - EPUSP
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
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
![4 Algoritmos Adaptativos para Supress˜ao de Interferˆencia · Na literatura de algoritmos adaptativos [60,61,62,63], algoritmos do tipo gradiente estoc´astico (SG) s˜ao soluc¸˜oes](https://img.document.onl/doc/110x75/5fd003bd26e9d43a64097f93/4-algoritmos-adaptativos-para-supressoeao-de-interfer-na-literatura-de-algoritmos.jpg)
