STACKPAR: Um Simulador Paralelo de Sistemas
de Memória baseado em Algoritmos de Pilha
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
• Viabilizar a execução paralela de simulações de sistemas
de memória, reduzindo assim o alto tempo despendido com
essa tarefa
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Escopo
• Algoritmos de Substituição de Páginas
– Gerenciamento de Memória
– Paginação
• Algoritmos de Pilha
– LRU Stack
– ÓTIMO Stack
• Programação Paralela
– Multiprocessamento
– Memória Compartilhada
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Algoritmos de Substituição de Páginas
• Estratégia utilizada pelo Sistema Operacional para retirar
uma página da memória, quando necessário;
• Procura estimar, com base em algum critério, que página
levará mais tempo para ser novamente acessada;
• Exemplos: Ótimo, LRU, FIFO, NRU, MRU, WS, PFF, ...
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Algoritmo Ótimo
• Algoritmo teórico, impossível de ser implementado na
prática;
• “Lê” o futuro e sabe que página deve ser retirada da
memória principal em caso de necessidade (falta de
página);
• Exemplo:
A
B
D
C
C
(memória)
(memória)
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Algoritmo LRU
• Algoritmo geralmente bastante eficiente;
• Least Recently Used: retira, quando necessário, a página
acessada há mais tempo;
• Exemplo:
D
A
B
C
(memória)
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Simulações
Programa
executável
resultados
Gerador
de traces
Simulador
arquivo de traces
desempenho
dos algoritmos
• Simulação e avaliação de sistemas de memória;
• Exemplo simplificado de arquivo de traces:
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Simulação Simples
Memória
npf
ExT
tamanho disponível
• Cálculo do número de faltas de páginas (page faults):
- Lê um acesso
- Se a memória está cheia e não contém a página acessada
npf = npf + 1
• Cálculo do produto Espaço x Tempo:
- Lê um acesso
- ExT = ExT + tamanho_memória_utilizada
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Algoritmos de Pilha
• Há uma classe de algoritmos de substituição de páginas
que possuem a seguinte propriedade:
M(m,r)  M(m+1,r)
Onde:
M - Conjunto de páginas na memória principal
m - tamanho da memória
r - instante (medido em número de referências acessadas)
• Os algoritmos de pilha exploram essa propriedade
• A classe de algoritmos inclui o Ótimo e o LRU
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Simulação com Pilha
Memória em forma de
pilha
tamanho
máximo
Histograma
(h)
npf ExT
• Cálculo do número de faltas de páginas (page faults):
- Lê um acesso
- p = posição da página lida na pilha
- h[p].npf = h[p].npf + 1
• Cálculo do produto Espaço x Tempo:
- Lê um acesso
- para m = 1 até tamanho_máximo_memória
h[m].ExT = h[m].ExT+(m<tam_mem_utilizada?m:tam_mem_utilizada)
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
StackPar
• Versão paralela do simulador baseado em pilha;
• Necessidade de tratar dependência de dados;
• Desenvolvido em linguagem C, utilizando pthreads;
• Trabalha com os mesmos formatos de arquivos de trace
que o simulador original.
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Simulação Paralela
Por processador
Memória em forma de
pilha
tamanho
máximo
Histograma
(h)
npf ExT
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Simulação Paralela
Memória
Entre dois
processadores
Transição
Memória
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Simulação Paralela
Memória
Transição
A cada trinca de
processadores
Dupla transição
Memória
Transição
Memória
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Simulação Paralela
• Primeiro Estágio:
Pilha 0
Dupla-transição 1
Transição 1
?
Pilha 1
Dupla-transição 2
Transição 2
?
Pilha 2
Transição 3
?
Pilha 3
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Simulação Paralela
• Segundo e Terceiro Estágios:
Segundo estágio:
tratamento de
dependências
Pilha 0
?
Dupla-transição 1
Transição 1
?
Pilha 1
?
Dupla-transição 2
Transição 2
?
Pilha 2
Transição 3
?
Pilha 3
Terceiro estágio:
cálculo do produto
espaçoXtempo
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
LRU Stack Paralelo
• Calcula o número de faltas de página e o produto espaço
X tempo paralelamente.
Tempos de Execução Obtidos (em segundos)
LRU
1 Proc.
212
346
350
559
22
29
LRU, rodando GZIP
400
350
LRU Stack
300
LRU StackPar (2 proc.)
250
LRU StackPar (3 proc.)
200
LRU StackPar (4 proc.)
150
100
50
0
Tempo de Execução
Tem po de Execução (segundos)
GZIP
SEQ
LU
Stack
(*) Testes executados em uma
máquina SMP com 4 processadores
Pentium II Xeon de 400 MHz e 256
MB de memória principal, sistema
operacional Linux.
StackPar
2 Proc. 3 Proc. 4 Proc.
174
115
88
281
188
144
15
10
7
400
350
300
250
200
150
100
50
0
Stack
StackPar
1
GZIP
SEQ
LU
2
3
4
Número de Processadores
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
ÓTIMO Stack Paralelo
• Calcula o número de faltas de página da forma tradicional;
• Calcula o produto espaço X tempo paralelamente.
Tempos de Execução Obtidos (em segundos)
Ótimo Stack
ÓTIMO, rodando GZIP
1000
900
800
700
600
500
400
300
200
100
0
Ótimo Stack
Ótimo StackPar (2 proc.)
Ótimo StackPar (3 proc.)
Ótimo StackPar (4 proc.)
Tempo de Execução
Tem po de Execução (segundos)
GZIP
SEQ
LU
1 Proc.
247
353
884
1115
32
44
(*) Testes executados em uma
máquina SMP com 4 processadores
Pentium II Xeon de 400 MHz e 256
MB de memória principal, sistema
operacional Linux.
StackPar
2 Proc. 3 Proc. 4 Proc.
188
147
118
692
574
499
25
18
15
400
350
300
250
200
150
100
50
0
Stack
StackPar
1
GZIP
SEQ
LU
2
3
4
Número de Processadores
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP
Trabalhos Futuros
• Verificar a viabilidade de paralelização do WS Stack;
• Desenvolver uma versão do simulador para trabalhar com
memória distribuída em clusters (MPI);
• Procurar meios mais eficientes de paralelizar o Ótimo
Stack.
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - 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
IV FITEM / 2002 - StackPar: Um Simulador Paralelo de Sistemas de Memória baseado em Algoritmos de Pilha - EPUSP