DE3853162T2

DE3853162T2 - Gemeinsamer intelligenter Speicher für die gegenseitige Verbindung von verteilten Mikroprozessoren.

Info

Publication number: DE3853162T2
Application number: DE3853162T
Authority: DE
Inventors: Claude Basso; Gerald Lebizay; Jean-Marie Munier; Andre Pauporte; Clement Poiraud
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1988-12-23
Filing date: 1988-12-23
Publication date: 1995-08-17
Anticipated expiration: 2008-12-24
Also published as: DE3853162D1; JPH02238552A; JPH0587854B2; US5148527A; EP0374338A1; EP0374338B1

Description

Gebiet der Erfindung

Die gegenwärtige Erfindung bezieht sich auf Systeme, in denen mehrere Prozessoren oder Benutzer Zugriff auf einen gewöhnlichen Speicher oder einen gemeinsamen Speicher haben, der aus einer Vielzahl einzeln ansprechbarer Speichermodule (Speicherbänke) besteht, und im Besonderen auf einen gemeinsamen intelligenten Speicher mit der Fähigkeit, Speicherplatz mehreren Prozessoren oder Benutzern zuzuteilen.

Hintergrund

Für Systeme mit einer Vielzahl gemeinsamer Ressourcen wie etwa Speicher, I/O-Geräten, Puffer usw. ist es von Interesse, für einen konkurrierenden Zugriff auf die gemeinsamen Ressourcen zu sorgen, wobei dies bevorzugterweise für die Benutzer oder mehreren Prozessoren transparent gegenüber der physischen Systemkonfiguration erfolgen soll.
Eine Computervorrichtung mit gemeinsamen Speicher, der konkurrierenden Zugriff für eine Vielzahl Benutzer ermöglicht, wurde in EP-B-0023 213 beschrieben.
Das dabei angesprochene Problem besteht darin, einen konfliktfreien Zugriff auf gemeinsame Speichermodule zu ermöglichen, ohne daß es zu Leistungsverlusten kommt, wenn die Anzahl der Zugriffe und die Anzahl der Speichermodule erhöht werden. Um dieses Ergebnis zu er zielen, werden Mittel in Form eines Generators für Zufallsadressen geliefert, wobei dieser angeschlossen wurde, um Zugriffsanfragen zu empfangen und die mit der Anfrage empfangenen Adressen unter Bezugnahme auf die Speichereinbeiten in zufällig verteilten Adressen zu übersetzen.
Jedoch liefert dieses System nach dem Stand der Technik den Benutzern keine ausreichende Transparenz gegenüber den aktuellen oder physischen Adressen von Informationen innerhalb der Speichermodule, da das System nach dem Stand der Technik nur die logische Adressierung für Adressumrechnungszwecke nutzt.
EP-A-0 166 268 beschreibt ein System, das einer Vielzahl Arbeitsstationen den Zugriff auf einen aus unabhängigen Modulen bestehenden gemeinsamen Speicher ermöglicht. Jeder Arbeitsstation ist eine Abbildungsbox zugeordnet, um die empfangenen virtuellen Adressen in eine Schaltanschlußbezeichnung und eine logische Adresse umzuwandeln, wobei diese von einen ersten Schalter an eine aus einer Reihe zweiter Abbildungsboxen weitergeleitet wird, wobei die Umwandlung in die physische Adresse und die Bestimmung des Schaltanschlusses des relevanten Speichermoduls erfolgt. Anforderungen, die von den Arbeitsstationen ausgegeben wurden, um Bereiche in dem gemeinsamen Speicher für einen bestimmten Zugriffstyp - Fähigkeiten - zu erwerben, zu laden, frei zugeben, oder, um auf diese Bereiche über logische Adressen zuzugreifen, werden über eine Schalthierarchie unter Einbeziehung eines zentralen Kommunikationsprozessors verarbeitet.

Aufgaben der Erfindung

Es ist deshalb eine Aufgabe der Erfindung, einen gemeinsamen intelligenten Speicher zu entwickeln, der einen einfachen und flexiblen Speicherzugriff in einer Multiprozessorumgebung auf eine Weise ermöglicht, die es den Benutzern oder Multiprozessoren erlaubt, über den gemeinsamen Speicher mit einem optimierten Wert an Transparenz gegenüber der physischen Lage von Informationen im Speicher zu kommunizieren.
Es ist eine andere Aufgabe der Erfindung, Mittel für die Auflösung des Managementproblems für den Platz innerhalb des gemeinsamen Speichers bereit zustellen, womit der Speicherplatz automatisch den Bedürfnissen des Benutzers zugewiesen wird.
Es ist eine weitere Aufgabe der Erfindung, die Benutzer oder Prozessoren mit einem Satz höherer Befehle für den Zugriff auf den gemeinsamen Speicher auszustatten, wobei jeder Benutzer den gemeinsamen Speicher als logische zentralisierte Einrichtung sieht, auch wenn die zugeordnete Hardware physisch verteilt ist.

Zusammenfassung der Erfindung

Diese Aufgaben wurden durch den gemeinsamen intelligenten Speicher, wie er Anspruch 1 definiert wurde, gelöst.
Die Vorrichtung gemäß der Erfindung wird für die Verbindung der Prozessoren einer Vielzahl Speicherbenutzer MU (11A, ... 11 N) genutzt, die über ein Verbindungsnetzwerk NW(15) mit einem gemeinsamen Speicher PM verkettet sind. Dieser besteht aus einer Vielzahl Speicherbänke MB (17A, ... 18N), die einen globalen gemeinsamen Speicherplatz festlegen, in dem die Speicherbenutzer auf den Speicher über einen Satz höherer Befehle zugreifen. Diese werden von den Speicherbenutzern MU (11A, ... 11N) für das Speichern und Wiederherstellen von Sätzen auf den/vom Speicherplatz ausgegeben, wobei die höheren Befehle nur logische Adressen LRA der Sätze nutzen.
Es enthält:
- dezentrale Speicherschnittstellenmittel (13A, ... 13N), wobei eine Speicherschnittstelle MI jedem Benutzer zugeordnet ist, um den Speicherbänken MB (17A, ... 17N) den Satz höherer Befehle über das Netzwerk NW (15) zu übergeben, sowie eine Speicherschnittstelle MI (13A, ... 13N) die Befehlsanforderung von seinem zugehörigen Speicherbenutzer MU durch Ausführung der folgenden Schritte verarbeitet:
- Lesen eines Speichersteuerwortes MCW von einem lokalen Speicher LN(91) eines Benutzers und dessen Decodierung;
- unabhängiges Auswählen einer der Speicherbänke MB (17A, ..., 17N);
- Herstellung einer Verbindung über ein Verbindungsnetzwerk NW (15) mit der ausgewählten Speicherbank;
- Senden des Befehls zu der ausgewählten Speicherbank und, bis zum Eintreffen einer Befehlsbestätigung MSW von der MB, Freigeben der Verbindung zu der Speicherbank;
- dezentrale Verarbeitungsmittel (12, 103, 107, 109, 111), die in jeder Speicherbank MB (17A, ... 17N) integriert sind, um die physischen Adressen der Datensätze gemäß ihrer logischen Adressen LRA wiederherzustellen und ausführen der höheren Befehle.
Während die Sicht des Benutzers auf den PM der Sicht auf eine logisch zentralisierte Einrichtung entspricht, die auf Datensätzen arbeitet, die alle durch logische Adressen festgelegt sind (z.B. Logischen Satzadressen, LRA), kann die zugehörige Hardware physisch verteilt werden, wobei eine grobe Struktur in Ausdrükken der Leistungsfähigkeit, Kapazität und Kosten geliefert wird.
Der PM gemäß der Erfindung löst das Problem der Speicherplatzverwaltung ebenfalls in solchen Sätzen, die aus einer Vielzahl verketteter Puffer innerhalb einer MB zusammengesetzt sind, sowie von der PMCE dynamisch erzeugt (und verbundenem Speicherplatz zugewiesen) und auf Anforderung von einer MU freigegeben wurden.
Wenn man die Struktur der PM gemäß der Erfindung betrachtet, ist es von Interesse, die Last oder Nutzung der MBs durch die MUs auszugleichen. Dieses Problem, das unabhängig zu dem in der gegenwärtigen Patentanmeldung besteht, findet eine Lösung in der ebenfalls anhängigen Patentanmeldung Nr. 88480101.0 mit der Veröffentlichungsnummer EP-A-0 374 337 und betitelt mit "Load balancing technique in shared memory with distributed structure".
Weitere Figenschaften und Vorteile der Erfindung werden aus der folgenden detaillierten Beschreibung einer bevorzugten Ausführungsform in Verbindung mit den zugehörigen Zeichnungen offensichtlich.

Kurzbeschreibung der Zeichnungen

Fig. 1 ist ein Blockdiagramm der gesamten Konfiguration eines Mehrbenutzersystems mit gemeinsamen Speicher, in dem die Erfindung eingesetzt wird.
Fig. 2 ist eine schematische Darstellung des Informationsflusses und der Schritt folge für einen Speicherzugriff in dem System von Fig. 1.
Fig. 3A zeigt das Format einer Logischen Satzadresse (LRA).
Fig. 3B zeigt das Format des Adressverschiebung D in einem Datensatz.
Fig. 4A zeigt die Formate der Befehle und Befehlsbestätigungen, die für die Speicheroperationen in dem System nach Fig. 1 genutzt werden.
Fig. 4B zeigt das Format eines Warteschlangen-Steuerblockes, der in einigen der in Fig. 4A dargestellten Befehle genutzt wird.
Fig. 5 zeigt die Formate der Speichersteuerblöcke, die in dem lokalen Speicher des Benutzers gespeichert sind und für die Informationsübertragung zwischen dem Benutzer und dessen Speicherschnittstelle benutzt werden.
Fig. 6 ist ein Blockdiagramm der Speicherschnittstelle (MI) die den Benutzer und den gemeinsamen Speicher in dem System von Fig. 1 miteinander verbindet.
Fig. 7 ist ein Flußdiagramm der Verarbeitung der Speicherbefehle in der Speicherschnittstellenlogik.
Fig. 8 zeigt eine schematische Darstellung der prinzipiellen Betriebsweise eines ENQUEUE- oder DEQUEUE-Befehls.
Fig. 9 zeigt eine schematische Darstellung einer Warteschlange, in der die ENQUEUE/DEQUEUE-Befehle aus Fig. 8 ausgeführt werden.
Fig. 10 ist ein Blockdiagramm des Steuerprogramms für Paketspeicherbefehle und des Datenspeichers in einer Speicherbank.
Fig. 11A ist eine schematische Darstellung eines LRA Verzeichnisses, das für die Übersetzung von logischen in physische Adressen benutzt wird.
Fig. 11B ist eine schematische Darstellung einer in Fig. 10 gezeigten Liste freier Puffer FBL.
Fig. 11C ist eine schematische Darstellung einer in Fig 10 gezeigten Liste freier Token.

Detaillierte Beschreibung der Erfindung

1. Systemüberblick
Fig. 1 zeigt die Konfiguration für ein System in dem die gegenwärtige Erfindung zur Anwendung kommt. Prinzipiell ist dies ein System, in dem mehrere Benutzer mit Mehrfachspeicherbänken (Speichermodulen) verbunden sind, die als gewöhnlicher (oder gemeinsamer) Speicher für den ganzen Satz der Benutzer wirken. Eine derartige Anordnung wird z.B. in Kommunikationssteuereinbeiten benutzt, in denen die gegenwärtige Patentanmeldung eine vorteilhafte Anwendung findet.
Jeder Speicherbenutzer MU (11A, 11B, ... 11N) wird über seine eigene Speicherschnittstelle MI (13A, 13B, ... 13N) mit einem gemeinsamen Verbindungsnetzwerk NW (15) verbunden. Die Speicherbänke MB (11A, 11B, ... 11N) sind identische Einheiten, die einzeln mit dem Verbindungsnetzwerk verbunden sind.
In einem weniger vorteilhaften System können alle Speicherbänke MB (11A, 11B, ... 11N) innerhalb eines einzelnen gemeinsamen Speichers, dargestellt durch eine gepunktete Linie (10), angeordnet werden, wobei diese Lösung jedoch vom Standpunkt der Zuverlässigkeit aus betrachtet schlechter wäre und in der Beschreibung nicht weiter berücksichtigt wird. Die gleiche Bemerkung kann für eine aufgeteilte Speicherschnittstelle MI (13A, 13B, ... 13N) gegenüber einer einzelnen Speicherschnittstelle gemacht werden. Fig. 1 zeigt desweiteren ein Steuerprogramm für Paketspeicherbefehle PMCE (12A, 12B, ... 12N), das in jede Speicherbank für die Ausführung der von den Speicherbenutzern übergebenen höheren Befehle integriert ist. Dessen Struktur wird später beschrieben.
Das Verbindungsnetzwerk ist ein Packetschalter mit mehrfachen Anschlüssen, das als Antwort auf Datenpakete, die an einem dieser Anschlüsse eingegeben wurden, diese Datenpakete zu dem benötigten Ausgangsanschluß leiten kann. Derartige Netzwerke sind bekannt und wurden z.B. in den folgenden Veröffentlichungen und der darin zitierten Literatur beschrieben. T. Feng: "A Survey of Interconnection Networks"; Computer (IEEE), Dezember 1981, S. 12 bis 30. V.P. Kumar u.a.: "Augmented Shuffle-Exchange Multistage Interconnection networks"; Computer (IEEE) Juni 1987, S. 30 bis 40.
Der Vorteil der gesamten Anordnung ist, daß sie modular erweitert werden kann (solange das Verbindungsnetzwerk eine ausreichende Kapazität und genug Anschlüsse besitzt). Die Anzahl der Speicherbänke kann an die Anzahl der Benutzer und deren Speicheranforderungen angepaßt werden. Ohne das Einsatzgebiet der Erfindung einzuschränken wird hier vorausgesetzt, daß die Anzahl der Speicherbänke N = 8 beträgt.
Der gesamte Fluß der Befehle und Kontrollinformationen für die Speicherzugriffe ist schematisch im Diagramm der Fig. 2 dargestellt.
Der Speicherbenutzer MU bereitet ein Speichersteuerwort MCW vor, das die angeforderte Operation und die enthaltenen Parameter genau angibt. Das MCW wird zu der Speicherschnittstelle MI übertragen, die die Befehlsanforderung verarbeitet und einen Befehl an eine der Speicherbänke MB sendet. Der Befehl wird vom PMCE der MB ausgeführt (Speichern von Daten, Lesen von Daten, usw.) und eine Befehlsbestätigung an die MI zurückgegeben. Die MI bereitet Statusdaten vor, die die von der MB empfangene Bestätigung widerspiegeln und mögliche weitere Statusdaten widerspiegeln, wie die Speicheroperation abgeschlossen wurde. Diese Statusdaten werden in einem Speicherstatuswort MSW an die NU übertragen.
Der Ausdruck "Befehl", wie er in der folgenden Beschreibung benutzt wird, bestimmt eine Anfrage nach einer höheren Speicheroperation, die von einem Speicherbenutzer/von einer Speicherschnittstelle an eine Speicherbank gesandt wird (wie etwa Anlegen, Bringen/Holen, Freigeben, Einreihen in eine Warteschlange, Entfernen aus einer Warteschlange) und sich grundsätzlich von den bekannten Schreib-Lese-Speicberoperationen unterscheidet.
Die Formate der Befehle und Befehlsbestätigungen, der MCW und der MSW werden später in Verbindung mit den Fig. 4 und 5 detailliert erläutert.
Die Befehlsverarbeitung (z.B. Darstellung, Formatierung) wird von einer logischen Schicht (in der MI) erledigt, die nach unten ein Schnittstelle zu dem Speicherbenutzer MU hat, die einen Schreib-/Lesezugriff auf den lokalen Speicher der MU erlaubt, und nach oben eine andere Schnittstelle zu dem Verbindungsnetzwerk NW besitzt. Einzelheiten der MI-Logik und deren Wirkungsweise werden später in Verbindung mit den Fig. 6 und 7 beschrieben.
Es muß festgehalten werden, daß ein Prinzip, das für das gegenwärtige System vorausgesetzt wird, darin besteht, daß die Verteilung der Benutzerdaten unter den Speicherbänken willkürlich ist, d.h., es gibt keinen festen Zusammenhang oder keine vorher festgelegte Zuweisung zwischen Speicherbänken und Benutzern, die physische Speicherzuweisung ist für die Letzteren transparent. Jedoch ein Problem, das aus diesem Prinzip erwächst, ist, daß die Speicherbänke ungleichmäßig benutzt (belastet) werden können. Es könnten somit einige Speicherbänke vollständig mit Daten gefüllt sein, während andere überhaupt nicht genutzt werden. Dies kann zu Überlastungen, unnötigen Wartezeiten und zum Verlust der Parallelität führen, was solange vermieden werden kann, wie der gesamte verfügbare Speicherplatz für alle zu speichernden Daten ausreichend ist. Dieses spezifische Problem wurde in der oben zitierten anhängigen Patentanmeldung Nr. 88480101.0 mit der Veröffentlichungsnummer EP-A-0 374 377 durch Lastausgleich zwischen allen Speicherbänken gelöst und wird in der gegenwärtigen Beschreibung nicht weiter berücksichtigt.

2. Packetspeicherprinzipien des Betriebes

Jetzt werden die Datenobjekte, die in dem Paketspeicher enthalten sind, und die höheren Befehle, die mit diesen Objekten arbeiten, beschrieben.
Der Paketspeicher enthält zwei Arten von Datenobjekten: Datensätze (R) und Warteschlangen (Q).
Die Datensätze sind benannte Speichergebiete mit adressierbarem Inhalt, die erzeugt, gestrichen, durch den Benutzer über einem später im Detail erklärten Befehlssatz in den Speicher geschrieben und aus dem Speicher gelesen werden.
Ein Datensatz ist durch eine logische Satzadresse (LRA) gekennzeichnet, die durch einem Speicherbenutzer bei der Erzeugung des Datensatzes zugeteilt wird. Physischer Adressraum wird der LRA auf eine Weise zugewiesen, wie es unter Bezugnahme auf Fig. 11A beschrieben wird. Ein Datenbit wird innerhalb eines Datensatzes durch eine Verschiebung D fixiert. Der Inhalt eines Datensatzes wird durch seinen Eigentümer verwaltet; es gibt nichts innerhalb des PM, das hilft herauszufinden, was die darin enthaltenen Daten beinhalten und wo sie sich befinden. Nicht beschriebene Bereiche innerhalb des Datensatzes haben einen nichtvorhersagbaren Inhalt.
In einer besonderen Ausführungsform der Erfindung gibt es 3 Klassen von Datensätzen, die sich in ihrer Kapazität, Zugriffszeit und in ihrem Platzbedarf unterscheiden. Datensätze der Klasse 0 können bis zu 512 Bytes enthalten und haben die kürzeste Zugriffszeit sowie den geringsten Speicherbedarf; Datensätze der Klasse 1 können bis zu 64 KByte enthalten und haben eine mittlere Zugriffszeit und einen mittleren Platzbedarf; Datensätze der Klasse 2 können bis zu 8 MByte enthalten und haben die ungünstigste Zugriffszeit und den ungünstigsten Platzbedarf. Die Klasse des Datensatzes wird von dem Benutzer festgelegt, während er diesen erzeugt. Dies bedeutet nicht, daß die Datensätze von Beginn an 512 Byte, 64 KByte oder 8 MByte große Speicherbereiche sind. Speicherplatz kann auf Bedarfsbasis, wenn Daten in den Datensatz eingebracht werden, zugeteilt werden.
Nach Erhalt eines Datensatz sieht der Benutzer eine lineare Folge logischer Adressen, die durch die Verschiebung D gekennzeichnet sind, wobei diese die logische Adresse eines Bytes eines physischen Datenpuffers darstellt, der beispielsweise eine feste Größe von 512 Byte hat. So werden, für den Benutzer nicht sichtbar, die Datensätze aus Puffern hergestellt (zum Beispiel jeder aus 512 Byte bestehend), wobei diese gemäß einem Schema zusammengesetzt werden, das unter Bezugnahme auf Fig. 10 beschrieben wird.
Die Datensätze werden benutzt, um flüchtige Daten (d.h. Daten, die eine kurze Lebensdauer haben) zu speichern, oder um Systemfunktionen wie etwa das Vermitteln von TP Paketen zu realisieren, aber auch, um feststehende Daten wie etwa Weiterleitungstabellen, Kontrollblöcke, usw. zu speichern.
Der logische Datensatzadresse (LRA) ist ein 4 Byte großer logischer Name, der einen Datensatz innerhalb des Paketspeichers eindeutig kennzeichnet. Dessen Format wird in Fig. 3A gezeigt.
In dem ASID (Adressraumkennzeichner) existiert ein Unterfeld, um die physische PM Bank zu kennzeichnen, die den Datensatz enthält. Er wird von der Speicherschnittstelle MI genutzt, um die passende Bank auszuwählen.
Die Verschiebung D lokalisiert ein Datenbyte innerhalb eines Datensatzes. Dessen Format wird in Fig. 3B gezeigt. Um so länger ein Datensatz (entsprechend seiner Klasse) sein kann, um so mehr Bits werden natürlich für die Definition der Verschiebung D benötigt.
Die oben betrachteten Warteschlangen werden über Datensätze aufgebaut, und sie haben konsequenterweise die gleichen Attribute: Name, maximale Größe. Sie sind aus Elementen fester Größe von 8, 16, 32, 64, 128 oder 256 Byte zusammengesetzt. Die Größe der Elemente wird bei der Erzeugung der Warteschlange festgelegt. Die Größe der Warteschlange wird durch die Größe des Datensatzes begrenzt. In dieser Spezifikation beziehen wir uns über ein Warteschlangentoken QT, das faktisch eine logische Datensatzadresse des darunterliegenden Datensatzes darstellt, auf eine Warteschlange.
Der Zugriff auf die Warteschlange ist als FIFO gestaltet und über die ENQ- und DEQ-Befehle erzeugt worden, die besonders während der Kommunikation von Aufgabe zu Aufgabe genutzt werden und später beschrieben werden.
Um die Warteschlange zu erzeugen, muß der darunterliegende Datensatz erzeugt und ein Steuerblock für die Warteschlange (QCB) mit den Anfangswerten des Zeigers für das Ein- und Ausreihen in bzw. aus der Warteschlange und dem Wert, der mit der Größe der eingereihten Elemente korrespondiert, hinein geschrieben werden. Wenn ein MU die gegenwartige Anzahl der Elemente in einer Warteschlange wissen möchte, kann er deren Steuerblock der Warteschlange über einen GET-Befehl lesen. Eine Warteschlange wird durch Freigeben des darunterliegenden Datensatzes durch einem RELEASE-Befehl freigegeben, der später erläutert wird. Das QCB- Format ist in Fig. 4B dargestellt. Es enthält einen Zeiger E für das Einreihen in eine Warteschlange, wobei dessen Adresse eine Länge von vier Bytes aufweist, einen Zeiger D für das Entfernen aus der Warteschlange, der ebenfalls eine vier Byte lange Adresse besitzt, und die Größe von jedem in der Warteschlange eingesetzten Element (8, 16, 32, 64, 128, 256 Byte), wobei die Wahl der Größe durch maximal ein Byte festgelegt ist.
Der Einsatz der ENQ- und DEQ-Befehle wird am besten unter Bezugnahme auf Fig. 8 verstanden. Diese Figur stellt die Situation dar, bei der ein erster Speicherbenutzer MU1 eine Nachricht M1 an einen zweiten Speicherbenutzer MU2 übertragen möchte, der mit der gleichen Speicherbank MB (17) über das Verbindungsnetzwerk (nicht dargestellt) verbunden ist.
Der MU1 legt deshalb die Nachricht M1 in einem Datensatz (r) innerhalb der MB unter Nutzung des PUT-Befehls (Schritt 1) ab. Da in diesem Zustand MU2 den Bezug der logischen Datensatzadresse, unter der M1 in MB abgelegt ist, nicht kennen kann, ist es notwendig, daß MU1 diese Angabe an MU2 über den ENQ-Befehl selbst übergibt (Schritt 2) . Dieser Befehl bewirkt, daß ein Element fester Größe ml in eine Warteschlange Q an einer Stelle, die von einem Zeiger für das Einreihen E angezeigt wird, eingereiht wird.
Es soll festgehalten werden, daß, wenn andere Nachrichten M2, M3, ... von MU1 an die MB übertragen werden, die zugehörigen Elemente der Warteschlange m2, m3 auf FIFO-Grundlage eingereiht (und später ausgereiht) werden, und der ENQ-Zeiger dementsprechend wie in Fig. 9 dargestellt, verschoben wird.
Wenn MU2 den Inhalt der Warteschlange Q (zum Beispiel über eine übliche Abfragemethode) überprüft, wird er das Element ml aus der Warteschlange entfernen (Schnitt 3), welches die logische Adresse des Nachrichtensatzes M1 angibt. Dann (Schnitt 4) wird ein von MU2 erteilter GET-Befehl es ihm erlauben, den gesamten Satz M1 zu lesen.
Dieses eben beschriebene Kommunikationsschema zwischen den Speicherbenutzern MU1 oder MU2 ist für die Task-zu-Task-Kommunikation zwischen den Speicherbenutzern besonders geeignet.
Es soll ebenfalls festgehalten werden, daß keine Verschiebung durch die ENQ-/DEQ-Befehlen festzulegen ist, da die ENQ-/DEQ- Befehle unter Bezug auf die Warteschlangenelemente m1, m2, ... vom FIFO-Typ sind.
Fig. 9 zeigt weiterhin den Aufbau einer Warteschlange, die aus einem Warteschlangen-Steuerblock QCB und einem bestimmten logischen Adressraum (A, B) besteht, wobei dieser mit der Größe der gesamten logischen Datensatzadressen (m1, m2, ...) der eingereihten Datensätze oder Nachrichten M1, M2, ... korrespondiert.
Die aufeinanderfolgenden Positionen E1, E2, ... En des Zeigers für das Einreihen in eine Warteschlange E werden ebenso wie die zugehöhri gen nacheinander eingereihten Warteschlangenel emente m1, m2, ... mn dargestellt.
Der Befehl zum Entfernen aus der Warteschlange bewirkt das Löschen der Warteschlangenelemente, die sich hinter dem DEQ-Zeiger D befinden. Da der Adressraum der Warteschlange durch (A,B) begrenzt ist, wird das Warteschlangenelement m(n+1) ganz vorn in die Warteschlange, direkt nach Position A eingereiht, wenn der ENQ-Zeiger E die Position En+1 erreicht.
Es soll festgehalten werden, daß für den Fall, das mehr Befehle zum Entfernen aus der Warteschlange als zum Einreihen in die Warteschlange über einen Zeitraum ausgeführt werden, der DEQ- Zeiger D für das Entfernen aus der Warteschlange die gegenwärtige Position des ENQ-Zeigers E erreicht, was wiederum bedeutet, daß die Warteschlange bis auf einen minimalen durch den QCB festgelegten Inhalt leer ist.
Natürlich sind die Positionen der E- und D-Zeiger nur dem Steuerprogramm für Datenspeicherbefehle und nicht den Speicherbenutzern bekannt, für die die ENQ/DEQ-Befehle ähnlich den höheren CREATE/PUT/GET/RELEASE-Befehlen transparent sind.
Es soll schließlich festgehalten werden, daß, da der unter einer Warteschlange liegende Datensatz dem Bedarf entsprechend wächst, dies genauso für die Größe der Warteschlangen gilt, die von der Anzahl der zwischen den Speicherbenutzern zu übertragenden Nachrichten abhängen.

3. Funktionen der Speicherschnittstelle und Befehlsformate

Die Aufgabe jeder Speicherschnittstelle MI besteht darin, jedem Speicherbenutzer MU eine dezentralisierte Standard-Speicherschnittstelle zu liefern. Diese befaßt sich mit den Speicherbefehlen, die durch den Speicherbenutzer MU wie folgt dargestellt werden. Sie wählt die zugehörige Speicherbank MB (zum Beispiel unter Nutzung einer lastausgleichenden Technik), bereitet eine Verbindung zu der Speicherbank MB über das Verbindungsnetzwerk NW vor, bildet und sendet einen Befehl (der auch Daten enthalten kann) über diese Verbindung, wartet auf eine Bestätigung des Befehls (der in einigen Fällen ebenfalls Daten von der MB enthalten kann), gibt die Verbindung frei und erzeugt für den Speicherbenutzer MU Statusdaten über den Abschluß.
Jeder Befehl setzt sich aus einem 12-Byte-Vorsatz (dargestellt in Fig. 4A), gefolgt von einem optionalen Datenfeld, zusammen. Jede Bestätigung eines Befehls setzt sich aus einem optionalen Datenfeld, gefolgt von einem 5-Byte Nachsatz zusammen.
Den Befehlen kann ein Anfangsbegrenzer (SD) vorangehen und sie können von einem Befehlsendebegrenzer (EOC) gefolgt werden. Diese sind nicht dargestellt.
Insgesamt sechs unterschiedliche Speicherbefehle und zugehörige Befehlsbestätigungen sind vorgesehen und werden im folgenden kurz beschrieben, wobei deren Realisierung durch das PMCE später unter Bezug auf die Fig. 10 und 11 beschrieben wird.
CREATE (Format: nur Cmd)
Dieser Befehl, erteilt von einem gegebenen Speicherbenutzer MU, bewirkt die Erzeugung von einem REKORD (einer logischen Speichereinheit) in dem gemeinsamen Speicher und der Zuordnung einer logischen Datensatzadresse (LRA) zu diesem RECORD. Die LRA ist ein im System einheitlicher Bezug, der es erlaubt, den Speichersatz aus dem gemeinsamen Speicher wiederzugewinnen.
Durch diesen Befehl wird einem neuen Satz (solange wie es keine darin zu speichernden Daten gibt) kein Speicherplatz zugewiesen.
Die Befehlsbestätigung gibt die LRA an die jeweilige Speicherschnittstelle MI zurück.
PUT (Format: Cmd, LRA, D, Daten)
Der PUT-Befehl bewirkt, daß die Daten, die er mit sich führt, in den durch seine LRA spezifizierten Satz bei der spezifizierten Verschiebung D geschrieben werden. Dem Satz wird dynamisch genügend Speicherplatz zugeteilt (wenn der PUT-Befehl ausgeführt wird), so daß die Daten gespeichert werden können.
Die Befehlsbestätigung bringt keine bestimmten Daten zu der Speicherschnittstelle MI zurück (mit Ausnahme des Rückgabecodes, die in jeder Befehlsbestätigung enthalten ist)
GET (Format: Cmd, LRA, D, N)
Der GET-Befehl bewirkt das Lesen von N Daten von einem durch seine LRA festgelegten Satz bei der festgelegten Verschiebung D.
Die Befehlsbestätigung trägt die N Datenbytes von der Speicherbank zurück zu der Speicherschnittstelle MI.
RELEASE (Format: Cmd, LRA)
Der RELEASE-Befehl bewirkt das Streichen des durch die LRA gekennzeichneten Satzes und das Freigeben des zugehörigen Speicherplatzes der MB.
Die Befehlsbestätigung enthält keine speziellen Daten (mit Ausnahme des Rückgabecodes).

Aufbau des Rückgabecodes und des Last-Status-Anzeigers

Der Rückgabecode, der Teil von jeder von einer Speicherbank zurückgegebenen Befehlsbestätigung ist, ist ein 8-Bit-Byte mit dem folgenden Aufbau: Die ersten vier Bits RRRR sind ein spezieller Code, der den Abschlußstatus des jeweiligen Speicherbefehls anzeigt.
Die verbleibenden Bits sind frei oder können als Anzeige für den Last-Status einer gegebenen Speicherbank genutzt werden.

ENQ(QT, Daten)

Die Wirkung dieses höheren Befehls wurde unter Bezugnahme auf die Figuren 8 und 9 beschrieben. QT bestimmt ein Warteschlangen- Token, das faktisch die logische Satzadresse des Satzes, auf dem die Warteschlange aufgebaut ist, darstellt.
Der ENQ-Befehl umfaßt verschiedene Schritte, die aus den GET- und PUT-Befehlen gebildet werden die durch das PMCE ausgeführt wurden. Als Konsequenz kann das PMCE während der Ausführung des Befehls nicht durch einen PUT- oder GET-Befehl gestört werden, der von einem Speicherbenutzer MU ausgeführt wird. Die Schritte eines ENQ-Befehls sind die Folgenden:
1. Das PMCE erzeugt einen GET-Befehl, wobei LRA gleich dem Warteschlangen-Token QT ist und die spezifische Verschiebung mit der Verschiebung des E-Zeigers innerhalb des QCB korrespondiert.
2. Das PMCE erzeugt einen PUT-Befehl, wobei LRA gleich QT sowie D gleich der Verschiebung von E in dem QCB ist, und die Daten, die mit dem PUT-Befehl bearbeitet werden sollen, die einzureihenden Warteschlangenelemente (m1, m2, ...) sind.
3. Das PMCE führt einen PUT-Befehl aus, wobei LRA = QT, D = Verschiebung von E in QCB und Daten = E + 32 (wenn 32 die Größe eines Warteschlangenelementes ist), wobei dies eine Aktualisierung des Zeigers E für das Einreihen in eine Warteschlange nach dem Befehl für das Einreihen bewirkt.

DEQ (QT)

Dieser Befehl wird benutzt, um ein Element M aus einer Warteschlange zu entfernen. Er ist ebenfalls ein höherer Befehl, der GET- und PUT-Befehle nutzt, und wird unten zusammenfassend mit seinen Parametern aufgeführt:
1. GET (LRA = QT; D = 0, N = 9): bewirkt ein Lesen der gesamten QCB.
2. GET (LRA = QT; D = Verschiebung von DEQ PTER; N = 32)
3. PUT (LRA = QT; D = Verschiebung von DEQ PTR; D +32)
4. Freigeben eines Puffers vom Speicherplatz: derjenige, der das Element enthielt, das gerade aus der Warteschlange entfernt wurde.

4. Speicherbenutzer und Speichersteuerblöcke

Den Speicherbenutzer MU kann man als einen Mikroprozessor mit seinem Hauptspeicher betrachten, den man als lokalen Speicher LM (91) der MU bezeichnet. Dies wird in Fig. 6 dargestellt. Die Speicherbefehle bewegen Daten zwischen dem gemeinsamen Speicher (die Gesamtheit aller Speicherbänke MB) und dem lokalen Speicher (91) des MU.
Der Informationsaustausch zwischen einem Speicherbenutzer MU und dessen Speicherschnittstelle MI wird über die Speichersteuerblöcke beeinflußt, deren Formate in Fig. 5 dargestellt sind.
Ein Speicherbefehl wird von einem Speicherbenutzer MU als ein Steuerblock übergeben, der "Speicherbefehlswort" (MCW) genannt wird und im lokalen Speicher des Speicherbenutzers NU vorbereitet wird. Das MCW enthält Steuerinformationen, die den Typ des Speicherbefehls (CREATE, GET, ...), die logische Satzadresse (LRA), die Datenverschiebung (D) innerhalb des Satzes, die Datenanzahl (N), und die Adressen des Datengebiets innerhalb des lokalen Speichers des MU (lokaler Speicherzeiger LMP) kennzeichnen.
Die Abschluß-Statusdaten werden von der Speicherschnittstelle MI dem Speicherbenutzer MU als Steuerblock in den lokalen Speicher des MU übergeben: das "Speicherstatuswort" (MSW). Die Statusdaten enthalten Informationen (CC) darüber, ob die Befehlsausführung erfolgreich war oder nicht. In dem Fall eines CREATE-Befehls enthält das MSW ebenfalls die logische Satzadresse LRA des erzeugten Satzes.

5. Speicherschnittstellenlogik

Ein Blockdiagramm der Speicherschnittstellenlogik wird in Fig. 6 dargestellt. Dessen Elemente und Aufbau sind wie folgt:
Die MI enthält grundsätzlich einen zentralen Teil 31, einen Anschluß 33 für das Verbindungsnetzwerk (NW), einen DMA-Teil oder Benutzeranschluß 35 und einen Steuerabschnitt 37.
Der zentrale Teil 31 umfaßt eine ALU 41, ein Akkumulator-Register (ACCU), einen lokalen Speicher LS 45 und ein lokales Speicheradressregister LSAR 47. Ein A-Bus 49 und ein B-Bus 51 sind mit den Einheiten der ALU verbunden und ein Ergebnisbus 53 ist mit dem Ausgang der ALU verbunden. Die Eingangsdaten an dem LS werden über die Leitungen 55, 57 und 59 und die Ausgangsdaten von dem LS werden über Leitung 61 übertragen.
Der NW-Anschluß 33 enthält vier Register und einen Zähler. Das NW-Dateneingangsregister (NWDI) 63 ist zwischen die LS-Ausgangsleitung 61 und einen Zweiwege-NW-Datenbus 65 geschaltet. Das NW Datenausgangsregister (NWDO) 67 ist zwischen die LS-Dateneingangsleitung 55 und den NW-Datenbus 65 geschaltet. Das NW-Eingangssteuer- (NWCI) Register 69 ist zwischen den ALU-Ergebnisbus 53 und eine NW-Steuereingangsleitung 71 geschaltet. Das NW-Ausgangssteuer- (NWCO) Register 73 ist zwischen den A-Bus 49 und eine NW-Ausgangssteuerleitung 75 geschaltet. Ein NW-Zähler (NWCT) 77 empfängt seine Eingangsdaten vom ALU-Ergebnisbus 53. Sein Inhalt kann um eine Einheit erhöht (oder verringert) werden, wenn ein Byte vom Netzwerk empfangen (oder zu ihm geliefert) wurde, und er kann auf den Inhalt null getestet werden.
Der Benutzeranschluß 35 enthält drei Register und einen Zähler: Das MU-Dateneingangs- (MUDI) Register 79 ist zwischen die LS- Eingangsleitung 57 und den Zweiwege-Benutzerdatenbus 81 geschaltet. Das MU-Datenausgabe- (MUDO) Register 83 ist zwischen die LS-Ausgangsleitung 61 und den Benutzerdatenbus 81 geschaltet. Das MU-Adress- (MUA) Register 85 ist zwischen den ALU-Ausgabebus 53 und eine Benutzerausgabeleitung 87 geschaltet. Ein MU-Zähler (MUCT) 89 empfängt seine Eingangsdaten vom ALU-Ergebnisbus 53. Der Inhalt kann um eine Einheit verringert werden, wenn ein Byte vom Benutzer empfangen (oder zu ihm geliefert) wurde, und er kann auf den Inhalt null getestet werden.
Der Steuerabschnitt 37 liefert die folgenden Daten oder Steuersignale:
IF = anliegendes Feld (LS-Operant oder LS-Adresse)
ALUOP = ALU-Bearbeitungs-Code (Addition, Subtraktion, AND, OR, XOR, Rotieren, ...)
ABS = A-Bus Quelle
BBS = B-Bus Quelle
LSOP = LS-Bearbeitungs-Code (Lesen, Schreiben, NOOP)
LSA = LS-Adressteuerung
MISC = verschiedene Steuerungen für das Beschreiben der Register, Starten der DMA, usw.
Die NI-Logik hat die folgenden Fähigkeiten:
1) Die MI-Logik kann arithmetische und boolesche Operationen an zwei Operanten durchführen, wobei einer einen unmittelbaren Wert (IE) hat, der von dem Steuerbereich erzeugt wurde, und der zweite den Inhalt eines LS-Platzes oder eines Steuerregisters hat.
2) Die NI-Logik hat Schreib/Lese-Zugriff auf den lokalen Speicher LM (91) des MU, auf die lokale Speicheradresse und die Byteanzahl, die jeweils in dem Adressregister des MU (MUA) und dem Zählregister des MU (MUCT) spezifiziert sind. Die Quelle der Daten während des Schreibens (oder das Ziel während des Lesens) ist der LS, der von dem LS-Adressregister (LSAR) adressiert wird.
3) Die MI-Logik kann eine Verbindung zu einer Speicherbank MB über das Verbindungsnetzwerk NW durch Laden einer Verbindungsanfrage und der MB-Adresse (Bezeichner) in das "NW-Steuereingangsregister" (NWCI) und dem Warten auf eine Verbindungseinwilligung, die von dem "NW-Steuerausgangsregister" (NWCO) zurückgegeben wird, aufbauen. Die Verbindung kann auf einem ähnlichen Weg durch Laden einer Anfrage auf Freigabe der Verbindung in das NWCI und Warten auf eine Bewilligung, die in das NWCO zurückgegeben wird, freigegeben werden. Das Verbindungsnetzwerk NW wird nicht weiter beschrieben, da es nicht Gegenstand der gegenwärtigen Erfindung ist (Veröffentlichungen, die das Verbindungsnetzwerk beschreiben, wurden weiter oben in Abschnitt 1 berücksichtigt). Wenn die Verbindung zu einer Speicherbank MB erstellt wurde, kann die MI-Logik eine Zweiwege-Datenübertragung über diese Verbindung herstellen: vorausgesetzt, das LSAR wurde mit dem Wert A und das NW-Zählregister (NWCT) mit dem Wert N initialisiert, werden die N Bytes, die sich bei LS(A) befinden, ausgelesen und zu der MB gesandt. Diese eingebundene Datenübertragung endet mit NWCT = 0 und LSAR = A + N. Die MB soll dann eine Zeichenfolge von Bytes zurückgeben, die empfangen werden und in das LS beginnend bei Adresse A+N gespeichert werden. Die Anzahl der empfangenen Bytes ist in dem NWCT bei Beendigung der abgehenden Übertragung verfügbar. Auf diese Weise werden die Befehle und Befehlsbestätigungen zwischen der Speicherschnittstelle MI und einer Speicherbank MB ausgetauscht.

6. Befehlsverarbeitung durch die Speicherschnittstellenlogik

Das Ablaufdiagramm von Fig. 7 illustriert die Schritte, die während der Befehlsverarbeitung in der Speicherschnittstellen- (MI) Logik ausgeführt werden. Es zeigt sich insbesondere, wie die Speicherbenutzungs- (Speicherlaststatus) Informationen, die ein wichtiger Teil der Lastausgleichstechnik ist, während der Verarbeitung der Speicherbefehle gehandelt wird, wobei dies jedoch nicht unbedingt für die gegenwärtige Erfindung notwendig ist.
Schritt A: Die MI liest das Speichersteuerwort MCW aus dem lokalen Benutzerspeicher LM (91) (unter Benutzung von DMA-Techniken) und speichert das MCW in seinem eigenen lokalen Speicher LS. Anschließend decodiert sie den Befehl. Abhängig von der Tatsache, ob der Befehl ein CREATE-Befehl ist oder nicht, wird als nächstes einer von zwei unterschiedlichen Schritten ausgeführt.
Schritt B1 (Befehl = CREATE) : Eine der Speicherbänke wird entsprechend der Last-Ausgleichstechnik ausgewählt (Auswahl wird in Abschnitt 7 beschrieben). Eine die gegenwärtige Speicherbank festlegende CMB-Variable (weiter unten erläutert) wird vorbereitet.
Schritt B2 (Befehl = anders als CREATE) : Die Speicherbank MB, die für diesen Befehl benutzt wird, wird durch das LRA-Feld des MCW festgelegt. Vgl. die Anmerkungen in Abschnitt 7b weiter unten. Eine CMB-Variable (die gegenwärtige Speicherbank festlegend) wird vorbereitet.
Schritt C: Die MI baut eine Verbindung über das Verbindungsnetzwerk NW zu der Speicherbank auf, die durch den gegenwärtigen CMB bestimmt wurde. In dem lokalen Speicher LS wird ein Befehl vorbereitet. (Details werden hier nicht gegeben, da dies für die Erfindung nicht wesentlich ist). Die Startadresse des Befehls im LS wird in das LSAR eingegeben und die Byteanzahl des Befehls wird in das Register NWCT geladen. Dann wird der Befehl zu der ausgewählten Speicherbank MB gesandt. Die Rückgabe einer Befehlsbestätigung von der MB wird erwartet.
Schritt D: Die Befehlsbestätigung wird verarbeitet, wenn sie in der MI empfangen wurde (Details werden hier nicht gegeben, da dies für die Erfindung nicht wesentlich ist).
Schritt E: Jetzt bereitet die MI das Speicherstatuswort MSW in seinem lokalen Speicher LS vor (unter Nutzung der Informationen, die mit der Befehlsbestätigung empfangen wurden). Dann lädt sie die LS-Adresse, bei der das MSW beginnt, in das LSAR und die Byteanzahl des MSW in den Zähler MUCT und kopiert das MSW von dem LS in den lokalen Speicher des Benutzers. Schließlich wird die Verbindung über das Verbindungsnetzwerk zu der MB freigegeben.

7. Auswahl der Speicherbank durch die Speicherschnittstelle

Es gibt zwei unterschiedliche Situationen, wenn eine Speicherschnittstelle MI eine Speicherbank MB für die Ausführung eines Speicherbefehls auszuwählen hat: (a) für einen CREATE-Befehl wird eine neue Speicherbank ausgewählt; (b) für alle anderen Speicherbefehle ist die Speicherbank bekannt (von dem LRA-Parameter) und die MI kann diese MB identifizieren.

a) Auswahl einer MB entsprechend der Lastausgleichstechnik

Die Auswahl einer Speicherbank MB für die Erzeugung eines neuen Datensatzes wird bevorzugterweise durch die Lastausgleichstechnik gemacht, die die Kenntnis über den Speicherlaststatus nutzt, der an jeder Speicherschnittstelle MI wie vorher erläutert, verfügbar ist. Die Lastausgleichstechnik ist Aufgabe der anhängigen Beschreibung Nr. 88480101.0 mit der Veröffentlichungsnummer EP-A-0 374 337, die hier nicht weiter beschrieben wird.

b) Auswahl einer MB, wenn die LRA bekannt ist, d.h. für einen anderen Befehl als CREATE

Die LRA, die von der MB auf einen CREATE-Befehl zurückgegeben wird, ist ein 32-Bit-Kennzeichner, in dem die Bits 8, 9 und 10 einen Code enthalten, der die MB spezifiziert (000 kennzeichnet die MB-Nummer 0; 001 kennzeichnet die MB-Nummer 1; usw.).
Deshalb weiss die MI-Logik, welche MB sie für die Errichtung der Verbindung hat.
Die Auswahl einer MB für andere Befehle als CREATE besteht aus der Identifizierung des LRA-Feldes in dem MCW (das gerade in den LS während des vorherigen CREATE-Befehls kopiert wurde), dem Herausnehmen der Bits 8 bis 10, dem Übersetzen dieses drei-Bit- Codes in das acht-Bit Format, das in der CMB benutzt wird und dem Laden des resultierenden Wertes in die CMB. Dies wird von einer sehr einfachen Hardware erledigt, die nicht weiter beschrieben wird.

8. Aufbau des PMCE

Fig. 10 zeigt den Gesamtaufbau des PMCE (12) und des Datenspeicher- (103) Abschnitts oder des RAW MEMORY einer Speicherbank.
Ein Speicherbenutzer MU (11), eine Speicherschnittstelle MI (13), ein Verbindungsnetzwerk NW (15) und ein Netzwerkanschluß (33) ähnlich dem unter Bezug auf Fig. 6 beschriebenen sind ebenfalls schematisch dargestellt, um die Verbindung zwischen dem Datenspeicher (103), dem PMCE (12) und dem Rest der in Fig. 1 gezeigten Vorrichtung zu zeigen.
Das PMCE enthält grundsätzlich einen Mikroprozessor (101) für die Verarbeitung der höheren Befehle, die von dem Speicherbenutzer geliefert werden, wobei die Verarbeitung von Mikroprogrammen erledigt wird, die sich in einem Programmspeicher (117) befinden. Die Schritte der befehlsabhängigen Mikroprogramme werden später detaillierter erläutert.
Das PMCE (12) umfaßt weiterhin eine mit dem Datenbus (104) verbundene lokale Speichereinheit LS (113), einen Adressbus (106) und einen Steuerbus (108) des Mikroprozessors (101). Die gleichen Busse werden parallel zum Datenspeicher (103) und Netzwerkanschluß (33) geliefert. Die lokale Speichereinheit LS (113) ist faktisch ein Zweiwegespeicher, der mit seinem zweiten Anschluß mit dem Netzwerkanschluß (33) über einen Datenbus (110), einen Adressbus (112) und einen Schreib/Lese-Anschluß verbunden ist. Endlich umfaßt der NW-Anschluß (33) einen Eingangsadresszähler IAC (119), dessen Status von dem Mikroprozessor (101) über Anschluß (116) gelesen wird.
Mit diesem gegebenen Aufbau wird jetzt der Betrieb des PMCE (12) beschrieben.

9. Betriebsweise des PMCE

Wenn ein Speicherbenutzer MU (11) einen höheren Befehl über MI (13), NW (15) und den NW-Anschluß (33) an die lokale Speichereinheit (113) sendet, wird dieser Befehl an den Datenbus (110) geliefert und im LS an die von dem Adressbds (112) spezifizierte Adresse geschrieben. Wenn der übertragene höhere Befehl zum Beispiel ein PUT-Befehl mit einem 12-Byte Befehlskopf ist und N Datenbyte zum Datenspeicher (103) übertragen werden sollen, wird der Kopf, der den Befehlsidentifikationscode enthält direkt zum Mikroprozessor (101) auf dem Bus (102) übertragen. Somit wird Mikroprozessor (10) alarmiert, daß er einen höheren Befehl zu verarbeiten hat und der höhere Befehl wird decodiert, um zu bestimmen, welcher höhere Befehl empfangen wurde. Wenn dies ein PUT-Befehl war, werden die N Datenbytes durch den NW-Anschluß (33) (dieser dient im Gegensatz zu dem NW-Anschluß, der unter Bezug auf Fig. 6 beschrieben wurde, als Slave-Anschluß) und die Busse (102) und (104) zum lokalen Speicher LS (113) übertragen.
Währenddessen wird die Anzahl der von LS (113) empfangenen Bytes von dem Eingangsadresszähler IAC (119) gezählt, und wenn eine bestimmte Anzahl Bytes, die ausreicht, um den Datenspeicherpuffer (115) zu füllen, empfangen wurde, wird der Mikroprozessor (101) über den Befehlsanschluß (118) benachrichtigt. Dies bewirkt, daß der Mikroprozessor mit der Übertragung der empfangenen und in LS (113) gespeicherten Datenbytes zum Datenspeicher (103) beginnt. Wenn der höhere Befehl zum Beispiel ein PUT-Befehl ist, wird der Mikroprozessor die N Datenbytes von dem LS (113), die den PUT-Befehl begleiten, über die Busse (104, 106, 108) lesen und die Daten in den Datenspeicher (103) zu einer Adresse übertragen, die mit der in dem PUT-Befehl spezifizierten logischen Satzadresse korrespondiert. Die physische Adresse der Puffer (115), bei denen die Datenbytes in den Datenspeicher (103) gespeichert werden, werden von einen Adressübersetzungsmechanismus bestimmt, der die physische Pufferadresse beginnend mit der Kenntnis der logischen Satzadresse festlegt. Dieser Übersetzungsmechanismus wird weiter beschrieben.
Es soll festgehalten werden, daß ebenfalls ein Befehlsende (EOC)-Begrenzer erwartet wird, und wenn er innerhalb des NW-Anschlusses 33) decodiert wurde, bevor der Eingabeadresszähler IAC (19) genügend Bytes abgezählt hat, um den Datenpuffer zu füllen, werden die Datenbytes des Befehls, der in LS (113) gespeichert ist, trotzdem von dem Mikroprozessor (101) zum Datenspeicher (103) übertragen, wobei Letzteres durch die Ankunft eines EOC durch den NW-Anschluß (33) über den Anschluß (118) angezeigt wird. Das Ereignis der Entdeckung eines EOC vor der normalen Aktivierung von Anschluß (118) durch den IAC (119) bedeutet einfach, daß nicht genügend Datenbytes in dem PUT-Befehl (gespeichert in LS) sind, um den gesamten Datenpuffer (115) zu füllen, der aus 512 Bytes aus dem Datenspeicher (103) besteht. Wenn die Datenbytes, die in dem PUT-Befehl enthalten sind, zum Datenspeicher (103) übertragen wurden, speichert der Mikroprozessor eine Befehlsbestätigung (deren Format in Fig. 4A gezeigt wurde) in LS (113) und fragt (über die Steuerbusse (103, 116)) den Speicherbenutzer MU (11) nach der Befehlsbestätigung aus dem lokalen Speicher LS (113).
Es soll festgehalten werden, daß der Betrieb der PMCE- (12) Elemente, so wie sie unter Bezugnahme auf einen PUT-Befehl beschrieben wurden, dem Fall eines GET-Befehls sehr ähnlich sind, für den der Fluß der Datenbytes invertiert ist. Deshalb wird der Betrieb des PMCE für einen GET-Befehl nicht vollständig beschrieben und kann leicht aus der Beschreibung, die sich auf den PUT-Befehl bezieht, hergeleitet werden.
Die Betriebsweise des PMCE für einen CREATE- oder RELEASE-Befehl, der nicht die Übertragung von Datenbytes einschließt, wird im Weiteren später vereinfacht zusammengefaßt (Abschnitt 11).

10. Aufbau des Datenspeichers

Der Datenspeicher (103) umfaßt einen ersten Abschnitt (103a), der Datenpuffer enthält (ein Puffer hat zum Beispiel einen Inhalt von 512 Byte), und einen zweiten Abschnitt (103b), der Speichermanagementtabellen (107, 109, 111) enthält. Die Speichermanagementtabellen umfassen ein logisches Satzverzeichnis (17) mit einem Eintrag je LRA, wobei sich in diesem Eintrag alle Informationen befinden, die benötigt werden, um auf die physische Adresse zu zeigen, die mit jedem Verschiebungswert korrespondiert, der in einem Satz geliefert wurde. Die Speichermanagementtabellen enthalten ebenfalls eine Liste freier Puffer (109) und einer Liste freier Token FTL (111), die alle im RAM- Speicher implementiert sind. In einer typischen Ausführung der Erfindung beträgt der Speicherplatz, der für das LRA-Verzeichnis (107), FBL (109) und FTL (111) benutzt wird, ungefähr 5% des globalen Datenspeichers (103).
Der Aufbau und die Nutzung des LRA-Verzeichnisses (107), FBL (109) und FTL (111) wird jetzt unter Bezugnahme auf die relevanten höheren Befehle beschrieben, die diese Vorrichtungen nutzen.
Das in Fig. 11A dargestellte LRA-Verzeichnis (107) wird für die logische und physische Adressübersetzung genutzt.
Im Falle eines Satzes der Klasse 1, der maximal 64 KBytes Daten oder 128 Puffer von 512 Byte enthält, enthält das LRA-Verzeichnis (107) für jede LRA einen Zeiger T. Dieser Zeiger PTR umfaßt 128 Elementarzeiger P0 bis P127 mit einer Länge von jeweils einem Byte, die die physische Adresse der Puffer B0 bis B127 angeben, wobei dies tatsächlich die physische Adresse ihres ersten Bytes ist.
Somit korrespondieren der erste Zeiger P0, der mit Puffer B0 korrespondiert (ebenfalls in Fig. 10 dargestellt), auch mit den Verschiebungen D = 0 bis D = 511 in der logischen Satzadresse LRA, der zweite Zeiger P1 mit den Verschiebungen D 512 bis 1023 in der LRA, usw. ...
Es ergibt sich, daß für ein Informationsbyte Information, das in einem höheren Befehl durch eine logische Satzadresse LRA und eine Verschiebung D definiert ist, die logische Adresse eines Informationsbytes in einem Puffer ergibt sich aus dem Rest der Division der Verschiebung D durch 512 (einer Pufferlänge), wobei der Dividend im Bereich der Pufferzeiger P0 bis P127 liegt.
Außerdem soll festgehalten werden, daß ein Pufferzeiger Pi (i = 0 bis 127), der gleich dem Byte 00000000 ist, bedeutet, daß kein Puffer zugeordnet wurde, um die zugehörigen Verschiebungen zu unterstützen.
Die Liste freier Puffer FBL (109) wird für die Zuordnung der Puffer benutzt und wird unter Bezugnahme auf Fig. 11B beschrieben. Wenn der Inhalt einer Speicherbank 4 Megabyte, eingeteilt in Puffer von 512 Byte, beträgt, wird die Liste freier Puffer 8000 Puffer zum Zeitpunkt der Initialisierung enthalten. Die Adressen dieser 8000 Puffer erhält man aus 4 Byte Wörtern der Adresse und die FBL wird während des Betriebes eine Größe von 32 K Bytes haben.
Die Adresse des ersten freien Puffers erhält man durch einen freien Pufferzeiger FBP, der auf die Adresse des Puffers zeigt, der bei der nächsten Pufferzuordnung einem Satz zugeordnet wird. Wenn dieser Puffer zugeordnet wurde, bewegt sich der Zeiger zur Position von FBP, der auf den nächsten freien Puffer im Datenspeicher (103) zeigt. Folglich existieren die vorher zugeordneten Puffer (die jetzt beschäftigt sind) nicht länger in der FBL, wodurch verhindert wird, daß ein gegebener Puffer doppelt zugeordnet wird. Es soll festgehalten werden, daß gemäß der Erfindung die physischen Datenpuffer B1, B2, B3, ..., die mit einem gegebenen höheren Befehl korrespondieren, sich überall im Bereich des Datenpuffers (103) befinden können, wobei die einzige Regel darin besteht, daß die Puffer frei sein müssen, wenn sie einem bestimmten Benutzer zugeordnet werden.
Die Liste freier Token FTL (111) wird eingesetzt für die Zuordnung der logischen Adressen (oder Token) zu Sätzen, und wird unter Bezugnahme auf Fig. 11C beschrieben. Die FTL (111) ist ein Stück Speicher, das einen Stapel von 4 Byte logischer Satzadressen enthält, die zu einem gegebenen Zeitpunkt frei sind. Die Größe der FTL (111) in Bytes ergibt sich aus der Bankgröße (in Bytes) geteilt durch die minimale Anzahl von Bytes in einem Satz (512 Bytes oder eine Puffergröße) und multipliziert mit vier, da sich eine LRA über 4 Byte ausdehnt.
Die erste freie LRA eines Stapels wird von einem Zeiger der Liste freier Token (FTLP) angezeigt. Wenn eine neue LRA benötigt wird, zum Beispiel für einen CREATE-Befehl, wird die von dem FTLP angezeigte LRA gelesen und zu dem neuen zu erzeugenden Satz bewegt. Dann wird der FTLP durch FTLP' aktualisiert und zu der neuen Spitze des LRA-Stapels verschoben.
Es soll festgehalten werden, daß eine LRA für den gesamten gemeinsamen Speicher einheitlich sein muß, um zu vermeiden, daß eine gegebene LRA an verschiedene physische Adressen vergeben wird. Deshalb kennzeichnen die ersten 3 Bits von jeder in der FTL (111) gespeicherten freien LRA eine Speicherbanknummer (1 von 8), und der Rest der 4 Bytes kennzeichnet die logische Satzadresse in einer gegebenen Bank.

11. Ausführung des höheren Befehls durch das PMCE:

Nimmt man den Aufbau des PMCE (12) und des Datenspeichers (103), wie sie vorher beschrieben wurden, werden die Schritte der von dem Mikroprozessor (101) ausgeführten Routinen für die Ausführung eines höheren Befehls jetzt zusammengefaßt.

Der CREATE-Befehl

1. Ordne eine logische Datensatzadresse dem in den Speicher zu speichernden Satz zu.
2. Bereite ein Erwiderungswort (vgl. Fig. 4A), das die LRA enthält, vor und übertrage es zum Netzwerkanschluß (33).
3. Starte den Netzwerkanschluß (33), der bewirkt, daß das Erwiderungswort an den Speicherbenutzer MU gesandt wird.
4. Austritt.

Der RELEASE-Befehl

Es soll festgehalten werden, daß der Freigabe-Befehl eine LRA selbst und alle auf diese einwirkenden physischen Speicherpuffer freigeben muß. Wie unter Bezugnahme auf Fig. 11A beschrieben, wird ein beschäftigter Puffer von seinem Zeiger Pi (i = 0 bis 127) der ungleich dem Byte 0 (d.h., es enthält acht Nullen) ist, berücksichtigt. Somit ist die Freigabe aller Puffer notwendig, um 0-Bytes in alle Zeiger Pi der 128 Bytes, die der Zeiger durch die LRA adressiert hat, freizugeben. Und um die LRA freizugeben, ist es notwendig, die LRA an die Spitze der Liste freier Token (111) zu setzen (vgl. Fig. 11C). Die Schritte werden zusammengefaßt unten dargestellt:
1. Zugreifen auf das LRA-Verzeichnis unter der freizugebenden LRA.
2. Freigeben aller der LRA zugeordneten Puffer durch Schreiben von Pi = 0 für alle Pi in das LRA-Verzeichnis an eine durch die LRA angezeigt Adresse.
3. Schreiben der LRA an die Spitze der Liste freier Token (111), wodurch die benannte LRA für eine Beeinflussung eines neuen Satzes freigemacht wird.

Der PUT-Befehl

Er liefert eine LRA, eine Verschiebung sowie N zu überragende Datenbytes. Seine Schritte werden unten zusammengefaßt:
1. Übersetzen von LRA und D in physische Adressen.
2. Testen, ob Puffer der LRA zugeordnet wurden (z.B.: alle Bits von Pi **ungleich** 0)
2.a. wenn nicht, ordne der LRA Puffer zu.
2.b. wenn doch, teste IAC (119) oder EOC.
Dies überprüft (IAC), ob genügend Datenbytes in LS (113) vorhanden sind, oder ob alle Datenbytes, die mit dem PUT- Befehl korrespondieren, dort vorhanden sind (EOC).
3. Bewege alle Datenbytes von LS (113) in die vorher zugeordneten Puffer.
4. Aktualisiere D in D', wobei D' = Verschiebung des ersten Bytes des nächsten Puffers des durch die LRA spezifizierten Satzes ist.
5. Testen, ob ein EOC empfangen wurde:
5.a. wenn nicht, gehe zu 1. für die Übersetzung von (LRA, D') in physische Adressen.
5.b. wenn doch, erzeuge im LS (113) ein 5 Byte Antwort-Wort auf den PUT-Befehl.
6. Starte den NW-Anschluß (33) für die Übertragung der Bestätigung an den Speicherbenutzer.
7. Austritt

GET-Befehl

Er liefert eine LRA, eine Verschiebung D und die Anzahl N der Bytes, die man aus dem Datenspeicher (103) erhält. Die ausgeführten Schritte sind:
1. Übersetzung der LRA in physische Adressen.
2. Testen der physischen Adressen, die mit wenigstens einem zugeordneten Puffer korrespondieren.
2.a. wenn nicht, erzeuge eine Fehleranzeige, da die Puffer durch einen früheren CREATE-Befehl zugeordnet hätten werden müssen.
2.b. wenn doch, gehe zu 3.
3. Bewege einen Puffer aus dem Datenspeicher in den lokalen Speicher LS (113).
4. Aktualisiere Verschiebung D T D'.
5. Teste, ob der Datenbytezähler erschöpft ist:
5.a. wenn nicht, gehe zu 1 (D' muß in eine physische Adresse übersetzt werden).
5.b. wenn doch, erzeuge eine 5 Byte Wort Befehlsbestätigung auf den GET-Befehl.
6. Starte den NW-Anschluß (33) für die Übertragung an den Speicherbenutzer.
7. Ende

Claims

1. Vorrichtung für die Verbindung der Prozessoren einer Vielzahl von über ein Verbindungsnetzwerk NW (15) miteinander verknüpften Speicherbenutzer MU (11A, ... 11N) mit einem gemeinsamen Speicher PM, der aus einer Vielzahl von Speicherbänken MB (11A, ... 11N) besteht, die einen globalen gemeinsamen Speicherraum festlegen, in dem die Speicherbenutzer auf den Speicher über einen Satz höherer Befehle zugreifen, die von den Speicherbenutzern MU (11A, ... 11N) für das Speichern und die Wiedergewinnung von Sätzen in/aus dem Speicherraum erteilt werden, wobei die höheren Befehle nur logische Adressen LRA der Sätze nutzen, dadurch gekennzeichnet, daß es folgendes umfaßt:

- dezentrale Speicher-Schnittstellenmittel (13A, ... 13N), wobei eine Speicherschnittstelle MI jedem Benutzer zugeordnet ist, um den Satz höherer Befehle über das Netzwerk NW (15) den Speicherbänken MB (17A, ... 17N) zu übergeben, wobei eine Speicherschnittstelle MI (13A, ... 13N) eine Befehlsanforderung von seinem zugehörigen Speicherbenutzer MU verarbeitet, um:

- das Speichersteuerwort MCW von dem lokalen Speicher des Benutzers LM (91) zu lesen und zu decodieren;

- eine der Speicherbänke MB (11A, ... 11N) unabhängig auszuwählen;

- eine Verbindung über das Verbindungsnetzwerk NW (15) zu der ausgewählten Speicherbank zu erstellen;

- Befehle zu der ausgewählten Speicherbank zu senden, und, nach dem Empfang einer Befehlsbestätigung MSW von der MB, die Verbindung zu der Speicherbank freizugeben,

- dezentralen Verarbeitungsmitteln (12, 103, 107, 109, 111), die in jede Speicherbank MB (17A, ... 17N) integriert sind, um die physischen Adressen der Sätze gemäß ihrer logischen Adressen LRA wiederzugewinnen und die höheren Befehle auszuführen.

2. Vorrichtung nach Anspruch 1, wobei die dezentralen Verarbeitungsmittel eine Vielzahl von Steuerprogrammen für Paketspeicherbefehle PMCE (12A, ... 12N) umfassen, die ihren jeweiligen Speicherbänken (17A, ... 17N) zugeordnet sind, ein gegebenes PMCE für die Ausführung eines höheren Befehls, das von einem Speicherbenutzer (11A, ... IIN) und dessen zugeordneter Speicherschnittstelle (13A, ... 13N) gesandt wurde, einschließlich eines Mikroprozessors (101) für die Verarbeitung der höheren Befehle, die von dem Speicherbenutzer MU erteilt und in einer lokalen Speichereinheit LS (113) gespeichert werden, wobei die Verarbeitung gemäß den befehlsabhängigen Mikroprogrammen erfolgt, die sich in einem Programmspeicher (117) befinden.

3. Vorrichtung nach Anspruch 2, wobei die dezentralen Verarbeitungsmittel einen Datenspeicher (103) einschließen, der folgendes enthält:

- eine Vielzahl von Datenpuffern mit fester Größe (115);

- ein Logisches Satzadressverzeichnis (107) für die Übersetzung einer logischen Satzadresse LRA, die als Zeiger auf das Verzeichnis (107) benutzt wird, in eine Anzahl physischer Adressen von Datenpuffern (115), die einem Satz mit einer LRA als logischer Adresse zugeordnet wird;

- einer Liste freier Puffer FBL (109), in der eine Liste von Datenpuffern (115), die keinem Satz zugeordnet sind, gepflegt wird;

- einer Liste freier Token FTL (111), in der eine Liste der logischen Satzadressen LRA, die sich nicht auf einen Satz auswirken, gepflegt wird.

4. Vorrichtung nach Anspruch 3, wobei der Satz höherer Befehle einen CREATE-Befehl umfaßt, der, wenn er von einem Speicherbenutzer MU (11A, ... 11N) und einer Speicherschnittstelle MI (13A, ... 13N) an eine Speicherbank MB (17A, ... 17N) gesandt und darin von dem zugehörigen PMCE (12A, ... 12N) ausgeführt wird, die folgenden Schritte umfaßt:

Erzeugen eines neuen Satzes innerhalb der Speicherbank, der in dem gemeinsamen Speicher PM (17) eindeutig durch eine logische Satzadresse LRA identifiziert wird, und

Zurückgeben der logischen Satzadresse LRA in einem Befehlsbestätigungswort an die jeweilige Speicherschnittstelle MI und den Speicherbenutzer MU und somit als letztes das Ermöglichen der Verarbeitung des erzeugten Satzes unter Nutzung der logischen Adresse LRA, unabhängig von der physischen Lage des Satzes im Speicher.

5. Vorrichtung nach einem der Ansprüche 3 oder 4, bei dem der Satz höherer Befehle einen PUT-Befehl umfaßt, der durch einen Befehlscode, eine logische Satzadresse LRA, eine Verschiebung D und eine variable Anzahl N von Datenbytes, die in den Datenspeicher (103) nach der Verschiebung D abgelegt werden, definiert ist, wobei der PUT-Befehl, wenn er von einem Speicherbenutzer MU (11A, ... 11N) und einer Speicherschnittstelle NI (13A, ... 13N) an eine Speicherbank MB (17A, ... 17N) gesandt und darin von dem zugehörigen PMCE (12A, ... 12N) ausgeführt wurde, die folgenden Schritte veranlaßt:

- Zuteilen der Anzahl physischer Speicherpuffer, die benötigt werden, um die Datenbytes zu enthalten, die mit dem spezifischen PUT-Befehl verknüpft sind, zu dem durch die LRA spezifizierten Satz;

- Speichern der N Datenbytes in den Speicherpuffer;

- Erstellen eines Eintrages, der alle Zeiger umfaßt die physischen Speicherpuffer adressieren, die mit der Verschiebung D korrespondieren, wobei ein LRA-Verzeichnis (107) einen Eintrag je LRA besitzt.

6. Vorrichtung nach einem der Ansprüche 3, 4 oder 5, bei dem der Satz höherer Befehle einen GET-Befehl umfaßt, der durch einen Befehlscode, eine logische Satzadresse LRA, eine Adressverschiebung D und eine Anzahl N von Datenbytes, die man von dem Datenspeicher erhält, umfaßt, wobei der GET-Befehl, wenn er von einem Speicherbenutzer MU (11A, ... 11N) und einer Speicherschnittstelle MI (13A, ... 13N) an eine Speicherbank MB (17A, ... 17N) gesandt wird und darin von dem zugehörigen Steuerprogramm PMCE (12A, ... 12N) ausgeführt wird, die folgenden Schritte veranlaßt:

- Zeigen mit der LRA auf das LRA-Verzeichnis (107) um die physische Adresse der Speicherpuffer zurückzugewinnen, die N Datenbytes nach der Adressverschiebung D enthalten;

- Lesen der N Datenbytes;

- Zurückbringen der N Datenbytes von dem Datenspeicher (103) zur Speicherschnittstelle MI (13) und dem Speicherbenutzer MU (11)

7. Vorrichtung nach einem der Ansprüche 3, 4, 5 oder 6, bei dem der Satz höherer Befehle einen RELEASE-Befehl enthält, der durch einen Befehlscode und eine logische Satzadresse LRA festgelegt ist, wobei der RELEASE-Befehl, wenn er von einem Speicherbenutzer MU (11A, ... 11N) und einer Speicherschnittstelle MI (13A, ... 13N) an eine Speicherbank MB (17A, ... 17N) gesandt und von dem zugehörigen PMCE (12A, ... 12N) ausgeführt wird, die folgenden Schritte veranlaßt:

- Streichen der spezifizierten logischen Satzadresse LRA aus dem LRA-Verzeichnis (107) der berücksichtigten Speicherbank;

- Freigeben aller physischen Speicherpuffer, die auf den Inhalt der spezifizierten LRA zeigen und

- Aktualisieren der freien LRA-Liste in der FTL (111).