Matrix Multiplikation Geschwindigkeit Probleme

Question

Ich untersuche, wie Cache-Misses die Geschwindigkeit der Berechnung beeinflussen. Ich weiß, es gibt bessere viele Algorithmen zur Multiplikation zweier Matrizen (auch einfachen Austausch von zwei der Schleifen unten helfen würde), aber bitte diesen Code betrachten:

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; 
     } 
    } 
} 

ich diesen Code neu kompiliert haben für viele Werte von N und gemessen Zeit, es zu laufen. Ich erwartete, einen plötzlichen Anstieg der Zeit um N=1250 zu finden, zu welchem ​​Zeitpunkt Matrix c nicht mehr in den Cache passt (Größe von c ist dann 1250*1250*sizeof(float)=6250000, oder etwa 6 MB, was die Größe meines L3-Cache ist).

In der Tat ist der allgemeine Trend, dass nach diesem Punkt die durchschnittliche Zeit im Vergleich zu extrapolierten Zeit von vor etwa verdreifacht. Aber der Wert von N%8 scheint einen großen Einfluss auf das Ergebnis zu haben. Zum Beispiel:

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 

Seit einiger Zeit dachte ich diese Ausrichtungsprobleme sein könnte - Reihen jeder Matrix auf 32 Byte ausgerichtet sind, wenn N%8==0 (erste Frage - warum 32 Bytes insbesondere SSE-Befehle, wie movaps kann? Arbeit an 16B ausgerichteten Daten).

Eine andere Idee war, dass dies irgendwie mit Cache-Assoziativität verbunden werden könnte (8-Wege für L1 und L2 und 12-Wege für L3 auf meinem Rechner).

Aber dann bemerkte ich, dass für einige Werte von N, wie 1536, es unerwartete Spitzen sind (auch wenn die Ausrichtung in diesen Fällen hervorragend sein sollte - 1536==256*6, die Assoziativität kein Thema zu sein - 1536==128*12==192*8). Zum Beispiel:

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

Das Timing ist ziemlich konsistent, so dass Spitzen der Prozessorlast kein Problem sind. Ich kompiliere den Code mit aktivierten Optimierungen (-O2). Meine Ideen laufen leider aus. Was könnte ein Grund für ein solches Verhalten sein?

Answer 1

Die wichtigsten für Ihr Beispiel - CPU-Cache-Zeilengröße. Für die CPU ist es typischerweise 64 Byte. Selbst wenn Ihr Programm 1 Byte liest oder schreibt, liest/schreibt die CPU für alle Zeilen (64 Byte). Aus diesem Grund ist Ihre Leistung gut, wenn Ihr Programm die Cache-Zeilen erreicht. Wenn es fehlt, gibt es einen zusätzlichen Aufwand zum Lesen/Schreiben von Speicher. Die Größe des L3-Caches ist nicht so kritisch.

für Ihren Code

// 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 
    } 
} 

Ähnlich Ihrem Fall is here. Diese Präsentation erklärt, wie man solchen Code optimiert und warum er so funktioniert. Ich hoffe, Sie finden alles, was Sie brauchen.