Warum beschleunigt das Ausdrücken von Berechnungen als Matrixmultiplikationen diese?

In Googles MNist-Tutorial mit TensorFlow wird eine Berechnung gezeigt, bei der ein Schritt der Multiplikation einer Matrix mit einem Vektor entspricht. Google zeigt zunächst ein Bild, in dem jede numerische Multiplikation und Addition, die für die Berechnung erforderlich wäre, vollständig ausgeschrieben ist. Als nächstes zeigen sie ein Bild, in dem es stattdessen als Matrixmultiplikation ausgedrückt wird, und behaupten, dass diese Version der Berechnung schneller ist oder zumindest sein könnte:

Wenn wir das als Gleichungen schreiben, erhalten wir:

Wir können dieses Verfahren "vektorisieren" und es in eine Matrixmultiplikation und Vektoraddition umwandeln. Dies ist hilfreich für die Recheneffizienz. (Es ist auch eine nützliche Art zu denken.)

Ich weiß, dass Gleichungen wie diese normalerweise von maschinell lernenden Praktikern im Matrixmultiplikationsformat geschrieben werden und dies natürlich unter dem Gesichtspunkt der Code-Knappheit oder des Verständnisses der Mathematik als vorteilhaft angesehen werden kann. Was ich nicht verstehe, ist Googles Behauptung, dass das Konvertieren von der Langschriftform in die Matrixform "für die Recheneffizienz hilfreich ist".

Wann, warum und wie können Leistungsverbesserungen in Software erzielt werden, indem Berechnungen als Matrixmultiplikationen ausgedrückt werden? Wenn ich als Mensch die Matrixmultiplikation im zweiten (matrixbasierten) Bild selbst berechnen würde, würde ich jede der im ersten (skalaren) Bild gezeigten unterschiedlichen Berechnungen nacheinander ausführen. Für mich sind sie nichts anderes als zwei Notationen für die gleiche Abfolge von Berechnungen. Warum ist das bei meinem Computer anders? Warum kann ein Computer die Matrixberechnung schneller ausführen als die skalare?

Dies mag offensichtlich klingen, aber Computer führen keine Formeln aus , sie führen Code aus , und wie lange diese Ausführung dauert, hängt direkt von dem Code ab, den sie ausführen, und nur indirekt von dem Konzept, das der Code implementiert. Zwei logisch identische Codeteile können sehr unterschiedliche Leistungsmerkmale aufweisen. Einige Gründe, die bei der Matrixmultiplikation auftreten können:

• Mehrere Threads verwenden. Es gibt kaum eine moderne CPU, die nicht über mehrere Kerne verfügt, viele verfügen über bis zu 8 Kerne, und spezialisierte Computer für Hochleistungs-Computing können problemlos 64 Kerne über mehrere Sockel verteilen. Das offensichtliche Schreiben von Code in einer normalen Programmiersprache verwendet nur eine davon. Mit anderen Worten, es werden möglicherweise weniger als 2% der verfügbaren Computerressourcen des Computers verwendet, auf dem es ausgeführt wird.
• Verwendung von SIMD-Anweisungen (verwirrenderweise wird dies auch als "Vektorisierung" bezeichnet, jedoch in einem anderen Sinne als in den Textzitaten in der Frage). Geben Sie der CPU im Wesentlichen anstelle von 4 oder 8 oder so skalaren Arithmetikbefehlen einen Befehl, der die Arithmetik für 4 oder 8 oder so Register parallel ausführt. Dies kann buchstäblich einige Berechnungen (wenn sie vollkommen unabhängig und für den Befehlssatz geeignet sind) 4 oder 8-mal schneller machen.
• Den Cache intelligenter nutzen . Der Speicherzugriff ist schneller, wenn sie zeitlich und räumlich kohärent sind, dh aufeinanderfolgende Zugriffe erfolgen auf nahe gelegene Adressen, und wenn Sie zweimal auf eine Adresse zugreifen, greifen Sie zweimal schnell hintereinander auf sie zu, anstatt mit einer langen Pause.
• Verwenden von Beschleunigern wie GPUs. Diese Geräte unterscheiden sich stark von CPUs, und ihre effiziente Programmierung ist eine ganz eigene Kunstform. Beispielsweise haben sie Hunderte von Kernen, die in Gruppen von einigen Dutzend Kernen zusammengefasst sind, und diese Gruppen teilen sich Ressourcen - sie teilen sich einige KB Speicher, der viel schneller als normaler Speicher ist, und wenn ein Kern der Gruppe eine ausführt ifAnweisung alle anderen in dieser Gruppe müssen darauf warten.
• Verteilen Sie die Arbeit auf mehrere Computer (sehr wichtig bei Supercomputern!), Was eine Menge neuer Kopfschmerzen mit sich bringt, aber natürlich den Zugriff auf erheblich größere Computerressourcen ermöglicht.
• Intelligentere Algorithmen. Für die Matrixmultiplikation ist der einfache O (n ^ 3) -Algorithmus, der mit den obigen Tricks optimiert wurde, oft schneller als die subkubischen für angemessene Matrixgrößen, aber manchmal gewinnen sie. Für spezielle Fälle wie dünne Matrizen können Sie spezielle Algorithmen schreiben.

Viele clevere Leute haben sehr effizienten Code für gängige lineare Algebra-Operationen geschrieben , wobei sie die oben genannten und viele weitere Tricks verwendeten und normalerweise sogar plattformspezifische Tricks. Daher profitiert die Umwandlung Ihrer Formel in eine Matrixmultiplikation und die anschließende Implementierung dieser Berechnung durch Aufrufen einer ausgereiften Bibliothek für lineare Algebra von diesem Optimierungsaufwand. Wenn Sie dagegen die Formel einfach auf offensichtliche Weise in einer höheren Sprache ausschreiben, wird der schließlich generierte Maschinencode nicht alle diese Tricks verwenden und ist auch nicht so schnell. Dies gilt auch, wenn Sie die Matrixformulierung nehmen und durch Aufrufen einer von Ihnen selbst erstellten naiven Matrixmultiplikationsroutine implementieren (ebenfalls auf offensichtliche Weise).

Das schnelle Erstellen von Code nimmt Arbeit in Anspruch , und oft ist es ziemlich viel Arbeit, wenn Sie die letzte Unze Leistung wünschen. Da so viele wichtige Berechnungen als Kombination mehrerer linearer Algebraoperationen ausgedrückt werden können, ist es wirtschaftlich, hochoptimierten Code für diese Operationen zu erstellen. Ihr einmaliger spezieller Anwendungsfall? Das interessiert niemanden außer Ihnen, so dass es nicht wirtschaftlich ist, das Ganze zu optimieren.

(spärliche) Matrix-Vektor-Multiplikation ist stark parallelisierbar. Das ist sehr praktisch, wenn Ihre Daten umfangreich sind und Sie über eine Serverfarm verfügen.

Dies bedeutet, dass Sie die Matrix und den Vektor in Blöcke aufteilen und separate Maschinen einen Teil der Arbeit erledigen lassen können. Teilen Sie dann einige ihrer Ergebnisse miteinander und erhalten Sie dann das Endergebnis.

In Ihrem Beispiel wären die Operationen wie folgt

1. Richten Sie ein Raster mit Prozessoren ein, die jeweils ein Wx, y entsprechend ihrer Koordinate im Raster enthalten

2. Broadcast des Quellvektors entlang jeder Spalte (Kosten O(log height))

3. habe jeden prozessor zur multiplikation vor ort (kosten O(width of submatrix * heightof submatrix))

4. Reduziere das Ergebnis entlang jeder Zeile mit einer Summe (Kosten O(log width))

Diese letzte Operation ist gültig, da die Summe assoziativ ist.

Dies ermöglicht auch das Einrichten von Redundanz und vermeidet, dass alle Informationen auf einem einzigen Computer gespeichert werden müssen.

Für kleine 4x4-Matrizen, wie Sie sie in Grafiken sehen, liegt es daran, dass die CPU spezielle Anweisungen und Register hat, um mit diesen Operationen umzugehen.

Am aufschlussreichsten wäre es, die Leistung Ihres Codes mit der Leistung der bereits implementierten Matrixmultiplikation zu vergleichen.

Es gibt immer eine niedrigere Optimierungsebene, an die Sie nicht gedacht haben. Hier finden Sie ein Beispiel:

https://simulationcorner.net/index.php?page=fastmatrixvector