Análise da Localidade de Programas e
Desenvolvimento de Algoritmos Adaptativos para
Substituição de Páginas
Hugo Henrique Cassettari
Orientador: Edson Toshimi Midorikawa
Trabalho de Mestrado, Janeiro de 2004
Escola Politécnica da Universidade de São Paulo
Departamento de Engenharia de Computação e Sistemas Digitais
Estrutura da Apresentação:
• Algoritmos de substituição de páginas (revisão);
• Localidade de referências;
• Ferramentas desenvolvidas para análise de localidade;
• Algoritmos adaptativos;
• Proposta LRU-WAR;
• Avaliação de desempenho.
Memória Virtual com Paginação:
Página
4 KB
Área de Swap
(Disco)
Memória
Principal
Memória Virtual com Paginação:
Problema da
Substituição:
Qual página
deve ser retirada
da memória?
Políticas de Substituição de Páginas:
• ÓTIMO
• LFU
- FBR
• FIFO
- Clock
• MFU
• LRU
- LRU-K e 2Q
• VMIN
• MRU
• WS
• NRU
• PFF
Working Set:
• Conjunto das páginas requeridas para o
processamento de um programa num certo intervalo
de tempo.
Localidade de Referências:
• Concentração dos acessos realizados à memória em
determinadas regiões do espaço de endereçamento
utilizado pelo programa;
• Temporal e/ou espacial.
Objetivo do Trabalho:
• Buscar novos meios para melhorar o desempenho do
sistema de memória, através de:
- Estudo e caracterização de localidade de referências;
- Pesquisa de algoritmos adaptativos para substituição de
páginas (algoritmos que adaptam o seu comportamento
em uma execução).
Análise da Localidade de Programas:
• Padrões de acesso à memória;
• Localidades de referência temporais e/ou espaciais;
• Distribuição dos acessos no espaço de endereçamento;
• Freqüência de reutilização das páginas;
• Interação entre páginas (acessos entrelaçados);
• Entre outros dados...
Conceitos:
• Recência de Reutilização:
- Corresponde à recência de reutilização de uma
página de memória em relação à reutilização das
demais páginas residentes;
- É determinada empiricamente pelo número de
páginas distintas referenciadas entre dois acessos
consecutivos a uma mesma página (IRR / InterReference Recency).
• Distância (ou IRG / Inter-Reference Gap):
- Indica o número de acessos ocorridos (tempo virtual)
entre duas referências consecutivas a uma mesma
página.
Exemplo:
• Recência:
IRR = 4
IRR = 4
A
B
C
B
D
C
E
C
D
E
C
A
D
E
B
C
A
B
E
D
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
• Distância (ou IRG / Inter-Reference Gap):
IRG = 10
IRG = 4
A
B
C
B
D
C
E
C
D
E
C
A
D
E
B
C
A
B
E
D
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Recência no Modelo LRU:
• Exemplo:
IRR = 4
IRR = 4
A
B
C
B
D
C
E
C
D
E
C
A
D
E
B
C
A
B
E
D
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
• Fila LRU:
C
E
D
B
A
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Ferramentas para Análise de Localidade:
• TelaTrace: Gráficos de acesso bidimensionais.
• Mapa3D: Gráficos de acesso tridimensionais.
• Trace Explorer:
- Gráficos de recência dos acessos;
- Gráficos de variação da recência dos acessos;
- Histogramas de recência dos acessos;
- Gráficos de distância entre acessos;
- Relatórios estatísticos sobre os traces analisados.
TelaTrace – Mapa de Acessos:
Mapa3D – Mapa de Acessos:
Mapa3D – Mapa de Acessos:
TraceExplorer – Recência dos Acessos:
TraceExplorer – Variação da Recência:
TraceExplorer – Distância entre Acessos:
Algoritmos Adaptativos de Substituição:
• Adaptam seu comportamento em uma execução;
• Atuam de acordo com as características de acesso à
memória detectadas;
• Podem:
• Modificar o tamanho da memória utilizada;
• Modificar o critério de substituição de páginas;
• Modificar os parâmetros associados ao critério vigente;
• Modificar as suas próprias regras adaptativas.
Propostas Adaptativas:
• SEQ e EELRU:
- Modelo LRU;
- Identificação de acessos seqüenciais.
• LIRS: Previsão de acesso baseada na última reutilização.
• DEAR, AFC e UBM: Procuram reconhecer padrões.
• LRFU: Considera a recência e a freqüência dos acessos.
• ARC: Versão adaptativa do algoritmo 2Q.
Proposta LRU-WAR (Working Area Restriction):
• Como o SEQ e o EELRU procura detectar padrões
de acesso seqüenciais;
• Utiliza LRU ou MRU-n;
• Princípio: Analisar a proporção de faltas de página
em relação ao número máximo de páginas
referenciadas entre cada falta;
• Verifica a reutilização das páginas carregadas no
modelo LRU e compara com o número de faltas de
página.
Área de Trabalho (Working Area):
• Porção inicial da fila LRU em que todas as páginas
referenciadas entre duas faltas consecutivas se
encontravam no momento do respectivo acesso.
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
Regiões da Fila LRU:
• Parâmetro L=MIN[50,M/2]: delimita a região seqüencial;
• Parâmetro C=5: delimita a região protegida.
Região Protegida
L
Região Seqüencial
Região LRU
C
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
Tendência Seqüencial:
• Área de trabalho pequena o suficiente para indicar
baixa reutilização de páginas.
Região Protegida
L
Região Seqüencial
Região LRU
C
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
Operação Seqüencial:
• Área de trabalho pequena o suficiente para indicar
baixa reutilização de páginas;
• Número de faltas de página – desde o início da
tendência – maior que o tamanho da área de trabalho.
Região Protegida
L
Região Seqüencial
Região LRU
C
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
Estados de Execução Previstos:
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
Região LRU
C
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
Pontos de Substituição do LRU-WAR:
Exemplo de falta de página
em operação seqüencial
L
Área de Trabalho
Ponto de Substituição
W +1
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Fila LRU
M = 20
Exemplo de falta de página
em tendência original (LRU)
L
Área de Trabalho
Ponto de Substituição
W
1
2
3
Fila LRU
4
5
6
7
8
9
LRU
10 11 12 13 14 15 16 17 18 19 20
M = 20
Exemplo de Simulação:
• Identificação e atualização dinâmica da área de
trabalho:
A
U
V
X
Y
Z
B
X
C
E
D
U
E
V
Y
W
A
U
C
E
V
1
2
3
4
5
Fila LRU
W
D
A
B
C
F
G
D
A
U
B
F
G
H
D
A
U
F
G
H
D
A
FI
G
H
D
F
JI
G
K
H
F
JI
G
K
H
L
JI
M
K
H
L
JI
M
N
K
L
JI
M
O
N
K
L
J
M
O
N
K
P
L
M
Q
O
N
P
L
M
Q
O
R
N
P
Q
O
R
N
S
P
Q
O
R
S
P
T
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
FALTA 5
1
2
3
4
M = 20
Mecanismo para Detecção de Erros:
• Tempo de carência antes do início de uma operação
seqüencial.
Área de Trabalho
Páginas não substituídas pela
L
Ponto de Substituição
op. seqüencial devido ao
tempo de carência
W +1 +2 +3 +4 +5 +6
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
Versões do Algoritmo LRU-WAR:
• Offline:
- Completa, mas teórica;
- Atualiza a fila LRU após cada acesso à memória.
• Online:
- Aproximada, mas factível;
- Atualiza a fila LRU somente após uma falta de página.
Metodologia para Avaliação de Desempenho:
Programa
executável
resultados
Gerador
de traces
Simulador
arquivo de traces
• Exemplo simplificado de arquivo de traces:
desempenho
dos algoritmos
Simulações Realizadas:
• 1669 simulações com 26 programas, representados por
traces que compõem 3 pacotes: Etch, Lirs e VMTrace.
Pacote
ETCH
TOTAL
Acroread
CC1
Compress
Go
Netscape
Perl
Photoshp
Powerpnt
Vortex
Winword
Número de
Simulações
628
95
71
78
52
51
81
60
49
42
49
Pacote
LIRS
TOTAL
2_Pools
CPP
CS
GLI
Multi1
Multi2
Multi3
PS
Sprite
Número de
Simulações
514
99
24
28
50
52
56
74
61
70
Pacote
VMTRACE
TOTAL
Espresso
GCC
Gnuplot
Grobner
GS
Lindsay
P2C
Número de
Simulações
527
66
90
77
56
110
103
25
Lirs
Resultados / Pacote Lirs:
ALGORITMO LRU-WAR: Diferença percentual no número de faltas de
página em relação ao algoritmo LRU
Pior Caso
Melhor Caso
Arquivos de
Média
Diferença % (Mem.) Diferença % (Mem.)
Trace
-5,29%
6,95%
-75,57%
Análise Geral
0,00%
(100)
0,03%
(. . .)
0,00%
2_Pools
-2,88%
(750)
0,24%
(50)
-33,89%
CPP
-36,40%
(1400)
0,00%
(1300)
-75,57%
CS
-20,24%
(. . .)
0,00%
(1100)
-46,56%
GLI
-5,25%
(. . .)
0,00%
(1600)
-39,13%
Multi1
-2,28%
(1300)
0,70%
(2300)
-13,41%
Multi2
-1,66%
(4700)
0,57%
(3500)
-8,88%
Multi3
-20,49%
(. . .)
0,00%
(250)
-44,62%
PS
3,31%
(2300)
6,95%
(300)
-2,46%
Sprite
-9,54%
6,95%
-75,57%
Pacote Lirs
Padrão de Acessos à Memória / Postgres:
Gráfico de Desempenho / Postgres:
PS.Lirs
10000
Ótimo
LRU
EELRU
8000
LIRS
LRU-WAR
7000
LRU-WAR Online
6000
5000
4000
10
50
11
50
12
50
13
50
14
50
15
50
16
50
17
50
18
50
19
50
20
50
95
0
85
0
75
0
65
0
55
0
45
0
35
0
25
0
15
0
3000
50
Número de faltas de página
9000
Tamanho da memória
LRU-WAR em Relação ao LRU / Postgres:
Diferenças Percentuais de Desempenho - PS.Lirs
4%
0%
-8%
-12%
-16%
-20%
-24%
-28%
-32%
-36%
-40%
LRU
-44%
LRU-WAR
Tamanho da memória
20
50
18
50
16
50
14
50
12
50
10
50
85
0
65
0
45
0
25
0
-48%
50
Diferença % (faltas de página)
-4%
Etch
Resultados / Pacote Etch:
ALGORITMO LRU-WAR: Diferença percentual no número de faltas de
página em relação ao algoritmo LRU
Melhor Caso
Pior Caso
Arquivos de
Média
Diferença % (Mem.) Diferença % (Mem.)
Trace
Análise Geral
-75,57%
6,95%
-5,29%
Acroread
-0,09%
(180)
0,51%
(400)
0,11%
CC1
-0,76%
(270)
1,83%
(550)
0,28%
Compress
-75,11%
(270)
0,02%
(15)
-10,34%
Go
0,00%
(. . .)
0,02%
(15)
0,00%
Netscape
-0,12%
(140)
0,74%
(300)
0,08%
Perl
-1,57%
(100)
6,29%
(4200)
2,03%
Photoshp
-1,20%
(150)
5,14%
(2600)
3,03%
Powerpnt
-0,01%
(20)
0,14%
(100)
0,01%
Vortex
-4,33%
(3100)
0,49%
(1600)
-0,72%
Winword
-0,01%
(140)
0,25%
(540)
0,04%
Pacote Etch
-75,11%
6,29%
-0,55%
Padrão de Acessos à Memória / Vortex:
Gráfico de Desempenho / Vortex:
VORTEX.Etch
29000
Ótimo
EELRU
24000
LIRS
LRU-WAR
19000
LRU-WAR Online
14000
9000
4000
15
00
16
00
17
00
18
00
19
00
20
00
21
00
22
00
23
00
24
00
25
00
26
00
27
00
28
00
29
00
30
00
31
00
32
00
33
00
34
00
35
00
36
00
37
00
Número de faltas de página
LRU
Tamanho da memória
LRU-WAR em Relação ao LRU / Vortex:
Diferenças Percentuais de Desempenho - VORTEX.Etch
0%
-2%
-4%
LRU
LRU-WAR
Tamanho da memória
35
00
31
00
27
00
23
00
19
00
-6%
15
00
Diferença % (faltas de página)
2%
VMTrace
Resultados / Pacote VMTrace:
ALGORITMO LRU-WAR: Diferença percentual no número de faltas de
página em relação ao algoritmo LRU
Pior Caso
Melhor Caso
Arquivos de
Média
Diferença % (Mem.) Diferença % (Mem.)
Trace
-5,29%
6,95%
-75,57%
Análise Geral
-0,28%
(27)
0,02%
(12)
-7,94%
Espresso
-1,24%
(245)
0,18%
(185)
-9,66%
GCC
-33,38%
(100)
-0,53%
(7700)
-66,22%
Gnuplot
-3,78%
(13)
1,02%
(28)
-11,75%
Grobner
1,34%
(300)
5,09%
(155)
-5,61%
GS
-8,60%
(130)
1,74%
(. . .)
-17,38%
Lindsay
-0,14%
(75)
0,04%
(50)
-0,72%
P2C
-6,58%
5,09%
-66,22%
Pacote VMTrace
Padrão de Acessos à Memória / GhostScript:
Gráfico de Desempenho / GhostScript:
GS.VMTrace
5000
Ótimo
4500
EELRU
4000
LIRS
3500
LRU-WAR
LRU-WAR Online
3000
2500
2000
1500
1000
500
14
5
16
0
17
5
19
0
20
5
22
0
23
5
25
0
26
5
28
0
29
5
31
0
32
5
34
0
35
5
37
0
38
5
40
0
41
5
43
0
44
5
46
0
47
5
49
0
50
5
52
0
Número de faltas de página
LRU
Tamanho da memória
LRU-WAR em Relação ao LRU / GhostScript:
Diferenças Percentuais de Desempenho - GS.VMTrace
3%
0%
-3%
LRU
LRU-WAR
Tamanho da memória
50
5
48
5
46
5
44
5
42
5
40
5
38
5
36
5
34
5
32
5
30
5
28
5
26
5
24
5
22
5
20
5
18
5
16
5
-6%
14
5
Diferença % (faltas de página)
6%
Grau de Otimalidade das Substituições:
Grau
Grau
de de
Otimalidade
Otimalidade
dasdas
Substituições
Substituições
de de
Página
Página
LRU-WAR
LRU
(GROBNER.VMTrace - memória de tamanho 28)
5000
4000
3000
2000
1000
Índice Decrescente de Otim alidade
27
25
23
21
19
17
15
13
11
9
7
5
3
0
1
Qtd. de Páginas Substituídas
6000
Pontos Ótimos de Substituição:
Pontos Ótimos de Substituição:
4000
3500
3000
2500
2000
1500
1000
500
Posição na Fila LRU
27
25
23
21
19
17
15
13
11
9
7
5
3
0
1
Quantidade de Pontos Ótimos
Posição na Fila LRU dos Pontos Ótim os de Substituição
(Sim ulação LRU - GROBNER.VMTrace - m em ória de tam anho 28)
Conclusões:
• É possível reconhecer certos padrões de acesso à
memória dinamicamente, somente observando as
posições na fila LRU das páginas referenciadas;
• O algoritmo LRU-WAR é uma proposta inédita e viável;
• O algoritmo cumpre sua meta: é uma variação do LRU
que alcança excelentes desempenhos quando padrões
de acesso seqüenciais predominam em um programa;
• Por outro lado, o algoritmo se mostra confiável: seu
desempenho não foi significativamente pior que o do
LRU original em nenhum caso analisado.
Principais Contribuições:
• Descrição compilada dos principais algoritmos de
substituição de páginas, estáticos e adaptativos;
• Desenvolvimento de ferramentas para análise de
localidade e caracterização de programas: TelaTrace,
Mapa3D e Trace Explorer;
• Apresentação de um novo algoritmo adaptativo, o LRUWAR, nas versões online e offline;
• Avaliação de desempenho das principais propostas
adaptativas, com a criação de simuladores de sistemas
de memória e análise sobre os resultados obtidos.
Trabalhos Futuros:
• Aperfeiçoamento do algoritmo LRU-WAR, utilizando
técnicas de IA e/ou diretivas inseridas pelo compilador;
• Tentativa de se chegar a um “meta-algoritmo”;
• Gerência do particionamento dinâmico da memória
entre os processos;
• Implementação prática do novo sistema de
gerenciamento de memória em um SO (Linux);
• Estudos complementares (locality surfaces,
experimentação com outros traces, etc.).