Zeilenmajor versus Spaltenmajor-Layout von Matrizen

16

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.

lächelnder Buddha
quelle
Wenn wir betrachten, b = A * x mit x-Spaltenvektor zu berechnen, können wir für den Zeilensprung A innere Produkte von Vektoren verwenden, A (i,:) ^ T x, um b (i) zu erhalten; Für Spaltenmajor benötigen wir möglicherweise nur skalare Multiplikationsvektoren, sum_i A (:, i) x (i). Mir scheint, Kolumne Major ist viel besser! Was denkst du?
Hui Zhang
Trainiere dich darin, Kolumne-Major zu mögen. Es ist einfach, wenn Sie Vektoren als Spalten oder deren Transposition als Zeilen visualisieren. Es macht die Visualisierung der Matrixmultiplikation sehr einfach und macht es einfach, vielen veröffentlichten Berechnungen zu folgen.
Mike Dunlavey

Antworten:

18

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.

interne Speicher Interner Speicher des Spaltenhauptformats

Brian Borchers
quelle
11

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 XEINX=XΛXMatrix 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.

Victor Liu
quelle
2
Ich denke, das sind schlechte Argumente. Die Tatsache, dass der letzte Index in '' 'double a [3] [2]' '' am schnellsten variiert, ist kein Zufall - es war eine bewusste Designentscheidung, genauso wie es eine bewusste Designentscheidung in Fortran war Machen Sie es umgekehrt, wenn Sie ein '' 'reales (3,2)' '' Array haben.
Wolfgang Bangerth
1
Darüber hinaus stimmt es nicht mehr, dass so gut wie jede hocheffiziente numerische lineare Algebra spaltenmajor ist. Dies gilt zwar immer noch für BLAS und LAPACK, aber nicht für jede größere lineare Algebra-Bibliothek, die in den letzten 15 Jahren erschienen ist: Beispielsweise verwenden sowohl PETSc als auch Trilinos Speicherformate für große, dünn besetzte Zeilenmatrix.
Wolfgang Bangerth
Mir ist bewusst, dass die C-Konvention eine bewusste Entscheidung war, die wahrscheinlich auf der natürlichen Lesereihenfolge basierte. Ich habe gemeint, dass es wahrscheinlich nicht mit Blick auf die numerische lineare Algebra entworfen wurde. Zweitens wollte ich nicht, dass das Argument für spärliche Matrizen gilt, sondern nur für dichte. Für Sparse ist es ein bisschen gemischt, mit komprimierten Zeilen- und Spaltenformaten.
Victor Liu
5
C war ursprünglich eine Systemsprache, die auf den früheren Sprachen B und BCPL basierte und auf Systemen wie dem PDP-11 ohne Gleitkommazahlen lief. Zu sagen, dass sie es mit numerischen Gesichtspunkten entworfen haben, ist eine ziemliche Strecke.
Victor Liu
7
War dort usw. Der Grund, warum Matrizen in C den letzten Index am schnellsten verschieben, ist, dass C keine Matrizen hat. Es enthält Vektoren von Vektoren, die transparent als feste Speicherblöcke oder als Arrays von Zeigern auf Arrays implementiert werden können. Die Kompatibilität der Indexreihenfolge mit Fortran war (ich vermute mal) nicht einmal auf Dennis Ritchies Radar.
Mike Dunlavey
2

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.

Paul
quelle
2

m×n

  • mich,jich×m+j
  • mich,jj×n+ich

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)

ich×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.

BrunoLevy
quelle