Zeilenmajor versus Spaltenmajor-Layout von Matrizen

Gibt es beim Programmieren dichter Matrixberechnungen einen Grund, ein Zeilen-Hauptlayout des über dem Spalten-Hauptlayout liegenden zu wählen?

Ich weiß, dass wir abhängig vom Layout der gewählten Matrix den entsprechenden Code schreiben müssen, um die Cache-Speicher aus Geschwindigkeitsgründen effektiv zu nutzen.

Das Zeilen-Hauptlayout erscheint mir natürlicher und einfacher (zumindest für mich). Wichtige Bibliotheken wie LAPACK, die in Fortran geschrieben wurden, verwenden jedoch das Spalten-Hauptlayout. Es muss also einen Grund geben, diese Wahl getroffen zu haben.

Das Spalten-Hauptlayout ist das von Fortran verwendete Schema und wird daher in LAPACK und anderen Bibliotheken verwendet.

Im Allgemeinen ist es in Bezug auf die Speicherbandbreitennutzung und die Cache-Leistung wesentlich effizienter, auf die Elemente eines Arrays in der Reihenfolge zuzugreifen, in der sie im Speicher angeordnet sind. Abhängig davon, wie Ihre Matrizen gespeichert sind, sollten Sie Algorithmen auswählen, die diese Vorteile nutzen.

Interner Speicher des Spaltenhauptformats

Im Vakuum ohne Berücksichtigung vorhandener Software gibt es keinen Grund, aus der Sicht des Codes Spaltenmajor gegenüber Zeilenmajor vorzuziehen. Die meiste mathematische Literatur ist jedoch so geschrieben, dass Vektoren in einer Matrix gruppiert werden, indem sie als Spalten statt als Zeilen gespeichert werden. Wenn Sie zum Beispiel die vollständige Eigenwertgleichung schreiben , ist das $AX=X\Lambda$$X$Matrix enthält alle in Spalten ausgeschriebenen Eigenvektoren. Man sieht es nie wirklich anders geschrieben (obwohl ich höre, dass Statistikleute Zeilenvektoren mögen). Daher war es selbstverständlich, dass die früheste Software das Spalten-Hauptformat annahm. Wenn Sie also eine Matrix haben, die eine Menge von Vektoren ist, ist die Speicherung eines einzelnen Vektors zusammenhängend. So stelle ich mir vor, dass die Tradition bis heute fortgeführt wurde, und wenn Sie mit der alten Fortran interagieren möchten, möchten Sie Kolumne Major verwenden. So ziemlich jede hocheffiziente numerische lineare Algebra wird in Spalte Dur ausgeführt.

Der Grund, warum C Zeilenmajor ist, ist eine Konsequenz seiner Array-Syntax. Sie deklarieren ein Array mit 3 Zeilen und 2 Spalten als double a[3][2]und spätere Indizes variieren schneller als frühere Indizes, was bei 2D-Arrays dazu führt, dass die Zeile größer wird. Wenn Sie dies mit der natürlichen westlichen Lesereihenfolge von links nach rechts kombinieren, wirkt Row Major natürlicher.

Die Hauptreihenfolge der Spalten scheint natürlicher zu sein. Angenommen, Sie möchten einen Film Bild für Bild in einer Datei speichern, dann verwenden Sie die Spaltenreihenfolge. Dies ist sehr intuitiv und wird von niemandem in der Reihenfolge der Zeilenschwerpunkte gespeichert.

Wenn Sie Programmierer in C / C ++ sind, sollten Sie einige Bibliotheken höherer Ebenen für Matrizen (Eigen, Armadillo, ...) mit der Standardreihenfolge für die Spalten verwenden. Nur Maniac würde rohe C-Zeiger mit Zeilenhauptordnung verwenden, obwohl C / C ++ etwas bietet, das an die Matrixindizierung erinnert.

Der Einfachheit halber sollte alles mit Zeilenhauptordnung als zumindest seltsam geformt angesehen werden. Scheibe für Scheibe ist einfach natürliche Ordnung und bedeutet Spalten-Hauptordnung (wie Fortran). Unsere Väter / Mütter hatten sehr gute Gründe, warum sie sich dafür entschieden haben.

Unglücklicherweise wurden, bevor klar wurde, mehrere interessante Bibliotheken in größerer Reihenfolge angelegt, wahrscheinlich aus Mangel an Erfahrung.

Um zu verdeutlichen, erinnern wir uns an die Definition der Zeilen-Hauptreihenfolge, bei der der rechte Index in einem Schritt schneller durch den Speicher variiert, z nicht wollen. Für Film A (x, y, t) ist der letzte Index die Zeit t. Es ist nicht schwer vorstellbar, dass es einfach unmöglich ist, einen Film im Zeilensprung-Modus zu speichern.

$m\times n$

• $m_{i,j}$$i \times m + j$
• $m_{i,j}$$j \times n + i$

Stellen Sie sich nun den folgenden Algorithmus vor:

for i from 1 to m
   for j from 1 to n
      do something with m(i,j)

$i \times m + j$

Schlussfolgerungen:

1. Ja, es ist wichtig, aber die Auswahl hängt davon ab, wie auf Daten zugegriffen wird. Wenn im vorherigen Beispiel die Spaltenreihenfolge verwendet wird, müssen Sie lediglich die beiden Schleifen vertauschen.

2. Faustregel: Der sich schnell ändernde Index sollte aufeinanderfolgenden Positionen im Speicher zugeordnet werden.

3. Noch wichtiger ist, dass das Messen / Benchmarking der Auswirkung der Auswahl von grundlegender Bedeutung ist, da dies von vielen Parametern abhängt (der Größe der Daten, der Größe des Caches, der Art und Weise, wie die verwendete Sprache mehrere Indizes auf einen linearen Index abbildet, der Art und Weise der Funktionsweise) Das System verwaltet den virtuellen Speicher so, wie die Schleifen in der von Ihnen verwendeten Bibliothek für lineare Algebra verschachtelt sind.