DE68924435T2 - Nichtblockierender NxM-Arbitrierungsschalter mit grosser Bandbreite. - Google Patents

Description

• Die Erfindung bezieht sich auf nichtblockierende NxM-Arbitrierungsschalter mit großer Bandbreite, die beispielsweise in Multiprozessorsystemen als Arbitrierungssystem zur Verarbeitung von zugriffsanforderungen von zahlreichen Eingängen an zahlreiche Ausgänge verwendet werden.
• In großen komplexen Computersystemen sind zahlreiche Speicher oder Basisspeichermoduln (BSM) sowie zahlreiche Prozessoren, die mit zahlreichen Speichern mit Zwischenspeicherung kommunizieren, von großem Interesse.
• Arbitrierungssysteme sind in der herkömmlichen Technik bekannt, so z.B. das in der Patentschrift US-A-4 473 880 von Budde et al., oder der Patentschrift US-A-4 499 538 von Finger et al. beschriebene System, das für mehrere Prozessoren oder Mikroprozessoren mit einem gemeinsamen Bus eine Art von Arbitrierung bereitstellt. Diese Arbitrierungssysteme mit einem gemeinsamen Bus sind relativ langsame Systeme, da nur ein Eingang für den Bus von einer Einheit über den Bus zu einer Ausgangseinheit in einem bestimmten Zeitintervall gesendet werden kann. Koppelpunktschalter in einer Schaltmatrix, wie sie in der Patentschrift US-A-4 417 245 von Melas et al. beschrieben wird, koppeln zahlreiche Eingänge gleichzeitig mit zahlreichen Ausgängen, sofern ein bestimmter Eingang nicht zusammen mit einem anderen Eingang auf denselben Ausgang zugreifen möchte, und unter der Voraussetzung, daß eine bestimmte Form von separater Steuerung vorhanden ist. Ein Arbiter ist nicht vorhanden.
• In der Patentschrift EP-A-97 351 wird ein NxM-Matrixschalter mit den Merkmalen des vorkennzeichnenden Teils von Anspruch 1 beschrieben, der in einem mehrstufigen Routing-Netzwerk verwendet wird.
• In dem Versuch, sowohl ungesteuerte Eingangsanforderungen und Arbitrierung zu vereinen, stellt die vorliegende Erfindung einen NxM-Schalter mit folgenden Komponenten vor:
M-Ausgangsports;
• N-Daten- und Anforderungseingängen, wobei jeder Anforderungseingang einem Dateneingang zugeordnet ist und anzeigt, zu welchem M-Ausgangsport das zugeordnete Datenpaket gesendet werden soll;
• M-Arbiter und Gattermittel, wobei jeder Arbiter und jedes Gattermittel zwischen den N-Daten- und den Anforderungseingängen sowie einem anderen M-Ausgangsport gekoppelt ist;
• jeder Arbiter und jedes Gattermittel reagiert auf die Datenund Anforderungseingänge, um Daten gleichzeitig mit den angeforderten Ausgangsports zu gaten, wenn keine konkurrierenden Anforderungseingänge für denselben Ausgangsport vorhanden sind, sondern wenn konkurrierende Anforderungseingänge für denselben Ausgangsport vorhanden sind, um die zugeordneten konkurrierenden Datenpakete für den oder die zugeordneten Ausgangsport(s) zu speichern und zu sequentieren, während gleichzeitig nicht-konkurrierende Datenpakete direkt zu den anderen Ausgangsports gesendet werden, wobei das System dadurch gekennzeichnet ist, daß FIFO-Puffermittel, die zwischen jedem der N-Daten- und Anforderungseingängen sowie den Arbitern und Gattermitteln gekoppelt sind, die Datenpakete und Anforderungssignale jedes Taktzyklusses speichern und sequentieren, wobei das FIFO-Puffermittel mindestens N-Stufen hat.
• Die vorliegende Erfindung stellt darüber hinaus ein Multiprozessorsystem mit diesem Schalter vor.
• In einem Ausführungsbeispiel der vorliegenden Erfindung werden zahlreiche Eingangssignale mit Daten und zugeordnetem Ausgangsanforderungscode selektiv zu einem der zahlreichen Ausgänge unter Verwendung eines Arbiters und Gattermitteln gesendet, die jeden Ausgang steuern. Die Arbiter und Gattermittel reagieren auf Eingangssignale, um die nicht-konkurrierenden Eingangssignale gleichzeitig mit den nicht-konkurrierenden Ausgängen zu gaten und um konkurrierende Signale zu den zugeordneten Ausgängen zu sequentieren.
• Der vorliegende Erfindung wird im folgenden anhand eines Ausführungsbeispiels mit Begleitzeichnungen beschrieben.
• Figur 1 ist ein Blockdiagramm eines Gesamtsystems gemäß einem Ausführungsbeispiel der vorliegenden Erfindung.
• Figur 2 ist ein Blockdiagramm eines Arbiters.
• Figur 3 ist ein Blockdiagramm einer bevorzugten Erweiterungsmöglichkeit des Systems von Figur 1, um zusätzliche Prozessoren und/oder Speicher hinzuzufügen.
• Im Systemblockdiagramm von Figur 1 ist ein Beispiel eines nichtblockierenden NxM-Arbitrierungsschalters mit großer Bandbreite in einem Multiprozessorsystem dargestellt. Das System in Figur 1 zeigt die Prozessoren 11 bis 14, die selektiv mit einem von vier Basisspeichermoduln (BSM) 21 bis 24 verbunden sind. In der Praxis kann die Zahl der mit dem Basisspeicher verbundenen Prozessoren 32 oder mehr betragen. Die Eingänge der Prozessoren 11 bis 14 werden zu den entsprechenden Puffern 31 bis 34 geleitet. Bei diesen Puffern 31 bis 34 kann es sich beispielsweise um FIFO-Puffer (First In, First Out) handeln. Der Ausgang von jedem der Prozessoren 11 bis 14 enthält ein Anforderungscodesignal und zugeordnete Datensignale oder Datenpakete. Das Anforderungscodesignal könnte einfach ein logischer Pegel 1 bei einem der vier Bleidrähte sein. Das Ausgangsanforderungscodesignal von jedem der Puffer 31 bis 34 wird zu jedem der vier Arbiter 41 bis 44 gesendet. Das Anforderungscodesignal und die zugeordneten Datensignale oder Datenpakete werden zusammen durch die Puffer 31 bis 34 sequentiert. Das Anforderungscodesignal kann über vier Drähte oder Leitungen gehen, wobei nur einer der vier Drähte einen logischen Pegel 1 hat, während die anderen Drähte einen logischen Pegel 0 haben. Der logische Pegel 1 kann fünf Volt haben, und der logische Pegel 0 Massepotential. Wenn der Prozessor 11 beispielsweise mit BMS 21 verbunden werden will, stellt der Prozessor 11 einen logischen Pegel 1 bei Draht 101 von Puffer 31 sowie einen logischen Pegel 0 bei den Drähten 102 bis 104 an den ersten Anforderungsports der Arbiter 42 bis 44 bereit. Wenn der Prozessor 11 mit BSM 22, BSM 23 oder BSM 24 gekoppelt werden möchte, wäre der logische Pegel 1 nur auf Leitung 102, 103 bzw. 104 vorhanden. Wenn Prozessor 14 mit BSM 21, BSM 22, BSM 23 oder BSM 24 gekoppelt werden möchte, wäre der logische Pegel 1 auf den Leitungen 141, 142, 143 bzw. 144 vorhanden. Die Prozessoren 12 und 13 können mit jedem BSM 21 bis 24 durch den entsprechenden logischen Pegel 1 bei der Anforderungsleitung zu den Arbitern 41 bis 44 gekoppelt werden.
• Jeder Arbiter legt zuerst fest, ob ein Eingang von einem der vier FIFO-Puffer 31 bis 34 vorhanden ist. Wenn mehr als ein Eingang für diesen Arbiter vorhanden ist, sequentiert dieser die Dateneingänge in jedem Taktzyklus durch einen zugeordneten Selektor 51 bis 54. Die Daten werden zu allen vier Selektoren 51 bis 54 gesendet. Wenn keine konkurrierenden Zugriffe vorhanden sind, oder mehr als ein Prozessor versucht, ein bestimmtes Speichermodul beim Arbiter zu verwenden, wird der Eingang von jedem Puffer 31 bis 34 bei jedem Selektor 51 bis 54 gleichzeitig über die zugeordneten Puffer 61 bis 64 mit dem zugeordneten BSM 21 gekoppelt. Die Selektoren 51 bis 54 sind jedem der BSM 21 bis 24 zugeordnet. Die Arbiter 41 bis 44 legen fest, zu welchem BSM 21 bis 24 die Eingangsdaten von einem gegebenen Prozessor gesendet werden, und stellen einen Auswahlcode für die Selektoren 51 bis 54 bereit, um die Daten von den Puffern 31 bis 34 mit den entsprechenden Puffern 61 bis 64 zu gaten.
• Wenn mehr als ein Konkurrent für ein bestimmtes BSM vorhanden ist, legt einer der Arbiter 41 bis 44, der einem bestimmten BSM zugeordnet ist, die Sequenz unter den zugeordneten Selektoren 51 bis 54 fest. Wenn beispielsweise ein Anforderungscodesignal von Prozessor 11 und Prozessor 12 über die Puffer 31 und 32 für BSM 21 eingeht, werden beide zum Arbiter 41 gesendet. Der Arbiter 41 sendet z.B. während des ersten Taktimpulses einen ersten Auswahlcode zum Selektor 51, um den Ausgang vom FIFO-Puffer 31 über den Selektor 51 mit dem Puffer 61 und dem BSM 21 zu gaten. Während des nächsten Taktzyklusses wird der zweite Auswahlsignalcode zum Selektor 51 gesendet, und die Daten des Prozessors 12 bei Puffer 32 werden über den Selektor 51 mit dem BSM 21 gekoppelt.
• In Figur 2 ist ein logisches Blockdiagramm für jeden Arbiter von Figur 1 abgebildet. Es sind vier Eingangsanforderungsports 201 bis 204 für jeden Arbiter 41 bis 44 vorhanden. Der erste Eingangsport 201 ist über den Puffer 31 mit dem Prozessor 11 gekoppelt. Für den Arbiter 41 ist dieser Eingangsport 201 über den Bleidraht 101 gekoppelt. Der zweite Eingangsport 202 ist über den Puffer 32 mit dem Prozessor 12 verbunden, der dritte Port 203 über den Puffer 33 mit dem Prozessor 13 und der vierte Port 204 über den Puffer 34 mit dem Prozessor 14. Die Anforderungen an den Eingängen 201 bis 204 werden zu den entsprechenden UND-Gattern A1 bis A4 gesendet. Die Ausgänge der UND-Gatter A1 bis A4 werden zu den Set-Eingängen der Flip- Flop-Register S1 bis S4 gesendet. Der Q-Ausgang von Register S1 wird direkt zum Ausgangsdraht 205 und zum NOR-Gatter 100 gesendet. Die Q-Ausgänge von den Registern S2 bis S4 werden ebenfalls zum NOR-Gatter 100 gesendet. Der -Ausgang des Schaltregisters S1 wird zum UND-Gatter A5 gesendet. Der Q-Ausgang von Register S2 wird ebenfalls zum UND-Gatter AS gesendet. Der Q-Ausgang der Schalter S3 und S4 wird mit den entsprechenden Eingängen der UND-Gatter A6 und A7 gekoppelt. Das UND-Gatter A6 empfängt ebenfalls den -Ausgang von den Registern S1 und S2. Das UND-Gatter A7 empfängt einen -Ausgang von den Registern S1, S2 und S3 sowie den Q-Ausgang von Register S4. Der Q-Ausgang von Schalter S1 wird zum Reset-Eingang des Schalters S1 gesendet. Der Ausgang des UND-Gatters A5 wird mit dem Reset-Eingang des Registers S2 gekoppelt. Der Ausgang von UND-Gatter A6, der mit dem Reset-Eingang von Register S3 und dem Ausgang von UND-Gatter A7 gekoppelt ist, wird mit dem Reset-Eingang von Register S4 gekoppelt. Die Ausgänge der UND- Gatter A5 bis A7 bei den Drähten 206 bis 208 und der Q-Ausgang von Register bei Draht 205 erzeugen einen 4-Bit-Adreßcode, der zum entsprechenden Selektor 51 bis 54 gesendet wird, um den Ausgang auszuwählen. Beim einfachen Ausführungsbeispiel von Figur 1 mit nur vier Prozessoren und vier BSM aktiviert der Arbiterausgang 205 bis 208 mit einem logischen Pegel 1 die zugeordneten Prozessordaten für das zugeordnete Basisspeichermodul. Wenn der Ausgang von Register S1 z.B. einen logischen Pegel 1 hat, wird der Ausgang von Prozessor 11 mit dem diesem Arbiter zugeordneten Basisspeichermodul gekoppelt. Im Fall von Arbiter 41 werden die Daten von Prozessor 11 mit BSM 21 gekoppelt. Im Fall von Arbiter 42 werden die Daten von Prozessor 11 mit BSM 22 gekoppelt, bei Arbiter 43 die Daten von Prozessor 11 mit BSM 23 und bei Arbiter 44 die Daten von Prozessor 11 mit BSM 24. Wenn im Fall von Arbiter 41 ein logischer Pegel 1 beim Ausgang 208 von Arbiter 41 vorhanden ist, werden die Daten von Prozessor 14 mit dem Basisspeichermodul 21 gekoppelt. Wenn der logische Pegel 1 bei Ausgang 208 des Arbiters 42 vorhanden ist, werden die Daten von Prozessor 14 mit BSM 22 gekoppelt. Bei Arbiter 43 die Daten von Prozessor 14 mit BSM 23, usw.
• Im Startzustand des Arbiters sind logische Pegel 0 bei den Q- Ausgängen und logische Pegel 1 bei den -Ausgängen der Register S1 bis S4 vorhanden. Das NOR-Gatter 100 stellt einen logischen Pegel 1 für die UND-Gatter A1 bis A4 mit Nullen am Eingang bereit. Wenn nur eine Anforderung oder ein logischer Pegel 1 bei Eingang 202 z.B. vorliegt, aktiviert dieser Ausgang das UND-Gatter A2 mit logisch 1, das mit dem Set-Eingang des Schalters S2 gekoppelt ist, um einen logischen Pegel 1 beim Q-Ausgang des Registers S2 zu erzeugen. Der Ausgang mit dem logischen Pegel 1 von Register S2 ist mit dem NOR-Gatter 100 gekoppelt, und als Reaktion auf diesen logischen Pegel 1 wird ein logisch niedriger Pegel oder Pegel 0 vom NOR-Gatter 100 zu den UND-Gattern A1 bis A2 gesendet, um alle weiteren Anforderungen zu unterbrechen. Der Eingang mit dem logischen Pegel 1 beim UND-Gatter A5 von Register S2 ermöglicht es dem Eingang mit dem logischen Pegel 1 vom -Ausgang des Registers S1, einen logischen Pegel 1 am Ausgang 206 zu erzeugen. Der Code mit dem logischen Pegel 1 nur auf Draht 206 fordert den dem Arbiter zugeordneten Selektor 51 bis 54 an, die Daten vom zweiten Prozessor 12 mit dem Basisspeichermodul zu koppeln, das dem Selektor zugeordnet ist. Bei Arbiter 41 beispielsweise werden die Daten von Prozessor 12 mit BSM 21 gekoppelt.
• Eine Konkurrenzsituation liegt dann vor, wenn zwei oder mehr Anforderungen für ein bestimmtes BSM bestehen. Es sei beispielsweise auf die Anforderungen bei den Eingängen 201 und 203 von den Prozessoren 11 und 13 für BSM 21 verwiesen. Der Arbiter 41 stellt den logischen Pegel 1 bei den UND-Gattern A1 und A3 fest, um es dem logisch 1 von NOR-Gatter 100 zu ermöglichen, eine Reihe von logischen Pegeln 1 bei den Set-Eingängen der Register S1 und S3 zu erzeugen. Dadurch wird ein logischer Pegel 1 bei den Q-Ausgängen der Register S1 und S3 erzeugt. Der logische Pegel 1 bei einem dieser "Q"-Ausgänge am NOR-Gatter 100 führt zu einem logisch "0" bei den UND-Gattern A1 bis A4, wodurch weitere Anforderungen unterbrochen werden. Ein logisch 0 oder niedriger Pegel wird von den -Ausgängen der Register S1 und S3 zu den UND-Gattern A5 bis A7 gesendet. Der Ausgang des UND-Gatters A6 bleibt auflogisch 0, wobei der -Ausgang von Register S1 niedrig ist. Nur die Anforderung bei Eingang 201 für BSM 21 wird im ersten Taktzyklus bestätigt. Sobald die Auswahl getroffen wurde, um die Daten von Prozessor 11 zu koppeln, wird das Register S1 über Draht 209 zurückgesetzt, so daß ein logischer Pegel 1 am -Ausgang des Registers S1 für das UND-Gatter A6 erzeugt wird, und die Anforderung bei Eingang 203 einen logischen Pegel 1 vom UND-Gatter A6 erzeugen kann. Der logische Pegel 1 beim Ausgang 207 von UND-Gatter A6 wählt die Daten von Prozessor 16 für das zugeordnete BSM im nächsten Taktzyklus aus. Nachdem der Anforderer bei Eingang 203 die Daten ausgewählt hat, wird das Register S3 durch den Rückkopplungspfad 210 vom UND-Gatter A6 zurückgesetzt, und der NOR-Ausgang von NOR-Gatter 100 geht nach oben. Wenn das NOR- Gatter nach oben geht, sind alle Register S1 bis S4 inaktiv, und jede mögliche Eingangsanforderung kann im nächsten vollen Zyklus bestätigt werden.
• Im Beispiel der Figuren 1 und 2 wurden zwei Taktzyklen benötigt, um zwei gleichzeitige Anforderungen für das gegebene Basisspeichermodul zu verarbeiten. Da Portanforderungen in jedem Zyklus erzeugt werden, sollte die Speicheranzahl der Eingangspuffer gleich groß wie die Zahl der Prozessoren sein. In Figur 1 beispielsweise werden vier Pufferstufen benötigt, um im Fall von vier Prozessoren, die mit einem gegebenen Basisspeichermodul zu kommunizieren versuchen, auszukommen. Die Daten werden über vier Taktzyklen gespeichert und sequentiert. Im vorgestellten Beispiel gab es nur vier Eingangsprozessoren, die mit vier Basisspeichermoduln gekoppelt wurden, während in einer bevorzugten Anwendung z.B. 32 Prozessoren vorhanden sein könnten, die mit 32 oder mehr Speichermoduln kommunizieren.
• Die in Figur 2 gezeigten Arbiter bestätigen Mehrfachanforderungen immer in Umlaufordnung von S1 bis S4, bis alle erledigt sind, d.h. im vorliegenden Fall hat die Anforderung bei Eingang 201 die höchste Priorität, die Anforderung bei Eingang 202 die zweithöchste, der Eingang bei 203 die dritthöchste und der Eingang bei 204 die niedrigste Priorität in diesem Arbitrierungszyklus.
• Während eines Taktzyklusses können vier Portanforderungen auf die vier BSM verteilt werden, und maximal vier BSM-Auswahlen können pro Taktzyklusintervall verarbeitet werden. Das Minimum wäre eine BSM-Auswahl pro Zyklus, wenn alle Portanforderungen für dasselbe BSM sind. Die Kopplung von mehr Prozessoren mit mehr Basisspeichermoduln, z.B. 32 Prozessoren mit 32 BSM, ist in Figur 3 dargestellt. In dieser Anordnung erzeugt jeder Prozessor 301-332 ein codiertes 5-Bit-Anforderungssignal für jeden Datenblock oder jedes Datenpaket zum BSM. Das Anforderungscodesignal mit dem zugeordneten Datenpaket wird über den zugeordneten Puffer sequentiert. Ein Decoder 301a-332a befindet sich am Ausgang jedes Eingangspuffers 301b-332b, um jedes codierte 5-Bit-Anforderungssignal des Prozessors zu decodieren und eine Anforderung mit logischem Pegel 1 über den Draht auf einer der 32 Ausgangsleitungen zum entsprechenden Arbiter zu senden. Der Decoder 301a z.B. decodiert den codierten Ausgang von Puffer 301b, der anzeigt, daß die Daten zum BSM 302f gesendet werden, und sendet einen logischen Pegel 1 auf Draht 400 oder eine Anforderung zum Arbiter 302c. Die Daten bei Puffer 301b werden anschließend über den Auswahlschalter 302d zum BSM 302f (über Puffer 302e) aktiviert. Die Arbiter 301c-332c sind wie in Figur 2 dargestellt, wobei 32 Eingänge und Ausgänge anstatt vier Ein- und Ausgänge vorhanden sind.

Claims (6)

1. Ein NxM-Schalter mit:

M-Ausgangsports;

N-Daten- und Anforderungseingängen, wobei jeder Anforderungseingang einem Dateneingang zugeordnet ist und anzeigt, zu welchem M-Ausgangsport das zugeordnete Datenpaket gesendet werden soll;

M-Arbiter (41-44) und Gattermittel (51-54), wobei jeder Arbiter und jedes Gattermittel zwischen den N-Daten- und Anforderungseingängen und einem anderen M-Ausgangsport gekoppelt ist;

wobei jeder Arbiter und jedes Gattermittel auf die Datenund Anforderungseingänge reagiert, um Daten gleichzeitig mit den angeforderten Ausgangsports zu gaten, wenn keine konkurrierenden Anforderungseingänge für denselben Ausgangsport vorhanden sind, sondern wenn konkurrierende Anforderungseingänge für denselben Ausgangsport vorhanden sind, um die zugeordneten konkurrierenden Datenpakete für den oder die zugeordneten Ausgangsport(s) zu speichern und zu sequentieren, während gleichzeitig nicht-konkurrierende Datenpakete direkt zu den anderen Ausgangsports gesendet werden, wobei das System dadurch gekennzeichnet ist, daß FIFO-Puffermittel (31-34), die zwischen jedem der N-Daten- und Anforderungseingänge sowie den Arbitern und Gattermitteln gekoppelt sind, die Datenpakete und Anforderungssignale jedes Taktzyklusses speichern und sequentieren, wobei das FIFO-Puffermittel mindestens N-Stufen hat.

2. Ein Schalter nach Anspruch 1, bei dem die M-Arbiter und die Gattermittel über eine Logik verfügen, die eine Prioritätssequenz hat, um das Gating der konkurrierenden Anforderungssignale aus den den Gattermitteln zu beginnen.

3. Ein Schalter nach einem der oben genannten Ansprüche, bei dem das Arbitermittel über eine Logik verfügt, um ein codiertes Signal zu den Gattermitteln zu senden, das den Anforderungseingang und das Gattermittel identifiziert, und direkt mit den FIFO-Puffermitteln gekoppelt ist und als Reaktion auf das codierte Signal vom Arbiter den Eingang zum zugeordneten Ausgangsport gatet.

4. Ein Schalter nach einem der oben genannten Ansprüche, bei dem die Arbiter (41-44) die konkurrierenden Daten zu dem/den zugeordneten Ausgangsport(s) auf Umlaufbasis sequentieren.

5. Ein Multiprozessorsystem, bei dem eine N-Vielzahl von Prozessoren (11-14) mit einer M-Vielzahl von Basisspeichermoduln (21-24) über einen in den zuvor genannten Ansprüchen vorgestellten Schalter zufällig gekoppelt wird, wobei

jedes Basisspeichermodul mit seinem eigenen Ausgangsport verbunden ist; jeder Prozessor mit seinem eigenen Eingangsport verbunden ist und hierfür bei Bedarf ein Datenpaket und ein Anforderungscodesignal sendet, das anzeigt, zu welchem Basisspeichermodul das Datenpaket gesendet werden soll;

wenn nur ein Datenpaket für ein bestimmtes Basisspeichermodul in einem Zyklus vorgesehen ist, und daher nur eine Anforderung zum entsprechenden Arbiter gesendet wird, veranlaßt der Arbiter das zugeordnete Gattermittel, das Datenpaket direkt mit seinem gekoppelten Basisspeichermodul zu gaten, und wenn mehr als eine Anforderung in einem bestimmten Zyklus für dasselbe Basisspeichermodul vorgesehen ist, und daher mehr als eine Anforderung beim entsprechenden Arbiter empfangen wird, sorgt der Arbiter dafür, daß die anderen Datenpakete zu dem zugeordneten Basisspeichermodul sequentiert werden.

6. Ein System nach Anspruch 5, das über ein zweites Puffermittel (61-64) zwischen jedem Gattermittel und dem zugeordneten Basisspeichermodul verfügt.