Zahlen, bitte! Intel Pentium: Tausende Transistoren für simple Multiplikation

Inhaltsverzeichnis

Nachdem am letzten Dienstag der erste Teil über den kurios anmutenden ×3-Schaltkreis des Intel Pentium erschien, wurde er rege im heise-Forum diskutiert: Manche erfreuten sich an der thematischen Tiefe, andere wiederum vermuteten, dass sie einen Aprilscherz entdeckt hatten – Nein, den Schaltkreis gibt es wirklich.

Hier ist nun der zweite Teil mit Schlussfolgerung des ins Deutsche übertragenden Exponats, das IT-Historiker Ken Shirriff ursprünglich in seinem Blog veröffentlicht hat. Er beschreibt diesen Multiplikator, den er als ×3-Schaltkreis bezeichnet, und erklärt seinen Zweck und seine Funktionsweise.

Der Verlag dankt Ken Shirriff herzlich für die freundliche Genehmigung. The original English version is available as well.

Teil 2: Zusammensetzen der Addiererteile

Das folgende Bild zeigt einen 8-Bit-Block des ×3-Multiplikators, der einen 8-Bit-Addierer implementiert. Oben befinden sich acht Eingangsleitungen (zusammen mit einigen nicht verbundenen Drähten). Beachten Sie, dass jede Eingangsleitung sich teilt, wobei ein Signal zum Addierer auf der linken Seite und ein Signal nach rechts geht.

Dadurch wird der Addierer mit 3 multipliziert: Er addiert den Eingang und den um ein Bit nach links verschobenen Eingang, das heißt mit zwei multipliziert

Zahlen, bitte!

In dieser Rubrik stellen wir immer dienstags verblüffende, beeindruckende, informative und witzige Zahlen aus den Bereichen IT, Wissenschaft, Kunst, Wirtschaft, Politik und natürlich der Mathematik vor.

• Alle Artikel zu "Zahlen, bitte!"

Der obere Teil des Addierers verfügt über acht Schaltkreise, um die Signale zu verbreiten (propagate) und zu erzeugen (generate). Diese Signale gehen in den 8-Bit-Kogge-Stone-Lookahead-Schaltkreis. Obwohl der Großteil des Addierers aus einem achtmal wiederholten Schaltkreisblock besteht, wirkt die Kogge-Stone-Schaltung chaotisch. Dies liegt daran, dass jedes Bit der Kogge-Stone-Schaltung anders ist – höhere Bits sind komplizierter zu berechnen als niedrigere Bits.

Die untere Hälfte des Schaltungsblocks enthält einen 8-Bit-Carry-Select-Addierer. Diese Schaltung erzeugt zwei Summen, wobei Multiplexer die richtige Summe basierend auf dem Übertrag in den Block auswählen. Beachten Sie, dass die Carry-Select-Addiererblöcke schmaler sind als die anderen Schaltkreise.¹⁰ Dadurch entsteht links Platz für einen Kogge-Stone-Block. Die Kogge-Stone-Schaltung der zweiten Ebene ist aufgeteilt; die 8-Bit-Carry-Lookahead-Schaltung hat ein Bit in jedem Block des Addierers implementiert und erzeugt das Carry-In-Signal für diesen Addiererblock. Mit anderen Worten enthält das obige Bild 1/8 der Kogge-Stone-Schaltung der zweiten Ebene. Schließlich verstärken acht Treiberschaltungen die Ausgangsbits, bevor sie an den Rest des Gleitkomma-Multiplikators gesendet werden.

Das folgende Blockdiagramm zeigt, wie die Teile kombiniert werden, um den x3-Multiplikator zu bilden. Der Multiplikator hat acht 8-Bit-Addierblöcke (grüne Kästen, die dem Bild oben entsprechen). Jeder Block berechnet acht Bits der Gesamtsumme. Jeder Block liefert P₇₀- und G₇₀-Signale an die Lookahead-Funktion der zweiten Ebene, die bestimmt, welche Blöcke einen Übertrag erhalten. Der entscheidende Punkt dieser Architektur ist, dass alles parallel berechnet wird, was die Addition beschleunigt.

Im obigen Diagramm ist der erste 8-Bit-Block erweitert, um seinen Inhalt zu zeigen. Der 8-Bit-Lookahead-Schaltkreis erzeugt die P- und G-Signale, die die internen Übertragssignale bestimmen. Der Übertrag-Auswahl-Addierer enthält zwei 8-Bit-Addierer, die die Übertrag-Lookahead-Werte verwenden. Wie bereits beschrieben, geht ein Addierer davon aus, dass der Carry-In des Blocks 1 ist, und der Zweite davon, dass der Carry-In 0 ist. Wenn der tatsächliche Carry-In-Wert von der Lookahead-Schaltung der zweiten Ebene bereitgestellt wird, wählt der Multiplexer die richtige Summe aus.

Das folgende Foto zeigt, wie der vollständige Multiplikator aus 8-Bit-Blöcken aufgebaut ist. Der Multiplikator erzeugt eine 69-Bit-Ausgabe, denn links befinden sich fünf "zusätzliche" Bits. Beachten Sie, dass die Kogge-Stone-Blöcke der zweiten Ebene rechts größer sind als links, da die Lookahead-Schaltung für Bits höherer Ordnung komplexer ist.

Wenn Sie sich den obigen vollständigen ×3-Schaltkreis ansehen, können Sie erkennen, dass die 8 Bits auf der rechten Seite eine deutlich einfachere Schaltung aufweisen. Da es in diesem Block keinen Übertrag gibt, kann die Übertrags-Auswahl-Schaltung weggelassen werden. Die internen Übertragungen des Blocks, die von der Kogge-Stone-Lookahead-Schaltung erzeugt werden, werden mithilfe von Exklusiv-Nicht-Oder-Gattern (XNOR) hinzugefügt. Das folgende Diagramm zeigt die Implementierung eines SFOR-Gatters unter Verwendung von Invertern und einem Multiplexer.

Die XNOR-Schaltung

Ich werde nun eine der Multiplizierschaltungen auf Transistorebene beschreiben, insbesondere ein XNOR-Gatter. Es ist interessant, sich XNOR anzusehen, da XNOR (wie XOR) ein schwierig zu implementierendes Gatter ist und verschiedene Prozessoren sehr unterschiedliche Ansätze verwenden. Beispielsweise implementiert der Intel 386 XOR aus AND-NOR-Gattern (Details), während der Z-80 Pass-Transistoren verwendet (Details). Der Pentium hingegen verwendet einen Multiplexer.

Das obige Diagramm zeigt eines der XNOR-Gatter in den niedrigen Bits des Addierers.¹¹ Das Gatter besteht aus vier Invertern und einem Pass-Transistor-Multiplexer. Eingang B wählt einen der beiden Eingänge des Multiplexers aus: Eingang A oder Eingang A invertiert. Das Ergebnis ist die XNOR-Funktion. (Inverter 1 puffert den Eingang, Inverter 5 puffert den Ausgang und Inverter 4 liefert das ergänzte B-Signal, um den Multiplexer zu steuern.)

Für das Foto habe ich die oberen beiden Metallschichten vom Chip entfernt und die untere Metallschicht, M1 genannt, belassen. Die dotierten Siliziumbereiche sind unter dem Metall kaum sichtbar. Wenn eine Polysiliziumleitung dotiertes Silizium kreuzt, bildet sie das Gate eines Transistors. Diese CMOS-Schaltung hat NMOS-Transistoren oben und PMOS-Transistoren unten. Jeder Inverter besteht aus zwei Transistoren, während der Multiplexer aus vier Transistoren besteht.

Die BiCMOS-Ausgangstreiber

Die Ausgänge des ×3-Schaltkreises erfordern starken elektrischen Strom. Insbesondere kann jedes Signal des ×3-Schaltkreises bis zu 22 Terme im Gleitkomma-Multiplikator ansteuern. Darüber hinaus können die Zielschaltkreise aufgrund der Größe des Multiplikators in beträchtlicher Entfernung vom ×3-Schaltkreis liegen. Da die ×3-Signale über lange Drähte mit vielen Transistor-Gates verbunden sind, ist die Kapazität hoch, sodass starker Strom erforderlich ist, um die Signale schnell zu ändern.

Der Pentium wird mit einem etwas ungewöhnlichen Verfahren namens BiCMOS hergestellt, bei dem bipolare Transistoren und CMOS auf demselben Chip kombiniert werden. Der Pentium verwendet in großem Umfang BiCMOS-Schaltkreise, da sie Signalverzögerungen um bis zu 35 Prozent reduzieren. Intel hat BiCMOS auch für die Pentium Pro-, Pentium II-, Pentium III- und Xeon-Prozessoren eingesetzt. Da die Chipspannungen jedoch sanken, sank auch der Nutzen von Bipolartransistoren, und BiCMOS wurde schließlich aufgegeben.

Das folgende Schema zeigt einen vereinfachten BiCMOS-Treiber, der seinen Eingang invertiert. Ein 0-Eingang schaltet den oberen Inverter ein und liefert Strom an die Basis des Bipolartransistors (NPN). Dadurch wird der Transistor eingeschaltet, sodass er den Ausgang stark und schnell hochzieht. Ein 1-Eingang hingegen stoppt den Stromfluss durch die Basis des NPN-Transistors und schaltet ihn aus. Gleichzeitig zieht der untere Inverter den Ausgang auf niedrig. (Der NPN-Transistor kann den Ausgang nur auf hoch ziehen.)

Beachten Sie die asymmetrische Konstruktion der Inverter. Da der obere Inverter starken Strom in die Basis des NPN-Transistors einspeisen muss, ist er so konzipiert, dass er einen starken (hochstromigen) positiven Ausgang und einen schwachen niedrigen Ausgang erzeugt. Der untere Inverter hingegen ist dafür verantwortlich, den Ausgang auf niedrig zu ziehen. Daher ist er so konstruiert, dass er einen starken niedrigen Ausgang erzeugt, während der hohe Ausgang schwach sein kann.

Der Treiber des ×3-Schaltkreises geht noch einen Schritt weiter: Er verwendet einen BiCMOS-Treiber, um einen zweiten BiCMOS-Treiber zu steuern. Der Grund dafür ist, dass die Hochstrom-Inverter ziemlich große Transistor-Gates haben, sodass sie mit starkem Strom betrieben werden müssen (aber nicht so viel, wie sie produzieren, damit es keine unendliche Regression gibt).¹²

Das folgende Schema zeigt die BiCMOS-Treiberschaltung, die der ×3-Multiplikator verwendet. Beachten Sie das große, kastenartige Aussehen der NPN-Transistoren, das sich stark von den regulären MOS-Transistoren unterscheidet. Jeder Kasten enthält zwei NPN-Transistoren, die sich die Kollektoren teilen: einen größeren Transistor auf der linken Seite und einen kleineren auf der rechten Seite. Man könnte erwarten, dass diese Transistoren zusammenarbeiten, aber die angrenzenden Transistoren sind Teil zweier separater Schaltkreise. Stattdessen sind der kleine NPN-Transistor links und der große NPN-Transistor rechts Teil desselben Schaltkreises.

Die Inverter sind als Standard-CMOS-Schaltkreise mit PMOS-Transistoren aufgebaut, um den Ausgang hochzuziehen, und NMOS-Transistoren, um den Ausgang herunterzuziehen. Die Inverter sind sorgfältig strukturiert, um asymmetrischen Strom zu liefern, was sie interessanter macht als typische Inverter. Zwei Pullup-Transistoren haben ein langes Gate, wodurch diese Transistoren ungewöhnlich schwach sind. Andere Teile der Inverter haben mehrere Transistoren parallel geschaltet, wodurch mehr Strom bereitgestellt wird. Darüber hinaus haben die Inverter ungewöhnliche Layouts, bei denen die NMOS- und PMOS-Transistoren weit voneinander entfernt sind, um das Layout effizienter zu gestalten. Weitere Informationen zu BiCMOS im Pentium finden Sie in meinem Artikel über interessante BiCMOS-Schaltungen im Pentium.

Schlussfolgerungen

Die Hardwareunterstützung für die Multiplikation in Computern hat eine lange Geschichte, die bis in die 1950er Jahre zurückreicht.¹³ Frühe Mikroprozessoren hatten jedoch nur sehr begrenzte Fähigkeiten, sodass Mikroprozessoren wie der 6502 keine Hardwareunterstützung für die Multiplikation hatten; die Benutzer mussten Multiplikation in der Software durch Verschiebungen und Additionen implementieren. Mit Weiterentwicklung der Hardware boten Prozessoren Multiplikationsanweisungen, die jedoch immer noch langsam waren. Beispielsweise implementierte der Intel 8086-Prozessor (1978) die Multiplikation in einem Mikrocode, der intern eine langsame Verschiebe- und Additionsschleife durchführte. Prozessoren wurden im Laufe der Zeit exponentiell leistungsfähiger, wie durch das Mooresche Gesetz beschrieben, sodass spätere Prozessoren dedizierte Multiplikationshardware enthalten konnten. Der 386-Prozessor (1985) enthielt eine Multiplikationseinheit, die jedoch immer noch langsam war und bis zu 41 Taktzyklen für eine Multiplikationsanweisung benötigte.

Zum Zeitpunkt des Pentium (1993) enthielten Mikroprozessoren Millionen von Transistoren, was neue Möglichkeiten für das Design eröffnete. Mit einer scheinbar unbegrenzten Anzahl von Transistoren konnten Chip-Architekten komplizierte neue Ansätze in Betracht ziehen, um mehr Leistung aus einem System herauszuholen. Dieser ×3-Schaltkreis enthält etwa 9.000 Transistoren, etwas mehr als ein ganzer Z80-Mikroprozessor (1976). Man sollte bedenken, dass der ×3-Schaltkreis nur ein kleiner Teil des Gleitkomma-Multiplikators ist, der wiederum Teil der Gleitkommaeinheit im Pentium ist. Somit ist dieses Stückchen einer Funktion komplizierter als ein ganzer Mikroprozessor von 17 Jahren davor, was die unglaubliche Zunahme der Prozessorkomplexität veranschaulicht.

Der Pentium-Teppich

Anlässlich eines Besuches in der National Gallery of Art in Washington, DC, kam Ken Shirriff der Pentium Navajo Teppich (offiziell "Replica of a Chip") unter. Das von Marilou Schultz gewebte Kunstwerk hat Shirriff dazu inspiriert, den Pentium-Prozessor genauer zu untersuchen. Er plant noch weitere Artikel zu diesem Meilenstein der CPU-Geschichte. Updates zu seinen Veröffentlichungen gibt es zB bei Mastodon unter @kenshirriff sowie in seinem RSS-Feed.

Fußnoten und Quellenangaben

9. Die übergeordnete Kogge-Stone-Lookahead-Schaltung verwendet die acht P₇₀– und G₇₀–Signale von den acht untergeordneten Lookahead-Schaltungen. Beachten Sie, dass P₇₀ und G₇₀ anzeigen, dass ein 8-Bit-Block einen Übertrag weitergibt oder erzeugt. Die übergeordnete Lookahead-Schaltung behandelt 8-Bit-Blöcke als eine Einheit, während die untergeordnete Lookahead-Schaltung 1-Bit-Blöcke als Einheit behandelt. Somit sind die über- und untergeordneten Lookahead-Schaltungen im Wesentlichen identisch und wirken auf 8-Bit-Werte.

10. Die Gleitkommaeinheit besteht aus Spalten fester Breite, eine für jedes Bit. Jede Spalte ist 38,5 µm breit, sodass die Schaltkreise in jeder Spalte so gestaltet werden müssen, dass sie dieser Breite entsprechen. In den meisten Fällen wird derselbe Schaltkreis für jedes der (ungefähr) 64 Bits wiederholt. Der Carry-Select-Addierer ist ungewöhnlich, da er nicht der Spaltenbreite der restlichen Gleitkommaeinheit folgt. Stattdessen werden acht Schaltkreise auf die Breite von 6,5 regulären Schaltkreisen gepackt. Dadurch bleibt Platz für einen Kogge-Stone-Schaltkreisblock.

11. Da es keinen Übertrag zum niedrigsten 8-Bit-Block der ×3-Schaltung gibt, wird die Übertrag-Auswahl-Schaltung nicht benötigt. Stattdessen kann jedes Ausgangsbit mit einem Exclusiv-Nicht-Oder-Gatter (XNOR) berechnet werden.

12. Das Prinzip des logischen Aufwands besagt, dass man für optimale Leistung nicht in einem Schritt von einem kleinen Signal zu einem Signal mit hoher Stromstärke springen sollte. Stattdessen erzeugt ein kleines Signal ein mittleres Signal, das ein stärkeres Signal erzeugt. Durch die Verwendung mehrerer Schaltungsstufen kann die Gesamtverzögerung reduziert werden.

13. Die Booth-Multiplikationstechnik wurde 1951 beschrieben, während parallele Multiplikatoren Mitte der 1960er Jahre von Wallace und Dadda vorgeschlagen wurden. Ein 1992 von Motorola veröffentlichtes Dokument mit dem Titel A Fast Hybrid Multiplier Combining Booth and Wallace/Dadda Algorithms befasst sich mit Radix-4- und Radix-8-Algorithmen für einen 32-Bit-Multiplikator, kommt jedoch zu dem Schluss, dass die Berechnung des Multiplikators ×3 den Radix-8-Algorithmus unpraktisch macht. IBM hat 1997 einen 32-Bit-Multiplikator erörtert: A Radix-8 CMOS S/390 Multiplier. Bewicks Doktorarbeit von 1994 Fast Multiplication: Algorithms and Implementation beschreibt zahlreiche Algorithmen.
Für Addierer ist Two-Operand Addition eine interessante Präsentation über verschiedene Ansätze. CMOS VLSI Design enthält gute Diskussion über Addition und verschiedene Lookahead-Netzwerke. Es fasst die Kompromisse zusammen: "Brent-Kung hat zu viele Logikpegel. Sklansky fächert zu sehr aus. Und Kogge-Stone hat zu viele Drähte. Zwischen diesen drei Extremen füllen die Han-Carlson-, Ladner-Fischer- und Knowles-Bäume den Entwurfsraum mit unterschiedlichen Kompromissen zwischen Anzahl der Stufen, Ausfächern und Drahtanzahl aus." Der im ×3-Multiplikator des Pentium verwendete Ansatz wird manchmal als Sparse-Tree-Addierer bezeichnet.

(mawi)