DE69131187T2

DE69131187T2 - Hochgeschwindigkeitsdividierer

Info

Publication number: DE69131187T2
Application number: DE69131187T
Authority: DE
Inventors: Tony Hurson; Thomas W Lynch; Stephen D Mcintyre; Salim A Shah; Ken Tseng
Original assignee: Advanced Micro Devices Inc
Current assignee: Advanced Micro Devices Inc
Priority date: 1990-04-02
Filing date: 1991-02-20
Publication date: 2000-01-05
Anticipated expiration: 2011-02-21
Also published as: JP3144816B2; EP0450754B1; EP0450754A3; JPH04227535A; EP0450754A2; DE69131187D1; ATE179809T1; US5128891A

Description

Die vorliegende Erfindung betrifft einen Gleitkomma-Prozessor für ein Computersystem und insbesondere einen Hochgeschwindigkeitsdividierer, der eine iterative Division ohne Bildung eines positiven Rests mit der Radix 4 durchführt. Die vorliegende Erfindung betrifft einen Hochgeschwindigkeitsdividierer, der eine iterative Division ohne Bildung eines positiven Rests mit der Radix 4 und Quadratwurzelberechnungen mit der Radix 2 durchführt.
Verwandte Erfindungen sind in den mitanhängigen Anmeldungen EP-A-0 450 755, EP-A-0 450 752 und EP-A-0 450 751 beschrieben.
Zahlreiche Computerprogramme erfordern eine große Zahl von arithmetischen Gleitkommaoperationen. Infolgedessen ist eine große Zahl der von einem Computer, in dem derartige Programme ablaufen, durchgeführten Befehle Gleitkomma-Befehle. Bei solchen Programmen gilt, daß je größer die Zahl der pro Zyklus ausführbaren arithmetischen Gleitkomma-Befehle ist, desto schneller ist die Betriebsgeschwindigkeit der Maschine. Daher wurden zahlreiche Bemühungen unternommen, die Gleitkomma-Verarbeitungszeit zu verkürzen. Beispielsweise offenbart das US-Patent 4 683 547 an DeGroot eine arithmetische Gleitkommaeinheit, die das Erzeugen von zwei Gleitkommaergebnissen pro Zyklus ermöglicht. Dasselbe Patent erörtert bekannte Lehren zu arithmetischen Einheiten, die das Ausführen mehrerer arithmetischer Operationen auf einmal ermöglichen. Ein weiterer Ansatz ist im US-Patent 4 075 705 an O'Leary dargelegt. Bei O'Leary sind der Gleitkomma-Addierer und der Gleitkomma-Dividierer Pipelineschaltungen mit mehreren Stufen, die zwischengefügte haltespeicher zum Einfangen von Teilergebnissen aufweisen, welche während eines Taktzyklus berechnet wurden und im nächsten Taktzyklus an die nächste Stufe weitergeleitet werden sollen. Ansätze, wie die in DeGroot und O'Leary diskutierten, konzentrieren sich hauptsächlich auf die Beschleunigung der Fähigkeit einer arithmetischen Gleitkommaeinheit zur Durchführung wiederholter Opera tionen und betrafen nicht die Erhöhung der Geschwindigkeit, mit der eine arithmetische Gleitkommaeinheit eine bestimmte Operation durchführen kann.
Da es sich beim Dividieren um die komplexeste arithmetische Operation handelt und üblicherweise mehr Hardware und Rechenzeit erforderlich ist als bei anderen arithmetischen Operationen, beispielsweise Addition oder Multiplikation, ist die Geschwindigkeit, mit der eine Divisionsberechnung von einem Dividierer ausgeführt werden kann, von besonderer Wichtigkeit. Mit zunehmender Zahl der Ziffern in den Operanden die dividiert werden sollen ist beispielsweise eine zunehmend lange Zeitspanne für die Durchführung der gewünschten arithmetischen Operationen durch den Dividierer erforderlich. Des weiteren verwenden große Computer mit Hochgeschwindigkeitsmultiplizierern oft eine Multiplikationsart der Division, bei der das Dividieren durch das Wiederholen von Multiplikationen geschieht. Jedoch erfordert die Implementierung einer derartigen multiplizierenden Division durch komplementäre Schaltungen große Mengen an Hardwareelementen und ist daher unpraktisch.
Divisionsverfahren können in "einen positiven Rest" und "keinen positiven Rest" bildende Verfahren unterteilt werden. Beim keinen positiven Rest bildenden Verfahren wird eine Reihe von Quotientenziffern mit den Werten:
-((Beta)-1), ..., -2, -1, 1, 2, ..., ((Beta)-1) (1)
wobei (Beta) die Radix des Divisors und k der Redundanzfaktor ist;
vorab bestimmt und jede Ziffer des Quotienten wird aus der Gruppe von Quotienten nach einem iterativen Verfahren ausgewählt, das auch eine Reihe von Teilresten produziert, die zum Wählen der nächsten Quotientenziffer verwendet werden. Eine Variante der keinen positiven Rest bildenden Division wird im allgemeinen als "SRT" Division bezeichnet, die durch das Vorabbestimmen einer Reihe von Quotientenziffern im Bereich von:
-(k(Beta)-1)), ..., -2, -1, 0, 1, 2, ..., (k(Beta)-1) (2)
wobei (Beta) die Radix der Division ist;
gekennzeichnet ist, aus dem jede Quotientenziffer gewählt ist.
Ein kennzeichnendes Merkmal der keinen positiven Rest bildenden Dividierer ist die Verwendung einer negativen Zahl und einer positiven Zahl im Teilrest, der in einer vorherigen Operation gebildet wurde, bei der eine Ziffer des Quotienten bestimmt wird. Ein derartiger, keinen positiven Rest bildender Dividierer ist im US-Patent 4 722 069 an Ikeda offenbart. Ikeda offenbart einen keinen positiven Rest bildenden Dividierer, der aufweist: ein Divisorregister zum Speichern eines Divisors, einteilrestregister zum Speichern eines Dividenden oder eines Teilrests, eine Vorhersageeinrichtung zum Vorhersagen eines Teilquotienten, einen Multiplizierer zum Multiplizieren des Inhalts des Divisorregisters, einen ersten Addierer zum Subtrahieren des Ausgangssignals des Multiplizierers von dem Inhalt des Teilrestregisters und zum Berechnen des Teilrests derart, daß die Vorhersageeinrichtung den Teilquotienten aus oberen Ziffern des Divisorregisters und oberen Ziffern des Teilrests vorhersagt. Die Verwendung von Multiplizierern und mehreren Addierern beim Ikeda-Dividie rer, führt jedoch zu erheblichen Kostensteigerungen und erhöhtem Platzbedarf des Dividierers, aufgrund des relativ hardware-intensiven Designs.
Ein anderer keinen positiven Rest bildender Dividierer ist im US-Patent 4 724 529 an Irukulla et al. beschrieben. Zwar verwendet der Dividierer nach Irukulla et al. einen Addierer/Subtrahierer, der einen Teilrest nach der Beziehung
Pj+1 = (Beta)Pj - qjD (3)
berechnet, jedoch verwendet dieser Dividierer kosten- und raumintensive Multiplikationsschaltungen zur Erzeugung von qjD. Schließlich offenbart der Artikel von Birman et al. mit dem Titel "Developing the WTL3170/3171 Sparc Floating-Point Coprocessors", IEEE Micro. S. 55-64 (Februar 1990) eine arithmetische Gleitkommaoperationseinheit zum Durchführen von keinen positiven Rest bildenden, Radix-4-Mantissen-Divisions- und Quadratwurzelberechnungen. Jedoch teilt sich die in dem Artikel von Birman et al. offenbarte Vorrichtung die Erst-Divisions-/Quadratwurzellogik und die "Mal-Drei"-Erzeugung mit einem Multiplizierer, wodurch der Gleitkommaprozessor daran gehindert ist, Multiplikationsoperationen während einer Divisionsoperation durchzuführen. Ferner ist die Vorrichtung nach dem Artikel von Birman et al. derart konfiguriert, daß sie die Erzeugung des Dreifachen des Divisors unter Verwendung von Multiplikationsschaltungen erfordert, bevor irgendein Quotientenbit bestimmt wird, wodurch die Berechnung des Quotienten verlangsamt wird.
Das IBM technical disclosure bulletin, Band 30; Nummer 6, 11/87, Seiten 415 bis 419 "Radix 16 Divider" offenbart einen weiteren bekannten Radix-Dividierer.
Ein Artikel von Milos D. Ercegovac und Tomas Lang, "On-The-Fly Conversion of Redundant into Conventional Representations", IEEE Transactions on Computers, Bd. C-36, Nr. 7, Juli 1987, offenbart einen bekannten Radix-2- Dividierer.
Die vorliegende Offenbarung beschreibt einen Hochgeschwindigkeitsdividierer, der eine keinen positiven Rest bildende iterative Division mit der Radix 4 durchführt. Der Dividierer führt ferner Quadratwurzelberechnungen mit der Radix 2 aus.
Der Dividierer minimiert die Menge der erforderlichen Logikschaltungen, während der Dividierer beschleunigt wird, um mit der Rate einer Iteration der Divisionsoperation pro Taktimpulsphase zu arbeiten.
Die vorliegende Erfindung schafft einen Dividierer mit zwei parallelen Quotientenregistern zum Speichern einer auszugebenden Quotientenvorhersage und zum Speichern der Quotientenvorhersage minus eins zum Korrigieren fehlerhafter Quotientenvorhersagen vor dem Ausgeben.
Nach einem Aspekt ist ein Dividierer zum Durchführen der Division eines ersten Operanden durch einen zweiten Operanden zur Erzeugung eines Ergebnisses vorgesehen, mit einer Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten, einer Einrichtung zum iterativen Vorhersagen von Quotientenbitwerten, alternativ auch Quotienten genannt, einer Einrichtung zum Erzeugen von Vielfachen des zweiten Operanden und einer Einrichtung zum Wählen eines der erzeugten Vielfachen. Die Einrichtung zum Erzeugen einer Reihe von Teilresten wählt den zweiten Operanden als den ersten Teilrest. Die Quotienten vorhersageeinrichtung sagt einen ersten Quotientenwert auf der Basis des ersten Operanden und des zweiten Operanden und einen nächsten Quotientenwert auf der Basis der Reihe von Teilresten und des zweiten Operanden vorher. Die Wähleinrichtung wählt eines der erzeugten Vielfachen zum Erzeugen eines nächsten Teilrests basierend auf der nächsten Quotientenvorhersage. Ein nächster Teilrest wird sodann aus dem erzeugten Teilrest und dem ausgewählten Vielfachen des zweiten Operanden erzeugt.
Nach einem anderen Aspekt ist eine Vorrichtung zum Dividieren eines Dividenden durch einen Divisor zum Erzeugen eines Ergebnisses vorgesehen, mit einem Teilrestregister, das zum Empfangen und Speichern von Teilresten verbunden ist, einem Divisorregister, das zum Empfangen und Speichern des Divisors verbunden ist, einer Quotientenvorhersageschaltung, die zum Empfangen des Divisors vom Divisorregister und einer Reihe Teilresten aus dem Teilrestregister verbunden ist, einem ersten Quotientenregister, das mit der Quotientenvorhersageeinrichtung verbunden ist, um die von der Quotientenvorhersageeinrichtung bestimmte Reihe von Quotientenwerten zu empfangen und zu speichern, einer Einrichtung zum Erzeugen von Vielfachen des Divisors, und einem speziellen Übertragspeicheraddierer der mit der Einrichtung zum Erzeugen von Vielfachen des Divisors und mit der Quotientenvorhersagelogik verbunden ist. Der Übertragspeicheraddierer wählt Vielfache des Divisors basierend auf den vorhergesagten Quotienten und bestimmt einen nächsten der Reihe von Teilresten basierend auf dem im Teilrestregister gespeicherten Teilrest und dem gewählten Divisorvielfachen. Die Quotientenvorhersagelogik empfängt sodann den nächsten Teilrest zur Bestimmung des nächsten aus der Reihe der Quotientenwerte.
Die zugehörigen Zeichnungen zeigen als Beispiele:
Fig. 1a - ein Blockschaltbild eines ersten Ausführungsbeispiels eines Hochgeschwindigkeitsdividierers zur Durchführung von keinen positiven Rest bildenden iterativen Divisionen mit der Radix 4, aufgebaut nach den Lehren der vorliegenden Erfindung;
Fig. 1b - ein Blockschaltbild des Quotientenregisters von Fig. 1a;
Fig. 1c - ein Blockschaltbild zusätzlicher Details des Quotientenregisters der Fig. 1a-b;
Fig. 2 - eine graphische Wiedergabe der ersten Vorhersagelogik des Dividierers von Fig. 1;
Fig. 3 - eine graphische Wiedergabe der Quotientenvorhersagelogik des Dividierers von Fig. 1;
Fig. 4 - ein Blockschaltbild eines zweiten Ausführungsbeispiel eines Hochgeschwindigkeitsdividierers zur Durchführung einer keinen positiven Rest bildenden iterativen Division mit der Radix 4;
Fig. 5 - ein Blockschaltbild des Hochgeschwindigkeitsdividierers von Fig. 4, der zum Durchführen von Quadratwurzelberechnungen mit der Radix 2;
Fig. 6 - eine graphische Wiedergabe der Quadratwurzelvorhersagelogik des Dividierers von Fig. 5; und
Fig. 7 - eine Darstellung der Phasenlogik.
Unter Bezugnahme auf die Fig. 1 wird zunähst ein Hochgeschwindigkeitsdividierer 100 zur Durchführung einer keinen positiven Rest bildenden iterativen Division mit der Radix 4 näher beschrieben. Es ist vorgesehen, daß der hierin offenbarte Dividierer als ein Bestandteil einer Gleitkommaprozessoreinheit, beispielsweise einer der in den von der Anmelderin eingereichten mitanhängigen Europäischen Patentanmeldungen mit den Veröffentlichungsnummern EP-A-0 450 755, EP-A-0 450 752 und EP-A-0 450 751 beschriebenen Gleitkommaprozessoreinheiten ist.
Wie in den genannten Anmeldungen im Detail ausgeführt, besteht ein Gleitkommaprozessor aus mehreren arithmetischen Gleitkommaoperationseinheiten, beispielsweise einem Addierer, einem Multiplizierer und einem Dividierer, zum Durchführen arithmetischer Operationen mit Eingabeoperanden. Wenn zwei Eingabeoperanden, beispielsweise der Operand A und der Operand B, in eine arithmetische Gleitkommaoperationseinheit eingegeben werden, führt die arithmetische Gleitkommaoperationseinheit die gewünschte arithmetische Operation an den eingegebenen Operanden durch und gibt die Ergebnisse auf einem Ergebnisbus aus. Üblicherweise kann der Prozessor sowohl Gleitkommazahlen, als auch ganze Zahlen verarbeiten. Zahlreiche verschiedene Gleitkommaformate können unterstützt werden, einschließlich 32 Bits (Einfach- Präzision) und 64 Bit (Doppel-Präzision). Darüber hinaus kann der Gleitkommaprozessor die Umwandlung von ganzen Zahlen in Gleitkommazahlen und umgekehrt vornehmen.
Bei einer Divisionsoperation wird ein Dividend durch einen Divisor zum Erzeugen des Quotienten geteilt. Bei der vorliegenden Erfindung wird ein Dividend dem Dividierer 100 über einen A-Bus und ein Divisor dem Dividierer 100 über einen B-Bus zugeführt, und der Quotient vom Dividierer 100 über einen RESULT-Bus ausgegeben. Wie im folgenden noch genauer beschrieben, ist der Dividierer 100 durch eine Dividierersteuerung 110 gesteuert, die Befehle von einem I-Bus empfängt und, basierend auf den empfangenen Befehlen, während des Dividierens Steuersignale an die verschiedenen Elemente des Dividierers 100 erzeugt, d. h. eine erste Quotientenvorhersageeinrichtung 102, ein Teilrestregister 106, ein Divisorregister 108, ein erstes Quotientenregister 114a, ein zweites Quotientenregister 114b, ein 3x-Divisorregister 116, eine Nullerkennungseinrichtung 122 und eine Restvorzeichenerkennungseinrichtung 123.
Der A-Bus ist mit einer ersten Quotientenvorhersageeinrichtung 102 und einem Teilrestregister 106 verbunden. In gleicher Weise ist der B-Bus mit der ersten Quotientenvorhersageeinrichtung 102, einem Schieber 103, einem ersten Eingang des Addierers 104 und einem Divisorregister 108 verbunden. Um einen Dividiervorgang zu beginnen, empfängt die Dividierersteuerung 110 einen Befehl von dem I-Bus, um die Divisionsoperationen zu beginnen. Die erste Stufe einer Divisionsoperation, im allgemeinen als "Pre-Overhead"-Stufe bezeichnet, beginnt, wenn ein Dividend, beispielsweise der Operand A der ersten Quotientenvorhersageeinrichtung 102 und dem Teilrestregister 106 über den A-Bus und ein Divisor, beispielsweise der Operand B, der ersten Quotientenvorhersageeinrichtung 102 und dem Divisorregister 108 über den B-Bus während einer ersten Phase eines von dem System erzeugten und verteilten zweiphasigen oszillierenden Taktimpulses zugeführt wird.
Während der ersten Phase des Taktimpulses wird der Dividend A im Teilrestregister 106 und der Divisor B im Divisorregister 108 zwischengespeichert. Darüber hinaus werden der Dividend A und der Divisor B in die erste Quotientenvorhersageeinrichtung 102 eingegeben, in der ein durch Dividieren des Dividenden A durch den Divisor B erzeugtes erstes Bit q&sub1; des Quotienten Q bestimmt wird. Die erste Quotientenvorhersageeinrichtung 102 besteht aus kombinatorischen Logikschaltungen, die derart konfiguriert sind, daß je nach in die erste Quotientenvorhersageeinrichtung 102 eingegebenem Dividenden A und Divisor B, ein erstes Quotientenbit q&sub1; ermittelt wird.
Fig. 2 stellt eine graphische Wiedergabe der kombinatorischen Logikschaltung dar, die die erste Quotientenvorhersageeinrichtung 102 aufweist. Genauer gesagt zeigt die Fig. 2 ein logisches PD-Diagramm, das zum Ableiten der kombinatorischen Logik für die erste Quotientenvorhersageeinrichtung 102 verwendet werden kann. In Fig. 2 sind mögliche Werte des in die erste Quotientenvorhersageeinrichtung 102 eingegebenen Divisors A entlang der Horizontalen und mögliche Werte des in die erste Quotientenvorhersageeinrichtung 102 eingegebenen Divisors B entlang der Vertikalen aufgetragen. Dementsprechend stellt jeder Punkt auf diesem Diagramm ein Paar aus einem Divisor und einem Dividenden. Da an dem Dividierer 100 ankommende Zahlen normalisiert werden müssen, und da der Dividend zu Anfang durch 4 geteilt wird, und da schließlich die erste Quotientenvorhersageeinrichtung 102 nur die obersten beiden Bits von jedem eingehenden Operanden empfängt, sind die einzigen in diesem Diagramm verwendeten Punkte: (1,00, 0,010), (1,00, 0,01), (1,01, 0,010), (1,01, 0,011), (1,10, 0,010), (1,10; 0,011), (1,11, 0,010) und (1,11, 0,011). Da jedoch der reale Wert des Divisors im Intervall [1,00, 10) und der reale Dividend im Intervall [0,01, 0.1) liegen kann, tritt in der ersten Quotien tenvorhersageeinrichtung 102 ein Quantisierungsfehler auf. Daher gibt die untere gestrichelte Linie in Fig. 2 die untere Grenze an, bei der ein erster "geratener" Quotient von zwei ausgewählt werden kann, ohne daß er dahingehend falsch ist, daß er um mehr als eins zu groß ist. In ähnlicher Weise zeigt die obere gestrichelte Linie die untere Grenze, bei der der geratene Quotient von drei gewählt werden kann, ohne um mehr als eins zu groß zu sein, und die obere Grenze, an der der Quotient von eins geraten werden kann. Schließlich zeigen die oberen und die unteren geraden Linien eine quantisierte Entscheidungsschwelle, die leicht in einer kombinatorischen Logik eingesetzt werden kann. Es ist für den Fachmann auf diesem Gebiet leicht erkennbar, daß, wenn die untere gerade Linie eine Schwelle angibt, bei oder oberhalb welcher ein Quotient eins geraten wird, und obere Linie eine Schwelle wiedergibt; bei oder oberhalb welcher ein Quotient von zwei geraten wird, die quantisierten Geratenen Werte gültig sind, ungeachtet der tatsächlichen Werte des Divisors und des Dividenden. In Fig. 2 bewirken sämtliche Punkte einen geratenen Quotienten von 1, außer (1,00, 0,011) und (1,01, 0,011), die einen geratenen Quotienten von 2 bewirken.
Wie in Fig. 1 dargestellt, ist die erste Quotientenvorhersageeinrichtung 102 mit einer Quotientenvorhersageeinrichtung 112 und dem Quotientenregister 114 derart verbunden, daß nach der Schätzung von q&sub1; durch die erste Quotientenvorhersageeinrichtung, dieser Schätzwert von q&sub1; an die Quotientenvorhersageeinrichtung 112 gesandt wird. Die Quotientenvorhersageeinrichtung 112 sendet ihrerseits einem Wert q&sub1;, der entweder 0, 1, 2, oder 3 sein kann, und das entsprechende Vorzeichenbit an das Quotientenregister 114. Darüber hinaus sendet die erste Quotientenvorhersageeinrichtung 102 ein Signal an das Quotientenregister 114, um den Beginn des Dividierens anzuzeigen.
Unter Bezugnahme auf die Fig. 1b sei im folgenden das Quotientenregister der Fig. 1a näher beschrieben. Das Quotientenregister 114 weist auf: ein erstes Quotientenregister (oder "Q") 114a zum Speichern des gegenwärtigen Schätzwertes des endgültigen Quotienten Q, ein zweites (oder "Q-1") Quotientenregister 114b zum Speichern des gegenwärtigen Schätzwerts des endgültigen Quotienten Q minus 1 von der gegenwärtigen Bitposition j, ein Schieberegister 114c zum Erzeugen gegenwärtiger Bitzeiger 1000, ein Steuersignal "Divide start" von der ersten Quotientenvorhersageeinrichtung 112; ein an die Dividierersteuerung 110 ausgegebenes Steuersignal "Divide end" 1016, einen q-Dekodierblock 114d zum Erzeugender gegenwärtigen Werte von q und q-1, die in die Quotientenregister 114a, 114b einzuschreiben sind, und eine (in Fig. 1c dargestellte) Einrichtung zum Schreiben des Inhalts des Q-Registers 114a in das Register Q-1 114b und zum Schreiben des Inhalts des Registers Q-1 114b in das Q-Register 114.
Im folgenden werden die Quotientenregister 114a, 114b im einzelnen anhand der Fig. 1c beschrieben. Jedes Quotientenregister 114a, 114b besteht aus einer Reihe von Quotientenbitregistern 114a-0, ...; 114a-(i-1), 114a-i, 114b-0, ..., 114b-(i-1); 114b-i, die jeweils parallel verbunden sind. Das Schieberegister 114c empfängt das Divisionsstartsignal von der ersten Quotientenvorhersageeinrichtung 112 und beginnt Paare von Zeigern 1000 zu erzeugen, die mit Paaren der Quotientenbitsregister 114a-0, ..., 114a-(i-1), 114a-i, 1 14b-0, ..., 114b-(i-1), 114b-i verbunden sind, derart, daß die mit den beiden höchstwertigen Quotientenregisterbits verbundenen Zeiger als erste aktiviert werden. Nachfolgende Iterationen bewirken die Aktivierung jeweils geringerwertiger Zeigerpaare. Basierend auf dem Wert und dem Vorzeichen, die die zweite Quotientenvorhersageeinrichtung 112 sendet, erzeugt der q-Dekodiererblock 114d die in die Positionen der gegenwärtig gezeigten Quotientenbitregister einzuschreibenden Bitwerte.
Während jeder beliebigen Iteration schreibt der q-Dekodierer 114d, wenn das q- Vorzeichen positiv ist, den q-Wert an die Position in den Quotientenbitregistern 114a, die gegenwärtig gezeigt werden, und den Wert q-1 an die Position in den Quotientenbitregistern 114b, die gegenwärtig gezeigt werden. Sämtliche verbleibenden Bitpositionen innerhalb des Registers Q-1 114b werden entsprechend den entsprechenden Bitpositionen im Register Q 114a beschrieben. Bei negativem Vorzeichenwert von q schreibt der q-Dekodierer 114a den entsprechenden q-Wert an die gegenwärtig angezeigte Position innerhalb des Quotientenbitregisters 114a und den Wert q-1 an die gegenwärtig angezeigten Positionen des Quotientenbitregisters 114b. Sämtliche verbleibenden Bitpositionen innerhalb des Q-Registers 114a werden entsprechend den Bitpositionen im Register Q-1 114b beschrieben. Wenn schließlich der Wert q Null ist, empfängt die Position im Quotientenbitregister 114a eine 0 und die Position innerhalb des Quotientenbitregisters 114b eine 3. Bestimmte Zeiger 1000 werden als Divisionsende-Indikatoren 1016 zur Verwendung durch die Dividierersteuerung 110 der Fig. 1 eingesetzt.
Während der ersten Phase des ersten Taktimpulses empfängt ferner der Addierer 104 den Divisor an einem ersten Eingang und das Doppelte des Divisors an einem zweiten Eingang. Die Erzeugung des Doppelten des Divisors ist ein relativ einfacher Vorgang und kann von einem Schieberegister 103 durchgeführt werden, das den Divisor empfängt, das Doppelte des Divisors durch Schieben des Divisors über eine einzelne Binärstelle nach links erzeugt und das Doppelte des Divisors dem Addierer 104 zuführt. Das Divisorregister ist mit einem Divisormultiplexer 118 verbunden und der Divisor B wird dem Divisormultiplexer 118 erneut während der ersten Phase des ersten Taktimpulses zugeführt.
Während einer zweiten Phase des ersten Taktimpulses beginnt die "Overhead"- Stufe der Divisionsoperation mit der Berechnung einer ersten Iteration der keinen positiven Rest bildenden Divisionsoperation. Zu diesem Zeitpunkt liefert das Teilrestregister 106 den Dividenden A und das Divisorregister 108 liefert den Divisor B an die Quotientenvorhersageeinrichtung 112. Dieser ähnlich, jedoch ein wenig komplizierter als die erste Quotientenvorhersageeinrichtung, ist die Quotientenvorhersageeinrichtung 112 eine kombinatorische Logikschaltung, die derart konfiguriert ist, daß je nach dem Dividenden A und dem Divisor B, die in die Quotientenvorhersageeinrichtung 112 eingegeben werden, ein Quotientenbit qj und ein Vorzeichenbit sj von der Quotientenvorhersageeinrichtung 112 gewählt werden.
Fig. 3 zeigt eine graphische Darstellung der kombinatorischen Logikschaltung, die die Quotientenvorhersageeinrichtung 112 aufweist. Wie in Fig. 2 ist in Fig. 3 ein logisches PD-Diagramm dargestellt, das zum Ableiten kombinatorischer Logik, im vorliegenden Fall der kombinatorischen Logik, welche die Quotientenvorhersageeinrichtung 112 aufweist, verwendet werden kann. Ferner zeigt Fig. 2 einen kleinen Teil der Fig. 3. Daher sind die in Zusammenhang mit der graphischen Darstellung von Fig. 2 im Detail ausgeführten Prinzipien gleichermaßen anwendbar. Wie aus Fig. 3 ersichtlich bestimmt die Quotientenvorhersageeinrichtung 112 Q al eine der folgenden Zahlen:
(-3), (-2), (-1), (-0), (+0), (+1), (+2), (+3);
je nach dem Teilrest und dem Divisor, die in die Quotientenvorhersageeinrichtung 112 eingegeben werden. Wiederum wird das vorzeichenbehaftete Quotientenbit Qj nach dem Wählen an die Quotientenregister 114a, 114b zum Speichern in dem Register für das nächstwertige Quotientenbit übertragen.
Des weiteren werden nach dem Wählen die Vorzeichen- und Quotientenbits von der Quotientenvorhersageeinrichtung 112 an einen Übertragspeicheraddierer 120 über Leitungen sj bzw. qj gesendet. Das Teilrestregister 106 gibt den Dividenden oder "ersten Teilrest" oder einen nächsten Teilrest an ein Schieberegister 107 aus, das den Teilrest um zwei Binärstellen nach links verschiebt, wodurch das Vierfache des Teilrests erzeugt wird, das wiederum vom Schieberegister 107 an den Übertragspeicheraddierer 120 geliefert wird. Die endgültigen Eingaben in den Übertragspeicheraddierer 120 sind die Eingänge +0, -0, +D, -D, +2D, -2D, +3D, -3D des Divisormultiplexers. Da jedoch das während der erste Iteration erzeugte Quotientenvorhersagebit qj nie +3 oder -3 sein kann, gibt der Divisormultiplexer +0, -0, +D. -D, +2D und -2D an den Übertragspeicheraddierer 120 aus. Da das Divisorregister 108 zuvor den Divisor an den Divisormultiplexer 118 ausgegeben hat, kann der Divisormultiplexer die genannten Ausgangssignale an den Übertragspeicheraddierer ohne Schwierigkeiten erzeugen.
Als nächstes wählt der Übertragspeicheraddierer 120, der in der genannten mitanhängigen Anmeldung EP-A-0 450 751 im einzelnen beschrieben ist, denjenigen der Eingänge des Divisionsmultiplexers 118, d. h. +0, -0, +D, -D, +2D, -2D, der gleich dem Produkt des vorzeichenbehafteten Quotientenbits und dem Divisor zur Verwendung bei der Durchführung des folgenden rekursiven Algorithmus ist. Unter Verwendung des gewählten Ausgangs des Divisormulti plexers 118 und des Ausgangs des Schieberegisters 107 führt der Übertragspeicheraddierer anschließend eine erste iterative Berechnung durch, um einen nächsten Teilrest durch Anwendung des in der folgenden Gleichung (4) genannten rekursiven Algorithmus zu erzeugen:
Pj+1, = 4Pj - qjD (4)
wobei:
Pj der im Teilrestregister 106 gespeicherte Teilrest ist;
qj das vorzeichenbehaftete Quotientenbit, das von der Quotientenvorhersageeinrichtung 112 erzeugt wird, bezeichnet;
D den Divisor angibt; und
Pj+1 der nächste Teilrest ist.
Auch während der zweiten Phase des ersten Taktimpulses, und überlappend mit der Berechnung der ersten Iteration von Pj+1, addiert der Addierer 104 den Divisor (D) und das Doppelte des Divisors (2D), um das Dreifache des Divisors (3D) zu erzeugen. Der Wert 3D wird sodann zum Speichern an das 3X Divisorregister 116 ausgegeben. Das 3X Divisorregister 116 gibt sodann den Wert 3D an den Divisormultiplexer 118 zum Erzeugen des +3D und des -3D Vielfachen des Divisors aus, die an den Übertragspeicheraddierer 120 zur möglichen Verwendung in nachfolgenden Iterationen der Teilrestberechnung ausgegeben werden.
Nach der Berechnung des nächsten Teilrests in redundanter Form, die aus einer Vielzahl von Summen und Überträgen besteht, durch eines Vielfachen von D von 4Pj, gibt der Übertragspeicheraddierer 120 die fünf höchstwertigen Summenbits und die fünf höchstwertigen Übertragbits an die Quotientenvorhersageeinrichtung 112 zur Verwendung in einer nächsten iterativen Berechnung einer nächsten iterativen Vorhersage eines vorzeichenbehafteten Quotientenbits durch die Quotientenvorhersageeinrichtung 112 aus.
Das sechst-höchstwertige Summen- bzw. Übertragsbit dienen der. Korrektur zweideutiger Quotientenbits der Quotientenvorhersageeinrichtung 112. Zur weiteren Erläuterung dieses Aspekts der Erfindung wird erneut auf Fig. 3 verwiesen. In zwei Bereichen des PD-Diagramms der Fig. 3 sind zwei kleine schraffierte Bereiche dargestellt. Diese beiden schraffierten Bereiche repräsentieren den Fehler, der durch Verwendung des Übertragspeicheraddierers 120 entsteht, wodurch es unmöglich wird, einen Quotienten innerhalb des theoretischen Fehlerlimits bei Verwendung einer 5-Bit-Teilrestschätzung vorherzusagen. Es ist jedoch sehr kostspielig, zum Schätzwert des Teilrests ein sechstes Bit hinzuzufügen. Unter Verwendung des NOR des sechsten Übertrags- und des sechsten Summenbits zum Schätzen des Fehlers im 5-Bit-Schätzwert, kann jedoch erfolgreich ein Quotient innerhalb theoretischer Grenzen geraten werden. Wenn das NOR des sechsten Summen- und des sechsten Übertragsbits eins ist, wird jeder Übertrag im sechsten Bit gelöscht, so daß der Unterschied zwischen dem Teilrestschätzwert, der aus dem Addieren der oberen fünf Bits der Summen zu den oberen 5 Bits der Überträge abgeleitet ist, und dem tatsächlichen Teilrest nicht größer als 2&supmin;&sup6; sein kann; somit kann der höhere der möglichen Quotientenvorhersagen sicher verwendet werden. Wenn im Gegensatz dazu das NOR des sechsten Summen- und des sechsten Übertragsbits Null ist, muß die Differenz zwischen dem Teilrestschätzwert und dem tatsächlichen Teilrest größer als 2&supmin;&sup7; sein; somit kann der niedrigere der möglichen vorhergesagten Quotienten verwendet werden, ohne Sorge, genau auf der Untergrenze des Bereichs anzukommen, wodurch man möglicherweise in Dreierwiederholungen gelangt.
Der Dividierer 100 fährt mit der iterativen Erzeugung eines nächsten vorzeichenbehafteten Quotientenbits zur Speicherung im Quotientenregister 114 fort, wie zuvor beschrieben, gefolgt von einer iterativen Bestimmung eines nächsten Teilrests im Übertragspeicheraddierer 120 bis der gesamte Quotient Q erzeugt ist. Bei einer Einfach-Präzisionszahl erfordert die Berechnung des Quotienten Q 14 zusätzliche Iterationen des rekursiven Algorithmus, wobei jede Iteration des Algorithmus in einer Phase eine Taktzyklus abgeschlossen wird. Bei einer Doppel-Präzisionszahl erfolgt die Berechnung des Quotienten in 28 zusätzlichen Iterationen des Algorithmus. Die Divisionsoperation ist abgeschlossen, wenn das Quotientenregister 114 voll ist.
Beim Eintritt in die "Post-Overhead"-Stufe der Divisionsoperation wird der in dem Teilrestregister 106 gespeicherte Teilrest nach Abschluß der vierzehnten Iteration des rekursiven Algorithmus, wenn eine Einfach-Präzisionsdivision durchgeführt wird, oder nach Abschluß der achtundzwanzigsten Iteration, wenn eine Doppel-Präzisionsdurchgeführt wird, an eine Nullerkennungseinrichtung 122, beispielsweise einen ersten Addierer von konventioneller Ausbildung, und eine Restvorzeichenerkennungseinrichtung 123, beispielsweise einen zweiten herkömmlich ausgebildeten Addierer, zum parallelen Bestimmen dieser Operationen ausgegeben. Die Restvorzeichenerkennungsoperation dient der Feststellung, ob der im Quotientenregister 114a gespeicherte Quotient um eins abweicht. Die Nullerkennungsoperation dient der Feststellung, ob die abge schlossene Division genau ist. Die Nullerkennungseinrichtung 122 und die Restvorzeichenerkennungseinrichtung 123 empfangen die verbleibenden Summen und Überträge, die von dem Teilrestregister 106 ausgegeben werden. Der Ausgangshaltespeicher 126 empfängt den Quotienten vom Quotientenregister 114, fügt das Null- oder "klebrige" Bit aus der Nullerkennungseinrichtung 122 an den vom Quotientenregister 114a empfangenen Quotienten, um den Quotienten mit einem Extrabit zum korrekten Runden in der Rundungseinheit des Gleitkommaprozessors zu versehen. Nahezu gleichzeitig mit der Nullbestimmung prüft die Restvorzeichenerkennungseinrichtung 123 das Vorzeichen der Addition der Summen und Überträge, die vom Teilrestregister 106 ausgegeben werden. Wenn das Vorzeichen der Addition der Summen und Überträge negativ ist, gibt die Restvorzeichenerkennungseinrichtung 123 ein Signal an den Ausgangshaltespeicher 126 aus, das angibt, daß der Quotient zu groß ist und das Q- 1-Register 114b verwendet werden soll. Der Ausgangshaltespeicher 126 verwendet sodann den Quotienten minus eins aus dem Quotientenregister 114b, fügt das Null- oder "klebrige" Bit aus der Nullerkennungseinrichtung 122 an den vom Quotientenregister 114a empfangenen Quotienten minus eins, um den Quotienten mit einem Extrabit zum korrekten Runden in der Rundungseinheit des Gleitkommaprozessors zu versehen.
Schließlich wird beim Berechnen des Mantissenbereichs des Quotienten entsprechend dem vorgenannten iterativen Verfahren der Exponentenbereich des Quotienten durch eine Exponentenberechnungseinrichtung 124 berechnet. Genauer gesagt ist die Exponentenberechnungseinheit zum Empfangen des Dividenden A über den A-Bus und des Divisors B über den B-Bus verbunden. Beim Empfang eines Steuersignals der Dividierersteuerung 110 subtrahiert die Exponentenberechnungseinrichtung 124 den Divisorexponenten von dem Dividendenexponenten und gibt das Ergebnis an den Ausgangshaltespeicher 126 aus. Sobald der Ausgangshaltespeicher 126 den Mantissenquotienten vom Quotientenregister 114 und der Exponentenberechnungseinrichtung 124 empfangen hat, wird das Ergebnis der Divisionsoperation an die Gleitkommaprozessoreinheit über den RESULT-Bus ausgegeben.
In Zusammenhang mit Fig. 4 wird im folgenden ein raumsparender Hochgeschwindigkeitsdividierer 300 zum Durchführen keinen positiven Rest bildender iterativer Divisionsoperationen mit der Radix 4 beschrieben. Der hier beschriebene raumsparende Hochgeschwindigkeitsdividierer ist in Konstruktion und Betrieb mit dem in Fig. 1 dargestellten Hochgeschwindigkeitsdividierer identisch, mit Ausnahme der nachfolgend genannten Merkmale. Der raumsparende Dividierer 300 weist wie der Dividierer 100 auf eine erste Quotientenvorhersageeinrichtung 302, einen Addierer 304, ein Teilrestregister 306, ein Schieberegister 307, ein Divisorregister 308, ein Schieberegister 309, eine Dividierersteuerung 310, eine Quotientenvorhersageeinrichtung 312, ein Quotientenregister 114, ein 3X-Divisorregister 316, einen Divisormultiplexer 318, einen Übertragspeicheraddierer 320, eine Exponentenberechnungseinrichtung 324 und ein Ausgangshaltespeicher 326, die in Verbindung und Betrieb mit denjenigen Komponenten des Dividierers 100 identisch sind. Im wesentlichen unterscheidet sich der raumsparende Hochgeschwindigkeitsdividierer 300 vom Hochgeschwindigkeitsdividierer 100 dadurch, daß das Schieberegister 103, die Nullerkennungseinrichtung 122 und die Resterkennungseinrichtung 123 entfallen. Bei diesem Ausführungsbeispiel jedoch, wird die zuvor von der Nullerkennungseinrichtung 122 durchgeführte Vorzeichen- und Nullerkennungsoperation vom Addierer 304 durchgeführt, der bei dem vorhergehenden Ausführungsbeispiel nur zum Kombinieren von D und 2D diente. Um den Addierer 304 in die Lage zu versetzen, mehrere Funktionen durchzuführen, ist ein Multiplexer 328 zum Steuern der Eingänge in den Addierer 304 vorgesehen.
Die Eingänge des Multiplexers 328 sind zum Empfangen des Operanden A über den A-Bus, des Operanden B über den B-Bus, einer Reihe von Summen über einen dritten Ausgang des Teilrestregisters 306 und einer Reihe von Überträgen über einen vierten Ausgang des Teilrestregisters 306 verbunden. Ein fünfter Eingang des Multiplexers 328 wird im folgenden näher beschrieben. Während der Bestimmung des Dreifachen des Divisors nimmt der Multiplexer 328 nach Empfang eines Steuersignals von der Dividierersteuerung 310 den empfangenen Divisor B, verschiebt den empfangenen Divisor B um eine einzelne Dezimalstelle, um das Doppelte des Divisors zu erzeugen und gibt den Divisor und das Doppelte des Divisors an den ersten und den zweiten Eingang des Addierers 304 aus. Nach Empfang des Divisors und des Doppelten des Divisors durch den Addierer 304 arbeitet der raumsparende Hochgeschwindigkeitsdividierer 300 wie zuvor in Zusammenhang mit Fig. 1 beschrieben, bis die letzte iterative Bestimmung des Teilrests in dem Teilrestregister 306 gespeichert ist und der raumsparende Hochgeschwindigkeitsdividierer 300 in die Post-Overhead-Stufe eintritt.
In der Post-Overhead-Stufe werden die verbleibenden Summen und Überträge an den Multiplexer 328 über den dritten und den vierten Ausgang des Teilrestregisters 306 geliefert. Zu diesem Zeitpunkt erzeugt die Dividierersteuerung 310 ein Steuersignal an den Multiplexer 328, so daß die Summen und die Überträge an den Addierer 304 über den ersten und den zweiten Addierereingang geliefert werden. Der Addierer 304 addiert die Summen und Überträge, die von dem Multiplexer 306 ausgegeben wurden, und gibt das Ergebnis der Addition an den Ausgangshaltespeicher 326. Anschließend gibt der Addierer 304 ein Signal, das ein positives oder negatives Vorzeichen angibt, über die Vorzeichenleitung an den Ausgangshaltespeicher 326 aus. Wenn die Addition der Summen und Überträge ein positives Vorzeichen des Rests zeigt, verwendet der Ausgangshaltespeicher 326 den Quotienten aus dem Quotientenregister 314a. Wenn jedoch die Addition der Summen und Überträge ein negatives Restvorzeichen angibt, verwendet der Ausgangshaltespeicher 326 den Inhalt des Registers Q-1. Der Ausgang des Addierers 304 wird ebenfalls dem fünften Eingang des Multiplexers 328 zugeleitet. Der Multiplexer 328 leitet sodann die Umkehrung des Addiererausgangssignals zurück in den Addierer 304 und addiert über die Übertrageingangsleitung 330 eins, um das Vorzeichen der ausgegebenen Summe zu bestimmen. Wie zuvor erläutert dient die Nullerkennung dem Setzen eines zusätzlichen Ergebnisbits im Ausgangshaltespeicher 326.
Unter Bezugnahme auf Fig. 5 wird ein raumsparender Hochgeschwindigkeitsdividierer zum Durchführen einer keinen positiven Rest bildenden iterativen Division mit der Radix 4 und einer Quadratwurzelberechnung mit der Radix 2 beschrieben. Der hier beschriebene Dividierer ist in Aufbau und Betriebsweise dem in Fig. 4 dargestellten Hochgeschwindigkeitsdividierer ähnlich, mit Ausnahme der folgenden Unterschiede. Der Dividierer 500 zum Durchführen von Divisionen und Quadratwurzelberechnungen weist auf eine erste Quotientenvorhersageeinrichtung 502, einen Addierer 504, ein erstes Teilrestregister 506, ein Schieberegister 507, ein Divisorregister 508, ein Schieberegister 509, eine Dividierersteuerung 510, eine Quotientenvorhersageeinrichtung 512, ein Quotientenregister 514, das aus einem Quotientenregister Q 514a und einem Quotientenregister Q-1 514b besteht, ein 3X Divisorregister 516, einen Divisormultiplexer 518, einen Übertragspeicheraddierer 520, eine Exponentenberechnungs einrichtung 524, einen Ausgangshaltespeicher 526 und einen Multiplexer 528, die nach ihrer Verbindung und in ihrer Betriebsweise mit den entsprechenden Komponenten des raumsparenden Hochgeschwindigkeitsdividierers 300 nach Fig. 4 identisch sind. Im folgenden wird die Modifizierung des Hochgeschwindigkeitsdividierers 500 für die Durchführung von Quadratwurzeloperationen mit der Radix 2, bei der Wurzelbits aus der Gruppe -1, 0 und +1 gewählt werden können, und für die Durchführung von Divisionsoperationen mit der Radix 4.
Anders als eine Divisionsoperation beinhaltet eine Quadratwurzeloperation die Eingabe eines einzelnen Operanden oder "Radikanden" und die Ausgabe eines Einzelergebnis, das die Quadratwurzel des eingegebenen Radikanden ist. Der eingegebene Radikand für den die Quadratwurzeloperation durchgeführt werden soll, wird in den Multiplexer 528 entweder über den A- oder den B-Bus eingegeben. Sobald die Dividierersteuerung 510 angibt; daß eine Quadratwurzeloperation mit dem Eingangssignal des A- oder B-Busses durchgeführt werden soll, wird der Radikand P um eine Dezimalstelle verschoben, um das Doppelte des Radikanden P zu erzeugen, und das Doppelte des Radikanden P wird über den Addierer 504 an die Quadratwurzelvorhersageeinrichtung 530 ausgegeben, die wie die erste Quotientenvorhersageeinrichtung 502 und die Quotientenvorhersageeinrichtung 512 eine Konfiguration herkömmlicher kombinatorischer Logikschaltungen ist, derart, daß, je nach dem Eingang 2P an die Quadratwurzelvorhersageeinrichtung 530, eine Vorhersage eines Quadratwurzelbits Q bestimmt werden soll.
Fig. 6 ist eine graphische Darstellung der Quadratwurzelvorhersageeinrichtung 530. Das Vorhersageeinrichtungsdiagramm sieht für einen bestimmten Eingangswert 2Pj eine entsprechende Vorhersage des Werts des Quadratwurzelquo tientenbits qj vor. Während jeder Iteration bestimmt die Quadratwurzelvorhersageeinrichtung 530 ein Bit der Quadratwurzel und gibt das vorhergesagte Bit an das Q- und das Q-1-Register 514a, 514b entsprechend der zuvor beschriebenen Verfahrensweise aus. Die Quadratwurzelvorhersageeinrichtung 530 gibt ferner das vorhergesagte Quadratwurzelbit and den Multiplexer 528 zur Verwendung in der nächsten Iteration weiter. Iterationen werden wiederholt, bis das Quotientenregister mit einer Reihe von vorhergesagten Bits gefüllt ist, und der Dividierer 500 arbeitet wie in Zusammenhang mit Fig. 4 zuvor beschrieben. Wie in Fig. 7 gezeigt, sind bestimmte Veränderungen des in Fig. 1b dargestellen Quotientenregisters 114 erforderlich, um eine Radix 2 Quadratwurzelberechnung zu ermöglichen, die das Schreiben eines Bits in das Q-Register 114a und das Q-1-Register 114b pro Iteration erfordert. In einer Iteration-pro-Phase- Logik liefern Signale von einem bestimmten Haltespeicher Daten an einen Logikblock, der in derselben Phase seinerseits ein Ergebnis an denselben Haltespeicher liefert. Dies würde einen Wettlauf durch herkömmliche Haltespeicher bewirken, bei dem das Ergebnis den Haltespeicher durchläuft und die Logikeingänge verändern würde, so daß ein nicht vorhersagbares Ergebnis erzielt würde. Um das Durchlaufen zu verhindern und eine synchrone Operation zu ermöglichen, wurden sogenannte "Partner"-Haltespeicher entwickelt, wie sie in Fig. 7 dargestellt sind. Während einer Phase empfängt ein Partner Daten, während der andere Partner Daten überträgt. In jeder nachfolgenden Phase tauschen die Partner die Plätze. Um dynamische Logik verwenden zu können, mußten Schaltungen dupliziert werden, wobei ein Partner in Phase 1 vorlädt und in Phase 2 auswertet, während der andere Partner in Phase 2 vorlädt und in Phase 1 auswertet.
Wie aus der vorhergehenden Beschreibung der vorliegenden Erfindung hervorgeht, ist eine arithmetische Operationseinheit geschaffen, die iterative Divisions- und Quadratwurzeloperationen mit hoher Geschwindigkeit durchführt, während sie die erforderlichen Schaltungen für die Divisionsoperationen minimiert. Die Pre-Overhead-Zeitspanne wird durch Überlappen der Berechnung einer ersten Iteration und der Bestimmung des Dreifachen des Divisors reduziert. Ferner eliminiert die Verwendung eines Addierers zum Erzeugen der Summe des Divisors und des verschobenen Divisors (des Doppelten des Divisors) die Notwendigkeit eines großen Multiplizierers. Durch Verwendung einfacher Quotientenvorhersagelogik und eines Multiplexers, der sämtliche möglichen Produkte des Quotienten Qj und des Teilrests Pj an die Einrichtung zum iterativen Erzeugen des nächsten Teilrests liefert, wird ein Übertragspeicheraddierer zum Erzeugen des nächsten Teilrests Pj+1 verwendet, wodurch die Notwendigkeit entfällt, daß die Multiplikationslogik die Berechnung pj+1 = 4Pj + QD durchführen muß, und der Übertragspeicheraddierer schnell P berechnen kann, so daß der Dividierer eine Iteration der Berechnung von Qj und Pj pro Taktimpuls durchführen kann. Die Post-Overhead-Zeitspanne wird durch parallele Nullerkennung und Restvorzeichenerkennung verkürzt. Schließlich entfällt die Notwendigkeit zusätzlicher Addiererschaltungen zum Bestimmen des endgültigen Quotienten durch das Vorsehen von Q- und Q-1-Registern zum parallelen Speichern des Quotienten und des Quotienten minus 1, derart, daß, wenn festgestellt wird, daß der Quotient um eins versetzt ist, der korrekte Quotient im parallelen Quotientenregister gespeichert ist und nicht berechnet werden muß. Bei dem raumsparenden Hochgeschwindigkeitsdividierer wird das Ausgangssignal des Teilrestregisters am Ende der iterativen Bestimmung des Quotienten dem 3D Addierer zugeführt, um das Vorzeichen des Teilrests festzustellen und zu ermitteln, ob der Teilrest gleich Null ist. Auf diese Weise werden die Nullerkennungseinrichtung und die Restvorzeichenerkennungseinrichtung eliminiert und Platz wird gespart.
Dem Fachmann werden, außer den speziell genannten Techniken, zahlreiche Modifizierungen und Variationen der beschriebenen Technik ersichtlich sein, ohne dabei wesentlich vom Konzept der vorliegenden Erfindung abzuweichen. Es sei daher deutlich gesagt, daß die hier beschriebene Form der Erfindung nur Beispielcharakter hat und keine Einschränkung des Umfangs der Erfindung darstellt.

Claims

1. Vorrichtung (100; 300; 500) zum Durchführen der Division eines ersten Operanden durch einen zweiten Operanden zur Erzeugung eines aus einer Reihe von Quotientenwerten bestehenden Ergebnisses, mit:

- einer Einrichtung (118, 120; 318, 320; 518, 520) zum iterativen Erzeugen einer Reihe von Teilresten, wobei die Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten den ersten Operanden als einen ersten Teilrest wählt;

- einer Einrichtung (102, 112; 302, 312; 502, 512) zum iterativen Vorhersagen von Quotientenwerten, wobei die Quotientenvorhersageeinrichtung einen ersten Quotientenwert auf der Basis des ersten Operanden und des zweiten Operanden und einen nächsten Quotientenwert auf der Basis der Reihe von Teilresten und des zweiten Operanden vorhersagt; wobei die Quotientenvorhersageeinrichtung ferner aufweist:

eine erste Quotientenvorhersageschaltung (102; 302; 502), die zum Empfangen des ersten und des zweiten Operanden verbunden ist, wobei die erste Quotientenvorhersageschaltung den ersten Quotientenwert vorhersagt, wobei der erste Operand vor der Vorhersage des ersten Quotientenwerts wenigstens durch 4 geteilt wird; und

eine zweite Quotientenvorhersageschaltung (112; 312; 512), die zum Empfange des vorhergesagten ersten Quotientenwerts, des zweiten Operanden und der Reihe der Teilreste verbunden ist, wobei die zweite Quotientenvorhersageschaltung iterativ die Restwerte der Reihe von Quotientenwerten vorhersagt;

- einem ersten Quotientenregister (114a), das mit der Quotientenvorhersageeinrichtung verbunden ist, um die von der Quotientenvorhersageeinrichtung bestimmte Reihe von Quotientenwerten zu empfangen und zu speichern;

- einem zweiten Quotientenregister (114b), das mit der Quotientenvorhersageeinrichtung verbunden ist um die Reihe von Quotientenwerten zu empfangen und die Reihe von Quotientenwerten minus eins zu speichern;

- einer Einrichtung (103, 104, 108, 116, 118; 328; 304, 308, 316, 318; 528, 504, 508, 516, 518) zum Erzeugen von Vielfachen des zweiten Operanden;

wobei die Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten einen nächsten Teilrest auf der Basis eines Teilrests aus der Reihe erzeugter Teilreste und einem der Vielfachen des zweiten Operanden bestimmt;

wobei die Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten ferner eine Einrichtung (120; 320; 520) aufweist, die auf der Basis des nächsten Quotientenwerts eines der erzeugten Vielfachen des zweiten Operanden zur Erzeugung des nächsten Teilrests wählt.

2. Vorrichtung nach Anspruch 1, bei der die Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten des ersten Operanden den nächsten Teilrest nach der folgenden Gleichung bestimmt:

PJ+1 = 4PJ + qjD

wobei

PJ = erster Teilrest;

PJ+1 = nächster Teilrest;

qj = vorhergesagter erster Quotient; und

D = zweiter Operand.

3. Vorrichtung nach Anspruch 2, bei der die Einrichtung (103, 104, 108, 116, 118; 328, 304, 308, 316, 318; 528, 504, 508, 516, 518) zum Erzeugen von Vielfachen des zweiten Operanden ferner eine Einrichtung zum Erzeugen des ±0-, ±1-, ±2- und ±3-Fachen des zweiten Operanden aufweist.

4. Vorrichtung nach Anspruch 3, bei der die Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten des ersten Operanden ferner eine Multiplexereinrichtung (118; 318; 518) zum Auswählen eines der erzeugten Vielfachen des zweiten Operanden zum Erzeugen des nächsten Teilrests aufweist, wobei das gewählte Vielfache des zweiten Operanden zu dem Produkt aus dem zweiten Operanden und dem vorhergesagten Quotienten äquivalent ist.

5. Vorrichtung nach Anspruch 4, bei der die Einrichtung zum Erzeugen von Vielfachen des zweiten Operanden ferner aufweist:

eine Einrichtung (103) zum Verschieben des zweiten Operanden, um das Doppelte des zweiten Operanden zu erzeugen; und

einen Addierer (104) zum Addieren des zweiten Operanden und des erzeugten Doppelten des zweiten Operanden, um das Dreifache des zweiten Operanden während der Berechnung der ersten Iteration von PJ+1 zu erzeugen.

6. Vorrichtung nach Anspruch 1, bei der die Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten des ersten Operanden die Reihe von Teilresten als eine Gruppe von Summen und Überträgen erzeugt.

7. Vorrichtung nach Anspruch 6, ferner mit einer Einrichtung (122, 123) zum Feststellen, daß das Ergebnis erzeugt wurde.

8. Vorrichtung nach Anspruch 7, bei der die Einrichtung (122; 123) zum Feststellen, daß das Ergebnis erzeugt wurde, ferner aufweist:

eine Einrichtung (123) zum Feststellen des Vorzeichens des ersten Teilrests; und

eine Einrichtung zum Anpassen des Ergebnisses auf der Basis des Vorzeichens des ersten Teilrests.

9. Vorrichtung nach Anspruch 8, bei der die Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten des ersten Operanden den nächsten Teilrest nach der folgenden Gleichung bestimmt:

PJ+1 = 4PJ + QD

wobei

PJ = erster Teilrest;

PJ+1 = nächster Teilrest;

Q = vorhergesagter erster Quotient; und

D = zweiter Operand.

10. Vorrichtung nach Anspruch 9, bei der die Einrichtung zum Erzeugen von Vielfachen des zweiten Operanden ferner eine Einrichtung zum Erzeugen des ±0-, ±1-, ±2- und ±3-Fachen des zweiten Operanden aufweist.

11. Vorrichtung nach Anspruch 10, bei der die Einrichtung zum iterativen Erzeugen einer Reihe von Teilresten ferner eine Multiplexereinrichtung (118; 318; 518) zum Auswählen eines der erzeugten Vielfachen des zweiten Operanden zum Erzeugen des nächsten Teilrests aufweist, wobei das gewählte Vielfache des Operanden zu dem Produkt aus dem zweiten Operanden und dem vorhergesagten Quotienten äquivalent ist.

12. Vorrichtung nach Anspruch 11, bei der die Einrichtung zum Erzeugen von Vielfachen des zweiten Operanden ferner aufweist:

13. Vorrichtung nach Anspruch 1, ferner mit:

einer Einrichtung zum Schreiben des Inhalts des ersten Quotientenregisters (114a) in das zweite Quotientenregister; und

einer Einrichtung zum Schreiben des Inhalts des zweiten Quotientenregisters (114b) in das erste Quotientenregister.

14. Vorrichtung nach Anspruch 1, ferner mit:

einem Teilrestregister (106; 306; 506), das zum Empfangen und Speichern des ersten Operanden als ersten Teilrest verbunden ist;

einem Divisorregister (108; 308; 508), das zum Empfangen und Speichern des zweiten Operanden verbunden ist;

wobei die Einrichtung (103, 104, 108, 116, 118; 328, 304, 308, 316, 318; 528, 504, 508, 516, 518) zum Erzeugen von Vielfachen des zweiten Operanden mit einem Übertragspeicheraddierer (120; 320; 520) verbunden ist, und wobei:

der Übertragspeicheraddierer (120; 320; 520) zum Empfangen der Vielfachen des zweiten Operanden von der Einrichtung zum Erzeugen von Vielfachen des zweiten Operanden und des vorhergesagten Quotientenwertes von der Quotientenvorhersageeinrichtung verbunden ist, wobei der Übertragssicherungsaddierer einen nächsten Teilrest durch Auswahl eines der Vielfachen des zweiten Operanden und durch Addieren desselben zu einem Vierfachen des ersten Teilrests bestimmt, wobei das Teilrestregister (106; 306; 506) zum Empfangen und Speichern des nächsten Teilrests anstelle des ersten Teilrests verbunden ist, und wobei die Quotientenvorhersageeinrichtung zum Empfangen des nächsten Teilrests verbunden ist, um einen nächsten Quotientenwert zu bestimmen.

15. Vorrichtung nach Anspruch 14, bei der der Übertragspeicheraddierer (120; 320; 520) den nächsten Teilrest als Gruppe von Summen und Überträgen erzeugt, und die Vorrichtung ferner einen ersten Addierer (122) aufweist, der zum Empfangen des nächsten Teilrests von dem Teilrestregister verbunden ist, wobei der Addierer die Summen und Überträge addiert, um zu bestimmen, ob das Ergebnis erzeugt wurde.

16. Vorrichtung nach Anspruch 15, ferner mit einem zweiten Addierer (123), der zum Empfangen des nächsten Teilrests von dem Teilrestregister verbunden ist, wobei das Ausgangssignal des zweiten Addierers zum Bestimmen des Vorzeichens der Summen und Überträge verwendet wird.

17. Vorrichtung nach Anspruch 16, bei der die zweite Quotientenvorhersageschaltung für jeden bestimmten Quotientenwert den Quotientenwert minus eins bestimmt, und das zweite Quotientenregister (114b) zum Empfangen und Speichern der von der Quotientenvorhersageschaltung bestimmen Quotientenwerte minus eins verbunden ist.

18. Vorrichtung nach Anspruch 17, ferner mit:

einer Einrichtung (123) zum Bestimmen, ob der in dem ersten Quotientenregister (114a) gespeicherte Quotientenwert inkorrekt ist; und

eine Einrichtung zum Ersetzen des in dem ersten Quotientenregister (114a) gespeicherten Quotienten durch den in dem zweiten Quotientenregister (114b) gespeicherten Quotienten minus eins.

19. Vorrichtung nach Anspruch 18, ferner mit einem Ausgangshaltespeicher (126; 326; 526), der zum Empfangen des Quotienten vom ersten Quotientenregister (114a) verbunden ist.

20. Vorrichtung nach Anspruch 19, bei der der erste Operand, der zweite Operand und das Ergebnis jeweils aus einem Mantissenteil und einem Exponententeil bestehen, wobei der Quotient durch Dividieren der Mantissen des ersten Operanden und des zweiten Operanden gebildet wird, und die Vorrichtung ferner eine Exponentenberechnungseinrichtung (124; 324; 524) aufweist, die zum Empfangen der Exponenten des ersten Operanden und des zweiten Operanden verbunden ist, wobei die Exponentenberechnungseinrichtung den Exponenten des zweiten Operanden von dem Exponenten des ersten Operanden subtrahiert, um den Ergebnisexponenten zu berechnen, wobei der Ausgangshaltespeicher ferner zum Empfangen des Ergebnisexponenten von der Exponentenberechnungseinrichtung verbunden ist.

21. Vorrichtung nach Anspruch 16, ferner mit:

einer ersten Schiebeeinrichtung (103), die zum Empfangen des zweiten Operanden zum Erzeugen des Doppelten des zweiten Operanden verbunden ist;

einem dritten Addierer (104), der zum Empfangen des Doppelten des zweiten Operanden von der ersten Schiebeeinrichtung und des zweiten Operanden verbunden ist; und

einem zweiten Divisorregister (116), das zum Empfangen und Speichern des Dreifachen des Divisors von dem zweiten Addierer verbunden ist.

22. Vorrichtung nach Anspruch 21, ferner mit einem ersten Multiplexer (118; 318; 518), der zum Empfangen des zweiten Operanden von dem Divisorregister (108; 308; 508) und des Dreifachen des zweiten Operanden vom zweiten Divisorregister (116; 316; 516) und zum Ausgeben des ±0-, ±1-, ±2- und ±3- fachen des zweiten Operanden an den Übertragspeicheraddierer (120; 320; 520) verbunden ist.

23. Vorrichtung nach Anspruch 22, bei der der Übertragspeicheraddierer (120; 320; 520) einen nächsten Teilrest nach der folgenden Gleichung bestimmt:

PJ+1 = 4PJ + qjD

wobei

PJ+1 = nächster Teilrest;

PJ = erster Teilrest;

qj= vorhergesagter erster Quotient; und

D = zweiter Operand.

24. Vorrichtung nach Anspruch 23, bei der der Übertragspeicheraddierer (120; 320; 520) ferner aufweist:

eine zweite Schiebeeinrichtung zum zweifachen Schieben des ersten Teilrests zur Erzeugung des Vierfachen des Teilrests; und

eine Einrichtung zum Wählen eines der Eingangssignale des Multiplexer auf der Basis der Vorhersage des ersten Quotienten.

25. Vorrichtung nach Anspruch 24, bei der Übertragspeicheraddierer (120; 320; 520) den nächsten Teilrest durch Addieren des zweifach verschobenen ersten Teilrests erzeugt, um das Vierfache des ersten Teilrests und des Multiplexereingangssignals zu erzeugen, das gleich dem Produkt des zweiten Operanden und der Vorhersage des ersten Quotienten ist.

26. Vorrichtung nach Anspruch 14, ferner mit:

einem ersten Multiplexer, der zum Empfangen des zweiten Operanden verbunden ist, wobei der Multiplexer eine Schiebeeinrichtung (103) zum Erzeugen des Doppelten des zweiten Operanden aus dem Divisorregister aufweist; und

einem ersten Addierer (104), der zum Empfangen des Doppelten des zweiten Operanden von der Multiplexereinrichtung und des zweiten Operanden verbunden ist.

27. Vorrichtung nach Anspruch 26, ferner mit einem zweiten Divisorregister (116; 316; 516), das zum Empfangen und Speichern des Dreifachen des zweiten Operanden vom ersten Addierer verbunden ist.

28. Vorrichtung nach Anspruch 26, bei der der erste Multiplexer ferner zum Empfangen einer Gruppe von Summen und Überträgen von dem Teilrestregister (106; 306; 506) verbunden ist, wobei der Multiplexer derart konfiguriert ist, daß er wahlweise entweder den zweitem Operanden an den ersten Addierer zum Bestimmen des Dreifachen des zweiten Operanden oder die Gruppe von Summen und Überträgen an den ersten Addierer zum Bestimmen des Teilrestvorzeichens und einer Endteilrest-Null-Erkennung ausgibt;

wobei die Vorrichtung ferner eine Einrichtung zum Bereitstellen eines Rückführpfades für die Addition der vom ersten Addierer ausgegebenen Summen und Überträge zurück zum ersten Addierer aufweist, um das Vorzeichen des ersten Teilrests zu bestimmen.

29. Vorrichtung nach Anspruch 28, ferner mit einem Ausgangshaltespeicher (126; 326; 526), der zum Empfangen des Quotienten vom Quotientenregister (114; 314; 514) verbunden ist, wobei der Ausgangshaltespeicher ferner zum Empfangen von Signalen vom ersten Addierer verbunden ist, welche anzeigen, ob der letzte Teilrest null ist.

30. Vorrichtung nach Anspruch 29, ferner mit einer Einrichtung zum Liefern des ermittelten Vorzeichens des letzten Teilrests an den Ausgangshaltespeicher (126; 326; 526).

31. Vorrichtung nach Anspruch 30, bei der die Quotientenregisterschaltung ferner für jeden ermittelten Quotientenwert den Quotientenwert minus eins bestimmt, wobei das zweite Quotientenregister (114b) zum Empfangen und Speichern des von der Quotientenregisterschaltung bestimmten Quotientenwertes minus eins verbunden ist.

32. Vorrichtung nach Anspruch 31, ferner mit:

einer Quadratwurzelvorhersagelogik (530), die zum Empfangen eines Radikanden vom Addierer (504) verbunden ist, wobei die Quadratwurzelvorhersagelogik einen vorhergesagten Wurzelwert auf der Basis des Radikanden bestimmt;

einer Einrichtung zum Liefern des vorhergesagten Wurzelwerts an das erste Quotientenregister (514a) und den ersten Multiplexer (528);

wobei der Multiplexer (528) iterativ das Doppelte des vorhergesagten Wurzelwertes an die Quadratwurzelvorhersagelogik zur Bestimmung eines nächsten vorhergesagten Wurzelwerts liefert.