TARDIS!

Time and Relative Dimensions In Space“! Yep! Tornei-me um “Whovian”! Mas, não vou falar da série britânica aqui, e sim dos CACHES e dois conceitos fundamentais: Localidade Temporal e Localidade Espacial.

Você pode achar estranho que o “Continuum” (espaço-tempo), conceito aplicável à Física e às séries de Ficção Científica, seja aplicável também à programação. Seu processador também usa conceito semelhante no que se refere aos CACHES. Lembre-se que CACHE é uma memória intermediária entre aquela endereçável nos seus pentes de memória (e na ROM) e a acessada, internamente, pelo processador, através de uma instrução. No meio do caminho temos algumas memórias RAM, rápidas, que são divididas em “linhas”, onde cada linha tem, hoje em dia, 64 bytes de tamanho.

Isso significa que o processador carregará, da memória principal, 64 bytes para dentro do CACHE e passará a lidar com esses 64 bytes, ao invés de, toda vez que quiser ler/escrever dados na memória, torrar ciclos de clock “esperando” que o circuito de sua RAM (por exemplo) esteja pronto para receber/enviar dados… Acontece que cada um dos CACHES disponíveis no interior do processador (e os disponíveis fora dele, como o cache L3, hoje em dia) tem capacidade limitada… Estamos interessados no cache L1 (sempre!), quando falamos de performance e este tem, no máximo 64 KiB de tamanho…

Sendo o cache L1 é o mais curto dos caches, tendo apenas 1024 linhas, precisamos nos certificar que todas as linhas disponíveis estejam sendo usadas pelo maior tempo possível. Isso significa que, se todas as linhas estiverem sendo usadas, para acessar memória que não consta do cache, uma linha terá que ser escrita na memória física, externa, e outro bloco de 64 bytes terá que ser lido e colocado no lugar. Isso também significa que os seus dados têm localidade temporal, ou seja, as linhas dos caches podem não estar presente nele por muito tempo.

O macete para obter alta performance é manter as linhas mais acessadas no cache o maior tempo possível, evitando poluí-lo com trocas ou “despejos” de linhas desnecessários… Nem sempre isso é possível, já que o kernel também usa o cache e não temos nenhum controle sobre o que o kernel faz, do ponto de vista de nossos códigos no userspace.

Existe também o conceito de localidade espacial. Se uma linha tem 64 bytes de tamanho, então, se mantivermos os dados mais acessíveis o mais próximos possível, poderíamos garantir que eles estejam na mesma linha, ou “no mesmo espaço”. Isso também vale para as instruções sendo executadas pelo processador… Se mantivermos um loop dentro de uma única linha, não corremos o risco de outra linha ser usada para conter as instruções do loop e ser “despejada”, precisar ser recarregada em cada iteração do loop, desperdiçando ciclos de clock! Por esse motivo, quanto menos instruções usarmos, melhor. A mesma coisa vale para o tamanho das instruções…

O mesmo raciocínio pode ser feito com dados. Se uma estrutura tiver 64 bytes ou menos de tamanho, podemos garantir que ela esteja dentro de uma única linha de cache desde que não ultrapasse a fronteira de uma linha. Como podemos fazer isso? Já que toda linha tem 64 bytes de tamanho, o endereço linear que marca o início de uma linha sempre terá os 6 bits inferiores zerados e a linha terminará com o endereço contendo os 6 bits inferiores setados… Note que um dado em um endereço linear não necessariamente está localizado no cache. Ele só estará lá quando for acessado (mostro outro jeito mais adiante).

Eis um exemplo de um array de 64 bytes alinhado com o início de uma linha de cache:

  section .data

  global array
  align 64  ; Alinha com o início de uma
            ; linha de cache.
array:
  times 64 db 0

Aqui, é garantido que o array inteiro, de 64 bytes, estará alocado em uma única linha do cache L1 quando for acessado. No entanto, isso não é lá muito prático… Em primeiro lugar, se ficarmos alinhando tudo quanto é estruturas no início de uma linha termos muitos “buracos” em nosso segmento de dados. De fato, poderemos até mesmo ter mais “buracos” do que dados efetivos. Garantiremos que uma estrutura estrutura individual qualquer esteja toda no menor número de linhas possível, mas nosso segmento de dados poderá ficar enorme!

Em segundo lugar, o principio da localidade espacial nos indica que devemos agrupar a maior quantidade de dados possível dentro de uma única linha… Ou seja, evitarmos que seus dados cruzem a fronteira de uma linha e passem a pertencer a duas linhas… Estatisticamente, se alinharmos nossos dados de 16 em 16 bytes (\frac{1}{4} de linha), podemos conseguir esse efeito com a maioria dos dados. No entanto, pode ser prudente o alinhamento de 8 ou 4 bytes, de acordo com o tipo de dado. No exemplo anterior, o array tem 64 bytes, então faz todo sentido alinhá-lo com o início de uma linha do cache se seu acesso for crítico para performance…

Mas, e quanto ao princípio de localidade temporal? Bem… para não poluir o cache, evitando “despejos”, podemos, às vezes, usar instruções especiais que lêem/escrevem direto na memória. MOVNTA, por exemplo, é uma instrução SSE que faz o MOV “Não temporal”, ou seja, não passa pelo cache… Às vezes é útil, mas não é prudente abusar… Acessar memória diretamente implica em esperar pela leitura/escrita e isso pode ser lento! Na prática queremos usar MOVNTA apenas para evitar despejos desnecessários de pequenos blocos de dados.

Para retardar a temporalidade de uma linha, podemos fazer um prefetch, ou seja, pedir ao processador que carregue uma linha antecipadamente, com os seus 64 bytes, se eles já não estiverem no cache. Para isso existe a instrução PREFETCH, que toma um endereço como argumento. Qualquer endereço no interior da linha fará com que a linha inteira seja carregada para o cache… Mas, note… Existem 3 caches diferentes no seu processador: O L1, L2 e L3… Existem 3 instruções PREFETCH também: PREFETCHT0, PREFETCHT1, PREFETCHT2 que, em teoria, pede para o processador transfira uma linha de um cache para outro ou da memória para um dos caches… Existe também PREFETCHW, que faz a mesma coisa que o PREFETCHT0, mas prepara a linha para a escrita (apenas as linhas que foram “modificadas” são reescritas num cache de nível superior ou na memória do sistema – PREFETCHW, suponho, marca a linha como “suja”, forçando a escrita quando ela for “despejada”).

As instruções de prefetching são uma “dica” para o processador. Usar essas instruções não garante que as linhas do cache sejam preenchidas. Mas, pelo menos, informa a intenção e pode melhorar a performance um bocado… Quando você precisar forçar um prefetching, recomendo o uso de PREFETCHT0, que tentará carregar todos os caches com a linha correspondente…

Essas instruções são úteis se você tem uma grande quantidade de dados e quer organizar quais porções deverão estar presentes no cache. Por exemplo, suponha que você tenha duas matrizes 4×4, onde cada item seja do tipo float. Temos 16 floats e, portanto 64 bytes que, é claro, cabe exatamente numa linha!… Você pode querer colocar cada uma das matrizes no cache L1d antes de começar a manipulá-los… Suponha que queira multiplicar uma matriz por outra e obter uma terceira… Suponha também que as três matrizes estejam alinhadas com o início de uma linha de cache (endereço com os 6 bits inferiores zerados)… Antes de multiplicá-las você poderia fazer:

; Estou assumindo que mat1, mat2 e
; mat_result estejam alinhados com o início 
; de uma linha.
  ...
  ; faz o prefetching...
  prefetcht0 [mat1]
  prefetcht0 [mat2]
  prefetcht0 [mat_result]

  ; chama a função matrix_mult.
  lea rdi,[mat_result]
  lea rsi,[mat1]
  lea rdx,[mat2]
  call matrix_mult
  ...

Com os 3 primeiros prefetches você dá a dica ao processador de que precisa dos 3 blocos de dados nos caches. Especialmente no cache L1! Claro, se matrix_mult “consumir muita memória”, esses prefetches serão “perdidos” (temporalidade!), mas aqui estamos usando apenas 192 bytes, ou 3 linhas do cache L1, que tem 1024…

Aí está! Espaço e Tempo são importantes quando lidamos com caches.

Anúncios