Caracterização de Cargas de Trabalho
em Estudos sobre Gerência de Memória Virtual
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
Descrever o Elephantools:
Um pacote composto por ferramentas de software voltadas
à caracterização de cargas de trabalho em experimentos
sobre gerência de memória virtual.
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Motivação
• Elephantus
- Ambiente para avaliação de sistemas de memória
- Conjunto de simuladores
Programa
executável
resultados
Gerador
de traces
Simulador
arquivo de traces
desempenho
dos algoritmos
• Dificuldade de caracterizar cargas de trabalho
- Localidades espacial e temporal
- Padrões de acesso à memória
- Freqüência de reutilização das páginas
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Apresentação
• Análise de localidade
- Recursos gráficos tradicionais
- Precisão, relevância e limitação dos dados
• Pacote Elephantools
- TelaTrace
- Mapa3D
- Trace Explorer
• Aplicação das ferramentas
- Estudo de caso
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Análise de Localidade
• Localidade de referências: espacial / temporal
• Working set
Espaço de endereçamento virtual
Working set: páginas acessadas em um intervalo de tempo
Exemplo de
localidade
espacial
de acessos
Exemplo de
localidade
temporal
de acessos
Tempo virtual (acessos à memória)
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Espaço de endereçamento virtual
Gráfico (Mapa) de Acessos
Tempo virtual (acessos à memória)
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Gráfico (Mapa) de Acessos
• Limitações
- Tamanho original: perda da visão global
- Tamanho reduzido: compressão visual com perda de dados
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Superfícies de Localidade
(Brigham Young University)
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Superfícies de Localidade
• Benefícios
- Destaca características de acesso à memória sobressalentes
- Informação concisa (processada)
• Limitações
- Possível compressão visual com perda de dados
- Ausência da informação cronológica
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Pacote Elephantools
• TelaTrace
- Gráficos de acesso tradicionais (em duas dimensões)
• Mapa3D
- Gráficos de acesso tridimensionais
• Trace Explorer
- Gráficos de execução simulada no contexto do modelo LRU
- Dados gerais e estatísticos sobre os traces analisados
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta TelaTrace
• Gráficos de acesso bidimensionais
- Diversas possibilidades de ampliação
- Visão global sempre presente
- Resolução definida pelo usuário
• Recursos adicionais para traces com formato especial
- Diferenciação entre processadores (programas paralelos)
- Diferenciação entre tipos de acesso à memória: leitura / gravação
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta TelaTrace
• Janela principal: visão global
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta TelaTrace
• Janela de aproximação: visão parcial detalhada
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta Mapa3D
• Gráficos de acesso tridimensionais
- Um gráfico de acessos visualmente comprimido se transforma em
uma superfície de acessos à memória
- A terceira dimensão informa quantos pontos foram aglutinados em
cada posição x,y
- Resolução definida pelo usuário
- Não desenha os gráficos: gera coordenadas em arquivos-texto
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta Mapa3D
• Gráfico de acessos 3D (desenhado com o Microsoft Excel)
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta Mapa3D
• Versões 2D e 3D referentes ao mesmo mapa de acessos
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta Trace Explorer
• Gráficos bidimensionais e tridimensionais – Modelo LRU
- Recência dos acessos à memória (posição na fila LRU)
- Histograma da recência dos acessos
- Variação da recência dos acessos
- Distância temporal entre acessos a uma mesma página
- Entre outros
• Dados gerais e estatísticos sobre os traces
- Número total de acessos e de páginas referenciadas
- Posição média dos acessos na fila LRU e desvio padrão
- Variação média da posição dos acessos na fila e desvio padrão
- Lista de todas as páginas referenciadas com estatísticas individuais
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta Trace Explorer
• Modelo LRU (Least Recently Used)
Fila LRU
(memória)
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta Trace Explorer
• Mapa de recência dos acessos (desenhado com o Gnuplot)
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Ferramenta Trace Explorer
• Mapa de distância entre acessos a uma mesma página
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso
• Dados gerais e estatísticos – Pacote de traces VMTrace
- A maioria dos traces consome pouca memória em sua execução
- Os acessos se concentram em páginas que ocupam as primeiras
posições da fila LRU
- Existe uma certa regularidade no intervalo entre acessos a uma
mesma página
VMTrace
Arquivo
Espresso
GCC
Gnuplot
Grobner
GS
Lindsay
P2C
Total de
Total de
Menor
Acessos à
Páginas
Página
Memória Acessadas (dec./hex.)
Posição dos Acessos na Fila LRU
Maior
Desvio
Var. Média Var. Zero
Página
Média Geral
Padrão
(módulo) (% Acessos)
(dec./hex.)
326938361
37524334
68458509
7787835
134371942
123690749
30722431
180 (b4)
1150 (47e)
7857 (1eb1)
166 (a6)
934 (3a6)
614 (266)
300 (12c)
77
458
7718
67
558
521
132
100 (64)
688 (2b0)
130 (82)
94 (5e)
219 (db)
89 (59)
165 (a5)
1,82
3,33
5,26
2,07
2,03
2,78
3,00
1,21
6,90
115,74
2,45
3,63
8,32
4,97
0,59
2,61
5,89
1,33
1,17
2,63
2,31
64,67%
39,95%
34,94%
49,01%
65,92%
57,88%
51,47%
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso – Programa Grobner
• Mapa de acessos bidimensional
- Working set médio tende a aumentar com o tempo
- Presença de localidade temporal e espacial
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso – Programa Grobner
• Mapa de acessos tridimensional
- Concentração dos acessos
em uma faixa diagonal do
gráfico
- Páginas tendem a ser
muito exploradas em
somente um período
- Padrão seqüencial
de acessos do ponto
de vista macroscópico
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso – Programa Grobner
• Mapa bidimensional da recência dos acessos à memória
- Os acessos acontecem em páginas que ocupam posições variadas
na fila LRU,
principalmente após
a metade do
processamento
- Muito poucos
acessos recaem em
posições da fila
superiores a 40
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso – Programa Grobner
• Mapa tridimensional da recência dos acessos à memória
- Concentração dos
acessos nas posições
iniciais da fila LRU
- Páginas com forte
localidade temporal são
referenciadas em meio
a páginas pouco
acessadas no
período
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso – Programa Grobner
• Variação da recência dos acessos à memória
- Grande simetria em relação à posição de variação zero
- As páginas tendem a
ocupar sempre uma
mesma posição na
fila LRU quando são
acessadas
- Quando a posição
varia, normalmente
retorna à situação
original no acesso
seguinte
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso – Programa Grobner
• Mapa bidimensional da recência dos acessos à memória
(participação da página mais referenciada pelo programa)
- A página 5E
geralmente ocupa
uma posição inferior
a 10 na fila LRU
quando é acessada
- O algoritmo LRU é
relativamente
eficiente quanto às
substituições que
realiza
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso – Programa Grobner
• Previsão de faltas de página
- Em quase 60% dos acessos, a página referenciada ocupa a 2ª
posição da fila LRU: localidade temporal constante
- Uma memória de tamanho 8 é suficiente para garantir uma taxa de
faltas de página inferior a 2% com o algoritmo LRU
GROBNER.VMTrace - Posição dos Acessos na Fila LRU
Pos. (a≤x<b)
0
1
2^1 - 2^2
2^2 - 2^3
2^3 - 2^4
2^4 - 2^5
2^5 - 2^6
2^6 - 2^7
Acessos
0
4620622
2210724
817293
96860
31374
10895
0
Ac. Acum.
0
4620622
6831346
7648639
7745499
7776873
7787768
7787768
% Acessos
0,00
59,33
28,39
10,49
1,25
0,40
0,14
0,00
% Acum.
0,00
59,33
87,72
98,21
99,46
99,86
100,00
100,00
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Estudo de Caso – Programa Grobner
• Formas de apresentação visual dos dados tabulares
- Histograma
- Curva acumulada
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP
Conclusão
• Pacote Elephantools
- Caracterização de cargas de trabalho quanto ao uso da memória
- Documentação gráfica de experimentos realizados
- Explanação simples e intuitiva acerca das conclusões
• Trabalhos futuros
- Aprimoramento das ferramentas existentes
- Nova ferramenta: melhor visualização das superfícies de localidade
• Agradecimentos
- Elizabeth S. Sorenson (Brigham Young University)
- Scott F. Kaplan (Amherst College)
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - 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 Software Básico
Av. Prof. Luciano Gualberto, travessa 3, 158, Cidade Universitária
CEP: 05508-900, São Paulo-SP
III WPerformance / 2004 – Caracterização de Cargas de Trabalho em Estudos sobre Gerência de Memória Virtual - EPUSP