Retratação: RDRAND é lerdo pacas!

Anteriormente fiz uma medição de ciclos do RDRAND com relação à chamada a função rand() – que usa o Linear Congruential Generator. O detalhe é que com pouquíssimas execuções da instrução ela é, de fato, bem rápida, mas com muitas execuções, parece, há algum problema e o processador leva quase 10 ms para executar a instrução (e isso está de acordo com a documentação da Intel).

Assim… se você quer uma garantia de aleatoriedade, use RDRAND, mas não espere grandes performances. Me desculpem pela informação meio errada.

Associatividade em caches

Confesso pra vocês que, por alguns anos, fiz uma confusão dos diabos sobre o que significa termos como “4 way set associative“. Sempre pensei nisso como se uma linha de cache fosse dividida em 4 pedaços e estava totalmente errado. O “set” do termo deveria ter chamado minha atenção.

Caches são memórias estáticas (hoje em dia, a maioria, pelo menos, contidas dentro do processador) que são bem mais rápidas que as memórias dinâmicas que estão contidas no “pentes” de memória instalados na sua placa mãe. O processador usa esses caches para acelerar o acesso à memória (evitando o acesso direto!).

Os caches são divididos em linhas. Nos processadores x86, desde o Pentium 4, pelo menos, cada linha de cache tem 64 bytes de tamanho. Não é possível lidar com menos de uma linha por vez, no que concerne os caches. Se você pedir para ler um único byte da memória, uma linha inteira (64 bytes) será carregada para o cache. Se você pedir para escrever um único byte, uma linha inteira de cache será, eventualmente, despejada para a memória, todos os 64 bytes, de uma só vez.

Cada linha é identificada por uma “marca” (uma tag) que corresponde aos bits superiores do endereço de memória usado. Os 6 bits inferiores do endereço compõem o offset dentro de uma linha. O que o processador faz quando você tentar ler/escrever num endereço é carregar uma linha inteira para o cache (L1) e marcá-la como pertencendo ao range de endereços onde os 6 bits inferiores vão de 0 até 0x3F… Daí toda leitura e escrita é feita com o processador procurando pela tag no cache e, se encontrar, o dado é escrito ou lido na linha.

Tipicamente o cache L1 (que é o cache mais próximo do processador lógico e o que mais nos interessa) tem 64 KiB de tamanho (em alguns processadores, 128 KiB ou 256 KiB). Vou assumir aqui 128 KiB… Com 128 KiB e 64 bytes por linha temos um total possível de armazenamento de 2048 linhas com tags diferentes. Quando você acessa a memória, o processador percorre todas as 2048 entradas procurando por uma tag idêntica à fornecida no endereço linear. Se achar, o acesso é feito no cache, senão, a linha é “carregada” (do cache L2).

Onde entra a associatividade de conjunto (set associativity)? Para melhorar essa pesquisa da tag alguns caches juntam mais de uma linha num conjunto de linhas, ligados (associados) à mesma tag, Ao invés de termos tag+offset, agora temos tag+way+offset. Onde way é uma indicação (um “caminho”) de uma linha em um conjunto (set) de linhas associadas a uma tag. Daí, “4 way set associative” significa que uma tag, nesse tipo de associativivdae possui 2 bits que indicam o caminho (way) para uma das 4 linhas associadas a uma tag.

O cache L1 está ligado a um processsador lógico individual e é dividido em 2 “tipos”: L1I (cache de instruções) e L1D (cache de dados). O cache L1I, em muitos processadores Intel modernos, é 4 way set assiciative, o que significa que cada tag comporta 4 linhas adjacentes ou 256 bytes. Cada linha é lidada de forma individual, mas ao alocar espaço para uma tag no cache, 4 linhas sempre serão alocadas. O cache L1D, por outro lado, é 8 way set associative. Alocação de 8 linhas por tag ou 512 bytes.

O cache L2 também costuma ser 8 way set associative e o cache L3 geralmente é chamado de full associative (ou seja, não tem o campo binário way no endereço linear – 1 tag, 1 linha).

Note que, e vou frisar isso, não é porque o cache L1D é 8 way set associative teremos o preenchimento de 8 linhas sempre que tentarmos ler/escrever um dado que não tenha uma tag no cache L1D… Apenas UMA linha é lida… mas 8 são sempre reservadas. Isso diminui, no nosso cache L1D de 128 KiB, a quantidade de tags de 2048 para 256, embora ainda tenhamos 2048 linhas disponíveis no cache.

Deu para esclarecer o que é “associatividade de conjunto” em caches?