DE3854321T2

DE3854321T2 - Populationszählung in Rechnersystemen.

Info

Publication number: DE3854321T2
Application number: DE3854321T
Authority: DE
Inventors: Koji Fujitsu Limited Kuroda; Shoji Fujitsu Limited Nakatani
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1987-11-30
Filing date: 1988-11-30
Publication date: 1996-01-18
Anticipated expiration: 2008-12-01
Also published as: DE3854321D1; US4989168A; AU2599388A; CA1289669C; EP0318957A3; EP0318957A2; AU598405B2; EP0318957B1

Description

Die vorliegende Erfindung bezieht sich auf das Populationszählen in Computersystemen.
Die Entwicklung von Computersystemen hat dazu geführt, daß die Datenverarbeitung, die in Computersystemen erfolgt, mit hoher Geschwindigkeit ausgeführt werden kann. Auf dem Gebiet der grafischen Anzeige ist zum Beispiel erreicht worden, daß die variable Dichte eines Graphs durch Computersysteme schnell verarbeitet werden kann. Das heißt, die variable Dichte wird in einem Computersystem mit hoher Geschwindigkeit verarbeitet, indem die Anzahl von "1"-Bits in numerischen Daten, die in Binärschreibweise dargestellt sind und graf ische Informationen enthalten, gezählt werden. Solch ein Zählen der Anzahl von "1"-Bits wird "Populationszählen" genannt, und eine Anweisung zum Ausführen solch eines Zählens wird als "Populationszählanweisung" bezeichnet. Die vorliegende Erfindung bezieht sich auf die Ausführung des Populationszählens in Computersystemen.
Das Populationszählen ist durch eine Schaltung ausgeführt worden, die in einem Computersystem ausschließlich für den Zweck vorgesehen war. Mit solch einer dedizierten Populationszählschaltung kann die Anzahl von "1"-Bits in numerischen Daten gezählt werden, welche Daten gewöhnlich aus 8 Bytes bestehen. Es wird jedoch immer ein Byte einzeln gezählt, und so dauert es eine lange Zeit, um in den gesamten numerischen Daten die "1"-Bits zusammenzuzählen. Allein angesichts einer erwünschten erhöhten Zählgeschwindigkeit könnte das Vorsehen einer dedizierten Zählschaltung erwogen werden, die zwei oder mehr Bytes auf einmal anstelle immer eines Bytes zählen könnte. Dies ist jedoch praktisch nicht realisierbar, da für solch eine dedizierte Schaltung eine große Menge an Hardware (elektrische Teile) erforderlich wäre. Somit hat die Verwendung einer dedizierten Schaltung die Nachteile erhöhter Kosten (für die Schaltung) und einer niedrigen Geschwindigkeit (d. h., eine beträchtliche Zeit ist erforderlich).
In Computersystemen, besonders in neuen Computersystemen mit hoher Geschwindigkeit, wie sogenannten Supercomputern, können Multipliziereinheiten eine Multiplikation mit hoher Geschwindigkeit ausführen, wobei Daten in Einheiten von mehr als zwei Bytes unter Verwendung von Übertragssicherungsaddierern (carry save adders CSA) und Übertragspropagationsaddierern (carry propagate adders CPA) verarbeitet werden, welches Addierer sind, die zum Einsatz in Multipliziereinheiten in Computersystemen wohlbekannt sind. Falls eine Multipliziereinheit verwendet werden könnte, um ein Populationszählen auszuführen, könnte demzufolge die Zählgeschwindigkeit des Populationszählens erhöht werden, ohne daß es notwendig wäre, eine dedizierte Populationszählschaltung vorzusehen. Ferner wird in Computersystemen die Multipliziereinheit im allgemeinen nicht so oft verwendet, und außerdem wird das Populationszählen nicht oft ausgeführt. Dementsprechend kann angenommen werden, daß die Verwendung einer Multipliziereinheit zur Populationszählung dazu beitragen würde, die Effektivität des Einsatzes der Multipliziereinheit eher zu erhöhen, als die Operation des Computersystems zu stören.
Die Verwendung einer Multipliziereinheit zur Populationszählung ist durch Shoji Nakatani versucht worden, der einer der Erfinder der vorliegenden Erfindung ist. Dieser Versuch führte zu einem Vorschlag, der in einer offengelegten japanischen Patentanmeldung SHOH 62-209621 (14. September 1987) beschrieben ist. In SHOH 62-209621 enthält die verwendete Multipliziereinheit jedoch nur eine Multiplizierschaltung mit einem Überlaufaddierer (spill adder). Wenn der Multiplikator von Multiplikationsdaten in eine Vielzahl von Elemente geteilt ist, muß deshalb die Multiplikation in der Multiplizierschaltung so viele Male wiederholt werden, wie die Anzahl an Elementen beträgt. Wenn der Multiplikator zum Beispiel aus 8 Bytes besteht und in 4 Elemente geteilt ist, muß eine Multiplikation viermal ausgeführt oder wiederholt werden (in diesem Fall ist der Multiplikand der Multiplikationsdaten nicht geteilt). Ferner wird der Überlaufaddierer zum Kompensieren von niedrigeren Stellen benötigt, die während der Wiederholung der Multiplikation erscheinen, um bis zu den Endmultiplikationsresultaten übertragen zu werden.
Im allgemeinen gibt es zwei Typen der Multipliziereinheit. Bei dem ersten Typ der Multipliziereinheit wird die Größe als wichtiger als die Zählgeschwindigkeit erachtet, so daß eine Multipliziereinheit des ersten Typs gewöhnlich nur eine Multiplizierschaltung enthält. Die Multipliziereinheit in SHOH 62-209621 ist dieser erste Typ. Bei dem zweiten Typ der Multipliziereinheit wird die Zählgeschwindigkeit als wichtiger als die Größe erachtet, so daß die Multipliziereinheit des zweiten Typs eine Vielzahl von Multiplizierschaltungen (Untereinheiten) enthält, die parallel arbeiten. Der Vorschlag von SHOH 62-209621 kann auf den zweiten Multiplizierertyp nicht angewendet werden.
Gemäß der vorliegenden Erfindung ist eine Multipliziereinheit vorgesehen, die in einem Computersystem vorgesehen ist, zum Ausführen einer Multiplikation von Multiplikandendaten und Multiplikatordaten in einem Multiplikationsmodus und zum Ausführen eines Populationszählens von Populationszähleingangsdaten in einem Populationszählmodus, welche Multipliziereinheit umfaßt:
ein Mittel zum Registrieren der Multiplikandendaten im Multiplikationsmodus;
ein Mittel zum Registrieren und gleichmäßigen Teilen der Multiplikatordaten in eine Vielzahl von Multiplikatorelementen im Multiplikationsmodus, und zum Registrieren und gleichmäßigen Teilen der Populationszähldaten in eine Vielzahl von Populationszählelementen mit derselben Anzahl wie die Multiplikatorelemente im Populationszählmodus;
eine Vielzahl von Multiplizieruntereinheiten zum Ausführen von gleichzeitigen Teilmultiplikationen zwischen dem Multiplikanden und den Multiplikatorelementen im Multiplikationsmodus, wobei Teilproduktdaten der Teilmultiplikationen erzeugt werden, und zum Ausführen von gleichzeitigen Teilpopulationszählungen bei den Populationszählelementen im Populationszählmodus, wobei Teilzähldaten der Teilpopulationszählungen erzeugt werden, von welchen Multiplizieruntereinheiten eine Vielzahl, die in der Anzahl den Populationszählelementen gleich ist, Multiplizieruntereinheiten des ersten Typs umfaßt, von welchen Multiplizieruntereinheiten des ersten Typs jede umfaßt:
ein erstes Untereinheitsregister zum Setzen eines der Multiplikatorelemente im Multiplikationsmodus, und zum Setzen eines der Populationszählelemente im Populationszählmodus;
einen zweiten Übertragssicherungsaddierer zum Zählen der Anzahl von "1"-Datenbits in dem Populationszählelement, das in dem genannten ersten Untereinheitsregister registriert ist, wobei immer zwei Datensignale des Populationszählelementes gleichzeitig eingegeben werden, welche zwei Datensignale die sind, die jeweilig an zwei Registrierpositionen des genannten ersten Untereinheitsregisters, die aneinandergrenzen, registriert worden sind, und elementare Summen- und Übertragsdaten des Populationszählelementes ausgegeben werden;
ein zweites Untereinheitsregister zum Setzen und Ausgeben der Multiplikandendaten im Multiplikationsmodus, und zum Erzeugen und Ausgeben von lauter "0"- Datenbits im Populationszählmodus;
einen Dekodierer zum Ausgeben von dekodierten Signalen, die zum Multiplizieren der Multiplikandendaten und des Multiplikatorelementes erforderlich sind, im Multiplikationsmodus, wobei das Multiplikatorelement von dem genannten ersten Untereinheitsregister eingegeben wird, und zum Erzeugen und Ausgeben von lauter "0"- Datenbits im Populationszählmodus;
einen Vielfachgenerator zum Erzeugen und Ausgeben von verschobenen Daten durch Kombinieren der Multiplikandendaten von dem genannten zweiten Untereinheitsregister und der dekodierten Signale von dem genannten Dekodierer im Multiplikationsmodus, und zum Erzeugen und Ausgeben von lauter "0"-Datenbits im Populationszählmodus;
ein Paar eines ersten Übertragssicherungsaddierers und eines ersten Übertragspropagationsaddierers zum Ausgeben der Teilproduktdaten der Teilmultiplikation der Multiplikandendaten und des Multiplikatorelementes im Multiplikationsmodus, wobei die verschobenen Daten von dem genannten Vielfachgenerator addiert werden, und zum Ausgeben der Teilzähldaten der Anzahl von "1"- Datenbits im Populationszählelement im Populationszählmodus, wobei die elementaren Summen- und Übertragsdaten von dem genannten zweiten Übertragssicherungsaddierer addiert werden; und
ein Selektormittel zum Selektieren der verschobenen Daten von dem genannten Vielfachgenerator und der elementaren Summen- und Übertragsdaten von dem genannten zweiten Übertragssicherungsaddierer, um gemäß dem Multiplikationsmodus bzw. Populationszählmodus eine Menge der genannten Daten zu dem genannten Paar eines ersten Übertragssicherungsaddierers und eines ersten Übertragspropagationsaddierers zu senden; und welche Multipliziereinheit auch umfaßt:
ein Mittel zum Addieren der genannten Teilproduktdaten von den genannten Multiplizieruntereinheiten im Multiplikationsmodus, wobei ein Multiplikationsresultat der Multiplikandendaten und der Multiplikatordaten ausgegeben wird, und zum Addieren der genannten Teilzähldaten der Teilpopulationszählungen von den genannten Multiplizieruntereinheiten im Populationszählmodus, wobei ein Populationszählresultat der Populationszähleingangsdaten ausgegeben wird.
In einer Multipliziereinheit gemäß der vorliegenden Erfindung können im Multiplikationsmodus die Multiplikandendaten gleichmäßig in eine Vielzahl von Multiplikandenelementen geteilt werden.
Eine Ausführungsform der vorliegenden Erfindung kann eine Erhöhung der Ausführungsgeschwindigkeit einer Populationszählanweisung vorsehen, die einem Computersystem erteilt wird, das eine Multipliziereinheit des zweiten Typs (mit Multiplizieruntereinheiten) enthält.
Eine Ausführungsform der vorliegenden Erfindung kann eine Verringerung der Menge an (dedizierten) elektrischen Teilen vorsehen, die zum Ausführen einer Populationszählanweisung in einem Computersystem vorgesehen sind.
Eine Ausführungsform der vorliegenden Erfindung kann die Leistung des Populationszählens mit niedrigeren Ausgaben bei Computersystemherstellungskosten vorsehen.
In einer Ausführungsform der vorliegenden Erfindung wird eine Multipliziereinheit des zweiten Typs verwendet, die eine Vielzahl von Multiplizieruntereinheiten enthält. Es werden CSAs und CPAs verwendet, die in den Multiplizieruntereinheiten vorgesehen sind, wobei zu jeder Multiplizieruntereinheit nur eine kleine Menge an Hardware (elektrische Teile) hinzugefügt wird, wie ein Addierer, Selektoren und einige logische Schaltungselemente.
Wenn in einer Multipliziereinheit eine Multiplikation ausgeführt wird, erfolgt dies gewöhnlich zum Zweck des Ausführens eines Programms in dem Computersystem. Dieser Operationszustand oder -modus wird nachfolgend als "regulärer Multiplikationsmodus" bezeichnet. Gemäß einer Ausführungsform der vorliegenden Erfindung ist das Computersystem jedoch so abgewandelt, daß die Multipliziereinheit sowohl für die reguläre Multiplikation als auch für die Populationszählung arbeiten kann. Dieser letztere Operationszustand oder -modus der Multipliziereinheit wird nachfolgend als "Populationszählmodus" bezeichnet.
Im Populationszählmodus werden numerische Daten zum Populationszählen in einem Multiplikatorregister in der Multipliziereinheit des zweiten Typs gesetzt und in eine Vielzahl von Elemente geteilt. Das Teilen des Multiplikators wird auf der Grundlage des Verfahrens ausgeführt, das im regulären Multiplikationsmodus verwendet wird; das heißt, das Teilen erfolgt unter Berücksichtigung der Berechnungsform, die im regulären Multiplikationsmodus ausgeführt wird, und der Anzahl der Multiplizieruntereinheiten, die in der Multipliziereinheit des zweiten Typs vorgesehen sind. Die Berechnungsform ist eine Form zum Multiplizieren von Multiplikand und Multiplikator, die der Multipliziereinheit gegeben sind. Im allgemeinen existieren in einer Multipliziereinheit des zweiten Typs mehrere Berechnungsformen. Gemäß einigen Berechnungsformen wird die Multiplikation zum Beispiel ausgeführt, indem Elemente miteinander multipliziert werden, die durch Teilen des Multiplikanden und des Multiplikators erhalten wurden, und gemäß einer anderen Berechnungsform wird die Multiplikation ausgeführt, indem der Multiplikand, der nicht geteilt ist, zusammen mit Elementen multipliziert wird, die durch Teilen des Multiplikators erhalten wurden.
Nachdem die numerischen Daten zur Populationszählung in dem Multiplikatorregister in eine Vielzahl von Elementen geteilt sind, werden die Bytes jedes Elementes zu der jeweiligen Multiplizieruntereinheit gesendet, und die Anzahl von "1"-Bits in jedem Element wird durch einen CSA gezählt, der für die jeweilige Multiplizieruntereinheit zum Ausführen der Populationszählung neu vorgesehen ist, und eine Halbsummenausgabe (HS) und eine Halbübertragsausgabe (HC) bezüglich der Anzahl von Bits "1" in jedem Element werden von dem neu vorgesehenen CSA erzeugt. Die HS- und HC-Ausgaben werden zu einem CSA und einem CPA gesendet, die in jeder Multiplizieruntereinheit vorgesehen worden sind (gewöhnlich vorgesehen sind), und durch sie unter Verwendung des wohlbekannten Booth-Algorithmus addiert.
Die gezählten Resultate der Anzahlen von "1"-Bits in jeweiligen Elementen werden von den Multiplizieruntereinheiten zu einem gemeinsamen CSA und einem gemeinsamen CPA gesendet, die auch in der Multipliziereinheit des zweiten Typs vorgesehen worden sind (gewöhnlich vorgesehen sind), in denen die gezählten Resultate von den Multiplizieruntereinheiten addiert werden und die Endresultate der Populationszählung von dem gemeinsamen CPA ausgegeben werden.
Da die Hardware und der Multiplizieralgorithmus der Multiplizieruntereinheiten in der Multipliziereinheit des zweiten Typs effektiv parallel genutzt werden können, kann in einer Ausführungsform der vorliegenden Erfindung die Populationszählung mit hoher Geschwindigkeit erfolgen, wobei weniger Hardware verwendet wird.
Als Beispiel wird Bezug auf die beiliegenden Zeichnungen genommen, in denen:-
Fig. 1 ein Blockdiagramm einer Populationszählschaltung nach Stand der Technik ist, die in einem Computersystem vorgesehen ist;
Fig. 2 8-Byte-Eingangs- und -Ausgangsdaten bezüglich einer Populationszählanweisung zeigt;
Fig. 3 ein Schaltungsdiagramm einer Populationszählschaltung nach Stand der Technik ist;
Fig. 4 ein Blockdiagramm einer ersten Ausführungsform der vorliegenden Erfindung ist;
Fig. 5 ein Schaltungsdiagramm ist, das einen Populationszählmodus der ersten Ausführungsform zeigt;
Fig. 6 ein Schaltungsdiagramm eines ersten Selektors und eines Teils eines Vielfachgenerators ist;
Fig. 7 ein Schaltungsdiagramm eines zweiten Selektors und eines Teils eines Vielfachgenerators ist;
Fig. 8 ein schematisches Diagramm ist, das ein Additionsverfahren zur Populationszählung in einer Untere inheit zeigt;
Fig. 9 ein schematisches Diagramm ist, das ein Additionsverfahren der Anzahl von "1"-Ausgaben von den vier Multipliziereinheiten in der ersten Ausführungsform zeigt;
Fig. 10 ein Blockdiagramm einer zweiten Ausführungsform der vorliegenden Erfindung ist;
Fig. 11 ein schematisches Diagramm ist, das ein Additionsverfahren in einer Untereinheit zeigt, um eine Vollsumme und einen Vollübertrag zu erhalten; und
Fig. 12 ein schematisches Diagramm ist, das ein Additionsverfahren der Anzahl von "1"en zeigt, die von den vier Multipliziereinheiten in der zweiten Ausführungsform ausgegeben wurden.
Bevor Ausführungsformen der Vorliegenden Erfindung beschrieben werden, werden unter Bezugnahme auf Fig. 1 bis 3 eine dedizierte Populationszählschaltung nach Stand der Technik und ein Vorschlag nach Stand der Technik für eine Multipliziereinheit des ersten Typs, die ein Populationszählen ausführen kann, kurz erläutert.
Fig. 1 ist ein Blockdiagramm einer dedizierten Populationszählschaltung, die für ein Computersystem vorgesehen ist. In der dedizierten Populationszählschaltung wird das Populationszählen wie folgt ausgeführt: numerische Daten (die aus 8 Bytes bestehen, in Binärschreibweise) für das Populationszählen werden einem Register (REG) 50 eingegeben; die 8-Byte-Daten werden über einen Selektor 51 zu einem weiteren Register REG 52 übertragen, und ein Byte, das die niedrigsten Einheiten der 8-Byte-Daten in REG 52 bildet und das nachfolgend als niedrigstes Byte in REG 52 bezeichnet wird, wird zu einer Operationsschaltung 53 gesendet, in der die Anzahl von "1"-Bits gezählt und in eine Binärzahl konvertiert und zu einem CPA 54 gesendet wird. In dem CPA 54 wird die Anzahl von "1"-Bits in dem niedrigsten Byte in REG 52 gezählt und in einem Zwischenregister REG 55 gespeichert. Während des obigen Schritts werden die 8-Byte-Daten in REG 52 nach rechts verschoben, so daß das nächstniedrigste Byte, ausgehend vom niedrigsten Byte, das bei dem obigen Schritt behandelt wurde, auf die Position des niedrigsten Bytes gesetzt wird. Dann wird die Anzahl von "1"-Bits in diesem nächstniedrigsten Byte durch dasselbe Verfahren wie oben gezählt, und das gezählte Resultat für dieses nächstniedrigste Byte wird zu dem gezählten Resultat für das vorhergehende niedrigste Byte addiert. Im CPA 54 wird das Zählen der Anzahl von "1" -Bits in jeweiligen Bytes für jedes Byte wiederholt, und die gezählten Resultate werden addiert. Die Ausgabe von dem CPA 54 wird zu einem Resultatsregister REG 56 gesendet, von dem die Anzahl von "1"-Bits in den numerischen 8-Byte-Daten ausgegeben wird, wie in Fig. 2 gezeigt. Somit ist in der dedizierten Populationszählschaltung nach Stand der Technik das Zählen von "1"-Bits ausgeführt worden, indem das Verfahren zum Zählen der Anzahl von "1"-Bits in einem Byte achtmal wiederholt wurde. Dies führt zu einer beträchtlichen Zeitvergeudung. Das Zählen könnte theoretisch immer bei zwei oder mehr Bytes auf einmal ausgeführt werden, aber in der Praxis ist dies vom Standpunkt der Hardwarekosten vollkommen unrealistisch.
Die Verwendung einer Multipliziereinheit zur Populationszählung ist gemäß einem Vorschlag versucht worden, wie in Fig. 3 gezeigt. Bei diesem Vorschlag ist jedoch die Multipliziereinheit eine Multipliziereinheit des ersten Typs, die nur eine Multiplizierschaltung mit einem Überlaufaddierer enthält, so daß dennoch das Problem einer schlechten Zählgeschwindigkeit vorhanden ist, wie oben erwähnt.
Wenn die Multipliziereinheit des ersten Typs, die in Fig. 3 gezeigt ist, im regulären Multiplikationsmodus arbeitet, arbeitet sie wie folgt: Multiplikationsdaten, die den Multiplikanden und den Multiplikator enthalten, die zum Beispiel in Binärschreibweise jeweils aus 8 Bytes bestehen, werden in einem Vektorregister (VR) 1 gesetzt; der Multiplikand in VR 1 wird über ein Register REG 1a zu einem Multiplikandenregister REG (CAND REG) 2a übertragen; der Multiplikator in VR 1 wird in ein Register REG 1b gesetzt und in vier Elemente geteilt, die jeweils aus 2 Bytes (16 Bits) bestehen; jedes Element von 2 Bytes wird in einen Dekodierer (DCDR) 3 gesetzt, in dem das Element auf der Grundlage des wohlbekannten Booth-Algorithmus in neun Arten von Schiebesteuersignalen dekodiert wird, welche neun Arten von Schiebesteuersignalen nachfolgend als "dekodierte Signale" bezeichnet werden; die dekodierten Signale von dem DCDR 3 werden als Multiplikator für den Multiplikanden, der in CAND REG 2a gesetzt ist, in ein Multiplikatorregister REG 2b gesetzt; der Multiplikand in CAND REG 2a und die dekodierten Signale in dem Multiplikator-REG 2b werden zu einem Vielfachgenerator (MG) 4 gesendet, in dem der Multiplikand so weit verschoben wird, wie durch die dekodierten Signale angegeben (so weit wie die bezeichneten Zahlen), welche Erzeugung in dem MG 4 als Vielfacherzeugung bezeichnet wird; die verschobenen Multiplikanden, die von dem MG 4 erzeugt wurden, werden zu einem ersten CSA (CSA(1)) 50 und einem zweiten CSA (CSA(2)) 51 gesendet, in denen die verschobenen Multiplikanden addiert werden, woraus sich eine Zwischensumme und ein Zwischenübertrag der Produkte des Multiplikanden und des relevanten Elementes des Multiplikators in Register REG 6a bzw. 6b ergibt; das obige Verfahren wird viermal wiederholt, um die Produkte des Multiplikanden und der vier Elemente zu erhalten; die Ausgaben von REG 6a und 6b werden zu einem ersten CPA (CPA(1)) 7 gesendet, in dem die vier Resultate bezüglich der vier Elemente addiert werden, woraus sich die Gesamtanzahl der "1"-Bits ergibt; und die Gesamtanzahl, nämlich ein Multiplikationsresultat, wird in einem Resultatsregister REG (ZR) 8 gesetzt.
Wenn der reguläre Multiplikationsmodus in der Multipliziereinheit des ersten Typs, die in Fig. 3 gezeigt ist, zu dem Populationszählmodus wechselt, führt die Multipliziereinheit des ersten Typs ein Populationszählen wie folgt aus: die numerischen Daten (die zum Beispiel in der Binärschreibweise aus 8 Bytes bestehen) für die Populationszählung werden in VR 1 gesetzt; die numerischen Daten für die Populationszählung werden zu REG 1b übertragen und in vier Elemente geteilt, die jeweils aus 2 Bytes bestehen; jedes 2- Byte-Element wird durch einen ersten Selektor (SEL(1)) 1c, der für die Multipliziereinheit des ersten Typs vorgesehen ist, von dem niedrigsten Element an selektiert, so daß das niedrigste Element zu einem vierten CSA (CSA(4)) 12 gesendet wird, der für die Multipliziereinheit des ersten Typs vorgesehen ist, in dem die Anzahl von "1"-Bits in jedem Element gezählt wird, woraus sich die Halbsumme (HS) von "1"-Bits in dem Element und der Halbübertrag (HC), der während des Verfahrens zum Erzeugen der HS vorgesehen wird, in einem HS-Register REG 12b bzw. einem HC-Register REG 12a ergeben; HS und HC, die in dem HS-REG 12b bzw. dem HC-REG 12a gesetzt sind, werden zu einem zweiten Selektor (SEL(2)) 41 gesendet, der in der Multipliziereinheit des ersten Typs neu vorgesehen ist, in dem HS und HC selektiert werden, um zu dem CSA(1) 50 und CSA(2) 51 gesendet zu werden, wobei die Ausgabe des MG 4 unterdrückt wird, so daß sie nicht zu dem CSA(1) 50 gesendet wird; dann werden die Anzahlen von "1"- Bits in allen vier Elementen addiert, wobei die Hardware und der Booth-Algorithmus des CSA(1) und des CSA(2) wiederholt, viermal, verwendet werden und auch ein Überlaufaddierer (SPA) 11 verwendet wird, zum Kompensieren des angehobenen Übertrags bei den niedrigen Einheiten, der während der Operation des CSA(1) 50 und CSA(2) 51 weggelassen wurde; und das Resultat der Populationszählung der gegebenen numerischen Daten wird an ZR 8 ausgegeben.
Wenn die Multipliziereinheit des ersten Typs zum Ausführen der Populationszählung verwendet wird, CSA(1) und CSA(2) verwendet werden, deren Operation so viele Male wiederholt wird, wie geteilte Elemente vorhanden sind, führt dies, wie oben erwähnt, beim Zusammenzählen aller "1"-Bits der numerischen Daten zu einer beträchtlichen Zeitvergeudung.
Zum Belegen der vorliegenden Erfindung werden unter Bezugnahme auf Fig. 4 bis 9 und 10 bis 12 erste bzw. zweite Ausführungsformen erläutert, bei denen zwei Arten der Multipliziereinheit des zweiten Typs verwendet werden, die jeweils vier Multiplizieruntereinheiten enthalten. In jeder Ausführungsform bestehen der Multiplikand und der Multiplikator jeweils aus 8 Bytes.
In der ersten Ausführungsform arbeitet die Multipliziereinheit des zweiten Typs im regulären Multiplikationsmodus nach solch einer Berechnungsform, daß der Multiplikand und der Multiplikator jeweils in zwei Elemente geteilt werden, so daß jedes Element aus 4 Bytes besteht. Der Multiplikand wird in ein oberes Multiplikandenelement (CU) und ein unteres Multiplikandenelement (CL) geteilt, und der Multiplikator wird in ein oberes Multiplikatorelement (IU) und ein unteres Multiplikatorelement (IL) geteilt. Dann wird die reguläre Multiplikation ausgeführt, indem die Elemente miteinander multipliziert werden, wie CU x IL, CL x IL, CU x IU, CL x IU, jeweilig unter Verwendung der vier Multiplizieruntereinheiten, und die multiplizierten Resultate von den Multiplizieruntereinheiten werden durch einen Übertragssicherungsaddierer (einen zweiten CSA (CSA(2')) und einen Übertragspropagationsaddierer (einen zweiten CPA (CPA(2')) addiert.
Fig. 4 ist ein Blockdiagramm einer zweiten Multipliziereinheit, wie sie in der ersten Ausführungsform verwendet wird. In Fig. 4 bezeichnen dieselben Bezugszeichen oder -zahlen wie in Fig. 3 dieselben oder ähnliche Funktionen oder Teile wie in Fig. 3. Wenn die Multipliziereinheit des zweiten Typs in Fig. 4 im regulären Multiplikationsmodus arbeitet, werden die Multiplikationen von CL x IU, CU x IL, CU x IU und CL x IL durch eine Multiplizieruntereinheit A, die nachfolgend einfach als "Untereinheit A" bezeichnet wird, eine Untereinheit B, eine Untereinheit C bzw. eine Untereinheit D ausgeführt. Im Populationszählmodus arbeiten die Untereinheiten A und B jedoch im Populationszählmodus und die Untereinheiten C und D im regulären Multiplikationsmodus. Deshalb sind nur die internen Blockdiagrammformen der Multiplizierschaltungen von Untereinheit A und C in Fig. 4 gezeigt, und andere Untereinheiten B und D sind außer Registern am Eingang und Ausgang der Untereinheiten leer gelassen worden.
Die reguläre Multiplikation wird wie folgt ausgeführt: Numerische Daten zum Ausführen der Multiplikation werden in VR 1 gesetzt; von VR 1 werden der 8-Byte-Multiplikand und der 8-Byte-Multiplikator zu dem Multiplikanden-REG 1a bzw. dem Multiplikator-REG 1b gesendet; der Multiplikand in REG 1a wird in CU-Daten und CL-Daten geteilt, und der Multiplikator in REG 1b wird in IU-Daten und IL-Daten geteilt, so daß jedes Element aus 4 Bytes besteht; die CL-Daten in REG 1a und die IU-Daten in REG 1b werden in REG 2a bzw. REG 2b in der Untereinheit A gesetzt; in der Untereinheit A werden die IU-Daten, die in REG 2b gesetzt sind, zu einem Dekodierer (DCDR) 3 gesendet, in dem die dekodierten Signale, die aus den IU-Daten erhalten werden, erzeugt und zu einem MG 4 gesendet werden; währenddessen werden die CL-Daten, die in REG 2a gesetzt sind, auch zu dem MG 4 gesendet, in dem die Vielfacherzeugung mit den CL-Daten und den dekodierten Signalen bezüglich der IU-Daten ausgeführt wird; die Ausgabedaten von MG 4 werden zu einem ersten CSA (CSA(1')) 5 und einem ersten CPA (CPA(1')) 6 gesendet, in denen die Ausgangsdaten von MG 4 gemäß dem Booth-Algorithmus addiert werden, woraus sich das Teilprodukt CL x IU in einem Resultatsregister REG 7a ergibt; in den Untereinheiten B, C und D werden jeweils ähnliche Operationen wie jene ausgeführt, die in der Untereinheit A erfolgen, wobei sich die Teilprodukte CU X IL, CU x IU bzw. CL x IL ergeben; diese Teilprodukte werden zu einem zweiten CSA (CSA(2')) 8 und einem zweiten CPA (CPA(2')) 9 gesendet, durch die das Endresultat der regulären Multiplikation erhalten wird; und das Endresultat wird durch einen Nachschieber 10 zur Normalisierung an ein Resultats-REG 11 ausgegeben. Somit kann in der Multipliziereinheit des zweiten Typs eine reguläre Multiplikation ausgeführt werden, indem bewirkt wird, daß die vier Untereinheiten gleichzeitig arbeiten, woraus im Vergleich zu der Operations zeit der Multipliziereinheit des ersten Typs eine Verkürzung der Operationszeit resultiert.
Wenn die Populationszählung unter Verwendung der Multipliziereinheit des zweiten Typs ausgeführt wird, die in Fig. 4 gezeigt ist, wechselt der Modus der Multipliziereinheit des zweiten Typs zu dem Populationszählmodus. In diesem Modus werden die numerischen 8-Byte-Daten zur Populationszählung, die nachfolgend als "8-Byte-Eingangsdaten" bezeichnet werden, VR 1 eingegeben, und die 8-Byte-Eingangsdaten werden in REG 1b gesetzt, worin die 8-Byte-Eingangsdaten gleichmäßig in zwei Elemente geteilt werden, die als IU-Daten und IL-Daten bezeichnet werden und die jeweils aus 4 Bytes bestehen. Die IU-Daten werden in den Untereinheiten A und C in REG 2b bzw. 2f gesetzt, und die IL-Daten werden in den Untereinheiten B und D in REG 2d bzw. 2h gesetzt.
In der Untereinheit A werden die IU-Daten zu einem dritten CSA (CSA(3')) 12 gesendet, der aus sechzehn Halbaddierern 12-0, 12-1, ---, 12-14 und 12-15 besteht, durch die sechzehn HC-Signale HC00, HC01, HC02, ---, HC14 und HC15 und sechzehn HS-Signale HS00, HS01, HS02, ---, HS14 und HS15 erzeugt werden und zu einem Selektor 41 gesendet werden, der aus einem ersten Selektor (SEL(1)) 41a und einem zweiten Selektor (SEL(2)) 41b besteht, wie in Fig. 4 und in Fig. 5 eingehend gezeigt. Die selektierten Daten von dem Selektor 41 werden zu dem CSA(1') 5 gesendet, der sechzehn Eingänge und sechs Stufen von Additionsschaltungen hat. Die Ausgabe von dem CSA(1') 5 wird zu dem CPA(1') 6 gesendet, in dem eine Übertrags- und eine Summenausgabe von dem CSA(1') 5 addiert werden. Die Resultate der Addition, die durch den CPA(1') erhalten werden, werden in REG 7a gesetzt.
REG 2a hat eine Funktion zum Ausgeben von Multiplikand- Bitsignalen und invertierten Signalen für die Multiplikand- Bitsignale im regulären Multiplikationsmodus. Die Ausgangssignale von REG 2a sind in Fig. 5 gezeigt, und in den Ausgangssignalen von REG 2a bezeichnet ein Plussignal, wie z. B. +R2-31, ein reguläres Bitsignal an der 31. Bitposition des REG 2a, und ein Minussignal, wie z. B. -R2-31, bezeichnet das invertierte Signal für das Bitsignal +R2-31.
Fig. 5 ist ein Schaltungsdiagramm, das die Schaltungsverbindungen zwischen dem CSA(3') 12, dem SEL(1) 41a, dem SEL(2) 41b, dem DCDR 3, dem MG 4 und dem CSA(1') 5 zeigt. In Fig. 5 bezeichnen dieselben Bezugszeichen oder -zahlen wie in Fig. 4 dieselben oder ähnliche Einheiten oder Teile wie in Fig. 4. REG 2b, das in FIG. 5 nicht gezeigt ist, hat 32 Bitpositionen zum Setzen der 4-Byte-IU-Daten, und die Bitsignale, die an den 32 Bitpositionen gesetzt sind, sind durch +R3-0, +R3-1, +R3-2, ---, +R3-30 und +R3-31 bezeichnet. Im Populationszählmodus werden die Bitsignale +R3-0 bis +R3-31, die in REG 2b gesetzt sind, zu dem CSA(3') 12 gesendet, der sechzehn Halbaddierer (HAs) 12-0, 12-1, 12-2, ---, 12-14 und 12-15 enthält. Zwei Bitsignale, die an den Bitpositionen (von REG 2b) gesetzt sind, die aneinandergrenzen, werden zum Ausführen der Halbaddition der zwei Bitsignale zu einem der sechzehn HAs gesendet. Zum Beispiel werden die Bitsignale +R3-0 und +R3-1, die in REG 2b an der Bitposition 0 und 1 gesetzt sind, die aneinandergrenzen, zu einem HA 12-0 in dem CSA(3') 12 gesendet. In jedem HA werden ein Halbsummen-(HS)-Signal und ein Halbübertrags-(HC)-Signal erzeugt, so daß 16 Paare von HS- und HC-Signalen von dem CSA(3') 12 ausgegeben werden und zu dem SEL(2) 41b bzw. SEL(1) 41a gesendet werden. Zum Beispiel wird ein Paar von Signalen +HS00 und +HC00 von dem HA 12-0 ausgegeben und zu dem SEL(2) 41b bzw. dem SEL(1) 41a gesendet, wie in Fig. 5 gezeigt.
Alle 65 dekodierten Signale +G1-POS1, +G1-NEG1, +G1- POS2, +G1-NEG2, ---, +G16-POS2, +G16-NEG2 und +G17-POS1, die von dem DCDR 3 ausgegeben werden, werden im Populationszählmodus auf Bit "0" gesetzt. Demzufolge sind im Populationszählmodus die Eingangssignale für MG 4 alle auf Bit "0" gesetzt, so daß die Ausgangssignale von MG 4 auch Bit "0" werden, wie aus Fig. 6 und 7 ersichtlich ist. Fig. 6 ist ein Blockdiagramm, das die Verdrahtungsverbindung zwischen MG 4 und SEL 41a zeigt, während Fig. 7 die Verdrahtungsverbindung zwischen MG 4 und SEL 41b zeigt. In Fig. 7 bezeichnet dasselbe Bezugszeichen oder dieselbe Bezugszahl wie in Fig. 5 oder 6 dieselbe Einheit oder dasselbe Signal wie in Fig. 5 oder 6. Wie in Fig. 6 und 7 gezeigt, werden die Ausgangssignale +G2-30, +G3-30, ---, +G16-30 und +G17-30 von MG 4 zu SEL(1) 41a gesendet, werden die Ausgangssignale +G2-31, +G3- 31, ---, +G16-31 und +G17-31 von MG 4 zu SEL(2) gesendet, und werden die anderen Ausgangssignale von MG 4 direkt zu dem CSA(1') gesendet; dabei bezeichnen die Zahlen 30 und 31 die Bitpositionen im CSA(1'), die später unter Bezugnahme auf Fig. 8 erläutert werden. Die Ausgangssignale von MG 4, von denen jedes die Zahl 30 hat, werden durch UND-Schaltungen in SEL(1) 41a im Populationszählmodus unterdrückt, so daß nur die Ausgangssignale +HC-00, +HC-01, ---, +HC-14 und +HC-15 von CSA(3') 12 von SEL(1) 41a als Eingangssignale +G2-30-S, +G3-30-S, ---, +G16-30-S und +G17-30-S an CSA(1') ausgegeben werden. Auf dieselbe Weise werden die Ausgangssignale von MG 4, von denen jedes die Zahl 31 hat, durch UND-Schaltungen in SEL(2) 41b im Populationszählmodus unterdrückt, so daß nur die Ausgangssignale +HS-00, +HS-01, ---, +HS-14 und +HS-15 von CSA(3') 12 von SEL(2) 41b als Eingangssignale +G2-31-S, +G3-31-S, ---, +G16-31-S und +G17- 31-S an CSA(1') 5 ausgegeben werden. Indessen werden im regulären Multiplikationsmodus die Ausgangssignale von CSA(3') 12 in SEL(1) und SEL(2) unterdrückt, und die Ausgangssignale von MG 4 werden durch SEL(1) 41a und SEL(2) 41b direkt zu CSA(1') gesendet, wie aus Fig. 5, 6 und 7 hervorgeht.
Wieder im Populationszählmodus werden die Signale bezüglich der HS- und HC-Signale der IU-Daten dem CSA(1') 5 eingegeben, in dem die Eingangssignale, die jeweils die Zahl 30, zum Beispiel +G2-30-S, und die Zahl 31 haben, zum Beispiel +G2-31-S, an eine bestimmte Bitposition von sechzehn Bitreihen gesetzt werden, die in Fig. 8 beschrieben sind.
Fig. 8 ist ein Diagramm, das schematisch eine Additionsweise zeigt, die zur Multiplikation in dem CSA(1') verwendet wird. Das Diagramm entspricht einem Teilprodukt von 4 Bytes x 4 Bytes, das im regulären Multiplikationsmodus ausgeführt wird. Eine Zahl von 32 Bits wird im regulären Multiplikationsmodus in jeder Reihe gesetzt, die nachfolgend als "Bitreihe" bezeichnet wird; jedoch sind im Populationszählmodus alle Positionen mit Bits "0" belegt, außer die schraffierten Positionen, da im Populationszählmodus alle Eingangssignale für den CSA(1') 5 vom MG 4 auf Bit "0" gesetzt sind, wie zuvor erklärt.
Zum Beispiel wird das Eingangsübertragssignal +G2-30-S für den CSA(1') 5 in der Bitreihe G2 an einer Bitposition angeordnet, die der 30. Bitposition in einer 64-Bit-Übertragszahlzeile entspricht, die in Fig. 8 unten gezeigt ist; das Eingangssummensignal +G2-31-S für den CSA(1') 5, das dem Übertragssignal +G2-30-S zugeordnet ist, wird in der Bitreihe G2 an einer Bitposition angeordnet, die der 31. Bitposition in der oben gezeigten 64-Bit-Zahlzeile entspricht; das Eingangsübertragssignal +G3-30-S für den CSA(1') 5 wird in der Bitreihe G3 an einer Bitposition angeordnet, die der 30. Position in der 64-Bit-Zahlzeile entspricht; das Eingangssummensignal +G3-31-S für den CSA(1') 5 wird in der Bitreihe G3 an der 31. Bitposition in der 64-Bit-Zahlzeile angeordnet; und so weiter.
Demzufolge sind die Übertrags- und Summendaten, die jeweilig an der 30. und 31. Position von jeder Bitreihe angeordnet sind, vertikal ausgerichtet. Wie aus Fig. 8 hervorgeht, werden im Populationszählmodus keine G1-Bitreihen verwendet.
Die Bitzahlen der Summe und des Übertrags, die in den Bitreihen G2 bis G17 gesetzt sind, werden in dem CSA(1') 5 und CPA(1') 6 addiert. Das addierte Resultat wird in der 64- Bit-Zahlzeile unten im Diagramm an der 26. bis 31. Bitposition angeordnet, die schraffiert sind. Das Resultat stellt die Bitzahl von "1"-Bits in den 4-Byte-IU-Daten dar, die in REG 2b in der Untereinheit A gesetzt wurden. Das Resultat wird zu REG 7a gesendet.
Da die 8-Byte-Eingangsdaten, die in REG 1b gesetzt sind, gleichmäßig in zwei Elemente geteilt sind, reichen zwei Untereinheiten aus, um das Populationszählen auszuführen. Deshalb werden in dieser Ausführungsform die Untereinheiten A und B in beiden Modi verwendet, im Populationszählmodus und im regulären Multiplikationsmodus, und andere Untereinheiten C und D werden nur im regulären Multiplikationsmodus verwendet. Dementsprechend ist die Hardware und die Funktion der Untereinheit B dieselbe wie jene der Untereinheit A, und die Hardware und die Funktion für die Untereinheiten C und D unterscheiden sich von jenen für die Untereinheiten A und B.
Die Untereinheiten C und D haben miteinander dieselbe Funktion und Hardware, außer daß der Multiplikand und der Multiplikator in den Untereinheiten verschieden sind. Die Untereinheit C hat im regulären Multiplikationsmodus die Funktion zum Ausführen der regulären Multiplikation, indem die CU-Daten und die IU-Daten multipliziert werden, und im Populationszählmodus zum Erzeugen von lauter Bits "0". Deshalb hat die Untereinheit C die Hardware, wie z. B. ein REG 2e, welches dieselbe Funktion wie REG 2a in der Untereinheit A hat, aber keinen CSA(3'), wie CSA(3') 12 in der Untereinheit A, und keinen SEL, wie SEL 41 in der Untereinheit A. Da REG 2e dieselbe Funktion wie REG 2a in der Untereinheit A hat, wie oben erwähnt, werden von REG 2e im regulären Multiplikationsmodus die regulären CU-Daten ausgegeben und im Populationszählmodus lauter Bit-"0"- Signale ausgegeben, so daß von einem REG 7c an den CSA(2') lauter Bit-"0"-Signale ausgegeben werden. Das Blockdiagramm für die Untereinheit C ist in Fig. 4 gezeigt. Da das Blockdiagramm für die Untereinheit D gleich jenem für die Untereinheit C ist, ist das Blockdiagramm der Untereinheit D in Fig. 4 weggelassen worden.
In der Untereinheit B wird im Populationszählmodus das addierte Resultat an der 26. bis 31. Bitposition, die schraffiert sind, in der 64-Bit-Zahlzeile unten im Diagramm angeordnet. Dabei werden die IL-Daten von REG 1b zu einem REG 2d in der Untereinheit B gesendet, wie aus Fig. 4 hervorgeht.
Die zwei Resultate, die von Untereinheiten A und B ausgegeben werden, werden durch den CSA(2') 8 addiert, wie in Fig. 4 gezeigt. Die Ausgabe des CSA(2') 8 wird zu dem CPA(2') 9 gesendet und in ihm addiert. Die Resultate des CPA(2') 9 werden durch den Nachschieber 10 nachgeschoben und in REG 11 gesetzt, wobei die Resultatsdaten an die Positionen für die oberen 8 Bytes gesetzt werden.
Fig. 9 zeigt die Addierweise der Operationsergebnisse der vier Untereinheiten A, B, C und D, die durch den CSA(2') 8 und den CPA(2') 9 ausgeführt wird. Ein Zeichen "R2 CAND" bezeichnet den Multiplikanden, der aus den CU-Daten und den CL-Daten besteht, die in REG(R2) 1a gesetzt sind, und ein Zeichen "R3 IER" bezeichnet den Multiplikator, der aus den IU-Daten und den IL-Daten besteht, die in REG(R3) 1b gesetzt sind. Im regulären Multiplikationsmodus wird die Addition der Teilprodukte CLxIL, CUxIL, CLxIU und CUxIU durch CSA(2') 8 und CPA(2') 9 ausgeführt, wie in Fig. 9 gezeigt. Dabei werden die Teilprodukte CLxIL, CUxIL, CLxIU und CUxIU von Untereinheiten D, B, A bzw. C erhalten. Im Populationszählmodus werden die Teilprodukte jedoch nur von den Untereinheiten A und B erhalten, und ferner befinden sich die Bit-"1"-Resultate der IU-Daten, die durch die Untereinheit A erhalten wurden, und jene der IL-Daten, die durch die Untereinheit B erhalten wurden, beide an derselben Bitposition, wie durch die schraffierten Abschnitte in Fig. 9 gezeigt. Deshalb kann das Resultat der Addition erhalten werden, indem der schraffierte Abschnitt, der durch IL und IU bezeichnet ist, unter Verwendung von CSA(2') 8 und CPA(2') 9 einfach addiert wird, wie im regulären Multiplikationsmodus. Die Daten, die an den oberen 8-Byte-Positionen enthalten sind, werden durch den Nachschieber 10 zu REG 11 gesendet.
Die Ausführung der Populationszählanweisung wird folgendermaßen zusammengefaßt:
1) Die 8-Byte-Eingangsdaten für das Populationszählen werden von VR 1 in REG 1b gesetzt;
2) Die oberen 4-Byte-Daten (IU-Daten) der 8-Byte- Eingangsdaten, die in REG 1b gesetzt sind, werden in REG 2b der Untereinheit A gesetzt, und die unteren 4-Byte-Daten (IL-Daten) der 8-Byte-Eingangsdaten in REG 1b werden in REG 2d der Untereinheit B gesetzt;
3) Die geteilten 4-Byte-(32 Bit)-Daten (IU- und IL- Daten) werden weiter in 16 Paare von zwei Bits geteilt, und eine 16-Bit-Summe und ein Übertrag werden durch 16 Halbaddierer erhalten, wobei der Weg von dem REG 2b zu dem DCDR 3 unterdrückt wird;
4) Die Ausgabe der Halbaddierer wird über den Selektor 41 dem CSA(1') 5 eingegeben;
5) Die Anzahl von "1"-Bits in den IU-Daten wird durch Addition erhalten, die durch CSA(1') 5 und CPA(1') 6 in der Untereinheit A ausgeführt wird;
6) Die Anzahl von "1"-Bits in den IL-Daten wird gleichzeitig in der Untereinheit B auf dieselbe Weise wie in der Untereinheit A erhalten;
7) Die Anzahl von "1"-Bits in den IU-Daten und die Anzahl in den IL-Daten wird in REG 7a in der Untereinheit A und in REG 7b in der Untereinheit B gesetzt; und
8) Die Daten in REG 7a und 7b werden durch CSA(2') 8 und CPA(2') 9 addiert, wobei die Stellenwerte von jeweiligen Bits berücksichtigt werden.
Als nächstes wird die zweite Ausführungsform der vorliegenden Erfindung erläutert.
FIG. 10 zeigt ein Blockdiagramm einer zweiten Multipliziereinheit, wie sie in der zweiten Ausführungsform der vorliegenden Erfindung verwendet wird und die vier Multiplizieruntereinheiten 16-A, 16-B, 16-C und 16-D enthält, die miteinander denselben Aufbau haben und gemäß einer Berechnungsform arbeiten, die sich von jener bei der ersten Ausführungsform unterscheidet. In Fig. 10 werden der Multiplikand und der Multiplikator in Registern REG 14 bzw. 15 gespeichert, und die Ausgabe der vier Untereinheiten wird durch einen CSA 17 und einen CPA 18 addiert und über einen Nachschieber SFT 19 zu einem Register REG 20 gesendet. Es wird nur die Untereinheit 16-A erläutert, da die Untereinheiten 16-B, 16-C und 16-D bezüglich ihrer Konstruktion und Funktion dieselben wie die Untereinheit 16-A sind.
In der zweiten Ausführungsform wird der 8-Byte-Multiplikator in vier 2-Byte-Elemente geteilt, die zu den Untereinheiten 16-A, 16-B, 16-C bzw. 16-D gesendet werden. Die Operation zur Multiplikation und Populationszählung in der Untereinheit 16-A ist im wesentlichen dieselbe wie in der Untereinheit A der ersten Ausführungsform, außer daß die Daten, die in dem Register REG 21 und in dem Register REG 22 gesetzt sind, 8-Byte- bzw. 2-Byte-Daten sind.
Im Populationszählmodus wird ein 8-Byte-Multiplikand, der in dem Register REG 14 gespeichert ist, zu einem Register REG 21 in der Untereinheit 16-A und zu drei anderen Registern, die dieselbe Funktion wie REG 21 haben, in den drei Untereinheiten 16-B, 16-C bzw. 16-D gesendet. Indessen werden die 8-Byte-Eingangsdaten zur Populationszählung in REG 15 auf einmal gespeichert, anstelle des 8-Byte-Multiplikators, und zur Populationszählung gleichmäßig in vier Elemente geteilt, die jeweils aus 2-Byte-Daten bestehen. Jedes 2-Byte-Datum wird zu einem Register REG 22 in der Untereinheit 16-A und zu drei anderen Registern, die dieselbe Funktion wie REG 22 haben, in den Untereinheiten 16-B, 16-C und 16-D gesendet. Das 2-Byte-Datum, das in REG 22 gesetzt ist, wird zu einem dritten CSA (CSA(3")) 27 gesendet. Ein Halbübertrag (HC) 27a und eine Halbsumme (HS) 27b, die von dem CSA (3") 27 ausgegeben werden, werden durch einen SEL 32 zu einem ersten CSA (CSA(1")) 25 gesendet, der neun Eingangsanschlüsse und vier Additionsstufen hat. Eine Summen- und Übertragsausgabe von dem CSA (1") 25 werden durch einen ersten CPA (CPA(1")) 26 addiert. Das Resultat der Addition von dem CPA(1") wird in einem REG 30-A gesetzt.
Dieselbe Operation wie in der Untereinheit 16-A wird jeweilig in den Untereinheiten 16-B, 16-C und 16-D gleichzeitig ausgeführt. Die vier Resultate, die durch die Untereinheiten 16-A, 16-B, 16-C und 16-D erhalten werden, werden durch einen zweiten CSA (CSA(2")) 17 und einen zweiten CPA (CPA(2")) 18 addiert, um ein Gesamtresultat der 8-Byte- Eingangsdaten zu erhalten. Die Ausgabe von dem CPA(2") 18 wird durch einen Nachschieber 19 in einem Register REG 20 gesetzt.
Fig. 11 zeigt schematisch eine Additionsweise in dem CSA(1") 25 in der Untereinheit 16-A, um die Vollsumme und den Vollübertrag zu erhalten. In der Untereinheit 16-A werden das Bitsignal des Übertrags durch einen ersten Selektor, der ein Teil des SEL 32 ist und in Fig. 10 nicht gezeigt ist, und das Bitsignal der Summe durch einen zweiten Selektor, der ein anderer Teil des Selektors 32 ist, einem Anschluß G2, der nicht gezeigt ist, des CSA(1") 25 eingegeben, und sie belegen die 48. bzw. 49. Bitposition einer 64- Bit-Zahlreihe. Die ähnlichen Bitsignale, die einem Anschluß G3 des CSA(1") 25 eingegeben werden, belegen die 50. und 51. Bitposition, und so weiter. Jene Eingaben für einen Anschluß G9 des CSA(1") 25 belegen die 62. und 63. Bitposition. In Fig. 11 ist dieselbe Addition in den Untereinheiten 16-B, 16-C und 16-D zusammen gezeigt.
Die Additionsresultate des Übertrags und der Summe durch den CSA(1") 25 befinden sich an den 59. bis 63. Positionen, wie unten im Diagramm gezeigt. Auf dieselbe Weise befindet sich die Position der Daten des Übertrags und der Summe in den Untereinheiten 16-B, 16-C und 16-D an den 43. bis 47., an den 27. bis 31. bzw. an den 11. bis 15., wie unten im Diagramm in Fig. 11 gezeigt. Die Vollsumme und der Vollübertrag, die in dem CSA(1") 25 erhalten werden und unten gezeigt sind, werden durch den CPA(1") 26 addiert, um die Anzahl von "1"en zu erhalten, die in dem ersten Viertel des Multiplikators vorhanden sind. Dann werden die Daten in REG 30-A gesetzt.
Fig. 12 zeigt schematisch eine Additionsweise in CSA(2") 17 und CPA(2") 18, um die Gesamtanzahl von "1"-Bits zu erhalten, die in dem Multiplikator vorhanden sind. Jedes Datum von den vier REG 30-A, 30-B, 30-C und 30-D wird als Addition von Teilprodukten addiert. Die Daten von REG 30-A, 30-B, 30-C und 30-D sind 10 Bytes. Die Anzahl von "1"en, die in einem Viertel des Multiplikators in REG 15 vorhanden ist, ist in den schraffierten Bits von jedem Datum gesetzt. Diese vier Daten sind in vier parallelen Reihen, die um 2 Bytes verschoben sind, vertikal ausgerichtet, wie in Fig. 12 gezeigt. So sind die resultierenden Daten 16 Bytes. Die unteren 8 Bytes nicht beachtend, ergibt die obere Hälfte der 16 Bytes die resultierenden 8-Byte-Daten, in denen die Gesamtanzahl von "1"-Bits, die in dem Multiplikator vorhanden ist, in den letzten sieben Bits gesetzt ist.
In einer Ausführungsform der vorliegenden Erfindung wird das Populationszählen unter Verwendung einer Multipliziereinheit in einem Computersystem ausgeführt, die eine Vielzahl Von Multiplizieruntereinheiten zum gleichzeitigen Ausführen von Teilmultiplikationen zwischen Elementen, die durch Teilen von Multiplikandendaten und Multiplikatordaten erhalten wurden, im regulären Multiplikationsmodus enthält. Im Populationszählmodus werden Eingangsdaten für das Populationszählen in Populationszählelemente statt in Multiplikatordaten geteilt, und Populationszählungen für die Elemente werden gleichzeitig ausgeführt, indem die Multiplizieruntereinheiten verwendet werden, wobei Teilzähldaten der Populationszählelemente erzeugt werden, und die Teilzähldaten werden zu einem Paar gesendet, das einen Übertragssicherungsaddierer und einen Übertragsausbreitungsaddierer umfaßt, wodurch ein Populationszählresultat für die Eingangsdaten erhalten und ausgegeben wird.

Claims

1. Eine Multipliziereinheit, die in einem Computersystem vorgesehen ist, zum Ausführen einer Multiplikation von Multiplikandendaten und Multiplikatordaten in einem Multiplikationsmodus und zum Ausführen eines Populationszählens von Populationszähleingangsdaten in einem Populationszählmodus, welche Multipliziereinheit umfaßt:

ein Mittel (1, 1a; 14) zum Registrieren der Multiplikandendaten im Multiplikationsmodus;

ein Mittel (1, 1b; 15) zum Registrieren und gleichmäßigen Teilen der Multiplikatordaten in eine Vielzahl von Multiplikatorelementen im Multiplikationsmodus, und zum Registrieren und gleichmäßigen Teilen der Populationszähldaten in eine Vielzahl von Populationszählelementen mit derselben Anzahl wie die Multiplikatorelemente im Populationszählmodus;

eine Vielzahl von Multiplizieruntereinheiten (A, B, C, D; 16-A, 16-B, 16-C, 16-D) zum Ausführen von gleichzeitigen Teilmultiplikationen zwischen dem Multiplikanden und den Multiplikatorelementen im Multiplikationsmodus, wobei Teilproduktdaten der Teilmultiplikationen erzeugt werden, und zum Ausführen von gleichzeitigen Teilpopulationszählungen bei den Populationszählelementen im Populationszählmodus, wobei Teilzähldaten der Teilpopulationszählungen erzeugt werden, von welchen Multiplizieruntereinheiten (A, B, C, D; 16-A, 16-B, 16-C, 16-D) eine Vielzahl, die in der Anzahl den Populationszählelementen gleich ist, Multiplizieruntereinheiten des ersten Typs (A, B; 16-A, 16-B, 16-C, 16-D) umf aßt, von welchen Multiplizieruntereinheiten des ersten Typs jede umfaßt:

ein erstes Untereinheitsregister (2b, 2d; 22) zum Setzen eines der Multiplikatorelemente im Multiplikationsmodus, und zum Setzen eines der Populationszählelemente im Populationszählmodus;

einen zweiten Übertragssicherungsaddierer (12; 27) zum Zählen der Anzahl von "1"-Datenbits in dem Populationszählelement, das in dem genannten ersten Untereinheitsregister (2b, 2d; 22) registriert ist, wobei immer zwei Datensignale des Populationszählelementes gleichzeitig eingegeben werden, welche zwei Datensignale die sind, die jeweilig an zwei Registrierpositionen des genannten ersten Untereinheitsregisters (2b, 2d; 22), die aneinandergrenzen, registriert worden sind, und elementare Summen- und Übertragsdaten des Populationszählelementes ausgegeben werden;

ein zweites Untereinheitsregister (2a, 2c; 21) zum Setzen und Ausgeben der Multiplikandendaten im Multiplikationsmodus, und zum Erzeugen und Ausgeben von lauter "0"-Datenbits im Populationszählmodus;

einen Dekodierer (3; 23) zum Ausgeben von dekodierten Signalen, die zum Multiplizieren der Multiplikandendaten und des Multiplikatorelementes erforderlich sind, im Multiplikationsmodus, wobei das Multiplikatorelement von dem genannten ersten Untereinheitsregister (2b, 2d; 22) eingegeben wird, und zum Erzeugen und Ausgeben von lauter "0"-Datenbits im Populationszählmodus;

einen Vielfachgenerator (4; 24) zum Erzeugen und Ausgeben von verschobenen Daten durch Kombinieren der Multiplikandendaten von dem genannten zweiten Untereinheitsregister (2a, 2c; 21) und der dekodierten Signale von dem genannten Dekodierer (3; 23) im Multiplikationsmodus, und zum Erzeugen und Ausgeben von lauter "0"-Datenbits im Populationszählmodus;

ein Paar eines ersten Übertragssicherungsaddierers (5; 25) und eines ersten Übertragspropagationsaddierers (6; 26) zum Ausgeben der Teilproduktdaten der Teilmultiplikation der Multiplikandendaten und des Multiplikatorelementes im Multiplikationsmodus, wobei die verschobenen Daten von dem genannten Vielfachgenerator (4; 24) addiert werden, und zum Ausgeben der Teilzähldaten der Anzahl von "1"-Datenbits im Populationszählelement im Populationszählmodus, wobei die elementaren Summen- und Übertragsdaten von dem genannten zweiten Übertragssicherungsaddierer (12; 27) addiert werden; und

ein Selektormittel (41; 32) zum Selektieren der verschobenen Daten von dem genannten Vielfachgenerator (4; 24) und der elementaren Summen- und Übertragsdaten von dem genannten zweiten Übertragssicherungsaddierer (12; 27), um gemäß dem Multiplikationsmodus bzw. Populationszählmodus eine Menge der genannten Daten zu dem genannten Paar eines ersten Übertragssicherungsaddierers (5; 25) und eines ersten Übertragspropagationsaddierers (6; 26) zu senden;

und welche Multipliziereinheit auch umfaßt:

ein Mittel (8, 9; 17, 18) zum Addieren der genannten Teilproduktdaten von den genannten Multiplizieruntereinheiten (A, B, C, D; 16-A, 16-B, 16-C, 16-D) im Multiplikationsmodus, wobei ein Multiplikationsresultat der Multiplikandendaten und der Multiplikatordaten ausgegeben wird, und zum Addieren der genannten Teilzähldaten der Teilpopulationszählungen von den genannten Multiplizieruntereinheiten (A, B, C, D; 16-A, 16-B, 16-C, 16-D) im Populationszählmodus, wobei ein Populationszählresultat der Populationszähleingangsdaten ausgegeben wird.

2. Eine Multipliziereinheit nach Anspruch 1, bei der das genannte Mittel (1, 1a) zum Registrieren der Multiplikandendaten im Multiplikationsmodus auch die Multiplikandendaten im Multiplikationsmodus gleichmäßig in eine Vielzahl von Multiplikandenelementen teilt, und die genannten Multiplizieruntereinheiten im Multiplikationsmodus Teilmultiplikationen zwischen den Multiplikandenelementen und den Multiplikatorelementen gleichzeitig ausführen, wobei Teilproduktdaten der Teilmultiplikationen erzeugt werden, in jeder genannten Multiplizieruntereinheit des ersten Typs das zweite Untereinheitsregister (2a, 2c) somit im Multiplikationsmodus eines der Multiplikandenelemente setzt und ausgibt, der Dekodierer (3) dekodierte Signale ausgibt, die zum Multiplizieren des Multiplikandenelementes und des Multiplikatorelementes erforderlich sind, der Vielfachgenerator (4) im Multiplikationsmodus verschobene Daten erzeugt und ausgibt, indem die Multiplikandenelementdaten von dem genannten zweiten Untereinheitsregister (2a, 2c; 21) und die dekodierten Signale von dem Dekodierer (3; 23) kombiniert werden, und das Paar des ersten Übertragssicherungsaddierers (5) und des ersten Übertragspropagationsaddierers (6) im Multiplikationsmodus die Teilproduktdaten der Teilmultiplikation der Multiplikandenelementdaten und des Multiplikatorelementes ausgibt, wobei die verschobenen Daten von dem genannten Vielfachgenerator (4) addiert werden.

3. Eine Multipliziereinheit nach Anspruch 1 oder 2, bei der von den Multiplizieruntereinheiten (A, B, C, D) eine weitere Vielzahl Multiplizieruntereinheiten des zweiten Typs (C, D) in einer Anzahl umfaßt, die erhalten wird, indem die Anzahl der Multiplizieruntereinheiten des ersten Typs (A, B) von einer Anzahl subtrahiert wird, die erforderlich ist, um die Teilmultiplikation zwischen dem Multiplikanden, oder den Multiplikandenelementen, und den Multiplikatorelementen auszuführen, von welchen Multiplizieruntereinheiten des zweiten Typs jede umfaßt:

ein drittes Untereinheitsregister (2f, 2h) zum Setzen und Ausgeben eines der Multiplikatorelemente im Multiplikationsmodus;

ein viertes Untereinheitsregister (2e, 2g) zum Setzen und Ausgeben der Multiplikandendaten, oder eines der Multiplikandenelemente, im Multiplikationsmodus, und zum Erzeugen und Ausgeben von lauter "0"-Datenbits im Populationszählmodus; und

einen Dekodierer (3) zum Ausgeben von dekodierten Signalen im Multiplikationsmodus, die zum Multiplizieren der Multiplikandendaten, oder des Multiplikandenelementes, und des Multiplikatorelementes erforderlich sind, wobei das Multiplikatorelement von dem genannten dritten Untere inheitsregister eingegeben wird, und zum Erzeugen und Ausgeben von lauter "0"-Datenbits im Populationszählmodus.