Upload
internet
View
108
Download
2
Embed Size (px)
Citation preview
Algoritmo de Substituição de Páginas Algoritmo de Substituição de Páginas 3P3P::Acrescentando Adaptatividade ao ClockAcrescentando Adaptatividade ao Clock
Hugo Henrique CassettariEdson Toshimi Midorikawa
EPUSP - Escola Politécnica da Universidade de São PauloPCS - 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
Problema da Substituição: Qual
página deve ser retirada da 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
Memória Principal
Área de Swap (Disco)
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:
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Posições onde páginas foram acessadas desde a última falta de página
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
Área de Trabalho (Working Area )
Página MRU Página LRU
...
Algoritmo LRU-WAR (Working Area Restriction)
• Utiliza LRU ou MRU-n
• Diferencia reuso imediato de localidade temporal
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - 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
Soluções Online
• Algoritmo Clock, ou Algoritmo do Relógio (1969)
• 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
C Ponteiro CLOCK
C1 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
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)
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
C Ponteiro CLOCK ÁREA JOVEM = 7 posições
A Ponteiro ANTECIPADO
0 Ponteiro APAGADOR
A 0 C1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
neste exemplo
...
Fila circular representando a memória principal
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)
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
C Ponteiro CLOCK ÁREA JOVEM = 7 posições
A Ponteiro ANTECIPADO
0 Ponteiro APAGADOR
A 0 C1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
neste exemplo
...
Fila circular representando a memória principal
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
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
C Ponteiro CLOCK ÁREA JOVEM = 7 posições
A Ponteiro ANTECIPADO
0 Ponteiro APAGADOR
A 0 C1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
neste exemplo
...
Fila circular representando a memória principal
Algoritmo 3P
• Três estados de execução, como o LRU-WAR
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
C Ponteiro CLOCK ÁREA JOVEM = 7 posições
A Ponteiro ANTECIPADO
0 Ponteiro APAGADOR
A 0 C1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
neste exemplo
...
Fila circular representando a memória principal
Operação Seqüencial Zerado MRU-n ANTECIPADOTendência Seqüencial Diminui LRU CLOCK
Tendência Original (LRU) Aumenta LRU CLOCK (após movimento)Fora de Operação Seqüencial e C BIT = 1
A BIT = 0 e A BIT_JOVEM = 1 e PC = 0Fora de Operação Seqüencial e C BIT = 0
ALGORITMO 3P
Estado de execução Condições(A = ANTECIPADO, C = CLOCK,
PC = Período de Carência)Período de Carência
Critério Teórico de Substituição
Ponto de Substituição (Ponteiro)
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
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
C Ponteiro CLOCK ÁREA JOVEM = 7 posições
A Ponteiro ANTECIPADO
0 Ponteiro APAGADOR
A 0 C1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
neste exemplo
...
Fila circular representando a memória principal
Avaliação de Desempenho
• 1041 simulações realizadas com 16 programas
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Clock CAR CART 3P LRU-WAREspresso 10, 11, 12, ..., 73, 74, 75 1 66 114,98% 114,14% 102,99% 80,60% 66,88%GCC 10, 15, 20, ..., 445, 450, 455 5 90 86,06% 86,00% 84,74% 82,13% 79,26%Gnuplot 100, 200, 300, ..., 7500, 7600, 7700 100 77 65,72% 65,75% 60,87% 0,71% 0,47%Grobner 10, 11, 12, ..., 63, 64, 65 1 56 139,20% 139,34% 118,21% 108,06% 125,40%
GS 10, 15, 20, ..., 545, 550, 555 5 110 66,15% 72,45% 66,21% 59,33% 55,75%Lindsay 10, 15, 20, ..., 510, 515, 520 5 103 44,05% 45,02% 51,07% 32,80% 32,80%P2C 10, 15, 20, ..., 120, 125, 130 5 25 148,63% 148,18% 136,32% 130,71% 136,50%
2_Pools 100, 200, 300, ..., 9700, 9800, 9900 100 99 58,79% 57,95% 58,04% 58,81% 59,00%CPP 50, 100, 150, ..., 1100, 1150, 1200 50 24 15,40% 7,40% 7,05% 13,89% 12,27%CS 50, 100, 150, ..., 1300, 1350, 1400 50 28 100,06% 98,64% 99,26% 10,44% 3,92%GLI 50, 100, 150, ..., 2400, 2450, 2500 50 50 35,12% 28,08% 26,94% 8,00% 6,72%Multi1 50, 100, 150, ..., 2500, 2550, 2600 50 52 53,46% 38,12% 38,40% 17,91% 42,10%Multi2 100, 200, 300, ..., 5400, 5500, 5600 100 56 37,55% 24,66% 19,94% 18,39% 34,79%
Multi3 100, 200, 300, ..., 7200, 7300, 7400 100 74 35,65% 27,53% 22,22% 22,62% 34,01%PS 50, 100, 150, ..., 2950, 3000, 3050 50 61 33,20% 28,42% 22,96% 9,42% 1,54%Sprite 100, 200, 300, ..., 6800, 6900, 7000 100 70 18,67% 23,68% 26,27% 25,13% 21,36%
1041 65,79% 62,84% 58,84% 42,43% 44,55%
ArquivoTamanhos de
Memória Simulados
Aumento percentual médio no número de faltas de página em relação ao caso ótimo
Intervalo entre
Tamanhos
Número de
Simulações
Avaliação de Desempenho
• Melhores e piores resultados médios (algoritmos online)
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Clock CAR CART 3P LRU-WAREspresso 10, 11, 12, ..., 73, 74, 75 1 66 114,98% 114,14% 102,99% 80,60% 66,88%
GCC 10, 15, 20, ..., 445, 450, 455 5 90 86,06% 86,00% 84,74% 82,13% 79,26%Gnuplot 100, 200, 300, ..., 7500, 7600, 7700 100 77 65,72% 65,75% 60,87% 0,71% 0,47%Grobner 10, 11, 12, ..., 63, 64, 65 1 56 139,20% 139,34% 118,21% 108,06% 125,40%GS 10, 15, 20, ..., 545, 550, 555 5 110 66,15% 72,45% 66,21% 59,33% 55,75%Lindsay 10, 15, 20, ..., 510, 515, 520 5 103 44,05% 45,02% 51,07% 32,80% 32,80%P2C 10, 15, 20, ..., 120, 125, 130 5 25 148,63% 148,18% 136,32% 130,71% 136,50%
2_Pools 100, 200, 300, ..., 9700, 9800, 9900 100 99 58,79% 57,95% 58,04% 58,81% 59,00%CPP 50, 100, 150, ..., 1100, 1150, 1200 50 24 15,40% 7,40% 7,05% 13,89% 12,27%CS 50, 100, 150, ..., 1300, 1350, 1400 50 28 100,06% 98,64% 99,26% 10,44% 3,92%GLI 50, 100, 150, ..., 2400, 2450, 2500 50 50 35,12% 28,08% 26,94% 8,00% 6,72%Multi1 50, 100, 150, ..., 2500, 2550, 2600 50 52 53,46% 38,12% 38,40% 17,91% 42,10%
Multi2 100, 200, 300, ..., 5400, 5500, 5600 100 56 37,55% 24,66% 19,94% 18,39% 34,79%Multi3 100, 200, 300, ..., 7200, 7300, 7400 100 74 35,65% 27,53% 22,22% 22,62% 34,01%PS 50, 100, 150, ..., 2950, 3000, 3050 50 61 33,20% 28,42% 22,96% 9,42% 1,54%Sprite 100, 200, 300, ..., 6800, 6900, 7000 100 70 18,67% 23,68% 26,27% 25,13% 21,36%
1041 65,79% 62,84% 58,84% 42,43% 44,55%
ArquivoTamanhos de
Memória Simulados
Intervalo entre
Tamanhos
Número de
Simulações
Aumento percentual médio no número de faltas de página em relação ao caso ótimo
Avaliação de Desempenho
• Diferenças de desempenho mais significativas
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Clock CAR CART 3P LRU-WAREspresso 10, 11, 12, ..., 73, 74, 75 1 66 114,98% 114,14% 102,99% 80,60% 66,88%GCC 10, 15, 20, ..., 445, 450, 455 5 90 86,06% 86,00% 84,74% 82,13% 79,26%Gnuplot 100, 200, 300, ..., 7500, 7600, 7700 100 77 65,72% 65,75% 60,87% 0,71% 0,47%Grobner 10, 11, 12, ..., 63, 64, 65 1 56 139,20% 139,34% 118,21% 108,06% 125,40%GS 10, 15, 20, ..., 545, 550, 555 5 110 66,15% 72,45% 66,21% 59,33% 55,75%Lindsay 10, 15, 20, ..., 510, 515, 520 5 103 44,05% 45,02% 51,07% 32,80% 32,80%P2C 10, 15, 20, ..., 120, 125, 130 5 25 148,63% 148,18% 136,32% 130,71% 136,50%
2_Pools 100, 200, 300, ..., 9700, 9800, 9900 100 99 58,79% 57,95% 58,04% 58,81% 59,00%CPP 50, 100, 150, ..., 1100, 1150, 1200 50 24 15,40% 7,40% 7,05% 13,89% 12,27%CS 50, 100, 150, ..., 1300, 1350, 1400 50 28 100,06% 98,64% 99,26% 10,44% 3,92%GLI 50, 100, 150, ..., 2400, 2450, 2500 50 50 35,12% 28,08% 26,94% 8,00% 6,72%Multi1 50, 100, 150, ..., 2500, 2550, 2600 50 52 53,46% 38,12% 38,40% 17,91% 42,10%Multi2 100, 200, 300, ..., 5400, 5500, 5600 100 56 37,55% 24,66% 19,94% 18,39% 34,79%Multi3 100, 200, 300, ..., 7200, 7300, 7400 100 74 35,65% 27,53% 22,22% 22,62% 34,01%PS 50, 100, 150, ..., 2950, 3000, 3050 50 61 33,20% 28,42% 22,96% 9,42% 1,54%Sprite 100, 200, 300, ..., 6800, 6900, 7000 100 70 18,67% 23,68% 26,27% 25,13% 21,36%
1041 65,79% 62,84% 58,84% 42,43% 44,55%
ArquivoTamanhos de
Memória Simulados
Intervalo entre
Tamanhos
Número de
Simulações
Aumento percentual médio no número de faltas de página em relação ao caso ótimo
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
Diferenças Percentuais de Desempenho - CS
-80,00%
-70,00%
-60,00%
-50,00%
-40,00%
-30,00%
-20,00%
-10,00%
0,00%
10,00%
50 150
250
350
450
550
650
750
850
950
1050
1150
1250
1350
Tamanho da memória
Dif
eren
ça %
(fa
ltas
de
pág
ina)
Clock
3P
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
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Diferenças Percentuais de Desempenho - SPRITE
-5,00%
0,00%
5,00%
10,00%
15,00%
20,00%
25,00%
1300
1600
1900
2200
2500
2800
3100
3400
3700
4000
4300
4600
4900
5200
5500
5800
6100
6400
6700
7000
Tamanho da memória
Dif
eren
ça %
(fa
ltas
de
pág
ina)
Clock
3P
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
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP
Diferenças Percentuais de Desempenho - GROBNER
-45,00%
-40,00%
-35,00%
-30,00%
-25,00%
-20,00%
-15,00%
-10,00%
-5,00%
0,00%
5,00%
10,00%
20 22 24 26 28 30 32 34 36 38 40 42 44
Tamanho da memória
Dif
eren
ça %
(fa
ltas
de
pág
ina)
Clock
3P
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 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-SPwww.lasb.pcs.poli.usp.br
II WSO / 2005 – Algoritmo de Substituição de Páginas 3P: Acrescentando Adaptatividade ao Clock - EPUSP