DE3751616T2

DE3751616T2 - Parallel-Grossrechner.

Info

Publication number: DE3751616T2
Application number: DE3751616T
Authority: DE
Inventors: Daniel W Hillis
Original assignee: Thinking Machines Corp
Current assignee: Thinking Machines Corp
Priority date: 1986-08-29
Filing date: 1987-05-20
Publication date: 1996-05-09
Anticipated expiration: 2007-05-21
Also published as: US5129077A; EP0262750B1; EP0262750A3; US5390336A; CA1293819C; EP0262750A2; WO1988001772A1; KR960012654B1; DE3751616D1; KR880003237A; CN1020972C; JPS63145567A; CN87106067A; JP2792649B2; IN170067B; US5978570A

Description

Die vorliegende Erfindung betrifft einen Parallelcomputer gemäß dem Oberbegriff des Patentanspruchs 1.
Ein derartiger Parallelcomputer ist aus EP-A-0 132 926 bekannt, welche Anmeldung dem US-Patent 4 498 400 entspricht, auf das im folgenden als '400-Patent Bezug genommen wird.
In der Fig. 1A des '400-Patents, welche als Fig. 1 wiedergegeben ist, sind ein Mainframe-Computer 10, ein Mikrocontroller 20, ein Feld von parallel verarbeiteten integrierten Schaltkreisen 35, eine Datenquelle 40, ein erster Puffer und ein Multiplexer/Demultiplexter 50, erste, zweite, dritte und vierte bidirektionale Bus-Steuerschaltkreise 60, 65, 70, 75, ein zweiter Puffer und Multiplexer/Demultiplexer 80 und eine Datensenke 90 gezeigt. Der Mainframe-Computer 10 kann ein geeignet programmierter, am Markt erhältlicher Computer, wie etwa eine VAX (TM), sein, wie sie von Digital Equipment Corporation hergestellt wird.
Der Mikrocontroller 20 ist ein Befehlssequenzer mit herkömmlichem Design zum Erzeugen einer Sequenz von Befehlen, die dem Feld 30 mittels eines 32 Bit-Parallelbusses 22 zugeführt werden. Der Mikrocontroller 20 empfängt von dem Feld 30 ein Signal auf der Leitung 26. Dieses Signal ist ein Allzweck- oder Global-Signal, das für den Datenausgang sowie für Steuerinformation verwendet werden kann. Der Bus 22 und die Leitung 26 sind parallel mit jedem IC 35 verbunden. Im Ergebnis werden die Signale vom Mikrocontroller 20 simultan jedem IC 35 des Feldes 30 zugeführt, 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 erreicht.
Das Feld 30 enthält Tausende identischer ICs 35. Jeder IC 35 enthält mehrere identische Prozessoren/Speicher 36. In der Ausführungsform, die in dem '400-Patent beschrieben ist, wird ein Feld mit bis zu 32.768 (=2¹&sup5;) identischer ICs 35 angegeben. Jeder IC 35 kann 32 (=2¹&sup5;) identische Prozessoren/Speicher 36 aufweisen. Zum Zeitpunkt der Einreichung vorliegender Patentanmeldung wurde ein System mit 4.096 (= 2¹²) identischen ICs 35, die jeweils 16 (=2&sup4;) identische Prozessoren/Speicher aufwiesen, von der Anmelderin gefertigt und unter dem Namen Connection Machine (TM) verkauft.
Die Prozessoren/Speicher 36 sind gemäß zwei Geometrieen organisiert und miteinander verbunden. Eine Geometrie stellt ein herkömmliches zweidimensionales Gittermuster dar, bei dem die Prozessoren/Speicher in einem rechtwinkeligen Feld organisiert und mit ihren vier nächsten Nachbarn in dem Feld verbunden sind. Vereinfachend werden die Seiten dieses Feldes mit Nord, Ost, Süd und West bezeichnet. Um jeden Prozessor/Speicher mit seinen vier nächsten Nachbarn zu verbinden, werden die individuellen Prozessoren/Speicher mittels elektrischer Leiter zwischen angrenzenden Prozessoren/Speichern in jeder Reihe und jeder Spalte des Gitters verbunden.
Die zweite Geometrie stellt einen Boolschen-N-Würfel mit 15 Dimensionen dar. Um das N-Würfel-Verbindungsmuster zu verstehen, ist es hilfreich, die Anzahl der ICs von 0 bis 32.767 durchzunumerieren und diese Nummern oder Adressen in Binärnotation unter Verwendung von 15 Binärstellen anzugeben. So wie die Position eines Objekts in einem zweidimensionalen Gitter durch zwei Nummern ausgedrückt werden kann, wobei eine die Position entlang einer ersten Dimension und die andere die Position entlang einer zweiten Dimension angibt, kann eine Nummer auch dazu verwendet werden, um die Position eines ICs in jeder der 15 Dimensionen eines Boolschen 15-Würfels zu beschreiben. In einem N-Würfel kann ein IC jedoch nur zwei unterschiedliche Positionen 0 und 1 in jeder Dimension aufweisen. Somit kann eine 15- stellige IC-Adresse in Binärnotation verwendet werden, um die Position des ICs in den 15 Dimensionen des N-Würfels anzugeben. Da eine Binärstelle nur zwei Werte aufweisen kann, 0 oder 1, und da jeder IC einmalig durch 15 Binärstellen identifiziert wird, hat jeder IC 15 andere ICs, deren Binäradressen sich nur in einer Stelle unterscheiden. Diese 15 ICs, deren Binäradresse sich nur um 1 von der eines ersten ICs unterscheiden, werden als die nächsten Nachbarn des ersten ICs bezeichnet. Für diejenigen, die sich mit der Definition der Hamming-Distanz auskennen, wird klar sein, daß der erste IC von den anderen 15 nächsten Nachbarn durch eine Hamming-Distanz 1 beabstandet ist.
Um die ICs 35 in Form eines Boolschen 15-Würfels zu verbinden, wird jeder IC mit den 15 nächsten Nachbarn durch 15 Eingangsleitungen 38 und 15 Ausgangsleitungen 39 verbunden. Jeder dieser 15 Eingangsleitungen 38 zu jedem IC 35 ist mit einer unterschiedlichen Dimension aus den 15 Dimensionen des Boolschen 15- Würfels assoziiert, und entsprechend ist jede der 15 Ausgangsleitungen 39 von jedem IC 35 mit einer unterschiedlichen Dimension assoziiert. Spezielle Details der Verbindungen bei dem Boolschen N-Würfel sind in der '237-Anmeldung beschrieben. Um eine Kommunikation durch das Verbindungsmuster des Boolschen 15-Würfels zu ermöglichen, werden die Ergebnisse der Berechnungen in Form von Nachrichtenpaketen organisiert. Diese Pakete werden von einem 10 zum nächsten über einen Weiterleitungsschaltkreis in jedem IC gemäß der Adreßinformation, die einen Teil des Pakets darstellt, weitergeleitet.
In der Fig. 7A des '400-Patents ist ein Prozessor/Speicher 36 im Detail beschrieben. Wie aus der Fig. 7A entnommen werden kann, besteht ein Prozessor/Speicher aus einem 32x12 Bit-RAM 250, einer Alu 280 und einem Flag-Controller 290. Die ALU arbeitet mit Daten von drei Quellen, zwei Registern in dem RAM und einem Flag-Eingang und erzeugt zwei Ausgänge, einen Summenausgang, der in eines der RAM-Register eingeschrieben wird, und einen Carry-Ausgang, der für gewisse Register in dem Flag- Controller sowie für bestimmte andere Prozessoren/Speicher verfügbar gemacht wird.
Die Eingänge zum RAM 250 sind die Adreßbusse 152, 154, 156, 158, eine Summenausgangsleitung 285 von der ALU 270, die Nachrichtenpaket-Eingangsleitung 122 von der CIU (180) der Fig. 6B des '400-Patents und eine WRITE ENABLE-Leitung 298 vom Flag- Controller 290. Die Ausgänge vom RAM 250 sind die Leitungen 256, 257. Die Signale auf den Leitungen 256, 257 werden von der gleichen Spalte von zwei unterschiedlichen Registern im RAM 250 erhalten, wobei eines das Register A und das andere das Register B ist. Die Busse 152, 154, 156, 158 adressieren diese Register und Spalten gemäß den Befehlswörtern von dem Mikro- Controller 20.
Die AlU 280 umfaßt einen Eins-Aus-Acht Decoder 282, einen Summenausgangsauswähler 284 und einen Carry-Ausgangsselektor 286. Wie im '400-Patent beschrieben, ermöglicht dies die Erzeugung von Summen- und Carry-Ausgängen für viele Funktionen einschließlich einer Addition, einer logischen ODER-Verknüpfung und einer logischen UND-Verknüpfung. Die ALU 280 arbeitet mit diesen drei Bits gleichzeitig, zwei auf der Leitung 256, 257 von den Registern A und B im RAM 250 und eine auf der Leitung 296 vom Flag-Controller 290. Die ALU weist zwei Ausgänge auf: eine Summe auf der Leitung 285, die in das Register A des RAMs 250 geschrieben wird und einen Carry-Ausgang auf der Leitung 287, der in ein Flag-Register 292 eingeschrieben wird und den Nord-, Ost-, Süd-, West- und Daisy-Eingängen anderer Prozessoren/Speicher 36, mit denen dieser Prozessor/Speicher verbunden ist. Die Signale auf der Carry-Leitung 287 können auch der CIU 180 über eine Nachrichtenpaketausgangsleitung 123 zugeführt werden.
Jeder integrierte Schaltkreis 35 enthält gewisse Überwachungsschaltkreise für die Prozessoren/Speicher auf dem IC und einen Weiterleitungsschaltkreis 200 zum Verbinden des ICs mit seinen nächsten Nachbar-ICs in dem Boolschen N-Würfel. Wie in dem '400-Patent beschrieben, enthält der Überwachungsschaltkreis einen Timing-Generator 140, eine PLA 150 zum Decodieren von Befehlen, wie sie von dem Mikrocontroller 20 empfangen werden und zum Bereitstellen der decodierten Befehle an die Prozessoren/Speicher des ICs und enthält weiterhin ein Kommunikationsinterface 180, welches den Fluß von ausgehenden und eingehenden Nachrichtenpaketen zwischen den Prozessoren/Speichern eines ICs und dem Weiterleitungsschaltkreis, der mit dem IC assoziiert ist, steuert.
Der Weiteleitungsschaltkreis 200 steuert die Weiterleitung von Nachrichtenpaketen von und zu den nächsten Nachbar-ICs in einem Boolschen N-Würfel. Durch diesen Schaltkreis können die Nachrichtenpakete von einem IC zu einem anderen IC in dem Boolschen N-Würfel weitergeleitet werden. Wie in Fig. 6B des '400-Patents gezeigt, enthält der Schaltkreis 200 einen Leitungszuweiser 205, einen Nachrichtendetektor 210, einen Puffer- und Adressenwiederhersteller 215 und einen Nachrichteneinfüger 220, die alle seriell in einer Schleife verbunden sind, so daß der Ausgang eines Elements dem Eingang des nächsten Elements zur Verfügung gestellt wird und der Augang des Nachrichteneinfügers 220 dem Leitungszuweiser 205 zugeführt wird. Der Leitungszuweiser 205 enthält ein 15x15 Feld von etwa identischen logischen Weiterleitungszellen 400. Jede Spalte dieses Feldes steuert den Nachrichtenpaketfluß zwischen einem nächsten Nachbarweiterleitungsschaltkreis 200 in einer Dimension des Boolschen 15-Würfels. Jede Reihe dieses Feldes steuert die Speicherung eines Nachrichtenpaktes im Weiterleitungsschaltkreis 200. Der Nachrichtendetektor 210 eines Weiterleitungsschaltkreises stellt die Nachrichtenpakete, die für die Prozessoren/Speicher, die mit diesem speziellen Weiterleitungsschaltkreis assoziiert sind, an eine CIU 180 zur Verfügung. Der Nachrichteneinfüger 220 fügt ein Nachrichtenpaket von der CIU 180 in eine Gruppe von Nachrichtenpaketen ein, welche in dem Weiterleitungsschaltkreis zirkulieren. Neun derartige logische Weiterleitungszellen 400 sind in Fig. 11 des '400-Patents verdeutlicht, wobei diese Figur als Fig. 2 im vorliegenden Patent wiedergegeben ist. Die drei Zellen in der linken Spalte sind mit der ersten Dimension assoziiert, die drei mittleren Spalten mit der zweiten Dimension und die drei rechten Spalten mit der fünfzehnten Dimension. Jede Spalte von Zellen weist einen Ausgangsbus 410 auf, der mit einer Ausgangsleitung 39, die mit dieser Dimension assoziiert ist, verbunden ist. Bezüglich der Reihen sind die drei Zellen in der untersten Reihe die tiefsten Zellen des Feldes und empfangen Eingänge von den Eingangsleitungen 38. Die oberen drei Zellen sind die obersten Zellen des Feldes. Die mittleren drei Zellen sind repräsentativ für alle Zellen zwischen den unteren und oberen Zellen und sind, wie gezeigt, mit der untersten Reihe verbunden.
Wie weiter in Fig. 2 gezeigt ist, sind drei Verarbeitungs- und Speichereinrichtungen 420 vorhanden, welche Teile des Nachrichtendetektors 210, des Puffer- und Adreßwiederherstellers 215 und des Nachrichteneinfügers 220 des Weiterleitungsschaltkreises 200, welcher Nachrichten von entsprechenden drei Reihen der Zellen 400 im Leitungszuweiser 205 verarbeitet und speichert, darstellen. Zwölf ähnliche Verarbeitungs- und Speichereinrichtungen (nicht gezeigt) werden verwendet, um Nachrichten von anderen Reihen zu verarbeiten und zu speichern.
Wenn kein Weiterleitungskonflikt auftritt, wird ein Nachrichtenpaket von einem Eingang an eine Weiterleitungszelle der ersten Dimension zum Register in dem Prozessor/Speicher, für den es adressiert ist, während eines einzigen Nachrichtenzyklusses weitergegeben. Wenn Weiterleitungskonflikte auftreten, wird das Nachrichtenpaket zwischenzeitlich in der Verarbeitungs- und Speichereinrichtung eines Weiterleitungsschaltkreises an einem oder mehreren dazwischenliegenden Punkten gespeichert. Somit wird mehr als ein Weiterleitungszyklus benötigt, um das Nachrichtenpaket zu seinem Ziel weiterzuleiten.
Die Fig. 2 zeigt eine Zusammenfassung der Ein- und Ausgangsanschlüsse einer jeden Weiterleitungszelle 400. Wie durch die drei Zellen 400 entlang der untersten Reihe angedeutet, werden die Nachrichtenpakete von unterschiedlichen Dimensionen des Boolschen 15-Würfels NAND-Gattern 405 zugeführt. Diese Gatter sind stets aktiv, mit Ausnahme während des Reset-Zustandes. Der Ausgang eines jeden NAND-Gatters 405, welcher das invertierte Nachrichtenpaket darstellt, wird dem Eingangsanschluß L-in einer der Zellen 400 in der untersten Reihe zugeführt. Ein Signal, das das Vorhandensein eines Nachrichtenpakets am Anschluß L-in andeutet, wird einem Eingangsanschluß LP-in derselben Zelle zugeführt. Für jede Zelle in der untersten Reihe wird das Nachrichten-Vorhanden-Signal auf Masse gehalten, was dazu führt, daß die Zelle in der nächsten Spalte in der untersten Reihe für die weitere Verarbeitung eines Nachrichtenpakets, welches an der Zelle empfangen wird, vorbereitet wird. Derartige Nachrichten-Vorhanden-Signale, die das Vorhandensein eines Nachrichtenpakets am Eingang der Zelle darstellen, werden im gesamten Weiterleitungsschaltkreis 200 verwendet, um Datenpfade durch den Schaltkreis 200 für die Nachrichtenpakete zur Verfügung zu stellen.
Ein Nachrichtenpaket, das an einer Leitung 38 empfangen wird, wird aus der untesten Zelle 400 in eine Spalte von dem Anschluß M-OUT weitergeleitet und wird dem Anschluß M-IN der Zelle 400 in der Spalte unmittelbar rechts daneben zugeführt. Zur gleichen Zeit wird das Nachrichten-Vorhanden-Signal von dem Anschluß MP-OUT zu dem Anschluß MP-IN der Zelle unmittelbar rechts daneben weitergeleitet.
Das am M-IN-Anschluß einer Zelle 400 empfangene Signal kann aus der Zelle entweder über den Bus-Anschluß, den U-OUT-Anschluß oder den M-OUT-Anschluß herausgeleitet werden, jeweils abhängig vom Signalzustand anderer Signale in dem Netzwerk. Die Bus- Anschlüsse aller Zellen 400 in einer Spalte sind mit einem gemeinsamen Ausgangsbus 410 verbunden, welcher über ein NOR- Gatter 415 mit der Ausgangsleitung 39 der nächsten Nachbarzelle in der Dimension des Boolschen N-Würfels verbunden ist. Der andere Eingang zum NOR-Gatter 415 stellt ein Timing-Signal T-INV- OUT-n dar, wobei n die Anzahl der Dimension ist. Dieses Timing- Signal komplementiert das geeignete Adreßbit in der duplizierten Adresse in dem Nachrichtenpaket, so daß diese Adresse erneuert wird, wenn sich das Nachrichtenpaket durch den Boolschen 15-Würfel bewegt.
Nachrichten, die die Zelle vom U-Aus-Anschluß verlassen, werden dem L-Ein-Anschluß der unmittelbar darüber und in der gleichen Spalte liegenden Zelle zugeführt und durch diese Zelle in gleicher Weise verarbeitet, wie ein Signal, welches auf einem L- Ein-Anschluß empfangen wird. Das Nachricht-Vorhanden-Signal wird in gleicher Weise von einem UP-Aus-Anschluß zu einem LP- Ein-Anschluß der unmittelbar darüberliegenden Zelle transferiert.
Der Schaltkreis in den Zellen 400 jeder Spalte ist ausgelegt, um auf einen Ausgangs-Bus 410 jeder Spalte (oder Dimension) die Nachricht zu placieren, die für die Dimension adressiert ist, die in der zur Spitze nächstliegenden Reihe zirkulieren und um alle Reihen bis zur obersten Reihe zusammenzufassen. Die Steuersignale Grant (G) und "alles voll" (AF) werden jeder Spalte zugeführt, um die individuellen Zellen der Spalte über den Status der Zellen zu informieren, die in der Spalte über ihnen angeordnet sind. Insbesondere steuert das Grant-Signal den Zugriff auf den Ausgangsbus 410 einer jeden Spalte oder Dimension durch ein Signal, welches in jeder Spalte der Zellen durch die G-Ein- und G-Aus-Anschlüsse zugeführt wird. Der Schaltkreis, der diese Signal weitergibt, gibt den Buszugriff an das höchste Nachrichtenpaket in der Spalte, das für diese Dimension adressiert ist und verhindert, daß Nachrichten in tieferen Zellen in der Spalte auf den Ausgangsbus weitergleitet werden. Das AF-Signal steuert den Transfer von Nachrichten von einer Zelle 400 zur Zelle darüber in der gleichen Spalte, indem jeder Zelle durch die AF-Aus- und AF-Ein-Anschlüsse mitgeteilt wird, ob Nachrichten in jeder darüberliegenden Zelle der Spalte vorhanden sind. Wenn eine der darüberliegenden Zellen leer ist, wird die Nachricht in jeder tieferen Zelle um eine Zelle in der Spalte nach oben bewegt.
Für die Zellen in der obersten Reihe ist der Eingang an den Anschluß immer "high". Für diese Zellen stellt das Eingangssignal zum G-Ein-Anschluß das Kompliment des Rücksetz-Signals dar und ist daher stets "high", außer beim Reset. Im Ergebnis wird das Nachrichtenpaket in der obersten Zelle einer Spalte normalerweise auf den Ausgangsbus 410 ausgegeben, falls es für diese Dimension vorgesehen ist. Wenn jedoch eine Ausgangsleitung 39 fehlerhaft ist, wird diese Leitung aus der 15-Würfel-Netzwerkverbindung dadurch entfernt, daß ein "low"-Signal dem G-Ein- Eingangsanschluß der obersten Zelle der Dimension, die mit dieser Leitung assoziiert ist, zugeführt wird. Bei der untersten Reihe der Zellen 400 wird das Grant-Signal von dem G-Aus- Anschluß verwendet, um einen Weiterleitungstransistor 425 zu steuern, welcher den Ausgangsbus auf Masse schalten kann. Insbesondere können, falls keine Nachricht auf der Ausgangsleitung weitergeleitet werden soll, Null-Bits auf die Ausgangsleitungen dieser Dimension geschrieben werden.
Der Betrieb bestimmter Flip-Flops in der Zelle wird durch die Timing-Signale T-COL-n gesteuert, wobei n die Anzahl der Dimension ist, während andere Flip-Flops durch das Basistaktsignal phi 1 getaktet werden. Wie für den Fachmann klar sein wird, arbeiten die Weiterleitungszellen jeder Spalte synchron mit allen anderen Weiterleitungszellen in der gleichen Spalte des Weiterleitungsschaltkreises im Feld 30.
Die Verwendung Tausender identischer Prozessoren/Speicher, die parallel zueinander arbeiten, ermöglicht neue Dimensionen in der Computertechnik. Probleme, die bisher nicht angegangen werden konnten, können nun in vernünftigen Zeitperioden unter Verwendung eines Parallelcomputers, wie beispielsweise dem Connection-Machine-Computer, gelöst werden.
Der erhebliche Anstieg in der Rechenleistung hat das Interesse für noch kompliziertere Probleme, als sie mit bisher bekannten Parallelcomputern gelöst werden können, geweckt und hat somit ein Bedürfnis nach noch größeren Parallelcomputern hervorgerufen. Gleichzeitig sind extrem große Computer nicht für jedes Problem erforderlich, welches vorteilhafterweise durch einen Parallelcomputer gelöst werden kann. Einige Probleme benötigen einfach nicht genügend Daten, um alle Möglichkeiten eines großen Parallelcomputers auszuschöpfen. Andere Probleme erfordern keine besonders hohen Rechenleistungen. Wenn kein Weg gefunden werden kann, um auch nur Teile des Parallelcomputers verwenden zu können, ist es sehr schwierig, einen derartigen Computer aus ökonomischen Gründen rechtfertigen zu können.
Ein Kompromiß in dieser Hinsicht besteht darin, zusätzliche Parallelprozessoren mittels weicher Kapazität zu simulieren, wie dies in EP-A-0 237 218 beschrieben ist. Gemäß dieser Technik wird der Speicher, der mit jedem physikalischen Prozessor assoziiert ist, in eine Vielzahl von Unterspeicher unterteilt, und jeder Unterspeicher kann dann so verwendet werden, als ob er mit einem eigenen Prozessor assoziiert wäre. Somit wird, wenn ein erster Befehl oder ein Satz von Befehlen an alle Prozessoren des Parallelcomputers zur Verfügung gestellt werden, um zu bewirken, daß zumindest einige Prozessoren Daten verarbeiten, die an ersten Stellen des ersten Unterspeichers gespeichert sind.? Danach wird der gleiche erste Befehl oder Satz von Befehlen allen Prozessoren des Computers zur Verfügung gestellt, um zu bewirken, daß zumindest einige Prozessoren Daten verarbeiten, die an der gleichen ersten Stelle in einem zweiten Unterspeicher gespeichert sind usw. Obwohl diese Technik für viele Situationen brauchbar ist, ist der eigentliche physikalische Prozessor, der die Daten für jede Gruppe von simulierten Prozessoren verarbeitet, selbst eine herkömmliche von Neumann- Maschine. Im Ergebnis werden, falls eine große Anzahl von simulierten Prozessoren und/oder eine große Anzahl von Daten mit dem physikalischen Prozessor assoziiert sind, die bei von Neumann erschienen üblichen Probleme bei den physikalischen Prozessor auftreten.
Es ist die Aufgabe der vorliegenden Erfindung, einen Parallelcomputer anzugeben, dessen Resourcen besser genutzt werden können.
Diese Aufgab wird durch den Gegenstand des Patentanpsruchs 1 gelöst.
Weiterhin ist der Parallelcomputer so organisiert, daß er die Simulation zusätzlicher paralleler Prozessoren zuläßt, wie dies in EP-A-0 237 218 beschrieben ist. Dies gilt für jeden physikalischen Prozessor in dem Feld, um somit eine Kommunikation zwischen den simulierten Parallelprozessorn zu erreichen. Gemäß der Erfindung ist es nicht nur möglich, daß siumulierte Porzessoren mit einem speziellen physikalischen Prozessor, mit dem sie assoziiert sind, kommunizieren können, sondern es ist auch möglich, daß jeder simulierte Prozessor mit jedem anderen simulierten Prozessor, der mit einem anderen physikalischen Prozessor des Parallelcomputers assoziiert ist, kommuniziert. Analog zum Konzept der virtuellen Speicherung werden diese simulierten Prozessoren als virtuelle Prozessoren bezeichnet. Gemäß der Erfindung sind weiterhin Einrichtungen vorgesehen zum Speichern der virtuellen Prozessoren im virtuellen Speicher.
Mit dem angegebenen Design ist es möglich, Parallelcomputer mit einer Anzahl von physikalischen Prozessoren im Bereich von 1.000.000 und einer Anzahl von virtuellen Prozessoren in einer Größenordnung von 1.000.000.000.000 zu bauen. Da der Computer dynamisch rekonfiguriert werden kann in eine Vielzahl unabhängiger Prozessorfelder, kann eine Einrichtung dieser Größe durch eine große Anzahl von Benutzern geteilt verwendet werden, wobei jeder Benutzer nur einen Teil des gesamten Computers, jeweils mit einer Kapazität, die für sein eigenes Problem geeignet ist, verwendet. Insbesonder können etwa 1000 Benutzer den Parallelcomputer mittels eines LANs verwenden.
Um eine Kommunikation zwischen den Prozessoren zu ermöglichen, sind die physikalischen Prozessoren untereinander in Form eines binären n-Würfels mit ausreichender Größe verbunden, um jedem physikalischen Prozessor einen einmaligen Platz in dem Würfel und jedem virtuellen Prozessor seine eigene Adresse zuzuweisen. Die Adressierungsstruktur erlaubt es, bis zu 240 virtuelle Prozessoren zu adressieren.
Andere Merkmale des Parallelcomputers gemäß der vorliegenden Erfindung sind die folgenden:
Der Computer untestützt einen normalen Wort-Pro-Zeitbefehlssatz. Zusätzlich unterstützt er einen exakten isomorphen Satz paralleler Befehle. Für jede Wort-Pro-Zeit-Operation wird der gesamte Datensatz parallel verarbeitet.
Der Computer stellt eine Hardware-Unterstützung für die Verteilung und synchrone Ausführung der Befehle über die vielen Prozessoren zur Verfügung. Im Ergebnis werden Operationen über die Maschine in vollständig vorbestimmten Zeiten zueinander ausgeführt.
Ein Benuter kann soviel Redundanz wie notwendig zuweisen, um genügend Sicherheit für wichtige Transaktionen zu haben. Dies kann eine einfache Selbstüberprüfung bei nicht kritischen Anwendungen bis hin zu einer vollständigen vierfachen modularen Redundanz für kritische Transaktionen umfassen. Da die redundanten Elemente nur dann zugewiesen sind, wenn dies notwendig ist, treten die Kosten für die Redundanz nur dann auf, wenn Redundanz gewünscht ist.

Kurze Beschreibung der Zeichnungen

Diese und andere Merkmale und Vorteile der Erfindung werden durch die folgende Beschreibung und unter Bezugnahme auf die beiliegenden Figuren näher erläutert. Dabei zeigen die Figuren im einzelnen:
Fig. 1 zeigt ein schematisches Schaltbild eines Parallelprozessors gemäß dem Stand der Technik;
Fig. 2 zeigt ein schematisches Schaltbild eines Weiterleitungsschaltkreises des Parallelprozessors der Fig. 1;
Fig. 3 zeigt ein allgemeines schematisches Schaltbild einer bevorzugten Ausführungsform der Erfindung;
Fig. 4 zeigt ein schematisches Schaltbild einer Prozessoreinheit gemäß der vorliegenden Erfindung;
Die Fig. 5 und 6 zeigen schematische Beispiele zum Darstellen der Organisation der Prozessoreinheiten der Fig. 4 in einem Feld von parallelen Prozessoren;
Fig. 7 zeigt ein detailliertes schematisches Schaltbild zum Erläutern eines Elements der Prozessoreinheit der Fig. 4;
Die Fig. 8 bis 12 zeigen detaillierte schematische Schaltbilder der Elemente der Fig. 7;
Fig. 13 zeigt eine Illustration des Adressierungsschemas für eine bevorzugte Ausführungsform der Erfindung; und
Fig. 14 zeigt eine schematische Darstellung, die zum Vestehen eines Teils der Erfindung nützlich ist.

Detaillierte Beschreibung einer bevorzugten Ausführungsform

Wie in Fig. 3 gezeigt ist, stellt die bevorzugte Ausführungsform der vorliegenden Erfindung ein System 300 dar, welches eine Vielzahl von Benutzerterminals 310 A bis N, ein LAN 320 und ein Prozessorfeld 330 umfaßt. Beispielhaft enthält jedes Terminal eine Konsole 312 mit einem Tastenfeld 314 und einen Anzeigemonitor 316, eine bestimmte Art von Druckern (nicht gezeigt) und ein Interface 318 zwischen dem Terminal und dem LAN 320. Herkömmliche PCs können für die Terminals 310 verwendet werden.
Das Prozessorfeld 330 umfaßt beispielhaft 262.144 (= 2¹&sup8;) physikalische Prozessoreinheiten (PPU), vier Megabytes RAM für jeden Prozessor, einen langsameren Massenspeicher und umfangreiche Schaltkreisanordnungen. Das Terabyte für den Hochgeschwindigkeitsspeicher wird typischerweise durch integrierte Speicherchips zur Verfügung gestellt. Der Massenspeicher kann beispielsweise aus 32.768 (=2¹&sup5;) Festplattenspeichern bestehen, wobei jede Platte eine Kapazität von 300 Megabytes aufweist, was zusammen 10 Terabyte ergibt. Die 262.144 PPUs sind über einen achtzehndimensionalen Hyper-Würfel miteinander verbunden, wobei jede PPU entlang seiner 18 Kanten des Hyperwürfels mit 18 angrenzenden PPUs verbunden ist, wie dies im folgenden im Detail beschrieben wird.
Das LAN 320 verbindet die Terminals 310 mit einigen der PPUs in dem Prozessorfeld 330, so daß ein bestimmter Terminal mit einer bestimmten PPU kommunizieren kann. Die PPUs steuern dynamisch andere PPUs des Feldes, und andere PPUs können wiederum andere PPUs steuern, so daß eine geeignete Verarbeitung und ein geeigneter Speicher für ein bestimmtes Problem zur Verfügung gestellt wird. Vorzugsweise ist das LAN wie ein Cross-Bar- Schalter flexibel konfigurierbar, so daß jeder Terminal mit jeder beliebigen PPU des Netzwerks verbunden werden kann und daß diese Verbindungen verändert werden können, falls dies in einer Zeitteilungsumgebung notwendig ist. Ein beliebiges herkömmliches LAN kann verwendet werden, wie beispielsweise das Ethernet-System oder eine digitale PBX, soweit dadurch eine ausreichend große Kapazität zur Verfügung gestellt wird, um die Anzahl der Terminals, wie sie in dem System 300 vorhanden sind, zu verbinden. Eine Vielzahl von LANs kann verwendet werden, falls dies gewünscht ist. Beispielsweise sollte das LAN in der Lage sein, tausend Terminals zu verbinden.
Es sollte klar sein, daß die Vorrichtung mit der vorliegenden Erfindung wesentlich größere Anzahlen von RAMs unterstützen kann, als bei einer herkömmlichen Maschine. Dies erlaubt es, gesamte Datenbanken in dem Hauptspeicher zu speichern, so daß die Zugriffszeit um das 1.000-fache höher ist als bei Platten. Hauptspeicher im Terabyte-Bereich sind üblicherweise nicht ökonomisch, da ein großer Speicher zu groß ist, um ungenützt zu sein, wenn ein einzelner Benutzer die Maschine bedient. Dieses Problem tritt bei der vorliegenden Erfindung nicht auf, da der Speicher an mehreren Stellen gleichzeitig benutzt werden kann.
Jede PPU kann als Mehrzahl von virtuellen Prozessoren betrieben werden, indem der Speicher, der mit der PPU assoziiert ist, unterteilt wird und indem jedem Unterspeicher ein unterschiedlicher virtueller Prozessor zugewiesen wird. Gemäß der vorliegenden Erfindung kann die Unterteilung des Speichers sich auch auf den virtuellen Speicher erstrecken, wie beispielsweise auf eine Festplatte oder einen Bandspeicher. Jeder virtuelle Prozessor kann als äquivalent zu einem physikalischen Prozessor betrachtet werden.
Gemäß der vorliegenden Erfindung kann der Benutzer einer PPU seine Erfordernisse hinsichtlich Datenverarbeitung und Speicherbedarf zuweisen, und die PPU kann dann eine Gruppe von Prozessoren bilden (sowohl physikalische Prozessoren als auch virtuelle Prozessoren), die ausreichend sind, um diesen Anforderungen zu genügen. Die Gruppe von Prozessoren kann rekursiv organisiert sein, so daß ein Prozessor einen oder mehrere andere Prozessoren steuert und diese anderen Prozessoren wiederum andere Prozessoren steuern.
Vorzugsweise ist jedes Element der Datenbank in einem Eins- Zu-Eins -Verhältnis mit einem der Porzessoren gespeichert, und die Prozessoren sind in gleicher Weise strukturiert wie die Datenbank. Als Ergebnis dieser Anordnung gilt folgendes:
1. Jeder Prozessor ist in der Lage, normale von-Neumann- Operationen einschließlich arithmetischer/logischer Operationen, Datenbewegungen und normale Operationssteuerungen, wie etwa Unterroutinenaufrufe und Verzweigungen, auszuführen.
2. Jeder Prozessor ist in der Lage, einen Satz von Datenprozessoren zuzuweisen, welche während der parallelen Befehlsausführung unter seiner Steuerung sind. Der zuweisende Prozessor wird der Steuerprozessor genannt, und die zugewiesenen Prozessoren werden Datenprozessoren genannt. Dies sind jedoch nur relative Ausdrücke, da Datenprozessoren die Fähigkeit aufweisen, als Steuerprozessoren zu fungieren.
3. Jeder Prozessor ist in der Lage, einen Satz aus den zugewiesenen Datenprozessoren auszuwählen. Dieser ausgewählte Satz betrifft die parallel zu verarbeitenden Daten. Der ausgewählte Satz wird entsprechend einer Bedingung ausgewählt, die allen Datenprozessoren zugewiesen wird. Die Sätze können gespeichert werden.
4. Jeder Prozessor kann parallele Operationen gleichzeitig für alle Daten des Satzes durchführen. Die parallelen Operationen sind genau die gleichen wie die sequentiellen Operationen unter Punkt 1, mit der Ausnahme, daß sie allen Daten des Satzes gleichzeitig zugeführt werden. Dies schließt alle Datenmanipulationen, Speicheroperationen und Steueroperationen mit ein. Für den Programmierer erscheinen die Operationen gleichzeitig auf allen Prozessoren des Datensatzes abzulaufen.
5. Jeder Prozessor ist in der Lage, auf die geteilte Datenbank zuzugreifen und Teile davon in seinen Speicher zu laden. Ein virtueller Prozessor ist in der Lage, die Datenbanken neu zu beschreiben.
Die Befehle des Parallelcomputers der vorliegenden Erfindung sind ähnlich wie die Befehle bei einem herkömmlichen Computer. Sie können in drei Kategorien eingeteilt werden: lokale Befehle, parallele Befehle und Context-Befehle.
Die lokalen Befehle sind genau die Befehle eines herkömmlichen Computers einschließlich Unterroutineaufrufe, bedingte und nicht bedingte Verzweigungen, Returns, registerbasierende arithmetische Datenbewegungen, logische Operationen und Testoperationen. Die lokalen Instruktionen werden innerhalb des Steuerprozessors ausgeführt.
Die Parallelbefehle sind gleich den lokalen Befehlen mit der Ausnahme, daß sie gleichzeitig auf dem Context-Satz von Datenprozessoren ausgeführt werden. Gruppen von parallelen Instruktionen, die als Orders bezeichnet werden, werden auf allen virtuellen Datenprozessoren des Context-Satzes gleichzeitig ausgeführt. Für jeden lokalen Datenbefehl gibt es einen korrespondierenden parallelen Datenbefehl.
Die Context-Befehle werden verwendet, um den Satz virtueller Datenprozessoren zu spezifizieren, welcher parallel betrieben werden soll. Es gibt vier Context-Befehle:
weise dem Context alle virtuellen Prozessoren zu, die einer bestimmen Bedingung genügen;
begrenze den Context auf einen Untercontext von Prozessoren innerhalb des momentanen Contextes, welche einer Bedingung genügen;
schiebe den momentanen Context auf einen Stack;
hole den momentanen Context von dem Stack.
Diese Context-Befehle können mit parallelen Datenbefehlen in Gruppen gemischt werden, um Orders zu bilden.
Die Order ist die Grundeinheit der Synchronisation in dem Parallelcomputer der vorliegenden Erfindung. Eine Order ist die Einheit einer Kommunikation zwischen einem Steuerprozessor und einem Datenprozessor. Im einfachsten Fall besteht eine Order aus einem einzelnen Befehl. Sie kann jedoch auch aus einer Gruppe von Befehlen bestehen, die miteinander ausgeführt werden können, ohne die Synchronisation der Datenprozessoren zu beeinflussen. Die Basisaktion eines Steuerprozessors ist es, eine Order durch den Alpha-Weiterleiter(Fig. 7) auszugeben und auf eine Bestätigung zu warten, daß die Order durch alle Datenprozessoren ausgeführt wurde. Unterschiedliche virtuelle Prozessoren können und werden im allgemeinen verschiedene Befehle innerhalb der Order zu unterschiedlichen Zeiten ausführen.
Eine Order ist auch die Basiseinheit für das Caching für Befehle in dem System. Das bedeutet, daß die Anzahl der Befehle für eine Order begrenzt ist. Da eine Order einen Rufbefehl enthalten kann, ist die Anzahl der durch eine Order ausgeführten Operationen beliebig groß. Zusätzlich zu Unterroutineaufrufen kann eine Order einfache Schleifen und bedingte Verzweigungen innerhalb der Order enthalten. Befehle sind in Order gemäß einfachen Regeln gruppiert, wobei die Regeln sicherstellen, daß die Befehle innerhalb der Order asynchron ausgeführt werden können. Dies kann beispielsweise dadurch erreicht werden, daß Befehle, die nicht lokale Kommunikation erfordern, nur als letzte Instruktion einer Order ausgeführt werden.
Order werden von Steuerprozessoren zu Datenprozessoren durch den Alpha-Weiterleiter ausgestrahlt. Es liegt in der Zuständigkeit des Alpha-Weiterleiters, den Steuerprozessor zu benachrichtigen, wenn die Order durch alle Datenprozessoren ausgeführt wurde. Dieser Benachrichtigungsmechanismus wird auch verwendet, um Bedingungscodes für die Steuerung eines Programmflusses innerhalb des Steuerprozessors zu kombinieren.
Wie in dem schematischen Schaltbild der Fig. 4 gezeigt ist, enthält jede PPU einen Mikroprozessor 350, einen Funktionsschaltkreis 360 und einen Speicher 370. Zusätzlich kann die PPU auch einen speziellen mathematischen Schaltkreis aufweisen, um mathematische Operationen mit hoher Geschwindigkeit ausführen zu können. Der Mikroprozessor 350, der Speicher 370 und der mathematische Schaltkreis 380 können herkömmliche integrierte Schaltkreise sein. Beispielsweise kann der Mikroprozessor 350 ein Intel 8086-Prozessor sein und der mathematische Schaltkreis 380 kann ein Fließpunkt-Accelerator sein, wie beispielsweise der Intel-Chip 8087. Alternativ kann der Motorola-Chip 68000 verwendet werden und Mikroprozessoren, wie beispielsweise der Fairchild Clipper, sind besonders geeignet, da sie separierte Befehls- und Datenpins aufweisen.
Der Speicher 370 kann ein beliebiger Schreib/Lese-Speicher mit hoher Geschwindigkeit und hoher Kapazität sein. Beispielweise kann der Speicher aus einem Viermegabyte-Speicher bestehen, wobei das Feld aus zweiunddreißig 4x64 Kilobit Schaltkreisen bestehen kann. Zusätzlicher Speicher wird verwendet, um Paritäts- und Fehlersteuerbits zur Fehlerdetektion und Korrektur zu speichern. Mit zunehmender Kapazität der Speicherchips kann der Speicherplatz vergrößert und/oder die Anzahl der integrierten Schaltkreischips verringert werden.
Der Funktionsschaltkreis 360 ist verantwortlich für Speicherinterface-Operationen, Nachrichtenweiterleitung, Fehlerkorrektur, Befehlsverteilung und Synchronisation, Daten-Caching und Steuerung virtuelller Prozessoren. Dieser Schaltkreis empfängt Information von der PPU und erzeugt Adreßinformation, die geeignet ist, um die dynamischen Speicher zu betreiben. Weiterhin bewegt er Daten zu und von den Datenpins der PPU und den Datenpins des dynamischen Speichers. Der Funktionsschaltkreis führt auch alle Management-Funktionen durch, die notwendig sind, um die PPU als virtuellen Prozessor zu betreiben. Diese Organisation des Mikroprozessors 350, des Funktionsschaltkreises 360 und des Speichers 370 ist so organisiert, daß der Funktionsschaltkreis 360 zwischen dem Mikroprozessor 350 und dem Speicher 370 angeordnet ist, wodurch ermöglicht wird, daß der Mikroprozessor eine größere Anzahl von Speichern adressiert, als dies bei dem System in dem '400-Patent der Fall ist, wo der Mikroprozessor und der Speicher jeweils miteinander direkt verbunden sind. Die vorliegende Organisation ermöglicht auch das Weiterleiten eines Nachrichtenpaketes, wie dies im folgenden beschrieben wird.
Die PPUs sind in Einheiten von 16 organisiert, so daß die integrierten Schaltkreise von sechzehn PPUs 0-15 und der Unterstützungsschaltkreis auf einer einzigen Platine 400 montiert sind, wie dies in Fig. 5 gezeigt ist. Der Unterstützungsschaltkreis enthält ein Platten-Interface 410, einen allgemeinen Ein/Aus- Schaltkreis 420, einen Selbstüberprüfungsschaltkreis 430, einen Taktschaltkreis 440, einen Identifikationsschaltkreis 450 und einen Ausführungsmeßschaltkreis 460.
Das Platteninterface 410 besteht aus einem Standard SCSI (small computer system interface), welches mit der PPU 0 verbunden ist. Es ist so ausgelegt, daß es ein Massenspeichermodul 470 verbinden kann. Die maximale Kommunikationsbandbreite ist etwa 10 Megabit pro Sekunde. Die anderen PPUs der Platine 400 stehen mit dem Massenspeichermodul über die PPU 0 in Verbindung, welcher als File-Server dient.
Der Eingangs/Ausgangsschaltkreis 420 besteht aus einm 32-Bit- Parallel-Port oder Serial-Port, der mit der PPU 1 verbunden ist. Dieser Port weist eine maximale Bandbreite von etwa 50 Megabit pro Sekunde auf. Der Schaltkreis 420 verbindet das LAN 320 mit der PPU 1, welche in dem Netzwerk als weiterer Terminal oder einfach als paralleler oder serieller Port auftaucht. Die andern PPUs der Platine 400 stehen mit den Eingangs/Ausgangs- Schaltkreis 420 über die PPU 1 in Verbindung. Als Ergebnis dieser Anordnung kann ein Benutzer an irgendeinem Terminal 310 A-N jede beliebige PPU in dem Prozessorfeld 330 adressieren, ähnlich, wie ein Benutzer mit jedem beliebigen Telefon, das mit einem Telefonnetzwerk verbunden ist, kommunizieren kann.
Der Selbstüberprüfungsschaltkreis 430 ist in der Lage, jegliche Fehler zu erkennen, die auf der Platine 400 auftreten, so daß das Modul von dem System entfernt werden kann. Vorteilhafterweise ist der Schaltkreis mit einer LED verbunden, welche eine sichtbare Anzeige liefert, daß das Modul nicht funktioniert, um die Wartung zu unterstützen. Jede Platine enthält ihren eigenen Taktschaltkreis 440, welcher mit dem Taktschaltkreis der anderen PPUs des Systems synchronisiert ist. Der Identifikationsschaltkreis 450 stellt einen elektrisch löschbaren, nicht flüchtigen Speicher dar, der die Herstellungs- und Wartungsinformation der Platine enthält und außerdem die Seriennummer etc. enthält. Der Betriebsmeßschaltkreis 460 überwacht die Softwareausführung.
Das Massenspeichermodul 470 besteht beispielsweise aus einem herkömmlichen Platten-Controller 480 und einem 5-1/4-inch 300- Megabyte Laufwerk 490, wobei Vorkehrungen getroffen sind, daß bis zu sieben zusätzliche Laufwerke an denselben Controller angeschlossen werden können, so daß insgesamt eine Kapazität von 2400-Megabyte erreicht werden kann.
Die Platinen 400 und die Speichermodule 470 sind in einem Gehäuse 500 montiert, wobei das Gehäuse Banken 502 für sechzehn Platinen 400 und sechzehn Module 470 aufweist. Somit werden im Fall eines Systems mit 262144 PPUs, 1024 (= 2¹&sup0;) Gehäuse verwendet, um die PPUs darin unterzubringen. Die Gehäuse sind miteinander über Glasfaserkommunikationsleitungen verbunden. Jedes Gehäuse enthält ein oder mehrere Kommunikationsmodule 505, welche jeweils mindestens eine Glasfasersende-/Empfangseinrichtung enthalten, welche verwendet wird, um Übertragungsdaten zwischen den Gehäusen zu multiplexen. Die Sende/Empfangseinrichtungen können herkömmliche Glasfaser-Sende/Empfangseinrichtungen mit Datenraten von 100 Megabit pro Sekunde sein und können in der Lage sein, eine Kommunikation in Zeitmultiplex mit verschiedenen PPUs in einem Gehäuse mit solchen von anderen Gehäusen auszuführen und somit die Vorteile der erhöhten Bandbreite von Glasfaserkommunikationsleitungen auszunutzen. Vorteilhafterweise werden zumindest zwei Sende/Empfangseinrichtungen in jedem Kommunikationsmodul verwendet, so daß die Signale gleichzeitig an jedem Kommunikationsmodul übertragen und empfangen werden können.
Die PPUs 330 sind vorzugsweise in einem Hyper-Würfel gemäß der Lehre der oben angegebenen EP-A-0206584 miteinander verbunden. Somit ist jede PPU in dem Würfel-Netzwerk mit vier anderen PPUs auf der gleichen Platine entsprechend vier Dimensionen des Hyper-Würfels verbunden und weiterhin mit vier PPUs auf vier anderen Platinen in einem Gehäuse entsprechend den vier weiteren Dimensionen des Hyperwürfels verbunden. Im Falle eines Systems mit 262144 PPUs, ist jede PPU in dem Gehäuse mit zehn PPUs in unterschiedlichen Gehäusen verbunden. Diese anderen zehn Verbindungen entsprechen den zehn verbleibenden Dimensionen des Hyper-Würfels. Die Verbindungen jedes Gehäuses über diese zehn Dimensionen wird über ein separates Kommunikationsmodul 505 hergestellt.
Wie in Figur 7 gezeigt ist, enthält der Funktionsschaltkreis 9 größe funktionale Einheiten: Einen Adreß-Abbilder 510, ein Speicherinterface 520, einen virtuellen Prozessor Sequenzer 530, einen Daten-Cache 540, einen Fehlerkorrigierer 550, einen Alpha-Weiterleiter 560, einen Beta-Weiterleiter 570, einen Abschneider 580, und einen Order-Cache 590. Alle diese funktionalen Einheiten sind in einem einzelnen Chip implementiert oder es können auch mehrere Chips dafür verwendet werden. Die Adreßpins 532 und die Datenpins 582 verbinden den VP-Sequenzer 530 und den Abschneider 580 mit dem Mikroprozessor 350 der PPU. Die Adreßpins 522 und die Datenpins 552 verbinden das Speicherinterf ace 520 und den Fehlerkorrigierer 550 mit dem Speicher 370 der PPU. Die Alpha-Pins 562 und die Würfel-Pins 572 verbinden den Alpha- und Beta-Weiterleiter 560, 570 einer PPU mit anderen Alpha- und Beta-Weiterleitern anderer PPUs, wie dies im folgenden beschrieben werden wird.
Wie in Figur 8 gezeigt, enthält der Adreß-Abbilder 510 ein PPU- Adreßregister 605, ein Onset-Register 610, ein VP-Offset- Register 615, ein VP-Erhöhungsregister 620 und eine Seitentabelle 625. Der Abbilder enthält erste, zweite und dritte Multiplexer 630, 635, 640 und erste und zweite Addierer 645, 650. Ein Eingang zum Adreßabbilder wird vom VP-Sequenzer 530 über den Adreßbus 602 empfangen und ein Ausgang vom Abbilder wird dem Speicherinterface 520 über den physikalischen Adreßbus 652 zur Verfügung gestellt. Zwei Bits der Seitenbits werden dem VP- Sequenzer 530 über die Seitenbitleitungen 654 zur Verfügung gestellt. Wie gezeigt, ist der Adreßbus 24 Bits groß und der physikalische Adreßbus ist 22 Bits groß.
Um den Betrieb des Adreßabbilders zu verstehen, ist es nützlich, das Adressierungsschema für das System der vorliegenden Erfindung zu verstehen. Wie in Figur 13 gezeigt, gibt es vier Typen von Adressen, die in dem System gespeichert sind: locative; Weiterleitungsadressen, virtuelle Adressen und physikalische Adressen. Um genügend virtuelle Prozessoren zu unterstützen, um den Bedürfnissen von 1000 Benutzern gerecht zu werden, unterstützt das System der vorliegenden Erfindung die virtuellen Prozessoren selbst wenn sie nur im virtuellen Speicher gespeichert sind. Somit können selbst Daten, die physikalisch auf Platten gespeichert sind, mit einem virtuellen Prozessor assoziiert werden. Als Ergebnis ist das erfindungsgemäße System in der Lage, bis zu 240 virtuelle Prozessoren zu unterstützen. Da der gesamte Adreßraum im Prinzip von einem einzelnen Benutzer genutzt werden kann, unterstützt die CM2 eine Adressierungsstruktur mit einem 64-bit-Adreßraum.
Die allgemeinste Form der Adresse ist ein Lokativ, welches 64 Bits im Speicher benötigt. Ein Lokativ ist in der Lage, auf einen beliebigen Speicherplatz innerhalb eines jeden virtuellen Prozessors des gesamten Systems zu zeigen. Die höchsten 40 Bits des Lokativs legen den ausgewählten virtuellen Prozessor fest. Die untersten 24 Bits legen einen Offset innerhalb des virtuellen Prozessors fest. Da 2&sup6;&sup4; größer ist als die Größe des virtueilen Speichers des gesamten Systems, bleibt genug Raum für Redundanzcodierung. Insbesondere können die 40 Bits die den virtuellen Prozessor festlegen, separat die PPU angeben, in der sich der virtuelle Prozessor befindet (18 Bits) sowie das Wort innerhalb des virtuellen Speichers der physikalischen Verarbeitungseinheit, bei der der virtuelle Prozessor beginnt (22 Bits). Ein virtueller Prozessor kann an jeder geraden 32' Bit- Grenze innerhalb des 24-Bit virtuellen Adressierungsraums des physikalischen Prozessors beginnen.
Die Weiterleitungsadressen sind die Adressen, die von dem Kommunikationsnetzwerk verwendet werden. Sie sind im wesentlichen eine kompakte Form von Lokativen, die gebildet werden, indem der 24-Bit-Offset und vier Mal der 22-Bit-Offset der virtuellen Prozessoradresse zueinanderaddiert werden. Eine Weiterleitungsadresse legt ein einzelnes Wort in dem virtuellen Speicher einer physisikalischen Prozessoreinheit innerhalb des Systems fest. Die Länge der Weiterleitungsadresse ist 42 Bits, was der Anzahl der Wörter des virtuellen Speichers des gesamten Systems entspricht.
Innerhalb einer PPU werden alle Pointer als 24-Bit virtueller Adressen gespeichert. In einer derartigen Adresse stellen 8 Bits eine Seite eines Speichers und 16 Bits die Adresse eines Bits innerhalb der Seite dar. Die Seite ist die Einheit eines angeforderten Cachings für das virtuelle Speichersystem. Zu einer beliebigen Zeit, können bis zu 64 Seiten physikalisch in dem Speicher enthalten sein.
Die 24-Bit virtuelle Adresse wird auf einer 22-Bit physikalischen Adresse durch die Seitentabelle 625 abgebildet. Jede Seitentabelle stellt ein 256-Word 6-Bit-Nachschlagetabelle dar, die jede der 2&sup8; Seiten in dem virtuellen Speicher in 2&sup6; Seiten des physikalischen Speichers abbildet.
Der Adressenabbilder 510 nimmt die virtuelle Adresse, die in den Funktionsschaltkreis eintritt und wandelt sie entweder in eine physikalische Adresse für den Speicher oder in eine Weiterleitungsadresse für Kommunikationen um. Der Adreßabbilder ist so ausgelegt, daß er drei verschiedene Adressierungsmoden unterstützt: normal, Virtuellprozessor relativ und erweitert. Beim normalen Adressierungsmode wird eine 24-Bit physikalische Adresse direkt von der PPU genommen und in eine 8-Bit Seitennummer und einen 16-Bit Offset aufgeteilt. Die 8-Bit- Seitennummer wird als Index in der Seitentabelle 625 verwendet, welcher die Abbildung der virtuellen Seiten auf dem physikalischen Speicher enthält. Im Falle, daß die Referenzseite im physikalischen Speicher enthalten ist, wird die Seitentabelle eine 6-Bit-Adresse erzeugen, die angibt, in welchem Teil des physikalischen Speichers die Seite enthalten ist. Dies wird mit einem 16-Bit-Offset kombiniert, um eine 22-Bit physikalische Adresse zu erhalten, die direkt an das Speicherinterface weitergegeben wird. Im Falle, daß die Referenzseite ausgetauscht wird, wird die Seitentabelle durch die gesetzten Seitenbits anzeigen und es wird der Seite gestattet, von einem zweiten Speicher in den physikalischen Speicher geladen zu werden. Die geladenen Seiten werden in einer FIFO geladen, so daß eine neue Seite über einer zuletzt geladenen Seite abgelegt wird. Es ist auch möglich, bei der Verwendung der Seitenbits gewisse Seiten festzulegen, so daß sie nie zum zweiten Speicher geschoben werden.
Der zweite Adressierungsmode ist der virtuelle Prozessor- Relativmode. In diesem Fall wird die Adresse, die von dem Bus kommt,als Offset relativ zur virtuellen Prozesser-Offsetadresse für den virtuellen Prozessor der momentan arbeitet, verwendet. Diese zwei 24-Bitadressen werden durch einen Addierer 650 zusammenaddiert um eine 24-Bit virtuelle Adresse zu schaffen, die dann in eine physikalische Adresse über die Seitentabelle so wie oben beschrieben, umgewandelt wird. Der virtuelle Prozessor-Offset wird durch den virtuellen Prozessorsequenzer gesetzt oder im Fall, daß der virtuelle Prozessor eine vorgegebene Größe hat, durch Inkrementieren.
Die endgültige Form der Adressierung stellt einen Mechanismus dar, durch den eine Zwischenprozessorkommunikaton ermöglicht wird. In diesem Fall wird die relevante Funktion über den Beta- Weiterleiter berechnet und die Adresse wie folgt berechnet: Die 18-Bit-Adresse der Ziel-PPU wird mit der Summe verbunden, die aus der 24-Bit physikalischen Adresse von dem Chip und dem 24-Bit-Onset Word das in dem Onset-Register 610 geladen ist, resultiert. Typischerweise wird dies im vorhergehenden Zyklus während einer erweiterten Adressierungsoperation ausgeführt. Wenn eine Nachrichtenadresse empfangen wird, als virtuelle Speicheradresse verwendet und als physikalische Adresse über die Seitentabelle so wie bei der normalen Adressierung bezeichnet.
Die Speicher-Interfaceeinheit 520 ist für das physikalische Multiplexen der Adressierung und der Speicherauffrischung bei dynamischen RAMs verantwortlich. Wie in Figur 9 gezeigt, umfaßt die Interface-Einheit 520 einen Auffrischungszähler 660, ein Reihenzählregister 665, einen Multiplexer 670 und einen Vergleicher 675. Der Multiplexer 670 multiplext die 22-Bit physikalische Adresse auf die 11 Adreßpins. Der Auffrischungszähler 660 kann für Diagnosezwecke zurückgesetzt werden. Die Speicher- Initerfaceeinheit wird so ausgelegt, daß sie einen Schnellblokkiermodezugriff aufweist, wie dies heutzutage durch die meisten dynamischen RAMs unterstützt wird. Um dies zu tun, speichert die Speicherinterfaceeinheit die Reihenzahl der letzten Reihe auf die von dem Reihenregister 665 zugegriffen wurde. Wenn der Vergleicher 675 bestimmt, daß ein Zugriff auf die gleiche Reihe als bei dem vorherigen Zugriff ausgeführt wird, wird ein Schnellzyklus ausgeführt, der nur den Spaltenteil der Adresse verwendet. Somit auf den gleichen Speicherblock in etwa der halben Zeit wie bei einem normalen Speicherzugriff zugegriffen werden. Dies ist insbesondere dann wichtig, wenn auch Blöcke von sequentiellen Daten zugegriffen werden soll.
Der virtuelle Prozessorsequenzer 530 kann eine einfache FINITE- Date-Maschine zum schnellen Ausführen von Listenoperationen sein, wie sie für virtuelle Prozessoren benötigt werden. Eine PPU implementiert mehrere virtuelle Prozessoren, indem sie deren Operation seitlich sequentiell multiplext. Ein bestimmter Abschnitt des Speicherraums der PPU (einschließlich des virtueilen Speicherbereichs) wird jedem virtuellen Prozessor zugewiesen, obwohl die Anzahl der virtuellen Speicher pro virtuellen Prozessor völlig variabel ist. Typischerweise werden die virtuellen Prozessoren durch eine PPU implementiert, die mehrere unterschiedliche Aufgaben hat. Für jede Aufgabe muß die PPU alle Prozessoren des momentanen Kontext der Aufgabe überprüfen, um die auszuführende Reihenfolge festzulegen. Es muß außerdem durch alle Order die mit der Sequenz von Aufgaben assoziiert sind, durchgehen. Es ist jedoch nicht notwendig, durch alle virtuellen Prozessoren, die durch die PPU implementiert sind, die nicht im Kontext der Aufgabe vorhanden sind, durchzugehen. Dadurch wird erheblich Zeit gespart.
Sowohl die virtuellen Prozessoren als auch die Mehrfachaufgaben Kontextumschaltung werden direkt durch Hardware unterstützt. Die Organisation der virtuellen Prozessoren im Speicher ist in schematischer Weise in Figur 14 gezeigt. Die Aufgaben sind so in einer circularen Liste, die als Aufgabenliste bezeichnet wird, miteinander verbunden und die PPU enthält zu jeder Zeit einen Zeiger, der auf eine der Aufgaben in der Aufgabenliste deutet. Mit Hilfe des Sequenzers 530 geht die PPU durch jede Aufgabe, führt einen Auftrag für jeden virtuellen Prozessor in dem Kontext der momentanen Aufgabe durch, bevor zur nächsten Aufgabe weitergegangen wird. Somit wird, falls der Kontext relativ klein ist, die Ausführung schneller von statten gehen, als in dem Fall, bei dem alle virtuellen Prozessoren zum momentanen Kontext gehören.
Jede Aufgabe ist mit einem Header assoziiert, der drei Informationsstücke enthält: einen Pointer für den momentanen Kontext, einen Pointer zu einem Stack, der als verwundene Liste gespeichert ist, und einen Pointer auf eine Liste von allen virtuellen Prozessoren der Aufgabe. Der Sequenzer enthält auch einen Pointer zur nächsten Aufgabe in der Aufgabenliste und Hilfsinformation über die Aufgabe, wie beispielsweise Priorität und Ablaufstatistik. Die PPU bestimmt den Platz jedes virtuellen Prozessors im virtuellen Speicher, indem sie der Liste folgt, und wobei mit dem Kontext-Pointer begonnen wird und fortgefahren wird bis Null erreicht wird. Diese Listen werden in einem geschützten Bereich des Speichers gespeichert.
Um einen "Push-Kontext"-Befehl auszuführen, weist die PPU ein neues Speicherelement zu und bringt den momentanen Kontext- Pointer auf den Stack, wechselt den Stack-Pointer zum obersten Platz auf dem Stack. Ein "pop-context"-Befehl ist dazu genau umgekehrt, ausgenommen dann, wenn der Stack leer ist, da in diesem Fall der oberste Kontextpointer verwendet wird. Die nächste häufig benötige Operation besteht im Eingrenzen des Kontext auf einen Untersatz des momentanen Kontext gemäß einer bestimmten Bedingung.
In diesem Fall wird die Liste der virtuellen Prozessoren gemäß der Bedingung aufgespaltet, wobei mit dem momentanen Kontext begonnen wird. Die virtuellen Prozessoren, die die spezielle Bedingung erfüllen, werden an das Ende der Liste angehängt. Ein Pointer zum Ende der Liste wird dann zum momentanen Kontext. Auf diesem Wege können die Untersätze, die aufeinanderfolgenden Kontext darstellen, effizient gespeichert werden. Mit diesem Schema stellen virtuelle Prozessoren die nicht im momentanen Kontext enthalten sind, keine unnötige Belastung während der Ausführung dar.
Wie in Figur 10 gezeigt ist, enthält jeder virtuelle Prozessorsequenzer 530 fünf Primärregister, von denen jedes in der Lage ist, die 22 höchsten Bits einer virtuellen Prozessoradresse zu speichern. Das Kontextregister 680 speichert einen Pointer auf den Anfang der momentanen Kontext-Liste. Das Stack-Register 685 speichert einen Pointer zum momentanen Stack für die momentane Aufgabe. Das Topregister 690 speichert einen Pointer zum Anfang der Kontextliste des momentanen Stacks. Das Aufgabenregister 695 speichert einen Pointer zur nächsten Aufgabe in einer Aufgabenliste und das nächste Register 700 speichert einen Pointer zum nächsten virtuellen Prozessor in der virtuellen Prozessorliste. Zusätzliche Register können verwendet werden, um Zusatzinformation zu speichern, falls dies erforderlich ist. Der Ausgang des Sequenzers 530 wird durch den Multiplexer 715 in Antwort auf Signale von einem PLA 710 ausgewählt.
Der virtuelle Prozessorsequenzer enthält eine "finite state"- Maschine, die im Zustandsregister 705 implementiert ist und enthält weiterhin eine PLA 710 zum Manipulieren dieser Register
und zum Steuern der Register in dem Adreßabbilder oder dem Order-Cache. Diese finite state-Maschine geht durch die Befehlsliste um sowohl Aufgaben als auch virtuelle Prozessoren zu berücksichtigen. Die Ausgänge der Maschine hängen vom momentanen Zustand und von Zustandsbits, die vom Rest des Funktionsschaltkreises kommen, beispielsweise den Seitenbits der Seitentabelle 625, ab. Die PLA ist auch in der Lage, bedingte Übergänge auszuführen, basierend, ob die momentanen Daten Null sind, wie dies von einem Null-Detektor 720 erkannt werden kann. In diesem Sinne ist der virtuelle Prozessorsequenzer ein sehr einfacher Computer ohne arithmetische Einheit.
Der Datencache 540 ist ein herkömmlicher Cache für das "Caching" von Nur-Lese-Daten.
Der Fehlerkorrigierer 550 ist eine herkömmliche Einbit- Fehlerkorrekturdetektionslogik, basierend auf einem 6-Bit- Hamming-Code. Wie in Figur 11 gezeigt, umfaßt der Leitungstreiber 740, 745, 750, 755, Fehlersteuerschaltkreise 760 und 765 zum Berechnen von Paritätbits, ein Exklusiv-Oder-Gatter 770 zum Detektieren von Paritätsfehlern, einen Dekoder 775 zum Bestimmen, ob ein Fehler korrigiert werden kann und ein Exklusiv- Oder-Gatter 780 zum Korrigieren eines erkannten Fehlers. Der Fehlersteuerschaltkreis 760 addiert Fehlerkorrekturbits zu allen Daten, die in einen physikalischen Speicher geschrieben werden. Alle Daten, die von dem physikalischen Speicher gelesen werden, werden überprüft, indem der Fehlersteuerschaltkreis 765 die Paritätsbits für die vom Speicher gelesenen Daten erneut berechnet und diese Bits im X oder Gatter 770 mit Paritätsbits, die aus dem Speicher gelesen werden, vergleicht. Der Dekoder 775 bestimmt, ob ein Fehler korrigiert werden kann und korrigiert, falls dies möglich ist, indem er ein geeignetes Signal an das XOR-Gatter 770 anlegt. Wenn mehrfache Fehler auftreten, wird ein Einheitenfehler durch den Dekoder 775 angezeigt. Die Alpha- und Beta-Weiterleiter 560 und 570 werden zur Befehlsund Daten-Verteilung eingesetzt und können die gleichen Kommunikationsleitungen teilen, obwohl die Weiterleitungshardware separat ist. Wie in Figur 12 gezeigt ist, enthält der Alpha- Weiterleiter 560 ein Feld von UND-Gattern 800 A bis N, die durch Flip-Flops 805A-N, erste und zweite ODER-Gatter 810, 815, ein Feld von Multiplexern 820A bis N, welches durch Flip-Flops 825A bis N gesteuert wird, einen ersten Multiplexer 830, der durch die Flip-Flops 832, 834 gesteuert wird und einen zweiten Multiplexer 840, der durch ein Flip-Flop 842 gesteuert wird. Eingangsleitungen 802A bis N werden den UND-Gattern 808 bis N zugeführt und die Ausgangsleitung 822A bis N erstrecken sich von den Multiplexern 820 A-N. Diese Leitungen verbinden den Alpha-Weiterleiter einer PPU mit den Alpha-Weiterleitern der nächsten Nachbar-PPUs in dem binären Hyper-Würfel. Entsprechend der Anzahl der UND-Gatter 800A bis N, entsprechend dem Multiplexer 820A bis N und ihre zugeordneten Schaltkreise der Anzahl der Dimensionen des Hyper-Würfels, beispielsweise 18. Zum Zwekke des besseren Verständnisses wurden jedoch nur drei Dimensionen gezeigt. Da die Eingangs- und Ausgangsleitungen, die mit jeder Dimension assoziiert sind, demselben Alpha-Weiterleiter zugehen, können diese Leitungen gemultiplext werden, falls dies gewünscht ist. Da diese Leitungen außerdem zu denselben PPUs wie die Eingangs- und Ausgangs-Leitungen des Beta-Weiterleiters führen, können sie auch mit den Leitungen des Beta- Weiterleiters gemultiplext werden.
Der Alpha-Weiterleiter wird verwendet, um Befehle zu verteilen und zu synchronisieren. Im wesentlichen führt er dieselbe Funktion aus wie der Befehlsverteilungsbaum und die Global-Oder- Bäume wie sie in dem '400 Patent beschrieben werden, mit Ausnahme dahingehend, daß jeder Prozessor oder jede Anzahl von Prozessoren eine Quelle für Befehle darstellen kann. Diese Befehle werden zu Gruppen zusammengefaßt, die als "Orders" bezeichnet werden. Die Ausführung einer Order wird für die ganze Maschine durch den Alpha-Weiterleiter synchronisiert, so daß eine Order vollständig ausgeführt wird, bevor die nächste Order ausgegeben wird. Die auszustrahlenden Order werden von dem lokalen Interzeptor 580 empfangen und Order, die von anderen Weiterleitern empfangen werden, werden über die Ausgangsleitung zu einem Order-Cache 540 weitergeleitet. Synchronisationssignale, die den Abschluß einer empfangenen Order anzeigen, werden über die PPU dem Weiterleiter auf der Sync-In-Leitung zugeführt und Signale, die den Abschluß einer Order durch andere PPUs anzeigen, werden der PPU auf der Sync-Aus-Leitung zugeführt.
Der Betriebsmode des Alpha-Weiterleiters wird durch Flip-Flops gemäß Signale, die von der PPU empfangen werden, gesteuert. Somit wird, falls die lokale PPU Order zu anderen PPUs ausstrahlt, das Flip-Flop 842 den Multiplexer 840 setzen, daß dieser das Signal über die Order-In-Leitung überträgt und die Flip-Flops 825A bis N werden die Multiplexer 820A bis N so setzen, daß eine Übertragung dieser Signale erfolgen kann. Wenn die lokale PPU Order von einer anderen PPU empfängt, werden die Flip-Flops 832 so gesetzt, daß sie eine spezielle eingehende Dimensionleitung zum Multiplexer 830 spezifizieren, von wo die Order erwartet wird. Wenn die Order zu einer anderen PPU weitergegeben wird, setzt das Flip-Flop 842 ebenfalls den Multiplexer 840, damit dieser das Signal vom Multiplexer 830 zu den Multiplexern 820A bis N überträgt. Durch diese Anordnung kann eine PPU-Order zu jedem seiner nächsten Nachbarn übertragen und sie dabei steuern. Jede PPU kann von seinen nächsten Nachbarn die Order beobachten, um von dieser gesteuert zu werden.
Nachdem eine Order ausgegeben wurde, beobachtet die PPU, die die Order ausgegeben hat, die Ausführung der Order mittels Synchronisationssignalen. Eine PPU gibt ein Sync-Signal über die Sync-In-Leitung zum Oder-Gatter 815 aus und setzt die Flip- Flops 825A bis N, so daß die Multiplexer 820A bis N das Signal vom ODER-Gatter 815 übertragen. Ein Sync-Signal wird empfangen, indem die Flips-Flops 805A bis N so gesetzt werden, daß die UND-Gatter 800A bis N in der Lage sind, ein empfangenes Signal zum ODER-Gatter 810 weiterzugeben. Der Ausgang des ODER-Gatters 810 kann auch zu anderen PPUs über einen Eingang zum ODER- Gatter 815 weitergegeben werden. Bei dieser Anordnung kann eine PPU selektiv Sync-Signale von seinen nächsten Nachbar-PPUs überwachen, welches sie steuert und sie kann Signale von anderen PPUs ignorieren, die sie nicht steuert.
Der Beta-Weiterleiter 570 ist im wesentlichen vom selben Typ wie der Weiterleiter, wie er im '400 Patent beschrieben ist. Wie in Figur 2 gezeigt, weist er ein Feld von Eingangs- und Ausgangsleitungen 38, 39 auf, die mit den Beta-Weiterleitern der nächsten Nachbar-PPUs in dem Hyperwürfel über die Würfelpins 572 der Figur 7 kommunizieren. Nachrichtenpakete werden dem Beta-Weiterleiter 570 von dem Mikroprozessor über den Adreß-Abbilder 510 und den Datencache 540 zur Verfügung gestellt und empfangene Nachrichtenpakete werden dem Mikroprozessor über die gleichen Elemente zur Verfügung gestellt. Die Eingangs- und Ausgangsleitungen können gemultiplext werden und diese Leitungen können ebenfalls mit den Leitungen 802A bis N und 822A bis N des Alpha-Weiterleiters gemultiplext werden.
Der Beta-Weiterleiter ist im wesentlichen für drei unterschiedliche Funktionen verantwortlich. Er leitet Nachrichtenpakete von einer PPU zur anderen weiter, wobei dies einer Funktion in dem '400 Patent entspricht. Weiter erzeugt er Nachrichtenpakete entsprechend den Speicheranfragen von der PPU mit der er assoziiert ist für Speicher, die mit anderen PPU's assoziiert sind. Er empf ängt eingehende Nachrichtenpakete von anderen PPU's, die für die PPU bestimmt sind, mit der er assoziiert ist und liefert diese Nachrichtenpakete entsprechend ab. Während die letzten zwei genannten Funktionen neu sind, ist die Weiterleitung eines jeden Nachrichtenpakets in jeder Funktion die gleiche wie sie im '400 Patent beschrieben ist.
Ein Parallelcomputer gemäß der vorliegenden Erfindung ist eine teuere Resource, vermutlich zu teuer, um von einem einzelnen Benutzer für eine längere Zeitperiode verwendet zu werden. Es ist jedoch möglich, daß der vorliegende Computer gleichzeitig von tausenden von Benutzern benutzt wird. Während die Spitzenanforderungen für jeden Benutzer sehr hoch sein können, kann angenommen werden, daß die mittlere Anforderung relativ moderat ist, beispielsweise 100 000 000 Befehle pro Sekunde pro Benutzer. Zusätzlich wird angenommen, daß die Benutzer in der Lage sind, auch andere Vorteile einer gemeinsamen Resource zu nutzen, beispielsweise das Teilen von Datenbanken.
Die Technik, die zum Teilen der Resource verwendet wird, kann als Raum-Aufteilung entsprechend der Zeit-Aufteilung bezeichnet werden, da die Benutzer die Raum-Zeit-Resource des Computers sowohl bezüglich Raum als auch bezüglich Zeit aufteilen. In diesem Sinne könnte die Raum-Teilung genauer als Raum- Zeit- Teilung bezeichnet werden, da Zeitmultiplex mit eingeschlossen sein kann. Raum-Zeit-Aufteilung würde funktionieren, wenn jeder Benutzer das gesamte System mit einer gleichmäßigen Last zu allen Zeiten belegt, jedoch arbeitet diese Aufteilung besser aufgrund der Nichteinheitlichkeiten einer typischen Benutzerlast:
Idle-Zeit: Viele Benutzer benötigen, wenn sie die Maschine benutzen, tatsächlich nur wenige Zyklen pro Zeiteinheit. Dies gilt insbesondere für ein transaktions-basierendes System, das Anfragen und eine geteilte Datenbank unterstützt.
Nichteinheitliche Parallelität: Wenn ein Parallelprogramm ausgeführt wird, kann es viele Punkte in dem Programm geben, wo es möglich ist, effizient hunderte von tausenden von virtuellen Prozessoren gleichzeitig effektiv zu nutzen. Es kann andere Punkte geben, wo eine einzelne Wort-pro-Zeitausführung ausreichend ist.
Nichteinheitliche Speicheranforderungen: Viele Benutzer werden direkten Zugrifflediglich zu einem geringen Teil des Terabyte- Speichers zu einem bestimmten Zeitpunkt benötigen.
Gemeinsamkeit von Daten: Viele Benutzer können auf die gleiche Datenbank in einer kurzen Zeitperiode zurückgreifen, was ermöglicht, daß diese Daten im Hauptspeicher mit relativ geringen Kosten verbleiben. Ein gleiches Argument gilt für geteilte Sof tware.
Um diese Nichteinheitlichkeiten auszunutzen, weist der Computer die physikalischen Prozessoren dynamisch den virtuellen Prozessoren basierend auf Lauf zeitanforderungen zu. Somit verbraucht ein Benutzer Resourcen proportional dazu, was die Anmeldung tatsächlich benötigt, im Gegensatz zu einem Anteil, den er möglicherweise benötigt.
Ein Merkmal des Beta-Weiterleiters macht es möglich, das Feld der PPUs zwischen unterschiedlichen Benutzern aufzuteilen um somit eine Raum-Aufteilung zu erreichen. Wie in Figur 2 gezeigt ist, steuert der G-in-Eingangsanschluß den Zugriff auf die Kommunikationsleitung 39, die ein Nachrichtenpaket von einer PPU zur anderen weiterleitet. Wenn diese Leitung unterbrochen ist, kann sie von dem Netzwerk dadurch entfernt werden, daß ein "Low-Signal" auf den G-in-Eingangsanschluß, der mit dieser Leitung assoziiert ist, angelegt wird. Gemäß der vorliegenden Erfindung kann jeder Unter-Würfel des Hyper-Würfels von dem Rest des Hyper-Würfels dadurch isoliert werden, daß ein "Low"-Signal an die G-in-Eingangsanschlüsse, die mit den Kommunikationsleitungen angelegt wird, die den Unterstrichwürfel mit dem Rest des Hyper-Würfels verbinden. Beispielsweise kann ein Unter- Würfel mit 256 PPUs von dem 18-dimensionalen Hyper-Würfel einfach dadurch isoliert werden, daß "Low"-Signale den G-in-Eingangsanschlüssen, die mit den Kommunikationsleitungen für die Dimensionen 8 bis 18 assoziiert sind, an jedem der 256 PPUs des Unter-Würfels angelegt werden. Gleichzeitig können eine Vielzahl anderer Unter-Würfel den anderen Teilen des Hyper-Würfels in ähnlicher Weise von dem Hyper-Würfel dadurch isoliert werden, indem Low-Signale den G-in-Eingangsanschlüssen, die mit der Kommunikationsleitung für die Dimension, die nicht verwendet werden, angelegt werden.
Um dies zu erreichen, wird dem Mikroprozessor einer jeden PPU Zugriff auf den G-in-Eingangsanschluß ermöglicht, so daß er ein Low-Signal in Antwort eine spezifizierte Konfiguration eines Unter-Würfels ausgibt. Der Zugriff kann durch ein Flip-Flop (nicht gezeigt) ausgeübt werden, dessen Ausgangszustand durch den Mikroprozessor der PPU gesteuert werden kann.
Gemäß der vorliegenden Erfindung identifiziert ein Tag-Bit in dem Befehl Parallelbefehle, die durch andere PPUs parallel ausgeführt werden müssen. Der Interzeptor 580 testet dieses Tag- Bit. Alle Daten, auf die im Speicher durch die PPU zugegriffen wird, gehen durch den Interzeptor 580. Wenn das Tag-Bit der Daten anzeigt, daß ein Parallelbefehl vorliegt, wird ein noop- Befehl an die Datenpins gesendet und der Interzeptor sendet den Parallelbefehl zu dem Alpha-Weiterleiter, damit dieser an andere PPUs weitergegeben wird. Wenn das Tag-Bit anzeigt, daß kein Parallelbefehl vorliegt, wird der Befehl durch die Datenpins der PPU zugeführt.
Der Order-Cache 590 ist ein Speicher, der zum Speichern von Order vom Alpha-Weiterleiter verwendet wird. Der virtuelle Prozessersequenzer 530 bewirkt, daß die PPU auf die Befehle von dem Order-Cache zugreift, um die Aktion bei jedem virtuellen Prozessor zu implementieren. Der Order-Cache ist im wesentlichen ein Befehlscache für die Befehle, die parallel für jede Aufgabe ausgeführt werden. Der Cache kann beispielsweise 256 Wörter groß sein.
Aufgrund der internen Verdopplung von Komponenten bei dem Computer ist er in der Lage, aufgrund von Redundanz fehlertolerant zu arbeiten. Vorteilhafterweise ist der gesamte Speicher der Datenbank auf zumindest zwei physikalisch separate Module verteilt, so daß wenn ein Speichermodul ausfällt, die Daten von dem Backup-Modul verwendet werden können und verdoppelt werden können um ein anderes Backup zu erzeugen. Wenn ein Prozessormodul ausfällt, wird es von dem System isoliert, bis es ersetzt werden kann und physikalische Prozessor vom Rest der funktionierenden Prozessoren zugewiesen wurden.
Die schwierigsten Probleme in einem fehlertoleranten System bestehen darin, Fehler zu detektieren und zu isolieren wenn sie auftreten und mit der Aufgabe fertig zu werden, die momentan verarbeitet wird, wenn der Fehler auftritt. Hierbei gibt es einen Kompromiß zwischen Sicherheitsgrad, daß die Aufgabe richtig zu Ende geführt wird und dem Hardwareaufwand für die Auf gabe zur Verfügung gestellt wird. In dem Parallelcomputer der vorliegenden Erfindung ist der Benutzer in der Lage, diesen Kompromiß während der Laufzeit zu machen, jeweils abhängig von der Bedeutung der Aufgabe. Eine Aufgabe kann in einem von drei Moden entsprechend der benötigten Redundanz ausgeführt werden. Im einfachsten Betriebsmode des Systems wird selbstüberprüfende Hardware wie beispielsweise ein Fehlerkorrekturschaltkreis 550 der Figur 11 verwendet, um Fehler zu detektieren und zu isolieren. Diese Hardware ist in der Lage, die häufigsten Fehlertypen und Ausfälle zu detektieren, beispielsweise nicht korrigierbare Speicherfehler, Leistungsverlust und nicht korrigierbare Fehler in der Übertragung. Immer wenn ein Fehler durch einen Selbstüberprüfungsschaltkreis im Selbstüberprüfungsmode gefunden wird, wird die momentane Transaktion abgebrochen und die Hardware rekonfiguriert, um das defekte Teil zu isolieren. Die Transaktion wird dann vom Anfang an gestartet.
Während ein Selbstüberprüfungsschaltkreis die meisten Fehler die auftreten können, erkennen wird, ist dadurch nicht garantiert, daß jeder Fehlertyp erkannt wird. Insbesondere können viele Fehler innerhalb der PPU selbst auftreten und werden daher nicht detektiert. In einem redundanten Mode wird das Betriebssystem zwei identische Kopien des Programms auf zwei physikalisch seperierten isomorphen Sätzen von Prozessoren rausführen und die Ergebnisse regelmäßig miteinander vergleichen. (Die Verkabelung des Kommunikationssystems, die entsprechend dem Muster eines n-dimensionalen Würfels ausgeführt ist, stellt exakt die richtigen Kommunikationspfade für diesen Vergleich zur Verfügung). Der Vergleichsmechanismus garantiert die Federdetektion und den Grund dafür. Wenn Fehler im redundanten Mode detektiert wurden, werden sie in exakt der gleichen Weise wie im Selbstüberprüfungsmode behandelt. Beide Prozessoren werden vom System isoliert, bis über Diagnoseabläufe festgestellt wurde, welcher Prozessor fehlerhaft ist.
Ein Nachteil der Selbstüberprüfung und des Redundanzmodes ist, daß sie einen Neustart der Transaktion erfordern, wenn ein Fehler aufgetreten ist. Dies kann für Aufgaben, die nicht in relativ kleine Transaktionen aufgeteilt werden, nicht akzeptierbar sein. Einige Aufgaben weisen Echtzeitzeitverarbeitungsanforderungen auf, die nicht erlauben, daß eine Transaktion wiederholt wird. Für diese zwei Situationen ist der quadrierte Redundanzmode für einen fehlersicheren Betrieb.
Dem quadrierten Redundanzmode werden vier identische Kopien der Anwendung synchron betrieben. Jede Aufgabe vergleicht seinen Betrieb mit anderen in zirkularer Weise. Beispielsweise überprüft A B, B C, C D und D A. Wenn ein Fehler auftritt, wird er sowohl detektiert als auch entsprechend dem Muster der Nichtübereinstimmung isoliert. In diesem Fall wird der korrigierte Zustand des Prozesses von einer nicht fehlerhaften Aufgabe zu einem anderen Unterwürfel kopiert und der Betrieb wird ohne bedeutende Unterbrechung weitergeführt. Es wird vierfache statt dreifache Redundanz verwendet, so daß eine geeignete Verkabelung für den Vergleich in dem N-dimensionalen Würfel zur Verfügung steht.
Verschiedene Modifikationen der Erfindung sind möglich. Beispielsweise kann, obwohl die Erfindung für ein Feld von Parallelprozessoren das in Form eines binären Hyperwürfels organisiert ist, beschrieben wurde, selbstverständlich auch eine andere Organisation verwendet werden wie sie beispielsweise im '400 Patent beschrieben wurden. Selbstverständlich müssen in diesen Fällen geeignete Modifikationen vorgenommen werden, beispielsweise hinsichtlich des Alpha- und Beta-Weiterleiters, die oben lediglich für die Signalisierung im Prozesserfeld beschrieben wurden.

Claims

1. Parallelcomputer mit:

einer Vielzahl von Prozessoreinheiten (330), wobei jede Prozessoreinheit aufweist:

einen Prozessor (350);

einen Lese/Schreib-Speicher (370); und

einen Steuerschaltkreis (360), der Einrichtungen zur Befehlsverteilung und Synchronisation zwischen der Vielzahl von Prozessoreinheiten über Kommunikationsleitungen in dem Parallelcomputer aufweist;

dadurch gekennzeichnet, daß

jeder Steuerschaltkreis einer Prozessoreinheit eine Einrichtung (Fig. 2; 800A-800N, 805A-805N, 825A-825N, Fig. 12) aufweist, die in Antwort auf von dem Prozessor empfangene Signale selektiv den Zugriff auf einzelne der Kommunikationsleitungen steuert, und

die Prozessoren von ausgewählten Prozessoreinheiten rekursiv beginnend mit einer anfänglichen Prozessoreinheit, eine ausgewählte Gruppe von Prozessoreinheiten, die mit diesen verbunden sind, identifizieren, um eine Verarbeitung unter ihrer Steuerung aufzuführen und ihre Steuerschaltkreise zu steuern, um selektiv Zugriff zu den entsprechenden Kommunikationsleitungen zuzulassen, mit denen die Prozessoreinheiten in der ausgewählten Gruppe verbunden sind.

2. Parallelcomputer nach Anspruch 1, wobei die Prozessoreinheiten in Form eines Hyperwürfels verbunden sind, wobei jede Kommunikationsleitung eine Verbindung zwischen Prozessoreinheiten entlang einer Dimension des Hyperwürfels ermöglicht, und wobei jeder Steuerschaltkreis aufweist:

ein Feld von Eingängen (802A-802N, Fig. 12), was in seiner Größe den Dimensionen des Hyperwürfels entspricht, wobei die Eingänge Signale über die Kommunikationsleitungen von den nächsten Nachbarprozessoreinheiten in dem Hyperwürfel empfangen;

ein Feld von Ausgängen (822A-822N, Fig. 12), das in seiner Anzahl den Dimensionen des Hyperwürfels entspricht, wobei die Ausgänge Signale über die Kommunikationsleitungen zu den nächsten Nachbarprozessoreinheiten in dem Hyperwürfel übertragen;

logische Einrichtungen (800A-800N, 810, 815, 820) zum Übertragen von Nachrichtenpaketen, die an den Eingängen empfangen wurden, an ausgewählte Ausgänge; und

eine Einrichtung (830, 832, 834) zum Durchlassen von Nachrichtenpaketen, die an den Eingängen empfangen wurden, in vorbestimmter Reihenfolge an einen ausgewählten Ausgang.

3. Parallelcomputer nach Anspruch 1, wobei die Prozessoreinheiten in Form eines Hyperwürfels mit n-Dimensionen verbunden sind, dadurch gekemizeichnt, daß der Steuerschaltkreis jeder Prozessoreinheit weiterhin aufweist:

eine erste Toreinrichtung (800A-800N, 810, 815), die einen Signaleingang von einer nächsten Nachbarprozessoreinheit in jeder Dimension des Hyperwürfels aufweist;

eine Einrichtung (805A-805N) zum Steuern der Toreinrichtung, so daß als ein Ausgang von der Toreinrichtung ein Signaleingang von einem oder mehreren Nachbarprozessoreinheiten des Hyperwürfels ausgewählt werden können;

eine zweite Toreinrichtung (820A-820N), die einen Signalausgang an eine nächste Nachbarprozessoreinheit in jeder Dimension des Hyperwürfels aufweist;

eine Einrichtung (825A-825N) zum Steuern der zweiten Toreinrichtung, so daß als ein Ausgang zu den nächsten Nachbarprozessoreinheiten des Hyperwürfels eines aus einer Vielzahl von Eingangssignalen ausgewählt werden kann, wobei ein erstes dieser Signale einen Ausgang von der ersten Toreinrichtung und ein zweites von diesen Signalen einen Ausgang von dem Prozessor in der gleichen Prozessoreinheit wie der Steuerschaltkreis ist, wobei die Signale von dem Prozessor oder von der ausgewählten nächsten Nachbarprozessoreinheit(en) über die zweite Toreinrichtung zu den nächsten Nachbarprozessoreinheiten, die mit der zweiten Toreinrichtung verbunden sind, ausgestahlt werden können.

4. Parallelcomputer nach Anspruch 3, dadurch gekennzeichnt, daß die erste Toreinrichtung eine Einrichtung (805A-805N, 800A-800N, 810) zum Auswählen eines oder mehrerer Signaleingänge von den nächsten Nachbarprozessoreinheiten und zum Bilden einer logischen ODER-Verknüpfung der ausgewählten Eingänge aufweist.

5. Parallelcomputer nach Anspruch 3 oder 4, dadurch gekennzeichnet, daß der zweite Signaleingang zu der zweiten Toreinrichtung ein Synchronisationssignal ("Synch In") von dem Prozossor ist, welches über die zweite Toreinrichtung zu den nächsten Nachbarprozessoreinheiten ausgestrahlt wird, die mit der zweiten Toreinrichtung verbunden sind.

6. Parallelcomputer nach Anspruch 5, dadurch gekennzeichnet, daß die Synchronisationssignale von dem Steuerschaltkreis der nächsten Nachbarprozessoreinheiten über den Ausgang (810) der ersten Toreinrichtung empfangen werden, wobei der Prozessor Operationen in den Prozessoreinheiten, die mit der zweiten Toreinrichtung verbunden sind, synchronisieren kann, indem Synchronisationsbefehle zu den Prozessoreinheiten über die zweite Toreinrichtung ausgestrahlt werden und indem der Ausgang der ersten Toreinrichtung nach einer geeigneten Antwort von den Prozessoreinheiten überwacht wird.

7. Parallelcomputer nach Anspruch 4, dadurch gekennzeichnet, daß das zweite Eingangssignal zur zweiten Toreinrichtung ein Befehlssignal ("Orders In", "Orders Out") von dem Prozessor ist, welches über die zweite Toreinrichtung zu den nächsten Nachbarprozessoreinheiten, die mit der zweiten Toreinrichtung verbunden sind, ausgestrahlt wird.

8. Parallelcomputer nach Anspruch 7, dadurch gekennzeichnet, daß die Befehlssignale von dem Steuerschaltkreis von einer ausgewählten nächsten Nachbareinheit über den Ausgang (830, 832, 834) der ersten Toreinrichtung empfangen werden.

9. Parallelcomputer nach einem der Ansprüche 3 bis 8, dadurch gekennzeichnet, daß der Steuerschaltkreis weiterhin aufweist:

eine dritte Toreinrichtung (830), die einen Signaleingang von einer nächsten Nachbarprozessoreinheit in jeder Dimension des Hyperwürfels aufweist;

eine Einrichtung (832, 834) zum Steuern der dritten Toreinrichtung, so daß als ein Ausgang von der Toreinrichtung ein Signaleingang von einer der nächsten Nachbarprozessoreinheiten in dem Hyperwürfel ausgewählt wird;

eine vierte Toreinrichtung (840), die einen Signalausgang aufweist, der als zweiter Eingang der zweiten Toreinrichtung zugeführt wird; und

eine Einrichtung (842) zum Steuern der vierten Toreinrichtung, um als Ausgang eines aus der Vielzahl von Eingangssignalen auszuwählen, wobei ein erstes Eingangssignal den Ausgang der dritten Toreinrichtung und ein zweites Eingangssignal den Ausgang von dem Prozessor in der gleichen Prozessoreinheit wie der Steuerschaltkreis darstellt, wobei die Signale von dem Prozessor oder von einer ausgewählten nächsten Nachbarprozessoreinheit über die zweite Toreinrichtung zu den nächsten Nachbarprozessoreinheiten, die mit der zweiten Toreinrichtung verbunden sind, ausgestrahlt werden kann.

10. Parallelcomputer nach Anspruch 9, dadurch gekennzeichnet, daß das zweite Eingangssignal zur zweiten Toreinrichtung ein Synchronisationssignal ("Synch In") von dem Prozessor ist, welches über die zweite Toreinrichtung zu den nächsten Nachbarprozessoreinheiten des Hyperwürfels ausgestrahlt wird, die mit der zweiten Toreinrichtung verbunden sind und das zweite Eingangssignal zur vierten Toreinrichtung ein Befehlssignal ("Orders In") von dem Prozessor ist, welches über die zweite Toreinrichtung zu den nächsten Nachbarprozessoreinheiten, die mit der zweiten Toreinrichtung verbunden sind, ausgestrahlt wird.

11. Prallelcomputer nach Anspruch 10, dadurch gekennzeichnet, daß die Synchronisationssignale von dem Steuerschaltkreis von den nächsten Nachbareinheiten durch den Ausgang der ersten Toreinrichtung empfangen werden und die Befehlssignale von dem Steuerschaltkreis von den nächsten Nachbarprozessoreinheiten über den Ausgang der dritten Toreinrichtung empfangen werden.

12. Parallelcomputer nach einem der Ansprüche l bis 11, weiterhin aufweisend eine Benutzerinferfaceeinrichtung (310) und eine Einrichtung (320) zum Verbinden der Benutzerinterfaceeinrichtung mit zumindest einer Prozessoreinheit, wobei eine anfängliche Prozessoreinheit mit der Benutzerinterfaceeinrichtung verbunden ist und die ausgewählte Gruppe in Antwort auf eine Verarbeitung, die von der Benutzerinterfaceeinrichtung ermöglicht wird, identifiziert.

13. Parallelprozessor nach einem der Ansprüche 1 bis 12, bei dem die Prozessoren ausgewählter Prozessoreinheiten selektiv bezüglich ihrem Zugriff zu einzelnen Kommunikationsleitungen, die mit den Prozessoreinheiten verbunden sind, die nicht der ausgewählten Gruppe angehören, deaktiviert werden.