ANÁLISE DO PADRÃO DE ACESSOS À MEMÓRIA DE PROGRAMAS PARALELOS Hugo Henrique Cassettari Edson Toshimi Midorikawa EPUSP - Escola Politécnica da Universidade

ANÁLISE DO PADRÃO DE ACESSOS À MEMÓRIAANÁLISE DO PADRÃO DE ACESSOS À MEMÓRIADE PROGRAMAS PARALELOSDE PROGRAMAS PARALELOS

Hugo Henrique CassettariEdson Toshimi Midorikawa

EPUSP - Escola Politécnica da Universidade de São PauloPCS - Departamento de Engenharia de Computação e Sistemas Digitais

ANÁLISE DO PADRÃO DE ACESSOS À MEMÓRIAANÁLISE DO PADRÃO DE ACESSOS À MEMÓRIADE PROGRAMAS PARALELOSDE PROGRAMAS PARALELOS

Hugo Henrique CassettariEdson Toshimi Midorikawa

EPUSP - Escola Politécnica da Universidade de São PauloPCS - Departamento de Engenharia de Computação e Sistemas Digitais

CBComp 2002 - Análise do Padrão de Acessos à Memória de Programas Paralelos / EPUSP

Escopo

• Avaliação de Desempenho

• Ferramenta Desenvolvida

• Programação Paralela– Computação de Alto Desempenho– Multiprocessamento

– Padrão de Acessos à Memória– Localidade de Referências

– Visualização e Análise– Simulação baseada em Arquivos de Trace


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


Contexto

• 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

Programaexecutável

Ferramenta deVisualização e Análise

resultadosarquivode traces

Gerador de traces tela


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


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


Janela Principal

• Todos os acessos do(s) programa(s) selecionado(s)

• Cada cor identifica um programa

• Sobreposição de cores


Janela Principal


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


Janela de Aproximação


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


Armazenamento de Matrizes em Memória

• Matriz quadrada de ordem 3:

a1 a2 a3

A = a4 a5 a6

a7 a8 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 a9Página 1 Página 2 Página 3 (exemplo simplificado)


Multiplicação de Matrizes

• Algoritmo tradicional (ijk):

• C = A x B, sendo que:

– MATRIZ A: Acesso por linhas– MATRIZ B: Acesso por colunas– MATRIZ C: Acesso por linhas

C[i][j]=C[i][j] + A[i][k]*B[k][j];

for (i=0; i<N; i++)

for (j=0; j<N; j++)

for (k=0; k<N; k++)

=

BAC




– MATRIZ A:– MATRIZ B:– MATRIZ C:

C[i][j]=C[i][j] + A[i][k]*B[k][j];

for (i=0; i<N; i++)

for (j=0; j<N; j++)

for (k=0; k<N; k++)



• Versão ikj:


– MATRIZ A: Acesso por linhas– MATRIZ B: Acesso por linhas– MATRIZ C: Acesso por linhas

C[i][j]=C[i][j] + A[i][k]*B[k][j];

for (i=0; i<N; i++)

for (j=0; j<N; j++)

=

BAC

for (k=0; k<N; k++)




– MATRIZ A:– MATRIZ B:– MATRIZ C:

C[i][j]=C[i][j] + A[i][k]*B[k][j];

for (i=0; i<N; i++)

for (k=0; k<N; k++)

for (j=0; j<N; j++)



• Versão jki:


– MATRIZ A: Acesso por colunas– MATRIZ B: Acesso por colunas– MATRIZ C: Acesso por colunas

C[i][j]=C[i][j] + A[i][k]*B[k][j];

for (i=0; i<N; i++)

for (k=0; k<N; k++)

for (j=0; j<N; j++)

=

BAC



• Todas as possíveis permutações:

=

BAC

=

BAC

=

BAC

=

BAC

=

BAC

=

BAC


Padrão de Acessos da Versão ijk


Padrão de Acessos da Versão ikj


Padrão de Acessos da Versão jki


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


Padrão de Acessos da Versão ikj-uj-sr


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


Tempos de Execução

Desempenho das Versões

0

100

200

300

400

500

600

700

800

1 2 3 4

Número de CPUs

Te

mp

o d

e E

xe

cuçã

o

(se

gu

nd

os) ijk

ikj

jki

ikj-uj-sr

(*) 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.


Versão Atual da Ferramenta

• Diferenciação entre leitura/gravação e processadores

Versão ijk com2 processadores

Proc. 1 - LeituraProc. 1 - GravaçãoProc. 2 - LeituraProc. 2 - Gravação


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)


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 Software BásicoAv. Prof. Luciano Gualberto, travessa 3, 158, Cidade UniversitáriaCEP: 05508-900, São Paulo-SP

Documents

ANÁLISE DO PADRÃO DE ACESSOS À MEMÓRIA DE PROGRAMAS PARALELOS Hugo Henrique Cassettari Edson Toshimi Midorikawa EPUSP - Escola Politécnica da Universidade