Multiplizieren–Akkumulieren-Operation - Multiply–accumulate operation

In der Computertechnik , insbesondere bei der digitalen Signalverarbeitung , ist die Multiply-Accumulate ( MAC ) oder Multiply-Add ( MAD ) Operation ein üblicher Schritt, der das Produkt zweier Zahlen berechnet und dieses Produkt zu einem Akkumulator addiert . Die Hardwareeinheit, die die Operation durchführt, wird als Multiplikator-Akkumulator ( MAC-Einheit ) bezeichnet; die Operation selbst wird oft auch als MAC- oder MAC-Operation bezeichnet. Die MAC-Operation modifiziert einen Akkumulator a :

Bei Gleitkommazahlen kann dies mit zwei Rundungen (typisch in vielen DSPs ) oder mit einer einzigen Rundung erfolgen. Wenn es mit einer einzelnen Rundung durchgeführt wird, wird es als fusioniertes Multiplizieren-Addieren ( FMA ) oder fusioniertes Multiplizieren-Akkumulieren ( FMAC ) bezeichnet.

Moderne Computer können einen dedizierten MAC enthalten, der aus einem Multiplizierer besteht, der in kombinatorischer Logik implementiert ist, gefolgt von einem Addierer und einem Akkumulatorregister, das das Ergebnis speichert. Der Ausgang des Registers wird an einen Eingang des Addierers rückgekoppelt, so dass bei jedem Taktzyklus der Ausgang des Multiplizierers zum Register addiert wird. Kombinatorische Multiplikatoren erfordern viel Logik, können aber ein Produkt viel schneller berechnen als die für frühere Computer typische Methode des Verschiebens und Addierens . Percy Ludgate war der erste, der in seiner Analytical Machine von 1909 einen MAC konzipierte, und der erste, der einen MAC zur Division ausnutzte (unter Verwendung einer Multiplikation, die durch Reziproke gesät wurde, über die konvergente Reihe (1+ x ) −1 ). Die ersten modernen Prozessoren, die mit MAC-Einheiten ausgestattet wurden, waren digitale Signalprozessoren , aber die Technik ist heute auch bei Universalprozessoren üblich.

In Gleitkomma-Arithmetik

Wenn es mit ganzen Zahlen gemacht wird , ist die Operation normalerweise exakt (berechnet modulo eine Zweierpotenz ). Allerdings Gleitkommazahlen haben Zahlen nur eine bestimmte Menge mathematischer Präzision . Das heißt, digitale Gleitkommaarithmetik ist im Allgemeinen nicht assoziativ oder distributiv . (Siehe Gleitkomma § Genauigkeitsprobleme .) Daher macht es für das Ergebnis einen Unterschied, ob die Multiplikation-Addition mit zwei Rundungen oder in einer Operation mit einer einzigen Rundung (eine fusionierte Multiplikation-Addition) durchgeführt wird. IEEE 754-2008 gibt an, dass es mit einer Rundung durchgeführt werden muss, um ein genaueres Ergebnis zu erzielen.

Fusioniert multiplizieren – addieren

Eine fusionierte Multiplikations-Addition ( FMA oder fmadd ) ist eine Gleitkomma-Multiplikations-Additionsoperation, die in einem Schritt mit einer einzigen Rundung durchgeführt wird. Das heißt, wenn eine nicht verschmolzene Multiplikations-Addition das Produkt b × c berechnen würde , es auf N signifikante Bits runden würde , das Ergebnis zu a addieren und auf N signifikante Bits zurückrunden würde, würde eine verschmolzene Multiplikations-Addition den gesamten Ausdruck a + . berechnen ( b × c ) auf seine volle Genauigkeit, bevor das Endergebnis auf N signifikante Bits abgerundet wird.

Eine schnelle FMA kann die Genauigkeit vieler Berechnungen beschleunigen und verbessern, die die Akkumulation von Produkten beinhalten:

Mit Fused Multiply-Add kann man sich in der Regel auf genauere Ergebnisse verlassen. Doch William Kahan hat darauf hingewiesen , dass es Probleme geben kann , wenn gedankenlos verwendet. Wenn x 2 − y 2 als (( x × x ) − y × y ) ausgewertet wird ( gemäß der von Kahan vorgeschlagenen Notation, in der redundante Klammern den Compiler anweisen, den ( x × x ) -Term zuerst zu runden ) mit fusioniertem Multiplizieren-Addieren, dann das Ergebnis kann sogar dann negativ sein, wenn x = y ist, da die erste Multiplikation Bits mit niedriger Wertigkeit verwirft. Dies könnte dann zu einem Fehler führen, wenn dann zB die Quadratwurzel des Ergebnisses ausgewertet wird.

Bei Implementierung innerhalb eines Mikroprozessors kann eine FMA schneller sein als eine Multiplikationsoperation gefolgt von einer Addition. Jedoch erfordern industrielle Standardimplementierungen, die auf dem ursprünglichen IBM RS/6000-Design basieren, einen 2 N- Bit-Addierer, um die Summe richtig zu berechnen.

Ein weiterer Vorteil der Einbeziehung dieses Befehls besteht darin, dass er eine effiziente Softwareimplementierung von Divisions- (siehe Divisionsalgorithmus ) und Quadratwurzeloperationen (siehe Verfahren zum Berechnen von Quadratwurzeln ) ermöglicht, wodurch die Notwendigkeit für dedizierte Hardware für diese Operationen eliminiert wird.

Dot-Produktanleitung

Einige Maschinen kombinieren mehrere fusionierte Multiply-Add-Operationen in einem einzigen Schritt, z. B. Durchführen eines Vier-Elemente-Punktprodukts an zwei 128-Bit- SIMD- Registern a0×b0 + a1×b1 + a2×b2 + a3×b3mit einem Durchsatz in einem einzigen Zyklus.

Die Unterstützung

Der FMA-Betrieb ist in IEEE 754-2008 enthalten .

Der VAX - Befehl der Digital Equipment Corporation (DEC) wird zum Bewerten von Polynomen mit der Horner-Regel unter Verwendung einer Folge von Multiplikations- und Addierschritten verwendet. Befehlsbeschreibungen geben nicht an, ob das Multiplizieren und Addieren unter Verwendung eines einzigen FMA-Schritts durchgeführt wird. Dieser Befehl ist seit seiner ursprünglichen 11/780-Implementierung im Jahr 1977 Teil des VAX-Befehlssatzes. POLY

Der Standard von 1999 der Programmiersprache C unterstützt die FMA-Operation durch die fma()standardmäßige mathematische Bibliotheksfunktion und Standard-Pragmas ( #pragma STDC FP_CONTRACT), die Optimierungen basierend auf FMA steuern.

Die fusionierte Multiply-Add-Operation wurde als "multiply-add fused" im IBM POWER1 (1990)-Prozessor eingeführt, ist aber seitdem zu zahlreichen anderen Prozessoren hinzugefügt worden:

Verweise