DE3853363T2

DE3853363T2 - Lastausgleichstechnik in einem gemeinsamen Speicher mit verteilter Struktur.

Info

Publication number: DE3853363T2
Application number: DE19883853363
Authority: DE
Inventors: Andre Pauporte; Phuoc Prof Dr Ing Tran-Gia
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-09-28
Anticipated expiration: 2008-12-24
Also published as: JPH02259944A; EP0374337A1; DE3853363D1; EP0374337B1; JPH0581939B2

Description

ANWENDUNGSBEREICH DER ERFINDUNG

Die vorliegende Erfindung bezieht sich auf Systeme, in denen mehrere Benutzer Zugriff auf einen gemeinsamen Speicher haben, der aus einer Mehrzahl an Speichermodulen (Speicherbänken) besteht, auf die ein separater Zugriff möglich ist; insbesondere bezieht sich die vorliegende Erfindung auf Verfahren zum Ausgleich der Last, das heißt, der Speichernutzung durch alle speichermodule.

HINTERGRUND DER ERFINDUNG

In Systemen, die eine Mehrzahl gemeinsamer Ressourcen wie beispielsweise Prozessoren, Ein-/Ausgabegeräte, Puffer usw. aufweisen, besteht ein Interesse, die Last oder die Nutzung unter den Ressourcen auszugleichen, um so eine Optimierung der Systemleistung zu erzielen. Es wurden mehrere Lösungen zum Ausgleich der Nutzung unter mehreren Geräten vorgeschlagen, wie dies in der nachfolgenden Auflistung von Patenten und Veröffentlichungen zum Ausdruck kommt.
Das U.S.-Patent 3,702,006 mit dem Titel "Method for Balancing the Utilization of Input/Output Devices". -- Das U.S.-Patent 4,403,286 mit dem Titel "Balancing Data-Processing Workloads". -- Das U.S.-Patent 4,633,387 mit dem Titel "Load Balancing in a Multiunit System".
Veröffentlichung im IBM Technical Disclosure Bulletin: -- J.A. McLoughlin: "Load Balancing Buffered Peripheral Subsystem"; Band 24, Nr. 1B (Juni 1981), Seiten 707-709. -- D.C.Cole et al.: "Recalibrating Buffer Peripheral Systems"; Band 24, Nr. (Juli 1981), Seiten 1041-1042. -- G.A.McLain et al.: "Multiple Utilization Threshold Control for I/O"; Band 24, Nr. 3 (August 1981), Seite 1406. -- D.W.Bolton et al. "Combined Real-Virtual Fixed-Size Buffer Mechanism in Shared Storage"; Band 27, Nr. 4B (September 1984), Seiten 2655-2660.
Bei all diesen bekannten Lösungen wird entweder eine zentrale Aufzeichnung benötigt, die die Informationen zum Last- oder zum Nutzungsstatus enthält, oder es wird eine zentrale Verarbeitung bereitgestellt, um die erforderlichen Informationen zu erhalten und um die Steuerung des Lastausgleichs durchzuführen; darüber hinaus sind bestimmte Übertragungen erforderlich, um den Laststatus und/oder die dazugehörige Steuerinformation abzurufen oder zu verteilen.
Die zentrale Speicherung oder Verarbeitung von Lastausgleichinformationen kann zu einer Überlastung führen, wenn zahlreiche Transaktionen gleichzeitig durchgeführt werden, und es kann zu Schäden kommen, wenn die jeweilige Einheit ausfällt; die Anforderung zusätzlicher Datenübertragungen senkt die Leistung. Darüber hinaus ist eine modulare Ausdehnung eines Systems möglicherweise nicht realisierbar, wenn die zentralisierten Aktualisierungsprozeduren auf eine bestimmte Konfiguration ausgelegt sind.

ZIELE DER ERFINDUNG

Es ist ein vorrangiges Ziel der vorliegenden Erfindung, ein Verfahren zum Ausgleich der Last unter mehreren Speichermodulen, die einen gemeinsamen Speicher für mehrere Benutzer auf vollkommen dezentralisierte Weise bilden, zu entwickeln.
Es ist ein weiteres Ziel der vorliegenden Erfindung, ein Lastausgleichverfahren für einen gemeinsamen Modularspeicher bereitzustellen, bei dem keine bestimmten Datenübertragungen für den Austausch von Laststatusinformationen benötigt werden. Es ist ein weiteres Ziel der vorliegenden Erfindung, einen Speicherlastausgleichsmechanismus zu entwickeln, der eine modulare Ausdehnung der Anzahl an Speichermodulen oder -bänken ohne die Erfordernis von Änderungen oder Anpassungen in den Benutzereinheiten, ihrer Schnittstellen und Erweiterungen, oder in den üblicherweise verwendeten Einheiten ermöglicht.

ZUSAMMENFASSUNG DER ERFINDUNG

Diese Ziele werden durch ein Verfahren des Lastausgleichs eines gemeinsamen Speichers gemäß Definition in Anspruch 1 und durch einen lastausgeglichenen gemeinsamen Speicher gemäß Definition in Anspruch 9 erzielt.
Die vorliegende Erfindung ermöglicht den Ausgleich der Speicherlast bei einer nur minimalen Anzahl zusätzlicher Operationen und ohne zusätzliche Informationsübertragungen, indem für jede Benutzereinheit eine Speicherlaststatusübersicht angelegt wird, die in geeigneten Situationen aktualisiert wird. Bei der Aktualisierung wird die Übertragung separater Informationen vermieden, indem als Träger die Befehlsantworten verwendet werden, die ohnehin regelmäßig von den Speicherbänken zu den Benutzereinheiten übertragen werden.
Weitere Eigenschaften und Vorteile der vorliegenden Erfindung werden aufgrund der nachfolgenden ausführlichen Beschreibung eines bevorzugten Ausführungsbeispiels in Verbindung mit den Begleitzeichnungen ersichtlich.

AUFLISTUNG DER ZEICHNUNGEN

Figur 1 ist ein Blockdiagramm der Gesamtkonfiguration eines Mehrbenutzersystems mit gemeinsamem Speicher, in dem die vorliegende Erfindung verwendet wird;
Figur 2 ist eine schematische Darstellung des Informationsflusses und der Sequenz der Schritte eines Speicherzugriffs im System von Figur 1;
Figur 3 zeigt die Formate der Befehle und Befehlsantworten, die für Speicheroperationen im System von Figur 1 verwendet werden;
Figur 4 zeigt die Formate der Speichersteuerblöcke, die im lokalen Speicher des Benutzers gespeichert sind und die für die Informationsübertragung zwischen dem Benutzer und seiner Speicherschnittstelle verwendet werden;
Figur 5 ist ein Blockdiagramm der Speicherschnittstelle (MI), über die ein Benutzer mit dem gemeinsamen Speicher im System von Figur 1 verbunden ist;
Figur 6 ist ein Flußdiagramm des Speicherbefehls, der in der Speicherschnittstellenlogik verarbeitet wird; und
Figur 7 ist ein Flußdiagramm der Auswahl einer Speicherbank, wie sie durch die Speicherschnittstelle unter Verwendung des Lastausgleichverfahrens der vorliegenden Erfindung erfolgt.

AUSFÜHRLICHE BESCHREIBUNG

1) SYSTEMÜBERSICHT

Figur 1 zeigt die Konfiguration eines Systems, in dem die vorliegende Erfindung Anwendung findet. Im Prinzip handelt es sich hierbei um ein System, in dem mehrere Benutzer mit mehreren Speicherbänken (Speichermodulen) verbunden sind, die als ein gemeinsamer Speicher allen Benutzern zur Verfügung stehen. Eine solche Anordnung wird beispielsweise in Kommunikations- Controllern verwendet.
Jeder Speicherbenutzer MU (11A, 11B, ... 11N) ist über seine eigene Speicherschnittstelle MI (13A, 13B, ... 13N) an ein gemeinsames Verbindungsnetz NW (15) angeschlossen. Die Speicherbänke (17A, 17B, ... 17N) sind gleiche Einheiten, von denen jede an das Verbindungsnetz angeschlossen ist.
Das verbindungsnetz ist ein Paketschalter mit mehreren Ports, der, wenn Datenpakete an einem seiner Ports eingegeben werden, diese an den gewünschten Ausgabeport weiterleiten kann. Solche Netze sind bekannt und werden beispielsweise in den folgenden Veröffentlichungen sowie in der darin zitierten Literatur beschrieben. T. Feng: "A Survey of Interconnection Networks"; Computer (IEEE) December 1981, Seiten 12-30. -- V.P. Kumar et al.: "Augmented Shuffle-Exchange Multistage Interconnection Networks"; Computer (IEEE) Juni 1987, Seiten 30-40.
Der Vorteil der gesamten Anordnung besteht darin, daß sie modular erweitert werden kann (solange das Verbindungsnetz eine ausreichende Kapazität und genügend Ports aufweist). Die Anzahl der Speicherbänke kann an die Anzahl der Benutzer und deren Speicheranforderungen angepaßt werden.
Der Gesamtfluß an Befehlen und Steuerinformationen für Speicherzugriffe wird schematisch im Diagramm von Figur 2 dargestellt.
Der Speicherbenutzer MU bereitet ein Steuerwort MCW vor, das die gewünschte Operation angibt und Parameter enthält. Das MCW wird an die Speicherschnittstelle MI übertragen, die die Befehlsanforderung verarbeitet und einen Befehl an eine der Speicherbänke MB sendet. Der Befehl wird im MB (Speichern von Daten, Lesen von Daten usw.) ausgeführt und an das MI eine Befehlsantwort zurückgesendet. Das MI bereitet Statusdaten vor, die die Antwort wiedergeben, die vom MB empfangen wurde, sowie inöglicherweise zusätzliche Statusdaten, die wiedergeben, wie die Speicheroperation beendet wurde; diese Statusdaten werden in einem Speicherstatuswort NSW an das MU übertragen.
Die Bezeichnung "Befehl", wie sie in der folgenden Beschreibung verwendet wird, bezeichnet eigentlich eine Anforderung einer Speicheroperation, die von einer Speicherbenutzer/Speicherschnittstelle zu einer Speicherbank (beispielsweise CREATE-Befehl, PUT-Befehl usw.) gesendet wurde.
Die Formate der Befehle und Befehlsantworten, des MCW und des MSW werden an späterer Stelle in Verbindung mit den Figuren 3 und 4 ausführlich beschrieben.
Die Befehlsverarbeitung erfolgt durch eine Logikschicht (im MI), die nach unten eine schnittstelle zum Speicherbenutzer MU hat, die den Lese-/Schreibzugriff auf den MU lokalen Speicher ermöglicht, und die nach oben eine weitere Schnittstelle zum Verbindungsnetz NW hat. Nähere Einzelheiten zur MI-Logik und ihrer Operation werden an späterer Stelle in Verbindung mit den Figuren 5 und 6 beschrieben.
Ein Prinzip, von dem man für das vorliegende System ausgeht, besteht darin, daß die Verteilung von Benutzerdaten unter den Speicherbänken willkürlich ist, das heißt, es gibt keine feste Zuordnung zwischen Speicherbänken und Benutzern. Ein Problem, das mit diesem Prinzip einhergeht, liegt darin, daß die Speicherbänke ungleich gefüllt (beladen) werden können. Daher kann es sein, daß einige Speicherbänke vollständig mit Daten gefüllt sind, während andere völlig ungenutzt bleiben. Dies kann zu Überlastung, unnötigen Wartezeiten und zum Verlust des Parallelismus führen, was vermieden werden kann, solange der gesamte verfügbare Speicher für alle zu speichernden Daten ausreichend ist. Die vorliegende Erfindung löst dieses Problem, indem die Last zwischen allen Speicherbänken ausgeglichen wird.

2) VERFAHREN FÜR DEN LASTAUSGLEICH

In der vorliegenden Beschreibung wird die Bezeichnung "Last" im folgenden Sinnzusammenhang verwendet: Die Last einer Speicherbank ist der Umfang an Speicherplatz (ausgedrückt in Einheiten wie beispielsweise Bytes, Wörtern oder Blöcken mit 256 Bytes), der Aufzeichnungen, die innerhalb der betreffenden Speicherbank vorhanden sind, effektiv zugeordnet ist.
Der "Laststatus" einer Speicherbank ist das Ergebnis eines Vergleichs zwischen der momentanen Last der Speicherbank und einer vorbestimmten Schwelle. Diese Schwelle kann beispielsweise 70% des gesamten verfügbaren Speichers in der betreffenden Speicherbank sein. Dieser Laststatus läßt sich durch einen binären "Laststatusindikator" darstellen. (Falls erwünscht, wäre es natürlich auch möglich, mehrere Stufen eines Laststatus zu definieren. Auf diese Weise könnte die tatsächliche Last mit drei verschiedenen Schwellenwerten verglichen werden, was zu vier verschiedenen Laststatusangaben führen würde, die sich mit zwei Bits darstellen ließen.)
Die Lösung der vorliegenden Erfindung für den Ausgleich von Last (Speicherbelegung) unter allen installierten Speicherbänken läßt sich wie folgt zusammenfassen:
a) Für jeden Benutzer (beispielsweise in der Speicherschnittstelle) wird eine Tabelle mit Angaben zum Laststatus jeder installierten Speicherbank angelegt;
b) Wenn ein Benutzer im gemeinsamen Speicher eine neue Aufzeichnung anlegen möchte, wird durch Abfrage der Laststatustabelle (um nach einer Speicherbank mit geringer Last zu suchen) eine der Speicherbänke ausgewählt;
c) Zusammen mit jedem Informationsblock, der ohnehin von einer Speicherbank zurück zu einem Benutzer geleitet wird (das heißt, Bestätigung des Erhalts eines Speicherbefehls vom Benutzer und Ausführung durch diesen Benutzer) werden Informationen zum Laststatus der entsprechenden Speicherbank gesendet;
d) Aktualisierung der Laststatustabelle, die für einen Benutzer (oder eine Speicherschnittstelle) angelegt ist, durch Eingabe der erhaltenen Laststatusinformation. Dieses neue Verfahren ermöglicht eine gleichmäßige Verteilung der Last unter allen Speicherbänken mit einer nur geringen Anzahl an zusätzlichen Operationen; es sind keine zusätzlichen Datenübertragungen erforderlich, da sich die Laststatusinformation in den Informationsblöcken befinden, die ohnehin übertragen werden.

3) SPEICHERSCHNITTSTELLENFUNKTIONEN UND BEFEHLSFORMATE

Die Funktion der Speicherschnittstelle MI besteht darin, jedem Speicherbenutzer MU eine standardmäßige dezentralisierte Speicherschnittstelle bereitzustellen. Diese behandelt die vom Speicherbenutzer MU eingegebenen Speicherbefehle wie folgt: Sie wählt die geeignete Speicherbank MB aus (unter Verwendung des Lastausgleichverfahrens der vorliegenden Erfindung), stellt über das Verbindungsnetz NW eine Verbindung zu dieser Speicherbank MB her, erzeugt und sendet über diese Verbindung einen Befehl (der auch Daten beinhalten kann), wartet auf eine Befehlsantwort (die in bestimmten Fällen auch Daten der Speicherbank MB enthält), gibt die Verbindung frei und erstellt für den Speicherbenutzer MU Vollständig-Statusdaten.
Jeder Befehl besteht aus einem 12-Byte-Datenkopf, gefolgt von einem optionalen Datenfeld. Jede Befehlsantwort besteht aus einem optionalen Datenfeld, gefolgt von einem 5-Byte-Datenschwanz.
Es werden vier verschiedene Speicherbefehle und dazugehörige Befehlsantworten bereitgestellt. Ihre Formate werden in Figur 3 dargestellt und nachfolgend kurz beschrieben:

CREATE (Format: nur Befehl)

Dieser Befehl bewirkt das Anlegen einer Aufzeichnung (RECORD) (eine logische Speichereinheit) im gemeinsamen Speicher und die Zuordnung einer logischen Aufzeichnungsadresse (Logical Record Address - LRA). Die LRA ist eine einmalig vorkommende Systemreferenz, die ein Auffinden einer Speicheraufzeichnung im gemeinsamen Speicher ermöglicht. Eine Speicherbank MB wird gemäß dem in diesem Dokument beschriebenen neuen Lastausgleichverfahren ausgewählt.
Einer neuen Aufzeichnung wird kein Speicherplatz zugeordnet (solange noch keine Daten zu speichern sind).
Die Befehlsantwort schickt die LRA zur entsprechenden Speicherschnittstelle MI zurück.

PUT (Format: Befehl, LRA, D, Daten)

Der Befehl PUT bewirkt, daß die Daten, die er miteinschließt, in die angegebene Aufzeichnung (LRA) mit der angegebenen Übertragungsgeschwindigkeit D geschrieben werden. Der Aufzeichnung wird (beim Ausführen des Befehls PUT) ausreichend Speicherplatz zugeordnet, so daß die Daten gespeichert werden können.
Die Befehlsantwort leitet keine speziellen Daten zurück zur Speicherschnittstelle MI (außer dem Rückmeldecode RC, der in jeder Befehlsantwort enthalten ist).

GET (Format: Befehl, LRA, D, N)

Der Befehl GET bewirkt, daß N Datenbytes aus der angegebenen Aufzeichnung (LRA) mit der angegebenen Übertragungsgeschwindigkeit gelesen werden.
Die Befehlsantwort leitet die N Datenbytes zurück zur Speicherschnittstelle MI.

RELEASE (Format: Befehl, LRA)

Der Befehl RELEASE bewirkt, daß die angegebene Aufzeichnung (LRA) aufgelöst und der dazugehörige Speicherplatz freigegeben wird.
Die Befehlsantwort enthält keine spezifischen Daten (außer dem Rückmeldecode).

Rückmeldecodestruktur und Laststatusindikator:

Der Rückmeldecode (RC), der Bestandteil jeder Befehlsantwort, die von einer Speicherbank zurückgesendet wird, ist, ist ein 8-Bit-Byte mit der folgenden Struktur: Die ersten vier Bits RRRR sind ein spezifischer Code, der den Vollständig-Status des betreffenden Speicherbefehls angibt. Das fünfte Bit L ist ein Laststatusindikator (LSI), dessen Binärwert den Laststatus der entsprechenden Speicherbank angibt: Eine 1 steht für niedrige Last (unterhalb eines gegebenen Schwellenwerts) und eine 0 zeigt eine hohe Last an.
Die letzten drei Bits eines Rückmeldecodes (RC) werden im vorliegenden Beispiel nicht verwendet. Sie könnten jedoch verwendet werden, um zwischen mehreren Stufen der Speicherlast zu unterscheiden: Mit einem 2-Bit-Laststatusindikator L (anstelle des oben erwähnten 1 Bit) kann ein Bit vier verschiedene Laststufen unterscheiden.
Das LSI, das in der Befehlsantwort zurückgeleitet wird, wird auf der Grundlage des Vergleichs zweier Quantitäten vom MB erzeugt Dem "freien Speicherplatz" und dem "Schwellenwert für den freien Speicherplatz". Der freie Speicherplatz ist die Anzahl an Speicherstellen im MB, die keiner Aufzeichnung zugeordnet sind. Während der Befehlsausführung wird diese Anzahl durch die MB-Steuerung aufgezeichnet. Die Befehle CREATE und GET, die keinen freien Speicherplatz benötigen, ändern diese Anzahl nicht. Die Befehle PUT benötigen Speicherplatz und reduzieren somit den freien Speicherplatz. Der Befehl RELEASE erhöht den freien Speicherplatz. Der Schwellenwert für den freien Speicherplatz ist ein Wert, der in jeder Speicherbank initialisiert wurde.
Die Operation der Speicherbänke wird in diesem Dokument nicht naher beschrieben, da diese nicht Gegenstand der vorliegenden Erfindung ist.

4) SPEICHERBENUTZER UND SPEICHERSTEUERBLÖCKE

Der Speicherbenutzer MU kann als Mikroprozessor mit eigenem Hauptspeicher (genannt lokaler Speicher) betrachtet werden.
Die Speicherbefehle übertragen Daten zwischen dem gemeinsamen Speicher (die Gesamtanzahl aller Speicherbänke MB) und dem lokalen Speicher des Speicherbenutzers.
Der Informationsaustausch zwischen einem Speicherbenutzer MU und seiner Speicherschnittstelle MI erfolgt über Speichersteuerblöcke, deren Formate in Figur 4 dargestellt sind.
Ein Speicherbefehl wird vom Speicherbenutzer MU als ein Steuerblock geliefert, der als "Speicherbefehlswort" (MCW) bezeichnet wird und im lokalen Speicher des Speicherbenutzers MU eingerichtet ist. Das MCW enthält Steuerinformationen, die den Typ des Speicherbefehls (CREATE, GET, PUT, RELEASE), die logische Autzeichnungsadresse (LRA), die Datenübertragungsgeschwndigkeit (D) innerhalb der Aufzeichnung, die Datenzählung (N) und die Adresse des Datenbereichs innerhalb des lokalen Speichers des Speicherbenutzers MU (Zeiger im lokalen Speicher - LMP) spezifizieren.
- Die Vollständig-Statusdaten wird dem Speicherbenutzer MU von der Speicherschnittstelle MI als Steuerblock im lokalen Speicher des Speicherbenutzers MU geliefert: dem "Speicherstatuswort" (MSW). Die Statusdaten enthalten Informationen (CC) darüber, ob die Befehlsausführung zufriedenstellend war oder nicht. Im Fall eines Befehls CREATE enthält das MSW auch die logische Aufzeichnungsadresse (LRA) der erstellten Aufzeichnung.

5) SPEICHERSCHNITTSTELLENLOGIK

Figur 5 enthält ein Blockdiagramm der Speicherschnittstellenlogik. Ihre Elemente und ihre Struktur sind wie folgt:
Die Speicherschnittstelle umfaßt im wesentlichen einen zentralen Teil 31, einen Verbindungsnetz-(NW)-Port 33, einen DMA- Teil oder Benutzerport 35 und einen Steuerteil 37.
Der zentrale Teil 31 umfaßt eine ALU 41, ein Akkumulatorregister (ACCU) 43, einen lokalen Speicher LS 45 und ein Lokalspeicher-Adressenregister LSAR 47. Ein A-Bus 49 und ein B-Bus 51 sind an die Eingänge des ALU angeschlossen, und ein Ergebnisbus 53 ist an den Ausgang der ALU angeschlossen. Die Eingabedaten an das LS werden auf den Leitungen 55, 57 und 59 übertragen, und die Ausgabedaten vom LS werden auf Leitung 61 übertragen.
Der NW-port 33 umfaßt vier Register und einen Zähler. Das NW- Daten-Ein-(NWDI)-Register 63 ist zwischen der LS-Ausgabeleitung 61 und einem Zweiweg-NW-Datenbus 65 angeschlossen. Das NW-Daten-Aus-(NWDO)-Register 67 ist zwischen der LS-Eingabeleitung 55 und dem NW-Datenbus 65 angeschlossen. Das NW- Steuer-Ein-(NWCI)-Register 69 ist zwischen dem ALU-Ergebnisbus 53 und einer NW-Steuer-Eingabeleitung 71 angeschlossen. Das NW-Steuer-Aus-(NWCO)-Register 73 ist zwischen dem A-Bus 49 und einer NW-Ausgabesteuerleitung 75 angeschlossen. Ein NW-Zähler (NWCT) 77 empfängt dessen Eingabe vom ALU-Ergebnisbus 53.
Seine Inhalte können um eine Einheit inkrementiert (oder dekrementiert) werden, wenn vom Netz ein Byte empfangen (oder wenn an das Netz ein Byte geliefert) wurde, und es kann auf Null getestet werden.
Der Benutzerport 35 enthält drei Register und einen Zähler. Das MU-Daten-EIN-(MUDI)-Register 79 ist zwischen der LS-Eingabeleitung 57 und einem Zweiweg-Benutzerdatenbus 8l angeschlossen. Das MU-Daten-AUS-(MUDO)-Register 83 ist zwischen der LS- Ausgabeleitung 61 und dem Benutzerdatenbus 81 angeschlossen. Das MU-Adressen-(MUA)-Register 85 ist zwischen dem ALU-Ausgabebus 53 und einer Benutzeradressenleitung 87 angeschlossen.
Ein MU-Zähler-(MUCT) 89 empfängt seine Eingabe vom ALU-Ergebnisbus 53. Seine Inhalte können um eine Einheit dekrementiert werden, wenn vom Benutzer ein Byte empfangen (oder wenn an den Benutzer ein Byte geliefert) wurde, und es kann auf Null getestet werden.
Der Steuerabschnitt 37 liefert die folgenden Daten oder Steuersignale:
IF = Unmittelbares Feld (LS-Operand oder LS- Adresse)
ALUOP = ALU-Operationscode (Addieren, Subtrahieren, Und, Oder, Xoder, Rotieren, ... )
ABS = A Busquelle
BBS = B Busquelle
LSOP = LS Operationscode (Lesen, Schreiben, NOOP)
LSA = LS-Adressensteuerung
MISC = Verschiedene Steuerungen zum Beschreiben von Registern, zum Starten von DMA, usw.
Die MI-Logik hat die folgenden Fähigkeiten:
1 - Die MI-Logik kann arithmetische und Bool'sche Operationen an zwei Operanden ausführen, wobei der eine Operand ein unmittelbarer Wert (IF) ist, der durch den Steuerabschnitt erzeugt wurde, und der zweite der Inhalt einer LS-Stelle oder der Inhalt eines Steuerregisters ist.
2 - Die MI-Logik besitzt Lese-/Schreibzugriff auf den lokalen MU-Speicher, wobei die lokale Speicheradresse und die Bytezählung im MU-Adressenregister (MUA) bzw. im MU-Zählerregister (MUCT) spezifiziert sind. Die Datenquelle während des Schreibens (oder das Ziel während des Lesens) ist das LS, das durch das LS-Adressenregister (LSAR) adressiert wurde.
3 - Die MI-Logik kann über das Verbindungsnetz NW eine Verbindung zu einer Speicherbank MB herstellen, indem sie eine Verbindungsanforderung und die MB-Adresse (Identifikator) in das "NW-Steuer-Ein-Register" (NWCI) lädt und darauf wartet, daß im "NW-Steuer-Aus-Register" (NWCO) eine Verbindungsbestätigung zurückgeleitet wird. Die Verbindung kann auf ähnliche Weise wieder aufgelöst werden, indem in das NWCI eine Verbindungsauf lösungsanforderung geladen und auf eine in das NWCO zurückgeleitete Bestätigung gewartet wird. Das Verbindungsnetz NW wird nicht näher beschrieben, da es nicht Gegenstand der vorliegenden Erfindung ist. (Veröffentlichungen, die Beschreibungen zu Verbindungsnetzen enthalten, wurden an obiger Stelle in Abschnitt 1 aufgeführt.) Sobald eine Verbindung zu einer Speicherbank MB aufgebaut ist, kann die MI-Logik über diese Verbindung eine Zweiweg-Datenübertragung laufen lassen: angenommen, das LSAR wird auf den Wert A initialisiert und das NW Zählerregister (NWCT) wird auf den Wert N initialisiert, dann werden die N Bytes, die sich an LS(A) befinden, ausgelesen und an das MB gesendet. Diese nach innen gerichtete Datenübertragung endet mit NWCT=0 und LSAR=A+N. Das MB muß dann eine Bytekette zurückleiten, die, beginnend an der Adresse A+N, im LS empfangen und gespeichert wird. Die Anzahl der empfangenen Bytes ist am Ende der nach außen gerichteten Übertragung im NWCT verfügbar. Die Befehle und die Befehlsantworten werden auf diese Weise zwischen der Speicherschnittstelle MI und einer Speicherbank MB ausgetauscht.

6) BEFEHLSVERARBEITUNG IN DER SPEICHERSCHNITTSTELLENLOGIK

Das Flußdiagramm in Figur 6 veranschaulicht die während der Befehlsverarbeitung in der Speicherschnittstellenlogik (MI) ausgeführten Schritte. Insbesondere wird gezeigt, wie die Speichernutzungsinformationen (Speicherlaststatus), die ein wesentlicher Bestandteil des Lastausgleichverfahrens der vorliegenden Erfindung sind, während der Verarbeitung von Speicherbefehlen behandelt werden.
Schritt A: Das MI liest das Speichersteuerwort MCW aus dem lokalen Speicher des Benutzers (unter Verwendung von DMA- Verfahren) und speichert das MCW in seinem eigenen lokalen Speicher LS. Daraufhin dekodiert es den Befehl. Je nach dem, ob der Befehl ein CREATE-Befehl ist oder nicht, folgt als nächstes einer von zwei Schritten.
Der Schritt B1 (Befehl = CREATE): Eine der Speicherbänke wird gemäß dem Lastausgleichverfahren (Beschreibung der Auswahl in Abschnitt 7 in Verbindung mit Figur 7) ausgewählt. Die CMB- Variable, die die derzeitige Speicherbank (nachfolgende Beschreibung) bezeichnet, wird eingerichtet.
Der Schritt B2 (Befehl = alle außer CREATE): Die für diesen Befehl zu verwendende Speicherbank MB wird durch das LRA-Feld des MCW bestimmt. Siehe Bemerkungen in Abschnitt 7b unten. Die CMB-Variable (die die derzeitige Speicherbank bezeichnet), wird eingerichtet.
Schritt C: Das MI stellt über das Verbindungsnetz NW eine Verbindung zur Speicherbank her, die durch das derzeitige CMB bezeichnet ist. Im lokalen Speicher LS (an dieser Stelle werden hierzu keine näheren Einzelheiten beschrieben, da diese für die Beschreibung des Lastausgleichverfahrens nicht wesentlich sind) wird ein Befehl eingerichtet. Die Anfangsadresse des Befehls in LS wird in LSAR eingegeben, und die Bytezahlung des Befehls in das Register NWCT geladen. Danach wird der Befehl an die ausgewählte Speicherbank MB gesendet. Die Rücksendung einer Befehlsantwort vom MB wird abgewartet.
Schritt D: Sobald die Befehlsantwort im MI empfangen wird, wird sie verarbeitet (an dieser Stelle werden hierzu keine näheren Einzelheiten beschrieben, da diese für die Beschreibung des Lastausgleichverfahrens nicht wesentlich sind). Das L-Bit des Rückkehrcodes wird als Laststatusanzeiger LSI behalten.
Schritt E: Das LSI-Bit wird getestet, um den Laststatus des soeben verwendeten MB zu bestimmen. Je nach Resultat folgt als nächstes einer von zwei unterschiedlichen Schritten.
Schritt F1 (LSI = 1) Das ausgewählte MB befindet sich in einem niedrigen Laststatus. Die LL-Variable (die alle Speicherbänke niedriger Last identifiziert, siehe nachfolgende Beschreibung) und die CMB-Variable (die die derzeitige Speicherbank bezeichnet) werden durch eine OR-Operation kombiniert, um LL zu aktualisieren, so daß sich auch die zuletzt verwendete Speicherbank (die soeben durch die Befehlsantwort ihren Laststatus mitgeteilt hat) in einem niedrigen Laststatus befindet.
Schritt F2 (LSI = 0): Das ausgewählte MB befindet sich in einem hohen Laststatus. Die LL-Variable (die alle Speicherbänke niedriger Last identifiziert) und die CMB-Variable (die die derzeitige Speicherbank bezeichnet) werden durch eine AND- Operation kombiniert, um LL zu aktualisieren, so daß sie den hohen Laststatus für das entsprechende MB anzeigt.
Schritt G: Nun richtet das MI das Speicherstatuswort MSW in seinem lokalen Speicher LS ein (unter Verwendung der Information, die zusammen mit der Befehlsantwort empfangen wurde).
Danach lädt es die LS-Adresse, an der das MSW beginnt, in das LSAR und die Bytezählung des MSW in den Zähler MUCT und kopiert das MSW aus dem LS in den lokalen Speicher des Benutzers. Schließlich wird die Verbindung über das Verbindungsnetz zum MB aufgelöst.
Bool'sche Variabeln im MI für die Speicherbankauswahl und Laststatusabbi ldung:
Das Verfahren verwendet die vier Bool'schen Variabeln CMB, RR, TL und LL, die im lokalen Speicher (LS) der Speicherschnittstelle MI residieren und die nachfolgend definiert werden. Diese vier Variabeln bezeichnen die Speicherbank MB, die derzeit vom entsprechenden MI verwendet wird- die Round-Robin- Variable, die Gesamtliste aller installierten Speicherbänke und die Liste der Speicherbänke, die sich derzeit in einem niedrigen Status befinden (das heißt, die noch mehr CREATE- Anforderungen aufnehmen können). In den nachfolgend aufgeführten Beispielen wird davon ausgegangen, daß die maximale Anzahl an Speicherbänken acht ist. Würden mehr als acht Speicherbänke bereitgestellt werden, müßten diese drei Variabeln zwei (oder mehr) Bytes und nicht, wie nachfolgend angenommen wird, nur ein Byte umfassen.

Derzeitige Speicherbank (CMB):

8-Bit-Variable, numeriert von 0 bis 7.
Alle Bits sind Nullen, außer einem Bit, dessen Position die ausgewählte Speicherbank MB angibt, die im derzeitigen Befehl enthalten ist.

Beispiel: CMB = 00100000

In diesem Beispiel wird die MB Nummer 2 ausgewählt.

Round-Robin-Variable (RR):

8-Bit-Variable, numeriert von 0 bis 7.
Alle Bits sind Nullen, außer einem Bit, dessen Position die während des letzten CREATE-Befehls ausgewählte Speicherbank MB angibt.

Beispiel: RR = 00010000

In diesem Beispiel wurde MB Nummer 3 während des zuletzt vom MI ausgegebenen CREATE-Befehls ausgewählt.

Gesamtliste (TL):

8-Bit-Variable, numeriert von 0 bis 7.
Die Bitpositionen im TL werden in die installierten Speicherbänke MB abgebildet.

Beispiel: TL = 11110000

In diesem Beispiel werden vier MBs in den Positionen 0, 1, 2 und 3 installiert.

Liste Niedrige Last (LL)

8-Bit-Variable, numeriert von 0 bis 7.
Bedeutungstragende Bits entsprechen installierten Speicherbänken MB gemäß Angabe in TL.
Ein bedeutungstragendes Bit auf eins gibt an, daß sich das dazugehörige MB in einem niedrigen Laststatus befindet.
Ein bedeutungstragendes Bit auf Null gibt an, daß sich das dazugehörige MB in einem hohen Laststatus befindet.

Beispiel: LL = xxxx0000

In diesem Beispiel ist x = 0, wenn sich das dazugehörige MB in einem hohen Laststatus befindet, und x = 1, wenn sich das dazugehörige MB in einem niedrigen Laststatus befindet.

7) AUSWAHL EINER SPEICHERBANK DURCH DIE SPEICHERSCHNITTSTELLE

Es gibt zwei verschiedene Situationen, in denen eine Speicherschnittstelle MI eine Speicherbank MB auswählen muß, um einen Speicherbefehl auszuführen: (a) Bei einem CREATE-Befehl muß eine neue Speicherbank gemäß dem Lastausgleichverfahren der vorliegenden Erfindung ausgewählt werden. (b) Bei allen anderen Speicherbefehlen ist die Speicherbank bekannt (durch den LRA-Parameter) und das MI kann dieses MB identifizieren.

a) Auswahl eines ND gemäß dem Lastausgleichverfahren:

Wie am Anfang bereits beschrieben wurde, erfolgt die Auswahl einer Speicherbank MB zur Erstellung einer neuen Aufzeichnung durch das Lastausgleichverfahren, die die Information über den Speicherlaststatus, die in jeder Speicherschnittstelle MI verfügbar ist, verwendet: Wenn eine Speicherbank niedriger Last vorhanden ist, wählt die Speicherschnittstelle die nächste in einer zyklischen Sequenz aus, die an derjenigen Speicherbank beginnt, die während des letzten durch das entsprechende MI ausgegebenen CREATE-Befehls ausgewählt wurde (im MI gibt es einen Indikator-RR, der dieses zuletzt verwendete MB identifiziert). Ist keine Speicherbank niedriger Last mehr vorhanden (das heißt, wurden alle MBs bereits hoch belastet), muß das MI unter allen installierten MBs eine Auswahl treffen; dies erfolgt ebenso durch den gleichen Round- Robin-Mechanismus.
Die vom Ml zur Auswahl eines MB auszuführenden Operationen werden im Flußdiagramm von Figur 7 dargestellt. Zuerst wird getestet, ob das eingestellte LL (MBs niedriger Last) leer ist, indem festgestellt wird, ob das LL nur Nullen enthält. (1) Wenn LL nicht nur Nullen enthält, das heißt, wenn es mindestens ein MB mit niedrigem Laststatus gibt, wird der RR- Wert um 1 erhöht (modulo m, die maximale Anzahl an MBs). Dies geschieht durch eine ROTATE1-ALU-Operation. Danach werden die Variablen RR und LL einer AND-Operation unterzogen. Ergibt das Ergebnis nur Nullen, hat das neue RR kein MB niedriger Last angetroffen und der Schritt muß wiederholt werden. Ergibt das Ergebnis nicht nur Nullen, hat das neue RR ein MB niedriger Last angetroffen und kann daher zur Auswahl des MB für die Ausführung des CREATE-Befehls verwendet werden. (2) Wenn LL nur Nullen sind, gibt es kein MB niedriger Last und folglich kann jedes beliebige MB verwendet werden. Auch hier wird das derzeitige RR um 1 erhöht (modulo m). Danach werden das neue RR und die Variable TL einer AND-Operation unterzogen. Ergibt das Ergebnis nur Nullen, hat das neue RR kein verfügbares MB angetroffen und der Schritt muß wiederholt werden. Ergibt das Ergebnis nicht nur Nullen, hat das neue RR ein verfügbares MB angetroffen und kann zur Auswahl des nächsten MB, auf das zur Erstellung einer neuen Aufzeichnung zugegriffen wird, verwendet werden.
Das ausgewählte MB wird durch die Inhalte von RR identifiziert. Diese RR-Inhalte werden nun zur weiteren Verarbeitung in das CMB geladen.

b) Auswahl eines NB, wenn das LRA bekannt ist:

Das LRA, das bei einem CREATE-Befehl vom MB wiedergegeben wird, ist ein 32-Bit-Identifikator, in dein die Bits 8, 9 und 10 einen Code enthalten, der das MB angibt (000 identifiziert MB Nummer 0; 001 identifiziert MB Nummer 1, usw.).
Daher weiß die MB-Logik, zu welchem MB sie eine Verbindung herstellen muß.
Die Auswahl eines MB für Befehle außer CREATE besteht in der Identifikation des LRA-Felds im MCW (das soeben in LS kopiert wurde), der Extraktion der Bits 8 bis 10 daraus, der Übersetzung dieses Drei-Bit-Codes in das im CMB verwendete Acht-Bit- Format und im Laden des resultierenden Werts in das CMB.

Claims

1. Technik für den Lastausgleich eines gemeinsam genutzten Speichers, der durch eine Mehrzahl an Speichereinheiten (17A, ... 17N) gebildet und von einer Mehrzahl an Benutzereinheiten (11A, ... 11N), die in der Lage sind, Befehle zu den genannten Speichereinheiten zu übertragen, gemeinsam genutzt wird, bei dem Befehlsantworten aus den Speichereinheiten zu den Benutzereinheiten zurückgeleitet werden, wobei die Technik die folgenden Schritte umfaßt:

- Erstellen einer Laststatustabelle, in der alle Benutzereinheiten aufgeführt sind, die den Speicherlaststatus der Speichereinheiten angibt; und, in jeder beliebigen Reihenfolge,

- Einfügen eines Laststatusindikators, der den Laststatus der genannten Speichereinheit angibt, in eine Befehlsantwort von einer Speichereinheit zu einer Benutzereinheit;

- Aktualisieren der Laststatustabelle einer Benutzereinheit, nachdem ein Laststatusindikator zusammen mit einer Befehlsantwort empfangen wurde;

- Senden einer Speicheraufzeichnungserstellungsanforderung einer Benutzereinheit gemäß ihrer Laststatustabelle, wodurch die Lasten der Speichereinheiten ausgeglichen werden.

2. Lastausgleichtechnik gemäß Anspruch 1, wobei

- eine Speicheroperation veranlaßt wird, indem ein Befehl von einer Benutzereinheit zu einer Speichereinheit gesendet wird;

- in jede Befehlsantwort ein Laststatusindikator eingefügt wird;

- jede Laststatustabelle einen Speicherlaststatus aller Speichereinheiten anzeigt;

- bevor ein Befehl von einer Benutzereinheit zur Anforderung der Erstellung einer neuen Speicheraufzeichnung in einer beliebigen Speichereinheit gesendet wird, die Laststatustabelle der Benutzereinheit abgefragt und eine Speichereinheit als Befehlsempfängerin ausgewählt wird, wenn in der genannten Tabelle ein niedriger Laststatus angegeben ist.

3. Lastausgleichtechnik gemäß Anspruch 1, bei dem

- der Laststatusindikator ein Binärzeichen ist, das entweder einen hohen oder einen niedrigen Laststatus anzeigt,

- und bei dem die Laststatustabelle für jede Speichereinheit mindestens eine Binärzeichenposition umfaßt, die mindestens den zuletzt von der entsprechenden Speichereinheit empfangenen Laststatusindikator anzeigt.

4. Lastausgleichtechnik gemäß Anspruch 3, bei dem

- ein bestimmter Prozentsatz seiner gesamten Speicherkapazität als Lastschwelle für jede Speichereinheit definiert ist;

- und bei dem der Laststatusindikator durch Vergleich der Menge an verfügbarem Speicherplatz mit der genannten Lastschwelle bestimmt wird.

5. Lastausgleichtechnik gemäß Anspruch 2 oder 3, bei dem

- zusammen mit jeder Benutzereinheit ein Identifikator gespeichert wird, der diese Speichereinheit identifiziert und der zuletzt als Erstellungsanforderungsempfänger ausgewählt wurde;

- eine zyklische Sequenz der Speichereinheiten definiert wird;

- und bei dem, wenn die Laststatustabelle einen niedrigen Laststatus für eine Mehrzahl an Speichereinheiten anzeigt, die erste von ihnen ausgewählt wird, die in der genannten Sequenz nach derjenigen folgt, die durch den genannten Identifikator als zuletzt ausgewählter Empfänger identifiziert wird.

6. Lastausgleichtechnik gemäß Anspruch 5, bei dem

- die erste Speichereinheit, die in der genannten Sequenz nach derjenigen folgt, die durch den genannten Identifikator als der zuletzt ausgewählte Empfänger identifiziert ist, wenn die Laststatustabelle nicht einen niedrigen Laststatus für eine der Speichereinheiten anzeigt.

7. Lastausgleichtechnik gemäß allen vorherigen Ansprüchen, bei dem

- für jede Speichereinheit ein Laststatusindikator eingerichtet wird, der den derzeitigen Laststatus der genannten Speichereinheit angibt;

- wenn von der Benutzereinheit ein CREATE-Befehl als Speicheraufzeichnungserstellungsanforderung gesendet wird, und wenn bei Empfang des CREATE-Befehls durch eine Speichereinheit eine Speicheraufzeichnung erstellt wird, ein Aufzeichnungsidentifikator zugeordnet ist und an die anfordernde Benutzereinheit eine Befehlsantwort gesendet wird, die den Laststatusindikator und den genannten Aufzeichnungsidentifikator umfaßt.

8. Lastausgleichtechnik gemäß Anspruch 7, bei dem

- wenn von einer Benutzereinheit ein PUT- oder ein RELEASE Befehl gesendet wird, um anzufordern, daß Daten in einer bestimmten Speicheraufzeichnung gespeichert werden sollen oder daß eine bestimmte Speicheraufzeichnung gelöscht werden soll, und beim Empfang des Befehls durch die Speichereinheit, die die Aufzeichnung enthält, die Daten hinzugefügt werden, die Aufzeichnung aufgelöst und der Laststatusindikator entsprechend aktualisiert und an die Benutzereinheit eine Befehlsantwort gesendet wird, die den Laststatusindikator umfaßt.

9. Gemeinsame Speichervorrichtung mit Lastausgleich, die eine Mehrzahl an Speichereinheiten (17A, ... 17N), eine Mehrzahl an Benutzereinheiten (11A, ... 11N) und ein Verbindungsnetz (15) umfaßt, das eine gemeinsame Nutzung der Speichereinheiten durch Benutzereinheiten, die Übertragung von Befehlen von einer Benutzereinheit zu einer Speichereinheit und umgekehrt die Übertragung von Befehlsantworten ermöglicht, wobei

- jede Benutzereinheit eine Laststatustabelle umfaßt, die den Speicherlaststatus der Speichereinheiten anzeigt und die entsprechend den empfangenen Befehlsantworten aktualisiert wird:

- jede der mindestens zwei Speichereinheiten umfaßt eine laststatusanzeigende Vorrichtung, die ihren Laststatus anzeigt;

- eine Befehlsantwort von einer Speichereinheit umfaßt einen Laststatusindikator, der dem Laststatus entspricht, der von der laststatusanzeigenden Vorrichtung der genannten Speichereinheit angezeigt wird;

- die gemeinsame Speichereinrichtung mit Lastausgleich umfaßt eine Speicherschnittstellenlogik, die Speicheraufzeichnungserstellungsanforderungen jeder Benutzereinheit entsprechend der Laststatustabelle der Benutzereinheit umleitet, wodurch die Lasten der Speichereinheiten ausgeglichen werden.

10. Gemeinsame Speichervorrichtung mit Lastausgleich gemäß Anspruch 9, wobei

- die Speicherschnittstellenlogik modular ist und jede Benutzereinheit ihr Modul (13A, ... 13N) der genannten Logik umfaßt, wobei jedes Modul eine oder mehrere der folgenden Komponenten umf aßt: einen Benutzerport (35), einen Verbindungsnetzport (33), einen Logik- und Steuerabschnitt 37 und einen lokalen Speicher (45) mit der Laststatustabelle:

- jede Speichereinheit umfaßt eine laststatusanzeigende Vorrichtung;

- die Vorrichtung wird durch das Hinzufügen oder Entfernen von Benutzer- und/oder Speichereinheiten nach Bedarf benutzergerecht angepaßt.