Localidade na cache: a ordem das leituras importa

Uma matriz de inteiros de 8 × 8 está guardada na memória, linha após linha. Entre a memória e o processador há uma cache com 8 linhas de 16 bytes. Some os elementos por linhas ou por colunas e acompanhe as leituras: cada célula indica a única linha de cache que o seu endereço pode ocupar. O âmbar assinala uma falha; o verde, um acerto. A cor clara mostra os elementos vizinhos carregados com uma falha.

Exemplo resolvido — Localidade na cache: a ordem das leituras importa

Leituras em qualquer ordem	64
Blocos de 16 bytes acedidos	16
Máximo de acertos possível	48 em 64 (75,0%)
Acertos por linhas	48 em 64 (75,0%)
Acertos por colunas	0 em 64 (0,0%)
Linhas usadas pela coluna 0	4 de 8

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Localidade na cache: a ordem das leituras importa

Uma cache é uma memória pequena e rápida que guarda cópias de dados da memória principal em linhas. Cada linha contém um bloco alinhado de L bytes. Uma leitura cujo bloco já está numa linha é um acerto; caso contrário, ocorre uma falha e carrega-se o bloco inteiro. Numa cache de mapeamento direto com S linhas, o bloco que contém o endereço a só pode ocupar a linha ⌊a / L⌋ mod S. Um ciclo que lê endereços vizinhos sucessivamente aproveita cada bloco carregado para várias leituras. A esta propriedade chama-se localidade espacial.

O que significa cada símbolo

L: tamanho da linha em bytes: 16 aqui, 64 na maioria dos processadores de computadores de secretária e servidores
S: número de linhas: 8 aqui

Pressupõe: Uma cache de mapeamento direto, inicialmente vazia, inteiros de 4 bytes e uma matriz guardada por linhas, como em C. Em Fortran, as matrizes são guardadas por colunas, pelo que a ordem mais rápida é a inversa. Contam-se apenas as leituras da matriz. As caches reais de dados de primeiro nível são maiores e associativas por conjuntos, tipicamente com 8 vias: um bloco pode ocupar qualquer uma das 8 linhas do seu conjunto. Isto elimina a maioria dos conflitos aqui ilustrados, mas não resolve a falta de espaço. Não se considera a pré-busca por hardware, que carrega a linha seguinte antes de esta ser solicitada.

As mesmas 64 adições dão 48 acertos ou nenhum 🖖

Prima 8 × 8 por linhas e depois 8 × 8 por colunas. Em ambos os casos, são lidos os mesmos 64 inteiros nos mesmos 64 endereços. Só muda a ordem. Por linhas, a primeira leitura de cada linha de cache de 16 bytes falha e carrega 4 inteiros; os 3 seguintes já lá estão. São 48 acertos. Por colunas, a leitura seguinte está na próxima linha da matriz, a 32 bytes de distância, noutra linha de cache. Aqui, cada linha da matriz ocupa exatamente 2 linhas de cache. Assim, a coluna 0 usa apenas as linhas 0, 2, 4 e 6, e a[4][0] remove o bloco que a[0][0] tinha carregado. Quando o ciclo regressa para ler a[0][1], o bloco já não está lá. Falham todas as 64 leituras. Ulrich Drepper mediu este efeito em maior escala em 2007: numa multiplicação de matrizes de 1000 × 1000 num Intel Core 2, o número de ciclos de relógio caiu para 23,4% do valor inicial quando se transpôs previamente a matriz lida por colunas, permitindo ler ambas por linhas.

Se a matriz cabe na cache, a ordem é indiferente 🖖

Escolha a dimensão 5 e alterne entre as ordens: há 18 acertos em 25 leituras em ambos os casos. A matriz ocupa 100 bytes e a cache tem 128 bytes. Os seus 7 blocos ocupam 7 linhas distintas; uma vez carregado, nenhum bloco é removido. Cada bloco provoca uma única falha, na primeira leitura, seja qual for a ordem. Com 6 × 6, a matriz ocupa 144 bytes e dois dos seus blocos têm de partilhar uma linha de cache. Os resultados passam a diferir: 27 acertos por linhas e 25 por colunas. Sem espaço extra entre linhas, a leitura por colunas tem menos acertos em todas as dimensões daí até 16 × 16.

4 inteiros não usados por linha fazem os acertos passar de 0 a 48 🖖

Prima Linhas com espaço extra. É a mesma matriz de 8 × 8, lida por colunas, mas cada linha é seguida de 4 inteiros que nunca são lidos. Cada linha ocupa agora 48 bytes, ou seja, 3 linhas de cache em vez de 2. Como 3 e 8 são primos entre si, a coluna 0 passa a usar todas as 8 linhas de cache. Os 8 blocos de uma coluna ficam na cache ao mesmo tempo, e as 3 colunas seguintes encontram-nos lá: 48 acertos em 64 leituras, tantos como por linhas. O custo são 128 bytes que nunca se leem. Este espaço extra elimina as falhas por conflito, em que dois blocos disputam a mesma linha enquanto outras ficam vazias. Não aumenta a capacidade da cache. O problema resolvido termina com uma matriz para a qual a dificuldade é precisamente essa.

Problema resolvido na íntegra

Quanto tráfego de memória custa a ordem menos favorável? 4 passos
Prima 8 × 8 por colunas e explique os 0 acertos. Considere depois uma matriz de 1024 × 1024 com inteiros de 4 bytes e uma cache de mapeamento direto de 32 KiB, com linhas de 64 bytes. Quantos bytes são transferidos da memória ao somar os elementos por linhas? E por colunas? Acrescentar a cada linha da matriz um espaço equivalente a uma linha de cache ajuda?

Abrir este problema na ferramenta
1. Nesta página, cada linha da matriz ocupa 8 × 4 = 32 bytes, ou seja, 2 linhas de cache. A linha i começa, portanto, na linha de cache 2i mod 8, e a coluna 0 usa apenas as linhas 0, 2, 4 e 6. a[4][0] ocupa a linha onde estava a[0][0]. Quando o ciclo chega a a[0][1], o seu bloco já foi removido: 0 acertos em 64 leituras. Por linhas, há uma falha por bloco de 16 bytes, num total de 16 falhas e 48 acertos: 1 − 4/16 = 75%.
  
  $8 \times 4 = 32 bytes = 2 lines : 2 i mod 8 \in {0, 2, 4, 6}, 64 - 16 = 48 hits by rows$
2. A cache maior tem 32 768 / 64 = 512 linhas. Por linhas, cada linha de cache de 64 bytes contém 16 inteiros, e só a primeira leitura falha: 1 048 576 / 16 = 65 536 falhas. A taxa de acertos é 1 − 4/64 = 93,75%, e são transferidos 65 536 × 64 = 4 194 304 bytes, exatamente o tamanho da matriz.
  
  $\frac{32 768}{64} = 512 lines, \frac{1 048 576}{16} = 65536 misses, 65536 \times 64 = 4194304$
3. Por colunas, cada linha da matriz ocupa 4 096 bytes, ou seja, 64 linhas de cache. A linha i começa na linha de cache 64i mod 512, e uma coluna usa apenas 8 das 512 linhas. a[8][0] remove o bloco de a[0][0], muito antes de o ciclo regressar para ler a[0][1]. Todas as 1 048 576 leituras falham: são transferidos 67 108 864 bytes, 16 vezes mais.
  
  $\frac{4 096}{64} = 64 : 64 i mod 512 takes 8 values, 1048576 \times 64 = 67108864$
4. Acrescentar 16 inteiros a cada linha da matriz aumenta o seu tamanho para 4 160 bytes, ou seja, 65 linhas de cache. Como 65 e 512 são primos entre si, cada coluna passa a usar todas as 512 linhas de cache. Continua a não haver acertos: uma coluna acede a 1 024 blocos e a cache só comporta 512. Todos os blocos são removidos antes de a coluna seguinte precisar deles.
  
  $\frac{4 160}{64} = 65, g cd (65, 512) = 1, 1024 blocks > 512 lines$
Resposta

4 MiB por linhas, 64 MiB por colunas. O espaço extra distribui os blocos de cada coluna por toda a cache, mas continua a não haver acertos. Resolve os conflitos; cada coluna desta matriz, porém, ocupa mais espaço do que a cache inteira.

$4 MiB by rows, 64 MiB by columns (16 \times)$

Percurso de aprendizagem

Como um computador executa um programa

Referências (1)

The first insight's measured case, the line size in the definition, and the 8-way first-level caches in `assumes`: Ulrich Drepper, "What Every Programmer Should Know About Memory," Red Hat, Inc., version 1.0, 21 November 2007. §3.2 (p. 15), §3.3.1 (pp. 17–18), §6.2.1 (pp. 49–50).

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.