Técnicas para desenvolvimento e aceleração de códigos científicos Prof. Edson Borin Instituto de Computação Universidade Estadual de Campinas Raul Baldin Faculdade de Engenharia Civil, Arquitetura e Urbanismo Universidade Estadual de Campinas

Atividade Prática: Blocagem de laços

Nesta atividade, exercitaremos os conceitos de blocagem de laços.

Conceitos Básicos

Primeiramente, analisaremos o desempenho de um algoritmo de cópia de matrizes. Como discutido antes, o desempenho deste algoritmo em matrizes grandes será limitado pela largura de banda da memória.

Analisaremos então o desempenho de um algoritmo ingênuo de transposição de matrizes. Este algoritmo acessa os dados da matriz em uma ordem que não favorece o reuso dos dados na cache.

Por fim, analisaremos o desempenho de um código de transposição de matrizes otimizado com a técnica de blocagem.

Atividades

Cada atividade possui um arquivo com código fonte para executar o algoritmo, medir o tempo de execução e reportar o tempo e o desempenho do acesso à memória, em Gigabytes por segundo (GB/s). O algoritmo é executado múltiplas vezes e os tempos médio, menor e maior são reportados.

Cópia de matrizes

• Comando para compilar o programa abaixo:

  gcc -O3 kernel1-copy_matrix.c -o kernel1-copy_matrix.x

• programa: kernel1-copy_matrix.c

Ao inspecionar o código do programa, você pode observar que:

• O núcleo, ou kernel, do algoritmo é executado RPT vezes.
• Antes de executar o kernel, a rotina clean_cache() é executada para limpar a cache, ou seja, remover quaisquer dados das matrizes que foram armazenados nas caches do processador por causa das execuções anteriores do kernel.
• Para cada execução do kernel o tempo é medido e armazenado no vetor times[ ].
• Após executar o kernel RPT vezes, os tempos e a vazão da memória (em GB/s) são reportados.
• Note que a variável de indução do laço que computa a média, o menor tempo e o maior tempo inicia com o valor 1, ou seja, o primeiro tempo é descartado. Isso é intencional, já que, a primeira execução geralmente sofre de uma sobrecarga causada pela carga de páginas sob demanda.

Há uma linha de código que imprime o tempo para cada execução do kernel. Esta linha está comentada no programa acima. Remova o comentário e observe os tempos de execução. A primeira execução teve um tempo maior?

Qual foi a maior vazão da memória atingida em seu computador?

Transposição de matrizes ingênua

• Comando para compilar o programa abaixo:

  gcc -O3 kernel2-transpose_naive.c -o kernel2-transpose_naive.x

• programa: kernel2-transpose_naive.c

Da mesma forma que no algoritmo de cópia de matrizes, o número de elementos lidos de uma matriz e armazenados na outra é MATRIX_N x MATRIX_N. Entretanto, por causa da ordem em que os dados são acessados e do modelo de funcionamento das caches, o processador busca o mesmo dado múltiplas vezes da memória. Ao inspecionar o código do programa, você pode observar que as únicas diferenças são:

• o nome do kernel: "transpose_naive" em vez de "copy_matrix"; e
• a ordem de acesso aos dados:

  ma[i][j] = mb[j][i];

  em vez de

  ma[i][j] = mb[i][j];

Execute este kernel e compare o desempenho do mesmo com o desempenho da cópia de matrizes.

Qual a relação de desempenho entre este algoritmo e o algoritmo de cópia de matrizes?

Transposição de matrizes com blocagem

• Comando para compilar o programa abaixo:

  gcc -O3 kernel3-transpose_blocking.c -o kernel3-transpose_blocking.x

• programa: kernel3-transpose_blocking.c

O código da rotina kernel() indica que a transposição é feita em blocos de BLK_FACTOR x MATRIX_N. O programa define BLK_FACTOR com 256, ou seja, os blocos são de 256xMATRIX_N elementos. Como discutido antes, o bloco tem que ser dimensionado de forma que todos os dados da linha sejam usados antes que a mesma seja removida da cache do processador para que a otimização de blocagem tenha efeito.

Qual a relação de desempenho entre este algoritmo e o algoritmo de transposição ingênua e o algoritmo de cópia de matrizes?

Verifique o desempenho do programa com diferentes tamanhos de bloco.
Dica: utilize o argumento -DBLK_FACTOR=800 durante a compilação para mudar o valor da definição BLK_FACTOR sem modificar o código.

gcc -O3 -DBLK_FACTOR=800 kernel3-transpose_blocking.c -o kernel3-transpose_blocking.x

Como computar o tamanho ideal do bloco?

Desafio

O desafio consiste em realizar a blocagem da multiplicação de matrizes. Sugestões:

• a) Utilize o programa kernel4-mat_mul_naive.c como base em suas análises de desempenho. Este programa contém um kernel que realiza a multiplicação de matrizes de forma ingênua.
• b) Modifique o programa para que a matriz B seja transposta antes da multiplicação. O algoritmo de multiplicação deve ser ajustado para usar os dados desta matriz transposta (Bt), em vez da matriz original B. Note que durante o acesso aos dados, os índices devem ser invertidos, ou seja, em vez de acessar B[i][j], o programa deve acessar Bt[j][i]. Em função da ordem de acesso aos dados, este programa deve ter um desempenho melhor do que o original, no entanto, o desempenho ainda será limitado pela largura de banda da memória quando as matrizes forem grandes.
• c) Implemente a blocagem no programa. Esta versão permitirá que os dados sejam reutilizados da cache do processador, aumentando significativamente a largura de banda do acesso aos dados.

Qual é a relação de desempenho entre cada uma das abordagens?