ANÁLISE DO PADRÃO DE ACESSOS À MEMÓRIA
DE PROGRAMAS PARALELOS
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
ANÁLISE DO PADRÃO DE ACESSOS À MEMÓRIA
DE PROGRAMAS PARALELOS
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
Escopo
• Avaliação de Desempenho
– Padrão de Acessos à Memória
– Localidade de Referências
• Ferramenta Desenvolvida
– Visualização e Análise
– Simulação baseada em Arquivos de Trace
• Programação Paralela
– Computação de Alto Desempenho
– Multiprocessamento
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Motivação
• Memória possui uma limitação teórica - “memory wall”
• Alternativa: explorar localidades de referências
• Técnicas de programação podem levar a uma maior
localidade de acessos
• Visualizar padrões de acesso de programas à memória
pode ser um recurso importante
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Contexto
Programa
executável
Ferramenta de
Visualização e Análise
Gerador
de traces
arquivo
de traces
tela
resultados
• Simulação e avaliação de sistemas de memória
– Técnicas de otimização
– Algoritmos de substituição de páginas
– Influência da propriedade de localidade de acessos
• Dificuldade em se detectar facilmente padrões de acesso
à memória
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Padrões de Acesso à Memória
• Refere-se a como os programas endereçam as posições
de memória
• Espaço virtual deve favorecer o funcionamento do sistema
• Exploração de uma “região” de endereços favorece o
desempenho
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Ferramenta de Visualização e Análise
• Desenvolvida em Java
• Módulo de pré-processamento desenvolvido em C
• Disponível nas plataformas Linux e Microsoft Windows
• Permite uma abordagem visual do comportamento dos
programas em relação aos seus acessos à memória
• Gráfico informa os endereços de memória acessados no
decorrer do tempo de execução
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Janela Principal
• Todos os acessos do(s) programa(s) selecionado(s)
• Cada cor identifica um programa
• Sobreposição de cores
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Janela Principal
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Janela de Aproximação
• Janela de aproximação base
– Seleção de trecho
– Aproximação parcial
• Janela de aproximação sucessiva
– Aproximação infinita
– Cópia comparativa temporária na janela de aproximação base
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Janela de Aproximação
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Estudo de Caso: Multiplicação de Matrizes
• Três formas básicas de acesso aos elementos:
– Acesso por linhas
– Acesso por colunas
– Acesso por diagonais
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Armazenamento de Matrizes em Memória
• Matriz quadrada de ordem 3:
a1
a4
a7
A=
a2
a5
a8
a3
a6
a9
• Armazenamento na memória, em C ou Pascal:
1
2
3
4
5
6
7
8
9
a1 a2 a3 a4 a5 a6 a7 a8 a9
Página 1
Página 2
Página 3
(exemplo simplificado)
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Multiplicação de Matrizes
• Algoritmo tradicional (ijk):
for (i=0; i<N; i++)
for (j=0; j<N; j++)
for (k=0; k<N; k++)
C[i][j]=C[i][j] + A[i][k]*B[k][j];
• C = A x B, sendo que:
– MATRIZ A: Acesso por linhas
– MATRIZ B: Acesso por colunas
– MATRIZ C: Acesso por linhas

=
C
A
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
B
Multiplicação de Matrizes
for (i=0; i<N; i++)
for (k=0; k<N; k++)
for (j=0; j<N; j++)
C[i][j]=C[i][j] + A[i][k]*B[k][j];
• C = A x B, sendo que:
– MATRIZ A:
– MATRIZ B:
– MATRIZ C:
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Multiplicação de Matrizes
• Versão ikj:
for (i=0; i<N; i++)
for (k=0; k<N; k++)
for (j=0; j<N; j++)
C[i][j]=C[i][j] + A[i][k]*B[k][j];
• C = A x B, sendo que:
– MATRIZ A: Acesso por linhas
– MATRIZ B: Acesso por linhas
– MATRIZ C: Acesso por linhas

=
C
A
B
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Multiplicação de Matrizes
for (j=0; j<N; j++)
for (k=0; k<N; k++)
for (i=0; i<N; i++)
C[i][j]=C[i][j] + A[i][k]*B[k][j];
• C = A x B, sendo que:
– MATRIZ A:
– MATRIZ B:
– MATRIZ C:
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Multiplicação de Matrizes
• Versão jki:
for (j=0; j<N; j++)
for (k=0; k<N; k++)
for (i=0; i<N; i++)
C[i][j]=C[i][j] + A[i][k]*B[k][j];
• C = A x B, sendo que:
– MATRIZ A: Acesso por colunas
– MATRIZ B: Acesso por colunas
– MATRIZ C: Acesso por colunas

=
C
A
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
B
Multiplicação de Matrizes
• Todas as possíveis permutações:

=
C
A
B
C
A
A
A
B

=
B
C

=
C
C

=

=
A
B

=
B
C
A
B
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Padrão de Acessos da Versão ijk
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Padrão de Acessos da Versão ikj
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Padrão de Acessos da Versão jki
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Versão ikj-uj-sr
• Otimizações no código de forma a explorar ainda mais a
hierarquia de memória
• Transformação unroll-and-jam
– Reúne vários acessos a uma mesma posição de matriz no loop
mais interno
• Transformação scalar replacement
– Posições referenciadas são atribuídas a variáveis escalares a
cada iteração
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Padrão de Acessos da Versão ikj-uj-sr
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Padrão de Acessos da Versão ikj-uj-sr
• Padrão de acessos praticamente idêntico ao da versão ikj
• Menor tempo de execução
• Exploração de registradores do processador
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Tempos de Execução
Desempenho das Versões
Tempo de Execução
(segundos)
800
700
600
500
ijk
400
ikj
300
jki
200
ikj-uj-sr
100
0
1
2
3
4
Número de CPUs
(*) Matrizes de ordem 1500,
executadas em uma máquina SMP
com 4 processadores Pentium II Xeon
de 400 MHz e 256 MB de memória
principal, sistema operacional Linux.
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Versão Atual da Ferramenta
• Diferenciação entre leitura/gravação e processadores
Versão ijk com
2 processadores
Proc. 1 - Leitura
Proc. 1 - Gravação
Proc. 2 - Leitura
Proc. 2 - Gravação
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP
Trabalhos Futuros
• Utilização de programas de estudo maiores
• Análise aprofundada do sistema de memória virtual
• Suporte a arquivos de trace compactados
• Suporte a programas MPI (processamento distribuído)
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / 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
CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP