AT501213B1 - Verfahren zum steuern der zyklischen zuführung von instruktionswörtern zu rechenelementen und datenverarbeitungseinrichtung mit einer solchen steuerung - Google Patents

Description

2 AT 501 213 B1

Die Erfindung betrifft ein Verfahren zum Steuern der zyklischen Zuführung von Instruktionswörtern zu parallel arbeitenden Rechenelementen einer Datenverarbeitungseinrichtung, wobei die Instruktionswörter aus einem Programmspeicher ausgelesen werden. 5 Weiters bezieht sich die Erfindung auf eine Datenverarbeitungseinrichtung mit mehreren parallel arbeitenden Rechenelementen, die zyklisch Instruktionswörter aus einem Programmspeicher unter Steuerung durch eine Steuereinheit zugeführt erhalten.

Es ist bekannt, Datenverarbeitungseinrichtungen zur Steigerung der Recheneffizienz mit einer io Anzahl von parallel arbeitenden Rechenelementen (auch Computing Slices genannt) auszubil-den. Bei diesen auch Vektormaschinen genannten Datenverarbeitungseinrichtungen sind im Prinzip zwei verschiedene Arten der Programmierung und Datenverarbeitung möglich. Bei der einen Programmierungsart wird ein und das selbe Instruktionswort für alle parallel arbeitenden Rechenelemente verwendet, so dass diese Rechenelemente jeweils die selben Operationen 15 ausführen. Den parallelen Rechenelementen werden dabei jeweils unterschiedliche Daten zur Verarbeitung zugeführt. Diese Verarbeitung wird auch Vektorverarbeitung genannt, und die allgemein übliche Benennung für diese Form der Abarbeitung von Daten wird SIMD-Verarbeitung genannt (SIMD - Single Instruction, Multiple Data). Bei der anderen, sich grundsätzlich von der erstgenannten Verarbeitungsart unterscheidenden Verarbeitungsart führen die 20 parallelen Rechenelemente in jedem Arbeitsschritt jeweils unterschiedliche Instruktionen aus, wobei die zu verarbeitenden Daten für jedes Rechenelement verschieden, aber in Prinzip auch gleich sein können. Diese Verarbeitungsform wird allgemein MIMD-Verarbeitungsart genannt (MIMD - Multiple Instruction, Multiple Data). Zwischen diesen beiden Extremfällen der SIMD-und MIMD-Verarbeitungsarten sind auch Mischformen möglich und häufig angewandt. Insbe-25 sondere in der digitalen Signalverarbeitung werden Parallelrechnerarchitekturen derart gestaltet, dass sie beide Programmierungs- bzw. Verarbeitungsarten sowie Mischformen ermöglichen. Für einen solchen Parallelrechner ist in der US 6 272 616 B1 bereits vorgeschlagen worden, im 30 Fall des Umschaltens zwischen verschiedenen Betriebsarten, wie SIMD und MIMD, auch Hardwareteile der einzelnen parallelen Verarbeitungspfade, die gerade nicht benötigt werden, zu deaktivieren, um Strom zu sparen. Weiters ist es aus der US 5 212 777 A bekannt, zur flexiblen Speicher-Ausnützung einen Crossbar-Switch zwischen Prozessoren, die im SIMD- bzw. im MIMD-Modus betrieben werden, und einem Arbeitsspeicher anzuordnen. Dabei geht es um die 35 dynamische Nutzung von Speicherbereichen durch parallele Recheneinheiten, wobei der Crossbar-Switch zur Adressenumleitung eingesetzt wird. Darüber hinaus kann auch der Zugriff der Prozessoren auf Datenspeicherbereiche durch den Crossbar-Switch verschoben werden. Die US 6 044 450 A befasst sich ferner mit der Verarbeitung von langen Instruktionswörtern (VLIW - Very long Instruction Words), wobei in darin enthaltenen kurzen Befehlswörtern die 40 Anzahl von folgenden NOP-lnstruktionen (NOP - No Operation) aufgenommen wird, die von folgenden, langen Befehlswörtern gestrichen werden. Im Einzelnen ist hier eine zweistufige, spezielle Codekomprimierung vorgesehen, wobei in einer „Zeit“-Kompression NOPs zusammengefasst werden und in einer „Raum“-Kompression eventuell idente Befehlskategorien von Instruktionen - nicht jedoch ganze Befehle - für parallele Recheneinheiten mit einem Gruppeni-45 dentifikator zusammengefasst werden. Eine Rechnerarchitektur, die speziell für VLIW-Instruktionen entwickelt wurde, ist im Übrigen im Artikel ,A VLIW Architecture for a Trace Sche-duling Compiler“ von R.P. Colwell et al., October 1987, ACM 0-89791-238-1/87/1000-0180; Proceedings of the Second Intern. Conference on Architectual Support for Programming Lan-guages and Operating Systems, S. 180-192, beschrieben. 50

Ganz allgemein gilt für Rechner-Architekturen wie vorstehend angeführt mit parallelen Rechenelementen Folgendes:

Den parallel arbeitenden Rechenelementen sind Befehlsregister zugeordnet, in denen die ein-55 zelnen Instruktionswörter für die Parallelrechenelemente sowie die Verarbeitungsvorgänge in 3 AT 501 213 B1 den Rechenelementen gespeichert werden. Wenn nun angenommen wird, dass das Instruktionsspeicher-Subsystem bzw. der Programmspeicher mit derselben Taktrate arbeitet wie die einzelnen Rechenelemente oder Rechenwerke, muss das Instruktionsspeicher-Subsystem in jedem Verarbeitungsschritt soviele Instruktionswörter gleichzeitig zur Verfügung stellen, wie 5 parallel arbeitende Rechenelemente vorhanden sind. Wenn die Anzahl der parallel arbeitenden Rechenelemente (Slices) mit n bezeichnet wird, und jedes Slice-Instruktionswort eine Breite von k Bits hat, dann muss, wenn nur die Slice-Instruktionswörter berücksichtigt werden, die Datenwortbreite für das Instruktionsspeicher-Subsystem n x k, also n x die Slice-Instruktionswortbreite, betragen. Hinzu kommt noch die Datenwortbreite für das sog. globale Instruktions-io wort, das bei Parallelrechnerarchitekturen in üblicher Weise zur Kontrolle des Programmflusses und für allgemein gültige Verwaltungsaufgaben verwendet wird. Wenn nun weiter angenommen wird, dass dieses globale Instruktionswort die selbe Wortbreite wie jedes Slice-Instruktionswort hat, so ergibt sich eine Gesamtwortbreite des Instruktionsspeicher-Subsystems von (n+1) x k, mit k = Slice-Instruktionswortbreite. Wenngleich eine solche Form der Instruktionswortzuführung 15 ersichtlich sowohl für die vorerwähnte MIMD-Verarbeitungsart als auch für die SIMD-Verarbeitungsart, sowie selbstverständlich auch für alle möglichen Mischformen hievon geeignet ist, so ist doch von großem Nachteil, dass dann, wenn nicht für alle parallel arbeitenden Rechenelemente eigene Instruktionswörter benötigt werden (was der MIMD-Verarbeitungsart entspricht), sondern zumindest teilweise die selben Instruktionswörter für einzelne der paralle-20 len Rechenelemente verwendet werden, die Ausnützung der Speicherkapazität im Instruktionsspeicher-Subsystem schlecht ist, und diese schlechte Ausnützung ist besonders extrem im Fall der SIMD-Verarbeitungsart, in der für alle Rechenelemente ein und das selbe Instruktionswort gültig ist, das aber für jedes der n Rechenelemente, also n-mal, gespeichert wird. 25 Es ist nun Aufgabe der Erfindung, hier Abhilfe zu schaffen und ein Verfahren bzw. eine Datenverarbeitungseinrichtung wie einleitend angegeben vorzusehen, wobei der Ausnützungsgrad, die Effizienz, bei der Zuführung der Instruktionswörter zu den Parallelrechenelementen verbessert bzw. optimiert wird. In der Folge wird somit eine Reduktion der Instruktionswörterzugriffe pro Zeiteinheit und demzufolge wiederum eine Reduktion des Leistungsverbrauchs der beteilig-30 ten Schaltungskomponenten angestrebt.

Zur Lösung der gestellten Aufgabe sieht die Erfindung ein Verfahren bzw. eine Datenverarbeitungseinrichtung wie in den unabhängigen Ansprüchen angegeben vor. Vorteilhafte Ausführungsformen und Weiterbildungen sind in den abhängigen Ansprüchen definiert. 35

Mit der erfindungsgemäßen Technik wird eine Art Instruktionskomprimierung ermöglicht, wodurch der Ausnützungsgrad um einen Faktor verbessert wird, der je nach Verarbeitungsart bis zu einem (n+1)/2-fachen im Fall der SIMD-Verarbeitungsart beträgt. Dabei wird im selben Ausmaß auch eine Reduktion der Instruktionswort-Zugriffe pro Zeiteinheit erzielt, und dies bedeutet 40 wiederum einen reduzierten Leistungsverbrauch der zugehörigen Schaltungsteile. Dem steht entgegen, dass eine eigene Steuerinformation bzw. ein Verteiler für die Verteilung der Instruktionswörter erforderlich ist, wobei jedoch die Steuerinformation relativ zur übrigen Programmdatenmenge tatsächlich praktisch nicht ins Gewicht fällt. Wenn diese Steuerinformation, wie dies bevorzugt wird, im globalen Instruktionswort vorgesehen wird, ist es nur notwendig, dieses 45 globale Instruktionswort um ein entsprechendes Bitfeld, zumindest der Länge log2(n) x n, zu erweitern. Dies rührt daher, dass jedem der n Rechenelemente in einem Instruktionswörter-Verteilfeld der Steuerinformation ein eigener Feldbereich zugeordnet wird, wobei diese gesonderten Feldbereiche (insgesamt n, entsprechend der Anzahl n der Rechenelemente) jeweils Zuordnungsbits aufgenommen sind, die die jeweils zugehörigen, verschiedenen Instruktions-50 Wörter indexmäßig angeben, wobei die Reihung der Feldbereiche der Reihung der Rechenelemente entspricht, so dass durch die Zuordnungsbits in den Feldbereichen auch die Zuordnung der Instruktionswörter zu den Rechenelementen gegeben ist. Es genügt, als Zuordnungsbits einfach Nummern der Slice-Instruktionswörter anzugeben. Die maximale Zahl, die mit den Zuordnungsbits in digitaler Form anzugeben ist, ist die Zahl n, wobei im Fall von acht Rechenelementen (also n=8) in jedem Feldbereich daher drei Bits Platz haben müssen, da mit drei Bits 55 4 AT 501 213 B1 acht Zahlen angebbar sind. Dementsprechend hat das Verteilfeld insgesamt eine Länge von 3 x 8 = 24 Bits. Dabei ist wie erwähnt jedem der n Rechenelemente eine feste Adresse - entsprechend der Position des zugehörigen Feldbereichs im Instruktionswörter-Verteilfeld - zugeordnet, d.h. die Position (oder der Index der Position) des zugehörigen Verteilfeldes gibt die 5 Adresse des jeweiligen Rechenelements an. Auf diese Weise wird auch die Bildung eines virtuellen Rechenelement-Zeigers („Slice-Pointer“) ermöglicht.

In der Steuerinformation kann für Steuer- und Prüfzwecke ein weiterer Feldbereich vorgesehen werden, der keinem Rechenelement zugeordnet wird, sondern angibt, wie viele gültige, d.h. von io einander verschiedene Instruktionswörter momentan vorliegen und dem zugehörigen globalen Instruktionswort folgen. Dieses Kontroll-Bitfeld muss demgemäß wiederum eine Bitbreite aufweisen, die ausreicht, um die Zahl n anzugeben, also ebenfalls eine Bitbreite von log2(n), im Fall von n=8 daher eine Breite von drei Bits. 15 Im Fall einer reinen SIMD-Programmierung folgt dem jeweiligen globalen Instruktionswort ein einziges Slice-Instruktionswort, das in einem Abarbeitungszyklus für alle Rechenelemente gültig und diesem zuzuführen ist. In diesem Fall enthalten alle Feldbereiche im Instruktionswörter-Verteilfeld der Steuerinformation nur die eine Nummer des einen Instruktionswortes, z.B. die Nummer „0“, wobei beispielsweise im Fall von acht Rechenelementen die Nummerierung von 0 20 bis 7 geht. Im aus dem Programmspeicher ausgelesenen ISS-Wort (ISS - Instruktionsspeicher-Subsystem) werden für einen solchen Verarbeitungsschritt nur zwei Instruktionsfelder belegt, nämlich das eine für das globale Instruktionswort und das andere für das eine Instruktionswort, das für alle acht (oder allgemein n) Rechenelemente in gleicher Weise gültig ist. Wenn dann das ISS-Wort für insgesamt neun Instruktionsfelder ausgelegt ist (ein globales Instruktionswort 25 und n = 8 Einzel-Instruktionswörter), so kann das dritte Instruktionsfeld im ISS-Wort bereits wieder ein globales Instruktionswort für den folgenden Abarbeitungszyklus enthalten, wobei auf dieses globale Instruktionswort das Instruktionswort oder die unterschiedlichen Instruktionswörter des folgenden Abarbeitungszyklus folgen. Hieraus ergibt sich auch, dass es nicht erforderlich ist, ISS-Wörter aus dem Programmspeicher in der Rate der Befehlsabarbeitung auszulesen, 30 vielmehr kann dieser Auslesezyklus entsprechend einem Quotienten gleich (n+1)/2 im optimalen Fall (wenn eine SIMD-Verarbeitungsart gegeben ist) reduziert werden.

In entsprechender Weise ist auch der dem Programmspeicher zugeordnete Programmzähler, der die Programmwörter im ISS adressiert, nicht mehr für jeden einzelnen Verarbeitungsschritt 35 zu inkrementieren, sondern erst dann, wenn ein ISS-Wort abgearbeitet ist. Für diese Arbeitsweise mit rationalisierter Auslesung von Instruktionswörtern aus dem Programmspeicher ist zweckmäßig auch in Ergänzung zum Programmzähler ein sog. Slot-Pointer mitzuführen, das ist ein Zeiger, der auf das jeweils gültige (aktuelle) globale Instruktionswort zeigt. Dieser Slot-Pointer ist nach jedem Verarbeitungsschritt um die Anzahl x (mit 1<xsn) der folgenden ver-40 schiedenen Slice-Instruktionswörter zu inkrementieren.

Da ein ISS-Wort eine Breite von n+1 Einzel-Instruktionswörtern hat (ein globales Instruktionswort + n Slice-Instruktionswörter), kann es Vorkommen, dass dann, wenn immer mehrere oder sogar alle Instruktionswörter für die Rechenelemente ident sind, wobei dann wie vorstehend 45 ausgeführt pro ISS-Wort mehrere Einheiten bestehend aus einem globalen Instruktionswort und zugehörigen Slice-Instruktionswörtern, in den n+1 Instruktionsfeldern untergebracht werden können, je nach Fallkonstellation ein folgendes globales Instruktionswort zwar noch in einem ISS-Wort vorliegt, die zugehörigen, folgenden Slice-Instruktionswörter (im Extremfall wie erwähnt auch nur ein einziges solches Slice-Instruktionswort) bereits im nächsten ISS-Wort zu so liegen kommen (bzw. kommt). Insbesondere für derartige Fälle ist es von Vorteil, wenn in der Steuerinformation ein Umschaltfeld vorgesehen wird, um im gegebenen Fall einen Sprung auf das nächste Instruktionswort im Befehlsregister, auf das nächste ISS-Wort, zu veranlassen, wenn das nächste globale Instruktionswort an einer neuen Adresse steht. Um in diesen Fällen die Decodierung der Instruktionen möglichst effizient zu gestalten, sollte nicht nur das jeweils 55 aktuelle ISS-Wort, sondern auch bereits das unmittelbar darauf folgende ISS-Wort (in dem sich 5 AT 501 213 B1 beispielsweise Slice-Instruktionswörter befinden, die zu einem globalen Instruktionswort gehören, das im gerade noch aktuellen ISS-Wort enthalten ist) sofort verfügbar sein. Es ist daher günstig, wenn zwei Puffer-Befehlsregister vorgesehen sind, von denen das eine zur Speicherung der jeweils aktuellen Instruktionswörter und das andere zur Speicherung der jeweils 5 nächstgültigen Instruktionswörter eingerichtet ist. Im Fall von zwei solchen Puffer-Speichern oder Puffer-Befehlsregistern (sog. „Ahead-Buffer“) kann dann die für die Überführung der ISS-Wörter aus dem Programmspeicher verantwortliche Steuereinheit den jeweils gerade nicht (mehr) in Bearbeitung befindlichen Puffer mit dem nächsten ISS-Wort füllen; dadurch wird ein kontinuierlicher Programmfluss gewährleistet, der frei von Unterbrechungen ist, da sofort zum io nächsten ISS-Wort übergegangen werden kann, ohne dass erst ein Auslesen aus dem Programmspeicher abgewartet werden muss. Der Rechenelemente-Zeiger (Slice-Pointer) dient während der Decodierung der Slice-Instruktionswörter als Hilfsvariable, um die Slice-Instruktionswörter relativ zum globalen Instruktionswort zu adressieren. 15 Für die Verteilung der einzelnen Slice-Instruktionswörter auf die entsprechenden Rechenelemente wird ein Instruktionswort-Verteiler zwischengeschaltet, der entsprechend dem Inhalt der Steuerinformation, insbesondere innerhalb des globalen Instruktionswortes, das im Puffer-Befehlsregister geladen ist, die jeweiligen Slice-Instruktionswörter auf die Rechenelemente in der gewünschten Weise verteilt. Dieser Instruktionswort-Verteiler kann auch als Multiplexer 20 bzw. Kreuzfeldverteiler angesehen werden, und er wird bevorzugt durch eine logische Gatterschaltung gebildet, wobei entsprechende Steuerbits, je nach der aktuellen Steuerinformation, an den Steuereingängen der einzelnen Gatter angelegt werden, um die Instruktionswörter zu den einzelnen Rechenelementen in gezielter Weise durchzulassen bzw. ihren Durchgang zu den Rechenelementen zu sperren. 25

Die Erfindung wird nachfolgend anhand von bevorzugten Ausführungsbeispielen, auf die sie jedoch nicht beschränkt sein soll, und unter Bezugnahme auf die Zeichnung noch weiter erläutert. Es zeigen: Fig. 1 schematisch eine erfindungsgemäße Datenverarbeitungseinrichtung, wobei nur jene Teile veranschaulicht sind, die für die Erfindung von Bedeutung sind; Fig. 2 ein 30 Schema zur Veranschaulichung einer Datenverarbeitung bei einer reinen SIMD-Programmierung, bei der also ein einziges Slice-Instruktionswort für alle n Rechenelemente gültig ist; Fig. 3 ein der Fig. 2 ähnliches Schema, bei dem jedoch zwei verschiedene Slice-Instruktionswörter gegeben sind, die abwechselnd auf die n Rechenelemente aufzuteilen sind; Fig. 4 den anderen Extremfall, nämlich jenen einer reinen MIMD-Programmierung, bei der lauter 35 verschiedene Slice-Instruktionswörter für die einzelnen Rechenelemente vorliegen; und Fig. 5 ein Zustandsdiagramm zur Veranschaulichung der Arbeitsweise der Steuereinheit der Datenverarbeitungseinrichtung gemäß Fig. 1, soweit diese Arbeitsweise hiervon Bedeutung ist.

In Fig. 1 ist ein Schema einer Datenverarbeitungseinrichtung 1, beispielsweise eines digitalen 40 Signalprozessors, gezeigt, wobei nur jene Komponenten veranschaulicht sind, die für die vorliegende Instruktionskomprimierung von Bedeutung sind, wogegen andere Komponenten, wie etwa jene für die Zuführung von zu verarbeitenden Daten und für die Ausgabe der berechneten Daten, der besseren Übersichtlichkeit halber weggelassen wurden. Diese Komponenten können in völlig herkömmlicher Weise ausgebildet werden, so dass sich auch eine Erläuterung 45 hiervon erübrigen kann.

Gemäß Fig. 1 enthält die Datenverarbeitungseinrichtung 1 einen Programmspeicher 2, der unter zugehörigen Adressen (vgl. auch Fig. 2 bis 4) entsprechende Programm-Instruktionen, die sog. ISS-Wörter (ISS-lnstruktionsspeicher-Subsystem), enthält. Weiters ist eine zentrale Steu-50 ereinheit 3 vorgesehen, die zum Auslesen der Instruktionen (in den sog. Fetch-Zyklen) dient, und von der ein Programmzähler 4 geführt und entsprechend den Fetch-Zyklen inkrementiert wird, um auf die jeweils im nächsten Schritt abzuarbeitende Befehlszeile (Adresse) zu zeigen. Eine mögliche Zustandsmaschine dieser Steuereinheit 3 ist in der nachfolgend noch näher zu erläuternden Fig. 5 gezeigt; diese zentrale Steuereinheit 3 wird auch als Programm-Sequenzer 55 bezeichnet. 6 AT 501 213 B1

Gemäß Fig. 1 werden die in den Fetch-Zyklen ausgelesenen ISS-Wörter einem von zwei parallelen Puffer-Befehlsregistern oder Pufferspeichern 5 bzw. 5' (vgl. außer Fig. 1 auch die Fig. 2 bis 4) zugeführt. Jedes ISS-Wort enthält ein globales Instruktionswort G sowie die für den jeweiligen Abarbeitungsschritt erforderlichen, voneinander verschiedenen Instruktionswörter (Slice-5 Instruktionswörter) für die Rechenelemente (Slices), im Fall von Fig. 1 zwei voneinander verschiedene Instruktionswörter SO, S1. Im vorliegenden Beispiel sind weiters acht (n=8) parallel arbeitende Rechenelemente CSO bis CS7 vorhanden (CS - Computing Slice), denen jeweils ein Rechenelement-Instruktionsfeld SIF (SIF - Slice Instruction Field) zugeordnet ist. Um die ausgelesenen, pro ISS-Wort vorhandenen, voneinander verschiedenen Instruktionswörter SO, S1 in io der gewünschten, durch Programmierung vorgegebenen Weise auf die Rechenelemente CSO bis CS7 zu verteilen, ist ein Instruktionswort-Verteiler 6 vorgesehen, wobei es sich hier um eine logische Gatterschaltung, mit entsprechenden Gatterkreisen, handelt, und wobei als Steuersignale Steuerinformationen an einem Eingang 6.1 zugeführt werden. Die jeweilige Steuerinformation ist im gezeigten Beispiel im globalen Instruktionswort G vorhanden, wie dies nachstehend 15 anhand der Fig. 2 bis 4 noch näher erläutert werden wird. In Fig. 1 sind demgemäß die im gegebenen Beispiel vorgegebenen Durchschaltwege für die Slice-Instruktionswörter SO, S1 eingezeichnet, wobei ersichtlich ist, dass die beiden Instruktionswörter SO, S1 abwechselnd den aufeinander folgenden Rechenelementen CSO bis CS7 (über die Instruktionsfelder SIF) zugeführt werden. Diese Verarbeitungsart ist auch schematisch in der nachfolgend noch näher 20 erläuterten Fig. 3 veranschaulicht.

Im gezeigten Ausführungsbeispiel sind somit n = 8 parallele Rechenelemente CS vorgesehen, was eine in der Praxis häufig vorkommende Anzahl ist. Es können aber selbstverständlich abweichend davon auch mehr oder weniger Rechenelemente CS vorhanden sein, wie etwa 25 bloß zwei oder vier oder aber 32 Rechenelemente, je nach Zielvorstellungen.

Bevor nun die Verarbeitungsart bei zwei voneinander verschiedenen Instruktionswörtern SO, S1 anhand der Fig. 3 näher erläutert wird, soll noch anhand der Fig. 2 zuvor der Extremfall der SIMD-Programmierung beschrieben werden, bei der ein einziges Slice-Instruktionswort S für 30 alle acht (allgemein alle n) Rechenelemente CS gültig ist. Damit ergibt sich für Fig. 2 die Situation, dass im gerade aktuellen Puffer-Befehlsregister oder Puffer-Speicher 5 bzw. 5', abwechselnd ein globales Instruktionswort G und ein zugehöriges, dem globalen Instruktionswort G folgendes Slice-Instruktionswort S vorliegen; wie ersichtlich hat der Pufferspeicher 5 (und ebenso der parallele Pufferspeicher 5') eine Wortbreite von neun Instruktionswörtern, wobei die 35 einzelnen Felder mit den Nummern 0 bis 8 nummeriert sind. Die Slice-Instruktionswörter S sind gemäß Fig. 2 jeweils für alle Rechenelemente CS ident, d.h. es ist jeweils nur ein einziges Instruktionswort S vorhanden, das die Nummer „0“ aufweist. (Wie andererseits aus Fig. 3 zu ersehen ist, haben dort die beiden verschiedenen Slice-Instruktionswörter S (bzw. genauer SO, S1) jeweils die Nummern „0“ bzw. „1“). 40

Aus Fig. 2 ist weiters im unteren Bereich die Struktur eines globalen Instruktionswortes ersichtlich. Das globale Instruktionswort G enthält in einem Feld G.1 die übliche globale Instruktions-Information, die bei Parallelrechnerarchitekturen zur Kontrolle des Programmflusses ebenso wie für allgemein gültige Verwaltungsaufgaben verwendet wird. Zusätzlich ist ein Erweiterungsfeld 45 G.2 vorhanden, bei dem es sich um ein Bitfeld mit der Länge log2(n) x (n+1) + 1 handelt. Als wesentlichen Teil enthält dieses Erweiterungsbitfeld G.2 ein Instruktionswörter-Verteilfeld G.2.2, welches acht (allgemein n) Feldbereiche, je einen in fixer Zuordnung zu einem Rechenelement CS, aufweist. Diesem Verteilfeld G.2.2 geht ein Umschaltfeld G.2.1 voraus, das entweder ein „0“-Bit oder ein „Γ-Bit enthalten kann und das dann, wenn in diesem Umschaltfeld eine „1“ so steht, einen Sprung auf das nächste Befehlswort im Programmspeicher (Befehlsregister) 2 auslöst, wenn die nächste globale Instruktion G an einer neuen Adresse steht.

In den einzelnen Feldbereichen des Erweiterungsbitfeldes G.2, die wie erwähnt den einzelnen Rechenelementen CS beispielsweise in der unmittelbaren Aufeinanderfolge direkt zugeordnet 55 sind, stehen die Nummern oder Indexe der verschiedenen im Pufferspeicher 5 zwischengespei- 7 AT 501 213 B1 cherten Slice-Instruktionswörter S. Im Fall der Fig. 2 liegt nur ein einziges solches Instruktionswort S vor, das die Nummer „0“ hat, und demgemäß ist in allen - durch strichlierte Linien voneinander getrennten - Feldbereichen des Verteilfeldes G.2.2 die Nummer „0“ eingetragen. Jeder Feldbereich hat eine Bitlänge entsprechend der größtmöglichen Zahl oder Nummer, die vor-5 kommen kann, also gleich n, entsprechend der Anzahl der Rechenelemente CS; im vorliegenden Beispiel gilt n = 8, wobei sich für n = 8 ergibt, dass jeder Feldbereich drei Bitstellen aufweist, da mit drei Bits acht verschiedene Zahlen oder Nummern binär (von 000 bis 111) angegeben werden können. io In einem dem Verteilfeld G.2.2 folgenden Kontrollfeld G.2.3, das ebenfalls eine Bitbreite log2(n), also hier gleich drei Bits, aufweist, wird die Zahl der jeweils verschiedenen Instruktionswörter S angegeben. Im Fall der Fig. 2, wo jeweils nur ein einziges Instruktionswort S gegeben ist, steht somit im KontrolI-Bitfeld G.2.3 die Zahl „1“. (Im Fall der Fig. 3, wo zwei verschiedene Instruktionswörter S, mit den Nummern 0 und 1, vorliegen, steht in diesem Kontrollfeld die Zahl „2“, und 15 im Beispiel der Fig. 4, in dem acht verschiedene Slice-Instruktionswörter SO bis S7 vorliegen, steht im Kontrollfeld die Zahl „8“.)

Wie aus Fig. 2 im Bereich des Pufferspeichers 5 bzw. 5' ersichtlich ist, sind für jeden Verarbeitungsschritt im ISS-Wort nur zwei Instruktionsfelder zu belegen, nämlich eines für das globale 20 Instruktionswort G und das zweite für das Slice-Instruktionswort S. Das dritte Instruktionsfeld kann bereits für das globale Instruktionswort G des folgenden Verarbeitungszyklus verwendet werden usw. Es ist daher auch nicht erforderlich, die ISS-Wörter im Takt der Befehlsabarbeitung aus dem Programmspeicher 2 zu holen, und auch der Programmzähler 4, der die Programmwörter im Programmspeicher 2 adressiert, ist nicht mehr für jeden Verarbeitungsschritt zu 25 inkrementieren.

In Ergänzung zum Programmzähler 4 wird jedoch ein auf das jeweils gültige globale Instruktionswort G zeigender Zeiger, der Slot-Pointer 8, mitgeführt, wobei hierfür wie aus Fig. 1 ersichtlich, die zentrale Steuereinheit 3 verantwortlich ist. Ein weiterer Zeiger ist der Rechenelement-30 Zeiger oder Slice-Pointer 9, der als Hilfsvariable während der Decodierung der Slice-Instruktionen zur Adressierung der Slice-Instruktionswörter S relativ zum zugehörigen globalen Instruktionswort G dient, und der de facto den Status des Verteilfeldes G.2.2 widerspiegelt.

Aus Fig. 1 ist im Übrigen noch eine Verbindung 10 vom Pufferspeicher 5 bzw. 5' zur Steuerein-35 heit 3 ersichtlich, über die auch die im globalen Instruktionswort G enthaltenen allgemeinen globalen Instruktionsinformationen, aus dem Bereich G.1, der Steuereinheit 3 zugeführt werden.

Wie aus Fig. 2 ferner ersichtlich ist, erbringt der jeweils zweite, parallele Pufferspeicher 5' den Vorteil, dass bereits die jeweils folgenden ISS-Wörter zwischengespeichert werden können, 40 während noch die Instruktionen im aktuellen Pufferspeicher 5 abgearbeitet werden. Dies ist vor allem dann von besonderem Vorteil, wenn wie in Fig. 2 ein globales Instruktionswort G noch im aktuellen Pufferspeicher 5 zu liegen kommt, wogegen das zugehörige Slice-Instruktionswort S bereits in einem folgenden ISS-Wort liegt, wobei es nichtsdestoweniger zufolge des parallelen Pufferspeichers 5' unmittelbar zu den Rechenelementen CS übertragen werden kann, so dass 45 die Decodierung der Instruktionen außerordentlich effizient erfolgen kann.

Die Darstellung in Fig. 3 entspricht jener gemäß dem Schema von Fig. 2, wobei nun jedoch die bereits in Fig. 1 angedeutete Verarbeitungsart oder Programmierung mit jeweils zwei verschiedenen Slice-Instruktionswörtern SO, S1 zugrunde gelegt ist. Auf jedes globale Instruktionswort so G folgen somit zwei Slice-Instruktionswörter SO, S1, und die Verteilung dieser Instruktionswörter SO, S1 auf die acht Rechenelemente CS0 bis CS7 erfolgt wie im Verteilfeld G.2.2 angegeben (s. dort die Nummern „0“ und „1“), also hier in abwechselnder Aufeinanderfolge. Es wäre aber beispielsweise auch eine Verteilung denkbar, gemäß welcher die ersten vier Rechenelemente CS0 bis CS3 das erste Instruktionswort SO (Nummer „0“ in G.2.2) und die nächsten vier Re-55 chenelemente CS4 bis CS7 das zweite Instruktionswort S1 (Nummer „1“ in G.2.2) zugeführt 8 AT 501 213 B1 erhalten sollen; in diesem Fall würden die Zahlen (Nummern) im Verteilfeld G.2.2 daher wie folgt sein (nicht dargestellt): 00001111. Selbstverständlich sind auch noch andere, beliebige Formen der Verteilung möglich und durch die Zahlen bzw. deren Position im Verteilfeld G.2.2 eindeutig gegeben. Entsprechend diesen Zahlen, somit entsprechend diesen Steuerinformatio-5 nen, wird dann im Verteiler 6, einem Multiplexer oder Kreuzfeldverteiler von an sich bekannter Art, die logische Gatterschaltung angesteuert, um die Instruktionswörter in der vorgegebenen Weise durchzulassen bzw. zu sperren. Nach jeder Decodierphase wird der Slot-Pointer 8 auf das folgende globale Instruktionswort G gesetzt, vgl. auch in Fig. 3 den mit strichpunktierter Linie eingezeichneten Slot-Pointer 8. Damit kann dann die Verteilung der Slice-Instruktions-io Wörter S für den nächsten Rechenzyklus von Neuem beginnen.

Wie ersichtlich, ist die zentrale Steuereinheit 3 für den Programmfluss allgemein wie auch für die Bereitstellung und Verteilung der Instruktionen verantwortlich. Bei einem Programmstart wird über die Steuereinheit 3 das erste Programmwort, das aus einem globalen Instruktionswort 15 G und einem oder mehreren Slice-Instruktionswort bzw. -Wörtern S besteht, aus dem Programmspeicher 2 in den Pufferspeicher 5 geholt. Während der Decodierphase entscheidet die Steuereinheit 3 anhand der über die Verbindung 10 zugeleiteten Information, die im globalen Instruktionswort G gegeben ist, unter anderem auch die Verteilung, d.h. in welcher Folge die Slice-Instruktionswörter S an die Rechenelemente CS weitergeleitet werden. Die Verteilung wird 20 dann über den Verteiler 6 wie beschrieben bewerkstelligt.

In Fig. 4 ist der im Vergleich zu Fig. 2 konträre extreme Verarbeitungsmodus veranschaulicht, in dem für die einzelnen Rechenelemente CS jeweils voneinander verschiedene Slice-Instruktionswörter SO bis S7 vorliegen. Dies entspricht der vorerwähnten reinen MIMD-25 Programmierung, und die Aufteilung der Slice-Instruktionswörter S ist ident mit jener Aufteilung, die sich ohne die vorliegende Instruktionskomprimierung ergibt. Im Erweiterungsfeld G2 des globalen Instruktionswortes G enthalten die einzelnen Feldbereiche 7 des Verteilfeldes G.2.2 die verschiedenen Zahlen 0 bis 7, d.h. jene Zahlen, die - in der gegebenen Reihenfolge - die Slice-Instruktionswörter im ISS-Wort bezeichnen, und die auch der Reihenfolge der Rechen-30 elemente CS0 bis CS7 entsprechen. Das darauf folgende Kontrollfeld G.2.3 enthält die Zahl „8“ als die Anzahl der dem globalen Instruktionswort G im Pufferspeicher 5 bzw. 5' folgenden verschiedenen Slice-Instruktionswörter S. Dieser Fall der reinen MIMD-Programmierung führt somit zu einer völlig herkömmlichen Arbeitsweise der Datenverarbeitungseinrichtung 1, wobei sich die beschriebenen erfindungsgemäßen Maßnahmen zur Instruktionskomprimierung hier nicht aus-35 wirken können. Es kommt jedoch dann zu einer Verbesserung des Ausnützungsgrades, wenn pro ISS-Wort zumindest zwei Slice-Instruktionswörter gleich sind, bis zu einer Verbesserung um einen Faktor (n+1)/2, nämlich im Fall der reinen SIMD-Programmierung (siehe Fig. 2). In diesem Fall wird der Programmablauf besonders kompakt, und es werden pro Fetch-Zyklus somit 4,5 Befehlszyklen erreicht, wenn acht Rechenelemente CS angenommen werden. 40

In Fig. 5 ist die Steuereinheit 3 als finite Zustandsmaschine veranschaulicht, wobei sie während des Betriebs folgende Zustände einnehmen kann:

In einem Zustand 11 „Reset“ werden alle Systemvariablen auf ihre Default-Werte zurückgesetzt. 45

In einem Zustand 12 „Fetch“ wird ein (erstes bzw. weiteres) ISS-Wort aus dem Programmspeicher 2 geholt und im zugehörigen Pufferspeicher (Puffer-Befehlsregister) 5, 5' abgelegt.

Im Zustand 13 „Fetch-Decode“ wird der erste Befehl im ISS-Wort decodiert und auf die Slice-50 Instruktionsfelder SIF der Rechenelemente verteilt. Zugleich wird das nächste ISS-Wort aus dem Programmspeicher 2 geholt, um den Pufferspeicher 5 bzw. 5' zu füllen.

Im Zustand 14 „Fetch-Decode-Execute“ werden der zweite und alle folgenden Befehle decodiert und von den Rechenelementen CS ausgeführt. Weiters muss je nach Länge der Befehle für 55 eine Wiederbefüllung des Pufferspeichers 5, 5' gesorgt werden. Im Fall eines Sprungbefehls im

Claims (11)

1. 9 AT 501 213 B1 Programm, wie bei 15 in Fig. 5 angedeutet, wird in den Zustand 12 „Fetch“ gewechselt, um das Programm an einer neuen Adresse fortführen zu können. Solange kein Sprungbefehl vorliegt, wird hingegen das Programm gemäß einer Schleife 16 abgearbeitet. 5 Patentansprüche: 1. Verfahren zum Steuern der zyklischen Zuführung von Instruktionswörtem (S) zu parallel arbeitenden Rechenelementen (CS0-CS7) einer Datenverarbeitungseinrichtung (1), wobei io die Instruktionswörter aus einem Programmspeicher (2) ausgelesen werden, dadurch ge kennzeichnet, dass jeweils nur voneinander verschiedene Instruktionswörter (SO, S1, ...), bei Gleichheit aller Instruktionswörter jeweils nur das eine Instruktionswort (S), aus dem Programmspeicher (2) ausgelesen und einem Puffer-Befehlsregister (5, 5') zugeführt werden bzw. wird und weiters eine Steuerinformation (G.2) vorgesehen wird, gemäß welcher 15 die voneinander verschiedenen Instruktionswörter oder das eine Instruktionswort in verge bener Weise auf die parallelen Rechenelemente verteilt werden bzw. wird.
2. 2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Steuerinformation (G.2) jeweils als Teil eines globalen Instruktionsworts (G) zusammen mit den Instruktionswörtern 20 (S) aus dem Programmspeicher (2) ausgelesen und dem Puffer-Befehlsregister (5, 5') zu geführt wird.
3. 3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die Steuerinformation (G.2) ein Instruktionswörter-Verteilfeld (G.2.2) mit, den einzelnen parallelen Rechenele- 25 menten zugeteilten Feldbereichen enthält, in denen für die einzelnen Rechenelemente (CS) Zuordnungsbits enthalten sind, die die jeweils vorliegenden, verschiedenen Instruktionswörter (SO, S1 ...) angeben.
4. 4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass die Zuordnungsbits im Verteil- 30 feld (G.2.2) einen virtuellen Rechenelement-Zeiger (9) bilden.
5. 5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass in der jeweiligen Steuerinformation (G.2) ein Kontrollfeld (G.2.3) vorgesehen wird, das die jeweilige Anzahl der verschiedenen Instruktionswörter (SO, S1,...) angibt. 35
6. 6. Verfahren nach einem der Ansprüche 2 bis 5, dadurch gekennzeichnet, dass von einer zentralen Steuereinheit (3) ein Zeiger (8), der auf das jeweils gültige globale Instruktionswort (G) im Befehlsregister (5, 5') zeigt, mitgeführt wird.
7. 7. Verfahren nach einem der Ansprüche 2 bis 6, dadurch gekennzeichnet, dass in der Steuer information (G.2) ein Umschaltfeld (G.2.1) vorgesehen wird, um einen Sprung auf das nächste Instruktionswort im Programmspeicher (2) zu veranlassen, wenn das nächste globale Instruktionswort an einer neuen Adresse steht.
8. 8. Datenverarbeitungseinrichtung (1) mit mehreren parallel arbeitenden Rechenelementen (CS0-CS7), die zyklisch Instruktionswörter (S) aus einem Programmspeicher (2) unter Steuerung durch eine Steuereinheit (3) zugeführt erhalten, dadurch gekennzeichnet, dass zwischen dem Programmspeicher (2) und den Rechenelementen (CS0-CS7) zumindest ein Puffer-Befehlsregister (5, 5’), in dem jeweils nur Instruktionswörter (S), so weit sie von- 50 einander verschieden sind, gespeichert werden, und ein Instruktionswort-Verteiler (6) an geordnet sind, der die im Puffer-Befehlsregister (5, 5') zwischengespeicherten, voneinander verschiedenen Instruktionswörter (S) mit einer durch Steuerinformation (G.2) vorgegebenen Verteilung den Rechenelementen (CS0-CS7) zuführt.
9. 9. Datenverarbeitungseinrichtung nach Anspruch 8, dadurch gekennzeichnet, dass das 10 AT 501 213 B1 Puffer-Befehlsregister (5, 5') einen Speicherbereich für die jeweilige Steuerinformation enthält, die jeweils zusammen mit den Instruktionswörtern aus dem Programmspeicher (2) ausgelesen wird.
10. 10. Datenverarbeitungseinrichtung nach Anspruch 8 oder 9, dadurch gekennzeichnet, dass die Steuerinformation als Teil eines globalen Instruktionsworts (G) aus dem Programmspeicher (2) ausgelesen und in das Puffer-Befehlsregister (5, 5’) überführt wird.
11. 11. Datenverarbeitungseinrichtung nach einem der Ansprüche 8 bis 10, dadurch gekennzeich-io net, dass zwei Puffer-Befehlsregister (5, 5') vorgesehen sind, von denen das eine zur Spei cherung der jeweils aktuellen Instruktionswörter (S) und das andere zur Speicherung der jeweils nächstgültigen Instruktionswörter (S) eingerichtet ist. 15 Hiezu 5 Blatt Zeichnungen 20 25 30 35 40 45 50 55