DE19532527C2

DE19532527C2 - Process for dynamic associative control of parallel processors

Info

Publication number: DE19532527C2
Application number: DE1995132527
Authority: DE
Inventors: Winfried Gehrke; Klaus Gaedke
Original assignee: Individual
Current assignee: Individual
Priority date: 1995-09-02
Filing date: 1995-09-02
Publication date: 2000-06-15
Anticipated expiration: 2015-09-03
Also published as: DE19532527A1

Description

Die Erfindung betrifft ein Verfahren zur dynamischen assoziativen Steuerung von Parallelprozessoren nach dem Oberbegriff des Anspruchs 1.The invention relates to a method for dynamic associative control of parallel processors after the Preamble of claim 1.

Durch die Fortschritte der Halbleitertechnologie ist es heute möglich, hochkomplexe Schaltungsarchitekturen mono lithisch zu integrieren und so gleichzeitig die Forderung einer kostengünstigen Implementierung mit der Forderung nach einer möglichst flexiblen programmierbaren Architek tur mit hoher Rechenleistung zu erfüllen. So ist mit ei ner derzeit verfügbaren 0,5 µm-CMOS-Technologie beispiels weise möglich, einen Parallelprozessor mit 16 Datenpfaden und einer Peak-Performance von 3,2 Giga Operationen pro Sekunde (GOPS) bei einer Taktfrequenz von 100 MHz zu rea lisieren. Die zukünftig verfügbare 0,35 µm-CMOS-Technolo gie wird es ermöglichen, ca. 30-40 Datenpfade mit einer Gesamt-Peak-Performance in der Größenordnung von etwa 10 GOPS implementieren.Due to the advances in semiconductor technology, it is possible today, highly complex circuit architectures mono to integrate lithically and at the same time the requirement a cost-effective implementation with the requirement for the most flexible programmable architec tur with high computing power. So with egg ner currently available 0.5 µm CMOS technology for example wise possible, a parallel processor with 16 data paths and a peak performance of 3.2 giga operations per Second (GOPS) at a clock frequency of 100 MHz to rea lize. The 0.35 µm CMOS technology available in the future technology will enable approximately 30-40 data paths with one Total peak performance in the order of about 10 Implement GOPS.

Bei einer Vielzahl von Datenpfaden ist die Steuerung der parallelen arithmetischen Einheiten auf dem Chip von großer Bedeutung. Grundsätzlich erfordert parallele Ver arbeitung die Unabhängigkeit der parallel zu verarbeiten den Operationen. Diese Unabhängigkeit kann entweder auf Datenebene oder auf Instruktionsebene vorliegen. Entspre chend kann für eine Implementierung die Parallelisierung über Daten oder über Instruktionen erfolgen. Als bekannte Techniken sind hier SIMD-(Single Instruction Stream Mul tiple Data Stream), MISD-(Multiple Instruction Stream Multiple Data Stream) Architekturen und eine Kombination aus beiden, MSIMD, zu nennen.With a large number of data paths, the control of the parallel arithmetic units on the chip is of great importance. Basically, parallel processing requires the independence of the operations to be processed in parallel. This independence can exist either at the data level or at the instruction level. Correspondingly, the parallelization for an implementation can take place via data or via instructions. As known techniques are here SIMD (S ingle I nstruction S tream M ul tiple D ata Stream), MISD- (Multiple Stream I nstruction M ultiple D ata Stream) architectures and a combination of both, MSIMD, to call.

SIMD-Architekturen basieren auf einer Parallelisierung auf Datenebene. Mehrere parallele Datenpfade werden durch einen zentralen Controller gesteuert. Da nur ein zentra ler Controller vorhanden ist, kann zu einem Zeitpunkt nur eine Instruktion an die Datenpfade ausgegeben werden und somit führen die Datenpfade identische Instruktionen aus. Die Verarbeitung von Verfahren mit datenabhängigem Kon trollfluß erfordert die sequentielle Ausführung der Zwei ge einer Verzweigung in Verbindung mit einem ergebnisab hängigen Abschalten einzelner Datenpfade. Aufgrund des selektiven Abschaltens einzelner Datenpfade fällt die effektiv verfügbare Rechenleistung mit der Verzweigungs tiefe eines Programmsegmentes ab. Ein weiterer Nachteil von SIMD-Architekturen liegt darin, daß eine zeiltgleiche Ausführung mehrerer Algorithmen nicht unterstützt wird.SIMD architectures are based on parallelization at the data level. Multiple parallel data paths are through controlled a central controller. Since only a centra controller is only available at a time an instruction is issued to the data paths and thus the data paths execute identical instructions. The processing of procedures with data-dependent accounts troll flow requires sequential execution of the two branching in connection with a result pending shutdown of individual data paths. Because of the selective switching off of individual data paths falls effectively available computing power with the branching depth of a program segment. Another disadvantage of SIMD architectures lies in the fact that Execution of multiple algorithms is not supported.

SIMD-Architekturen bieten den Vorteil eines geringen Implementierungsaufwands und führen für Algorithmen mit datenunabhängigem Kontrollfluß, z. B. FIR-Filter, Trans formationen wie die DCT oder DFT u. a., zu einer effizien ten Implementierung. Viele datenparallele Algorithmen erfordern jedoch einen datenabhängigen Kontrollfluß. Für diese Algorithmen sinkt die Effizienz des SIMD-Ansatzes erheblich.SIMD architectures offer the advantage of being small Implementation effort and carry for algorithms data-independent control flow, e.g. B. FIR filter, trans formations like the DCT or DFT u. a., to be efficient implementation. Many data-parallel algorithms however, require a data-dependent control flow. For these algorithms decrease the efficiency of the SIMD approach considerably.

SIMD-Architekturen wurden in der Vergangenheit für sehr unterschiedliche Aufgaben eingesetzt. Es wurden bisher sowohl monolithische wie auch nicht-monolithische Imple mentierungen realisiert.SIMD architectures have been very popular in the past used different tasks. So far both monolithic and non-monolithic imple mentations realized.

MIMD-Architekturen stellen für jeden Datenpfad eine einzelne Kontrolleinheit zur Verfügung. Auf diese Weise kann sichergestellt werden, daß jeder Datenpfad die In struktion erhält, die er aufgrund seines gegenwärtigen Status benötigt. Die SIMD-typischen Rechenzeitverluste entfallen somit für MIMD-Architekturen. Der Nachteil von MIMD-Architekturen liegt in dem hohen schaltungstechni schen Aufwand für die Steuerungslogik. Ein weiterer er heblicher Kostenfaktor ist der Aufwand für die Speiche rung der Instruktionen, da entweder für jeden Datenpfad ein eigener Instruktionsspeicher implementiert werden muß, oder ein einzelner Speicher mit einer der Anzahl der Datenpfade entsprechenden Portanzahl benötigt wird.MIMD architectures set one for each data path single control unit available. In this way can be ensured that each data path the In structure that he receives based on his current Status needed. The typical SIMD computing time losses are therefore no longer required for MIMD architectures. The disadvantage of MIMD architectures lie in the high level of circuit technology effort for the control logic. Another he The cost for the spoke is a significant cost factor instructions as either for each data path a separate instruction memory can be implemented must, or a single memory with one of the number of Corresponding number of data paths is required.

MIMD-Architekturen ermöglichen erheblich höhere Leistung, da prinzipiell sowohl auf Daten- wie auf Instruktions ebene parallelisiert werden kann. Der Aufwand für eine MIMD-Architektur ist sehr hoch, da für jeden Datenpfad eine Kontrolleinheit zur Verfügung gestellt wird. Darüber hinaus wird der Instruktionsspeicher einer MIMD-Architek tur bei der Ausführung datenparalleler Algorithmen nicht effizient genutzt, da im Extremfall alle Instruktions speicher denselben Programmcode beinhalten und alle Da tenpfade dieselben Instruktionen ausführen. Somit wären alle Kontrolleinheiten bis auf eine redundant.MIMD architectures enable significantly higher performance, because in principle both on data and on instructions plane can be parallelized. The effort for one MIMD architecture is very high because of every data path a control unit is made available. About that In addition, the instruction memory of a MIMD Architek structure when executing data-parallel algorithms used efficiently because in extreme cases all instructions memory contain the same program code and all Da Follow the same instructions. So would be all control units except one redundant.

In der Vergangenheit wurde eine Vielzahl von MIMD-Archi tekturen realisiert. Diese Architekturen basieren auf parallelen, meist skalaren Prozessoren, die auf Systeme bene zu einem MIMD-System zusammengefügt werden.In the past, a variety of MIMD archi tectures realized. These architectures are based on parallel, mostly scalar processors based on systems can be combined into a MIMD system.

Eine Kombination des MIMD- und des SIMD-Konzeptes stellen Multiple-SIMD-Architekturen, MSIMD, dar. Diese Ansätze basieren auf parallelen SIMD-Architekturen, sogenannten SIMD-Clustern, die unabhängig voneinander arbeiten kön nen. Auf diese Weise kann der schaltungstechnische Auf wand für die Realisierung verringert werden, da für jedes Cluster nur eine Kontrolleinheit benötigt wird. Dadurch kommt man dem Ziel näher, eine möglichst hohe Rechenlei stung mit einer möglichst geringen Chipfläche zu erzie len. Auch die vorliegende Erfindung beinhaltet Elemente der MSIMD-Architekturen.A combination of the MIMD and SIMD concept provide M ultiple SIMD architectures MSIMD,. These approaches are based on parallel SIMD architectures, the so-called SIMD clusters NEN operate independently Kgs. In this way, the circuitry complexity for the implementation can be reduced, since only one control unit is required for each cluster. This brings us closer to the goal of achieving the highest possible computing performance with the smallest possible chip area. The present invention also includes elements of the MSIMD architectures.

Aus der Veröffentlichung "A Parallel VLSI Architecture for Object-Based Analys-Synthesis Coding", IEEE Workshop Visual Signal Processing and Communication, September 19-20, 1994, S. 136-141 ist bereits ein Verfahren zur dyna mischen assoziativen Steuerung von Parallelprozessoren mit den Merkmalen des Oberbegriffs des Anspruchs 1 be kannt. Das auszuführende Programm ist in als Basic-Blöcke bezeichnete Programmsegmente unterteilt, die keine Sta tusmerkmale oder Abhängigkeiten zu anderen Programmseg menten umfassen. Die Abhängigkeitsinformationen werden beim Laden eines Programms in einem Basic-Block-Abhängig keitsspeicher zwischengespeichert. Diese Information wird von einem Verteiler bei der Abarbeitung des Programms ausgewertet und die abgearbeiteten Basic-Blöcke werden anschließend markiert.From the publication "A Parallel VLSI Architecture for Object-Based Analysis-Synthesis Coding ", IEEE Workshop Visual Signal Processing and Communication, September 19-20, 1994, pp. 136-141 is already a process for dyna mix associative control of parallel processors with the features of the preamble of claim 1 be knows. The program to be executed is in basic blocks designated program segments divided that no Sta Features or dependencies on other program segments elements include. The dependency information will be dependent on loading a program in a basic block cached memory. This information will from a distributor during the execution of the program evaluated and the processed basic blocks are then marked.

Außerdem ist aus REQUA, Joseph und McGRAW, James: The Piecewise Data Flow Architecture: Architectural Concepts. in: IEEE Trans. on Computers, Mai 1983, Vol. C-32, No. 5, Seite 425 bis 438 ein Verfahren zur Steuerung von Paral lelprozessoren entnehmbar, wobei das auszuführende Pro gramm in als Basic-Blöcke bezeichnete Programmsegmente unterteilt ist, die sowohl Steuerungsinformationen als auch Rechnerbefehle enthalten.REQUA, Joseph and McGRAW, James: The Piecewise Data Flow Architecture: Architectural Concepts. in: IEEE Trans. on Computers, May 1983, Vol. C-32, No. 5, Pages 425 to 438 a method for controlling Paral Removable processors, whereby the Pro grams in program segments called basic blocks is divided, which is both control information also contain computer commands.

Ferner ist aus der EP 0 234 785 A1 ein Verfahren zur Steuerung von Parallelprozessoren entnehmbar, wobei das auszuführende Programm in mit Basic-Blöcke bezeichnete Segmente unterteilt ist, wobei auch Statusmeldungen der einzelnen Prozessoren Verwendung finden.Furthermore, EP 0 234 785 A1 describes a method for Control of parallel processors can be removed, whereby the program to be executed in labeled with basic blocks Segments is subdivided, with status messages of the individual processors.

Weiter ist aus der US 5 361 370 ebenfalls ein Steuerungs verfahren für eine Architektur mit SIMD und Parallelpro zessoren entnehmbar, wobei ein "Transfer Block Control ler" zur Steuerung der parallelen Datenpfade eingesetzt wird, der beim Auftreten von Datenabhängigkeiten Brauch barkeitskodes und zur Blockübertragung Abhängigkeitsli sten benutzt.Furthermore, a control is also from US 5 361 370 procedure for an architecture with SIMD and Parallelpro cessors removable, with a "Transfer Block Control ler "used to control the parallel data paths that is used when data dependencies occur availability codes and block transfer dependency links most used.

Schließlich ist aus der WO 88/07242 A3 ein SIMD-Prozes sor-Aufbau bekannt, wobei zur Steuerung datenabhängiger Algoritmen von den einzelnen Prozessoren kommende Status meldungen verwendet werden.Finally, WO 88/07242 A3 is a SIMD process sor structure known, with data-dependent control Algorithms of status coming from each processor messages can be used.

Der Erfindung liegt die Aufgabe zugrunde, das eingangs genannte Verfahren dahingehend zu verbessern, daß eine weitere Steigerung der Rechenleistung erzielt wird.The invention has for its object that to improve the method in such a way that a further increase in computing power is achieved.

Diese Aufgabe wird bei einem Verfahren nach dem Oberbe griff des Anspruchs 1 durch die im Kennzeichen dieses An spruchs angegebenen Merkmale gelöst.This task is carried out in a Oberbe procedure attacked of claim 1 by the in the mark of this to characteristics specified resolved.

Bei dem erfindungsgemäßen Verfahren müssen die Abhängig keitsinformationen von Programmsegmenten nicht mehr beim Laden des Programms aus gesonderten Abhängigkeitssegmen ten in einen Zwischenspeicher geschrieben werden, sondern können direkt aus den Programmsegmenten selbst entnommen werden, da sie Bestandteile dieser sind. Neben einer Re duzierung von Schreib/Lese-Zyklen wird dadurch auch Spei cherplatz auf dem Chip eingespart. Außerdem wird die An wendung leistungsfähigerer Strategien bei der Behandlung von Programmschleifen ermöglicht. Ein ganz besonderer Re chenleistungsgewinn ergibt sich bei Verzweigungen inner halb eines abzuarbeitenden Programms, da nicht benötigte Programmteile gezielt übersprungen werden können.In the method according to the invention, the dependent information from program segments no longer with Load the program from separate dependency segments be written to a buffer, but can be taken directly from the program segments themselves because they are part of this. In addition to a re Reduction of read / write cycles is also a result of this Space saved on the chip. In addition, the An use more effective treatment strategies of program loops enabled. A very special re Gain performance gain arises with branching internally half of a program to be processed since it was not required Program parts can be skipped selectively.

Dabei ist vorgesehen, daß Abhängigkeiten zwischen den Programmsegmenten, die zu Programmschleifen führen, zu sätzlich in den allgemeinen Abhängigkeitsinformationen in den entsprechenden Programmsegmenten angeordnet und durch den Verteiler ausgewertet werden. Hierdurch ist die In formation über auszuführende Programmschleifen frühzeitig verfügbar. Dadurch kann ebenfalls das Laden von nicht be nötigten Programmsegmenten verhindert werden.It is provided that dependencies between the Program segments that lead to program loops to additionally in the general dependency information in arranged and through the corresponding program segments the distributor can be evaluated. As a result, the In formation about program loops to be executed early available. This also prevents loading from necessary program segments can be prevented.

Gemäß einer Weiterbildung werden bei Auftreten von Pro grammschleifen alle nachfolgenden Programmsegmente erst nach einer die vollständige Abarbeitung der Programmseg mente innerhalb der Schleife durch die beteiligten Daten pfade kennzeichnenden Statusmeldung zur Ausführung be reitgestellt. Durch diese Maßnahme wird das Laden und die Ausgabe der Instruktionen von Programmsegmenten verhin dert, die nach Ausführung der Schleife nicht benötigt werden. Auf diese Weise ergibt sich ein Rechenzeitgewinn.According to a further training, when Pro grind all subsequent program segments first after a complete processing of the program segment elements within the loop through the data involved Path-indicating status message for execution provided. Through this measure, the loading and the Prevent the output of instructions from program segments not needed after the loop has been executed become. In this way, computing time is saved.

Vorzugsweise wird eine Statusmeldung der Datenpfade aus gewertet, die besagt, daß mindestens einer der bereitge stellten Programmsegmente von keinem Datenpfad ausgeführt wird. Bei Auftreten dieser Statusmeldung wird eine zu sätzliche alternative Abhängigkeitsinformation ausgewer tet. Die zusätzlichen alternativen Abhängigkeitsinforma tionen der Programmsegmente, die bei nicht ausgeführten Programmsegmenten ausgewertet werden, können zusätzlich zu den allgemeinen Abhängigkeitsinformationen in den entsprechenden Programmsegmenten angeordnet sein. Durch Überspringen derartiger Programmsegmente ergibt sich ein weiterer Rechenleistungsgewinn.A status message for the data paths is preferably produced rated, which says that at least one of the prepared provided program segments from no data path becomes. When this status message occurs, one becomes additional alternative dependency information selected tet. The additional alternative dependency information tions of the program segments that are not executed Program segments can be evaluated additionally to the general dependency information in the corresponding program segments can be arranged. By Skipping such program segments results further computing power gain.

Weiter ist vorgesehen, daß Programmsegmente erst in Ab hängigkeit von der Verfügbarkeit einer entsprechenden Anzahl von Datenpfaden und/oder der zu verarbeitenden Daten zur Ausführung bereitgestellt werden.It is also envisaged that program segments only in Ab depending on the availability of a corresponding Number of data paths and / or the ones to be processed Data to be provided for execution.

Durch diese Maßnahme lassen Verzögerungen durch unnötiges Zwischenspeichern nicht benötigter Programmsegmente ver ringern wodurch die sogenannte Cache-Miss-Rate gesenkt werden kann. Ferner läßt sich ein implementierungsunab hängiger Code verwenden. Dies hat den Vorteil, daß der Code auf Prozessoren mit unterschiedlicher Parallelität laufen kann. Damit lassen sich code-kompatible Prozessor familien realisieren. Ferner kann bei der Herstellung von Prozessoren auf Chips eine größere Defekttoleranz zuge lassen werden, wodurch die Fertigungskosten verringert werden können.This measure allows delays due to unnecessary Caching unnecessary program segments wrestle which lowers the so-called cache miss rate can be. Furthermore, an implementation-independent use pending code. This has the advantage that the Code on processors with different parallelism can run. This allows code-compatible processors realizing families. Furthermore, in the manufacture of Processors on chips have a greater defect tolerance can be left, thereby reducing the manufacturing costs can be.

Nachfolgend wird die Erfindung anhand der Zeichnung erläutert. In der Zeichnung zeigen:The invention is described below with reference to the drawing explained. The drawing shows:

Fig. 1 ein Blockschaltbild eines Parallelrech ners, Fig. 1 is a block diagram of a parallel computational agent,

Fig. 2 ein Beispiel einer Programmsegment-Tabelle und Fig. 2 shows an example of a program segment table

Fig. 3 ein Flußdiagramm als Beispiel eines zykli schen Abhängigkeitsgraphen. Fig. 3 is a flowchart as an example of a cyclic dependency graph.

Der Parallelrechner gemäß Fig. 1 umfaßt n-parallele Da tenpfade 10, die lesend und schreibend auf einen Daten speicher 12 zugreifen können. Der Begriff Datenpfad 10 umfaßt je eine arithmetische Verarbeitungseinheit mit den nötigen Peripheriebausteinen zur Adressierung und Zwi schenspeicherung. Ein solcher Datenpfad 10 könnte z. B. gemäß Fig. 3 der eingangs erwähnten Veröffentlichung "A Parallel VLSI Architecture for Object-Based Analys-Syn thesis Coding" aufgebaut sein. Die Datenpfade 10 sind mittels einer Steuereinheit steuerbar, die m-parallel arbeitende Ansteuereinheiten 14 und einen Verteiler 18 umfaßt. Dabei sind den n-parallelen Datenpfaden 10 m- parallel arbeitende Ansteuereinheiten 14 zugeordnet. Der Verteiler 18 ist mit den Ansteuereinheiten 14 und den Datenpfaden 10 verbunden. Ferner ist ein mit den Ansteu ereinheiten 14 verbundener Instruktionsspeicher 16 vor gesehen.The parallel computer of FIG. 1 comprises n-parallel Da tenpfade 10, 12 can access the read and write memory to a data. The term data path 10 each includes an arithmetic processing unit with the necessary peripheral components for addressing and intermediate storage. Such a data path 10 could e.g. B. of FIG. 3 of the aforementioned publication "A Parallel VLSI Architecture for Object-Based Analysis-Syn thesis Coding". The data paths 10 can be controlled by means of a control unit which comprises control units 14 operating in parallel and a distributor 18 . In this case, control units 14 operating in parallel are assigned to the n-parallel data paths 10 m. The distributor 18 is connected to the control units 14 and the data paths 10 . Furthermore, an instruction memory 16 connected to the control units 14 is seen before.

Der Ansatz der dynamischen assoziativen Steuerung basiert auf der Zerlegung des abzuarbeitenden Programms in Pro grammsegmente und diese Programmsegmente verbindende Ab hängigkeitsinformationen. Bei dem erfindungsgemäßen Ver fahren sind die Programmsegmente verbindenden Abhängig keitsinformationen jeweils als Zusatz innerhalb von Pro grammsegmenten angeordnet und können aus dem Programmcode in einen Speicher des Verteilers 18 als Programmsegment- Tabelle geschrieben werden. Fig. 2 zeigt ein Beispiel einer Programmsegment-Tabelle. Diese Programmsegment- Tabelle steht dem Verteiler 18 für seine Aufgabe zur Verfügung.The dynamic associative control approach is based on breaking down the program to be processed into program segments and dependency information connecting these program segments. In the method according to the invention, the dependency information connecting program segments are each arranged as an addition within program segments and can be written from the program code into a memory of the distributor 18 as a program segment table. Fig. 2 shows an example of a program segment table. This program segment table is available to distributor 18 for its task.

Die Ansteuereinheiten 14 dienen zur Steuerung des In struktionsflusses innerhalb eines Programmsegmentes. Die Anzahl der Ansteuereinheiten 14 legt die Anzahl der maxi mal verfügbaren Instruktionsströme fest. The control units 14 serve to control the flow of construction within a program segment. The number of control units 14 determines the number of instruction streams that are available to a maximum.

Der Verteiler 18 hat die Aufgabe, ausführbare Programm segmente zu identifizieren und das Laden des zugehörigen Programmcodes aus einem Programmspeicher in den lokalen Instruktionsspeicher 16 mittels der Ansteuereinheiten 14 zu initiieren. Ferner startet der Verteiler 18 nach der Programmsegment-Tabelle unter logischer Verknüpfung mit Statusmeldungen der Datenpfade 10 und Ansteuereinheiten 14 die Ansteuereinheiten 14 zur Ausführung der bereitge stellten Instruktionen zur Laufzeit und steuert die Aus wahlmöglichkeiten der in den Instruktionsströmen über einen Instruktionsbus bereitgestellten Instruktionen.The distributor 18 has the task of identifying executable program segments and initiating the loading of the associated program code from a program memory into the local instruction memory 16 by means of the control units 14 . Further, the distributor 18 starts after the program segment-table in logical association with status messages of the data paths 10 and drive units 14, the drive units 14 for executing the bereitge presented instructions at runtime, and controls the off options of the instructions provided in the instruction streams on a instruction bus.

Das Ende eines Programmsegments ist durch ein Bit des In struktionswortes codiert und wird parallel an die jewei lige Ansteuereinheit 14 und an den Verteiler 18 überge ben. Erkennt der Verteiler 18 das Ende eines Programmseg ments, werden mit Hilfe der Programmsegment-Tabelle alle Programmsegmente auf Ausführbarkeit überprüft. Dabei wird der Nachfolger des abgearbeiteten Programmsegments be stimmt und überprüft, ob dieses Programmsegment weitere Vorgänger besitzt. Ist dies der Fall, überprüft der Ver teiler 18, ob alle Vorgänger abgearbeitet sind. Erst nach der Abarbeitung aller Vorgänger kann die Verarbeitung ei nes neuen Programmsegments gestartet werden. Wird ein Programmsegment gefunden, das aufgrund der Abhängigkeiten zu anderen Programmsegmenten ausgeführt werden kann, wird die Abarbeitung dieses Programmsegmentes gestartet, so fern eine freie Ansteuereinheit 14 zur Verfügung steht und der Programmcode für den zu startenden Block in den Programmspeicher geladen worden.The end of a program segment is coded by a bit of the construction word and is passed in parallel to the respective control unit 14 and to the distributor 18 . If the distributor 18 recognizes the end of a program segment, all program segments are checked for executability with the aid of the program segment table. The successor of the processed program segment is determined and it is checked whether this program segment has other predecessors. If this is the case, the distributor 18 checks whether all predecessors have been processed. The processing of a new program segment can only be started after all predecessors have been processed. If a program segment is found that can be executed due to the dependencies on other program segments, the processing of this program segment is started as long as a free control unit 14 is available and the program code for the block to be started has been loaded into the program memory.

Hierzu wählt der Verteiler 18 eine freie Ansteuereinheit 14 aus und übergibt an sie die Startadresse des zu star tenden Programmsegments, sowie die Kennung dieses Pro grammsegments. Die Kennung wird an die Datenpfade 10 übertragen.For this purpose, the distributor 18 selects a free control unit 14 and transfers to it the start address of the program segment to be started, as well as the identifier of this program segment. The identifier is transmitted to the data paths 10 .

Die Entscheidung über die auszuführenden Instruktionen geschieht in den Datenpfaden 10 selbst in Abhängigkeit ihres aktuellen Zustandes, d. h. assoziativ. Da die Da tenpfade 10 autonom über die Ausführung von Instruktionen entscheiden, müssen die Datenpfade 10 die Möglichkeit be sitzen, eine Zuordnung eines physikalischen Instruktions stromes zu einem logischen Instruktionsstrom durchzufüh ren. Diese Zuordnung erfolgt über Kennungen, die den Da tenpfaden 10 mit dem Start eines Programmsegments über einen gesonderten Kennungsbus mitgeteilt werden.The decision about the instructions to be executed takes place in the data paths 10 themselves depending on their current state, ie associatively. Since the data paths 10 autonomously decide on the execution of instructions, the data paths 10 must be able to carry out an assignment of a physical instruction stream to a logical instruction stream. This assignment takes place via identifiers that the data paths 10 with the start of a Program segments are communicated via a separate identification bus.

Die Instruktionen steuern daraufhin Operationen der Da tenpfade 10. Wird von einem Datenpfad 10 keine passende Instruktion gefunden, führt er einen Leerzyklus aus.The instructions then control operations of data paths 10 . If no suitable instruction is found by a data path 10 , it executes an empty cycle.

Nach Programmverzweigungen kann prinzipiell der Fall auf treten, daß ein Instruktionsstrom von keinem der Daten pfade 10 benötigt wird. Für die Steigerung der Leistung kann dann die Bearbeitung dieses Instruktionsstromes durch die Ansteuereinheit 14 abgebrochen werden und gege benenfalls ein anderes ausführbares Programmsegment ge startet werden. Um dies zu ermöglichen, erfolgt von den Datenpfaden 10 eine Rückmeldung an den Verteiler 18, über die ausgeführte Instruktionen adressiert werden. Wird vom Verteiler 18 anhand dieser Information erkannt, daß eine Ansteuereinheit 14 nicht aktiv ist, kann wie bei einem Programmsegment-Ende ein neues Programmsegment gestartet werden.In principle, after program branches, the case may arise that an instruction stream is not required by any of the data paths 10 . To increase the power, the processing of this instruction stream can then be interrupted by the control unit 14 and, if appropriate, another executable program segment can be started. In order to make this possible, the data paths 10 provide feedback to the distributor 18 , via which instructions that are executed are addressed. If the distributor 18 uses this information to recognize that a control unit 14 is not active, a new program segment can be started like at the end of a program segment.

Dieser Ansatz der dynamischen assoziativen Steuerung hat folgende Eigenschaften und Vorteile gegenüber einer sta tischen assoziativen Steuerung.This approach has dynamic associative control following properties and advantages over a sta associative control.

Die Zuteilung von Ansteuereinheiten 14 wird zur Laufzeit durchgeführt. Auf diese Weise wird gewährleistet, daß die maximal mögliche Anzahl an Instruktionsströmen parallel verarbeitet wird. The allocation of control units 14 is carried out at runtime. This ensures that the maximum possible number of instruction streams is processed in parallel.

Es findet eine implizite Synchronisation zur Laufzeit statt. Die Abarbeitung eines neuen Programmsegments wird erst dann gestartet, wenn alle Vorgänger verarbeitet wor den sind. Da die Abhängigkeitsliste aus dem Programm- Quelltext extrahiert werden kann, ist es für den Program mierer nicht notwendig, Synchronisationspunkte explizit im Programm anzugeben.There is an implicit synchronization at runtime instead of. The processing of a new program segment will only started when all predecessors were processed they are. Since the dependency list from the program Source code can be extracted, it is for the program Not necessary, synchronization points explicit to be specified in the program.

Der für die Verarbeitung von Verschachtelungen des Pro grammcodes, zum Beispiel durch Schleifen oder Unterpro grammaufrufe notwendige Stack-Speicher kann entfallen.The one for processing nesting of the Pro gram codes, for example by grinding or subpro The stack memory required for gram calls can be omitted.

Da die Startadressen der nachfolgenden Programmsegmente bekannt sind, kann der zugehörige Programmcode vor dem Start der Verarbeitung in den lokalen Instruktionsspei cher 16 geladen werden. Instruktions-Cache-Misses können so verringert bzw. vermieden werden.Since the start addresses of the subsequent program segments are known, the associated program code can be loaded into the local instruction memory 16 before the start of processing. Instruction cache misses can thus be reduced or avoided.

Nachfolgend wird die Arbeitsweise der Ansteuereinheiten 14 und des Verteilers 18 anhand von Beispielen häufig auftretender Programmkonstrukte erläutert.The operation of the control units 14 and the distributor 18 is explained below using examples of frequently occurring program constructs.

Control units Execution of program segments

Die Abarbeitung von Programmsegmenten erfordert definiti onsgemäß das sequentielle Auslesen aufeinanderfolgender Instruktionen aus dem Instruktionsspeicher 16. Die An steuerung des Instruktionsspeichers 16 kann somit durch einen Zähler erfolgen. Der Zählerstand wird mit der Aus führung einer Instruktion inkrementiert.The processing of program segments by definition requires the sequential readout of successive instructions from the instruction memory 16 . At the control of the instruction memory 16 can thus be done by a counter. The counter reading is incremented when an instruction is executed.

Das Ende eines Programmsegments kann durch eine entspre chende Codierung im Befehlswort gekennzeichnet werden. Mit dem Ende eines Programmsegments beendet die An steuereinheit 14 die Adressierung des Instruktionsspei chers 16. Anschließend kann die Ansteuereinheit 14 mit einer neuen Programmsegment-Startadresse geladen werden, ab der die Befehlsausführung fortgesetzt wird.The end of a program segment can be identified by an appropriate coding in the command word. At the end of a program segment, the control unit 14 ends the addressing of the instruction memory 16 . The control unit 14 can then be loaded with a new program segment start address, from which the command execution is continued.

Data-independent jumps

Für die Implementierung von datenunabhängigen Sprüngen muß die Programmspeicheradresse, an der die Abarbeitung fortgesetzt werden soll, durch eine Instruktion an die Ansteuereinheit 14 übergeben werden. Die Ansteuereinheit 14 setzt daraufhin den Programmzähler auf den in dieser Instruktion angegebenen Wert und setzt die Programmbear beitung wie im vorigen Abschnitt beschrieben fort. For the implementation of data-independent jumps, the program memory address at which processing is to be continued must be transferred to the control unit 14 by an instruction. The control unit 14 then sets the program counter to the value specified in this instruction and continues the program processing as described in the previous section.

Loops with data-independent number of iterations

Für die Implementierung von Schleifen mit datenunabhängi ger Iterationsanzahl können Hardwareschleifenzähler zur Rechenleistungserhöhung verwendet werden. Wird eine be liebige Verschachtelungstiefe zugelassen, müssen die ak tuellen Schleifenparameter, wie Schleifenbeginn und An zahl noch zu verarbeitender Schleifendurchläufe, bei dem Aufruf jeder nächsttieferen Verachachtelungsebene zwi schengespeichert werden. Die Ansteuereinheiten 14 müssen hierzu die Möglichkeit besitzen, auf den lokalen Speicher des Prozessors zuzugreifen.For the implementation of loops with data-independent number of iterations, hardware loop counters can be used to increase computing power. If an arbitrary nesting depth is permitted, the current loop parameters, such as the start of the loop and the number of loops to be processed, must be buffered when each next lower level of nesting is called up. For this purpose, the control units 14 must be able to access the local memory of the processor.

Der Hardwareaufwand kann verringert werden, wenn eine ma ximale Verschachtelungstiefe für hardwareunterstützte Schleifen festgelegt wird. In diesem Fall kann für jede Verschachtelungsebene ein separater Zähler realisiert werden.The hardware expenditure can be reduced if a ma Maximum nesting depth for hardware-supported Grinding is set. In this case, for each Nesting level realized a separate counter become.

Distributor Processing of data-independent jumps

In vorigen Abschnitt wurde die Möglichkeit beschrieben, datenunabhängige Sprünge durch die Ansteuereinheit 14 ausführen zu lassen. Eine Alternative hierzu ist die Kontrolle von datenunabhängigen Sprüngen durch den Ver teiler:In the previous section, the possibility was described of having the control unit 14 perform data-independent jumps. An alternative to this is the control of data-independent jumps by the distributor:

Der Verteiler 18 erkennt anhand des Programmsegment-Ende- Bits in der letzten Instruktion des aktuellen Programm segments das Ende dieses Programmsegments. Mit Hilfe der Abhängigkeitsliste kann der Verteiler 18 die Startadresse des nachfolgenden Programmsegments bestimmen und an eine nicht belegte Ansteuereinheit 14 weitergeben. Die An steuereinheit 14 liest die Instruktionen des nachfolgen den Programmsegments aus dem Instruktionsspeicher 16 aus und bietet diese den Datenpfaden 10 zur Ausführung an.The distributor 18 recognizes the end of this program segment from the program segment end bit in the last instruction of the current program segment. With the help of the dependency list, the distributor 18 can determine the start address of the subsequent program segment and pass it on to an unoccupied control unit 14 . The control unit 14 reads the instructions of the subsequent program segment from the instruction memory 16 and offers them to the data paths 10 for execution.

Data-dependent splitting of the program flow

Für die Verarbeitung von Algorithmen mit datenabhängigem Kontrollfluß wird eine Aufteilung des Instruktionsflusses unterstützt. Diese Aufspaltung des Kontrollflusses kann als Beginn eines neuen Programmsegments bei gleichzeiti ger Fortsetzung des aktuellen Programmsegments aufgefaßt werden. Somit wird die Verarbeitung des aktuellen Pro grammsegments fortgesetzt und zusätzlich die Verarbeitung eines weiteren Programmsegments gestartet.For processing algorithms with data-dependent Control flow becomes a division of the instruction flow supported. This split of the control flow can as the beginning of a new program segment with simultaneous eng Continued the current program segment become. The processing of the current Pro gram segments continued and processing in addition another program segment started.

Die Verarbeitung von datenabhängigen Verzweigungen des Kontrollflusses durch den Verteiler 18 ist ähnlich der Verarbeitung von datenunabhängigen Sprüngen. Der Vertei ler 18 muß jedoch zusätzlich überprüfen, ob eine weiterer Ansteuereinheit 14 belegt werden kann. Sind bereits alle Ansteuereinheit 14 belegt, muß die Abarbeitung des neu zu startenden Programmsegments verzögert werden, bis eine der belegten Ansteuereinheiten 14 frei wird.The processing of data-dependent branches of the control flow by the distributor 18 is similar to the processing of data-independent jumps. The distributor 18 must, however, additionally check whether a further control unit 14 can be occupied. If all control units 14 are already occupied, the processing of the program segment to be restarted must be delayed until one of the occupied control units 14 becomes free.

Processing of subroutine calls

Für die Verarbeitung von Unterprogrammaufrufen bieten sich zwei Alternativen an, die im folgenden beschrieben werden. Für beide Ansätze gilt, daß ein Unterprogrammauf ruf bzw. der Rücksprung in den aufrufenden Programmteil das Ende eines Programmsegments darstellt.Offer for processing subroutine calls consider two alternatives, which are described below become. A subroutine applies to both approaches call or return to the calling program part represents the end of a program segment.

a) Dynamic processing of subroutine calls

Bei Einsatz dieser Alternative muß der Verteiler 18 beim Auftreten eines Unterprogrammaufrufs die Adresse des nachfolgenden Programmsegments in der aufrufende Ebene in einem Stack-Speicher zwischenspeichern. Anschließend wir der Programmsegment des Unterprogramms gestartet. Wird das Unterprogramm beendet, liest der Verteiler 18 die ge speicherte Adresse des nachfolgenden Programmsegments aus dem Stack-Speicher aus und startet diesen Block.When using this alternative, the distributor 18 must cache the address of the subsequent program segment in the calling level in a stack when a subroutine call occurs. Then the program segment of the subroutine is started. If the subroutine is ended, the distributor 18 reads the stored address of the following program segment from the stack and starts this block.

b) Static processing by dissolving the control flow at translation time

Da die Abhängigkeiten der Unterprogrammaufrufe zur Über setzungszeit bestimmt werden können, können alle Unter programmaufrufe in die Abhängigkeitsliste eingetragen werden. Hierzu muß der Assembler das Quellprogramm analy sieren und verschachtelte Unterprogrammaufrufe auflösen.Since the dependencies of the subroutine calls for the over settlement time can be determined, all sub program calls entered in the dependency list become. To do this, the assembler must analyze the source program and resolve nested subroutine calls.

Der Vorteil der zweiten Alternative ist die Verringerung der Komplexität des Verteilers 18, da die Verwaltung von verschachtelten Unterprogrammen zur Laufzeit entfällt. Mit diesem Ansatz wird die Abhängigkeitsliste bei Verwen dung von verschachtelten Unterprogrammaufrufen vergrö ßert, da für jeden Unterprogrammaufruf ein Eintrag in die Abhängigkeitsliste erfolgt. Da die Abhängigkeitsliste dy namisch nachgeladen wird, wirkt sich eine längere Abhän gigkeitsliste nicht negativ aus.The advantage of the second alternative is that the complexity of the distributor 18 is reduced since the administration of nested subroutines at runtime is eliminated. With this approach, the dependency list is enlarged when nested subroutine calls are used, since an entry is made in the dependency list for each subroutine call. Since the dependency list is dynamically reloaded, a longer dependency list does not have a negative effect.

Program loops

In den vorangegangenen Abschnitten wurde davon ausgegan gen, daß der Abhängigkeitsgraph des Programms azyklisch ist. Die Ausführung von Programmschleifen führt dagegen auf einen zyklischen Abhängigkeitsgraphen. Die Verarbei tung von Programmschleifen führt zu Erweiterungen des bisher vorgestellten Konzeptes. Diese Erweiterungen wer den im folgenden anhand eines Beispiels motiviert.This was assumed in the previous sections that the dependency graph of the program is acyclic is. On the other hand, the execution of program loops leads on a cyclic dependency graph. The processing program loops leads to extensions of the concept presented so far. These extensions who motivated in the following with an example.

Gegeben sei der in Fig. 3 dargestellte Abhängigkeits graph. Nach der sequentiellen Abarbeitung der Programm segmente 1 und 2 verzweigt der Kontrollfluß. In Abhängig keit von den Daten wird Programmsegment 2 erneut ausge führt bzw. Programmsegment 3 gestartet. Nach der Abarbei tung von Programmsegment 3 verzweigt der Kontrollfluß erneut und es wird, in Abhängigkeit des Daten-Pfad-Sta tus, Programmsegment 4 bzw. Programmsegment 5 gestartet. Nach der Abarbeitung von Programmsegment 4 wird die Ver arbeitung mit Programmsegment 2 fortgesetzt.Given the dependency graph shown in FIG. 3. After the sequential processing of program segments 1 and 2 , the control flow branches. Depending on the data, program segment 2 is executed again or program segment 3 is started. After processing of program segment 3 , the control flow branches again and, depending on the data path status, program segment 4 or program segment 5 is started. After program segment 4 has been processed, processing with program segment 2 is continued.

Bei der Abarbeitung des Abhängigkeitsgraphen überprüft der Verteiler 18, ob alle Vorgänger eines Programmseg ments abgearbeitet sind. Auf Basis dieser Strategie füh ren zyklische Abhängigkeitsgraphen zu einem Deadlock, da einzelne Vorgänger erst nach dem aktuell auszuführenden Programmsegment gestartet werden dürfen. Für das oben be schriebene Beispiel ist Programmsegment 4 Vorgänger des Programmsegments 2. Somit dürfte Programmsegment 2 erst dann gestartet werden, wenn Programmsegment 4 bereits be arbeitet ist. Andererseits kann Programmsegment 4 erst nach der Verarbeitung von Programmsegment 3 und dieser erst nach der Verarbeitung von Programmsegment 2 gestar tet werden. Ein zweiter Deadlock ergibt sich aus der Rückführung des Kontrollflusses von Programmsegment 2 auf sich selbst. Da Programmsegment 2 als sein eigener Vor gänger aufgefaßt wird, kann dieser Block nicht gestartet werden.When processing the dependency graph, the distributor 18 checks whether all predecessors of a program segment have been processed. Based on this strategy, cyclical dependency graphs lead to a deadlock, since individual predecessors may only be started after the program segment currently being executed. For the example described above, program segment 4 is the predecessor of program segment 2 . Thus, program segment 2 should only be started when program segment 4 has already been processed. On the other hand, program segment 4 can only be started after the processing of program segment 3 and this only after the processing of program segment 2 . A second deadlock results from the return of the control flow from program segment 2 to itself. Since program segment 2 is seen as its own predecessor, this block cannot be started.

Um diese Deadlocks durch zyklische Graphen zu vermeiden, muß dem Verteiler 18 mit jeder Kante des Abhängigkeits graphen die Information, ob es sich um eine Rückführung handelt, mitgeteilt werden. Diese Information wird durch eine Abhängigkeitsanalyse zur Übersetzungszeit vom As sembler generiert und in die Abhängigkeitsliste eingetra gen. Der Verteiler 18 kann mit Hilfe dieser Information alle rückgeführten Kanten von der Vorgänger-Überprüfung ausschließen. Für den in Fig. 3 dargestellten Abhängig keitsgraphen würden die Kanten von Programmsegment 4 nach Programmsegment 2 und die Rückführung von Programmsegment 2 auf sich selbst bei der Überprüfung der Vorgänger von Programmsegment 2 nicht berücksichtigt. Damit wird nach der Ausführung von Programmsegment 1 Programmsegment 2 gestartet, da lediglich Programmsegment 1 als Vorgänger ausgewertet wird.In order to avoid these deadlocks by means of cyclic graphs, the distributor 18 must be informed with each edge of the dependency graph that the information as to whether it is a return. This information is generated by a dependency analysis at translation time by the sembler and entered in the dependency list. The distributor 18 can use this information to exclude all traced edges from the previous check. For the dependency graph shown in FIG. 3, the edges of program segment 4 to program segment 2 and the return of program segment 2 to themselves would not be taken into account when checking the predecessors of program segment 2 . This starts program segment 2 after the execution of program segment 1 , since only program segment 1 is evaluated as the predecessor.

Um die Synchronisation zyklischer Abhängigkeitsgraphen zu gewährleisten, ist eine weitere Erweiterung der Strategie zur Abarbeitung des Abhängigkeitsgraphen durch den Ver teiler 18 vorzunehmen. Diese Erweiterung kann ebenfalls anhand des oben beschriebenen Beispiels motiviert werden. Die Verzweigung nach Programmsegment 3 führt zu einer Aufspaltung des Kontrollflusses. Werden die Programmseg mente 4 und 5 jeweils zum frühestmöglichen Zeitpunkt ge startet, kann dies zur Aufspaltung der Instruktionsströme für die einzelnen Datenpfade 10 führen, wenn die Anzahl der Schleifendurchläufe für die Datenpfade 10 unter schiedlich sind. Werden mehr logische Instruktionsströme benötigt, als physikalisch unterstützt werden können, kann dies zu erheblichen Rechenleistungseinbußen führen. Daher ist die Erhöhung der Anzahl logischer Instruktions ströme durch datenabhängige Schleifendurchläufe zu ver meiden.In order to ensure the synchronization of cyclic dependency graphs, a further expansion of the strategy for processing the dependency graph must be carried out by distributor 18 . This extension can also be motivated using the example described above. The branching according to program segment 3 leads to a split of the control flow. If the program segments 4 and 5 are started at the earliest possible time, this can lead to the splitting of the instruction streams for the individual data paths 10 if the number of loop runs for the data paths 10 are different. If more logical instruction streams are required than can be physically supported, this can lead to considerable computing power losses. Therefore, the increase in the number of logical instruction flows through data-dependent loop runs must be avoided.

Dies kann gewährleistet werden, wenn der Verteiler 18 vor dem Start eines Programmsegments alle vorliegenden Schleifendurchläufe verarbeitet. Durch diese Maßnahme kann vermieden werden, daß die Anzahl parallel auszufüh render Instruktionsströme kontinuierlich ansteigt. This can be ensured if the distributor 18 processes all of the loop runs present before the start of a program segment. By this measure it can be avoided that the number of instruction streams to be executed in parallel increases continuously.

Processing of cache misses

Können Datenzugriffe auf den lokalen Speicher nicht aus geführt werden, weil die entsprechenden Daten nicht in dem lokalen Speicher des Datenpfades 10 verfügbar sind (Cache-Misses), muß die Verarbeitung unterbrochen und zunächst die angeforderten Daten in den lokalen Speicher geladen werden. Die Zeit für dieses Nachladen ist abhän gig von dem gewählten Speicherkonzept. Im allgemeinen kann davon ausgegangen werden, daß mindestens 20-40 Taktzyklen benötigt werden. Um die Synchronisierung zu gewährleisten, müssen während dieser Zeit alle Datenpfade 10, die auf dem gleichen logischen Instruktionsstrom wie der nachladende Datenpfad 10 arbeiten, angehalten werden.If data accesses to the local memory cannot be carried out because the corresponding data are not available in the local memory of data path 10 (cache misses), the processing must be interrupted and the requested data must first be loaded into the local memory. The time for this reloading depends on the selected storage concept. In general, it can be assumed that at least 20-40 clock cycles are required. To ensure synchronization, all data paths 10 that operate on the same logical instruction stream as the reloading data path 10 must be stopped during this time.

Da dieses Anhalten der Datenpfade 10 lokal in den Daten pfaden 10 durchgeführt werden kann, wird für die Kon trolle der Datenpfade 10 kein Ansteuereinheit 14 benö tigt. Somit kann im Fall eines Cache-Miss eine An steuereinheit 14 freigegeben werden und gegebenenfalls die Ausführung eines neuen Programmsegments gestartet werden. Neben dem Start eines neuen Programmsegments muß der Verteiler 18 den unterbrochenen Programmsegment in der Abhängigkeitsliste mit einer neuen Startadresse als ausführbereit eintragen. Mit Hilfe dieser Strategie kann der Leistungsverlust durch das Auftreten von Cache-Misses verringert werden.Because this stopping of the data paths 10 paths locally in the data can be performed 10, 10 for the con troll of the data paths not drive unit 14 Untitled Benö. In the event of a cache miss, a control unit 14 can thus be released and, if necessary, the execution of a new program segment can be started. In addition to starting a new program segment, the distributor 18 must enter the interrupted program segment in the dependency list with a new start address as ready to be executed. Using this strategy, the loss of performance due to the occurrence of cache misses can be reduced.

Claims

1. Method for the dynamic associative control of parallel processors by means of a control which feeds n-parallel data paths ( 10 ) m-parallel instruction streams, which control operations of the data paths ( 10 ), instructions received in an instruction memory ( 16 ) using m- parallel control units ( 14 ) are addressed, read and the data paths ( 10 ) are provided and the control units ( 14 ) for executing the instructions provided are currently controlled by a distributor ( 18 ), the program contained in the program memory being divided into program segments is broken down and the program includes program information connecting dependency information and the distributor ( 18 ) identifies executable program segments, loads them from the program memory into the instruction memory ( 16 ), based on status messages of the data paths ( 10 ) and control units ( 14 ), the control units ( 14 ) for execution de r provided instructions starts at runtime and controls the selection options of the instructions provided in the instruction streams, while the decision about the instructions to be executed takes place in the data paths ( 10 ), characterized in that the program segments connecting dependency information ( FIG. 2), which comprise at least information about possible program segments to be processed below, each arranged as an addition within program segments and written from the program memory into a memory of the distributor ( 18 ) as a program segment table that the distributor ( 18 ) the control units ( 14 ) according to the program segment table under logical linkage with the status messages of the data paths ( 10 ), as they are generated after executing operations of the data paths ( 10 ), and the status messages of the control units ( 14 ) as they indicate the ready state of the control units ( 14 ) signal, controls, and that dependencies between the program segments that lead to program loops are additionally arranged in the general dependency information in the corresponding program segments and evaluated by the distributor ( 18 ).

2. The method according to claim 1, characterized in that that all follow when program loops occur the program segments only after a complete Ab working the program segments within the loop by the status characterizing the data paths involved message to be provided for execution.

3. The method according to claim 1 or 2, characterized indicates that a status message of the data paths is selected tet, which says that at least one of the prepared provided program segments from no data path and that when this status message occurs, an al alternative dependency information is evaluated.

4. The method according to claim 3, characterized in that the alternative dependency information of the Pro gram segments that are used when the program segment is not executed elements are evaluated, together with the general Dependency information in the corresponding pro gram segments are arranged.

5. The method according to any one of claims 1-4, characterized characterized that program segments only dependent on the availability of a corresponding number of Da paths and / or the data to be processed leadership will be provided.