Como memória cache funciona?

Question

Hoje, quando eu estava na aula de organização de computadores, professor falou sobre algo interessante para mim. Quando se trata de falar sobre por que obras de memória cache, ele disse que:

for (i=0; i<M; i++)
   for(j=0; j<N; j++)
      X[i][j] = X[i][j] + K; //X is double(8 bytes)

não é bom para mudar a primeira linha com o segundo. Qual é a sua opinião sobre este assunto? E por que é assim?

Answer 1

localidade de referência. Como os dados são armazenados por linhas, para cada fileira das colunas j são em endereços de memória adjacentes. O sistema operacional será tipicamente carregar uma página inteira da memória para as referências de cache e de endereços adjacentes provavelmente vai se referir a essa mesma página. Se você incrementa pelo índice de linha no loop interno é possível que estas linhas estarão em páginas diferentes (uma vez que eles são separados por j duplica cada) e da cache pode ter que constantemente trazer e jogar fora páginas de memória à medida que as referências os dados. Isso é chamado de surra e é ruim para o desempenho.

Na prática e com maiores, caches modernos, os tamanhos das linhas / colunas precisaria ser razoavelmente grande antes que este iria entrar em jogo, mas ainda é uma boa prática.

[EDIT] A resposta acima é específico para C e podem ser diferentes para outros idiomas. O único que eu sei que é diferente é Fortran. armazena Fortran coisas em grande ordem da coluna (acima é fileira major) e seria correta para alterar a ordem das declarações em Fortran. Se você quiser / eficiência necessidade, é importante saber como o seu armazenamento de dados implementos linguísticas.

Answer 2

Há um papel muito bom por Ulrich Drepper da Red Hat e fama glibc, O que cada programador deve saber Sobre Memória . Uma seção discutido caches em grande detalhe. Por exemplo, existem efeitos de cache em sistemas SMP onde CPUs podem acabar debatendo propriedade de uma linha de volta de cache modificado e para trás, muito prejudicar o desempenho.

Answer 3

É como que becauses caches como localidade. O mesmo número de memória acessada, mas espaçados mais distante, vai bater diferentes "linhas" de cache, ou pode até mesmo perder o cache completamente. Por isso, é bom, sempre que você tem a escolha, para organizar os dados para que os acessos que são susceptíveis de acontecer perto uns dos outros no tempo, também fazê-lo no espaço. Isso aumenta a chance de um acerto de cache, e dá-lhe mais desempenho.

Há, naturalmente, uma riqueza de informações sobre este tópico disponíveis, ver, por exemplo esta entrada wikipedia da localidade de referência. Ou, eu acho, seu próprio livro de texto do curso. :)

Answer 4

C, matrizes n-dimensionais são linha principal, o que significa que o último índice para a matriz representa espaços adjacentes em memória. Isto é diferente do que alguns outros idiomas, Fortran, por exemplo, que são coluna principal. Em FORTRAN, é mais eficiente para percorrer uma matriz 2D como este:

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo

Answer 5

A memória cache é uma memória muito rápido e muito caro que fica perto da CPU. Ao invés de buscar um pequeno pedaço de dados da RAM cada vez, a CPU busca um pedaço de dados e armazena em cache. A aposta é que, se você acabou de ler um byte, então o próximo byte que você lê é provável que seja logo depois. Se este for o caso, então ele pode vir a partir do cache.

Ao estabelecer o seu ciclo como você tem, você ler os bytes na ordem em que eles são armazenados na memória. Isso significa que eles estão no cache, e podem ser lidos muito rapidamente pela CPU. Se você trocou em torno de linhas 1 e 2, então você ler cada "N" bytes de cada vez em torno do laço. Os bytes que você está lendo não são mais consecutiva na memória, e assim eles não podem estar no cache. A CPU tem que buscá-los a partir da (mais lento) RAM, e assim o seu desempenho diminui.