Sind dünn besetzte Matrizen in der Regel in der Reihenfolge der größeren oder der größeren Reihenreihenfolge gespeichert?

Question

Ein kleiner Hintergrund: Ich interessiere mich für Forschung über spärliche Matrix * Vektor Multiplikation.

Ich habe durch diese Datenbank schwach besetzte Matrizen suchen:

The University of Florida Sparse Matrix Collection

ich bemerkt, dass es drei Formate die Matrizen in verfügbar sind:

1. MATLAB (.mat)
2. Matrix Markt (.mtx)
3. Harwell-Boeing (.rb)

Es scheint, dass die Matrizen in Spaltenhauptordnung gespeichert sind (d. H. Spalten werden nacheinander gespeichert und nicht direkt hintereinander. In der Literatur scheint es jedoch, dass das komprimierte Sparse-Zeilen- (CSR) -Format anscheinend das üblichste Format ist (siehe "Scientific Computing-Kernel auf dem Zellprozessor Samuel"). Ich weiß, dass irgendwie nur der Index (i, j) und der Wert an diesen Koordinaten gespeichert werden, aber ich denke, dass ich die Daten zuerst neu formatieren müsste, um die Matrix * Vektormultiplikation effizient durchzuführen.

Für meine Implementierung wäre es sinnvoller, die Daten in der Reihenfolge der Zeilenreihenfolge zu speichern, damit nacheinander auf die Elemente in einer Zeile zugegriffen werden kann, da sie in aufeinanderfolgenden Speicheradressen gespeichert würden.

Das CSR-Format scheint jedoch anzunehmen, dass die Daten in der Reihenfolge der Zeilenreihenfolge gespeichert werden. Also was ich frage mich, ist das: Wie werden Daten in der Regel für spärliche Matrizen im Speicher gespeichert? Und beinhaltet ein Teil der Vektorberechnung mit spärlichem Matrix * das Umgruppieren der Daten von der Reihenfolge der Spaltenmajor zur Reihe? Ich frage, weil ich frage mich, ob diese Konvertierung in Sparse Matrix Benchmark-Ergebnisse in der Regel berücksichtigt wird.

Answer 1

Ich fürchte, es gibt keine kurze Antwort. Das beste Speicherschema hängt von dem Problem ab, das Sie lösen möchten.Die Dinge, die berücksichtigt werden müssen, sind nicht nur die Speichergröße, sondern auch, wie effizient, aus rechnerischer und Hardware-Perspektive, der Zugriff und die Operationen auf dieses Speicherformat sind.

Für dünn besetzte Matrixvektormultiplikation ist CSR ein gutes Format, da es einen linearen Zugriff auf die Elemente einer Matrixzeile ermöglicht, was für die Speicher- und Cache-Leistung gut ist. CSR induziert jedoch ein unregelmäßigeres Zugriffsmuster in den Multiplikanden: Holt Elemente an unterschiedlichen Positionen, abhängig davon, welchen Index Sie aus der Zeile abrufen; Dies ist schlecht für die Cache-Leistung. Eine CSC-Matrixvektormultiplikation kann den irregulären Zugriff auf den Multiplikanden auf Kosten eines unregelmäßigeren Zugriffs in dem Lösungsvektor entfernen. Abhängig von Ihrer Matrixstruktur können Sie das eine oder andere auswählen. Zum Beispiel kann eine Matrix mit ein paar langen Reihen mit einer ähnlichen Verteilung ungleich Null effizienter in einem CSC-Format gehandhabt werden.

Einige Beispiele in den bekannten Software-Paketen/Tool:

1. Nach bestem Wissen und Gewissen verwenden Matlab eine Spalte Speicher standardmäßig.

2. Wissenschaftliche Codes (und BLAS) basierend auf Fortran verwenden standardmäßig auch einen Spaltenspeicher. Dies ist hauptsächlich auf historische Gründe zurückzuführen, da Fortran-Arrays zu Beginn mit AFAIK-Spalten ausgerichtet waren und eine große Anzahl von Dense/Sparse-BLAS-Codes ursprünglich in Fortran geschrieben wurden.

3. Eigen verwendet standardmäßig auch einen Spaltenspeicher, der jedoch angepasst werden kann.

4. Intel MKL erfordert, dass Sie IIRC wählen.

5. Boost ublas verwendet standardmäßig ein zeilenbasiertes Speicherformat.

6. PetSC, die ein weit verbreitetes Werkzeug wissenschaftliches Rechnen in größerem Maßstab ist, verwendet a row based format (SequentialAIJ für CSR steht), sondern auch ermöglicht es Ihnen, von einer Vielzahl von Speicherformaten (siehe die Funktionen MatCreate * auf wählen ihre documentation)

Und die Liste könnte weitergehen. Wie Sie sehen können, gibt es einige Unterschiede zwischen den verschiedenen Tools, und ich bezweifle, dass die Kriterien die Leistung der SpMV-Operation war :) Wahrscheinlich Aspekte wie die gemeinsamen Speicherformate in den Zielproblembereichen, typische Erwartungen von Programmierern in der Zielproblemdomäne Die Integration mit anderen Bibliotheksaspekten und bereits existierenden Codes war der Hauptgrund für den Einsatz von CSR/CSC. Diese unterscheiden sich offensichtlich pro Werkzeug.

• Es gibt auch Formate Blockspeicher, die lokal zu nutzen versuchen:

  Wie auch immer, einen kurzen Überblick über die spärlichen Speicherformate können here aber viele mehr Speicherformate wurden/werden vorgeschlagen in Sparse Matrix Forschung gefunden werden dichte Unterstrukturen der Matrix. Siehe zum Beispiel "Schnelle spärliche Matrix-Vektor-Multiplikation durch Ausnutzen einer variablen Blockstruktur" von Richard W. Vuduc, Hyun-Jin Moon.

• Ein sehr kurzer, aber nützlicher Überblick über einige gängige Speicherformate finden Sie in der Python scipy Dokumentation zu spärlichen Formaten http://docs.scipy.org/doc/scipy/reference/sparse.html.
  • Iterative Methoden für spärliche lineare Systeme, Yousef Saad
  • SPARSKIT:: Ein Basiswerkzeugsatz für spärliche Matrix
  • Weitere Informationen über die Vorteile der verschiedenen Formate können in die folgenden Texte (und viele andere) entnommen werden Berechnung, Tech. Rep. CSRD TR 1029, CSRD, Universität von Illinois, Urbana, IL, 1990.
  • LAPACK Arbeitsnotiz 50: Verteilte Sparse Datenstrukturen für lineare Algebra Operationen, Tech. Rep. CS 92-169, Fachbereich Informatik, University of Tennessee, Knoxville, TN, 1992.

Ich habe für Sparse Matrix-Algorithmen auf dem Erstellen von benutzerdefinierten Hardware-Architekturen Forschung in dem Sparse-Matrix-Bereich getan (wie SpMV). Erfahrungsgemäß ignorieren einige Matrix-Benchmarks den Overhead der Konvertierung zwischen verschiedenen Formaten. Dies liegt daran, dass im Prinzip davon ausgegangen werden kann, dass Sie nur das Speicherformat Ihres gesamten Algorithmus anpassen können. SpMV selbst wird kaum isoliert verwendet und ist im Allgemeinen ein Teil eines größeren iterativen Algorithmus (z. B. ein linearer oder nichtlinearer Solver). In diesem Fall können sich die Kosten für die Konvertierung zwischen Formaten über die vielen Iterationen und die gesamte Laufzeit des gesamten Algorithmus amortisieren. Natürlich müssten Sie rechtfertigen, dass Ihre Annahme in dieser Situation hält.

Als Haftungsausschluss, in meinem Bereich sind wir besonders geneigt, so viele Annahmen wie möglich zu machen, da die Kosten und Zeit, um eine Hardware-Architektur für einen linearen Löser Benchmark ein neues spmv Speicherformat ist in der Regel erheblichen umzusetzen (in der Größenordnung von Monaten). Wenn Sie in Software arbeiten, ist es viel einfacher, Ihre Annahmen zu testen, zu qualifizieren und zu quantifizieren, indem Sie so viele Benchmarks wie möglich ausführen, was wahrscheinlich weniger als eine Woche dauern würde: D

Answer 2

Dies ist nicht die Antwort, aber kann nicht in den Kommentaren schreiben. Das beste Darstellungsformat hängt von der zugrunde liegenden Implementierung ab. Zum Beispiel

lassen

M = [m_11 m_12 m_13; == [r1; == [c1 c2 c3] 
    m_21 m_22 m_23]  r2] 

wo r1,2 sind die Zeilen und Spalten sind c1,2,3 und

v = [v1; 
    v2; 
    v3] 

Sie können M * v als

M*v = [r1.v; 
     r2.v] 

implementieren

als Punktprodukt von Vektoren oder

M*v = v1*c1 + v2*c2 + v3*c3 

wobei * die skalare Vektormultiplikation ist.

Sie können die Anzahl der Operationen minimieren, indem Sie das Format in Abhängigkeit von der Matrixgröße auswählen. Je weniger Zeilen/Spalten, desto besser.