DE3882990T2

DE3882990T2 - Verfahren und gerät zur simulation von m-dimensionalen verbindungsnetzwerken in einem n-dimensionalen netzwerk, worin m kleiner ist als n.

Info

Publication number: DE3882990T2
Application number: DE88904811T
Authority: DE
Inventors: Daniel Hillis; Brewster Kahle; George Robertson; Guy Steele
Original assignee: Thinking Machines Corp
Current assignee: Thinking Machines Corp
Priority date: 1987-04-27
Filing date: 1988-04-26
Publication date: 1993-11-25
Anticipated expiration: 2008-04-27
Also published as: DE3882990D1; US5050069A; ATE92658T1; EP0358704B1; JPH02503245A; EP0358704A4; WO1988008566A1; EP0358704A1

Description

Verweis auf Anmeldungen, die mit der vorliegenden Anmeldung in Beziehung stehen

Mit der vorliegenden Anmeldung in Beziehung stehende Anmeldungen sind "Parallel Processor", US-A-4 814 973, und "Parallel Processor/Memory Circuit", US-A-6 709 327, die beide am 31. Mai 1983 eingereicht worden sind, sowie "Method and Apparatus for Routing Message Packets", US-Patent 4 598 400 und "Method and Apparatus for Interconnecting Processors in a Hyper-Dimensional Array", US-A-4 805 091, die am 31. Mai 1985 eingereicht worden sind.

Hintergrund der Erfindung

Die vorliegende Erfindung bezieht sich auf mehrdimensionale Verbindungsnetzwerke. Für die Verbindung paralleler Prozessoren, wie sie in der oben angegebenen US-Patentschrift 4 598 400 beschrieben worden sind und wie sie im nachfolgenden beschrieben werden, sind derartige Netzwerke insbesondere nützlich, jedoch eignen sie sich auch für andere Gebiete.
Wie in der Figur 1A in US-PS 4 598 400 gezeigt ist, umfaßt das Parallelprozessorsystem dieses Patents einen Mainframe-Computer 10, einen Mikrocontroller 20, ein Feld 30 parallel verarbeitender integrierter Schaltkreise 35, eine Datenquelle 40, einen ersten Puffer und Multiplexer/Demultiplexer 50, erste, zweite, dritte und vierte bidirektionale Bussteuerschaltkreis 60, 65, 70, 75 einen zweiten Puffer und Multiplexer/Demultiplexer 80 und eine Datensenke 90. Der Mainframe-Computer 10 kann ein in geeigneter Weise und kommerziell verfügbarer "general purpose computer", wie etwa ein VAX-Computer, wie er von Digital Equipment Corp. hergestellt wird, sein. Der Mikrocontroller 20 stellt einen Befehlssequenzer herkömmlicher Art zum Erzeugen einer Sequenz von Befehlen dar, welche dem Feld 30 über einen Zweiunddreißig-Bit-Parallel-Bus 22 zugeführt werden. Der Mikrocontroller 20 empfängt von dem Feld 30 ein Signal auf der Leitung 26. Der Bus 22 und die Leitung 26 sind parallel mit jedem IC 35 verbunden. Als Ergebnis werden die Signale von dem Mikrocontroller 20 gleichzeitig zu jedem IC 35 im Feld 30 angelegt und das Signal, das dem Mikrocontroller 20 auf der Leitung 26 zugeführt wird, wird durch Kombinieren der Signalausgänge von allen ICs 35 des Feldes gebildet.
Das Feld 30 enthält tausende identischer ICs 35; jeder IC 35 enthält mehrere identische Prozessoren/Speicher 36. In der Ausführungsform, wie sie in dem '400-Patent enthalten ist, ist angedeutet, daß das Feld bis zu 32.768 (= 2&sub1;&sub5;) identische ICs 35 enthält; jeder IC 35 kann 32 (= 2&sub5;) identische Prozessoren/Speicherrr 36 enthalten. Zum Zeitpunkt der Einreichung dieser Anmeldung in den USA wurden Felder mit bis zu 4.096 (= 2&sub1;&sub2;) identischen PCs 35, die jeweils 16 (= 2&sub4;) identische Prozessoren/Speicher enthalten, vom Abtretungsempfänger hergestellt und als Connection Machine-Computer (Reg. TM) auf den Markt gebracht.
Das '400-Patent beinhaltet einen parallelen Prozessor, in dem die Prozessoren/Speicher 36 in zwei Geometrien organisiert und miteinander verbunden sind. Die erste ist ein herkömmliches zweidimensionales Gittermuster, in dem die Prozessoren/Speicher in einem rechteckigen Feld organisiert sind und mit ihren vier nächsten Nachbarn des Feldes verbunden sind. Die zweite ist ein Boolscher n-Würfel mit 15 Dimensionen. Um die Prozessoren/Speicher in einem zweidimensionalen Gittermuster zu verbinden, sind die ICs 35 des Feldes 30 in einem rechteckförmigen Feld von 256 (= 2&sub8;) Reihen und 128 (= 2&sub7;) Spalten organisiert; die 32 Prozessoren/Speicher jedes ICs sind in einem rechteckförmigen Feld von 4 (= 2&sub2;) Reihen und 8 (= 2&sub3;) Spalten verbunden. Im Ergebnis sind 1.048.576 Prozessoren/Speicher 36 des Feldes 30 in einem Rechteck von 1.024 (= 2&sub1;&sub0;) Reihen und 1.024 Spalten verbunden. Zum leichteren Verständnis sind die Seiten dieses quadratischen Feldes mit NORD, OST, SÜD UND WEST bezeichnet. Um jeden Prozessor/Speicher mit seinen vier nächsten Nachbarn zu verbinden, sind die individuellen Prozessoren/Speicher durch elektrische Leitungen zwischen benachbarten Prozessoren/Speichern in jeder Reihe und Spalte miteinander verbunden; die vier nächsten Nachbarn jedes ICs mit Ausnahme derer an den Ecken des Feldes werden als die vier ICs gewählt, die in nördlicher, östlicher, südlicher und westlicher Richtung unmittelbar dem IC benachbart sind.
Das oben beschriebene zweidimensionale Gitter läßt keinen Stellenaustausch von Daten in beliebigen Richtungen zwischen den prozessoren/Speichern 36 in dem zweidimensionalen Feld zu. Darüber hinaus ist es zum Verschieben von Daten zwischen der Kante des Feldes und einem speziellen prozessor/Speicher notwendig, diese Daten durch alle prozessoren/Speicher zwischen der Kante und dem entsprechenden prozessor/Speicher zu schieben, was Schiebeoperationen durch mehr als 500 prozessoren/Speicher notwendig macht. Selbst wenn es möglich ist, eine einzelne Schiebeoperation mit sehr hoher Geschwindigkeit auszuführen, macht es die Notwendigkeit, 500 derartige Schiebeoperationen auszuführen, um eine komplette Operation zu erhalten, untolerierbar langsam. Mit den zusätzlichen Komplikationen zum Ausführen derartiger Schiebeoperationen zur gleichen Zeit für eine große Anzahl von Prozessoren/Speichern in beliebigen und voneinander unabhängigen Richtungen, wird des unmöglich, ein derartiges großes zweidimensionales Gitter von Prozessoren/Speichern mit vernünftigen Kosten zu betreiben.
Dieses Problem wird gelöst, indem die Prozessoren/Speicher 36 gemäß einer zweiten Geometrie miteinander verbunden werden. Insbesondere sind die ICs 35 in dem Beispiel, wie es in dem '400-Patent beschrieben ist, in der Form eines Boolschen n-Würfels mit fünfzehn Dimensionen organisiert und miteinander verbunden. Jeder IC weist einen Logik-Schaltkreis auf, um das Weiterleiten von Nachrichten durch ein derartiges Verbindungsnetzwerk zu steuern; innerhalb jedes ICs sind Busverbindungen zu den zweiunddreißig prozessoren/Speichern vorgesehen, so daß jeder der mehr als eine Million Prozessoren/Speicher eine Nachricht zu jedem anderen senden kann. Weiterhin können eine sehr große Anzahl von Nachrichten zu jeder Zeit gesendet werden und die Nachrichten können in beliebige Richtungen weitergeleitet werden.
Die Vorteile eines derartigen hyperdimensionalen Verbindungsnetzwerkes sind, verglichen mit denen eines herkömmlichen zweidimensionalen Verbindungsnetzwerkes, derartig bedeutend, daß sich die Frage stellt, ob zwei Verbindungsnetzwerke gerechtfertigt sind. Das zweidimensionale Netzwerk hat den Vorteil, daß es in seiner Struktur identisch zu vielen Datenfeldern ist, welche durch parallele Prozessoren manipuliert werden können. Somit ist es mit einem zweidimensionalen Verbindungsnetzwerk möglich, unmittelbar Operationen mit dem linken oder rechten, dem oberen oder unteren Nachbarn auszuführen, wie dies oft beim Manipulieren von zweidimensionalen Datenfeldern ausgeführt wird. Jedoch werden die Kosten des zweidimensionalen Netzwerkes zum großen Teil durch die begrenzte Fläche eines integrierten Schaltkreises und eine sehr hohe Anzahl von Verbindungen oder Pins auf dem integrierten Schaltkreis im Verhältnis zur bereitgestellten Funktion verursacht. Beispielsweise werden, falls jeder integrierte Schaltkreis ein 4x4-Feld von Prozessoren trägt, 16 Pins benötigt, um die Verbindungen zu den linken, rechten, oberen und unteren Nachbarprozessoren auf angrenzenden integriertem Schaltkreis zur Verfügung zu stellen. Während diese Anzahl dadurch reduziert werden kann, daß die Pin-Richtungen gemultiplext werden, wird ein Minimum von drei Pins weiterhin für diese Feldgröße benötigt.
EP-A2-0 201 797 beschreibt einen Computer mit einer Vielzahl von Prozessoren, die über ein n-dimensionales Hyper-Würfel-Netzwerk miteinander verbunden sind. Insbesondere ist die Emulation eines zwei-, drei- oder vierdimensionalen Verbindungsnetzwerkes innerhalb eines Hyper-Würfels mit mehr als vier Diemensionen durch geeignete Auswahl der nächsten Nachbarn unter Verwendung eines Gray-Code-Auswahl-Schemata beschrieben.
Es ist die Aufgabe der vorliegenden Erfindung, einen Parallel-Prozessor und ein Verfahren zum Steuern eines Parallel-Prozessors anzugeben, mit dem eine Emulation eines Verbindungsnetzwerkes mit einer geringeren Dimension als die des physikalischen Verbindungsnetzwerkes erreicht werden kann.
Diese Aufgabe wird durch die Gegenstände der Ansprüche 1 und 5 gelöst.
Gemäß der Erfindung wird jedem Element oder Knoten in einem n-dimensionalen Verbindungsmuster eine einmalige Binärzahl oder Adresse durch Nummerieren der Elemente zugewiesen. Danach werden die individuellen Binärstellen der mit jedem Element assoziierten Adresse einer unterschiedlichen Dimension des Verbindungsmusters mit m Dimensionen gemäß einer festen Regel zugeordnet. Jeder Satz von Binärstellen, der einer Dimension zugewiesen ist, wird dann als Adresse der Knotens in dieser Dimension in einem Gray-Code-Raum behandelt; die Knoten, die ihre nächsten Nachbarn in dieser Dimension sind, sind die Knoten, die die Gray-Code-Werte beinhalten, die unmittelbar vor ihm und unmittelbar hinter ihm in der Gray-Code-Sequenz darstellen. Die Daten werden dann an den nächsten Nachbarn in einer Richtung in einer Dimension dadurch weitergeleitet, daß sie von einem Knoten zum anderen Knoten weitergegeben werden, der die nächste nachfolgende (oder vorgehende) Gray-Code-Adresse enthält und ein Knoten kann so konditioniert werden, daß er die Daten empfängt, indem er nach Daten von dem Knoten mit der nächsten vorhergehenden (oder nachfolgenden) Adresse Ausschau hält.
Vorteilhafterweise kann die vorliegende Erfindung so implementiert sein, daß sie ein zweidimensionales Verbindungsnetzwerk in einem Feld von ICs, die miteinander in Form eines Hyper-Würfels mit zwölf oder mehr Dimensionen verbunden sind, simuliert.
Weiterhin ist es durch Verwendung eines "Exchangers" (Austauschers) oder Permutieres möglich, Verbindungsmuster mit unterschiedlichen Dimensionen auf individuellen IC-Chips zu simulieren. In einer bevorzugten Ausführungsform wird der Exchanger dazu verwendet, Daten von jedem Prozessor eines Feldes auf einem IC-Chip in Speicherabschnitten, die mit unterschiedlichen Prozessoren assoziiert sind, zu speichern. Mit geeigneten Austauschungen können die Datenspeichermuster die gleiche Schiebeoperation mit Daten simulieren, die unter spezifischen Betrieben in einem Netzwerk von einer, zwei oder mehreren Dimensionen auftreten würden. Zusätzlich können derartige Schiebeoperationen innerhalb eines Chips mit Datenübertragungen zwischen Chips kombiniert werden, so daß sich die Verbindungsmuster, wie sie auf individuellen Chips simuliert werden, über das gesamte Feld von Chips in dem n-dimensionalen Verbindungsnetzwerk erstrecken.

Kurze Beschreibung der Zeichnungen

Diese und andere Aufgaben, Merkmale und Vorteile der Erfindung werden anhand der detaillierten Beschreibung der Erfindung verständlich, wobei
Fig.1 ein Flußdiagramm einer bevorzugten Ausführungsform der Erfindung zeigt;
Fig.2 eine schematische Darstellung integrierter Schaltkreise ist, die zur Ausführung der Erfindung verwendet werden können;
Fig.3 eine schematische Darstellung eines Exchangers, wie er zum Ausführen eines weiteren Aspekts der Erfindung verwendet wird, zeigt;
Fig.4 eine schematische Darstellung einer Ausführungsform eines Schalters, wie er in dem Exchanger verwendet wird; und
Fig.5 ein Flußdiagramm einer weiteren Anwendung der Erfindung zeigt.

Beschreibung einer bevorzugten Ausführungsform der Erfindung

Um ein n-dimensionales Würfel-Verbindungsmuster zu verstehen, ist es hilfreich, die Elemente des Musters der Reihe nach durchzunummerieren, und diese Nummern oder Adressen in binärer Notation auszudrücken. Ist das Verbindungsmuster beispielsweise in einem Feld von 4096 integrierten Schaltkreises implementiert, so kann man die ICs von 0 bis 4095 nummerieren und diese Nummern in Binärstellen, so wie auf Tabelle I, anschreiben. TABELLE I IC-Adresse in dezimaler Notation IC-Adresse in binärer Notation
Da ein IC innerhalb des n-Würfels nur eine von zwei unterschiedlichen Positionen, 0 und 1, in jeder Position haben kann, kann die zwölfstellige IC-Adresse in binärer Notation, wie sie in Tabelle I angegeben wurde, auch dafür verwendet werden, um die Position des ICs in dem n-Würfel mit zwölf Dimensionen anzugeben. Zum leichteren Verständnis werden wir die am weitesten links stehende Binärstelle der zwölfstelligen Binärzahl zum Bestimmen der Position des ICs in der ersten Dimension verwenden und so weiter in Richtung zu der am weitesten rechts stehenden Binärstelle, um die Position des ICs in der zwölften Dimension zu bestimmen.
Weiterhin hat jeder IC zwölf andere ICs, dessen Binäradresse sich nur um eine Binärstelle von seiner eigenen Adresse unterscheidet, da eine Binärstelle nur zwei Werte, Null und Eins, annehmen kann, und da jeder IC einheitlich durch zwölf Binärstellen identifiziert ist. Wir werden diese zwölf ICs, deren Adressen sich nur um eine Stelle von der des ersten ICs unterscheiden, als die nächsten Nachbarn des ersten ICs bezeichnen. Diejenigen, die sich mit der mathematischen Definition der Hamming-Distanz auskennen, werden erkennen, daß der erste IC von den anderen zwölf nächsten Nachbarn durch die Hamming-Distanz Eins beabstandet ist. Zwei Beispiele von Adressen eines ICs und seinen zwölf nächsten Nachbarn sind in Tabelle II angegeben. TABELLE II Beispiel IC-Adresse: Adressen der nächsten Nachbarn:
In physikalischer Hinsicht sind die ICs in ein- oder zweidimensionalen Feldern auf integrierten Platinen aufgebracht. Sie sind in der Form eines zwölfdimensionalen Würfelmusters durch physikalisch verlegte Drähte von jedem IC mit seinen zwölf nächsten Nachbarn in dem Würfel verbunden. Eine besonders vorteilhafte Verbindungstechnik zum Erreichen dieser Verbindung ist in der oben genannten 740 943-Anmeldung beschrieben.
Da eine Leitung mit jeder Dimension assoziiert ist und sich nur zwei ICs in jeder Dimension befinden, kann gezeigt werden, daß die Exklusiv-Oder-Verknüpfung der Adressen beliebiger zwei ICs eine zwölfstellige Zahl ist, in der die 1-Bits die Dimensionen spezifizieren, die verwendet werden müssen, um die zwei ICs zu verbinden und somit die Leitungen des n-dimensionalen Würfels, die die zwei ICs verbinden. Eine weitere Vorstellung der hyperdimensionalen Verbindungsmuster kann von einer Betrachtung eines drei- und vierdimensionalen Würfelverbindungsnetzwerks, wie es in den Figuren 2 und 3 in dem oben genannten '400-Patent gezeigt ist, gewonnen werden.
Um ein Verbindungsmuster mit geringeren Dimensionen in einem n-dimensionalen Muster zu simulieren, ist es notwendig, in dem n-dimensionalen Muster ein Verbindungsmuster zu erstellen, das in gleicher Weise funktioniert wie das Verbindungsmuster von geringeren Dimensionen. Um eine ausführbare Simulation anzugeben, muß es auch möglich sein, diese Simulation in einer Serie paralleler Operationen zu implementieren, die gleichzeitig an allen Elementen des n-dimensionalen Musters ausgeführt werden können.
Gemäß der Erfindung wird dies, wie in Figur 1 gezeigt, durch die folgenden Schritte erreicht. Zuerst wird jedem Element oder Knoten in dem n-dimensionalen Verbindungsmuster eine einmalige Binärzahl oder Adresse durch Nummerieren der Elemente zugewiesen. Danach werden die individuellen Binärstellen der Adresse, die mit jedem Elemente assoziiert sind, unterschiedlichen Dimensionen des Verbindungsmusters von geringeren Dimensionen entsprechend einer festen Regel zugewiesen. Beispielsweise werden bei einem zweidimensionalen Verbindungsmuster die ersten sechs Bits einer Zwölf-Bit-Binäradresse der ersten Dimension oder x-Koordinate des zweidimensionalen Verbindungsmusters zugewiesen und die letzten sechs Bits der zweiten Dimension oder der y-Koordinate. Alternativ könnten die ungerade nummerierten Bits der ersten Dimension zugewiesen werden und die gerade nummerierten Bits der zweiten Dimension. Jede beliebige Regel kann verwendet werden, solange sie für jede binäre Adresse in dem n-dimensionalen Muster angewendet wird.
Jeder Satz von Binärstellen, der einer Dimension zugewiesen ist, wird dann als Adresse des Knotens in der Dimension in einem Gra-Code-Raum behandelt; und die Knoten, die dessen nächsten Nachbarn in dieser Dimension sind, sind diejenigen Knoten, die die Gray-Code-Werte unmittelbar vor und unmittelbar nach dem in der Gray-Code-Sequenz einnehmen. Somit kann für einen gegebenen Knoten die Adresse seines nächsten Nachbarknotens in einer Richtung in einer Dimension dadurch bestimmt werden, in dem die Gray-Code-Adresse des gegebenen Knotens in der Dimension in ihre binäre äquivalente Darstellung konvertiert wird, eine binäre Eins zu der äquivalenten Darstellung addiert wird und das Ergebnis zurück in den Gray-Code konvertiert wird. Die Adresse des nächsten Nachbarn in der anderen Richtung der gleichen Dimension wird erhalten, indem dasselbe Verfahren angewendet wird mit dem Unterschied, daß eine binäre Eins von der binären äquivaltenen Darstellung subtrahiert statt addiert wird. Alternativ könnten die Gray-Code-Adressen der nächsten Nachbar-ICs von einer sequentiellen Auflistung von Gray-Codes bestimmt werden.
In gleicher Weise können die Sätze binärer Stellen, die anderen Dimensionen des Verbindungsnetzwerks mit geringerer Dimension zugewiesen sind, in entsprechender Weise als Gray-Code-Adressen dieses Knotens behandelt werden; und in jeder Dimension werden die nächsten Nachbarn dadurch bestimmt, daß eine binäre Eins von dem binären Äquivalent des Gray-Code-Werts addiert und subtrahiert wird und die Ergebnisse in Gray-Code-Werte konvertiert werden.
Daten können dann an den nächsten Nachbarn in einer Richtung in einer gewünschten Dimension dadurch weitergegeben werden, daß sie über das n-dimensionale Netzwerk von einem IC zu dem IC, der die nächstfolgende Gray-Code-Adresse aufweist, weitergegeben werden; und ein IC kann eingestellt werden, um derartige Daten zu empfangen, indem man ihn veranlaßt, nach Daten von dem IC mit der nächstvorausgehenden Adresse Ausschau zu halten. Alternativ können Daten in die entgegengesetzte Richtung weitergeleitet werden, indem man sie von einem IC zu dem IC mit der nächstvorhergehenden Adresse weitergibt und indem nach Daten von dem IC mit der nächstnachfolgenden Adresse Ausschau gehalten wird.
Eine geeignete zu verwendendene Würfelverbindung wird bestimmt, indem man eine Exklusiv-Oder-Verknüpfung der Gray-Code-Adressen des Quell-ICs und des Ziel-ICs ausführt. Da diese Adressen sequentielle Gray-Code-Adressen sind, unterscheiden sie sich nur in einem Bit und dieses eine Bit spezifiziert die Verbindung, die für die Kommunikation verwendet werden muß. In gleicher Weise wird die Leitung, die für den Empfang von Daten beobachtet werden muß, dadurch bestimmt, daß man die Exklusiv-Oder-Verknüpfung der Gray-Code-Adressen des Quell-ICs und des Ziel-ICs verwendet. Erneut stellen diese Adressen sequentielle Gray-Code-Adressen dar und das eine Bit, in dem sie sich unterscheiden, spezifiziert die für die Kommunikation zu verwendende Leitung.
Die nächsten Nachbar-Verbindungen können dann soweit wie nötig zum Weiterleiten von Daten in der gleichen Dimension verwendet werden. In gleicher Weise können die nächsten Nachbaradressen in anderen Dimensionen bestimmt werden.
Weiterhin werden genau die gleichen Berechnungen und Operationen an jedem Knoten ausgeführt, um seine nächsten Nachbarn zu bestimmen. Somit werden die gleichen Bits der Knotenadresse an jedem Knoten untersucht, um die Gray-Code-Adresse in dieser Dimension zu bestimmen. Die gleichen Schritte werden ausgeführt, um die Adresse und die Würfelverbindung für den nächsten Nachbar-IC in der gewünschten Richtung in dieser Dimension zu bestimmen; und die gleichen Schritte werden ausgeführt, um die Adresse und die Würfelverbindung des nächsten Nachbar-ICs in der entgegengesetzten Richtung zu bestimmen. Im Ergebnis können alle ICs des n-dimensionalen Netzwerkes gleichzeitig betrieben werden, um Daten an ihre nächsten Nachbarn in einer Dimension gemäß der Ordnung, wie sie durch die Gray-Code-Sequenz bestimmt wurde, zu bewegen.
Das folgende Beispiel illustriert, wie die Erfindung ausgeführt sein kann. Gemäß der Erfindung wird eine einmalige Binärzahl jedem Knoten in dem Verbindungsnetzwerk zugewiesen. Nimmt man an, daß 4.096 (= 2¹²) Knoten in dem Netzwerk vorhanden sind, und daß die Binärzahl 000 111 001 101 einem dieser Knoten zugewiesen ist, so werden zur Bestimmung der nächsten Nachbarn dieses Knotens in einem zweidimensionalen Netzwerk einige der Binärstellen der Binärzahl einer Dimension und einige einer anderen Dimension zugewiesen. Es wird angenommen, daß die ersten sechs Stellen der ersten Dimension oder x-Koordinate und die letzten sechs Stellen der zweiten Dimension oder y-Koordinate zugewiesen worden sind. Da jeder Knoten eine einmalige Binärzahl aufweist, spezifizieren die sechs Stellen in jeder Dimension ein zweidimensionales Feld von 64x64 (= 2&sup6; x 2&sup6;) Knoten. Diese Binärstellen werden dann als Gray-Codes zum Zwecke der Bestimmung ihrer nächsten Nachbarn in der ersten und zweiten (x und y) Dimensionen und dabei zum Spezifizieren ihrer Verbindungen verwendet.
Es gibt unterschiedliche Gray-Codes und unterschiedliche Formeln für deren Bildung. Eine bevorzugte Formel zur Erzeugung eines Gray-Codes einer Binärzahl n ist
Gray Code (n) = n (n um 1 nach rechts geschoben) (1)
wobei die logische Exklusiv-Oder-Verknüpfung und (n um 1 nach rechts geschoben) die Binärzahl n um 1 nach rechts verschoben ist. In der anderen Richtung kann die äquivalente Binärzahl eines Gray-Codes durch Verwendung der folgenden Formel auf Binärstelle nach Binärstellen-Basis zum Erzeugen der Binärstellen der Binärzahl bestimmt werden:
bdi = gdi gdi-1 ... gd&sub1; (2)
wobei die logische Exklusiv-Oder-Verknüpfung, i die Anzahl der Binärstellen in der Binärzahl oder in dem Gray-Code-Äquivalent ist, bdi die i-te derartige Binärstelle, und gdi die i-te derartige Gray-Code-Stelle ist. Vorteilhafterweise werden diese Formel für die Erfindung benutzt, um die Gray-Code- und Binär-Umwandlungen zu berechnen. Jedoch zum Zwecke des Verständnisses des Beispiels ist eine Tabelle, die die Beziehung der Gray-Codes mit ihrem Binärwert aufzeigt, geeigneter und die ersten sechzehn Werte und der letzte Wert einer derartigen Vierundsechzig-Wert-Code-Tabelle ist in Tabelle III angegeben. TABELLE III Binärwert Gray-Code-Wert
Somit wird zum Auffinden der nächsten Nachbarn in der ersten Dimension des Knotens mit der Adresse 000 111 001 101 die Zahl 000 111 als Gray-Code-Wert betrachtet und deren binäres Äquivalent unter Verwendung der Formel (2) zu 000 101 berechnet. Um die nächsten Nachbarn in einer Richtung zu finden, wird der Binärwert 1 zu diesem Äquivalent addiert, um den Wert 000 110 zu erreichen, welcher dann in den Gray-Code-Wert von 000 101 unter Verwendung der Formel (1) konvertiert wird, wodurch der Knoten in dieser Richtung identifiziert wird. Die Exklusiv-Oder-Verknüpfung der Adressen 000 111 und 000 101 erzeugt die Zahl 000 010, die anzeigt, daß die Weiterleitungsleitung die fünfte Würfelleitung des Satzes ist, welcher mit der fünften Dimension in dem zwölfdimensionalen Netzwerk korrespondiert. Um den nächsten Nachbarn in der anderen Richtung zu lokalisieren, wird der Binärwert 1 von dem binären Äquivalent subtrahiert, um den Wert 000 100 zu erreichen, welcher dann in 000 110 konvertiert wird, wodurch der Knoten in dieser Richtung identifiziert wird. Die Exklusiv-Oder-Verknüpfung von 000 111 und 000 110 erzeugt die Zahl 000 001, die anzeigt, daß die Kommunikation mit dem nächsten Nachbarn in der anderen Richtung über die sechste Leitung des Satzes, welcher mit der sechsten Dimension des zwölfdimensionalen Netzwerkes korrespondiert, stattfindet.
In gleicher Weise werden die nächsten Nachbarn in der zweiten Dimension als 001 100 und 001 111 bestimmt und die Kommunikation mit diesem Knoten in dem zweidimensionalen Netzwerk findet über die fünfte und sechste Leitung des Satzes, der mit der elften und zwölften Dimension des zwölfdimensionalen Netzwerkes korrespondiert, statt.
Wenn es erwünscht ist, Netzwerke zu simulieren, die eine andere Dimension als zwei Dimensionen aufweisen, so ist dies lediglich eine Frage der Zuweisung geeigneter Binärstellen der Adresse jedes Knotens des n-dimensionalen Verbindungsnetzwerkes zu der gewünschten Anzahl von Dimensionen. Nachdem die Zuweisung stattgefunden hat, werden die Operationen für jede Dimension unabhängig in einer Weise, wie es für das obige Beispiel eines simulierten zweidimensionalen Netzwerkes beschrieben wurde, ausgeführt.
In der Vorrichtung, wie sie in dem '400-Patent beschrieben ist, wird das zweidimensionale Verbindungsnetzwerk auch dazu benutzt, um die individuellen Prozessoren in einem integrierten Schaltkreis zu verbinden; und das zweidimensionale Muster, das auf jedem IC errichtet ist, wird von einem Chip auf dessen nächste Nachbarn in einem zweidimensionalen Feld von Chips weitergeführt. Somit haben für den Fall, in dem die Prozessoren in einem zweidimensionalen Muster mit vier Zeilen und acht Spalten miteinander verbunden sind, die vier Prozessoren auf der rechten Seite eines ICs einen nächsten Nachbarprozessor zur rechten Seite, der auf der linken Seite des ICs angeordnet ist, der der nächste Nachbar-IC auf der rechten Seite ist; die acht Prozessoren entlang der oberen Kante eines ICs haben jeweils einen nächsten Nachbarprozessor über ihnen, der an der unteren Kante des ICs angeordnet ist, der der nächste Nacnbar-IC in der oberen Richtung ist; und so weiter nach links in die unteren Richtungen. Falls gewünscht, kann dieses zweidimensionale Verbindungsnetzwerk auf den individuellen IC-Chips auch dadurch simuliert werden, daß die oben beschriebenen Techniken und eine Vorrichtung, wie sie auf dem Markt verfügbaren Ausführungen der Vorrichtung, wie sie im '400-Patent gezeigt ist, verwendet werden.
Insbesondere umfaßt, wie in schematischer Weise in Figur 2 gezeigt ist, ein integrierter Schaltkreis zur Benutzung in einem parallelen Prozessor sechzehn Prozessoren 10, ein Speicher-Interface 20, einen Steuerschaltkreis 30 und ein Kommunikations-Interface oder Weiterleiter (router) 40.
Beispielhaft sind die Prozessoren gleich denen, wie sie in dem '400-Patent beschrieben wurden, mit der Ausnahme, daß ein Lese/Schreibspeicher 25 auf einem oder mehreren anderen ICs angeordnet ist, auf den durch das Speicher-Interface in einer Weise zugegriffen wird, wie sie beispielsweise in der Figur 6 der oben erwähnten 924 090-Anmeldung gezeigt ist. Daten, die für die spätere Verwendung von dem gleichen Prozessor gespeichert werden sollen oder die an andere Prozessoren auf dem gleichen IC oder zu den Prozessoren auf andere IC übertragen werden sollen, werden von den Prozessoren 10 über die Datenbusse 12 und 22 und das Speicher-Interface 20 zu dem Lese/Schreib-Speicher 25 zur Verfügung gestellt, wo sie gespeichert werden, bis sie verwendet werden können oder übertragen werden können. Für Daten, die von dem aussendenden Prozessor oder anderen Prozessoren auf dem gleichen IC gebraucht werden, werden die Daten von dem Lese/Schreib-Speicher entfernt und über das Speicher-Interface 20 und den Datenbus 26 an die Prozessoren zur Verfügung gestellt. Für die Übertragung an andere ICs werden die Daten von dem Lese/Schreib-Speicher 25 entfernt und dem Kommunikations-Interface 40 über das Speicher-Interface 20 und den Datenbus 28 zur Verfügung gestellt. Das Kommunikations-Interface 40 ist über die Würfel-Leitungen 42, die zu anderen integrierten Schaltkreisen führen, verbunden, um ein n-dimensionales Verbindungsnetzwerk unter den integrierten Schaltkreisen zu erreichen.
Mit den Prozessoren 10 ist ein Auswechsler (exchanger) oder Permutierer 15 assoziiert zum Vertauschen der Signale an den Ausgangsleitungen von den Prozessoren, bevor diese Signale dem Speicher-Interface zugeführt werden. Wie in den Figuren 3 und 4 gezeigt ist, umfaßt der Exchanger (Auswechsler) ein Feld von Schaltern 62, von denen jeder so wie gezeigt zwischen einem Feld von Eingängen 64 und einem Feld von Ausgängen 66 und einer Steuersignalquelle 68 für jeden Schalter verbunden ist. Wie in Figur 4 gezeigt ist, umfaßt jeder Schalter 62 vier Und-Gatter 72-75, die wie gezeigt, zwischen einem Paar von Eingängen 76, 77 und einem Paar von Ausgängen 78, 79 verbunden sind, und von einem Signal von der Quelle 68 gesteuert werden. Im Betrieb wird ein Signal, welches auf der Leitung 76 eingegeben wird, auf der Leitung 78 oder der Leitung 79 ausgegeben, abhängig vom Zustand des Signals von der Quelle 68; und in gleicher Weise wird ein Signal, welches auf der Leitung 77 eingegeben worden ist, auf der Leitung 79 oder der Leitung 78 ausgegeben, abhängig von dem Signal von der Quelle 68. Im Ergebnis werden die Signale auf den Leitungen 76 und 77 entweder vertauscht oder nicht vertauscht.
Beispielhaft ist der Exchanger, so wie in Figur 3 gezeigt ist, so ausgelegt, daß er die Signale auf sechzehn Eingangsleitungen 64, wobei von jedem der Prozessoren eine ausgeht, zu vertauschen, wofür ein 4x8-Feld von Schaltern A1-A8 bis D1-D8 und zweiunddreißig Signalquellen 68 benötigt werden. Die Signalquellen sind beispielhaft als Register oder mehrere Register implementiert, die einen Zweiunddreißig-Bit-Ausgang aufweisen, wobei jedes Bit den Zustand eines unterschiedlichen Schalters steuert.
Gemäß der Erfindung können der Exchanger 15 und der Speicher 25 dazu benutzt werden, um Daten zwischen den Prozessoren in einem Muster zu verschieben, welches ein Verbindungsfeld, wie beispielsweise eines mit einer oder zwei Dimensionen, simuliert. insbesondere werden unterschiedliche Abschnitte des Speichers 25 durch unterschiedliche Ausgangsleitungen 24 von dem Exchanger 15 beschrieben und die Daten, die in diesen Daten gespeichert sind, werden jeweils einem anderen Prozessor zugänglich gemacht. In entsprechender Weise können durch das Vertauschen der Signale auf den Ausgangs leitungen von den Prozessoren, Daten von einem Prozessor in einem Abschnitt des Speichers, welcher mit einem anderen Prozessor assoziiert ist, gespeichert werden und dann von diesem Abschnitt ausgelesen werden und dem anderen Prozessor zugeführt werden. Als Beispiel werden die 16 Prozessoren durch die Buchstaben a-p identifiziert und die Prozessoren sollen in einem 4x4-Feld, wie es in Tabelle IV gezeigt ist, angeordnet sein. TABELLE IV
Jeder dieser Prozessoren hat einen Datenausgang, welcher mit einer der Eingangs leitungen des Exchangers 15 verbunden ist. Beispielsweise ist, wie dies in den Spalten 1 und 2 der Tabelle V gezeigt ist, der Prozessor a mit der Eingangsleitung 0 verbunden, der Prozessor b mit der Leitung 1 und so weiter. Bei geeigneter Einstellung A-F der Schalter 62 werden die Dateneingänge an den Exchanger 15 auf der Leitung 0 vom Prozessor a, die Ausgänge von dem Exchanger auf den Leitungen 3, 1, 4, 12, 1 und 15 sein, und daher innerhalb des Speichers in einem Abschnitt gespeichert werden, der mit den Prozessoren d, b, e, m, b und p assoziiert ist. In entsprechender Weise gibt die Tabelle V für jede anderen Eingangs/Ausgangsleitung die Beziehung zwischen der Information an den Eingangs- und Ausgangsleitungen und der Schalterfestsetzung an. TABELLE V I/O Leitung Datenquelle Schaltstellung Datenausgang
wobei
die Schalter A1-A8, B2, B4, B6, B8 so gesetzt sind, daß sie die Signale in der Schalterstellung A vertauschen; die Schalter A1-A8, B1, B3, B5, B7 so gesetzt sind, daß sie sie die Signale in der Schalterstellung B vertauschen; die Schalter C1-C8, D1-D4 so gesetzt sind, daß sie die Signale in der Schalterstellung C vertauschen;
die Schalter C1-C8, D5-D8 so gesetzt sind, daß sie die Signale in der Schalterstellung D vertauschen;
die Schalter A1-A8, B1, B3, B5, B7, C1, C5, D1 so gesetzt sind, daß sie die Signale in der Schalterstellung E vertauschen; und
die Schalter A1-A8, B2, B4, B6, B8, C4, C8, D8 so gesetzt sind, daß sie die Signale in der Schalterstellung F vertauschen.
Für die Schalterstellungen A-D ist der Exchanger-Ausgang so, daß die Daten von den Prozessoren a-p in dem Speicher in den Mustern, wie sie in den Tabellen VIA-VID gezeigt sind, gespeichert werden. TABELLE VIA TABELLE VIB TABELLE VIC TABELLE VID
Somit hat die Schalterstellung A bewirkt, daß die Daten von den Prozessoren des 4x4-Feldes eine Spalte nach rechts verschoben wurden, die Schalterstellung B, daß die Daten eine Spalte nach links verschoben wurden, die Schalterstellung C hat bewirkt, daß sie um eine Reihe nach oben verschoben wurden und die Schalterstellung D, daß sie um eine Reihe nach unten verschoben wurden. Die Schalterstellung E und F haben in gleicher Weise bewirkt, daß eine Verschiebung um eine Einheit nach links und eine Verschiebung um eine Einheit nach rechts bei einem eindimensionalen sequentiellen Feld von sechzehn Elementen bewirkt wurde.
Durch die vorhergehende Lehre wurde eine Einrichtung angegeben zum Simulieren eines ein- und zweidimensionalen Verbindungsnetzwerkes in einem Schaltkreis, der einen Exchanger und einen Speicher anstatt einer direkten physikalischen Verdrahtung zwischen nächsten Nachbarelementen aufweist.
Diese Technik kann auf mehr Dimensionen ausgedehnt werden, wenn dies gewünscht wird. Diese Technik kann auch mit der Simulationstechnik, wie sie in Verbindung mit Figur 1 besprochen wurde, kombiniert werden, um dadurch beispielsweise ein zweidimensionales Feld, das in einem Exchanger implementiert ist, über eine Vielzahl von IC-Chips, die in einem n-dimensionalen kubischen Netzwerk verbunden sind, auszudehnen. Wie in Figur 5 gezeigt ist, wird dies dadurch erreicht, daß zuerst die nächsten Nachbarchips durch die gleiche Prozedur, wie sie in Figur 1 beschrieben wurde, identifiziert werden, und dann der Exchanger dazu benutzt wird, um die Daten von den Prozessoren auf jeden Chip an die Speicherplätze, die mit unterschiedlichen Prozessören auf dem gleichen Chip assoziiert sind, zu verschieben, und danach das n-dimensionale Netz dazu verwendet wird, um die Daten in der geeigneten Richtung und Dimension an die nächsten Nachbar-ICs vom Prozessor, die sich an der Kante eines jeden Chips, der sich am nächsten zum nächsten Nachbar-IC befindet, zu übertragen und schließlich die übertragenen Daten in dem Speicher bei jedem übertragenen IC mit Daten auszutauschen, welche von seinem nächsten Nachbar-IC in der entgegengesetzten Richtung, jedoch in der gleichen Dimension empfangen worden sind.
Beispielsweise werden, um alle Daten um eine Einheit nach rechts für den Fall eines n-dimensionalen kubischen Netzwerkes integrierter Schaltkreischips, die ein 4x4-Feld von Prozessoren auf jedem Chip aufweisen, zu schieben, werden die Chips zuerst nummeriert, ihre Adressen in dem zweidimensionalen Netzwerk bestimmt und ihre nächsten Nachbarn unter Verwendung der Gray-Code-Sequenz identifiziert. Auf dem Chip-Level werden die Verschiebungen nach rechts durch Verwendung der Schalterstellung A in dem Exchanger 15 implementiert, um die Daten von jedem Prozessor auf jeden Chip in dem Speicherraum zu speichern, welcher dem auf der rechten Seite in dem 4x4-Feld liegenden Prozessor zugeordnet ist, zu speichern. Die Daten von den vier Prozessoren auf der nächsten Seite jedes Feldes werden dann durch das n-dimensionale Netzwerk von jedem IC zu seinem nächsten Nachbar-IC auf der rechten Seite in der x- oder Zeilen-Dimension übertragen. Die Identität der Würfelleitung, die diese Verbindung zur Verfügung stellt, wird dadurch bestimmt, indem die Exklusiv-Oder-Verknüpfung der Adresse des ICs und der Adresse seines nächsten Nachbar-ICs zur rechten Seite in der Reihen-Dimension verwendet wird. Bei jedem IC werden Daten von dem unmittelbar vorhergehenden IC zur linken Seite empfangen und die Würfelleitung, die diese Verbindung zur Verfügung stellt, wird durch die Exklusiv-Oder-Verknüpfung der Adresse des ICs und der Adresse des unmittelbar vorhergehenden IC nach links in der Reihen-Dimension bestimmt. Die Daten werden so, wie sie empfangen wurden, in den Abschnitt des Speichers, der mit den Prozessoren zur linken Seite des 4x4-Feldes assoziiert sind, gespeichert. Danach wird auf die Daten, die in dem Speicher gespeichert sind, durch individuelle Prozessoren zugegriffen, wobei jeder jetzt die Daten hat, die vorher bei dem Prozessor unmittelbar zur linken Seite in dem simulierten zweidimensionalen Netzwerk vorhanden waren. Die Schrittsequenz zum Verschieben der Daten nach links, oben oder unten, ist ähnlich.

Claims

1. Verfahren zum Steuern eines Parallelprozessors mit einem Feld von in etwa identischen integrierten Schaltkreisen und Speicherplätzen, auf die alle integrierten Schaltkreise zugreifen können, wobei jeder integrierte Schaltkreis eine Vielzahl von Prozessoren (10) und eine Permutiereinrichtung (15) zum Permutieren von Daten unter den Prozessoren auf jedem integrierten Schaltkreis aufweist, wobei der Parallelprozessor weiterhin ein Verbindungsnetzwerk (40) zum Verbinden der integrierten Schaltkreise in einem n-dimensionalen Netzwerk aufweist, wobei "n" größer als 2 ist und wobei jeder integrierte Schaltkreis physikalisch direkt mit n benachbarten integrierten Schaltkreisen verbunden ist, und wobei das Verfahren es dem Parallelprozessor erlaubt, ein m-dimensionales Verbindungsnetzwerk zu emulieren, wobei "m" kleiner ist als "n", welches sich über die integrierten Schaltkreise erstreckt und wobei das Verfahren folgende Schritte aufweist:

A) Setzen der Permutiereinrichtung (15) auf den integrierten Schaltkreisen, um ein geeignetes Datentransfermuster innerhalb der Prozessoren auf einem einzelnen integrierten Schaltkreis durch Schieben von Daten von den Prozessoren auf jedem integrierten Schaltkreis an die Speicherplätze, die unterschiedlichen Prozessoren auf dem gleichen integrierten Schaltkreis zugeordnet sind, was in einem Transfer von Daten entlang einer gewünschten Richtung des emulierten m-dimensionalen Verbindungsnetzwerkes auf jedem integrierten Schaltkreis resultiert, und

B) Setzen des n-dimensionalen Verbindungsnetzwerkes, um Daten zwischen gewissen Prozessoren benachbarter integrierter Schaltkreise zu verschieben, indem eine physikalische Verbindung zwischen benachbarten integrierten Schaltkreisen aktiviert wird, um eine Übertragung von Daten entlang einer ausgewählten Richtung des emulierten m-dimensionalen Verbindungsnetzwerkes auch zwischen integrierten Schaltkreisen zu erzielen,

wobei das Setzen des n-dimensionalen Verbindungsnetzwerkes umfaßt:

- Zuteilen einer einmaligen Binärzahl mit zumindest "n" Stellen an jeden integrierten Schaltkreis;

- Zuweisen gewisser Stellen jeder Binärzahl für jeden integrierten Schaltkreis an jede der "m"-Dimensionen, wobei die gleichen Stellen in jeder Binärzahl der gleichen Dimension zugewiesen sind;

- Identifizieren der nächsten Nachbarn für jeden Schaltkreis entlang jeder der "m"-Dimensionen durch Interpretieren gewisser Binärstellen, die jeder der "m"-Dimensionen zugeordnet sind, als Gray-Codes und Betrachten für jede der "m"-Dimensionen, diejenigen zwei Prozessoren als Nachbarprozessoren, die sequentielle Gray-Codes aufweisen.

2. Verfahren nach Anspruch 1, indem der Identifizierungsschritt für die nächsten Nachbarn folgende Schritte aufweist:

- Konvertieren der Stellen der Binärzahl für eine der "m"-Dimensionen von einem Gray-Code-Wert in einen äquivalenten Binärwert für jeden integrierten Schaltkreis;

- Addieren oder Subtrahieren eines Binärwerts von 1 von dem äquivalenten Binärwert um einen binären resultierenden Wert für jeden integrierten Schaltkreis zu erhalten; und

- für jeden integrierten Schaltkreis Konvertieren des resultierenden Binärwerts in sein Gray-Code-Äquivalent, wobei das Gray-Code-Äquivalent zusammen mit dem Rest der Binärzahl den nächsten Nachbarn entlang der Dimension für jeden integrierten Schaltkreis identifiziert.

3. Verfahren nach Anspruch 1 oder 2, bei dem der Setz-Schritt für das n-dimensionale Netzwerk die folgenden Schritte aufweist:

- für jeden integrierten Schaltkreis Identifizieren der Prozessoren, die die nächsten Nachbarprozessoren darstellen, die für die Übertragung von Daten an Prozessoren eines anderen integrierten Schaltkreises dienen und der Prozessoren, die die nächsten Nachbarprozessoren darstellen, die zum Empfangen von Daten von Prozessoren auf anderen integrierten Schaltkreisesn dienen; und

- Setzen der identifizierten Prozessoren, um Daten für das Verbindungsnetzwerk zu übertragen und zu empfangen.

4. Verfahren nach Anspruch 1, 2 oder 3, bei dem zumindest einige der obigen Schritte parallel ausgeführt werden.

5. Parallelprozessor mit:

A) einem Bereich von etwa identischen integrierten Schaltkreisen, von denen jeder eine Vielzahl von Prozessoren (10) und eine Permutiereinrichtung (15) zum Permutieren von Daten unter den Prozessoren auf jedem integrierten Schaltkreis aufweist,

B) Speicherplätzen (25), auf die alle integrierten Schaltkreise zugreifen können,

C) einem Verbindungsnetzwerk, welches die integrierten Schaltkreise in einem n-dimensionalen Netzwerk verbindet, wobei "n" größer als 2 ist und wobei jeder integrierte Schaltkreis physikalisch direkt mit n benachbarten integrierten Schaltkreisen verbunden ist,

D) einer Steuereinrichtung (30) zum Steuern der Prozessoren, um ein n-dimensionales Verbindungsnetzwerk zu emulieren, wobei "m" kleiner als "n" ist, welches sich über die integrierten Schaltkreise erstreckt, wobei die Steueranordnung aufweist:

i) eine Einrichtung zum Setzen der permutiereinrichtung (15) auf den integrierten Schaltkreisen, um ein geeignetes Datenübertragungsmuster innerhalb der Prozessoren auf einem einzelnen integrierten Schaltkreis durch Schieben von Daten von den Prozessoren auf jeden integrierten Schaltkreis zu den Speicherplätzen, die mit unterschiedlichen Prozessoren auf dem gleichen integrierten Schaltkreis assoziiert sind, zu erreichen, was in einer Übertragung von Daten entlang einer ausgewählten Richtung des emulierten m-dimensionalen Verbindungsnetzwerkes auf jedem integrierten Schaltkreis resultiert, und

ii) eine Einrichtung zum Setzen des n-dimensionalen Verbindungsnetzwerkes, um Daten zwischen bestimmten Prozessoren benachbarter integrierter Schaltkreise durch Aktivieren einer physikalischen Verbindung zwischen benachbarten integrierten Schaltkreisen zu übertragen, um eine Übertragung von Daten entlang einer ausgewählten Richtung des emulierten m-dimensionalen Verbindungsnetzwerkes auch zwischen integrierten Schaltkreisen zu erreichen, wobei die Setzeinrichtung aufweist:

- eine Einrichtung zum Zuteilen einer einmaligen Binärzahl mit zumindest "n" Stellen an jeden integrierten Schaltkreis;

- einer Einrichtung zum Zuweisen für jeden integrierten Schaltkreis gewisser Stellen jeder Binärzahl an jede der "m"-Dimensionen, wobei gleiche Stellen jeder Binärzahl gleichen Dimensionen zugeteilt werden;

- eine Einrichtung zum Identifizieren für jeden Schaltkreis seiner nächsten Nachbarn entlang jeder der "m"-Dimensionen, indem gewisse Stellen, die jeder der "m"-Dimensionen zugeordnet sind, als Gray-Codes interpretiert werden, und indem für jede der "m"-Dimensionen diejenigen zwei Prozessoren als Nachbarprozessoren betrachtet werden, die sequentielle Gray-Codes aufweisen.

6. Parallelprozessor nach Anspruch 5, bei der Identifizierungseinrichtung für die nächsten Nachbarn aufweist:

- eine Einrichtung zum Konvertieren der Steilen der Binärzahl, die einer der "m"-Dimensionen zugeordnet sind, von einem Gray-Code-Wert in einen äquivalenten Binärwert;

- eine Einrichtung zum Addieren oder Subtrahieren eines Binärwertes von 1 von dem äquivalenten Binärwert, um einen resultierenden Binärwert zu erzeugen; und

- eine Einrichtung zum Konvertieren des resultierenden Binärwertes zu seinem Gray-Code-Äquivalent, wobei das Gray-Code-Äquivalent zusammen mit dem Rest der Binärzahl für jeden integrierten Schaltkreis den nächsten integrierten Nachbar-Schaltkreis entlang dieser Dimension identifiziert.

7. Parallelprozessor nach Anspruch 5 oder 6, bei dem jeder integrierte Schaltkreis-Chip weiterhin ein Verbindungsnetzwerk-Interface (40) zum Bereitstellen einer Schnittstelle mit dem Verbindungsnetzwerk aufweist, und ein Speicherinterface (20) aufweist zum Bereitstellen einer parallelen Schnittstelle zwischen den Prozessoren und dem Speicher, und wobei die Permutiereinrichtung (15) zwischen den Prozessoren (10) und dem Speicher-Interface (20) verbunden ist, um das Permutieren von Daten zu erleichtern, wenn Daten zwischen dem Speicher-Interface (20) und den Prozessoren (10) übertragen werden.

8. Parallelcomputer nach mindestens einem der Ansprüche 5 bis 7, wobei für jeden integrierten Schaltkreis (10) die Permutiereinrichtung eine Mehrstufen-Schalteinrichtung (64) aufweist, wobei jede Schaltstufe eine Vielzahl von Schaltzellen aufweist, welche für die Übertragung von Daten unter den Prozessoren gemäß vorgegebenem Muster, die durch Steuersignale, die die Schaltzellen steuern, eingerichtet werden, verwendet werden, wobei die Setz-Einrichtung für die Permutiereinrichtung die Steuersignale steuert, um eine Übertragung von Daten unter den Prozessoren entlang der ausgewählten Richtung zu erreichen.

9. Parallelcomputer nach zumindest einem der Ansprüche 5 bis 8, weiterhin aufweisend einen Host-Computer zum Steuern der entsprechenden Elemente in paralleler Weise.

10. Parallelcomputer nach zumindest einem der Ansprüche 5 bis 9, bei dem die n-dimensionale Netzwerkübertragungssetzeinrichtung aufweist:

- eine Einrichtung zum Identifizieren für jeden integrierten Schaltkreis, diejenigen Prozessoren, die die nächsten Nachbarprozessoren darstellen, welche zum Übertragen von Daten an Prozessoren auf einem anderen integrierten Schaltkreis verwendet werden, und derjenigen Prozessoren, die die nächsten Nachbarprozessoren darstellen, welche zum Empfang von Daten von Prozessoren auf einem anderen integrierten Schaltkreis verwendet werden; und

- eine Einrichtung zum Setzen der identifizierten Prozessoren, um in entsprechender Weise Daten über das Verbindungsnetzwerk zu übertragen und zu empfangen.

11. Verfahren oder Parallelcomputer entsprechend zumindest einem der vorhergehenden Ansprüche, bei dem "m" 2 ist.