DE69430838T2 - Schaltung und Verfahren zur parallelen Verschiebung und Addition - Google Patents

Description

• Die Erfindung bezieht sich auf Computer, insbesondere arithmetische Einheiten zur Nutzung hierin
• Computer umfassen normalerweise eine arithmetische Logikeinheit (ALU - "arithmetic)logic unit"), die einen Addierer aufweist, welcher Zahlen einiger maximaler Bitanzahlen addiert. Addierer für Wörter der Länge 32 oder 64 Bit sind in Mikroprozessoren oder dergleichen üblich. Diese Addierer arbeiten auch für viel kleinere Wörter. Wenn sie dies tun, ist die Mehrzahl der von dem Addierer umfaßten Logikschaltungen unbelegt. Beispielsweise kann ein 64 Bit-Addierer genutzt werden, um zwei 8 Bit-Wörter mit Hilfe des Anordnens jedes 8 Bit- Worts in dem niederwärtigsten Teil eines entsprechenden 64 Bit-Worts und des anschließenden Addierens der 64 Bit-Wörter zu addieren. Während der Addition ist die Logikschaltung, welche sich mit dem Addieren der sieben höherwertigen Bits jedes Worts beschäftigt, effektiv unbelegt. Folglich wird ein 7-/8-tel der Kapazität des Addierers während dieser Operation nicht genutzt.
• Berechnungen, die Operationen mit einer großen Anzahl kleiner Wörter einschließen, treten häufig bei Multimedia-Datenverarbeitung auf. Bilder werden normalerweise als Anordnungen von Bildpunkten bzw. Pixeln repräsentiert, in welchen jeder Bildpunkt durch ein Wort repräsentiert ist, welches wesentlich kleiner als eine maximale Wortgröße der arithmetischen Logikeinheit ist. Ein Grauskalen-Bild wird typischerweise durch eine Anordnung eines Bytes ganzer Zahlen repräsentiert, die die Lichtintensität in entsprechenden Bereichen des Bildes repräsentieren. In ähnlicher Weise werden Tonaufzeichnungen typischerweise durch Anordnungen von 1 oder 2 Byte ganzer Zahlen repräsentiert, die die Intensität der Tonaufzeichnung als eine Funktion der Zeit repräsentieren. Folglich nutzt die Multimedia-Datenverarbeitung typischerweise die Rechenkapazität der arithmetischen Logikeinheit, welche in dem typischen Allzweckcomputer integriert ist, nicht vollständig.
• Zusätzlich zu der nicht vollständigen Nutzung der Kapazität der ALU führt diese Art von Datenverarbeitung zu weiteren Ineffizienzen, die sich aus der Notwendigkeit ergeben, die Daten vor ihrem Verarbeiten in der ALU zu verdichten und zu entpacken. Beispielsweise sind die Bildpunkte des Bildes typischerweise in Wörter verdichtet, weil Speicherraum stets sehr gefragt ist. Wenn die Basiswortgröße in dem Computer 32 Bit beträgt, können vier der Bildpunkte eines Grauskalen-Bildes pro Wort gepackt werden. Es sei eine Operation betrachtet, die für jeden Bildpunkt in dem Bild ausgeführt werden muß. Zusätzlich zu der Zeit, die zum Ausführen der Operation benötigt wird, muß das Programm auch die Bildpunktinformation vor jeder Berechnung entpacken und das Ergebnis packen. Diese Verdichtungs- und Entpack- Operationen vermindern die Betriebseffizienz weiter.
• Die in Multimedia-Operationen angetroffene Berechnungszeit kann sehr groß sein. Folglich werden oft spezielle Parallelcomputer-Architekturen angewendet, um die Zeit zwischen der Ausführung des Summenbild-Befehls und der Zeit zu vermindern, zu der das Summenbild beendet ist. Multimedia-Verarbeitungsoperationen, die für einen Bildpunkt oder eine Tonprobe ausgeführt werden, sind oft unabhängig von den für andere Bildpunkte oder andere Tonproben ausgeführten Operationen. Folglich können die Operationen parallel ohne Rücksicht auf die Reihenfolge ausgeführt werden. Ein Computer mit M Addierern kann im Prinzip ein Ergebnis in der Zeit 1/M liefern, wenn die Bewegung der Bildpunkte zwischen dem Speicher und den Addierern nicht limitierend wird. Folglich wäre es vorteilhaft, eine Computer- Architektur zu haben, in welcher mehrere Additionen parallel ausgeführt werden können. Leider verhindern die Kosten für das Bereitstellen dieser zusätzlichen ALU's und der zum Steuern benötigten Hardware dieses oft.
• Eine Klasse von Berechnungen, die oft über eine große Datenfolge ausgeführt wird, ist die Multiplikation mit einem Binärbruch. Eine solche Berechnung ist bei Filteroperationen und bei Datenkompressions- und Datendekompressionsoperationen üblich. In diesen Fällen wird mit einer Konstante multipliziert.
• John R. Mick, "A powerful new achitecture for a 32-bit bit-slice microprocessor" in WESCON 86/Konferenz-Band, Vol. 30, No. 27/3, S. 1-5, offenbart eine arithmetische Einheit zum Erzeugen der Summe eines ersten Worts dividiert durch 2m und eines zweiten Worts, das heißt eine bekannte "Addier- und Verschieber"-Einheit, welche mehrere Additionen jedoch nicht parallel ausführen kann.
• JP-A-59-43442 offenbart eine arithmetische Einheit zum Implementieren einer "Addier- und Verschiebe"-Operation, wobei die verschobenen Bits über eine Multiplexerschaltung an einen Addierer geliefert werden. Diese Referenz erlaubt ebenfalls nicht eine parallele Ausführung mehrerer Additionen.
• US-A-3,987,297 offenbart einen bekannten parallelen Digitaladdierer mit einstellbaren Grenzmechanismen zum Unterteilen des Addierers in mehrere unabhängige Betriebszonen. Diese Referenz beschreibt jedoch nicht das Teilen eines der Operanden durch 2m vor der Additionsoperation.
• Aufgabe der Erfindung ist es, eine verbesserte ALU anzugeben.
• Es ist weiterhin Aufgabe der Erfindung, eine ALU anzugeben, die mit hoher Effizienz arbeitet, wenn Mehrfachoperationen verarbeitet werden, die Wärter einschließen, welche kleiner als die Breite der ALU sind.
• Weiterhin ist es Aufgabe der Erfindung, eine ALU anzugeben, die für eine Berechnung mehrerer Multiplikationen angepaßt ist, welche einen binären Bruch einschließen.
• Die Erfindung gibt eine Vorrichtung mit den Merkmalen nach Anspruch 1 an.
• Diese und andere Aufgaben der Erfindung ergeben sich für den Fachmann aus der folgenden detailierten Beschreibung der Erfindung und der zugehörigen Zeichnung.
• Die Erfindung ist eine arithmetische Logikeinheit zum Betreiben auf den Inhalten eines X- Worts mit Bits Xi und eines Y-Worts mit Bits Yi zum Erzeugen eines Ergebnisworts mit Bits Zi , wobei i=0 bis N-1. Das X-Wort und das Y-Wort können in Unterwörter geteilt sein. 4 ist das niedrigstwertige Bit eines der Unterwörter. ZN-1 ist das höchstwertige Bit eines der Unterwörter. Die arithmetische Logikeinheit reagiert auf ein Maskenwort zum Partitionieren des X-, des Y- und des Ergebnisworts in mehrere Unterwörter, wobei jedem Unterwort des X- Worts ein Unterwort des Y-Worts und ein Unterwort des Ergebnisworts entspricht. Die Erfindung erzeugt die Summe jedes X-Unterworts dividiert durch 2m und des entsprechenden Y- Unterworts, um ein Ergebnis zu erzeugen, welches in dem entsprechenden Unterwort des Ergebnisworts gespeichert wird. m ist eine nichtnegative ganze Zahl.
• Eine Ausführungsform der Erfindung wird aus N-Einzelbitaddierern konstruiert, die in einer Rangfolgesequenz verbunden sind. Jede Einzelbit-Addiererstufe empfängt ein erstes Bitsignal von dem X-Wort und ein zweites Bitsignal von dem Y-Wort, wobei der i-te Einzelbitaddierer in der Sequenz mit dem Bit Yi in dem Y-Register verbunden ist. Jeder Einzelbitaddierer empfängt darüber hinaus ein Übertrageingangssignal. Jeder Einzelbitaddierer addiert das erste und das zweite Bitsignal und das Übertrageingangssignal zum Erzeugen eines Summensignals und eines Übertragausgangssignals, wobei das Summensignal mit Hilfe des Einzelbitaddierers erzeugt wird, welcher mit Yi verbunden ist, um das Bitsignal Zi zu liefern. Das Übertragsausgangssignal des Einzelbitaddierers, der mit Yi verbunden ist, wird auf den Übertrageingang in dem Einzelbitaddierer gegeben, der mit Yi+1 für i=0 bis N-1 verbunden ist. Die Logikeinheit umfaßt weiterhin N Multiplexer, wobei ein Multiplexer mit jeder Addiererstufe verbunden ist und auf ein Signal reagiert, welches m spezifiziert. Der mit der p-ten Addiererstufe verbundene Multiplexer verbindet diese Stufe mit Xp+m, wenn sich Xp, und Xp+m in demselben Unterwort des Y-Worts befinden. Die Verbindungen für die verbleibenden Bits werden dadurch bestimmt, ob jedes der X-Unterwörter eine vorzeichenbehaftete oder eine nicht vorzeichenbehaftete ganze Zahl repräsentiert oder nicht. Wenn die X-Unterwörter vorzeichenbehaftete ganze Zahlen repräsenterien, werden die verbleibenden Bits mit dem höchstwertigen Bit des betreffenden X-Unterworts verbunden. Wenn dieses nicht der Fall ist, werden die verbleibenden Bits auf "0" verbunden.
• Die Erfindung wird im folgenden anhand von Ausführungsbeispielen unter Bezugnahme auf eine Zeichnung näher erläutert. Hierbei zeigen:
• Fig. 1 die Art, in welcher eine erfindungsgemäße ALU in Beziehung zu den Inhalten von zwei Registern arbeitet;
• Fig. 2 ein Blockdiagramm eines Teils einer erfindungsgemäßen ALU, welche in zwei Unteroperanden aufgeteilt werden kann und auch eine Rechtsverschiebung um einen Platz in dem X-Operanden vor der Addition ausführen kann; und
• Fig. 3 ein Blockdiagramm einer Multiplexeranordnung, die ungerades Runden des niedrigstwertigen Bits eines Ergebnisses implementiert.
• Die Erfindung basiert auf zwei Beobachtungen. Erstens ist eine Multiplikation mit einer Konstante, die aus einem binären Bruch besteht, äquivalent zu mehreren Additionen, welche eine Rechtsverschiebung einschließen, die für einen der Summanden ausgeführt wird. Es sei das Produkt eines binären Bruchs f und einer Zahl r betrachtet. Wenn die Bits von f bi (i=0 bis B- 1) sind, kann das Produkt p wie folgt geschrieben werden:
• p = bi*r
• Dieses erlaubt eine Zerlegung des Produkts in mehrere Summierungen, die in der folgenden Form geschrieben werden können:
• x + x/2k (2)
• wobei k eine positive ganze Zahl und x eine ganze Zahl sind, die entweder r oder das Ergebnis einer früheren Operation in einer Zerlegung dieser Art ist. Beispielsweise kann das r-fache der binären Zahl 1.101 wie folgt geschrieben werden:
• P = r + r/2 + r/8
• Diese Operation kann in zwei Operationen ausgeführt werden, beispielsweise
• x = r + r/2
• und
• p = x + r/8
• Wenn der binäre Bruch eine Konstante ist, kann der Compiler die geeigneten Instruktionen zum Zerlegen der Multiplikation in die benötigten Operationen erzeugen. Jede dieser Operationen kann in einem Ausdruck als eine Summe von zwei Operanden geschrieben werden, wobei einer der Operanden der Inhalt eines um m Bits nach rechts verschobenen Registers ist. Folglich wäre es vorteilhaft, eine ALU zu haben, die eine Instruktion der Form "Verschieben nach rechts um m und Addieren" implementiert.
• Die zweite Beobachtung bezieht sich auf eine einfache Hardware-Modifikation, die es einem ansonsten herkömmlichen Addierer erlaubt, mehrere kleine Operanden in einem einzelnen Maschinenzyklus zu addieren. Im Prinzip kann der Addierer in mehrere Teile unterteilt werden, wobei jeder Teil für Wörter mit einer Größe arbeitet, die kleiner als die ganze Breite des Addierers ist. Die Summe der Bits in jedem Teil muß kleiner oder gleich der Breite des Addierers sein. In jedem Maschinenzyklus können mehrere Additionsoperationen für diese kleineren Wörter ausgeführt werden. Darüber hinaus kann der Addierer als ein herkömmlicher Addierer genutzt werden.
• Die bevorzugte Ausführungsform der Erfindung liefert einen Addierer, der in nur einige der möglichen Wortkombinationen unterteilt werden kann, obwohl Ausführungsformen der Erfindung möglich sind, bei denen die Breite der ALU in Wörter beliebiger Größe unterteilt ist. Beispielsweise wird ein 32 Bit-Addierer vorzugsweise in Teile unterteilt, die das Addieren von Wörtern erlauben, die 1 oder 2 Bits lang sind. Um die folgende Diskussion zu vereinfachen, wird angenommen, daß die ALU in der Hälfte unterteilt ist. In diesem Fall können pro Maschinenzyklus zwei Halbwortzusätze oder ein Gesamtwortzusatz ausgeführt werden.
• Gemäß Fig. 1 akzeptiert eine erfindungsgemäße ALU 10 zwei N Bitoperanden 12 und 14. Diese Bits des ersten Operanden werden mit Xi für i=0 bis N-1 bezeichnet, die Bits des zweiten Operanden werden mit Yi bezeichnet. Die Operanden werden typischerweise in zwei der Register der CPU des Computers gespeichert. Wenn die ALU 10 mit voller Breite betrieben wird, erzeugt sie ein m-Bit-Ausgang 16 mit der 2er-Komplementsumme von X, die um m Bits nach rechts verschoben ist, und Y. Die Bits des Ausgangs der ALU 10 werden in der folgenden Diskussion mit Zi bezeichnet. Das Ergebnis der Addition wird typischerweise in eines der Register der CPU zurückgespeichert.
• In der folgenden Diskussion werden die Bits in den verschiedenen Wörtern von den niedrigstwertigen zu den höchstwertigen beziffert. Das heißt, X&sub0; ist das niedrigstwertige Bit des Operanden IX und XNI ist das höchstwertige Bit des X-Operanden. Dieselbe Konvention wird für die X- und die Z-Wörter benutzt.
• Die Erfindung ermöglicht es, daß jeder Operand in mehrere Unterwörter unterteilt wird. Zur Vereinfachung wird die Erfindung zuerst in Verbindung mit einer Einzeldivision jedes Operanden in Teiloperanden erklärt. In diesem Fall sind die ersten q Bits des X-Operanden, X&sub0; bis Xq-1, die Bits des ersten Teiloperanden 18 des X-Worts. Die verbleibenden Bits Xq bis XN-1 sind die Bits des zweiten Teiloperanden 17 des X-Worts. Der Y-Operand ist in ähnlicher Weise in Teilwörter 19 und 20 unterteilt. In dieser Betriebsart sind die Bits Z&sub0; bis Zq die Bits der Summe des Teiloperanden 18 verschoben um m Bits und des Teiloperanden 20, und die Bits Zq bis ZN-1 sind die Bits der Summe des Teiloperanden 17 verschoben um m Bits und des Teiloperanden 19.
• Aus praktischen Gründen ist m typischerweise auf eine ganze Zahl kleiner oder gleich vier begrenzt. Eine herkömmliche ALU umfaßt eine Vorrichtung zum Erzeugen des 2er-Komplements des Y-Operanden vor der Addition. Wie weiter unten im Detail erläutert wird, umfaßt die Erfindung einen neuen Schieber, der auf dem X-Operanden vor der Addition arbeitet. Um sicherzustellen, daß die Einführung dieses Schiebers nicht die Leistung der ALU verschlechtert, dürfen die der Verschiebeoperation inhärenten Verzögerungen nicht größer als die sein, die für den Y-Operanden beim Passieren der 2er-Komplement-Hardware auftreten. In der Praxis begrenzt dieses m auf die oben genannten Werte.
• Bei der bevorzugten Ausführungsform der Erfindung sind die Teiloperanden vorzeichenbehaftete ganze Zahlen. Im Fall eines Überlaufs oder eines Unterlaufs werden die Ergebnisse an maximale bzw. minimale Werte für vorzeichenbehaftete ganze Zahlen der in Rede stehenden Länge gebunden. Wenn beispielsweise N = 32 und eine Halbwortverschiebung (das heißt 16 Bit) und eine Addieroperation implementiert sind, würde das Ergebnis im Hexadezimalformat bei 7FFF bzw. 8000 festgelegt sein.
• Um die folgende Diskussion zu vereinfachen, wird die Erfindung zunächst unter Bezugnahme auf eine ALU erläutert, die eine Verschiebung nach rechts um einen Platz des X-Operanden und anschließend eine Addition der verschobenen Operanden zu den entsprechenden Y- Operanden ausführt. Um die Diskussion weiter zu vereinfachen, wird angenommen, daß die ALU aus mehreren Einzelbitaddierern konstruiert ist, welche Übertragausbreitung während der Addition nutzen. Fig. 2 ist ein Blockdiagramm eines Teils einer erfindungsgemäßen ALU 30, welche in zwei Unteroperanden unterteilt werden kann und auch eine Rechtsverschiebung um einen Platz der X-Operanden vor der Addition ausführen kann. Die Grenze zwischen den zwei Teiloperanden erscheint auf der Bitposition k der ALU 30. Dieses bedeutet, daß das Bit k das höchstwertige Bit einer Folge an Unteroperanden und daß das Bit k+1 das niedrigstwertige Bit der anderen Folge an Unteroperanden ist. Die Additionssektion der ALU 30 ist aus einer Anordnung von einem Bit-Addiererstufen in einer Art ähnlich zu der herkömmlicher Übertragausbreitungs-Addierer konstruiert. Beispielhafte Einzelbitaddierer sind in 31-35 gezeigt. Bei der Erfindung können die Stufen entkoppelt sein, um es der ALU zu erlauben, parallele Additionen in den Teilwörtern auszuführen. Jeder Einzelbitaddierer addiert zwei Bits, eines von dem X-Operanden und eines von dem Y-Operanden abgeleitet, und einen Übertragbit von der vorhergehenden Stufe in dem Addierer, die mit Ci-1 für die i-te Stufe bezeichnet ist, um ein Summenbit und ein neues Übertrag-Bit zu erzeugen. Die mit 33 und 32 gezeigten zwei Stufen sind Einzelbitaddierer, die zum Addieren der höchstwertigen Bits der Teiloperanden 80 und 20 bzw. der niedrigstwertigen Bits der Teiloperanden 17 und 19 genutzt werden. Der Einzelbitaddierer 33 addiert beispielsweise Bits Ck-1, Xk und Yk, um ein Summenbit Sk und ein Übertrag-Bit Ck zu erzeugen. In der folgenden Diskussion wird die Stufe des Addierers, welche auf Yp agiert, als die p-te Stufe des Addierers bezeichnet. Bei einem herkömmlichen Addierer breitet sich das Übertrag-Bit jeder Stufe zu der nächsten Stufe mit Hilfe einer Verbindung des Übertragbit-Eingangs jeder Stufe mit dem Übertragbit- Ausgang der vorhergehenden Stufe in der Anordnung von Einzelbitaddierern aus.
• Bei der Erfindung wird das Übertrag-Bit von der Stufe, die sich unmittelbar vor der Grenztrennung der zwei Teiloperanden befindet, mit einer Sperrschaltung 37 verbunden. Wenn die ALU 30 als ein herkömmlicher Addierer genutzt wird, der beim Betrieb die gesamten Inhalte der Register 12 und 14 als einzelne Wörter behandelt, verbindet die Sperrschaltung 37 den Übertragausgang des Einzelbitaddierers 33 mit dem Übertrageingang des Einzelbitaddierers 32. Wenn die ALU 30 genutzt wird, um zwei Additionen parallel mit der Teilwortgrenze zwischen den Bits k und k+1 in jedem Register auszuführen, zwingt die Sperrschaltung 37 das Übertragbit des Einzelbitaddierers 33 bei der Addition 0 zu sein. Dieses wird mittels eines Grenzsignals Mk gesteuert. Die Übertragausgänge aller Einzelbitaddierer werden in den verbleibenden Stufen der ALU 30 in herkömmlicher Weise verbunden. Folglich breiten sich Übertragbits in herkömmlicher Weise innerhalb jeder Sektion der ALU aus, die einen speziellen Teiloperanden bearbeitet. Die Summenbits für jede Addiererstufe werden mit entsprechenden Bits des Ausgangsanschlusses verbunden, welcher mit Zk bezeichnet ist.
• Bei der obigen Beschreibung der ALU 30 wurde angenommen, daß Additionen der Operanden stattfinden. Die Sperrschaltung 37 ersetzt das Übertragbit mit 0 während einer Addition, in welcher dei Addierer in zwei Unteraddierer mit einer Grenze bei der Sperrschaltung unterteilt ist. Wenn der Addierer auch eine 2er-Komplement-Substraktion nutzt, in welcher der Addierer ähnlich unterteilt ist, muß das Übertragbit nicht auf 0 sondern auf 1 gezwungen werden. Die Sperrschaltung 37 nach Fig. 2 implementiert sowohl Additionen als auch Subtraktionen, in dem ein Eingang F mit einem Wert von "0" oder "1" vorgesehen ist. Wenn eine Grenze an der Sperrschaltung 37 aktiv ist, ist der Wert von F der Wert, welcher der nächsten Stufe präsentiert wird. Wenn die Grenze inaktiv ist, überträgt die Sperrschaltung 37 lediglich das Übertragbit Ck an die nächste Stufe.
• Bei herkömmlichen Addierern wird von dem höchstwertigen Bit der Operanden und dem niedrigstwertigen Bit des Ergebnisses ein vorzeichenbehaftetes Überlaufsignal erzeugt. Ein Überlauf ohne Vorzeichen wird von dem Übertragbit des Addierers des höchstwertigen Bits berechnet, der auf dem höchstwertigen Bit der Operanden arbeitet. Wenn dieses Merkmal für jeden Teiloperanden implementiert wird, wird das Überlaufsignal der Addition jedes Teiloperanden an eine geeignete Überlaufschaltung gekoppelt. Bei einer Ausführungsform der Erfindung werden die Überlaufsignale zusammen auf ODER-Bausteine gegeben, und das Ergebnissignal wird zum Erfassen eines Überlaufs genutzt. Dieses Bit kann zum Triggern einer Fangvorrichtung genutzt werden, oder es kann über ODER-Bausteine mit den Inhalten eines einzelnen Bitregisters zusammengebracht werden. Im letzten Fall kann das Programm die Inhalte des Registers prüfen, um festzustellen, ob irgendeine Operation seit dem das Register letztmalig geprüft wurde zu einem Überlauf geführt hat.
• Wie oben beschrieben, ist die ALU 30 konstruiert, um die Inhalte des X-Registers vor der Addition um eine Position nach Rechts zu schieben. Dieses wird als Reaktion auf ein Signal m durch einen 2-zu-1-Multiplexers ausgeführt, der die Bits der X-Operanden auf die geeigneten Einzelbitaddiererstufen gibt. Beispielhafte Multiplexer sind in 41-45 in Fig. 2 gezeigt. Wenn ein Multiplexersteuersignal wahr ist, ist X, mit dem Einzelbitaddierer für die Stufe (p- 1) verbunden. Wenn der Steuereingang falsch ist, ist das Bit mit Stufe p verbunden.
• Wenn die ALU vorzeichenbehaftete ganze Zahlen bearbeitet, muß das höchstwertige Bit jedes Operanden auf seiner Position nachgebildet als auch auf seine neue Position kopiert werden, weil diese Bit das Vorzeichenbit ist. Folglich müssen die Multiplexer an der Grenze der zwei Unterwörter von Multiplexern verschieden sein, die mit den X-Bits verbunden sind, welche nur im inneren eines Teiloperanten sein können. Multiplexer 43 ist ein solcher Multiplexer. Der Multiplexer 43 verbindet Xk mit Stufe k, wenn m wahr ist und das X-Register ist unterteilt, so daß die Stufe Xk das höchstwertige Bit eines Operanden ist. Wenn das X-Register nicht derart unterteilt ist, d. h. Mk ist falsch, verhält sich der Multiplexer 43 in der selben Art und Weise wie die anderen Multiplexer.
• Bei der bevorzugten Ausführungsform der Erfindung wird der Ort der Stufe an der Grenze der Operanden mit Hilfe einer Maske spezifiziert, deren Bits mit Mp bezeichnet werden. Die Bits Mp spezifizieren den Ort des höchstwertigen Bits jedes Teiloperanden. Diese Maske wird in der folgenden Diskussion als die Grenzmaske bezeichnet. Die Bits der Maske können in einem Register der ALU gespeichert sein oder direkt aus der Instruktion erzeugt werden, die von der Instruktions-Dekodierschaltung des Prozessors ausgeführt werden, in welchem der Addierer angeordnet ist.
• Für den Fachmann ergibt sich, daß die Lehre der Erfindung auf eine Vielzahl Addiererkonfigurationen angewendet werden kann, obwohl die oben genannten Ausführungsformen der Erfindung in Verbindung mit einem Addierer beschreiben sind, der aus Einzelbitaddierern konstruiert ist, welche Übertragausbreitung nutzen. Jede Addiererkonfiguration, in welcher der Addierer in Unteraddierer so unterteilt werden kann, daß das höchstwertige Bit jedes möglichen Unteroperanden an einer Grenze eines Unteraddierers angeordnet ist, kann zum Ausführen der Erfindung konfiguriert werden. Der Addierer wird mittels der Einführung einer Schaltung verändert, die den Übertrag von dem Unteraddierer unterbricht, wenn der Addierer an dem in Rede stehenden Unteraddierer unterteilt ist.
• Bei der bevorzugten Ausführungsform der Erfindung wird eine Vorher-Übertragarchitektur genutzt, weil sie kleinere Verzögerungen aufweist. In einem Vorher-Übertragaddierer ("carry look ahead adder") erzeugt die Übertragerzeugungsschaltung ein Ausbreitungs- und ein Erzeugungssignal entsprechend jedem Bit des Addierers. Diese Signale können in analoger Weise zu den oben beschriebenen Übertragbits genutzt werden, um ein Aufteilen des Addierers in parallele Unterwortaddierer zu ermöglichen. Es sei der Fall betrachtet, daß der Addierer so unterteilt ist, daß die Stufe k auf dem höchstwertigen Bit des Unterwortergebnisses arbeitet. Eine Sperrschaltung, beispielsweise die Sperrschaltung 37 nach Fig. 2 kann in die Übertragerzeugungslogik so eingefügt werden, daß das Ausbreitungsbit und das Erzeugungsbit in Abhängigkeit von der ausgeführten Operation, d. h. Addition oder Subtraktion, auf die entsprechenden Werte gezwungen werden. Wenn der Addierer auf Wörtern genutzt wird, die nicht bei Stufe k unterbrochen sind, verändert die Sperrschaltung die Werte des Ausbreitungs- und des Erzeugungsbits nicht entsprechend Stufe k.
• Die Ausführungsform der Erfindung nach Fig. 2 ist konstruiert, um die X-Operanden nur um einen Platz nach rechts zu verschieben. Es ergibt sich aus der Diskussion jedoch, daß die selben Prinzipien genutzt werden können, um eine ALU zu schaffen, die die X-Operanden um eine beliebige Größe m ≤ u verschieben kann. In diesem Fall würden die als 41-45 gezeigten 2-zu-1-Multiplexer durch (u+1)-zu-1-Multiplexer ersetzt werden. Das Signal m muß in der Lage sein zu spezifizieren, welche der (u+1) möglichen Verschiebepositionen spezifiziert ist. Wenn die Stufe p des Addierers nur auf einem inneren Bit eines Operanden arbeiten kann, verbindet der hieran gekoppelte Multiplexer-Stufe p mit Xp+m. Wenn Stufe p jedoch innerhalb von m Stufen einer potentiellen Unterwortgrenze ist, muß der mit der Stufe p in Verbindung stehende Multiplexer die Maskenbits als auch das Verschiebesignal m untersuchen. Es sei der Fall betrachtet, daß die Maskenbits anzeigen, daß in der Stufe k eine Grenze aktiv ist, d. h. Xk ist das höchstwertige Bit eines Unterworts. Dann muß der der Stufe p zugeordnete Multiplexer Xk zu dem Addierer der Stufe p kopieren wenn (k-m) ≤ p ≤ k gilt. Es wird darauf hingewiesen, daß Xk mit einem der Eingänge jedes der in Rede stehenden Multiplexer verbunden wird.
• Jede Eingangsverbindung, die eine mögliche Operandengrenze kreuzt, muß ein Gatter umfassen, beispielsweise das Gatter 49 nach Fig. 2. Dieses Gatter blockiert die Ausbreitung des Datenbits über die Grenze, wenn die Grenze aktiv ist. Diese bedeutet, daß in dem Fall, daß die Addiererstufe p mit der Eingangsleitung Xq verbunden ist, diese Verbindung ein Gatter umfassen muß, welches die Verbindung unterbricht, wenn Mk für irgendein k von q bis p-1 wahr ist.
• Wenn X immer eine ganze Zahl ohne Vorzeichen ist, sind die Sperrgatter notwendig, wie Gatter 49. Der Multiplexer 43 kann jedoch aus einem Multiplexer konstruiert sein, der der gleiche wie die anderen Multiplexer ist (d. h. 41, 42, 44 und 45). Wenn X eine vorzeichenbehaftete Zahl ist, dann müssen u-Bits von M in den Multiplexer 43 eingegeben werden, so daß dieser von den anderen Multiplexern verschieden wird. In diesem Fall kann auf die Sperrgatter, beispielsweise Gatter 49 verzichtet werden, weil ihre Betriebsart die Gatter überflüssig macht.
• Die Verschiebeoperation nach rechts kann zu einem Aufrundungsfehler führen. Der Aufrundungsfehler tritt auf, wenn eine 1 aus dem X-Unterwort geschoben wird. Die oben beschriebenen Ausführungsformen der Erfindung runden das Ergebnis mittels Abbruch. Während ein Abbruch beim Runden des Ergebnisses einer Division durch eine ganze Zahl genutzt werden kann, kann es ungewünschte Probleme verursachen, die mit Hilfe anderer Formen des Rundens vermieden werden können. Beispielsweise führt Abbruch zu Fehlern in dem Fall, bei dem die Division auf eine Sammlung von Wörtern angewendet wird, und der Mittelwert der Sammlung ist von Bedeutung. Abbruchrunden führt zu einer Verschiebung des Mittelwerts, weil alle Vierte auf die nächstkleinere ganze Zahl gerundet werden.
• Bei der bevorzugten Ausführungsform der Erfindung wird eine Logik für ungerades Runden genutzt, um diese Art systematischer Abweichung zu verhindern. In Systemen zum ungeraden Runden wird das Ergebnis auf die nächste ungerade Zahl gerundet, wenn durch die Rechtsverschiebung ein Aufrundungsfehler erzeugt wird. Wenn die Antwort vor dem Runden exakt ist, wird keine Änderung vorgenommen. Ein Aufrundungsfehler tritt immer dann auf, wenn eine 1 aus dem Ergebnis verschoben wird. Dieses tritt auf, wenn m niedrigstwertige Bits vor dem Verschieben wenigstens eine "1" aufweisen. m ist hier die Anzahl der verschobenen Bits. In einem System zum ungeraden Runden wird das niedrigstwertige Bit des Erlebnisses auf eine "1" gesetzt, wenn eine "1" aus dem Wort geschoben wurde. Wenn alle herausgeschobenen Bits "0" sind, dann war das Ergebnis auch nach dem Verschieben exakt und das niedrigstwertige Bit des Ergebnisses wird nicht geändert.
• Ein ungerades Rundungssystem kann in die Erfindung dadurch integriert werden, daß der mit der Stufe p verbundene Multiplexer durch eine Multiplexeranordnung gemäß 200 in Fig. 3 ersetzt wird, wenn die Stufe p entweder auf einem internen Bit eines Unterworts oder dem niedrigstwertigen Bit eines Unterworts arbeitet. Die Anordnung umfaßt einen (2u+1)-zu-1- Multiplexer 202, der von einem Rundungssignal, einem Verschiebesignal m und dem Maskenbits M gesteuert wird. Die Eingänge des Multiplexers 202 können in zwei Gruppen unterteilt werden. Eine Gruppe 221 wird genutzt, wenn die Stufe p auf dem niedrigstwertigen Unterwort arbeitet, und das Rundungssignal R zeigt an, daß Runden ausgeführt wird in diesem Fall ist die Stufe p mit einem Signal verbunden, welches durch Auswählen des m-ten Eingangs der Gruppe 221 den Wert (Xp ODER Xp+1 ODER ... Hp+m) hat. Der m-te Eingang der Gruppe 221 ist mit einer ODER-Schaltung verbunden, welche Eingänge Xp bis Xp+m aufweist. Beispielhafte ODER-Schaltungen sind als 205-207 gezeigt. Wenn kein Runden ausgeführt wird, dann ist die Stufe p mit dem m-ten Eingang einer Gruppe 220 verbunden. In dieser Betriebsart verhält sich die Multiplexer-Anordnung in der gleichen Weise wie die anderen an die Stufen gekoppelten (u+1)-zu-1-Multiplexer, die nur auf internen Bits von Unterwörtern arbeiten können.
• Es kann gezeigt werden, daß der mittlere Fehler, welcher mit dieser Form des Rundens erhalten wird, Null ist, wenn die niedrigstwertigen (m+1)-Bits vorn X vor dem Verschieben einheitlich verteilt werden. Es wird darauf hingewiesen, daß ein System zum geraden Runden beim Runden ebenfalls systematische Abweichungen verhindert. In einem System zum geraden Runden wird das Ergebnis auf die nächste gerade ganze Zahl gerundet, wenn ein Aufrundungsfehler auftritt, und das Ergebnis vor dem Runden ist ungerade. Die zum Implementieren eines geraden Rundungsschemas benötigte Hardware ist jedoch wesentlich komplexer als die oben beschriebene. Folglich wird ein System zum ungeraden Runden bevorzugt.
• Es ergibt sich für den Fachmann, daß Ausführungsformen, in denen die Grenzen und/oder die Anzahl an Unterwörtern von den oben beschriebenen abweichen, mittels der Nutzung der obigen Lehre implementiert werden können, obwohl die oben beschriebenen Ausführungsformen der Erfindung entweder für Vollwortoperationen oder parallele Operationen von zwei Halbwörtern angegeben wurden. Die einzige Begrenzung der Anzahl von Unteroperanden besteht darin, daß die Summe der Bits in den Unteroperanden nicht größer als die Breite der ALU sein darf, die in der Vollbreite-Betriebsart arbeitet. In ähnlicher Weise können die Unteroperanden-Grenzen im Prinzip zwischen beliebigen zwei Bits in der ALU mit Hilfe des Setzens des entsprechenden Maskenbits gesetzt werden.
• Es ergibt sich für den Fachmann, daß die Erfindung auch die Differenz jedes Unterworts in dem X-Wort dividiert durch 2m und des entsprechenden Unterworts in dem X-Wort liefern kann, obwohl die oben beschriebenen Ausführungsformen der Erfindung in Verbindung mit dem Berechnen der Summe jedes Unterworts in dem X-Unterwort dividiert durch 2 m und des entsprechenden Unterworts in dem Y-Wort beschreiben wurden. Wie oben beschrieben, liefern die meisten ALUs Schaltungstechnik zum Ersetzen des Y-Eingangs durch das 2er- Komplement hiervon. Folglich können die in Frage stehenden Differenzen mittels dieser herkömmlichen Schaltungstechnik auf den Y-Operanden berechnet werden.
• Es ergibt sich für den Fachmann, daß die Erfindung auch Vorteile liefert, wenn sie für nicht unterteilte Datenwörter ausgeführt wird, obwohl die Erfindung in Verbindung mit einer ALU beschrieben wurde, die unterteilbar ist. In diesem Fall ermöglicht die Erfindung das Ausführen einer Division und einer Addition in einem einzelnen Maschinenzyklus als Reaktion auf eine Einzelinstruktion.
• Es ergibt sich für den Fachmann, daß die Operationen der Erfindung mit Hilfe elektrischer Signale getriggert werden können, die nicht mittels Instruktionen eines gespeicherten Computerprogramms erzeugt werden, obwohl die oben genannten Ausführungsformen der Erfindung in Verbindung mit Instruktionen als Mittel zum Triggern der von der Erfindung ausgeführten verschiedenen Operationen beschrieben wurde. Folglich umfaßt der Ausdruck "Instruktion", wenn er in den Ansprüchen genutzt wird, auch Operationen, die von anderen Formen der Signalgebung getriggert werden. Weiterhin ergibt sich für den Fachmann, daß die Erfindung in Schaltungstechnik genutzt werden kann, die nicht Teil eines Computers ist.
• Verschiedene Modifikationen der Erfindung ergeben sich für den Fachmann aus der vorhergehenden Beschreibung und der zugehörigen Zeichnung. Dementsprechend wird die Erfindung allein durch den Bereich der folgenden Ansprüche definiert.

Claims (6)

1. Vorrichtung zum Verarbeiten der Inhalte eines X-Worts mit Bits Xi und eines Y-Worts mit Bits Yi zum Erzeugen eines Ergebnisworts mit Bits Zi, wobei I = 0 bis Id - 1, Z&sub0; das niedrigstwertige Bit und ZN-1 das höchstwertige Bit sind, die Vorrichtung aufweisend:

Mittel (10; 30) zum getrennten Partitionieren des X-, , des Y- und des Ergebnisworts in mehrere Unterwörter (17, 18, 19, 20, 21, 22), wobei jedem Unterwort des X-Worts (12) ein Unterwort des Y-Worts und ein Unterwort des Ergebnisworts (14, 16) entspricht; und

Mittel (10; 30), die mit einem ersten Befehl ansprechbar sind, zum Erzeugen der Summe jedes X-Unterworts (17, 18) dividiert durch 2m und des entsprechenden Y- Unterworts (19, 20), wobei das Ergebnis hiervon das entsprechende Unterwort (21, 22) des Ergebnisworts (16) bestimmt und wobei m eine von 0 verschiedene ganze Zahl ist,

wobei die Mittel zum Erzeugen der Summe 0-te bis [N-1]-te Einzelbitaddierer (31-35) und entsprechende 0-te bis [N-1]-te [u+1] - bis -1-Multiplexer (41-45) umfassen, wobei jeder Einzelbitaddierer das von dem entsprechenden Multiplexer gelieferte Bit und das entsprechende Bit des Y-Worts (14) addiert, wobei u ≥ m,

wobei Eingänge des p-ten Multiplexers mit Bits Xp bis Xp+u des X-Worts (12) verbunden sind und der p-te Multiplexer Bit Xp+m ausgibt, und

wobei die Mittel zum gezielten Aufteilen eine Sperrschaltung (37) zum gezielten Verhindern des Ausbreitens eines in einem Addierer von einem der Unterwörter erzeugten Übertragbits zu einem Addierer eines anderen der Unterwörter und zum gezielten Sperren der Ausbreitung von Bits Xi eines der Unterwörter zu den Multiplexern umfassen, die den Addierern eines anderen der Unterwörter entsprechen.

2. Vorrichtung nach Anspruch 1, gekennzeichnet durch Mittel (30), die mit Hilfe eines zweiten Befehls ansprechbar sind, zum Erzeugen der Differenz jedes Unterworts in dem X-Wort dividiert durch 2m und des entsprechenden Unterworts in dem Y-Wort, wobei das Ergebnis hiervon das entsprechende Unterwort des Ergebnisworts (21, 22) bestimmt.

3. Vorrichtung nach Anspruch 1 oder 2, gekennzeichnet durch Mittel (202) zum Runden des Ergebnisses der Division jedes Unterworts des X-Worts auf die nächst höhere ungerade ganze Zahl, wenn die Division durch 2m zu einem Abrundungsfehler führt.

4. Vorrichtung nach Anspruch 1, 2 oder 3, die Einzelbitaddierer (31-35) aufweisend:

mehrere Y-Eingabemittel, wobei jedes Y-Eingabemittel ein von dem Y-Wort abgeleitetes Bit empfängt, und wobei die Y-Eingangsmittel das von Yp abgeleitete Bit empfangen, welches das p-te Y-Eingangsmittel ist, wobei. p das Produkt eines Binäranteils und einer Anzahl ist;

mehrere X-Eingabemittel, wobei jedes X-Eingabemittel ein von dem X-Wort abgeleitetes Bit empfängt, eines der X-Eingabemittel existiert, das jedem der Y- Eingabemittel entspricht, und das dem p-ten Y-Eingabemittel entsprechende X- Eingabemittel das p-te X-Eingabemittel ist; und

wobei mehrere der Einzelbitaddierer-Addierstufen (31-35) in Reihe verbunden sind, jede Addierstufe Mittel zum Addieren eines oder mehrerer Bits; die von dem X- Eingabemittel empfangen werden, und der von den Y-Eingabemittel empfangenen entsprechenden Bits sowie Mittel zum Ausbreiten eines Übertragbits von der Addierstufe zu der nächsten Addierstufe in der Reihenverbindung umfaßt, wobei die Yp verarbeitende Addierstufe die p-te der Addierstufen ist und wobei die Aufteilmittel Mittel zum Zwingen (37) des Übertragbits auf einen Wert umfassen, der durch den Betrieb bestimmt wird, welcher ausgeführt wird, wenn die Addierstufen mit Bits verschiedener Unterwörter des X-Worts arbeiten.

5. Vorrichtung nach Anspruch 4, gekennzeichnet durch Mittel (200) zum Erzeugen eines Signals mit dem Wert (Xp OR Xp+1 OR ... Xp+m) und zum Verbinden des Signals mit der p-ten Addierstufe, wenn Xp das niedrigstwertige Bit eines der Unterwörter ist.

6. Vorrichtung nach Anspruch 4 oder 5, wobei die Aufteilmittel weiterhin Mittel (37) zum Erzeugen eines Signals umfassen, das anzeigt, daß eines der Übertragbits eine "1" vor dem Übertragbit war, welches auf den vorbestimmten Wert gezwungen wird.