-
Die vorliegende Erfindung bezieht sich auf eine verbesserte Carry-Lookahead-
Technik z. B. für den Einsatz in einem Addierer.
-
Verwandte Erfindungen sind in unseren mitanhängigen Erfindungen, die unter EP
450 752, EP 450 751 und EP 450 754 veröffentlicht und mit der vorliegenden
Anmeldung eingereicht worden sind, beschrieben.
-
Bei der Binärstellenwertaddition werden zwei in dem Binärstellenwertcode
dargestellte Operanden zum Erzeugen eines ebenfalls im Binärstellenwertcode
dargestellten Ergebnisses addiert. Jeder Operand und das Ergebnis stellen ein Array
von Bits dar. Im Binärwertcode bestimmt die Position eines Bits in dem Array
seine Zweierpotenz; somit gilt Wert = Summe (Bit · 2^pos). Das Bit mit der
geringsten Gewichtung bei der Bestimmung des Werts einer Darstellung wird als
niederwertigstes Bit oder LSB bezeichnet. Ähnlich wird das Bit mit der größten
Gewichtung als höchstwertiges Bit oder MSB bezeichnet. Andere Zahlensysteme
weisen bessere Additionseigenschaften auf, werfen aber andere Probleme auf,
somit verwendet praktisch jeder handelsübliche Computer heute den
Binärstellenwertcode.
-
Bei einem manuellen Additionsverfahren wird die Summe für die LSB-Position
gebildet, breitet sich ein Übertrag möglicherweise in die nächste Bitposition aus und
wird der Prozess für nachfolgende Bitpositionen wiederholt, bis jedes Bit im
Ergebnis berechnet worden ist. Dieses Verfahren ist Fachleuten auf dem Gebiet als
"Ripple-Übertrags"addition, wie in Fig. 1 dargestellt, bekannt. Die
Ripple-Übertragsaddition ist aufgrund ihrer seriellen Natur inhärent langsam.
-
Die Addition ist auf herkömmliche Weise durch Anwendung einer der folgenden
Techniken, die in CMOS VLSI Design, Addison-Wesley, von 1985 beschrieben
sind, beschleunigt worden: Carry-Lookahead, Manchester Carry-Lookahead,
Binär-Carry-Lookahead-Bäume and Übertragsselektionsaddition. Eine weitere
Technik, wie in Sth Annual Symposium on Theoretical Aspects of Computer
Science, STACS von 1988 beschrieben, ist die Condition-Sum-Addition. Eine
weitere Technik bezieht sich auf den Mehrausgangs-Domino-Logikaddierer, der in
Solid-State Circuits Conference Digest of Technical Papers von 1988 beschrieben
ist.
-
Jeder dieser Addierer, mit Ausnahme des Übertragsselektions- und des
Conditional-Sum-Addierers, basiert auf den Konzepten von Übertragsausbreitung,
Übertragsgenerierung und Carry-Kill (siehe Fig. 2), die Fachleuten auf dem Gebiet
bekannt sind. Ein Übertrag wird als sich durch eine Bitposition "ausbreitend"
bezeichnet, wenn einem Übertrag in die Summieroperation für eine vorgegebene
Bitposition ein Übertrag aus der vorgegebenen Bitposition in die nächsthöhere
Position folgt, wohingegen das Summieren für die vorgegebene Bitposition
keinen Übertrag für die nächsthöhere Position erzeugt, wenn kein Übertrag
eingegeben wird. Ein Übertrag wird als von einer vorgegebenen Bitposition "generiert"
bezeichnet, wenn das Summieren für die vorgegebene Position einen von einem
Übertrag aus einer vorhergehenden Position unabhängigen Übertrag für die
nächsthöhere Position erzeugt. Ein Übertrag wird als in einer Bitposition "gekillt"
bezeichnet, wenn sich ein Übertrag nicht durch das Bit ausbreitet. Wie
Fachleuten auf dem Gebiet bekannt und in Fig. 2 dargestellt ist, können die
Ausbreitungs- und Generiersignale ohne tatsächliche Durchführung der Summierung
detektiert werden.
-
Eine Gruppierung benachbarter Summenfunktionen, benachbarter
Ausbreitungsfunktionen oder benachbarter Generierfunktionen kann als "Block" bezeichnet
werden, ein Beispiel dafür ist in Fig. 1 gezeigt. Die Terme Ausbreiten, Generieren
und Kill können auf die Blocks angewandt werden. Ein Übertrag wird als sich
durch einen vorgegebenen Block ausbreitend bezeichnet, wenn einem Übertrag
in die LSB-Summierung des vorgegebenen Blocks ein Übertrag aus der MSB-
Summierung eines vorgegebenen Blocks in die nächsthöhere Position folgt. Ein
Block wird als einen Übertrag generierend bezeichnet, wenn die
MSB-Summierung des Blocks einen von den Überträgen in das LSB des Blocks unabhängigen
Übertrag in die nächsthöhere Position erzeugt. Es ist Fachleuten auf dem Gebiet
bekannt, dass ein Block nur dann eine Generierung durchführen kann, wenn eine
vorgegebene Bitposition in dem Block eine Generierung durchführt und sich
sämtliche Bits zwischen dem vorgegebenen Bit und dem MSB des Blocks
ausbreiten; wie in der in CMOS VLSI, Addison Wesley, von 1985 beschriebenen
Manchester-Übertragskette.
-
Digital Computer Arithmetic von J. J. F. Cavanagh, Seite 107-117, McGraw-Hill
(1984) gibt einen Überblick über die Carry-Lookahead-Addierertheorie. Der CLA
beschleunigt die Berechnung der Überträge durch Anwendung einer redundanten
Logik. Ein Block ist für eine vorgegebene Bitposition derart definiert, dass das
LSB des Blocks dem LSB der Addierung entspricht und das MSB des Blocks der
vorgegebenen Bitposition entspricht. Somit gibt es so viele Blöcke wie
Bitpositionen in dem Ergebnis minus 1, wie in Fig. 3 dargestellt. Es wird ein zusätzlicher
Block benötigt, wenn ein Übertrag in die nächsthöhere Position erforderlich ist.
Jeder Block hat nur die Eingangsoperanden und den Übertrag in die Addierung
als Eingangssignale und einen Übertrag als Ausgangssignal. Theoretisch kann
eine beliebige einzelne Logikfunktion in zwei Gatterverzögerungen durchgeführt
werden, so dass die Zeit zum Erzeugen einer Summe in einem Carry-Lookahead-
Addierer theoretisch eine konstante Vier-Gatterverzögerung ist; die endliche
Verstärkung von Realgattern beschränkt jedoch die Größe der Last, die ein
beliebiges Gatter in einer vorgegebenen Zeitspanne aktivieren kann, so dass weitere
Gatterverzögerungen hinzugefügt werden müssen. Ferner ist die Anzahl von
Übertragsblöcken, die aktiviert werden können, und somit die Anzahl von Bits,
die das Ergebnis aufweisen kann, ebenfalls eingeschränkt, da die
Eingangsoperanden selbst von Gattern aktiviert werden. Der Carry-Lookahead-Addierer wird
bei Ergebnisgrößen, die über einige wenige Bits hinausgehen, relativ langsam.
Die Leistung der Carry-Lookahead-Addierer zeigt, dass die Belastung von
Realgattern die Addierzeit bestimmt, nicht die theoretische Anzahl von
Gatterverzögerungen. Ein von Ling erfundener Addierer, der im IBM-Journal of Research and
Development, May 1981 vorgestellt worden ist, reduziert die Last vom Ausgang
im Ausbreitungs- und Generierzustand um einen Gattereingang pro Bit und pro
Block. Obwohl dieses Verfahren das Lastproblem teilweise löst, bleibt der CLA-
Addierer für Addierungen von mehr als einigen Bits relativ ineffizient.
-
Der Manchester-Carry-Lookahead-Addierer aus Fig. 4 beschleunigt die Addition
dadurch, dass er es Überträgen ermöglicht, sich ausbreitende Blöcke zu
überspringen. Zum Anwenden dieses Verfahrens wird eine Addierung derart in eine
Reihe von Blöcken eingeschaltet, dass keine Übertragsausbreitungslogik
dupliziert wird. Dann werden sämtliche Bitausbreitungen für einen vorgegebenen
Block zwecks Feststellung, ob sich der vorgegebene Block ausbreitet, durch
logisches UND verknüpft. Wenn sich der Block ausbreitet, wird ein Bypass
eingeschaltet, der Überträge in das LSB des Blocks direkt zum Ausgang des MSB des
Blocks leitet. Dieses Verfahren funktioniert gut bei Addierern mit bestimmten
Größen in CMOS; die Leistung ist jedoch immer noch linear mit der Größe des
Addierers verbunden. Bei Bemühungen, dieses Problem zu lösen, wurden
mehrere Überspringungsebenen hinzugefügt, wie in IEEE Transactions on Computers,
Volume 36, erläutert. Bei Addierern mit mehr als 32 Bits kann sich dieses
Verfahren der Geschwindigkeit eines Binär-Lookahead-Addierers nur annähern; es ist
aus theoretischen und praktischen Gründen wesentlich langsamer als das des in
der vorliegenden Anmeldung vorgestellten Addierers.
-
Der Binärbaum ist eine besondere graphische Darstellung von Knoten und
Verbindungslinien, ähnlich einem Familienstammbaum. Der eine Knoten am oberen
Ende hat keine Vorgänger, er wird als "Wurzel"knoten bezeichnet. Jeder Knoten
im Baum hat ein oder zwei "Kinder", mit Ausnahme der "Blatt"knoten, die keine
Kinder haben (entsprechend der jüngsten Generation). Schaltungen mit
speziellen Eigenschaften können mit Gattern als Knoten ausgebildet sein. Im Jahr 1980
wurde gezeigt, dass ein '6-Operator definiert werden konnte, der eine
Implementierung von Überträgen in einem Addierer in einen Binärbaum ermöglicht (CMOS
VLSI Design). Der Binär-Lookahead-Baum konnte jedoch nur Überträge für
Bitpositionen der Zweierpoteflz (d. h. 2,4,8, ...) bereitstellen, sodass ein
"invertierter" Baum zum Ableiten der Zwischenüberträge verwendet werden musste, was
zu einem zusätzlichem Aufwand führte.
-
Der Binär-Lookahead-Übertragsbaum aus Fig. 5 weist mit der Logbase 2
verbundene Gatterverzögerungen der Addierlänge plus einen zusätzlichen Aufwand auf.
Wie im Fall des Carry-Lookahead-Addierers verhindert die Schaltungslast die
Realisierung der Gatterverzögerungen der Logbase 2 für große Bäume, d. h.
Bäume für Addierungen von mehr als 8 Bits. Ferner wissen Fachleute auf dem
Gebiet, dass der Baum bei großem Addieraufwand groß und ineffizient wird. Der
in IEEE Solid-State Circuits Conference Digest of Technical Paper von 1988
beschriebene MODL-Gatteraddierer stellt einen Versuch zum Lösen dieses Problems
dar und ermöglicht für größere Addierungen eine Logbase 2 · lineare Leistung
(weniger als Logbase 2).
-
Ein Übertragsselektionsaddierer aus Fig. 6 basiert auf dem Prinzip der
Partionierung des Addierers in drei Blöcke. Der erste Block addiert die untere Hälfte der
beiden Operanden. Der zweite Block addiert die obere Hälfte der Operanden,
wobei von einem Übertrag von dem ersten Block Null ausgegangen wird. Der dritte
Block addiert die obere Hälfte der Operanden, wobei von einem Übertrag aus
dem ersten Block Eins ausgegangen wird. Wenn der Übertrag vom ersten Block
berechnet wird, wird dieser zum Aufnehmen der korrekten oberen Hälfte des
Ergebnisses durch Selektion der Summe aus dem Block Zwei oder der Summe aus
Block Drei über einen Zwei-zu-Eins-Multiplexer verwendet. Wenn
Übertragsselektionsaddierer in Reihe geschaltet sind, weisen sie eine linear Leistung in Bezug
auf die Anzahl von Abschnitten plus die Addierzeit des ersten Abschnitts auf. Bei
großen Addierern ist dieser Addierertyp relativ langsam, aber klein.
-
Der Conditional-sum-Addierer ist ein rekursiv angewandter
Übertragsselektionsaddierer. Ein Addierer wird in eine Vielzahl von redundanten Blöcken Zwei
eingeschaltet, dann wird ein Satz aufgenommen, so dass nur die Hälfte der möglichen
Summen verbleiben. Der Prozess der Halbierung der möglichen Summen wird in
Mehrfachstufen fortgeführt, bis nur das Ergebnis übrigbleibt. Der Addierer weist
eine Logbase 2-Leistung auf, er ist sogar größer als der BLC-Addierer. Da die
Summierung gemeinsam mit den Überträgen in jeder Stufe berechnet wird, wird
die Summierlogik unnötigerweise viele Male reproduziert. Ferner wird dieser
Addierer aufgrund des Summieraufwands langsamer als der BLC-Addierer.
-
Da Addierer das Herz vieler Digitalschaltungen sind und sie in großem Umfang zu
der erforderlichen Taktzeit von RISC-Mikroprozessoren beitragen, besteht Bedarf
an schnelleren Addierern.
-
- Ein Carry-Lookahead-Addierer auf der Basis herkömmlicher
Block-Carry-Lookahead-Techniken ist in "Proceedings, 7t" Symposium on Computer Arithmetic, 4-
6 Juni '85, Illinois, S. 9-15" beschrieben.
-
Ein Binäraddierer, der eine spezifische Konfiguration der
Lookahead-Übertragsebenen zum Reduzieren der Anzahl von für die Übertragsfunktion erforderlichen
Logikebenen verwendet, ist in IBM Technical Disclosure, Vol. 7, Nr. 11, April
1965 "Binary Adder with Quaternary Lookahead" von R. M. Wade beschrieben.
-
In IEEE 1988 Custom Integrated Circuit Conference May 1988, Seite 1751 bis
1756 wird über einen dynamisch rekonfigurierbaren 32-Bit
Hochgeschwindigkeits-CMOS-Addierer berichtet. Der Addierer verwendet eine 32-Bit-Carry-
Lookahead-Schaltung auf der Basis einer Mehrfachausgangs-Domino-Logik
(MODL). Die MODL-4/8-Bitgruppen-Generier- und Ausbreitungsblöcke liefern
Signale zu einem Gruppenübertragsblock mit einem
3-Bit-Mehrfachübertragsgenerator.
-
Im US-Patent 4,905,180 wird ein aus mehreren 4-Bit-Slice-Blöcken gefertigter
partionierter Carry-Lookahead-Addierer beschrieben. Diese Blöcke sind derart
organisiert, dass sie Gruppenausbreitungssignale generieren und jeder Block eine
Übertragsleitung mit einem zwischen den Eingangs- und Ausgangsanschlüssen
des Blocks angeschlossenen Einzeltransistor aufweist; es ist ferner eine
Übertragsleitung mit vom Gruppenausbreitungssignal gesteuerten Transistoren
vorgesehen. Die generelle Konfiguration ähnelt der des
Manchester-Carry-Lookahead-Addierers aus Fig. 4.
-
Erfindungsgemäß ist eine Carry-Lookahead-Baum-Logikschaltung vorgesehen,
die folgendes aufweist: eine Carry-Lookahead-Baum-Logikschaltung zum Einsatz
in einem Zweioperanden-Addierer mit: mehreren Baumknoten bestehend aus
Teilschaltungen; wobei jede Teilschaltung acht Eingangsanschlüsse, zwei
Ausgangsanschlüsse und eine interne Logikschaltung mit einem Übertragskettenteil
aufweist; wobei die Teilschaltungen derart geschaltet sind, dass sie einen Baum
mit drei Ebenen mit vierzehn Teilschaltungen der ersten Ebene und vier
Teilschaltungen der zweiten Ebene aufweisen; jede Teilschaltung der ersten Ebene
derart betreibbar ist, dass sie Blockausbreitungs- und -generierterme für Vierbit-
Generier- und Vierbit-Ausbreitungs-Eingangspositionen der Operanden an ihren
Eingangsanschlüssen erzeugt; drei der Teilschaltungen der zweiten Ebene derart
geschaltet sind, dass sie von vier Teilschaltungen der ersten Ebene erzeugte
Blockausbreitungs- und -generierterme empfangen und daraus
Blockausbrei
tungs- und -generierterme erzeugen; und wobei die vierte Teilschaltung der
zweiten Ebene derart geschaltet ist, dass sie von zwei Teilschaltungen der ersten
Ebene erzeugte Blockausbreitungs- und -generierterme empfängt, und dass sich
zwei Teilschaltungen auf der dritten Ebene des Baums befinden, wobei eine
Teilschaltung der dritten Ebene derart geschaltet ist, dass sie von den vier
Teilschaltungen der zweiten Ebene erzeugte Blockausbreitungs- und -generierterme
empfängt und daraus Blockausbreitungs- und -generierterme erzeugt; die andere
Teilschaltung der dritten Ebene derart geschaltet ist, dass sie Blockausbreitungs-
und -generierterme von zwei Teilschaltungen der zweiten Ebene empfängt und
ferner diese Signale als Ausgangssignal zum Erhalt von Übertragssignalen zur
Verfügung stellt; und wodurch die andere Teilschaltung der dritten Ebene
Informationen über Zwischenüberträge auf 8-Bit-Grenzen des Baums liefert.
-
Bei einer bevorzugten Ausführungsform ist der Baum ein
Radix-4-Carry-Lookahead-Baum und weist die interne Logikschaltung in jeder Teilschaltung ferner
einen NAND-Gatterteil bestehend aus einer Kette von Gattern auf, die zum
Durchführen eines logischen NAND an Ausbreitungseingängen entlang der
Gatterkette gekoppelt sind.
-
Entsprechend wird eine relativ kleine Schaltung zum Durchführen einer relativ
großen Addierung innerhalb einer kurzen Zeitspanne beschrieben.
-
Die Schaltung kann auf einfache und praktische Weise skaliert werden und
verliert bei dieser Skalierung nur wenig an Geschwindigkeit.
-
Die beigefügten Zeichnungen zeigen beispielhaft:
-
Fig. 1-6 verschiedene dem Stand der Technik entsprechende
Konfigurationen;
-
Fig. 7 ein Blockschaltbild eines Computersystems mit einem Prozessor, in
dem ein erfindungsgemäßer Lookahead-Baum eingebaut sein kann;
-
Fig. 8 ein Blockschaltbild des Prozessors aus Fig. 7;
-
Fig. 9 ein detaillierteres Blockschaltbild des Prozessors aus Fig. 8;
-
Fig. 10 ein Blockschaltbild einer Gleitkommaeinheit;
-
Fig. 11A eine schematische Darstellung eines Radix-Vier-Carry-Lookahead-
Baums;
-
Fig. 11B eine schematische Darstellung eines erfindungsgemäßen Radix-Vier-
Carry-Lookahead-Baums, wobei der Baum auf dem Baum aus Fig.
11A basiert, jedoch eine redundante Zelle aufweist;
-
Fig. 12 eine schematische Darstellung einer modifizierten Übertragskette
zum Einsatz in dem Baum aus Fig. 11B;
-
Fig. 13 eine schematische Darstellung einer Modifizierung für eine
Übertragszelle für den Übertrag aus einer vorhergehenden Position zum
Einsatz in dem Baum aus Fig. 11B; und
-
Fig. 14 eine schematische Darstellung eines
Manchester-Übertragskettenblocks zum Einsatz in dem Baum aus Fig. 11B.
-
Fig. 7 zeigt ein vereinfachtes Systemdiagramm eines Computersystems mit
einem Prozessor 2. Der Sinn des Diagramms sowie mehrerer folgender Diagramme
ist die Darstellung einer Umgebung, in der ein erfindungsgemäßer
Carry-Lookahead-Baum eingebaut sein kann.
-
Der Prozessor 2 greift mittels dreier nicht im Multiplexerbetrieb arbeitender
Busse auf externe Instruktionen und Daten zu. Der Kanal umfasst einen 32-Bit-Bus
4 für Instruktionsübertragungen, einen zweiten 32-Bit-Bus 5 für
Datenübertragungen und einen dritten Adressenbus 8 für Zugriff sowohl auf Instruktionen als
auch Daten. Der Adressenbus 8 weist eine Pipeline-Konfiguration auf, so dass er
vor Abschluss einer Instruktions- oder Datenübertragung freigegeben werden
kann. Dies ermöglicht einen nachfolgenden Zugriff vor Abschluss des ersten und
ferner die gleichzeitige Ausführung von zwei Zugriffen durch den Prozessor 2.
-
Das in Fig. 7 dargestellte Gesamtsystem kann ferner ein Instruktions-ROM 10
und einen Instruktionsspeicher 12 aufweisen, die beide operativ zwischen dem
Adressenbus 8 und dem Instruktionsbus 4 geschaltet sind. Außerdem sind ein
Datenspeicher 14 und eine Datenübertragungssteuereinrichtung 16 gezeigt, die
operativ zwischen dem Adressenbus 8 und dem Datenbus 6 geschaltet sind.
Ferner ist die Datenübertragungssteuereinrichtung 16 ebenfalls operativ verbunden,
so dass Signale zu einem Systembus 18 gesandt und von diesem empfangen
werden.
-
Fig. 8 zeigt ein Datenflussdiagramm des Prozessors 2, das den Prozessor 2
genauer erläutert.
-
Der Prozessor 2 implementiert eine vierstufige Pipeline zur
Instruktionsausführung, wobei es sich bei den vier Stufen um "Abrufen", "Dekodieren", "Ausführen"
und "Rückschreiben" handelt. Die Instruktionsabrufeinheit 20 des Prozessors 2
ruft Instruktionen ab und liefert Instruktionen an andere Funktionseinheiten. Die
Einheit 20 enthält einen Instruktionsvorabrufpuffer, einen Verzweigungs-Target-
Cache-Speicher und eine Programmzähleinheit. Diese Teileinheiten werden
nachstehend mit Bezug auf Fig. 9 beschrieben. Sämtliche Komponenten der
Instruktionsabrufeinheit 20 arbeiten in der Abrufphase der Prozessor-Pipeline.
-
Der Prozessor 2 weist ferner eine Ausführungseinheit 22 auf. Die
Ausführungseinheit 22 umfasst eine Registerdatei, eine Adresseneinheit eine Arithmetik-/
Logikeinheit, eine Feldverschiebeeinheit, einen Priorisierer und eine
Gleitkommaverarbeitungseinheit. Diese Teileinheiten werden wie die Teileinheiten der
Instruktionsabrufeinheit 20 nachstehend mit Bezug auf Fig. 9 beschrieben. Die
Registerdatei und die Adresseneinheit arbeiten in der Dekodierphase der Pipeline.
Die Arithmetik-/Logikeinheit, die Feldverschiebeeinheit und der Priorisierer
arbeiten in der Ausführungsphase der Pipeline. Die Registerdatei arbeitet in der
Rückschreibphase.
-
Ferner zeigt Fig. 2, dass der Prozessor 2 eine Speicherverwaltungseinheit 24
aufweist. Die Speicherverwaltungseinheit 24 führt Adressenübersetzungs- und
Speicherschutzfunktionen für sämtliche Verzweigungen, Lasten und Speicher
aus. Die Einheit 24 arbeitet in der Ausführungsphase der Pipeline, so dass die
von ihr erzeugte reelle Adresse zu Beginn der Rückschreibphase zur Verfügung
steht.
-
Das Zusammenschalten der Einheiten 20, 22 und 24 im Prozessor 2 sowie ihre
Interfaces zu den Systembussen ist ebenfalls in Fig. 8 dargestellt.
-
Fig. 9 zeigt eine weitere schematische Darstellung von Details bezüglich der
Teilkomponenten des Prozessors 2. Wie oben gesagt, weist die
Instruktionsabrufeinheit 20 einen Instruktionsvorabrufpuffer 26, einen Verzweigungs-Target-Cache-
Speicher 28 und eine Programmzähleinheit 30 auf. Wie oben ferner gesagt,
umfasst die Speicherverwaltungseinheit 24 eine Vorrichtung 32 zum Durchführen
von Adressenübersetzungs- und Speicherschutzfunktionen für sämtliche
Verzweigungen, Lasten und Speicher. Und schließlich weist die Ausführungseinheit
22 eine Registerdatei 24, eine Adresseneinheit 36, eine Arithmetik-/Logikeinheit
38, eine Feldverschiebeeinheit (mit Bezugszeichen 38 bezeichnet), einen
Priorisierer (ebenfalls mit Bezugszeichen 38 bezeichnet) und eine
Gleitkommaverarbeitungseinheit 40 auf. Obwohl verschiedene andere Elemente (z. B.
Spezialregister 42) und Zusammenschaltdetails in Fig. 9 dargestellt sind, sind weitere
Details bezüglich sämtlicher Einheiten mit Ausnahme der Gleitkommaeinheit 40 und
anderer operativ mit dieser verbundener Elemente hier nicht beschrieben, da
diese nur peripher mit der Erfindung in Zusammenhang stehen und das
Diagramm allein für Fachleute auf dem Gebiet zum Verständnis des Prozessors 2
ausreicht.
-
Mehrere interessante Aspekte der Gleitkommaeinheit 40 sind in Fig. 9
dargestellt. Unter Berücksichtigung der Tatsache, dass die Gleitkommaeinheit 40
Operanden A und B manipuliert, kommen diese Operanden A und B über Busse 44
bzw. 46 von der Registerdatei 34. Ergebnisse der von der Gleitkommaeinheit 40
durchgeführten Manipulationen, z. B. Berechnungen, werden über den
Ergebnisbus 48 in die Registerdatei geschrieben. Ferner werden Instruktionen für die
Operation der Gleitkommaeinheit 40 über den Prozessorinstruktionsbus 50 an die
Registerdatei übermittelt.
-
Fig. 10 zeigt verschiedene Teilkomponenten einer als Pipeline ausgeführten
Gleitkommaverarbeitungseinheit gemäß der vorliegenden Erfindung.
-
Die oben mit Bezug auf Fig. 9 beschriebenen Interface-Stellen sind in dieser Figur
in ähnlicher Weise dargestellt und bezeichnet, d. h. Operanden von der
Registerdatei werden über die A- und B-Busse 44,46 der Gleitkommaeinheit zugeführt,
die Ergebnisse verlassen die Gleitkommaeinheit über den Ergebnisbus 48 und
Instruktionen werden über den Instruktions- oder I-Bus 50 an die
Gleitkommaeinheit übermittelt. Insbesondere zeigt Fig. 10, dass A-Bus, B-Bus und
Ergebnisbus operativ mit einer Interface-Einheit 52 innerhalb der Gleitkommaeinheit
verbunden sind, wohingegen der I-Bus operativ mit einer ebenfalls in der
Gleitkommaeinheit vorgesehenen Steuereinrichtung 54 verbunden ist.
-
Es ist bekannt, dass bei Eingabe von zu verarbeitenden Zahlen, d. h. Operanden
A und B, in eine Gleitkommaeinheit, wie die Gleitkommaeinheit 40, die
Gleitkommaeinheit die gewünschten (oder angewiesenen) arithmetischen
Operationen durchführt und das Ergebnis auf einem Ergebnisbus, wie dem Ergebnisbus
48, ausgibt. Gleitkommaeinheiten, wie die Gleitkommaeinheit 40, können sowohl
Gleitkomma- als auch ganze Zahlen verarbeiten. Verschiedene
Gleitkommaformate können unterstützt werden, wie das 32-Bit- (einfache Genauigkeit) und 64-
Bit-Format (doppelte Genauigkeit). Ferner kann die Gleitkommaeinheit 40 die
Konversion von ganzen Zahlen in Gleitkommazahlen und umgekehrt verarbeiten.
Jeder der oben genannten Aspekte hinsichtlich der Gleitkommaeinheit 40 wird
ferner in den oben erwähnten verwandten Fällen, auf die hier Bezug genommen
wird, behandelt.
-
Ferner ist für Fachleute auf dem Gebiet die Funktion und Operation der meisten
dargestellten Teilkomponenten von Gleitkommaeinheiten anhand von Fig. 10
ersichtlich. Diese Teilkomponenten, die in einer im wesentlichen konventionellen
individuellen Weise arbeiten und daher an dieser Stelle nicht detailliert
beschrieben werden, umfassen einen Vordetektor 56, einen Denormalisierer 58, eine
Multifunktionseinheit 60, einen Renormalisierer 62, einen Multiplizierer 64, einen
Teilproduktsummierer 66, einen Dividierer 68, einer Runder 70 und einen
Akkumulator/Akkumulatoren 72. Es gibt jedoch einige sehr wichtige Aspekte bezüglich
dieser Teilkomponenten und deren Zusammenwirken, und diese sind ausführlich
in den verwandten Fällen, auf die der Leser dringend verwiesen wird,
beschrieben.
-
Fig. 11A zeigt eine schematische Darstellung eines erfindungsgemäßen Radix-
Vier-Lookahead-Baums. Dieser Radix-Vier-Lookahead-Baum ist, wie in der
verwandten Anmeldung Nr. 91301348.8 beschrieben, in einen Addierer einbaubar
und ferner in Elementen, wie dem Dividierer 68, dem Multiplizierer 64 und der
Multifunktionseinheit 60 der in Fig. 10 dargestellten Gleitkommaeinheit
eingebaut. Es versteht sich von selbst, dass dieser Radix-Vier-Lookahead-Baum sowie
der oben genannte Addierer auch an vielen anderen Stellen eingesetzt werden
kann.
-
Der in Fig. 11A dargestellte Baum weist drei verschiedene Arten von Blöcken auf.
Diese drei verschiedenen Arten von Blöcken sind ein modifizierter
Übertragskettenblock, eine Modifizierung für den Übertrag aus einer vorhergehenden Position
in den Übertragskettenblock und ein Manchester-Übertragskettenblock. Jeder
dieser drei unterschiedlichen Blöcke wird nachstehend beschrieben.
-
Fig. 11A und Fig. 11B zeigen, dass diese drei unterschiedlichen Arten von
Blöcken in drei Ebenen angeordnet sind. Die erste Ebene weist fünfzehn modifizierte
Übertragskettenblöcke 74-102 und einen sechzehnten Block auf, der eine
Modifizierung für den Übertrag aus einer vorhergehenden Position in den
Übertragskettenblock 104 ist. Diese zweite Ebene umfasst vier
Manchester-Übertragskettenknoten 106-112 und die dritte Ebene (insbesondere in Fig. 11B dargestellt) zwei
Manchester-Übertragskettenknoten 114,116 (von denen einer, nämlich der mit
Bezugszeichen 116 bezeichnete, eine "redundante Zelle" ist, die nachstehend
beschrieben wird) (es sei darauf hingewiesen, dass die redundante Zelle in. Fig.
11A nicht dargestellt ist).
-
Fig. 12, 13 und 14 zeigen, das eine Manchester-Übertragskette, Block 110,
Ausbreitungs- und Generiersignale von vier Kinderknoten oder von den
Ausbreitungs-/Generiereingängen empfängt und die Blockgenerier- und
Blockausbreitungssignale erzeugt. Eine modifizierte Übertragskette, Block 74, hat eine
ähnliche Funktion mit weniger Transistoren. Die modifizierte Übertragskette, Block
104, führt eine ähnlich Funktion aus, wobei ein Übertrag aus einer
vorhergehenden Position berücksichtigt wird.
-
Fig. 11A zeigt, dass jeder auf Ebene Eins dargestellte Knoten: 74, 76, 78, 80, 82,
84, 86, 88, 90, 92, 94, 96, 98, 100, 102 und 104 Blockausbreitungen und
-generierungen für vier Eingangspositionen erzeugen. Jeder der Knoten auf Ebene
Zwei: 106, 108, 110 und 112 erzeugt Blockausbreitungen und -generierungen
von vier Blöcken der Ebene Eins. Somit liefert Ebene Zwei Informationen über
4 · 4- oder 16-Bit-Blöcke. Block 114 auf Ebene Drei liefert Blockinformationen
über vier der Blöcke auf Ebene Zwei oder 4x(4 · 4) oder 64 Bits. Fachleute auf
dem Gebiet erkennen, dass diese Schaltung Überträge ohne große interne
Belastung in Logbase 4-Verzögerungen aufnimmt.
-
Fachleute auf dem Gebiet seien darauf hingewiesen, dass die in Fig. 11B
dargestellte Schaltung auf einem Radix-Vier-Lookahead-Baum basiert. Der Basis-
Radix-Vier-Carry-Lookahead-Baum aus Fig. 11B liefert Überträge bei Bit 0 (Cin),
4, 8, 16, 32, 48 und 56. Übertrag 8 steht über eine herkömmliche Vorrichtung
von Block 112 zur Verfügung. Überträge 24, 32 und 40 können, wie nachstehend
beschrieben, durch Hinzufügen einer redundanten Zelle erhalten werden.
Überträge 32, 48 und 56 können von Block 114 erhalten werden. Jede der
Übertragsausgangsstellen ist in Fig. 11B eindeutig dargestellt. Natürlich können
bestimmte Überträge an mehr als einer Stelle vom Baum abgezogen werden, z. B.
kann CLA 32 sowohl von 118 als auch von 112 abgezogen werden. Es stehen
Überträge an sämtlichen 8-Bit-Grenzen zur Verfügung, was zu einem idealen
Übertragsvorhersageblock für, jedoch nicht beschränkt auf, den
Hochgeschwindigkeits-Radix-Addierer mit gemischter Basis von Lynch, et al., Anmeldung Nr.
91301348.8 führt, auf die der Leser dringend verwiesen wird.
-
Zum Berechnen von Zwischenüberträgen kann immer eine redundante Zelle,
z. B. Block 116, hinzugefügt werden. Eine solche Zelle ist vom restlichen Baum
versetzt angeordnet, so dass die Zwischenübertragswerte vervollständigt werden
können. In Fig. 11B wird Block 116 zum Beenden der Überträge 24 und 40
verwendet. Es sei darauf hingewiesen, dass der Einsatz der redundanten Zelle zu
keiner Hinzufügung von Gatterverzögerungen führt.
-
Bei einer anderen Variante können sämtliche Blöcke auf der ersten Logikebene
aus dem in Fig. 11A und 11B dargestellten Baum gelöscht und die
Ausbreitungen und Generierungen direkt auf die zweite Ebene gesandt werden. Diese neue
Konfiguration kann jeden anderen Übertrag für eine 16-Bit-Addierung in zwei
Gatterverzögerungen erzeugen. Das Hinzufügen weiterer redundanter Zellen
kann dem Auffinden sämtlicher Überträge ohne Erhöhung der Anzahl von
Gatterverzögerungen dienen.
-
Ein wichtiger Aspekt der vorliegenden Erfindung bezieht sich auf den Manchester-
Übertragskettenblock, z. B. Block 110 aus Fig. 14. Bei dem Basis-Baumknoten
handelt es sich im wesentlichen um das Zusammenfügen zweier
unterschiedlicher Schaltungen, wie Fachleuten auf dem Gebiet jetzt klar sein dürfte. Die linke
Seite ist die Manchester-Übertragskette und die rechte Seite eine
NAND-Gatterkette.
-
Erfindungsgemäß können spezielle Carry-Lookahead-Bäume eine beliebige Radix
aufweisen. Fachleute auf dem Gebiet erkennen, dass die in diesem Patent
beschriebenen Prinzipien immer nach anwendbar sind. Als weiteres Beispiel kann
ein Achter-Baum dadurch konfiguriert werden, dass jeder Knoten 8 Kinder haben
kann. Die in dem vorliegenden Patent beschriebenen Prinzipien sind auch dann
anwendbar. Ein Dreier-Baum hat eine Logbase 3-Leistung, während ein Achter-
Baum eine Logbase 8-Leistung hat. Natürlich erzeugt der Logbase 8-Baum einen
sehr kleinen Satz von Überträgen und hat sehr große Baumknoten.
-
Es sei ferner darauf hingewiesen, dass bei einer erfindungsgemäßen Schaltung
fundamentale Übertragsketten in einem Baum mit hoher Radix angeordnet sind.
-
Diese Schaltung stellt im wesentlichen eine Verbesserung gegenüber binären
Carry-Lookahead-Schaltungen dar. Der Grund dafür, dass die Schaltung eine
Verbesserung darstellt, besteht darin, dass sie eine Hochradixtechnik enthält, die
bessere Last- und Geschwindigkeitscharakteristiken aufweist als binäre Carry-
Lookahead-Schaltungen. Die erfindungsgemäße Schaltung hat eine Logbase-
Radix von N Gatterverzögerungen, wobei N eine Größe für die Addition und die
Radix ein Vielfaches des Baums ist. Ferner verwendet eine erfindungsgemäße
Schaltung nur drei einfache Teilblöcke. Außerdem stellt die Schaltung aufgrund
des einfachen Auffindens von Zwischenüberträgen eine Verbesserung dar.
-
Fachleute auf dem Gebiet erkennen, dass die in Fig. 11A und 11B dargestellten
Schaltungen auf einfache Weise für Carry-Lookaheads mit anderen Größen als
Vier bis zur iten Potenz beschnitten werden können, wobei i gleich 1, 2, 3, ... ist.
Ungeachtet der Tatsache, dass eine solche Skalierung erfolgt, sollte die in Fig.
11A und 11B dargestellte Schaltung beim Skalieren nur wenig an
Geschwindigkeit verlieren. Ein 64-Bit-Carry-Lookahead sollte z. B. drei Gatterverzögerungen
benötigen, wohingegen ein 256-Bit-Carry-Lookahead nur vier
Gatterverzögerungen benötigen würde.
-
Fachleute auf dem Gebiet erkennen jetzt, dass die vorliegende Erfindung eine
Verbesserung gegenüber binären Carry-Lookahead-Schaltungen darstellt. Die
erfindungsgemäße Schaltung löst das Problem der Durchführung einer
umfangreichen Addierung in einer kurzen Zeitspanne mittels einer relativ kleinen
elektronischen Schaltung. Die erfindungsgemäße Schaltung ist schneller und relativ
kleiner als frühere Schaltungen. Sie hat eine Logbase 4 von N Gatterverzögerungen,
wobei N die Größe für die Addition ist, während drei einfache Teilblöcke
verwendet werden. Weitere wichtige Aspekte der vorliegenden Erfindung sind bereits
beschrieben worden.
-
Fachleute auf dem Gebiet erkennen, dass zahlreiche Modifikationen und
Änderungen neben den oben genannten an den hier beschriebenen
Konstruktionstechniken durchgeführt werden können, ohne dass dadurch vom Konzept der
vorliegenden Erfindung abgewichen wird. Entsprechend sei darauf hingewiesen,
dass im Rahmen der folgenden Patentansprüche die vorliegende Erfindung
anders als hier beschrieben angewendet werden kann.