Atividade 05

Computação Paralela · 2022.1

Leia com atenção as instruções abaixo.

Valor: 2,0 pontos na 1ª Nota.

Data da Entrega Limite: 21/05/2022

Formato de Entrega: envie um .pdf com a resolução, feito em meios digitais, para o chat privado do professor no Slack.

A atividade é individual.

Questão 01 - 1,0 Ponto

Desempenho da Convolução. Considere uma CPU com um único núcleo funcionando a 2.5 GHz e capaz de realizar 8 operações em ponto flutuante de precisão simples por ciclo. Essa CPU está conectada a um módulo DRAM com pico de transferência de memória em 25.6 GB/s. Ela tem um cache de 256 KB funcionando na mesma velocidade de um registrador. Queremos calcular a convolução de uma imagem 2D \(I\) de tamanho \(n \times n\) armazenada na memória principal com uma máscara \(M\) de tamanho \((2k+1)\times(2k+1)\), isto é, queremos calcular uma imagem \(C\) de tamanho \(n \times n\) com:

\begin{equation} C[x][y] = \sum_{i=-k}^{k}\sum_{j=-k}^{k}{I[x+i][y+j] \times M[k-i][k-j]}\text{ para todo } \{ 0 \le x,y \le n - 1 \} \end{equation}

Na equação acima, temos \(I[x+i][y+j] = 0\) se \(x + i \lt 0\) ou \(x + i \ge n\) ou \(y + j \lt 0\) ou \(y + j \ge n\).

Responda e justifique os seguintes itens.

  1. Estabeleça um limite superior no desempenho alcançável deste sistema para calcular a convolução de uma imagem \(I\) com valores reais de tamanho \(256 \times 256\) e uma máscara \(M\) de tamanho \(1 \times 1\).
  2. Faça o mesmo para uma máscara \(5 \times 5\).
  3. Qual seria uma boa estratégia para caching se \(I\) for muitas vezes maior que a cache?

Questão 02 - 1,0 Ponto

Linhas de Cache e Vetorização. Considere uma CPU com uma linha de cache de tamanho \(L = sizeof(float) \times 16\) e duas matrizes quadradas \(A, B \in float^{N \times N}\), cada uma com tamanho \(N = 1024\). Nos items a seguir, queremos calcular \(C = A + B\) processando as entradas \(C_{ij} = A_{ij} + B_{ij}\) para todo \(i,j \in {0, ..., N-1}\).

  1. Calcule o número total de erros de cache na função row_wise_add:

    // row-major-order addition
void row_wise_add(float *A, float *B, float *C, size_t N) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            C[i*N + j] = A[i*N + j] + B[i*N + j];
}

  2. Faça o mesmo para a função column_wise_add:. Qual das duas funções tem melhor desempenho?

    // column-major-order addition
void column_wise_add(float *A, float *B, float *C, size_t N) {
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            C[i*N + j] = A[i*N + j] + B[i*N + j];
}

  3. Usando a função intríseca __mm256_load_ps você pode carregar 8 valores de precisão simples em ponto flutuante de uma vez de um vetor alinhado e armazená-los em uma variável local __mm256 tmp. A função equivalente __mm256_store_ps pode ser usada para armazenar o vetor de volta na memória. Encontre o comando apropriado para somar duas variáveis do tipo __mm256. Depois implemente uma versão AVX da função row_wise_add:.

  4. Compare o tempo de execução das três versões acima.