# Máquinas paralelas e memória cache

Memória partilhada e distribuída, linhas de cache e o efeito da ordem de acesso no desempenho.

Página: https://resumos.rgo.pt/cadeiras/cpd/arquiteturas-memoria-cache/

Dois programas com as mesmas operações podem demorar tempos muito diferentes conforme a ordem em que tocam na memória. Esta página explica porquê, e é a base prática do primeiro projeto da cadeira.

## Duas organizações de memória

Nas máquinas de **memória partilhada**, todos os núcleos veem o mesmo espaço de endereços. É o teu portátil e é o modelo do OpenMP. Programar é mais simples, porque uma variável é visível a todas as threads, mas é preciso sincronizar os acessos, como vais ver na página de [concorrência](https://resumos.rgo.pt/cadeiras/cpd/arquiteturas-memoria-cache/concorrencia-sincronizacao/).

Nas máquinas de **memória distribuída**, cada nó tem a sua memória privada e os nós trocam mensagens pela rede. É o modelo dos clusters e é a porta de entrada para a segunda metade da cadeira. Programar exige decidir explicitamente que dados viajam e quando.

## A cache decide

Entre o núcleo e a memória principal há caches pequenas e rápidas, organizadas em **linhas** de tipicamente 64 bytes. Quando o núcleo lê um endereço, traz a linha inteira. Se os acessos seguintes caírem na mesma linha, são quase gratuitos (_localidade espacial_). Se saltarem de linha em linha, cada acesso paga uma ida à memória.

Em C, uma matriz `double a[N][N]` guarda cada linha seguida em memória. Percorrer por linhas usa cada linha de cache até ao fim, 8 doubles por linha de 64 bytes. Percorrer por colunas salta $N \times 8$ bytes a cada acesso e desperdiça 7 doubles de cada linha trazida.

![Uma linha de cache com 8 doubles. No percurso por linhas os 8 são úteis. No percurso por colunas só 1 é útil e 7 são desperdiçados.](https://resumos.rgo.pt/cadeiras/cpd/arquiteturas-memoria-cache/figura-1.svg)

## Exemplo completo

Multiplicação ingénua $C = A \times B$ com $N = 1024$, somando ao longo de $k$. A versão por linhas fixa $i$ e $j$ e percorre $k$ em sequência, aproveitando a cache. A versão por colunas percorre a matriz saltando entre linhas. Numa medição típica num portátil atual:

| Versão | Tempo |
| --- | --- |
| Por linhas | cerca de 1,1 s |
| Por colunas | cerca de 3,9 s |

A diferença, um fator de 3 a 4, vem quase toda da cache, porque as operações aritméticas são as mesmas.[1](https://resumos.rgo.pt/cadeiras/cpd/arquiteturas-memoria-cache/#user-content-fn-tempos-cache) A leitura crítica: antes de paralelizar, ordena os acessos. Um programa paralelo com mau padrão de acesso multiplica o problema pelo número de núcleos, que passam a disputar a largura de banda da memória em vez de calcular.

Os dois percursos em C, a única diferença é a ordem dos índices:

```
#define N 1024
static double a[N][N], b[N][N];

/* Por linhas: cada linha de cache serve 8 acessos. */
for (long i = 0; i < N; i++)
    for (long j = 0; j < N; j++)
        b[i][j] = a[i][j] + 1.0;

/* Por colunas: cada acesso cai numa linha nova. */
for (long j = 0; j < N; j++)
    for (long i = 0; i < N; i++)
        b[i][j] = a[i][j] + 1.0;
```

[Vídeo: Storage Hierarchy, Caching, and Locality, Princeton COS 217](https://www.youtube.com/watch?v=4YeRe60KWTc)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=4YeRe60KWTc)

 Ver por que 8 doubles por linha

Um `double` ocupa 8 bytes e a linha de cache tem 64 bytes, por isso cada linha traz 8 elementos seguidos. No percurso por linhas, cada falta à cache serve 8 acessos úteis. No percurso por colunas com $N = 1024$, cada acesso cai numa linha diferente e cada falta serve 1 acesso útil, pelo que o programa traz cerca de 8 vezes mais dados da memória.

## Notas de rodapé

1.  Os valores 1,1 s e 3,9 s são ilustrativos, medidos num portátil concreto para $N = 1024$. Noutra máquina mudam, mas a ordem de grandeza da diferença mantém-se enquanto a linha tiver 64 bytes. [Voltar](https://resumos.rgo.pt/cadeiras/cpd/arquiteturas-memoria-cache/#user-content-fnref-tempos-cache)