Programa C para determinar os níveis e o tamanho do cache

Re-Write / Atualização completa para maior clareza (e sua sanidade, é um pouco longo demais) … ( Post antigo )

Para uma atribuição, preciso encontrar os níveis (L1, L2, …) e o tamanho de cada cache. Dadas as sugestões e o que encontrei até agora: acho que a ideia é criar matrizes de tamanhos diferentes e lê-los. Cronometrando estas operações:

sizes = [1k, 4k, 256K, ...] foreach size in sizes create array of `size` start timer for i = 0 to n // just keep accessing array arr[(i * 16) % arr.length]++ // i * 16 supposed to modify every cache line ... see link record/print time 

ATUALIZADO (28 de setembro às 18:57 UTC + 8)

Veja também fonte completa

Ok, agora, seguindo o conselho de @mah, eu poderia ter corrigido o problema da relação SNR … e também encontrei um método para sincronizar meu código ( wall_clock_time partir de um código de exemplo de laboratório)

No entanto, parece que estou obtendo resultados incorretos: estou em um Intel Core i3 2100: [ SPECS ]

  • L1: 2 x 32K
  • L2: 2 x 256 K
  • L3: 3MB

Os resultados que obtive, em um gráfico:

lengthMod: 1KB a 512K

insira a descrição da imagem aqui

A base do primeiro pico é 32K … razoável … o segundo é 384K … por quê? Estou esperando 256?

lengthMod: 512k a 4MB

insira a descrição da imagem aqui

Então, por que esse intervalo pode estar uma bagunça?


Eu também li sobre pré-busca ou interferência de outros aplicativos, então fechei o maior número possível de coisas enquanto o script está rodando, aparece consistentemente (através de múltiplas execuções) que os dados de 1MB e acima são sempre tão confusos?

O tempo que leva para medir o seu tempo (isto é, o tempo apenas para chamar a function clock ()) é muitas (muitas, muitas, muitas vezes ….) vezes maiores que o tempo que leva para executar arr[(i*16)&lengthMod]++ . Esta relação sinal / ruído extremamente baixa (entre outras armadilhas prováveis) torna o seu plano impraticável. Uma grande parte do problema é que você está tentando medir uma única iteração do loop; o código de exemplo vinculado está tentando medir um conjunto completo de iterações (leia o relógio antes de iniciar o loop; leia-o novamente após sair do loop; não use printf () dentro do loop).

Se o seu loop for grande o suficiente, você poderá superar o problema da relação sinal-ruído.

Quanto a “qual elemento está sendo incrementado”; arr é um endereço de um buffer de 1MB; arr[(i * 16) & lengthMod]++; faz com que (i * 16) * lengthMod gere um deslocamento desse endereço; esse deslocamento é o endereço do int que é incrementado. Você está realizando uma mudança (i * 16 irá se transformar em i << 4), uma lógica e, uma adição, então uma leitura / adição / gravação ou um único incremento, dependendo da sua CPU).

Edit: Como descrito, o seu código sofre de um SNR pobre (relação sinal-ruído), devido às velocidades relativas de access à memory (cache ou sem cache) e chamando funções apenas para medir o tempo. Para obter os horários que você está recebendo atualmente, presumo que você modificou o código para se parecer com algo como:

 int main() { int steps = 64 * 1024 * 1024; int arr[1024 * 1024]; int lengthMod = (1024 * 1024) - 1; int i; double timeTaken; clock_t start; start = clock(); for (i = 0; i < steps; i++) { arr[(i * 16) & lengthMod]++; } timeTaken = (double)(clock() - start)/CLOCKS_PER_SEC; printf("Time for %d: %.12f \n", i, timeTaken); } 

Isso move a medição para fora do loop, então você não está medindo um único access (o que seria realmente impossível), mas sim você está medindo os accesss das steps .

Você está livre para aumentar as steps conforme necessário e isso terá um impacto direto nos seus horários. Como os tempos que você está recebendo são muito próximos e, em alguns casos, até mesmo invertidos (seu tempo oscila entre os tamanhos, o que provavelmente não é causado pelo cache), você pode tentar alterar o valor das steps para 256 * 1024 * 1024 ou até mesmo maior.

OBSERVAÇÃO: Você pode executar steps tão grandes quanto possível em um int assinado (que deve ser grande o suficiente), desde que o lógico e garanta que você o envolva no seu buffer.

Após 10 minutos pesquisando o manual de instruções da Intel e outros 10 minutos de codificação, desenvolvi isso (para processadores baseados na Intel):

 void i386_cpuid_caches () { int i; for (i = 0; i < 32; i++) { // Variables to hold the contents of the 4 i386 legacy registers uint32_t eax, ebx, ecx, edx; eax = 4; // get cache info ecx = i; // cache id __asm__ ( "cpuid" // call i386 cpuid instruction : "+a" (eax) // contains the cpuid command code, 4 for cache query , "=b" (ebx) , "+c" (ecx) // contains the cache id , "=d" (edx) ); // generates output in 4 registers eax, ebx, ecx and edx // taken from http://download.intel.com/products/processor/manual/325462.pdf Vol. 2A 3-149 int cache_type = eax & 0x1F; if (cache_type == 0) // end of valid cache identifiers break; char * cache_type_string; switch (cache_type) { case 1: cache_type_string = "Data Cache"; break; case 2: cache_type_string = "Instruction Cache"; break; case 3: cache_type_string = "Unified Cache"; break; default: cache_type_string = "Unknown Type Cache"; break; } int cache_level = (eax >>= 5) & 0x7; int cache_is_self_initializing = (eax >>= 3) & 0x1; // does not need SW initialization int cache_is_fully_associative = (eax >>= 1) & 0x1; // taken from http://download.intel.com/products/processor/manual/325462.pdf 3-166 Vol. 2A // ebx contains 3 integers of 10, 10 and 12 bits respectively unsigned int cache_sets = ecx + 1; unsigned int cache_coherency_line_size = (ebx & 0xFFF) + 1; unsigned int cache_physical_line_partitions = ((ebx >>= 12) & 0x3FF) + 1; unsigned int cache_ways_of_associativity = ((ebx >>= 10) & 0x3FF) + 1; // Total cache size is the product size_t cache_total_size = cache_ways_of_associativity * cache_physical_line_partitions * cache_coherency_line_size * cache_sets; printf( "Cache ID %d:\n" "- Level: %d\n" "- Type: %s\n" "- Sets: %d\n" "- System Coherency Line Size: %d bytes\n" "- Physical Line partitions: %d\n" "- Ways of associativity: %d\n" "- Total Size: %zu bytes (%zu kb)\n" "- Is fully associative: %s\n" "- Is Self Initializing: %s\n" "\n" , i , cache_level , cache_type_string , cache_sets , cache_coherency_line_size , cache_physical_line_partitions , cache_ways_of_associativity , cache_total_size, cache_total_size >> 10 , cache_is_fully_associative ? "true" : "false" , cache_is_self_initializing ? "true" : "false" ); } } 

Referência: http://download.intel.com/products/processor/manual/325462.pdf 3-166 vol. 2A

Isso é muito mais confiável do que medir latências de cache, já que é praticamente impossível desativar a pré-busca de cache em um processador moderno. Se você precisar de informações semelhantes para uma arquitetura de processador diferente, será necessário consultar o respectivo manual.

Editar: Adicionado descritor de tipo de cache. Edit2: Adicionado o indicador de nível de cache. Edit3: Adicionado mais documentação.

Eu sei isso! (Na realidade, é muito complicado por causa da pré-busca)

  for (times = 0; times < Max; time++) /* many times*/ for (i=0; i < ArraySize; i = i + Stride) dummy = A[i]; /* touch an item in the array */ 

Alterar stride permite testar as propriedades dos caches. Ao olhar para um gráfico, você receberá suas respostas.

Veja os slides 35-42 http://www.it.uu.se/edu/course/homepage/avdark/ht11/slides/11_Memory_and_optimization-1.pdf

Erik Hagersten é um professor muito bom (e também muito competente, foi o principal arquiteto do sol em algum momento), então dê uma olhada no resto de seus slides para maiores explicações!

Para responder a sua pergunta de números estranhos acima de 1MB, é bem simples; políticas de evicção de cache que têm a ver com a previsão de ramificação e o fato de que o cache L3 é compartilhado entre os núcleos.

Um Core i3 tem uma estrutura de cache muito interessante. Na verdade, qualquer processador moderno faz. Você deve ler sobre eles na wikipedia; existem todos os tipos de maneiras para ele decidir “bem, eu provavelmente não precisarei disso …” então ele pode dizer “eu colocarei no cache da vítima” ou qualquer outra coisa. Os intervalos de cache L1-2-3 podem ser muito complexos com base em um grande número de fatores e nas decisões de design individuais feitas.

Além disso, todas essas decisões e mais (veja artigos da Wikipedia sobre o assunto) precisam ser sincronizadas entre os caches dos dois núcleos. Os methods para sincronizar o cache L3 compartilhado com caches L1 e L2 separadas podem ser feios, eles podem envolver o rastreamento de volta e refazer cálculos ou outros methods. É altamente improvável que você tenha um segundo núcleo completamente livre e nada competindo pelo espaço de cache L3 e causando estranheza na synchronization.

Em geral, se você está trabalhando em dados, digamos, convolutando um kernel, você quer ter certeza de que ele se encheckbox dentro do cache L1 e moldar seu algoritmo em torno disso. O cache L3 não serve para trabalhar em um dataset do jeito que você está fazendo (embora seja melhor que a memory principal!)

Eu juro que se eu tivesse que implementar algoritmos de cache, eu enlouqueceria.

Para o benchmarking com passos variados, você pode tentar lat_mem_rd do pacote lmbench, é open-source: http://www.bitmover.com/lmbench/lat_mem_rd.8.html

Eu tinha postado o meu porto para o Windows para http://habrahabr.ru/post/111876/ – é bastante longo para ser copypasted aqui. Isso é de dois anos atrás, eu não testei com CPUs modernas.

Para janelas, você pode usar o método GetLogicalProcessorInformation .

Para o linux, você pode usar o sysconf() . Você pode encontrar argumentos válidos para o sysconf em /usr/include/unistd.h ou /usr/include/bits/confname.h