DE69031100T2

DE69031100T2 - Interprozessor-Datenabhängigkeit minimierendes Übersetzungsverfahren

Info

Publication number: DE69031100T2
Application number: DE69031100T
Authority: DE
Inventors: Rajiv Gupta
Original assignee: Philips Electronics NV
Current assignee: NXP BV
Priority date: 1989-08-29
Filing date: 1990-08-27
Publication date: 1998-02-12
Anticipated expiration: 2010-08-28
Also published as: JPH0397059A; DE69031100D1; EP0415497B1; EP0415497A2; US5317734A; EP0415497A3; JP2980178B2

Description

HINTERGRUND ZU DER ERFINDUNG.

Die Erfindung bezieht sich auf ein Übersetzungsverfahren für die Planung datenabhängiger Operationen, beschreibbar als eine azyklische Graphik mit Knoten, die Operationen darstellen und mit Kanten, die Datenabhängigkeiten darstellen, geleitet in eine Vielzahl an parallelen Instruktionsströme für die Verarbeitung durch eine Vielzahl an digitalen Prozessoren und für die Planung synchronisierter Datentransfers auf einer Vielzahl an Interprozessor-Datentransfermitteln nach der vorrede des Anspruches 1. In der Veröffentlichung der 21. jährlichen Hawaii International Conference über Systemwissenschaften in Kailua-Kona, HI, vom 5.-8. Januar 1988, Band 1 S.148-156 von R. Gupta et al: "A Matching Approach to Utilizing Fine-grained Parallelism" (D1) wird eine Methode für die Planung von Operationen in einer breiten Anordnung von Prozessoren nr x nc beschrieben, wobei nach der Verteilung der Operationen über verschiedene individuelle Regionen die Operationen in jeder der jeweiligen Regionen die Operationen, die auf dem größten Pfad der noch vorzunehmenden Operationen liegen zuerst vorgesehen werden.
Die Erhöhung der Arbeitsgeschwindigkeit über die eines Uniprozessors unter Verwendung paralleler Prozessoren zur gemeinsamen Durchführung sequentieller Programme hängt von der effektiven Nutzung der feinkörnigen Parallelität des Programms ab, um die gleichzeitige Durchführung paralleler Operationen an verschiedenen Prozessoren zu ermöglichen. Während die Parallelität auf Schleifenebene in handelsüblichen Multiprozessorsystemen allgemein effizient genutzt wird, ist die effiziente Nutzung der in den sequentiellen Teilen des Programms vorhandenen Parallelität der Zusatzschleife (außerhalb der Schleife oder nicht geschlossen) schwieriger.
Mit der Anordnungsweise in einem Very Long Instruction Word (VLIW) kann der in den sequentiellen Teilen des Programms vorhandene feinkörnige Parallelismus genutzt werden. Bekannte Geräte dieses Typs verwenden ein Übersetzungsprogramm auf der Grundlage der Ablaufplanung (siehe z.B. J.A. Fisher,
"TRACE SCHEDULING: A TECHNIQUE FOR GLOBAL MICROCODE COMPACTION", IEEE Trans. on Computers, Band 7, Nr. C-30, Seiten 478-490, Juli 1981) zur Erfassung und Planung von Parallelismus außerhalb einer Schleife in sequentiellen Teilen des Programms und zur Nutzung des Parallelismus auf Schleifenebene durch Entrollen der Schleifen und Konvertieren des Parallelismus auf Schleifenebene in Parallelismus außerhalb der Schleife.
Das VLIW-Gerät besteht jedoch aus einer Vielzahl in Sperrschritten arbeitenden Prozessoren, die einem einzigen Informationsfluß entnommene Instruktionen ausführen. Das lange Instruktionswort ermöglicht die Auslösung yerschiedener feinkörniger Operationen mit jeder Instruktion, was die Planung von Operationen zur parallelen Ausführung von verschieden Prozessoren ermöglicht. Während der Sperrschritt-Betrieb der Prozessoren vorbehaltlos garantiert, daß die Prozessoren synchronisiert sind, wird die Geschwindigkeit der VLIW-Geräte schwer durch Vorgänge beeinträchtigt, die während der Laufzeit auftreten und zum Übersetzungszeitpunkt unvorhersehbar sind. Konflikte beim Speicherbankzugriff z.B. können nicht immer vermieden werden, da die für eine Operation erforderlichen Operanden zum Übersetzungszeitpunkt möglicherweise nicht bekannt sind. Solche Laufzeitereignisse können eine Verzögerung bei der Übersetzung einer der Operationen bei einer langen Instruktion hervorrufen, was die Vollendung der gesamten Instruktion verzögert.
Die Ausdehnung der VLIW-Anordnung in eine Anordnung mit einer Vielzahl an Informationsströmen erfordert Mittel zur Synchronisierung der parallelen Prozessoren, um zu gewährleisten, daß die von einem Prozessor erzeugten und von einem anderen benötigten Daten von dem einen Prozessor bereits in gemeinsame Speichermittel geschrieben wurden, bevor der andere Prozessor versucht, die gemeinsamen Speichermittel zu lesen. Die Verwendung gemeinsamer Speichermittel zur Ermöglichung des Datenaustausches zwischen Prozessoren erfordert außerdem eine zusätzliche Synchronisierung, um zu gewährleisten, daß die in einem Speicher befindlichen Daten bereits von allen Prozessoren gelesen wurden, die diese benötigen, bevor andere Daten eingetragen werden.
Eine Methode zur Synchronisierung von Prozessoren besteht in der Planung von Barrieren in den Instruktionsströmen, um die zeitliche Reihenfolge der Interprozessorabläufe wie das Lesen und Schreiben aus und in den gemeinsamen Speicher zu gewährleisten. Bei der vorliegenden Erfindung sind die parallelen Prozessoren auf andere Art synchronisiert, d.h. unter Verwendung von Interstrom- Kommunikation abhängiger Daten zwischen Prozessoren zur Synchronisierung dieser Prozessoren.
Der HEP-Multiprozessor (siehe B.J. Smith, "ARCHITECTURE AND APPLICATIONS OF THE HEP MULTIPROCESSOR COMPUTER SYSTEM", REAL-TIME SIGNAL PROCESSING, Band 298, Seiten 241-248, August 1981, und J.S. Kowalik, Herausgeber, "PARALLEL MIMD COMPUTATION: REP SUPERCOMPUTER AND ITS APPLICATIONS", MIT Press, 1985) enthält eine große Anzahl an Kanälen, die dazu in der Lage sind, die Datenkommunikation zwischen Prozessoren durch Hinzufügen eines Synchronisationsbits in jeden gemeinsamen Speicherbereich und die Registervorrichtung zu synchronisieren. Die in jeder Instruktion enthaltenen Steuerbits zeigen an, ob eine Leseoperation implizit ist oder warten muß, bis der Bereich "voll" ist. Allerdings veranlaßt in einem HEP-Multiprozessor das Synchronisationsbit den Prozessor nicht immer zum Stoppen, wenn das Bit nicht den geeigneten Zustand aufweist. Dagegen verbleiben bei einem Prozeßstopp der Programmzähler und die Instruktion unverändert im Prozeß. Der Ablauf wechselt auf einen anderen Prozeß, und die Durchführung der unausgeführten Instruktion wird erst dann wieder versucht, wenn der Prozeß erneut die Leitung durchläuft. Zwischenzeitlich werden Instruktionen von anderen Strömen ausgegeben, damit die Leitung voll bleibt.
Folglich ist die HEP-Methode nicht sonderlich nützlich, außer wenn die Anzahl Ströme die im System vorhandene Anzahl Prozessoren übersteigt. Auch ist die potentiell unendliche, im gemeinsamen Speicher vorgesehene Anzahl Kanäle für die Kommunikation von Prozessor-Synchronisierungsabläufen oder Daten aufgrund ihrer relativen Langsamkeit im Vergleich zu in den Registern vorgesehenen Kanälen nicht nützlich. Andererseits sind in den Registern vorgesehene Kanäle, obgleich nützlich für die Kommunikation von Synchronisierungsabläufen, an sich in der Anzahl begrenzt, um in bezug auf einen oder mehrere Register oder Funktionen mit typischen Instruktionen adressiert werden zu können. Folglich kann die Anzahl interprozessorabhängiger Abläufe oder synchronisationsbedürftiger Daten aufgrund der Anwendung bekannter Übersetzungstechniken für VLIW-Anordnungen in bezug auf typische sequentielle Programme die Anzahl nützlicher, für die Erzwingung solcher Abhängigkeiten verfügbarer Kanäle übersteigen.
Wie beim REP-Verfahren erfordert Dl eine relativ hohe Anzahl Ströme.
Dazu wird mit dem D1-Verfahren nicht das Problem der Synchronisierung zwischen den verschiedenen Strömen bei der Ausführung berücksichtigt. So ist es eines der Ziele der vorliegenden Erfindung, eine Methode für den Multiprozessorbetrieb zur Synchronisierung des Prozessors bereitzustellen, unter Verwendung einer relativ kleinen Anzahl von Mittel zur schnellen Synchronisierung der Kommunikation zwischen den Prozessoren. Ein weiteres Ziel der Erfindung ist die Bereitstellung einer Übersetzungsmethode zur Erzeugung paralleler Instruktionsströme auf eine Art, die Inter-Datenströme und/oder Abhängigkeiten wesentlich verringert.
Entsprechend einem der Aspekte der Erfindung weist sie gemäß Anspruch 1 das Merkmal auf, daß die Methode aus folgendem besteht:
erste Planung der Knoten der besagten Graphiken in die besagte Vielzahl an Strömen, wobei jede Kante des besagten Graphiken entweder als eine Interstromkante oder Zwischenstromkante beschreibbar ist, die besagten Knoten werden derart vorgesehen, daß die Intrastromkanten in dieselbe Richtung gelenkt werden;
erste Identifizierung der nicht-synchronisationsbedürftigen Kanten unter den besagten Interstromkanten; und
zweite Planung der nicht-synchronisationsbedürftigen Interstromkanten, wie Synchronisations-Datentransfers auf den besagten Interprozessor- Datentransfermitteln.
Weitere relevante Techniken ergehen aus der ICS 87 - 2nd International Conference on Supercomputing, Band 3, 1987, Seiten 141-148: R. Gupta et al, "Region Scheduling" (D2), und der ISC 88, 1988 International Conference on Supercomputer, St. Malo (FR) 4.-8. Juli 1988, Seiten 207-215: F. Allen et al: "A Framework for Determining Usefel Parallelism" (D3). Wie D1 wird in keinem der Artikel das Problem unter Verwendung einer Synchronisation zwischen den parallelen Operationsströmen beim Ablauf verwendet.
Diese und andere Ziele werden durch den Einbau einer relativ kleinen Anzahl an Registerkanälen für die Beförderung von Synchronisationsdatenabhängigkeiten zwischen Prozessoren erreicht. Die Beförderung von interprozessorabhängigen "Daten" (wobei dieser Ausdruck auch die Anzeige eines eingetretenen Ablaufs beinhalten soll) zeichnet sich durch eine Schreiboperation von einem Prozessor in die Speichermittel und eine darauffolgende Leseoperation aus den Speichermitteln von einem anderen Prozessor aus. Ein Merkmal der Erfindung ist, daß die sogenannten "synchronisationsredundanten" Interprozessor-Datenabhängigkeiten auf nicht-synchronisierende Art befördert werden können, über ein erstes Schreiben in einen und ein darauffolgendes Lesen aus einem herkömmlichen gemeinsamen Speicher (ohne Synchronisationsbit), um die begrenzten Registerkanalressourcen nicht zu belasten. Die Synchronisation dieser synchronisationsredundanten Datenabhängigkeiten wird durch die Erzwingung über einen oder mehrere Registerkanäle gewährleistet, die jeweils mit einer bestimmten Interprozessor-Datenabhängigkeit verbunden sind, mit dem Merkmal einer zeitlichen Sequenz eines oder mehrerer Schreib-Lese-Paare, beginnend mit dem zweiten Schreiben eines anderen Prozessors, nicht vor dem ersten Schreiben, und einem nächsten bis letzten Schreibens des besagten anderen Prozessors, nicht vor dem besagten letzten Lesens. Die zeitliche Reihenfolge der verschiedenen Schreib- oder Leseabläufe wird von den Registerkanälen und den relativen Bereichen des Schreibens oder Lesens in den Instruktionsströmen der verschiedenen Prozessoren bestimmt.
Bei der Übersetzungsmethode werden Operationen eines sequentiellen Programms in eine Vielzahl an parallelen Strömen vorgesehen, und auch das Schreiben und Lesen von Interstrom-Datenabhängigkeiten wird vorgesehen. Um dies zu erreichen wird das sequentielle Programm zuerst als geleitete azyklische Knotengraphik beschrieben, die Operationen darstellt, und geleiteter Kanten, die Datenabhängigkeiten darstellen, und die Knoten werden in eine Vielzahl an Instruktionsströmen vorgesehen.
Die Kanten zwischen den Knoten sind dann entweder Intrastrom- oder Interstromkanten. Die Planung ist derart, daß die Knoten in einer Weise in den Strömen angeordnet werden, daß die Intrastromkanten implizit stromabwärts geleitet werden und die von den Intrastromkanten dargestellten Datenabhängigkeiten erzwingen. Die Interstromkanten stellen Interstrom- (oder Interprozessor-)Datenabhängigkeiten dar, die einen Datentransfer zwischen Prozessoren erfordern.
Gemäß einem anderen Merkmal der Erfindung werden synchronisationsredundante Interstromkanten identifiziert, um zu ermöglichen, daß die nicht-synchronisationsredundanten Interstromkanten als Schreib-Lese-Paare auf einer begrenzten Anzahl Synchronisations-Datentransfermitteln vorgesehen werden, die als Kanalregister eingebaut sind.
Gemäß noch einem anderen Merkmal der Erfindung wird die Methode zur Planung der Knoten in Ströme gewählt, um die Anzahl der sich ergebenden Interstromkanten zu minimieren. Dies wird erreicht, indem die Planung in umgekehrter Reihenfolge hinsichtlich der Verarbeitung vorgesehen wird und insbesondere dadurch, daß zuerst die nicht vorgesehenen Knoten mit der größten Höhe in der Graphik identifiziert werden, und diese Knoten dann in einer Weise in verschiedene Ströme vorgesehen werden, um die Erzeugung von Interstromkanten so gering wie möglich zu halten. Und noch ein weiteres Merkmal dieser Methode ist, daß nachdem die Knoten mit der größten Höhe vorgesehen wurden, die mit den besagten Knoten verwurzelten Untergraphiken identifiziert werden und von jeder Untergraphik eine gleiche Änzahl Knoten in absteigender Knotenhöhe in dieselben jeweiligen Ströme wie die verwurzelten Knoten vorgesehen werden. Ein zusätzliches Merkmal der Übersetzungsmethode ist die Identifizierung von Anwärtern in Interstromkanten für die Wiederverwendung derselben Synchronisations-Datentransfermittel.
Die Erfindung hat das zusätzliche Merkmal der Identifizierung impliziter Synchronisationen, hervorgerufen durch die Möglichkeit der Sperrung, auf wiederverwendete Interprozessor-Datentransfermittel zu schreiben und die weitere Identifizierung von Kanten unter Interstromkanten, die dadurch synchronisationsredundant wurden.
Die zahlreichen Merkmale der Erfindung durch die Verminderung oder Minimierung der Anzahl Interprozessor-Datenabhängigkeiten erfordert eine synchronisierende Erzwingung, um es dem Multiprozessor zu ermöglichen, den feinkörnigen Parallelismus in typischen Programmen effektiv zu nutzen, wobei nur eine begrenzte Anzahl an Registerkanälen eingebaut werden muß, um die diesbezüglichen parallelen Prozessoren zu synchronisieren.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Weitere Ziele, Merkmale und Vorteile der vorliegenden Erfindung werden aus der folgenden detaillierten Beschreibung bevorzugter Durchführungsformen in Verbindung mit den beigefügten Zeichnungen ersichtlich, von denen:
Abbildung 1a einen Schaltplan eines Multiprozessors gemäß den Prinzipien der Erfindung darstellt, einschließlich gemeinsamer Registerkanäle;
Abbildung 1b den Plan der Organisation der Bitpositionen eines der gemeinsamen Registerkanäle von Abbildung 1a darstellt;
Abbildung 2a die Veranschaulichung einer geleiteten azyklischen Graphik für eine bestimmte Sequenz von datenabhängigen Instruktionen darstellt;
Abbildung 2b ein Diagramm zur Angabe der Knotenhöhen und -tiefen in der Graphik der Abbildung 2a darstellt;
Abbildung 3 die geleitete azyklische Graphik von Abbildung 2a ohne Operationsbezeichnungen und das Ergebnis der Knotenplanung zwischen zwei parallelen Instruktionsströmen mit einer natürlichen Zuweisungsmethode darstellt;
Abbildung 4 ein Ablaufdiagramm zeigt, das die Methode zur Planung der Knoten zwischen parallelen Instruktionsströmen gemäß der Erfindung darstellt;
Abbildung 5a eine der Abbildung 3 ähnliche geleitete azyklische Graphik darstellt, die jedoch die Planung der Knoten in zwei parallelen Instruktionsströmen gemäß dem Ablaufdiagramm von Abbildung 4 zeigt;
Abbildung 5b die geleitete azyklische Graphik von Abbildung 5a darstellt, entsprechend der Planung neu in Instruktionsströme angeordnet;
die Abbildungen 6a und 6b Zeichnungen von parallelen Instruktionsströmen darstellen, die eine sichere Wiederverwendung von Kanälen zeigen; Abbildung 7 ein Diagramm von parallelen Instruktionsströmen darstellt, die eine durch die Kanalwiederverwendung ausgelöste implizite Synchronisation aufweisen;
Abbildung 8a ein Diagramm von Instruktionsströmen darstellt, das eine einfachen Synchronisationsredundanz zeigt;
Abbildung 8b ein Diagramm von Instruktionsströmen darstellt, das eine redundante Synchronisation in Verbindung mit einer implizierten Synchronisation zeigt;
Abbildung 9 ein Diagramm von Instruktionsströmen darstellt, das eine redundante Synchronisation in Verbindung mit implizierten und impliziten Synchronisationen zeigt;
Abbildung 10 ein Ablaufdiagramm darstellt, das die erfundene Methode der Identifizierung redundanter Synchronisationen in Verbindung mit der Registerkanalzuweisung zeigt;
Abbildung 11 eine geleitete azyklische Graphik der inneren Schleife eines typischen Programms darstellt; und
Abbildung 12 die geleitete azyklische Graphik von Abbildung 11 darstellt, neu in parallelen Instruktionsströmen angeordnet.

DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN DURCHFÜHRUNGSFORMEN

Unter erster Bezugnahme auf die Abbildungen la und lb der Zeichnung wird ein Multiprozessor 10 dargestellt, organisiert in Multipel-Instruktionsstrom- Multipel-Datenstrom-(MIMD-)Form, mit einer Vielzahl an Prozessoren P&sub1;-P&sub4; (vier gemäß der Abbildung) für die jeweilige Durchführung sequentieller Instruktionen an einer gleichen Anzahl Instruktionsströmen S&sub1;-S&sub4;. Die Ströme S&sub1;S&sub4; werden von einem geeigneten Speichermittel (nicht abgebildet) jeweils in die Prozessoren P&sub1;-P&sub4; eingegeben. Auch wurde nicht extra abgebildet, daß jeder Prozessor eigene interne Register enthält und möglicherweise seinen eigenen Speicher, der Mittel bereitstellt, von einem Prozessor entwickelte Daten zur späteren Verwendung durch diesen Prozessor zu speichern, in Verbindung mit stromabwärts verlaufenden Operationen in den Instruktionsströmen für denselben Prozessor.
Dazu enthält der Multiprozessor 10 einen herkömmlichen gemeinsamen Direktzugriffsspeicher 12 mit einer relativ hohen Anzahl an Speicherbereichen, die selektiv von einem beliebigen der Prozessoren P&sub1;-P&sub4; über Adressier- und Datenleitungen 14, zwischen jeden Prozessor und den gemeinsamen Speicher 12 geleitet, gelesen oder beschrieben werden können. Der gemeinsame Speicher 12 kann nicht für die Übertragung von interprozessor- oder interstromabhängigen Daten zwischen den Prozessoren verwendet werden, ohne daß andere Mittel für die Synchronisation angewandt werden. Dies liegt daran, daß der gemeinsame Speicher 12 nicht über implizite Mittel verfügt, um zu gewährleisten, daß ein Wert nicht gelesen wird, bevor er geschrieben ist (wenn z.B. zuerst der Speicherinhalt gefüllt wurde), und ein neuer Wert wird nicht in einen Speicherbereich geschrieben, bevor nicht ein bestehender Wert in dem Speicherbereich gelesen wurde (wenn z.B. der Speicherbereich zuerst geleert wurde). Andererseits wird eine begrenzte Anzahl gemeinsamer Registerkanäle 16 bereitgestellt, damit ein anderer Prozessor P&sub1;-P&sub4; mit grundlegend derselben relativ schnellen Rate darauf zugreift, mit der jeder Prozessor auf einen seiner internen Register zugreifen würde, über Daten-, Adressier- und Steuerleitungen 18 von den jeweiligen Prozessoren. Die besagten Registerkanäle 16 haben jedoch auch Kommunikationsattribute oder Kanalsemantiken, die aus Synchronisationszwecken ein Sperren des Lesens oder Schreibens ermöglichen. Jeder der gemeinsamen Registerkanäle 16 enthält einen Bereich 20 zur Speicherung eines Datenworts derselben Form oder Anzahl Bits, wie in einem gemeinsamen Speicherbereich gespeichert werden könnte, und einen zusätzlichen Bereich 22 für ein Synchronisationsbit, das angibt, ob ein Registerkanal voll oder leer ist.
Die Instruktionssätze des Prozessors enthalten herkömmliche Schreib- und Leseinstruktionen, die zum gemeinsamen Speicher 12 geleitet werden, und vorzugsweise die folgenden Instruktionen für die gemeinsamen Registerkanäle 16:

CLEAR.

Setzt das Synchronisationsbit auf "null" zur Anzeige, daß ein bestimmter Registerkanal leer ist.

NON-DESTRUCTIVE READ.

Ein Lesen kann stattfinden, wenn das Synchronisationsbit "eins" ist zur Anzeige, daß der Kanal voll ist. Das Synchronisationsbit wird vom nicht-destruktiven Lesen unverändert belassen und ermöglicht ein darauffolgendes Lesen. Solange das Synchronisationsbit "null" ist, ist der Registerkanal zum Lesen gesperrt.

DESTRUKTIVE READ.

Entspricht dem nicht-destruktiven Lesen, außer daß beim Lesen das Synchronisationsbit auf "null" gebracht wird.

NON-DESTRUKTIVE WRITE.

Wenn das Synchronisationsbit "null" ist wird der Wert geschrieben und das Synchronisationsbit auf "eins gebracht, um anzuzeigen, daß der Registerkanal voll ist; solange das Synchronisationsbit "eins" ist, ist der Registerkanal zum Schreiben gesperrt.

DESTRUCTIVE WRITE.

Entspricht dem nicht-destruktiven Schreiben, außer daß das Schreiben selbst dann vorgenommen wird, wenn das Synchronisationsbit "eins" ist. Nach dem Schreiben ist das Synchronisationsbit "eins".
Die Instruktionsströme S&sub1;-S&sub4; werden durch die Übersetzung eines sequentiellen Programms erzeugt, um den feinkörnigen Parallelismus in einem Programm durch die Identifizierung der Operationssequenzen zu nutzen, was parallej in verschiedenen Prozessoren vorgenommen werden kann. Dies erfordert die Analyse von Daten- oder Ablaufabhängigkeiten zwischen Operationen in dem sequentiellem Programm.
Abbildung 2a zeigt eine einfache gelenkte azyklische Graphik (GAG) für folgende, der Veranschaulichung dienende Programmschritte:
a[i[: = x*y+c/d
z: = a[j]*5
Dabei stellen die rechteckigen Kästchen die Operationen mit der Bezeichnung "Knoten" dar, die aus Referenzgründen von N1 bis N17 durchnummeriert sind, und die direkten Linien zwischen den Knoten stellen Daten- oder Ablaufabhängigkeiten mit der Bezeichnung "Kanten" dar. Insbesondere die Knoten N1 bis N9 stellen Operationen dar, die die verschiedenen Daten für die Veranschaulichung der Programmschritte erzeugen, und die Knoten N10 bis N17 stellen die Leistung der sequentiellen Programmschritte in bezug auf die besagten Daten dar. Bei dem Beispiel erhält N15 einen Datenwert von N14 und erhält Daten in der Form von Adressenwerten von N10. N15 weist den Wert (durch Schreiben) dieser Adresse zu, und bringt a[i] hervor. N16 erhält eine Adresse von N13 und liest diese Adresse für die Bewertung von a[j]. Da es erforderlich ist, daß a[i] von N15 bereits zugewiesen wurde, denn bei i=j weist N15 den Wert von a[j] zu, wird die von N15 und N16 geleitete Kante 24 mit einer Art von Datenabhängigkeit gezeigt, die eine Ablaufabhängikeit ist. N17 befindet sich aufgrund des Erhalts des Wertes a[j] von N16, einer Konstanten von N9, oben auf der Graphik, und bewertet für die Erzeugung von z die letzte Operation.
Die Planung der Knoten in vielen Instruktionsströmen wird in bezug auf die Knotenhöhe oder -tiefe in der GAG vorgenommen.
Abbildung 2b zeigt die Tiefen und Höhen der verschiedenen Knoten in der Graphik von Abbildung 2a. Wenn die Graphik analog ist mit einem Stammbaum, bei dem jeder Knoten von einem Nachfahrenknoten zu seinem direkten Vorfahrenknoten geleitet wird, hat N17 für Zwecke der Tiefe eine Tiefe gleich eins und jeder andere Knoten die Tiefe seines direkten Vorfahrenknotens plus eins. Für Zwecke der Höhe hat jeder der Knoten N1 bis N9 eine Höhe gleich eins und jeder andere Knoten eine Höhe von eins plus die Höhe des größten Nachfahrens. Dazu sollten für die Planung der Knoten in die zahlreichen Instruktionsströme allgemein zuerst die Knoten mit der größten Tiefe und/oder der kleinsten Höhe in der GAG verarbeitet werden, und die Knoten mit der größten Höhe allgemein zuletzt verarbeitet werden. Obwohl die folgende Abhandlung nur auf dem Baum der Abbildung 2a gründet ist die Erfindung genauso für allgemeine azyklische Graphiken anwendbar, in denen ein Nachfahren mehr als einen Vorfahren haben kann, indem bestimmte Daten zweimal oder mehrere Male verwendet werden.
Abbildung 3 zeigt eine gelenkte azyklische Graphik (GAG) ähnlich der von Abbildung 2a mit als Kreisen dargestellten Knoten mit den Bezeichnungen N1-N14, wobei die Operationen verzögert werden, weil jetzt nur die Form der GAG wichtig ist. Jeder Knoten wird zudem mit einer der Bezeichnungen S1,1-S1,9 und S2,2-S2,8 gekennzeichnet, um mit einer natürlichen Methode die vorgesehene Zuweisungsmethode der Knoten in jeweilige erste und zweite Instruktionsströme für den Ablauf in jeweiligen ersten und zweiten parallelen Prozessoren anzuzeigen.
Bei dieser natürlichen Methode werden die für die Planung fertigen Knoten identifiziert, die die größte Höhe haben und abwechselnd den Instruktionsströmen zugewiesen. Somit werden N3-N6 jeweils folgendermaßen zugewiesen: die erste Instruktion in den ersten Strom (S1,1,); die erste Instruktion in den zweiten Strom (S2,1); die zweite Instruktion in den ersten Strom (S1,2); und die zweite Instruktion in den zweiten Strom (S2,2) Das nächste Niveau der planungsbereiten Knotentiefe wird identifiziert als die Knoten N1, N2, N11 und N12, und die abwechselnde Zuweisung in die Instruktionsströme der identifizierten Knoten wird fortgesetzt. Danach werden weitere Niveaus an Knotentiefen identifiziert und vorgesehen, bis alle Knoten vorgesehen sind. Wenn das Ergebnis der natürlichen Methode geprüft wird, sind acht Kanten mit der Bezeichnung "E" Interstrom- oder Querstromkanten mit Datenabhängigkeiten, die für die Erzwingung zwischen Prozessoren erforderlich sind.
Abbildung 4 zeigt ein Ablaufdiagramm der Übersetzungsmethode für die Planung von Knoten in eine Vielzahl an Instruktionsströme laut den Grundlagen der Erfindung, was die Anzahl der erzeugten Interstroinkanten grundlegend verringert. Dabei wird die Planung der Knoten in umgekehrter Reihenfolge vorgenommen, da von oben begonnen wird, auf u.a. der Grundlage der Höhe anstatt der Tiefe. Somit wird beim ersten Schritt 26 die Höhe jedes Knotens in der GAG bestimmt. Dann wird in Schritt 28 eine Liste der Reihenfolge der Knoten erzeugt, die für die Planung bereit sind. Danach wird in Schritt 30 bestimmt, ob die Anzahl der für die Planung bereitstehenden Knoten unter der der Prozessoren (oder Ströme) liegt. In Schritt 32 wird die Anzahl der planungsbereiten Knoten zur Anzahl Prozessoren in verschiedenen Prozessoren vorgesehen, damit wo möglich der Knoten in demselben Prozessor vorgesehen wird wie sein direkter Vorfahre (oder seine Vorfahren). Schritt 34 bestimmt, ob im vorhergehenden Schritt in jedem Prozessor ein Knoten vorgesehen war und ob alle diese Knoten die Wurzel (Vorfahre) einer Untergraphik sind. Falls ja wird Schritt 36 durchgeführt, in dem eine gleiche Anzahl der höchsten Knoten von den kleinsten mit diesen Knoten verwurzelten Untergraphiken für denselben Prozessor vorgesehen werden wie der Wurzeiknoten. Wenn Schritt 34 falsch war, gibt es einen Zweig zu Schritt 38, der normalerweise Schritt 36 folgt. In Schritt 38 wird bestimmt, ob Knoten weiterhin vorgesehen werden. Wenn ja gibt es einen Zweig zurück zu Schritt 28; wenn nicht stoppt der Planunsgvorgang.
Die Anwendung dieser Übersetzungs oder Planungsmethode für die geleitete azyklische Graphik von Abbildung 2a erzeugt wie in Abbildung Sa gezeigt nur zwei Interstromkanten mit der Bezeichnung E. Diese Methode wird anhand der folgenden Schritte in bezug auf Abbildung 5a besser verständlich: Da 17 Knoten vorzusehen sind werden zuerst 9 Knoten in den ersten Strom bei den Positionen S1,1- S1,9 und 8 Knoten in den zweiten Strom bei den Positionen S2,1-S2,8 vorgesehen. Zu Beginn sind die Knoten N17 und N16 planungsbereit, da N17 keinen Vorfahre hat und die Planung von N17 die Planung von N16 ermöglichen wird. Diese Knoten werden jeweils bei der letzten Operation im ersten Strom (S1,9) und der letzten Operation im zweiten Strom (S2,8) vorgesehen. N16 ist mit zwei Untergraphiken anstatt mit einer einzigen Untergraphik verwurzelt und macht Schritt 34 falsch und Schritt 38 wahr, was die Rückkehr auf Schritt 28 bewirkt. In Schritt 28 werden die Knoten N15 und N14 als planungsbereit identifiziert und in Schritt 32 als jeweils S2,7 und S1,8 vorgesehen. Wiederum ist Schritt 34 falsch, da N14 mit zwei Untergraphiken anstatt mit einer Untergraphik verwurzelt ist, und bewirkt letztlich die Rückkehr auf Schritt 28 und dabei die Identifizierung der Knoten N10 und N13 als planungsbereit. In Schritt 32 werden die Knoten N10 und N11 jeweils als S2,6 und S1,7 vorgesehen. Wiederum wird, da S1,8 mit zwei Untergraphiken verwurzelt ist, auf Schritt 28 zurückgekehrt, wobei die Knoten N12 und N13 als planungsbereit identifiziert werden. Die Knoten N12 und N13 werden jeweils als S1,6 und S2,5 vorgesehen. Danach werden die Knoten NI bis N9 als planungsbereit identifiziert und in ähnlichen sequentiellen Schritten N1 bis N9 folgendermaßen Paaren zugeordnet:
N&sub1;;N&sub3;wieS2,4; S1,5
N&sub2;;N&sub4;wie S2,3; S1,4
N&sub5;;N&sub4; wies S1,3; S2,2
N&sub6;; N&sub8; wie S1,2; S1,1
Jetzt dürfte deutlich sein, wie die Interprozessorkanten grundlegend verringert werden können, indem die Knoten auf der Grundlage der Knotenhöhe in umgekehrter Reihenfolge vorgesehen werden können, da bei diesem Verfahren. versucht wird, eine gesamte Untergraphik einem Prozessor zuzuweisen und so den zwischen Prozessoren verlaufenden Datenumfang so gering wie möglich zu halten. Bei der Planung von jeweils mit ihrer eigenen Untergraphik verwurzelten Knoten wird der Übersetzungsprozeß in Schritt 36 beschleunigt, der eine gleiche Anzahl höchster Knoten von den Untergraphiken für denselben Prozessor vorsieht, für den der Wurzelknoten vorgesehen ist.
Abbildung 5b zeigt eine Neuanordnung der Knoten von Abbildung 5a ihn der Reihenfolge der Planung in zwei Spalten, die jeweils den ersten und den zweiten Instruktionsstrom S&sub1; und S&sub2; darstellen. Die Operationen in den Strömen S&sub1; und S&sub2; werden jeweils von den Prozessoren P&sub1; und P&sub2; in stromabwärts verlaufender Richtung durchgeführt. Verschiedene zwischen Knoten gelenkte Kanten derselben Spalte werden als Interstromkanten bezeichnet, die alle stromabwärts gelenkt werden. Die beiden erzeugten, zwischen den Spalten gelenkten Kanten E werden "Querstrom"-, Interprozessor"- oder "Interstrom"-Kanten bezeichnet. Da das Voranschreiten des Ablaufs entlang der beiden Ströme in gegenseitigem Bezug variieren kann, wird gemäß der Erfindung eine Synchronisation der Kanten E durch eine begrenzte Anzahl Registerkanäle bereitgestellt, die durch das Sperren des Lesens bevor sie geschrieben haben gewährleisten, daß der Ablauf des Stroms S&sub2; falls erforderlich genau vor NiS anhält und auf die Bestimmung des Ergebnisses von N14 in Strom S&sub1; wartet. Ähnlich dazu wird der Ablauf von Strom S&sub1; genau vor N17 anhalten und auf die Bestimmung des Ergebnisses von N16 in Strom S&sub2; warten. Tatsächlich kann derselbe Registerkanal für die Erzwingung der beiden Interstromkanten E wiederverwendet werden, da die Durchquerungsfolge dieser Kanten von N16 stromabwärts zu N15 gewährleistet wird.
Die Abbildungen 6a und 6b zeigen die Bedingungen für sichere Wiederverwendung. Jede Abbildung zeigt drei Instruktionsströme Si,Sj,Sk mit Schreib/Lese-Paaren zu einem Registerkanal, der die jeweils gelenkten Interstromkanten "E" von einer Schreiboperation "W" auf eine Leseoperation "R" zwingt oder synchronisiert. Diese Erzwingung gründet auf der Semantik der Sperrung des Kanals zum Lesen, wenn noch nicht in ihn geschrieben wurde. In Abbildung 6a wird eine erste Interstromkante, von W&sub1;, vorgesehen in Si, nach R&sub1; gelenkt, vorgesehen in Sj, während eine zweite Kante von W&sub2;, vorgesehen in stromabwärts gelenkt wird, von R&sub1; nach R&sub2;, vorgesehen in Sk. Da W&sub2; nach R&sub1; liegen muß kann jede Kante demselben Registerkanal C&sub1; zugewiesen werden, und es besteht keine Möglichkeit, daß W&sub2; zeitlich vor W&sub1; oder daß R&sub2; zeitlich vor R&sub1; auftreten könnte. In Abbildung 6b werden drei Interstromkanten gezeigt, mit einer ersten von W&sub1; nach R&sub1; gelenkten Kante, zugewiesen an C&sub1;, einer zweiten von W&sub2; nach R&sub2; gelenkten Kante, zugewiesen an C&sub2; (obwohl auch eine Zuweisung an C&sub1; möglich gewesen wäre) und eine dritte, von W&sub3; nach R&sub3; gelenkten Kante, die in C&sub1; wiederverwendet wird. Diese Wiederverwendung ist zulässig, da W&sub2; stromabwärts von R&sub1; und W&sub3; stromabwärts von R&sub2; liegt und so die zeitliche Erzwingungsfolge der Interstromkanten gewährleistet.
In Abbildung 7 wird eine andere Situation gezeigt, bei der eine Registerwiederverwendung zulässig ist, doch eine zusätzliche Synchronisation mit der Bezeichnung "Implizit"-Synchronisation erzeugt wird. Dabei werden die ersten und zweiten Kanten von Si nach Sj gelenkt, mit W&sub2; stromabwärts von W&sub1; in Si, und R&sub2; stromabwärts von R&sub1; und Sj. Wenn beide Kanten vom selben Registerkanal C&sub1; erzwungen werden entsteht die Möglichkeit, daß C&sub1; W&sub2; bis zum Auftreten von R&sub1; sperrt. Dies wird mit einer impliziten Interstromsynchronisation U, gelenkt von R&sub1; nach W&sub2; dargestellt.
Abbildung 8a zeigt den einfachen Fall einer ersten Interstromkante V, die redundant von einer zweiten Interstromkante E synchronisiert wird. Dabei werden die Kanten V und E als W&sub1; und W&sub2; in die Ströme Si jeweils nach R&sub1; und R&sub2; in den Strom Sj gelenkt. Da W&sub2; stromabwärts von W&sub1; und R&sub1; stromabwärts von R&sub2; liegt, gewährleistet die Erzwingung von E, daß V erzwungen wird. Anders ausgedrückt muß W&sub2; nach W&sub1; und R&sub1; nach R&sub2; liegen, und die Erzwingung von R&sub2; nach W&sub2; gewährleistet, daß R&sub1; nach W&sub1; liegt. Folglich muß die durch V dargestellte Datenabhängigkeit nicht von einem Registerkanal erzwungen werden, dagegen können W&sub1; und R&sub1; in den gemeinsamen Speicher 12 gelenkt werden.
Abbildung 8b zeigt eine implizierte Synchronisation T, erzeugt von den zweiten und dritten Kanten E. Im allgemeinen wird eine implizierte Synchronisation T vom Anfang bis zum Ende von Synchronisationserzwingungsserien und Stromabwärtsbewegungen gesteuert. Folglich gibt es in Abbildung 8b eine Synchronisation von W&sub2; nach R&sub2;, die Stromabwärtsbewegung entlang &sup5;k von R&sub2; nach W&sub3; und die Synchronisation von W&sub3; nach R&sub3;. Die implizierte Synchronisation T macht dann die von W&sub1; nach R&sub1; geleitete Kante synchronisationsredundant gemäß dem Gesetzt von Abbildung 8a. Im Gegensatz dazu kann die Synchronisationsredundanz von V direkt über ein Gesetzt etabliert werden, das eine Reihe von direkten Stromabwärtsbewegungen und Synchronisationserzwingungen von W&sub1; nach R&sub1; erfordert.
Abbildung 9 zeigt die Wechselwirkung der vorgenannten Synchronisationsarten. Dabei erzeugen die implizite Synchronisation U, gelenkt von R&sub1; nach W&sub3;, aufgrund der Wiederverwendung von C&sub1; wie in Abbildung 7 zusammen mit der Kante von W&sub1; nach R&sub1; die Stromabwärtsbewegung von W&sub3; nach W&sub4; und der Kante von W&sub4; nach R&sub4; die implizierte Synchronisation T von R&sub1; nach R&sub4;, die dann die Kante V synchronisationsredundant macht.
Abbildung 10 ist ein Ablaufdiagramm einer weiteren Übersetzungsmethode gemäß der Erfindung für die Registerkanalzuweisung, deren Eingang die gelenkte azyklische Graphik (GAG) ist, die in Schritt 40 wie in Abbildung 4 in eine Vielzahl an Instruktionsströmen vorgesehen wird, und die sich ergebenden Interstromkanten E werden identifiziert. Danach, in Schritt 42, werden wie in Abbildung 8b implizierte Synchronisationen hinzugefügt, indem die Kantensequenzen unter den drei oder mehr Strömen wie in Abbildung 8b identifiziert werden. Danach, in Schritt 44 werden Synchronisationsredundanzen gemäß den Prinzipien der Abbildungen 8a, 8b oder 9 identifiziert und als Ergebnis in zwei Klassen, eine synchronisationsredundante und eine nicht-synchronisationsredundante unterteilt. Die synchronisationsredundanten Kanten werden in Schritt 46 vorgesehen, durch einen gemeinsamen Schreib- und Lesespeicher 12, während die nicht synchronisationsredundanten Kanten für die Registerkanalzuteilung weiter analysiert werden.
In Schritt 48 wird ein Zweig erzeugt, der bei der ersten Reiteration oder dem ersten Durchlauf auf Schritt 50 übergeht, in dem die Anwärter unter den nichtsynchronisationsredundanten Kanten für die Kanaiwiederverwendung, die nicht wie in den Abbildungen 6a und 6b implizite Synchronisationen erzeugen, identifiziert und für die Wiederverwendung der Kanäle vorgesehen werden. Außer bei der ersten Iteration bewirkt der Zweig in Schritt 48 die Umgehung von Schritt 50, da diese Anwärter bereits für die Kanalwiederverwendung zugewiesen wurden. Danach wird in Schritt 52 bestimmt, ob die verbleibende Anzahl nicht-synchronisationsredundanter Kanten die Anzahl verbleibender, für eine Zuweisung verfügbarer Kanäle übersteigt. Wenn nicht werden die verbleibenden Kanten in Schritt 54 vorgesehen. Wenn jedoch mehr Kanten als verfügbare Kanäle verbleiben wird Schritt 56 vorgenommen, in dem ein weiterer Anwärter zur Kanalwiederverwendung identifiziert wird. Diese Anwärter entsprechen dem Typ von Abbildung 7. Danach wird die dabei erzeugte implizite Synchronisation in Schritt 58 hinzugefügt, und die Schritte werden ab Schritt 42 wiederholt, wobei weitere implizierte Synchronisationen aufgrund der hinzugefügten impliziten Synchronisationen hinzugefügt werden, und dann werden in Schritt 44 die dabei synchronisationsredundant gewordenen Kanten in Schritt 46 identifiziert und vorgesehen. Hieraus sollte ersichtlich werden, daß dieses Verfahren allgemein über die Zuweisung von Kanten an Registerkanäle unter der Voraussetzung eine vollständige Synchronisation ermöglicht, daß die Anzahl Registerkanäle für die Anforderungen eines typischen Programms ausreicht. Dementsprechend wird hier ein Anwendungsbeispiel der Grundlagen der Erfindung an einem typischen sequentiellen Programm in Verbindung mit den Abbildungen 11 und 12 beschrieben.
Abbildung 11 ist eine gelenkte azyklische Graphik (GAG) eines typischen Programms. Es ist die innere Schleife des Programms "ENTCAF and ENTRE: Evaluation of Normalized Taylor Coefficients of an Analytic Function", CACM 14 (10, Oktober 1971, S.669-675). Diese GAG ist von Thomas L. Rodeheffer, "COMPILING ORDINARY PROGRAMS FOR EXECUTION ON AN ASYNCHRONOUS MULTIPROCESSOR", Ph. D. Dissertation, Carnegie-Mellon University 1985.
Abbildung 12 zeigt die Neuanordnung der GAG von Abbildung 11 in vier Ströme S&sub1;-S&sub4; wobei die Knoten in den Strömen in Übereinstimmung mit den Grundlagen der vorliegenden Erfindung angeordnet sind. Hier sollte bemerkt werden, daß nur 11 Interstromkanten erzeugt werden, von denen zwei synchronisationsredundant sind. Die neun nicht-synchronisationsredundanten Kanten werden von nur 6 Registerkanälen C&sub1;-C&sub6; hinsichtlich der zwei Wiederverwendungen von C&sub1; und der einen Wiederverwendung von C&sub2; erzwungen.
Im allgemeinen entspricht für ein unbekanntes Programm die Mindestanzahl erforderlicher Registerkanäle für die Gewährleistung der Synchronisation mindestens einer für das Schreiben verschiedener Werte von dem jeweiligen Prozessor und für das Lesen von einem anderen Prozessor erforderlichen Anzahl. Dies steht in folgendem Verhältnis:
Nc≥p(p-1),
wobei:
Nc = die Anzahl Kanäle und
p = die Anzahl Prozessoren sind.
Diese Mindestanzahl kann nicht ausreichend sein, um zu gewährleisten, daß kein Prozessor zum Schreiben gesperrt wird, weil ein Kanal noch nicht gelesen wurde. Die Höchstanzahl erforderlicher Kanäle für die Gewährleistung der Synchronisation liegt dem jeweiligen Programm zugrunde und hat folgende Obergrenze:
Nc≤Nb(p-1)/2,
wobei:
Nb die Anzahl Knoten im Basisblock des Programms ist.
Die Ergebnisse der Anwendung der Grundlagen der Erfindung zum Testen von Programmen führen zu der Empfehlung, daß p(p-1) Registerkanäle für die Synchronisation typischer Programme ausreichen.
Die vorliegende Erfindung wurde in bestimmten Details beschrieben, doch es sollte berücksichtigt werden, daß in solchen Detailbeschreibungen innerhalb des vorgesehenen Anwendungsbereichs der Erfindung, wie in den Ansprüchen Definiert, zahlreiche Änderungen, Einfügungen und Streichungen möglich sind. Um in Ströme vorgesehen zu werden müssen den Knoten z.B. nicht eine größere Höhe, sondern ihnen kann eine größere Höhe im Verhältnis zu der erwarteten Zeit zugewiesen werden, die die Operation in Anspruch nimmt. Somit hätte jeder Knoten eine Höhe, die seiner erhöhten Höhe plus der Höhe des größen Nachfahren entspricht.

Claims

1. Ein Übersetzungsverfahren für die Planung datenabhängiger Operationen, beschreibbar als eine azyklische Graphik mit Knoten, die Operationen darstellen und mit Kanten, die Datenabhängigkeiten darstellen, geleitet in eine Vielzahl an parallelen Instruktionsströme für die Verarbeitung durch eine Vielzahl an digitalen Prozessoren und für die Planung synchronisierter Datentransfers auf einer Vielzahl an Interprozessor-Datentransfermitteln, wobei die besagte Methode folgende Merkmale aufweist:

eine erste Planung der Knoten der besagten Graphiken in die besagte Vielzahl an Strömen, wobei jede Kante der besagten Graphiken entweder als eine Interstromkante oder Zwischenstromkante beschreibbar ist, die besagten Knoten werden derart vorgesehen, daß die Intrastromkanten in dieselbe Richtung gelenkt werden; eine erste Identifizierung der nicht-synchronisationsbedürftigen Kanten unter den besagten Interstromkanten; und

eine zweite Planung der nicht-synchronisationsbedürftigen Interstromkanten, wie Synchronisations-Datentransfers auf den besagten Interprozessor- Datentransfermitteln.

2. Die Methode von Anspruch 1, bei der zuerst die Planung auf eine Art vorgenommen wird, um die Anzahl an Interstromkanten grundlegend zu minimieren.

3. Die Methode von Anspruch 1, bei der die besagte Planung in umgekehrter Reihenfolge festgelegt wird und folgendes enthält:

eine zweite Identifizierung unter den nicht vorgesehenen Knoten der besagten Graphik einer Vielzahl an Knoten mit den relativ größten Höhen; und eine dritte Planung der Knoten der besagten zweiten identifizierten Vielzahl in verschiedene Ströme unter grundlegender Minimierung der Anzahl sich ergebender zu den vorgesehenen Knoten geleiteten Interstromkanten.

4. Die Methode von Anspruch 3, bei der die besagte erste Planung außerdem folgendes enthält:

eine dritte Identifizierung einer Vielzahl der an dritter Stelle vorgesehenen Knoten jeglicher mit den besagten Knoten verwurzelter Untergraphiken; und

eine vierte Planung, wenn möglich einer gleichen Anzahl an Knoten der jeweiligen dritten identifizierten Untergraphiken in dieselben jeweiligen Ströme wie die dritten vorgesehenen Knoten, verwurzelt mit den besagten jeweiligen Untergraphiken, wobei die besagte vierte Planung in absteigender Knotenhöhe der besagten dritten vorgesehenen Knoten vorgenommen wird.

5. Die Methode von Anspruch 4, bei der die besagte zweite Identifizierung nach der besagten vierten Planung wiederholt wird.

6. Die Methode von Anspruch 1, bei der die besagte Planung folgendes enthält:

eine zweite Identifizierung der besagten Zwischenstromkanten, die nicht synchronisationsredundant sind, wobei Kanten, die Datenabhängigkeiten aufweisen, in einer bestimmten Reihenfolge als Anwärter vorgesehen werden müssen, um über die Wiederverwendung derselben Interprozessor-Datentransfermittel aufgenommen zu werden.

7. Die Methode von Anspruch 6, wobei bei der besagten zweiten Identifizierung der Anwärter, die für die Wiederverwendung derselben Interprozessor- Datentransfermittel vorgesehen sind, bei die Wiederverwendung aufgrund der möglichen Schreibsperrung auf den besagten Datentransfermitteln keine impliziten Synchronisationen entstehen.

8. Die Methode von Anspruch 6 enthält außerdem:

eine dritte Identifizierung impliziter Synchronisationen aufgrund der möglichen Sperrung des Lesens auf wiederverwendeten Interprozessor-Datentransfermitteln; und eine vierte Identifizierung weiterer Jnterstromkanten, die durch die besagten impliziten Synchronisationen synchronisationsredundant werden würden.

9. Die Methode von Anspruch 1, bei der die besagte Planung in umgekehrter Reihenfolge vorgenommen wird und folgendes enthält:

eine erste Identifizierung unter den nicht vorgesehenen Knoten der besagten Graphik einer Vielzahl an Knoten mit relativ den größten Höhen in der besagten Graphik; und

eine zweite Planung von Knoten der besagten ersten identifizierten Vielzahl in verschiedene Ströme unter Minimierung der Anzahl sich ergebender, zu den vorgesehenen Knoten geleiteten Interstromkanten.

10. Die Methode von Anspruch 9 enthält außerdem:

eine zweite Identifizierung einer Vielzahl der an zweiter Stelle vorgesehenen Knoten jeglicher mit den besagten Knoten verwurzelter Untergraphiken;

und

eine dritte Planung, wenn möglich einer gleichen Anzahl an Knoten der jeweiligen zweiten identifizierten Untergraphiken in dieselben jeweiligen Ströme wie die dritten vorgesehenen Knoten, verwurzelt mit den besagten jeweiligen Untergraphiken, wobei die besagte vierte Planung in absteigender Knotenhöhe der besagten dritten vorgesehenen Knoten vorgenommen wird.

11. Die Methode von Anspruch 10, bei der die besagte erste Identifizierung nach der besagten dritten Planung wiederholt wird.

12. Eine Methode laut Anspruch 1, bei der die besagten Interprozessor- Datentransfermittel weiterhin als ein von den besagten Prozessoren zugänglicher Registerkanal definiert werden, wobei ein Synchronisationsbit anzeigt, ob in den besagten Registerkanal geschrieben wurde und die den besagten Prozessoren zugänglichen Speichermittel nicht über ein Synchronisationsbit verfügen, und eine Methode für die Übertragung einer Vielzahl an querstromabhängiger Daten zwischen den besagten Prozessoren auf synchronisierende Art, bestehend aus folgendem:

einem ersten Schreiben durch den besagten ersten Prozessor in die besagten Speichermittel, die ersten querstromabhängigen Daten sind dem besagten ersten Prozessor verfügbar;

einem zweiten Schreiben durch den besagten ersten Piozessor in den besagten Registerkanal, nicht vor dem besagten ersten Schreiben, die zweiten querstromabhängigen Daten sind dem besagten ersten Prozessor verfügbar;

dem Warten, falls erforderlich, des besagten zweiten Prozessors, bis das besagte Synchronisationsbit anzeigt, daß das besagte zweite Schreiben stattgefunden hat;

einem ersten Lesen von besagtem zweiten Prozessor der zweiten querstromabhängigen Daten aus besagtem Registerkanal; und

einem zweiten Lesen von besagtem zweiten Prozessor, nicht vor dem ersten Lesen, der ersten querstromabhängigen Daten aus den besagten Speichermitteln.

13. Eine Methode laut Anspruch 1 zur Verwendung mit dem ersten, zweiten und dritten Prozessor für die Durchführung sequentieller, in jeweils ersten, zweiten und dritten Instruktionsströmen mit Querstrom-Datenabhängigkeiten spezifizierten Operationen, die weiterhin die ersten und zweiten, von den besagten Prozessoren zugänglichen Registerkanäle definieren, die jeweils das Merkmal eines Synchronisationsbit aufweisen, das anzeigt, ob in den besagten Registerkanal geschrieben wurde, und von den besagten Prozessoren zugänglichen Speichermitteln, die nicht über ein Synchronisationsbit verfügen, wobei die Methode für die Übertragung einer Vielzahl an querstromabhängigen Daten zwischen den besagten Prozessoren auf synchronisierende Art aus folgendem besteht:

einem zweiten Schreiben durch den besagten ersten Prozessor in den besagten ersten Registerkanal, nicht vor dem besagten ersten Schreiben, die zweiten querstromabhängigen Daten sind dem besagten ersten Prozessor verfügbar;

einem ersten Warten, falls erforderlich, des besagten zweiten Prozessors, bis das besagte Synchronisationsbit des besagten ersten Registerkanals anzeigt, daß das besagte zweite Schreiben stattgefunden hat;

einem ersten Lesen von besagtem zweiten Prozessor der zweiten querstromabhängigen Daten aus besagtem ersten Registerkanal;

einem dritten Schreiben durch den besagten zweiten Prozessor in den besagten zweiten Registerkanal, nicht vor dem besagten zweiten Lesen, die dritten querstromabhängigen Daten sind dem besagten zweiten Prozessor verfügbar;

einem zweiten Warten, falls erforderlich, des besagten dritten Prozessors, bis das besagte Synchronisationsbit des besagten zweiten Registerkanals anzeigt, daß das besagte dritte Schreiben stattgefunden hat;

einem dritten Lesen von besagtem dritten Prozessor, nicht vor dem zweiten Lesen, der ersten querstromabhängigen Daten aus den besagten Speichermitteln.

14. Eine Methode laut Anspruch 1 zur Verwendung mit einer Vielzahl an parallelen Prozessoren für die Durchführung sequentieller, in jeweils einer Vielzahl an Instruktionsströmen mit Querstrom-Datenabhängigkeiten spezifizierten Operationen, die weiterhin eine Vielzahl an den besagten Prozessoren zugänglichen Registerkanäle für die Synchronisierung von zwischen den besagten Prozessoren verlaufenden Daten definieren, und den besagten Prozessoren zugängliche Speichermittel für zwischen den besagten Prozessoren verlaufende nicht synchronisierte Daten, wobei die Methode für die Übertragung einer Vielzahl an querstromabhängigen Daten zwischen den Prozessoren auf synchronisierte Art aus folgendem besteht:

einem ersten Schreiben durch einen der besagten Prozessoren in die besagten Speichermittel, die ersten querstromabhängigen Daten sind dem besagten ersten Prozessor verfügbar;

einem letzten Lesen der besagtem querstromabhängigen Daten aus den besagten Speichermitteln durch einen anderen der besagten Prozessoren; und

dem Erzwingen anderer Querstromdatenabhängigkeiten durch eine zeitliche Sequenz eines oder mehrerer Schreib-Lese-Paare in jeweiliger Verbindung mit einem oder mehreren Registerkanälen, wobei die besagte zeitliche Sequenz mit einem zweiten Schreiben in einen anderen Registerkanal beginnt, nicht vor dem besagten ersten Schreiben, und der Beendigung mit einem letzten Lesen aus demselben oder einem anderen Registerkanal, nicht später als das besagte letzte Lesen.