DE4132764A1 - Organisation of computer network system - using precedence rules with dynamic adaption within cycle for computers coupled onto network - Google Patents
Organisation of computer network system - using precedence rules with dynamic adaption within cycle for computers coupled onto networkInfo
- Publication number
- DE4132764A1 DE4132764A1 DE19914132764 DE4132764A DE4132764A1 DE 4132764 A1 DE4132764 A1 DE 4132764A1 DE 19914132764 DE19914132764 DE 19914132764 DE 4132764 A DE4132764 A DE 4132764A DE 4132764 A1 DE4132764 A1 DE 4132764A1
- Authority
- DE
- Germany
- Prior art keywords
- computers
- computer
- processes
- assignment
- process system
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 claims abstract description 237
- 230000008569 process Effects 0.000 claims description 186
- 238000004891 communication Methods 0.000 claims description 8
- 230000008901 benefit Effects 0.000 abstract description 4
- 238000013461 design Methods 0.000 description 13
- 230000006870 function Effects 0.000 description 7
- 238000012546 transfer Methods 0.000 description 6
- 238000004519 manufacturing process Methods 0.000 description 5
- 230000005540 biological transmission Effects 0.000 description 4
- 230000007246 mechanism Effects 0.000 description 4
- 238000012545 processing Methods 0.000 description 4
- 238000005457 optimization Methods 0.000 description 3
- 238000012549 training Methods 0.000 description 3
- 230000008859 change Effects 0.000 description 2
- 230000002950 deficient Effects 0.000 description 2
- 230000001419 dependent effect Effects 0.000 description 2
- 238000005192 partition Methods 0.000 description 2
- 238000013459 approach Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000018109 developmental process Effects 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
- 230000026676 system process Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5061—Partitioning or combining of resources
- G06F9/5066—Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Multi Processors (AREA)
Abstract
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 4. Die Erfindung betrifft darüber hinaus Rechnernetzwerke zur Durchfüh rung der Verfahren.The invention relates to a method according to the preamble of claim 1 The invention further relates to a method according to the preamble of the Proverb 4. The invention also relates to computer networks for implementation procedure.
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 Precedenceregeln partiell geordnete Menge von Prozessen. Eine "Precedenceregel" 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 Precedenceregeln festgelegt sein. Im mathematischen Sinn definieren die Predenceregeln eine partielle Ordnung auf der Menge der Prozesse. Precedence 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 Praxis wird ein Prozeßsysteme oft als gerichteter Graph (dem sog. "Datenflußgraph") mit Knoten (den Prozessen) und Kanten (den Precedenceregeln) dargestellt. Dieser Da tenflußgraph muß nicht zusammenhängend sein. Insbesondere, wenn das Prozeßsy stem aus unabhängigen Aufgaben (unter Umständen von verschiedenen Benutzern) hervorgegangen ist, zerfällt der Graph in der Regel in mehrere unabhängige Kompo nenten (Teilprozeßsysteme). Da sich in diesem Fall mehrere Aufgaben das Rechner netz teilen, spricht man auch von "Space-sharing". Es ist nicht nötig, daß alle Teilpro zeßsysteme gleichzeitig gestartet werden, sondern es ist auch möglich, daß einige die ser Teilprozeßsysteme erst gestartet werden, wenn andere bereits arbeiten.A "process" is a sequential sequence of computer instructions A "process system" is understood to be a partial one by precedence rules ordered set of processes. A "precedence 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. Define in a mathematical sense the preaching rules a partial order on the set of processes. Precedence 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 practice a process system is often used as a directed graph (the so-called "data flow graph") Nodes (the processes) and edges (the precedence rules). This there tenflussgraph need not be contiguous. Especially when the process sy stem from independent tasks (possibly from different users) emerged, the graph usually breaks down into several independent compos nenten (sub-process systems). Since in this case there are several tasks the computer sharing a network is also known as "space sharing". It is not necessary that all subpro zeßsysteme be started at the same time, but it is also possible that some of the These sub-process systems can 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ßsystems. 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 system. 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 des Prozeßsystems" versteht man die Gesamt heit 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 bestimm ten Zeitpunkt t während der Laufzeit des Prozeßsystems, die die Gesamtheit der Kenntnisse widerspiegelt, die zu diesem Zeitpunkt t über das Prozeßsystem verfügbar sind.The "external representation of the process system" means the total knowledge of the process system that is available at design time. The on the other hand stands the "internal representation of the process system" to a certain th time t during the running time of the process system, which is the total of Knowledge that is available at this time t through the process system are.
Die Zuordnung der einzelnen Prozesse des Prozeßsystems zu den einzelnen Rechner 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.
- - Die Entscheidungen, welcher Rechner welche Prozesse bearbeitet.- The decisions which computer processes which processes.
- - Die Reihenfolge, in der ein Rechner die ihm zugeteilten Prozesse bearbeitet.- 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 vorgebenen Rechnernetz minimiert wird. Dabei ist zu beachten, das die Precedencregeln 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 Precedenceregeln 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 do not get injured. 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. Furthermore 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) getätigt werden. Wenn die Zuordnung während der Lauf zeit vorgenommen wird, kann sie durch eine zentrale Institution oder durch ein ver teiltes Verfahren getätigt 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. Dagegen spricht man von einer "verteilten" Zuordnung, wenn mehrere (mindestens zwei) Rechner Zuordnungsaufgaben übernehmen.The assignment can take place at runtime of the process system or before the start of the process system (at design time). If the assignment during the run time, it can be done by a central institution or by a ver shared procedure. A "central institution" means 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. In contrast, one speaks of a "distributed" assignment if take over several (at least two) computer assignment tasks.
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 will.
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" 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 is required between the individual computers. 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". "Essentially the same information" 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 only as estimates before starting the process system 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ßsystems (z. B. die Anzahl der Prozesse und die Precedenceregeln) 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 Prozeßsystem erst während der Laufzeit endgültig festzulegen. Das hat den Vorteil, daß die Entwicklungen, die sich während der Laufzeit ergeben, best mö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) 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 depends on the data. 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 to finalize the process system only during runtime. The has the advantage that the developments that occur during the term are best can be reflected in the structure of the process system.
Der Erfindung liegt folgende Aufgabe zugrunde. Ausgehend von einer "externen" Repräsentation der Information über das Prozeßsy stem soll eine Zuordnung der Prozesse des Prozeßsystems zu den Rechnern des Rechnernetzes hergestellt werden, so daß die Ausführungszeit des Prozeßsystems minimiert wird.The invention is based on the following object. Starting from an "external" representation of the information about the process sy system should assign the processes of the process system to the computers of the Computer network are produced so that the execution time of the process system is minimized.
Die verfahrensspezifischen Aufgaben werden durch den kennzeichnenden Teil des Anspruchs 1 und den kennzeichnenden Teil des Anspruchs 4 gelöst. Weiterhin ist vorgesehen, daßThe process-specific tasks are defined by the characterizing part of the Claim 1 and the characterizing part of claim 4 solved. It is also provided that
- - die Precedenceregeln, die das Prozeßsystem charakterisieren- The precedence rules that characterize the process system
- - während der Laufzeit des Prozeßsystems,- during the running time of the process system,
- - präzisiert oder- specified or
- - modifiziert oder- modified or
- - festgelegt oder- fixed or
- - in sonstiger Weise beeinflußt werden.- are influenced in any other way.
Eine vorteilhafte Ausgestaltung des Verfahrens ist dadurch gegeben, daß keine glo balen Rundschreiben übertragen werden, wenn Prozesse gestartet werden. Eine weitere vorteilhafte Ausgestaltung des Verfahrens ist dadurch gegeben, daß die Zuordnung nicht durch eine zentrale Institution vorgenommen wird.An advantageous embodiment of the method is given by the fact that no glo bale circulars are transmitted when processes are started. 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 Datenflußgraphen. Fig. 4 An example of a classic data flow 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) Aus der externen Repräsentation des Prozeßsystems wird eine initiale interne Repräsentation hergestellt.1) The external representation of the process system becomes an initial internal one Representation made.
- 2) Aus der internen Repräsentation wird eine Zuordnung hergestellt.2) An assignment is made from the internal representation.
Bei der externen Repräsentation (genannt: "Datenflußgraph") handelt es sich um ge richtete, 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 Daten 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 Datenflußgraphen (z. B. "d1") vorange stellt und durch einen Punkt abgetrennt werden. Unter "space sharing" versteht man eine Technik, bei der mehrere Prozeßsysteme die einzelnen Rechner eines Rechner netzes untereinander aufteilen.The external representation (called: "data flow graph") is ge directed, 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 data as Result generated. An arrow in the opposite direction indicates that the process P the Data D is required as input data. It also has 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 of loops or branches have node names except the dynamic components, which are denoted by a ′ ′ character and the name of the Loop or branch are shown. To model "space sharing" can precede the node name with the name of the data flow graph (e.g. "d1") places and separated by a point. "Space sharing" means a technique in which multiple process systems are the individual computers of a computer divide the network among each other.
Eine Verzweigung besteht (neben ihrem Namen) aus einem Verzweigungsknoten, einem Sammelknoten und einem Datenfluß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 data flow 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 substituted by the values 1..n. In the example shown, the data nodes d1.d.1, d1.d.2, .., d1.dn are created
Schleifen besitzen neben ihrem Namen nur einen Rumpf, der ebenfalls aus einem Datenfluß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 have only one body, which also consists of a data flow 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 (in the example "schl") 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 Länge 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 konkrete Realisierung des Prozeßsy stems in Fig. 3 wieder.The representation in Fig. 4 shows a possible concrete implementation of the Prozesssy stems in Fig. 3 again.
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 nodes 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. She usually 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 entsprec hend 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.
Eine andere Möglichkeit zur Realisierung der externen Repräsentation ist die Ver wendung klassischer Datenflußgraphen wie in Fig. 4 dargestellt. Das sind bekanntlich bipartite Graphen mit Prozeß- und Datenknoten. Bei klassischen Datenflußgraphen besteht keine Möglichkeit, während der Laufzeit die Struktur des Prozeßsystems (z. B. die Precedenceregeln) zu verändern, deswegen stimmt die interne Repräsenta tion bei klassischen Datenflußgraphen zu jedem Zeitpunkt mit der externen Reprä sentation überein.Another possibility for realizing the external representation is the use of classic data flow graphs as shown in FIG. 4. As is well known, these are bipartite graphs with process and data nodes. With classic data flow graphs, there is no possibility to change the structure of the process system (e.g. the precedence rules) during runtime, which is why the internal representation in classic data flow graphs matches the external representation at all times.
Zur Herstellung der gewünschten Zuordnung aus der internen Repräsentation kann beispielsweise folgendes Verfahren verwendet werden.To create the desired assignment from the internal representation For example, the following method can 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 "hauptberuflich" oder "nebenberuflich" ausgeübt werden; d. h., unter Umständen können die der Menge SR zugehörigen Steuerrech ner außer ihrer Zuordnungsaufgabe noch Produktionsprozesse bearbeiten (nebenbe ruflicher Fall) oder aber sich ausschließlich ihrer Zuordnungsaufgabe widmen (hauptberuflicher 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 tax can be exercised "full time" or "part time" by the tax calculators will; d. that is, under certain circumstances the tax calculations belonging to the quantity SR In addition to their assignment task, they also process production processes (incidentally, professional case) or devote themselves exclusively to their assignment task (full-time 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 Job-Bezirke bzw. Wor ker-Bezirke genannt.Computer quantities are assigned to each control computer, the respective partial quantities are the computer of the computer network. These quantities become job areas or wor called ker districts.
Die Job-Bezirke stellen eine Partition auf der Menge der Rechner des Rechnernet zes dar; d. h., jeder Rechner gehört zu genau einem Job-Bezirk. Dagegen dürfen sich die Worker-Bezirke auch überschneiden. D.h. jeder Rechner gehört zu mindestens einem Worker-Bezirk. Die Steuerrechner selbst genießen unter Umständen eine Ausnahmestellung, denn wenn die Zuordnungsaufgabe hauptberuflich ausgeübt wird, gehören die Steuerrechner zu keinem Worker-Bezirk. Eine Alternative wäre, daß auch die Worker-Bezirke eine Partition darstellen, also jeder Rechner zu genau ei nem Worker-Bezirk gehört.The job districts place a partition on the set of computers on the computer network zes represents; d. that is, each computer belongs to exactly one job district. Against that the worker districts also overlap. I.e. every computer belongs to at least a worker district. The control computers themselves may enjoy one Exceptional position, because if the assignment task is performed full-time, the control computers do not belong to any worker district. An alternative would be that the worker districts also represent a partition, i.e. each computer has exactly one egg belongs to a worker district.
Die Intention der beschriebenen Rechnermengen ist, daß ein Rechner, der Prozesse erzeugt hat, die noch zugeordnet werden müssen, diese Prozesse an den Steuerrech ner meldet, dessen Job-Bezirk er angehört. Umgekehrt vergibt ein Steuerrechner Prozesse, die ihm gemeldet werden innerhalb seines Worker-Bezirks.The intention of the computer sets described is that one computer, the processes generated, which still have to be assigned, these processes to the tax office ner reports whose job district he belongs to. Conversely, a tax calculator awards Processes reported to him within his worker's district.
Im einzelnen wird die Zuordnung wird dann auf folgende Weise hergestellt.The assignment is then made in the following manner.
- 1) Der Rechner SR 1 ermittelt aufgrund der internen Repräsentation des Prozeßsy stems den oder die Prozesse, die von keinem anderen Prozeß Daten benötigen (den sog. "Inputprozessen").1) The computer SR 1 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) Jeder Steuerrechner pflegt eine Liste von bislang unbearbeiteten Prozessen in seinem Verantwortungsbereich. Die Liste wird "Jobliste" genannt. 2) Each control computer maintains a list of previously unprocessed processes in his area of responsibility. The list is called the "job list".
- 3) Der Steuerrechner SR1 initialisiert seine Jobliste mit den Imputprozessen.3) The control computer SR1 initializes its job list with the input processes.
- 4) Alle anderen Steuerrechner initialisieren ihre Jobliste mit der leeren Menge.4) All other control computers initialize their job list with the empty set.
- 5) Jeder Steuerrechner pflegt eine Liste von Rechners, die im Augenblick keinen Prozeß bearbeiten (genannt: "Idle-liste"). Die Idle-listen werden mit dem gesamten Worker-Bezirk initialisiert.5) Each tax calculator maintains a list of calculators that currently do not Process the process (called: "idle list"). The idle lists are with the whole Worker district initialized.
- 5) Die Schritte (6) bis (12) werden wiederholt bis das Prozeßsystem bearbeitet ist, d. h. bis der letzte Prozeß fertig ist.5) Steps (6) to (12) are repeated until the process system is processed, d. H. until the last process is done.
- 6) Jeder Steuerrechner prüft seine Jobliste. Wenn die Liste Prozesse enthält, wer den diese Prozesse an Rechner vergeben, die in der Idle-liste eingetragen sind. Da bei sind folgende Punkte zu beachten.6) Each control computer checks its job list. If the list contains processes, who which these processes assign to computers that are entered in the idle list. There The following points should be noted at
- - Viele Prozesse benötigen Daten, die andere Prozesse erzeugt haben. Wenn bei spielsweise ein Prozeß P auf einem Rechner R gestartet werden soll, müssen die vom Prozeß P benötigten Daten zum Rechner R transferiert werden. Dabei entste hen Übertragungskosten. Das zuständige Steuerrechner ist deswegen bestrebt, den Prozeß P auf einem Rechner zu starten, so daß die Übertragungskosten möglichst gering bleiben. Dazu pflegt der Steuerrechner Listen, in denen eingetragen ist, wel che Prozesse auf welchen Rechnern beendet wurden und welche Daten auf welchen Rechnern residieren. Außerdem notiert sich jeder Steuerrechner, in welchem Zu stand (wartend, laufend, fertig) die einzelnen Prozesse des Prozeßsystems sind. Um diese Listen zu aktualisieren, pflegen die Steuerrechner untereinander ein System von Rundschreiben, das jedesmal aktiviert wird, wenn Prozesse gestartet oder been det werden oder wenn Daten transferiert werden.- 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 tax calculator 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.
- - Wenn sich die Worker-Bezirke überschneiden, muß dafür Sorge getragen werden, daß nicht mehrere Steuerrechner einem Rechner gleichzeitig Aufgaben übertragen. Dazu eignet sich beispielsweise folgendes Protokoll.- If the worker districts overlap, care must be taken that not several control computers transfer tasks to one computer at the same time. The following protocol is suitable for this, for example.
Der Steuerrechner sendet dem potentiellen Worker eine "Biete Job" Nachricht.The control computer sends the potential worker a "bid job" message.
Wenn der Worker bereits anderweitig Aufgaben angenommen hat, antwortet er mit "Akzeptiere Job NICHT".If the worker has already accepted tasks elsewhere, he replies with "DO NOT accept job".
Wenn der Worker aber tatsächlich arbeitslos ist, antwortet er mit "Akzeptiere Job". Auf evtl. weitere "Biete Job" Nachrichten von anderer Seite, die später eintreffen, antwortet der Worker ab jetzt bis zum Abschluß des Dialogs mit "Akzeptiere Job NICHT".If the worker is actually unemployed, he answers with "accept job". For any other "job offer" messages from other parties that arrive later, the worker replies from now until the dialog is closed with "Accept job NOT".
Wenn der Steuerrechner eine "Akzeptiere Job" Nachricht erhält, vergibt es die Auf gabe an den Worker. Bei einer "Akzeptiere Job NICHT" Nachricht müssen weitere "Biete Job" Nachrichten versendet werden.When the control computer receives an "accept job" message, it issues the open handover to the worker. In the case of a "DO NOT accept job" message, more must be done "Offer job" messages are sent.
(Ende des Protokolls und Ende Schritt (6).(End of protocol and end of step (6).
- 7) Wenn der Steuerrechner einen Prozeß P an einen Rechner R vergeben will, prüft der Steuerrechner anhand der internen Repräsentation des Prozeßsystems nach, wel che Daten D für die Ausführung des Prozesses P erforderlich sind. Aufgrund seiner internen Aufzeichnungen weiß der Steuerrechner, wo die Daten D residieren. Der Steuerrechner veranlaßt die Übertragung der Daten D an den Rechner R.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. The Control computer causes data D to be transferred to computer R.
- 8) Wenn ein Rechner R von einem Steuerrechner (z. B. "SR_Start" genannt) einen Prozeß P zur Bearbeitung erhalten hat, wartet er auf die benötigten Daten. Sobald er über die Daten verfügen kann, startet er den Prozeß P.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.
- Nach einiger Arbeitszeit ist der Prozeß P dann beendet. Dieses Ereignis vermeldet der Rechner R an den Steuerrechner, dessen Job-Bezirk der Rechner R zugeteilt ist. Im Beispiel hätte dieser Steuerrechner vielleicht den Namen "SR_X". Process P is then ended after a few working hours. Reported this event the computer R to the control computer, the job area of which the computer R is assigned. In the example, this control computer might have the name "SR_X".
- 9) Der Steuerrechner SR_X publiziert das Ende des Prozesses P (ebenso wie SR_Start vorher den Start publiziert hat) via dem Rundschreibenmechanismus Kreise der Steuerrechner; d. h., an die anderen Rechner der Menge SR.9) The control computer SR_X publishes the end of process P (as well SR_Start previously published the start) via the circular mechanism Circles of control computers; d. that is, to the other computers in the set SR.
- 10) Durch das Ende des Prozesses P werden in vielen Fällen neue Daten (genannt: "D_neu") verfügbar. Unter Umständen können deshalb jetzt weitere Prozesse (ge nannt: "P_neu") gestartet werden. Der Steuerrechner nimmt die Prozesse aus P neu in seine JobListe auf, wenn folgende Bedingungen gelten.10) At the end of process P, new data (called: "D_neu") available. Under certain circumstances, additional processes (ge called: "P_neu") can be started. The control computer takes the processes out of P. in his job list if the following conditions apply.
- - Die Prozesse benötigen Daten aus D_neu und- The processes require data from D_neu and
- - Alle Daten, die die Prozesse benötigen sind bereits erzeugt.- All data that the processes need has already been created.
-
11) Aufgrund von Übertragungszeiten für die Rundschreiben, kann es zu Konflikten
kommen. Mögliche Konflikte können sein, daß sich für den Start eines bestimmten
Prozesses P kein einziger Steuerrechner verantwortlich fühlt, oder daß umgekehrt
mehrere Steuerrechner ein und denselben Prozeß an verschiedenen Stellen starten.
Gegen diese Konflikte müssen Vorkehrungen getroffen werden. Eine Möglichkeit
dafür ist, daß immer der Steuerrechner den Prozeß P startet, in dessen Job-Bezirk
der letzte Vorgänger von P beendet wird. Sollten trotzdem mehrere Steuerrechner
jeweils eine "Inkarnation" des Prozesses P starten, wird diese Problematik über den
Rundschreibenmechanismus über kurz oder lang aufgedeckt. Dann muß willkürlich
eine Inkarnation ausgewählt werden, die weiterarbeitet, und alle anderen Inkarnatio
nen werden abgebrochen. Eine solche willkürliche Auswahl könnte beispielsweise
sein, daß der Prozeß auf dem Rechner mit der größten Seriennummer weiterarbei
ten darf.
Der Steuerrechner SR_X teilt deswegen den anderen Steuerrechnern mit, daß es die Prozesse P neu in seine Jobliste aufgenommen hat. Wenn ein anderer Steuerrechner (z. B. "SR_Y") einen Prozeß P aus der Menge P neu bereits in seine Jobliste aufge nommen hat, erhebt es beim Steuerrechner SR_X einen Einspruch. Es wird eine willkürliche (aber eindeutige) Vereinbarung getroffen, welcher Steuerrechner den Prozeß dann aus seiner Jobliste streichen muß (z. B. der Steuerrechner, der die klei nere Seriennummer hat). Um einen evtl. Einspruch eines anderen Steuerrechners abzuwarten, muß sowohl der Steuerrechner SR_X als auch der Steuerrechner SR_Y vor dem Start der Prozesse in P_neu eine Karenzzeit einhalten. Die Karenzzeit kann man durch die maximalen Übertragungszeiten im Rechnernetz und einer Sicher heitsreserve abschätzen.
Um Probleme zu vermeiden, die entstehen, wenn sich kein Steuerrechner für einen Prozeß zuständig fühlt, ist es vorteilhaft, wenn ein Steuerrechner einen Prozeß aus P_neu im Zweifelsfall zunächst in seine Jobliste aufnimmt.11) Due to transmission times for the circulars, conflicts can arise. Possible conflicts can be that no single control computer feels responsible for the start of a particular process P, or conversely several control computers start one and the same process at different points. Precautions must be taken against these conflicts. One possibility for this is that the control computer always starts the process P, in whose job area the last predecessor of P is ended. Should several control computers nevertheless start an "incarnation" of process P, this problem will sooner or later be uncovered via the circular mechanism. Then an incarnation that continues to work must be selected at random and all other incarnations are terminated. Such an arbitrary selection could be, for example, that the process may continue to work on the computer with the largest serial number.
The control computer SR_X therefore informs the other control computers that it has added processes P to its job list. If another control computer (eg "SR_Y") has already added a process P from the set P to its job list, it raises an objection to the control computer SR_X. An arbitrary (but clear) agreement is reached as to which control computer must then delete the process from its job list (e.g. the control computer that has the smaller serial number). To wait for a possible objection from another control computer, both the control computer SR_X and the control computer SR_Y must observe a waiting period in P_neu before starting the processes. The waiting period can be estimated by the maximum transmission times in the computer network and a security reserve.
To avoid problems that arise when no control computer feels responsible for a process, it is advantageous if a control computer first includes a process from P_neu in its job list. - 12) Wenn ein Steuerrechner überdurchschnittlich belastet ist, kann er Aufgaben an andere Bezirke delegieren.12) If a tax calculator is loaded above average, it can perform tasks delegate other districts.
Ein Beispiel für ein solches Lastausgleichsverfahren könnte wie folgt aussehen. Jeder Steuerrechner habe beispielsweise maximal "MaxAnzNachbar" viele benachbarte Steuerrechner. In periodischem Abstand tauschen die benachbarten Steuerrechner Informationen über ihre Auslastung aus, die durch die Anzahl der startbereiten Pro zesse (d. h. die Elemente der Jobliste) charakterisiert ist. Aufgrund dieser Daten be rechnet jeder Steuerrechner die mittlere Auslastung (genannt: "MittelLast") in sei ner Nachbarschaft. Wenn die eigene Auslastung (genannt: "EigeneLast") signifikant über der mittleren Auslastung liegt und die ("NachbLast" genannte) Auslastung eines Nachbars (z. B. "Nachb" genannt) signifikant unter MittelLast liegt, werden einige Prozesse transferiert. Durch skalare Parameter (Schwellwerte) läßt sich festlegen, was "signifikant" inhaltlich bedeutet. An example of such a load balancing process could look as follows. Everyone For example, control computers 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 job list). Based on this data be each control computer calculates the average load (called: "medium load") in a neighborhood. If your own workload (called: "OwnLast") is significant is above the average utilization and the utilization (called "NachbLast") of a Neighbors (e.g. called "Nachb") is significantly below MediumLoad, some Processes transferred. Scalar parameters (threshold values) can be used to determine which means "significant" in terms of content.
Beispielsweise könnte man festlegen, daß maximal x Prozesse transferiert werden. x: = MIN ((EigeneLast- MittelLast) / (2*MaxAnzNachbar), (MittelLast - NachbLast ) / (2*MaxAnzNachbar)).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)).
Eine andere Alternative für ein Lastausgleichsverfahren wäre ein Anbietungsproto koll, bei dem ein Steuerrechner, der sich überlastet fühlt, den Nachbarn Aufgaben anbietet. Ein Beispiel eines solchen Protokolls wäre wie folgt gegeben.Another alternative for a load balancing process would be a bid 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.
Überlasteter Steuerrechner sendet "Biete Job"Overloaded control computer sends "bid job"
Nachbar entscheidet, ob er noch zusätzliche Prozesse verkraften kann und antwortet entsprechend mit "Akzeptiere Job" oder "Akzeptiere Job NICHT".Neighbor decides whether he can handle additional processes and answers accordingly with "accept job" or "do not accept job".
Überlasteter Steuerrechner delegiert gegebenenfalls Prozeß an NachbarOverloaded control computer may delegate process to neighbor
Besondere Beachtung erfordert, daß das Lastausgleichsverfahren "stabil" arbeitet. Das Verfahren darf beispielsweise nicht zum Schwingen neigen; d. h., es darf nicht (oszillierend) Prozesse zwischen verschiedenen Steuerrechnern hin- und herverla gern, ohne dem eigentlichen Ziel (der gleichmäßigen Belastung) wesentlich näher zu kommen.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) processes between different control computers back and forth gladly, without much closer to the actual goal (the constant load) come.
(Ende Schritt (12) und Ende der Beschreibung des Verfahrens in Einzelschritten)(End of step ( 12 ) and end of the description of the method in individual steps)
Weitere Ausgestaltungsmöglichkeiten.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 : = Const 1* 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, MittelAB und MittelAN bezeichnen die mittlere Distanz innerhalb eines Job-Bezirks, bzw. Worker-Bezirks. Die Parameter des Verfahrens sind Const1, Const2, Const3 und die Anzahl der Steuerrechner. Diese Parameter können intuitiv gewählt werden (beispielsweise: Const1 = Const2 = Const3 = 1) oder, nachdem die anderen Komponenten des Verfahrens bereits festgelegt sind, auch trainiert wer den. Unter einem "Training" versteht man ein Optimierungsverfahren, das auf einem Satz typischer Anwendungsbeispiele (hier: Prozeßsysteme) beruht, der "Trainings menge" genannt wird. Ausgehend von einer weitgehend beliebigen initialen Bele gung der Parameter (hier: Const1, Const2, Const3), wird ein iteratives Optimierungs verfahren angewandt. Bekannte Beispiele solcher Optimierungsverfahren sind "Gra dientenabstieg" 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.Objective function: = Const 1 * MittelSR + Const2 * MittelAG + Const3 * MittelAN; In this form, Const1, Const2 and Const3 stand for any but selected real weight factors. MittelSR stands for the mean distance between Control computers, MittelAB and MittelAN indicate the average distance within of a job district or worker district. The parameters of the procedure are Const1, Const2, Const3 and the number of control computers. These parameters can be intuitive can be selected (for example: Const1 = Const2 = Const3 = 1) or after the other components of the procedure are already defined, including those who are trained the. A "training" is an optimization process based on a The set of typical application examples (here: process systems) is based on the "training quantity "is called. Starting from a largely arbitrary initial Bele parameters (here: Const1, Const2, Const3), an iterative optimization procedure applied. Known examples of such optimization methods are "Gra descent "and" coordinate descent " of the training volume continuously checked that the target function (here the runtime of the process systems) are 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 Job-Bezirke und die Worker-Bezirke so, daß der Kommunikationsaufwand insgesamt minimiert wird". Für die Lösung derartiger Probleme kennt man eine Reihe von Verfahren wie "Branch & Bound" sowie "Integerprogrammierung".Another possibility would be the exact or approximate solution of the Optimie problem: "Choose the amount of control computers SR, the job areas and the Worker districts so that the overall communication effort is minimized ". A number of methods are known for solving such problems, such as "Branch & Bound" and "Integer programming".
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. With regular, mesh-like connection networks, one could, for example, divide the entire computer network into X * Y rectangular fields and transfer 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 (nebenberuflicher) Steuerrechner ist. Der Job-Bezirk wäre dann nur der einzelne Rechner, und der Worker-Bezirk wäre das gesamte Rechnernetz. In diesem Fall geht geht das beschriebene Verfahren in ein vollständig verteiltes Verfahren über. Ein solches Verfahren hat aber den Nachteil, daß globale Rundschreiben nötig sind, die bekanntlich bei größeren Rechnernetzen nur sehr aufwendig realisiert wer den können. Deswegen eignet sich das vollständig verteilte Verfahren hauptsächlich für kleinere Rechnernetze.An interesting borderline case of the described method is that every computer is his own (part-time) tax calculator. The job district would then only be that individual computers, and the worker district would be the entire computer network. In this If the process goes, it goes into a completely distributed process about. However, such a procedure has the disadvantage that global circulars are necessary are, which, as is well known, only very costly to implement in larger computer networks that can. Therefore, the fully distributed method is mainly suitable for smaller computer networks.
Ein anderer Grenzfall des Verfahrens ist ein zentrales Verfahren. In diesem Fall gibt es nur einen einzigen Steuerrechner. Der Job-Bezirk und der Worker-Bezirk stim men mit dem gesamten Rechnernetz überein. Das Lastausgleichsverfahren 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 job district and the worker district stim with the entire computer network. The load balancing process between the control computers will then of course become superfluous.
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, as is well known, 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 gemäß 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 stems, which must meet strict real-time requirements, already assigned 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 provided by the control computers in a command procedure 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 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 during design 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, as soon as the failure 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 reasons 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 process, 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. D.h. 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 lagurungskosten 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. I.e. no relocation of ongoing processes. But also these provisional ones The restriction can be overcome easily. 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 significantly 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 provides 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. Einer Menge von Rechnern (den Steuerrechnern).1. A set of computers (the control computers).
- 2. Den zugehörigen Job-Bezirken.2. The associated job areas.
- 3. Den zugehörigen Worker-Bezirken.3. The associated worker districts.
- 4. Booleanwertigen Variablen "nebenberuflich".4. Boolean variables "part time".
- 5. Dem Lastausgleichsverfahren zwischen den Steuerrechnern.5. The load balancing process between the control computers.
- 6. Dem Protokoll zur Vergabe von Aufgaben.6. The protocol for assigning tasks.
- 7. Dem Protokoll zur Mitteilung unbearbeiteter Aufgaben.7. The protocol for the notification of unprocessed tasks.
- 8. Den maximalen Anzahlen von Produktionsprozessen auf einer Maschine.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.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.
Die Rechner (1, 2, 3, 4) sowie (5, 6, 7, 8) stellen in Fig. 5 die Job-Bezirke dar, die mit den Worker-Bezirken übereinstimmen. Die hauptberufliche Funktion des Steu errechners übernehmen die Rechner 3 und 5.The computers ( 1 , 2 , 3 , 4 ) and ( 5 , 6 , 7 , 8 ) represent the job areas in FIG. 5 which correspond to the worker areas. The full-time function of the tax calculator is performed by computers 3 and 5 .
- 1) SR1 ermittelt den Inputprozeß t1.1) SR1 determines the input process t1.
- 2) Im Augenblick sind alle drei Worker des Bezirks von SR1 arbeitslos.2) All three workers in the SR1 district are currently unemployed.
- 3) SR1 startet den Prozeß t1 auf dem nächstgelegenen Rechner (= CPU1).3) SR1 starts the process t1 on the closest computer (= CPU1).
- 4) SR1 aktualisiert sein lokales Wissen.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) CPU 1 erkennt, daß keine Daten benötigt werden und startet t 1.5) CPU 1 recognizes that no data is required and starts t 1.
- 6) CPU 1 wird mit t1 fertig; t 1 entscheidet, daß t 1 fünf Nachfolger haben wird.6) CPU 1 copes with t1; t 1 decides that t 1 will have five successors.
- 7) t 1 auf CPU 1 konkretisiert die interne Repräsentation des Prozeßsystems. 7) t 1 on CPU 1 concretizes the internal representation of the process system.
- 8) t1 erzeugt die Datenknoten d.0.0, d.0.1,...d.0.4 und sie im Speicher von CPU1 ab.8) t1 creates the data nodes d.0.0, d.0.1, ... d.0.4 and saves them in the memory of CPU1.
- 9) t 1 meldet an SR 1, daß t 1 jetzt fertig ist.9) t 1 reports to SR 1 that t 1 is now ready.
- 10) Aus der Fertigmeldung von t1 ersieht der SR1, daß die Daten d.0.0 .. d.0.4 erzeugt sind und im Speicher von CPU 1 stehen.10) From the completion report of t1, the SR1 sees that the data d.0.0 .. d.0.4 are generated and are in the memory of CPU 1.
- 11) Der Steuerrechner SR1 soll jetzt die Nachfolgeprozesse von t1 starten.11) The control computer SR1 should now start the successor processes of t1.
- 12) Die Nachfolger von t1 sind t.0.0.. t.0.4.12) The successors of t1 are t.0.0 .. t.0.4.
- 13) SR1 muß nachprüfen, welche der Prozesse t.0.0 .. t.0.4 jetzt gestartet werden können. t.0.0 hat als Vorgänger nur d.0.0, der bereits erzeugt ist. Analoges gilt für die anderen Knoten. Alle fünf Prozesse können somit gestartet werden.13) SR1 must check which of the processes t.0.0 .. t.0.4 are now 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) SR 1 hat in seinem Bezirk drei freie Rechner, die jeweils einen Prozeß erhalten. SR1 startet die t.0.0, t.0.1 und t.0.2 auf CPU1, CPU2 bzw. CPU4 und stößt die Über tragung der benötigten Daten an.14) SR 1 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 überträgt die Daten und löscht sie im eigenen Speicher.15) CPU1 transfers the data and deletes it in its own memory.
- 16) CPU2 und CPU4 erhalten die Daten und können die Prozesse t.0.1 und t.0.2 somit starten. Die Zuordnung der ersten drei Prozesse ist damit beendet.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) Bislang wurde das Lastausgleichsverfahren zwischen den Steuerrechnern aus
Gründen der Übersichtlichkeit völlig ignoriert.
Nun tauschen die Steuerrechner SR 1 und SR2 ihren Auslastungsgrad aus. SR 1 hat zwei startbereite Prozesse und SR2 überhaupt keinen.
SR 1 wendet folgende Formel an.
AnzVerlagerteProzesse = (Last(SR1)-Last(SR2))/(AnzNachbarn*2) = (20)/(1*2) = 1.
Nach dieser Formel wäre also ein Prozeß von SR 1 an SR2 zu übertragen.17) So far, the load balancing procedure between the control computers has been completely ignored for reasons of clarity.
The control computers SR 1 and SR2 now exchange their degree of utilization. SR 1 has two ready-to-start processes and SR2 has none at all.
SR 1 applies the following formula.
Number of displaced processes = (Last (SR1) -Last (SR2)) / (No. of neighbors * 2) = (20) / (1 * 2) = 1.
According to this formula, a process would be transferred from SR 1 to SR2. - 18) SR1 entscheidet sich, t.0.3 zu verlagern.18) SR1 decides to relocate t.0.3.
- 19) SR 1 sendet an SR2 folgende Information: "Ich übertrage dir die Ausführung des Prozesses t.0.3. Wie du weißt, benötigt dieser Prozeß die Daten d.0.3. Sie stehen im Speicher von CPU1."19) SR 1 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 erhält diese Nachricht und startet den Prozeß t.0.3 auf CPU7 stößt die Übertragung der Daten an.20) SR2 receives this message and starts the process t.0.3. CPU7 encounters the Transfer the data to.
- 21) Ein Zyklus des Lastausgleichs ist damit beendet.21) This completes a cycle of load balancing.
- 22) Schließlich geht CPU 1 daran, den Prozeß t.0.0 zu beenden.22) Finally, CPU 1 goes to end process t.0.0.
- 23) t.0.0 entscheidet, daß die Schleife "schl" noch nicht verlassen werden kann und erzeugt die Daten d.1.0 im Speicher von CPU1.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 bittet die interne Repräsentation des Prozeßsystems folgende Tatsache per manent zu machen: "t.0.0 hat sich entschieden, daß die Schleife noch nicht verlassen wird".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 teilt SR1 mit, daß er fertig ist.25) t.0.0 notifies SR1 that it is finished.
- 26) Im Gegenzug startet SR1 den letzten verbleibenden Nachfolger t.0.4 auf CPU1.26) In return, SR1 starts the last remaining successor t.0.4 on CPU1.
-
27) Nach einiger Zeit beendet auch t.0.2 auf CPU4 die Arbeit.
Im Unterschied zu t.0.0 entscheidet er aber, daß sein Zweig die Schleife verläßt.27) After some time, t.0.2 on CPU4 also ends.
In contrast to t.0.0, it decides that its branch leaves the loop. - 28) t.0.2 teilt SR1 mit, daß er fertig ist.28) t.0.2 notifies SR1 that it is finished.
- 29) SR1 startet t.1.0 auf CPU4.29) SR1 starts t.1.0 on CPU4.
- 30) Nach einiger Zeit werden sämtliche fünf d2.vrzw erzeugt sein.30) After a while all five d2.vrzw will be created.
- 31) Der Rechner SR1 weiß, daß t2 fünf Vorgänger hat, die nun erzeugt sind. Des wegen kann t2 nun gestartet werden.31) The computer SR1 knows that t2 has five predecessors that are now generated. Des because of this, t2 can now be started.
Anordnungsspezifischer Teil der Erfindung.
Die Erfindung kann beispielsweise durch ein Netzwerk von Computern realisiert
werden. Ein Beispiel ist in Fig. 6 gegeben. Die Funktion des Steuerrechners wird
hauptberuflich übernommen (im Beispiel in Fig. 6 durch die Rechner 13 und 14).
Sämtliche Rechner, die eine Zuordnungsaufgabe wahrnehmen, sind durch einen Bus
miteinander verbunden (in Fig. 6 "Bus 2" genannt). Dadurch läßt sich der Rund
schreibmechanismus sehr effizient realisieren, denn der sendende Steuerrechner er
reicht mit einem einzigen Zugriff auf den Bus alle Empfänger.Arrangement-specific part of the invention.
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 full-time (in the example in FIG. 6 by computers 13 and 14 ). All computers which perform an assignment task are connected to one another by a bus (called "bus 2 " in FIG. 6). This enables the circular writing 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 SPEIC dual-port memory. 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 Job-Bezirke stimmen mit den Worker-Bezirken überein. Im Beispiel in Fig. 6 sind das die Rechner (1, 2, 3, 4, 5, 6), (7, 8, 9, 10, 11, 12). Die Rechner der Job-Be zirke können untereinander durch ein Verbindungsnetzwerk kommunizieren. Im Beispiel in Fig. 6 ist dieses Netzwerk durch einen doppelt vermaschten Ring reali siert. Diese Struktur wird allgemein der Klasse der Netzwerke auf der Basis lokaler Nachbarschaften zugerechnet. Solche Verbindungsnetzwerke sind wegen ihrer Lei stungsfähigkeit, ihren einfachen Realisierungsmöglichkeiten und ihrer Fehlertoleran zeigenschaften sehr geschätzt.The job areas are the same as the worker areas. In the example in FIG. 6, these are the computers ( 1 , 2 , 3 , 4 , 5 , 6 ), ( 7 , 8 , 9 , 10 , 11 , 12 ). The computers in the job areas can communicate with each other via a connection network. In the example in Fig. 6, this network is realized by a double mesh ring. This structure is generally assigned to the class of networks based on local neighborhoods. Such connection networks are highly valued for their performance, their simple implementation options and their fault tolerance properties.
Zwischen sämtlichen Rechnern eines Job-Bezirks und dem zugehörigen Steuerrech ner besteht eine direkte Verbindung. Damit kann der wichtige Kontakt eines Steuer rechner zu seinem Bezirk auf effiziente Weise hergestellt werden. Durch einen wei teren Bus (in Fig. 6 als "Bus 1" bezeichnet) ist eine Kommunikationsmöglichkeit zwi schen Rechnern verschiedener Bezirke hergestellt. Auf diesen Bus können alle Rechner außer den Arbeitämtern zugreifen.There is a direct connection between all the computers in a job district and the associated tax computer. This enables the important contact between a tax calculator and its district to be established efficiently. Through a further bus (referred to in FIG. 6 as "Bus 1 "), a communication option between computers of different districts is established. All computers except the employment offices can access this bus.
Claims (10)
- - präzisiert oder
- - modifiziert oder
- - festgelegt oder
- - in sonstiger Weise beeinflußt werden.
- - specified or
- - modified or
- - fixed or
- - are influenced in any other way.
- - präzisiert oder
- - modifiziert oder
- - festgelegt oder
- - in sonstiger Weise beeinflußt werden.
- - specified or
- - modified or
- - fixed or
- - are influenced in any other way.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| DE19914132764 DE4132764C2 (en) | 1991-10-02 | 1991-10-02 | Method and arrangement for assigning processes in a process system to the individual computers in a computer network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| DE19914132764 DE4132764C2 (en) | 1991-10-02 | 1991-10-02 | Method and arrangement for assigning processes in a process system to the individual computers in a computer network |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| DE4132764A1 true DE4132764A1 (en) | 1993-04-15 |
| DE4132764C2 DE4132764C2 (en) | 1995-01-05 |
Family
ID=6441958
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| DE19914132764 Expired - Fee Related DE4132764C2 (en) | 1991-10-02 | 1991-10-02 | Method and arrangement for assigning processes in a process system to the individual computers in a computer network |
Country Status (1)
| Country | Link |
|---|---|
| DE (1) | DE4132764C2 (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE4330479A1 (en) * | 1993-09-09 | 1994-02-10 | Johann Rost | Distribution of functions to computers of network system - having number of computers designated as control units that can exchange functions and can assign functions |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE3741953A1 (en) * | 1986-12-19 | 1988-06-30 | Nippon Telegraph & Telephone | MULTIPROCESSOR SYSTEM AND METHOD FOR DISTRIBUTING WORK LOAD IN SUCH A |
-
1991
- 1991-10-02 DE DE19914132764 patent/DE4132764C2/en not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE3741953A1 (en) * | 1986-12-19 | 1988-06-30 | Nippon Telegraph & Telephone | MULTIPROCESSOR SYSTEM AND METHOD FOR DISTRIBUTING WORK LOAD IN SUCH A |
Non-Patent Citations (2)
| Title |
|---|
| BARAK, A. et a.: A distributed load-balan- cing policy for a multicomputer. In: Soft- ware-Practice and Experience, 1985, Vol. 15 (9), S. 901-913 * |
| PENG, Dartzen u. SHIN, Kang: Modeling of Cancurrent Task Execution in a Distributed System for Real-Time Control. In: IEEE Trans. on Computers, April 1987, Vol. C-36, No. 4, S. 500-514 * |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE4330479A1 (en) * | 1993-09-09 | 1994-02-10 | Johann Rost | Distribution of functions to computers of network system - having number of computers designated as control units that can exchange functions and can assign functions |
Also Published As
| Publication number | Publication date |
|---|---|
| DE4132764C2 (en) | 1995-01-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| DE60301202T2 (en) | METHOD AND DEVICE FOR TRANSPORTING A WEB FARM | |
| DE68920490T2 (en) | Process for selecting the least significant route in a communication network. | |
| DE69838506T2 (en) | PROCEDURE FOR TRANSACTIONS BETWEEN DISTRIBUTED DATABASES | |
| DE102020203718B4 (en) | Computer-implemented method for production planning and/or control of a production system and production planning and/or control system for production optimization | |
| DE69230700T2 (en) | Digital data processor for higher commands | |
| DE4110144A1 (en) | RAW MATERIAL PRODUCT GROUP ASSIGNMENT COORDINATOR | |
| DE19955004A1 (en) | Workload management method for computerized workflow management system, automatically generating workload management enclave when control flow enters enclave graph | |
| EP3444997A1 (en) | Devices to provide a quantity of cryptographically protected and filtered as well as sorted transaction datasets of a link of a block chain | |
| DE2449547A1 (en) | COMPUTER AND DATA PROCESSING SYSTEM | |
| DE102019131291B4 (en) | SIMULTANEOUS PERFORMANCE OF SERVICES | |
| DE1218761B (en) | Data storage device | |
| EP0959407A2 (en) | Method for task allocation, data processing system, client data processing node and computer-readable storage medium | |
| DE112006001011T5 (en) | Expandable scheduling of messages on time-triggered buses | |
| DE2556617A1 (en) | DATA PROCESSER FOR THE ROTATABLE MOVEMENT OF BITS OF A DATA WORD | |
| EP2648094B1 (en) | Method and system for creating a source code for a computer program for executing and simulating a process | |
| DE19960048A1 (en) | Start condition processing method for computer workflow management system evaluates correctness of control links for each process activity and verifies time interval conditions | |
| DE69426229T2 (en) | Process for parallel processing of fuzzy logic inference rules and matching circuit architecture with fuzzy input and output | |
| DE19849855C1 (en) | Method for using a computer system to generate a text expression automatically while retaining meaning determines a statistical model on a number of preset pairs of word meanings and associated expressions. | |
| DE69031327T2 (en) | Computer aided decision making facility and process | |
| DE4132764A1 (en) | Organisation of computer network system - using precedence rules with dynamic adaption within cycle for computers coupled onto network | |
| DE60022398T2 (en) | SEQUENCE GENERATOR | |
| EP1647898A1 (en) | Serverless replication of databases | |
| Voss et al. | Strategische M&A-Kompetenz im Rahmen von Akquisitionsstrategien–Komponenten, Erfolgsfaktoren und Aufbau | |
| EP2479664A1 (en) | System and method for generating a source code for a computer program | |
| EP3028182B1 (en) | Method and system for synchronising data |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| OP8 | Request for examination as to paragraph 44 patent law | ||
| 8127 | New person/name/address of the applicant |
Owner name: ROST, JOHANN, 96050 BAMBERG, DE |
|
| 8127 | New person/name/address of the applicant |
Owner name: ROST, JOHANN, 90478 NUERNBERG, DE |
|
| D2 | Grant after examination | ||
| 8364 | No opposition during term of opposition | ||
| 8339 | Ceased/non-payment of the annual fee | ||
| 8370 | Indication of lapse of patent is to be deleted | ||
| 8339 | Ceased/non-payment of the annual fee |