Warum ist die Leistungsmultiplikation bei 2048 x 2048 gegenüber der Array-Multiplikation bei 2047 x 2047 enorm?

127

Ich mache ein Benchmarking für die Matrixmultiplikation, wie bereits unter Warum ist MATLAB bei der Matrixmultiplikation so schnell erwähnt?

Jetzt habe ich ein weiteres Problem: Wenn Sie zwei 2048x2048-Matrizen multiplizieren, gibt es einen großen Unterschied zwischen C # und anderen. Wenn ich versuche, nur 2047x2047-Matrizen zu multiplizieren, scheint das normal zu sein. Einige andere zum Vergleich hinzugefügt.

1024 x 1024 - 10 Sekunden.

1027 x 1027 - 10 Sekunden.

2047 x 2047 - 90 Sekunden.

2048 x 2048 - 300 Sekunden.

2049 x 2049 - 91 Sekunden. (aktualisieren)

2500 x 2500 - 166 Sekunden

Das sind dreieinhalb Minuten Unterschied für den Fall 2k mal 2k.

mit 2dim Arrays

//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;
   }
 }
Wolf
quelle
23
Dies wäre eine großartige Prüfungsfrage für eine fortgeschrittene C-Programmier- oder OS-Design-Klasse ;-)
Dana the Sane
Haben Sie versucht, sowohl mehrdimensionale [,] als auch gezackte [] [] Arrays sowie 32- und 64-Bit-Arrays zu testen? Ich habe nur ein paar Mal getestet, aber gezackt schien mehr mit Ihren Ergebnissen übereinzustimmen, aber gezackte 64-Bit waren hoch. Ich weiß nicht, ob es im Jit Heuristiken gibt, die für diese Situation gelten, oder ob der Cache wie zuvor vorgeschlagen zusammenhängt. Wenn Sie eine GPGPU-Lösung wünschen, gibt es research.microsoft.com/en-us/projects/accelerator, das mit der Zeit in Ihrem anderen Beitrag konkurrieren sollte.
Kris
Etwas naive Frage, aber wie viele Operationen (Addieren / Multiplizieren) sind beim Multiplizieren von zwei quadratischen Matrizen beteiligt?
Nick T

Antworten:

61

Dies hat wahrscheinlich mit Konflikten in Ihrem L2-Cache zu tun.

Cache-Fehler auf matice1 sind nicht das Problem, da auf sie nacheinander zugegriffen wird. Wenn jedoch für matice2 eine vollständige Spalte in L2 passt (dh wenn Sie auf matice2 [0, 0], matice2 [1, 0], matice2 [2, 0] usw. zugreifen, wird nichts entfernt), gibt es kein Problem mit Cache fehlt auch mit matice2.

Um nun genauer zu untersuchen, wie Caches funktionieren, wenn die Byteadresse Ihrer Variablen X ist, lautet die Cache-Zeile dafür (X >> 6) & (L - 1). Dabei ist L die Gesamtzahl der Cache-Zeilen in Ihrem Cache. L ist immer eine Potenz von 2. Die sechs ergibt sich aus der Tatsache, dass 2 ^ 6 == 64 Bytes die Standardgröße der Cache-Zeile sind.

Was bedeutet das nun? Nun, es bedeutet, dass wenn ich Adresse X und Adresse Y habe und (X >> 6) - (Y >> 6) durch L teilbar ist (dh eine große Potenz von 2), sie in derselben Cacheline gespeichert werden.

Um nun auf Ihr Problem zurückzukommen: Was ist der Unterschied zwischen 2048 und 2049?

wenn 2048 deine Größe ist:

Wenn Sie & matice2 [x, k] und & matice2 [y, k] nehmen, ist die Differenz (& matice2 [x, k] >> 6) - (& matice2 [y, k] >> 6) durch 2048 * 4 (Größe) teilbar von float). Also eine große Potenz von 2.

Abhängig von der Größe Ihres L2 treten daher viele Cache-Zeilen-Konflikte auf, und Sie verwenden nur einen kleinen Teil Ihres L2 zum Speichern einer Spalte. Daher können Sie nicht die gesamte Spalte in Ihrem Cache speichern, sodass Sie eine schlechte Leistung erzielen .

Wenn die Größe 2049 ist, beträgt der Unterschied 2049 * 4, was keine Zweierpotenz ist. Sie haben also weniger Konflikte und Ihre Spalte passt sicher in Ihren Cache.

Um diese Theorie zu testen, können Sie einige Dinge tun:

Ordnen Sie Ihr Array matice2 Array wie dieses matice2 [razmor, 4096] zu und führen Sie es mit razmor = 1024, 1025 oder einer beliebigen Größe aus. Sie sollten im Vergleich zu zuvor eine sehr schlechte Leistung sehen. Dies liegt daran, dass Sie alle Spalten zwangsweise so ausrichten, dass sie miteinander in Konflikt stehen.

Versuchen Sie dann matice2 [razmor, 4097] und führen Sie es mit einer beliebigen Größe aus, und Sie sollten eine viel bessere Leistung sehen.

zviadm
quelle
Haben Sie in Ihren letzten beiden Absätzen einen Fehler gemacht? Beide Versuche sind genau gleich. :)
Xeo
Auch die Cache-Assoziativität spielt eine Rolle.
Ben Jackson
20

Wahrscheinlich ein Caching-Effekt. Mit Matrixdimensionen, die große Zweierpotenzen sind, und einer Cache-Größe, die auch eine Zweierpotenz ist, können Sie nur einen kleinen Bruchteil Ihres L1-Caches verwenden, was die Dinge erheblich verlangsamt. Die naive Matrixmultiplikation wird normalerweise durch die Notwendigkeit eingeschränkt, Daten in den Cache abzurufen. Optimierte Algorithmen, die Kacheln verwenden (oder Algorithmen, die den Cache nicht kennen), konzentrieren sich darauf, den L1-Cache besser zu nutzen.

Wenn Sie andere Paare zeitlich festlegen (2 ^ n-1,2 ^ n), werden Sie wahrscheinlich ähnliche Effekte sehen.

Um dies genauer zu erklären, ist es in der inneren Schleife, in der Sie auf matice2 [m, k] zugreifen, wahrscheinlich, dass matice2 [m, k] und matice2 [m + 1, k] um 2048 * sizeof (float) voneinander versetzt sind. und somit demselben Index im L1-Cache zugeordnet werden. Bei einem assoziativen N-Wege-Cache verfügen Sie normalerweise über 1-8 Cache-Speicherorte für alle diese. Somit lösen fast alle diese Zugriffe eine L1-Cache-Räumung und das Abrufen von Daten aus einem langsameren Cache oder Hauptspeicher aus.

Jonathan Moore
quelle
+1. Klingt wahrscheinlich. Bei der Cache-Assoziativität muss man vorsichtig sein.
Macke
16

Dies hängt möglicherweise mit der Größe Ihres CPU-Cache zusammen. Wenn 2 Zeilen der Matrixmatrix nicht passen, verlieren Sie Zeit beim Austauschen von Elementen aus dem RAM. Die zusätzlichen 4095-Elemente reichen möglicherweise gerade aus, um das Anpassen von Reihen zu verhindern.

In Ihrem Fall liegen 2 Zeilen für 2047 2d-Matrizen innerhalb von 16 KB Speicher (unter der Annahme von 32-Bit-Typen). Wenn Sie beispielsweise einen L1-Cache (der der CPU auf dem Bus am nächsten liegt) von 64 KB haben, können Sie mindestens 4 Zeilen (von 2047 * 32) gleichzeitig in den Cache einfügen. Bei den längeren Zeilen wird es unordentlich, wenn eine Auffüllung erforderlich ist, die die Zeilenpaare über 16 KB hinausschiebt. Jedes Mal, wenn Sie den Cache "verpassen", verzögert sich das Austauschen von Daten aus einem anderen Cache oder Hauptspeicher.

Ich vermute, dass die Varianz der Laufzeiten, die Sie bei den unterschiedlich großen Matrizen sehen, davon abhängt, wie effektiv das Betriebssystem den verfügbaren Cache nutzen kann (und einige Kombinationen sind nur problematisch). Das alles ist natürlich eine grobe Vereinfachung für mich.

Dana the Sane
quelle
2
aber es ist sehr unwahrscheinlich, dass er 16,7 MB CPU-Cache hat
Marino Šimić
Ich habe die Ergebnisse mit 2049x2049 - 91 Sekunden aktualisiert. Wenn es sich um ein "Cache-Problem" handelte, sollten dies nicht immer noch 300+ sein?
Wolf
@ Marino Die Antwort wurde aktualisiert, um dies zu berücksichtigen.
Dana the Sane
1
Ich bin der Meinung, dass keine dieser Erklärungen die neuen Details in Bezug auf die verschiedenen und spärlichen Größen, die das Problem hervorrufen, angemessen ansprechen kann, während andere dazwischen nicht betroffen sind.
Ken Rockot
2
Ich denke nicht, dass diese Erklärung richtig ist. Das Problem liegt darin, dass die Cache-Kapazität aufgrund von Cache-Zeilen-Konflikten bei einer Größe von 2 nicht vollständig genutzt wird. Auch das Betriebssystem hat wirklich nichts mit Caches zu tun, da nicht das Betriebssystem entscheidet, was zwischengespeichert und was entfernt werden soll in Hardware. Das Betriebssystem hat etwas mit der Datenausrichtung zu tun, aber in diesem Fall geht es darum, wie C # Daten zuweist und wie ein 2D-Array im Speicher dargestellt wird. Das Betriebssystem hat nichts damit zu tun.
Zviadm
10

Louis Brandy schrieb zwei Blog-Beiträge, in denen genau dieses Problem analysiert wurde:

Mehr Cache-Verrücktheit und Rechenleistung - Eine Fallstudie für Anfänger mit einigen interessanten Statistiken und Versuchen, das Verhalten detaillierter zu erklären, führt tatsächlich zu Einschränkungen der Cache-Größe.

Christian Hang-Hicks
quelle
5

Angesichts der Tatsache, dass die Zeit bei größeren Größen abnimmt, wäre es nicht wahrscheinlicher, dass es sich um Cache-Konflikte handelt, insbesondere bei Zweierpotenzen für die problematischen Matrixgrößen? Ich bin kein Experte für Caching-Probleme, aber ausgezeichnete Informationen zu Cache-bezogenen Leistungsproblemen hier .


quelle
Insbesondere Abschnitt 5 des Links zur Cache-Assoziativität scheint zu gelten.
Dana the Sane
4

Wenn Sie matice2vertikal auf das Array zugreifen , wird es viel häufiger in den Cache und aus dem Cache heraus verschoben. Wenn Sie das Array diagonal spiegeln, damit Sie [k,m]stattdessen mit darauf zugreifen können [m,k], wird der Code viel schneller ausgeführt.

Ich habe dies für 1024x1024-Matrizen getestet und es ist ungefähr doppelt so schnell. Bei 2048x2048-Matrizen ist es ungefähr zehnmal schneller.

Guffa
quelle
Dies erklärt nicht, warum 2049 schneller als 2048 ist.
Macke
@ Macke: Das liegt daran, dass das Speicher-Caching eine gewisse Grenze überschreitet, so dass es viel mehr Cache-Fehler gibt.
Guffa
Warum das Downvote? Wenn Sie nicht sagen, was Sie für falsch halten, kann dies die Antwort nicht verbessern.
Guffa
Noch eine Ablehnung ohne Erklärung ... Ist es so, dass meine Antwort zu wenig "wahrscheinlich", "erraten" und "sollte" enthält, wie die Antworten, die die meisten positiven Stimmen erhalten ...?
Guffa
4

Cache-Aliasing

Oder Cache-Thrashing , wenn ich einen Begriff prägen kann.

Caches funktionieren durch Indizieren mit Bits niedriger Ordnung und Markieren mit Bits höherer Ordnung.

Stellen Sie sich vor, Ihr Cache enthält 4 Wörter und Ihre Matrix ist 4 x 4. Wenn auf eine Spalte zugegriffen wird und die Zeile eine Zweierpotenz hat, wird jedes Spaltenelement im Speicher demselben Cache-Element zugeordnet.

Eine Zweierpotenz plus eins ist eigentlich ungefähr optimal für dieses Problem. Jedes neue Spaltenelement wird dem nächsten Cache-Slot genau so zugeordnet, als würde nach einer Zeile zugegriffen.

Im wirklichen Leben deckt ein Tag mehrere nacheinander ansteigende Adressen ab, die mehrere benachbarte Elemente in einer Reihe zwischenspeichern. Durch das Versetzen des Buckets, dem jede neue Zeile zugeordnet ist, ersetzt das Durchlaufen der Spalte nicht den vorherigen Eintrag. Wenn die nächste Spalte durchlaufen wird, wird der gesamte Cache mit verschiedenen Zeilen gefüllt und jeder Zeilenabschnitt, der in den Cache passt, wird für mehrere Spalten getroffen.

Da der Cache erheblich schneller als der DRAM ist (hauptsächlich aufgrund der On-Chip-Funktion), ist die Trefferquote alles.

DigitalRoss
quelle
2

Sie scheinen eine Cache-Größenbeschränkung erreicht zu haben oder haben möglicherweise Probleme mit der Wiederholbarkeit Ihrer Timings.

Was auch immer das Problem ist, Sie sollten die Matrixmultiplikation einfach nicht selbst in C # schreiben und stattdessen eine optimierte Version des BLAS verwenden. Diese Matrixgröße sollte auf jeder modernen Maschine in weniger als einer Sekunde multipliziert werden.

David Heffernan
quelle
1
Ich kenne BLAS, aber die Aufgabe bestand nicht darin, es so schnell wie möglich zu machen, sondern es in verschiedenen Sprachen zu schreiben und zu testen. Das ist ein sehr seltsames Problem für mich und ich bin wirklich neugierig, warum die Ergebnisse so sind, wie sie sind.
Wolf
3
@Wolf Es fällt mir schwer, mich darüber zu freuen, ob etwas, das eine Sekunde dauern sollte, 90 Sekunden oder 300 Sekunden dauert.
David Heffernan
4
Der beste Weg, um zu lernen, wie etwas funktioniert, besteht darin, es selbst zu schreiben und zu sehen, wie Sie Ihre Implementierung verbessern können. das ist (hoffentlich) was Wolf tut.
Callum Rogers
@ Callum Rogers, stimmte zu. Auf diese Weise habe ich gelernt, wie wichtig Puffergrößen beim Kopieren von Dateien sind.
Kelly S. French
1

Die effektive Nutzung der Cache-Hierarchie ist sehr wichtig. Sie müssen sicherstellen, dass mehrdimensionale Arrays Daten in einer schönen Anordnung haben, was durch Kacheln erreicht werden kann . Dazu müssen Sie das 2D-Array zusammen mit einem Indizierungsmechanismus als 1D-Array speichern. Das Problem bei der herkömmlichen Methode besteht darin, dass, obwohl zwei benachbarte Array-Elemente, die sich in derselben Zeile befinden, nebeneinander im Speicher liegen, zwei benachbarte Elemente in derselben Spalte durch W- Elemente im Speicher getrennt werden, wobei W die Anzahl der Spalten ist . Kacheln können einen Leistungsunterschied von bis zu zehn Faktoren bewirken.

Arlen
quelle
Hmm - dennoch wird ein als 2D deklariertes Array (float [,] matice = new float [rozmer, rozmer];) im RAM immer nur als eindimensionales Array zugewiesen und Zeilen- / Schrittberechnungen unter der Haube durchgeführt. Warum sollte es also schneller sein, es als 1D zu deklarieren und manuelle Zeilen- / Schrittberechnungen durchzuführen? Meinen Sie damit, dass sol'n ein großes Array als Array kleinerer Kacheln zuweist, von denen jedes in den Cache passt, wo das große Array dies nicht tun würde?
Eric M
1
Wenn Ihre Bibliothek oder ein anderes von Ihnen verwendetes Tool Kacheln ausführt, müssen Sie dies nicht tun. Wenn Sie jedoch ein traditionelles 2D-Array beispielsweise in C / C ++ verwenden, verbessert das Kacheln die Leistung.
Arlen
0

Ich vermute, es ist das Ergebnis von etwas, das " Sequential Flooding " genannt wird. Dies bedeutet, dass Sie versuchen, die Liste der Objekte zu durchlaufen, die etwas größer als die Cache-Größe ist. Daher muss jede einzelne Anforderung an die Liste (das Array) vom RAM ausgeführt werden, und Sie erhalten keinen einzelnen Cache schlagen.

In Ihrem Fall durchlaufen Sie 2048-mal Ihre Arrays 2048-Indizes, haben jedoch nur Platz für 2047 (möglicherweise aufgrund eines gewissen Overheads durch die Array-Struktur). Jedes Mal, wenn Sie auf eine Array-Position zugreifen, muss diese Array-Position abgerufen werden vom Widder. Es wird dann im Cache gespeichert, aber kurz bevor es wieder verwendet wird, wird es ausgegeben. Der Cache ist also im Wesentlichen nutzlos, was zu einer viel längeren Ausführungszeit führt.

Automatico
quelle
1
Falsch. 2049 ist schneller als 2048, was Ihre Behauptung widerlegt.
Macke
@ Macke: Das ist durchaus möglich. Es besteht jedoch eine geringe Wahrscheinlichkeit, dass die in seinem Prozessor verwendete Cache-Richtlinie diese Entscheidung noch trifft. Es ist nicht sehr wahrscheinlich, aber es ist nicht undenkbar.
Automatico