Matrixmultiplikation: Kleiner Unterschied in der Matrixgröße, großer Unterschied in den Timings

77

Ich habe einen Matrix-Multiplikationscode, der so aussieht:

Hier wird die Größe der Matrix durch dargestellt dimension. Wenn die Größe der Matrizen 2000 beträgt, dauert es 147 Sekunden, um diesen Code auszuführen. Wenn die Größe der Matrizen 2048 beträgt, dauert es 447 Sekunden. Also, während der Unterschied in Nr. von Multiplikationen ist (2048 * 2048 * 2048) / (2000 * 2000 * 2000) = 1,073, der Unterschied in den Timings ist 447/147 = 3. Kann jemand erklären, warum dies passiert? Ich habe erwartet, dass es linear skaliert, was nicht der Fall ist. Ich versuche nicht, den schnellsten Matrix-Multiplikationscode zu erstellen, sondern nur zu verstehen, warum dies geschieht.

Technische Daten: AMD Opteron Dual Core-Knoten (2,2 GHz), 2 G RAM, gcc v 4.5.0

Programm kompiliert als gcc -O3 simple.c

Ich habe dies auch auf Intels icc-Compiler ausgeführt und ähnliche Ergebnisse gesehen.

BEARBEITEN:

Wie in den Kommentaren / Antworten vorgeschlagen, habe ich den Code mit dimension = 2060 ausgeführt und es dauert 145 Sekunden.

Hier ist das komplette Programm:

jitihsk
quelle
9
Wahrscheinlich ist der Schlüssel zu Ihrem Verständnis, dass die Matrixmultiplikation nicht linear skaliert, sondern dass Ihr Code in der Größenordnung von liegt O(n^3).
Brc
6
Vielleicht im Zusammenhang mit Caching, wenn man die Zweierpotenz von 2048 berücksichtigt?
Christian Rau
12
@brc Ich weiß nicht, wie das in irgendeiner Weise mit seinem Problem zusammenhängt. Er ist sich der Komplexität seines Algorithmus voll bewusst. Hast du die Frage überhaupt gelesen?
Christian Rau
3
Versuchen Sie einen Test mit z. B. dimension = 2060 - dies zeigt Ihnen, ob das Problem mit z. B. der Cache-Größe zusammenhängt oder ob es sich um ein Super-Alignment-Problem handelt, z. B. Cache-Thrashing oder TLB-Thrashing.
Paul R
2
Beachten Sie, dass das Transponieren einer der Matrizen (kann an Ort und Stelle durchgeführt werden) zu besseren Ergebnissen für diese typischen Größen führt (der Break-Even-Punkt kann variieren). In der Tat ist das Transponieren O (n ^ 2) (vs. O (n ^ 3) Multiplikation) und der Speicher wird für beide Matrizen nacheinander aufgerufen, was zu einer besseren Cache-Nutzung führt.
Alexandre C.

Antworten:

84

Hier ist meine wilde Vermutung: Cache

Es kann sein, dass Sie 2 Zeilen von 2000 doubles in den Cache einfügen können . Das ist etwas weniger als der 32kb L1-Cache. (beim Verlassen des Raumes andere notwendige Dinge)

Wenn Sie es jedoch auf 2048 erhöhen, wird der gesamte Cache verwendet (und Sie verschütten einige, weil Sie Platz für andere Dinge benötigen).

Angenommen, die Cache-Richtlinie ist LRU. Wenn Sie den Cache nur geringfügig verschütten, wird die gesamte Zeile wiederholt geleert und erneut in den L1-Cache geladen.

Die andere Möglichkeit ist die Cache-Assoziativität aufgrund der Zweierpotenz. Obwohl ich denke, dass der Prozessor 2-Wege-L1-assoziativ ist, denke ich nicht, dass es in diesem Fall wichtig ist. (aber ich werde die Idee trotzdem rauswerfen)

Mögliche Erklärung 2: Konflikt-Cache-Fehler aufgrund von Super-Alignment im L2-Cache.

Ihr BArray wird in der Spalte iteriert. Der Zugang ist also geschritten. Ihre Gesamtdatengröße 2k x 2kbeträgt ca. 32 MB pro Matrix. Das ist viel größer als Ihr L2-Cache.

Wenn die Daten nicht perfekt ausgerichtet sind, haben Sie eine anständige räumliche Lokalität auf B. Obwohl Sie Zeilen hüpfen und nur ein Element pro Cacheline verwenden, verbleibt die Cacheline im L2-Cache, um bei der nächsten Iteration der mittleren Schleife wiederverwendet zu werden.

Wenn die Daten jedoch perfekt ausgerichtet sind (2048), landen diese Hops alle auf demselben "Cache-Weg" und überschreiten Ihre L2-Cache-Assoziativität bei weitem. Daher Bbleiben die Cache-Zeilen, auf die zugegriffen wird, für die nächste Iteration nicht im Cache. Stattdessen müssen sie vollständig vom Widder eingezogen werden.

Mystisch
quelle
3
Ich bin damit einverstanden, Cache zu vermuten. Sie können eine Reihe von Experimenten durchführen und die Laufzeit gegen die Dimension zeichnen. Wenn es sich um einen Cache handelt, sehen Sie eine Linearität in der Nähe ähnlicher Größen mit einigen scharfen Bruchstellen, an denen Sie einen großen Schritt erhalten und die lineare Steigung ändern.
TJD
2
Nicht nur die Cache- Größe - wenn die Matrizen wie im Fall 2048 superausgerichtet sind, können Probleme mit Cache-Thrashing, TLB-Thrashing usw. auftreten. Versuchen Sie es mit z. B. 2060 und sehen Sie, was passiert ...
Paul R
Ich habe es mit dimension = 2060 ausgeführt und es dauerte 145 Sekunden. Mit Blick auf Erklärung 2 sollte auch dies eine schlechte räumliche Lokalität haben. Für Dimension> = 2048 müssen Cache-Zeilen von B aus dem RAM abgerufen werden, oder?
Jitihsk
2
@AhmedMasud Und ich glaube nicht, dass die Verwendung timessein Problem erklärt.
Christian Rau
4
Aufgrund der Funktionsweise von Caches kann ein N-Way-Cache nur höchstens N Cachelines mit derselben Adresse modulo einer großen Zweierpotenz enthalten. (Ich kenne die genaue Nummer nur, wenn Sie mir mitteilen, welches Prozessormodell Sie haben.) Wenn N = 2048, haben die Cachelines, auf die balle zugreifen, eine Adresse mit demselben Modulo über die Zweierpotenz. Also werden sie sich widersprechen. (Google: "Conflict Cache Miss")
Mysticial
34

Sie bekommen definitiv eine sogenannte Cache- Resonanz . Dies ähnelt dem Aliasing , ist jedoch nicht genau dasselbe. Lassen Sie mich erklären.

Caches sind Hardwaredatenstrukturen, die einen Teil der Adresse extrahieren und als Index in einer Tabelle verwenden, ähnlich wie ein Array in der Software. (Tatsächlich nennen wir sie Arrays in der Hardware.) Das Cache-Array enthält Cache-Zeilen mit Daten und Tags - manchmal einen solchen Eintrag pro Index im Array (direkt zugeordnet), manchmal mehrere solcher (N-Wege-Satzassoziativität). Ein zweiter Teil der Adresse wird extrahiert und mit dem im Array gespeicherten Tag verglichen. Index und Tag identifizieren zusammen eine Cache-Zeilen-Speicheradresse eindeutig. Schließlich identifiziert der Rest der Adressbits zusammen mit der Größe des Zugriffs, welche Bytes in der Cache-Zeile adressiert sind.

Normalerweise sind Index und Tag einfache Bitfelder. Eine Speicheradresse sieht also so aus

(Manchmal sind der Index und das Tag Hashes, z. B. einige XORs anderer Bits in den Mittelbereichsbits, die der Index sind. Viel seltener, manchmal sind der Index und seltener das Tag Dinge wie das Aufnehmen der Cache-Zeilenadresse modulo a Primzahl. Diese komplizierteren Indexberechnungen sind Versuche, das hier erläuterte Resonanzproblem zu bekämpfen. Alle leiden unter irgendeiner Form von Resonanz, aber die einfachsten Bitfeldextraktionsschemata leiden unter Resonanz bei allgemeinen Zugriffsmustern, wie Sie festgestellt haben.)

Also, typische Werte ... es gibt viele verschiedene Modelle von "Opteron Dual Core", und ich sehe hier nichts, was angibt, welches Sie haben. Wählen Sie eines nach dem Zufallsprinzip aus, das neueste Handbuch, das ich auf der AMD-Website, im Bios and Kernel Developer's Guide (BKDG) für 15-Stunden-Modelle der AMD-Familie 00h-0Fh , 12. März 2012, sehe .

(Familie 15h = Bulldozer-Familie, der jüngste High-End-Prozessor - die BKDG erwähnt Dual Core, obwohl ich die Produktnummer nicht genau kenne, die Sie beschreiben. Trotzdem gilt für alle Prozessoren dieselbe Resonanzidee. Es ist nur so, dass die Parameter wie Cache-Größe und Assoziativität etwas variieren können.)

Ab S.33:

Der 15-Stunden-Prozessor der AMD-Familie enthält einen 16-KByte-4-Wege-L1-Datencache mit zwei 128-Bit-Ports. Dies ist ein Durchschreibcache, der bis zu zwei 128-Byte-Ladevorgänge pro Zyklus unterstützt. Es ist in 16 Bänke mit einer Breite von jeweils 16 Bytes unterteilt. [...] In einem Zyklus kann nur ein Ladevorgang von einer bestimmten Bank des L1-Cache ausgeführt werden.

Um zusammenzufassen:

  • 64-Byte-Cache-Zeile => 6 Offset-Bits innerhalb der Cache-Zeile

  • 16KB / 4-Wege => Die Resonanz beträgt 4KB.

    Das heißt, die Adressbits 0-5 sind der Cache-Zeilenversatz.

  • 16 KB / 64 KB Cache-Zeilen => 2 ^ 14/2 ^ 6 = 2 ^ 8 = 256 Cache-Zeilen im Cache.
    (Bugfix: Ich habe dies ursprünglich als 128 falsch berechnet, dass ich alle Abhängigkeiten behoben habe.)

  • 4-Wege-Assoziativ => 256/4 = 64 Indizes im Cache-Array. Ich (Intel) nenne diese "Sets".

    Das heißt, Sie können den Cache als ein Array von 32 Einträgen oder Sätzen betrachten, wobei jeder Eintrag 4 Cache-Zeilen und ihre Tags enthält. (Es ist komplizierter als das, aber das ist okay).

(Übrigens haben die Begriffe "set" und "way" unterschiedliche Definitionen .)

  • Es gibt 6 Indexbits, Bits 6-11 im einfachsten Schema.

    Dies bedeutet, dass alle Cache-Zeilen, die genau dieselben Werte in den Indexbits 6 bis 11 haben, demselben Satz des Caches zugeordnet werden.

Schauen Sie sich jetzt Ihr Programm an.

Schleife k ist die innerste Schleife. Der Basistyp ist doppelt, 8 Bytes. Wenn dimension = 2048, dh 2 KB, sind aufeinanderfolgende Elemente, auf B[dimension*k+j]die die Schleife zugreift, 2048 * 8 = 16 KB voneinander entfernt. Sie werden alle demselben Satz des L1-Cache zugeordnet - sie haben alle denselben Index im Cache. Dies bedeutet, dass anstelle von 256 Cache-Zeilen im Cache nur 4 zur Verfügung stehen - die "4-Wege-Assoziativität" des Caches.

Dh Sie werden wahrscheinlich alle 4 Iterationen um diese Schleife einen Cache-Fehler bekommen. Nicht gut.

(Eigentlich sind die Dinge etwas komplizierter. Aber das Obige ist ein gutes erstes Verständnis. Die Adressen der Einträge von B, die oben erwähnt wurden, sind eine virtuelle Adresse. Es kann also leicht unterschiedliche physikalische Adressen geben. Darüber hinaus verfügt Bulldozer über einen prädiktiven Cache. Wahrscheinlich werden virtuelle Adressbits verwendet, damit nicht auf eine Übersetzung von virtuellen zu physischen Adressen gewartet werden muss. Auf jeden Fall: Ihr Code hat eine "Resonanz" von 16 KB. Der L1-Datencache hat eine Resonanz von 16 KB. Nicht gut .)]

Wenn Sie die Dimension nur geringfügig ändern, z. B. auf 2048 + 1, werden die Adressen von Array B auf alle Sätze des Caches verteilt. Und Sie erhalten deutlich weniger Cache-Fehler.

Es ist eine ziemlich übliche Optimierung, Ihre Arrays aufzufüllen, z. B. 2048 auf 2049 zu ändern, um diese Resonanz zu vermeiden. "Cache-Blockierung ist jedoch eine noch wichtigere Optimierung. Http://suif.stanford.edu/papers/lam-asplos91.pdf


Neben der Cache-Line-Resonanz gibt es hier noch andere Dinge. Beispielsweise hat der L1-Cache 16 Bänke mit einer Breite von jeweils 16 Bytes. Mit der Dimension = 2048 werden aufeinanderfolgende B-Zugriffe in der inneren Schleife immer an dieselbe Bank gesendet. Sie können also nicht parallel geschaltet werden - und wenn der A-Zugriff zufällig auf dieselbe Bank geht, verlieren Sie.

Ich denke nicht, dass dies so groß ist wie die Cache-Resonanz.

Und ja, möglicherweise gibt es ein Aliasing. Beispielsweise vergleicht der STLF (Store To Load Forwarding-Puffer) möglicherweise nur ein kleines Bitfeld und erhält falsche Übereinstimmungen.

(Wenn Sie darüber nachdenken, ist Resonanz im Cache wie Aliasing, das mit der Verwendung von Bitfeldern zusammenhängt. Resonanz wird durch mehrere Cache-Zeilen verursacht, die denselben Satz abbilden und nicht über diese verteilt sind. Alisaing wird durch Matching basierend auf unvollständiger Adresse verursacht Bits.)


Insgesamt meine Empfehlung zur Abstimmung:

  1. Versuchen Sie, den Cache ohne weitere Analyse zu blockieren. Ich sage das, weil das Blockieren des Caches einfach ist und es sehr wahrscheinlich ist, dass dies alles ist, was Sie tun müssten.

  2. Verwenden Sie danach VTune oder OProf. Oder Cachegrind. Oder ...

  3. Besser noch, verwenden Sie eine gut abgestimmte Bibliotheksroutine, um die Matrixmultiplikation durchzuführen.

Krazy Glew
quelle
2
Sehr interessante Antwort (+1), aber schreckliche Formatierung und Bearbeitung :) Ich habe mein Bestes getan, um sie ein wenig zu verbessern.
Onkel Zeiv
Nett. kleiner Tippfehler: 256 Cache-Zeilen statt 128.
Taye
Danke, dass du das verstanden hast: 2 ^ 8 = 256. Ich werde versuchen, es zu korrigieren, aber ich wette, ich fange nicht alle Abhängigkeiten. Als ich bei Intel arbeitete, schrieb ich eine kleine "Free Text Spreadsheet", in der Formeln in den Text eingefügt werden konnten: Geben Sie eine neue Nummer ein und das Update wurde weitergegeben. (Ich schrieb das in der Grundschule; vielleicht kann ich wiederbeleben.)
Krazy Glew
17

Es gibt mehrere mögliche Erklärungen. Eine wahrscheinliche Erklärung ist das, was Mysticial vorschlägt: Erschöpfung einer begrenzten Ressource (entweder Cache oder TLB). Eine andere wahrscheinliche Möglichkeit ist ein falscher Aliasing-Stillstand, der auftreten kann, wenn aufeinanderfolgende Speicherzugriffe durch ein Vielfaches einer Zweierpotenz (häufig 4 KB) getrennt sind.

Sie können beginnen, die Arbeit einzugrenzen, indem Sie Zeit / Dimension ^ 3 für einen Wertebereich zeichnen. Wenn Sie einen Cache oder eine erschöpfte TLB-Reichweite gesprengt haben, sehen Sie einen mehr oder weniger flachen Abschnitt, gefolgt von einem starken Anstieg zwischen 2000 und 2048, gefolgt von einem weiteren flachen Abschnitt. Wenn Sie Aliasing-bezogene Stände sehen, sehen Sie ein mehr oder weniger flaches Diagramm mit einer schmalen Spitze nach oben bei 2048.

Dies hat natürlich diagnostische Aussagekraft, ist aber nicht schlüssig. Wenn Sie abschließend wissen möchten , woher die Verlangsamung stammt, sollten Sie sich über Leistungsindikatoren informieren , die diese Art von Frage definitiv beantworten können.

Stephen Canon
quelle
+1, ich habe in diesem Zusammenhang noch nie von falschen Aliasing-Ständen gehört. Aber von der Seite des Hardware-Designs aus macht es Sinn.
Mysticial
10

Ich weiß, das ist viel zu alt, aber ich werde einen Bissen nehmen. Es ist (wie gesagt) ein Cache-Problem, das die Verlangsamung bei Zweierpotenzen verursacht. Aber es gibt noch ein anderes Problem: Es ist zu langsam. Wenn Sie sich Ihre Rechenschleife ansehen.

Die innerste Schleife ändert k bei jeder Iteration um 1, was bedeutet, dass Sie nur 1 Doppel vom letzten Element, das Sie von A verwendet haben , zugreifen, aber eine ganze 'Dimension' verdoppelt sich vom letzten Element von B. Dies nutzt keinen Vorteil das Zwischenspeichern der Elemente von B.

Wenn Sie dies ändern in:

Sie erhalten genau die gleichen Ergebnisse (Modulo-Doppeladditions-Assoziativitätsfehler), aber es ist viel cachefreundlicher ( lokal ). Ich habe es versucht und es gibt wesentliche Verbesserungen. Dies kann zusammengefasst werden als

Multiplizieren Sie Matrizen nicht per Definition, sondern mit Zeilen


Beispiel für die Beschleunigung (Ich habe Ihren Code geändert, um die Dimension als Argument zu verwenden.)


Als Bonus (und was dies mit dieser Frage zusammenhängt) ist, dass diese Schleife nicht unter dem vorherigen Problem leidet.

Wenn Sie das alles schon gewusst haben, dann entschuldige ich mich!

Guido
quelle
+1 Ein besserer Algorithmus macht immer einen größeren Unterschied - unabhängig davon, welche Art von Cache (oder auch wenn es einen gibt), ist dies schneller.
Jerry Jeremiah
9

In einigen Antworten wurden Probleme mit dem L2-Cache erwähnt.

Sie können dies tatsächlich mit einer Cache- Simulation überprüfen . Valgrinds Cachegrind- Tool kann das.

Stellen Sie die Befehlszeilenparameter so ein, dass sie mit den L2-Parametern Ihrer CPU übereinstimmen.

Wenn Sie es mit verschiedenen Matrixgrößen testen, werden Sie wahrscheinlich einen plötzlichen Anstieg der L2-Fehlerquote feststellen.

Karoly Horvath
quelle