DE3853105T2 - Ein Petri-Netz verwendendes Programmierverfahren und strukturierte Daten verarbeitendes System. - Google Patents

Description

• Die Erfindung betrifft ein Verfahren unter Verwendung eines Petri-Netzes, wobei das Verfahren einen Satz Befehle zum Ausführen eines Datenflußprogramms aufbaut, das strukturierte Daten, zu denen Datensätze, Mengenvereinigungen und Listen gehören, verarbeitet, und sie betrifft ein Prozessor- System, das mit strukturierten Daten betrieben wird und sich zum direkten Handhaben von Datenfluß-Softwarespezifikationen eignet.
• Wie zum Beispiel in "Iwanami Lectures On Microelectronics 8 VLSI Computer I", 10. Dezember 1984, S. 70 bis 75 und in der zugehörigen Grundveröffentlichung von J. B. Dennis et al "A Preliminary Architecture for a Basic Data-Flow Processor", Proc. of 2nd Annual Int. Symp. on Computer Architecture, 1975, S. 126 bis 132 erörtert, kann ein herkömmliches, mit strukturierten Daten betriebenes Prozessorsystem programmiert werden und hat bei Paralleloperationen hohes Funktionsvermögen, obwohl die Operandendaten eines Befehls auf einfache Zahlenwerte beschränkt sind.
• Die vorstehend genannte herkömmliche Technik betrifft Datenflußverarbeitung nur für einfache Daten wie ganze Zahlen und Bitketten und berücksichtigt nicht die Verarbeitung strukturierter Daten. Um strukturierte Daten zu verarbeiten, ist es erforderlich, dieselben in Grund- oder Elementdaten wie ganze Zahlen oder reelle Zahlen zu zerlegen. Daher ist beim Programmieren viel Zeit (Arbeit) erforderlich und es tritt die Schwierigkeit sehr schlechter Lesbarkeit eines Programms auf.
• Ein Programmierverfahren unter Verwendung eines Petrinetzes ist in IEEE 1986 National Aerospace and Electronic Conference, NAECON 1986, Seiten 727 - 732 von G. S. Hura et al: "Petri Net Models of Programming Languages: A unified modelling approach" offenbart. Auch dieses Dokument berücksichtigt nur die Verarbeitung einzelner, einfacher Datenwerte. Ein Verfahren zum Handhaben komplexerer Datenstrukturen ist nicht offenbart.
ZUSAMMENFASSUNG DER ERFINDUNG
• Es ist daher eine Aufgabe der Erfindung, ein Verfahren zum Aufbauen eines Datenflußprogramms zu schaffen, das nicht nur einfache Daten, sondern auch strukturierte Daten handhabt, und ein Prozessorsystem zu schaffen, das auch dazu in der Lage ist, derartige strukturierte Daten zu handhaben.
• Diese Aufgabe wird durch das im Anspruch 1 spezifizierte Verfahren und das in Anspruch 3 dargelegte Datenprozessorsystein gelöst. Bevorzugte Ausführungsformen sind in den Unteransprüchen spezifiziert.
• Um ein Petrinetz als Programmiersprache zu interpretieren, schafft die Erfindung eine Regel oder Bedeutung, durch die strukturierte Daten in Form von Datensätzen, Mengenvereinigungen und Listen gehandhabt werden können. D.h., daß Daten mit dem Datentyp eines kartesischen Produkts, einer direkten Mengenvereinigung und einer Folge direkt auf einen Datenpfad oder eine Verbindung gekoppelt werden, die einem "Ort" im Petrinetzmodelldiagramm entspricht. Daher wird es möglich, einen Befehlssatz zusammenzusetzen, der ein Datenflußprogramm direkt ausführen kann, während zu verarbeitende strukturierte Daten durchlaufen. Das Petrinetzmodell ist detailliert in Robert E. Filman & Daniel P. Friedmann "Coordinated Computing: Tools and Techniques for Distributed Software" 1984, Mc-Graw Hill angegeben, und das Programmierverfahren für strukturierte Daten ist detailliert in Q. J. Dahl, E. W. Dijkstra und C. A. R. Hoare "Structured Programming" Academic Press, 1972 angegeben.
• Das gesamte Anweisungsausführungs-Funktionsvermögen kann durch parallele Operationen der mehreren Prozessoren unter Verwendung der Zusammensetzungs- und Zerlegungsbefehle verbessert werden.
• Für den Zerlegungsbefehl werden strukturierte Daten als Eingangsoperand verwendet und sie werden in Aufbauelemente zerlegt, die ihrerseits als Ausgangsoperanden verwendet werden, und für einen Zusammensetzungsbefehl werden Aufbauelemente als Eingangsoperanden verwendet und sie werden zu strukturierten Daten zusammengesetzt, die ihrerseits als Ausgangsoperanden verwendet werden. Im Ergebnis können strukturierte Daten zur Berechnung (arithmetische Operation) verwendet werden, ohne daß die strukturierten Daten in nichtstrukturierte Grunddaten zerlegt werden, wie bei der herkömmlichen Technik. Die Operanden der Zusammensetzungs- und Zerlegungsbefehle sind in einem Format beschrieben, das die Verbindung spezifiziert, auf der die Daten vorhanden sind. Derartige Verbindungsinformationen sind alle in einem Verbindungspuffer abgespeichert, um eine ausschließliche Steuerung derselben durch eine Verbindungssteuerung auszuführen, um wirkungsvollen Parallelbetrieb zu ermöglichen.
KURZE BESCHREIBUNG DER ZEICHNUNGEN
• Fig. 1 zeigt die Anordnung eines Ausführungsbeispiels eines erfindungsgemäßen Prozessorsystems, das mit strukturierten Daten betrieben wird;
• Fig. 2A und 2B zeigen ein Beispiel £ür den Datenfluß nichtstrukturierter Daten;
• Fig. 3A und 3B zeigen ein Beispiel einer Regel zum Umsetzen eines Datenflußdiagramms in ein Programm;
• Fig. 4 zeigt ein Beispiel eines Datenflußprogramms;
• Fig. 5A, 5B und 5C zeigen Datenstrukturen;
• Fig. 6 zeigt eine spezielle Datenstruktur;
• Fig. 7A und 7B veranschaulichen eine Operation an Daten mit der Struktur eines kartesischen Produkts;
• Fig. 8A und 8B veranschaulichen eine Operation an Daten mit der Struktur einer direkten Mengenvereinigung;
• Fig. 9A und 9B veranschaulichen eine Operation an Daten mit Folgestruktur;
• Fig. 10A bis 10F zeigen Operationen an strukturierten Daten, die in Form von Texten ausgedrückt sind;
• Fig. 11 zeigt ein Beispiel eines Datenflusses, der strukturierte Daten handhabt;
• Fig. 12A und 12B veranschaulichen ein Beispiel eines Befehlsformats und ein Beispiel eines Datenflußprogramms, das strukturierte Daten handhabt;
• Fig. 13A und 13B veranschaulichen die Datenanordnung in einem Verbindungspuffer;
• Fig. 14 zeigt ein Beispiel für die Anordnung des Verbindungspuffers;
• Fig. 15 ist ein Flußdiagramm, das Prozesse veranschaulicht, wie sie von einer Ausführungssteuerung ausgeführt werden;
• Fig. 16 ist ein Flußdiagramm, das Prozesse veranschaulicht, wie sie von einer Prozessoreinheit ausgeführt werden; und
• Fig. 17A und 17C sind Flußdiagramme, die Prozesse veranschaulichen, wie sie von einer Verbindungspuffersteuerung aus geführt werden.
BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSBEISPIELE
• Ausführungsbeispiele der Erfindung werden im einzelnen unter Bezugnahme auf die beigefügten Zeichnungen beschrieben. In den nachfolgend zu beschreibenden Ausführungsbeispielen wird der objektive Datenfluß in einem zweigeteilten Graphen beschrieben, der Arbeitsknoten und Verbindungsknoten abwechselnd über Pfeile verbindet.
• Ein für den Datenfluß verwendetes Programm ist ein Satz von Befehlen, von denen jeder einen Befehlscode, der für einen Arbeitsknoten definiert ist und Operanden aufweist, die in Verbindungsknoten am Eingang und Ausgang des Arbeitsknotens vorhanden sind. Bei Ausführen eines Programms wird dafür gesorgt, daß ausführbare Befehle im Befehlssatz parallel ausgeführt werden. Ein ausführbarer Befehl bedeutet hier ein Befehl, der alle Daten eines Verbindungsknotens oder von Verbindungsknoten am Eingang eines betreffenden Arbeitsknotens enthält. Befehlsausführung bedeutet hier eine Operation, bei der Daten von jeder Eingangsverbindung aufgenommen werden, um eine Umsetzoperation auszuführen, wie sie durch den Befehlscode definiert ist, und bei der die sich ergebenden Daten an jede Ausgangsverbindung ausgegeben werden.
• Der Datenfluß wird beispielhaft unter Verwendung des Problems des Auffindens der Wurzeln eine guadratischen Gleichung beschrieben. Fig. 2A zeigt einen Datenfluß zum Auffinden der Wurzeln einer quadratischen Gleichung. Zu den Eingangsdaten gehört der Koeffizient a des Terms zweiter Ordnung, der Koeffizient b des Terms erster Ordnung und eine Konstante c, und das Berechnungsergebnis sind zwei Wurzeln. Das Diagramm wird unter Verwendung der in Fig. 2B dargestellten Notation beschrieben, in dem Arbeitsknoten repräsentierende Rechtecke und Verbindungsknoten repräsentierende Kreise abwechselnd über Pfeile verbunden sind, um einen zweigeteilten Graph zu bilden. Arbeitsknoten sind mit W1 bis W16 markiert, wobei ein Befehlscode innerhalb eines Rechtecks dargestellt ist, Verbindungsknoten sind mit 11 bis 124 markiert. Ein Verbindungsknotenkreis mit angezeichneter Tangente wird als konstante Verbindung bezeichnet und liefert immer einen konstanten Wert, der für den Verbindungsknoten spezifisch ist. Zur Vereinfachung der Beschreibung ist an der Seite jedes Verbindungsknotenkreises ein Buchstabe angebracht oder es sind Buchstaben angebracht, die den Datenwert repräsentieren, der aus den Starteingangswerten für a, b und c berechnet wird.
• An Befehlscodes OP repräsentiert "+" die Addition, "-" die Subtraktion, "*" die Multiplikation, "/" die Divison, "" die Potenzbildung, "NEG" die Zeichenumkehr, "SQRT" die Quadratwurzel und "DUP" eine Duplizierung. Z.B. werden durch den Befehlscode DUP am Arbeitsknoten W1 Daten aus der eingangsseitigen Verbindung 11 entnommen und dieselben Daten werden in beide ausgangsseitigen Verbindungen 14 und 15 eingegeben. Durch den Befehlscode im Arbeitsknoten W4 werden Daten aus der Verbindung 15 als erster Operand entnommen, während Daten aus der Konstantenverbindung, die den Wert 2 liefert, als zweiter Operand entnommen werden, und es wird die zweite Potenz des ersten Operanden berechnet, um ihn in die ausgangsseitige Verbindung 19 einzugeben. Ähnliche Operationen werden durch andere Arbeitsknoten ausgeführt.
• In den Fig. 3A und 3B ist eine Regel zum Umsetzen eines Datenflusses in ein Programm dargestellt. Fig. 3A zeigt ein allgemeines Datenflußdiagramm für jeden Arbeitsknoten, wobei W die Markierung des Arbeitsknotens repräsentiert, OP einen Befehlscode, l1 bis ln Markierungen der Eingangsseitigen Verbindungsknoten und k1 bis km Markierungen der ausgangsseitigen Verbindungsknoten. Eine Programmanweisung, die dem obigen Datenflußdiagramm entspricht, ist so gegeben, wie es in Fig. 3B dargestellt ist. Fig. 4 zeigt einen Satz von Programmbefehlen, die gemäß der Regel aus dem in Fig. 2A dargestellten Datenflußdiagramm umgesetzt wurden.
• Ausführbare Befehle sind solche, die alle Daten für Eingangsoperanden enthalten, wie bereits beschrieben. Im Fall des in Fig. 4 dargestellten Programms werden erste Daten a, b und c jeweils auf die Verbindungen 11, 12 bzw. 13 als Anfangswert gegeben (sh. Fig. 2A) . In diesem Anfangszustand sind ausführbare Befehle diejenige in W1 und W2. Nach Abschluß der Ausführung der zwei Anweisungen verschwinden die Daten auf den Verbindungen 11 und 12 und sie werden in die Verbindungen 14, 15, 16 und 17 eingegeben. In diesem Zustand sind ausführbare Befehle diejenigen in W3, W4, W7 und W8. Auf ähnliche Weise wird dafür gesorgt, daß ausführbare Befehle der Reihe nach oder parallel ausgeführt werden, um Berechnungsvorgänge im Folgeablauf zu wiederholen, bis ein Zustand erreicht wird, in dem kein ausführbarer Befehl vorliegt. Beim vorliegenden Ausführungsbeispiel dauert die Ausführung an, bis Daten in die Verbindungen 123 und 124 eingegeben sind.
• Die Datenstruktur beinhaltet drei Grundstrukturen, d.h. die Bildung des kartesischen Produkts, die direkte Mengenvereinigung und Folgestrukturen. Es sei angenommen, daß Datensätze D1 und D2 vorliegen. Dann ist ein Satz kartesischer Daten aus D1 und D2 ein Satz von Elementen, wobei jedes Element ein Paar eines Elements D1 und eines Elements D2 ist, was so ausgedrückt wird, wie es in Fig. 5B dargestellt ist. Ein Satz von Folgedaten von D1 ist ein Satz von Elementen, wobei jedes Element kein Element von D1 oder nicht mehr als 1 Element von D1 enthält, was so ausgedrückt wird, wie es in Fig. 5C dargestellt ist.
• Eine wahlfreie Kombination dieser Grundstrukturen wird zum Ausbilden einer Datenstruktur verwendet. Fig. 6 zeigt ein spezielles Beispiel einer kombinierten Datenstruktur. Ein Satz von Daten "Zahlungsfolge für das aktuelle Jahr" besteht aus einer Liste "Zahlungen im aktuellen Jahr". "Zahlungen im aktuellen Jahr" ist ein kartesisches Produkt aus "Name" und "Zahlungsbetrag". "Zahlungsbetrag" ist eine direkte Mengenvereinigung aus "Sonder-Zahlungserhöhung" und "Grundzahlung". "Sonder-Zahlungserhöhung" ist ein kartesisches Produkt aus "Grundzahlung" und "Zahlungserhöhung".
• Die vorstehend genannten Datenstrukturen werden an Verbindungen im Datenfluß gekoppelt. D.h., daß die Datenstrukturen immer Verbindungen zugeordnet sind. Eine Reihe von Befehlen ist für die Datenstrukturen definiert.
• Für die kartesische Datenstruktur werden ein Produktzerlegungsbefehl und ein Produktzusammensetzungsbefehl bereitgestellt. Die allgemeine Anordnung der Zerlegung eines kartesischen Produkts ist in Fig. 7A dargestellt. Die Datenstruktur D an der eingangsseitigen Verbindung L eines Arbeitsknotens W ist ein kartesisches Produkt aus D1 bis Dn, ein Befehlscode, der dem Arbeitsknoten zugeordnet ist, ist ein Produktzerlegungsbefehl PD und die Datenstrukturen an den ausgangsseitigen Verbindungen L1 bis Ln des Arbeitsknotens W sind D1 bis Dn. In diesem Zustand wird der Arbeitsknoten ausführbar, wenn in die Verbindung L ein Wert V für D eingegeben wird. Bei der Ausführung durch den Arbeitsknoten wird der Wert V der Verbindung entnommen und in die Elemente V1 bis Vn zerlegt, um sie jeweils in die ausgangsseitigen Verbindungen L1 bis Ln einzugeben.
• Eine allgemeine Anordnung für die Zusammensetzung eines kartesischen Produkts ist in Fig. 7B dargestellt. Die Datenstrukturen an den eingangsseitigen Verbindungen L1 bis Ln eines Arbeitsknotens W sind D1 bis Dn, ein dem Arbeitsknoten zugeordneter Befehlscode ist ein Produktzusammensetzungsbefehl PC und die Datenstruktur D an der ausgangsseitigen Verbindung L des Arbeitsknotens W ist das kartesische Produkt aus D1 bis Dn. In diesem Zustand wird der Arbeitsknoten W ausführbar, wenn Werte V1 bis Vn für die 0atenstrukturen D1 bis Dn in die Verbindungen L1 bis Ln eingegeben werden. Bei der Ausführung durch den Arbeitsknoten W werden die Werte V1 bis Vn gleichzeitig in den Arbeitsknoten aufgenommen, um die Werte V1 bis Vn in einen Wert V zusammenzusetzen, der in die Verbindung L eingeschrieben wird.
• Für die Struktur mit direkter Mengenvereinigung werden ein Vereinigungsmenge-Zerlegungsbefehl und ein Vereinigungsmenge-Zusammensetzungsbefehl bereitgestellt. Eine allgemeine Anordnung für die Zerlegung einer direkten Mengenvereinigung ist in Fig. 8A dargestellt. Die Datenstruktur D auf der eingangsseitigen Verbindung L der Arbeitsknoten W1 bis Wn ist eine direkte Mengenvereinigung von D1 bis Dn, der jedem Arbeitsknoten zugeordnete Befehlscode ist ein Vereinigungsmenge-Zerlegungsbefehl UD und die Datenstrukturen auf den ausgangsseitigen Verbindungen L1 bis Ln der Arbeitsknoten W1 bis Wn sind D1 bis Dn. In diesem Zustand wird der Arbeitsknoten Wi ausführbar, wenn ein Wert V für D in die Verbindung L eingeschrieben wird und der Wert V zu Di (i = 1 bis n) gehört. Bei der Ausführung durch den Arbeitsknoten Wi wird der Wert V der Verbindung entnommen und als Element von Di in die Verbindung Li eingeschrieben. Eine allgemeine Anordnung für direkte Vereinigungsmenge-Zusammensetzung ist in Fig. 8B dargestellt. Die Datenstrukturen D auf den Eingangsseitigen Verbindungen L1 bis Ln der Arbeitsknoten W1 bis Wn sind D1 bis Dn, der jedem Arbeitsknoten zugeordnete Befehlscode ist ein direkter Vereinigungsmenge-Zusammensetzungsbefehl UC und die Datenstruktur D auf der ausgangsseitigen Verbindung L der Arbeitsknoten W1 bis Wn ist eine direkte Vereinigung von D1 bis Dn. In diesem Zustand wird der Arbeitsknoten Wi ausführbar, wenn ein zur Verbindung Li unter den Verbindungen L1 bis Ln gehöriger Wert Vi eingeschrieben wird. Bei der Ausführung durch den Arbeitsknoten Wi wird der Wert Vi der Verbindung entnommen und als Element von D in die Verbindung L eingeschrieben.
• Für eine Folgedatenstruktur, d.h. eine Liste, wird eine Folgezerlegungsbefehl- und eine Folgezusammensetzungsbefehl-Folge bereitgestellt. Eine allgemeine Anordnung für eine Folgezerlegung ist in Fig. 9A dargestellt. Die Datenstruktur D (z.B. eine Liste) auf der eingangsseitigen Verbindung L eines Arbeitsknotens W ist eine Liste D1 (z.B. eine Zeile der Liste), der dem Arbeitsknoten W zugeordnete Befehlscode ist ein Folgezerlegungsbefehl SD und die Datenstruktur auf der ausgangsseitigen Verbindung L1 ist D1. In diesem Zustand wird der Arbeitsknoten W ausführbar, wenn auf die Verbindung L ein Wert V für D eingeschrieben wird. Bei der Ausführung durch den Arbeitsknoten W wird der Wert V der Verbindung entnommen und in Folgestrukturelemente V1 bis Vn zerlegt, die alle in die Verbindung L1 eingeschrieben werden, während die Reihenfolge der Elemente eingehalten wird. Eine allgemeine Anordnung einer Folgezusammensetzung ist in Fig. 9B dargestellt. Die Datenstruktur auf der eingangsseitigen Verbindung L1 eines Arbeitsknotens W ist D1, der dem Arbeitsknoten zugeordnete Befehlscode ist ein Folgezusammensetzungsbefehls SC und die Datenstruktur auf der ausgangsseitigen Verbindung L ist eine Liste D1. In diesem Zustand wird der Arbeitsknoten ausführbar, wenn Werte V1 bis Vn (n ist 1 oder größer) für D1 auf der Verbindung L1 eingeschrieben werden. Bei der Ausführung durch den Arbeitsknoten W werden die Werte V1 bis Vn gleichzeitig vom Arbeitsknoten aufgenommen, um sie in ein Element V der Folgestrukturdaten D zu zerlegen und dieses in die Verbindung L einzuschreiben.
• Die Formate von Programmbefehlen, wie sie in den Fig. 7A, 7B, den Fig. 8A, 8B und den Fig. 9A, 9B dargestellt sind, sind in den Fig. 10A bis 10F gezeigt. Ein Beispiel für einen Datenfluß, der derartige Datenstrukturen handhabt, ist in Fig. 11 dargestellt.
• Ein Ausführungsbeispiel eines automatischen Verarbeitungssystems als eine der Anwendungen der Erfindung wird nachfolgend beschrieben.
• Fig. 1 zeigt ein Blockdiagramm, das ein mit strukturierten Daten betriebenes Prozessorsystem gemäß der Erfindung veranschaulicht, durch das ein strukturierte Daten handhabendes Datenflußprogramm ausgeführt werden kann. Das mit strukturierten Daten betriebene Prozessorsystem dieses Ausführungsbeispiels beinhaltet eine Prozessoreinheit 1, einen Verbindungspuffer 2, eine Verbindungspuffersteuerung 3, einen Befehlspuffer 4 und eine Ausführungssteuerung 5. Die Prozessoreinheit 1 besteht aus mehreren Prozessoren 6&sub1;, 6&sub2;, 6&sub3;, ... Der Verbindungspuffer 2 besteht aus einem Instanzbereich 7 und einem Definitionsbereich 8, wobei der erstere aus mehreren Instanzzellen 9&sub1;, 9&sub2;, ... besteht und der letztere aus mehreren Definitionszellen 10&sub1;, 10&sub2;, .. besteht. Der Befehlspuffer 4 besteht aus mehreren Befehlszellen 11&sub1;, 11&sub2;, 11³, ...
• Information zu Programmbefehlen, die mit dem in Fig. 3B dargestellten Befehlsformat übereinstimmen, ist in den Befehlszellen 11&sub1;, 11&sub2;, 11&sub3;, ... des Befehlspuffers 4 abgespeichert. Die Information wird in dieser Beschreibung als Befehlspaket bezeichnet. Das Format des Befehlspakets ist beispielhaft in Fig. 12A dargestellt. Ein Befehlspaket besteht aus einem Befehlscode, Verbindungsinformation für die Eingangsseite und Verbindungsinformation für die Ausgangsseite. Wie eine Befehlspaketgruppe für den in Fig. 11 dargestellten Datenfluß im Befehlspuffer abgespeichert ist, ist beispielhaft in Fig. 12B dargestellt.
• Verbindungsinformation für das Datenflußprogramm ist in den Instanzzellen 9&sub1;, 9&sub2;, 9&sub3;, ... innerhalb des Instanzbereich 7 des Verbindungspuffers 2 abgespeichert. Jede Verbindung ist mit einer Nummer markiert, um die Verbindung eindeutig zu kennzeichnen. Der in einer Verbindung abgespeicherte Wert ist der Datenstruktur für diese Verbindung zugewiesen. Solche Datenstrukturinformation ist als Zeiger auf die Definitionszelle 8 abgespeichert. Das Format einer Instanzzelle ist beispielhaft in Fig. 13A dargestellt.
• In den Definitionszellen 10&sub1;, 10&sub2;, ... innerhalb des Definitionsbereichs 8 des Verbindungspuffers 2 ist Datenstrukturinformation abgespeichert. In einer Definitionszelle 10i = 1 bis n) ist Strukturinformation zu einem kartesischen Produkt, zu einer direkten Mengenvereinigung oder einer Folge, wie in Fig. 5 dargestellt, oder Grunddatentypinformation abgespeichert. Fig. 13B zeigt Beispiel für das Format der Definitionszellen 10&sub1;, 10&sub2;, ...
• Ein Beispiel für das Format des Verbindungspuffers 2 für den in Fig. 11 dargestellten Datenfluß ist in Fig. 14 gezeigt.
• Fig. 15 zeigt ein Flußdiagramm, das einen Ausführungsablauf durch die in Fig. 1 dargestellte Ausführungssteuerung 5 veranschaulicht. Beim Betrieb der Ausführungssteuerung 5 wird ein Befehlspaketsignal 12 vom Befehlspuffer 4 empfangen (Schritt 101), um Eingangsoperanden des Befehlspakets zu sammeln und eine Eingangsverbindungsnummernkette zu erzeugen (Schritt 102). Danach wird zum Überprüfen, ob der Zustand erfüllt ist oder nicht, gemäß dem ein Befehl erst dann ausführbar ist, wenn die Werte in alle betroffenen Eingangsverbindungen eingeschrieben sind, das Eingangsverbindungsnummernkette-Signal 14 an die Verbindungspuffersteuerung 3 geliefert und das sich ergebende Beurteilungssignal 13 wird empfangen (Schritt 103). Es ist zu beachten, daß dann, wenn eine Eingangsverbindung mit nur einem einzigen Datenwert (herausgegriffenes Element) mit mehreren Arbeitsknoten verbunden wird und das herausgegriffene Element durch einen der Arbeitsknoten aufgenommen wird, die anderen Arbeitsknoten in einen Sperrzustand eintreten und nicht ausgeführt werden, wobei das Paket zum Befehlspuffer zurückgeführt wird.
• Wenn das Beurteilungssignal 13 einen ausführbaren Zustand anzeigt, wird das Befehlspaketsignal 16 an die Prozessoreinheit 1 geliefert (Schritt 104). Falls nicht, wird das Befehlspaketsignal 15 zum Befehlspuffer 4 zurückgeliefert (Schritt 105). Die vorstehenden Prozesse können für jede Befehlszelle 11 parallel ausgeführt werden, um so das Betriebsfunktionsvermögen zu verbessern.
• Fig. 16 zeigt ein Flußdiagramm, das den Ausführungsablauf der in Fig. 1 dargestellten Prozessoreinheit 1 veranschaulicht. Die Prozessoreinheit 1 besteht aus mehreren Prozessoren 6&sub1;, 6&sub2;, 6&sub3;, ..., so daß mehrere Befehlspakete parallel verarbeitet werden können.
• Der Betrieb der Prozessoreinheit 1 ist der im folgenden beschriebene. Wenn die Prozessoreinheit 1 ein Befehlspaketsignal 16 von der Ausführungssteuerung 5 empfängt (Schritt 201), ordnet sie die Ausführung des Befehlspakets einem ungenutzten Prozessor zu. Nachdem aus dem empfangenen Befehls-Paket Eingangsverbindungsnummern gewonnen wurden, wird ein Verbindungsnummernkette-Signal 18 an die Verbindungspuffersteuerung gegeben, um in den zugeordneten Verbindungen abgespeicherte Werte zu erhalten und das sich ergebende Verbindungsdatenkette-Signal 17 wird empfangen (Schritt 202). Wenn der Empfang von Verbindungsdaten fehlschlägt, wird das Befehlspaket ohne Ausführung desselben an den Befehlspuffer zurückgeliefert (Schritt 205).
• Wenn Erfolg hinsichtlich des Erhaltens von Verbindungsdaten besteht, wird auf Grundlage der erhaltenen Werte eine Berechnung gemäß dem Anweisungscode des Befehlspakets ausgeführt (203). Die sich ergebende, berechnete Datenkette wird als Ausgangsverbindungsdatenkette-Signal 18 an die Verbindungspuffersteuerung 3 geliefert (Schritt 204). Nach der Berechnung wird das Befehlspaketsignal 19 an den Befehlspuffer 4 geliefert (Schritt 205).
• Die Fig. 17A bis 17C zeigen Flußdiagramme, die die Ausführungsabläufe der in Fig. 1 dargestellten Verbindungspuffersteuerung 3 veranschaulichen. Die Verbindungspuffersteuerung 3 wird dazu verwendet, eine ausschließliche Steuerung für den Zugriff auf die Verbindungsinformation eines Datenflußprogramms gemäß einer Prioritätsreihenfolge auszuführen. Die Abläufe beim Zugreifen auf Verbindungsinformation beinhalten eine Ausführungsbeurteilung durch die Ausführungssteuerung 5, ein Zugreifen auf Daten und ein Einschreiben von Daten durch die Prozessoreinheit 1, was alles parallel ausgeführt werden kann.
• Der Betrieb der Prozessoreinheit 1 ist der im folgenden beschriebene.
• Fig. 17A zeigt ein Flußdiagramm, das den Ablauf der Ausführungsbeurteilung veranschaulicht. Wenn die Verbindungspuffersteuerung 6 von der Ausführungssteuerung 5 ein Eingangsverbindungsnummernkette-Signal 16 empfängt (Schritt 301), bleibt sie im Wartezustand, bis alle in der Verbindungsnummernkette enthaltenen Verbindungen entsperrt sind (Schritt 302), sie sperrt alle Verbindungen, um eine ausschließliche Steuerung der Verbindungszugriffe von anderen Prozessen auszuführen (Schritt 303) und sie beurteilt, ob in jede Verbindung ein Wert eingeschrieben ist (Schritt 304).
• Wenn in alle Verbindungen Werte eingeschrieben sind, wird an die Ausführungssteuerung 5 ein Beurteilungssignal 13 geliefert, das den ausführbaren Zustand anzeigt (Schritt 306). Wenn in nur eine der Verbindungen kein Wert eingeschrieben ist, wird ein Beurteilungssignal 13, das einen Sperrzustand anzeigt, an die Ausführungssteuerung 5 geliefert (Schritt 305). Schließlich wird der Sperrzustand der Verbindungen aufgehoben (Schritt 307).
• Fig. 17B zeigt ein Flußdiagramm, das den Ablauf einer Datenerfassung veranschaulicht. Wenn die Verbindungspuffersteuerung 3 von der Prozessoreinheit 1 ein Verbindungsnummerkette-Signal 18 empfängt, geht sie in den Wartezustand, bis alle Verbindungen in der Verbindungsnummernkette entsperrt sind (Schritt 309) , sie sperrt alle Verbindungen, um eine ausschließliche Steuerung von Verbindungszugriffen von anderen Prozessen auszuführen (Schritt 310) und sie beurteilt, ob in jede Verbindung ein Wert eingeschrieben ist (311).
• Wenn in nur eine der Verbindungen kein Wert eingeschrieben ist, wird an die Prozessoreinheit 1 ein Steuersignal 17 ausgegeben, das einen Mangel bei der Datenerfassung anzeigt (Schritt 312). Wenn in alle Verbindungen Werte eingeschrieben sind, werden die Verbindungsdaten aus ihnen entnommen und das zugeordnete Verbindungsdatenkette-Signal 17 wird an die Prozessoreinheit 1 geliefert (Schritt 313) , um danach die aus der Verbindung entnommenen Daten zu löschen (Schritt 314). Schließlich wird, auf ähnliche Weise wie oben, der Sperrzustand aller Verbindungen aufgehoben (Schritt 315).
• Fig. 17C zeigt ein Flußdiagramm, das den Ablauf des Einschreibens von Daten veranschaulicht. Wenn die Verbindungspuffersteuerung 3 von der Prozessoreinheit 1 ein sich ergebendes, berechnetes Ausgangsverbindungsdatenkette-Signal 18 empfängt (Schritt 316), geht sie in einen Wartezustand, bis alle Verbindungen im Ausgangsverbindungsdatenkette-Signal 18 vom Verbindungspuffer in den entsperrten Zustand gelangt sind (Schritt 317), sie sperrt alle Verbindungen, um eine ausschließliche Steuerung des Verbindungszugriffs von anderen Prozessen auszuführen (Schritt 318) und sie schreibt in jede Verbindung Daten ein, die durch das Ausgangsverbindungsdatenkette-Signal 18 spezifiziert werden (Schritt 319). Schließlich wird der Sperrzustand aller Verbindungen aufgehoben (Schritt 320).
• Bei den in den vorstehenden Ausführungsbeispielen beschriebenen Prozessorsystemen, die mit strukturierten Daten betrieben werden, können nicht nur herkömmliche Grunddaten verarbeitet werden, sondern es können auch strukturierte Daten mit Datensätzen, Mengenvereinigungen und Listen direkt verarbeitet werden. Daher kann ein Datenflußprogramm entwikkelt werden, das abstrakter ist und vom Menschen leichter verstanden werden kann, und die Zuverlässigkeit eines Programms kann aufgrund des einfachen Verständnisses für dasselbe verbessert werden. Ferner ist eine Operation, die strukturierte Daten handhabt, eingeführt, die auf ähnliche Weise wie andere Berechnungen ausgeführt werden kann. Daher ist parallele Ausführung gewährleistet, was die Ausführungsgeschwindigkeit eines Programms verbessert.
• In den vorstehenden Ausführungsbeispielen wurden die Erfindung verkörpernde Prozessorsysteme, die mit strukturierten Daten betrieben werden, beispielhaft beschrieben. Jedoch ist es dem Fachmann erkennbar, daß die Erfindung nicht auf Prozessorsysteme beschränkt ist, die mit strukturierten Daten betrieben werden, sondern daß sie auch auf Prozessorsysteme vom Von-Neumann-Typ anwendbar sind.

Claims (5)

1. Verfahren zur Durchführung auf einem Computer mit einem Satz an Befehlen für ein Datenfluß-Programm aus einem Petrinetz-Diagramm, das das Programm nachbildet und auf strukturierte Daten ausgerichtet ist, die ein kartesisches Produkt von Sätzen, eine direkte Verbindung von Sätzen und/oder Listen oder eine Kombination davon aufweisen, wobei das Verfahren die folgenden Schritte umfaßt:

Bereitstellen gewünschter Datenwege (l1 ... ln), d.h. Plätze in dem genannten Petrinetz-Diagramm, wobei jeder Weg eine zugeordnete Datenstruktur aufweist, die die zu verarbeitenden Daten festlegt;

Bereitstellen von Bearbeitungsknoten (W1 ... W9), d.h. Übergängen in dem genannten Petrinetz-Diagramm, wobei die Bearbeitungsknoten Knoten (PD, UD, SD) zur Zerlegung der genannten strukturierten Daten in ihre Grundbestandteile und Knoten (PC, UC, SC) zum Zusammensetzen von Grundbestandteilen zu solchen strukturierten Daten aufweisen; und

Umwandeln des genannten Petrinetz-Diagramms, so daß für jeden Bearbeitungsknoten ein entsprechender Befehl erzeugt wird und jeder Befehl mit seinen jeweiligen Eingangs- und Ausgangswegen als Operanden versehen ist.

2. Verfahren nach Anspruch 1, wobei die Befehle einen Zerlegungsbefehl, bei dem strukturierte Daten als Eingangsoperand verwendet und in ihre Bestandteile zerlegt werden, die wiederum als Ausgangsoperanden verwendet werden, und einen Verbindungsbefehl, bei dem Bestandteile als Eingangsoperanden verwendet und zu strukturierten Daten zusainmengesetzt werden, die wiederum als Ausgangsoperand verwendet werden, aufweist.

3. Verarbeitungssystem für strukturierte Daten, aufweisend:

einen Befehlspuffer (4) zur Aufnahme von Befehlen bei der Ausführung eines Datenfluß-Programms,

eine Ausführungs-Steuereinrichtung (5) zur Beurteilung, ob aufgegriffene Befehle ausführbar sind und um sie zu einer Vielzahl von Prozessoren (1) zu senden, und

eine Einrichtung zur Verbindung der Ausführungs-Steuereinrichtung (5), des Befehlspuffers (4) und der Vielzahl von Prozessoren (1),

wobei diejenigen Befehle, die einen kompletten Satz an Operandendaten aufweisen, parallel ausgeführt werden können,

dadurch gekennzeichnet,

daß ein Verbindungspuffer (7) zur Speicherung von Informationen über Verbindungen, die ein Datenfluß-Programm- Diagramm darstellen, vorgesehen ist, der einen Speicherbereich (8, 10) zur Speicherung von Informationen über eine Datenstruktur, die ein kartesisches Produkt von Sätzen, eine direkte Verbindung von Sätzen und/oder Listen beinhaltet, zu speichern,

daß zur ausschließlichen Steuerung der genannten Information über die Verbindungen eine Verbindungspuffer-Steuereinrichtung (3) vorgesehen ist, um in Zusammenarbeit mit der Ausführungs-Steuereinrichtung (5) entsprechend der Befehlsinformation von dem Befehlspuffer die Information über die Verbindungen an die Vielzahl von Prozessoren (1) zu senden, und

daß der Befehlspuffer einen Speicherbereich (11&sub1; 11&sub2;, 11&sub3;, ...) zur Speicherung eines Codes, der einen Zerlegungsbefehl und einen Zusammensetzungsbefehl angibt, aufweist, wobei der Zerlegungsbefehl Daten des Programms mit der genannten Struktur eines kartesischen Produkts von Sätzen, einer direkten Verbindung von Sätzen oder Listen, oder Daten, die in eine solche Datenstruktur umwandelbar sind, in Abhängigkeit der zu verarbeitenden Daten in Bestandteile zerlegt, und wobei der Zusammensetzungsbefehl Daten der genannten Struktur aus Bestandteilen zusammensetzt.

4. System nach Anspruch 3, dadurch gekennzeichnet, daß der Verbindungspuffer (7) einen Speicherbereich (9) zur Speicherung von Operanden von Instruktionen beinhaltet.

5. System nach einem der Ansprüche 3 bis 4, dadurch gekennzeichnet, dar das Format der Befehle, die in dem Befehlspuffer (4) gespeichert sind, ein Befehlspaket darstellt, das einen Befehlscode und Verbindungsinformationen über Eingang und Ausgang des Befehls beinhaltet.