fma(a,b,c) entspricht a*b+c, außer dass das Zwischenergebnis nicht abgerundet wird.Welche Algorithmen profitieren am meisten von fusioniertem Multiply Add?
Können Sie mir einige Beispiele für Algorithmen nennen, die nicht von dieser Rundung profitieren?
Es ist nicht offensichtlich, da Rundungen nach Multiplikationen, die wir vermeiden, weniger problematisch sind als Rundungen nach Addition, was wir nicht tun.
taw traf auf ein wichtiges Beispiel; Im Allgemeinen erlaubt FMA Bibliotheksautoren, viele andere Fließkommaoperationen mit korrekter Rundung effizient zu implementieren.
Zum Beispiel kann eine Plattform, die über ein FMA verfügt, diese verwenden, um eine korrekt gerundete Division und Quadratwurzel zu implementieren (PPC und Itanium nahmen diesen Ansatz an), wodurch die FPU grundsätzlich eine Einzweck-FMA-Maschine sein kann. Peter Tang und John Harrison (Intel) und Peter Markstein (HP) haben einige Artikel, die diese Verwendung erklären, wenn Sie neugierig sind.
Das Beispiel taw ergab, ist breiter als nur in Tracking-Fehler Grenzen nützlich. Sie können das Produkt zweier Gleitkommazahlen als Summe zweier Gleitkommazahlen ohne Rundungsfehler darstellen. Dies ist sehr nützlich beim Implementieren von korrekt gerundeten Fließkomma-Bibliotheksfunktionen. Jean-Michel Mullers Buch oder die Papiere auf crlibm wären gute Startplätze, um mehr über diese Anwendungen zu erfahren.
FMA eignet sich auch weitgehend zur Reduzierung von Argumenten in Math-Library-Routinen für bestimmte Arten von Argumenten; Wenn man die Argumentreduktion durchführt, ist das Ziel der Berechnung oft ein Ausdruck der Form (x - a*b), wobei (a*b) sehr ähnlich zu x selbst ist; insbesondere liegt das Ergebnis oft in der Größenordnung des Rundungsfehlers im (a*b) Begriff, wenn dieser ohne FMA berechnet wird. Ich glaube, dass Muller darüber auch in seinem Buch geschrieben hat.
Aus der Spitze von meinem Kopf - Matrix-Multiplikation, Newtons Regel Polynombewertung, numerische Methoden
Der Hauptvorteil der FMA ist, dass es doppelt so schnell sein kann. Statt einen Zyklus für die Multiplikation und dann einen Zyklus für die Addition zu nehmen, kann die FPU beide Operationen in demselben Zyklus ausgeben. Offensichtlich profitieren die meisten Algorithmen von schnelleren Operationen.
Einige Beispiele: Vektor-Dot-Produkte. Fourier-Transformationen. Digitale Signalverarbeitung. Polynome. Alle möglichen Dinge.
Es ist eine Frage der Optimierung und Hardwareauswertung mehr als alles andere. Eine Summe von Produkten ist eine sehr häufige Anforderung in numerischen Methoden, und auf diese Weise können Sie dem Compiler eine explizite Anweisung geben, wie Sie eine Sache schnell und vielleicht mit ein wenig mehr Präzision ausführen können. Wenn ich mich nicht irre, ist der Compiler frei, a = b * c + d durch eine FMA-Anweisung zu ersetzen, aber es ist auch kostenlos, dies nicht zu tun. (es sei denn, der Standard fordert eine Rundung, aber reale Compiler verletzen regelmäßig routinemäßig die Standards).
Der Compiler kann b * c + d nicht durch eine FMA ersetzen, es sei denn, Sie sagen dem Compiler ausdrücklich, dass er OK ist (mit -ffast-math oder etwas Ähnlichem), da er die Ergebnisse stört. –
@StephenLin: Unter der Annahme, dass die Bewertung von 'b',' c' und 'd' nicht mutiert oder andere Nebenwirkungen hat, wie kann eine solche Hardware-Optimierung die Ergebnisse" stören "? – stakx
@stakx: Viele der zusammengesetzten Anweisungen in einem Fließkomma-Befehlssatz sind da, weil der Rundungsfehler das Ergebnis überschwemmen würde. Beispiel: Wenn Sie e^(nahe bei Null) nehmen, liegt das Ergebnis nahe bei eins, aber das begrenzt Ihre Präzision erheblich. Wenn Sie eine Anweisung haben, die e^epsilon-1 repräsentiert, dann kann die Hardware eine viel größere Genauigkeit geben. Jede gegebene Hochsprache kann so definiert werden, dass sie Zugang zu der präziseren Anweisung bietet oder den Ausdrucksbaum unter erkennbaren Umständen neu schreibt. Ersteres ist vorhersehbarer. – Ian
Das einzige, was ich bisher gefunden habe, sind "fehlerfreie Transformationen". Für Gleitkommazahlen sind Fehler von , a-b und a*b auch Gleitkommazahlen (in der runden zum nächsten Modus, vorausgesetzt, kein Überlauf/Unterlauf usw. usw.).
Addition (und offensichtlich Subtraktion) Fehler ist einfach zu berechnen; Wenn abs(a) >= abs(b), Fehler ist genau b-((a+b)-a) (2 Flops oder 4-5, wenn wir nicht wissen, welche größer ist). Multiplikation Fehler ist trivial zu berechnen mit fma - es ist einfach fma(a,b,-a*b). Ohne fma ist es 16 Flops von ziemlich bösen Code. Und vollständig generische Emulation von korrekt gerundet fma ist sogar langsamer als das.
Extra 16 Flops Fehler Tracking pro Flop der realen Berechnung ist ein riesiger Overkill, aber mit nur 1-5 Pipeline-freundliche Flops ist es durchaus sinnvoll, und für viele Algorithmen auf der Grundlage dieser 50% -200% Overhead der Fehlerverfolgung und die Kompensation ergibt einen Fehler, der so klein ist, als ob alle Berechnungen in doppelter Anzahl von Bits durchgeführt würden, wodurch in vielen Fällen eine schlechte Konditionierung vermieden würde.
Interessanterweise wird fma nicht immer in diesen Algorithmen verwendet, um Ergebnisse zu berechnen, nur Fehler zu finden, weil die Suche nach Fehler von fma ist ein langsamer als Fehler der Multiplikation ohne fma war zu finden.
Relevante Schlüsselwörter zu suchen wäre "kompensiertes Horner-Schema" und "kompensiertes Dot-Produkt", mit Horner-Schema profitieren viel mehr.
Ich frage mich, wie die Hardwarekosten von FMA auf 'float'-Werten mit den Hardwarekosten einer Operation verglichen würden, die das Vollpräzisionsprodukt von zwei' float'-Werten zu einem 'double' hinzufügte. Durch mein Verständnis ist die Kosten-Hardware einer "doppelten" Multiplikation mehr als viermal so groß wie eine gleich schnelle "float" -Multiplikation, die ein Ergebnis mit voller Genauigkeit ergibt, und für viele Operationen wie dot-product ist es notwendig, Zwischenwerte mit mehr zu halten Genauigkeit als die Operanden oder Endergebnis. Die Verwendung von Multiplizieren und Fma zusammen könnte funktionieren, aber die Verwendung einer f * f + d-Operation würde doppelt so schnell erscheinen. – supercat
Es wurde ziemlich gut erklärt auf der Wikipedia entry for FMA, dass die Algorithmen, die etwas mit Anhäufung von Produkten profitieren am meisten von der Verwendung FMA zu tun:
A fast FMA can speed up and improve the accuracy of
many computations that involve the accumulation of products:
* Dot product
* Matrix multiplication
* Polynomial evaluation (e.g., with Horner's rule)
* Newton's method for evaluating functions.
Frage geht es um Auswirkungen der Rundung, nicht darüber. Ihre Antwort ist auch falsch, da fma 3 Eingabe-Fließkomma-Einheit anstelle von 2 Standard-Eingaben, Extraport in Fließkomma-Registerdatei und breitere Gleitkomma-Addierer benötigt. Dies ist nicht kostenlos, es ist ein Kompromiss von fma-Unterstützung auf Kosten von einigen andere Hardware. – taw
taw: Sie haben gefragt, welche Algorithmen von FMA profitieren und für einige Beispiele, wo die Rundung ein nicht-trivialer Vorteil ist. Ich habe den ersten Teil beantwortet, was bedeutet, dass die meisten Algorithmen davon profitieren werden. – Gabe