Qual é o custo de um Cache Miss L1?
https://stackoverflow.com/questions/1126529
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Editar : Para fins de referência (se alguém se depara com esta questão), Igor Ostrovsky escreveu um grande post sobre erros de cache. Ele discute várias questões e programas de diferentes números de exemplo. Fim Editar
Eu fiz alguma <long story goes here> testando e estou querendo saber se uma diferença de desempenho é devido a erros de cache de memória. O código a seguir demonstra o problema e ferve-la para a parte momento crítico. O código a seguir tem um par de voltas que a memória visita em ordem aleatória e, em seguida, em ordem de endereço ascendente.
Eu corri-lo em uma máquina XP (compilado com VS2005: cl / O2) e em uma caixa de Linux (gcc -Os). Ambos produziram tempos semelhantes. Estes tempos são em milissegundos. Eu acredito que todos os circuitos estão em execução e não são otimizados para fora (caso contrário ele seria executado “instantaneamente”).
*** Testing 20000 nodes Total Ordered Time: 888.822899 Total Random Time: 2155.846268
Será que estes números fazem sentido? É a diferença principalmente devido a erros de cache L1 ou é algo mais acontecendo também? Há 20.000 ^ 2 acessos à memória e se cada um fosse um erro de cache, que é de cerca de 3,2 nanossegundos por falta. O XP (P4) máquina I testado em é 3.2GHz e eu suspeito que (mas não sei) tem uma cache de 32KB L1 e 512 KB L2. Com 20.000 entradas (80KB), presumo que não há um número significativo de acidentes L2. Portanto, este seria (3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss. Isso parece alto para mim. Talvez não seja, ou talvez minha matemática é ruim. Eu tentei medir erros de cache com VTune, mas eu tenho um BSOD. E agora eu não posso obtê-lo para se conectar ao servidor de licenças (grrrr).
typedef struct stItem
{
long lData;
//char acPad[20];
} LIST_NODE;
#if defined( WIN32 )
void StartTimer( LONGLONG *pt1 )
{
QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}
void StopTimer( LONGLONG t1, double *pdMS )
{
LONGLONG t2, llFreq;
QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
QueryPerformanceFrequency( (LARGE_INTEGER*)&llFreq );
*pdMS = ((double)( t2 - t1 ) / (double)llFreq) * 1000.0;
}
#else
// doesn't need 64-bit integer in this case
void StartTimer( LONGLONG *pt1 )
{
// Just use clock(), this test doesn't need higher resolution
*pt1 = clock();
}
void StopTimer( LONGLONG t1, double *pdMS )
{
LONGLONG t2 = clock();
*pdMS = (double)( t2 - t1 ) / ( CLOCKS_PER_SEC / 1000 );
}
#endif
long longrand()
{
#if defined( WIN32 )
// Stupid cheesy way to make sure it is not just a 16-bit rand value
return ( rand() << 16 ) | rand();
#else
return rand();
#endif
}
// get random value in the given range
int randint( int m, int n )
{
int ret = longrand() % ( n - m + 1 );
return ret + m;
}
// I think I got this out of Programming Pearls (Bentley).
void ShuffleArray
(
long *plShuffle, // (O) return array of "randomly" ordered integers
long lNumItems // (I) length of array
)
{
long i;
long j;
long t;
for ( i = 0; i < lNumItems; i++ )
plShuffle[i] = i;
for ( i = 0; i < lNumItems; i++ )
{
j = randint( i, lNumItems - 1 );
t = plShuffle[i];
plShuffle[i] = plShuffle[j];
plShuffle[j] = t;
}
}
int main( int argc, char* argv[] )
{
long *plDataValues;
LIST_NODE *pstNodes;
long lNumItems = 20000;
long i, j;
LONGLONG t1; // for timing
double dms;
if ( argc > 1 && atoi(argv[1]) > 0 )
lNumItems = atoi( argv[1] );
printf( "\n\n*** Testing %u nodes\n", lNumItems );
srand( (unsigned int)time( 0 ));
// allocate the nodes as one single chunk of memory
pstNodes = (LIST_NODE*)malloc( lNumItems * sizeof( LIST_NODE ));
assert( pstNodes != NULL );
// Create an array that gives the access order for the nodes
plDataValues = (long*)malloc( lNumItems * sizeof( long ));
assert( plDataValues != NULL );
// Access the data in order
for ( i = 0; i < lNumItems; i++ )
plDataValues[i] = i;
StartTimer( &t1 );
// Loop through and access the memory a bunch of times
for ( j = 0; j < lNumItems; j++ )
{
for ( i = 0; i < lNumItems; i++ )
{
pstNodes[plDataValues[i]].lData = i * j;
}
}
StopTimer( t1, &dms );
printf( "Total Ordered Time: %f\n", dms );
// now access the array positions in a "random" order
ShuffleArray( plDataValues, lNumItems );
StartTimer( &t1 );
for ( j = 0; j < lNumItems; j++ )
{
for ( i = 0; i < lNumItems; i++ )
{
pstNodes[plDataValues[i]].lData = i * j;
}
}
StopTimer( t1, &dms );
printf( "Total Random Time: %f\n", dms );
}
Solução
Embora eu não possa oferecer uma resposta para saber se ou não os números fazem sentido (não estou bem versado nas latências de cache, mas para o registro ~ 10 ciclo de cache L1 Misses soa sobre a direita), posso lhe oferecer Cachegrind como uma ferramenta para ajudá-lo a realmente ver as diferenças de o desempenho do cache entre os 2 testes.
Cachegrind é uma ferramenta Valgrind (quadro que alimenta o sempre-linda memcheck) que perfis de cache e bate filial / erra. Ele lhe dará uma idéia de quantas cache de acessos / acidentes na verdade você está recebendo em seu programa.
Outras dicas
Aqui é uma tentativa de fornecer uma visão sobre o custo relativo de erros de cache, por analogia com bicarbonato de biscoitos de chocolate ...
Suas mãos são seus registros. Demora 1 segundo para cair gotas de chocolate na massa.
O balcão da cozinha é o seu cache L1, doze vezes mais lento do que registros. Demora 12 x 1 = 12 segundos para o passo para o balcão, pegar o saco de nozes, e esvaziar algum em seu mão.
O frigorífico é o cache L2, quatro vezes mais lento do que L1. Leva 4 x 12 = 48 segundos para caminhar até a geladeira, abri-lo, mova sobras da noite passada fora do caminho, take uma caixa de ovos, abra a embalagem, coloque 3 ovos em cima do balcão, e colocar a parte de trás da caixa na geladeira.
O armário é o cache L3, três vezes mais lento do que L2. É preciso 3 x 48 = 2 minutos e 24 segundos para dar três passos para o armário, curvar-se, abra a porta, raiz ao redor para encontrar a lata de abastecimento cozimento, extraí-lo do armário, abri-lo, cavar para encontrar o fermento em pó, coloque-o sobre o balcão e varrer a bagunça que você derramado no chão.
E a memória principal? Essa é a loja da esquina, 5 vezes mais lento do que L3. Demora 5 x 2:24 = 12 minutos para encontrar sua carteira, colocar seus sapatos e jaqueta, traço na rua, pegar um litro de leite, casa traço , tirar os sapatos e jaqueta, e voltar para a cozinha.
Note que todas estes acessos são constantes complexidade - O (1) - mas as diferenças entre eles pode ter um enorme impacto no desempenho. Otimizando puramente para big-O complexidade é como decidir se deseja adicionar gotas de chocolate à massa 1 de cada vez ou 10 de cada vez, mas esquecendo-se de colocá-los em sua lista de compras.
Moral da história:. Organize sua acessos à memória assim que o CPU tem que ir para mantimentos tão raramente quanto possível
Os números foram retirados do CPU Cache Flushing Falácia post, o que indica que para um determinado 2012-era processador Intel, o seguinte é verdadeiro:
- registo de acesso = 4 instruções por ciclo
- L1 latência = 3 ciclos (12 x registo)
- L2 latência = 12 ciclos (4 x L1, 48 x registo)
- L3 latência = 38 ciclos (3 x L2, L1 12 x, 144 x registo)
- DRAM latência = 65 ns = 195 ciclos de um CPU de 3 GHz (5 x L3, 15 x L2, L1 60 x, 720 x registo)
O Galeria de processador de efeitos Cache também faz boa leitura em este tema.
3.2ns para um cache L1 falta é inteiramente plausível. Para efeito de comparação, em um determinado moderna multicore PowerPC CPU, um L1 falta é de cerca de 40 ciclos - um pouco mais para alguns núcleos do que outros, dependendo de como eles estão longe de cache L2 (sim realmente) . Um L2 falta é , pelo menos 600 ciclos.
Cache é tudo no desempenho; CPUs são muito mais rápido do que a memória agora que você está realmente quase otimização para o barramento de memória em vez do núcleo.
Bem, sim, que se parece com ele será principalmente L1 cache misses.
10 ciclos para um cache L1 falta faz som sobre razoável, provavelmente um pouco no lado de baixo.
A leitura da RAM vai levar da ordem de 100s ou pode ser ainda 1000s (Am cansado demais para tentar fazer as contas agora;).) De ciclos por isso ainda é uma enorme vitória sobre que
Se você planeja usar cachegrind, por favor nota que é apenas um simulador de cache hit / falta. Não vai ser sempre precisas. Por exemplo: se você acessar alguma posição de memória, dizer 0x1234 em um loop 1000 vezes, cachegrind sempre mostrar-lhe que havia apenas um cache miss (primeiro acesso), mesmo se você tem algo como:
CLFLUSH 0x1234 em seu loop.
Em x86, isso fará com que todos os erros de cache 1000.
Alguns números para um P4 3.4GHz de uma corrida Lavalys Everest:
- L1 dcache é 8K (cacheline 64 bytes)
- L2 é 512K
- L1 buscar a latência é de 2 ciclos
- L2 buscar a latência é de cerca do dobro do que você está vendo: 20 ciclos
Mais aqui: http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt
(para as latências olhar para o fundo da página)
É difícil dizer nada com certeza, sem muito mais testes, mas na minha experiência que escala de diferença definitivamente pode ser atribuído ao L1 CPU e / ou cache L2, especialmente em um cenário com acesso aleatório. Você provavelmente poderia piorar ainda mais, garantindo que cada acesso é pelo menos alguma distância mínima do passado.
A coisa mais fácil a fazer é tirar uma fotografia em escala da cpu alvo e medir fisicamente a distância entre o núcleo e cache de nível 1. Multiplique essa distância pelos elétrons distância pode viajar por segundo em cobre. Em seguida, descobrir quantas relógio ciclos você pode ter no mesmo tempo. Esse é o número mínimo de ciclos de CPU você vai perder em um cache L1 falta.
Você também pode trabalhar fora o custo mínimo de buscar dados de RAM em termos do número de ciclos de CPU desperdiçado da mesma forma. Você pode se surpreender.
Observe que o que você está vendo aqui definitivamente tem algo a ver com o cache-acidentes (seja ele L1 ou ambos L1 e L2), porque normalmente o cache irá retirar dados na mesma linha de cache uma vez que você acessar qualquer coisa em que o cache -line exigindo menos viagens para a RAM.
No entanto, o que provavelmente você está vendo também é o fato de RAM (mesmo que seja chamadas Random Access Memory) ainda preferres acesso à memória linear.
