News Steamroller (Bulldozer_v3) bekommt eine Radix-8-Dividierer-Einheit

[Opteron]

<div class="newsfloatleft"><a href="123"><img src="http://www.planet3dnow.de/photoplog/images/54308/1_AMD-Logo.png" border="0" alt="AMD-Logo"></a></div>Wie wir gerade auf <a href="http://twitter.com/#!/Dresdenboy" target="b">Dresdenboys Twitterseite</a> gesehen haben, gab es eine Publikation zu dem Dividierer-Part der Steamroller-FPU. Steamroller - der Nachfolger der Piledriver-Architektur, die erstmals in den kommenden Chips Trinity und Vishera Verwendung finden wird - ist damit also die dritte Generation der Bulldozerfamilie. <a href="http://www.planet3dnow.de/cgi-bin/newspub/viewnews.cgi?id=1328302051">Diese ist bereits für 2013 - für den Trinity-Nachfolger Kaveri - angekündigt</a>. Laut <a href="http://www.russinoff.com/papers/srt8.pdf" target="b">diesem Papier</a> bekommt Steamroller eine Radix-8-Divisor-Einheit. Selbige ist Teil der FPU und nicht nur für das Geteilt-durch, sondern auch für das Wurzelziehen zuständig. <p style="clear:left;"></p>Entwickler des Ganzen ist mit David M. Russinoff die gleiche Person, die auch schon für die <a href="http://view.samurajdata.se/psview.php?id=52148583&page=1&all=1" target="b">DIV-Einheit Llanos verantwortlich war</a>. Letztere war einer der wenigen Unterschiede zu den früheren K10-Chips, die noch ohne DIV-Hardwareunterstützung auskommen mussten. Bulldozer teilt dieses Schicksal, Divisionen werden in den FMAC-Units "nur" mittels eines Zustandsautomaten berechnet. Steamroller bekommt nun aber wie Llano eine Hardwaredivisionseinheit spendiert. Natürlich aber nicht 1:1 die Gleiche, denn anstatt einer Radix-4 Einheit wird eine Radix-8 Version implementiert. Das bedeutet einfach, dass in einem Schritt nicht zwei Bits des Ergebnisses berechnet werden, sondern gleich drei Bits.

Alte Kenner der CPU-Szene werden bei "Radix" vielleicht hellhörig. Mit diesem kryptischen Ausdruck wird nicht zum ersten Mal geworben. Intel hatte schon seinerzeit bei den ersten 45nm-CPUs (Codename Penryn) die Werbetrommeln gerührt. Allerdings wurde damals - und auch noch bei den aktuellen Chips - gleich eine Radix-16 Einheit implementiert:

<center><a href="http://www.planet3dnow.de/photoplog/index.php?n=18717"><img src="http://www.planet3dnow.de/photoplog/file.php?n=18717&w=o" border="0" alt="alte Intel Radix-16 Penryn Folie"></a>
<FONT SIZE=-2>Quelle: Intel</FONT></center>

Warum AMD nicht den gleichen Weg einschlägt ist zuerst verwunderlich. Vor allem vor dem Hintergrund, dass sich zwei Kerne eine FPU teilen müssen, erschiene eine aufwendigere Lösung logischer. Naheliegendste Erklärung dürfte wohl ein zu hoher Strom- oder Transistorenverbrauch sein. Eine CPU bei der Division zu optimieren, ist verhältnismäßig uninteressant, da in jedem Programmierhandbuch steht, dass man anstatt einer Division mit dem Kehrwert multiplizieren sollte. Die Verwendung ist also eher gering. Das einfache Weglassen der DIV-Einheit scheint aber vermutlich auch keine gute Idee zu sein,es gibt ja auch noch die Wurzelfunktionen. Von daher scheint eine Radix-8-Implementierung möglicherweise wieder ein guter Kompromiss aus Aufwand und Nutzen zu sein.

<b>Links zum Thema:</b><ul><li><a href="http://www.planet3dnow.de/cgi-bin/newspub/viewnews.cgi?id=1328302051">AMD Analystentag 2012, der Tag danach: Piledriver 10h & 20h; Fragezeichen bei 28nm CPU-Updates</a></li><li><a href="http://www.russinoff.com/papers/srt8.pdf" target="b">Paper zu Steamrollers DIV-Einheit</a></li><li><a href="http://www.russinoff.com/papers/srt.ps" target="b">Paper zu Llanos DIV-Einheit (Postscript)</a></li></ul>

 

[kalkzone]

verlinkt auf irgendeinen ELPIDE - blabla

 

[Opteron]

verlinkt auf irgendeinen ELPIDE - blabla

Ach die brauchts hier sowieso nicht, da wir schon im Kommentarthread sind ... weg ist sie

 

[JonZales]

Aber wie berechnet man denn den Kehrwert ohne Division?

Ja die Frage ist ernst gemeint.
Ja ich habe verstanden das eine entsprechende Einheit verbaut wird.
Ja ICH weiß das der Kehrwert von 0,2 -> 5 ist (die CPU eher nicht). Aber ich weiß nicht den Kehrwert von 0,2414587 ohne zu dividieren.

 

[Makso]

Und ich verstehe nur Bahnhof was damit gemeint ist. Sorry
Kann mich eine richtig aufklären?
danke

 

[TheFox]

Aber wie berechnet man denn den Kehrwert ohne Division?

Ja die Frage ist ernst gemeint.
Ja ich habe verstanden das eine entsprechende Einheit verbaut wird.
Ja ICH weiß das der Kehrwert von 0,2 -> 5 ist (die CPU eher nicht). Aber ich weiß nicht den Kehrwert von 0,2414587 ohne zu dividieren.

Ein schlauer Compiler könnte das ja vor der Umsetzung in Maschinencode über die Dividiereinheit berechnen

 

[JonZales]

DAS war jetz irgendwie nich sonderlich hilfreich. ^^

 

[MSIler]

Aber wie berechnet man denn den Kehrwert ohne Division?

Ja die Frage ist ernst gemeint.
Ja ich habe verstanden das eine entsprechende Einheit verbaut wird.
Ja ICH weiß das der Kehrwert von 0,2 -> 5 ist (die CPU eher nicht). Aber ich weiß nicht den Kehrwert von 0,2414587 ohne zu dividieren.

ein guter compiler wird aber wissen, dass 0,2414587=2414587/10000000 sind und dessen kehrwert ist 10000000/2414587 mit dem man dann multiplizieren kann.

 

[[MTB]JackTheRipper]

Der stellt dir deine Division einer Konstanten aber auch gleich in ne Multiplikation um
.
EDIT :
.

0,2414587=2414587/10000000

ähm

 

[TheFox]

Was macht denn der Compiler (oder ich) ab besten, wenn im Quelltext z.B. a/b steht und die Werte zur Übersetzungszeit noch nicht bekannt sind?

Ist a*pow(b,-1) schneller? Kann ich mir nicht vorstellen. Genausowenig wie a*1/b.

Ist in diesem Fall nicht die Dividiereinheit nötig?

 

[JonZales]

@MSIler: Bombe! Seit wann ersetzen Schrägstriche das Dividieren?

@Fox: Dit is ja mein Problem.

 

[Opteron]

Ne, der Witz ist eben, dass man für den Kehrwert *keine* Division benötigt, das geht über ein paar Shift-Operation, die sehr "billig" zu haben sind. Allerdings muss man dazu 1/x "etwas" umformen *g*

Weiteres hier:
http://tech.yanto-flora.net/e-070917-015947_How_to_Compute_the_Reciprocal_of_A_Value

 

[Dresdenboy]

@Opteron:
Das hast du ja noch ganz schön ausgeweitet. Ich hätte noch 2 Dinge:

Der Link zum PDF-Llano-Paper fehlte zwar auf der Webseite, aber es existiert als PDF:
http://www.russinoff.com/papers/srt.pdf

Und im Anandtech-Forum hat da auch noch einer eine interessante Aussage im Paper bzgl. Radix-16/32-Dividierern gefunden:
http://forums.anandtech.com/showpost.php?p=33075640&postcount=179

 

[JonZales]

Danke Opteron!
Ich hatte überlegt es über iteration zu machen, aber da hätte es ja keinen Unterschied gemacht obs nun mit Kehrwert läuft oder eben nicht.

Das es auf der Bit-ebene so einfach zu realisieren ist war mir nicht bewußt/bekannt.

 

[Ge0rgy]

Das geht aber auch nicht in allen Fällen.
es ist zwar ok, dass bevor ich
val/2 eben val *0.5 schreiben kann.
Und analog statt /100 eben *0,01 aber bei /3 wirds schon schwieriger.
Abgesehen davon, wenn ich eine ganzzahl dividiere, ist das immernoch langsamer als die umwandlung in eine fließkommazahl mit FP-Mul?
Kann ich mir bei dem Aufwand irgendwie auch kaum vorstellen...!?

 

[[MTB]JackTheRipper]

Letztlich stellt sich die Frage eher an die Compilerentwickler.

 

[Opteron]

@Opteron:
Das hast du ja noch ganz schön ausgeweitet. Ich hätte noch 2 Dinge:

Der Link zum PDF-Llano-Paper fehlte zwar auf der Webseite, aber es existiert als PDF:
http://www.russinoff.com/papers/srt.pdf

Ah Danke, viel einfacher als das Postscript.

Und im Anandtech-Forum hat da auch noch einer eine interessante Aussage im Paper bzgl. Radix-16/32-Dividierern gefunden:
http://forums.anandtech.com/showpost.php?p=33075640&postcount=179

Auweia ... heilige Sch....e, soll das heißen alle CPUs seit Penryn haben ne Art FDIV-Bug? Das wär ja ne ziemlich dicke Meldung...
Ich hab mir beim schreiben noch gedacht, dass das Radix8, vielleicht irgendwas mit der Korrektheit der Ergebnisse zu tun hätte, von denen der Forscher da ziemlich oft schreibt, aber den Satz mit dem Radix16 hab ich überlesen

Preisfrage ist nun: Ist das Intel Radix16 basierend auf den zitierten Radix16-Paper von 2005, oder nicht? Bei Intel würde ich da mal nicht 100%ig ausschließen, dass sie irgendwas dranbasteln. Aber falls das Paper von nem Intel-Ingenieur war, dann würde ich mal sagen: ja. Muss da aber erstmal die Namen checken.

Edit:
Wohl kein Intel Mitarbeiter:

Peter Kornerup received the mag.scient. de-gree in mathematics from Aarhus University,
De nm ar k, i n 1 9 67 . A f t er a pe r i o d wi t h t h e
Univers ity Comput ing Cent er, from 196 9 he was involved i n e stab lishing th e compu ter science curriculum at Aarhus University, where he helped found the Computer Science Depart-ment in 1971. Through most of the 1970s and1980s, he served as chairman of that depart-ment. Since 1988, he has been a professor of computer science at Odense University, now the University of Southern Denmark, where he has also served a period as the chairman of the department. His interests include compiler construction, microprogram-ming, computer networks, and computer architecture, but, in particular,his research has been in computer arithmetic and number representa-tions, with applications in cryptology and digital signal processing. He has served on the program committees for numerous IEEE, ACM, and other meetings; in particular, he has been on the program committees for the fourth through the 16th IEEE Symposia on Computer Arithmetic and served as program cochair for these symposia in 1983, 1991, and 1999. He has been a guest editor for a number of journal special issues and served as an associate editor of the IEEE Transactions on Computers during 1991-1995. He is a member of the IEEE.

Da leg ich mich vorerst lieber noch nicht mit Intel an - In dubio pro reo

 

[OBrian]

Also für mich liest sich das auch wie ein ganz großer Hammer, wenn er schreibt: "Wir beweisen hier, daß die bisherige Methode fehlerhaft ist". Andererseits, falsche Rechenergebnisse der Intel-CPUs seit 2005 wären doch aufgefallen, wenn man sie mit den durch andere CPUs auf andere Weise erhaltenen Ergebnissen verglichen hätte, was man sicher auch hat, oft genug. Intel müßte dann ja schon selbst während der Entwicklung aufgefallen sein, daß da was nicht paßt, meinetwegen auch erstmal ohne zu wissen wieso.

Also ich für meinen Teil muß da einfach erstmal Auswertungen von in dem Fach weitaus versierteren Leuten als mir abwarten, bevor ich dazu irgendwas meinen kann.

 

[Opteron]

Hab das Paper jetzt noch einmal (richtig) gelesen. Revidiere meine obige Aussage, im ersten Paragraphen in der Einleitung wird deutlich Intel (und IBM) erwähnt den SRT-Algo zu benützen. Dann wird weiter erzählt, dass dieser Algo eben nicht 100% Wasserdicht wäre. Da besteht ein direkter Bezug. Beim schnellen Durchlesen wird das nicht ganz deutlich, da sich der Bezug hinter den Quellen angaben [5],[7] und [15] versteckt. 15 ist er dabei selber mit der Llano DIV-Einheit, aber die ist nur Radix-4 was seit dem P1 FDIV-Bug einigermaßen geprüft wurde und von Ihm auch noch ausführlich.

Wieso ein Bug bisher nicht aufgefallen ist .. gute Frage ... hier schreibt er, dass besonders die Wurzelberechnung kompliziert ist:

and, like earlier efforts, ours did not address the more complicated problem of square root extraction.

Eventuell gibts dann nur beim Wurzelberechnen ein paar Fehler. Aber wann braucht man das schon? Selbst im HPC-Bereich gibts doch in den meisten Fällen nur Matrix-Multiplikationen.

Zweite Sache die ich von oben auch revidieren muss:
Wenn ein Algo implementiert wird, der fehlerhaft ist, dann kann man daran durch "Herumbasteln" , Extratransistoren oder was auch immer, wohl kaum was am Fehler ändern - es sei denn man ändert dann den Algo.

Fazit: Die Intels sind potentiell buggy. Aber wahrscheinlich tritt der Fall noch seltener als AMDs TLB-Bug auf

 

[genervt]

Mh. Ich meine gelesen zu haben, dass der Radix16 von Intel auf zwei sich überlappenden Radix4 basiert. Damit würde man mglw. diesen theor. Bug umgehen. Man bewegt sich dann nur auf breit ausgetretenen Radix4 Pfaden.

Hier einige Folien dazu, aber einen konkreten Beweis, dass es so auch in den Intel verwendet wird, habe ich noch nicht finden können:

Die Intel-Beschreibung
http://www.intel.com/technology/itj/2008/v12i3/3-paper/8-radix.htm

Papers zu overlapping Quotient Selection
www2.imm.dtu.dk/~an/pubs/ARITH20.pdf
Auszug:
"The proposed unit is compared to a radix-4 combined division/square root unit, and to a radix-16 unit, obtained by cascading two radix-4 stages, which is similar to the one implemented in a state-of-the-art processor."

www.acsel-lab.com/arithmetic/papers/ARITH07/ARITH07_Taylor.pdf