DE4132764C2

DE4132764C2 - Method and arrangement for assigning processes in a process system to the individual computers in a computer network

Info

Publication number: DE4132764C2
Application number: DE19914132764
Authority: DE
Inventors: Johann Rost
Original assignee: Individual
Current assignee: ROST, JOHANN, 90478 NUERNBERG, DE
Priority date: 1991-10-02
Filing date: 1991-10-02
Publication date: 1995-01-05
Anticipated expiration: 2011-10-03
Also published as: DE4132764A1

Description

Die Erfindung betrifft ein Verfahren nach dem Oberbegriff des Anspruchs 1. Die Erfindung betrifft darüber hinaus ein Verfahren nach dem Oberbegriff des An spruchs 5. Die Erfindung betrifft darüber hinaus Rechnernetzwerke zur Durchfüh rung der Verfahren nach dem Oberbegriff des Anspruchs 9.The invention relates to a method according to the preamble of claim 1. Die The invention further relates to a method according to the preamble of the Proverb 5. The invention also relates to computer networks for implementation tion of the method according to the preamble of claim 9.

Bei der Bearbeitung von Problemen P auf parallelen Rechnerarchitekturen "Rech nernetzwerk") sind unter anderen folgende zwei Aufgaben zu lösen.When processing problems P on parallel computer architectures "Rech network ") the following two tasks have to be solved.

Das zur Lösung des Problems P ins Auge gefaßte Verfahren - beispielsweise eine mathematische Formel - muß durch ein Prozeßsystem realisiert werden.The method envisaged to solve problem P - for example one mathematical formula - must be implemented by a process system.

Unter einem "Prozeß" versteht man eine sequentielle Folge von Rechneranweisun gen. Unter einem "Prozeßsystem" versteht man eine durch Präzedenz-Regeln partiell geordnete Menge von Prozessen. Eine "Präzedenz-Regel" ist eine Aussage über ein Paar von Prozessen (z. B. "A" und "B") von der Form, daß der Prozeß A beendet sein muß, bevor der Prozeß B gestartet werden kann. Innerhalb eines Prozeßsystems kön nen für alle Paare von Prozessen, für einige Paare oder - im Grenzfall - für kein einziges Paar Präzedenz-Regeln festgelegt sein. Im mathematischen Sinn definieren die Präzedenz-Regeln eine partielle Ordnung auf der Menge der Prozesse. Präze denz-Regeln können beispielsweise Ausdruck der Tatsache sein, daß die Resultate eines Prozesses A als Eingabedaten für einen Prozeß B benötigt werden. In der Pra xis wird ein Prozeßsystem oft als gerichteter Graph (dem sog. "Präzedenz-Graph" oder auch "Datenflußgraph") mit Knoten (den Prozessen) und Kanten (den Präze denz-Regeln) dargestellt. Die Präzedenz-Regeln bilden in ihrer Gesamtheit den Prä zedenz-Graphen, der das Prozeßsystem charakterisiert. Dieser Präzedenz-Graph muß nicht zusammenhängend sein. Insbesondere, wenn das Prozeßsystem aus unab hängigen Aufgaben (unter Umständen von verschiedenen Benutzern) hervorgegan gen ist, zerfällt der Graph in der Regel in mehrere unabhängige Komponenten (Teil prozeßsysteme). Da sich in diesem Fall mehrere Aufgaben das Rechnernetz teilen, spricht man auch von "Space-Sharing". Es ist nicht nötig, daß alle Teilprozeßsysteme gleichzeitig gestartet werden, sondern es ist auch möglich, das einige dieser Teilpro zeßsysteme erst gestartet werden, wenn andere bereits arbeiten.A "process" is a sequential sequence of computer instructions A "process system" means one by precedence rules partially ordered set of processes. A "precedent rule" is a statement about a Pair of processes (e.g. "A" and "B") of the form that Process A should be finished before process B can be started. Within a process system for all pairs of processes, for some pairs or - in the limit - for none single pair of precedence rules must be set. Define in a mathematical sense the precedence rules a partial order on the set of processes. Precise denz rules can, for example, be an expression of the fact that the results of a process A are required as input data for a process B. In the Pra A process system is often called a directed graph (the so-called "precedence graph" or also "data flow graph") with nodes (the processes) and edges (the precis denz rules). In their entirety, the precedence rules form the pre cedence graph that characterizes the process system. This precedence graph does not have to be coherent. Especially if the process system from independent pending tasks (possibly from different users) the graph usually breaks down into several independent components (part process systems). In this case, since several tasks share the computer network, one also speaks of "space sharing". It is not necessary that all sub-process systems started at the same time, but it is also possible that some of these subpro zeßsysteme only be started when others are already working.

Unter der "Laufzeit" eines Prozeßsystems versteht man den Zeitabschnitt zwischen dem Start des ersten Prozesses bis zum Ende des letzten Prozesses des Prozeßsy stems. Im Unterschied dazu wird die Zeit vor dem Start des ersten Prozesses eines Prozeßsystems die "Designzeit" des Prozeßsystems genannt.The "runtime" of a process system is the period between the start of the first process until the end of the last process of the process stems. In contrast, the time before the start of the first process becomes one Process system called the "design time" of the process system.

Unter der "externen Repräsentation der Information über das Prozeßsystems" (kurz: "der externen Repräsentation des Prozeßsystems") versteht man die Gesamtheit der Kenntnisse über das Prozeßsystem, die zur Designzeit verfügbar sind. Dem gegen über steht die "interne Repräsentation des Prozeßsystems" zu einem bestimmten Zeitpunkt t während der Laufzeit des Prozeßsystems, die die Gesamtheit der Kennt nisse widerspiegelt, die zu diesem Zeitpunkt t über das Prozeßsystem verfügbar sind. Under the "external representation of the information about the process system" (short: "the external representation of the process system") one understands the totality of the Knowledge of the process system that is available at design time. Against The "internal representation of the process system" relates to a specific one Time t during the running time of the process system, which the whole of the knowledge reflects nisse that are available at this time t via the process system.

Die Zuordnung der einzelnen Prozesse des Prozeßsystems zu den einzelnen Rechnern des Rechnernetzwerks.The assignment of the individual processes of the process system to the individual computers of the computer network.

Dabei wird unter der "Zuordnung" die Gesamtheit folgender zwei Sachverhalte ver standen.Here, the totality of the following two facts is ver under the "assignment" stood.

- The decisions which computer processes which processes.
- The order in which a computer processes the processes assigned to it.

Die Zuordnung der Prozesse zu den Rechnern (kurz: "Zuordnung") soll so herge stellt werden, daß die Laufzeit des gesamten Prozeßsystems auf einem vorgegebenen Rechnernetz minimiert wird. Dabei ist zu beachten, daß die Präzedenz-Regeln nicht verletzt werden. Besonders nachteilig wirkt es sich beispielsweise aus, wenn einzelne Rechner sehr viel stärker als andere belastet sind, oder wenn Rechner aufgrund von Präzedenz-Regeln sehr lange auf das Ende von Prozessen warten müssen. Außerdem ist der Kommunikationsaufwand zu beachten, der entsteht, wenn Resultate eines Prozesses von einem Rechner auf einen anderen Rechner übertragen werden müs sen.The assignment of the processes to the computers (in short: "assignment") is intended to be used here be that the runtime of the entire process system on a predetermined Computer network is minimized. It should be noted that the precedence rules are not get hurt. For example, it is particularly disadvantageous if individual Computers are much more heavily loaded than others, or if computers are due to Precedence rules have to wait a long time for processes to end. also the communication effort that arises when results of a Process must be transferred from one computer to another computer sen.

Da das beschriebene Problem NP-vollständig ist, kann eine optimale Lösung in ei nem mathematisch strengen Sinn bei praxisrelevanten Problemgrößen in der Regel nicht hergestellt werden, denn bekanntlich wächst bei allen bekannten Verfahren zur Lösung NP-vollständiger Probleme der Aufwand exponentiell mit der Größe des Problems. Deswegen wird "minimal" und "optimal" nicht im strengen Sinn verwendet, sondern in der Bedeutung "möglichst nahe am mathematischen Optimum".Since the problem described is NP-complete, an optimal solution can be found in ei nem mathematically strict sense with practice-relevant problem sizes as a rule not be produced, as is known to grow in all known processes Solving NP-complete problems exponentially with the size of the effort Problem. Therefore "minimal" and "optimal" are not used in the strict sense, but in the meaning "as close as possible to the mathematical optimum".

Die Zuordnung kann zur Laufzeit des Prozeßsystems oder vor dem Start des Prozeß systems (zur Designzeit) hergestellt werden. Wenn die Zuordnung während der Laufzeit hergestellt wird, kann sie durch eine zentrale Institution oder durch ein ver teiltes Verfahren hergestellt werden. Unter einer "zentralen Institution" versteht man einen Sachverhalt, der im Rechnernetz nur einmal existiert - beispielsweise eine spe zielle elektronische Schaltung oder ein einzelner ausgewählter Rechner, der die Zu ordnung übernimmt. Unter Umständen kann auch eine Datenstruktur, die nur ein mal im Rechnernetz existiert (beispielsweise eine zentrale Prozeßwarteschlange) als "zentrale Institution" gesehen werden. Dagegen spricht man von einer "verteilten" Zuordnung, wenn mehrere (mindestens zwei) Rechner Zuordnungsaufgaben über nehmen.The assignment can take place at runtime of the process system or before the start of the process systems (at design time). If the assignment during the Term is established, it can be done by a central institution or by a ver shared process. A "central institution" is understood a situation that only exists once in the computer network - for example, a specific one zielle electronic circuit or a single selected computer that the Zu order takes over. Under certain circumstances, a data structure that is only one times exists in the computer network (for example a central process queue) as "central institution" can be seen. In contrast, one speaks of a "distributed" Assignment if several (at least two) computers assign tasks via to take.

Die Prozesse des Prozeßsystems, das den Rechnern des Rechnernetzes zugeordnet werden soll, werden "Produktionsprozesse" genannt. Damit wird von "Verwaltungs prozessen" unterschieden, die für die inneren Aufgaben des Betriebssystems benötigt werden.The processes of the process system assigned to the computers in the computer network are to be called "production processes". This means that "Administrative processes ", which are required for the internal tasks of the operating system become.

Bei der Bearbeitung eines Prozeßsystems auf einem Rechnernetz ist in der Regel zwischen den einzelnen Rechnern ein Informationsaustausch nötig. Wenn ein einzi ger Rechner an mehrere Rechner im wesentlichen die gleiche Information versendet und wenn die Information einen gewissen Mindestumfang besitzt (etwa einige Byte), spricht man von einem "Rundschreiben". Bei kürzeren Informationen würde man von einem "Signal" sprechen. Eine "im wesentlichen gleiche Information" z. B. ist gegeben, wenn sich die Information nur durch kommunikationstechnische Angaben (wie z. B. Empfängeridentifikation) unterscheidet. Wenn ein Rundschreiben an alle Rechner des Rechnernetzes gerichtet ist, spricht man von einem "globalen Rundschreiben".When processing a process system on a computer network is usually An exchange of information between the individual computers is necessary. If a single ger computer sent to several computers essentially the same information and if the information has a certain minimum size (about a few bytes), one speaks of a "circular". With shorter information one would of speak a "signal". An "essentially the same information" e.g. B. is given if the information can only be identified by communication-related information (such as Recipient identification). If a circular to all computers of the computer network is referred to as a "global circular".

Nach dem Stand der Technik wird die Zuordnung zur Designzeit (also vor dem Start des ersten Prozesses) hergestellt. Eine solche Vorgehensweise erfordert aber genaue Kenntnisse der Ausführungszeiten der einzelnen Prozesse bereits vor dem Start des Prozeßsystems. In vielen wichtigen Problemen sind diese Ausführungszeiten aber da tenabhängig und deswegen vor dem Start des Prozeßsystem nur als Schätzungen ver fügbar. Beispielsweise kann die Lösung von Travelling-Salesman-Problemen gleicher Größe zwischen wenigen Sekunden und mehreren Stunden dauern. Wenn die tat sächlichen Ausführungszeiten von den Schätzungen abweichen, kann eine Zuord nung, die auf der Basis der Schätzungen hergestellt wurde, sehr ungünstig werden. Um diese Schwäche zu beseitigen, ist beabsichtigt, die Zuordnung erst während der Laufzeit herzustellen. Das hat den Vorteil, daß zunehmend detailliertere Kenntnisse über die tatsächlichen Ausführungszeiten verfügbar sind, und deswegen die Zuord nung den tatsächlichen Gegebenheiten wesentlich besser angepaßt ist.According to the state of the art, the assignment at design time (i.e. before the start of the first process). However, such an approach requires precise Knowledge of the execution times of the individual processes before the start of the Process system. However, these execution times are there in many important problems Depending on the ten and therefore before the start of the process system only ver as estimates available. For example, the solution of traveling salesman problems can be the same Size can last from a few seconds to several hours. If she did actual execution times may differ from the estimates, an assignment that were made on the basis of the estimates become very unfavorable. In order to eliminate this weakness, the intention is to assign only during the Establish term. This has the advantage of increasingly detailed knowledge about the actual execution times are available, and therefore the assignment tion is much better adapted to the actual circumstances.

Weiterhin wird nach dem Stand der Technik die Struktur des Prozeßsystem (z. B. die Anzahl der Prozesse und die Präzedenz-Regeln) zur Designzeit festgelegt. In vielen wichtigen Problemen ist diese Struktur aber datenabhängig. Beispielsweise ist in ei nigen Divide-and-Conquer Verfahren der Verzweigungsgrad datenabhängig. Das kann sich in einem datenabhängigen Verzweigungsgrad im Prozeßsystem widerspie geln. Wenn das Prozeßsystem zur Designzeit bereits festgelegt ist, können solche Verfahren nicht optimal umgesetzt werden. Um diese Schwäche zu beseitigen, ist beabsichtigt, das die Präzedenz-Regeln (und damit das Prozeßsystem) erst während der Laufzeit endgültig festzulegen. Das hat den Vorteil, daß die Entwicklungen, die sich während der Laufzeit ergeben, bestmöglich in der Struktur des Prozeßsystems niederschlagen können.Furthermore, according to the prior art, the structure of the process system (e.g. the Number of processes and precedence rules) set at design time. In many important problems, however, this structure is data-dependent. For example, in egg divide-and-conquer method, the degree of branching is data-dependent. The can be reflected in a data-dependent degree of branching in the process system apply. If the process system is already defined at design time, it can Procedures are not optimally implemented. To eliminate this weakness is intends that the precedence rules (and thus the process system) only during to finally determine the term. This has the advantage that the developments that arise during the runtime, best possible in the structure of the process system can knock down.

Obwohl es dynamische Lastausgleichs-Verfahren für Probleme ohne Präzedenz- Graph gibt, können diese Verfahren nicht auf Probleme mit Präzedenz-Graph ange wandt werden. Statt dessen liegt es nahe, für Probleme mit Präzedenz-Graph stati sche Verfahren zu verwenden, da diese einfacher zu realisieren sind. Die bloße An wendung von dynamischen Lastausgleichs-Verfahren auf Probleme mit Präzedenz- Graph scheitert schon daran, daß die damit erzeugten Zuordnungen keineswegs opti mal oder auch nur brauchbar wären.Although there are dynamic load balancing procedures for problems without precedence Graph there, these methods cannot indicate problems with precedence graph be turned. Instead, it stands to reason for problems with precedence graph stati use procedures since they are easier to implement. The Mere To application of dynamic load balancing methods to problems with precedence Graph already fails because the assignments generated in this way are in no way opti times or even just usable.

Eine spezifische Problematik der dynamischen Lösung von Zuordnungsproblemen mit Präzedenz-Graph liegt in der Wechselwirkung des dynamischen Verfahrens mit den Präzedenz-Graph. Das gilt besonders dann, wenn beliebige (nicht in ihrer Struk tur eingeschränkte) Präzedenz-Graphen durch ein verteiltes Verfahren zugeordnet werden sollen. Ein Problem wird deutlich am Beispiel eines Prozesses P mit mehre ren Vorgängern. Um unnötige Wartezeiten zu vermeiden, sollte P erst dann gestartet werden, wenn alle Vorgänger von P bereits fertig sind. Deshalb muß der Rechner R, der P startet, Kenntnis über mindestens folgende Sachverhalte besitzen.A specific problem of the dynamic solution of assignment problems with precedence graph lies in the interaction of the dynamic method the precedence graph. This is especially true if any (not in their structure restricted) precedence graphs assigned by a distributed method should be. A problem becomes clear using the example of a process P with more predecessors. In order to avoid unnecessary waiting times, P should only be started then when all predecessors of P are already finished. Therefore the computer R, the P starts, have knowledge of at least the following facts.

- Which processes are the predecessors of P.
- In what state (waiting, running, finished) are these processes.

In verteilten Verfahren ist der Rechner R nicht vom Anfang an festgelegt. Deshalb muß das Verfahren so konstruiert sein, daß die benötigten Informationen rechtzeitig bei dem Rechner verfügbar sind, der dann schließlich für den Start des Prozesses P verantwortlich sein wird.In distributed processes, the computer R is not fixed from the start. That's why The process must be constructed in such a way that the information required is timely are available at the computer, which is then finally used to start the process P will be responsible.

Dynamische Verfahren ohne Präzedenz-Graph kennen diese Schwierigkeiten nicht. Ein Verfahren für baumartige Präzedenz-Graphen, das die Zuordnung vor dem Start des ersten Prozesses vornimmt wird in der Offenlegungsschrift des Deutschen Paten tamtes DE 37 41 953 A1 dargelegt. Ein weiteres statisches Verfahren für periodische Prozeßsysteme wird von Dartzen Peng beschrieben (Peng et. al., Modelling of Con current Task Execution in a Distributed System for Real-Time Control, IEEE Trans actions on Computers, Vol. C-36, No. 4, April 1987, pp. 500-514). Ein Verfahren für Prozeßsysteme ohne Präzedenz-Graph wird von Ammon Barak beschrieben (Am mon Barak et. al., A Distributed Load-balancing Policy for a Multicomputer. Softwa re Practice and Experience, Vol. 15 (9), pp. 901-913, September 1985).Dynamic methods without a precedence graph do not know these difficulties. A method for tree-like precedence graphs that assigns before starting The first process is carried out in the published patent of the German Godfather tamtes DE 37 41 953 A1 set out. Another static method for periodic Process systems are described by Dartzen Peng (Peng et. Al., Modeling of Con current Task Execution in a Distributed System for Real-Time Control, IEEE Trans actions on Computers, Vol. C-36, No. April 4, 1987, pp. 500-514). A procedure for Process systems without a precedence graph are described by Ammon Barak (Am mon Barak et. al., A Distributed Load-balancing Policy for a Multicomputer. Softwa re Practice and Experience, Vol. 15 (9), pp. 901-913, September 1985).

Dem Anmeldungsgegenstand liegt die Aufgabe zugrunde, ausgehend von einer "ex ternen" Repräsentation der Information über das Prozeßsystem eine Zuordnung der Prozesse des Prozeßsystems zu den Rechnern des Rechnernetzes herzustellen, so daß die Ausführungszeit des Prozeßsystems minimiert wird. Diese Aufgabe soll durch den kennzeichnenden Teil des Patentanspruchs 1 sowie den kennzeichnenden Teil des Patentanspruchs 5 (Verfahrensansprüche) sowie durch die in Patentan spruch 9 beanspruchten Netzwerke (Anordnungsanspruch) gelöst werden.The object of the application is based on the task, starting from an "ex Representation of the information about the process system an assignment of the Manufacturing processes of the process system to the computers of the computer network, so that the execution time of the process system is minimized. This task is supposed to by the characterizing part of claim 1 and the characterizing Part of claim 5 (process claims) and by the in Patentan claim 9 claimed networks (claim to arrangement) can be solved.

Weiterhin ist vorgesehen, daßIt is also provided that

- the precedence rules that characterize the process system
- During the running time of the process system
- specified or
- modified or
- be determined.

Eine vorteilhafte Ausgestaltung des Verfahrens ist dadurch gegeben, daß keine glo balen Rundschreiben übertragen werden, wenn Prozesse gestartet werden.An advantageous embodiment of the method is given by the fact that no glo bale circulars are transmitted when processes are started.

Eine weitere vorteilhafte Ausgestaltung des Verfahrens ist dadurch gegeben, daß die Zuordnung nicht durch eine zentrale Institution vorgenommen wird.Another advantageous embodiment of the method is given in that the Assignment is not made by a central institution.

Die Erfindung betrifft auch Rechnernetzwerke, die nach einem erfindungsgemäßen Verfahren betrieben werden.The invention also relates to computer networks according to the invention Process operated.

Die Erfindung wird anhand der Fig. 1 bis Fig. 7 dargestellt. Darin zeigtThe invention is illustrated with reference to FIGS. 1 to Fig. 7. In it shows

Fig. 1 Die externe Repräsentation einer Verzweigung. Fig. 1 The external representation of a branch.

Fig. 2 Die externe Repräsentation einer Schleife. Fig. 2 The external representation of a loop.

Fig. 3 Ein Beispiel der externen Repräsentation eines Prozeßsystems ("Dynamische Anzahl von Pipelines"). Fig. 3 An example of the external representation of a process system ("dynamic number of pipelines").

Fig. 4 Ein Beispiel für einen klassischen Präzedenz-Graphen. Fig. 4 An example of a classic precedence graph.

Fig. 5 Ein Beispiel für ein Rechnernetzwerk. Fig. 5 An example of a computer network.

Fig. 6 Ein Beispiel für ein Rechnernetzwerk gemäß des anordnungsspezifischen Teils der Erfindung. Fig. 6 shows an example for a computer network according to the arrangement of the specific part of the invention.

Fig. 7 Vorrichtung zur Verbindung zwischen einem Rechner und einem Bus. Fig. 7 device for connection between a computer and a bus.

Die Herstellung der Zuordnung erfolgt in zwei Schritten.The assignment is made in two steps.

(1) The external representation of the process system becomes an initial internal one Representation made.
(2) An assignment is made from the internal representation.

Bei der externen Repräsentation (genannt: "Präzedenz-Graph") handelt es sich um gerichtete, bipartite Graphen mit Prozeßknoten (kreisförmig abgebildet) und Daten knoten (rechteckig abgebildet). Wenn von einem Prozeßknoten P ein Pfeil zu einem Datenknoten D führt, hat das die Interpretation, daß der Prozeß P die Daten D als Resultat erzeugt. Ein Pfeil in umgekehrter Richtung besagt, daß der Prozeß P die Daten D als Eingabedaten benötigt. Außerdem besitzt die externe Repräsentation Verzweigungen und Schleifen. Die Knoten der externen Repräsentation werden auf folgende Weise identifiziert: Knotennamen besitzen immer einen statischen Anteil (z. B. "t1"). Innerhalb von Schleifen oder Verzweigungen haben Knotennamen außer dem dynamische Komponenten, die durch ein ''-Zeichen und den Namen der Schleife bzw. Verzweigung dargestellt sind. Zur Modellierung von "Space-Sharing" kann dem Knotennamen noch der Name des Präzedenz-Graphen (z. B. "d1") voran gestellt und durch einen Punkt abgetrennt werden. Unter "Space-Sharing" versteht man eine Technik, bei der mehrere Prozeßsysteme die einzelnen Rechner eines Rechnernetzes untereinander aufteilen.The external representation (called: "precedence graph") is directional, bipartite graphs with process nodes (shown in a circle) and data knot (shown rectangular). If from an process node P an arrow to an Data node D leads, this has the interpretation that the process P the data D as Result generated. An arrow in the opposite direction indicates that the process P the Data D is required as input data. Also has the external representation Branches and loops. The nodes of the external representation are opened identified as follows: Node names always have a static part (e.g. "t1"). Inside loops or branches have node names except the dynamic components, which are denoted by a '' sign and the name of the Loop or branch are shown. To model "space sharing" can precede the node name with the name of the precedence graph (e.g. "d1") and separated by a dot. Under "space sharing" means one technique in which several process systems the individual computers one Divide the computer network among each other.

Eine Verzweigung besteht (neben ihrem Namen) aus einem Verzweigungsknoten, einem Sammelknoten und einem Präzedenz-Graphen (dem Verzweigungsrumpf). In Fig. 1 ist die dynamische Verzweigung mit dem Namen "vrzw" dargestellt, deren Rumpf nur aus einem einzigen Datenknoten besteht. Wenn bei der Ausführung des Prozeßsystems der Verzweigungsgrad (z. B. n) entschieden wird, werden n Kopien des Rumpfes angelegt. Die dynamische Komponente "vrzw" in den Knotennamen der n Kopien wird durch die Werte 1 . . . n substituiert. Im abgebildeten Beispiel entste hen somit die Datenknoten d1.d.1, d1.d.2, . . . , d1.d.n.A branch consists (in addition to its name) of a branch node, a collection node and a precedence graph (the branch body). In Fig. 1, the dynamic branch with the name "vrzw" is shown, the hull consists of only a single data node. If the degree of branching (e.g. n) is decided when executing the process system, n copies of the body are created. The dynamic component "vrzw" in the node names of the n copies is replaced by the values 1. . . n substituted. In the example shown, the data nodes d1.d.1, d1.d.2,. . . , d1.dn

Schleifen besitzen neben ihrem Namen nur einen Rumpf, der ebenfalls aus einem Präzedenz-Graphen besteht. Die Schleife in Fig. 2 heißt "schl". Für jede Iteration der Schleife wird eine neue Kopie des Rumpfes angelegt und der Wert des Schleifenzäh lers inkrementiert. Der Name der Schleife (im Beispiel "schl") wird in den Kopien des Rumpfes durch den Wert des Schleifenzählers ersetzt.In addition to their name, loops only have one body, which also consists of a precedence graph. The loop in Fig. 2 is called "schl". For each iteration of the loop, a new copy of the body is created and the value of the loop counter is incremented. The name of the loop ("schl" in the example) is replaced by the value of the loop counter in the copies of the body.

In Fig. 3, Fig. 4 ist ein Prozeßsystem abgebildet, das eine dynamische Anzahl von Prozeß-Pipelines unterschiedlicher Lange darstellt. Die Wendung "dynamische An zahl" bedeutet, daß die Anzahl erst während der Laufzeit des Prozeßsystems ent schieden wird. Analog wird die Länge der Pipeline (d. h. die Anzahl der Iterationen der Schleife) erst während der Laufzeit entschieden.In Fig. 3, Fig. 4, a process system is shown illustrating a number of dynamic process pipelines of different lengths. The phrase "dynamic number" means that the number is only decided during the running time of the process system. Similarly, the length of the pipeline (ie the number of iterations of the loop) is only decided during runtime.

Die Darstellung in Fig. 4 gibt eine mögliche interne Repräsentation (eine mögliche konkrete Realisierung) des Prozeßsystems in Fig. 3 wieder.The representation in FIG. 4 shows a possible internal representation (a possible concrete implementation) of the process system in FIG. 3.

Wenn ein Knoten der externen Repräsentation (ein sog. "Schablonenknoten", z. B. d2.vrzw in Fig. 3) Element einer Verzweigung oder einer Schleife ist, steht er meist für mehrere Knoten (den sog. "Ausprägungen" des Schablonenknotens, z. B. d2.1, d2.2 in Fig. 4) in der internen Repräsentation. Die Schablonenknoten eines Schlei fenrumpfes erhalten beispielsweise Ausprägungen für jeden Durchlauf der Schleife, die sich in ihrer Kantenstruktur unterscheiden können. Die Knoten am Ende des ersten Durchlaufs einer Schleife haben als Nachfolger beispielsweise die Knoten am Anfang des zweiten Durchlaufs. Dagegen haben die Knoten am Ende des letzten Durchlaufs als Nachfolger die Knoten nach der Schleife. Deshalb muß in der inter nen Repräsentation für jede Ausprägung eines Schablonenknotens Information über die Kantenstruktur gespeichert werden.If a node of the external representation (a so-called "template node", e.g. d2.vrzw in Fig. 3) is an element of a branch or a loop, it usually stands for several nodes (the so-called "characteristics" of the template node, e.g. d2.1, d2.2 in Fig. 4) in the internal representation. The template knots of a loop body receive, for example, characteristics for each pass of the loop, which can differ in their edge structure. For example, the nodes at the end of the first pass in a loop have the nodes at the beginning of the second pass as successors. On the other hand, the nodes at the end of the last run as successors have the nodes after the loop. For this reason, information about the edge structure must be stored in the internal representation for each form of a template node.

Unter der "initialen internen Repräsentation" versteht man den Zustand der internen Repräsentation zum Startzeitpunkt des Prozeßsystems. Sie stimmt in der Regel mit der externen Repräsentation überein.The "initial internal representation" means the state of the internal Representation at the start of the process system. As a rule, she agrees the external representation.

Wenn während der Laufzeit Entscheidungen über die Struktur des Prozeßsystems getroffen werden, (z. B. bezüglich des Grades einer dynamischen Verzweigung oder der Anzahl der Durchläufe einer Schleife), muß die interne Repräsentation entspre chend geändert werden. When making decisions about the structure of the process system during runtime (e.g. regarding the degree of dynamic branching or the number of passes of a loop), the internal representation must correspond be changed accordingly.

Eine andere Möglichkeit zur Realisierung der externen Repräsentaion ist die Ver wendung klassischer Präzedenz-Graphen wie in Fig. 4 dargestellt. Da sind bekannt lich bipartite Graphen mit Prozeß- und Datenknoten. Bei klassischen Präzedenz- Graphen besteht keine Möglichkeit, während der Laufzeit die Struktur des Prozeßsy stems (z. B. die Präzedenz-Regeln) zu verändern, deswegen stimmt die interne Re präsentation bei klassischen Präzedenz-Graphen zu jedem Zeitpunkt mit der exter nen Repräsentation überein.Another possibility for realizing the external representation is to use classic precedence graphs as shown in FIG. 4. There are known bipartite graphs with process and data nodes. With classic precedence graphs, there is no possibility to change the structure of the process system (e.g. the precedence rules) during the runtime, which is why the internal representation in classic precedence graphs matches the external representation at all times .

Zur Herstellung der gewünschten Zuordnung kann beispielsweise folgendes Verfah ren verwendet werden.The following procedure can be used, for example, to produce the desired assignment be used.

Aus den einzelnen Rechnern des Rechnernetzes wird eine (nichtleere) Teilmenge "SR" ausgewählt. Diese Teilmenge kann einen einzelnen Rechner, einige Rechner oder alle Rechner umfassen. Den Rechnern der Teilmenge SR wird jeweils eine Aufgabe übertragen, die in etwa mit einem menschlichen Arbeitsamt vergleichbar ist. Die Rechner der Menge SR werden Steuerrechner genannt. Die Zuordnungsauf gabe kann von den Steuerrechnern "dediziert" oder "non-dediziert" ausgeübt werden; d. h., unter Umständen können die der Menge SR zugehörigen Steuerrechner außer ihrer Zuordnungsaufgabe noch Produktionsprozesse bearbeiten (non-dediziert. Fall) oder aber sich ausschließlich ihrer Zuordnungsaufgabe widmen (dediziert Fall). Ein ausgewählter Rechner der Menge SR erhält den Namen "SR1".The individual computers in the computer network become a (non-empty) subset "SR" selected. This subset can be a single computer, some computers or include all computers. The computers in the subset SR each have one Transfer task that is roughly comparable to a human labor office is. The computers of the set SR are called tax computers. The assignment order The gift can be administered "dedicated" or "non-dedicated" by the control computers; d. that is, under certain circumstances, the control computers belonging to the set SR can edit production processes for their assignment task (non-dedicated. case) or devote yourself exclusively to their assignment task (dedicated case). A selected computer of the set SR is given the name "SR1".

Jedem Steuerrechner werden Rechnermengen zugewiesen, die jeweils Teilmengen der Rechner des Rechnernetzes sind. Diese Mengen werden Arbeitgeber-Bezirke bzw. Arbeitnehmer-Bezirke genannt.Computer quantities are assigned to each control computer, the respective partial quantities are the computer of the computer network. These quantities become employer districts or employee districts called.

Die Arbeitgeber-Bezirke stellen eine Partition auf der Menge der Rechner des Rechnernetzes dar; d. h., jeder Rechner gehört zu genau einem Arbeitgeber-Bezirk. Dagegen dürfen sich die Arbeitnehmer-Bezirke auch überschneiden. Das heißt jeder Rechner gehört zu mindestens einem Arbeitnehmer-Bezirk. Die Steuerrechner selbst genießen unter Umständen eine Ausnahmestellung, denn wenn die Zuord nungsaufgabe dediziert ausgeübt wird, gehören die Steuerrechner zu keinem Arbeit nehmer-Bezirk. Eine Alternative wäre, daß auch die Arbeitnehmer-Bezirke eine Par tition darstellen, also jeder Rechner zu genau einem Arbeitnehmer-Bezirk gehört.The employers' districts put a partition on the set of computers Computer network; d. that is, each computer belongs to exactly one employer district. In contrast, the employee districts may also overlap. That means everyone Computer belongs to at least one employee district. The tax calculator themselves may enjoy an exceptional position, because if the assignment tasks are performed in a dedicated manner, the control computers do not belong to any work takers district. An alternative would be that the employee districts also have a par representation, that is, each computer belongs to exactly one employee district.

Die Intention der beschriebenen Rechnermengen ist, daß ein Rechner, der startbe reite Prozesse erzeugt hat, die noch zugeordnet werden müssen, diese Prozesse an den Steuerrechner meldet, dessen Arbeitgeber-Bezirk er angehört. Die Wendung "startbereite Prozesse erzeugen" steht als Abkürzung für den Sachverhalt, daß der Rechner Daten erzeugt hat und in der Folge Prozesse, die eben diese Daten als Eingabe benötigen deshalb unter Umständen startbereit werden. Umgekehrt vergibt ein Steuerrechner Prozesse, die ihm gemeldet werden innerhalb seines Arbeitneh mer-Bezirks.The intention of the computer sets described is that a computer that starts has created processes that still have to be assigned to these processes reports the tax calculator whose employer district he belongs to. The turn "Generate ready processes" stands as an abbreviation for the fact that the Computer has generated data and subsequently processes that just this data as Entry may therefore need to be ready to start. Conversely forgives a control computer processes that are reported to him within his work mer district.

Im einzelnen wird die Zuordnung dann auf folgende Weise hergestellt.The assignment is then made in the following manner.

(1) The computer SR1 determines on the basis of the internal representation of the process system processes or processes that do not require data from any other process (the so-called "input processes").
(2) Each control computer maintains a list of previously unprocessed processes in his area of responsibility. The list is called the "process list".
(3) The control computer SR1 initializes its process list with the input processes.
(4) All other control computers initialize their process list with the empty set.
(5) Each control computer maintains a list from the computer that currently does not Process the process (called: "idle list"). The idle lists are with the whole Workers district initialized.
(5) Steps (6) to (12) are repeated until the process system is processed, d. H. until the last process is done.
(6) Each control computer checks its process list. If the list contains processes, these processes are assigned to computers that are entered in the idle list. The following points should be noted.
- Many processes require data that other processes have created. If at for example, a process P to be started on a computer R, the data required by the process P are transferred to the computer R. This creates hen transmission costs. The responsible tax calculator is therefore striving to Process P to start on a computer, so that the transmission costs as possible stay low. For this purpose, the control computer maintains lists in which is entered what processes on which computers were terminated and which data on which Computers reside. In addition, each control computer notes in which Zu stood (waiting, running, finished) the individual processes of the process system. Around To update these lists, the control computers maintain a system among themselves of circulars that are activated every time processes are started or completed or when data is being transferred.
- If the employee districts overlap, care must be taken be that not several control computers perform one computer at the same time transfer. The following protocol is suitable for this, for example.
(Message 1)
The control computer sends the potential employee a "bidding process" message.
(Message 2)
If the employee has already accepted tasks elsewhere, he replies with "DO NOT accept process".
If the worker is actually unemployed, he replies with "Accept Process ". On possibly further" offer process "messages from other sides, which later the worker replies from now until the end of the dialogue "DO NOT accept process".
(Message 3)
When the control computer receives an "accept process" message, it assigns the task to the employee. With an "Accept process NOT" message, further "Offer process" messages must be sent. (End of protocol and end of step (6))
(7) If the control computer wants to assign a process P to a computer R, checks the control computer based on the internal representation of the process system according to wel che data D are required for the execution of the process P. Because of his internal records, the control computer knows where the data D reside. Of the Control computer causes data D to be transferred to computer R.
(8) If a computer R from a control computer (eg called "SR_Start") one Process P received for processing, it waits for the required data. As soon as he can access the data, he starts process P.
Process P is then ended after a few working hours. Avoid this event the computer R to the control computer, whose employer district the computer R is too is divided. In the example, this control computer might have the name "SR_X".
(9) The control computer SR_X publishes the end of process P (as well as SR_Start previously published the start) via the circular mechanism in Circles of control computers; d. that is, to the other computers in the set SR.
(10) When process P ends, new data (called: "D_neu") becomes available in many cases. Under certain circumstances, additional processes (called: "P_neu") can now be started. The control computer includes the processes from P_new in its process list if the following conditions apply.

- The processes require data from D_neu and

- All data that the processes need has already been created.
(11) Due to transmission times for the circular, there may be conflicts come. Possible conflicts can be that of starting a certain one Process P does not feel responsible for a single control computer, or that vice versa several control computers start the same process in different places. Precautions must be taken against these conflicts. A possibility this is because the control computer always starts the process P in whose employer District the last predecessor of P is ended. Should still have several taxes start an "incarnation" of process P, this problem becomes discovered sooner or later via the circular mechanism. Then must arbitrarily one incarnation that continues to work, and everyone else Incarnations are canceled. Such an arbitrary selection could be for example, that the process on the computer with the largest serial number may continue to work.
The control computer SR_X therefore notifies the other control computers that it is Processes P_neu has added to its process list. If another tax computer (eg "SR_Y") a process P from the set P_new already in its process list, it raises an objection to the SR_X control computer. It an arbitrary (but clear) agreement is reached as to which tax law ner then has to delete the process from its process list (e.g. the control computer, who has the smaller serial number). For a possible objection from another tax computer, both the control computer SR_X and the tax must Compute SR_Y a waiting period before starting the processes in P_neu. The Waiting time can be determined by the maximum transmission times in the computer network and estimate a safety reserve.
To avoid problems that arise when there is no tax calculator for you Feels responsible, it is advantageous if a control computer starts a process If in doubt, P_neu first includes it in its process list.
(12) If a tax calculator is loaded above average, it can perform tasks delegate other districts.
An example of such a load balancing procedure could look as follows. Everyone Control computers, for example, have a maximum of "MaxAnzNachbar" many neighboring ones Tax calculator. The neighboring control computers swap periodically Information about their utilization, which is determined by the number of Pro processes (i.e. the elements of the process list). Because of this data each control computer calculates the average load (called: "medium load") in his neighborhood. If your own workload (called: "OwnLast") is signifi is above the average load and the load (called "NachbLast") of a neighbor (e.g. called "Nachb") is significantly below MittelLast, eini processes transferred. Scalar parameters (threshold values) can be used to determine which means "significant" in terms of content.
For example, you could specify that a maximum of x processes should be transferred. x: = MIN ((Own load - Medium load) / (2 * MaxAnzNachbar),
(MediumLoad - Postload) / (2 * MaxAnzNachbar)).
Another alternative for a load balancing process would be an offer prototype coll, in which a tax calculator that feels overloaded assigns tasks to its neighbors offers. An example of such a protocol would be given as follows.
(Message 1)
Overloaded control computer sends "bidding process".
(Message 2)
Neighbor decides whether he can handle additional processes and responds accordingly with "accept process" or "accept process NOT".
(Message 3)
Overloaded control computer may delegate process to neighbor. (End of protocol)
Special attention requires that the load balancing process works "stably". For example, the method must not tend to vibrate; d. that is, it must not (oscillating) cyclically shift processes between different control computers, without coming much closer to the actual goal (the even load) men.
(End of step (12) and end of the description of the method in individual steps)

Other design options

Das Problem der Aufteilung in Bezirke und die Wahl der Steuerrechner ist ein Opti mierungsproblem: Die Bezirke und Steuerrechner sind so zu wählen, daß eine geeig nete Zielfunktion, die den Kommunikationsaufwand charakterisiert, minimiert wird. Für die Zielfunktion kann beispielsweise eine einfach zu berechnende Heuristik ein gesetzt werden. Eine Möglichkeit wäre:The problem of dividing into districts and choosing the tax calculator is an option mation problem: The districts and tax calculators should be chosen so that a suitable nete objective function, which characterizes the communication effort, is minimized. For example, a heuristic that is easy to calculate can be used for the target function be set. An option would be:

ZielFunktion: = Const1_*MittelSR + Const2_*MittelAG + Const3_*MittelAN;Objective function: = Const1 _* MittelSR + Const2 _* MittelAG + Const3 _* MittelAN;

In dieser Form stehen Const1, Const2 und Const3 für beliebige, aber festgewählte reell-wertige Gewichtsfaktoren. MittelSR steht für die mittlere Distanz zwischen Steuerrechnern, MittelAG und MittelAN bezeichnen die mittlere Distanz innerhalb eines Arbeitgeber-Bezirks, bzw. Arbeitnehmer-Bezirks. Die Parameter des Verfah rens sind Const1, Const2, Const3 und die Anzahl der Steuerrechner. Diese Parame ter können intuitiv gewählt werden (beispielsweise: Const1 = Const2 = Const3 = 1) oder, nachdem die anderen Komponenten des Verfahrens bereits festgelegt sind, auch trainiert werden. Unter einem "Training" versteht man ein Optimierungsverfah ren, das auf einem Satz typischer Anwendungsbeispiele (hier: Prozeßsysteme) be ruht, der "Trainingsmenge" genannt wird. Ausgehend von einer weitgehend beliebi gen initialen Belegung der Parameter (hier: Const1, Const2, Const3), wird ein iterati ves Optimierungsverfahren angewandt. Bekannte Beispiele solcher Optimierungsver fahren sind "Gradientenabstieg" und "Koordinatenabstieg". Im Zuge der Optimierung wird anhand der Trainingsmenge fortlaufend geprüft, daß sich die Zielfunktion (hier: die Laufzeit der Prozeßsysteme) auch tatsächlich verbessert.In this form, Const1, Const2 and Const3 stand for any but selected real weight factors. MittelSR stands for the mean distance between Tax calculators, MittelAG and MittelAN indicate the average distance within of an employer district or employee district. The parameters of the procedure rens are Const1, Const2, Const3 and the number of control computers. This parame can be selected intuitively (for example: Const1 = Const2 = Const3 = 1) or, after the other components of the process have already been determined, also be trained. A "training" is an optimization process ren based on a set of typical application examples (here: process systems) rests, which is called "training amount". Starting from a largely arbitrary If the parameters are initially assigned (here: Const1, Const2, Const3), an iterati ves optimization process applied. Known examples of such Optimierungsver driving are "gradient descent" and "coordinate descent". In the course of optimization the training volume is used to continuously check that the target function (here: the running time of the process systems) is actually improved.

Eine andere Möglichkeit wäre die exakte oder näherungsweise Lösung des Optimie rungsproblems: "Wähle die Menge der Steuerrechner SR, die Arbeitgeber-Bezirke und die Arbeitnehmer-Bezirke so, daß der Kommunikationsaufwand insgesamt mini miert wird". Für die Lösung derartiger Probleme kennt man eine Reihe von Verfah ren wie "Branch & Bound" sowie "Integerprogrammierung".Another possibility would be the exact or approximate solution of the Optimie problem: "Choose the amount of tax calculator SR, the employer districts and the employee districts so that the overall communication effort is mini A number of methods are known for solving such problems such as "Branch & Bound" and "Integerprogramming".

Eine weitere Möglichkeit besteht in der manuellen Aufteilung des Rechnernetzes. Bei regelmäßigen, maschenähnlichen Verbindungsnetzwerken könnte man beispiels weise das gesamte Rechnernetz in X_*Y rechteckige Felder aufteilen und jeweils ei nem zentral gelegenen Rechner (geometrischer Schwerpunkt) die Zuordnungsfunk tion übertragen. Diese Vorgehensweise hat den Vorteil, daß sie sehr einfach zu reali sieren ist. Im Rechnernetz von Fig. 5 wurde diese Technik angewandt.Another possibility is the manual division of the computer network. In the case of regular, mesh-like connection networks, one could, for example, divide the entire computer network into X _* Y rectangular fields and transmit the assignment function to a centrally located computer (geometric focus). This procedure has the advantage that it is very easy to implement. This technique was used in the computer network of FIG .

Ein interessanter Grenzfall des beschriebenen Verfahrens ist, daß jeder Rechner sein eigener (non-dediziert) Steuerrechner ist. Der Arbeitgeber-Bezirk wäre dann nur der einzelne Rechner, und der Arbeitnehmer-Bezirk wäre das gesamte Rechner netz. In diesem Fall geht das beschriebene Verfahren in ein vollständig verteiltes Verfahren über. Ein solches Verfahren hat aber den Nachteil, daß globale Rund schreiben nötig sind, die bekanntlich bei größeren Rechnernetzen nur sehr aufwen dig realisiert werden können. Deswegen eignet sich das vollständig verteilte Verfah ren hauptsächlich für kleinere Rechnernetze.An interesting borderline case of the described method is that every computer is its own (non-dedicated) tax calculator. The employer district would then be only the single computer, and the employee district would be the entire computer network. In this case, the described method goes into a completely distributed one Procedure about. However, such a method has the disadvantage that global round Write are necessary, which is known to be very difficult for larger computer networks dig can be realized. That is why the fully distributed procedure is suitable mainly for smaller computer networks.

Ein anderer Grenzfall des Verfahrens ist ein zentrales Verfahren. In diesem Fall gibt es nur einen einzigen Steuerrechner. Der Arbeitgeber-Bezirk und der Arbeitneh mer-Bezirk stimmen mit dem gesamten Rechnernetz überein. Das Lastausgleichsver fahren zwischen den Steuerrechnern wird dann natürlich überflüssig.Another borderline case of the procedure is a central procedure. In this case there there is only one control computer. The employer district and the employee mer district match the entire computer network. The load balancing ver driving between the control computers is then of course unnecessary.

Die Praxis zeigt aber, daß bei einem einzigen zentralen Steuerrechner die Gefahr besteht, daß dieser einzige Steuerrechner überlastet ist und in der Folge die Lei stung des Gesamtsystems dann sinkt. Außerdem sind bekanntlich bei einem einzigen Steuerrechner Notwendigkeiten der Fehlertoleranz schwieriger zu berücksichtigen.Practice shows, however, that there is a risk with a single central control computer there is that this only control computer is overloaded and consequently the Lei performance of the overall system then drops. In addition, it is known that there is only one Control computers more difficult to consider necessities of fault tolerance.

In bestimmten Anwendungen kann es sinnvoll sein, Teile einer Zuordnung bereits zur Designzeit festzulegen und nur die verbleibenden noch nicht festgelegten Teile der Zuordnung zur Laufzeit herzustellen. Beispielsweise können Teile des Prozeßsy stems, die strengen Echtzeitanforderungen genügen müssen, bereits vorab zugeord net werden. In diesem Fall stellt das Verfahren die Zuordnung auf folgende Weise her: Die Prozesse, deren Zuordnung bereits vorab zur Designzeit festgelegt ist, wer den in einem Kommandoverfahren von den Steuerrechnern an die dafür vorgesehe nen Rechner vergeben. Alle anderen Prozesse werden gemaß des bisher beschriebe nen Verfahrens zugeordnet.In certain applications, it may make sense to have parts of an assignment already to be determined at design time and only the remaining undecided parts the assignment at runtime. For example, parts of the process sy assigned to stems that have to meet strict real-time requirements in advance be net. In this case, the procedure makes the assignment in the following way forth: The processes, the assignment of which is determined in advance at the design time, who that in a command procedure from the control computers to the intended Assign a calculator. All other processes are described according to the previously assigned a procedure.

Unter der Annahme, daß Rechner einer gewissen Ausfallwahrscheinlichkeit unterlie gen, kann es nötig werden, eine zur Designzeit festgelegte Zuordnung während der Laufzeit zu ändern. Sobald nämlich ein Prozeß einem Rechner zugeordnet werden soll, der als defekt diagnostiziert ist, kann die Zuordnung nicht so realisiert werden, wie es zur Designzeit vorgesehen war. In diesem Fall stellt das Verfahren die Zuord nung auf folgende Weise her: Solange kein Rechner defekt ist, ordnet das Verfahren die Prozesse so zu, wie es zur Designzeit festgelegt wurde. Sobald aber der Fehlerfall eintritt, wird die zur Designzeit festgelegte Zuordnung ignoriert und die Prozesse werden gemäß des bisher beschriebenen Verfahrens zugeordnet.Assuming that the computer was subject to a certain probability of failure , it may be necessary to make an assignment at design time during the Change term. As soon as a process is assigned to a computer should be diagnosed as defective, the assignment can not be realized so as it was intended at design time. In this case, the procedure provides the assignment in the following way: As long as no computer is defective, the procedure arranges the processes as it was set at design time. But as soon as the error occurs occurs, the assignment defined at design time and the processes are ignored are assigned according to the procedure described so far.

Der Übersichtlichkeit wegen wurde bisher unterstellt, daß auf jedem Rechner maxi mal ein Produktionsprozeß bearbeitet wird. Das dargestellte Verfahren eignet sich aber auch für die parallele Bearbeitung mehrerer Produktionsprozesse. Eine einfa che Möglichkeit wäre, daß auf jedem physikalischen Rechner mehrere "virtuelle Ma schinen" simuliert werden. Im beschriebenen Verfahren treten dann die virtuellen Maschinen an die Stelle der physikalischen Rechner.For the sake of clarity, it was previously assumed that maxi times a production process is processed. The method shown is suitable but also for the parallel processing of several production processes. A simple che possibility would be that several "virtual Ma machines "are simulated. In the described method, the virtual ones then occur Machines in the place of physical computers.

Desweiteren wurde der Übersichtlichkeit wegen im dargestellten Verfahren unter stellt, daß ein Prozeß vollständig auf dem Rechner ausgeführt wird, auf dem er ge startet wurde. Das heißt keine Verlagerung laufender Prozesse. Aber auch diese vorläufi ge Einschränkung kann auf einfache Weise überwunden werden. Eine Möglichkeit dafür wäre die einzelnen Prozesse in der externen Repräsentation des Prozeßsystems durch Sequenzen von Teilprozessen zu ersetzen. Nach jedem Teilprozeß kann dann eine Verlagerung stattfinden. Man beachte in diesem Zusammenhang, daß die Ver lagerungskosten eines Prozesses im Verlauf seiner Laufzeit starken Schwankungen unterliegt. Zu bestimmten Zeitpunkten kann ein Prozeß beispielsweise im großen Umfang temporäre Daten erzeugen. Während dieser Zeiten ist die Verlagerung be sonders aufwendig. Die beschriebene Aufteilung der Prozesse in Sequenzen von Teilprozessen stellt eine Möglichkeit zur Verfügung, eine Verlagerung des Prozesses zu solch ungünstigen Zeitpunkten zu verhindern.Furthermore, for the sake of clarity, the procedure described below represents that a process is completely executed on the computer on which it ge was started. That means no relocation of ongoing processes. But also these provisional ones Restriction can be overcome in a simple manner. A possibility for that would be the individual processes in the external representation of the process system to be replaced by sequences of sub-processes. Then after each sub-process a relocation take place. It should be noted in this connection that the Ver Storage costs of a process fluctuate greatly over the course of its life subject to. At certain points in time, for example, a process can be large Generate amount of temporary data. During these times the relocation will be particularly complex. The described division of the processes into sequences of Subprocesses provide a possibility, a relocation of the process to prevent at such unfavorable times.

Insgesamt ist das beschriebene Verfahren durch mindestens 8 Größen beeinflußbar.Overall, the method described can be influenced by at least 8 variables.

1. A set of computers (the control computers).
2. The associated employer districts.
3. The associated employee districts.
4. "Dedicated" Boolean variables.
5. The load balancing process between the control computers.
6. The protocol for assigning tasks.
7. The protocol for the notification of unprocessed tasks.
8. The maximum number of production processes on one machine.

Um die beschriebenen Techniken zu verdeutlichen, sollen die Prozesse des Prozeß systems aus Fig. 3 den Rechnern des Rechnernetzes in Fig. 5 zugeordnet werden. Die Rechner (1, 2, 3, 4) sowie (5, 6, 7, 8) stellen in Fig. 5 die Arbeitgeber-Bezirke dar, die mit den Arbeitnehmer-Bezirken übereinstimmen. Die dediziert Funktion des Steuerrechners übernehmen die Rechner 3 und 5.In order to clarify the techniques described, the processes of the process system from FIG. 3 are to be assigned to the computers of the computer network in FIG. 5. The computers ( 1 , 2 , 3 , 4 ) and ( 5 , 6 , 7 , 8 ) represent the employer districts in FIG. 5 which correspond to the employee districts. Computers 3 and 5 assume the dedicated function of the control computer.

(1) SR1 determines the input process t1.
(2) All three workers in the SR1 district are currently unemployed.
(3) SR1 starts the process t1 on the closest computer (= CPU1).
(4) SR1 updates its local knowledge.

Der Übersichtlichkeit wegen wird die Aktualisierung des lokalen Wissens via des Rundschreibenmechanismus auf der Ebene der Steuerrechner nicht dargelegt.For the sake of clarity, the local knowledge is updated via the Circular mechanism not set out at the level of the tax calculator.

(5) CPU1 recognizes that no data is required and starts t1.
(6) CPU1 copes with t1; t1 decides that t1 will have five successors.
(7) t1 on CPU1 concretizes the internal representation of the process system.
(8) t1 creates the data nodes d.0.0, d.0.1,. . . , d.0.4 and places them in the memory of CPU1 from.
(9) t1 reports to SR1 that t1 is now ready.
(10) From the completion report of t1, the SR1 sees that the data d.0.0. . . d.0.4 are generated and stored in the memory of CPU1.
(11) The control computer SR1 should now start the successor processes of t1.
(12) The successors of t1 are t.0.0. . . t.0.4.
(13) SR1 must check which of the processes t.0.0. . . t.0.4 can now be started can. As the predecessor, t.0.0 only has d.0.0 that has already been created. The same applies to the other knot. All five processes can thus be started.
(14) SR1 has three free computers in its district, each of which receives a process. SR1 starts t.0.0, t.0.1 and t.0.2 on CPU1, CPU2 or CPU4 and pushes the over the required data.
(15) CPU1 transfers the data and deletes it in its own memory.
(16) CPU2 and CPU4 receive the data and can process t.0.1 and t.0.2 thus start. The assignment of the first three processes is now complete.
(17) So far, the load balancing procedure between the control computers has been terminated Completely ignored for reasons of clarity.

Nun tauschen die Steuerrechner SR1 und SR2 ihren Auslastungsgrad aus. SR1 hat zwei startbereite Prozesse und SR2 überhaupt keinen.The control computers SR1 and SR2 now exchange their degree of utilization. SR1 has two ready-to-start processes and SR2 none at all.

SR1 wendet folgende Formel an.SR1 applies the following formula.

AnzVerlagerteProzesse = (Last(SR1)-Last(SR2))/(AnzNachbarn_*2) = (2-0)/(1_*2) = 1.Number of displaced processes = (Last (SR1) -Last (SR2)) / (No. of neighbors _* 2) = (2-0) / (1 _* 2) = 1.

Nach dieser Formel wäre also ein Prozeß von SR1 an SR2 zu übertragen.According to this formula, a process would be transferred from SR1 to SR2.

(18) SR1 decides to relocate t.0.3.
(19) SR1 sends the following information to SR2: "I transfer the execution of the Process t.0.3. As you know, this process requires the data d.0.3. They are in the CPU1's memory. "
(20) SR2 receives this message and starts the process t.0.3. CPU7 encounters the Transfer the data to.
(21) This completes a cycle of load balancing.
(22) Finally, CPU1 goes to end process t.0.0.
(23) t.0.0 decides that the loop "schl" cannot be left and generates the data d.1.0 in the memory of CPU1.
(24) t.0.0 asks the internal representation of the process system as follows to make manent: "t.0.0 has decided that the loop has not yet left becomes".
(25) t.0.0 reports to SR1 that it is finished.
In return, SR1 starts the last remaining successor t.0.4 on CPU1.
(27) After some time, t.0.2 on CPU4 also ends.

Im Unterschied zu t.0.0 entscheidet er aber, daß sein Zweig die Schleife verläßt.In contrast to t.0.0, it decides that its branch leaves the loop.

(28) t.0.2 informs SR1 that it is finished.
(29) SR1 starts t.1.0 on CPU4.
(30) After a while all five d2.vrzw will be created.
(31) The computer SR1 knows that t2 has five predecessors that have now been generated. Des because of this, t2 can now be started.

Anordnungsspezifischer Teil der Erfindung. Arrangement-specific part of the invention.

Die Erfindung kann beispielsweise durch ein Netzwerk von Computern realisiert werden. Ein Beispiel ist in Fig. 6 gegeben. Die Funktion des Steuerrechners wird dediziert übernommen (im Beispiel in Fig. 6 durch die Rechner 13 und 14). Sämtli che Rechner, die eine Zuordnungsaufgabe wahrnehmen, sind durch einen Bus mit einander verbunden (in Fig. 6 "Bus 2" genannt). Dadurch läßt sich der Rundschreib mechanismus sehr effizient realisieren, denn der sendende Steuerrechner erreicht mit einem einzigen Zugriff auf den Bus alle Empfänger.The invention can be implemented, for example, by a network of computers. An example is given in FIG. 6. The function of the control computer is taken over in a dedicated manner (in the example in FIG. 6 by computers 13 and 14 ). All computers that perform an assignment task are connected to each other by a bus (called "bus 2 " in FIG. 6). This enables the circular mechanism to be implemented very efficiently, because the sending control computer reaches all receivers with a single access to the bus.

Im Beispiel können die Steuerrechner mit dem Bus über eine spezielle Vorrichtung (in Fig. 6 dargestellt durch ein kleines Quadrat) verbunden sein, die die Steuerrech ner wesentlich beim Versand und Empfang von Rundschreiben entlastet. Eine Reali sierungsmöglichkeit dieser Vorrichtung ist in Fig. 7 gegeben.In the example, the control computers can be connected to the bus via a special device (represented by a small square in FIG. 6), which substantially relieves the tax computers of sending and receiving circulars. A realization possibility of this device is given in Fig. 7.

Die Vorrichtung besteht aus einer handelsüblichen Schaltung zur Busansteuerung (in Fig. 7 mit "BZG" bezeichnet) und einem Dual-Port-Speicher (in Fig. 7 mit "SPEIC" bezeichnet). Die Einheit BZG liest eintreffende Rundschreiben von Bus und schreibt sie in den Dual-Port Speicher SPEIC. Aus dem Dual-Port-Speicher SPEIC werden sie vom Steuerrechner (in Fig. 7 "SR" bezeichnet) übernommen. Der Steuer rechner wird somit von den Ansteuerungsaufgaben für den Bus entlastet.The device consists of a commercially available circuit for bus control (labeled "BZG" in FIG. 7) and a dual-port memory (labeled "SPEIC" in FIG. 7). The BZG unit reads incoming circulars from the bus and writes them to the dual-port memory SPEIC. They are taken over from the dual-port memory SPEIC by the control computer (designated "SR" in FIG. 7). The control computer is thus relieved of the control tasks for the bus.

Die Arbeitgeber-Bezirke stimmen mit den Arbeitnehmer-Bezirken überein. Im Bei spiel in Fig. 6 sind das die Rechner (1, 2, 3, 4, 5, 6), (7, 8, 8, 10, 11, 12). Die Rechner der Arbeitgeber-Bezirke können untereinander durch ein Verbindungsnetzwerk kommunizieren. Im Beispiel in Fig. 6 ist dieses Netzwerk durch einen doppelt ver maschten Ring realisiert. Diese Struktur wird allgemein der Klasse der Netzwerke auf der Basis lokaler Nachbarschaft zugerechnet. Solche Verbindungsnetzwerke sind wegen ihrer Leistungsfähigkeit, ihren einfachen Realisierungsmöglichkeiten und ih rer Fehlertoleranzeigenschaften sehr geschätzt.The employer districts are the same as the employee districts. In the example in Fig. 6, these are the computers ( 1 , 2 , 3 , 4 , 5 , 6 ), ( 7 , 8 , 8 , 10 , 11 , 12 ). The computers of the employers' districts can communicate with each other through a connection network. In the example in Fig. 6, this network is realized by a double meshed ring. This structure is generally assigned to the class of networks based on local neighborhood. Such connection networks are highly valued for their performance, their simple implementation options and their fault tolerance properties.

Zwischen sämtlichen Rechnern eines Arbeitgeber-Bezirks und dem zugehörigen Steuerrechner besteht eine direkte Verbindung. Damit kann der wichtige Kontakt eines Steuerrechner zu seinem Bezirk auf effiziente Weise hergestellt werden. Durch einen weiteren Bus (in Fig. 6 als "Bus 1" bezeichnet) ist eine Kommunikationsmög lichkeit zwischen Rechnern verschiedener Bezirke hergestellt. Auf diesen Bus kön nen alle Rechner außer den Steuerrechnern zugreifen.There is a direct connection between all computers in an employer district and the associated tax computer. This enables the important contact of a tax calculator to its district to be established in an efficient manner. By another bus (referred to in FIG. 6 as "bus 1 ") is a communication possibility between computers in different districts. All computers except the control computers can access this bus.

Claims

1. A method of operating a computer network consisting, characterized of a plurality of intercommunicating computers, which are allocated according to one of precedence rules characterized processing system processes in the form of sequential computer instructions that the assignment during the life of the process system by one or more selected control computer of the computer network dynamic according to the workload of the individual computers

- specified or
- modified or
- be determined,

by the selected control computer after completing a Process that now assign processes to computers that are ready to start are not fully utilized.

2. The method according to claim 1, characterized in that transmit the necessary information through targeted messages become.

3. The method according to claim 1, characterized in that the specification of the assignment takes place in that

- Processes, the assignment of which is already determined at design time, are assigned to the intended computers and that
- The assignment of all other processes is determined dynamically in accordance with the workload of the computers and the data transfer times.

4. The method according to claim 1, characterized in that the modification of the assignment takes place in that

- Processes, the assignment of which is not yet determined at the design time, are dynamically determined according to the data transfer times and the workload of the computers, and that
- Processes, the assignment of which is already fixed at the design time, are assigned to the intended computers if the respective computer is not defective and that
- Processes whose assignment to the design time has already been determined can be dynamically defined according to the data transfer times and the workload of the computers if the respective computer is defective.

5. A method of operating a computer network consisting of a plurality of computers communicating with one another, to which processes in the form of sequential computer instructions are assigned according to a process system characterized by precedence rules, characterized in that

(a) that the precedence rules are set during the life of the process system.
(b) and that
- Processes can have a number of successors unknown at the design time or
- Process loops can have an unknown number of passes at design time

6. The method according to claim 5, characterized in that transmit the necessary information through targeted messages becomes.

7. The method according to claim 5, characterized in that the specification of the assignment takes place in that

8. The method according to claim 5, characterized in that the modification of the assignment takes place in that

9. Computer network for carrying out methods 1 to 8 by means of n computers which can connect to one another via communication links; with some selected computers that take over a control function and each carry out the assignment in a limited area of the computer network, characterized in that

- The control computers are connected to each other via dual-port memory and a first bus and that
- There is a direct connection to the associated control computer between all computers in the delimited area and that
- The individual delimited areas are connected to each other by a second bus that all computers except the control computer can access.