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.
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.
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}\).
// 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];
}
// 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];
}