Faustregel für spärliche oder dichte Matrixspeicherung

9

Angenommen, ich kenne die erwartete Sparsamkeit einer Matrix (dh die Anzahl der Nicht-Nullen / die insgesamt mögliche Anzahl der Nicht-Nullen). Gibt es eine Faustregel (möglicherweise eine ungefähre Angabe) für die Entscheidung, ob ein spärlicher Matrixspeicher (insbesondere ein komprimierter Zeilenspeicher) verwendet oder als dichte Matrix gespeichert werden soll?

  1. Geschwindigkeit ist in meiner Anwendung wichtiger als Speicher. Aus allgemeiner Neugier bin ich jedoch an Antworten aus Sicht der Geschwindigkeit und des Gedächtnisses interessiert.
  2. Nach dem Generieren der Matrix wende ich nur Additions- und Multiplikationsoperationen darauf an.
  3. Ich konnte nur qualitative Antworten finden, zB diese Frage und diese Frage, aber ich suche nach so etwas

... wenn die Sparsity mehr als ungefähr beträgt , verwenden Sie dichten Speicher.x%

EM_IE
quelle

Antworten:

8

Alle Matrixoperationen sind auf heutigen Prozessoren speichergebunden (und nicht rechnergebunden). Grundsätzlich müssen Sie sich fragen, in welchem ​​Format weniger Bytes gespeichert sind. Dies ist einfach zu berechnen:

  • Für eine vollständige Matrix speichern Sie 8 Bytes (ein Doppel) pro Eintrag
  • Für eine dünn besetzte Matrix speichern Sie 12 Bytes pro Eintrag (ein Double für den Wert und eine Ganzzahl für den Spaltenindex des Eintrags).

Mit anderen Worten, wenn Ihre Sparsity unter 67% liegt - dh für fast jede Matrix, die eine vernünftige Person als sparse bezeichnen würde -, führt das sparse-Matrix-Format nicht nur zu einer besseren Speichernutzung, sondern auch zu einer besseren Rechenzeit.

Wolfgang Bangerth
quelle
Ich würde gerne hören, warum jemand diese Antwort abgelehnt hat. Es ist qualitativ, quantitativ und gibt eine gute Faustregel. Wenn ich es zweimal positiv bewerten könnte, würde ich es tun.
Charles
3
Sie benötigen etwas mehr Speicherplatz - Sie müssen auch die Zeilen im Auge behalten. Ein Bit pro Zeile ist ausreichend.
Brian Borchers
3
Die Matrix-Matrix-Multiplikation dichter Matrizen ist ein Ort, an dem Sie eine ausreichende Wiederverwendung des Cache erhalten, um den Spitzen-FLOPS sehr nahe zu kommen. Ich bin damit einverstanden, dass die Matrixvektormultiplikation die Speicherbandbreite begrenzt.
Brian Borchers
1
67% sind tatsächlich sehr weit von dem Punkt entfernt, an dem Berechnungen von der Sparsamkeit profitieren würden. Eine dichte Matrix-Vektor-Multiplikation kann wesentlich stärker vom Caching profitieren. (Sie benötigen einen sehr unregelmäßigen Speicherzugriff für die Multiplikation von Matrix-Vektoren mit geringer Dichte.) Wenn es darum geht, lineare Systeme mit einem direkten Löser zu lösen, wird manchmal gesagt, dass eine Matrix dünn ist, wenn sie weniger als 0,1% der Werte ungleich Null aufweist. In der Praxis ist die tatsächliche Konnektivität der Matrixeinträge jedoch viel wichtiger als die Anzahl der Nicht-Nullen.
Henrik Schumacher
1
@WolfgangBangerth: Ihre Definition von "spärlich" ("spärlich" bedeutet, dass die Anzahl der Einträge ungleich Null pro Zeile unabhängig von der Größe für eine Reihe von Matrizen ist, die immer größer werden) unterscheidet sich erheblich von der Definition von JH Wilkinson (informelles Arbeiten) : "Jede Matrix mit genügend Nullen, die sich auszahlt, um sie auszunutzen", was in der Literatur häufig zitiert wird. Ich bevorzuge Wilkinsons Definition.
wim
11

Für zufällige spärliche Matrizen der Größe 10.000 x 10.000 im Vergleich zu dichten Matrizen der gleichen Größe war auf meiner Xeon-Workstation mit MATLAB und Intel MKL als BLAS die Multiplikation des spärlichen Matrixvektors bei Dichten von 15% schneller oder weniger. Mit 67% (wie in einer anderen Antwort vorgeschlagen ) war die dichte Matrix-Vektor-Multiplikation etwa dreimal schneller.

Brian Borchers
quelle
Interessant, danke. Einige meiner Matrizen sind bis zu 30-40% spärlich (ungünstigerweise genau zwischen den Schätzungen von 15% und 67%), daher sollte ich wahrscheinlich ähnliche Tests wie Sie durchführen (für die Operationen, an denen ich interessiert bin), um festzustellen, ob der Speicher vorhanden ist Vorteile sind die Verlangsamung wert.
EM_IE
3
Viel hängt von der verwendeten Hardware und Software ab. Mein Gerät verfügt über einen Quad-Channel-Speicher, sodass es mehr Speicherbandbreite als ein typisches Dual-Channel-System hat. MKL ist ein sehr gutes BLAS und die spärlichen Matrixdatenstrukturen von MATLAB sind möglicherweise nicht perfekt dafür optimiert.
Brian Borchers
1
Ein Problem beim komprimierten Zeilenspeicher (oder beim komprimierten Spaltenspeicher) besteht darin, dass die Einträge normalerweise in einem anderen Speicherbereich als die Indexinformationen gespeichert werden. Dieser Mangel an Lokalität kann die Leistung beeinträchtigen. Im Vergleich dazu können Sie beim herkömmlichen dichten Matrixspeicher (nach Zeilen (C) oder Spalten (Fortran)) Einträge der Matrix nacheinander effizienter aus dem Speicher laden.
Brian Borchers
1
In den letzten Jahren wurden neue Speicherformate für dünn besetzte Matrizen erforscht, die eine verbesserte Leistung für die Multiplikation von spärlichen Matrixvektoren auf Mehrkernprozessoren, Maschinen mit SIMD-Anweisungen und GPUs ermöglichen. Siehe zum Beispiel: pdfs.semanticscholar.org/041b/…
Brian Borchers
5

Selbst wenn eine Matrix sehr dünn ist, kann ihr Matrixprodukt mit sich selbst dicht sein. Nehmen Sie zum Beispiel eine Diagonalmatrix und füllen Sie ihre erste Zeile und Spalte mit Einträgen ungleich Null. sein Produkt mit sich selbst wird vollständig dicht sein. Eine solche Matrix kann beispielsweise als Graph Laplace eines Graphen entstehen, in dem sich ein Scheitelpunkt befindet, der mit allen anderen Scheitelpunkten verbunden ist. In der Praxis reicht es aus, wenn es nur wenige Eckpunkte mit ziemlich hoher Konnektivität zum Rest des Netzwerks gibt. Für die Matrixvektormultiplikation ist dieses Phänomen weniger relevant, obwohl es zu Ungleichgewichten führen kann, wenn versucht wird, die Matrixvektormultiplikation zu parallelisieren.

Was ich hervorheben möchte: Es hängt wirklich vom Sparsity-Muster ab und davon, was Sie mit der Matrix machen möchten. Die beste Definition einer spärlichen Matrix, die ich finden kann (die gleichzeitig ziemlich nutzlos ist), lautet also wie folgt:

Eine Matrix ist spärlich, wenn es vorteilhaft ist, nur ihre Werte ungleich Null und ihre Positionen zu speichern und den zusätzlichen Aufwand zu investieren, der durch die Verwaltung der entstehenden Datenstruktur entsteht.

Die Lektion zu lernen: Es hängt wirklich davon ab, was Sie damit machen möchten , welchen Algorithmus Sie verwenden und (wie andere bereits betont haben) welche Hard- und Software Sie verwenden, ob eine bestimmte Matrix spärlich ist oder nicht (lesen Sie als: ob Sie eine spärliche oder dichte Matrixdatenstruktur verwenden sollten). Es kann keine rein prozentuale Regel geben, wenn es nicht nur um das Speichern von Daten oder die Multiplikation von Matrixvektoren geht. Der beste Weg, um herauszufinden, ob Ihre Matrizen spärlich sind, besteht darin, es zu versuchen und mit Methoden mit dichter Matrix zu vergleichen.

Henrik Schumacher
quelle
1
Der berühmte JH Wilkinson definierte eine spärliche Matrix als: "Jede Matrix mit genügend Nullen, die sich auszahlen, um sie auszunutzen." Genau diese Definition wurde von anderen häufig zitiert. Trotzdem ist Ihre Definition auch durchaus geeignet.
wim
1
Nett. Genau diese Definition versuchte ich nachzuahmen, aber ich konnte mich nicht an die Quelle erinnern.
Henrik Schumacher