Gibt es einen offensichtlichen Grund, dass Tensorflow ein anderes COO-Format als CSR für die spärliche Matrix verwendet?

Question

Ich versuche, Leistungsvorteile von integrierten Sparse Matrix Multiplikation API von Tensorflow zu nehmen. Und keveman empfohlen, dass tf.embedding_lookup_sparse ist der richtige Weg.

Aber es scheint, dass die Leistung embedding_lookup_sparse ist etwas enttäuscht in my experiments. Obwohl es ziemlich kleine Matrixmultiplikationen ausführt, kann < 1, 3196> und < 3196, 1024>, spärliches Matmul mit 0,1 Sparsity die dichte Matrixmultiplikation nicht gewinnen.

Wenn meine Implementierung korrekt ist, denke ich, dass Tensorflow das COO-Format verwendet, das alle Index-Nullen-Paare speichert. Ich bin kein Experte in diesem Bereich, aber ist nicht allgemein bekannt, dass das CSR-Format bei dieser Art von Berechnung leistungsfähiger ist? Gibt es einen offensichtlichen Grund dafür, dass Tensorflow intern ein anderes COO-Format als CSR für die Darstellung einer spärlichen Matrix verwendet?

Answer 1

Nur für das Protokoll, Sie sagen Matrix Multiplikation, aber eine Ihrer Matrizen ist in der Tat ein Vektor (1 x 3196). So würde es eine Matrix-Vektor-Multiplikation machen (verschiedene BLAS-Kernel). Ich nehme an, Sie meinen Matrix-Vektor-Multiplikation für meine Antwort.

Ja, CSR sollte theoretisch schneller sein als COO für Matrix-Vektor-Multiplikation; Dies liegt daran, dass die Speichergröße im CSR-Format O(2nnz + n) vs O(3nnzs) ist und die Sparse-Matrix-Vektormultiplikation in vielen Fällen speichergebunden ist.

Der genaue Leistungsunterschied im Vergleich zu einer dichten Matrixmultiplikation variiert jedoch basierend auf der Problemgröße, dem Sparsymuster, dem Datentyp und der Implementierung. Es ist schwierig, spontan zu sagen, was schneller sein sollte, weil das Sparse-Speicherformat eine Indirektion einführt, was potentiell zu einer verringerten Lokalität und einer schlechten Verwendung von Recheneinheiten führt (z. B. keine Verwendung von Vektorisierung).

Besonders wenn die Matrix und die Vektorgröße so klein sind, dass fast alles in den Cache passt, würde ich begrenzte Leistungsvorteile erwarten. Spärliche Matrixstrukturen sind typischerweise für wirklich große Matrizen, die von 10 sK × 10 sK bis 1B × 1B reichen, die unter Verwendung einer dichten Darstellung nicht einmal in den Hauptspeicher passen würden, nützlicher. Bei kleinen Problemgrößen wird meiner Erfahrung nach der Speichervorteil im Vergleich zu dichten Formaten normalerweise durch den Verlust an Lokalität und arithmetischer Effizienz zunichte gemacht. Bis zu einem gewissen Grad wird dies durch hybride Speicherformate (wie zum Beispiel Block CSR) behoben, die versuchen, das Beste aus beiden Welten zu nutzen, und sind für einige Anwendungen sehr nützlich (sieht nicht so aus, als ob tensorflow dies unterstützt).

In tensorflow, würde ich annehmen, das COO-Format verwendet wird, weil es effiziente für andere Operationen, ist es beispielsweise unterstützt O(1) Updates, Einfügungen und Löschungen aus der Datenstruktur. Es scheint vernünftig zu sein, ~ 50% Leistung in spärlichen Matrix-Vektor-Multiplikationen zu tauschen, um die Leistung bei diesen Operationen zu verbessern.