PatentDe  


Dokumentenidentifikation DE3882772T2 10.02.1994
EP-Veröffentlichungsnummer 0286125
Titel Vektorprozessor angepasst zum Sortieren von Vektordaten.
Anmelder Hitachi, Ltd., Tokio/Tokyo, JP
Erfinder Kojima, Keiji, Kodaira-shi Tokyo, JP
Vertreter Strehl, P., Dipl.-Ing. Dipl.-Wirtsch.-Ing.; Schübel-Hopf, U., Dipl.-Chem. Dr.rer.nat.; Groening, H., Dipl.-Ing.; Lang, G., Dipl.-Phys.; Rasch, M., Dipl.-Ing. Univ., Pat.-Anwälte, 80538 München
DE-Aktenzeichen 3882772
Vertragsstaaten DE, GB
Sprache des Dokument En
EP-Anmeldetag 08.04.1988
EP-Aktenzeichen 881056428
EP-Offenlegungsdatum 12.10.1988
EP date of grant 04.08.1993
Veröffentlichungstag im Patentblatt 10.02.1994
IPC-Hauptklasse G06F 7/24
IPC-Nebenklasse G06F 15/76   

Beschreibung[de]
HINTERGRUND DER ERFINDUNG

Die Erfindung betrifft einen Vektorprozessor, spezieller einen Vektorprozessor, wie er zum Verarbeiten von Symbolen, wie zum Sortieren von Symbolen, geeignet ist.

Bisher ist eine Vorrichtung bekannt, die aus speziell konstruierter Hardware besteht, um Datensequenzen mit hoher Geschwindigkeit gestützt auf Vektorverarbeitung zu sortieren, wie in EP-A-0 149 213 offenbart. Diese Vorrichtung ermöglicht es, Mischprodukte in Form von Vektoren zu sortieren, die bisher nicht in der Form von Vektoren behandelt werden konnten.

Beim Stand der Technik wurde jedoch Fällen keine Beachtung geschenkt, bei denen zu sortierende Datensequenzen vorsortiert sind, z.B. solche, bei denen nahezu alle Eingangsdatensequenzen bereits ab dem erstenmal sortiert waren. Dieses Problem wird nun kurz unter Bezugnahme auf Zeichnungen erläutert.

Fig. 10 ist ein Diagramm, das schematisch das Sortierverfahren unter Verwendung eines herkömmlichen Vektorprozessors veranschaulicht. Wenn die zu sortierenden Eingangsvektorelemente aus 2, 5, 7, 4, 1, 6, 8 und 3 bestehen, werden gemäß diesem Verfahren die Vektorelemente in der Mitte in zwei Vektoren aufgeteilt, d.h. X = (2, 5, 7, 4) und Y (1, 6, 8, 3). Danach wird, gestützt auf die Voraussetzung, daß die Daten in den Vektoren X und Y zufällig angeordnet sind, die Länge von Elementen in ansteigender Reihenfolge in jeder der Vektoren als 1 bezeichnet, um beim Ausführen der Mischsortieranweisung als Parameter zu dienen, und die Daten werden Stück für Stück ausgehend vom Anfang der Vektoren X und Y gemischt. Der Mischvorgang steht für eine Verarbeitung, bei der die Elemente von X und Y miteinander verglichen werden und das Kleinere (oder das Größere) erzeugt wird. Im Ergebnis werden Vektoren 1, 2, 5, 6, 7, 8, 3 und 4 erzeugt, wobei zwei aufeinanderfolgende Elemente sortiert sind. Daher werden die Vektoren erneut in einen Vektor X = (1, 2, 5, 6) und einen Vektor Y = (7, 8, 3, 4) unterteilt. Die Mischsortieranweisung gibt nun an, daß die Elemente in ansteigender Reihenfolge in jedem der Vektoren die Länge 2 haben, und dann werden zwei aufeinanderfolgende Elemente gemischt. Im Ergebnis werden Vektoren 1, 2, 7, 8, 3, 4, 5 und 6 erzeugt, in denen vier aufeinanderfolgende Elemente sortiert sind. Die Vektoren werden erneut in X = (1, 2, 7, 8) und Y = (3, 4, 5, 6) unterteilt. Dieses Mal werden die Elemente mit einer Länge der Elemente in ansteigender Reihenfolge von 4 gemischt, und der Sortiervorgang für die gesamten Elemente wird abgeschlossen.

Bei diesem System ist es erlaubt, nur den Elementen mit ansteigender Reihenfolge in den Vektoren eine vorbestimmte Länge zuzuordnen, es ist jedoch nicht erlaubt, Vektoren zu verarbeiten, die aus Elementen mit verschiedenen Längen bestehen. D.h., daß die Länge der Elemente mit ansteigender Reihenfolge für jeden Mischvorgang verdoppelt wird, d.h., daß die Länge mit jedem Mischvorgang auf 1, 2, 4, --- zunimmt. Wenn die Länge des Eingangsvektors N ist, muß daher der Mischvorgang log&sub2; N-mal ausgeführt werden. In diesem Fall muß der Mischvorgang log&sub2; 8 = 3-mal vorgenommen werden. Dieses System beruht auf der Annahme, daß die Eingangsvektoren zufällig geordnet sind. Beim praktischen Eingeben von Daten sind die Daten jedoch in vielen Fällen vorsortiert. Z.B. können die Daten schon beim erstenmal beinahe in ansteigender Reihenfolge angeordnet sein. Dieses System ist jedoch nicht dazu in der Lage, die Beschaffenheit derartiger Datenelemente zu nutzen.

EP-A-0 184 828 beschreibt einen Vektorprozessor mit den Merkmalen im ersten Teil von Anspruch 1. Ähnlich wie beim Stand der Technik, auf den oben Bezug genommen wurde, verwendet auch dieser Vektorprozessor ein Misch/Sortier-Verfahren, das auf dem Mischen zu sortierender Datenelemente beruht, und das in Pipeline-Weise ausgeführt wird.

Ein bekanntes Verfahren, das an einen skalaren Prozessor angepaßt ist, besteht darin, daß die Eigenschaften von Datenelementen verwendet werden, um den Wirkungsgrad zu erhöhen (siehe z.B. E. E. Knuth: "The Art of Computer Programming, Vol. 3, Sorting and Searching", Addison-Wesley (1973)).

Durch Mischen der Datenelemente mit ansteigender Reihenfolge mit verschiedenen Längen, oder der Datenelemente mit absteigender Reihenfolge mit verschiedenen Längen in den Eingangsdatenelementen wird es ermöglicht, das Sortieren mit einer verringerten Anzahl von Mischvorgängen im Vergleich zum Mischen bei einem herkömmlichen skalaren Prozessor auszuführen.

Die oben angegebene Literaturstelle offenbart jedoch nicht, wie das obige Verfahren an einen Vektorprozessor angepaßt werden könnte.

ZUSAMMENFASSUNG DER ERFINDUNG

Es ist die Aufgabe der Erfindung, einen Vektorprozessor anzugeben, der zum Verarbeiten von Vektoren mit hoher Geschwindigkeit geeignet ist, die aus Elementen mit verschiedenen Längen in aufsteigender oder absteigender Reihenfolge bestehen.

Diese Aufgabe wird durch den durch Anspruch 1 definierten Vektorprozessor und durch das durch Anspruch 9 definierte Verfahren gelöst.

Gemäß der Erfindung werden Vektorelemente synchron mit der Zuführung von Vektorelementen zur Arithmetikeinheit mit den Vektorelementen vorangehenden Vektorelementen verglichen, und der Vorgang, der für die einzelnen Vektorelemente aus zuführen ist, wird abhängig von den Vergleichsergebnissen gewählt.

Genauer gesagt, wird gemäß der Erfindung eine Stoßstelle zwischen den in aufsteigender Reihenfolge angeordneten Elementen und den in absteigender Reihenfolge angeordneten Elementen ermittelt, die nachfolgend parallel mit der Ausführung des Mischvorgangs für das beim vorigen Mal gelesene Vektorelement gelesen werden, und der Mischvorgang für die anschließend gelesenen Vektorelemente wird entweder für die Elemente mit ansteigender Reihenfolge oder für die Elemente mit absteigender Reihenfolge abhängig vom ermittelten Ergebnis ausgeführt.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 ist ein Diagramm, das die Gesamtstruktur eines Vektorprozessors gemäß einem Ausführungsbeispiel der Erfindung veranschaulicht;

Fig. 2 ist ein Diagramm, das ein Anweisungsformat veranschaulicht;

Fig. 3 ist ein Zeitablaufdiagramm, das den Betrieb veranschaulicht;

Fig. 4 ist ein Diagramm, das die Struktur einer Zeitsteuerungsschaltung veranschaulicht;

Fig. 5 ist ein Diagramm, das die Struktur einer Operandensteuerungsschaltung veranschaulicht;

Fig. 6 ist ein Diagramm, das die Struktur einer Modussteuerungsschaltung veranschaulicht;

Fig. 7 ist ein Diagramm, das die Struktur einer Adreßsteuerungsschaltung veranschaulicht;

Fig. 8 ist ein Diagramm, das die Struktur einer Operationsschaltung veranschaulicht;

Fig. 9 ist eine Wahrheitstabelle, die die Funktion einer Steuerungslogik für die nächste Operation veranschaulicht;

Fig. 10 ist ein Diagramm, das ein Verfahren für Nischsortierung unter Verwendung eines herkömmlichen Vektorprozessors veranschaulicht; und

Fig. 11 ist ein Diagramm, das schematisch den Mischvorgang gemäß der Erfindung veranschaulicht.

BESCHREIBUNG DES BEVORZUGTEN AUSFÜHRUNGSBEISPIELS

Bevor die Erfindung im einzelnen beschrieben wird, wird der Mischvorgang gemäß dem Ausführungsbeispiel kurz unter Bezugnahme auf Fig. 11 beschrieben. Ein Eingangsvektor aus Vektorelementen 2, 5, 7, 4, 1, 6, 8 und 3 wird dadurch bearbeitet, daß von seinen beiden Enden ausgehend begonnen wird. Zunächst werden benachbart aufeinanderfolgende Vektorelemente hinsichtlich ihrer Größe verglichen, um zu untersuchen, ob die Daten in aufsteigender oder absteigender Reihenfolge geordnet sind. Z.B. gilt 2 < 5 für das obere Ende, und 3 < 8 gilt für das untere Ende, was anzeigt, daß die Vektorelemente in aufsteigender Reihenfolge geordnet sind. Zum Betriebsmodus gehört ein aufsteigender Mischmodus und ein absteigender Mischmodus, und Werte "0" und "1" werden dazu entsprechend in ein Betriebsmodusregister eingeschrieben. Wenn nun der Anfangswert "0" in das Betriebsmodusregister eingeschrieben ist, wird der Betrieb mit dem aufsteigenden Mischmodus begonnen. Im aufsteigenden Mischmodus werden Elemente in der Reihenfolge mit zunehmender Größe erzeugt. Daher wird zunächst das Elemente "2" erzeugt. Die nachfolgenden zwei Elemente vom oberen Ende her werden als 5 < 7 verglichen, d.h., die absteigende Reihenfolge gilt immer noch. Daher ändert sich der Betriebsmodus nicht, und es wird "3" erzeugt. Die nächstfolgenden zwei Elemente vom unteren Element werden als 8 > 6 verglichen, d.h., daß sich die aufsteigende Reihenfolge zur absteigenden Reihenfolge ändert. Da kein Element mit aufsteigender Reihenfolge vom unteren Ende her vorhanden ist, wird das Element mit aufsteigender Reihenfolge "5" vom oberen Ende erzeugt. Im Ergebnis werden die folgenden zwei Elemente vom oberen Ende her als 7 > 4 miteinander verglichen, d.h., die aufsteigende Reihenfolge ändert sich in die absteigende Reihenfolge. Von "7" und "8" wird daher der größere Wert erzeugt, d.h. es wird "8" erzeugt. Da das erste Element mit aufsteigender Reihenfolge hierbei nicht mehr vorhanden ist, wird das Betriebsmodusregister auf "1" aufgefrischt, und die Vektorelemente in absteigender Reihenfolge werden gemischt. Im Mischmodus mit absteigender Reihenfolge werden die Elemente in absteigender Reihenfolge erzeugt. Daher wird zunächst "8" erzeugt. Wie im Fall der Vektorelemente in aufsteigender Reihenfolge werden die Vektorelemente in absteigender Reihenfolge gemischt. Ähnlich wird dann, wenn weder Vektorelemente in aufsteigender Reihenfolge noch Vektorelemente in absteigender Reihenfolge vorhanden sind, der Modus aufgefrischt, und Elemente der nächsten Untersequenz werden gemischt.

Dies ermöglicht es, eine Stoßstelle zwischen Untersequenzen von Elementen parallel zum Mischvorgang zu ermitteln. Ferner ist es erlaubt, den aufsteigenden Mischmodus und den absteigenden Mischmodus auszuführen, ohne daß die Anweisung auf die Vektorelemente in aufsteigender Reihenfolge oder in absteigender Reihenfolge hin neu gestartet wird, was es ermöglicht, Pipeline-Verarbeitung auszuführen, was zum Beibehalten eines guten Wirkungsgrades beiträgt.

Die Erfindung kann nicht nur auf eine solche Mischverarbeitung angewandt werden, sondern auch auf jede andere Verarbeitung.

Ein Ausführungsbeispiel der Erfindung wird nun im einzelnen in Zusammenhang mit den Zeichnungen beschrieben. Zunächst werden die Struktur und die Funktion des Vektorprozessors gemäß einem Ausführungsbeispiel der Erfindung kurz unter Bezugnahme auf Fig. 1 beschrieben.

Eine Vektormischanweisung, wie sie in einem Hauptspeicher 111 abgespeichert ist, wird über einen Datenpfad 129 in ein Anweisungswortregister 101 ausgelesen. Auf diese Anweisung hin erzeugt eine Zeitsteuerungsschaltung 105 mehrere Steuersignale. Parallel hierzu werden für die Ausführung der Anweisung erforderliche Daten von einer Gruppe von Universalregistern 103 an eine Operandensteuerungsschaltung 106, Adreßsteuerungsschaltungen 109a bis 109c sowie an eine Modussteuerungsschaltung 107 ausgegeben, und sie werden dort eingeschrieben, um diese Schaltungen zu initialisieren.

Nachdem sie initialisiert wurde, sendet die Zeitsteuerungsschaltung 105 wiederholt eine Abrufanforderung FREQ für Elemente eines ersten Vektors (nachfolgend als Vektor X bezeichnet) und eines zweiten Vektors (nachfolgend als Vektor Y bezeichnet), die zu bearbeiten sind, an den Hauptspeicher 111, wie auch eine Abspeicheranforderung SREQ für Elemente eines Vektors (nachfolgend als Vektor Z bezeichnet), der als Ergebnis der Operation erhalten wird.

Eine X-Adressteuerungsschaltung 109X und eine Y-Adreßsteuerungschaltung 109Y erzeugen aufeinander folgend Adressen von Anforderungen, die durch die Vektoren X und Y zu lesen sind. Eine Z-Adressteuerungsschaltung 109Z erzeugt aufeinanderfolgend Schreibadressen für Anforderungen des Vektors Z. Der Hauptspeicher 111, der die Abrufanforderung FREQ erhalten hat, liest die Vektorelemente der Vektoren X und Y abhängig von den Abrufadressen XADR und YADR, wie sie von den Adresssteuerungsschaltungen 109X und 109Y über einen Datenpfad 124 geliefert wurden. Das Element XDATA des Vektors X und das Element YDATA des Vektors Y, die ausgelesen wurden, werden an eine Mischoperationsschaltung 110Z geliefert.

Die Mischoperationsschaltung 110Z besteht aus einem Komparator 806, der die Daten XDATA mit den Daten YDATA vergleicht, und einem Selektor 800. Der Selektor wählt den Datenwert XDATA oder den Datenwert YDATA aus (den Kleineren). Der ausgewählte Datenwert wird als Element des Vektors Z als Operationsergebnis in den Hauptspeicher eingeschrieben. Die Schreibadresse zu diesem Zweck wird durch die oben genannte Z-Adreßsteuerungsschaltung 109Z erzeugt. So wird die Mischoperation für ein Datenpaar abgeschlossen. Ein auf ein vom obigen Selektor 800 ausgewähltes Vektorelement (z.B. XDATA) folgendes Vektorelement wird durch eine entsprechende Adreßsteuerungschaltung gelesen, z.B. durch die X-Adreßsteuerungsschaltung 109X, an die Mischoperationsschaltung 110Z geliefert, und erneut zusammen mit dem beim vorigen Mal nicht ausgewählten Datenwert (z.B. YData) der Mischoperation unterworfen. Dieselbe Operation wir danach wiederholt.

Wenn die Operandensteuerungsschaltung 106 das Ende feststellt, wird ein diese Tatsache anzeigendes Steuerungssignal ENDO an eine Zeitsteuerungsschaltung 105 ausgegeben, wodurch die Aufrufanforderung FREQ und die Abspeicheranforderung SREQ nicht mehr ausgegeben werden und die Anweisung abgeschlossen wird. Danach wird die nächste Anweisung aus dem Hauptspeicher 111 entnommen und an das Anweisungswortregister 101 geliefert, um die Verarbeitung fortzusetzen.

Die oben angegebene Operation ist dieselbe wie die Mischoperation unter Verwendung eines herkömmlichen Vektorprozessors.

Dieses Merkmal dieses Ausführungsbeispiels wird nachfolgend beschrieben. D.h., das Merkmal dieser Erfindung liegt darin, daß eine Beurteilungsschaltung 110X für aufsteigende X-Reihenfolge, eine Beurteilungsschaltung 110Y für aufsteigende Y-Reihenfolge, eine Modussteuerungsschaltung 107 und eine Steuerungslogik 108 für die nächste Operation, die auf die Ausgangssignale dieser Schaltungen und das Ausgangssignal des Komparators 806 hin arbeitet, vorgesehen sind.

Die Beurteilungsschaltung 110X für aufsteigende X-Reihenfolge vergleicht das Vektorelement XDATA mit dem Element des vorigen Vektors X und berurteilt, ob das Vektorelement XDATA in aufsteigender Reihenfolge vorliegt.

Die Beurteilungsschaltung 110Y für aufsteigende Y-Reihenfolge führt dieselbe Operation für das Element YDATA des Vektors Y aus.

Die Modussteuerungsschaltung 107 speichert ein Modussignal MODE, das angibt, ob die Mischung in aufsteigender Reihenfolge (d.h. Operation zum Auswählen des kleineren Datenwertes von zwei Eingangsdatenwerten) oder das Mischen nach absteigender Reihenfolge (d.h. Operation zum Auswählen des größeren Wertes unter den zwei Eingangsdatenwerten) durch die Mischoperationsschaltung 110Z auszuführen ist. D.h., daß das Element XDATA des aus dem Hauptspeicher 111 ausgelesenen Vektors X an die Beurteilungsschaltung 110X für aufsteigende X-Reihenfolge geliefert wird und mit dem Element des zuvor gelesenen Vektors X verglichen wird, und es wird dort beurteilt, ob sich der Datenwert XDATA in aufsteigender Reihenfolge bezogen auf den vorigen Datenwert befindet. Ein Signal CMP1 repräsentiert das Beurteilungsergebnis.

Eine ähnliche Beurteilung wird durch die Beurteilungsschaltung 110Y für aufsteigende Y-Reihenfolge für das Element YDATA des Vektors Y ausgeführt, und es wird ein Signal CMP3 erzeugt, um das Beurteilungsergebnis zu repräsentieren.

Auf die Signale CMP1, CMP2 und ein in der Modussteuerungsschaltung 107 abgespeichertes Modussignal ermittelt die Steuerungslogik 108 für die nächste Operation, ob der Mischoperationsmodus in aufsteigender Reihenfolge oder der Mischoperationsmodus in absteigender Reihenfolge für die der Mischoperationsschaltung 110Z zugeführten Datenwerte XDATA, YDATA ausgeführt werden soll, und sie sendet ein Signal UPMC an die Modussteuerungsschaltung 107, wenn der Modus zu ändern ist. Abhängig vom Ausgangssignal CMP2 des Komparators 806 für die Datenwerte XDATA, YDATA, und dem oben ermittelten Operationsmodus wird der Selektor 800 so gesteuert, daß er einen dieser beiden Datenwerte auswählt. Ferner werden die Steuerungsschaltung 110X für aufsteigende X-Reihenfolge und die Steuerungsschaltung 110Y für aufsteigende Y-Reihenfolge durch die Adreßsteuerungsschaltungen 109X, 109Y und 109Z gesteuert.

Die Signale UP1, UP2 und UP3 arbeiten dahingehend, daß diese Steuerungsfunktionen ausgeführt werden.

Dadurch ist es ermöglicht, die Art von Operationen abhängig vom Ergebnis der Operation während der Verarbeitung eines Vektors dynamisch zu ändern. Im Fall z.B. einer Mischsortierung wird die Operation in solcher Weise ausgeführt, daß die Mischausgangswerte in zunehmender Reihenfolge (Mischung in zunehmender Reihenfolge) für die Vektoren mit einer Untersequenz in aufsteigender Reihenfolge erzeugt werden, und die Mischausgangswerte in absteigender Reihenfolge (Mischung in absteigender Reihenfolge) für die Vektoren mit einer Untersequenz in absteigender Reihenfolge erzeugt werden, während nach Vektoren mit einer Untersequenz mit aufsteigender Reihenfolge oder mit einer Untersequenz mit absteigender Reihenfolge unter den Vektoren geschaut wird. Daher wird die Vektoroperation effektiv ausgeführt und ist weder mit dem Overhead zur Unterteilung in Untersequenzvektoren noch mit dem Startoverhead für eine Vektoranweisung verbunden.

Vor dem Beschreiben des Vektorprozessors von Fig. 1 im Detail, wird nun das Anweisungsformat für die Vektoranweisung gemäß diesem Ausführungsbeispiel unter Bezugnahme auf Fig. 2 beschrieben, bei dem eine Vektoranweisung aus 32 Bits besteht. Die oberen 16 Bits 201 der Anweisung repräsentieren die Art der Vektoranweisung. Ein Feld R1 202 repräsentiert eine aus 4 Bits bestehende ganze Binärzahl, und es kennzeichnet ein Universalregister 204 mit einer durch das Feld R1 angezeigten Nummer, wie auch Register 205, 206, 207, 208 und 209, die auf 205 folgen, in einer Gruppe von 16 Universalregistern 103. Auf ähnliche Weise kennzeichnet ein Feld R2 ein Universalregister 210 mit einer durch das Feld R2 angezeigten Nummer, wie auch Register 211, 212 und 213, die auf 210 folgen.

Die Universalregister 204, 206 und 208 speichern die Startadressen für den Vektor X, den Vektor Y und den Vektor Z. Die Universalregister 205, 207 und 209 speichern die Gesamtanzahl der Elemente der Vektoren X, Y und Z. Die Universalregister 210, 211 und 212 speichern die verarbeiteten Vektorelemente der Vektoren X, Y und Z. Das Universalregister 213 bildet eines der Merkmale der Erfindung, und es speichert den Operationsmodus. Die Vektoroperation, die die Verarbeitung von Fig. 11 ausführt, wird nachfolgend als Mehrfachmodus-Mischoperation bezeichnet.

Wie in Fig. 1 dargestellt, besteht der Vektor X aus Datenelementen in der Form zu sortierender Vektoren, und der Vektor Y besteht aus denjenigen des Vektors X, die jedoch in umgekehrter Reihenfolge angeordnet sind. Genau gesagt, wird die Anfangsadresse des Vektors Y mit der Adresse des letzten Elements des Vektors X gleichgesetzt, die Adresse des letzten Elements wird sukzessive verringert, wie dies später beschrieben wird, die Adresse eines zu lesenden Elementes des Vektors X wird als Element des Vektors Y erzeugt, es wird auf den Hauptspeicher 111 gestützt auf die erzeugte Adresse zugegriffen, und die Elemente des Vektors X werden in umgekehrter Reihenfolge im Vergleich zu denen des Vektors Y ausgelesen.

Daher besteht kein Erfordernis, den Vektor Y aus dem Vektor X vorab zu erzeugen, um ihn in den Hauptspeicher 111 einzuspeichern. Zum Zweck eines einfachen Verständnisses von Fig. 1 wird der Vektor Y getrennt vom Vektor X beschrieben. Die Erfindung kann jedoch genau in derselben Weise auch dann ausgebildet sein, wenn der Vektor Y etwas ganz anderes als der Vektor X ist.

Bei diesem Ausführungsbeispiel wird angenommen, daß die Anzahl der Vektorelemente in den Universalregistern 205, 207, 209 immer "8" ist. Ferner kann "0" als Anfangswert für die Anzahl verarbeiteter Elemente in die Universalregister 210, 211 und 212 eingeschrieben sein. Null wird auch als Anfangswert für den Operationsmodus 213 gesetzt.

Nachfolgend wird die Funktion des Vektorprozessors im einzelnen unter Bezugnahme auf Fig. 11 beschrieben. Genau gesagt, wird auch auf den Fluß des Zeitablaufdiagramms von Fig. 3 Bezug genommen, das den Fortschritt der Verarbeitung zeigt, während die Strukturen der betroffenen Logikschaltungen (Fig. 4 bis 9) berücksichtigt werden.

Fig. 3 ist ein Zeitablaufdiagramm, das die Funktion des Vektorprozessors von Fig. 1 veranschaulicht. Wie in Fig. 3 dargestellt, verwendet der Vektorprozessor Taktsignale mit zwei Phasen CK&sub0; und CK&sub1; zum Beibehalten der Synchronisierung.

Fig. 4 ist ein Diagramm, das die Struktur der Zeitsteuerungsschaltung 105 veranschaulicht, wobei FF ein Flipflop bezeichnet.

Wenn als Ergebnis der Dekodierung durch die Dekoderschaltung 102 ermittelt wird, daß die Vektoranweisung der in Fig. 2 dargestellten Form, wie sie vom Anweisungsregister 101 über den Datenpfad 112 gesendet wird, eine Mehrfachmodus-Mischanweisung ist, sendet die Zeitsteuerungsschaltung 105 Steuersignale iNiT0 bis iNiT3 (117a bis 117c), die die Schaltungen initialisieren. Gleichzeitig wird ein H-Flipflop 401 so gesetzt, daß es anzeigt, daß die Mehrfachmodus-Mischanweisung verarbeitet wird.

Fig. 5 veranschaulicht die Struktur der Operandensteuerungsschaltung 106, wobei Bezugsziffern 501 bis 503 Operandenzähler zum Zählen der Anzahlen verarbeiteter Elemente in den Vektoren X, Y und Z bezeichnen. Der Zähler 501 besteht aus einem Operandenzählregister 501A, einem +1-Addierer 501B zum Erneuern des Wertes des Operandenzählregisters 510A, und einem Selektor 501C. Die anderen Zähler 502 und 503 sind auf dieselbe Weise aufgebaut.

Gemäß Angabe durch das iNiT0-Signal 117a werden die Werte der Universalregister 210, 211 und 212, d.h. der Anfangswert "0" in die Operandenzählregister 501A, 502A und 503A in der Operandensteuerungsschaltung 106 über Selektoren 501C, 502C und 503C eingeschrieben. Gemäß Angabe durch das Signal iNiT0 wird ferner der Wert der Universalregister 205, 207 und 209, d.h. "8" in die Gesamtelementanzahl-Register 504A, 502A und 506A eingeschrieben. So wird die Operandensteuerungsschaltung 106 initialisiert.

Der Komparator 504B vergleicht die Anzahl der verarbeiteten Vektorelemente im Register 501A mit der Anzahl von Vektorelementen im Register 504A. Die anderen Komparatoren 505B und 506B arbeiten auf dieselbe Weise. Wenn ein Übereinstimmungssignal von einem dieser Komparatoren ermittelt wird, werden die Beendigungssignale ENDO und END1 erzeugt.

Fig. 6 ist ein Diagramm, das die Struktur der Modussteuerungsschaltung 107 veranschaulicht. Gemäß Angabe durch ein Signal iNiT2 117C wird der Anfangswert GRDATA (0 in diesem Fall) für den Operationsmodus, wie er im Universalregister 213 abgespeichert ist, anfangs über den Selektor 601B in das Operationsmodus-Zählregister 601 eingeschrieben. So wird die Initialisierung der Modussteuerungsschaltung 107 abgeschlossen. Eine Bezugsziffer 601A bezeichnet einen Addierer, der +1 zum Inhalt des Registers 601 zählt. Der Zähler wird durch den Addierer 601A und das Register 601 gebildet.

Fig. 7 ist ein Diagramm, das die Struktur der Adreßsteuerungsschaltungen 109X, 109Y und 109Z veranschaulicht. Die X-Adreßsteuerungsschaltung 109X besteht aus einem Adreßregister 701A, das die Adresse der X-Vektorelemente hält, einem +4-Addierer 701B zum Auffrischen des Wertes derselben um +4, und einen Selektor 701C. Die Y-Adreßsteuerungsschaltung 109Y besteht aus einem Adreßregister 702A zum Halten der Adressen der Y-Vektorelementen, einem -4-Addierer 702B zum Erneuern des Wertes derselben um -4, und einem Selektor 702C. Die Z-Adreßsteuerungsschaltung 109Z ist auf dieselbe Weise wie die X-Adreßsteuerungsschaltung 109X aufgebaut.

Gemäß Angabe durch ein Signal iNiT1 117b werden die Startadressen (a1, a2, a3) der Vektoren X, Y und Z, wie sie in den Universalregistern 204, 206 und 208 abgespeichert sind, in die Adreßregister 701A, 702A und 703A eingeschrieben. So wird die Initialisierung der Adreßsteuerungsschaltungen 109X, 109Y und 109Z abgeschlossen.

Auf einen Takt eines DEC-Signals 113 folgend wird ein Abrufzugriffsignal FREQ von der Zeitsteuerungsschaltung 105 (Fig. 4) an den Hauptspeicher 111 ausgegeben. Danach wird das Signal FREQ nach jedem weiteren Takt erzeugt, bis der Betrieb beendet wird.

Nach Empfang des ersten Abrufanforderungssignals ( 1 in Fig. 3) liest der Hauptspeicher 111 die Vektorelemente XDATA und YDATA unter Verwendung der X-Vektorelementadresse XADR und der Y-Vektorelementadresse YADR, wie sie von den Adreßregistern 701A und 702A als Abrufadressen über Datenpfade 124a und 124b von den Adreßregistern 701A und 702A geliefert werden, und er gibt diese an die Beurteilungsschaltung 110X für aufsteigende X-Reihenfolge, die Beurteilungsschaltung 110Y für aufsteigende Y-Reihenfolge und die Operationsschaltung 110Z.

Fig. 8 veranschaulicht die Struktur der Beurteilungsschaltung 110X für aufsteigende X-Reihenfolge, der Beurteilungsschaltung 110Y für aufsteigende Y-Reihenfolge und der Operationsschaltung 110Z. Die Beurteilungsschaltung 110X für aufsteigende X-Reihenfolge besteht aus einem Arbeitsregister 801 (nachfolgend als WXN-Register bezeichnet) zum Halten des Vektorelements XDATA, einem Register 803 (nachfolgend als WXC-Register bezeichnet) zum Halten des Vektorelements, das früher als das obige Vektorelement gelesen wurde, und einem Komparator 805, der die Werte dieser Register miteinander vergleicht. Die Beurteilungsschaltung 110Y für aufsteigende Y-Reihenfolge ist auf dieselbe Weise aufgebaut. Die Operationsschaltung 110Z besteht aus einem Komparator 806, der die X-Vektorelemente mit den Y-Vektorelementen in den Registern 803 und 804 vergleicht, und einem Selektor 800, der einen dieser Komparatoren auswählt. In Fig. 8 bezeichnet ein Symbol FF ein Flipflop.

Die Anfangselemente "2" und "3" der Vektoren X und Y, wie sie aus dem Hauptspeicher 111 ausgelesen werden, werden durch ein Signal iNiT3 117d in das WXN-Register 801 bzw. das WYN-Register 802 eingelesen.

Nach Empfang eines 2-Takt-Verzögerungssignals des Signals iNiT1 117b erhalten die Adreßregister 701 und 702 in den Adreßsteuerungsschaltungen 109a und 109b (Fig. 7) die Werte +4 bzw. -4, um Adressen für die nächsten Elemente einzunehmen. Die Vektorelemente "5" und "8", sie sie durch diese Adressen gekennzeichnet werden, werden gemäß der Abrufanforderung ( 2 in Fig. 3) zum zweiten Zeitpunkt gelesen und an die Beurteilungsschaltung 110X für aufsteigende X-Reihenfolge, die Beurteilungsschaltung 110Y für aufsteigende Y-Reihenfolge und die Operationsschaltung 110Z (Fig. 8) gegeben. Die gelieferten Elemente "5" und "8" werden durch ein 3- Takt-Verzögerungssignal des Signals iNiT3 in das WXN-Register 801 und das WYN-Register 802 eingeschrieben. Gleichzeitig werden die im WXN-Register 801 und im WYN-Register 802 abgespeicherten Daten "2" und "3" an das WXC-Register 803 bzw. das WYC-Register 804 übertragen. Die Komparatoren 805, 806 und 807 vergleichen die Inhalte des WXN-Registers 801 und des WXC-Registers 803, die Inhalte des WXC-Registers 803 und des WYC-Registers 806 sowie die Inhalte des WYN-Registers 802 und des WYC-Registers 804, und die Vergleichergebnisse COMP1, COMP2 und COMP3 werden über Signalleitungen 126a, 126b und 126c an die Steuerungslogik 108 für die nächste Operation geliefert.

Fig. 9 ist eine Wahrheitstabelle, die die Funktion der Steuerungslogik 108 für die nächste Operation veranschaulicht. Abhängig vom Wert eines Signals MODE (122), das den Wert des Operationsmodusregisters 601 repräsentiert, kann die Steuerungslogik 108 für die nächste Operation in Eingabezahlen 1 bis 6 (108a) und Eingabezahlen 7 bis 13 (108b) unterteilt werden. D.h., daß ein 108a den Fall des Mischmodus in aufsteigender Reihenfolge (MODE = 0) repräsentiert, und daß 108b den Fall des Mischmodus in absteigender Reihenfolge (MODE = 1) repräsentiert. Hierbei repräsentiert das Signal COMPI 2 ≤ 5, das Signal COMP2 repräsentiert 2 ≤ 3 und das Signal COMP3 repräsentiert 3 ≤ 8. In der Operandensteuerungsschaltung 106 (Fig. 5) sind ferner die Anzahlen OC1, OC2 und OC3 der verarbeiteten Elemente in den Operandenzählerregistern 501A, 502A und 503A alle "0", und in den Elementennummerregistern 504B, 505B und 506B sind die Werte alle "8". Daher ist das Signal END0 oder END1 "0". Da der Wert des Operationsmodusregisters 601 "0" ist, nimmt ferner das Signal MODE (122), das aus dem geringstsignifikanten Bit besteht, ebenfalls den Wert "0" ein. Daher wird die Operation (Mischung in aufsteigender Reihenfolge) für die Eingabezahl 1 in der Wahrheitstabelle von Fig. 9 ausgewählt, und es werden die Ausgangssignale UP1 (120a), UP2 (120b), UP3 (120c) und UPMC (123) mit den Werten "1", "0", "1" bzw. "0" erzeugt. Diese Ausgangssignale werden an die Operandensteuerungsschaltung 106, die Modussteuerungsschaltung 107 und die Adreßsteuerungsschaltung 109 geliefert, und die Register werden aufgefrischt. Wenn die Operation mit der Eingangsnummer 1 in Fig. 9 spezifiziert ist, nehmen das Signal UP1 (120a) und das Signal UP3 (120C) den Wert "1" ein, wodurch die Vektorelement-Zählerregister 501A und 502A (Fig. 5) für die Vektoren X und Z um +1 hochgezählt werden. Ferner werden die Adreßregister 701A und 703A (Fig. 7) aufgefrischt (+4), um die nächsten Vektorelemente zu spezifizieren. Andererseits nimmt das Signal UP2 (117b) den Wert "0" ein, und das Vektorelement-Zählerregister 502A für den Vektor Y und das Adreßregister 702A (Fig. 7) werden nicht aufgefrischt. Auf ähnliche Weise wird auch das Operationsmodusregister 601 (Fig. 6) nicht aufgefrischt, da das Signal UPXC (123) auf dem Wert "0" bleibt. Dies bedeutet das Folgende. D.h., daß, wie dies oben unter Bezugnahme auf Fig. 9 beschrieben wurde, dann, wenn das Signal MODE (122) den Wert "0" einnimmt, die Vektormischung nach aufsteigender Reihenfolge von der Eingangszahl 1 bis hoch zur Eingangszahl 6 (108a) ausgeführt wird, und daß dann, wenn das Signal MODE den Wert "1" einnimmt, die Vektormischung nach absteigender Reihenfolge von der Eingangsnummer 7 bis hoch zur Eingangsnummer 13 (108b) ausgeführt wird. Andererseits ist der Anfangswert des Operationsmodusregisters 601 "0", was den Modus nach auf steigender Reihenfolge kennzeichnet. Aus den Ergebnissen von COMP1 (126a) und COMP3 (126c) ist es hierbei offensichtlich, daß die Daten in aufsteigender Reihenfolge angeordnet sind und daß kein Erfordernis zum Ändern des Modus besteht.

Die Abrufanforderung zum dritten Zeitpunkt ( in Fig. 3) wird gemäß der erneuerten Adresse ausgeführt. D.h., daß die X-Operandenadresse XADR "a1 + 8" und die Y-Operandenadresse YADR "a2 - 4" ist. Daher werden die Daten "7" und "8" aus dem Hauptspeicher 111 ausgelesen. D.h., daß für den Vektor Y dieselben Vektorelemente wie die für die Abrufanforderung für den zweiten Zeitpunkt ausgelesen werden. Die Daten "7" und "8", die ausgelesen werden, werden an die Beurteilungsschaltung 110X für aufsteigende X-Reihenfolge, die Beurteilungsschaltung 110Y für aufsteigende Y-Reihenfolge und die Operationsschaltung 110Z geliefert. Das Vektorelement "7" des Vektors X wird in das WXN-Register 801 (Fig. 8) eingeschrieben, da UP1 = 1 ist. Da jedoch UP2 = 0 ist, wird das Vektorelement "8" des Vektors Y nicht in das WYN-Register 802 (Fig. 8) eingeschrieben, und der Inhalt dieses Registers wird nicht erneuert. Auf ähnliche Weise wird der Anfangswert "5" des WXN-Registers 801 in das WXC-Register 803 eingeschrieben, jedoch wird der Inhalt des WYN-Registers 804 nicht erneuert. Da UP1 = 1 ist, wird hierbei der Anfangswert "2" des WXC-Registers 803 in das WX-Register 808 eingeschrieben, das den Datenwert speichert.

Nach einem Takt des Abrufanforderungssignals FREQ ( in Fig. 3) zum dritten Zeitpunkt wird ein erstes Speicheranforderungssignal SREQ (113b) von der Zeitsteuerungsschaltung 105 an den Hauptspeicher 111 geliefert.

Die Abspeicherungsanforderung wird unter Verwendung des Inhalts ZADR des Adreßregisters 703A der Z-Adreßsteuerungsschaltung 109c (Fig. 7) als Speicheradresse und des Inhalts des WZ-Registers 808 (Fig. 8) als Speicherdaten STDATA (134) ausgeführt. Daher wird "2" als erstes Element des Vektors Z in die Adresse "a3" eingeschrieben.

Das nächste Operationsergebnis wird von der Steuerungslogik 108 für die nächste Operation parallel zum Abspeicherungsvorgang erzeugt, d.h. nach einem Takt der Abrufanforderung ( in Fig. 3) zum dritten Zeitpunkt. Diesmal repräsentiert das Signal CMP1 (126a) 5 ≤ 7, CMP2 (126b) repräsentiert 5 > 3, CMP3 (126c) repräsentiert 3 ≤ 8, END0 und END1 repräsentieren 0, und MODE (122) repräsentiert 0. Daher wird die Operation für die Eingangszahl 2 ausgewählt, d.h. es wird die Operation für den Fall im Mischmodus nach aufsteigender Reihenfolge ausgewählt, bei dem der Vektor Y klein ist, so daß UP1 (120a) 0 annimmt, UP2 (120b) 1 annimmt, UP3 (120c) 1 annimmt und UPMC (123) 0 annimmt. Demgemäß werden das Adreßregister 701A und das Operandenzählregister 501A nicht erneuert, 4 wird vom Adreßregister 702A abgezogen, so daß es den Wert a2 - 8 annimmt, und 1 wird zum Operandenzählregister 502A hinzugezählt, so daß es den Wert 1 annimmt. Darüber hinaus wird 1 zum Operandenzählregister 503A addiert, so daß es den Wert 2 annimmt. Ein Abrufdatenwert "6", der der Abrufanforderung ( in Fig. 3) zum vierten Zeitpunkt entspricht, wird in das WYN-Register 802 eingeschrieben, "8" wird in das Register 804 eingegeben, und "3" wird in das WZegister 134 eingeschrieben und als zweites Element des Vektors Z abgespeichert. Die Inhalte des Register WXN 801 und des Registers WXC 803 werden nicht erneuert.

Danach wird der Vorgang auf dieselbe Weise fortgesetzt. Bei der Operation für die Abrufdaten, die der Abrufanforderung ( in Fig. 3) zum vierten Zeitpunkt entsprechen, repräsentiert CMP1 (126a) 5 ≤ 7, CMP2 (126b) repräsentiert 5 ≤ 8 und CMP3 (126c) repräsentiert 8 > 6. Aus den Ergebnissen für CMP1 und CMP3 ist offensichtlich, daß die Elemente im Vektor X immer noch in aufsteigender Reihenfolge angeordnet sind, daß jedoch kein Element in aufsteigender Reihenfolge mehr im Vektor Y vorhanden ist. Es wird die Operation zur Eingangsnummer 3 (Modus für aufsteigende Reihenfolge) in Fig. 9 gewählt, die Operandenzählregister 501A, 503A für die Vektoren X und Y werden erneuert, die Adreßregister 701A und 703A werden erneuert, das WXN-Register 801, das WXC-Register 803 und das WZ-Register 808 werden erneuert, und der Datenwert "5" für den Vektor X wird als nächstes Element des Vektors Z abgespeichert.

Auf die Abrufanforderung ( in Fig. 3) zum fünften Zeitpunkt wird "4" in das WXN-Register 801 eingeschrieben, und "7" wird in das WXC-Register 803 eingeschrieben. Als Ergebnis der Operation repräsentiert CMP1 7 > 4, CMP2 repräsentiert 7 ≤ 8 und CMP3 repräsentiert 8 > 6, woraus erkennbar ist, daß auch im Vektor X kein Element in aufsteigender Reihenfolge mehr vorhanden ist. Daher wird diesmal die Operation auf die Elementmischung in absteigender Reihenfolge umgeschaltet. Genau gesagt, wird die Operation zur Eingangsnummer 5 in Fig. 9 ausgewählt, und die Operandenzählregister 501A und 503A für die Vektoren X und Y, die Adreßregister 701A, 703A und die Arbeitsregister 801 und 803 werden erneuert, und der Datenwert "7" für den Vektor X wird als Element des Vektors Z abgespeichert. Da die Vektormischung nach aufsteigender Reihenfolge, wie zuvor erwähnt, abgeschlossen wurde, wird das Signal UPMC (123) dahin überführt, daß es "1" einnimmt, und das Operationsmodusregister 601 wird erneuert (+1), um die Operation zur Vektormischung nach absteigender Reihenfolge zu ändern. Daher nimmt das Signal MODE (122) den Wert 1 ein.

Auf die Abrufanforderung ( in Fig. 3) zu dem sechsten Zeitpunkt wird "1" in das WXN-Register 801 und "4" in das WXC-Register 803 eingeschrieben. Als Ergebnis der Operation repräsentiert CMP1 4 ≤ 1, CMP2 repräsentiert 4 ≤ 8, CMP3 repräsentiert 8 ≥ 6 und MODE ist 1. Daher wird das Mischen für die Vektorelemente in absteigender Reihenfolge ausgeführt. Genau gesagt, wird die Operation (Modus für absteigende Reihenfolge) zur Eingangsnummer 7 in Fig. 9 ausgewählt, wodurch die Operandenzählregister 502A, 503A für die Vektoren Y und Z, die Adreßregister 702A, 703A sowie das WYN-Register 802, das WYC-Register 804 und das WZ-Register 808 jeweils erneuert werden. Hierbei wird "8" in den Hauptspeicher 111 eingeschrieben (der größere Wert wird erzeugt, da das Mischen nach absteigender Reihenfolge ausgeführt wird). Der Modus verbleibt unverändert, da sich beide Vektoren X und Y in absteigender Reihenfolge befinden.

Auf die Abrufanforderung ( in Fig. 3) zum siebten Zeitpunkt hin wird "1" in das WYN-Register 802 und "6" in das WYC-Register 804 eingeschrieben. Als Ergebnis der Operation repräsentiert CMP1 4 ≥ 1, CNP2 repräsentiert 4 ≤ 6 und CMP3 repräsentiert 6 ≥ 1. Wie beim vorigen Mal wird daher die Operation (Modus mit absteigender Reihenfolge) zur Eingangszahl 7 in Fig. 9 ausgewählt, wodurch die Operandenzählregister 502A, 503A für die Vektoren X und Z wie auch die Adreßregister 702A, 703A, das WYN-Register 802, das WYC-Register 804 und das WZ-Register 808 jeweils erneuert werden. Der Datenwert "6" vom Vektor Y wird als nächstes Element für den Vektor Z abgespeichert.

Auf die Abrufanforderung ( in Fig. 3) zum achten Zeitpunkt hin wird "4" in das WYN-Register 802 und "1" in das WYC-Register 804 eingeschrieben. Als Ergebnis der Operation repräsentiert CMP1 4 ≥ 1, CMP2 repräsentiert 4 ≥ 1 und CMP3 repräsentiert 1 < 4, woraus erkennbar ist, daß immer noch ein Vektorelement in absteigender Reihenfolge beim Vektor X vorliegt, daß jedoch kein Vektorelement in absteigender Reihenfolge im Vektor Y vorhanden ist. Hierbei wird die Operation (Modus mit absteigender Reihenfolge) für die Eingabe 9 in Fig. 9 ausgewählt, wodurch die Operandenzählregister 501A, 503A für die Vektoren X und Y wie auch die Adreßregister 701A, 703A, das WXN-Register 801, das WXC-Register 803 und das WZ-Register 808 jeweils erneuert werden, und der Datenwert "4" vom Vektor X wird als Element des Vektors Z abgespeichert.

Auf die Abrufanforderung ( in Fig. 3) zum neunten Zeitpunkt hin wird "6" in das WXN-Register 801 und "1" in das WXC-Register 803 eingeschrieben. Als Ergebnis der Operation repräsentiert CMP1 1 < 6, CMP2 repräsentiert 1 ≤ 1 und CMP3 repräsentiert 1 < 4. Diesmal nehmen jedoch, da das Element Nummernregister 503A des Vektors Z den Wert "7" aufweist, die Signale END0 und END1 (116, 121) den Wert "1" ein, und es wird die Operation zur Eingangsnummer 13 in Fig. 9 ausgewählt. Demgemäß werden das Operandenzählregister 503A für den Vektor Z, das Adreßregister 703A und das WZR-Register 808 erneuert, und der Datenwert des Vektors Y wird als Element von Z abgespeichert.

Das Signal END0 (116) wird an die Zeitsteuerungsschaltung 105 geliefert, ein Flipflop 401 wird rückgesetzt, um anzuzeigen, daß die Mehrfachmodus-Mischanweisung ausgeführt wird, und das Abrufanforderungssignal FREQ (113a) wird nicht mehr erzeugt, und nach drei Takten wird das Abspeicheranforderungssignal SREQ (113b) nicht mehr erzeugt. Darüber hinaus werden die Werte 4, 3 und 7 des jeweils endgültigen Status der Operandenzählregister 501A, 502A und 503A, wie auch ein Wert 1 für den endgültigen Status des Operationsmodusregisters 601 in die entsprechenden Universalregister 210, 211, 212 und 213 über Datenpfade 132a, 132b, 132c und 133 zurückgeschrieben, wodurch die Verarbeitung der Mehrfachmodus- Mischanweisung abgeschlossen wird.

Bei der Beschreibung des Betriebs dieses Ausführungsbeispiels wurde mit dem Anfangswert des Modusregisters 601 von "0" begonnen, wobei es sich um eine gerade Zahl handelt. Dies bedeutet, daß der Vorgang damit begonnen wird, daß zunächst nach Vektorelementen in aufsteigender Reihenfolge gesehen wird. Die Daten werden selbst im Vektor Z in aufsteigender Reihenfolge abgespeichert. Wenn als Anfangswert für das Modusregister 601 mit einer ungeradzahligen Zahl, wie "1" begonnen wird, werden die Daten in absteigender Reihenfolge im Vektor Z abgespeichert. Demgemäß werden die abgespeicherten Ergebnisse in aufsteigender Reihenfolge erhalten, wenn die Mehrfachmodusmischung wiederholt wird, während der Anfangswert des Modusregisters immer auf eine gerade Zahl eingestellt ist, und die sortierten Ergebnisse werden in absteigender Reihenfolge erhalten, wenn der Anfangswert immer mit einer ungeradzahligen Zahl begonnen wird.

Die Erfindung kann ferner auf den unten angegebenen Fall angewandt werden. Genauer gesagt, werden beim oben genannten Ausführungsbeispiel Vektorelemente in aufsteigender Reihenfolge und Vektorelemente in absteigender Reihenfolge in den Vektoren ermittelt, und die folgenden zwei Elemente werden verglichen.

Die Ermittlung kann selbst dann ausgeführt werden, wenn ein Maskenvektor verwendet wird. D.h., daß ein Maskenvektor M1 bereitgestellt wird, bei dem M1 (i) = 1 den Vektorelementen X (i) im Vektor X in aufsteigender Reihenfolge entspricht, und M1 (j) = 0 den Vektorelementen X (j) in absteigender Reihenfolge entspricht. Ein Maskenvektor M2 wird in derselben Weise auch für den Vektor Y erstellt. Dann wird eine Mischoperationseinheit auf Grundlage der zwei Maskenvektoren in solcher Weise bereitgestellt, daß die Elemente X (k) und Y (l) der Vektoren X und Y in absteigender Reihenfolge gemischt werden, wenn M1 (k) = 0 und M2 (l) = 0 sind, und sie werden in aufsteigender Reihenfolge gemischt, wenn M1 (k) = 1 und M2 (l) = 1 sind.

Gemäß der Erfindung, wie sie oben beschrieben wurde, werden dann, wenn der eingegebene Vektoroperand aus mehreren Teilvektoren mit verschiedenen Eigenschaften besteht, die Elemente für jeden der Teilvektoren bearbeitet, Stoßstellenbereiche zwischen den Teilvektoren werden ermittelt und die Art der Operation wird abhängig von den Eigenschaften der Teilvektoren geändert, wobei all diese Operationen parallel zueinander ausgeführt werden, was es ermöglicht, die Verarbeitung mit hoher Geschwindigkeit auszuführen. Im Fall einer Mehrfachmodus-Mischanweisung werden z.B. Vektorelemente in aufsteigender Reihenfolge und absteigender Reihenfolge, wie sie normal in einem Eingangsvektoroperanden vorliegen, ermittelt, und gleichzeitig wird die Mischoperation in unterschiedlichem Modus abhängig von den Vektorelementen mit aufsteigender Reihenfolge und den Vektorelementen mit absteigender Reihenfolge ausgeführt. Daher kann die Anzahl von Malen der Mischoperation im Vergleich zum Fall verringert werden, wenn die Vektorelemente in aufsteigender Reihenfolge und absteigender Reihenfolge im Eingangsvektoroperanden nicht verwendet werden. In der Praxis sind die zu sortierenden Daten oft so vorsortiert, daß sie beinahe alle sortiert sind. Insbesondere werden die größten Auswirkungen dann erhalten, wenn die Eingaben vorab sortiert wurden, und die Mehrfachmodus-Mischanweisung muß unter Verwendung des erfindungsgemäßen Vektorprozessors einmal ausgeführt werden. Unter Verwendung eines herkömmlichen Vektorprozessors muß jedoch die Mischung log&sub2; N-mal ausgeführt werden (wenn die Anzahl von Elementen N ist). Ferner kann die Anzahl von Vektorelementen bei jedem Mischvorgang zu N gewählt werden. Da weder eine Zerlegung in Teilvektoren noch ein Overhead zum Beginnen der Vektoranweisung erforderlich ist, ist darüber hinaus die Zeit, die für einen zeitlichen Durchlauf eines Mischvorgangs erforderlich ist, dieselbe wie beim herkömmlichen Stand der Technik. Daher wird die Verarbeitungsgeschwindigkeit des erfindungsgemäßen Vektorprozessors für vorab sortierte Eingaben um log&sub2; N erhöht.

Wenn Vektorelemente in aufsteigender Reihenfolge und absteigender Reihenfolge, wie sie von selbst in den Eingangsvektoren vorhanden sind, zu verwenden sind, ist es erforderlich, zu wissen, ob der Sortiervorgang abgeschlossen ist, oder nicht, nachdem die Mehrfachmodus-Mischanweisung ausgeführt wurde. Gemäß dem Verfahren von Fig. 10, das keine Teilvektoren verwendet, wird die Sortierung notwendigerweise nach log&sub2; N Mischvorgängen abgeschlossen. Gemäß dem Verfahren von Fig. 11 kann die Sortierung jedoch nach einem einmaligen Mischvorgang abgeschlossen werden. Gemäß der Erfindung, die die Anzahl von Umkehrungen des Modus zählt, wird daher der Wert des Moduszählers untersucht, nachdem die Mehrfachmodus- Mischanweisung ausgeführt wurde. Wenn der Wert derselbe wie vor dem Ausführen der Mehrfachmodus-Mischanweisung ist, bedeutet dies, daß alle Eingangsdaten in aufsteigender Reihenfolge oder in absteigender Reihenfolge angeordnet sind. Daher besteht nach der Abarbeitung kein Erfordernis zum Ausführen einer Abtastung zum Untersuchen, ob die Sortierung abgeschlossen wurde oder nicht, und die Operation kann wirkungsvoll ausgeführt werden.


Anspruch[de]

1. Vektorprozessor, umfassend eine Datenspeichereinrichtung (111), eine Einrichtung (109X, 109Y) zum Lesen der zu mischenden Vektorelemente zweier Vektoren aus der Datenspeichereinrichtung (111), und

eine Operationseinrichtung (110Z) zur Durchführung einer Mischoperation an jeweils zwei der Leseeinrichtung (109X, 109Y) zugeführten Vektorelementen,

gekennzeichnet durch

eine Einrichtung (110X, 110Y) zum Ermitteln, ob jeder der beiden Vektoren zu einer Sequenz gehören, in der die Vektorelemente in aufsteigender Reihenfolge angeordnet sind, oder zu einer Sequenz, in der die Vektorelemente in absteigender Reihenfolge angeordnet sind, und

eine Bestimmungseinrichtung (107, 108), die bewirkt, daß die Operationseinrichtung (110Z) je nach dem Ermittlungsergebnis der Ermittlungseinrichtung (110X, 110Y) eine Mischoperation entweder in aufsteigender oder in absteigender Reihenfolge durchführt.

2. Vektorprozessor nach Anspruch 1, wobei die Ermittlungseinrichtung (110X, 110Y) so betätigbar ist, daß sie ein nachfolgendes Vektorelement parallel mit der Ausführung der Operation an dem vorhergehenden Vektorelement durch die Operationseinrichtung (110Z) erfaßt.

3. Vektorprozessor nach Anspruch 1 mit einer Einrichtung, die die Mischoperation mit aufsteigender Reihenfolge in eine solche mit absteigender Reihenfolge ändert, wenn beide von der Operationseinrichtung (110Z) zu mischenden Vektorelemente Anfangselemente in einer Sequenz von in aufsteigender Reihenfolge angeordneten Vektorelementen sind, bzw. die Mischoperation mit absteigender Reihenfolge in eine solche mit aufsteigender Reihenfolge ändert, wenn beide von der Operationseinrichtung (110Z) zu mischenden Vektorelemente Anfangselemente in einer Sequenz von in absteigender Reihenfolge angeordneten Vektorelementen sind.

4. Vektorprozessor nach Anspruch 1, wobei die Leseeinrichtung (109X, 109Y) Vektorelemente eines zu sortierenden Vektors in einer ersten und einer davon verschiedenen zweiten Reihenfolge liest und die in der ersten Reihenfolge gelesene Vektorelement-Sequenz und die in der zweiten Reihenfolge gelesene Vektorelement-Sequenz als zwei zu mischende Vektorelemente der Operationseinrichtung (110Z) zuführt.

5. Vektorprozessor nach Anspruch 1,

wobei die Leseeinrichtung eine erste Zuführeinrichtung (109X) aufweist, die Vektorelemente einer ersten Gruppe nacheinander aus der Datenspeichereinrichtung (111) liest und nacheinander der Operationseinrichtung (110Z) zuführt, sowie eine zweite Zuführeinrichtung (109), die Vektorelemente einer zweiten Gruppe nacheinander aus der Datenspeichereinrichtung (111) liest und nacheinander der Operationseinrichtung (110Z) zuführt,

wobei die Ermittlungseinrichtung eine erste Komparatoreinrichtung (110X) aufweist, die ein gerade gelesenes Vektorelement der ersten Gruppe mit dem vorhergehenden Vektorelement der ersten Gruppe vergleicht, sowie eine zweite Komparatoreinrichtung (110Y), die ein gerade gelesenes Vektorelement der zweiten Gruppe mit dem vorhergehenden Vektorelement der zweiten Gruppe vergleicht, und

wobei die Bestimmungseinrichtung (107, 108) je nach den Ausgangssignalen der ersten und der zweiten Komparatoreinrichtung (110X, 110Y) diejenige Operation bestimmt, die an dem gerade gelesenen Vektorelement der ersten Gruppe oder an dem der zweiten Gruppe durchzuführen ist.

6. Vektorprozessor nach Anspruch 5, wobei die Operationseinrichtung (110Z) aufweist:

einen Komparator (806), der ein Vektorelement der von der ersten Zuführeinrichtung (109X) zugeführten ersten Gruppe mit einem Vektorelement der von der zweiten Zuführeinrichtung (109Y) zugeführten zweiten Gruppe vergleicht, und

eine Auswahleinrichtung (800), die eine erste Operation zur Bearbeitung des größeren der Vektorelemente der ersten und der zweiten Gruppe oder eine zweite Operation zur Bearbeitung des kleineren der Vektorelemente der ersten und der zweiten Gruppe auswählt,

wobei die Bestimmungseinrichtung (107, 108) bewirkt, daß die Auswählreinrichtung (800) je nach den Ausgangssignalen der ersten und der zweiten Komparatoreinrichtung (110X, 110Y) entweder die erste oder die zweite Operation ausführt.

7. Vektorprozessor nach Anspruch 6, wobei die Bestimmungseinrichtung (107, 108) aufweist:

eine Einrichtung, die bewirkt, daß die Auswähleinrichtung (800) je nach der bestimmten Operation und dem Ausgangssignal des Komparators (806) ein Vektorelement aus der ersten oder der zweiten Gruppe auswählt, und

eine Einrichtung, die die erste und die zweite Zuführeinrichtung (109X, 109Y) so instruiert, daß ein Vektorelement, das dem durch die Auswahl ausgewählten Vektorelement am nächsten steht, und ein Vektorelement, das durch die Auswahl nicht ausgewählt ist, der Operationseinrichtung (110Z) als das als nächstes zu bearbeitende Paar von Vektorelementen zugeführt wird.

8. Vektorprozessor nach Anspruch 7, wobei die erste Zuführeinrichtung (109X) zu sortierende Vektorelemente, beginnend mit dem ersten Element, und die zweite Zuführeinrichtung (109Y) zu sortierende Vektorelemente, beginnend mit dem letzten Element, nacheinander ausliest.

9. Verfahren zum Mischen von Vektorelementen zweier Vektoren, mit folgenden Schritten:

(a) es wird ermittelt, ob die beiden Vektoren zu einer Vektorelement-Sequenz gehören, in der die Vektorelemente in aufsteigender Reihenfolge angeordnet sind, oder zu einer solchen, in der die Vektorelemente in absteigender Reihenfolge angeordnet sind;

(b) aufgrund des Ergebnisses des Ermittlungsschrittes (a) wird bestimmt, ob die beiden zu mischenden Vektorelemente einem Mischvorgang mit aufsteigender oder mit absteigender Reihenfolge zu unterziehen sind, und

(c) an den beiden Vektorelementen wird der so bestimmte Mischvorgang ausgeführt,

wobei die Schritte (a) bis (c) von einem Vektorprozessor ausgeführt werden.

10. Verfahren nach Anspruch 9, wobei die Ermittlung parallel mit dem Mischvorgang an den jeweils vorhergehenden Vektorelementen in den beiden Vektoren durchgeführt wird.

11. Verfahren nach Anspruch 9, wobei in dem Schritt (b) erfaßt wird, ob das Ergebnis des Schrittes (a) für die als nächstes zumischenden beiden Vektorelemente von dem für die vorher gemischten beiden Vektorelemente verschieden ist, und der Schritt (b) aufgrund dieser Ermittlung durchgeführt wird.

12. Verfahren nach Anspruch 11, wobei in dem Schritt (b) der Mischvorgang mit aufsteigender Reihenfolge in einen solchen mit absteigender Reihenfolge geändert wird, wenn beide als nächste zu bearbeitenden Vektorelemente Anfangselemente in einer Sequenz von in aufsteigender Reihenfolge angeordneten Vektorelementen sind, bzw. der Mischvorgang mit absteigender Reihenfolge in einen solchen mit aufsteigender Reihenfolge geändert wird, wenn beide als nächste zu bearbeitenden Vektorelemente Anfangselemente in einer Sequenz von in absteigender Reihenfolge angeordneten Vektorelementen sind.







IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com