DE69232300T2

DE69232300T2 - Gerät zur Parallelverarbeitung und Verfahren zur Benutzung von Unterteilung

Info

Publication number: DE69232300T2
Application number: DE69232300T
Authority: DE
Inventors: Jacklin Kotikian; Linda Q. Lee; William F. Mann; Timothy G. Peters; Christopher L. Reeve; James B. Rothnie; Tani Shavit
Original assignee: Sun Microsystems Inc
Current assignee: Sun Microsystems Inc
Priority date: 1991-09-20
Filing date: 1992-09-16
Publication date: 2002-08-08
Anticipated expiration: 2012-09-17
Also published as: EP0533445A3; EP0533445B1; US5535393A; CA2078315A1; DE69232300D1; JPH05298272A; EP0533445A2; ATE211275T1

Description

Hintergrund der Erfindung

Die vorliegende Erfindung bezieht sich auf digitale Datenverarbeitung und genauer gesagt auf Verfahren und eine Vorrichtung zum Ausführen von Programmen auf parallel arbeitenden Computern.
Frühere Computer beruhten typischerweise auf einer einzigen Verarbeitungseinheit oder "CPU" (zentrale Prozessoreinheit), um Verarbeitungsfunktionen auszuführen. Quellcodeprogramme, die für diese Computer geschrieben wurden, wurden in eine Folge von Maschinenanweisungen bzw. -befehlen übersetzt, die dann einer nach dem anderen von der CPU ausgeführt wurden. Bei wiederholten Abfolgen von Schritten oder Schleifen, die in dem ursprünglichen Programm vorhanden waren, hat der einzelne Prozessor jede Anweisung in der Schleife aufgenommen und ein- und dieselben Anweisungen bzw. Befehle bei jeder Wiederholung der Schleife ausgeführt.
Der spätere Fortschritt hat es ermöglicht, einige Sätze von Anweisungen "parallel" zueinander auszuführen. Dieser Fortschritt, der als gleichzeitige Verarbeitung (Coprocessing) bezeichnet wurde, stellte neben der CPU einen Prozessor für einen speziellen Zweck bereit. Die Ausführung von Programmen auf solch einer Maschine wurde daher zwischen dem Coprozessor und der CPU aufgeteilt.
Mit dem Aufkommen von Computern mit mehreren Prozessoren wurde es möglich, vollständige Aufgaben getrennten, gleichzeitig arbeitenden CPUs zuzuordnen. Eine besondere Klasse dieser Mehrfachprozessoren, die als parallele Prozessoren bezeichnet werden, ist mit speziellen Synchronisationsmechanismen ausgerüstet und ist deshalb besonders für das gleichzeitige Ausführen von Abschnitten desselben Programms geeignet.
Die "Parallelisierung" des Ausführens von Computerprogrammen, so daß sie in effizienter Weise auf parallelen Prozessoren laufen können, ist eine anspruchsvolle Aufgabe. Zunächst muß man den Datenstrom und den Steuerstrom des Programms verstehen und diese müssen dann neu geordnet werden, um einen Satz von eindeutig aufteilbaren Aufgaben zu definieren. Die signifikantesten Verstärkungseffekte, die man bisher erreicht hat, lagen in der Neuanordnung der Ausführung von Schleifen, das heißt dem "Schleifenaustausch", der Synchronisation und (in begrenztem Maße) dem flächenhaften Aufteilen ("Kacheln" bzw. "Feldaufteilung").
In einem Artikel mit dem Titel "More Iteration Space Tiling" von Michael Wolfe, veröffentlicht in Proceedings Supercomputing '89, 13.-17. November 1989, (ACM order number 415892), Seiten 655-664 beschreibt dieser ein Verfahren zum Kompilieren eines Programms einschließlich einer iterativen Sequenz für die Ausführung auf einer Mehrzahl von Prozessoren. Das Verfahren umfaßt das Unterteilen des Iterationsraumes einer Schleife in Blöcke oder "Kacheln" bzw. "Felder" mit einer festen maximalen Größe. Die Felder werden zu einem natürlichen Kandidaten als Arbeitseinheit für die Planung von parallelen Aufgaben. Synchronisationen zwischen Prozessoren können zwischen Feldern vorgenommen werden, was die Synchronisationsfrequenz (unter einem gewissen Verlust der potentiellen Parallelität) reduziert. Die Größe und Form eines Feldes kann optimiert werden, um aus einer Speicherposition für die Ausnutzung der Speicherhierarchie Vorteil zu ziehen. Vektorisierung und Registerlokalität passen in das Optimierungsschema innerhalb eines Feldes, während Parallelität und Cachelokalität in den Optimierungsbereich zwischen Feldern gehört bzw. paßt. Ein Verfahren zum Kompilieren eines Programms umfaßt die Schritte, daß eine in Felder aufgeteilte Befehlssequenz erzeugt wird und daß Regeln für das Erzeugen von Grenzen zwischen den Feldern erzeugt werden, über welche hinweg die in Feldern aufgeteilte Sequenz ausgeführt werden soll.
Auch wenn viel Parallelisierungsarbeit von Hand vorgenommen wird, gehen neuere Entwicklungen dahin, diese Aufgabe zu automatisieren. Dies wird typischerweise durchgeführt in Verbindung mit dem Kompilierungsvorgang, der den Programmquellcode in Maschinencode umwandelt. Ein kommerziell verfügbares Produkt, der KAP/KAI-Vorprozessor, der von Kuck and Associates, Inc. aus Illinois erhältlich ist, führt einige dieser Funktionen durch. Insbesondere liefert dieser Vorprozessor Eigenschaften des Schleifenaustauschs und der Synchronisation.
In Anbetracht des Vorstehenden besteht eine Aufgabe der vorliegenden Erfindung darin, eine verbesserte Datenverarbeitungsvorrichtung und Verfahren zum parallelen Verarbeiten sowie einen Compiler (Übersetzer) bereitzustellen, um die Parallelisierung von Computerprogrammen zu ermöglichen.

Zusammenfassung der Erfindung

Gemäß einem Aspekt der Erfindung wird eine digitale Parallelprozessordatenverarbeitungsvorrichtung bereitgestellt, die eine Mehrzahl von Verarbeitungseinheiten hat, die jeweils für die Ausführung von Befehlen vorgesehen sind, wobei Speichereinrichtungen mit den Verarbeitungseinheiten verbunden sind, um zumindest entweder Daten und/oder Befehle zu speichern, und mit einer Interprozessorkommunikationseinrichtung, die mit der Verarbeitungseinheiten verbunden ist, um Information zwischen diesen zu übertragen, und wobei für das Verarbeiten einer iterativen Folge von Befehlen die Speichereinrichtung Einrichtungen für das Speichern einer in Kacheln bzw. Felder aufgeteilten Sequenz von Befehlen aufweist, welche die iterative Sequenz repräsentieren, und wobei jede Verarbeitungseinheit Einrichtungen umfaßt, um ihre Verfügbarkeit für das Ausführen der in Felder aufgeteilten Sequenz über einen Bereich eines Iterationsraumes anzuzeigen, der zu der iterativen Sequenz gehört, wobei der Bereich als ein "Feld" ("Kachel") bezeichnet wird, wobei die Vorrichtung eine Einrichtung für das nächste Feld aufweist, die mit den Verarbeitungseinheiten verbunden ist, um auf zumindest eine ausgewählte derartige Anzeige durch diejenigen Verarbeitungseinheiten zu reagieren, um ein Signal zu erzeugen, welches Grenzen eines Feldes entspricht, auf welchem die in Felder aufgeteilte Sequenz auszuführen ist, wobei jedes derartige Feld nicht mit irgendeinem anderen Feld überlappt, und wobei alle Felder gemeinsam den Iterationsraum abdecken, wobei die Einrichtung für das nächste Feld Einrichtungen für das Erzeugen von den Grenzen entsprechenden Signalen aufweist, die den Grenzen entsprechen, um den Ort eines Datensubjektes maximal zu machen, um während der Ausführung auf eines oder mehrere entsprechende Felder zuzugreifen, und um die Konkurrenz für den Zugriff auf derartige Daten während einer solchen Ausführung minimal zu machen, und wobei jede Verarbeitungseinheit Einrichtungen umfaßt, um auf ein den Grenzen entsprechendes Signal zu reagieren, welches in Reaktion auf die Anzeige der Verarbeitungseinheit zum Ausführen der in Felder aufgeteilten Sequenz über dem entsprechenden Feld erzeugt wird.
Gemäß einem anderen Aspekt der Erfindung wird ein Compiler von dem Typ bereitgestellt, der Programmsignale, welche einem Programm entsprechen, einschließlich einer iterativen Sequenz, aus dem Quellcodeformat in eine Codesequenz von Anweisungen in einem Objektcodeformat übersetzt, welches für das Laden zum Ausführen durch eine Mehrzahl paralleler digitaler Datenverarbeitungseinheiten geeignet ist, wobei der Compiler eine Abhängigkeitseinrichtung umfaßt, um eine Abhängigkeitsrichtung der iterativen Sequenz zu bestimmen, und um ein Signal zu erzeugen, welches dem entspricht, und eine Feldeinrichtung, um auf die iterative Sequenz im Quellcodeformat zu reagieren, um eine in Felder aufgeteilte Sequenz von Befehlen zu erzeugen, welche dieser in einem Objektcodeformat entspricht, und um weiterhin auf diese iterative Sequenz und auf keine, eine oder mehrere von einem Benutzer angegebene Signale zu reagieren, um eines oder mehrere Signale zu erzeugen, um Grenzen für eines oder mehrere Felder zu erzeugen, auf welchen die in Felder aufgeteilte Sequenz auszuführen ist.
Gemäß einem weiteren Aspekt der Erfindung wird ein Verfahren zum Betreiben einer digitalen Parallelprozessor-Datenverarbeitungsvorrichtung bereitgestellt, und zwar von dem Typ, der eine Mehrzahl von Verarbeitungseinheiten hat, die jeweils für die Ausführung von Anweisungen vorgesehen sind, wobei eine Speichereinrichtung mit den Verarbeitungseinrichtungen verbunden ist, um zumindest entweder Daten und/oder Anweisungen zu speichern, und mit einer Interprozessorkommunikationseinrichtung, die mit den Verarbeitungseinheiten verbunden ist, um zwischen diesen Informationen zu übertragen, wobei das Verfahren das Speichern einer in Felder aufgeteilten Sequenz von Befehlen aufweist, welche die iterative Sequenz repräsentieren, wobei für jeden Prozessor seine Verfügbarkeit für die Ausführung der in Felder aufgeteilten Sequenz über einem Bereich eines Iterationsraumes, der der iterativen Sequenz zugeordnet ist, angezeigt wird, wobei der betreffende Bereich als ein Feld bezeichnet wird, Reagieren auf jede von zumindest ausgewählten entsprechenden Anzeigen durch diese Verarbeitungseinheiten, um ein Signal zu erzeugen, welches Grenzen eines Feldes repräsentiert, auf welchem die in Felder aufgeteilte Sequenz auszuführen ist, wobei jedes derartige Feld nicht mit irgendeinem anderen Feld überlappt und wobei alle derartige Felder gemeinsam den Iterationsraum abdecken, Erzeugen von Grenzen entsprechenden Signalen, die Grenzen entsprechen, um den Ort bzw. Bereich von Daten maximal zu machen, welche während der Ausführung von einem oder mehreren entsprechenden Feldern einem Zugriff ausgesetzt sind, und um die Konkurrenz für den Zugriff auf derartige Daten während einer solchen Ausführung minimal zu machen, und wobei jeder Prozessor auf ein Grenzen entsprechendes Signal reagiert, welches in Reaktion auf die Anzeige durch diese Prozessoreinheit erzeugt wurde, um die in Felder aufgeteilte Sequenz über dem entsprechenden Feld auszuführen.
Gemäß einem weiteren Aspekt der Erfindung wird ein Verfahren zum Betreiben eines Compilers bereitgestellt, und zwar von dem Typ für das Übersetzen von Programmsignalen, welche einem Programm, einschließlich einer iterativen Sequenz, entsprechen, von einem Quellcodeformat in eine Codesequenz von Befehlen in einem Objektcodeformat, das für das Laden zum Ausführen durch eine Mehrzahl von parallelen digitalen Datenverarbeitungseinheiten geeignet ist, wobei der Compiler eine Abhängigkeitseinrichtung aufweist, um eine Abhängigkeitsrichtung der iterativen Sequenz zu bestimmen, und um ein dementsprechendes Signal zu erzeugen, wobei das Verfahren das Reagieren auf die iterative Sequenz im Quellcodeformat aufweist, um eine in Felder aufgeteilte Sequenz von Befehlen zu erzeugen, die derselben im Objektcodeformat entspricht, und um weiterhin auf diese iterative Sequenz sowie auf keines, eines oder mehrere benutzerspezifische Signale zu reagieren, um eines oder mehrere Signale zu erzeugen, um Grenzen für eines oder mehrere Felder zu erzeugen, auf welchen die in Felder aufgeteilte Sequenz ausgeführt werden soll.
Eine Ausführungsform der Erfindung stellt einen verbesserten Parallelprozessor zum Ausführen einer iterativen Sequenz von Anweisungen bereit, indem die Sequenz in Teilaufgaben angeordnet wird und diese den Prozessoren zugeordnet werden. Diese Aufteilung und Zuordnung wird in einer solchen Art und Weise ausgeführt, daß die Datenkonkurrenz zwischen den Prozessoren minimal gemacht wird und die Lokalität bzw. Nähe der Daten zu den Prozessoren, welche auf die Daten zugreifen, maximal gemacht wird.
Eine Ausführungsform der Erfindung stellt einen verbesserten Prozessor des Typs bereit, der eine Mehrzahl von Verarbeitungseinheiten hat, die jeweils für das Ausführen von Anweisungen vorgesehen sind, einen Speicher für das Speichern von Daten und Befehlen, und einen Mechanismus für das Ermöglichen der Kommunikation zwischen den Prozessoren hat. Der Speicher kann selbst eine Mehrzahl von Speicherelementen enthalten, die jeweils in der Lage sind, Daten und Befehle zu speichern. Der Kommunikationsmechanismus kann beispielsweise ein Anzeigeprotokoll sein, welches gemeinsame Bereiche des Speichers verwendet.
Eine in Felder aufgeteilte Sequenz von Anweisungen bzw. Befehlen, welche der iterativen Sequenz entsprechen, ist in dem Speicher gespeichert. Weiterhin zeigt jeder Prozessor seine Verfügbarkeit für das Ausführen eines Bereiches der in Felder aufgeteilten Sequenz an. Außerdem reagiert ein nächstes Feldelement auf diese Signalisierung durch Erzeugen eines Signals, welches den Grenzen eines "Feldes" entspricht -, das heißt ein Bereich eines Iterationsraumes, welcher der iterativen Sequenz zugeordnet ist. Der Signalgebungsprozessor führt dann die in Felder aufgeteilte Sequenz über diesem Feld aus.
Die durch das nächstes-Feld-Element erzeugten Felder bzw. Blöcke überlappen einander nicht, jedoch decken alle Felder bzw. Blöcke gemeinsam den Iterationsraum ab (füllen den Iterationsraum ohne Überlappung aus). Wie oben bereits erwähnt, werden diese Felder so erzeugt, daß sie die Datenkonkurrenz zwischen den Prozessoren minimal machen, während sie die Lokalität bzw. Nähe von Daten zu diesen maximal macht.
Ein Parallelprozessor, wie er oben beschrieben wurde, kann eine Feldaufbaueinrichtung aufweisen, die ein Feldformsignal erzeugt, welches die Maße innerhalb des Iterationsraumes für die Felder definiert. Beispielsweise kann ein Iterationsraum definiert werden durch die Indizes (i) und (j), wobei (i) von 1 bis 100 reicht und wobei (j) von 1 bis 25 reicht. Ein Feld für einen solchen Raum kann so definiert werden, daß es 16 Schritte entlang (i) und 25 Schritte entlang (j) abdeckt. Demnach teilt man den Iterationsraum in 6 Felder gleicher Größe (das heißt mit je 16 Schritten) und ein kleineres Feld (das heißt mit 4 Schritten) entlang einer Kante auf.
Die Feldaufbaueinrichtung erzeugt das Feldformsignal in Anbetracht der Abhängigkeit, die zwischen den sich ergebenden Feldern vorliegt. Abhängigkeit in dieser Hinsicht ist eine Eigenschaft zwischen Feldern, die sich auf die Beziehung zwischen diesen bezüglich der Daten bezieht, auf welche sie zugreifen, so daß die serielle Ausführungsreihenfolge erhalten wird, soweit es darauf ankommt. Wenn beispielsweise das erste Feld einen Datenwert schreiben muß, bevor er von einem zweiten Feld gelesen werden kann, so sagt man, daß das zweite Feld von dem ersten abhängt.
Genauer gesagt liegt eine Datenabhängigkeit zwischen zwei Feldern vor, wenn
(i) ein Befehl in dem ersten Feld einen ausgewählten Datenwert schreibt, welchen ein Befehl in dem zweiten Feld anschließend liest,
(ii) ein Befehl in dem ersten Feld einen ausgewählten Datenwert liest, den ein Befehl in dem zweiten Feld nachfolgend schreibt, oder
(iii) ein Befehl in dem ersten Feld einen ausgewählten Datenwert schreibt, welchen ein Befehl in dem zweiten Feld ebenfalls nachfolgend schreibt.
Ein vollständigeres Verständnis der Abhängigkeit selbst kann man erhalten unter Bezug auf Wolfe, Optimizing Supercompilers for Supercomputers (The MIT Press, 1989).
Die Feldaufbaueinrichtung optimiert unter anderem die Speicherausnutzung. Beispielsweise kann sie eine Speicherform auswählen, welche die Anzahl individueller Datenwerte minimal macht, die einem Zugriff vom Schreibtyp durch unterschiedliche der Felder ausgesetzt sind, um Datenbewegung minimal zu machen. Weiterhin kann er, um die Konkurrenz minimal zu machen, diejenige Feldform wählen, welche die Anzahl von individuellen Daten minimal macht, welche einem Zugriff vom Schreibtyp durch mehrere gleichzeitig arbeitende Felder ausgesetzt sind.
Gemäß einem anderen Aspekt erzeugt die Feldaufbaueinrichtung eines Parallelprozessors wie oben beschrieben ein "Affinitäts"-Signal (oder "SSB"), welches eine Abfolge für die Feldausführung repräsentiert, die die Übertragung von Daten zwischen den Prozessoren minimal macht.
Die Feldform wird als Funktion mindestens einer Abhängigkeitsrichtung der Felder, eines Affinitätssignals (SSB), einer Abschätzung des Aufwands (das heißt der Anzahl von Maschinenzyklen) des Ausführens der Felder, der Größe des Iterationsraumes, der Anzahl der für die Ausführung der in Felder aufgeteilten Sequenz verfügbaren Prozessoren, und in Abhängigkeit davon erzeugt ob die Felder innerhalb eines "Affinitätsbereiches" liegen, das heißt eines Bereiches des Programms, wo der Iterationsraum durch eine Vielzahl von Feldsequenzen definiert ist anstatt durch eine einzelne.
Eine Ausführungsform eines Parallelprozessors gemäß der Erfindung umfaßt ein Feldstrategieelement, welches die Art und Weise und Abfolge für das Erzeugen von Feldern aus einem Satz von Strategien auswählt. Das Feldstrategieelement erzeugt ein entsprechendes Signal, auf welches das Element für das nächste Feld mit der Erzeugung von Feldern reagiert.
Eine "Scheiben"-Strategie teilt den Iterationsraum durch die Anzahl verfügbarer Prozessoren. Jeweils eines dieser Felder wird einem entsprechenden der Prozessoren zugeordnet. Wenn es zehn Prozessoren gibt, hat man also zehn Felder: das erste Feld wird dem ersten Prozessor zugeordnet, das zweite Feld dem zweiten Prozessor usw.
Diese Strategie wird gewählt, wenn es keine Datenabhängigkeit zwischen den sich ergebenden Feldern gibt. Auch wenn es nur eine geringe Affinität zwischen ihnen gibt - das heißt wenn nur wenige Daten, auf welche durch einen von ihnen zugegriffen wird (sei es zum Lesen oder zum Schreiben), auch von einem anderen zugegriffen wird.
Eine "Modulo"-Strategie teilt den Iterationsraum in eine Anzahl von Feldern auf, die größer sein kann als die Anzahl verfügbarer Prozessoren, und ordnet die sich ergebenden Felder auf der Basis des Modulus der Feldzahl zu. Wenn es demnach drei verfügbare Prozessoren und neun Felder gibt, unabhängig von dem Zeitablauf ihrer Verfügbarkeit, so werden dem ersten Prozessor die Felder 1, 4 und 7, dem zweiten Prozessor die Felder 2, 5 und 8 und dem dritten Prozessor die Felder 3, 6 und 9 zugeordnet.
Diese Strategie wird ebenfalls ausgewählt, wenn es keine Abhängigkeit und nur geringe Affinität zwischen den Feldern gibt. Zusätzlich wird diese Strategie ausgewählt, wenn die sich ergebenden Felder und die Feldzuordnungen die Wiederverwendung von Daten durch jeden der Prozessoren maximal macht, selbst wenn sich die Größe des Iterationsraums verändert.
Eine "Wellenfront"-Strategie teilt den Iterationsraum ebenso in der Weise auf, daß es mehr Felder als verfügbare Prozessoren geben kann. Sie wird ausgewählt, wenn die sich ergebenden Felder eine Datenabhängigkeit zeigen und dementsprechend die Felder in einer Abfolge erzeugt werden müssen, die durch die Abhängigkeitsrichtung der Felder vorgegeben ist.
Gemäß einem Beispiel kann es sein, daß ein erstes Feld vor einem zweiten Feld und einem dritten Feld ausgeführt werden muß. Gemäß der Wellenfrontstrategie würde, selbst wenn gleichzeitig drei Prozessoren für die Aufnahme der Felder verfügbar wären, nur einer von ihnen ein Feld erhalten. Insbesondere würde das erste Feld für die Ausführung einem Prozessor zugeordnet werden. Nur nachdem dieses vollendet ist, könnten die zweiter; und dritten Felder auf der Basis der Ergebnisse der Ausführung des ersten Feldes ausgeführt werden.
Eine Modulo-Wellenfront-Strategie teilt den Iterationsraum auf und ordnet die Felder sowohl gemäß der Modulo- als auch bezüglich der Wellenfront-Strategie auf. Diese Strategie wird gewählt, wenn es eine Datenabhängigkeit zwischen den Feldern gibt und wenn eine Datenwiederverwendung durch die Prozessoren maximal gemacht werden kann, und zwar wiederum selbst dann, wenn sich eine Änderung in der Größe des iterativen Raumes ergibt.
Eine "Ergreifungs"-Strategie ("Grab"-Strategie) teilt den Iterationsraum ebenfalls so auf, daß es mehr Felder als verfügbare Prozessoren gibt. Die sich ergebenden Felder werden den anfordernden Prozessoren nach dem Prinzip "wer zuerst kommt, mahlt zuerst" (first-come-first-served) zugeordnet. Im Gegensatz zu den Modulo- und Wellenfront-Strategien wird diese Strategie verwendet, wenn es keine Abhängigkeit und nur geringe Affinität zwischen den Feldern gibt. Sie ermöglicht einen Lastausgleich bzw. eine Lastverteilung zwischen den Prozessoren.
Zusätzlich zu den oben diskutierten Bedingungen kann das Feldstrategieelement irgendeine der vorstehenden Strategien je nach Anforderung des Benutzers auswählen.
Ein Parallelprozessor, wie er oben beschrieben wurde, kann ein Affinitätsbereich- Aufbauelement umfassen, um einen Iterationsraum zu definieren, der mehr als eine in Felder aufgeteilte Sequenz aufweist. Zusätzlich zum Erzeugen eines Signals, welches diesen Bereich repräsentiert, kann dieses Element außerdem ein Signal erzeugen, welches ein Maß bzw. die Dimension des Feldes definiert, ein Signal, welches eine Sequenz definiert sowie eine Art und Weise zum Erzeugen von Feldern, und ein Signal, welches definiert, welche Prozessoren die Felder ausführen sollen.
Nach einem weiteren Aspekt liefert die Erfindung einen verbesserten Compiler des Typs, der ein Computerprogramm in einen Objektcode übersetzt, welcher geeignet ist, um für die Ausführung durch eine Mehrzahl von parallelen Prozessoren geladen zu werden.
Ein Felderzeugungselement erzeugt eine in Felder aufgeteilte Sequenz von Anweisungen, welche eine iterative Folge in dem Quellprogramm repräsentieren. Das Felderzeugungselement erzeugt außerdem Signale, die einen Rahmen für die Verwendung in einem parallelen Prozessor des Typs bereitstellen, der oben beschrieben wurde, um Felder zu definieren und zu erzeugen, auf welchen die in Felder aufgeteilte Sequenz in der Laufzeit auszuführen ist. In dieser Hinsicht reagiert das Feld- bzw. Felderzeugungselement auf die iterative Abfolge ebenso wie auf vom Benutzer definierte Parameter.
Das Feldelement kann einen Parallelisierer aufweisen, der auf die Abhängigkeitsrichtung der iterativen Sequenz reagiert, ebenso wie auf die Sequenz selbst, um Indizes in dem Iterationsraum auszuwählen, auf welchen die in Felder aufgeteilte Sequenz auszuführen ist. Der Parallelisierer kann automatisch die Indizes für die Felderzeugung auf dieser Basis auswählen. Während der Parallelisierer durch den Benutzer definierte Vorzugswerte für diese Indizes annehmen kann, vergleicht er sie mit den automatisch gekennzeichneten, um deren Machbarkeit sicherzustellen.
Ein wie oben definierter Compiler kann außerdem einen Optimierer für das Erzeugen eines Affinitätssignals (SSB) aufweisen, der eine Feldausführungssequenz repräsentiert, die eine Übertragung von Daten minimal macht, welche irgendeinem Zugriff vom Lese- oder Schreibtyp während der Ausführung der Sequenz in mehreren Feldern ausgesetzt sind.
Der Optimierer kann auch ein Affinitätsbereichssignal erzeugen, welches eine oder mehrere Iterationssequenzen in dem Quellprogramm kennzeichnet, die auf dieselben Daten zugreifen. Während der Optimierer ebenfalls vom Benutzer definierte Affinitätsbereiche annehmen kann, vergleicht er sie mit den automatisch gekennzeichneten, um zu überprüfen, ob die vom Benutzer definierten Bereiche vernünftig sind.
Der Optimierer kann den Aufwand bestimmen, der mit der Ausführung einer in Felder aufgeteilten Sequenz verknüpft ist und kann ein Signal erzeugen, welches diesem entspricht.
Ein einen Aufruf erzeugendes Element innerhalb des Compilers kann die iterative Sequenz in dem Quellcode durch eine Anweisung ersetzen, die einen Aufruf an ein einen Code aussendenden Unterprogramm repräsentiert. Ein Laufzeitelement kann den Aufruf ausführen, um die Ausführung der in Felder aufgeteilten Sequenz durch die Prozessoren auszulösen.
Diese und andere Aspekte der Erfindung ergeben sich deutlich aus den Figuren und der Beschreibung, die sich nunmehr anschließt.

Kurze Beschreibung der Figuren

Ein vollständigeres Verständnis der Erfindung kann man unter Bezug auf die Figuren erhalten, von denen:
Fig. 1 und 2 die Struktur eines Mehrprozessorsystems für die Verwendung in einer bevorzugten Anwendung der Erfindung zeigen,
Fig. 3 die Module zeigt, welche für die Parallelisierung und Ausführung von Softwareprogrammen einschließlich iterativer Sequenzen verwendet werden,
Fig. 4A-4D Schleifentabellen zeigen, die durch den Vorprozessor 60a gemäß Fig. 3 erzeugt wurden,
Fig. 5 bevorzugte Anweisungen und Vorgaben für den Vorprozessor 60a nach Fig. 3 zeigt,
Fig. 6 die Umgebungsparameter während der Laufzeit für die Verwendung bei der Ausführung des Systems nach Fig. 3 zeigt,
Fig. 7 die Transformation eines Feldes in ein Aufgabenunterprogramm veranschaulicht,
Fig. 8 eine teilweise Feldordnung durch das System nach Fig. 3 zeigt,
Fig. 9A-9C Arbeitspläne zeigen, die durch das System nach Fig. 3 ausgearbeitet wurden, um eine in Felder aufgeteilte Sequenz auszuführen, und
Fig. 10 ein Blockdiagramm einer Laufzeitbibliothek 66 nach Fig. 3 auf einer höheren Ebene ist.

Genaue Beschreibung der dargestellten Ausführungsformen

Fig. 1 zeigt ein bevorzugtes Mehrprozessorsystem, welches für die Anwendung der vorliegenden Erfindung verwendet wird. Das dargestellte System 10 umfaßt drei Informationsübertragungsniveaus: Niveau:0, Niveau:1 und Niveau:2. Jedes Informationsübertragungsniveau umfaßt eines oder mehrere Niveausegmente, die durch ein Buselement und eine Mehrzahl von Schnittstellenelementen gekennzeichnet sind. Insbesondere umfaßt das Niveau:0 des dargestellten Systems 10 sechs Segmente, die mit 12A, 12B, 12C, 12D, 12E und 12F gekennzeichnet sind. In ähnlicher Weise umfaßt das Niveau:1 Segmente 14A und 14B, während das Niveau:2 das Segment 16 aufweist.
Jedes Segment des Niveaus:0, das heißt die Segmente 12A, 12B, ... 12F weist eine Mehrzahl von Verarbeitungszellen auf. Beispielsweise umfaßt das Segment 12A die Zellen 18A, 18B und 18C, das Segment 12B umfaßt die Zellen 18D, 18E und 18F, usw. Jede dieser Zellen weist eine zentrale Verarbeitungseinheit (Prozessoreinheit) und ein Speicherelement auf, die entlang eines intrazellulären Prozessorbusses (nicht dargestellt) miteinander verbunden sind. Gemäß der bevorzugten Ausführung der Erfindung speichert das Speicherelement, welches in jeder Zellen enthalten ist, alle Steuer- und Datensignale, die durch ihre zugeordnete zentrale Verarbeitungseinheit verwendet werden.
Bestimmte Zellen des Verarbeitungssystems 10 sind mit sekundären Speichereinrichtungen verbunden. In dem dargestellten System ist beispielsweise die Zelle 18C mit einem Plattenlaufwerk 19A verbunden, die Zelle 18D ist mit dem Plattenlaufwerk 19B verbunden und die Zelle 180 ist mit dem Plattenlaufwerk 19C verbunden. Die Plattenlaufwerke 19A-19C sind konventionelle Modelle und können aus verschiedenen kommerziell erhältlichen Geräten ausgewählt werden. Es versteht sich, daß sekundäre Speichergeräte, die keine Plattenlaufwerke sind, z. B. Bandlaufwerke, ebenso zum Speichern von Information verwendet werden können.
Fig. 2 zeigt die Verarbeitungszellen und ihre Verbindung innerhalb des Prozessorsystems nach Fig. 1 genauer. In der Zeichnung sind mehrere zentrale Prozessoreinheiten 40A, 40B und 40C jeweils mit zugehörigen Speicherelementen 42A, 42B und 42C verbunden. Die Verbindungen zwischen den Verarbeitungs- und Speichereinheiten jedes Paares werden entlang von Bussen 44A, 44B und 44C ausgeführt, wie dargestellt. Das Netzwerk 46, welches die zuvor erwähnten Niveausegmente und Routingzellen repräsentiert, überträgt Informationspakete (die über Busse 48A, 48B und 48C an das Netzwerk 46 geleitet werden) zwischen den dargestellten Verarbeitungszellen 42A- 42C.
In der dargestellten Ausführungsform weisen die zentralen Verarbeitungseinheiten 40A, 40B und 40C jeweils ein Zugriffsanforderungselement auf, welches mit 50A, 50B bzw. 50C bezeichnet ist. Diese Zugriffsanforderungselemente erzeugen Anforderungen für einen Zugriff auf Daten, die in den Speicherelementen 42A, 42B und 42C gespeichert sind. Unter den Zugriffsanforderungssignalen, die durch die Elemente 50A, 50B und 50C erzeugt werden, befindet sich die Besitzanforderung, welche eine Anforderung nach einem exklusiven, modifizierenden Zugriff auf einen Datenwert repräsentiert, der in den Speicherelementen gespeichert ist. In einer bevorzugten Ausführungsform weisen die Zugriffsanforderungselemente 50A, 50B und 500 einen Teilsatz eines Befehlssatzes auf, der auf den CPUs 40A, 40B und 40C implementiert ist. Dieser Befehlsteilsatz wird unten beschrieben.
Die zentralen Verarbeitungseinheiten 40A, 408, 40C arbeiten unter der Steuerung eines Betriebssystems 51, von welchem Teile 51A, 51B und 51C auf entsprechenden der zentralen Verarbeitungseinheiten laufen. Das Betriebssystem 51 liefert eine Schnittstelle zwischen Anwendungsprogrammen, die auf den zentralen Verarbeitungseinheiten laufen und den Objekten bzw. Elementen des Systems 10 und umfaßt ein virtuelles Speicherverwaltungssystem für das Verwalten von Datenzugriffen und Zuordnungen.
Ein bevorzugtes Betriebssystem für die Steuerung der zentralen Verarbeitungs- bzw. Prozessoreinheiten 40A, 40B und 40C ist ein UNIX-artiges Betriebssystem und noch bevorzugter OSF/1, welches gemäß der hier gegebenen Lehre modifiziert ist.
Die Speicherelemente 42A, 42B und 42C umfassen Cachesteuereinheiten 52A, 52B bzw. 52C. Jede dieser Cachesteuereinheiten bildet eine Schnittstelle zu einem Datenspeicherbereich 54A, 54B und 54C über ein entsprechendes Verzeichniselement 56A, 56B und 56C, wie dargestellt.
Die Speicher 54A, 54B und 54C werden durch das dargestellte System verwendet, um physikalischen Speicherraum für Daten und Anweisungssignale bereitzustellen, die von ihren entsprechenden zentralen Prozessoreinheiten benötigt werden.
Ein weitergehendes Verständnis des Aufbaus und der Arbeitsweise des dargestellten digitalen Datenverarbeitungssystems 10 kann man unter Bezug auf die folgenden gleichzeitig anhängigen und auf denselben Anmelder übertragenen Anmeldungen erhalten, deren Lehre hier durch diese Bezugnahme übernommen wird:
1) US-Patentanmeldung Seriennr. 136,930, eingereicht am 22. Dezember 1987 (Anwaltsaktenzeichen: KSP-001), mit dem Titel "MULTIPROCESSOR DIGITAL DATA PROCESSING SYSTEM",
2) US-Patentanmeldung Seriennr. 696,291, eingereicht am 20. Mai 1991 (Anwaltsaktenzeichen: KSD-002C2),
3) US-Patentanmeldung Nr. 370,325 (Anwaltsaktenzeichen: KSP-006), eingereicht am 22. Juni 1989 mit dem Titel "MULTIPROZESSORSYSTEM MIT MEHREREN BE-FEHLSQUELLEN",
4) US-Patentanmeldung Nr. 370,341 (Anwaltsaktenzeichen Nr. KSP-007), eingereicht am 22. Juni 1989 mit dem Titel "IMPROVED MEMORY SYSTEM FOR A MULTIPROCESSOR",
5) US-Patentanmeldung Nr. 370,287 (Anwaltsaktenzeichen Nr. KSP-007CP), eingereicht am 22. Juni 1989 mit dem Titel "IMPROVED MULTIPROCESSOR SYSTEM",
6) US-Patentanmeldung Nr. 499,182 (Anwaltsaktenzeichen Nr. KSP-014), eingereicht am 26. März 1990 mit dem Titel "HIGH-SPEED PACKET SWITCHING APPARATUS AND METHOD",
7) US-Patentanmeldung Nr. 521,798 (Anwaltsaktenzeichen Nr. KSP-011), eingereicht am 10. Mai 1990 mit dem Titel "DYNAMIC PACKET ROUTING NETWORK",
8) US-Patentanmeldung Nr. 526,396 (Anwaltsaktenzeichen Nr. KSP-015), eingereicht am 18. Mai 1990 mit dem Titel "PACKET ROUTING SWITCH",
9) US-Patentanmeldung Nr. 531,506 (Anwaltsaktenzeichen Nr. KSP-016), eingereicht am 31. Mai 1990 mit dem Titel "DYNAMIC HIERARCHICAL ASSOCITATIVE MEMORY",
10) US-Patentanmeldung Nr. _ (Anwaltsaktenzeichen Nr. KSD-043), eingereicht am gleichen Tag wie die vorliegende Anmeldung, mit dem Titel "DIGITAL DATA PROCESSOR WITH IMPROVED PAGING",
11) US-Patentanmeldung Nr._ (Anwaltsaktenzeichen Nr. KSD-044), eingereicht am gleichen Tag wie die vorliegende Anmeldung, mit dem Titel "DIGITAL DATA PROCESSOR WITH IMPROVED CHECKPOINTING & FORKING", und
12) US-Patentanmeldung Nr._ (Anwaltsaktenzeichen Nr. KSD-045), eingereicht am gleichen Tag wie die vorliegende Anmeldung, mit dem Titel "IMPROVED DIGITAL DATA PROCESSOR WITH DISTRIBUTED MEMORY SYSTEMS".

Codeparallelisierung und Ausführung

Fig. 3 zeigt eine bevorzugte Anordnung von Softwaremodulen, die in dem digitalen Datenprozessor 10 für eine Parallelisierung und Ausführung von Softwareprogrammen verwendet werden, welche iterative Sequenzen enthalten. Ein Kompilierungssystem 60 übersetzt Quellcodeeingaben in Objektcode. Der Quellcode kann in einem konventionellen Format geschrieben sein, z. B. als Quelldatei der Programmiersprachen Fortran 77 oder Fortran 90 oder C und enthält typischerweise iterative Sequenzen oder "Schleifen". Zusätzlich zu konventionellen Programmieraussagen kann der Quellcode durch den Benutzer spezifizierte Anweisungen für eine Parallelisierung enthalten. Diese Direktiven werden vorzugsweise als "Kommentare", das heißt nicht ausführbare Aussagen bereitgestellt. Um sie von konventionellen Kommentaren zu unterscheiden (die typischerweise als erläuternder Text verwendet werden), haben die Direktiven bzw. Anweisungen vorzugsweise ein spezielles Format, wie es im folgenden noch genauer diskutiert wird.
Das Kompilierungssystem 60 umfaßt einen Vorprozessor 60a und einen Compiler 60b. Der Vorprozessor 60a führt vorab eine vorläufige Analyse der iterativen Sequenzen in dem Sourcecode aus, um die Abhängigkeitsrichtungen derselben zu bestimmen und führt auch gewisse Schleifenaustausche aus. Der Vorprozessor 60a erzeugt ebenfalls Direktiven von dem oben beschriebenen Typ und für die Verwendung durch den Compiler 60b. Techniken für die Bestimmung einer Abhängigkeitsrichtung und Schleifenaustausche sind bekannt. Modifizierungen dieser bekannten Techniken für eine verbesserte Parallelisierung von iterativen Sequenzen werden im folgenden noch beschrieben.
Der Compiler 60b des Kompilierungssystems 60 übersetzt Programmaussagen aus dem vorverarbeiteten Quellcodeformat in das Objektcodeformat. Zusätzlich zum Übersetzen von konventionellen Codes konvertiert der Compiler 60b iterative Sequenzen in dem vorverarbeiteten Quellcode in "in Felder aufgeteilte" Sequenzen für die Verwendung bei einer parallelen Ausführung. Dieser Vorgang wird als "Feldaufteilung" bezeichnet und wird teilweise durch die durch den Vorprozessor 60a erzeugten Direktiven gesteuert, ebenso wie durch diejenigen, die in dem Quellcode 62 selbst enthalten sind.
Der durch das Kompilierungssystem 60 ausgegebene Objektcode wird über einen Verknüpfungseditor 64 mit einer Laufzeitbibliothek 66 verknüpft, um einen Code zu erzeugen, der für die Ausführung auf dem digitalen Datenprozessor 10 geeignet ist. Im folgenden wird ein bevorzugter Vorprozessor 60a beschrieben. Auch wenn die Techniken auf eine Vielfalt von Softwaresprachen anwendbar sind, wie z. B. die Programmiersprachen Fortran 77 oder 90 und C, bezieht sich die folgende Diskussion auf die Übersetzung des Quellcodes Fortran 77.
Die nachstehend beschriebenen Techniken können so angepaßt werden, daß sie in Verbindung mit früher bekannten Vorverarbeitungssystemen #arbeiten - insbesondere können sie so angepaßt werden, daß sie die Abhängigkeitsrichtung von #terativen Sequenzen des Quellcodes in der unten beschriebenen Weise bestimmen. Solche früheren Systeme umfassen den kommerziell erhältlichen KAP/KAI-Vorprozessor von Kuck and Associates aus Illinois, ebenso wie Vorprozessoren, die von Pacific Sierra erhältlich sind (das heißt der "am meisten verbreitete" Vorprozessor).

Der Vorprozessor

1. Überblick

Die Hauptaufgabe des Vorprozessors 60a besteht darin, Annotationen in ein Vorprogramm zu setzen, die eine parallele Ausführung ermöglichen, das heißt Feldaufteilungsrichtlinien einzufügen. Der Vorprozessor 60a führt optional auch einige Transformationen des Codes aus, wie z. B. einen Schleifenaustausch, entweder um die Feldaufteilung zu ermöglichen oder zum Zwecke der Optimierung.
In der dargestellten Ausführungsform ist der Vorprozessor 60a eine Fortran-Programmquelle und seine primäre Ausgangsgröße ist ebenfalls ein Fortran-Programm, wenn auch ein "vorverarbeitetes" -, welches die Feldaufteilungsanweisungen enthält. Dieses zweite Programm ist ein gültiges und korrektes Fortran-Programm, welches, wenn es seriell ausgeführt wird, dieselben Ergebnisse liefert wie das ursprüngliche Programm. Dieses zweüe Programm ist die Eingangsgröße für den Compiler 60b.

2. Die Feldaufteilungsanweisungen - Vorprozessorausgangsgröße

Die Feldaufteilungsanweisungen, die der Vorprozessor 60a in den Code einfügt, haben die allgemeine Form:

2.1 Die "tiling-args" (Feldaufteilungsargumente)

Die tiling-args, die der Vorprozessor in die Feldaufteilungsanweisungen einfügen kann, haben die allgemeine Form:
Die Feldaufteilungsparameter (tiling-param), die in der Feldaufteilungsanweisung spezifiziert werden, liefern Informationen über Attribute der in Felder aufgeteilten Schleife. Beispielsweise bedeutet ein tiling-Argument "local=t" in der Feldaufteilungsanweisung: "Diese in Felder aufgeteilte Schleife enthält eine Variable "t", die für jeden Vorgang okal sein soll."
Die Feldaufteilungsparameter, die der Vorprozessor 60a erzeugt, sind in der folgenden Tabelle wiedergegeben. Diese werden im folgenden als der Primärsatz von Parametern bezeichnet.

Primärsatz von Parametern

Syntax Beispiel

order = < dep-list> order=k
lastvalue=< var-list> smallest
local=< var-list> tmp or (t1, t2)
reduction=< var-list> sum
Der Primärsatz von Feldaufteilungsparametern ist ein Teilsatz der vollständigen Liste von Feldaufteilungsparametern, die der Compiler 60b annehmen kann, wie im folgenden noch diskutiert wird. Diese Feldaufteilungsparameter enthalten jedoch Information, die auf die Korrektheit des Programms Einfluß haben kann und man wird im folgenden erkennen, wie dies die Feldaufteilung beeinflußt.

2.2 Zusammenfassung der Feldaufteilungsanweisung

Die Syntax der ausgegebenen Feldaufteilungsanweisung des Vorprozessors 60a ist:
Die Feldaufteilungsanweisung muß vor den Schleifen (das heißt den Ausführungsanweisungen) erfolgen, deren Indizes in < tile-index-list> enthalten sind.
Die Schleifenindizes in < tile-index-list> liegen in derselben Reihenfolge vor, wie sie in dem Schleifensatz erscheinen, von links nach rechts entspricht von außen nach innen in dem Schleifensatz. (Dies ist eine Konvention für die Lesbarkeit.)
Die Feldaufteilungsparameter, die der Vorprozessor 60a erzeugen kann, bilden einen Teilsatz (der manchmal auch der Primärsatz genannt wird) der Feldaufteilungsparameter, welche der Compiler 60b verstehen kann. Der Primärsatz von Feldaufteilungsparametern ist: order, lastvalue, local, reduction (Reihenfolge, letzter Wert, lokal, Reduzierung). Der Vorprozessor 60a kennt nicht die vollständige Liste von Feldaufteilungsparametern, er verläßt sich auf die Syntaxdefinitionen für das Zergliedern.
Feldaufteilungsparameter, die in der Feldeingabeanweisung spezifiziert sind, werden so, wie sie vorliegen, in die Feldausgangsanweisung übergeben (das heißt, wenn diese Feldaufteilungsanweisungen nicht zu dem Primärsatz gehören. Wenn sie doch dazu gehören, so werden sie als Fehler markiert und die Schleife wird nicht in Felder aufgeteilt.) Formale Syntaxdefinition:

3. Automatische Feldaufteilung

Dieser Abschnitt konzentriert sich auf die vom Vorprozessor 60a ausgegebenen Feldaufteilungsanweisungen unter einem funktionellen Gesichtspunkt. Für diese Diskussion (soweit nicht ausdrücklich anders angegeben) werden drei Dinge angenommen: Der Vorprozessor 60a führt ein vollständig automatisches Feldaufteilen durch, die Optimierungsanweisungen (AUTOFILE. ROUNDOFF) des Vorprozessors 60a sind so eingestellt, daß sie die maximale Parallelisierung ermöglichen, und es gibt keine Vorgaben.
Die Prinzipien des Feldaufteilens bestehen darin, von dem am weitesten außen liegenden Index ausgehend vorzugehen, und soviel wie möglich in Felder aufzuteilen (das heißt so viele Indizes wie möglich).

3.1 Überblick

Ein gegebener Schleifensatz kann nicht immer in allen Richtungen bzw. in jeder Hinsicht aufgeteilt werden. Es kann jedoch mehr als eine Möglichkeit für ein korrektes Feldaufteilen geben. Dieser Abschnitt erläutert, welche Feldaufteilungsmöglichkeit der Vorprozessor 60a auswählt (wie der Benutzer in die Auswahl der Indizes zum Feldaufteilen eingreift, wird im nächsten Abschnitt diskutiert).
Der Vorprozessor 60a führt eine Abhängigkeitsanalyse mit der iterativen Abfolge aus. Die Prinzipien der Datenabhängigkeitsanalyse kann man gemäß "Data Dependence and Its Application to Parallel Processing" von Michael Wolfe und Utpal Banerjee, International Journal of Parallel Programming, Band 16, Nr. 2, April 1988, "Optimizing Supercompilers for Supercomputers", Michael Wolfe, Ph.D. Thesis, Dept. of Comp. Sci., Report Nr. 82-1009, Univ. of Illinois, Urbana, IL, Oktober 1982, und "Advanced Compiler Optimization for Supercomputers", David Padua und Michael Wolfe, Communications of the ACM, Band 29, Nr. 12, Dezember 1986, verstehen.
Man erkennt, daß die Datenabhängigkeit in den Schleifen liegt, und daß im Kontext des Vorprozessors 60a die Abhängigkeit zwischen den Feldern vorliegt.
Mehrere Feldaufteilungshindernisse können ein Feldaufteilen verhindern, beispielsweise ein Zyklus in der Abhängigkeit. Da eine Abhängigkeit in einer Schleife enthalten ist, verhindert sie ein Aufteilen dieser Schleife in Felder, während andere Schleifen in demselben Schleifensatz dennoch in Felder aufgeteilt werden können. Darüber hinaus sind einige Aussagen bzw. Anweisungen nicht in Felder aufteilbar. Diese umfassen ein Herausgehen (goto) aus dem Schleifensatz und den Aufruf eines Unterprogramms. Dieses Feldaufteilungshindernis beeinflußt den gesamten Schleifensatz, der die nicht in Felder aufteilbaren Anweisungen enthält.
Ein weiteres Hindernis ist eine Schleife, die unvollständig in dem Satz aufgenommen ist. Dies tritt auf, wenn Anweisungen (andere als Ausführungsanweisungen) zwischen den Schleifen in dem Schleifensatz vorhanden sind. Ein unvollständiges bzw. unzureichendes Verschachteln führt zu einer Einschränkung, als ob dort, wo das unvollständige Verschachteln auftritt, eine "Mauer" wäre. In diesem Fall kann das Feldaufteilen entweder "oberhalb" oder "unterhalb" dieser Mauer, jedoch nicht auf beiden Seiten stattfinden.
Ein weiteres Beispiel eines Hindernisses ist eine Schleife, bei welcher die Grenze bzw. Grenzen der Schleife von dem Index einer äußeren Schleife abhängen. Dies erzeugt einen nicht rechtwinkligen Iterationsraum und impliziert eine Einschränkung dahingehend, daß diese beiden Schleifen sich wechselseitig für eine Feldaufteilung ausschließen. Es versteht sich, daß diese Einschränkung in besonderen Fällen vereinfacht werden kann, wie z. B. bei dreieckigen Schleifen.
Auf der Basis der Analyse des Schleifensatzes (die unter anderem alle Feldaufteilungshindernisse herausfindet) teilt der Vorprozessor 60a die Schleife auf, wobei die Feldaufteilungshindernisse umgangen werden. Dabei erzeugt er eine Schleifentabelle, welche die Feldaufteilungshindernisse und die darauf beruhenden Feldaufteilungsentscheidungen zeigt.
Die endgültige Entscheidung, ob es sich lohnt, eine in Felder aufgeteilte Schleife parallel auszuführen oder nicht, erfolgt durch den Compiler (oder während des Programmlaufes). Der Vorprozessor 60a kann eindimensionale ("1D") Schleifen mit Abhängigkeit ebenso wie Schleifen mit kleinem Arbeitsumfang, etc. aufteilen. Der Hauptgrund liegt darin, daß, während der Vorprozessor 60a zu einem Zeitpunkt eine Schleife betrachtet, allgemeinere Betrachtungen, wie z. B. die Speicherverteilung, die Strategie des Feldaufteilens beeinflussen können. Der Compiler kann die Feldaufteilungsanweisung "entfernen", um allgemeine Belastungen (Zusatzlasten) während des Programmlaufs zu beseitigen.
Das Neuordnen (Schleifenaustausch) findet, wenn überhaupt, nach dem Feldaufteilen statt und nur innerhalb des Feldes.

3.2 Auswählen der Indizes zum Feldaufteilen

Die Hauptaufgabe des Vorprozessors 60a besteht darin, Feldaufteilungsanweisungen in den Code einzufügen:
C*KSR* TILE (< tile-index-list> [,< tiling-param> ...]
Das Auswählen der Feldaufteilungsindexliste bildet die Hauptentscheidung. Die übrigen Feldaufteilungsparameter werden entsprechend bestimmt.
Für die Zwecke der vorliegenden Diskussion sei angenommen, daß der Vorprozessor 60a die Schleifentabelle in zwei Schritten erzeugt. Zunächst sammelt er die Information über den Schleifensatz, Feldaufteilungshindernisse, etc. Dann entscheidet er, welche Indizes nach Feldern aufgeteilt werden (man beachte, daß die Schleifen in der Schleifentabelle in derselben Reihenfolge geordnet sind, wie die Schleifen in dem Schleifensatz, wobei der am weitesten außen liegende zuerst kommt). Nach der Analyse des Vorprozessors 60a und bevor irgendwelche Entscheidungen hinsichtlich der Feldaufteilung getroffen werden, hat die Schleifentabelle die in Fig. 4A dargestellte Form.
Darin zeigt eine Spalte "Feld aufteilbar?" an, ob es ein Feldaufteilungshindernis gibt, das verhindert, daß diese spezielle Schleife in Felder aufgeteilt wird, unabhängig davon, ob andere Schleifen in Felder aufgeteilt sind oder nicht. Dieses erfolgt, wenn die Schleife einen Zyklus in Abhängigkeit ausführt oder wenn der Schleifenhauptteil eine nicht in Felder aufteilbare Anweisung enthält, etc.
Die Spalte "Einschränkung" gibt an, welche weiteren Schleifen in dem Schleifensatz durch das Feldaufteilen der vorliegenden Schleife beeinflußt werden könnten. Dies tritt beispielsweise auf, wenn die Schleife nicht vollständig verschachtelt oder nicht rechtwinklig ist. Wie zuvor bereits erwähnt, kann man sich den Punkt, an welchem das unvollständige Verschachteln auftritt, als eine "Wand" vorstellen. Die Wand kann entweder an der vorherigen Schleife oder an der nächstfolgenden Schleife angebracht sein. Man kann willkürlich (ohne Beschränkung der Allgemeinheit) annehmen, daß sie an der vorherigen Schleife angebracht ist. Das Feldhindernis enthält beschreibende Information über das Feldaufteilungshindernis, falls ein solches vorhanden ist.
Nun muß nur noch die Spalte Feldaufteilungs-Entscheidung ausgefüllt werden, und zwar auf der Basis der Information in den Spalten "aufteilbar"? und "Einschränkungen". Der Vorprozessor 60a teilt die Schleife von außen nach innen auf, so daß sie so angesehen werden kann, als würde sie von der ersten Reihe in der Schleifentabelle beginnen Lind sich von dort abwärts bewegen, wobei so viel wie möglich aufgeteilt wird, während jegliche Einschränkungen berücksichtigt werden.
Die Schleifentabelle kann verwendet werden, um die Konzepte der Einschränkungshandhabung zu beschreiben werden. Wann immer entschieden wird, daß eine Schleife in Felder aufgeteilt wird, so wird sie in der Spalte "Feldaufteilungs-Entscheidung" als in Felder aufgeteilt markiert. Dann betrachtet man ihr Einschränkungsfeld: Wenn es eine Anzeige "unvollständig" gibt, so läuft der Vorprozessor 60a weiter und markiert in der Spalte (Feldaufteilungs-) Entscheidung alle darunter liegenden Reihen als "nicht in Felder aufgeteilt". Wenn dort ein < idx> vorliegt, (oder mehr als eines), so markiert der Vorprozessor 60a in der Spalte "Entscheidung" die entsprechenden Schleifen als "nicht (S. 24 Mitte) in Felder aufgeteilt".
Man beachte, daß der Vorprozessor 60a immer nur "abwärts" zu gehen braucht.
Nachdem der Vorprozessor 60a die erste Schleife in einem Schleifensatz in Felder aufgeteilt hat, können Reihen, die weiter unten in der Schleifentabelle sind, bereits einen Eintrag über eine Feldaufteilungsentscheidung haben. Dies ergibt sich aus einer Einschränkung, die durch eine zuvor in Felder aufgeteilte Schleife auferlegt wurde. In diesem Fall überspringt der Vorprozessor 60a diese Schleifenreihe, wenn er an diese herankommt, uni bewegt sich zu der nächsten.
Hinsichtlich des Konzeptes ist dies die Art und Weise, auf welche der Vorprozessor 60a die Indizes auswählt, die die < tile-index-list> für die "Feldaufteilungsanweisung" bilden. Im Anschluß daran werden die anderen < tiling-param> bestimmt und der Vorgang der Feldaufteilung ist damit vollendet.
Die Beispiele im übrigen Teil dieses Abschnittes zeigen dieses Verhalten. Für jedes Beispiel wird ein in Felder aufgeteiltes Programm bereitgostellt, wobei die Schleifentabelle in der zugehörigen Figur dargestellt ist. 3.3 Beispiele Beispiel 1. Angeregt durch den Bezugspur kt Linpack:
Wie in Fig. 4B dargestellt ist, kann die k-Schleife nicht in Felder aufgeteilt werden, da sie einen Abhängigkeitszyklus aufweist. Demnach gelten die Einschränkungseinträge für k nicht für die Feldaufteilungsentscheidung bezüglich j und i.
Der Vorprozessor 60a teilt diese Schleife folgendermaßen auf: Beispiel 2. Matrizenmultiplikation
Wie in Fig. 4C wiedergegeben, bewirkte die Einschränkung bezüglich der j-Schleife, daß die Feldaufteilung an diesem Punkt stoppte.
Der Vorprozessor 60a teilte diese Schleife folgendermaßen in Felder auf: Beispiel 3. Angeregt durch die Legendre-Transformation:
Damit dieses Beispiel funktioniert, ist es erforderlich, eine Erklärung einzufügen (die hier nicht dargestellt ist), um die angenommene Abhängigkeit zu beseitigen. Außerdem verwendet der Vorprozessor 60a in diesem Fall eine fortschrittliche Substitutionstechnik, so daß die k-Schleife und die j-Schleife perfekt verschachtelt werden können. Der Vorprozessor 60a teilt deshalb das Programm in Felder auf, als ob die Schleife die folgende wäre.
Wie in Fig. 4D dargestellt ist, erzwingt, wenn cler Vorprozessor 60a entscheidet, daß die k- Schleife in Felder aufgeteilt wird, die Einschränkung bezüglich der i-Schleife, die Entscheidung, daß bezüglich i nicht in Felder aufgeteilt wird.

4. Halbautomatisches Feldaufteilen

Dieser Abschnitt beschreibt das halbautomatische Verfahren zum Feldaufteilen, was es dem Benutzer ermöglicht, sich über die Feldaufteilungsentscheidungen, wie sie durch den Vorprozessor 60a vorgenommen wurden, teilweise hinwegzusetzen.

4.1 Überblick

Im allgemeinen Fall gibt es mehr als eine Möglichkeit, die Indizes für das Feldaufteilen auszuwählen. Der Vorprozessor 60a wählt über den automatischen Feldmechanismus eine dieser Möglichkeiten aus. Das halbautomatische Feldaufteilen ermöglicht es dem Benutzer, in den Vorgang des Auswählens der Indizes für das Feldaufteilen einzugreifen, indem er ausdrücklich angibt, welche Indizes er in Felder aufgeteilt zu werden wünscht. Unter Verwendung der halbautomatischen Feldaufteilung erhält der Benutzer eine zusätzliche Kontrolle über das Feldaufteilen, während er dieselbe Garantie der Korrektheit wie beim automatischen Feldaufteilen beibehält.
Dies erfolgt durch Verwenden der folgenden Eingangsanweisung des Vorprozessors 60a:
C*KSR* TILE (< tile-index-list> [,< tiling-param> ...])
Der Feldaufteilungsparameter < tiling-param> kann irgendein Parameter sein, der nicht einer der Feldaufteilungsparameter aus dem Primärsatz ist. Der Grund hierfür liegt darin, daß, wie zuvor bereits erwähnt, die Feldaufteilungsparameter in dem Primärsatz (Reihenfolge, letzter Wert, lokal, Reduzierung) die Korrektheit des Programms beeinflussen können.
Der Vorprozessor 60a transformiert die Eingangsanweisung in die folgende Anweisung:
wobei < tiling-param> alle Feldaufteilungsparameter enthält, die in der C*KSR*TILE- Anweisung angegeben waren, und möglicherweise zusätzliche Feldaufteilungsparameter aus dem Primärsatz. Und dabei ist < tile-index-list> dieselbe wie diejenige, die der Benutzer angegeben hat. Wenn der Benutzer eine Kombination angegeben hat, die nicht korrekt ist (gemäß den Kriterien des Vorprozessors 60a), so gibt der Vorprozessor 60a eine Fehlermeldung aus.

4.2 Beispiel

Es wird erneut auf das obige Beispiel Bezug genommen, welches durch "die Legendre- Transformation angeregt wurde", indem eine fortschrittliche Substitutionstechnik verwendet wird, wobei die Schleife in 3D in Felder aufgeteilt wird. Der Benutzer könnte sie jedoch in 2D aufteilen, indem er die folgende Zeile vor dem Schleifensatz einfügt:
C*KSR* TILE (I, k)
Dies weist den Vorprozessor 60a an, nur in diesen Indizes in Felder aufzuteilen. Da es eine zulässige Möglichkeit ist (wie man aus der Schleifentabelle erkennen kann), führt der Vorprozessor 60a dies aus, ohne eine Fehlermeldung zu erzeugen.
Der Vorprozessor 60a teilt folgendermaßen in Felder auf:

5. Ähnliche Fragestellungen

Die obigen Abschnitte konzentrieren sich auf den Feldaufteilungsgesichtspunkt beim Betrieb des Vorprozessors 60a. Nachstehend folgt eine kurze Diskussion anderer Gesichtspunkte der Arbeitsweise des Vorprozessors, die nicht unmittelbar mit dem Feldaufteilen in Beziehung stehen, die jedoch die Ergebnisse des in Felder aufgeteilten Programms beeinflussen können.
Eine Verteilung wird durchgeführt, wenn sie bei der Feldaufteilung hilfreich ist. Beispielsweise um einen Teil der Schleife in Felder aufzuteilen, wenn sich I/O-Anweisungen darin befinden.
In einigen Fällen muß eine Codetransformation stattfinden, um ein Programm (beispielsweise wenn eine Reduktion vorhanden ist oder wenn der letzte Wert benötigt wird) in Felder aufzuteilen. Einige dieser Transformationen erfordern es, daß man die Grenzen eines Feldes kennt - einen Wert während des Programmlaufs, der verfügbar ist, wenn ein Feld ausgeführt wird.
In den meisten Fällen erfolgt die Transformation durch den Vorprozessor 60a. Wenn jedoch aus irgendeinem Grund Benutzer (oder Vorprozessoren 60a) diese Art von Transformation ausführen, so müssen sie möglicherweise den Wert der Grenzen des Feldes während des Programmlaufs kennen. Dies kann man erreichen durch Verwendung einer intrinsischen Funktion.
Die inneren Schleifenindizes einer seriellen Schleife innerhalb einer äußeren, in Felder aufgeteilten Schleife werden durch den Compiler als lokale Größen behandelt. Beispielsweise
Der Compiler behandelt diese Schleife, als ob dort eine implizite lokal = (i,j) wäre.

Die Laufzeitbibliothek

1. Überblick

Die folgenden Abschnitte beschreiben die Betriebsweise der Laufzeitbibliothek 66.

2. Das Programmiermodell

Die Laufzeitbibliothek 66 ist (programmier-) sprachenunabhängig. Sie kann von einer Vielzahl von Sprachen aufgerufen werden, z. B. von Fortran 77 oder 90, C oder dergleichen. Die folgenden Abschnitte diskutieren sie jedoch bezüglich ihrer Verwendung aus Fortran-Programmen.
Die drei parallelen Konstruktionen, welche die Laufzeitbibliothek 66 handhabt, sind das Feldaufteilen, parallele Bereiche und parallele Abschnitte. Die Feldaufteilungskonstruktion erlaubt es dem Benutzer, do-Schleifen von Fortran parallel auszuführen. Die Parallelabschnittskonstruktion ermöglicht es dem Benutzer, unterschiedliche Codesegmente eines Programms parallel auszuführen. Die Parallelbereichskonstruktion erlaubt es dem Benutzer, ein einzelnes Codesegment eines Programms gleichzeitig mehrere Male ablaufen zu lassen.
Alle Parallelkonstruktionen können verschachtelt werden. Die Laufzeitbibliothek 66 kann jedoch jede parallele Konstruktion seriell ablaufen lassen, wenn keine ausreichenden Ressourcen verfügbar sind.
Der Rest dieses Abschnittes enthält eine kurze Beschreibung der Parallelkonstruktionen, die durch die Laufzeitbibliothek 66 unterstützt werden. Die folgenden Abschnitte diskutieren jede im einzelnen.

2.1 Feldaufteilung

Die Feldaufteilung eines Fortran-Schleifensatzes ist eine Aufteilung des Iterationsraumes in rechteckige Blöcke in Form eines Parallelepipeds, die Felder oder Blöcke (wörtlich: Kacheln) genannt werden. Demnach ist ein Feld eine Ansammlung von Iterationen. Die Gruppe von Feldern, die einen Schleifensatz bilden, wird eine Feldfamilie genannt. Die Felder sind die grundlegenden Einheiten, die parallel ausgeführt werden können. Zahlreiche Prozessoren können denselben Schleifensatz ausführen, wobei jeder von ihnen gleichzeitig mit den anderen ein getrenntes Feld bearbeitet. Beispiel:
In diesem Fall ist der Schfeifensatz in die Felder mit den beiden Indizes i und j aufgeteilt. Es ist möglich, nur einen Teil der Schleifenindizes in Felder aufzuteilen. Beispielsweise wäre in dem obigen Beispiel auch die folgende Feldaufteilung möglich:
Das Feldaufteilungsmodell hat zwei Eigenschaften, die für die Laufzeitbibliothek 66 wichtig sind. Als erstes ist dies die Flexibilität hinsichtlich des Verhältnisses von Arbeitsleistung/Grundlast. Die Laufzeitbibliothek 66 stellt einen allgemeinen Weg für die Handhabung der "Granularität" bzw. "Körnigkeit" in der Parallelität bereit, die von einer Iteration zu einer beliebigen Anzahl von Iterationen reicht. Als zweites ist es die Bequemlichkeit bei der Handhabung von Abhängigkeit: Die Laufzeitbibliothek 66 liefert einen einfachen Weg, eine teilweise Reihenfolge (Feldabhängigkeit) zu definieren und einen Weg, Parallelität bei Vorliegen von Abhängigkeit zu verwenden.

2.2 Affinitätsbereiche

Der Mechanismus des Affinitätsbereiches gilt für die Parallelkonstruktion der Feldaufteilung. Er liefert ein Verfahren für den Benutzer, um Optimierungsinformation an die Laufzeitbibliothek 66 zu übermitteln. Ein Affinitätsbereich ist eine Sammlung von Feldfamilien, welche die Laufzeitbibliothek 66 in einer Art und Weise auszuführen versucht, so daß Datenkonkurrenz und -verschiebung vermieden wird. Die Laufzeitbibliothek 66 enthält einige Information über den gesamten Satz von Feldfamilien und benutzt dies, um Felder auf Prozessoren aufzuteilen, so daß Prozessoren von Feldfamilie zu Feldfamilie mit denselben Daten arbeiten.
Um einen Affinitätsbereich zu erklären, muß cer Benutzer den gewünschten Code in die Anweisungen Affinitätsbereich und Ende des Affinitätsbereiches einbinden. Die Anweisungen dürfen keine Feldfamilie unterbrechen. Wenn der Affinitätsbereich innerhalb eines parallelen Abschnittes als solcher deklariert wird, so muß er sich innerhalb eines Sektionsblockes befinden. Die Deklarierung muß innerhalb eines einzelnen Unterprogramms oder Hauptprogramms erfolgen.
Dies sind Parameter, welche eher die Effizienz der Ausführung anstatt deren Korrektheit beeinflussen. Der Affinitätsbereich erfordert eine globale Entscheidungsfindung und dies ist die Art und Weise für den Benutzer, diese zu spezifizieren. Wenn der Benutzer dieselben Parameter in einer Feldaufteilungsanweisung angegeben hat, die in einen Affinitätsbereich eingebettet ist, so setzen sich die Parameter in dem Affinitätsbereich über diejenigen in der Feldaufteilungsanweisung hinweg.
Affinitätsbereiche können verschachtelt werden. Beispiel:

2.3 Teamoperatoren

Parallele Konstruktionen bzw. Konstruktionselemente werden in der Laufzeitbibliothek 66 durch Gruppen von p-Strängen ausgeführt. Im Standardbetrieb sind die p-Strang-Gruppen für den Benutzer unsichtbar. Die Laufzeit Bibliothek 66 implementiert jedoch eine Schnittstelle zu diesen Gruppen von p-Strängen für den Benutzer, welcher ein größeres Maß an Kontrolle über sein Programm wünscht. Die Funktionen, die die p-Strang-Gruppen verwalten, werden "Team"-Operatoren genannt. Das Interface wird genauer an einem Ende dieses Abschnittes beschrieben.

2.3.1 Definition eines Teams

Jede p-Strang-Gruppe oder Team besteht aus einem oder mehreren p-Strängen, wobei ein p-Strang als "Führer" bezeichnet wird. Jedes Teammitglied hat eine Mitgliedskennung, die in dem Team einzigartig ist, mit 0 beginnt und ohne Lücken in der Abfolge ansteigt. Die Mitgliederkennung des Teamführers ist 0.

2.3.2 Standard-Team-Benutzung

Die Laufzeitbibliothek 66 erzeugt und verwaltet Teams automatisch und löst sie auch automatisch auf ohne Anweisung von dem Benutzer. Die Schnittstelle der Laufzeitbibliothek 66 ermöglicht es jedoch dem Benutzer, eine Teamerzeugung, Verteilung und Nutzung explizit anzugeben.
Wenn der Benutzer eine Teambenutzung nicht spezifiziert, folgt die Laufzeitbibliothek 66 der generellen Praxis des Erzeugens eines neuen Strang-Teams für jede neue Parallelkonstruktion. Das Strang-Team wird am Ende der Konstruktion aufgelöst. Eine Ausnahme wird gemacht für Feldaufteilungskonstruktionen, die lexikalisch in einer Affinitätsbereichsanweisung enthalten sind; alle derartigen Feldaufteilungskonstruktionen werden durch dasselbe Strang-Team ausgelöst.

2.3.3 Teamkennzeichnungen

Teamkennzeichnungen sind in dem gesamten Programm durchgehend eindeutig.

2.3.4 Teamerzeugung

Der p-Strang, der über einen ipr_create_team-Aufruf läuft, führt den Aufruf aus und wird der Teamleiter. Die p-Stränge können Mitglieder mehrerer Teams sein.

2.3.5 Beschränkung hinsichtlich der Benutzung von Teams

Ein Team kann nicht parallel verwendet werden - es kann zu einer gegebenen Zeit nur ein Konstruktionselement ausführen. Wenn jedoch die Konstruktionen bzw. Konstruktionselemente verschachtelt sind, kann ein p-Strang Mitglied mehrerer Teams sein und kann mehrfache Konstruktionen bzw. Konstruktionselemente ausführen.
Ein paralleles Konstruktionselement kann nur durch ein Team ausgeführt werden, wenn der p-Strang, der mit dem Konstruktionselement zusammentrifft, ein Mitglied und der Führer des Teams ist. Der Grund für diese Einschränkung ist ein grundlegendes Implementierungsproblem. Der p- Strang, der mit dem Konstruktionselement zusammentrifft, ist der einzige p-Strang, der den Kontext hat, um den seriellen Code vor und nach dem parallelen Konstrukt bzw. Konstruktionselement auszuführen. Es wäre möglich, daß eine Laufzeitbibliothek 66 einem p-Strang erlaubt, ein Team aufzurufen, das kein Mitglied zum Ausführen des Konstruktionselementes ist, wobei jedoch der ursprüngliche p-Strang während der parallelen Ausführung zum Leerlauf gezwungen ist.

3. Schnittstellen

3.1 Laufzeitbibliothek 66/Benutzerschnittstelle

Benutzer geben Eingaben in die Laufzeitbibliothek 66 über Laufzeitparameter, Programmanweisungen oder Aufrufe von Unterprogrammen ein. Die Laufzeitparameter ermöglichen es dem Benutzer, die Ressourcen und die durch die Laufzeitbibliothek 66 vorgenommenen Berechnungen zu steuern, was es ermöglicht, im Hinblick auf Leistungsfähigkeit abzustimmen. Die Programmanweisungen erlauben es dem Benutzer, Gelegenheiten für Parallelität anzuzeigen. Die Programmanweisungen können an den KSR-Compiler oder an den Vorprozessor 60a oder an beide adressiert werden. Unterprogrammaufrufe werden verwendet, um die Stranggruppen- (Team-) Verwaltung der Laufzeitbibliothek 66 ausdrücklich zu kontrollieren.

3.1.1 Programmanweisungen

Wie oben erwähnt, liegen Programmanweisungen in der Form von Fortran-Kommentaren vor. Wenn eine Programmanweisung vorhanden ist, erzeugt der Compiler 60b Aufrufe an die Laufzeitbibliothek der Laufzeitbibliothek 66, um die parallele Ausführung des Schleifensatzes zu veranlassen.
Die Anweisungen paralleler Abschnitt, paralleler Bereich und Satz werden nur von dem Benutzer erzeugt und nur von dem Compiler verstanden. Affinitätsbereichsanweisungen werden durch den Benutzer oder den Compiler erzeugt und nur von dem Compiler verstanden. Feldaufteilungsanweisungen werden durch den Benutzer und/oder den Compiler 60b erzeugt.
Um ein Fortran-Programm in Felder aufzuteilen, kann der Benutzer entweder die Feldaufteilungsanweisungen von Hand einfügen oder sich darauf verlassen, daß der Vorprozessor 60a dies tut. Der Vorprozessor 60a nimmt ein Fortran-Programm als Eingangsgröße und erzeugt das transformierte Fortran-Programm, welches die Feldaufteilungsanweisungen enthält. Es ist möglich, eine Mischung von manuellem und automatischem Feldaufteilen zu verwenden. Damit kann der Vorprozessor ein teilweise in Felder aufgeteiltes Programm aufnehmen, die Schleifensätze, die bereits für sich allein in Felder aufgeteilt sind, erhalten und die anderen Schleifen in Felder aufteilen. Die Ausgangsgröße des Vorprozessors 60a ist ein zulässiges Fortran-Programm.
In dem vollständig automatischen Betrieb ruft der Benutzer das Kompilierungssystem 60 auf, welches seinerseits den Vorprozessor 60a aufruft. Es versteht sich, daß die Laufzeitbibliothek 66 selbst den Unterschied zwischen automatischer und halbautomatischer Feldaufteilung nicht wahrnimmt. Diese unterschiedlichen Verfahren erzeugen aus der Sicht der Laufzeitbibliothek 66 identische Eingangsgrößen.

3.1.2 Laufzeitparameter

Die Parameter der Laufzeitumgebung, die in den Fig. 6 dargestellt sind, sind unter Verwendung von Variablen einer Unix-Umgebung definiert. Diese Parameter können ebenfalls unter Verwendung der Satz-Anweisung gesetzt werden.
Um eine parallele Ausführung zu erreichen, wird der Code innerhalb eines parallelen Konstruktionselementes in eine besondere Art eines Unterprogramms transformiert. Das Aufgabenunterprogramm (die Programme) nehmen die Form eines verschachtelten Unterprogramms nach Art von Pascal an. Man erkennt, daß dies keine Erweiterung der Programmiersprache selbst ist, die Aufgabenunterprogramme werden nur in den internen Datenstrukturen des Kompilierungssystems 60 erzeugt.
Fig. 7 veranschaulicht die Transformation eines Feldes in ein Aufgabenunterprogramm. In der Figur ist das ursprüngliche Programm (11.f) als ein Block 70a gekennzeichnet. Das in Felder aufgeteilte Programm (11.cmp) ist als ein Block 70b gekennzeichnet. Das in Felder aufgeteilte Programm wird intern in den ("als ob") Code transformiert, der in Block 70c dargestellt ist.
Indem diese Transformation ausgeführt wird, hat sich der Schleifensatz in ein Unterprogramm verwandelt. Die Argumente dieses Unterprogramms sind die Grenzen des Feldes. In dem in Fig. 7 dargestellten Beispiel wurde
do 10 i = 1, n
do 10 j = 1, n
transformiert in
do 10 i = i1, i2
do 10 j = j1, j2
und die Grenze wurde zum Argument des Aufgabenunterprogramms. Wenn beispielsweise ein Feld mit einer Feldgröße von 16 · 16 verwendet wird, gibt ein Strang einen Aufruf an talk foo_$1 (32, 47, 16, 31) aus. Dies bewirkt dann die Ausführung von
Damit führt dieser Strang 16 Iterationen in der Dimension i und 16 Iterationen in der Dimension j aus. Die Laufzeitbibliothek 66 ruft die Aufrufe nach task foo_$1 von den verschiedenen Strängen mit den entsprechenden Argumenten auf, so daß alle Iterationen ausgeführt werden. Die Parallelität wird dadurch ausgeführt, daß man mehrere Stränge hat, die die verschiedenen Argumente (das heißt die Grenzen) des Aufgabenunterprogramms aufrufen.
Die Existenz der parallelen Konstruktionselemente löst einen Aufruf für das Ausführen eines Programmlaufs in der Laufzeitbibliothek 66 aus und der Compiler leitet den Namen des Aufgabenunterprogramms als ein Argument weiter. Die Argumente dieser Ausführungsabläufe enthalten die gesamte Information über das Konstruktionselement, welche benötigt wird, um es parallel auszuführen. Ein Teil dieser Information kommt aus der Programmanweisung selbst (das heißt, welche Indizes in Felder aufzuteilen sind, Abhängigkeitsinformation etc.), ein Teil kommt aus dem Quellprogramm (das heißt Grenzen und Schritt bzw. Schrittweite des Schleifensatzes), ein Teil der Information wird durch das Kompilierungssystem 60 erzeugt (das heißt SSB, Codegröße - wie oben diskutiert). Es gibt außerdem einige Daten, die benötigt werden für den Übergang zwischen dem Code innerhalb des Aufgabenunterprogramms und außerhalb desselben (Zeiger auf das Aufgabenunterprogramm, Framezeiger, Anzeige für das Unterstützen des letzten Wertes).
Die vorliegende Ausführungsform liefert einen einfachen Weg für das Ausführen des Feldes als unabhängige Einheit (indem es ein Unterprogramm ist) und gleichzeitiges Erkennen der Variablen des Hauptprogramms bzw. darüberliegenden Programms unter Verwendung eines vorhandenen Compilermechanismus (indem es ein verschachteltes Unterprogramm ist). In diesem speziellen Beispiel erkennt es das Feld a.

3.2 Schnittstelle Laufzeitbibliothek/Betriebssystem

Die Parallelität der Laufzeitbibliothek 66 wird implementiert mit der OSF-Implementierung von p-Strängen. Die Schnittstelle zwischen dem OS und der Laufzeitbibliothek 66 und den p- Strängen und dem Laufzeitsystem 66 wird hier nicht im einzelnen erläutert, jedoch gibt es einige grundlegende Annahmen hinsichtlich der Umgebung, in welcher die Laufzeitbibliothek 66 lebt, und welche benötigt werden, um den Rahmen hierfür bereitzustellen.
Die Laufzeitbibliothek 66 verwendet eine variable Anzahl von Strängen während der Laufzeit des Programms. Ein einzelner Strang wird zu Beginn ausgelöst und wird der Programmführungsstrang. Dieser Strang ist verantwortlich für das Ausführen aller seriellen Abschnitte des Programms.
Jedes parallele Konstruktionselement wird durch ein Team von Strängen ausgeführt, die eine "Stranggruppe" genannt werden. Jede Stranggruppe hat einen Strang, der als Gruppenführer bzw. -leiter gekennzeichnet ist, während alle anderen Mitglieder Gruppensklaven sind.
Die Laufzeitbibliothek 66 delegiert einen großen Teil der Last, welche auf die Stränge verteilt ist, auf den Planer des Betriebssystems. In einigen Fällen nimmt die Laufzeitbibliothek 66 an, daß ein Strang einem Prozessor zugeordnet ist und daß diese Verbindung erhalten bleibt. Dies ist eine wichtige Annahme, die von der Laufzeitbibliothek 66 bei der Modulo-Feldaufteilungsstrategie verwendet wird, bei welcher Arbeit in der Weise aufgeteilt wird, daß eine Zelle auf Daten Bezug nimmt, die sie schon besitzt.
Die Laufzeitbibliothek 66 kann Information an den OS-Planer leiten, um ihn darin zu unterstützen, Entscheidungen über den Lastausgleich auf einer besseren Informationsbasis zu treffen.

4. Feldaufteilung

Die Feldaufteilung, wie oben bereits dargelegt, ist ein Verfahren zum parallelen Ausführen eines Schleifensatzes bzw. von verschachtelten Schleifen. Dieser Abschnitt erläutert die Semantik der Feldaufteilungsanweisung und veranschaulicht die Art und Weise, in welcher eine in Felder aufgeteilte Schleife ausgeführt wird.

4.1 Feldaufteilungsanweisung - Semantik

Nicht jede Schleife kann in einfacher Weise in Felder aufgeteilt werden. Einige Schleifen können überhaupt nicht in Felder aufgeteilt werden und einige Schleifen können nur mit besonderer Sorgfalt aufgeteilt werden, um eine korrekte Ausführung sicherzustellen. "Korrekte Ausführung" bedeutet in diesem Kontext, daß man dasselbe Ergebnis erhält wie dadurch, daß man dasselbe Programm seriell ablaufen läßt.
Die Syntax der Feldaufteilungsanweisung ermöglicht Spezifikationen von Feldaufteilungsparametern, die die zusätzliche Information liefern, welche erforderlich ist, um eine korrekte Ausführung sicherzustellen. Dieses sind die Reihenfolge, der letzte Wert, die Lokalität und die Reduktion bzw. Reduzierung.
Zusätzlich gibt es andere Feldaufteilungsparameter, die die Korrektheit des Programms nicht beeinflussen, jedoch seine Leistungsfähigkeit beeinflussen.

4.2 Feldaufteilung mit dem Feldaufteilungsparameter Ordnung bzw. Reihenfolge

Der Feldaufteilungsparameter Ordnung gibt eine partielle Reihenfolge für die Ausführung von Feldern an, die aus der Datenabhängigkeit innerhalb des in Felder aufgeteilten Schleifensatzes abgeleitet wird. Der Feldaufteilungsparameter Ordnung erfordert eine spezielle Aufmerksamkeit in diesem Abschnitt, da es verwirrend sein kann und oftmals nicht intuitiv verstanden werden kann, wie die Abhängigkeit und demnach die richtige Reihenfolge zu bestimmen ist. Zusätzlich ist er einer der Feldaufteilungsparameter, welche die Richtigkeit der Programmausführung beeinflussen kann.
Die Tatsache, daß Abhängigkeit - und damit die Feldaufteilungsanweisung der Ausführungsreihenfolge - nicht einfach zu bestimmen ist, ist nicht besorgniserregend, da sie typischerweise automatisch durch den Vorprozessor 60a erfaßt wird. Wenn der Benutzer sich entschließt, den Vorprozessor 60a nicht zu benutzen, so kann er oder sie dies spezifizieren und dann wird es zu seiner oder ihrer Verantwortlichkeit.
Wenn ein Schleifensatz mit dem Feldaufteilungsparameter der Reihenfolge in Felder aufgeteilt wird, versucht die Laufzeitbibliothek 66 eine parallele Ausführung dieser Schleife zu erreichen unter Sicherstellung der richtigen Reihenfolge der Ausführung. In einigen Fällen bewirkt das Beachten der Reihenfolge eine serielle Ausführung. In einigen anderen Fällen jedoch kann eine Schleife, die mit der richtigen Reihenfolge in Felder aufgeteilt ist, parallel ablaufen.
Wenn ein Schleifensatz parallel ausgeführt wird, so müssen die Iterationen nicht notwendigerweise in derselben Reihenfolge wie bei der seriellen Ausführung desselben Schleifensatzes ausgeführt werden. In einigen Fällen spielt es keine Rolle, während in anderen Fällen die Datenabhängigkeit eine teilweise Ordnung zwischen den Iterationen verlangt. Dies impliziert wiederum eine teilweise Ordnung zwischen den Feldern, um eine korrekte Ausführung zu garantieren.
Die Art und Weise, dieses zu handhaben, liegt in der Spezifizierung einer Feldaufteilungsanweisung mit Ordnung bzw. Reihenfolge. Dies bewirkt, daß die Laufzeitbibliothek 66 die notwendige Synchronisation zwischen der Ausführung von Feldern vornimmt, um die richtige Ausführung sicherzustellen. Beispiel:
Dieser Schleifensatz kann in beiden Dimensionen auf folgende Weise in Felder aufgeteilt werden:
Dieses definiert die folgende partielle Reihenfolge zwischen den Feldern: Ausführung eines Feldes kann beginnen, wenn das in i-Richtung davor liegende Feld ausgeführt worden ist und wenn das dahinter liegende Feld in Richtung j ausgeführt bzw. vollendet ist. In dem in Fig. 8 dargestellten Programm kann das mit "x" markierte Feld ausgeführt werden, wenn die mit "d" markierten Felder vollendet bzw. ausgeführt sind. Dies bewirkt typischerweise, daß die Laufzeitbibliothek 66 die Wellenfront-Feldaufteilungsstrategie auswählt, die eine parallele Ausführung bei Vorliegen einer Ordnung bzw. Reihenfolge in zwei Dimensionen ermöglicht.

4.3 Der Feldaufteilungsparameter der Reihenfolge und Datenabhängigkeit - anhand eines Beispiels

Wie oben erwähnt, wird die Reihenfolge: ORDER = -J, I typischerweise durch den Vorprozessor 60a eingefügt. Dieser Abschnitt erläutert anhand eines Beispiels die Beziehungen zwischen der Datenabhängigkeit und der Feldaufteilung mit Reihenfolge.
Gemäß dem ursprünglichen Programm gilt:
Zunächst muß man, um die Reihenfolge, in welcher Iterationen ausgeführt werden müssen, den Hauptteil der Schleife betrachten. Angenommen, die Position einer gegebenen Iteration sei durch "x" markiert und die Position der Iteration(en), vcn welcher sie abhängt, ist mit einem "*" markiert, so ist das resultierende Diagramm:
In der ursprünglichen Schleife ist j der innere Index und damit derjenige, der sich schneller bewegt, so daß, wenn "x" ausgeführt wird, der Fall vorliegen muß, daß die Iterationen auf seiner oberen rechten Seite schon ausgeführt sind (dies wird durch ein "+" angezeigt) und daß die Iteration an seiner unteren linken Seite noch nicht ausgeführt ist (dies wird durch ein "-" angezeigt). Das Ergebnis ist das folgende:
Mit anderen Worten, es ist sicher, eine Iteration an der Position x auszuführen dann und nur dann, wenn die Iteration oben rechts davon erfolgt ist. Dies kann auf die Abhängigkeit zwischen zwei Iterationen reduziert werden, und zwar folgendermaßen:
Der nächste Schritt besteht darin, die teilweise Ordnung zwischen den Feldern herauszufinden. Innerhalb des Feldes bleibt die ursprüngliche Ordnung erhalten. Um zu untersuchen, was zwischen den Feldern besteht, kann die "Schablone" in (I) oben um die Grenzen eines imaginären Feldes bewegt werden, wie nachstehend wiedergegeben:
Das Äquivalent von (II) ist folgendes, wobei Großbuchstaben verwendet werden, um Felder zu kennzeichnen:
Das D oben rechts ist redundant: Die untere Linie impliziert, daß ein Feld x auf das Feld zu seiner Rechten warten muß, bevor es beginnen kann. Demnach ist es, wenn das Feld unten links auf das Feld oben links davon wartet, ausreichend sicherzustellen, daß das Feld oben rechts bereits erledigt ist. Demnach muß das Feld unten links (welches mit X gekennzeichnet ist) darauf warten, daß die Felder "oben" und "auf seiner Rechten" erledigt sind und durch Rekursion wird die richtige Reihenfolge definiert. Damit ist das Ergebnis das folgende:
Dies wird in der Feldaufteilungsanweisung in folgender Weise ausgedrückt:
C*KSR* TILE (I, J, ORDER = (-J, I))

4.4 Feldaufteilung mit local, lastvalue und Reduktion

Zusätzlich zu den Indizes und Abhängigkeitsparametern gibt es drei weitere Feldaufteilungsparameter, die die Korrektheit des Programms beeinflussen können. Typischerweise werden diese Feldaufteilungsparameter durch den Vorprozessor 60a erzeugt. Sie sind:
LOCAL - Eine Bestimmung lokaler Variablen, die von dem neuen lexikalischen Unterprogramm benötigt werden. Dies wird durch den Compiler 60b gehandhabt und wird nicht zu der Laufzeitbibliothek 66 weitergeleitet.
LASTVALUE - Zeigt an, ob der letzte Wert der Schleifenindizes nach der Schleifenausführung erhalten bleiben muß. Die Laufzeitbibliothek 66 muß dies handhaben, da die Parallelisierung der Schleife die Ausführungsreihenfolge der Iterationen beeinflußt. Die Laufzeitbibliothek 66 berechnet den letzten Wert durch Überprüfen der Grenzen jedes ausgeführten Feldes. Wenn das Feld, welches die höchsten Grenzwerte des Iterationsraumes enthält, ausgeführt worden ist, wird der letzte Wert durch die Laufzeitbibliothek 66 an das Kompilierungssystem 60 übermittelt.
REDUCTION - Erklärt, daß eine Reduktion auf eine Variable innerhalb des Feldes angewendet werden muß. Die Reduktion wird durch das Kompilierungssystem 60 gehandhabt und erfordert eine gewisse Unterstützung aus der Laufzeitbibliothek 66.

4.5 Andere Feldaufteilungsparameter

Es gibt Feldaufteilungsparameter, die es dem Benutzer ermöglichen, in die Entscheidungen der Laufzeitbibliothek 66 einzugreifen und Effizienzentscheidungen zu beeinflussen. Sie werden nur von dem Benutzer zugeführt und niemals durch das Kompilierungssystem 60 und sie werden in den vorstehenden Abschnitten als "Extra"-Parameter bezeichnet. Diese Parameter werden im folgenden aufgelistet.
TILESIZE - Dies ist ein vom Benutzer zugeführter Vektor für die Feldgröße der folgenden Feldfamilie. Dieser Vektor gilt nur für diese Feldfamilie und gilt nicht für irgendeinen der nachfolgenden Schleifensätze. Mögliche Werte sind n (wobei n ein Zahlenwert größer als 0 ist), x (wobei x eine Variable ist) oder "*" (ein Symbol, welches anzeigt, daß das Feld in dieser Dimension den gesamten Iterationsraum umfassen sollte). Der Vektor muß Werte für alle in Felder aufgeteilte Indizes angeben. Die Syntax folgt der allgemeinen Parametersyntax der Feldaufteilung durch das Kompilierungssystem 60.
STRATEGY - Eine Benutzeranweisung bezüglich der Feldaufteilungsstrategie, die für die nachfolgende Feldfamilie verwendet werden soll. Dieser Wert gilt nur für diese Feldfamilie. Mögliche Werte sind GRAB oder MOD. Die Syntax entspricht der allgemeinen Parametersyntax für die Feldaufteilung durch das Kompilierungssystem 60.

4.6 Ausführung eines in Felder aufgeteilten Schleifensatzes

Wenn eine neue Feldfamilie für den Beginn einer Ausführung bereit ist, entscheidet die Laufzeitbibliothek 66 über einen Arbeitsplan. Diese Entscheidung beruht auf den Faktoren, welche Affinität, Abhängigkeit und Datenlokalität umfassen.
Der Arbeitsplan ist eine Ansammlung von Entscheidungen, die die parallele Ausführung der Feldfamilie bestimmen: Zuordnung von Strängen (Abläufen), Aufteilen des Iterationsraumes und Auswählen einer Feldaufteilungsstrategie. Das Auswählen des richtigen Arbeitsplanes und - insbesondere - das Auswählen der richtigen Strategie, hat einen wesentlichen Effekt auf die Leistungsfähigkeit. Prinzipiell wird der Arbeitsplan ausgewählt, wenn eine neue Feldfamilie beginnt. Wenn diese Feldfamilie zu einem Affinitätsbereich gehört, beruht der Arbeitsplan auf einer Schablone bzw. Vorlage des Arbeitsplanes für den Affinitätsbereich. Dies wird später diskutiert.

4.7 Zuordnung von "Strängen"

Bei der Feldaufteilung berücksichtigt die Laufzeitbibliothek 66 die Menge an verfügbaren Ressourcen und verwendet für jede Feldfamilie n Stränge, wobei n kleiner oder gleich der Anzahl von für dieses Programm verfügbaren Prozessoren ist. Der Standard besteht darin, daß man die maximale Anzahl von verfügbaren Prozessoren verwendet. Wenn die Feldfamilie strukturiert ist, so daß es keinen Sinn macht, die maximale Anzahl zu verwenden, wird eine kleinere Anzahl von Strängen ausgewählt. Dieser Algorithmus wird verwendet unabhängig von der Verschachtelung.
Es gibt gewisse Unterschiede in der Zuordnung von Strängen gemäß der Feldaufteilungsstrategie, die verwendet wird (die Feldaufteilungsstrategie wird im folgenden noch beschrieben):
Wenn man die GRAB-Strategie verwendet, läßt die Laufzeitbibliothek 66 den Planer alle Strang-Prozessor-Verbindungen, Lastausgleiche, Affinität etc. handhaben.
Wenn die MODULO- und die WAVEFRONT-Strategien verwendet werden, würde die Laufzeitbibliothek 66 gern annehmen, daß die Strang-Prozessor-Verbindung konstant ist. Die Laufzeitbibliothek 66 konstruiert und ordnet Felder dementsprechend zu. Diese Verbindungsannahme würde es zweckmäßig machen, daß der Planer weiß, daß die Laufzeitbibliothek 66 eine größere Strang- Prozessor-Stabilität bei dieser Art von Strängen haben würde.
Diese Regeln gelten auch für verschachtelte Parallelstrukturen.

4.8 Feldgröße und -form

Ein Feld ist zahlenmäßig im Iterationsraum definiert und damit ist die Feldgröße nach Kriterien bzw. Begriffen des Iterationsraumes definiert. Der Feldgrößenvektor gibt die Anzahl von Iterationen in jeder Dimension der Feldfamilie an. Beispielsweise kann eine Schleife
welche in Felder aufgeteilt wird, einen Feldgrößenvektor von (16, 32) haben. Und damit ist die Feldgröße eine 16 · 32 = 512 Iteration. Man beachte, daß die Feldgröße nicht direkt in den Iterationsraum passen muß. Die Laufzeitbibliothek 66 paßt die Ränder der Felder an, die nach außen über den Iterationsraum hinauslaufen.
Die Feldgröße wird bestimmt, sobald die Ausführung einer Feldfamilie beginnt und bleibt während der Ausführung dieser Feldfamilie konstant. Dieselbe Feldfamilie kann in dem Programm mehr als einmal ausgeführt werden und die Feldgröße kann jedesmal verschieden sein, beispielsweise aufgrund unterschiedlicher Grenzen der Schleifen.
Die Feldformen müssen unter Berücksichtigung zweier Aufgaben ausgewählt werden: Maximierung der Parallelität und gute Ausnutzung des gesamten Cachespeichersystems. Die folgende Diskussion vermischt Betrachtungen der Abhängigkeit und des Unterseitenzugriffs, um die beiden Ziele zu erreichen.
Ein Feld ist ein rechtwinkliges, n-dimensionales Parallelepiped mit einer Dimension, welche jeder der Dimensionen in dem Iterationsraum entspricht. Die Frage nach der Feldform ist - wie lang sollte das Feld in jeder Dimension sein? Die grundlegende Idee besteht darin, die Felder in Richtung der Arraybezüge zu "strecken" und die Felder in Richtung der Abhängigkeit zu "strecken".
Der erste Punkt vermeidet Konkurrenz zwischen zwei oder mehr s-Strängen für dieselbe Unterseite. Der zweite Punkt minimiert die Synchronisation, Felder werden Vielfache von Unterseiten oder zwei Unterseiten.
Die endgültige Entscheidung über die Feldgröße ist ein Kompromiß zwischen einander widersprechenden Betrachtungen: Einerseits möchte man genügend große Felder haben, um die unvermeidliche Zusatzbelastung des Startens jedes Feldes zu rechtfertigen. Andererseits möchten wir viele Felder haben, um die Lastverteilung zu optimieren. Nachdem die Form entschieden worden ist, bestimmen wir die tatsächliche Größe, indem wir uns die Menge an zu leistender Arbeit, die Anzahl der verfügbaren Prozessoren, etc. betrachten. Wenn die Felder zu klein sind, so "strecken" wir sie.

4.9 Feldaufteilungsstrategie

Die Feldaufteilungsstrategie ist das Verfahren, welches verwendet wird, um die Arbeit zwischen den p-Strängen aufzuteilen, so daß alle Felder, welche die Feldfamilie aufweisen, korrekt und effizient ausgeführt werden. Ähnlich wie die Feldgröße wird auch die Feldaufteilungsstrategie zu Beginn der Ausführung einer neuen Feldfamilie festgelegt. Die Laufzeitbibliothek 66 verwendet einen Selbstplanungsmechanismus, was bedeutet, daß nach einer anfänglichen Einstellung, die durch den Führer vorgenommen wird, jeder Strang seinen Arbeitsblock selbst finden kann. Demnach wird die Strategie im Hinblick darauf ausgedrückt, was ein Strang tun muß, um herauszufinden, was er als nächstes tun muß.
Es gibt zwei fundamentale Prinzipien bezüglich der Strategien der Laufzeitbibliothek 66, die durch den Wunsch nach Eleganz des Modells und geringer Allgemeinlast bezüglich der Laufzeit bestimmt sind. Das erste ist die Genauigkeit - die Strategie definiert exakt, wie das nächste Feld in jeder Situation ausgewählt wird. Die Idee besteht darin, so wenig wie möglich Berechnung für den Punkt zu hinterlassen, wenn ein Strang das nächste Feld erhalten muß und deshalb die Allgemeinlast bzw. Grundlast bei der Laufzeitverarbeitung für das Heranholen des nächsten Feldes minimal zu machen. Wenn eine Strategie ausgewählt ist, sollte das Auswählen eines neuen Feldes ein sehr schneller Vorgang sein.
Das zweite Prinzip ist Progression - die Strategien sind so strukturiert, daß die Ausführung bei einem bekannten Punkt in dem Iterationsraum beginnt und in einer bekannten Richtung fortschreitet. Die Motivation ist es, den Bedarf an komplizierten Datenstrukturen zu vermeiden, die aufzeichnen und sich erinnern, welchen Teil des Iterationsraumes sie abgedeckt haben.
Die Laufzeitbibliothek 66 berücksichtigt die folgenden Faktoren beim Entscheiden über eine Feldaufteilungsstrategie:
1) Existenz von Datenabhängigkeiten. Datenabhängigkeiten erzeugen Reihenfolgenerfordernisse zwischen den Feldern, was es notwendig macht, die Felder zu synchronisieren. Im extremen Fall kann die Datenabhängigkeit dazu führen, daß eine Feldfamilie seriell ausgeführt werden muß, weil alle Felder der Feldfamilie in derselben Ordnungsbeziehung zueinander stehen. In anderen Fällen ist ein gewisser Grad an Parallelisierung in der Feldfamilie möglich, weil jedes Feld von einer gewissen Anzahl anderer Felder unabhängig ist.
2) Spezifizierung der Strategie durch den Benutzer. Der Benutzer kann eine Strategie angeben, indem er die Umgebungsvariable PLSTRATEGY setzt, unter Verwendung der SET- Anweisung, oder indem er einen Strategiewert als Parameter an die TILE- oder AFFINITY REGION- Anweisungen leitet.
3) Spezifikation der Feldgröße durch den Benutzer. Wenn der Benutzer festlegt, daß eine Dimension mit Ordnungserfordernissen in Felder aufgeteilt werden soll, kann die Feldaufteilungsstrategie erforderlich sein, um das Ordnen bzw. die Reihenfolge zu handhaben.
Die Entscheidungstabelle der Feldaufteilungsstrategie der Laufzeitbibliothek 66 ist die folgende:
(x) = gleichgültig
Man beachte, daß die Tatsache, daß eine Feldfamilie in Felder aufgeteilt ist und daß Felder auf mehrere Stränge aufgeteilt sind, die Parallelität nicht erzwingen. Eine Feldfamilie, die Ordnungserfordernisse hat, kann in Felder aufgeteilt sein, wird aber dennoch seriell ausgeführt aufgrund der durch die Reihenfolgeninformation erforderlichen Synchronisierung. Diese Situation kann optimal sein, wenn das Fehlen der Parallelisierung aufgehoben wird durch den Vorteil des Aufrechterhaltens der Datenaffinität.
Das Folgende ist eine Beschreibung von Strategien der Laufzeitbibliothek 66.

SLICE-Strategie

Diese Strategie teilt den Iterationsraum der Feldfamilie einfach in n Felder auf, wobei n gleich der Anzahl von p-Strängen ist, die an der Konstruktion teilhaben, und sie ordnet jedem Strang ein Feld zu. Dies ist die Standardstrategie für Feldfamilien, die nicht in einem Affinitätsbereich eingeschlossen sind und sie ist dafür ausgelegt, die Zusatz- bzw. Grundlast der Feldaufteilung und die Möglichkeit der Datenkonkurrenz an den Feldgrenzen minimal zu machen.

MODULO-Strategie

Diese Strategie verteilt die Felder gleichmäßig über den Iterationsraum auf die Stranggruppe. Es sei angenommen, daß Stränge und Felder mit 0 beginnend durchnumeriert sind. Die Felder, die durch einen gegebenen Strang ausgeführt werden, sind diejenigen, für die gilt
Feld-Nr. MODULO Zahl der zugeordneten Stränge = Strangkennung
Ausgedrückt durch die Selbstplanungsstrategie bedeutet dies, daß ein Strang, dessen Strangkennung P ist, die folgenden Felder ausführt:
- erstes Feld ist dasjenige Feld, dessen Nummer dieselbe ist wie die Strangkennung
- nächstes Feld ist das vorherige Feld + (Anzahl der beteiligten Stränge)
Diese Strategie ist eine halbstatische. Sie ist dynamisch im Hinblick auf die Anzahl von Prozessoren, welche verfügbar sind, wenn die Ausführung der Feldfamilie begonnen hat, kann jedoch nicht eine Anpassung an eine Veränderung der Verfügbarkeit von Prozessoren während der Ausführung der Feldfamilie oder an eine ungleichmäßig verteilte Belastung vornehmen.
Die Hauptvorteile dieser Strategie liegen darin, daß keine Synchronisierung zwischen Feldern erforderlich ist. Außerdem ist die gesetzte Iterationsraum-Strangzuordnung dafür ausgelegt, Datenaffinität zu handhaben, insbesondere, wenn sie mit Affinitätsbereichen verwendet wird. Weiterhin ist das "Modulo"-Verteilungssystem der Iteration-Strangzuordnung dafür ausgelegt, den Lastausgleich innerhalb von Affinitätsbereichen zu optimieren, wobei jede Feldfamilie innerhalb des Affinitätsbereiches einen anderen Teil des Iterationsraumes abdecken kann. Wegen dieses Verteilungsschemas hängt der Prozentsatz an Arbeit, der jedem Strang zugeordnet ist, nicht von dem durch eine einzelne Feldfamilie verwendeten Iterationsraum ab.
Dies ist die Standardstrategie für Feldfamilien, die in Affinitätsbereichen eingeschlossen bzw. enthalten sind.

WAVEFRONT-Strategie

Diese Strategie ist dafür ausgelegt, Feldfamilien mit Datenabhängigkeiten korrekt und mit maximaler Parallelisierung auszuführen.
Bei dieser Strategie werden Felder in einem "Wellenfront"-Muster auf einer zweidimensionalen Ebene ausgeführt. Die Laufzeitbibliothek 66 wählt zwei Indizes aus der Liste von in Felder aufgeteilten Indizes aus, welche Reihenfolgenerfordernisse haben, um die 2D-Wellenfrontebene des Iterationsraumes auszubilden. Ein Index wird als der "Spalten"-Index bezeichnet, während der andere als "Unterfeld"-Index bezeichnet wird. Die Spalten der 2D-Ebene werden den Mitgliedern des ausführenden Strangteams in einer Modulo-Weise zugeordnet. Jede Spalte wird aus einer Anzahl von Feldern gebildet.
Jedes Feld hat ein danebenliegendes, dominantes Nachbarfeld, von welchem es abhängig ist und es kann mit der Ausführung nicht beginnen, bevor dieser Nachbar fertig ist. Der dominante Nachbar eines Feldes liegt in der Spalte rechts oder links, je nach den Reihenfolgenanforderungen des Spaltenindex. Das dominante Feld hat denselben Unterfeldindexwert. Die Ausführung der Feldfamilie beginnt an einer der vier Ecken der 2D-Ebene, abhängig von der Reihenfolge in dem Spalten- und dem Unterfeldindex.
Diese Strategie versucht ebenfalls, Felder gleichmäßig über den Iterationsraum auf das ausführende Strangteam zu verteilen und sie ist kompatibel mit der Verwendung der Affinitätsbereichs- Anweisung.
Die Laufzeitbibliothek 66 handhabt einen Iterationsraum mit Reihenfolgenerfordernissen, welcher mehr oder weniger als zwei Indexdimensionen hat, auf einer Anzahl verschiedener Wege. Wenn der Iterationsraum nur einen Index hat und ein Reihenfolgenerfordernis hat, so muß der Ablauf seriell erfolgen und die Laufzeitbibliothek 66 versucht dann, ein Feld zu erzeugen. Wenn der Benutzer das Feldaufteilen durch Angeben einer Feldgröße erzwingt, führt die Laufzeitbibliothek 66 die Feldfamilie nach dem 2D-Wellenfrontmuster aus, wobei der Unterfeldindex 1 ist.
Wenn der Iterationsraum mehr als zwei Dimensionen hat, jedoch nur zwei Indizes Ordnungserfordernisse haben, so verarbeitet die Laufzeitbibliothek 66 die Feldfamilie als eine Serie von 2D-Ebenen, wobei die Wellenfrontstrategie auf jeder Ebene unabhängig ausgeführt werden kann.
Wenn es mehr als zwei Dimensionen gibt und mehr als zwei Indizes, die Ordnings- bzw. Reihenfolgenerfordernisse haben, teilt die Laufzeitbibliothek 66 die zusätzlichen geordneten Indizes nicht in Felder auf und erzeugt "blockförmige" oder umfangreichere Felder, um nach der 2D- Wellenfrontstrategie vorzugehen.
Benutzerspezifizierte Feldgrößen, die eine Feldaufteilung in mehr als zNei geordnete Indizes erfordern, werden zurückgewiesen bzw. verweigert.

GRAB-Strategie

Diese Strategie gibt Felder nach dem Prinzip "wer zuerst kommt, mahlt zuerst" an die Stranggruppe aus. Jeder Strang muß ein gemeinsames bzw. eine Verbindung für den Zugriff auf ein Feld für die Ausführung erhalten. Diese Strategie ist dafür ausgelegt, einen Lastausgleich zwischen den Strängen der Stranggruppe zu schaffen.
Man beachte, daß diese Strategie keine Datenaffinitätsgesichtspunkt berücksichtigt, wenn Felder den Prozessoren zugeordnet werden und daß es keine gute Wahl einer Strategie in Verbindung mit Affinitätsbereichen wäre.

4.10 Relative Vorteile der Strategien

Die halbstatische MODULO-Feldaufteilungsstrategie hat zwei Hauptvorteile: Es ist einfach, eine Datenaffinität aufrechtzuerhalten und sie minimiert die Synchronisation. Andererseits sind die Zuordnungen von Feld zu Strang statisch und passen sich während der Ausführungszeit nicht an ungleich verteilte Lasten an.
Die SLICE-Feldaufteilungsstrategie ist ebenfalls halbstatisch und ha# den geringsten Aufwand hinsichtlich der Feldaufteilung, enthält jedoch auch keinerlei Ansatz zur Aufrechterhaltung einer Datenaffinität über die Feldfamilien.
Die GRAB-Feldaufteilungsstrategie ist dynamisch und beschäftigt jeden Strang so gut wie möglich, bewirkt jedoch sehr wahrscheinlich auch, daß eine Datenwanderung häufiger auftritt. Zusätzlich zu Problemen des Affinitätsverlustes hat man einen zusätzlichen Synchronisationsaufwand aufgrund der Verriegelung bzw. Anbindung, die erforderlich ist, um auf ein neua Feld zuzugreifen.
Die WAVEFRONT-Feldaufteilungsstrategie ist erforderlich, wenn Feldfamilien Erfordernisse hinsichtlich ihrer Reihenfolge haben, die durch Datenabhängigkeiten verursacht sind. Die Datenaffinität wird beibehalten, ebenso wie bei der Modulo-Strategie, jedoch erzeugt die erforderliche Synchronisierung von Feld zu Feld einen zusätzlichen Aufwand.

4.11 Arbeitsplanbeispiele

Das Folgende sind einige wenige Beispiele des von der Laufzeitbibliothek 66 ausgewählten Arbeitsplanes zur Ausführung von in Felder aufgeteilten Schleifen. Einzelheiten dahingehend, warum ein bestimmter Arbeitsplan ausgewählt wurde, werden nicht mitgeteilt, stattdessen soll nur versucht werden, einen Eindruck von dem Verhalten verschiedener Arbeitspläne zu vermitteln.

Beispiel 1

Ein 2D-Iterationsraum wird in 2D-Felder aufgeteilt. Die Anzahl der verfügbaren Prozessoren ist kleiner als die Anzahl von Spalten. Es gibt keine Abhängigkeit.
Der Arbeitsplan ist in Fig. 9A wiedergegeben. Dort ist
Anzahl der Prozessoren: N
Feldgröße: eine komplette Spalte
Strategie: Modulo

Beispiel 2

Wie oben, jedoch gibt es diesmal eine Abhängigkeit in beiden Richtungen: Die verwendete Strategie ist die Modulo-Strategie mit Abhängigkeit (Wellenfront). Man beachte, daß diese Strategie effizient hinsichtlich der Datenaffinität ist, wenn sie in derselben Affinitätsgruppe mit der normalen Modulo-Strategie verwendet wird, die in dem vorherigen Beispiel dargestellt ist. Der Arbeitsplan ist in Fig. 9B wiedergegeben, dort ist
Anzahl der Prozessoren: N
Feldgröße: Blöcke von Spaten
Strategie: Wellenfront

Beispiel 3

Datenaffinität ist kein Problem, Lastverteilung ist wichtig. Es gibt keine Abhängigkeit. Der SSB zeigt sowohl in Richtung i als auch in Richtung j Index.
Der Arbeitsplan ist in Fig. 9C wiedergegeben. Dort ist
Anzahl der Prozessoren: N
Feldgröße: Spalten
Strategie: GRAB
Man beachte, daß in diesem Beispiel die Pfeile zeigen, wie die Felder numeriert sind. Dies darf nicht mit einer Reihenfolge von Feldern verwechselt werden. Die Numerierung ist nur eine Art und Weise, um Übersicht darüber zu behalten, was ausgeführt worden ist. Die Art der Numerierung der Felder ist willkürlich und gibt keine bestimmte Reihenfolge wieder, in welcher die Felder ausgeführt werden müssen.

5. Affinitätsbereich

Die Laufzeitbibliothek 66 versucht, Arbeit in einer Weise auf Stränge zuzuordnen, die die Konkurrenz und Datenbewegung minimal macht.
Die Erzeugung eines Affinitätsbereiches ist eine Art und Weise, wie man die Entscheidung über die Feldaufteilungen des Arbeitsplanes, die für eine Gruppe von Feldfamilien getroffen werden, koordiniert. Die folgenden Annahmen werden gemacht, um dieses Ziel zu unterstützen:
1. Datenbewegung ist aufwendig.
2. Die Feldfamilien innerhalb des Affinitätsbereiches beziehen sich auf dieselben Daten.
3. Die Feldfamilien innerhalb des Affinitätsbereiches haben die Tendenz, dieselbe Zuordnung von Datenraum zu Iterationsraum zu haben.
4. Der Datenraum ist entlang von Unterseitengrenzen ausgerichtet und Felder können so konstruiert werden, daß Datenkonkurrenz vermieden wird.
In früheren Abschnitten wurde die Entscheidung über den Arbeitsplan als eine zweiteilige Entscheidung beschrieben, mit einer Komponente der Feld-Strang-Zuordnung und einer Feldgrößenkomponente. Wenn ein Affinitätsbereich bestimmt wird, werden diese Entscheidungen über den gesamten Satz von Feldfamilien in dem Affinitätsbereich getroffen.
Die Feld-Strang-Zuordnung wird über Feldfamilien hinweg aufrechterhalten, so daß derselbe Strang (und hoffentlich auch derselbe Prozessor) auf jedem Feld arbeitet, so daß die Datenlokalität aufrechterhalten wird. Die Affinitätsbereichs-Anweisung ist nur mit gewissen Feldaufteilungsstrategien effektiv. Beispielsweise erlaubt die GRAB-Feldaufteilungsstrategie nicht die Aufrechterhaltung einer Feld-Strang-Zuordnung.
Die Entscheidung über die Feldgröße wird ebenfalls unter Berücksichtigung des Iterationsraumes aller Feldfamilien in dem Affinitätsbereich und nicht nur des Iterationsraumes einer einzelnen Feldfamilie getroffen. Im Ergebnis verwenden alle Feldfamilien dieselbe Feldgröße gemeinsam, was es möglich macht, über Feldfamilien hinweg eine Feld-Strang-Zuordnung aufrechtzuerhalten bzw. beizubehalten.
Die Entscheidung über den Feldarbeitsplan kann Faktoren einbeziehen, die nur einige der Feldfamilien betreffen, die aber auf alle Feldfamilien ausgedehnt werden. Beispielsweise kann auf einem bestimmten Index für einige der Feldfamilien eine Datenabhängigkeit vorliegen. Der Effekt, den die Abhängigkeit auf die Feldaufteilungsstrategie hat, gilt nicht für alle Feldfamilien in dem Affinitätsbereich.
Man beachte, daß die Erzeugung eines Affinitätsbereichs nur eine Frage der Effizienz ist.

5.1 Erkennen eines Affinitätsbereiches

Affinitätsbereiche können durch den Benutzer bestimmt oder durch das Kompilierungssystem 60 identifiziert werden.

5.2 Gemeinsamer Indexsatz

Es muß möglich sein, daß alle Schleifensätze in dem Affinitätsbereich bezüglich desselben Satzes von Indizes in Felder aufgeteilt werden. Dies ist die "gemeinsamer Indexsatz"-Regel. Dies ist erforderlich, weil an der Affinität ausgerichtete Strategien eine Funktion für die Iteration-Prozessor- Zuordnung benötigen, welche festlegt, welcher Prozessor das Feld bearbeitet. Wenn die Anzahl der in Felder aufgeteilten Indizes von Schleifensatz zu Schleifensatz variiert, so schlägt diese Zuordnung fehl. Dies bedeutet nicht, daß jede Feldfamilie identische in Felder aufgeteilte Indizes haben muß, sondern nur, daß es eine Schnittmenge von Indizes zwischen den verschiedenen Schleifensätzen gibt.

6. Probleme der Leistungsfähigkeit

6.1 Allgemeinlasten

Es gibt Allgemeinlasten bzw. einen Grundaufwand bezüglich der folgenden Betriebsgesichtspunkte: (1) Affinitätsbereich (Erzeugen der Vorlage), (2) Beginn der Feldfamilie (Erzeugen des MCB), (3) Auswählen des nächsten Feldes (durch jeden Strang).

6.2 Entscheidungsfindung der Laufzeitbibliothek 66

Die Laufzeitbibliothek 66 wird hauptsächlich unter dem Gesichtspunkt der Effizienz entworfen bzw. gestaltet. Ein wichtiges Konzept ist das Vorbringen bzw. Voranbringen von Entscheidungen zum frühestmöglichen Zeitpunkt. Offensichtlich ist es effizienter, eine Entscheidung bereits zum Zeitpunkt des Kompilierens anstatt während des Programmlaufs (der Laufzeit) zu treffen. Konsequenterweise ist es effizienter, eine Entscheidung zu treffen, wenn eine Feldfamilie mit der Ausführung beginnt anstatt beim Beginn der Ausführung jedes Feldes.
Das Verfahren der Laufzeitbibliothek 66 liegt darin, eine Entscheidung so schnell wie möglich zu treffen, und zwar auf Basis sämtlicher verfügbarer Information. Wenn die Entscheidung getroffen ist, so vergißt die Laufzeitbibliothek 66 die Gründe hierfür. Das Ziel ist es, daß zu dem Zeitpunkt, zu welchem ein bestimmter Strang das nächste Feld zur Ausführung finden muß, dies ein sehr einfacher Vorgang ist, der typischerweise einige einfache Vergleiche und Additionen beinhaltet.
Während der Laufzeit ist, wenn die Laufzeitbibliothek 66 damit beginnt, eine Feldfamilie auszuführen, sämtliche Information über diesen Schleifensatz bereits bekannt, und zwar ob eine Abhängigkeit zwischen den Feldern vorliegt oder nicht, wie viele Prozessoren verfügbar sind, die Größe der Schleife (Grenzen) etc. Auf dieser Basis kann die Laufzeitbibliothek 66 über eine Feldaufteilungsstrategie entscheiden.
Es gibt viele Faktoren, die die Auswahl der Feldaufteilungsstrategien beeinflussen. Einige von ihnen sind zum Zeitpunkt der Kompilierung bekannt, beispielsweise die Abhängigkeit oder der Arbeitsumfang in der Schleife. Andere können zum Zeitpunkt der Kompilierungszeit bekannt sein - z. B. die Anzahl verfügbarer Prozessoren. Ein Teil der Information ist im allgemeinen während der Laufzeit bekannt, ist jedoch in der Praxis sehr oft wieder schon zur Kompilierungszeit bekannt (oder dem Benutzer bekannt, der sie über Anweisungen bereitstellen kann).
Das System hat einige Entscheidungspunkte, wo Entscheidungen getroffen werden können. Diese liegen zur Kompilierungszeit bei dem Kompilierungssystem 60. Während der Laufzeit liegen sie bei der Laufzeitbibliothek 66 beim Starten einer neuen Feldfamilie (_pr_execute_tiles), und wenn das nächste Feld für die Ausführung gesucht wird (_pr_tile_next).
Das Folgende ist eine Liste von Faktoren, die die Entscheidungen der Laufzeitbibliothek 66 beeinflussen können. Die Reihenfolge dieser Faktoren, wie sie hier wiedergegeben wird, ist im wesentlichen zufällig.
- Größe der Schleife (Grenzen)
- statischer Umfang der Arbeit in einer Iteration
- dynamischer Umfang der Arbeit in einer Iteration
- Abhängigkeit zwischen den Feldern
- Zuordnung von Iterationen zu Daten
- Anzahl der Prozessoren
- Datenaffinität (SSB)
- Vorgeschichte (Affinitätsbereich)
- Ressourcen- (Prozessoren-) Verfügbarkeit (Lastausgleich)
- [wichtiges Array]

7. Architektur der Laufzeitbibliothek 66

7.1 Blockdiagramm

Fig. 1 ist ein Blockdiagramm höherer Ebene der Laufzeitbibliothek 66. Es beschreibt die Hauptprogramme und den Steuerungsstrom bzw. -ablauf. Die Funktion dieser Programme bzw. Unterprogramme wird im folgenden beschrieben.
_pr_programme_master mit wird ganz am Anfang der Ausführung eines Programms aufgerufen. Es liest die Umgebungsvariable der Laufzeitbibliothek 66, um die Benutzerkonfiguration aufzunehmen (wie z. B. die gewünschte Anzahl von Prozessoren). Es führt eine allgemeine Initialisierung der Laufzeitbibliothek 66 aus.
_pr_slave ist der "Haupt"-Sklave. Es gibt viele von ihnen, die gleichzeitig laufen - dies ist im wesentlichen eine Leerlaufschleife. Wenn der Leiter "den Schalter schließt", so ruft dies den Feldaufteilungsgenerator (pr tile_gen) auf und wenn er seine Arbeit beendet, so kehrt er zu pr_slave zurück und bleibt in der Leerlaufschleife, bis der Leiter es ein nächstes Mal laufen läßt.
_pr_execute_tiles_start zum Ausführen einer Feldfamilie: Zuordnen von Strängen (entweder Erzeugen derselben oder Verwenden von vorhandenen). Initialisiert auch die Ausführungsdaten für eine bestimmte in Felder aufgeteilte Schleife. Dies umfaßt die Entscheidung über die Feldaufteilungsstrategie und andere Aspekte der Initialisierung. Sein Ausgang wird in eine zentrale Datenstruktur gegeben, die als MCB (Master Control Block - Hauptsteuerungsblock) bezeichnet wird, die für alle Stränge sichtbar ist. Nachdem dies geschehen ist, wird der Leiter als solcher nicht mehr benötigt. Der Leiter schickt die Sklaven zur Arbeit und schließt sich an, das heißt er ruft pr_tile_gen auf.
Nach der Rückkehr von pr_tile_gen nimmt er seine Verantwortlichkeit als Leiter wieder auf: Er wartet, bis alle Sklaven ihre Arbeit beendet haben, führt die notwendige "Reinigung" aus und kehrt zu dem Aufrufenden (Programm) zurück.
Der MCB enthält die Information bezüglich der Felder. Der erste Abschnitt enthält Information über die Feldfamilie. Der zweite Abschnitt enthält Information über jede Dimension der Feldfamilie (Ordnung) - und enthält damit Arrays (d) von Gebieten, wobei d = 1 ... order (Ordnung) ist. Ein typischer Wert von "order" ist klein (4 ist ausreichend, 8 ist mehr als ausreichend).
In der folgenden Tabelle steht jedem Gebiet ein Buchstabe voran, der seine charakteristischen Eigenschaften kennzeichnet und zwar bezüglich des Zeitpunktes, zu welchem es seinen Wert erhält: "C" steht für Kompilierungszeit; "I" steht für die Initialisierung des MCB, das heißt einmal für jede Ausführung einer Feldfamilie. MCB - Hauptsteuerungsblock
_pr_tile_gen ist das Programm, welches den aktuellen Aufruf der Aufgabenunterprogramme mit den entsprechenden Argumenten ausführt,
_pr_tile_next ist das Programm, welches das nächste durch diesen Strang auszuführende Feld auswählt. Es liefert eine Liste von ganzen Zahlen zurück, welche die Liste der unteren Grenze eines Feldes, das heißt die Ecke des Feldes, bilden. Da die feldgröße festgelegt ist, ist dadurch das Feld definiert.
_pr_tile_next befragt den MCB und an dieser Stelle übt die Feldaufteilungsstrategie eigentlich ihren Einfluß aus: Die grundlegende Steuerstruktur von _pr_tile_next ist eine Schalterklärung (wie sie in der Programmiersprache C bezeichnet wird) oder eine Fallerklärung (Case Statement, wie sie in Pascal bezeichnet wird) entsprechend dem Arbeitsplan.
_pr_execute_parallel-Abschnitte ordnet Sklaven für die Ausführung der Abschnitte zu und übergibt jedem von ihnen einen zweiten Block.
_pr_end wird einmal ausgeführt, wenn das Programm beendet wird. Zusätzlich zur generellen Reinigung erzeugt es Statistiken und Berichte.

Laufzeitbibliothek - Interne Architektur

1. Übersicht

Die folgenden Abschnitte beschreiben die Laufzeitbibliothek 66 genauer und insbesondere den internen Aufbau einer bevorzugten Ausführungsform derselben.

2. Das Programmiermodell

Die Laufzeitumgebung der Laufzeitbibliothek 66 ermöglicht es, daß Programme auf dem digitalen Datenprozessor 10 parallel ablaufen. Die gehandhabten bzw. behandelten parallelen Konstruktionselemente sind Felder, parallele Abschnitte oder parallele Bereiche. Die Parallelität ist in allen Konstruktionselementen implementiert durch die Verwendung von Strängen. Der gesamte Code außerhalb des parallelen Konstruktionselementes wird seriell durch einen der Programmstränge ausgeführt. Der gesamte serielle Code wird durch denselben "Haupt"-Programmstrang ausgeführt.

2.1 Implementierung von Parallelität

Die Programmausgangsgrößen von dem Kompilierungssystem 60 werden mit der Laufzeitbibliothek 66 verknüpft, um diese Konstruktionselemente parallel auszuführen. Ein solches Programm wird ein "Presto-Programm" genannt. Programme, die parallele Konstruktionselemente enthalten und die mit einem "kein paralleler Laufzeitschalter" kompiliert werden, behandeln die parallelen Konstruktionsanweisungen als Kommentare und machen die Ausführung seriell ohne zusätzlichen Aufwand durch die Laufzeitbibliothek 66.
Jedes parallele Konstruktionselement wird durch eine Gruppe von Strängen ausgeführt, die ein Team genannt werden, welches ein oder mehrere Mitglieder hat. Zum Zwecke der Synchronisierung hat jedes Team ein Mitglied, welches als Teamleiter bezeichnet wird. Wenn das Programm beginnt, gibt es einen Strang, der als Programmleiter gekennzeichnet ist. Die Laufzeitbibliothek 66 verwaltet die Strangteams für den Benutzer transparent, der Benutzer kann jedoch die Teams auch ausdrücklich steuern.
Ein Strang kann eines oder mehrere Codesegmente haben, die er ausführen muß. Die Laufzeitbibliothek 66 implementiert eine Anzahl von Strategien. Wenn das parallele Konstruktionselement eine Feldfamilie ist, so hat jeder Strang zumindest eines und typischerweise viele Felder auszuführen. In den Parallelabschnitts- und parallelen Bereichskonstruktionselementen hat jeder Strang nur ein Codesegment auszuführen.

2.2 Übergang zwischen seriellen und parallelen Teilen des Programms

Alle Serienteile des Programms werden durch einen einzelnen Strang, das Hauptprogramm bzw. den Programm-Master, ausgeführt. Wenn ein paralleles Konstruktionselement auftritt, wird dem Konstruktionselement eine Gruppe von Strängen zugeordnet. Der Anfang des Konstruktionselementes ist ein Synchronisierungspunkt für die Gruppe von Strängen, während das Ende des Konstruktionselementes ein Synchronisierungspunkt für den Master der Gruppe ist. Jedes Gruppenmitglied beginnt den parallelen Abschnitt, sobald die Stranggruppe zugeordnet ist und der Master der Gruppe den vorangehenden seriellen Code beendet hat. D e Gruppenmitglieder müssen auf den Gruppenmaster warten, jedoch nicht auf die (anderen) Mitglieder.
Am Ende führt der Master der Gruppe erst dann den auf den parallelen Abschnitt folgenden Code aus, wenn alle Gruppenmitglieder ihre Arbeit beendet haben; der Gruppenmaster muß auf alle Mitglieder warten. Während der seriellen Abschnitte des Programms befinden sich alle Stränge mit Ausnahme des Programm-Masters im Leerlauf.
Der Synchronisationspunkt am Ende des Konstruktionselementes wird an einer Stelle angeordnet, die auch als Punkt der Codeabhängigkeit bezeichnet wird.
Parallele Konstruktionselemente können verschachtelt sein. Der generelle Implementierungsansatz ist auf jedem Niveau derselbe. Für jedes neue Konstruktionselement gibt es eine lokale Gruppe von Strängen mit einem lokalen Master.

2.3 Ressourcenzuordnung zwischen parallelen Konstruktionselementen

Die Laufzeitbibliothek 66 delegiert viel von der Aufgaben- und Lastverteilung zwischen den Prozessoren auf den Planer des Betriebssystems ("OS"). Die Laufzeitbibliothek 66 beeinflußt die Ressourcenzuweisung durch Auswählen der Anzahl von Strängen für die Verwendung für ein paralleles Konstruktionselement. Das OS verwaltet die Ressourcenzuordnung zwischen den Strängen. Es können zu jedem beliebigen Zeitpunkt mehr oder weniger Stränge als verfügbare Prozessoren vorhanden sein.

2.3.1 Feldaufteilung

Bei der Feldaufteilung betrachtet die Laufzeitbibliothek 66 die Menge bzw. Zahl der verfügbaren Ressourcen und verwendet für jede Feldfamilie n Stränge, wobei n kleiner oder gleich der Anzahl der für dieses Programm verfügbaren Prozessoren ist. Der Standard besteht darin, die maximale Anzahl von verfügbaren Prozessoren zu benutzen. Wenn die Feldfamilie so strukturiert ist, daß es sich nicht lohnt, die maximale Anzahl zu benutzen, so wird eine kleinere Anzahl von Strängen ausgewählt. Dieser Algorithmus wird unabhängig vom Verschachteln verwendet.
Wenn die GRAB-Strategie verwendet wird, läßt die Laufzeitbibliothek 66 den Planer alle Strang-Prozessor-Verbindungen und Affinitätsbetrachtungen handhaben. Wenn die MODULO-, WAVEFRONT- oder SLICE-Strategie verwendet wird, versucht die Laufzeitbibliothek 66 anzunehmen, daß die Strang-Prozessor-Verbindung konstant ist. Die Laufzeitbibliothek 66 konstruiert und ordnet Felder dementsprechend zu. Diese Verbindungsannahme macht es zweckmäßig, den Planer darüber zu informieren, daß die Laufzeitbibliothek 66 eine größere Strang-Prozessor-Stabilität für diese Arten von Strängen erfordert.

3. Schnittstellen (Interfaces)

3.1 Laufzeitbibliothek 66/Kompilierungssystem 60

Der Vorprozessor 60a transformiert den in einem parallelen Konstruktionselement enthaltenen Code in ein lexikalisches Unterprogramm. Das Erzeugen des neuen Unterprogramms ermöglicht es, daß die Stränge der Laufzeitbibliothek 66 mit demselben Code parallel laufen. Das Kompilierungssystem 60 erzeugt außerdem Aufrufe an Laufzeitprogramme, die die parallele Ausführung einstellen und veranlassen.
Bei dem Feldkonstruktionselement besteht das lexikalische Unterprogramm aus dem durch die Feld-Anweisungen umfaßten Code. Es wird ein Unterprogramm erzeugt und durch jedes der Stranggruppenmitglieder mit unterschiedlichen Schleifengrenzen aufgerufen.
Alle Variablen, die für den Code sichtbar sind, welcher zum "Aufrufenden" des lexikalischen Unterprogramms wird, müssen für das Unterprogramm selbst verfügbar sein. Da jedoch das Unterprogramm durch ein Programm der Laufzeitbibliothek 66 aufgerufen wird, wird ein Mechanismus benötigt, um den Anwendungsbereich abzudecken. Unter der Information, die von dem Kompilierungssystem 60 an die Laufzeitbibliothek 66 geleitet wird, befindet sich ein Zeiger auf das lexikalische Unterprogramm und den efp (enclosing frame pointer - umfassender Framezeiger) des Aufrufcodes. Dies ermöglicht es, daß die Stränge der Laufzeitbibliothek 66 das Unterprogramm mit dem angemessenen Umfang aufrufen kann.

3.1.1 Generelle Schnittstelle

Die Laufzeitbibliothek 66 und das Kompilierungssystem 60 verwenden die folgenden Werte für bestimmte Schnittstellenargumente:
- Boolesche Werte: 0 = FALSCH, 1 = WAHR
- Strategiewerte: 1 = GRAB, 2 = MODULO, 3 = WAVEFRONT, 4 = SLICE, -1 = nicht angegeben
- im allgemeinen ist -1 = nicht spezifiziert
- Größen: 0 = gesamter Iterationsraum, n = Wert von n

3.1.2 Beginn der Affinitätsbereiche

Wenn das Kompilierungssystem 60 auf eine Benutzeranweisung für einen Affinitätsbereich stößt oder wenn es einen potentiellen Affinitätsbereich erkennt, so erzeugt es einen Aufruf an _pr_start_affinity mit Information zum Initiieren des Affinitätsbereichs-Arbeitsplanes (von dem Kompilierungssystem 60 zu dem Bereichsarbeitsplan). Dies überträgt nur die auf Affinität bezogene Information von dem Kompilierungssystem 60 auf die internen Datenstrukturen der Laufzeitbibliothek 66 und löst keinerlei parallele Ausführung aus. Man beachte, daß dieses Interface sowohl für lexikalisch getrennte Feldfamilien als auch für Feldfamilien gilt, die innerhalb einer enthaltenden Schleife verschachtelt sind, und daß die Laufzeitbibliothek 66 zwischen den beiden nicht unterscheidet. Die Benutzeranweisung lautet:
Dies führt dazu, daß der Compiler einen Ruf erzeugt an:
Argumente sind:
Num_Indices (long): Dies ist die Anzahl von durch den Benutzer aufgelisteten Indizes. Das Kompilierungssystem 60 überprüft, ob die vom Benutzer angegebenen Indizes ein Teilsatz der Schnittmenge aller Indizes sind, die durch die umfaßten Feldfamilien verwendet werden.
Wenn es keinen gemeinsamen Satz von Indizes gibt, so erzeugt das Kompilierungssystem 60 eine Warnbotschaft für den Benutzer, daß der Affinitätsbereich nicht möglich war und gibt den Ruf an _pr_stat_affinity aus.
Code_size (long): Durchschnittliche Codegröße über alle Feldfamilien, die durch den Affinitätsbereich abgedeckt werden.
Numthreads (long): -1 = nicht spezifiziert, 0..n = vom Benutzer eingegebener Wert. Die Anzahl der innerhalb dieses Affinitätsbereiches durch die Feldfamilien zu benutzenden Stränge.
Strategy (long): Durch alle Feldfamilien innerhalb des Affinitätsbereiches zu verwendende Strategie. Der Anwendungsbereich erstreckt sich nur auf den Affinitätsbereich. -1 = nicht spezifiziert, 1 = GRAB, 2 = MODULO.
Tile_size_spec (long): 0, wenn die Feldgröße nicht vom Benutzer übermittelt wurde, 1, wenn sie vom Benutzer übermittelt wurde.
Teamid (long): -1, falls nicht angegeben, anderenfalls die Team-ID, die durch den Benutzer übermittelt wurde.
Intercall: -1, falls nicht spezifiziert, ansonsten 0 oder 1.
Order_num (long): Anzahl der bereitgestellten Abhängigkeitsvektorwerte. Man beachte, daß der Benutzer einige Abhängigkeitswerte spezifizieren kann.
Dependency_vector [order_num] (long []): Abhängigkeitswerte über alle durch den Affinitätsbereich abgedeckten Feldfamilien. Dies ist die Vereinigung aller Abhängigkeitswerte, die für die Feldfamilie spezifisch sind. Beispielsweise:
Abhängigkeitswerte sind immer positive Zahlen im Gegensatz zu dem Abhängigkeitsvektor, der in dem pr_execute-Aufruf übermittelt wurde. Der Richtungsgeber (director) wird ignoriert. Wenn der Benutzer irgendwelche Abhängigkeitswerte spezifiziert hat, so wird dieser Wert für diesen Index übergeben, ansonsten berechnet das Kompilierungssystem 60 den Wert.
Low_bound [num_indices] (long []): Der niedrigste untere Grenzwert für jeden Index über den Affinitätsbereich hinweg. Durch den Benutzer spezifiziert.
High bound [num_indices] (long []): Analog zu unterem Grenzwert, wird immer vom Benutzer geliefert.
Affinity [num_indices] (SSB_T): SSB-Werte für jeden Index, der durch die affinity.group abgedeckt wird. Gültige SSB-Werte für das Kompilierungssystem 60 sind NONE und SP. Abschnitt 6.4.1 der SSB-Berechnung beschreibt, wie SSBs erzeugt werden.
Tile_size_vals [num_indices] (long []): Vom Benutzer spezifizierte Feldgröße, wird direkt aus der Fortran-Anweisung weitergeleitet. Das Kompilierungssystem 60 überprüft, ob die Zahl der Feldgrößenwerte mit dem Wert für num_indices zusammenpaßt. Die Feldgröße bleibt nur für diesen einen Affinitätsbereich wirksam. Siehe Aktion bei der TILE- (Feld-) Anweisung für das Format der Werte.

3.1.3 Ende der Affinitätsbereiche

Wenn das Kompilierungssystem 60 auf eine Anweisung END AFFINITY REGION trifft oder zum Ende eines von dem Kompilierungssystem 60 erfaßten Affinitätsbereiches kommt, so erzeugt es einen Aufruf an

3.1.4 Satzanweisung

Wenn das Kompilierungssystem 60 auf eine Anweisung SET trifft, werden die geeigneten Laufzeitparameter der Laufzeitbibliothek 66 verändert. Das Kompilierungssystem 60 überprüft, daß diese Anweisung nicht innerhalb eines parallelen Konstruktionselementes verwendet wird. Dies löst keinerlei parallele Ausführung aus.
Die Benutzeranweisung ist:
Jedes Variable/Benutzer-Wertepaar ist ein Paar aus zwei langen Worten. Der weiterzuleitende Variablenwert wird in einer eingeschlossenen Datei "Runtime Library 66.h" definiert und ist das Schlüsselwort, welches mit zwei Unterstrichen vor dem Namen definiert ist. Das Kompilierungssystem 60 muß die Variablen analysieren, um die Variablenwerte zu erzeugen. Beispielsweise:
Das Kompilierungssystem 60 leitet {0, 1, 2, 3, 4} als die PL STRATEGY-Werte weiter, wobei die Strategiewerte den folgenden Wegen zugeordnet sind (NONE = 0, GRAB = 1, MODULO = 2, WAVEFRONT = 3, SLICE = 4). Diese sind in der Laufzeitbibliothek 66.h definiert. Für alle anderen Parameter ist der Benutzerwert derjenige Wert, der von dem Benutzer in der Anweisung zugeführt wird.

3.1.5 Start der Feldfamilie

Wenn das Kompilierungssystem 60 auf eine TILE-Anweisung trifft, so erzeugt es einen Aufruf eines Unterprogramms der Laufzeitbibliothek 66, welches die Feldaufteilungsinformation einstellt und eine parallele Ausführung beginnt. Die Benutzeranweisung ist:
Dies führt dazu, daß das Kompilierungssystem einen Aufruf erzeugt:
Argumente sind:
Family_name (int*): Zeiger zu einem Unterprogramm, welches den Feldhauptteil hält.
Code_size (long): Anzahl von Anweisungen in dem Hauptteil des Feldes.
Frame_pointer (char*): Framezeiger, der den Aufrufer für das Unterprogramm des Feldhauptteiles umfaßt.
Num_Indices (long): Anzahl der Schleifenindizes.
Strategy (long): -1 = nicht benutzerspezifiziert, 1 = GRAB, 2 = MODULO. Die Laufzeitbibliothek 66 führt eine Fehlerüberprüfung dahingehend durch, daß Strategy einen gültigen Wert hat. Strategy bleibt nur für diese eine Feldfamilie wirksam.
Tile_size_spec (long): 0, falls die Feldgröße nicht von dem Benutzer geliefert wird, 1, wenn sie von dem Benutzer geliefert wird.
Teamid (long): -1, wenn nicht spezifiziert, ansonsten die vom Benutzer übermittelte team_id.
Order (long): Anzahl der Ordnungsvektorwerte.
This_level_ar (long): 0, falls diese Feldfamilie nicht in einem Affinitätsbereich lexikalisch enthalten ist, 1, wenn diese Feldfamilie innerhalb eines Affinitätsbereiches lexikalisch enthalten ist.
Reduction_ptr (int*): Zeiger auf ein Unterprogramm, welches einen Code zum Beenden jeglicher Reduktionen innerhalb des Feldhauptteiles hält. Wenn dieser Zeiger nicht 0 ist, so führt jeder Strang, der an dieser Feldfamilie beteiligt ist, diesen Aufruf aus, wenn er seinen Anteil der Arbeit beendet hat. Wenn dieser Punkt bzw. Zeiger 0 ist, so hat er keinen Effekt.
Psc_ptr (int*): Zeiger auf ein Unterprogramm für die Laufzeitunterstützung von privat verwendeten Allgemeinteilen (privately shared common). Wenn dieser Zeiger nicht NULL ist, so werden die folgenden vier Schritte unternommen:
1) Der Teamleiter ruft call_pr_psc_init_mwu auf,
2) jeder Strang ruft call_pr_psc_use_mwu mit_sc_ptr als Argument auf,
3) dann folgt für den Strang calls_pr_psc_halper_leave, und
4) der Hauptstrang calls_pr_psc_master_leave.
Numthreads (long): -1 = nicht angegeben, Wert von 0..n wird vom Benutzer geliefert. Anzahl der durch die Feldfamilie zu verwendenden Stränge.
Aff_member (long): -1 = nicht spezifiziert, 0 = Benutzer möchte nicht, daß diese Familie in den umfassenden Affinitätsbereich aufgenommen wird, 1 = Feldfamilie sollte innerhalb des Affinitätsbereiches ausgeführt werden.
Dep_vector (long []): Werte von Indizes, welche Abhängigkeiten haben. Vektorwerte sind negativ, wenn die Abhängigkeit rückwärts gerichtet ist, positiv, wenn die Abhängigkeit vorwärts gerichtet ist. Beispielsweise bedeutet ein Vektorwert von -3, daß der dritte Schleifenindex, gezählt ab 1, eine rückwärtige Abhängigkeit hat.
Low_bound (long []): Untere Grenzwerte für alle Schleifenindizes.
High_bound (long []): Hohe Grenzwerte für alle Schleifenindizes.
Loop_stride (long []): Schleifenschrittwerte für alle Schleifenindizes.
Affinity [num_indices] (SSB_T): SSB-Werte für jeden Index, der durch die Feldfamilie abgedeckt wird. Gültige SSB-Werte für das Kompilierungssystem 60 sind NONE und SP. Abschnitt 6.4.1 über die SSB-Berechnung beschreibt, wie SSBs erzeugt werden.
Areg_map [num_indices] (long []): Nur dann gültig, wenn diese Feldfamilie sich in der Mitte eines von dem Benutzer bestimmten Affinitätsbereiches befindet oder durch das Kompilierungssystem 60 identifiziert ist. Für jeden Schleifenindex der Feldfamilie gilt: -1: wenn der Schleifenindex nicht für den Affinitätsbereich verwendet wird, n: wenn dieser Schleifenindex dem n-ten Schleifenindex des Affinitätsbereiches entspricht. Zum Beispiel:
Tile size vals [num_indices] (long []): Vom Benutzer spezifizierte Feldgröße, die direkt von der Fortran-Anweisung weitergeleitet wird. Das Kompilierungssystem 60 überprüft, daß die Zahl für die Feldgrößenwerte mit dem Wert für num_indices zusammenpaßt. Die Feldgröße bleibt nur für diese eine Feldfamilie wirksam.
Gültige Werte für die Feldgröße sind Konstanten, Variablen und "*".
Beispielsweise sind die folgenden Feldanweisungen gültig:
areg_shift [num_jndices] (long []): Nur gültig, wenn diese Feldfamilie sich in der Mitte eines Affinitätsbereiches befindet, welcher von dem Benutzer bestimmt wurde, oder welcher durch das Kompilierungssystem 60 gekennzeichnet wurde. Behält üblicherweise die Affinitätsausrichtung, wenn die Feldfamilien Indizes verwenden, die um einen konstanten Wert verschoben sind.
Für jeden Schleifenindex der Feldfamilie gilt: n = Betrag der für den Gebrauch von diesem Index hinzuaddiert wird.

3.1.6 Ausführung einer Feldfamilie

Die Laufzeitbibliothek 66 führt die Feldfamilie aus, indem sie ein lexikalisches Unterprogramm aufruft, welches den Feldhauptteilcode enthält, wobei die Grenzen des Iterationsraumes von diesem Feld abgedeckt werden, und einen Booleschen Wert, der anzeigt, ob der letzte Wert der Schleifenindizes erforderlich ist. Die Reihenfolge der Argumente ist nach unten begrenzt und für jeden Index in der Reihe nach oben begrenzt, worauf ast-value-needed (letzter Wert wird benötigt) folgt. Dies wird durch den Aufruf des Kompilierungssystems 60 von to_pr_execute_tiles ausgelöst.

3.2 Schnittstellenverbindung der Laufzeitbibliothek 66 mit dem Betriebssystem

Die Laufzeitbibliothek 66 delegiert viel Verantwortung für den Lastausgleich der Stränge auf den Planer des Betriebssystems ("OS"), wie oben bereits beschrieben. Die Laufzeitbibliothek 66 hat einige Kommunikation mit dem Planer bei folgenden Themen.

3.2.1 Verfügbare Prozessoren

Die Laufzeitbibliothek 66 verwendet Information über die Anzahl der für ein Programm verfügbaren Prozessoren, wenn sie Felder erzeugt. Zu Beginn fragt die Laufzeitbibliothek 66 entweder nach einer Satzzahl von Prozessoren, falls der Benutzer eine Anzahl angegeben hat, oder fragt nach der "MAX"-Anzahl (maximalen Zahl) verfügbarer Prozessoren. Der OS-Planer reagiert mit der aktuellen Zahl, die verfügbar ist.
Es gibt noch mehr Abfragekriterien, wie z. B. die Angabe einer minimalen Zahl von Prozessoren, die Anforderung, daß Prozessoren sich auf einem einzelnen Ring 0 befinden oder die Anforderung, keine I/O-Zellen zu verwenden.
Wenn der Planer die Fähigkeit hat, Prozessorsätze auszudehnen oder zusammenzuziehen, so überprüft die Laufzeitbibliothek 66 den Planer zu Beginn von jedem der n parallelen Konstruktionselemente (n ist konfigurierbar), um seine Zahl bzw. Zählung verfügbarer Prozessoren auf den neuesten Stand zu bringen.

3.2.2 Planerhinweise/Priorität

Der Planer verwendet die durch die Anwendung gelieferte Information, um eine Ressourcenzuordnung zu bzw. zwischen den Strängen zu beeinflussen. Der Planer implementiert einen Schlaf- /Aufwachmechanismus, welches Anwendungen ermöglicht, die Aufhebung der Planung von Strängen zu beeinflussen.

3.2.2.1 Synchronisierung

Die Synchronisierung der Laufzeitbibliothek 66 wird mit den Konstruktionselementen mutex und barrier bewerkstelligt, die durch die Bibliothek der p-Stränge zugeführt werden.

3.2.2.2 Leerlauf

Ein Strang "läuft", wenn er den Hauptteil des konstruktionselementes oder einen seriellen Code ausführt und er synchronisiert ("sync'ing"), wenn er in eine Synchronisierungsroutine eingetreten ist. Zu allen anderen Zeiten befindet sich ein Strang im "Leerlauf" ("idle"). Ein Strang kann in den Leerlauf kommen, wenn er Mitglied einer Stranggruppe ist, die mehrere parallele Konstruktionselemente ausführt und wenn er nicht der Master der Gruppe ist und wenn er mit dem Eintritt in die Barriere (barrier) des Konstruktionselementes fertig ist. Ein Leerlaufstrang läuft während einer konfigurierbaren Zeitdauer in einer Schleife um und gibt dann eine Schlafmeldung ab. Der Strang wird durch den Master der Gruppe wieder aufgeweckt, wenn es Zeit ist, die Barriere zu verlassen.

4. Feldaufteilung

4.1 Erzeugen von Feldgrößen

Die Feldgrößen und -formen werden bestimmt durch eine Kombination von Eingaben:
1. Speicherzuordnung des Iterationsraumes und des Zugriffs der Feldfamilie auf den Speicher (wie durch den SSB der Feldfamilie beschrieben). Der SSB wird in dem Kompilierungssystem 60 erzeugt.
2. Berücksichtigung der minimal wünschenswerten Feldgröße (wie durch die Umgebungsvariable PL_MININST_PER_TILE beschrieben).
3. Abhängigkeiten der Feldindizes.
Die Laufzeitbibliothek 66 macht mit der Feldgröße einen ersten Durchlauf unter Verwendung der SSB- und Abhängigkeitsinformation, um ein Feld mit minimaler Größe herzustellen. Die beiden möglichen, vom Kompilierungssystem 60 berechneten SSB-Werte sind NONE und SP. Dieser erste Durchlauf verbessert die SSB-Werte um die Abhängigkeitsinformation, wenn es eine Abhängigkeit auf diesem Index gibt und wenn es keine anderen Abhängigkeiten in dem Feld gibt, so wird der SSB in MAX umgewandelt, um eine Abhängigkeitssynchronisierung zu vermeiden. Wenn es eine Abhängigkeit auf diesem Index gibt, jedoch auch noch mehr Abhängigkeiten auf dem Feld, wird eine Zwischengröße von SP ausgewählt.
Die folgende Wahrheitstabelle beschreibt den Algorithmus zum Erzeugen der Feldgrößenvorlage im ersten Durchlauf.
x) = egal
Die Laufzeitbibliothek 66 übernimmt diesen ssb-Wert der Laufzeitbibliothek 66, um minimale Feldgrößen zu erzeugen. Wenn der ssb-Wert für einen Index MAX ist, so ist die Feldgröße in dieser Dimension der gesamte Iterationsraum in dieser Dimension. Wenn der ssb-Wert NONE ist, so ist die Größe in dieser Dimension der Minimalwert von einer Iteration. Wenn der ssb = SP ist, so ist die Feldgröße von diesem Index 32. Nach diesem ersten Durchlauf sollte man eine Feldform vorliegen haben, die der Abhängigkeit und den Gesichtspunkten der Unterseitenbegrenzung folgt und eine minimale Größe hat.
Die Laufzeitbibliothek 66 führt dann einen zweiten Durchlauf durch, welcher die Feldgröße mit der minimal für dieses Feld erforderlichen Größe vergleicht. Wenn die Feldfamilie nach der slice- Strategie ausgeführt wird, ist diese minimale Größe gleich der Anzahl von Anweisungen in der Feldfamilie, dividiert durch die Anzahl von Strängen in dem ausführenden Team. Ansonsten wird die minimale Größe durch die Umgebungsvariable spezifiziert, welche die minimale Größe des Feldes durch Anweisungen spezifiziert (PL_MIN_INST_PER_TILE).
Das Feld wird gestreckt, bis es diese Minimalgrößenanforderung erfüllt, wobei es innerhalb der Einschränkungen durch den SSB-Wert bleibt. Wenn eine Seite des Feldes bereits der gesamte Iterationsraum ist, so ist bezüglich dieser Dimension nichts weiter zu tun. Wenn die Größe einen SSB-Wert von SP hat, so wird das Feld zu Mehrfachen von 32 gestreckt. Wenn diese Seite einen SSB-Wert NONE hat, so wird die Feldgröße in dieser Dimension in Einer-Schritten gestreckt.
Die Laufzeitbibliothek 66 wählt Indizes aus, uri das Feld in der folgenden Reihenfolge zu strecken:
Wenn die Strategie der Feldfamilie WAVEFRONT ist, so wird zuerst der Spaltenindex gestreckt und im Anschluß daran der Unterfeldindex. Aufgabe ist es, die Feldgrößen in den Maßen bzw. Dimensionen zu erhöhen, in welchen es Datenabhängigkeiten gibt, um die Synchronisation zwischen Feldern minimal zu machen.
Indizes mit SSB-Werten von SP werden zur Optimierung der Affinität als nächstes ausgewählt. Diese Indizes werden ihrerseits gestreckt. Wenn beispielsweise eine Feldfamilie Indizes 1j und k hat, mit Indizes 1 und j mit SSB-Werten von SP, so streckt die Laufzeitbibliothek 66 i, dann j, dann i, etc., bis entweder i und/oder j erschöpft ist oder das Feld seinen minimalen Wert erreicht hat. Indizes mit SSB-Werten von 0 werden als letzte ausgewählt.

4.2 Feld/Strang-Zuordnung

Es gibt mehrere Algorithmen, die auch Strategien genannt werden, um Felder Strängen zuzuordnen. Von den vier oben beschriebenen verwendet die Grab-Strategie Gesichtspunkte des Lastausgleichs, während die Modulo-, Wavefront- und Slice-Strategien Gesichtspunkte der Datenaffinität berücksichtigen bzw. verwenden. Die Wavefront-Strategie ist außerdem dafür ausgelegt, Feldfamilien mit Ordnungserfordernissen mit so viel Parallelisierung wie möglich auszuführen.

4.2.1 Grab-Strategie

Bei der Grab-Strategie werden Felder Strängen gemäß dem Algorithmus "wer zuerst kommt, wird zuerst" bedient, zugeordnet.

4.2.2 Modulo-Strategie

Bei der Modulo-Strategie werden Felder gleichmäßig über die Stränge verteilt. Die Zuordnung ist ((tilenumber % total_tiles (Gesamtzahl der Felder)) = Strang-ID). Dies kann bezüglich paralleler Abschnitte modifiziert werden, so daß die Strang-ID die Strang-ID der lokalen Gruppe ist.
Zusätzlich versucht die Laufzeitbibliothek, wenn die Modulo-Strategie in Verbindung mit Affinitätsbereichen verwendet wird, daß jeder Strang Felder ausführt, die in den Iterationsraum fallen, die dieser Strang in früheren Feldfamilien verwendet hat, um eine Datenaffinität aufrechtzuerhalten. Die Laufzeitbibliothek 66 betrachtet nur den Iterationsraum und nicht den Datenraum, unter der Annahme, daß die Zuordnung Iterationsraum → Datenraum über alle Feldfamilien innerhalb des Affinitätsbereiches hinweg konstant ist.
Die Laufzeitbibliothek 66 ist in der Lage, sich an den jedem Strang zugeordneten Iterationsraum zu erinnern und verwendet dies, um die ((tile_number % total_tiles = thread id)-Zuordnung über Feldfamilien hinweg zu normalisieren.

4.2.3 Datenabhängige Strategien

4.2.3.1 Korrektheit

Datenabhängigkeiten erzeugen ein Reihenfolgenerfordernis beim Ausführen des in Felder aufgeteilten Codes. Felder werden in einer Sequenz ausgeführt, die die Abhängigkeitsrichtung nicht beeinträchtigt, um korrekte Ergebnisse zu garantieren.

4.2.3.2 Leistungsfähigkeit

Da Datenabhängigkeiten den Feldern Ordnungsbeschränkungen auferlegen, lohnt sich eine Feldaufteilung in Richtung einer Abhängigkeit oftmals nicht, wenn man sie nur im Kontext der betreffenden Feldfamilie betrachtet. Beispielsweise muß ein eindimensionaler Iterationsraum mit einer Abhängigkeit in einer strikten seriellen Ordnung ausgeführt werden und der Zusatzaufwand, der für die serielle Anordnung der Felder erforderlich ist, ist vergeudet. Gesichtspunkte der Leistungsfähigkeit des gesamten Programms können jedoch dazu führen, daß die Laufzeitbibliothek 66 eine Feldaufteilung in Richtung einer Abhängigkeit in Erwägung zieht.
Die Affinität ist ein wichtiger Faktor bei der Auswahl von Feldaufteilungsstrategien, die zu der Entscheidung zu einer Feldaufteilung im Falle einer Abhängigkeit führen können. Der Zusatzaufwand der seriellen Anordnung von Feldern kann sich lohnen, wenn dadurch die Affinität der Daten für andere Feldfamilien in dem Programm aufrechterhalten wird, die keine Einschränkungen haben und vollständig parallelisiert werden können. Dies gilt unabhängig von der Datenabhängigkeit; die Sgefa-Routine von Linpack ist ein Fall, bei welchem der erste, kleinere 1D-Iterationsraum in Felder aufgeteilt wird, um mit dem zweiten, 2D-Iterationsraum konsistent zu sein.
Zusätzlich kann eine Feldaufteilung einer Dimension mit Abhängigkeit auch die Möglichkeit bieten, eine teilweise serielle Feldaufteilungsordnung zu verwenden. In solchen Fällen sind Felder in Gruppen organisiert, die seriell ausgeführt werden müssen. Innerhalb der Gruppen kann jedoch das Feld parallel ausgeführt werden. Eine partielle serielle Feldaufteilungsordnung kann nur dann verwendet werden, wenn der Iterationsraum mehr als eindimensional ist.

4.2.3.3 Wavefront-Strategie

Die Laufzeitbibliothek 66 teilt Datenabhängigkeiten in Felder auf, um Affinität zu erhalten und um eine teilweise serielle Feldaufteilungsordnung zu verwenden. Die Feldaufteilungsordnung, die implementiert werden muß, ist die Wellenfrontordnung.

5. Affinität

Ein Affinitätsbereich ist eine Ansammlung von Feldfamilien, die die Laufzeitbibliothek 66 in einer Art und Weise auszuführen versucht, so daß Datenkonkurrenz und -bewegung vermieden wird. Wenn die Laufzeitbibliothek 66 auf einen Affinitätsbereich trifft, so empfängt sie Information, die den von den Feldfamilien innerhalb des Bereiches abgedeckten Iterationsraum zusammenfaßt. Die Laufzeitbibliothek 66 muß nicht zwischen lexikalisch getrennten Feldfamilien und Feldfamilien in einer äußeren Schleife unterscheiden. Die Laufzeitbibliothek 66 verwendet diese Information, um eine Feldgrößenvorlage und eine Aufteilungsstrategie zu erzeugen, die verwendet wird wie für alle Feldfamilien innerhalb des Bereiches, was es erlaubt, daß ein Strang für jede Feldfamilie auf denselben Bereich des Iterationsraumes zugreift.
Man beachte, daß Affinitätsbereiche sinnlos sind, wenn die gewählte Feldaufteilungsstrategie die reine Grab-Strategie ist.
Affinitätsbereiche können verschachtelt sein. Jeder neue Affinitätsbereich erzeugt eine neue Stranggruppe und verwendet seinen eigenen Feldaufteilungs-Arbeitsplan.

5.1 Gemeinsamer Indexsatz

Eine Schablone bzw. Vorlage für die Feldgröße wird erzeugt durch Betrachten eines Satzes von Schleifenindizes, ihren Abhängigkeiten und ihren SSBs. Der Satz von interessierenden Schleifenindizes ist derjenige, der für alle Feldfamilien in dem Affinitätsbereich verwendet wird. Es muß ermöglicht werden, daß für alle Schleifensätze in einem Affinitätsbereich auf demselben Satz von Indizes in Felder aufgeteilt werden. Dies ist die Regel "gemeinsamer Indexsatz". Der gemeinsame Indexsatz ist ein Teilsatz der Schnittmenge von Indizes, die durch die Feldfamilien innerhalb eines Affinitätsbereiches verwendet wurden. Dies ist notwendig, weil affinitätsorientierte Strategien eine Zuordnungsfunktion Iteration → Prozessor benötigen, die festlegt, welcher Prozessor das Feld ausführt. Wenn die Anzahl der in Felder aufgeteilten Indizes sich von Schleifensatz zu Schleifensatz verändert, so schlägt diese Zuordnung fehl.
Beispielsweise:
Der kommende Indexsatz ist "i" für das folgende Beispiel.
In dem folgenden Beispiel ist es notwendig, den Code zu verändern, so daß ein gemeinsamer Indexsatz identifiziert werden kann. Hier ist das Original:
Hier ist der veränderte Code. Die am ehesten optimale Version, um einen gemeinsamen Indexsatz von (n, m) ist:

5.2 Affinitätsbereiche und Unterprogrammaufrufe

Das Standarderfordernis besteht darin, daß alle Feldfamilien innerhalb einer Affinitätsbereichserklärung auf demselben lexikalischen Niveau wie die Affinitätsbereichserklärung sein müssen. Alle Feldfamilien innerhalb der Affinitätserklärung, jedoch in einem anderen Unterprogramm, laufen über eine andere Stranggruppe (daher möglicherweise auch über einen anderen Satz von Prozessoren und ohne dieselbe Affinität). Die Motivation besteht darin, daß Affinitätsbereichserklärungen erfordern, daß das Kompilierungssystem 60 über alle Feldfamilien mit der Erklärung hinwegscannt und Zusammenfassungen der charaktaristischen Eigenschaften der Feldfamilien erzeugt. Das Kompilierungssystem 60 kann nicht auf Unterprogramme zugreifen und die Unterprogramme können nicht in die Information über den Aflinitätsbereich aufgenommen werden.
Der Benutzer kann jedoch den Parameter "intercall" der Affinitätsbereichsanweisung verwenden, um sich über dieses Erfordernis hinwegzusetzen. Das Kompilierungssystem 60 ist nicht in der Lage, über die Feldfamilien hinwegzuscannen, die nicht auf demselben lexikalischen Niveau sind, und wenn der Benutzer keine detaillierte Information über andere Parameter liefert, kann der Affinitätsbereich nicht optimal eingestellt werden.
Ein Beispiel des Standardverhaltens:

6. Architektur der Laufzeitbibliothek 66

6.1 Verwendung der Synchronisierung

Die Laufzeitbibliothek 66 erfordert eine Synchronisierung ihrer Strangmitglieder an verschiedenen Punkten während der Ausführung eines Presto-Programms. Die Synchronisierungsmechanismen, die verwendet werden, sind kritische Abschnitte und Barrieren bzw. Grenzstellen. Die Laufzeitbibliothek 66 verwendet die p-Strang-Mutex-Rufe, um kritische Abschnitte zu implementieren und die p-Strang-Barrierenrufe, um Barrieren zu implementieren.

6.1.1 Anfang und Ende eines parallelen Konstruktionselementes (Barriere)

Zu Beginn einer Feldfamilie oder eines parallelen Abschnittes werden alle Stränge, die an dem parallelen Konstruktionselement teilhaben, in einer Barriere bzw. Umgrenzung gehalten, bis der Master der Stranggruppe alle serielle Codierung abgearbeitet bzw. beendet. Am Ende der Ausführung dieses Konstruktionselementes treten alle Strangmitglieder wieder ein. Der Hauptstrang führt im Anschluß an das parallele Konstruktionselement bzw. den parallelen Abschnitt keinerlei Code aus, bis nicht alle Strangmitglieder wieder in die Barriere eingetreten sind.
Es können zahlreiche Barrieren bzw. Grenzen oder Einschränkungen bestimmt werden, wenn das Programm eine Verschachtelung paralleler Konstruktionselemente hat. Ein Strang kann Mitglied mehrerer Barrierengruppen sein, wenn er an mehreren verschachtelten Konstruktionselementen teilhat.

6.1.2 Verriegeln während der Grab-Strategie (kritischer Abschnitt)

Die Grab-Strategie erfordert, daß alle Strangmitglieder eine kennzeichnende Datenstruktur auf den neuesten Stand bringen, um das nächste verfügbare Feld zu erhalten. Diese kennzeichnende Datenstruktur wird in einem verriegelten Zustand gehalten.

6.1.3 Verriegeln der Stranggruppen-ID (kritischer Abschnitt)

Jede neue Stranggruppe erhält eine eindeutige ID (Identitätskennung), die verwendet wird, um parallele Konstruktionselemente für eine Sichtbarmachung, eine Datenerfassung und eine Kennzeichnungsausgabe zu identifizieren. Die aktuelle Gruppen-ID wird in einem Datenverriegelungszustand gehalten und für jede neue Stranggruppe um einen Schritt heraufgesetzt.

6.1.4 Verriegeln während der Stranggruppenerzeugung und Auflösung (kritischer Abschnitt)

Die Laufzeitbibliothek 66 erzeugt p-Stränge und hält sie bereit in einem Leerlaufvorrat. Wenn eine Stranggruppe erzeugt und aufgelöst wird, müssen Stränge dem Leerlaufvorrat zugeordnet oder aus diesem herausgenommen werden. Dies wird synchronisiert durch Halten der Anzahl der verfügbaren Leerlaufstränge in einem Datenverriegelungszustand.

6.1.5 Verriegeln während der Erzeugung/Zerstörung von Teams (kritischer Abschnitt)

Die Laufzeitbibliothek 66 ermöglicht es dem Benutzer, dauerhafte Teams zu erzeugen, die über ein einzelnes paralleles Konstruktionselement hinaus überleben. Diese Teams werden in einer global verknüpften Liste gehalten. Die Erzeugung und Zerstörung von Teams wird synchronisiert durch lock_pr)_team_lock.

6.1.6 Verriegeln zum Speichern von statistischen Informationen (kritischer Abschnitt)

Die Laufzeitbibliothek 66 kann so ausgestaltet sein, daß sie statistische Information über Leistungsfähigkeit sammelt. Diese Daten werden in globalen Variablen gehalten, die in einem kritischen Abschnitt geschrieben sein müssen.

6.2 Verwendung von Strängen

6.2.1 Strangteams

Ein Presto-Programm beginnt mit einem p-Strang, der auch als Programm-Master bekannt ist. Zu Beginn erzeugt die Laufzeitbibliothek 66 zusätzliche p-Stränge und hält sie in einem Leerlaufvorrat verfügbarer Stränge bereit. Wenn das Programm ausgeführt wird, erzeugt die Laufzeitbibliothek 66 p-Strang-Teams, um auftretende, neue parallele Konstruktionselemente zu handhaben. Stranggruppen können entweder eines oder mehrere parallele Konstruktionselemente handhaben. Wenn Teams aufgelöst werden, werden die Mitglieder des p-Stranges zu dem Leerlaufvorrat der Laufzeitbibliothek 66 zurückgegeben. Dieser Leerlaufvorrat ist dafür ausgelegt, den hohen Aufwand der p-Strang-Erzeugung minimal zu machen.
Parallele Abschnitte und Bereiche: Standardmäßig wird ein neues Strangteam für jeden neuen Abschnitt erzeugt. Am Ende des Abschnittes wird das Strangteam aufgelöst. Wenn der Benutzer in diesem Konstruktionselement ein Team für die Benutzung spezifiziert, so wird dieses Team benutzt und wird am Ende des Konstruktionselementes nicht aufgelöst.
Feldfamilien ohne Affinitätsbereich: Für jede neue Feldfamilie, die nicht in einem Affinitätsbereich enthalten ist, wird ein neues Strangteam erzeugt, es sei denn, ein Team ist in der Anweisung spezifiziert. Am Ende der Feldfamilie wird die neue Stranggruppe aufgelöst.
Wenn ein Team in der Anweisung spezifiziert ist, so wird dieses Team verwendet und es wird kein neues Team erzeugt. Ein vom Benutzer spezifiziertes Team wird am Ende des Konstruktionselementes nicht aufgelöst.
Feldfamilien innerhalb von Affinitätsbereichen: Standardmäßig wird zur Ausführung aller Feldfamilien innerhalb eines Affinitätsbereiches eine neue Stranggruppe erzeugt. Wenn ein Team in der Affinitätsbereichsanweisung spezifiziert wird, so wird dieses Team verwendet und es wird kein neues Team erzeugt. Das Strangteam wird über die Feldfamilien hinweg aufrechterhalten, um eine gleichbleibende Feld → Strangzuordnung über den Affinitätsbereich aufrechtzuerhalten. Die Motivation hierfür liegt in der Annahme, daß Stränge die Tendenz haben, während der Lebensdauer des Stranges an demselben Prozessor zu bleiben. Am Ende jedes Affinitätsbereiches wird die neue Stranggruppe aufgelöst, es sei denn, es handelt sich um ein vom Benutzer erzeugtes und spezifiziertes Team.
Ein einzelner Strang kann Mitglied mehrerer Strangteams sein, wenn parallele Konstruktionselemente verschachtelt sind.

6.2.2 Erzeugen und Zerstören von Strängen

Eine Stranggruppe besteht aus einem Gruppenmaster und 0 bis n Gruppensklaven. Ein Presto-Programm beginnt mit einem Strang, dem Programm-Master. Wenn Stranggruppen erzeugt werden, wird der jeweils aktuelle Master der Gruppenmaster der neuen Stranggruppe und die Sklaven werden erzeugt. Wenn Stranggruppen aufgelöst werden, werden die Gruppensklaven in den Leerlaufvorrat zurückgegeben.
Dieser Vorgang erstreckt sich auf verschachtelte parallele Konstruktionselemente. Man stelle sich ein Programm mit einer Reihe von parallelen Konstruktionselementen vor, die in einer Tiefe von zwei Ebenen verschachtelt sind. Auf dem Niveau 1 erzeugt der Programm-Master eine Stranggruppe und wird zum Gruppenmaster. Auf dem Niveau 2 erzeugt jeder Sklave, der auf ein weiteres paralleles Konstruktionselement trifft, eine neue Stranggruppe und wird der Gruppenmaster auf dem Niveau 2. Wenn das Konstruktionselement auf dem Niveau 2 endet, wird die Stranggruppe auf dem Niveau 2 aufgelöst und die Gruppensklaven werden zurückgegeben. Der Gruppenmaster des Niveaus 2 gibt seine Masteridentität auf und nimmt seine eigene Identität als Sklave auf dem Niveau 1 oder auch als Master wieder an. Wenn die Stranggruppe auf dem Niveau 1 aufgelöst wird, werden alle Gruppensklaven zurückgegeben mit Ausnahme des Gruppen- (und Programm-) Masters.

6.3 Datenstrukturen

6.3.1 Global zu Programm

Umgebungsvariable: Alle Umgebungsvariablen der Benutzerschnittstelle sind gemeinsam verwendete Globale für das Programm und sind auf al e parallelen Konstruktionselemente anwendbar.
Statistikinformation: Diese Maßanweisungszahlen in verschiedenen Kategorien werden in gemeinsam verwendeten globalen Variablen gespeichert.
_pr_master_thread: ID des Programm-Masters zur udb-Unterstützung. Gemeinsam verwendete globale Variable.
_pr_fp: Dateizeiger, der für die Ausgabe am Ende des Programms verwendet wird. Wird benötigt wegen der Behandlung der Standardausgabe in einer Fortran-Umgebung. Gemeinsam verwendete Globale.
_pr_t_state: Laufender, Leerlauf- oder Synchronisierungszustand für udb-Unterstützung. Private global.
_pr_kurr_mcb_p: Zeiger auf aktuellen mcb, für udb-Unterstützung. Private global.
_TEAM_MEM_ID: Die ID dieses Stranges in seinem aktuellen Team. Private global.
_POOL_ID: Die ID dieses aktuellen Stranges für den Leerlaufstrangvorrat der Laufzeitbibliothek 66. Private global.
_MY_THREAD_ID: Die ID des p-Stranges dieses Stranges. Private global.

Zusammenfassung

Im Vorstehenden wurde ein verbessertes digitales Datenverarbeitungssystem beschrieben, welches die zuvor erwähnten Aufgaben erfüllt. Insbesondere wurde ein verbesserter paralleler Prozessor beschrieben, der iterative Folgen ausführt, indem er sie in Teilaufgaben aufteilt und diese den Prozessoren zuweist. Diese Aufteilung und Zuordnung wird in einer Art und Weise ausgeführt, daß Datenkonkurrenz zwischen den Prozessoren minimal gemacht wird und Lokalität von Daten an den Prozessoren, die auf diese Daten zugreifen, maximal gemacht wird. Fachleute auf diesem Gebiet verstehen, daß die oben beschriebenen Ausführungsformen nur beispielhaft sind und daß andere Vorrichtungen und Verfahren, einschließlich von Modifikationen, Hinzufügungen und Weglassungen in den Rahmen der Erfindung fallen.
Beispielhaft erkennt man, daß die Funktionalität des Vorprozessors 60a in den Compiler 60b selbst einbezogen werden kann. Dadurch wird das Erfordernis eines separaten Vorverarbeitungsschrittes beseitigt.
Man versteht weiterhin, daß die oben beschriebenen Techniken auf massiv parallele Systeme und andere Multiprozessorsysteme angewendet werden können. Mit Blick auf ein weiteres Beispiel versteht es sich, daß unterschiedliche Datenstrukturen, welche Feldaufteilungsinformation speichern, verwendet werden können. Äquivalente, jedoch abgewandelte Verfahrensweisen können verwendet werden, um die iterativen Sequenzen zu parallelisieren und auszuführen. Beispielsweise können auch weitere Feldaufteilungsanweisungen hinzugefügt werden.

Claims

1. Digitale Datenverarbeitungsvorrichtung mit Parallelprozessoren mit:

einer Mehrzahl von Verarbeitungseinheiten bzw. Prozessoren, jeweils für das Ausführen von Befehlen bzw. Anweisungen,

Speichereinrichtungen, die mit den Verarbeitungseinrichtungen verbunden sind, um zumindest Daten oder Befehle zu speichern, und

einer Kommunikationseinrichtung zwischen den Prozessoren, die mit den Verarbeitungseinheiten verbunden ist, um Information zwischen diesen zu übertragen,

und wobei für das Verarbeiten einer iterativen Folge von Anweisungen

die Speichereinrichtung Einrichtungen für das Speichern einer parallelen Folge von Anweisungen aufweist, welche die iterative Sequenz bzw. Folge repräsentiert, und jede Verarbeitungseinheit Einrichtungen aufweist, um ihre Verfügbarkeit anzuzeigen, die nebengeordnete bzw. parallele Sequenz über einen Abschnitt des iterativen Raumes hinweg auszuführen, der zu der iterativen Sequenz gehört, wobei der Abschnitt als ein Feld bezeichnet wird,

die Vorrichtung eine Einrichtung für ein nächstes Feld aufweist, welche mit den Verarbeitungseinheiten verbunden ist, um auf jede zumindest ausgewählte dieser Anzeigen durch diese Verarbeitungseinheiten zu reagieren, um ein Signal zu erzeugen, welches die Grenzen eines Feldes angibt, auf welchem die in Felder eingeteilte Sequenz ausgeführt werden soll, wobei jedes derartige Feld kein weiteres Feld überlappt und wobei alle diese Felder gemeinsam den Iterationsraum abdecken,

wobei die Einrichtung für das nächste Feld Einrichtungen für das Erzeugen von Grenzen entsprechenden Signalen aufweist, die Grenzen entsprechen, um den Platz für Daten maximal zu machen, die einem Zugriff während der Ausführung eines oder mehrerer entsprechender Felder ausgesetzt sind, und um die Zugriffskonkurrenz für solche Daten während der Ausführung minimal zu machen, und wobei

jede derartige Verarbeitungseinheit eine Einrichtung aufweist, um auf ein den Grenzen entsprechendes Signal zu reagieren, welches in Reaktion auf die Anzeige durch diese Prozessoreinheit erzeugt wurde, daß die in Felder aufgeteilte Abfolge über das entsprechende Feld ausgeführt wird.

2. Vorrichtung nach Anspruch 1, mit:

einer Feldaufbaueinrichtung, um ein Feldformsignal zu erzeugen, welches ein oder mehrere Maße der den Grenzen entsprechende Signale anzeigt in Anbetracht der Abhängigkeit zwischen den entsprechenden Feldern,

wobei die Speichereinrichtung in der Weise betreibbar ist, daß sie die in Felder aufgeteilte Frequenz speichert, die eine oder mehrere Anweisungen für einen Schreibezugriff auf in der Speichereinrichtung gespeicherte Daten aufweist,

wobei die Speichereinrichtung umfaßt

i) eine Mehrzahl von Speicherelementen, jeweils für das Speichern zumindest von Daten oder von Befehlen, wobei das Speicherelement mit einer zugehörigen der Prozessoreinheiten verbunden ist, und

ii) eine Speicherverwaltungseinrichtung, die mit den Speicherelementen verbunden ist, um wahlweise Informationen zwischen diesen zu übertragen, und wobei

die Einrichtung für das nächste Feld Einrichtungen umfaßt für das Erzeugen der den Grenzen entsprechenden Signale als Funktion des Feldformsignals.

3. Vorrichtung nach Anspruch 2, wobei die Feldaufbaueinrichtung eine Einrichtung zum Erzeugen eines Feldformsignales aufweist, welches Maße der den Grenzen entsprechenden Signale anzeigt, welche die Anzahl der individuellen Daten minimal machen, die Gegenstand des Schreibzugriffs während der Ausführung verschiedener der entsprechenden Felder sind.

4. Vorrichtung nach Anspruch 2, wobei die Feldaufbaueinrichtung eine Einrichtung für das Erzeugen eines Feldformsignales umfaßt, welches die Maße der die Grenzen repräsentierenden Signale anzeigt, welche die Anzahl der individuellen Daten minimal machen, die Gegenstand eines Zugriffs vom Schreibtyp durch mehrere gleichzeitig arbeitende der Prozessoreinheiten sind.

5. Vorrichtung nach Anspruch 2, wobei die Speichereinrichtung in der Weise betreibbar ist, daß sie erste und zweite Felder speichert, die eines der folgenden umfassen:

i) eine Anweisung in dem ersten Feld, welche einen Schreibzugriff auf ausgewählte Daten hat, sowie eine Anweisung in dem zweiten Feld, die anschließend einen Lesezugriff auf dieselben Daten hat,

ii) eine Anweisung in dem ersten Feld mit einem Lesezugriff auf ausgewählte Daten und eine Anweisung in dem zweiten Feld, die anschließend einen Schreibzugriff auf dieselben Daten hat, und

iii) eine Anweisung in dem ersten Feld, die einen Schreibzugriff auf ausgewählte Daten hat und eine Anweisung in dem zweiten Feld, die anschließend einen Schreibzugriff auf dieselben Daten hat, und wobei

die Feldaufbaueinrichtung Einrichtungen umfaßt für das Erzeugen eines Feldformsignales, welches die Maße bzw. Abmessungen der grenzrepräsentativen Signale anzeigt, die die Abhängigkeit der Ausführung des zweiten Feldes beim Ausführen des ersten Feldes bezüglich der jeweiligen Zugriffe auf die ausgewählten Daten minimal macht.

6. Vorrichtung nach Anspruch 2, wobei die Feldaufbaueinrichtung Einrichtungen umfaßt für das Erzeugen eines Affinitätssignals, welches eine Feldausführfolge wiedergibt, die eine Übertragung von Daten minimal macht, welche während der Ausführung aufeinanderfolgender Felder durch unterschiedliche Verarbeitungseinheiten irgendeinem Lese- oder Schreibzugriff ausgesetzt sind.

7. Vorrichtung nach Anspruch 2, wobei die Feldaufbaueinrichtung eine Feldformeinrichtung aufweist, um das Feldformsignal zu erzeugen als eine Funktion zumindest von

i) einem Affinitätssignal, welches eine Feldausführabfolge repräsentiert, die eine Übertragung von Daten minimal macht, die irgendeinem Zugriff vom Lese- oder Schreibtyp durch aufeinanderfolgende Anweisungen der Felder von verschiedenen der Verarbeitungseinheiten ausgesetzt sind,

ii) einer Abhängigkeitsrichtung der n Felder aufgeteilten Abfolge,

iii) dem Verarbeitungsaufwand, der mit der Ausführung der in Felder aufgeteilten Sequenz verknüpft ist,

iv) der Größe bzw. einem Maß des Iterationsraumes,

v) einer Anzahl von Verarbeitungseinheiten, die für die Ausführung der in Felder aufgeteilten Sequenz erforderlich sind, und

vi) einem Affinitätsbereichssignal, welches anzeigt, daß die in Felder aufgeteilte Sequenz mit einem Iterationsraum ausgeführt werden soll, der durch eine Mehrzahl solcher Feldsequenzen definiert ist.

8. Vorrichtung nach Anspruch 1, wobei die Einrichtung für das nächste Feld eine Einrichtung aufweist für das Erzeugen aufeinanderfolgender der den Grenzen entsprechenden Signale als Funktion von zumindest:

i) einem Feldformsignal, welches ein oder mehrere Maße der die Grenzen repräsentierenden Signale anzeigt,

ii) einem Feldstrategiesignal, welches zumindest die Reihenfolge oder die Art und Weise der Zuordnung von Feldern zu den Prozessoreinheiten anzeigt, und

iii) einem Affinitätsbereichssignal, welches anzeigt, daß die in Felder aufgeteilte Abfolge innerhalb eines Iterationsraumes ausgeführt werden soll, der durch eine Mehrzahl von Feldfolgen definiert ist,

wobei die Vorrichtung eine Feldstrategieeinrichtung aufweist, um das Feldstrategiesignal zu erzeugen, und

wobei der Iterationsraum durch eine Mehrzahl von Indizes definiert wird.

9. Vorrichtung nach Anspruch 8, wobei die Feldstrategieeinrichtung eine wahlweise betätigbare Scheiben- bzw. Schnitteinrichtung aufweist, um

i) ein Feldformsignal zu erzeugen, welches Grenzen entsprechende Signale anzeigt, die den Iterationsraum durch eine Anzahl von Verarbeitungseinrichtungen teilen, welche der Ausführung bezüglich eines der Indizes zugeordnet sind und den Iterationsraum bezüglich der anderen der Indizes aufspannen, wobei die Anzahl der entsprechenden Felder gleich der Anzahl verfügbarer Verarbeitungseinheiten ist, wobei diese Felder im wesentlichen die gleiche Größe haben, und

ii) ein Feldstrategiesignal zu erzeugen, welches die Erzeugung der entsprechenden Felder anzeigt, um dadurch zu bewirken, daß jedes dieser Felder von einer entsprechenden der verfügbaren Verarbeitungseinheiten ausgeführt wird.

10. Vorrichtung nach Anspruch 9, wobei die Feldstrategieeinrichtung eine Einrichtung für das Betätigen der Scheiben- bzw. Schnitteinrichtung für die Fälle umfaßt, bei denen

i) Daten, die während der Ausführung irgendeines solchen Feldes einem Zugriff ausgesetzt sind, nicht von denjenigen abhängen, welche während der Ausführung irgendeines anderen derartigen Feldes modifiziert wurden, und

ii) keine wesentliche Menge von Daten, die Gegenstand irgendeines Zugriffs vom Lese- und Schreibtyp durch ein solches Feld sind, auch Gegenstand eines Zugriffs vom Lese- oder Schreibtyp eines weiteren solchen Feldes sind.

11. Vorrichtung nach Anspruch 9 mit Einrichtungen zum Betätigen der Scheibeneinrichtung in Reaktion auf ein vom Benutzer zugeführtes Signal.

12. Vorrichtung nach Anspruch 8, wobei die Feldstrategieeinrichtung eine wahlweise betätigbare Modulo-Einrichtung aufweist, um

i) Grenzen entsprechende Signale zu erzeugen, um den Iterationsraum in Abschnitte fester Länge entlang aller Indizes aufzuteilen, und

ii) ein Feldstrategiesignal zu erzeugen, welches eine Anzeige für die Zuordnung der jeweiligen Felder auf der Basis Modulo einer zahlenmäßigen Kennzeichnung ist, die jeder der verfügbaren Verarbeitungseinheiten zugeordnet ist, sowie einer zahlenmäßigen Kennzeichnung, die jedem der Felder zugeordnet ist.

13. Vorrichtung nach Anspruch 12, wobei die Feldstrategieeinrichtung Einrichtungen zum Betätigen der Modulo-Einrichtung in Fällen aufweist, bei denen

i) Daten, die während der Ausführung irgendeines solchen Feldes Gegenstand eines Zugriffs sind, nicht von denjenigen abhängen, die während der Ausführung irgendeines anderen solchen Feldes modifiziert werden,

ii) keine wesentliche Menge von Daten, die irgendeinem Lese- oder Schreibzugriff durch ein solches Feld ausgesetzt sind, auch einem Lese- oder Schreibzugriff durch irgendein weiteres solches Feld ausgesetzt sind, und

iii) die erneute Verwendung von Daten, die irgendeinem Zugriff vom Lese- oder Schreibtyp ausgesetzt sind, durch eine Verarbeitungseinheit, welche eine Vielzahl von Feldern ausführt, maximal gemacht wird, selbst bei Vorliegen einer Größenänderung des Iterationsraumes.

14. Vorrichtung nach Anspruch 12 mit Einrichtungen zum Betätigen der Modulo-Einrichtung in Reaktion auf ein vom Benutzer zugeführtes Signal.

15. Vorrichtung nach Anspruch 8, wobei die Feldstrategieeinrichtung eine wahlweise betätigbare Wellenfronteinrichtung aufweist für

i) das Erzeugen von Grenzen entsprechenden Signalen, die den Iterationsraum entlang eines oder mehrerer der Indizes aufteilen, wobei Daten, die während der Ausführung zumindest ausgewählter Felder Gegenstand eines Zugriffs sind, von denjenigen abhängen, die während der Ausführung eines anderen Feldes modifiziert werden, und wobei diese Felder eine Abhängigkeitsrichtung haben,

ii) ein Feldstrategiesignal zu erzeugen, welches eine Folge der Erzeugung der entsprechenden Felder gemäß der Abhängigkeitsrichtung anzeigt.

16. Vorrichtung nach Anspruch 15, wobei die Feldsträtegieeinrichtung eine Einrichtung aufweist, um die Wellenfronteinrichtung zu betätigen, wobei Daten, die während der Ausführung von zumindest einem solchen Feld Gegenstand eines Zugriffs sind, von denjenigen abhängen, die während der Ausführung eines anderen solchen Feldes modifiziert werden.

17. Vorrichtung nach Anspruch 15, mit Einrichtungen zum Betätigen der Wellenfronteinrichtung in Reaktion auf ein vom Benutzer zugeführtes Signal.

18. Vorrichtung nach Anspruch 8, wobei die Feldstrategieeinrichtung eine wahlweise betätigbare Modulo/Wellenfronteinrichtung aufweist für

i) das Erzeugen von Grenzen entsprechenden Signalen, um den Iterationsraum entlang aller Indizes in Abschnitte fester Länge aufzuteilen, wobei Daten, die während der Ausführung zumindest eines ausgewählten Feldes Gegenstand eines Zugriffs sind, von denjenigen abhängen, die während der Ausführung einer oder mehrerer anderer Felder modifiziert werden, und wobei die Felder eine Abhängigkeitsrichtung haben, und für

ii) das Erzeugen eines Feldstrategiesignales, welches die Zuordnung der entsprechenden Felder auf der Basis Modulo einer numerischen Kennzeichnung anzeigt, die zu jeder der verfügbaren Prozessoreinheiten gehört, sowie eine numerischen Kennzeichnung, die zu jedem der Felder gehört, und auf Basis der Abhängigkeitsrichtung.

19. Vorrichtung nach Anspruch 18, wobei die Feldstrategieeinrichtung eine Einrichtung umfaßt für das Betätigen der Modulo/Wellenfronteinrichtung in Fallen, bei denen

i) Daten, die während der Ausführung zumindest einen solchen Feldes Gegenstand eines Zugriffs sind, von denjenigen abhängen, die während der Ausführung eines oder mehrerer anderer derartiger Felder modifiziert werden, und

ii) die erneute Verwendung von Daten, die Gegenstand irgendeines Lese- oder Schreibzugriffs durch eine Verarbeitungseinheit sind, welche eine Mehrzahl von Feldern ausführt, maximal gemacht wird, selbst bei Vorliegen einer Größenänderung des iterativen Raumes.

20. Vorrichtung nach Anspruch 18 mit einer Einrichtung zum Betätigen der Modulo/Wellenfronteinrichtung in Reaktion auf ein von dem Benutzer zugeführtes Signal.

21. Vorrichtung nach Anspruch 8, wobei die Feldstrategieeinrichtung eine wahlweise betätigbare Greifeinrichtung aufweist, um

i) Grenzen entsprechende Signale zu erzeugen, um den Iterationsraum entlang aller der Indizes in Abschnitte fester Länge aufzuteilen, und wobei Daten, die während der Ausführung irgendeines Feldes einem Zugriff ausgesetzt sind, nicht von denjenigen abhängig sind, die während der Ausführung eines anderen Feldes modifiziert werden, und

ii) ein Feldstrategiesignal zu erzeugen, welches eine Folge in der Erzeugung entsprechender Felder anzeigt, in Reaktion auf die Signalgebung für die Verfügbarkeit durch die Verarbeitungseinheiten auf der Basis first-come-first-serve.

22. Vorrichtung nach Anspruch 21, wobei die Feldstrategieeinrichtung eine Einrichtung zum Betätigen der Greifeinrichtung aufweist,

i) um einen Lastausgleich zwischen den Verarbeitungseinheiten, welche die Felder ausführen, zu ermöglichen, und in Fällen, wenn

ii) keine beträchtliche Menge an Daten irgendeinem Zugriff vom Lese- oder Schreibtyp durch ein solches Feld ausgesetzt ist, auch irgendeinem Zugriff vom Lese- und Schreibtyp durch ein weiteres Feld ausgesetzt ist.

23. Vorrichtung nach Anspruch 21, welche eine auf den Benutzer reagierende Einrichtung zum Betätigen der Wellenfronteinrichtung aufweist.

24. Vorrichtung nach Anspruch 1 mit

A. einer Einrichtung zum Bereitstellen eines Affinitäts-Bereichssignals, welches einer oder mehrerer Iterationsfolgen entspricht, die auf dieselben Daten zugreifen,

B. einer Affinitätsbereichs-Aufbaueinrichturg, um eines oder mehrere der folgenden zu erzeugen:

i) ein Signal, welches einem Iterationsraum entspricht, in welchem eine oder mehrere in Felder angeordnete Folgen in dem Affinitätsbereich ausgeführt werden sollen,

ii) ein Feldformsignal, welches einem oder mehreren Maßen eines den Grenzen entsprechenden Signals entspricht,

iii) ein Feldstrategiesignal, welches zumindest eine Folge oder eine Art und Weise der Zuordnung von Feldern zu den Prozessoreinheiten anzeigt, und

iv) ein Teamsignal, welches einem Satz von Verarbeitungseinheiten entspricht, durch welche die in Felder angeordneten Folgen innerhalb des Affinitätsbereiches ausgeführt werden sollen, um eine Übertragung von Daten, die während einer solchen Ausführung irgendeinem Zugriff vom Lesetyp oder vom Schreibtyp ausgesetzt sind, minimal zu machen.

25. Vorrichtung nach Anspruch 24, wobei die Affinitätsbereichs-Aufbaueinrichtung eine Einrichtung für das Festlegen des Iterationsraums aufweist, um einen oder mehrere der Iterationsplätze in den Feldfolgen des Affinitätsbereiches zu umfassen.

26. Compiler von dem Typ, welcher Programmsignale, die einem Programm entsprechen, mit einer iterativen Folge im Quellcodeformat in eine Codesequenz von Anweisungen in einem Objektcodeformat übersetzt, welches für das Laden zwecks Ausführung durch eine Vielzahl paralleler digitaler Datenverarbeitungseinheiten geeignet ist, wobei der Compiler eine Abhängigkeitseinrichtung aufweist, um eine Abhängigkeitsrichtung der iterativen Folge zu bestimmen, und um ein Signal zu erzeugen, welches dieser entspricht, und mit einer Feldeinrichtung, um auf die iterative Folge im Quellcodeformat zu reagieren, indem eine in Felder aufgeteilte Folge von Anweisungen im Objektcodeformat erzeugt wird, die jener entsprechen, und um weiterhin auf diese iterative Folge zu reagieren und um eines oder mehrere vom Benutzer angegebene Signale auf Null zu setzen, um ein oder mehrere Signale zu erzeugen, um Grenzen für eines oder mehrere Felder zu erzeugen, auf welchen die in Felder aufgeteilte Folge auszuführen ist.

27. Compiler nach Anspruch 26, mit einer Parallelisierungseinrichtung, um auf Anweisungen in der iterativen Abfolge und auf das Signal, welches der Abhängigkeitsrichtung entspricht, zu reagieren, um Signale zu erzeugen, die einem oder mehreren Indizes in dem Iterationsraum entsprechen, über welchen die in Felder aufgeteilte Abfolge auszuführen ist.

28. Compiler nach Anspruch 27, mit

einer Eingabeeinrichtung für das Annehmen von Signalen, die einer vom Benutzer spezifizierten Indizierung des Iterationsraumes entsprechen, und

Einrichtungen, die mit der Eingabeeinrichtung und der Parallelisierungseinrichtung verbunden sind, Einrichtungen zum Vergleichen der durch den Benutzer spezifizierten Indizierungssignale mit denjenigen umfassen, die durch die Parallelisierungseinrichtung erzeugt wurden, und um für den Fall zumindest einer ausgewählten Nichtübereinstimmung derselben ein Anzeigesignal zu erzeugen.

29. Compiler nach Anspruch 27, mit einer Optimierungseinrichtung, die mit der Parallelisierungseinrichtung verbunden ist, um bei der Optimierung der parallelen Ausführung der in Felder aufgeteilten Sequenz ein oder mehrere Signale für die Verwendung während der Laufzeit zu erzeugen.

30. Compiler nach Anspruch 29, wobei die Optimierungseinrichtung eine Einrichtung zum Erzeugen eines Affinitätssignals aufweist, welches einer Feldausführungsfolge entspricht, die eine Übertragung von Daten, die während der Ausführung derselben in mehreren Feldern irgendeinem Zugriff vom Lese- oder Schreibtyp ausgesetzt sind, minimal macht.

31. Compiler nach Anspruch 29, wobei die Optimierungseinrichtung eine Einrichtung zum Erzeugen eines Affinitätsbereichssignals aufweist, welches einer oder mehreren Iterationsfolgen entspricht, welche auf dieselben Daten zugreifen.

32. Compiler nach Anspruch 31, mit

einer Eingabeeinrichtung, um Signale anzunehmen, die einem durch den Benutzer spezifizierten Affinitätsbereichssignal entsprechen, und

Einrichtungen, die mit der Eingabeeinrichtung verbunden sind, wobei die Optimierungseinrichtung Einrichtungen aufweist für das Vergleichen des durch den Benutzer spezifizierten Affinitätsbereichssignals mit demjenigen, welches durch die Optimierungseinrichtung erzeugt wurde, und um ein Anzeigesignal für den Fall zu erzeugen, daß zumindest eine ausgewählte Nichtübereinstimmung auftritt.

33. Compiler nach Anspruch 29, wobei die Optimierungseinrichtung eine Einrichtung für das Erzeugen eines Signals aufweist, welches einer Abschätzung des Verarbeitungsaufwands entspricht, die mit der Ausführung der in Felder aufgeteilten Sequenz verknüpft ist.

34. Compiler nach Anspruch 26, mit einer Ruferzeugungseinrichtung, um die iterative Folge in dem Quellcodeformat durch eine Anweisung zu ersetzen, die einem Aufruf eines den Code abfertigenden Unterprogramms entspricht.

35. Compiler nach Anspruch 34 mit einer Laufzeiteinrichtung, um die dem Aufruf entsprechende Anweisung auszuführen, um die Ausführung der in Felder aufgeteilten Sequenz durch die Verarbeitungseinrichtung auszulösen.

36. Verfahren zum Betreiben einer digitalen Datenverarbeitungseinrichtung mit Parallelprozessoren von dem Typ, der

eine Mehrzahl von Verarbeitungseinheiten hat, jeweils für die Ausführung von Anweisungen,

Speichereinrichtungen hat, die mit den Verarbeitungseinrichtungen verbunden sind, um zumindest Daten oder Befehle zu speichern, und

eine Kommunikationseinrichtung zwischen den Prozessoren hat, die mit den Verarbeitungseinheiten verbunden ist, um Daten zwischen diesen zu übertragen, wobei das Verfahren aufweist

Speichern einer in Felder aufgeteilten Abfolge von Anweisungen, die einer iterativen Abfolge entsprechen,

Anzeigen der Verfügbarkeit jedes Prozessors, um die in Felder aufgeteilte Folge über einen Bereich eines Iterationsraumes auszuführen, der der iterativen Sequenz zugeordnet ist, wobei der Bereich als ein Feld bezeichnet wird,

Reagieren zumindest auf ausgewählte derartige Anzeigen durch diese Prozessoreinheiten, um ein Signal zu erzeugen, welches den Grenzen eines Feldes entspricht, auf welchem die in Felder aufgeteilte Sequenz auszuführen ist, wobei jedes derartige Feld nicht mit irgendeinem anderen Feld überlappt und wobei alle diese Felder gemeinsam den Iterationsraum abdecken,

Erzeugen von Grenzen entsprechenden Signalen, die den Grenzen entsprechen, um den Ort bzw. die Verteilung von Daten maximal zu machen, die während der Ausführung eines oder mehrerer entsprechender Felder Gegenstand eines Zuriffs sind, um die Konkurrenz für den Zugriff auf solche Daten während der Ausführung minimal zu machen, und

Reagieren jedes der Prozessoren auf ein den Grenzen entsprechendes Signal, welches in Reaktion auf die Anzeige durch diese Prozessoreinheit erzeugt wurde, um die in Felder aufgeteilte Sequenz auf dem entsprechenden Feld auszuführen.

37. Verfahren nach Anspruch 36, welches aufweist

Erzeugen eines Feldformsignales, welches in Anbetracht der Abhängigkeit zwischen den entsprechenden Feldern eines oder mehrere Maße der den Grenzen entsprechenden Signale anzeigt,

Wobei die in Felder aufgeteilte Sequenz eine oder mehrere Anweisungen für einen Zugriff vom Schreibtyp auf Daten umfaßt, die in den Speichereinrichtungen gespeichert sind,

Bereitstellen einer Mehrzahl von Speicherelementen, jeweils für das Speichern zumindest von Daten oder Befehlen bzw. Anweisungen, wobei jedes dieser Speicherelemente mit einer zugehörigen der Prozessoreinheiten verbunden ist, und wahlweise Übertragen von Information zwischen den Speicherelementen, und

Erzeugen der den Grenzen entsprechenden Signale als Funktion eines Feldformsignals.

38. Verfahren nach Anspruch 37, welches das Erzeugen des Feldformsignals aufweist, das Maße der den Grenzen entsprechenden Signale anzeigt, welche die Anzahl individueller Daten minimal machen, welche während der Ausführung verschiedener der entsprechenden Felder einem Schreibzugriff ausgesetzt sind.

39. Verfahren nach Anspruch 37, welches das Erzeugen eines Feldformsignales aufweist, das Maße der den Grenzen entsprechenden Signale anzeigt, die die Anzahl individueller Daten minimal machen, welche während mehrerer gleichzeitig arbeitender Prozessoreinheiten einem Zugriff vom Schreibtyp ausgesetzt sind.

40. Verfahren nach Anspruch 37, wobei erste und zweite Felder irgendeines der folgenden aufweisen:

i) eine Anweisung in dem ersten Feld, die auf ausgewählte Daten nach einem Zugriff vom Schreibtyp zugreift, und eine Anweisung in dem zweiten Feld, die anschließend auf dieselben Daten in einem Zugriff vom Lesetyp zugreift,

ii) eine Anweisung in dem ersten Feld, die auf ausgewählte Daten in einem Zugriff vom Lesetyp zugreift und eine Anweisung in dem zweiten Feld, welche anschließend auf dieselben Daten in einem Zugriff vom Schreibtyp zugreift, und

iii) eine Anweisung in dem ersten Feld, welche auf ausgewählte Daten in einem Zugriff vom Schreibtyp zugreift und eine Anweisung in dem zweiten Feld, welche anschließend auf dieselben Daten in einem Zugriff vom Schreibtyp zugreift, wobei das Verfahren

das Erzeugen eines Feldformsignales aufweist, welches die Maße der den Grenzen entsprechenden Signale anzeigt, welche die Abhängigkeit der Ausführung des zweiten Feldes von der Ausführung des ersten Feldes bezüglich ihrer entsprechenden Zugriffe auf die ausgewählten Daten minimal machen.

41. Verfahren nach Anspruch 37, welches das Erzeugen eines Affinitätssignals aufweist, das einer Feldausführungsabfolge entspricht, welche eine Übertragung von Daten minimal macht, die irgendeinem Zugriff vom Lesetyp oder Schreibtyp während der Ausführung aufeinanderfolgender Felder durch unterschiedliche Prozessoreinheiten ausgesetzt sind.

42. Verfahren nach Anspruch 37, welches das Erzeugen des Feldformsignals als Funktion zumindest eines der folgenden aufweist

i) eines Affinitätssignals, welches einer Feldausführungssequenz entspricht, die eine Übertragung von Daten minimal macht, welche irgendeinem Zugriff vom Lese- oder Schreibtyp durch aufeinanderfolgende Ausführungen der Felder durch verschiedene der Prozessoreinheiten ausgesetzt sind,

ii) einer Abhängigkeitsrichtung der in Felder aufgeteilten Sequenz,

iii) des Verarbeitungsaufwandes, der mit der Ausführung der in Felder aufgeteilten Sequenz verknüpft ist,

iv) der Größe des Iterationsraumes,

v) einer Anzahl von Verarbeitungseinrichtungen, die für die Ausführung der in Felder aufgeteilten Sequenz verfügbar sind, und

vi) eines Affinitätsbereichssignals, welches anzeigt, daß die in Felder aufgeteilte Sequenz innerhalb eines Iterationsraumes ausgeführt werden soll, der durch eine Mehrzahl von Feldsequenzen definiert ist.

43. Verfahren nach Anspruch 36, mit

Erzeugen aufeinanderfolgender der den Grenzen entsprechenden Signale als Funktion von zumindest

i) einem Feldformsignal, welches ein oder mehrere Maße des den Grenzen entsprechenden Signals anzeigt,

ii) einem Feldstrategiesignal, welches zumindest eine Sequenz oder eine Art und Weise der Zuordnung der Felder zu den Prozessoreinheiten anzeigt,

iii) einem Affinitätsbereichssignal, welches anzeigt, daß die in Felder aufgeteilte Sequenz innerhalb eines Iterationsraumes ausgeführt werden soll, der durch eine Mehrzahl von Feldsequenzen definiert sind,

Erzeugen des Feldstrategiesignals, und

wobei der Iterationsraum durch eine Mehrzahl von Indizes definiert ist.

44. Verfahren nach Anspruch 43 mit auswählbar betätigbaren Scheiben bzw. Schneideinrichtungen, um

i) ein Feldformsignal zu erzeugen, welches Grenzen entsprechende Signale anzeigt, die den Iterationsraum durch eine Anzahl von Verarbeitungseinheiten aufteilen, welche der Ausführung bezüglich eines der Indizes zugeordnet sind und den Iterationsraum bezüglich der anderen dieser Indizes aufspannen, wobei die Anzahl der entsprechenden Felder gleich der Anzahl der verfügbaren Prozessoreinheiten ist, und wobei diese Felder von im wesentlichen gleicher Größe sind, und

ii) Erzeugen eines Feldstrategiesignales, welches die Erzeugung der entsprechenden Felder anzeigt, um so zu bewirken, daß jedes dieser Felder durch eine entsprechende der verfügbaren Prozessoreinheiten ausgeführt wird.

45. Verfahren nach Anspruch 44, welches das Betätigen der Scheibeneinrichtungen in Fällen aufweist, in denen

i) Daten, die während der Ausführung irgendeines solchen Feldes einem Zugriff ausgesetzt sind, nicht von denjenigen abhängen, die während der Ausführung eines anderen solchen Feldes modifiziert werden, und

ii) keine beträchtliche Menge von Daten, die irgendeinem Zugriff vom Lesetyp oder vom Schreibtyp durch ein solches Feld ausgesetzt sind, auch irgendeinem Zugriff vom Lesetyp oder Schreibtyp durch ein anderes derartiges Feld ausgesetzt sind.

46. Verfahren nach Anspruch 44, welches das Betätigen der Scheibeneinrichtung in Reaktion auf ein vom Benutzer zugeführtes Signal aufweist.

47. Verfahren nach Anspruch 43, wobei die weitere Verbesserung das Bereitstellen einer gezielt betätigbaren Modulo-Einrichtung aufweist, um die Schritte auszuführen

i) Erzeugen von Grenzen entsprechenden Signalen, um den Iterationsraum entlang aller Indizes in Abschnitte fester Länge aufzuteilen, und

ii) Erzeugen eines Feldstrategiesignals, welches die Zuordnung der entsprechenden Felder auf der Basis Modulo einer numerischen Kennzeichnung anzeigt, die jeder der verfügbaren Verarbeitungseinheiten zugeordnet ist, sowie einer numerischen Kennzeichnung, die jedem der Felder zugeordnet ist.

48. Verfahren nach Anspruch 47, welches das Beiätigen der Modulo-Einrichtung in Fällen aufweist, in denen

i) Daten, die während der Ausführung irgendeines solchen Feldes einem Zugriff ausgesetzt sind, nicht von denjenigen abhängig sind, die während der Ausführung irgendeines anderen derartigen Feldes modifiziert werden,

ii) keine beträchtliche Menge von Daten, die einem Zugriff vom Lesetyp oder Schreibtyp durch ein derartiges Feld ausgesetzt sind, auch einem Zugriff vom Lese- oder Schreibtyp durch ein anderes derartiges Feld ausgesetzt sind, und

iii) die erneute Verwendung von Daten, die irgendeinem Zugriff vom Lesetyp oder Schreibtyp durch eine Prozessoreinheit ausgesetzt sind, der eine Mehrzahl von Feldern ausführt, maximal gemacht wird, selbst wenn eine Veränderung der Größe des Iterationsraumes vorliegt.

49. Verfahren nach Anspruch 47, welches das Betätigen der Modulo-Einrichtung in Reaktion auf ein vom Benutzer zugeführtes Signal aufweist.

50. Verfahren nach Anspruch 43, welches das Bereitstellen einer gezielt betätigbaren Wellenfronteinrichtung aufweist, um die Schritte auszuführen

i) Erzeugen von Grenzen entsprechenden Signalen, die den Iterationsraum entlang eines oder mehrerer der Indizes aufteilen, wobei Daten, die während der Ausführung zumindest ausgewählter Felder einem Zugriff ausgesetzt sind, von denjenigen abhängig sind, die während der Ausführung eines anderen Feldes modifiziert werden, und wobei diese Felder eine Abhängigkeitsrichtung haben,

ii) Erzeugen eines Feldstrategiesignales, welches eine Folge der Erzeugung der entsprechenden Felder entsprechend der Abhängigkeitsrichtung anzeigt.

51. Verfahren nach Anspruch 50, wobei die Feldstrategieeinrichtung Einrichtungen für das Betätigen der Wellenfronteinrichtung aufweist, wobei die Daten, die während der Ausführung zumindest eines solchen Feldes einem Zugriff ausgesetzt sind, von denjenigen abhängig sind, die während der Ausführung eines anderen solchen Feldes modifiziert werden.

52. Verfahren nach Anspruch 50, welches das Betätigen der Wellenfronteinrichtung in Reaktion auf ein vom Benutzer zugeführtes Signal aufweist.

53. Verfahren nach Anspruch 43, welches das Bereitstellen von einer wahlweise betätigbaren Modulo/Wellenfronteinrichtung aufweist, um die Schritte auszuführen

i) Erzeugen von Grenzen entsprechenden Signalen, um den Iterationsraum entlang aller Indizes in Abschnitte fester Länge aufzuteilen, wobei Daten, die während der Ausführung zumindest eines ausgewählten Feldes einem Zugriff ausgesetzt sind, von denjenigen abhängig sind, die während der Ausführung eines oder mehrerer anderer Felder modifiziert werden, und wobei diese Felder eine Abhängigkeitsrichtung haben, und

ii) Erzeugen eines Feldstrategiesignals, welches die Zuordnung der entsprechenden Felder auf der Basis Modulo einer numerischen Kennzeichnung anzeigt, die jeder der verfügbaren Prozessoreinheiten zugeordnet ist, sowie einer numerischen Kennzeichnung, die jedem der Felder zugeordnet ist, sowie auf der Basis der Abhängigkeitsrichtung.

54. Verfahren nach Anspruch 53, welches das Betätigen der Modulo/Wellenfronteinrichtungen in Feldern aufweist, in denen

i) Daten, die während der Ausführung zumindest eines solchen Feldes einem Zugriff ausgesetzt sind, von denjenigen abhängig sind, die während der Ausführung eines oder mehrerer anderer solcher Felder ausgesetzt sind, und

ii) erneute Verwendung von Daten, die irgendeinem Zugriff vom Lesetyp oder Schreibtyp durch eine Verarbeitungseinrichtung ausgesetzt sind, welche eine Mehrzahl von Feldern ausführt, maximal gemacht werden, selbst wenn eine Veränderung der Größe des Iterationsraumes vorliegt.

55. Verfahren nach Anspruch 53, welches das Betätigen der Modulo/Wellenfronteinrichtung in Reaktion auf ein vom Benutzer zugeführtes Signal aufweist.

56. Verfahren nach Anspruch 43, welches das Bereitstellen einer wahlweise betätigbaren Greifeinrichtung aufweist, um

i) Grenzen entsprechende Signale zu erzeugen, um den Iterationsraum entlang aller Indizes in Abschnitte fester Länge einzuteilen, wobei Daten, die während der Ausführung irgendeines Feldes einem Zugriff ausgesetzt sind, nicht von denjenigen abhängig sind, die während der Ausführung eines anderen Feldes modifiziert werden, und

ii) ein Feldstrategiesignal zu erzeugen, welches eine Folge der Erzeugung der entsprechenden Felder anzeigt in Reaktion auf die Anzeige der Verfügbarkeit durch die Prozessoreinheiten, und zwar auf der Basis first-come-first-serve.

57. Verfahren nach Anspruch 56, wobei die Feldstrategieeinrichtung Einrichtungen aufweist für das Betätigen der Greif- bzw. Erfassungseinrichtung,

i) um einen Lastenausgleich zwischen den Prozessoreinheiten zu ermöglichen, welche die Felder ausführen, und in Fällen, in welchen

ii) keine beträchtliche Menge an Daten irgendeinem Zugriff vom Lesetyp oder Schreibtyp durch ein solches Feld ausgesetzt sind, die auch irgendeinem Zugriff vom Lese- oder Schreibtyp durch ein anderes solches Feld ausgesetzt sind.

58. Verfahren nach Anspruch 56, welches das Betätigen der Wellenfronteinrichtung in Reaktion auf ein vom Benutzer zugeführtes Signal aufweist.

59. Verfahren nach Anspruch 36, welches die Schritte aufweist

Bereitstellen eines Affinitätsbereichssignals, welches einer oder mehrerer Iterationssequenzen entspricht, die auf dieselben Daten zugreift,

Erzeugen eines oder mehrerer von

i) einem Signal, welches einem Iterationsraum entspricht, in dem eine oder mehrere in Felder aufgeteilte Sequenzen innerhalb des Affinitätsbereiches auszuführen sind,

ii) einem Feldformsignal, welches einem oder mehreren Maßen eines Grenzen entsprechenden Signals entspricht,

iii) einem Feldstrategiesignal, welches zumindest eine Folge oder eine Art und Weise der Zuordnung von Feldern zu den Prozessoreinheiten anzeigt, und

iv) einem Teamsignal, welches einem Satz von Prozessoreinheiten entspricht, durch welche die in Felder aufgeteilten Sequenzen innerhalb des Affinitätsbereiches ausgeführt werden sollen, um eine Übertragung von Daten minima zu machen, die während einer solchen Ausführung irgendeinem Zugriff vom Lesetyp oder Schreibtyp ausgesetzt sind.

60. Verfahren nach Anspruch 59, wobei die Aufbaueinrichtung für den Affinitätsbereich Einrichtungen umfaßt für das Festlegen des Iterationsraumes, so daß er einen oder mehrere der Iterationsräume der Feldsequenzen in dem Affinitätsbereich umfaßt.

61. Verfahren zum Betreiben eines Compilers von dem Typ für das Übersetzen von Programmsignalen, die einem Programm entsprechen, einschließlich einer iterativen Sequenz, im Quellcodeformat, in eine Codesequenz von Anweisungen in einem Objektcodeformat, welches geeignet ist, um für die Ausführung durch eine Mehrzahl von parallelen digitalen Datenverarbeitungseinheiten geladen zu werden, wobei der Compiler eine Abhängigkeitseinrichtung umfaßt, um eine Abhängigkeitsrichtung für die iterative Sequenz zu bestimmen, und um ein hierfür repräsentatives Signal zu erzeugen, wobei das Verfahren aufweist: Reagieren auf die iterative Sequenz im Quellcodeformat, um eine in Felder aufgeteilte Sequenz von Anweisungen zu erzeugen, die derselben im Objektcodeformat entspricht, und um weiterhin auf die iterative Sequenz zu reagieren und um ein oder mehrere vom Benutzer spezifizierte Signale auf Null zu setzen, um ein oder mehrere Signale zu erzeugen, um Grenzen für eines oder mehrere Felder zu erzeugen, auf welchen die in Felder aufgeteilte Sequenz auszuführen ist.

62. Verfahren nach Anspruch 61, welches die Reaktion auf Anweisungen in der iterativen Sequenz und auf das der Abhängigkeitsrichtung entsprechende Signal aufweist, um Signale zu erzeugen, die einem oder mehreren Indizes in dem Iterationsraum entsprechen, über welchen die in Felder aufgeteilte Sequenz auszuführen ist.

63. Verfahren nach Anspruch 62, mit

Annehmen von Signalen, die einer vom Benutzer spezifizierten Indizierung des Iterationsraumes entsprechen, und

Vergleichen der vom Benutzer spezifizierten Indexierungssignale mit denjenigen, die durch das Verfahren erzeugt wurden, und um ein Kennzeichnungssignal für den Fall zu erzeugen, daß zumindest eine ausgewählte Nichtübereinstimmung auftritt.

64. Verfahren nach Anspruch 62, mit Erzeugen eines oder mehrerer Signale für die Verwendung während der Laufzeit, um die parallele Ausführung der 11 Felder aufgeteilten Sequenz zu optimieren.

65. Verfahren nach Anspruch 64, mit Erzeugen eines Affinitätssignals, welches einer Feldausführungssequenz entspricht, die eine Übertragung von Daten minimal macht, welche während der Ausführung derselben in mehreren Feldern irgendeinem Zugriff vom Lese- oder Schreibtyp ausgesetzt sind.

66. Verfahren nach Anspruch 64, wobei die Optimierungseinrichtung Einrichtungen aufweist für das Erzeugen eines Affinitätsbereichssignals, welches einer oder mehrerer Iterationssequenzen entspricht, die auf dieselben Daten zugreifen.

67. Verfahren nach Anspruch 66, welches weiterhin aufweist

Annehmen von Signalen, die einem vom Benutzer spezifizierten Affinitätsbereichssignal entsprechen, und

Vergleichen des vom Benutzer spezifizierten Affinitätsbereichssignals mit demjenigen, welches durch das Verfahren erzeugt wurde, und um ein Kennzeichnungssignal für den Fall zu erzeugen, daß zumindest eine ausgewählte Nichtübereinstimmung auftritt.

68. Verfahren nach Anspruch 64, mit Erzeugen eines Signals, welches einer Abschätzung eines Verarbeitungsaufwandes entspricht, der zu der Ausführung der in Felder aufgeteilten Sequenz gehört.

69. Verfahren nach Anspruch 61 mit Ersetzen der iterativen Sequenz in dem Quellcodeformat durch eine Anweisung, die einem Aufruf an ein einen Code abfertigenden Unterprogramm entspricht.

70. Verfahren nach Anspruch 69 mit Ausführung der dem Aufruf entsprechenden Anweisung, um die Ausführung der in Felder aufgeteilten Sequenz durch die Prozessoreinheiten auszulösen.