Problemy z szybkością mnożenia macierzy

Question

Badam, jak pomyłki pamięci podręcznej wpływają na szybkość obliczeń. Wiem, że istnieje wiele algorytmów lepiej do mnożenia dwóch macierzy (nawet prostą wymianę dwóch pętlach poniżej by pomóc), ale należy rozważyć ten kod:

float a[N][N]; 
float b[N][N]; 
float c[N][N]; 
// ... 
{ 
    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; j++) { 
      float sum = 0.0; 
      for (int k = 0; k < N; k++) { 
       sum = sum + a[i][k] * b[k][j]; 
      } 
      c[i][j] = sum; 
     } 
    } 
} 

Mam zrekompilowane ten kod dla wielu wartości N i mierzone czas, aby to uruchomić. Spodziewałem się nagłego wzrostu czasu około N=1250, w którym to punkcie macierz c nie pasuje już do pamięci podręcznej (rozmiar c to wtedy 1250*1250*sizeof(float)=6250000, czyli około 6 MB, co jest wielkością mojej pamięci podręcznej L3).

Rzeczywiście, ogólna tendencja jest taka, że ​​po tym punkcie czas średnia z grubsza potroi się w porównaniu do ekstrapolowanego czasu sprzed. Ale wartość N%8 wydaje się mieć ogromny wpływ na wynik. Na przykład:

1601 - 11.237548 
1602 - 7.679103 
1603 - 12.216982 
1604 - 6.283644 
1605 - 11.360517 
1606 - 7.486021 
1607 - 11.292025 
1608 - 5.794537 
1609 - 11.469469 
1610 - 7.581660 
1611 - 11.367203 
1612 - 6.126014 
1613 - 11.730543 
1614 - 7.632121 
1615 - 11.773091 
1616 - 5.778463 
1617 - 11.556687 
1618 - 7.682941 
1619 - 11.576068 
1620 - 6.273122 
1621 - 11.635411 
1622 - 7.804220 
1623 - 12.053517 
1624 - 6.008985 

Do pewnego czasu myślałem te mogą być problemy wyrównania - rzędy dowolnej macierzy są wyrównane do 32 bajtów kiedy N%8==0 (pierwsze pytanie - dlaczego 32 bajty w szczególności instrukcje SSE, takie jak movaps może? pracować na wyrównanych danych 16B).

Innym pomysłem było, że może to być w jakiś sposób połączone ze zjednoczeniem pamięci podręcznej (8-ścieżkowe dla L1 i L2 oraz 12-drogowe dla L3 na mojej maszynie).

Ale potem zauważyłem, że dla pewnych wartości, takich jak N1536, istnieje niespodziewane skoki (mimo że dostosowanie powinno być doskonała w tych przypadkach - 1536==256*6 The asocjatywność bycia nie problem zbyt - 1536==128*12==192*8). Na przykład:

1504 - 4.644781 
1512 - 4.794254 
1520 - 4.768555 
1528 - 4.884714 
1536 - 7.949040 
1544 - 5.162613 
1552 - 5.083331 
1560 - 5.388706 

Czas jest dość spójny, więc skoki obciążenia procesora nie stanowią problemu. Kompiluję kod z włączonymi optymalizacjami (-O2). Moje pomysły kończą się niestety. Jaki może być powód takiego zachowania?

Answer 1

Najważniejszy dla twojego przykładu - rozmiar linii pamięci podręcznej procesora. Dla procesora jest to zazwyczaj 64 bajty. Nawet jeśli twój program odczytuje lub zapisuje 1 bajt, CPU odczytuje/zapisuje dla całej linii (64 bajty). Dlatego jeśli twój program trafi w linie pamięci podręcznej, twoje wyniki są dobre. Jeśli go brakuje, istnieje dodatkowy napływ pamięci do odczytu/zapisu. Rozmiar pamięci podręcznej L3 nie jest tak istotny.

o kodzie

// all your stack variables are good. Compiler will optimize them well. 
for (int i = 0; i < N; i++) { 
    for (int j = 0; j < N; j++) { 
     float sum = 0.0; 
     for (int k = 0; k < N; k++) { 
      sum = sum + 
        a[i][k] * // here you are good, you read memory sequentially 
        b[k][j]; // here, you are not good, every read comes from different cache line 
     } 
     c[i][j] = sum; // here doesn't matter, it is rare operation 
    } 
} 

podobne do przypadku is here. Ta prezentacja wyjaśnia, jak zoptymalizować taki kod i dlaczego działa w ten sposób. Mam nadzieję, że znajdziesz wszystko, czego potrzebujesz.