- Der Intel Pentium von 1993 enthielt eine dedizierte ×3-Schaltung, die für schnelle Gleitkomma-Multiplikationen den dreifachen Wert erzeugte; allein diese kleine Schaltung nutzte Tausende Transistoren
- Der Pentium verwendet bei 64-Bit-Multiplikationen Radix-8-Multiplikation, um die Zahl der zu addierenden Terme von 64 auf 22 zu reduzieren; dafür müssen jedoch ×3-Vielfache schnell erzeugt werden
- Die ×3-Berechnung selbst ist zwar nur eine Addition
x + 2x, doch weil die übrigen Multiplikationsschritte auf dieses Ergebnis warten, sind schnelle Addierer-Techniken wie Carry Lookahead und Kogge-Stone nötig - Die Schaltung ist hierarchisch aufgebaut: acht 8-Bit-Blöcke werden mit einem übergeordneten Lookahead kombiniert; wegen Überlauf und Rundung ist die tatsächliche Ausgabe auf 69 Bit verbreitert
- Dass rund 9000 Transistoren für eine einzige ×3-Schaltung eingesetzt wurden, zeigt, wie viel komplexe Hardware-Optimierung in der Pentium-Generation für Performance investiert wurde
Warum der Pentium eine eigene ×3-Schaltung hatte
- Der Gleitkomma-Multiplizierer des Pentium multipliziert zwei 64-Bit-Zahlen im Radix-8-Verfahren
- Bei gewöhnlicher binärer Multiplikation wird für jedes Bit entweder 0 oder der Multiplikand addiert, sodass bei einer 64-Bit-Multiplikation 64 Terme nötig sind
- Beim Radix-8-Verfahren werden die Bits des Multiplikators in Dreiergruppen zusammengefasst und mit einem Wert von 0 bis 7 multipliziert; dadurch sinkt die Zahl der zu addierenden Terme auf 22
- Einige der Vielfachen von 0 bis 7 lassen sich in Hardware vergleichsweise einfach erzeugen
- ×2 wird durch eine Linksverschiebung um 1 Bit erledigt
- ×4 wird durch eine Linksverschiebung um 2 Bit erledigt
- ×6 und ×7 lassen sich mit dem Booth-Multiplikationsalgorithmus behandeln, indem ein +1 in der nächsten Radix-8-Stelle mit einer Subtraktion in der aktuellen Stelle kombiniert wird
- ×5 kann gewonnen werden, indem man ×3 von ×8 abzieht
- Das schwierige Vielfache ist damit letztlich ×3, und der Pentium löst dies mit einer dedizierten Schaltung innerhalb des Gleitkomma-Multiplizierers
Wo eine einfache Addition zum Flaschenhals wird
- Der dreifache Wert kann erzeugt werden, indem man den Eingabewert und den um ein Bit nach links verschobenen Eingabewert addiert
- Strukturell ist das eine Addition
x + 2x
- Strukturell ist das eine Addition
- Der Flaschenhals entsteht bei der Carry-Propagation während der Addition
- Bei einem Ripple-Carry-Addierer muss ein Carry aus den unteren Bits nacheinander bis zu den höheren Bits weitergereicht werden
- Bevor das ×3-Ergebnis bereitsteht, kann der restliche Multiplikationsprozess nicht beginnen; daher muss die Verzögerung reduziert werden
- Der Pentium verwendet einen Carry-Lookahead-Addierer, um die Carries nicht sequenziell weiterzureichen, sondern parallel zu berechnen
- Für jedes Bit werden Carry-generate- und Carry-propagate-Signale erzeugt
- Generate zeigt an, dass an dieser Position ein Carry erzeugt wird
- Propagate zeigt an, dass ein eingehender Carry weitergegeben wird
- Wenn die Carries parallel berechnet werden, können auch die Summenbits parallel berechnet werden
Kogge-Stone und zweistufiger Carry Lookahead
- Würde man Carry Lookahead einfach direkt implementieren, stiege mit der Bitzahl der Aufwand für Schaltung und Verdrahtung stark an
- Je höher die Bitposition, desto komplexer wird die Logik
- Gatter mit vielen Eingängen werden aus elektrischen Gründen langsamer
- Der Pentium nutzt Kogge-Stone-Parallel-Prefix-Addierer in 8-Bit-Einheiten
- Kogge-Stone führt Propagate-/Generate-Signale bereichsweise zusammen und berechnet Carries parallel
- Zwischenergebnisse werden wiederverwendet, um Verzögerung und Schaltungsumfang zu kontrollieren
- Statt die gesamten 64 Bit mit einem einzigen Kogge-Stone zu verarbeiten, wird die Schaltung in eine zweistufige Hierarchie aufgeteilt
- Die untere Ebene berechnet mit acht 8-Bit-Kogge-Stone-Schaltungen die Carries innerhalb jedes Blocks
- Die obere Ebene betrachtet jeden 8-Bit-Block als eine Einheit und berechnet die Carries zwischen den Blöcken
- Zusammen liefern die beiden Ebenen die für die 64-Bit-Summe benötigten Carries schnell
- Die Schaltung kann als 64-Bit-Schaltung betrachtet werden, tatsächlich erzeugt sie aber inklusive Zusatzbits für Überlaufschutz und Rundung eine 69-Bit-Ausgabe
Carry-Select reduziert die Wartezeit
- Jeder 8-Bit-Block enthält einen Carry-Select-Addierer
- Die Summe wird vorab für beide Fälle berechnet: Carry-in gleich 0 und Carry-in gleich 1
- Wenn die übergeordnete Lookahead-Schaltung den tatsächlichen Carry-in liefert, wählt ein Multiplexer das richtige Ergebnis aus
- Dieses Verfahren spart Zeit auf Kosten zusätzlicher Hardware
- Es werden zwei Addierer und ein Multiplexer zur Ergebnisauswahl benötigt
- Summenberechnung und Carry-Berechnung überlappen sich, wodurch die Gesamtverzögerung sinkt
- Der unterste 8-Bit-Block hat keinen Carry-in und braucht daher keine Carry-Select-Schaltung
- Die Ausgabebits dieses Blocks werden mit XNOR-Gattern berechnet
Was in einem 8-Bit-Block passiert
- Jeder 8-Bit-Block der ×3-Schaltung teilt die Eingangsleitungen in einen linken Addierer und einen rechten Pfad auf
- Diese Verzweigungsstruktur implementiert ×3, indem sie den Eingabewert und den um ein Bit nach links verschobenen Eingabewert addiert
- Der obere Bereich des Blocks besteht aus Schaltungen, die Propagate-/Generate-Signale erzeugen
- Diese Signale gehen in die 8-Bit-Kogge-Stone-Lookahead-Schaltung
- Der Kogge-Stone-Teil hat je nach Bitposition unterschiedliche Komplexität und sieht daher nicht wie ein wiederholter Block aus, sondern unregelmäßig
- Der untere Bereich des Blocks ist die Carry-Select-Addierer-Zone
- Zwei Summen werden vorab berechnet, und ein Multiplexer wählt je nach Carry-in aus
- Der Carry-Select-Addiererblock ist schmaler als die umgebende Schaltung angeordnet, um Platz für Teile der übergeordneten Kogge-Stone-Schaltung zu schaffen
- Jeder Block verstärkt die Ausgabebits über Treiber-Schaltungen, bevor er sie an die nächste Multiplizierer-Schaltung weitergibt
XNOR-Gatter und Implementierung auf Transistorebene
- Die XNOR-Gatter im unteren Bitbereich sind im Pentium als Multiplexer implementiert
- Der Intel 386 implementierte XOR mit AND-NOR-Gattern, und der Z-80 verwendete Pass-Transistoren; der Ansatz des Pentium ist jedoch ein anderer
- Die betreffende XNOR-Schaltung besteht aus vier Invertern und einem Pass-Transistor-Multiplexer
- Eingang B wählt im Multiplexer zwischen Eingang A und dem invertierten A
- Daraus entsteht die XNOR-Funktion
- Bei der Analyse der Chipfotos wurden die oberen beiden Metallschichten entfernt, um die untere Metallschicht M1 und die dotierten Siliziumbereiche zu betrachten
- Stellen, an denen eine Polysilizium-Leitung dotiertes Silizium kreuzt, bilden Transistorgates
- Die CMOS-Schaltung besteht aus obenliegenden NMOS- und untenliegenden PMOS-Transistoren
BiCMOS-Ausgangstreiber
- Die Ausgabe der ×3-Schaltung benötigt hohen Strom
- Jedes ×3-Signal kann innerhalb des Gleitkomma-Multiplizierers bis zu 22 Terme treiben
- Die Zielschaltung kann weit von der ×3-Schaltung entfernt liegen
- Durch lange Leitungen und viele Transistorgates steigt die Kapazität, und um Signale schnell umzuschalten, wird hoher Strom benötigt
- Der Pentium verwendet einen BiCMOS-Prozess, der Bipolartransistoren und CMOS auf demselben Chip kombiniert
- Der Pentium nutzte BiCMOS-Schaltungen umfangreich, um Signalverzögerungen um bis zu 35 % zu reduzieren
- Intel setzte BiCMOS auch beim Pentium Pro, Pentium II, Pentium III und Xeon ein
- Als die Chipspannungen sanken, nahmen die Vorteile von Bipolartransistoren ab, sodass BiCMOS schließlich nicht mehr verwendet wurde
- Der Treiber der ×3-Schaltung ist so aufgebaut, dass ein BiCMOS-Treiber wiederum einen zweiten BiCMOS-Treiber ansteuert
- Da die Transistorgates des Hochstrom-Inverters groß sind, ist eine Zwischenstufe nötig, um ihn zu treiben
- Wenn ein kleines Signal in mehreren Stufen verstärkt wird, kann die Gesamtverzögerung reduziert werden
- Die NPN-Transistoren des BiCMOS-Treibers erscheinen im Gegensatz zu gewöhnlichen MOS-Transistoren als große kastenförmige Strukturen
- Der Inverter verwendet die Standard-CMOS-Struktur: PMOS zieht den Ausgang nach oben, NMOS zieht ihn nach unten
- Einige Inverter sind mit asymmetrischen Stromcharakteristiken ausgelegt, um ein starkes High- oder ein starkes Low-Signal zu liefern
Die wachsende Komplexität von Multiplikationshardware
- Die Geschichte der Multiplikationshardware in Computern reicht bis in die 1950er-Jahre zurück
- Die Booth-Multiplikationsmethode wurde 1951 beschrieben
- Parallele Multiplizierer wurden Mitte der 1960er-Jahre von Wallace und Dadda vorgeschlagen
- Frühe Mikroprozessoren hatten nur begrenzte Hardwareunterstützung für Multiplikation
- Prozessoren wie der 6502 hatten keine Multiplikationshardware, sodass Nutzer Multiplikation per Shift und Addition in Software implementieren mussten
- Der Intel 8086 führte per Mikrocode eine langsame Shift-and-Add-Schleife aus
- Der 386 enthielt zwar eine multiply unit, doch eine Multiplikationsinstruktion konnte bis zu 41 Taktzyklen dauern
- Zur Pentium-Zeit konnten Millionen Transistoren integriert werden, wodurch komplexere Performance-Optimierungen möglich wurden
- Eine Gleitkomma-Multiplikation des Pentium dauert 3 Taktzyklen, wobei die Multiplikationsschaltung während 2 dieser Zyklen genutzt wird
- Die Ganzzahlmultiplikation
MUList mit 11 Zyklen deutlich langsamer - Die Nehalem-Mikroarchitektur von 2008 reduzierte die Zeit für Gleitkomma-Multiplikationen auf 1 Zyklus
- Der ×3-Multiplizierer des Pentium enthält rund 9000 Transistoren
- Das ist etwas mehr als der gesamte Z80-Mikroprozessor von 1976
- Die ×3-Schaltung ist nur ein kleiner Teil des Gleitkomma-Multiplizierers in der Gleitkommaeinheit des Pentium
1 Kommentare
Hacker-News-Kommentare
Das ist zwar ein ziemlicher Nebenaspekt, aber vor langer Zeit habe ich bei der Arbeit an einer Emulation eines ternären Computers einen hübschen Trick verwendet, um eine geschlossene Transformation zu finden, die Divisionen durch Potenzen von 3 in eine Reihe aus Bit-Shifts und Additionen umwandelt.
Zuerst betrachtet man
1/3 - 1/2 = 2/6 - 3/6, also1/3 = 1/2 - 1/2 (1/3).Setzt man diesen Ausdruck unendlich oft in die rechte Seite ein, erhält man eine Form wie
1/3 = -(-1/2)^N, wobeiNim Bereich1..infliegt.Das funktioniert nicht nur für Paare aus Potenzen von 2 und 3, sondern ähnlich auch in anderen Zahlensystemen.
Bedeutet: Für Werte nahe einer Zweierpotenz kann man mit nur Addierern und Subtrahierern recht einfach eine Konstantzeit-Schaltung für Division durch eine Konstante bauen.
Der Prozessor der Cinematronics-Arcade-Spiele hat zwei 12-Bit-Akkumulatoren.
Der Multiplikationsbefehl shiftet beide nach rechts, als wären sie ein einzelner 24-Bit-Wert, und addiert den Speicherinhalt, wenn aus dem niederwertigsten Bit eine 1 herauskommt.
Also löscht man die obere Hälfte, lädt einen Wert in die untere Hälfte, ich habe vergessen, wie die Speicheradresse des anderen Operanden gesetzt wurde, und führt dann mehrfach hintereinander 1-Bit-Multiplikationen aus.
So erhält man ein 24-Bit-Produkt, aber der Code, den ich gesehen habe, verwendete meistens 8 Multiplikationen hintereinander; der häufigste Einsatz war 2x2-Matrixmultiplikation zur Rotation von Spielobjekt-Koordinaten.
Das wurde Mitte der 1970er mit handelsüblichen Bauteilen der 7400-Serie gebaut, mit einem Spitzendurchsatz von 5 MIPS.
In den letzten 20 Jahren musste ich ein paarmal Festkomma-Arithmetik machen, und mein Respekt vor Programmierern früherer Generationen ist gewachsen.
Ergänzend zu der Stelle, dass man vielleicht schon von Techniken wie
carry lookaheadoderKogge-Stone additiongehört hat: Kogge ist hier Peter Kogge.Er promovierte in Stanford, arbeitete am Space Shuttle, ist IBM Fellow und gilt als Erfinder der ersten Multicore-CPU.
Eine „Multicore-CPU“ ist streng genommen eher eine Idee als eine einzelne Erfindung. An einem bestimmten Punkt der Halbleitergeschichte ist sie auch eine ziemlich offensichtliche und triviale Idee.
Eine Multicore-CPU tatsächlich zum Laufen zu bringen, ist nicht trivial, aber auch das ist keine einzelne Erfindung; zu diesem Zeitpunkt waren die Entwicklungsteams schon so groß, dass es eher beleidigend ist zu behaupten, eine Person habe alle Probleme allein gelöst.
Kogge mag die Entwicklung der ersten Multicore-CPU geleitet haben, und er mag ein Pionier gewesen sein, der darauf drängte, bevor andere es für möglich hielten; so oder so hat er sie nicht allein erfunden.
Dieser Ansatz lässt sich intellektuell gut begründen. Wenn es Latenz oder Kosten verursacht, Daten in zentrale Rechenanlagen zu verschieben, ist er sinnvoll; in unserem Fall ging es um weltraumgestützte Sensoren, daher konnte man so argumentieren.
Soweit ich weiß, wurde diese Art der Verarbeitung allerdings nie systematisch in weltraumgestützten Verarbeitungssystemen übernommen, auch wenn viele Systeme wie Radar ad-hoc Datenreduktion auf Hardware nahe am Sensor durchführen.
Danke für den Hinweis auf diese Verbindung.
Ich bin der Autor. Wenn es Fragen gibt, beantworte ich sie gern.
x4vonx7abziehen, umx3zu erhalten?Mir scheint, da fehlt etwas.
Wenn ×2 so leicht zu berechnen ist, dass man 6x = 8x - 2x nutzen kann, und ×4 mit 4x = 4x ebenfalls leicht zu berechnen ist, warum ist es dann schwieriger, 3x als Summe aus 2x + 1x oder als Differenz 4x - 1x zu berechnen?
Außerdem: Wenn ×6 auf irgendeine Weise leicht berechnet werden kann, warum kann man diesen Wert nicht nach rechts shiften, um ×3 zu erhalten? Das wäre zwar ein zusätzlicher Schritt, aber dieser zusätzliche Schritt ist nur ein Shift.
Jeder Term muss trivial zu berechnen sein; man kann also shiften oder das Vorzeichen umkehren, um einen Term zu erhalten, aber keine weitere Addition durchführen.
Der Kernpunkt ist: Wenn man ×3 einmal vorab berechnet, kann man ihn danach einfach an jeder der 22 Stellen einsetzen, an denen er gebraucht wird.
Man kann innerhalb eines Terms nicht ×2 und ×1 einsetzen, um ×3 zu bilden. Dafür bräuchte man für jeden Term einen weiteren Addierer.
Anders gesagt: Gewünscht ist eine Schaltung zur Berechnung von ×3, nicht 22 Schaltungen.
Zur Frage nach ×6: Dieser Wert wird berechnet, indem man einen negativen ×2-Term einsetzt und konzeptionell zur nächsten Ziffer 1 addiert, um ×8 zu erhalten. Dieser ×8-Wert ist Teil eines ganz anderen Terms und kann daher nicht nach rechts geshiftet werden.
Durch die vielen Zahlen und Summen wird es kompliziert, aber so betrachtet sollte es Sinn ergeben.
Multiplikation mit 3 ist tatsächlich eine häufige Operation, besonders bei Adressberechnungen, bei denen ein Index oft per Shift und Addition mit 3 multipliziert wird.
Naiv implementiert erhöht das die Latenz erheblich. Mit dieser Schaltung kann die LEA-Anweisung (Load Effective Address) aber in einem Zyklus verarbeitet werden; dafür ein solches Transistorbudget auszugeben, war also durchaus eine gute Entscheidung.
LEA ist lediglich eine Anweisung, die die vom Adressierungsmodus berechnete Adresse in den Zieloperanden schreibt, statt Daten von dieser Adresse zu laden; und alle Adressberechnungen, die LEA kann, kann auch die MOV-Anweisung.
Der Index-Adressierungsmodus, den MOV oder LEA auf x86 verwenden, unterstützt keinen Skalierungsfaktor 3, sondern nur Zweierpotenzen wie 1, 2, 4, 8. Daher gibt es bei der Adresserzeugung keinen Einsatzort für eine 3-fach-Multiplikation.
Der Artikel sagt klar, dass der 3-fach-Multiplizierer Teil des Gleitkomma-Multiplizierers ist.
„Dieser ×3-Multiplizierer enthält ungefähr 9000 Transistoren, etwas mehr als der gesamte Z80-Mikroprozessor (1976). Man sollte bedenken, dass der ×3-Multiplizierer nur ein kleiner Teil des Gleitkomma-Multiplizierers in der Gleitkommaeinheit des Pentium ist. Anders gesagt: Ein kleines Stück einer Funktion ist komplexer als ein kompletter Mikroprozessor von vor 17 Jahren; das zeigt, wie enorm die Komplexität von Prozessoren gewachsen ist.“
Diese Geschwindigkeit des Leistungswachstums hat die heutige Software-Bloat hervorgebracht. Denn die Leistungssteigerung des nächsten Jahres konnte die meisten Sünden überdecken, bei denen man Algorithmen sowie Kontext und Lokalität von Datenflüssen nicht kritisch bedacht hatte.
Heute sind wir, soweit ich gelesen habe, an den praktischen Grenzen dessen angelangt, was mit Silizium-Halbleitertechnik und dem heutigen Verständnis der Physik vernünftigerweise möglich ist. Jetzt muss das Pendel in die andere Richtung schwingen, und Computer müssen nicht härter, sondern intelligenter arbeiten.
Allerdings denke ich, dass Software-Bloat schneller wächst.
goto/jmp→ vtable-Lookup → Hashing und Lookup in einem Dictionary → Ausführen eines großen Sprachmodells.„Statt mit 7 zu multiplizieren, addiert man das Achtfache der Zahl und subtrahiert die Zahl, um das Siebenfache zu erhalten. Das klingt nach zwei Schritten, aber durch den Trick, in der linken Stelle eine 1 zusätzlich zu multiplizieren, erhält man den Faktor 8 ohne zusätzlichen Schritt.“
Bedeutet das, dass es einen Addierer gibt, der an der „nächsten Stelle“ 1 addiert, bevor die Zahl in den Hauptmultiplizierer-Teil gelangt? Das wirkt für sich genommen auch ähnlich wie eine Carry-Lookahead-Schaltung.
Ich frage mich auch, wann das nötig ist:
7 = 8-1,6 = 8-2,5 = 8-3,4 = 8-4Im letzten Fall sagt der Artikel zwar nicht, dass es so gemacht wird, aber wenn man anhand des höchstwertigen Bits eines 3-Bit-Werts entscheidet, ob man an der nächsten Stelle 1 addieren muss, ließen sich wohl ein paar Gates sparen.
Interessant ist die Wahl eines Radix-8-Booth-Multiplizierers, der eine ×3-Schaltung benötigt. Das wirkt wie ein Flächen-/Leistungs-Kompromiss zur Erhöhung der Maximalfrequenz; dasselbe hätte man wohl auch mit stärkerem Pipelining erreichen können, daher scheint es Einschränkungen bei den Latenzzyklen gegeben zu haben.
Pipelining ist schwierig, weil es keine gute Stelle gibt, um das Multiplikationsarray in zwei Teile aufzuteilen.
https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
8086: 29.000
386: 275.000
486: 1,2 Millionen
Pentium: 3,1 Millionen
Soweit ich mich erinnere, ist die NSA irgendwann nach 2000 in dieses Spiel eingestiegen.