HN-Vorstellung: Matrixmultiplikation mit halb so vielen Multiplikationen

Neue Hardware-Architektur für Machine Learning

• Dieses Repository enthält den Quellcode für eine ML-Hardware-Architektur, die die gleiche Leistung wie herkömmliche Inner-Product-Berechnungen erreicht, dabei aber nur fast die Hälfte der Multiplikationsoperationen benötigt.
• Durch die Nutzung von Additionen mit geringer Bitbreite als Ersatz für fast die Hälfte der Multiplikationen führt sie einen alternativen Inner-Product-Algorithmus aus und erhöht so die theoretischen Grenzen von Durchsatz und Recheneffizienz von ML-Beschleunigern.
• Weitere Details finden sich in einem im Journal IEEE Transactions on Computers veröffentlichten Paper.

Neuer Algorithmus und neue Hardware-Architektur

• Vorgestellt werden ein neuer Algorithmus und eine Hardware-Architektur namens Free-pipeline Fast Inner Product (FFIP).
• Er verbessert den 1968 von Winograd vorgeschlagenen Fast-Inner-Product-Algorithmus (FIP).
• FIP steht in keinem Zusammenhang mit dem Winograd-Minimal-Filtering-Algorithmus, der auf konvolutionale Layer angewendet wird, und kann auf alle Layer von ML-Modellen angewendet werden, die sich hauptsächlich auf Matrixmultiplikation zurückführen lassen.
• Es wird die erste Implementierung von FIP in einem ML-Beschleuniger vorgestellt sowie der FFIP-Algorithmus und eine verallgemeinerte Architektur, die die Taktfrequenz von FIP und den daraus resultierenden Durchsatz verbessern.
• Zudem werden ML-spezifische Optimierungen für die FIP- und FFIP-Algorithmen sowie -Architekturen beigetragen.
• FFIP lässt sich nahtlos in bestehende Fixed-Point-Systolic-Array-ML-Beschleuniger integrieren, um mit halb so vielen Multiply-Accumulate-(MAC-)Einheiten den gleichen Durchsatz zu erreichen oder bei festem Hardware-Budget eine größere maximale Systolic-Array-Größe umzusetzen.
• FFIP-Implementierungen für nicht-sparse ML-Modelle mit 8- bis 16-Bit-Fixed-Point-Eingaben erreichen auf derselben Art von Computing-Plattform höheren Durchsatz und bessere Recheneffizienz als führende Lösungen.

Struktur des Quellcodes

• compiler: enthält einen Compiler, der Python-Modellbeschreibungen in Beschleunigerbefehle parst, sowie Interface-Code zum PCIe-Treiber, der die Modellausführung auf dem Beschleuniger startet, Ergebnisse und Performance-Counter ausliest und die Korrektheit der Ergebnisse testet.
• rtl: enthält synthesefähiges SystemVerilog-RTL.
• sim: enthält Skripte zum Einrichten einer Simulationsumgebung für Tests.
• tests: enthält UVM-basierten Testbench-Quellcode, der den Beschleuniger in der Simulation mit Cocotb verifiziert.
• utils: enthält zusätzliche Python-Pakete und Skripte, die im Projekt verwendet werden, sowie allgemeine Entwicklungs-Utilities und Hilfen, die vom Autor erstellt wurden.

Meinung von GN⁺

• Dieser Artikel stellt einen innovativen Fortschritt bei ML-Hardware-Architekturen vor und beschreibt insbesondere einen neuen Algorithmus und eine neue Architektur, die Multiplikationsoperationen reduzieren, ohne die Leistung zu verringern. Das ist ein wichtiger Fortschritt, der die Effizienz von ML-Berechnungen deutlich verbessern kann.
• Der FFIP-Algorithmus fügt bestehenden Entwürfen von ML-Beschleunigern eine neue Dimension hinzu und bietet eine Möglichkeit, Hardware-Ressourcen effizienter zu nutzen. Das ist in heutigen Computing-Umgebungen, in denen Energieeffizienz und Kosteneffizienz wichtig sind, besonders relevant.
• Damit sich diese Technologie breit durchsetzt, müssen jedoch die Kompatibilität mit bestehenden ML-Beschleunigern, das Verständnis der Entwickler für die neue Architektur sowie Leistungs- und Kostenfragen bei der Implementierung in realer Hardware berücksichtigt werden.
• Vergleichbare Projekte oder Produkte mit ähnlicher Funktionalität sind etwa Googles TPU (Tensor Processing Unit) oder NVIDIAs CUDA-Kerne, die bereits am Markt etablierte ML-Beschleunigerlösungen sind.
• Bei der Einführung neuer Technologien oder von Open Source sollten die Kompatibilität mit bestehenden Systemen, mögliche Kostensteigerungen im Verhältnis zum Performance-Gewinn sowie die Komplexität von Entwicklung und Wartung berücksichtigt werden. Zu den Vorteilen von FFIP gehören höherer Durchsatz und bessere Recheneffizienz; mögliche Nachteile sind die Lernkurve für Entwickler bei neuen Systemen und anfängliche Implementierungskosten.

[GN⁺]

Hacker-News-Kommentare

• Diese Technik wirkt beeindruckend, aber ich frage mich, warum sie nicht bereits in Beschleunigern umgesetzt wurde – ob es sich einfach um einen vergessenen Algorithmus handelt oder ob der Bau von Beschleunigern dadurch teurer wird oder andere Nachteile entstehen.
• In dieser Arbeit geht es darum, eine Matrixmultiplikations-Pipeline in Hardware zu synthetisieren, was in Hardware wie FPGA oder ASIC nützlich sein könnte. Auf CPU oder GPU dauern Multiplikation und Addition normalerweise gleich lang, aber Multiplikationseinheiten belegen mehr Transistoren. Wenn man also die Schaltungskomplexität reduziert, kann man Geschwindigkeit und parallelen Durchsatz erhöhen und zugleich Energieverbrauch sowie Routing-Komplexität senken.
• Eine weitere Möglichkeit, Multiplikationen in der Matrixmultiplikation zu eliminieren, ist die Verwendung verschiedener Semiringe. Zum Beispiel ersetzt der Tropical Semiring Multiplikation durch Addition und Addition durch das Minimum (oder Maximum). Es handelt sich also weiterhin um Matrixmultiplikation, nur dass die binären Operationen ausgetauscht werden. Forschung im Bereich der Tropical Algebra wird für Optimierungsprobleme und für die Optimierung neuronaler Netze verwendet und ist derzeit aktiv und umfangreich.
• Auch die Verwendung des Log Semiring ist eine effiziente Methode, Multiplikationen zu eliminieren. Wenn man eine Kette von Wahrscheinlichkeiten multiplizieren muss (z. B. in einer Markov-Kette), werden die Zahlen sehr klein, sodass Gleitkommazahlen an Genauigkeit verlieren. Skaliert man die Zahlen logarithmisch, wird Multiplikation zu Addition und Addition zu x + log1p(exp(y - x)).
• Es überrascht mich, dass dieser Ansatz tatsächlich funktioniert, weil schon die Entscheidung, ob man Multiplikation oder Addition verwendet, langsamer sein könnte als einfach direkt zu multiplizieren – besonders wenn große Mengen an Arbeit parallel verarbeitet werden.
• Dass dieses Verfahren bereits 1968 erfunden wurde und bis heute nicht für diesen Zweck verwendet worden ist, finde ich äußerst interessant.
• Ich habe 2018 ein ähnliches Konzept ausprobiert, aber alle meine Bewerbungen für Promotionsprogramme wurden abgelehnt, daher habe ich aufgegeben. Das Konzept hier versucht, Backpropagation in einem externen Netzwerk zu replizieren, und behauptet, dass dies wahrscheinlich das ist, was das Gehirn tatsächlich tut.
• Wenn du dich für die mathematische Theorie subkubischer Algorithmen für Matrixmultiplikation interessierst, kannst du hier anfangen. Es wird vermutet, dass es Zahlen ( n ) gibt, für die sich alle ( n \times n )-Matrizen in ( O(n^{2+j}) ) Schritten multiplizieren lassen (inzwischen bewiesen für ( 2+j = w = 2.3728596 ) bzw. ( j > 0.3728596 )).
• Dieses Readme erklärt nur sehr unzureichend, worin die Verbesserung besteht oder wie die Anzahl der Multiplikationen halbiert wird. Auch die Big-O-Laufzeit und ob sich dadurch die beste bekannte Schranke ändert, bleiben unklar. Die Diagramme sind verwirrend und erklären nicht, warum dieser Ansatz schnell und gut sein soll. Das führt dazu, dass ich nicht einmal Lust habe, auf das PDF zu klicken. Um die Glaubwürdigkeit des Projekts zu erhöhen, sollte man eine ehrliche und klare Erklärung samt anschaulichen Illustrationen dazu liefern, was hier tatsächlich passiert.