Dois laços aninhados que visitam as mesmas células de uma matriz podem diferir por um fator de sete em faltas de cache só por qual laço fica por dentro. Esta aula compara a leitura linha a linha e coluna a coluna, depois corta uma transposição em ladrilhos para que um bloco fique no cache enquanto é usado, e mede os dois numa matriz feita com fechamentos do SPY.
Qual laço fica por dentro?
Uma matriz de n linhas e n colunas é guardada em ordem por linhas. Um laço que anda ao longo de uma linha, mudando j, lê valores vizinhos. Um laço que desce uma coluna, mudando i, pula uma linha inteira a cada passo. Os dois laços abaixo visitam as mesmas células, um com j por dentro e outro com i. Mostramos os seis primeiros endereços de uma matriz 4 por 4 de valores float64.
def row_major_trace(n): return [(i * n + j) * 8 for i in range(n) for j in range(n)]def col_major_trace(n): return [(i * n + j) * 8 for j in range(n) for i in range(n)]1print("row:", row_major_trace(4)[:6])print("col:", col_major_trace(4)[:6])
row: [0, 8, 16, 24, 32, 40] col: [0, 32, 64, 96, 8, 40]
- 1Com i por dentro, a leitura seguinte está uma linha inteira adiante (aqui 4 valores = 32 bytes).
Linha a linha os endereços sobem 8 bytes, o passo do primeiro tópico, e uma linha de cache serve oito leituras. Coluna a coluna eles pulam 32 bytes aqui, e o tamanho de uma linha inteira numa matriz maior. Agora contamos as faltas das duas ordens, num cache pequeno de 4 KB, para matrizes de 16 por 16 até 73 por 73.
for n in (16, 32, 48, 73): print(n, "x", n, "row:", count_misses(row_major_trace(n)), "col:", count_misses(col_major_trace(n)))
16 x 16 row: 32 col: 32 32 x 32 row: 128 col: 1024 48 x 48 row: 288 col: 2304 73 x 73 row: 667 col: 4573
Uma matriz de 16 por 16 tem 2 KB e cabe no cache, então depois de carregada as duas ordens custam 32 faltas, o mesmo. A partir de 32 por 32 a matriz não cabe mais, e a ordem por colunas falha em toda leitura: 1024 faltas contra 128, um fator de oito, que são os oito valores de uma linha. Em 73 por 73 o fator é quase sete. A forma dos laços não mudou; mudou o tamanho dos dados.
Trocar os laços não custa nada quando a matriz é maior que o cache e não faz nada quando ela cabe. Um teste com uma matriz pequena pode esconder o problema por completo, e o programa fica lento depois com dados reais. Meça no tamanho real.
Quando os dois laços discordam: a transposição
Às vezes nenhuma ordem de laços ajuda. A transposição B[j][i] = A[i][j] lê A e escreve B, e se os laços andam pelas linhas de A eles descem pelas colunas de B. Qualquer que seja o laço por dentro, uma das duas matrizes é percorrida com um passo grande. A cura é o ladrilhamento de laços: processar a matriz em pequenos ladrilhos quadrados, para que as poucas linhas que um ladrilho toca sejam usadas muitas vezes antes de serem removidas.
- 1Escolher um tamanho de ladrilho tPequeno o bastante para que um ladrilho de A e um de B caibam no cache.
- 2Percorrer os ladrilhosDois laços externos com passo t: ii e jj dão o canto de um ladrilho.
- 3Trabalhar dentro do ladrilhoOs dois laços internos visitam só as t por t células deste ladrilho, como antes.
- 4Passar ao próximo ladrilhoSó agora o programa deixa para trás as linhas do ladrilho antigo.
O código abaixo só lista a ordem em que as células são visitadas, para uma matriz 4 por 4, sem e com ladrilhos de 2. Com ladrilhos, o programa termina o bloco 2 por 2 do canto superior esquerdo antes de tocar qualquer outra célula.
def visit_order(n, tile=None): step = n if tile is None else tile order = [] for ii in range(0, n, step):1 for jj in range(0, n, step): for i in range(ii, min(ii + step, n)): for j in range(jj, min(jj + step, n)): order.append((i, j)) return orderprint("plain:", visit_order(4)[:8])print("tile 2:", visit_order(4, 2)[:8])
plain: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)] tile 2: [(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3)]
- 1Os dois laços externos percorrem os ladrilhos; os dois internos percorrem o interior de um ladrilho.
Passemos à transposição de verdade. Escrevemos o rastro das leituras de A e das escritas de B, com B guardada logo depois de A, e contamos as faltas para uma matriz 73 por 73 sem ladrilho e com ladrilhos de 4, 8, 16 e 32.
def transpose_trace(n, tile=None): base_b = n * n * 8 step = n if tile is None else tile trace = [] for ii in range(0, n, step): for jj in range(0, n, step): for i in range(ii, min(ii + step, n)): for j in range(jj, min(jj + step, n)): trace.append((i * n + j) * 8) trace.append(base_b + (j * n + i) * 8) return tracefor tile in (None, 4, 8, 16, 32): print("tile", tile, "misses:", count_misses(transpose_trace(73, tile)))
tile None misses: 5996 tile 4 misses: 2603 tile 8 misses: 2036 tile 16 misses: 1960 tile 32 misses: 1714
Sem ladrilhos a transposição falha 5996 vezes. Com ladrilhos de 4 já cai para 2603, e com ladrilhos de 8 a 32 fica entre 2036 e 1714, cerca de três vezes menos. Um ladrilho pequeno demais desperdiça as bordas das linhas que carrega, então o ganho cresce com o ladrilho até ele deixar de caber.
Um ladrilho ajustado para um cache de 4 KB não serve para um de 32 KB. Aqui tudo de 8 a 32 fica a menos de 20% do melhor, então um ladrilho intermediário é uma escolha segura. Quando a máquina mudar, meça de novo em vez de copiar um número.
NumPy e BLAS já multiplicam e transpõem arrays grandes em ladrilhos. Você encontra o ladrilhamento quando escreve seus próprios laços, em Numba, C++ ou Rust, ou quando um kernel próprio é mais lento que a chamada de biblioteca que ele substituiu.
O que você vai construir
O laboratório segue a aula: as duas ordens de leitura, o rastro da transposição com um ladrilho opcional, a contagem de faltas por ordem e por ladrilho, a escolha do melhor ladrilho e o estudo sobre a matriz do SPY.
- Função · perguntaBaseia-se em
- row_major_trace(n)Quais endereços uma leitura linha a linha toca?Aritmética simples
- col_major_trace(n)E uma leitura coluna a coluna?Aritmética simples
- transpose_trace(n, tile=None)Quais endereços uma transposição toca, com ou sem ladrilhos?Quatro laços aninhados
- compare_orders(n)Quão pior é a ordem por colunas?row_major_tracecol_major_trace
- misses_by_tile(n, tiles)Como os ladrilhos mudam as faltas da transposição?transpose_trace
- best_tile(n, tiles)Qual ladrilho é o melhor?misses_by_tile
- study(bars)O que o ladrilhamento ganha numa matriz de fechamentos do SPY?compare_ordersbest_tile
Próximo tópico: o ladrilhamento esconde o atraso de uma falta reutilizando linhas; a pré-busca o esconde pedindo uma linha antes de ela ser necessária. Em Pré-busca você adiciona ao cache um detector de passos e vê quais padrões de acesso ele consegue prever e quais, como um passeio aleatório numa tabela, ele não consegue.
Lab: o que é avaliado
7 tarefas · 100 pts- Leitura linha a linha10 pts
- Leitura coluna a coluna10 pts
- A transposição, com ou sem ladrilhos25 pts
- Comparar as ordens15 pts
- As faltas por ladrilho15 pts
- O melhor ladrilho10 pts
- O estudo com a matriz do SPY15 pts