Por que há um enorme desempenho atingido na multiplicação de matriz 2048x2048 versus 2047x2047?

Estou fazendo alguns testes comparativos de multiplicação de matrizes, como mencionado anteriormente em Por que o MATLAB é tão rápido na multiplicação de matrizes?

Agora, tenho outro problema: ao multiplicar duas matrizes de 2048x2048, há uma grande diferença entre C # e outras. Quando tento multiplicar apenas matrizes 2047x2047, parece normal. Também foram adicionados outros por compaixão.

1024x1024 - 10 segundos.

1027x1027 - 10 segundos.

2047x2047 - 90 segundos.

2048x2048 - 300 segundos.

2049x2049 - 91 segundos. (atualizar)

2500x2500 - 166 segundos

Essa é a diferença de três minutos e meio para o caso 2k por 2k.

usando matrizes 2dim

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];

//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k];
     }
     matice3[j, k] = temp;
   }
 }

Provavelmente isso tem a ver com conflitos no cache L2.

As falhas de cache no matice1 não são o problema porque são acessadas sequencialmente. No entanto, para o matice2, se uma coluna completa couber em L2 (ou seja, quando você acessa o matice2 [0, 0], matice2 [1, 0], matice2 [2, 0] ... etc, nada é despejado), não há problema com o cache também falha com o matice2.

Agora, para aprofundar o funcionamento dos caches, se o endereço de bytes da sua variável for X, a linha de cache seria (X >> 6) e (L - 1). Onde L é o número total de linhas de cache em seu cache. L é sempre a potência de 2. Os seis vêm do fato de que 2 ^ 6 == 64 bytes é o tamanho padrão da linha de cache.

Agora, o que isso significa? Bem, isso significa que se eu tiver o endereço X e o endereço Y e (X >> 6) - (Y >> 6) for divisível por L (ou seja, uma grande potência de 2), eles serão armazenados no mesmo cache.

Agora, voltando ao seu problema, qual é a diferença entre 2048 e 2049,

quando 2048 for do seu tamanho:

se você usar & matice2 [x, k] e & matice2 [y, k], a diferença (& matice2 [x, k] >> 6) - (& matice2 [y, k] >> 6) será divisível até 2048 * 4 (tamanho de flutuador). Portanto, uma grande potência de 2.

Assim, dependendo do tamanho do seu L2, você terá muitos conflitos de linha de cache e utilizará apenas uma pequena parte do seu L2 para armazenar uma coluna, assim, na verdade, você não poderá armazenar a coluna completa no cache, obtendo um desempenho ruim. .

Quando o tamanho é 2049, a diferença é 2049 * 4, que não é a potência 2, portanto, você terá menos conflitos e sua coluna caberá com segurança no cache.

Agora, para testar essa teoria, há algumas coisas que você pode fazer:

Aloque sua matriz matice2 como esta matice2 [razmor, 4096] e execute com razmor = 1024, 1025 ou qualquer tamanho, e você verá um desempenho muito ruim comparado ao que tinha antes. Isso ocorre porque você alinha com força todas as colunas para entrar em conflito.

Em seguida, tente o matice2 [razmor, 4097] e execute-o com qualquer tamanho e você verá um desempenho muito melhor.

Provavelmente um efeito de cache. Com dimensões de matriz com grandes potências de dois e um tamanho de cache que também é uma potência de dois, você pode acabar usando apenas uma pequena fração do cache L1, tornando as coisas mais lentas. A multiplicação de matriz ingênua geralmente é limitada pela necessidade de buscar dados no cache. Os algoritmos otimizados usando o recurso lado a lado (ou algoritmos que ignoram o cache) se concentram em fazer melhor uso do cache L1.

Se você cronometrar outros pares (2 ^ n-1,2 ^ n), espero que você veja efeitos semelhantes.

Para explicar mais detalhadamente, no loop interno, onde você acessa o matice2 [m, k], é provável que o matice2 [m, k] e o matice2 [m + 1, k] sejam deslocados um do outro em 2048 * sizeof (float) e, portanto, mapeie para o mesmo índice no cache L1. Com um cache associativo N-way, você normalmente terá de 1 a 8 locais de cache para todos eles. Assim, quase todos esses acessos acionarão uma remoção de cache L1 e a busca de dados de um cache mais lento ou da memória principal.

Isso pode ter a ver com o tamanho do seu cache da CPU. Se duas linhas da matriz não couberem, você perderá tempo trocando elementos da RAM. Os elementos 4095 extras podem ser suficientes para impedir o encaixe das linhas.

No seu caso, 2 linhas para 2047 matrizes 2d estão dentro de 16 KB de memória (assumindo tipos de 32 bits). Por exemplo, se você tiver um cache L1 (mais próximo da CPU no barramento) de 64 KB, poderá caber pelo menos 4 linhas (de 2047 * 32) no cache de uma só vez. Com as linhas mais longas, se houver algum preenchimento necessário que empurre os pares de linhas além de 16 KB, as coisas começam a ficar confusas. Além disso, toda vez que você sente falta do cache, a troca de dados de outro cache ou memória principal atrasa as coisas.

Meu palpite é que a variação nos tempos de execução observados nas matrizes de tamanhos diferentes é afetada pela eficácia com que o sistema operacional pode usar o cache disponível (e algumas combinações são problemáticas). Claro que tudo isso é uma simplificação grosseira da minha parte.

Louis Brandy escreveu dois posts de blog analisando exatamente esse problema:

Mais loucura no cache e desempenho computacional - Um estudo de caso para iniciantes com algumas estatísticas interessantes e tentativas de explicar o comportamento em mais detalhes, na verdade se resume a limitações de tamanho do cache.

Dado que o tempo está caindo em tamanhos maiores, não seria mais provável que houvesse conflitos de cache, especialmente com potências de 2 para os tamanhos problemáticos de matrizes? Não sou especialista em questões de Cache, mas excelente informações sobre problemas de desempenho relacionados de cache aqui .

Como você está acessando a matice2matriz verticalmente, ela será trocada dentro e fora do cache muito mais. Se você espelhar o array na diagonal, para poder acessá-lo usando em [k,m]vez de [m,k], o código será executado muito mais rápido.

Testei isso para matrizes 1024x1024, e é duas vezes mais rápido. Para matrizes 2048x2048, é cerca de dez vezes mais rápido.

Alias ​​de cache

Ou thrashing de cache , se eu puder cunhar um termo.

Os caches funcionam indexando com bits de baixa ordem e marcando com bits de alta ordem.

Imagem que seu cache possui 4 palavras e sua matriz é 4 x 4. Quando uma coluna é acessada e a linha possui uma potência de dois, então cada elemento da coluna na memória será mapeado para o mesmo elemento de cache.

Um poder de dois-mais-um é realmente ótimo para esse problema. Cada novo elemento da coluna será mapeado para o próximo slot de cache exatamente como se estivesse acessando por linha.

Na vida real, uma tag cobre vários endereços sequencialmente crescentes que armazenam em cache vários elementos adjacentes em uma linha. Ao compensar o intervalo para o qual cada nova linha é mapeada, atravessar a coluna não substitui a entrada anterior. Quando a próxima coluna for percorrida, o cache inteiro será preenchido com linhas diferentes e cada seção de linha que se encaixar no cache será atingida por várias colunas.

Como o cache é muito mais rápido que a DRAM (principalmente por estar no chip), a taxa de acertos é tudo.

Parece que você atingiu um limite de tamanho de cache ou talvez tenha alguns problemas de repetibilidade em seus horários.

Qualquer que seja o problema, você simplesmente não deve escrever a multiplicação de matrizes em C # e, em vez disso, usar uma versão otimizada do BLAS. Esse tamanho de matriz deve ser multiplicado em menos de um segundo em qualquer máquina moderna.

A utilização eficaz da hierarquia de cache é muito importante. Você precisa garantir que as matrizes multidimensionais possuam dados em uma boa organização, o que pode ser realizado por lado a lado . Para fazer isso, você precisará armazenar a matriz 2D como uma matriz 1D, juntamente com um mecanismo de indexação. O problema com o método tradicional é que, embora dois elementos de matriz adjacentes que estão na mesma linha estejam próximos um do outro na memória, dois elementos adjacentes na mesma coluna serão separados por elementos W na memória, onde W é o número de colunas . O lado a lado pode fazer uma diferença de desempenho de dez a dez.

Eu suspeito que é o resultado de algo chamado " inundação sequencial ". O que é isso é que você está tentando fazer um loop pela lista de objetos que é um pouco maior que o tamanho do cache, portanto, cada solicitação para uma lista (matriz) deve ser feita a partir da ram e você não obterá um único cache acertar.

No seu caso, você está repetindo suas matrizes 2048 índices 2048 vezes, mas você só tem espaço para 2047 (possivelmente devido a alguma sobrecarga da estrutura da matriz), portanto, toda vez que você acessa uma posição da matriz, ela precisa obter essa posição da matriz do carneiro. Em seguida, ele é armazenado no cache, mas logo antes de ser usado novamente, é descartado. Portanto, o cache é essencialmente inútil, levando a um tempo de execução muito maior.