DE3933361A1 - Einrichtung und verfahren zur warteschlangenbildung von anforderungen und antworten auf einem pipeline-paketbus - Google Patents

Description

Die Erfindung bezieht sich auf Multiprozessorsysteme und ins­ besondere auf eine Anordnung und ein Verfahren zur Warte­ schlangenbildung von Anforderungen für den Zugriff auf und Antworten zum Empfang über einen parallel beaufschlagten (pipelined) Paketbus, der mehrere Modulen miteinander verbin­ det.

Ein Multiprozessorsystem ist in den US-PS′n 43 15 308, 44 80 307 und 44 73 880 beschrieben. Bei diesem bekannten System teilen sich einige Module in einen gemeinsamen Bus zur Signal­ übertragung zwischen den Modulen. Die Module können Datenpro­ zessoren, Speicher oder Eingabe/Ausgabe-Geräte und deren ent­ sprechende Steuergeräte sein. Einige Anforderungen zur Verwen­ dung des Busses müssen gehalten bzw. gespeichert werden, bis der Bus zur Übernahme der Anforderung zur Verfügung steht. Über den Bus empfangene Antworten müssen in ähnlicher Weise gepuffert, ggf. umgeordnet und zu dem richtigen anfordernden Modul übertragen oder neu versucht werden, um eine Fehlerbe­ dingung zu korrigieren. Informationen werden über den Bus in Form von Informationspaketen während zugeordneter Busübertra­ gungszeitschlitze übertragen. Die Bussteuerung liegt in Form einer Anzahl von Silo- bzw. Stapel- (FIFO)-Warteschlangen vor, welche diese Pakete halten bzw. speichern. Beispielsweise ist eine Zuteilungswarteschlange ein Silopuffer, der Anforderungs­ pakete hält bzw. speichert, die auf den Zugriff zum Bus war­ ten.

Die Bussteuerung wird komplex, wenn Maßnahmen zur Fehlerbe­ stimmumg und Erneuerung getroffen werden, und wenn viele ver­ maschte Silos (FIFOs) definiert werden, um Daten zu und von der internen Logik von den Bus benutzenden Modulen bewegt werden. Es können vierzehn verschiedene, datenhaltende Silo- Warteschlangen notwendig sein, um einen vollständig funktio­ nierenden Paketbus richtig zu beschreiben, der drei getrennte Busanforderungen gleichzeitig verfolgt. Ein Busprotokoll ent­ wickelt und hält eine Pipeline für Anforderungen und Antworten aufrecht überwacht die Pipeline auf Fehlerbedingungen und fügt Antworten in die Pipeline während der richtigen Zeit­ schlitzposition entsprechend einer erkannten Anforderung ein.

Da die Scheibchenoberfläche an erster Stelle steht bei der Implementierung einer komplexen Bussteuerung in der VSLI- Schaltungstechnologie, ist es notwendig, eine Schaltung vorzu­ sehen, welche größenmäßig beschränkt ist, jedoch bei der höch­ sten Geschwindigkeit arbeiten kann, für die die Schaltungen ausgelegt sind.

Die Erfindung liegt daher die Aufgabe zugrunde, eine Einrich­ tung und ein Verfahren zur Warteschlangenbildung von Anforde­ rungen und Antworten an einen parallel beaufschlagten (pipe­ lined) Paketbus zu schaffen, der größenmäßig begrenzt ist, jedoch trotzdem bei voller Geschwindigkeit zu arbeiten ver­ mag.

Diese Aufgabe wird erfindungsgemäß dadurch gelöst, daß ein RAM vorgesehen ist, der Busanforderungen durch Speicherung von Paketinformationen entsprechend jeder Anforderung puffert, die über einen Bus in jeder Anforderung zugeordneten Buszeit­ schlitzen gesandt wird. Eine Anzahl von Sendeschlangenzählern wird durch eine Reihe von Zuständen geschaltet, um eine her­ ausgehende Anforderung und eine entsprechende einlaufende Antwort zu verfolgen. Der Empfängerwarteschlangenzähler wird durch eine Folge von Zuständen geschaltet, um eine einlaufende Anforderung und eine entsprechende Antwort zu verfolgen. Sen­ deschlitze verfolgen den Zustand der Sendeanforderungen, die im RAM gespeichert sind, und Empfangsschlitze verfolgen den Zustand von empfangenen Anforderungen, welche im RAM gespei­ chert sind. Ein Ausgangsmux, der zum Senden und Empfangen von Schlitzen geeignet ist, erzeugt Zustandsinformationen bezüg­ lich des Zustandes von Anforderungen, die von derjenigen Kom­ ponente ausgehen, in der der Warteschlangen-Ausgangsmux ange­ ordnet ist. Die Zustandsinformation bezüglich des Zustandes des Sendens und Empfangens von Schlitzen dient zur Steuerung des Inkrementierens oder Dekrementierens der Sendewarteschlan­ genzähler und der Empfängerwarteschlangenzähler entsprechend einem vorgegebenen Systembusprotokoll.

Die Erfindung hat den Vorteil, daß ein komplexes Paketbus-Se­ quenzprotokoll mit Fehlertoleranz derart implementiert wird,

Im folgenden wird die Erfindung unter Bezugnahme auf die Zeichnung näher erläutert. In der Zeichnung zeigen:

Fig. 1 ein Blockschaltbild eines Dualbus-Datenverarbei­ tungssystems, in welchem die Erfindung verwirklicht ist;

Fig. 2 ein detallierteres Blockschaltbild der Systembus- Steuerlogik innerhalb des BXU der Fig. 1;

Fig. 3 ein genaueres Blockschaltbild des Sendewarteschlan­ genblocks aus Fig. 1;

Fig. 4 ein genaueres Blockschaltbild des empfangenden Warteschlangenblocks gemäß Fig. 1;

Fig. 5 ein genaueres Blockschaltbild eines der Sende­ schlitze innerhalb des Sendeschlitzblocks in Fig. 2;

Fig. 6 ein genaueres Blockschaltbild eines der Empfangs­ schlitze innerhalb des Empfangsschlitzblocks in Fig. 2;

Fig. 7 ein Sendewarteschlangen-Zustandsdiagramm für abge­ hende Anforderungen; und

Fig. 8 ein Empfangswarteschlangen-Zustandsdiagramm für einlaufende Anforderungen.

In Fig. 1 ist ein Blockschaltbild eines dualen Systembus-Mul­ tiprozessorsystems gezeigt. Buserweiterungseinheiten (BXU) 10, 12 sind mit Doppelsystembussen 20, 22 und einem lokalen Bus 18 verbunden. Der lokale Bus bildet die Schnittstelle zu generalisierten Datenprozessoren 34, 36. Ein zweiter, in der Zeichnung nicht dargestellter lokaler Bus kann hinzukommen, um eine Schnittstelle zu Kanalprozessoren (nicht dargestellt) zu bilden, welche mit Eingabe/Ausgabe-Geräten verbunden sein können.

Der lokale Bus 18 wird von einer lokalen Bussteuerlogik 8 auf der Buserweiterungseinheitsseite (BXU-Seite) gesteuert.

Die Buserweiterungseinheit 10 ist an einen der Systembusse 22 über eine Systembus-Steuerlogik 6 und an einen lokalen Bus 18 über ein Lokalbus-Steuerlogik 8 angeschlossen. Die Partnerbus­ -Erweiterungseinheit 12 ist mit dem anderen Systembus 20 über ihre eigene Systembus-Steuerlogik und mit dem lokalen Bus 18 über ihre eigene Lokalbus-Steuerlogik gekoppelt.

Der Systembus 20 ist genauer in den oben bezeichneten US-Pa­ tentschriften der Firma INTEL beschrieben. Die Systembus-Steu­ erlogik 8 enthält eine Logik zur Entscheidung, zur Pipeline- Überwachung, zur Adressenerkennung und zur Bussignalgabe. Die Systembus-Steuerlogik 6 bildet die Pufferung zur Zwischenspei­ cherung bzw. zum Halten von Anforderungen und Antworten bei deren Bewegung zwischen dem Bus und den internen Logik 4 der BXU. Die Systembus-Steuerlogik 8 bildet sechs Puffer, von denen jeder ein gesamtes Buspaket zu speichern bzw. halten geeignet ist. Drei Puffer sind outbound-Anforderungen (Anfor­ derungen von außen) und drei inbound-Anforderungen (Anforde­ rungen von Innen) zugeordnet.

Die Speichersteuereinheiten 50, 51 sorgen für die Steuerung von Datenübertragungen zu und von Speicherfeldern 42, 44, 46, 48 über Speicherbusse 54, 56.

Die BXU′s 10, 12 steuern auch einen gemeinsamen Cache-Speicher 24.

Im folgenden wird auf Fig. 2 Bezug genommen, die die zum Ver­ folgen des logischen Zustandes der Systembus-Steuerlogik 6 erforderliche Logik zeigt. Diese Logik verfolgt gleichzeitig bis zu sechs Transaktionen (Anforderungen) an den AP-Bus 22, hält den Informationszustand für drei abgehende Anforderungen und drei einlaufende Anforderungen aufrecht. Diese Zustandsin­ formation 222 wird von dem Bus-Schnittstellensteuerblock (BICTL) 202, und dem Entscheidungssteuerblock (ARBCTL) 206 zur Entscheidung darüber verwendet, welche Aktionen vorzunehmen sind. Beispielsweise sagt der Warteschlangenzustand dem EXTCTL "diese BXU besitzt den ersten Schlitz in PiQ" aus dem Aus­ gangs-MUX 214, daß die nächste Antwort an den Bus zu dieser Komponente gehört. Der Zustand "erster in GnQ" aus dem Aus­ gangs-MUX 214 sagt EXTCTL, daß eine Anforderung an den näch­ sten Anforderungsschlitz an den Bus zu senden ist. Die Logik der Fig. 2 verfolgt die Ordnung der Anforderungen, die Antwort Zurückstellung, das Wiederanlegen von Antworten, die Partner­ bildung von Anforderungen unter BXU′s und handhabt einen er­ neuten Versuch nach einem Fehler. Die Logik der Fig. 2 spei­ chert auch Identifizierungsbits (ID-Bits) in einem ID-Silo 224. Die ID-Bits werden im ID-Silo gespeichert, wenn eine Anforderung über den AP-Bus 22 übertragen wird und werden zur internen Logik 4 mit der Antwort zurückgeführt. ID-Bits werden nicht auf den AP-Bus gesendet, Antworten werden mit geeigneten Anforderungen auf dem AP-Bus durch Ordnen in Übereinstimmung gebracht. Die Reihenfolge an dem Bus ist zuerst hinein, zuerst hinaus, mit der Ausnahme von Antwortverzögerungen, und alle Komponenten auf dem Bus verfolgen die Reihenfolge.

Die Logik der Fig. 2 ist eine Zustandsmaschine, deren Opera­ tion nachfolgend unter Bezugnahme auf Fig. 7 und 8 be­ schrieben wird. Die Logik der Fig. 2 wird von Zählern, Latches und Multiplexern gebildet, wobei die Steuerung von dem EXTCTL-Block 204 und dem BICTL-Block 202 in Form von Einspei­ chern und Entnehmen für die Warteschlangen 230 und 232 er­ folgt. Die Logik verfolgt die Tiefe aller Warteschlangen sowie den Ort jeder Transaktion in der Warteschlange, welche im BCL-RAM 212 gepuffert wird.

Wie in Fig. 3 gezeigt, sind neun sendende Warteschlangen als Zähler implementiert, welche die Tiefe der sendenden Warte­ schlangen verfolgen. Die Sendewarteschlangen haben eine A-Sei­ te und eine B-Seite, welche zwei Ansichten derselben Transak­ tion enthalten. Generell sind die A-Warteschlangen die primä­ ren und die B-Warteschlangen die sekundären Warteschlangen, welche verzögerte Informationen zur Verwendung bei der Fehler­ -Wiedergewinnung enthalten. Die Eingänge 252 zu den Warte­ schlangen sind Einspeicherungen und Entnahmen, welche die Zähler zum Aufwärts- und Abwärtszählen veranlassen. Der Sende­ tiefenausgang 256 ist die Information bezüglich der Länge der Warteschlange (die Anzahl der in einer Warteschlange befindli­ chen Anforderungen).

Wie in Fig. 4 gezeigt, sind vier Empfangswarteschlangen als Zähler implementiert, welche die Tiefe der Empfangswarte­ schlangen verfolgen. Die Empfangswarteschlangen haben eine A-Seite und B-Seite, welche zwei Ansichten der gleichen Trans­ aktion enthalten. Generell sind die A-Warteschlangen die pri­ mären und B-Warteschlangen die sekundären Warteschlangen, welche verzögerte Informationen zur Verwendung der Fehler-Wie­ dergewinnung enthalten. Die Eingänge 264 zu den Warteschlangen sind Einspeicherungen und Entnahmen, welche die Zähler zum Vorwärts- und Rückwärtszählen veranlassen. Der Empfangstiefen­ ausgang 266 ist die Information bezüglich der Warteschlangen­ länge (der Anzahl der in einer Warteschlange enthaltenen An­ forderungen).

Wie in Fig. 2 gezeigt ist, halten drei Sendeschlitze 0 : 2 (208) und drei Empfangsschlitze 3 : 5 (210) den Zustand aller im BCL-RAM 212 gepufferten Transaktionen. Es handelt sich hierbei um Transaktionen, welche entweder auslaufende oder einlaufende Anforderungen sind. Der Zustand einer Transaktion besteht in Informationen darüber, in welcher Warteschlage die Transaktion stattfindet und wie tief die Transaktion in der Warteschlange angeordnet ist. Beispielsweise kann ein auslaufender Anforde­ rungsschlitz den Zustand "erste in Pipe-Warteschlange (PiQ)" enthalten.

Die Sendeschlitze 208 enthalten den Zustand der auslaufenden Anforderungen und einlaufenden Antworten, und die Empfangs­ schlitze 210 enthalten den Zustand von einlaufenden Anforde­ rungen und abgehenden Antworten. Sendeschlitze bilden eine Schnittstelle zu Sendewarteschlangen 230 und sind im einzelnen in Fig. 5 gezeigt. Empfangsschlitze bilden eine Schlitz­ schnittstelle zu Empfangswarteschlangen 232 und sind im ein­ zelnen in Fig. 6 gezeigt.

Der Ausgangsmux 214 gemäß Fig. 2 erzeugt die Gesamtschlitz-Zu­ standsinformation 222, die von den anderen Logikblöcken benö­ tigt wird. Der Ausgangsmux 214 erzeugt die RAM-Wortansteuerun­ gen 220 für sendende Anforderungen dadurch, daß er bestimmt, welche Sendeschlitze für Einschreiben aus dem RAM 212 während des nächsten Pakets zur Verfügung stehen. Durch Vergleich der RAM Lese- und Schreib-Adresse nimmt der Ausgangsmux eine Beipaßbestimmung 318 vor. Der Ausgangsmux erzeugt außerdem die Sendeschlitz-Zustandsinformation 320 für EXTCTL und BICTL. Diese Zustandsinformation zeigt an, welche Sendewarteschlan­ genstellen von dieser Komponente besetzt sind.

Der Ausgangsmux 214 erzeugt die RAM-Wortansteuerungen 313 für Empfangsanforderungen durch Bestimmung, welche Empfangs­ schlitze zum Füllen aus dem AP-Bus 222 während des nächsten Pakets zur Verfügung stehen. Der Ausgangsmux bestimmt den Zustand des Empfangsschlitzes und erzeugt die Empfangsschlitz­ -Zustandsinformation 321 zur Verwendung durch die EXTCTL und BICTL-Steuerblöcke. Diese Zustandsinformation gibt an, welche Empfangswarteschlangenstellen von dieser Komponente besetzt sind.

Der ID-FIFO 224 ist der logische Block, welcher die Identifi­ zierungs(ID)-Bits (0 : 6) hält. Die gleichen Bits werden zur internen Logik 4 mit der Antwort zurückgeführt. Die interne Logik verwendet diese Bits zur Identifizierung derjenigen Anforderung, auf die die Antwort gegeben wird. Da die Antwor­ ten in der gleichen Reihenfolge zur internen Logik zurückge­ führt werden, in der sie ausgegeben wurden, handelt es sich bei der ID-FIFO-Logik um einen einfachen FIFO- bzw. Silo-Spei­ cher. Bits werden in den FIFO eingespeichert, wenn eine Anfor­ derung empfangen wird, und sie werden aus dem FIFO abgezogen, wenn die Antwort von der internen Logik angenommen wird. Die ID-Ausgangsbits IDOUT (1 : 6) sind die aktuellen FIFO-Bits der bodenseitigen Eingabe. Dies ermöglicht es der internen Logik, vorauszusehen und zu bestimmen, welcher Art von Anforderung die nächste Antwort zugeordnet ist. Zusätzlich zum FIFO er­ zeugt der ID-FIFO-Block ein PopQue-Signal 226, das auf den PopQue-Ausgangsstift zur Signalgabe an die Partner-BXU 12 gelegt wird. Dieses Signal wird angelegt, wenn eine Antwort bei einer Schreibanforderung erfolgreich zu der internen Logik übertragen worden ist. Nur Schreibbefehle werden signalisiert, da Leseanforderungen nicht nicht partnerschaftlich erfolgen. Um festzustellen, ob die Anforderung eine Schreibanforderung war, prüft die Logik das ID1-Bit.

Sendewarteschlangen

Der Sendewarteschlangenblock 230 der Fig. 2 ist aus neun War­ teschlangenzählern und einem Warteschlangen-Steuerblock 250 aufgebaut, der in Fig. 3 gezeigt ist. Die Warteschlangenzähler sind, abhängig von den Erfordernissen der Warteschlange, von unterschiedlichen Größen, sind jedoch alle Schieberegister, welche bei einer Einspeicherung nach links schieben und bei einer Entnahme nach rechts schieben. Der Steuerblock 250 ent­ hält die Logik, die zur Erzeugung der Steuersignale 252 für die Sendezähler und des Rücksetzsignals 234 für die Empfangs­ zähler erforderlich ist.

Der Sendewarteschlangensteuerblock 250 addiert Informationen zu einigen Einspeicher- und Entnahmesignalen (push and pop signals), um eine Antwortverzögerung, eine PopQue-Signalgabe und eine Wiederholungsvorbereitung in Betracht zu ziehen. Er erzeugt auch die Signale 254, die zum Rücksetzen der BCL 6 in Antwort auf Initiierungs- oder Fehlerbedingungen notwendig sind. Einige Zustandsleitungen werden von Wartschlangentiefen 256 erzeugt, um Informationen an den Rest der BCL zu geben.

Empfangswarteschlangen

Der Empfangswarteschlangenblock 232 der Fig. 2 enthält sechs 4-Bit-Zähler und einen Empfangswarteschlagen(RQueue)­ -Steuerlogikblock 260 für die Zählersteuerung, wie in Fig. 4 gezeigt ist. Fünf der Zähler stellen die Empfangswarteschlan­ gen dar, und es gibt einen zusätzlichen Zähler, Halteantwort­ warteschlange 123, der verfolgt, wieviele Antworten von dieser Komponente auf den AP-Bus ausgegeben, jedoch nicht wegen Feh­ lerbedingungen gelöscht worden sind. Die Funktion dieses Zäh­ lers 123 besteht darin, die PlRpy-Interfaceleitung 125 zu beaufschlagen, welche angibt, daß es keine Antworten gibt, welche auf ein Bus-Fehlerberichtsleitungssignal (BERL) warten. Dieser Zähler bildet keine Schnittstelle zu den Schlitzen und ist nicht Bestandteil der Zustandsdiagramme, die in den Fig. 7 und 8 gezeigt sind.

Alle Empfangswarteschlangenzähler haben vier Bits, da dies das Maximum, was die Empfangswarteschlange braucht. Eingänge 261 zu den Zählern sind Einspeicher- und Entnahmesignale (pushes and pops) vom EXTCTL-Block 204 und vom BICTL-Block 202 und ein Rücksetzsignal 234, das in den Sendewarteschlangen 230 erzeugt wird. Das Rücksetzsignal 234 wird vom Init-Signal oder BusErr­ -Signal bestätigt und bewirkt, daß alle Empfangswarteschlangen auf Null rückgesetzt werden, mit Ausnahme der freien Anforde­ rungswarteschlange, welche auf drei (die Anzahl der Empfangs­ schlitze) rücksetzt.

Der RQueue-Steuerblock 260 erzeugt Kombinationseinspeicherun­ gen und -entnahmen aus dem BICTL-Block und dem EXTCTL-Block, um denjenigen Fall zu berücksichtigen (der nachfolgend unter Bezugnahme auf Fig. 8 erläutert wird), bei dem die Anforde­ rungswarteschlange zu überbrücken ist. Der BICTL-Block signa­ lisiert den Beipaßfall durch Anlegen eines Signals, welches der BCL 6 sagt, daß eine einlaufende Anforderung direkt zur internen Logik 4 zu übertragen ist. Der RQueue-Steuerblock 260 erzeugt geeignete Signale, welche das Überbrücken der Anfor­ derungswarteschlange 124 bewirken.

Sende- und Empfangsschlitze (SSlt und RSlt)

Wie in Fig. 2 gezeigt ist, gibt es sechs Schlitze 208, 210 in dem BCL 6: drei Sendeschlitze 0 : 2 und drei Empfangsschlitze 3 : 5. Sendeschlitze 208 halten den Zustand der Sendeanforde­ rungstransaktionen, und Empfangsschlitze 210 halten den Zu­ stand der Empfangsanforderungstransaktionen. Sende- und Emp­ fangsschlitze sind von ähnlichem Aufbau, unterscheiden sich jedoch in zwei maßgeblichen Beziehungen: Die Anzahl der Zu­ standsbits und das Bus-Fehlerhandling. Sendeschlitze erfordern mehr Zustandsbits zum Codieren des Warteschlangenzustandes, da es mehr Sendewarteschlangen als Empfangswarteschlangen gibt. Sendeschlitze behandeln auch Bus-Fehler-Wiederholungen durch Wiederausgabe aller offenstehenden Anforderungen. Empfangs­ schlitze gehen auf Rücksetzen bei einem Busfehler, da diese empfangenen Anforderungen wiederholt gesendet werden.

Ein Schlitz hält den Zustand einer speziellen BCL-Transaktion. Wenn die BCL 6 eine Anforderung über den AP-Bus 22 sendet, wird die Anforderung einem Schlitz zugeordnet und in dem sCL- RAM 212 gepuffert. Die Schlitzzahl und die RAM-Wortadresse sind die gleichen, was dem Schlitz die Erzeugung der RAM- Adresse ermöglicht. Der Schlitz hält den Zustand dieser Trans­ aktion solange, bis sie beendet ist. Einlaufende Anforderungen werden gepuffert und einem Schlitz in der gleichen Weise zuge­ ordnet. Der Zustand einer Transaktion umfaßt die Information darüber, in welcher Warteschlange die Transaktion ist und wie tief sie sich in der Warteschlange befindet.

Die Sende- und Empfangsschlitze erhalten ihre Steuerbefehle von dem Bus-Interfacesteuerblock (BICTL-Block) 202, dem exter­ nen Steuerblock (EXTCTL-Block) 204 und dem Entscheidungssteu­ erblock (ARBCTL-Block) 206. Diese Steuerblöcke erzeugen die Ein- und Ausspeicherungen (pushes und pops) der Sende- und Empfangswarteschlangen und bewirken, daß der Schlitz abwärts­ zählt oder neue Zustandsinformationen geladen werden. Neue Zustandsinformationen werden aus den Warteschlangen 230, 232 geladen. Wenn beispeilsweise diese BXU die erste in der Zutei­ lungswarteschlange ist und eine Anforderung sendet, so erzeugt EXTCTL das Signal "popGnQ", wodurch die GnQ zum Abwärtszählen, die PiQ zum Aufwärtszählen bzw. Inkrementieren und der Schlitzzustand zur Anderung von GnQ auf PiQ veranlaßt werden. Der in den Schlitz geladene Zählwert wird aus dem Ausgang 254 von PiQ innerhalb des Sendewarteschlangenblocks 230 geladen. Wenn der PiQ-Zähler auf "3" steht, so wird "3" in den Schlitz geladen.

Der Ausgangsmux 214 erzeugt die Schlitzzustandsinformation 320, 321 aus den Schlitzzählern. Ein Beispiel der Zustandsin­ formation ist "sich verfüge über den ersten Schlitz in PiQ".

Im folgenden wird auf Fig. 5 Bezug genommen. Die Sende- und Empfangsschlitz-Zustandszähler 304, 404 halten die Zustands­ bits welche darstellen, in welcher Warteschlange sich dieser Schlitz befindet. Die Zustandscodierung, die Rücksetzwerte (AStDef/BStDef) und die Fehlerwerte (AStErr/BStErr) sind unten in Tabelle I angegeben.

Tabelle I

Jeder Zustandszähler 304, 404 ist aus Zustandszellen aufge­ baut, die matrixartig angeordnet sind, um diesen Zustandszäh­ ler zu bilden. Eine der Zustandszellen (Zelle Qst) hat eine Ladefunktion, welche einen neuen Zustand und zwei Rücksetzwer­ te lädt. Der erste Rücksetzwert ist der Initwert (StDef), und der zweite Rucksetzwert ist der Fehlerzustandsrücksetzwert (StErr). In Sendeschlitzen ist der Fehlerzustand eine zeitwei­ ligen Warteschlange (TpQ) und die Fehlerrücksetzung geschieht konditionell in Abhängigkeit von dem Zustand des Schlitzes zum Zeitpunkt des Fehlers. Empfangsschlitze werden auf den glei­ chen Wert bei Init und Fehler rückgesetzt.

Die Sende- und Empfangsschlitz-Tiefenzähler 306, 308; 406, 408 verfolgen die Tiefe des Schlitzes in der Warteschlange. Die A-Schlitzzähler halten die Tiefe in den A-Warteschlangen, und die B-Schlitzzähler halten die Tiefe in den B-Warteschlangen. Die Schlitzzähler zählen abwärts bzw. dekrementieren bei jedem Entnehmen "pop" und Laden eine neue Tiefe, wenn der Zähler Null erreicht. Die neue Tiefe kommt aus dem Schlitz-Eingangs­ mux (300 oder 400), welcher die zu ladende geeignete Warte­ schlangentiefe auswählt.

Jeder Schlitz-Tiefenzähler ist ein 4-Bit-Schieberegisterzäh­ ler. Der maximale Zählwert wird von der maximalen Warteschlan­ gentiefe bestimmt, da jeder Schlitz in jeder Warteschlange sein kann. Jeder Sende- oder Empfangsschlitz setzt auf einen speziellen Wert zurück. Tabelle 2 zeigt die Zustandsdzähler- Rücksetzwerte für jeden Schlitz.

Tabelle II

Die Tiefenzähler setzen zusammen mit dem Zustandszähler-Rück­ setzwert zurück, wobei die Sendeschlitze auf erste, zweite und dritte in einer freien Sendewarteschlange (FoQ) und die Emp­ fangsschlitze auf die erste, zweite und dritte in der freien Empfangswarteschlange (FrQ) initialisiert werden. Zur Vorbe­ reitung eines Neuversuchs setzt jeder Sendeschlitz konditio­ nell auf erste zweite oder dritte in der zeitweiligen Warte­ schlange (TpQ) zurück. Wenn der Schlitz in einem nicht-Wieder­ holungszustand ist, ändert er bei einem Fehler seinen Zustand nicht. Die Empfangsschlitze setzen auf erste, zweite oder dritte in einer freien Empfangswarteschlange (FrQ) bei einem Fehler zurück.

Die Schlitzsteuerblöcke 302; 402 erzeugen alle Signale zur Steuerung der Schlitzzustandszähler und Tiefenzähler. Die Steuerblöcke erzeugen Pop-, Lade- und Wiederumlaufsignale sowie die Fehlerrücksetzsignale.

Jeder Schlitz-Eingangsmux 300; 400 in Fig. 2 versorgt die Eingänge zu den Schlitzzustands- und Tiefenzählern. Jeder Schlitz-Eingangsmux ist aus drei Teilen aufgebaut: Einem Zu­ standsmux, der die nächsten Zustandsbits für den Zustandszäh­ ler auswählt, einem Tiefenmux, der die nächste Zustandstiefe für die Schlitztiefenzähler auswählt, und einem Pop-Mux, der das geeignete Entnahme- bzw. Popsignal für die Schlitz-Tiefen­ zähler auswählt.

Die Zustandsmuxfolgen durch die Warteschlangen-Zustandsüber­ gänge werden weiter unten unter Bezugnahme auf die Fig. 7 und 8 erörtert. Der Zustandsmux bestimmt den nächsten Warte­ schlangenzustand 303 aus den aktuellen Warteschlangen-Zu­ standsbits 222. Wenn beispielsweise ein Sendeschlitz in der Zuteilungswarteschlange ist, ist die nächste Warteschlange, in die er gehen wird, die Leitungswarteschlange (pipe queue). Einige Zustände haben mehr als einen möglichen nächsten Zu­ stand und erfordern ein weiteres Signal zur Bestimmung des nächsten Zustandes. So kann beispielsweise aus der wartenden Sendewarteschlange ein Schlitz in die verriegelte Warteschlan­ ge gehen, wenn eine verriegelte (locked) Antwort empfangen wird, oder in die freie Sendewarteschlange, wenn die Antwort nicht verriegelt ist. Die Eingänge zum Zustandmux sind die aktuellen Zustandsbits aus dem Schlitz-Zustandszähler plus den push-pop (Ein-Ausspeicher) und internen Interfaceleitungen, die erforderlich sind, um die Entscheidung unter den beiden möglichen nächsten Zuständen zu treffen. Die Ausgänge sind die nächsten Zustandsbits.

Der Tiefenmux wählt die Warteschlangentiefe für den nächsten Warteschlangenzustand. Wenn ein Schlitz von einer Warteschlan­ ge zur anderen wechselt, werden neue Zustandsbits in den Zu­ standszähler 304 geladen, um diesen neuen Warteschlangenzu­ stand darzustellen, und die vier Tiefenleitungen aus dieser Warteschlange werden in die Schlitzzähler 306, 308 geladen. Die Auswahlleitungen für den Mux sind die aktuellen Zustands­ bits.

Der Popmux wählt das Popsignal für die Schlitzzähler 306, 308 aus allen Warteschlangen-Popsignalen. Unter Verwendung aktuel­ ler Schlitz-Zustandsbits als Auswahlleitungen wählt der MUX die Entnahme (Pop) für die Warteschlange, in der sich dieser Schlitz befindet. Wenn dieser Schlitz beispielsweise in der Leitungswarteschlange (pipe queue) ist, wählt der Pop-MUX PopPiQ als das richtige Schlitz-Zähler-Popsignal.

Der Ausgangsmux 214 verdichtet den Schlitzstatus 309, 310 zur Erfüllung der Bedürfnisse der anderen BCL-Blöcke und verarbei­ tet spezielle Fälle, die die Schlitzzähler 306, 308 und den Zustandszähler 304 komplizieren würden. Der Ausgangsmux 214 erzeugt RAM-Wortadressen 220 zusammen mit einer Beipaßbestim­ mung 311, erzeugt Positionsleitungen 316, welche Aufschluß darüber geben, welche Warteschlangenpositionen von Transak­ tionen dieser Komponente besetzt sind, und ordnet Antworten durch Umordnung der Schlitztiefenzählerwerte um. Der Ausgangs­ mux ist aus vier kleineren Ausgangsmultiplexern aufgebaut, von denen einer jedem Schlitz zugeordnet ist. Der Ausgangsmux jedes Schlitzes wirkt unabhängig, ausgenommen für gemeinsame Leitungen, die zwischen den Schlitzen ODER-verknüpft sind. Der Ausgangsmuxblock 214 enthält drei Logiken. Der Schlitznummern­ generator erzeugt Wortadresse 220, 313 für den nächsten RAM- Zugriff. Der Schlitz-Nummernmultiplexer setzt Lese/Schreib- Wortadressen ins Zeitmultiplex um und erzeugt die Beipaß-Be­ stimmungsleitung 318. Die Schlitzposition erzeugt ein "von dieser Komponente besetzt"-Signal für bestimmte Warteschlan­ genpositionen.

Die Schlitzzahl einer Transaktion und die Wortposition, in der sie im BCL-RAM gespeichert ist, sind die gleichen. Diese Kor­ respondenz ermöglicht dem Ausgangsmux die Erzeugung von RAM­ -Wortadressen aus einem Schlitzzustand. Sechs RAM-Wortadressen werden erzeugt: Sende-Schreiben, Sende-Lesen, Sende-Adresse, Empfangslesen, Empfangsschreiben und Empfangsadresse. Der Zustand zusammen mit AP und BiData-Buszustand bestimmt, ob das RAM-Wort, welches diesem Schlitz entspricht, von dem nächsten Zyklus ein- oder ausgelesen wird.

Wenn beispielsweise ein Schlitz im TpQ-Zustand (102) entweder auf die Entscheidung wartet oder entscheidet und der BiData­ -Bus eine auslaufende Anforderung enthält, wird eine Sende/Schreibadresse für den Schlitz bestätigt, um die BiData­ -Busdaten in den RAM 212 zu schreiben. Die anderen Schlitze, welche die gleiche Auswertung unter Verwendung ihres Schlitzu­ standes vorgenommen haben, bestätigen die Sende/Schreibadresse nicht, wobei sie eine decodierte 6-Bit-Wortadresse erzeugen. Die fünf Adreßleitungen aus jedem Schlitz (Sendeschlitze er­ zeugen keine Empfangsleseadresse, und Empfangsschlitze erzeu­ gen keine Sendeleseadresse) werden in drei Leitungen in das Zeitmultiplex gebracht, und das Beipaß-Bestimmungssignal 318 wird im Ausgangsmux 310 erzeugt.

Das Beipaß-Bestimmungssignal wird am Ausgangsmux 310 durch Vergleich der Lese- und Schreibadressen sowohl für die Sende- als auch die Empfangs-RAM′s erzeugt. Dies geschieht als Bit­ -Für-Bit-Vergleich am Schlitz, und die Übereinstimmungsleitung (match line) wird zwischen den Schlitzen durch Verdrahtung ODER-verknüpft. Das Zeitmultiplexen geschieht zwischen den Lese- und Schreibadressen. Dieses Multiplexen erzeugt drei Adreßleitungen aus jedem der sechs Schlitze für insgesamt achtzehn Wortadreßbits.

Der Ausgangsmux 310 erzeugt den Gesamtschlitzstatus 320, wofür Warteschlangenplätze durch einen der Schlitze belegt werden. Dieser Zustand wird in Leitung 222 kombiniert und in EXTCTL und BICTL-Blöcke 202, 204 eingegeben.

Das generelle Format der Positionsleitungen 316 ist PlNxxQ; beispielsweise bedeutet Pl1Gnq, daß sich einer der Schlitze an erster Stelle in der Zuteilungswarteschlange befindet. Vier Platz- bzw. Positionsleitungen BiRpOk, BiRpP, RdRpOk und RdRpP folgen der generellen Konvention nicht. Sie geben Informa­ tionen der Platz- bzw. Positionsart, wobei sie eine Antwort­ verzögerung in Betracht ziehen. Die Platz- bzw. Positionslei­ tungen sind Lade-Entlade-Leitungen, die allen Schlitzen des­ selben Sende-Empfangs-Typs gemeinsam sind.

Im folgenden wird auf Fig. 7 Bezug genommen, die ein Zustands­ diagramm zum Senden einer Anforderung auf dem AP-Bus 22 darge­ stellt. Jeder Zustand steht in Beziehung mit einer ent­ sprechendn Warteschlange, wie in Tabelle I definiert ist. Eine Warteschlange wird auf den in der letzten Spalte in Tabelle I gezeigten Wert in Abhängigkeit von Initialisierungssignalen (init) oder Fehlersignalen entsprechend der Angabe in der vorletzten Spalte rückgesetzt.

Tabelle III

Unter Bezugnahme auf Fig. 7 sind die Warteschlangensequenzen durch die Zustände wie folgt:

FoQ-Zustandsblock 100. Der FoQ hält die auf ein abgehendes Sendeanforderungspaket wartenden freien Schlitze. Diese Warte­ schlange muß einen freien Schlitz haben, bevor sie eine abge­ hende Forderung akzeptiert. SdRdy und OtRqPnd (auf Bus 254) werden aus dieser Warteschlangentiefe berechnet. Der EXTCTL- Block 204 speichert in diese Warteschlange ein, wenn alle Zyklen einer einlaufenden Antwort zur internen Logik 4 über­ tragen worden sind. Der BICTL-Block 202 entnimmt aus dieser Warteschlange, wenn es eine abgehende Anforderung gibt, die von der internen Logik abgesendet zu werden beginnt. Wenn das Sendepaket ankommt, wechselt der Zustand in den nächsten Zu­ stand.

TpQ-Zustandsblock 102. Eine Anforderung geht vom FoQ-Zustands­ block 100 entweder zum TpQ-Zustandsblock 102 oder zum PrQ-Zu­ standsblock 114, und zwar in Abhängigkeit davon, ob die Anfor­ derung für diese BXÜ oder ihren Partner bestimmt ist. TpQ hält eine auf die Entscheidungslogik 106 wartende Anforderung. Diese Anforderungen warten entweder darauf, zu entscheiden, oder sie entscheiden gerade. Der ARBCTL-Block 206 benutzt das Vorhandensein eines Schlitzes in dieser Warteschlange zur Auslösung einer Entscheidung. Anforderungen in dieser Warte­ schlange werden bei einem Fehler wiederholt. Der BICTL-Block 202 speichert in diese Warteschlange ein, wenn die interne Logik eine abgehende Anforderung zu senden beginnt oder wenn eine verriegelte Anforderung neu ausgegeben wird. (Die neue Anforderung hat Priorität.) Der ARBCTL-Block 206 speichert (pops) in diese Warteschlange ein, wenn der Anforderung Zutei­ lung gegeben wird. Wenn die Zuteilung von der Entscheidungs­ logik gewährt worden ist, ändert sich der Zustand.

GnQ-Zustandsblock 104. Der GnQ hält die Reihenfolge der Zutei­ lungen, die von der ARBC TL-Logik 206 gewährt worden sind. Die Tiefe dieser Warteschlange wird von allen Komponenten an dem AP-Bus überwacht. Diese Warteschlange zählt alle Zuteilungen, die an dem Bus gegeben worden sind, jedoch wird die indivi­ duelle Position in der Warteschlange nur für Zuteilungen ge­ halten, welche zu dieser Komponente gehören.

Der EXTCTL-Block 204 verwendet diesen Warteschlangenzustand zur Feststellung, ob die erste Zuteilung zu dieser Komponente gehört. Ist dies der Fall, so ist dies die nächste über den AP-Bus zu sendende Anforderung. Anforderungen in dieser Warte­ schlange werden bei einem Fehler wiederholt. Der ARBCTL-Block 206 speichert (pushes) in diese Warteschlange ein, wenn der Anforderung Zuteilung gewährt wird. Der EXTCTL-Block 204 ent­ nimmt (pops) aus dieser Warteschlange, wenn die Anforderung auf dem AP-Bus beginnt. Bei Sendung ändert sich der Zustand.

PiQ-Zustandsblock 106. PiQ hält die Anforderungen, welche auf dem AP-Bus ausstehen und auf Antwort warten. Die Tiefe dieser Warteschlange wird von allen an den AP-Bus angeschlossenen Komponenten überwacht. Die Warteschlange hält alle ausstehen­ den Anforderungen, die auf den AP-Bus gegeben worden sind, jedoch hält jede Komponente gerade ihre individuelle Position in der Warteschlange und die Warteschlangentiefe. Der EXTCTL­ -Block 204 verwendet diesen Warteschlangenzustand zur Bestim­ mung, ob die Antwort auf dem Bus dieser Komponente gilt. Der EXTCTL-Block 204 speichert in diese Warteschlange ein, wenn eine Anforderung auf dem AP-Bus beginnt. Der EXTCTL-Block 204 entnimmt (pops) aus dieser Warteschlange, wenn eine Antwort auf dem Bus zu sehen ist. Wenn eine Antwort empfangen wird, ändert sich der Zustand.

RsQ-Zustandsblock 108. RsQ hält die Antwort von dem Bus, die darauf wartet zur internen Logik 4 übertragen zu werden. BICTL-Block 202 sieht auf den Kopf dieser Warteschlange, um festzustellen, ob eine Antwort an die interne Logik zu senden ist. Der EXTCL-Block 204 speichert bzw. stapelt in diese War­ teschlange ein, wenn eine einlaufende Antwort auf dem Bus zu sehen ist, vorausgesetzt, daß die Antwort ihrer Art nach nicht eine wiederholte Antwort ist. Der BICTL-Block 202 entnimmt aus dieser Warteschlange, wenn die Übertragung zu der internen Logik akzeptiert worden ist. Der entnommene (popped) Schlitz betritt die freie Warteschlange, um auf eine neue Anforderung zu warten. Es gibt eine zugehörige "B" Warteschlange, die wartende Sendewarteschlange (WsQ). Die WsQ hält auch die ein­ laufenden Antworten, jedoch gerade lange genug, damit die Daten als fehlerfrei festgestellt werden können. Wenn die Antwort zur internen Logik übertragen worden ist, ändert sich der Zustand zum FoQ-Zustandsblock 100.

PrQ-Zustandsblock 114. Eine Anforderung geht vom FoQ-Zustands­ block 100 entweder zum TpQ-Zustandsblock 102 oder zum PrQ-Zu­ standsblock 114, und zwar in Abhängigkeit davon, ob die Anfor­ derung für diese BXÜ oder deren Partner bestimmt ist. Die Partnerwarteschlange hält ausstehende Schreibanforderungen für diesen BXU-Partner. Der Warteschlangen-Ausgangsmux verwendet den PrQ-Zustand zur Bestimmung, ob er einen Neuversuch von Anforderungen für seinen Partner bei einer Abkopplung (detach) benötigt. Der BICTL-Block 202 speichert (pushes) in diese Warteschlange ein, wenn eine Partneranforderung auf dem BiDa­ ta-Bus übertragen wird.

Aus der Partnerwarteschlange wird entnommen (popped) durch Empfang einer PopQue von der Partner-BXU. Der Partner signali­ siert PopQue in Abhängigkeit von einem internen PopRsQ, was bedeutet, daß die Antwort an die interne Logik übertragen worden ist.

HpQ-Zustandsblock 116. Die Haltepartnerwarteschlange hält Anforderungen, welche in einem abkoppelnden Partner gefangen sind. Die Funktion des HpQ wird weiter unten unter "Partner­ schaftsströme" genauer beschrieben. Haltepartnerwarteschlange ist notwendig, um im Falle einer Partnerabkopplung einen neuen Versuch richtig durchzuführen. Eine Antwort, die zurückgekom­ men und wegen Fehlern gelöscht worden ist, braucht nicht wie­ derholt zu werden. Wenn die Antwort fehlerhaft zurückgekommen ist, kann sie nicht zu internen Logik übertragen oder in die freie Warteschlange zurückgelegt werden. Die Haltepartnerwar­ teschlange ist ein Halteplatz für diese gefangenen Anforderun­ gen. HpQ wird eingespeichert (pushed), wenn PopQue während des Partner-Kommunikationsfensters signalisiert wird. Dies ge­ schieht nur in einer BXU, deren Partner abkoppelt (is detach­ ing). Eine Entnahme (Pop) wird erzeugt, wenn die Anforderung aufgrund einer Wiederholung einer vorhergehenden Anforderungs­ komplettierung freigegeben wird.

B Warteschlangen

WsQ-Zustandsblöcke 110. Die wartende Sendewarteschlange hält die von dem Bus kommenden Antworten, die darauf warten, daß die Übertragung als fehlerfrei festgestellt wurde. Der Wieder­ holungsmechanismus unternimmt neue Versuche an Schlitzen in dieser Warteschlange. Der EXTCTL-Block 204 speichert diese Warteschlange ein, wenn eine einlaufende Antwort auf dem Bus gesehen wird, vorausgesetzt, daß die Art der Antwort keine Wiederholung ist. Der EXTCTL-Block 104 entnimmt aus dieser Warteschlange, wenn die Ubertragung auf dem AP-Bus als korrekt festgestellt worden ist. Es gibt eine entsprechende A-Warte­ schlange, die RsQ (Antwortwarteschlange), welche die einlau­ fenden Antworten jeweils jedoch nur solange hält, bis sie von der internen Logik akzeptiert worden sind.

LcQ-Zustandsblock 112. Die Verriegelungswarteschlange hält die Anforderungen, welche auf eine Wiederholung nach Empfang einer neu ausgegebenen Antwort warten. Die Logik gibt diese Anforde­ rungen automatisch neu aus, wenn die Sendeschnittstelle frei ist. Schlitze in dieser Warteschlange werden bei einem Fehler wiederholt. Der EXTCTL-Block 204 speichert in diese Warte­ schlange ein, wenn eine einlaufende Antwort auf dem Bus ge­ sehen wird und die Antwort ihrer Art nach eine wiederholte Ausgabe ist. Der BICTL-Block 202 entnimmt (pops) aus dieser Warteschlange, wenn die Sendeschnittstelle frei ist und die Anforderung den Neuausgabevorgang einleiten kann.

Im folgenden wird auf Fig. 8 Bezug genommen, die ein Zustands­ diagramm zum Empfang einer Anforderung auf dem AP-Bus dar­ stellt. Jeder Zustand ist mit einer entsprechenden Warte­ schlange, definiert in Tabelle IV, korreliert.

Tabelle IV

FrQ Zustandsblock 120. FrQ hält die auf eine einlaufende An­ forderung wartenden freien Schlitze. Der EXTCTL-Block 204 prüft diese Warteschlange nach einem freien Schlitz, bevor er eine einlaufende Anforderung akzeptiert. Der EXTCTL-Block 204 speichert in diese Warteschlange ein, wenn alle Zyklen einer abgehenden Antwort als fehlerfrei erkannt worden sind. Der EXTCTL-Block 204 entnimmt dieser Warteschlange, wenn der erste Zyklus einer einlaufenden Anforderung auf dem AP-Bus empfangen worden ist. Wenn das Anforderungsempfangspaket ankommt, wech­ selt der Zustand in den nächsten Zustand.

IrQ-Zustandsblock 122. Die Einlaufanforderungswarteschlange hält ausstehende Anforderungen auf dem AP-Bus. Die Tiefe die­ ser Warteschlange ist gleich derjenigen der PiQ 106 in Fig. 7 und wird von allen an den AP-Bus angekoppelten Komponenten überwacht. Diese Warteschlange hält alle ausstehenden Anforde­ rungen, die auf den AP-Bus ausgegeben sind; jedoch hält jede Komponente gerade ihre individuelle Position in der Warte­ schlange und die Warteschlangentiefe. Der EXTCTL-Block 204 benutzt den Zustand dieser Warteschlange, um den Zeitpunkt zu bestimmen, an welchem dieser Teil eine Antwort aussenden soll­ te, oder ob RPYDEF (Antwortverzögerung) bestätigt werden soll­ te. Der EXTCTL-Block 204 speichert in diese Warteschlange ein, wenn der Empfang der Anforderung auf dem AP-Bus begonnen hat.

Der EXTCTL-Block 204 entnimmt aus dieser Warteschlange, wenn der letzte Zyklus der entsprechenden Antwort auf dem AP-Bus als fehlerfrei festgestellt worden ist. Es gibt in Beziehung stehenden "A"-Warteschlangen, die RqQ 124, die PnQ 126 und die RpQ 128.

RqQ-Zustandsblock 124. RqQ-Warteschlange hält einlaufende Anforderungen, welche auf ihre Übertragung zur internen Logik 4 warten. Der BICTL-Block 202 sucht zu erkennen, ob sich am Kopfende dieser Warteschlange eine Anforderung nach dieser BXU befindet. Ist dies der Fall, so ist diese die nächste an die interne Interface zu sendende Anforderung. Der EXTCTL-Block 204 speichert in diese Warteschlange ein, wenn der erste Zy­ klus einer einlaufenden Anforderung vom AP-Bus empfangen wor­ den ist. In diese Warteschlange wird nicht eingespeichert, wenn die einlaufende Anforderung nicht zu dem Adreßbereich dieser Komponente "paßt" (sowohl physikalische Adressen oder IAC′s-Zwischenstationskommunikationsadressen werden geprüft). Alle anderen IAC′s werden wie normale Anforderungen von dem PCL behandelt. Der BICTL-Block 202 entnimmt aus dieser Warte­ schlange, wenn der erste Zyklus der Anforderung an die interne Schnittstelle gesendet wird. IRQ ist die in Beziehung stehende "B"-Warteschlange. Sobald die Anforderung von der internen Logik 4 akzeptiert worden ist, ändert sich der Zustand.

PnQ-Zustandsblock 126 hält diejenigen Anforderungen, welche von der internen Logik 4 akzeptiert worden sind, jedoch noch keine Antworten von der internen Logik 4 erhalten haben. Der BICTL-Block 202 verwendet den Zustand dieser Warteschlange, um zu bestimmen, welcher Paketpuffer im RAM 212 zur Speicherung der Antwort verwendet werden sollte. Der BICTL-Block speichert in diese Warteschlange ein, wenn die ersten Zyklen der An­ forderung an die interne Schnittstelle gesendet werden. Der EXTCTL-Block 204 entnimmt aus dieser Warteschlange, wenn der erste Zyklus der Antwort auf den AP-Bus gesendet wird. Sobald eine Antwort aus der internen Logik 4 empfangen worden ist, ändert sich der Zustand.

RpQ-Zustandsblock 128. RpQ hält diejenigen Antworten, welche von der internen Logik 4 kommen und auf einen AP-Busschlitz warten. Sobald die Antwort auf den AP-Bus gesendet worden ist, ändert sich der Zustand in den FrQ-Zustand 120.

Der einfache Fall des Sendens und Empfangs einer Anforderung wird durch Verfolgung des Zustandes einer Einzeltransaktion ausgeführt, wie sie oben beschrieben worden ist. Die Zustands­ diagramme der Fig. 7 und 8 stellen zustätzliche Zustände dar, welche durch einige Faktoren kompliziert werden:

• 1. Bis zu sechs Transaktionen können gleichzeitig statt­ finden.
• 2. Das Vorsehen einer Antwortverzögerung bedingt zusätzlich die Umordnung der Warteschlangen.
• 3. Zusätzliche Zustandsinformationen werden für Fehlertoleran­ zen benötigt.
• 4. In Fehlerfällen brauchen Anforderungen frühere Zustandsin­ formationen für Neuversuche bzw. Wiederholungen.
• 5. Partner-Bussteuereinheiten (BXÜs) müssen des anderen Anfor­ derungen verfolgen können.

Die erste Schwierigkeit wird dadurch beherrscht, daß jeder Zustand in Diagrammen gemäß Fig. 7 und 8 zu einer FIFO bzw. Stapel-Warteschlange gemacht und das gleichzeitige Zirkulieren vieler Transaktionen ermöglicht wird. Das zweite Problem der Antwortverzögerung wird wie folgt behandelt. Zustände, welche umgeordnet werden können, werden mit einem Rezirkulationsweg versehen, der die Entnahme einer Anforderung vom Boden der Warteschlange und die Einspeicherung auf dem Kopf der Warte­ schlange während des gleichen Zyklus ermöglicht. Die dritte Komplikation der Beschaffung zusätzlicher Zustandsinforma­ tionen für Fehlertoleranzen wird mit Extrazuständen im Zu­ standsdiagramm beherrscht. Die vierte Komplikation, die Wie­ derholung, wird durch Hinzufügen von Extrazustandsübergängen gehandhabt, welche die Anforderungen in einen früheren Zustand zurückgehen lassen, wenn ein Fehler auftritt. Die letzte Kom­ plikation einer Partnerschaft wird durch zusätzliche Warte­ schlangen berücksichtigt, welche den Zustand eines Partners verfolgen.

Abgehende Anforderungsströme

Anfangs befinden sich drei freie Schlitze in einer freien abgehenden Warteschlange 100, die auf eine auslaufende Anfor­ derung wartet. Wenn eine Anforderung an die Bus-Steuerlogik BCL gegeben wird, wird der erste Sendeschlitz in der freien abgehenden Warteschlange 100 der Anforderung zugeordnet, und der Sendeschlitz fällt in die zeitweilige Warteschlange 102. In der zeitweiligen Warteschlange wartet der Schlitz auf die nächste AP-Busentscheidungssequenz und wird zum richtigen Zeitpunkt einer Entscheidung unterworfen. Wenn eine Zuteilung gegeben wird, fällt der Anforderungsschlitz in die Zuteilungs­ warteschlange 104, wo er auf seine Ankopplung an den AP-Bus wartet. Die Doppellinien des Zuteilungswarteschlangenblocks 104 sagen, daß diese Warteschlange eine Tiefe über den Bus hat. Wenn die Anforderung auf den Bus gegeben wird, fällt der Schlitz in die Leitungswarteschlange (pipe queue) 106, wo er auf eine Antwort wartet. Die Doppellinien des Leitungswarte­ schlangenblocks 106 besagen, daß diese Warteschlange eine über den Bus gehende Tiefe hat. Wenn die Antwort auf dem Bus gese­ hen wird, fällt der Schlitz in die Antwortwarteschlange 108. Die Antwort wartet in der Antwortwarteschlange, bis sie zur internen Logik übertragen werden kann. Nach der Annahme der Antwort durch die interne Logik wird der Schlitz wieder frei, und umgekehrt in die freie Warteschlange 100 zurück.

Parallel zum Fallen in die Antwortwarteschlange 108 tritt der Sendeschlitz auch in die wartende Sendewarteschlange 110 ein. Die Doppellinien der wartenden Sendewarteschlange 110 besagen, daß diese Warteschlange eine über den Bus reichende Tiefe hat. Der Sendeschlitz wartet in der wartenden Sendewarteschlange solange, bis sich die Transaktion als fehlerfrei erwiesen hat. Wenn "aktiviere Warten für berl" gesetzt wird, so verläßt der Sendeschlitz die wartende Sendewarteschlange 110 zwei Zyklen später; anderenfalls verläßt der Schlitz die wartende Sende­ warteschlange beim nächsten Zyklus.

Wiederholungsantwort

Wenn die Antwort eine Wiederholungsantwort ist, so fällt der Schlitz aus der wartenden Sendewarteschlange 110 in die ver­ riegelte Warteschlange 112. Der Schlitz wartet in der verrie­ gelten Warteschlange solange bis keine neue Anforderung von dem Bi-Bus akzeptiert wird. Der Schlitz geht dann zurück in die zeitweilige Warteschlange 102, wo er neu entschieden und auf den AP-Bus gesendet wird.

Wenn eine Anforderung die erste Anforderung in der Leitungs­ warteschlange 106 ist und eine Antwortverzögerung auftritt, wird die Anforderung der Leitungswarteschlange entnommen und auf dem kopfseitigen Ende der Leitungswarteschlange wieder eingespeichert. Wenn die Anforderung dadurch wieder die erste Anforderung in der Leitungswarteschlange 106 wird und die Antwort zurückkommt, so fällt die Anforderung in die Antwort­ warteschlange 108. Wenn Verzögerungen dazu geführt haben, daß Antworten außerhalb der Reihenfolge zurückkommen, warten alle außerhalb der Reihefolge zurückgekommenden Antworten in der Antwortwarteschlange 108 auf ihre Umordnung. Anforderungen werden vom Boden entnommen und am Kopfende der Antwortwarte­ schlange 108 eingespeichert, bis die erste Anforderung am Boden der Warteschlange ist. Die Antwort auf diese erste An­ forderung kann danach zu internen Logik zurückgeführt werden, und der Sendeschlitz kehrt zu der freien Warteschlange 100 zurück.

Fehlerströme

Wenn ein Fehler auftritt, müssen alle diejenigen Sendeschlit­ ze, welche sich in einem offenen Anforderungszustand befinden, wiederholt werden. Dies geschieht dadurch, daß zunächst jeder Schlitzzustand geprüft wird, um festzustellen, ob sich ein Schlitz in der zeitweiligen Warteschlange 102, der Zuteilungs­ warteschlange 104, der Leitungswarteschlange 107, der warten­ den Sendewarteschlange 110, der verriegelten Warteschlange 112 oder in der Partnerwarteschlange 114 befindet. Wenn sich ein Schlitz in einer dieser offenstehenden Anforderungswarte­ schlangen befindet, wird er zur zeitweiligen Warteschlange 102 zurückgeführt, wo er die Entscheidungssequenz wieder starten kann. Anforderungen in der Antwortwarteschlange 108, jedoch nicht diejenigen in der wartenden Sendewarteschlange 110, sind beendet. Wegen der Antwortverzögerung ist die Antwort außer der Reihe und kann nicht zur internen Logik zurückgeführt werden. Diese Schlitze bleiben in der Antwortwarteschlange 108 durch die Fehlerfenster, und während der Wiederholung wird die vorhergehende Anforderung kompletiert, und danach kann die Antwort zur internen Logik übertragen werden. Der Schlitz wird danach frei und zur freien auslaufenden Warteschlange 100 zurückgeführt.

Partnerschaft

Wenn eine Anforderung von der BXU 10 als eine Partneranforde­ rung erkannt, d.h. wenn eine Anforderung von der Partner-BXU 12 behandelt wird, wird sie in die Partnerwarteschlange 114 eingegeben. Sie wartet dort, während die Partneranforderung entscheidet, die Partner-BXU die Anforderung an den AP-Bus 20 sendet, die Partnerantwort zurückommt, und die Partnerantwort von der internen Logik der Partner-BXU 12 akzeptiert wird. Wenn die Partner-BXU 12 die Übertragung der Antwort vervoll­ ständigt, legt sie ein Signal an die PopQue-Leitung, die in den lokalen Bus 18 einbezogen ist, um dadurch der BXU 10 zu signalisieren, daß die Anforderung aus der Partnerwarteschlan­ ge der BXU 10 entnommen wird. Die Anforderung wird aus der Partnerwahlschlange 114 entnommen und in den HpQ-Zustandsblock 116 gesetzt. Wenn die Partneranforderungen in Ordnung sind, fließen sie unmittelbar auf die freie Warteschlange, FoQ-Zu­ standsblock 100. Wenn die Antwort außer der Reihe zurückgege­ ben wurde, kann sie weder zur internen Logik übertragen, noch in die freie Warteschlange FoQ zurückgelegt werden. Eine Part­ ner-Haltewarteschlange ist eine Haltestelle für diese einge­ fangenen Anforderungen.

Da alle Anforderungen von beiden BXUs 10, 12 verfolgt werden, wird die Reihenfolge bezüglich aller Anforderungen mittels eines einzigen lokalen Busses 18 aufrechterhalten. Obwohl eine Antwortverzögerung in Partnerfällen entaktiviert wird, können Antworten außer der Reihe zurückkommen, da sie über separate AP-Busse 20 oder 22 entsprechend der zugehörigen BXU 12 oder 10 übertragen wurden. Ein AP-Bus kann geringeren Verkehr oder eine raschere Speicherantwort haben, so daß eine Anforderung an diesen Bus früher als eine vorhergehende Anforderung an den anderen Bus beendet werden kann.

Da die Anforderungsreihenfolge von beiden BXUs aufrechterhal­ ten wird, wartet eine außer der Reihe gegebene Antwort an der BXU 10 in der Antwortwarteschlange 108, bis die vorhergehende Anforderung an die Partner-BXU 12 vollständig ist und so an die BXU 10 mittels der PopQue-Leitung 226 signalisiert wird. Danach wird die Antwort an die interne Logik 8 zurückgeführt, und das PopQue-Signal an den Partner gegeben. Wenn ein Fehler vor Beendigung der vorhergehenden Anforderung aufgetreten ist, so könnte diese Anforderung eingefangen werden. Das bedeutet, die Anforderung beendet, jedoch hinter einer noch nicht been­ deten vorhergehenden Anforderung eingefangen worden ist. In normalen Fehlerfällen bildet das Einfangen kein Problem, da jede BXU ihre eigenen Anforderungen wiederholt. Die eingefan­ gene Anforderung wird nicht wiederholt, sondern wartet in der Antwortschlange 8 während der Wiederholung solange, bis die vorhergehende Anforderungswiederholung abgeschlossen ist. Wenn die Partner-BXU 12 die PopQue-Leitung bestätigt, wird die eingefangene Anforderung auf der BXU 10 freigegeben und kann zur internen Logik 4 übertragen werden. Das Einfangen wird zu einem Problem in dem Falle, daß eine BXU abgekoppelt wird. Wenn eine BXU abgekoppelt wird, sieht sie auf ihre Warte­ schlangen, um festzustellen, ob irgendwelche Anforderungen beendet, jedoch eingefangen worden sind. Wenn es eingefangene Anforderungen gibt, muß die BXU ein Signal an ihren Partner geben, damit diese Anforderungen nicht wiederholt werden. Dieses Signalgabe geschieht über die PopQue. Wenn die verblei­ bende BXU dieses Signal sieht, so nimmt sie diese Partneran­ forderung aus der Partnerwarteschlange 114 in die Haltepart­ nerwarteschlange 116. Anforderungen in der Haltepartnerwarte­ schlange werden nicht wiederholt. Der Schlitz wartet in der Haltepartnerwarteschlange, bis die vorhergehende Anforderung, die eingefangen worden ist, wiederholt und beendet worden ist. Die Reihenfolge wird jetzt erneut gewonnen, und der Schlitz wird in die freie Warteschlange 100 zurückgesandt.

Im folgenden wird auf Fig. 8 Bezug genommen, anhand der die einlaufenden Anforderungsströme beschrieben werden.

Anfangs sind drei freie Empfangsschlitze in einer freien Emp­ fangswarteschlange 120, die auf eine einlaufende Anforderung wartet. Ein freier Empfangsschlitz für einlaufende Anforderun­ gen wartet in der freien Empfangswarteschlange 120, bis eine Anforderung für diese BXU auf dem AP-Bus erkannt wird. Dieser Empfangsschlitz fällt dann in die Einlauf-Anforderungswarte­ schlange 122 und parallel in die Anforderungswarteschlange 124. Die Doppellinien auf der Einlauf-Anforderungswarte­ schlange 122 besagen, daß diese Warteschlange eine über den Bus gehende Tiefe hat. Die Einlauf-Anforderungswarteschlange 122 hält die gleiche Information wie die Leitungswarteschlange 106 in Fig. 7 aufrecht. Dieser Leitungswarteschlangenzustand muß auf der Empfangsseite aufrechterhalten werden, damit die Empfangs-BXU weiß, wann es an ihr ist, zu antworten. Wenn eine Anforderung die erste Anforderung in der Einlauf-Anforderungs­ warteschlange 122 ist und eine Antwortverzögerung auftritt, wird die Anforderung aus der Einlauf-Anforderungswarteschlange 122 entnommen und auf das Kopfende der Einlauf-Warteschlange wieder eingespeichert. Wenn die Anforderung wieder zur ersten Anforderung in der Einlauf-Anforderungswarteschlange 122 wird und die Antwort zurückkommt, so kehrt die Anforderung in die freie Warteschlange 120 zurück.

Die Anforderungswarteschlange 124 hält den Zustand einer An­ forderung aufrecht, die angenommen worden ist und in BCL war­ tet. Wenn die Anforderung zur internen Logik übertragen worden ist, fällt der Empfangsschlitz in die laufende Warteschlange 126, wo sie auf eine Antwort wartet. Wenn die Antwort zum BCL zurückkommt, fällt der Schlitz in die Antwortwarteschlange 128, die dem BCL sagt, daß er die Verzögerung der Antwort beenden und die Antwort auf den AP-Bus zur richtigen Zeit senden soll. Wenn die Antwort auf den AP-Bus ausgegeben wird, fällt der Schlitz aus der Einlauf-Anforderungswarteschlange 122 und kehrt zur freien Warteschlange 120 zurück.

Es gibt einige wenige Fälle, die dieses Empfangswarteschlan­ genmodell komplizieren. Eine Antwortverzögerung bewirkt, daß die Einlauf-Anforderungswarteschlange 122 in der gleichen Weise wie die Leitungswarteschlange 106 in Fig. 7 umgeordnet wird. Wenn "Durchlauf" 125 aktiviert wird, so läuft die ein­ laufende Anforderung direkt vom AP-BUS zur internen Logik durch, und die Anforderungswarteschlange 124 wird umgangen. Fehler werden sehr einfach in der Empfangswarteschlange behan­ delt. Da alle ausstehenden Anforderungen wiederholt bzw. neu ausgegeben werden, werden die Empfangswarteschlangen bei einem Fehler zurückgesetzt.

Claims (14)

1. Einrichtung zur Warteschlangenbildung von Anforderungen und Antworten auf einem Pipeline-Paketbus, gekennzeichnet durch:
einen RAM (212) zur Pufferung von Busanforderungen dadurch, daß Paketinformationen entsprechend jeder über den Bus zu sendenden Anforderung in jeder Anforderung zugeordneten Bus­ zeitschlitzen gespeichert wird; eine Anzahl (n) von Sende­ schlitzen (208) zum Verfolgen des Zustandes von n Sende­ anforderungen, die in dem RAM (212) gespeichert sind;
eine Anzahl (m) von Empfangsschlitzen (210) zur Verfolgung des Zustandes von m Empfangsanforderungen, welche in dem RAM (212) gespeichert sind;
mehrere Sendewarteschlangenzähler (230) zur Bildung einer ersten Zustandslogik, die durch eine Folge von Zuständen ent­ sprechend einer Reihe von Sendewarteschlangen zum Verfolgen einer abgehenden Anforderung und einer entsprechenden einlau­ fenden Antwort durchschaltbar ist;
mehrere Empfangswarteschlangenzähler (232) zur Bildung einer zweiten Zustandslogik, die durch eine Folge von Zustän­ den entsprechend einer Reihe von Empfangswarteschlange zum Verfolgen einer einlaufenden Anforderung und einer ent­ sprechenden Antwort durchschaltbar ist;
einen mit den Sende- und Empfangsschlitzen verbundenen Ausgangsmux bzw. -multiplexer (214) zur Erzeugung von Zu­ standsinformationen bezüglich des Zustandes der Schlitze; und mit dem Ausgangsmux (214) gekoppelte Mittel (203, 204, 206), die in Abhängigkeit von den Zustandsinformationen bezüg­ lich des Zustandes der Schlitze die Sendewarteschlangenzähler (230) und die Empfangswarteschlangenzähler (232) entsprechend einem vorgegebenen Systembusprotokoll inkrementieren oder dekrementieren.

2. Einrichtung nach Anspruch 1, dadurch gekennzeichnet, daß der Ausgangsmux (214) Mittel zur Erzeugung von Positionslei­ tungen aufweist, welche Informationen bezüglich der durch Transaktionen besetzten Warteschlangenpositionen vermitteln.

3. Einrichtung nach Anspruch 1 oder 2, dadurch gekennzeich­ net, daß der Ausgangsmux (214) Mittel zum Umordnen von Antwor­ ten durch Ordnen der Schlitze und Mittel zum Erzeugen von RAM-Wortansteuerungen (220) durch Bestimmung der zum Ein­ schreiben aus dem RAM (212) verfügbaren Schlitze aufweist.

4. Einrichtung nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß der Ausgangsmux (214) Mittel (313) zur Erzeugung von RAM-Wortansteuerungen durch Bestimmung der zum Füllen aus dem Bus verfügbaren Schlitze aufweist.

5. Einrichtung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß jeder der Sendeschlitze und der Empfangs­ schlitze einen Multibit-Schieberegister-Tiefenzähler aufweist, dessen maximaler Zählwert gleich der maximalen Warteschlangen­ tiefe ist, und daß Mittel zum Rücksetzen jedes der Tiefenzäh­ ler auf einen speziellen Wert vorgesehen sind.

6. Einrichtung nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, daß jeder der Sendeschlitze und der Empfangs­ schlitze einen Schlitzzustandszähler zum Verfolgen des Zustan­ des des Schlitzes in den Sende- und Empfangswarteschlangen aufweist, wobei die Anordnung so getroffen ist, daß die Tie­ fenzähler und die Zustandszähler auf Werte rückgesetzt werden, welche die Sendeschlitze auf erste, zweite und dritte in der freien Sendewarteschlange und die Empfangsschlitze auf erste, zweite und dritte in der freien Empfangswarteschlange initia­ lisieren.

7. Einrichtung nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß die Tiefenzähler und die Zustandszähler auf Werte zurückgesetzt werden, welche die Empfangsschlitze auf erste, zweite oder dritte Positionen der freien Empfangs­ warteschlange bei Auftreten eines Fehlers setzen.

8. Verfahren zur Warteschlangenbildung von Anforderungen und Antworten auf einem Pipeline-Paketbus, dadurch gekennzeichnet, daß

• A. Busanforderungen dadurch gepuffert werden, daß Paket­ informationen entsprechend jeder über den Bus zu sendenden Anforderung in zugeordneten Buszeitschlitzen gespeichert wer­ den;
• B. in n Sendeschlitzen (208) der Zustand von n Sendean­ forderungen verfolgt wird, die in einem RAM (212) gespeichert werden;
• C. in m Empfangsschlitzen (210) der Zustand von m Emp­ fangsanforderungen verfolgt wird, welche in dem RAM (212) gespeichert werden;
• D. eine erste Zustandslogik durch eine Reihe von Zustän­ den entsprechend einer Reihe von Sendewarteschlangen geschal­ tet wird, um eine abgehende Anforderung und eine entsprechende einlaufende Antwort zu verfolgen;
• E. eine zweite Zustandslogik durch eine Reihe von Zustän­ den entsprechend einer Reihe von Empfangswarteschlangen ge­ schaltet wird, um eine einlaufende Anforderung und eine ent­ sprechende Antwort zu verfolgen;
• F. Zustandsinformationen bezüglich des Zustandes der Schlitze erzeugt werden; und
• G. Sendewarteschlangenzähler (230) und Empfangswarte­ schlangenzähler (232) in Abhängigkeit von der Zustandsinforma­ tion bezüglich des Zustandes der Schlitze entsprechend einem vorgegebenen Systembusprotokoll inkrementiert oder dekremen­ tiert werden.

9. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß Positionsleitungen erzeugt werden, welche Informationen bezüg­ lich der von Transaktionen besetzten Warteschlangenpositionen erzeugen.

10. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß Antworten durch Umordnen der Schlitze umgeordnet und RAM-Wort­ auswahlen dadurch getroffen werden, daß die zum Einschreiben aus dem RAM (212) verfügbaren Schlitze bestimmt werden.

11. Verfahren nach Anspurch, dadurch gekennzeichnet, daß RAM-Wortauswahlen (313) dadurch getroffen werden, daß die zum Füllen aus dem Bus verfügbaren Schlitze bestimmt werden.

12. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß jeder der Sendeschlitze und Empfangsschlitze mit einem Multi­ bit-Schieberegister-Tiefenzähler versehen wird, dessen maxima­ ler Zählwert gleich der maximalen Warteschlangentiefe gewählt wird, und daß jeder der Tiefenzähler auf einen speziellen Wert rückgesetzt wird.

13. Verfahren nach Anspruch 8 oder 9, dadurch gekennzeichnet, daß jeder der Sendeschlitze und der Empfangsschlitze mit einem Schlitzzustandszähler zur Verfolgung des Zustandes des Schlit­ zes in den Sende- und Empfangswarteschlangen versehen und die Tiefenzähler und die Zustandszähler auf Werte rückgesetzt werden, welche die Sendeschlitze auf erste, zweite und dritte Positionen in der freien Sendewarteschlange und die Empfangs­ schlitze auf erste, zweite und dritte Positionen der freien Empfangswarteschlange initialisieren.

14. Verfahren nach einem der Ansprüche 8 bis 13, dadurch gekennzeichnet, daß die Tiefenzähler und die Zustandszähler auf Werte rückgesetzt werden, welche die Empfangsschlitze auf erste, zweite oder dritte Positionen in der freien Empfangs­ warteschlange bei Auftreten eines Fehlers bringen.