DE69031297T2

DE69031297T2 - Eingabewarteschlange für Speichersubsysteme

Info

Publication number: DE69031297T2
Application number: DE69031297T
Authority: DE
Inventors: Lawrence Andrew Paul Chisvin; John Koehler Grooms; Joseph Franklin Rantala
Original assignee: Digital Equipment Corp
Current assignee: Digital Equipment Corp
Priority date: 1989-07-06
Filing date: 1990-06-27
Publication date: 1998-04-02
Anticipated expiration: 2010-06-28
Also published as: US5388222A; JPH0652519B2; JPH03118649A; CA2020385A1; ATE157183T1; DE69031297D1; EP0407087B1; EP0407087A2; CA2020385C; EP0407087A3

Description

Gebiet der Erfindung

Die vorliegende Erfindung betrifft ein Speicherungs-Speichermanagement in einem Datenverarbeitungssystem mit einem durch mehrere Knoten gemeinsam nutzbaren Speicherbetriebsmittel, und insbesondere ein Verfahren und eine Schaltung zum Managen von Lese- und Schreibbefehlen für Daten vom gemeinsam nutzbaren Speicherbetriebsmittel, wie beispielsweise von Befehlen, die von Knoten kommen, mit einer beliebigen Kombination von "Zurückschreib"-Caches, "Durchschreib"- Caches oder keinen Caches auf demselben Datenbus.

Hintergrund der Erfindung

Datenverarbeitungssysteme, die mehrere Knoten und einen gemeinsamen Datenbus für die gemeinsame Nutzung von Daten von einem oder mehreren Speicherbetriebsmitteln enthalten, können Knoten enthalten, die ihre eigenen Speicher-"Caches" zum Speichern und zum Verarbeiten von Daten vom gemeinsam nutzbaren Speicher haben. "Knoten" im Datenverarbeitungssystem sind alle eindeutig identifizierbaren Einheiten, die mit demselben Speicherbetriebsmittel gekoppelt sind, wie beispielsweise zentrale Verarbeitungseinheiten (CPUs) und Eingabe-/Ausgabevorrichtungen. Der gemeinsam nutzbare Speicher hat allgemein eine Schnittstelle zu den Knoten über einen gemeinsamen Datenbus. Die Knoten mit solchen Caches müssen eine Schnittstelle zum gemeinsam nutzbaren Speicher haben, so daß Blöcke von Daten, auf die sie zugreifen und die sie erfassen, für jeden der Knoten verfügbar sind. Zu diesem Zweck können die Knoten entweder "Durchschreib"- oder "Zurückschreib"-Caches haben.
Wenn ein Knoten mit einem Durchschreib-Cache entscheidet, daß er auf einen bestimmten Block von Daten zugreifen muß, führt er einen Lesebefehl zu jener Stelle des Blocks im gemeinsam nutzbaren Speicher durch. Dies ändert den "Blockzustand" jenes Blocks im gemeinsam nutzbaren Speicher nicht. Der "Blockzustand" des Datenblocks zeigt den Status des Datenblocks an, wie beispielsweise "FREI" oder "IN BESITZ GENOMMEN".
Während die Daten im Cache eines Knotens sind, wird beim Lesen jenes Datenblocks von jenem Knoten auf die Kopie des Caches Bezug genommen, aber beim Schreiben zu jenem Datenblock wird der ursprüngliche Datenblock im gemeinsam nutzbaren Speicher erneuert. Der Schreibbefehl erneuert den gemeinsam nutzbaren Datenblock im Speicher, ändert aber nicht den Blockzustand der Daten. Wie es der Name impliziert, schreibt der Knoten durch den Cache und in den gemeinsam nutzbaren Speicher.
Mehr als ein Knoten kann denselben Block von Daten gleichzeitig im Cache speichern, aber alle im Cache speichernden Knoten müssen den Bus in bezug auf Schreibbefehle überwachen, die zu den Blöcken gerichtet sind, von denen sie Kopien in ihren jeweiligen Caches haben. Wenn ein Schreibbefehl zu einem im Cache gespeicherten Datenblock erfaßt wird, dann führen alle Knoten, die eine Kopie in ihrem Cache haben, eine Ungültigkeitsoperation bezüglich der Kopie durch, so daß sie nicht mehr verwendbar ist. Wenn sie einen Datenblock lesen müssen, nachdem ihre Cachekopie nicht mehr verwendbar ist, senden sie einen Lesebefehl zum Datenblock im gemeinsam nutzbaren Speicher, um eine reine" Kopie zu empfangen. Bei einem Durchschreib-Schema für ein Speichern im Cache ändern die Datenübertragungen zwischen dem Cache und dem gemeinsam nutzbaren Speicher den Blockzustand der Datenblöcke des gemeinsam nutzbaren Speichers nicht.
Wenn ein Knoten mit einem Zurückschreib-Cache entscheidet, daß er auf einen bestimmten Block von Daten zugreifen muß, besteht eine Art, auf die er ein Besitzerlesen an jener Stelle des Blocks im gemeinsam nutzbaren Speicher durchführen kann, darin, den Blockzustand jenes Blocks im gemeinsam nutzbaren Speicher auf "IN BESITZ GENOMMEN" zu setzen, während die Daten im Cache des Knotens sind.
Während die Daten im Cache der CPU sind, wird sowohl beim Lesen als auch beim Schreiben zu jenem Datenblock die Kopie des Caches verwendet. Ein Schreiben erneuert die Kopie des Caches der Daten, erneuert aber nicht die Kopie des gemeinsam nutzbaren Speichers. Die Kopie des gemeinsam nutzbaren Speichers wird erneuert, wenn der Knoten den Block "ablehnt", weil ein anderer Knoten wünscht, jenen Block des gemeinsam nutzbaren Speichers zu besitzen, oder wenn der besitzende Knoten ein Zugreifen auf einen Block beendet hat.
Beim Zurückschreib-Schema für ein Speichern im Cache beeinflussen die Datenübertragungen zwischen dem Cache und dem gemeinsam nutzbaren Speicher den Blockzustand der Blöcke des gemeinsam nutzbaren Speichers. Der Blockzustand wird auf IN BESITZ GENOMMEN gesetzt, wenn der Knoten den Datenblock "ausleiht", und der Blockzustand wird auf FREI gesetzt, wenn der Knoten den Datenblock "zurückbringt".
Wenn ein Knoten mit einem Zurückschreib-Cache einen Datenblock "borgt" und seinen Blockzustand auf IN BESITZ GENOMMEN setzt, nimmt er an, daß er die einzige offizielle Kopie des Datenblocks hat. Wenn ein Knoten mit einem Durchschreib-Cache versucht, denselben Datenblock in seinen Cache zu ziehen, ist es aus der vorangehenden Beschreibung der zwei Schemen für ein Speichern im Cache klar, daß die Integrität jenes Datenblocks verloren worden ist.
Knoten, die schließlich keine Art von Speichercache haben, arbeiten nur direkt an den im gemeinsam nutzbaren Speicher gespeicherten Daten. Solche Knoten erkennen kein "Besitzen" der gemeinsam nutzbaren Daten, wenn sie in Systemen verwendet werden, die Knoten mit Zurückschreib-Caches enthalten, so daß sie nicht unterscheiden können, wann die angeforderten Daten durch einen anderen der Knoten erneuert werden.

Zusammenfassung der Erfindung

Die Erfindung in ihrer allgemeinen Form besteht in einem Verfahren zum Lösen eines Konflikts bei einer Ausführung von Befehlen in einem Netz und in einer Schaltung dafür, wie es jeweils in den Ansprüchen 1 und 2 angegeben ist.
Die vorliegende Erfindung schafllt eine Kompatibilität eines gemeinsam nutzbaren Speicherbetriebsmittels zu allen der oben beschriebenen Knotentypen in einem Datenverarbeitungssystem bei einem gemeinsamen Datenbus. Eine spezielle Eingabewarteschlange für den gemeinsam nutzbaren Speicher erkennt Befehle von Knoten, die Durchschreib-Caches verwenden, von Knoten, die Zurückschreib- Caches verwenden, und schließlich von Knoten ohne Caches. Die Eingabewarteschlange ordnet Befehisadressen und Konfliktlösungszustände jedem empfangenen Lese- oder Schreibbefehl zu, und speichert die Befehle, Zustände und im Fall von Schreibbefehlen Schreibdaten oder zugehörige Maskendaten getrennt. Die gespeicherten Befehle werden aufgereiht, um Lese- und Schreibbefehle zu speichern, bis hinter potentiell konkurrierenden "Besitzer"-Befehlen von Knoten im System mit Zurückschreib-Caches "Ablehnungs"-Befehle folgen. Jedoch werden die Befehle verarbeitet und entsprechende Daten werden in den Speicher geschrieben, wobei die maskierenden Daten des so beschriebenen Speichers in einem Maskenpuffer gespeichert werden. Wenn die "Ablehnungs"-Befehle ausgeführt werden, werden die Daten, die in die im Maskenpuffer gespeicherten Stellen geschrieben worden sind, während der Ablehnungs-Schreiboperation nicht erneut geschrieben, was eine Kompatibilität sicherstellt. Lesebefehle mit Befehlsad ressen, die mit "Besitzer"- Lesebefehlen übereinstimmen, werden verzögert, bis die "Besitzer"-Lesebefehle verarbeitet werden.

Beschreibung der Zeichnungen

Fig. 1 ist ein Blockdiagramm eines allgemeinen Aufbaus für ein Speichereingabewarteschlangensystem gemäß dem bevorzugten Ausführungsbeispiel.
Fig. 2 ist ein Diagramm, das die Beziehungen der Befehls-/Adressenwarteschlange, der Maskenwarteschlange und der Datenwarteschlange im in Fig. 1 gezeigten Eingabewarteschlangensystem zeigt.
Fig. 3 ist ein funktionelles Blockdiagramm des in Fig. 1 gezeigten Eingabewarteschlangensystems.
Fig. 4 ist ein Blockdiagramm des Befehlslade- und -verarbeitungssystems für das in Fig. 1 gezeigte Eingabewarteschlangensystem.
Fig. 5 ist ein detailliertes Blockdiagramm des in Fig. 1 gezeigten bevorzugten Ausführungsbeispiels

Beschreibung des bevorzugten Ausführungsbeispiels

Unter Bezugnahme auf die Zeichnungen, wobei Bezugszeichen gleiche oder entsprechende Teile in allen Ansichten bezeichnen, ist Fig. 1 ein allgemeines Blockdiagramm eines Speichereingabewarteschlangensystems 2 gemäß der vorliegenden Erfindung. Das Eingabewarteschlangensystem 2 enthält eine Befehls-/Adressenwarteschlange 4 zum Empfangen von Lese- und Schreibbefehlen vom Datenverarbeitungssystem (nicht gezeigt) zum gemeinsam nutzbaren Speicherbetriebsmittel (nicht gezeigt), wozu das Eingabewarteschlangensystem 2 gehört.
Die Befehls-/Adressenwarteschlange 4 hat einen Befehls-/Adressenpuffer 6 mit einer Vielzahl von Befehls-/Adressenschlitzen 8, von denen jeder Information halten kann, die zu einem vollständigen Lese- oder Schreibbefehl gehört. In Fig. list der Befehls-/Adressenpuffer 4 mit 12 Schlitzen 8 gezeigt, obwohl gemäß einer Wahl beim Aufbau irgendeine Anzahl von Schlitzen 8 verwendet werden kann. Die Information in jedem der Schlitze 8 ist derart angeordnet, daß sie einen Befehlstyp, eine Befehlslänge, eine Befehlsidentifikation, eine Befehlsadresse, Eingabedatenspeicherzeigerinformation und einen Befehlsstatus anzeigt. Tabelle I zeigt eine Anordnung von Feldern, die für diesen Zweck geeignet ist. TABELLE I
Das Eingabewarteschlangensystem 2 enthält auch eine Eingabedatenmaskenwarteschlange 10. Die Eingabedatenmaskenwarteschlange 10 hat einen Eingabedatenmaskenpuffer 12 mit einer Vielzahl von Maskenschlitzen 14, wobei jeder Schlitz 14 für Information darüber reserviert ist, welche Bytes eines Speicherwortes durch einen entsprechenden Schreibbefehl in einem der Schlitze 8 des Befehls-/Adressenpuffers 6 in der Befehls-/Adressenwarteschlange 4 zu modifizieren sind. Obwohl der Eingabedatenmaskenpuffer 12 in Fig. 1 mit 12 Schlitzen 14 gezeigt ist, um für jeden der Schlitze 8 im Befehls-/Adressenpuffer 6 einen entsprechenden der Schlitze 14 im Eingabedatenmaskenpuffer 12 vorzusehen, kann der Eingabedatenmaskenpuffer 12 gemäß einer Wahl beim Aufbau eine größere oder kleinere Anzahl von Schlitzen 14 entsprechend einer größeren oder kleineren Anzahl von Schlitzen 8 im Befehls-/Adressenpuffer 6 haben.
Das Eingabewarteschlangensystem 2 enthält auch eine Schreibdatenwarteschlange 16. Die Schreibdatenwarteschlange 16 hat einen Schreibdatenpuffer 18 mit einer Vielzahl von Datenschlitzen 20. Die Schlitze 20 im Datenpuffer 18 sind in den Speicher zu schreibenden Schreibdaten mit entsprechenden Schreibbefehlen in der Befehls-/Adressenwarteschlange 4 zugeordnet. Obwohl in Fig. 1 24 Schlitze 20 gezeigt sind, kann der Datenpuffer 18 gemäß einer Wahl beim Aufbau eine größere oder kleinere Anzahl haben.
Fig. 2 zeigt ein Beispiel davon, wie die Befehls-/Adressenwarteschlange 4 eine Schnittstelle mit der Eingabedatenmaskenwarteschlange 10 und der Schreibdatenwarteschlange 16 bildet. Jeder der Befehls-/Adressenpufferschlitze 8 hat einen Maskenzeiger 22 zu einem entsprechenden der Maskenschlitze 14. Wenn der Befehl in einem der Befehls-/Adressenschlitze 8 ein Schreibbefehl ist, enthält der zu jenem Befehls-/Adressenschlitz 8 gehörende Maskenschlitz 14 entsprechende Maskendaten, die auf geeignete Weise bestimmen, welche Bytes des Speicherwortes, das Gegenstand des Befehis ist, modifiziert werden. Wenn der Befehl in den Befehls-/Adressenschlitzen 8 vom Lesetyp ist, sind die Daten in dem einen der Maskenschlitze 14, der zum Befehls-/Adressenschlitz 8 gehört, nicht bedeutsam und ist in Fig. 2 durch einen gestrichelten Pfeil für jeden zugehörigen der Maskenzeiger 22 dargestellt. Den Befehls-/Adressenschlitzen 8 im Befehlsadressenpuffer 6 der Befehls-/Adressenwarteschlange 4, die Schreibbefehle enthalten, sind Schreibdatenzeiger 24 zugeordnet, die auf einen entsprechenden der Schreibdatenschlitze 20 im Schreibdatenpuffer 18 der Schreibdatenwarteschlange 16 zeigen. Der eine der Schreibdatenschlitze 20, auf den der entsprechende der Datenzeiger 24 zeigt, stellt die erste einer möglichen Anordnung aufeinanderfolgender Schreibdatenschlitze 20 für den entsprechenden Befehl in einem der Befehls-/Adressenschlitze 8 dar. Ein Lesebefehl in einem der Befehls-/Adressenschlitze 8 hat keinen entsprechenden Datenzeiger 24, da es keine ihm zugehörigen Schreibdaten gibt.
Fig. 2 zeigt mehrere Befehle, die in die Schlitze 8 des Befehls-/Adressenpuffers 6 in der Befehlsadressenpufferwarteschlange 4 geladen sind. Der erste der Schlitze 8, der als "Schlitz 0" identifiziert ist, hat einen "Ablehnungsschreib"-Befehl im Befehlstypenfeld, das mit "DWMASK" bezeichnet ist. Die Speicheradresse für diesen Befehl ist als "0020A" im Befehlsadressenfeld gezeigt. Die Länge der zu schreibenden Daten ist als Hexawort gezeigt, das im Befehlslängenfeld mit "HEXA" bezeichnet ist. Die Identifikation der Einheit, die den Befehl hervorbringt, wie beispielsweise eine CPU, ist im Befehls-ID-Feid als "0A" gezeigt. Der Status des Schlitzes 8, der mit "Schlitz 0" bezeichnet ist, ist im Befehlsschlitz-Statusfeld als "NEU" gezeigt. Der bezeichnete der Schreibdatenschlitze 20, zum diese Daten zu schreiben sind, im Schreibdatenpuffer 18 der Schreibdatenwarteschlange 16 ist im Zeigerfeld des ersten Datenwortes als "2" gezeigt, was die Bedeutung desjenigen der Schreibdatenschlitze 20 hat, der mit "Schlitz 2" bezeichnet ist.
In diesem Fall ist einer der Maskenzeiger 20 des mit "Schlitz 0" bezeichneten Schlitzes 8 zu einem entsprechenden der Eingabedatenmaskenschlitze 14 im Eingabedatenmaskenpuffer 12 der Eingabedatenmaskenwarteschlange 10 gerichtet. Der mit "Schlitz 0" bezeichnete Schlitz 14 hat 32 Bits von Maskendaten für ein Hexawort, oder 32 Bytes für die Länge von Schreibdaten, die die Bytes des Speicherwortes bezeichnen, das im mit "Schlitz 0" bezeichneten Schlitz 8 adressiert ist, der durch die Schreibdaten beginnend bei dem bestimmten der Schlitze 20 im Schreibdatenpuffer 18 zu modifizieren ist. Jedes Bit der Maskendaten stellt ein Byte der Schreibdaten dar. Da die Schreibdaten beginnend beim mit "Schlitz 2" bezeichneten Schlitz 20 gezeigt sind und die Länge der Schreibdaten ein Hexawort oder 32 Bytes ist, erstrecken sich die Schreibdaten für die Anzahl aufeinanderfolgender Schlitze vom mit "Schlitz 2" bezeichneten Schlitz 20 zum Unterbringen der Daten. In Fig. 2 ist jeder der Schreibdatenschlitze 20 mit acht Bytes bezüglich der Länge gezeigt. Daher erstrecken sich die Schreibdaten für den Schreibbefehl im mit "Schlitz 0" bezeichneten Schlitz 8 vom mit "Schlitz 2" bezeichneten Schlitz 20 zum mit "Schlitz 5" bezeichneten Schlitz 20.
Die "Ablehnungsschreib"-Bestimmung für den Befehl im mit "Schlitz 0" bezeichneten Schlitz 8 bedeutet, daß der Befehl von einem Knoten mit einem Zurückschreib- Cache im System ist, das "ausgeprüfte" Daten beginnend von der identifizierten Adresse hat und sie nun mit diesem Schreibbefehl ablehnt, der ein Modifizieren der "ausgeprüften" Daten enthält. Der Status "NEU" bedeutet, daß der Befehl in das Eingabewarteschlangensystem 2 geladen worden ist und dazu bereit ist, in einer First-ln-First-Out-(FIFO)-Reihenfolge verarbeitet zu werden, wenn der gemeinsam nutzbare Speicher (nicht gezeigt) nicht mehr mit dem vorherigen Befehl beschäftigt ist.
Der als "Schlitz 1" identifizierte zweite der Schlitze 8 im Befehls-/Adressenpuffer 6 hat einen "Besitzerlese"-Befehl im Befehlstypenfeld, das mit "OREAD" bezeichnet ist. Die Speicheradresse für diesen Befehl ist im Befehlsadressenfeld als "01C04" gezeigt. Die Länge der zu lesenden Daten ist im Befehlslängenfeld als Hexawort gezeigt. Die Identifikation der Einheit, die den Befehl hervorbringt, ist im Befehls-ID- Feld als "11" gezeigt. Der Status des mit "Schlitz 1" bezeichneten Schlitzes 8 ist im Befehlsschlitz-Statusfeld als "NEU" gezeigt. Es gibt im Zeigerfeld für das erste Datenwort keine Schreibdatenzeigerbestimmung, weil dies ein Lesebefehl ist. Da dies ein Lesebefehl ist, ist der Maskenzeiger 22 zum Eingabedatenmaskenschlitz 14 des mit "Schlitz 1" bezeichneten Eingabedatenmaskenpuffers 12 als gestrichelter Pfeil gezeigt, und im mit "Schlitz 1" bezeichneten Schlitz 14 sind keine Maskendaten gezeigt.
Die "Besitzerlese"-Bestimmung für den Befehl im mit "Schlitz 1" bezeichneten Schlitz 8 bedeutet, daß der Befehl von einem Knoten mit einem Zurückschreib- Cache im System ist, das Daten beginnend von der bestimmten Adresse für die angezeigte Datenlänge "ausprüft". Wiederum bedeutet der Status "NEU", daß der Befehl in das Eingabewarteschlangensystem 2 geladen worden ist und dazu bereit ist, verarbeitet zu werden.
Der dritte als "Schlitz 2" identifizierte der Schlitze 8 im Befehls-/Adressenpuffer 6 hat einen "Schreib"-Befehl im Befehlstypenfeld, das mit "WMASK" bezeichnet ist. Die Speicheradresse für diesen Befehl ist im Befehlsadressenfeld mit "20000" gezeigt. Die Länge der zu schreibenden Daten ist im Befehlslängenfeld als Oktawort oder 16 Bytes gezeigt. Die Identifikation der Einheit, die den Befehl hervorbringt, ist im Befehls-ID-Feid als "10" gezeigt. Der Status des mit "Schlitz 2" bezeichneten Schlitzes 8 ist im Befehlsschlitz-Statusfeld als "NEU" gezeigt. Der bestimmte der Schreibdatenschlitze 20 mit den zu schreibenden Daten ist im Zeigerfeld für das erste Datenwort als "6" gezeigt, was bedeutet, daß sein zugehöriger Zeiger 24 auf einen der Schreibdatenschlitze 20 zeigt, der mit "Schlitz 6" bezeichnet ist.
In diesem Fall ist einer der Maskenzeiger 22 des mit "Schlitz 2" bezeichneten Schlitzes 8 auf einen entsprechenden der Eingabedatenmaskenschlitze 14 im Eingabedatenmaskenpuffer 12 der Eingabedatenmaskenwarteschlange 10 gerichtet. Der mit "Schlitz 2" bezeichnete Schlitz 14 hat 32 Bits von Maskendaten für eine Hexawortlänge von Schreibdaten, die die Bytes des im Schlitz 8 adressierten Speicherwortes bezeichnen, das durch die Schreibdaten beginnend beim bestimmten der Schlitze 20 im Schreibdatenpuffer 18 zu modifizieren ist. Da die Schreibdaten beginnend beim mit "Schlitz 6" bezeichneten Schlitz 20 gezeigt sind, und die Länge der Schreibdaten ein Oktawort oder 16 Bytes ist, erstrecken sich die Schreibdaten vom mit "Schlitz 6" bezeichneten Schlitz 20 zum mit "Schlitz 7" bezeichneten Schlitz 20, da jeder dieser Schlitze acht Bytes lang ist.
Die "Schreib"-Bestimmung für den Befehl im Schlitz 8, der als "Schlitz 2" bezeichnet ist, zeigt an, daß sie ein Schreibbefehl von einem der Knoten ist. Der Status "NEU" bedeutet, daß der Befehl in das Eingabewarteschlangensystem 2 geladen worden ist und dazu bereit ist, verarbeitet zu werden.
Der vierte der Schlitze 8, der als "Schlitz 3" identifiziert ist, im Befehls-/Adressenpuffer 6 hat einen "Lese"-Befehl im Befehlstypenfeld, das mit "LESEN" bezeichnet ist. Die Speicheradresse für diesen Befehl ist im Befehlsadressenfeld als "ABCDE" gezeigt. Die Länge der zu lesenden Daten ist im Befehlslängenfeld, das mit "QUAD" bezeichnet ist, als Quadwort gezeigt. Die Identifikation der Einheit, die den Befehl hervorbringt, ist im Befehls-ID-Feld als "2F" gezeigt. Der Status des mit "Schlitz 3" bezeichneten Schlitzes 8 ist im Befehlsschlitz-Statusfeld als "WARTEN" gezeigt. Es gibt im Zeigerfeld für das erste Datenwort keine Schreibdatenzeigerbestimmung, weil dies ein Lesebefehl ist. Da dies ein Lesebefehl ist, ist der Maskenzeiger 22 zum Eingabedatenmaskenschlitz 14 des Eingabedatenmaskenpuffers 12, der mit "Schlitz 3" bezeichnet ist, als gestrichelter Pfeil gezeigt, und im Schlitz 14, der mit "Schlitz 3" bezeichnet ist, sind keine Maskendaten gezeigt.
Die "Lese"-Bestimmung für den Befehl im mit "Schlitz 3" bezeichneten Schlitz 8 bedeutet, daß sie ein Lesebefehl von einem der Knoten ist. Der Status "WARTEN" bedeutet, daß dieser Befehl schon verarbeitet worden ist, während er im Zustand "NEU" ist, aber aus irgendeinem Grund noch anhängig ist. Der Status dieses Befehis ändert sich zum Zustand "ÜBEREINSTIMMUNG", wenn der mit "Schlitz 3" bezeichnete Schlitz 8 dazu bereit ist, beendet zu werden.
Der fünfte als "Schlitz 4" identifizierte der Schlitze 8 im Befehls-/Adressenpuffer 6 hat einen mit "Schreiben" bezeichneten Befehl im Befehlstypenfeld, das mit "WMASK" abgekürzt ist. Die Speicheradresse für diesen Befehl ist im Befehlsadressenfeld als "ABCDE" gezeigt. Die Länge von zu schreibenden Daten ist im Befehlslängenfeld als Quadwort gezeigt. Die Identifikation der Einheit, die den Befehl hervorbringt, ist im Befehls-ID-Feld als "3A" gezeigt. Der Status des mit "Schlitz 4" bezeichneten Schlitzes 8 ist im Befehlsschlitz-Statusfeld als "WARTEN" gezeigt. Es gibt im Zeigerfeld für das erste Datenwort keine Schreibdatenzeigerbestimmung, weil dieser Befehl schon verarbeitet worden ist, wie es durch seinen "WARTE"- Status angezeigt wird.
Einer der Maskenzeiger 22 des mit "Schlitz 4" bezeichneten Schlitzes 8 ist auf einen entsprechenden der Eingabedatenmaskenschlitze 14 im Eingabedatenmaskenpuffer 12 der Eingabedatenmaskenwarteschlange 10 gerichtet. Der mit "Schlitz 4" bezeichnete Schlitz 14 hat eine Hexawort-Länge von Maskendaten, die die Bytes des im Schlitz 8 adressierten Speicherwortes bestimmen, die durch die Schreibdaten entsprechend dem Schreibbefehl im mit "Schlitz 4" bezeichneten Schlitz 8 modifiziert worden sind. Natürlich ist dieser Befehl schon verarbeitet worden, so daß die Daten schon modifiziert worden sind. Somit zeigt diese Maskeninformation für diesen Befehl im mit "Schlitz 4" bezeichneten Schlitz 14 an, welche Bytes des adressierten Speicherwortes durch die Verarbeitung dieses Befehis modifiziert worden sind.
Der sechste als "Schlitz 5" identifizierte der Schlitze 8 im Befehls-/Adressenpuffer 6 hat einen "Lese"-Befehl im Befehlstypenfeld, das mit "LESEN" bezeichnet ist, die Speicheradresse für diesen Befehl ist im Befehlsadressenfeld als "0101 E" gezeigt. Die Länge der zu lesenden Daten ist als Oktawort gezeigt, das durch "OCTA" bezeichnet ist. Die Identifikation der Einheit, die den Befehl hervorbringt, ist im Befehls-ID-Feld als "34" gezeigt. Der Status des mit "Schlitz 5" bezeichneten Schlitzes 8 ist im Befehlsschlitz-Statusfeld als "NEU" gezeigt. Es gibt im Zeigerfeld für das erste Datenwort keine Schreibdatenzeigerbestimmung, weil dies ein Lesebefehl ist. Da dies ein Lesebefehl ist, ist der Maskenzeiger 22 zum mit "Schlitz 5" bezeichneten Eingabedatenmaskenschlitz 14 des Eingabedatenmaskenpuffers 12 als gestrichelter Pfeil gezeigt, und im mit "Schlitz 5" bezeichneten Schlitz 14 sind keine Maskendaten gezeigt.
Die übrigen sechs der mit "Schlitz 6" bis "Schlitz 11" bezeichneten Schlitze 8 im Befehls-/Adressenpuffer 6 haben in ihren jeweiligen Befehlsschlitz-Statusfeldern alle einen Zustand, der mit "FREI" bezeichnet ist. Die anderen Felder sind leer. Der Zustand "FREI" bedeutet, daß diese Schlitze 8 zum Empfangen neuer Befehle in einer FIFO-Reihenfolge bereit sind. Wenn ein neuer Befehl in das Eingabewarteschlangensystem 2 geladen wird, speichert der mit "Schlitz 6" bezeichnete Schlitz 8 den Befehl, und der Zustand ändert sich zu "NEU". Gleichermaßen speichert dann, wenn ein nachfolgender Befehl in das Eingabewarteschlangensystem 2 geladen wird, der mit "Schlitz 7" bezeichnete Schlitz 8 den nachfolgenden Befehl, und der Zustand ändert sich zu "NEU". Der im mit "Schlitz 7" bezeichneten Schlitz 8 gespeicherte Befehl wird verarbeitet. Gleichermaßen speichern und verarbeiten die mit "Schlitz 8" bis "Schlitz 11" bezeichneten Schlitze 8 zusätzliche Befehle, die in das Eingabewarteschlangensystem 2 geladen sind.
Fig. 3 ist ein vereinfachtes Blockdiagramm des Eingabewarteschlangensystems 2, das nur die wesentlichen Elemente zeigt. Leitungen, die zum Verbinden von Datenfeldern zwischen den Elementen gezeigt sind, sind in Wirklichkeit eine Vielzahl von Leitungen, um die gesamten Datenfelder unterzubringen. Jeder Befehl wird in einen bestimmten Befehlsspeicherschlitz 26 eines Eingabespeicherpuffersystems 28 geladen. Auf jeden Befehl wird durch seine Identifikation in einem entsprechenden Eingabezeigerschlitz 30 einer Befehlsanfangsblockzeigerwarteschlange 32 Bezug genommen. Ein Zeigeridentifikationsfeld am Ausgang der Befehlsanfangsblockzeigerwarteschlange 32 führt in einen Eingang eines Entscheidungsmultiplexers 34 auf einer Leitung 36. Ein Befehlsauswahlfeld vom Ausgang des Entscheidungsmultiplexers 34 führt auf einer Leitung 40 in einen Auswahleingang eines Befehlsauswahlmultiplexers 38. Der Auswahimultiplexer 38 wählt die eine einer Vielzahl von Eingabespeicherschlitzleitungen 42 aus, die mit jedem der Schlitze 26 im Eingabespeicherpuffer 28 gekoppelt ist, der ein Befehlsadressenfeld entsprechend dem Befehlsauswahlfeld hat, auf der Leitung 40. Der Auswahlmultiplexer 38 erzeugt dann ein Ausgabefeld mit dem im ausgewählten Schlitz 26 an einem Anfangsblock einer Warteschlangenleitung 44 gespeicherten Befehl. Der auf der Leitung 44 ausgegebene Befehl wird dann verarbeitet. Jeder der Schlitze 26 weist eine ihm zugehörige Befehlsadresse auf, und die Adresse jedes der Schlitze 26, die einen Befehl enthalten, wird mit der Adresse eines Befehls am Anfang der Warteschlangenleitung 44 in einer Komparatorschaltung 46 über eine Vielzahl von Vergleichsleitungen 48 von jedem der Schlitze 26 und über eine mit der Leitung 44 gekoppelten Befehlsausgabesignalleitung 51 verglichen. Wenn eine der Befehisadressen in den Schlitzen 26 des Eingabespeicherpuffers 28 mit der Adresse der Befehlsadresse am Anfang der Warteschlangenleitung 44 über die Leitung 51 übereinstimmt, zeigt die Ausgabe der Komparatorschaltung 46 die Übereinstimmung dem Eingabezeigerentscheidungsmultiplexer 34 über eine Leitung 50 an. An dieser Stelle wird eine Konfliktlösung in bezug auf das Eingabewarteschlangensystem 2 durchgeführt, und der Multiplexer 34 löst die Auswahl der neuen Eingabezeigerwarteschlange 32 und wählt statt dessen eine Konfliktlösungsschaltung 52 aus, die mit dem Multiplexer 34 über eine Leitung 54 gekoppelt ist. Die Konfliktlösungsschaltung 52 wählt jede der Befehlsadressen aus, die mit der Adresse an dem Befehlsfeld am Anfang der Warteschlangenleitung 44 übereinstimmt, in einer Reihenfolge der Schlitzadressen ihrer Schlitze 26, und zwar die niedrigste zuerst. Jede der übereinstimmenden Befehlsadressen wird gelöscht, sobald ihre zugehörigen Lesebefehle durchgeführt werden, so daß auf ein Durchführen aller übereinstimmenden Adressen hin die Komparatorschaltung 46 zuläßt, daß der Multiplexer 34 die Auswahl der Konfliktlösungsschaltung 52 löst und wiederum die neue Eingabezeigerwarteschlange 32 auswählt.
Fig. 4 zeigt, wie Befehle in das Eingabewarteschlangensystem 2 geladen werden und von ihm verarbeitet werden. Befehle werden sequentiell in die Vielzahl von Schlitzen 30 der in Fig. 3 gezeigten kreisförmigen Befehlsanfangszeigerwarteschlange 32 geladen. Zwölf der Schlitze 30 sind in Fig. 4 gezeigt, obwohl eine grö ßere oder kleinere Anzahl von Schlitzen 30 gemäß einer Wahl beim Aufbau verwendet werden kann. Die Befehle werden gemäß der Richtung eines Endzeigers 60 geladen, der sequentiell auf jeden der Befehle zum niedrigsten freien der Schlitze 30 zeigt. Die Kästen an den Enden der Zeiger 60 und 62, die jeweils die Werte "5" und "1" enthalten, stellen lediglich die Adressen der Schlitze 30 dar, zu denen sie zeigen. Neue Befehle werden gemäß der Richtung eines Anfangszeigers 62 sequentiell verarbeitet, der sequentiell auf jeden der Befehle zum niedrigsten der Schlitze 30 mit einem Befehlseintrag zeigt. Zwischen den neuen Befehlen können zerlegte Lesebefehle liegen.
Das Eingabewarteschlangensystem 2 hat auch eine Befehlspufferanordnung 64, die eine Vielzahl von Befehlspufferschlitzen 66 enthält. Zwölf der Befehlspufferschlitze 66 sind gezeigt, obwohl eine größere oder kleinere Anzahl von Schlitzen 66 verwendet werden kann. Es kann wie bei den Schlitzen 30 eine größere oder kleinere Anzahl von Schlitzen 66 geben. Der Befehlspufferschlitz 66, auf den ein Zeiger 68 zeigt, enthält die Befehlsadresse, den Befehlstyp, den Status, die Länge, eine Knoten-ID und eine Maskeninformation für den Befehl mit derselben Schlitzadresse, gespeichert in der Befehlsanfangszeigerwarteschlange 32. Die Befehlspufferanordnung 64 ist funktionell das Äquivalent zur Eingabebefehls4adressenwarteschlange 4 und zur Eingabedatenmaskenwarteschlange 10.
Fig. 5 ist ein detailliertes Blockdiagramm des bevorzugten Ausführungsbeispiels in Fig. 1, das zeigt, wie die Hauptelemente miteinander verbunden sind. Leitungen, die zum Verbinden von Datenfeldern zwischen den Elementen gezeigt sind, sind in Wirklichkeit eine Vielzahl von Leitungen zum Unterbringen der gesamten Datenfelder. Die oben beschriebene Befehlsanfangszeigerwarteschlange 32 in Fig. 3 ist in der Befehls-/Adressenwarteschlange 4 enthalten. Wenn Befehle durch das Eingabewarteschlangensystem 2 empfangen werden, werden die Befehle in den Befehls4adressenpuffer 6, den Eingabedatenmaskenpuffer 12 und den Eingabedatenpuffer 18 geladen, wie es oben in Verbindung mit Fig. 1 beschrieben ist. Gleichzeitig wird die Schlitzadresse jedes Befehls in den Schlitzen 8 des Befehls-/Adressenpuffers 6 in einen entsprechenden der Schlitze 30 der Befehlsanfangszeigerwarteschlange 32 eingegeben. Das Schlitzadressenfeld am Anfang der Befehlsanfangszeigerwarteschlange 32 wird zu einem Eingang des Multiplexers 34 mit zwei Eingängen über die Leitung 36 geführt. Der Multiplexer 34 wählt normalerweise die Leitung 36 aus und läßt das Schlitzadressenfeld auf der Leitung 36 über seinen Ausgang auf die Leitung 40 durch.
Das Schlitzadressenfeld auf der Leitung 40 wird zum Auswahleingang des Befehls-/Adressenmultiplexers 38 mit einer Vielzahl von Multiplexereingängengeführt. In Fig. 5 ist der Befehls-/Adressenmultiplexer 38 mit 12 Multiplexereingängen gezeigt, um einen separaten Eingang für jeden der Schlitze 8 des Befehls4adressenpuffers 6 bereitzustellen. Eine größere oder kleinere Anzahl von Eingängen kann in Abhängigkeit von der Anzahl von Schlitzen 8 im Befehls-/Adressenpuffer 6 und solange wie der Befehls-Iadressenmultiplexer 38 wenigstens einen Eingang für jeden der Schlitze 8 hat, verwendet werden. Jeder der Schlitze 8 führt einen der Eingänge des Multiplexers 38 über eine der Vielzahl von Leitungen 42. Der Multiplexer 38 wählt den einen der Schlitze 8 mit einem Schlitzadressenfeld, das mit jenem auf der Leitung 40 vom Multiplexer 34 übereinstimmt. Der Multiplexer 38 läßt den Befehlstyp, die Adresse, die Länge, die Knoten-ID und die Statusdaten des Befehls im ausgewählten der Schlitze 8 auf der Leitung 44 durch. Diese Befehls- und Adressendaten sind die Ausgabe für den Anfang der Befehls-/Adressenwartesch lange 4.
Gleichzeitig werden die Befehls- und Adressendaten auf der Leitung 44 zu einem Referenzeingang der Komparatorschaltung 46 über die Leitung 51 übertragen. Die Komparatorschaltung 46 hat eine Vielzahl von Vergleichseingängen und - ausgängen mit wenigstens so vielen Vergleichseingängen und -ausgängen, wie es Schlitze 8 im Befehlsadressenpuffer 6 gibt. In Fig. 5 hat die Komparatorschaltung 46 12 Vergleichseingänge und 12 Vergleichsausgänge mit einem Referenzeingang. Jeder der Schlitze 8 führt einen der Vergleichseingänge der Komparatorschaltung 46 über einer einer Vielzahl der Leitung 48. Die Komparatorschaltung 46 vergleicht die über die Leitung 51 zum Referenzeingang geführte Befehlsadresse mit den Befehlsadressen jedes der Befehle in den Schlitzen 8. Wenn es eine Übereinstimmung gibt, wird die Schlitzadresse des Schlitzes 8 für die übereinstimmende Befehlsadresse durch einen entsprechenden der Vergleichsausgänge durchgelassen und zu einem entsprechenden einer Vielzahl von Übereinstimmungsschlitzen 86 in einem Übereinstimmungspuffer 88 über eine Vielzahl von Leitungen 89 geführt. Der Übereinstimmungspuffer 88 hat wenigstens so viele Schlitze 86, wie es Schlitze 8 im Befehls-/Adressenpuffer 6 gibt. In Fig. 5 sind 12 Schlitze 86 gezeigt.
Jeder der Schlitze 86 speichert auch den Typ des entsprechenden Befehls, der mit der Adresse des Befehls am Anfang der Befehls-/Adressenwarteschlange übereinstimmt, so daß die Übereinstimmung als Leseübereinstimmung, Schreibübereinstimmung oder Ablehnungsschreibübereinstimmung identifiziert werden kann. Die Schlitzadressen der Übereinstimmungen werden aufeinanderfolgend von der niedrigsten Schlitzadresse der Schlitze 86 des Übereinstimmungspuffers 88 gelesen, und jede Schlitzadresse wird über die Leitung 54 zu einem zweiten Eingang des Multiplexers 34 geführt. Der Übereinstimmungspuffer 88 identifiziert auch den Typ des von jedem der Schlitze 86 über eine entsprechende einer Vielzahl von Leitungen 92 gelesenen Befehls. Diese Befehlstypendaten werden über einen Datenbus 100 zu jeweiligen Eingängen einer Leseübereinstimmungsgatterschaltung 94, einer Schreibgatterschaltung 96 und einer Ablehnungsschreibgatterschaltung 98 übertragen. Alternativ dazu kann die Komparatorschaltung 46 zur Übertragung der Befehls-/Adressendaten von jedem der Schlitze mit übereinstimmenden Adressen direkt von den Schlitzen 8 zum Datenbus 100 aufgebaut sein.
Wo es eine Leseübereinstimmung gibt, führt die Leseübereinstimmungsgatterschaltung 95 ein Auswahlsignal an ihren Ausgang, das über die Leitung 50 zu einem Auswahleingang am Multiplexer 34 geführt wird. Das Signal auf der Leitung 50 veranlaßt, daß der Multiplexer 34 die Schlitzadresse vom Übereinstimmungspuffer 88 auf der Leitung 54 statt der Schlitzadresse auf der Leitung 36 von der neuen Befehlsanfangszeigerwarteschlange 32 wählt. Der Multiplexer 34 läßt dann die Schlitzadresse auf der Leitung 54 zum Auswahleingang des Befehls-/Adressenmultiplexers 38 über die Leitung 40 durch. Der Multiplexer 38 wählt dann den Schlitz 8 des Befehls-/Adressenpuffers 6 mit der entsprechenden Schlitzadresse. Auf diese Weise ändert die Erfassung einer Leseübereinstimmung die Reihenfolge von Verarbeitungsbefehlen von der durch die Befehlsanfangszeigerwarteschlange 32 aufgebauten Reihenfolge zu der Reihenfolge der Übereinstimmungen in den Schlitzen 86 des Übereinstimmungspuffers 88.
Schreibbefehle enthalten ein Auswählen der geeigneten Maskendaten und Eingabedaten vom Eingabewarteschlangensystem 2. Dies ändert die Verarbeitungsreihenfolge nicht. Die Schlitzadresse auf der Leitung 40 wird über eine Leitung 106 auch zu einem Auswahleingang eines ersten Maskenmultiplexers 104 mit einer Vielzahl von Multiplexereingängen geführt. Der Multiplexer 104 hat wenigstens so viele Multiplexereingänge, wie es Schlitze 14 im Eingabedatenmaskenpuffer 12 gibt. In Fig. 5 hat der Multiplexer 104 12 Eingänge, wobei jeder der Schlitze 14 des Eingabedatenmaskenpuffers 12 einen der Multiplexereingänge des Multiplexers 104 über eine entsprechende einer Vielzahl von Leitungen 108 führt. Der Multiplexer 104 wählt den einen der Schlitze 14 mit einer Schlitzadresse, die mit der Schlitzadresse auf der Leitung 106 übereinstimmt, und läßt die Maskendaten für den ausgewählten Schlitz 14 über seinen Ausgang zu einer Leitung 110 durch. Somit entsprechen die Maskendaten auf der Leitung 110 den Befehls-/Adressendaten auf der Leitung 44.
Die Schlitzadresse auf der Leitung 40 wird auch über eine Leitung 116 zum Auswahleingang eines Datenzeigermultiplexers 114 mit einer Vielzahl von Multiplexereingängen geführt. Der Multiplexer 114 hat wenigstens so viele Multiplexereingänge, wie es Schlitze 8 im Befehls-/Adressenpuffer 6 gibt. In Fig. 5 hat der Multiplexer 114 12 Multiplexereingänge, wobei zu jedem Multiplexereingang einer der Schlitze 8 über eine entsprechende einer Vielzahl von Leitungen 118 führt. Der Multiplexer 114 wählt den einen der Schlitze 8 mit einer Schlitzadresse aus, die mit der Schlitzadresse auf der Leitung 116 übereinstimmt, und läßt die Datenzeigerdaten vom ausgewählten Schlitz 8 zu einem Eingang einer wohlbekannten Lade-/Inkrementier-Logikschaltung 120 "ber eine Leitung 122 durch. Die Lade-/Inkrementier-Logikschaltung 120 lädt anfangs die Datenzeigerdaten auf der Leitung 122 über ihren Ausgang auf einer Leitung 124 in Antwort auf ein zu einem Logikeingang auf einer Leitung 126 geführten Inkrementier-Logiksteuerfeld. Das Inkrementier-Logiksteuerfeld wird durch eine wohlbekannte Inkrementier- Logiksteuerschaltung (nicht gezeigt) zugeführt.
Die Datenzeigerdaten auf der Leitung 124 werden zu einem Auswahleingang eines Eingabedatenmultiplexers 128 mit einer Vielzahl von Multiplexereingängen geführt. Der Multiplexer 128 hat wenigstens so viele Multiplexereingänge, wie es Schlitze 20 im Schreibdatenpuffer 18 gibt. In Fig. 5 hat der Multiplexer 128 24 Multiplexereingänge, wobei jedem Multiplexereingang einer der Schlitze 20 über eine entsprechende eine Vielzahl von Leitungen 130 zugeführt wird. Der Multiplexer 128 wählt einen der Schlitze 20 mit den Datenzeigerdaten aus, die mit den Datenzeigerdaten auf der Leitung 124 übereinstimmen. Der Multiplexer 128 läßt die Eingangsdaten vom ausgewählten Schlitz 20 über seinen Ausgang auf einer Leitung 132 durch, der als Anfang der Schreibdatenwarteschlange 16 dient. Die Inkrementier- Logikschaltung 120 inkrementiert den Wert der Datenzeigerdaten auf der Leitung 124 Schlitz für Schlitz in einer kreisförmigen Folge, und die Schlitzadressen der Schlitze 20 umgebend, wenn die Daten von jedem der Schlitze 20 zur Leitung 132 übertragen werden. Dies wird durch das Inkrementier-Logiksteuerfeld auf der Leitung 126 durchgeführt.
Wenn der Übereinstimmungspuffer 88 ein Schreibbefehl von einem der Schlitze 86 identifiziert und der Warteschlangenanfangsbefehl auf der Leitung 44 auch ein Schreibbefehl ist, erzeugt die Schreibübereinstimmungsgatterschaltung 96 ein Schlitzadressenfeld auf der Leitung 134, das der Schlitzadresse des Schreibbefehls im entsprechenden der Schlitze 8 des Befehls-/Adressenpuffers 6 entspricht. Die Schlitzadresse auf der Leitung 34 wird zu einem Auswahleingang eines Maskendaten-Demultiplexers 136 mit einem einzelnen Multiplexereingang und einer Vielzahl von Ausgängen geführt. Der Demultiplexer 136 hat wenigstens so viele Ausgänge, wie es Schlitze 14 im Eingabedatenmaskenpuffer 12 gibt. Jeder der Ausgänge des Demultiplexers 136 führt zu einem unterschiedlichen der Schlitze 14 über eine entsprechende einer Vielzahl von Leitungen 138. Die Maskendaten auf der Leitung 110 werden zum Multiplexereingang des Demultiplexers 136 über eine Leitung 140 geführt. Der Demultiplexer 136 wählt den einen der Schlitze 14 aus, der eine Schlitzadresse hat, die mit der Schlitzadresse auf der Leitung 134 übereinstimmt. Auf diese Weise werden die Maskendaten auf der Leitung 140 mit den im ausgewählten der Schlitze 14 gespeicherten Maskendaten verbunden.
Wenn der Übereinstimmungspuffer 88 einen Ablehnungsschreibbefehl von einem der Schlitze 86 identifiziert, erzeugt die Ablehnungsschreibübereinstimmungsgatterschaltung 98 ein Schlitzadressenfeld auf einer Leitung 142. Das Schlitzadressenfeld auf der Leitung 142 wird in einen Auswahleingang eines zweiten Datenmaskenmultiplexers 152 mit einer Vielzahl von Multiplexereingängen geführt. Der Multiplexer 152 hat wenigstens so viele Multiplexereingänge, wie es Schlitze 14 im Eingabedatenmaskenpuffer 12 gibt. In Fig. 5 hat der Multiplexer 152 12 Eingänge, wobei jedem Eingang einer der Schlitze 14 über eine entsprechend einer Vielzahl von Leitungen 154 zugeführt wird.
Der Multiplexer 152 wählt den einen der Schlitze 14 aus, der eine Schlitzadresse hat, die mit der Schlitzadresse auf der Leitung 142 übereinstimmt. Der Multiplexer 152 läßt die Maskendaten vom ausgewählten Schlitz 14 über seinen Ausgang auf einer Leitung 156 durch. Die Maskendaten auf der Leitung 156 werden in einen ersten Eingang einer Sperrgatterschaltung 158 geführt. Das Freigabesignal von der Ablehnungsschreibgatterschaltung 98 auf der Leitung 142 wird zu einem zweiten Eingang der Gatterschaltung 158 über eine Leitung 160 geführt. Die Sperrgatterschaltung 158 erzeugt ein Maskendatensperrfeld auf der Leitung 156 über ihren Ausgang auf einer Leitung 162, wenn das Freigabesignal auf der Leitung 160 vorhanden ist.
Das Maskendatenfeld auf der Leitung 110 wird zu einem ersten Eingang einer Filtergatterschaltung 164 geführt. Das Maskendatensperrfeld auf der Leitung 162 wird zum zweiten Eingang der Filtergatterschaltung 164 geführt. Wenn es kein Freigabesignal von der Ablehnungsschreibgatterschaltung 98 gibt, gibt es kein Maskendatensperrfeld auf der Leitung 162, so daß die Gatterschaltung 164 die Maskendaten durch ihren Ausgang auf einer Leitung 166 durchläßt. Jedoch dann, wenn das Freigabesignal auf der Leitung 142 vorhanden ist, erzeugen die Maskendaten auf der Leitung 156 das Maskendatensperrfeld im Gatter 158. Da es dann ein Maskendatensperrfeld auf der Leitung 162 gibt, das den Maskendaten auf der Leitung 110 entspricht, blockiert die Filtergatterschaltung 164 die Maskendaten, die schon geschrieben worden sind, für eine Übertragung zur Leitung 166 während der Periode eines Ablehnungsschreibbefehls. Dies hält den Ablehnungsschreibbefehl vor einem Überschreiben von Daten ab, die zuvor mit anderen Schreibbefehlen geschrieben sind. Dies simuliert zuerst die Schritte eines Durchführens des Ablehnungsbefehls und dann eines Durchführens der Übereinstimmungsschreibbefehle.
Die unteren Adressenbits des Befehls-/Adressenfelds auf der Leitung 44 führen über eine Leitung 170 in einen Eingang einer wohlbekannten Lade4lnkrementier- Logikschaltung 168. Die Lade4lnkrementier-Logikschaltung 168 läßt die unteren Adressenbits des Befehls-/Adressendatenfelds auf einer Leitung 172 in Antwort auf ein zu einem Logiksteuereingang der lnkrementier-Logikschaltung 168 auf einer Leitung 174 geführtes Lade-Logiksteuersignal durch. Das Inkrementier- Logiksteuersignal wird durch eine wohlbekannte Inkrementier-Logikschaltung (nicht gezeigt) entwickelt. Die Adressendaten auf der Leitung 172 führen zu einem Auswahleingang eines Multiplexers 176 mit vier Eingängen und einem Ausgang. Die Leitung 166 führt zum Eingang des Multiplexers 176. Der Multiplexer 176 wählt ein Byte von Maskendaten auf der Leitung 166 aus, wobei jedes Bit im Byte ein Byte eines Quadwortes darstellt, das den Adressendaten auf der Leitung 172 entspricht. Der Multiplexer 176 läßt die ausgewählten Maskendaten über seinen Ausgang auf einer Leitung 178 durch, der als der Anfang der Eingabedatenmaskenwarteschlange 10 dient. Die Inkrementier-Logikschaltung 168 inkrementiert sequentiell die Adresse auf der Leitung 172 in Antwort auf das Inkrementier-Logiksteuersignal auf der Leitung 174, um jedes der Bytes von Maskendaten im ausgewählten Schlitz 14 des Eingabedatenmaskenpuffers 12 sequentiell auszugeben.
Die Speicheruntersystemeingabewarteschlange gemäß der vorliegenden Erfindung, wie es oben beschrieben ist, sortiert die durch ein gemeinsam nutzbares Speicherbetriebsmittel empfangenen Lese- und Schreibbefehle von unterschiedlichen CPUs in einem Datenverarbeitungssystem aus, um zu verhindern, daß konkurrierende Befehle auftreten, selbst wenn das Datenverarbeitungssystem eine Mischung aus Knoten mit Zurückschreib-Caches, Knoten mit Durchschreib-Caches und Knoten ohne Caches enthält. Die Eingabewarteschlange speichert empfangene Befehle und verarbeitet sie sequentiell auf eine FIFO-Weise, bis ein Ablehnungsschreibbefehl verarbeitet wird.
Wenn ein Lesebefehl verarbeitet wird und die Stelle in Besitz genommen ist, wird dem Lesebefehl ein Übergangsstatus "Warten" zugeteilt, und seine Ausführung wird verzögert. Wenn ein Schreibbefehl verarbeitet wird, und die Stelle in Besitz genommen ist, wird das Schreiben fortgeführt, und die Befehlsinformation und die Maskendaten werden auf der Eingabewarteschlange in ihren dann aktuellen Schlitzen gespeichert. Dem Schreibbefehl wird ein Übergangsstatus "Warten" zugeteilt. Wenn ein vorheriger Schreibbefehl für dieselbe Adresse schon im Status "Warten" ist, werden die Maskendaten des aktuellen Schreibbefehls mit den Maskendaten des vorherigen Schreibbefehls verbunden. Nur ein Schreibbefehl im Zustand "Warten" bleibt für diese Adresse zurück.
Wenn ein Ablehnungsschreibbefehl verarbeitet wird, findet die Eingabewarteschlange irgendeinen der anderen empfangenen Befehle, die gespeichert worden sind und die dieselbe Befehlsadresse haben. Die Maskendaten der übereinstimmenden Adressenbefehle des Schreibtyps werden dazu verwendet, die Maskendaten des Ablehnungsschreibbefehls von einem nochmaligen Schreiben über die Daten abzuhalten, die durch die übereinstimmenden Adressenbefehle des Schreibtyps geschrieben sind, die den Wartestatus haben.
Auf diese Weise werden Schreibbefehle, die durch Knoten ausgegeben werden, die keine Zurückschreib-Caches haben und keine Besitzschaft von Datenblöcken erkennen, durch den Ablehnungsschreibbefehl eines Knotens mit einem Zurückschreib-Cache nicht zerstört. Die übereinstimmenden Adressenbefehle des Lesetyps, einschließlich jener, die den Übereinstimmungsstatus haben, werden dann verarbeitet. Auf diese Weise werden die Lesebefehle von Knoten, die keine Zurückschreib-Caches haben und keinen Besitz an Datenblöcken erkennen, nicht verarbeitet, bis der Ablehnungsschreibbefehl den Datenblock freimacht.
Somit ist hierin ein Verfahren und eine Schaltung zum Managen von Lese- und Schreibbefehlen in bezug auf ein gemeinsam nutzbares Speicherbetriebsmittel von Knoten mit Zurückschreib-Caches, Knoten mit Durchschreib-Caches und Knoten ohne Caches beschrieben worden.

Claims

1. Verfahren zum Lösen von Konflikten zwischen einer Ausführung von Befehlen von einer Vielzahl von Knoten zu einem gemeinsam nutzbaren Speicherbetriebsmittel durch Verwendung einer Speichereingabewarteschlange (2), wobei die Befehle jeweils zu einer spezifischen Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet sind, wobei die Speichereingabewarteschlange eine Vielzahl von Speicherstellen (8) aufweist, die zur Speicherung der Befehle verfügbar sind, wobei jede der Vielzahl von Speicherstellen einen "freien" Zustand, einen "neuen" Zustand, einen "Warte"-Zustand oder einen "Übereinstimmungs"-Zustand aufweist, wobei wenigstens einer der Vielzahl von Knoten einen Zurückschreib-Cache aufweist und wenigstens einer der Vielzahl von Knoten keinen Zurückschreib-Cache aufweist, wobei die Befehle Befehle vom Typ "Besitzerlesen" und vom Typ "Ablehnungsschreiben" von wenigstens einem der Vielzahl von Knoten mit einem Zurückschreib-Cache aufweisen, und Befehle vom Typ "Lesen" und vom Typ "Schreiben" von wenigstens einem der Vielzahl von Knoten ohne Zurückschreib-Cache, wobei die Speichereingabewarteschlange zwischen der Vielzahl von Knoten zum Empfangen der Befehle davon und dem gemeinsam nutzbaren Speicherbetriebsmittel zum Zugreifen aurdas gemeinsam nutzbare Speicherbetriebsmittel angeschlossen ist, wobei das Verfahren folgende Schritte aufweist:

Empfangen irgendeines der Befehle in der Speichereingabewarteschlange (2) als empfangene Befehle;

Setzen jeder der Vielzahl von Speicherstellen in der Speichereingabewarteschlange, die zur Speicherung der Befehle verfügbar ist, auf den "freien" Zustand;

Speichern jedes der empfangenen Befehle in einer der Speicherstellen (8) als gespeicherte Befehle in der Speichereingabewarteschlange und Ändern des Zustands der einen der Speicherstellen aus dem "freien" Zustand zum "neuen" Zustand, um anzuzeigen, daß die gespeicherten Befehle zu verarbeiten sind;

Erzeugen von Maskendaten (10) entsprechend jedem der gespeicherten Befehle des Typs "Ablehnungsschreiben" und des Typs "Schreiben";

Auswählen jedes der gespeicherten Befehle aus den Speicherstellen in der Speichereingabewarteschlange;

Ändern des Zustands jeder der Speicherstellen vom "neuen" Zustand zum "Warte"-Zustand, die einen der gespeicherten Befehle speichert, wenn der eine der gespeicherten Befehle zur selben spezifischen Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet ist wie ein anderer der gespeicherten Befehle des Typs "Besitzerlesen" oder des Typs "Ablehnungsschreiben";

Verzögern der Ausführung jedes der gespeicherten Befehle des Typs "Lesen" in den "Warte"-Zustand, bis wenigstens einer der gespeicherten Befehle des Typs "Besitzerlesen" oder des Typs "Ablehnungsschreiben" ausgeführt ist;

Verbinden und Speichern der Maskendaten (10), die jedem der gespeicherten Befehle des Typs "Schreiben" entspricht, um verbundene Maskendaten zu erzeugen;

für jeden der gespeicherten Befehle des Typs "Ablehnungsschreiben" Ändem des Zustands jeder der Speicherstellen (8) in der Speichereingabewarteschlange vom "Warte"-Zustand zum "Übereinstimmungs"-Zustand, die einen der gespeicherten Befehle speichert, der zur selben Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet ist wie einer der gespeicherten Befehle des Typs "Ablehnungsschreiben", und Verwenden der Maskendaten der gespeicherten Befehle des Typs "Schreiben" von den Speicherstellen im "Übereinstimmungs"-Zustand zum Sperren der Maskendaten jedes der gespeicherten Befehle des Typs "Ablehnungsschreiben" während einer Ausführung, und Ausführen jedes der gespeicherten Befehle des Typs "Lesen" von den Speicherstellen im "Übereinstimmungs"-Zustand nach einer Ausführung der gespeicherten Befehle des Typs "Ablehnungsschreiben";

nach einer Ausführung eines der gespeicherten Befehle, der nicht zur selben Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet ist wie irgendwelche anderen der gespeicherten Befehle des Typs "Besitzerlesen" oder "Ablehnungsschreiben", Ändern der Speicherstelle, die den beliebigen der gespeicherten Befehle speichert, vom "neuen" Zustand zum "freien" Zustand, um anzuzeigen, daß die Speicherstelle, die den beliebigen der gespeicherten Befehle speichert, zum Empfangen eines neuen der Befehle verfügbar ist; und

nach einer Ausführung eines der gespeicherten Befehle von einer der Speicherstellen im "Übereinstimmungs"-Zustand Ändern der einen der Speicherstellen im "Übereinstimmungs"-Zustand vom "Übereinstimmungs"-Zustand zum "freien" Zustand, um anzuzeigen, daß die Speicherstelle, die vom "Übereinstimmungs"-Zustand zum "freien" Zustand geändert wurde, zum Speichern eines neuen der Befehle verfügbar ist.

2. Schaltung zum Lösen von Konflikten zwischen einer Ausführung von Befehlen von einer Vielzahl von Knoten zu einem gemeinsam nutzbaren Speicherbetriebsmittel durch Verwendung einer Speichereingabewarteschlange (2), wobei die Befehle jeweils zu einer spezifischen Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet sind, wobei die Speichereingabewarteschlange eine Vielzahl von Speicherstellen (8) aufweist, die zur Speicherung der Befehle verfügbar sind, wobei jede der Vielzahl von Speicherstellen in einem "freien" Zustand, einem "neuen" Zustand, einem "Warte"-Zustand oder einem "Übereinstimmungs"-Zustand ist, wobei wenigstens einer der Vielzahl von Knoten einen Zurückschreib-Cache aufweist, und wobei wenigstens einer der Vielzahl von Knoten keinen Zurückschreib-Cache aufweist, wobei die Befehle Befehle vom Typ "Besitzerlesen" und vom Typ "Ablehnungsschreiben" von jedem der Vielzahl von Knoten mit einem Zurückschreib-Cache aufweisen, und Befehle vom Typ "Lesen" und vom Typ "Schreiben" von jedem der Vielzahl von Knoten ohne Zurückschreib-Cache, wobei die Speichereingabewarteschlange zwischen der Vielzahl von Knoten zum Empfangen der Befehle davon und dem gemeinsam nutzbaren Speicherbetriebsmittel zum Zugreifen auf das gemeinsam nutzbare Speicherbetriebsmittel angeschlossen ist, wobei die Schaltung zum Lösen von Konflikten folgendes aufweist:

eine Einrichtung zum Ausführen der Befehle;

eine Einrichtung (6) zum Empfangen irgendwelcher der Befehle in der Speichereingabewarteschlange (2) als empfangene Befehle;

eine Einrichtung zum Setzen jeder der Vielzahl von Speicherstellen in der Speichereingabewarteschlange, die zur Speicherung der Befehle verfügbar ist, auf den "freien" Zustand;

eine Einrichtung zum Speichern jedes der empfangenen Befehle in einer der Speicherstellen als gespeicherte Befehle und Ändern des Zustands jeder der Speicherstellen, die einen der gespeicherten Befehle speichert, vom "freien" Zustand zum "neuen" Zustand, um anzuzeigen, daß der gespeicherte Befehl zu verarbeiten ist;

eine Einrichtung zum Bestimmen der spezifischen Adresse für jeden der gespeicherten Befehle;

eine Einrichtung zum Auswählen jedes der gespeicherten Befehle;

eine Einrichtung zum Ändern des Zustands jeder der Speicherstellen vom "neuen" Zustand zum "Warte"-Zustand, die einen der gespeicherten Befehle speichert, wenn der eine der gespeicherten Befehle zur selben spezifischen Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet ist wie ein anderer der gespeicherten Befehle des Typs "Besitzerlesen" oder "Ablehnungsschreiben";

eine Einrichtung zum Verzögern der Ausführung jedes der gespeicherten Befehle des Typs "Lesen" in den "Warte"-Zustand, bis wenigstens einer der gespeicherten Befehle des Typs "Besitzerlesen" oder "Ablehnungsschreiben" ausgeführt ist;

eine Einrichtung zum Erzeugen von Maskendaten (10) entsprechend jedem der gespeicherten Befehle des Typs "Ablehnungsschreiben" und des Typs "Schreiben";

eine Einrichtung zum Verbinden und Speichern der Maskendaten zum Erzeugen verbundener Maskendaten entsprechend jedem der gespeicherten Befehle des Typs "Schreiben" im "Warte"-Zustand;

eine Einrichtung, die auf einen der gespeicherten Befehle des Typs "Ablehnungsschreiben" antwortet, zum Ändern des "Warte"-Zustands zum "Übereinstimmungs"-Zustand des Zustands jeder der Speicherstellen, die einen der gespeicherten Befehle des Typs "Schreiben" oder des Typs "Lesen" speichert, der zur selben spezifischen Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet ist wie der eine der gespeicherten Befehle des Typs "Ablehnungsschreiben", und zum Verwenden der verbundenen Maskendaten der gespeicherten Befehle des Typs "Schreiben", die zur selben spezifischen Adresse gerichtet sind, um die Maskendaten des einen der gespeicherten Befehle des Typs "Ablehnungsschreiben" während einer Ausführung zu sperren, und zum Ausführen der gespeicherten Befehle des Typs "Lesen", die zur selben spezifischen Adresse gerichtet sind, nach einer Ausführung des einen der gespeicherten Befehle des Typs "Ablehnungsschreiben";

eine Einrichtung zum Ändern jeder Speicherstelle, die einen der gespeicherten Befehle speichert, der nicht zur selben spezifischen Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet ist wie einer der gespeicherten Befehle des Typs "Besitzerlesen" oder des Typs "Ablehnungsschreiben" vom "neuen" Zustand zum "freien" Zustand nach der Ausführung des einen der gespeicherten Befehle, der nicht zur selben spezifischen Adresse im gemeinsam nutzbaren Speicherbetriebsmittel gerichtet ist wie einer der gespeicherten Befehle des Typs "Besitzerlesen" oder des Typs "Ablehnungsschreiben", um anzuzeigen, daß die Speicherstelle, die vom "neuen" Zustand zum "freien" Zustand geändert wurde, zum Speichern eines neuen der Befehle verfügbar ist; und

eine Einrichtung zum Ändern jeder Speicherstelle, die einen der gespeicherten Befehle speichert, in den "Übereinstimmungs"-Zustand nach einer Ausführung des einen der gespeicherten Befehle in den "Übereinstimmungs"- Zustand vom "Übereinstimmungs"-Zustand zum "freien" Zustand, um anzuzeigen, daß die Speicherstelle, die vom "Übereinstimmungs"-Zustand zum "freien" Zustand geändert wurde, zum Speichern eines neuen der Befehle verfügbar ist.