DE60308832T2

DE60308832T2 - Gemeinsame warteschlange für mehrere eingangströme

Info

Publication number: DE60308832T2
Application number: DE60308832T
Authority: DE
Inventors: Vishal Anand; K. Rama ALAMPALLY
Original assignee: Koninklijke Philips Electronics NV
Current assignee: NXP BV
Priority date: 2002-02-27
Filing date: 2003-02-25
Publication date: 2007-08-09
Anticipated expiration: 2023-02-26
Also published as: EP1481317A2; DE60308832D1; CN1639680A; TWI280506B; US20030163618A1; AU2003206070A8; ATE341787T1; WO2003073296A2; AU2003206070A1; EP1481317B1; CN100382009C; TW200409032A; WO2003073296A3; JP2005519371A

Description

Diese Erfindung betrifft das Gebiet der Computer- und Kommunikationssysteme und insbesondere ein System, das mehrere Eingangsströme empfängt, die zu einem gemeinsamen Ausgangsport geleitet werden.
Systeme mit mehreren Eingängen und einem gemeinsamen Ausgang werden auf diesem technischen Gebiet häufig verwendet. Zum Beispiel können mehrere Hosts Daten an einen gemeinsamen Server übermitteln; mehrere Prozessoren können auf eine gemeinsame Speichervorrichtung zugreifen; mehrere Datenströme können zu einem gemeinsamen Übertragungsmedium geleitet werden, und so weiter. Im Allgemeinen ist der Eingang in das Mehrfacheingangssystem durch burstartige Aktivitäten aus einem oder mehreren Eingangsströmen gekennzeichnet. Während dieser Aktivitäten-Bursts übersteigt die Ankunftsrate der Eingangsdaten im Allgemeinen die zulässige Abgangsrate der Daten zu einem nachfolgenden Empfangssystem, und es muss eine Puffer erfolgen, um Datenverluste zu vermeiden.
Herkömmlicherweise wird einer von zwei Systemtypen verwendet, um das Routen mehrerer Eingangsströme zu einem gemeinsamen Ausgang zu verwalten, und zwar je nachdem, ob die Designpriorität maximale Speicherauslastungseffizienz oder maximale Leistung ist.
Bei einer auf Speichereffizienz ausgelegten Ausführungsform ist ein gemeinsamer Puffer vorhanden, um die Daten von den Eingangsströmen in eine Warteschlange einzureihen, und jeder Prozess, der einen Eingangsstrom bereitstellt, steuert den Zugriff auf diesen gemeinsamen Puffer entsprechend einem vorgegebenen Steuerprotokoll. Daten werden aus diesem gemeinsamen Puffer entladen, um die gemeinsame Ausgabe zu erzeugen. Weil ein gemeinsamer Puffer verwendet wird, um den Fluss aus den verschiedenen Eingangsströmen entgegenzunehmen, kann die Größe des Puffers für eine bestimmte Ankunfts-Gesamtrate optimiert werden. Das heißt, weil es überaus unwahrscheinlich ist, dass alle Eingangsströme gleichzeitig aktiv sind, ist der gemeinsame Puffer wesentlich kleiner bemessen als die Größe, die benötigt wird, um den maximalen Fluss von allen Strömen gleichzeitig aufzunehmen. Die Leistung einer solchen Ausführungsform hängt jedoch von dem leistungsschwächsten Prozess ab, der einen Eingangsstrom bereitstellt, weil ein leistungsschwacher Prozess den gesamten gemeinsamen Puffer in Anspruch nehmen kann, während alle anderen Prozesse auf den Zugang zu dem gemeinsamen Puffer warten.
Ein Warteschlangeneinreihungssystem dieses Typs mit mehreren Eingängen ist in US-Patent Nr. 5,233,603 offenbart. Das System enthält einen einzelnen Pufferspeicher, der mit mehreren Eingangs- und Ausgangsleitungen verbunden ist. Ein Multiplexer und ein Demultiplexer verbinden die Eingangs- und Ausgangsleitungen mit dem Speicher. Es sind verschiedene Speicherbereiche für verschiedene Eingänge und Ausgänge vorhanden. Bei einer anderen Ausführungsform offenbart dieses Patent die Verwendung verschiedener Speicherelemente, die jeweils mit einer anderen vorgegebenen Ausgangsleitung verbunden sind. Die Eingangsleitungen greifen über einen gemeinsamen Bus auf diese Speicherelemente zu. Bei einer weiteren Ausführungsform wird ein separater Pufferspeicher für jede Kombination aus einer Eingangsleitung und einer Ausgangsleitung verwendet.
GB-A-2349296 offenbart einen Netzwerkschalter mit einem Pufferungssystem mit mehreren Eingängen und einem einzelnen Ausgang. Für jeden Eingang gibt es einen zuvor festgelegten Pufferspeicher.
Um eine Unabhängigkeit unter den Prozessen zu wahren, die die mehreren Eingänge bereitstellen, arbeiten herkömmliche Hochleistungssysteme mit mehreren Eingängen in der Regel mit mehreren Eingangspuffern, wie durch das System 100 von 1 veranschaulicht. Jeder Puffer 110 stellt eine Warteschlange zum Empfangen von Daten von seinem entsprechenden Eingangsstrom 101 bereit. In dem Beispiel von 1 gibt ein Empfangssystem einen "Unload(n)"-Befehl aus, um das nächste verfügbare Datenelement aus der n-ten Warteschlange auszuwählen, und dieses ausgewählte Datenelement Q_n wird anschließend an das Empfangssystem übermittelt. Die Auswahl des konkreten Eingangsdatenstroms n erfolgt in der Regel auf der Grundlage eines Priorisierungsschemas. Das System 100 enthält in der Regel ein (nicht gezeigtes) Mittel zum Informieren des Empfangssystems, dass Daten aus einem Eingangsstrom zur Verfügung stehen, und das Empfangssystem trifft seine Auswahl unter den verfügbaren Strömen auf der Grundlage einer Priorität, die dem Strom zugeordnet ist. Es werden häufig auch andere Protokolle zum Steuern des Datenstroms von mehreren Eingangsströmen verwendet, einschließlich beispielsweise Übertragungssteuerung in dem System 100 und eine Kombination aus Übertragungs- und Empfangssteuerung durch das System 100 bzw. das Empfangssystem. In gleicher Weise kann die Auswahl des konkreten Eingangsstroms zusätzlich zu dem oben angesprochenen Prioritätsschema oder anstelle des angesprochenen Prioritätsschemas ein beliebiges aus einer Vielzahl von Schemata enthalten, einschließlich einer First-in-First-out-Auswahl, einer Round-Robin-Auswahl und so weiter.
Zu den Designentscheidungen, die bei einem Mehrfacheingangssystem zu treffen sind, gehört auch die Wahl der Größe D der Eingangswarteschlangen. Auf der Grundlage der geschätzten Eingangs- und Ausgangsdatenflussraten kann eine Warteschlangengröße D bestimmt werden, um die Wahrscheinlichkeit eines Überlaufens der Warteschlange zu minimieren. Zum besseren Verständnis sind die Warteschlangen, die jedem Eingangsstrom 101 des Systems 100 zugeordnet sind, in ähnlicher Größe dargestellt. Wenn man weiß, dass ein bestimmter Eingangsstrom eine Datenflussrate hat, die sich wesentlich von den anderen Eingangsströmen unterscheidet, so kann ihm eine kleinere oder größere Warteschlangengröße zugewiesen werden. Wie veranschaulicht, ist das System 100 so konfiguriert, dass es einen maximalen Burst aus D Datenelementen von einem der Eingangsströme auf der Grundlage der erwarteten Verarbeitungsgeschwindigkeit des anschließenden Empfangssystems ermöglicht. Einreihungstheorie-Techniken zur Bestimmung eines optimales Wertes D anhand einer erwarteten Verteilung von Ankünften von Datenelementen bei einem Eingangsstrom und einer erwarteten Verteilung von Entnahmen der Datenelemente durch das nachfolgende Empfangssystem sind auf diesem technischen Gebiet allgemein bekannt.
Weil die Warteschlangengröße D auf geschätzten Ankunftsraten von Datenelementen aus jedem Eingangsstrom beruht, ist jede Warteschlange so bemessen, dass sie eine Schlimmstfall-Schätzung von Ankünften verarbeiten kann. Obgleich ein bestimmter Eingangsstrom häufig in die Nähe einer vollständigen Befüllung seiner Schlange kommen kann, ist die Wahrscheinlichkeit, dass alle Eingangsströme gleichzeitig in die Nähe einer vollständigen Befüllung aller Schlangen kommen, im Allgemeinen überaus gering. Oder anders betrachtet: Die Anzahl ungenutzter Speicherplätze unter allen Schlangen ist zu jeder Zeit im Allgemeinen überaus hoch, so dass die Speicherausnutzungseffizienz des herkömmlichen Systems 100 mit mehreren Warteschlangen und mehreren Eingängen überaus gering ist.
Es ist eine Aufgabe dieser Erfindung, eine Vorrichtung mit mehreren Eingängen und ein Verfahren bereitzustellen, welche die Speicherausnutzungseffizienz maximieren. Es ist eine weitere Aufgabe dieser Erfindung, eine Vorrichtung mit mehreren Ein gängen und ein Verfahren bereitzustellen, welche die Speicherausnutzungseffizienz maximieren, während gleichzeitig eine hohe Leistung aufrechterhalten bleibt. Es ist eine weitere Aufgabe dieser Erfindung, eine Vorrichtung mit mehreren Eingängen und hoher Leistung bereitzustellen, welche die Fläche minimiert, die durch Speichervorrichtungen beansprucht wird.
Diese und weitere Aufgaben werden durch Bereitstellen eines Warteschlangeneinreihungssystems mit mehreren Eingängen nach Anspruch 1 erreicht. Um ein unabhängig gesteuertes Entladen der einzelnen Datenelemente aus dem gemeinsamen Puffer mit mehreren Eingängen zu ermöglichen, verwaltet das System eine Abbildung der Speicherplätze des Puffers, die jedem Datenelement in jedem Eingangsstrom zugewiesen werden. Um den Speicher und den Aufwand zu minimieren, der mit der Verwaltung einer Abbildung jedes Datenelements verbunden ist, werden die Speicherplätze, die jedem Eingangsstrom zugeordnet sind, in einer sequenziellen First-in-First-out-Schlange verwaltet. Wenn ein nachfolgendes Empfangsgerät bestätigt, dass es bereit ist, ein Datenelement aus einem bestimmten Eingangsstrom zu empfangen, so wird die Identifikation des zugewiesenen Speicherplatzes aus der Warteschlange des Eingangsstromes entfernt, und das Datenelement, das sich in dem zugewiesenen Speicher in dem gemeinsamen Puffer befindet, wird an das Empfangsgerät übermittelt.
Die Erfindung wird eingehender und beispielhaft unter Bezug auf die begleitenden Zeichnungen erläutert, in denen Folgendes zu sehen ist:
1 veranschaulicht ein beispielhaftes Blockschaubild eines zum Stand der Technik gehörenden Warteschlangensystems mit mehreren Eingängen.
2 veranschaulicht ein beispielhaftes Blockschaubild eines Warteschlangensystems mit mehreren Eingängen gemäß dieser Erfindung.
3 veranschaulicht ein beispielhaftes Blockschaubild eines Warteschlangensystems mit mehreren Eingängen.
2 veranschaulicht ein beispielhaftes Blockschaubild eines Warteschlangensystems 200 mit mehreren Eingängen gemäß dieser Erfindung. Das System 200 enthält einen Doppelport-Speicher 220, wobei Schreibvorgänge in den Speicher 220 durch eine Zuordnungs- und Ausgleichsvorrichtung 240 (im Weiteren eine "Zuordnungsvorrichtung 240") gesteuert werden und Lesevorgänge aus dem Speicher 220 durch eine Abbildungs- und Sequenzierungsvorrichtung 250 (im Weiteren eine "Abbildungsvorrichtung 250") gesteuert werden. Die Schreib- und Lesevorgänge in den bzw. aus dem Speicher 220 sind symbolisch durch einen Schalter 210 bzw. einen Schalter 260 dargestellt.
Wie in 2 veranschaulicht, enthält der Speicher 220 P adressierbare Speicherelemente, und jedes Speicherelement hat eine ausreichende Breite W, um ein Datenelement von einem der Eingangsströme 101 aufzunehmen. Unter Verwendung herkömmlicher Einreihungstheorie-Techniken kann die Anzahl P an Speicherelementen, die erforderlich sind, um einen bestimmten Vertrauensbereich bezüglich des Vermeidens eines Überlaufens des Speichers 220 zu gewährleisten, auf der Grundlage der erwarteten Eingangs- und Ausgangsdatenflussraten, wie oben im Zusammenhang mit dem zum Stand der Technik gehörenden System 100 von 1 besprochen, bestimmt werden. Vorzugsweise ist der Parameter P im System 200 wenigstens so groß wie der Parameter D im System 100. Es ist jedoch zu beachten, dass das System 100 insgesamt N·D Speicherelemente der Breite W enthält, wohingegen der Speicher 220 insgesamt P Speicherelemente der Breite W enthält.
Die Zuordnungsvorrichtung 240 ist dafür konfiguriert, die Position eines momentan ungenutzten Speicherelements in dem Speicher 220 anzugeben, wohin das nächste Datenelement aus den Eingangsströmen 101 geleitet wird, wie durch den Ausgangsschalter Sb in dem Schalter 210 angedeutet. Wie durch die Strichlinien zwischen den Eingangsströmen 101 und der Zuordnungsvorrichtung 240 angedeutet, ist die Zuordnungsvorrichtung 240 dafür konfiguriert, jedes Mal eine Miteilung zu empfangen, wenn ein Eingangsstrom 101 ein zu übertragendes neues Datenelement hat. Bei einer bevorzugten Ausführungsform enthält die Zuordnungsvorrichtung 240 eine Ausgleichslogik für den Fall, dass zwei oder mehr Eingangsströme 101 gleichzeitig Daten zu übertragen haben. Bei einer einfachen Ausführungsform kann beispielsweise den Eingangsports zum Schalter 210 eine sequenziell geordnete Priorität zugewiesen werden, wobei der erste Port die höchste Priorität hat, der zweite Port eine geringere Priorität hat, und so weiter. Jeder Eingangsstrom M1, M2,..., MN wird je nach seiner Priorität physikalisch mit dem entsprechenden Port verbunden. In einem solchen Beispiel wählt die Zuordnungsvorrichtung 240 über den Eingangsschalter Sa lediglich den Port mit der kleinsten Nummer aus, der ein zu übertragendes Datenelement hat. Auf diesem technischen Gebiet sind auch andere Prioritätsschemata üblich, einschließlich einer dynamischen Priorisierung auf der Grundlage des Inhalts jedes Datenelements oder auf der Grundlage eines bisherigen Übertragungsverlaufs von einem oder mehreren der Eingangsströme 101, und andere. Alternativ kann ein einfaches Round- Robin-Eingangsauswahlschema verwendet werden, wobei die Zuordnungsvorrichtung 240 der Reihe nach jeden Eingangsstrom 101 nach neuen Daten abtastet und die neuen Daten in der Abtastungsreihenfolge zu dem nächsten verfügbaren ungenutzten Speicherelement im Speicher 220 leitet. Dem Durchschnittsfachmann ist klar, dass das konkrete Schema, das verwendet wird, um mögliche Konflikte zwischen der Vielzahl verschiedener Eingangsströme zu lösen, von den Prinzipien dieser Erfindung unabhängig ist.
Es ist zu beachten, dass – wie weiter unten noch besprochen wird – die Zuordnungsvorrichtung 240 dafür konfiguriert ist, das Entfernen von Datenelementen aus den einzelnen Speicherelementen festzustellen. Wenn ein Datenelement entfernt wird, so steht das Speicherelement, in dem sich dieses Datenelement befand, nunmehr als ein momentan ungenutztes Speicherelement zur Verfügung, um neue Datenelemente zu empfangen. Zu einem Überlaufen des Speichers 220 kommt es nur, wenn alle P Speicherelemente mit Datenelementen befüllt sind, die noch nicht entfernt wurden.
Weil jeder Eingangsstrom auf jedes momentan ungenutzte Speicherelement im Speicher 220 zugreifen kann, weist das System 200 die Speicherauslastungseffizienz des Systems mit einem gemeinsamen Puffer auf, wie es unter "Allgemeiner Stand der Technik" besprochen wurde. Weil aber die Zuordnungsvorrichtung 240 dafür konfiguriert ist, jedes verfügbare Speicherelement nach Bedarf zuzuordnen, ist das System 200 nicht abhängig von einer Steuerung des Speichers 220 durch einen oder mehrere der Prozesse, welche die Eingangsströme bereitstellen.
Weil des Weiteren die Zuordnungs- und Ausgleichsfunktionen der Zuordnungsvorrichtung 240 und insbesondere die Interaktionen der Zuordnungsvorrichtung mit dem Schalter 210 im Wesentlichen unabhängig von den Prozessen sind, welche die Eingangsströme 101 bereitstellen, können Modifikationen an der Zuordnungsvorrichtung 240 und dem Schalter 210 vorgenommen werden, ohne dass Änderungen an den Prozessen notwendig sind, welche die Eingangsströme 101 bereitstellen. Um zum Beispiel die Leistung zu erhöhen und die Wahrscheinlichkeit von Konflikten unter den Eingangsströmen 101 zu verringern, kann der Schalter 210 dafür konfiguriert sein, das gleichzeitige Routen mehrerer Datenelemente zu mehreren Speicherelementen in dem Speicher 220 zu ermöglichen. Das heißt, der Schalter Sa ist in 2 als ein N-zu-1-Schalter veranschaulicht, und der Schalter 2b ist als ein 1-zu-P-Schalter veranschaulicht. Alternativ können die Schalter Sa und Sb, um bis zu k gleichzeitige Übertragungen zu unterstützen, ein N-zu-k-Schalter bzw. ein k-zu-P-Schalter sein. Eine solche Änderung ist jedoch für die Eingangsströme M1 ... MN insofern "transparent", als die Prozesse, welche die Datenelemente bereitstellen, nicht modifiziert zu werden brauchen, um mit einem N-zu-1-Schalter kompatibel zu sein, im Gegensatz zu einem N-zu-k-Schalter.
Die Abbildungsvorrichtung 250 ist so konfiguriert, dass sie gewährleistet, dass Datenelemente in einer zweckmäßigen Reihenfolge aus dem Speicher 220 entladen bzw. entfernt werden. Wenn die Reihenfolge von Ausgangsdatenelementen Qn der gleichen Reihenfolge entsprechen soll, in der die Datenelemente empfangen werden, so braucht die Abbildungsvorrichtung 250 lediglich mit der gleichen Reihenfolge zu arbeiten, die zum Steuern des Schalters Sb im Schalter 210 verwendet wird. Das heißt zum Beispiel, wenn der Schalter Sb Speicherelemente im Speicher 220 der Reihe nach auswählt, so würde die Abbildungsvorrichtung 250 ebenfalls dafür konfiguriert sein, die Speicherelemente im Speicher 220 der Reihe nach zur Übermittlung an ein nachfolgendes Empfangssystem auszuwählen. In der Regel ist das System 200 jedoch so konfiguriert, dass es dem nachfolgenden Empfangssystem möglich ist, Datenelemente in einer mehr oder weniger unabhängigen Weise zu empfangen.
In einer typischen Ausführungsform, wie oben unter "Allgemeiner Stand der Technik" besprochen, ruft das Empfangssystem Datenelemente in einer Reihenfolge auf, die sich von der Reihenfolge unterscheiden kann, in der die Datenelemente von dem Warteschlangeneinreihungssystem 200 mit mehreren Eingängen empfangen werden. Bei einer bevorzugten Ausführungsform ist das System 200 so konfiguriert, dass es dem Empfangssystem möglich ist, den Eingangsstrom n zu benennen, von dem das nächste Datenelement gesendet werden soll. Auf diese Weise kann beispielsweise ein Prozess an einem Eingangsstrom n eine Anforderung einleiten, m Datenelemente an das Empfangssystem zu senden, und das Empfangssystem sendet anschließend m "unload(n)"-Befehle an das Warteschlangeneinreihungssystem 200, um diese m Datenelemente zu empfangen, und zwar unabhängig von der Ankunft anderer Datenelemente im System 200 von den anderen Eingangsströmen 101. Das heißt, in Bezug auf jeden Eingangsstrom werden die Datenelemente dem Empfangssystem der Reihe nach zur Verfügung gestellt, aber das Empfangssystem kann die Datenelemente von ausgewählten Eingangsströmen unabhängig von der Reihenfolge der Ankunft von Datenelementen von anderen Eingangsströmen aufrufen.
Um es dem Empfangssystem zu ermöglichen, eine Folge von Datenelementen von einem ausgewählten Eingangsstrom anzufordern, übermittelt die Zuordnungsvorrichtung 240 die Zuordnung jedes Speicherelementplatzes p zu jedem Eingangsstrom n als ein Stromelement-Paar (n, p) an die Abbildungsvorrichtung 250. Die Abbildungsvorrichtung 250 führt auf diese Weise eine Liste mit jedem Speicherelementplatz-Indikator p_n, der der Reihe nach einem jeden ankommenden Datenelement von jedem Eingangsstrom n zugewiesen wird. Wenn das Empfangssystem das "nächste" Datenelement von einem bestimmten Eingangsstrom n anfordert, so extrahiert die Abbildungsvorrichtung 250 den nächsten Platz-Indikator p_n aus der Liste, die dem Eingangsstrom n zugewiesen ist, und verwendet diesen Platz-Indikator p_n dafür, den Inhalt des Speicherelements p als die Ausgabe Qn über den Schalter 260 zu übermitteln. Dieser Platz-Indikator p_n wird aus der Liste, die dem Eingangsstrom n zugewiesen ist, entfernt, und die Zuordnungsvorrichtung 240 nimmt daraufhin das Speicherelement p als einen momentan ungenutzten Speicherplatz auf.
3 veranschaulicht ein beispielhaftes Blockschaubild eines Mehrfacheingangs-Warteschlangeneinreihungssystems 300 mit einer Mehrfachwarteschlangenspeicherzuordnungskarte 250 gemäß dieser Erfindung, wie es sich zur Verwendung als eine Abbildungsvorrichtung 250 in dem System 200 von 2 eignen würde. Vor dem Hintergrund dieser Offenbarung fallen dem Durchschnittsfachmann noch weitere Ausführungsformen einer Abbildungsvorrichtung 250 ein.
In der beispielhaften Ausführungsform von 3 enthält die Abbildungsvorrichtung 250 mehrere First-in-First-out (FIFO)-Warteschlangen 355, wobei jede Warteschlange 355 einem entsprechenden Eingangsstrom 101 zu dem Mehrfacheingangs-Warteschlangeneinreihungssystem 300 zugeordnet ist. Wenn die Zuordnungsvorrichtung 240 ein Speicherelement p zu einem Eingangsstrom n zuordnet, so wird die Adresse dieses Speicherelements p in der Warteschlange gespeichert, die dem Eingangsstrom n entspricht, wobei der Index n dafür verwendet wird, die Warteschlange 355 auszuwählen, die dem Eingangsstrom n entspricht. Mit jedem neuen Datenelement, das von einem Eingangsstrom empfangen wird, wird die Adresse p, unter der das Datenelement gespeichert wird, in der Warteschlange, die dem Eingangsstrom entspricht, der Reihenfolge nach gespeichert.
Jede Warteschlange 355 in der beispielhaften Abbildungsvorrichtung 250 von 3 ist mit einer Warteschlangenlänge D veranschaulicht, die den in 1 veranschaulichten Warteschlangenlängen nach dem Stand der Technik entspricht. Es ist jedoch zu beachten, dass die Breite der Warteschlangen 110 von 1 gleich W ist, so dass die Gesamtlänge jeder Warteschlange 110 gleich D·W ist. Weil jede Warteschlange 355 von 3 dafür konfiguriert ist, eine Adresse zu den P Speicherelementen zu speichern, ist die Gesamtgröße jeder Warteschlange 355 gleich D·log₂P. In einer typischen Ausführungs form ist die Breite der Adresse log₂P im Allgemeinen wesentlich kleiner als die Breite eines Datenelements. Wenn beispielsweise die Datenelemente 32 Bit breit sind und der Puffer 220 dafür konfiguriert ist, 1024 Datenelemente zu speichern (log₂(1024) = 10), so haben die Warteschlangen 355 von 3 weniger als ein Drittel (10/32) der Größe der Puffer 110 von 1.
Wenn das Empfangssystem über einen "Unload(n)"-Befehl das nächste Datenelement von einem ausgewählten Eingangsstrom anfordert, so wählt eine Multiplex- und Wählvorrichtung 350 die Warteschlange aus, die dem gewählten Eingangsstrom n entspricht, und der nächste verfügbare Index p_n wird aus der gewählten Warteschlange 355 entfernt. Der Index p_n dient dem Auswählen des entsprechenden Speicherelements p über den Schalter/Multiplexer 260, um die Ausgabe Qn bereitzustellen, die dem Unload(n)-Befehl von dem Empfangssystem entspricht. Nachdem das Datenelement in dem Speicherelement p zur Ausgabe ausgewählt ist, enthält die Zuordnungsvorrichtung 240 das Speicherelement p als ein momentan ungenutztes Speicherelement, wodurch es nach Bedarf neu ankommenden Datenelementen zugewiesen werden kann.
In 3 ist außerdem eine beispielhafte Ausführungsform eines Schalters 210 mit mehreren Eingängen und mehreren Ausgängen veranschaulicht, der dafür konfiguriert ist, ein Datenelement von einem Eingangsstrom 101 zu einem ausgewählten Speicherelement p in einem Speicher 220 zu leiten. Der beispielhafte Schalter 210 enthält eine Multiplex- und Wählvorrichtung 310, die jedem Speicherelement des Speichers 220 entspricht und die über einen select(n_P)-Befehl von der Zuordnungsvorrichtung 240 aktiviert wird. In dieser beispielhaften Ausführungsform ist jede Multiplex- und Wählvorrichtung 310, die jedem Speicherelement zugeordnet ist, dafür konfiguriert, einen select(n_P)-Befehl zu empfangen, wobei n_P den ausgewählten Eingangsstrom identifiziert, der dem Speicherelement zugewiesen wurde. Auf diese Weise wird das Datenelement von dem n-ten Eingangsstrom zu dem p-ten Speicherelement geleitet. Es ist zu beachten, dass diese beispielhafte Ausführungsform die Speicherung von Datenelementen von mehreren gleichzeitigen Eingangsströmen ermöglicht. Das heißt zum Beispiel, wenn die Eingangsströme 1, 3 und 7 momentan versuchen, Datenelemente zu übertragen, und die Speicherelemente 2, 8 und 13 (und eventuell noch weitere) momentan ungenutzt sind, so gibt die Zuordnungsvorrichtung 240 bei einer bevorzugten Ausführungsform einen select(1)-, einen select(3)- und einen select(7)-Befehl an die Multiplexer 310 aus, die den Speicherelementen 2, 8 bzw. 13 zugeordnet sind, wodurch gleichzeitig der Eingangsstrom 1 zu dem Speicherelement 2 geleitet wird, der Eingangsstrom 3 zu dem Speicherelement 8 geleitet wird und der Eingangsstrom 7 zu dem Speicherelement 13 geleitet wird.
Vor dem Hintergrund dieser Offenbarung fallen dem Durchschnittsfachmann noch andere Ausführungsformen zum Routen von Datenelementen von mehreren Eingangsströmen zu zugewiesenen Speicherplätzen ein. Zum Beispiel veranschaulicht 3 einen N-zu-1-Multiplexer 310, der jedem Speicherelement des Puffers 220 zugeordnet ist, um eine Auswahl unter N Eingangsströmen zu treffen. Bei einer alternativen Ausführungsform kann eine 1-zu-P-Wählvorrichtung jedem Eingangsstrom 101 zugeordnet sein, um jeden Eingangsstrom zu einem ausgewählten Speicherelement des Puffers 220 zu leiten.

Claims

Warteschlangeneinreihungssystem (200) mit mehreren Eingängen, umfassend: Eingänge (101) zum Empfangen mehrerer Eingangsströme (M1-MN), einen Puffer (220), der mehrere Speicherelemente umfasst, eine Zuordnungsvorrichtung (240), die dafür konfiguriert ist, Speicherelemente der mehreren Speicherelemente zu jeweiligen ausgewählten Eingangsströmen von mehreren Eingangsströmen (M1-MN) zuzuordnen, um Datenelemente von den ausgewählten Eingangsströmen zu speichern, und eine Abbildungsvorrichtung (250), die dafür konfiguriert ist, eine Anforderung (Unload(n)) für eine Ausgabe zu empfangen, die dem ausgewählten Eingangsstrom entspricht, eine Adresse (d_n), die dem Speicherelement zugeordnet ist, auf der Grundlage der Anforderung für den gewählten Eingangsstrom zu bestimmen, und das Datenelement von dem Speicherelement auf der Grundlage der Adresse, die dem Speicherelement zugeordnet ist, als eine Ausgabe (Qn) bereitzustellen, dadurch gekennzeichnet, dass das Warteschlangeneinreihungssystem Folgendes umfasst: – einen Schalter (210), der zwischen den Eingängen und den Speicherelementen angeschlossen ist und einen Steuerungseingang hat, der mit der Zuordnungsvorrichtung (240) verbunden ist, wobei der Schalter dafür konfiguriert ist, die Datenelemente gleichzeitig von mehreren der gewählten Eingangsströme zu mehreren der zugewiesenen Speicherelemente zu leiten.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 1, das des Weiteren einen zweiten Schalter (260) enthält, der mit der Abbildungsvorrichtung (250) wirkverbunden ist, wobei der zweite Schalter dafür konfiguriert ist, das Datenelement von dem Speicherelement zu dem Ausgang zu leiten.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 1, wobei die Zuordnungsvorrichtung (240) des Weiteren dafür konfiguriert ist, das Speicherelement auf der Grundlage einer von dem ausgewählten Eingangsstrom ergangenen Anforderung nach einer Zuordnung zuzuordnen.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 3, wobei die Zuordnungsvorrichtung (240) des Weiteren dafür konfiguriert ist: Zuordnungsanforderungen von anderen Eingangsströmen der mehreren Eingangsströme (M1-MN) zu erhalten, eine relative Priorität der Zuordnungsanforderungen von den anderen Eingangsströmen und der Anforderung von dem ausgewählten Eingangsstrom zu bestimmen, und den ausgewählten Eingangsstrom auf der Grundlage der relativen Priorität zu identifizieren.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 3, wobei die Zuordnungsvorrichtung (240) des Weiteren dafür konfiguriert ist: Zuordnungsanforderungen von anderen Eingangsströmen der mehreren Eingangsströme (M1-MN) zu erhalten, und weitere Speicherelemente der mehreren Speicherelemente zum Speichern weiterer Datenelemente von den weiteren Eingangsströmen zuzuordnen.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 5, wobei die Zuordnungsvorrichtung (240) dafür konfiguriert ist, die weiteren Speicherelemente gleichzeitig mit der Zuordnung des Speicherelements zum Speichern des Datenelements von dem ausgewählten Eingangsstrom zuzuordnen.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 5, wobei die Abbildungsvorrichtung (250) dafür konfigurier ist: Anforderungen nach Ausgaben entsprechend den weiteren Eingangsströmen entgegenzunehmen, Adressen, die den weiteren Speicherelementen zugeordnet sind, auf der Grundlage der Anforderung nach den weiteren Eingangsströmen zu bestimmen, und die weiteren Datenelemente von dem weiteren Speicherelement als Ausgaben von dem Warteschlangeneinreihungssystem (200) mit mehreren Eingängen auf der Grundlage der Adressen, die dem weiteren Speicherelement zugeordnet sind, bereitzustellen.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 1, wobei der Schalter (210) Folgendes umfasst: mehrere Eingangs-Multiplexer (310), wobei jeder Eingangs-Multiplexer mit einem Speicherelement der mehreren Speicherelemente (220) verbunden ist.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 8, wobei das Puffersystem (300) des Weiteren Folgendes enthält: eine Abbildungsvorrichtung (250), die mit der Zuordnungsvorrichtung (240) wirkverbunden ist, wobei die Abbildungsvorrichtung Folgendes enthält: einen Speicher (355), der dafür konfiguriert ist, Informationen zu speichern, die den Zuordnungsbefehlen entsprechen, und einen Multiplexer (350), der mit dem Speicher (355) wirkverbunden ist, wobei der Multiplexer dafür konfiguriert ist, auf die Informationen zuzugreifen, die den Zuordnungsbefehlen entsprechen, und dadurch eine Identifizierung des einen oder der mehreren Speicherelemente vorzunehmen, die einem ausgewählten Eingangsstrom der mehreren Eingangsströme (M1-MN) entsprechen, und einen Ausgabe-Multiplexer (260), der mit den mehreren Speicherelementen (220) und mit der Abbildungsvorrichtung (250) wirkverbunden ist, wobei der Ausgabe-Multiplexer dafür konfiguriert ist, ein ausgewähltes Speicherelement der mehreren Speicherelemente (220) auf der Grundlage der Identifizierung des einen oder der mehreren Speicherelemente, die dem ausgewählten Eingangsstrom entsprechen, mit einem Ausgang des Puffersystems (300) zu verbinden.
Warteschlangeneinreihungssystem (200) mit mehreren Eingängen nach Anspruch 9, wobei der Speicher (355) der Abbildungsvorrichtung (250) mehrere Warteschlangen enthält, wobei jede Warteschlange der mehreren Warteschlangen jedem Eingangsstrom der mehreren Eingangsströme (M1-MN) entspricht.
Verfahren zum Puffern von Datenelementen von mehreren Eingangsströmen (M1-MN), das Folgendes enthält: Empfangen einer Eingangsbenachrichtigung von einem oder mehreren Eingangsströmen der mehreren Eingangsströme (M1-MN), Zuordnen (240) ausgewählter Speicherelemente von mehreren Speicherelementen (220) zu einem jeweiligen Eingangsstrom des einen oder der mehreren Eingangsströme, Konfigurieren eines Schalters (210) dergestalt, dass ein Routen von empfangenen Datenelementen von den Eingangsströmen zu den zugeordneten ausgewählten Speicherelementen möglich ist, Speichern (220) der empfangenen Datenelemente von dem ausgewählten Eingangsstrom in den ausgewählten Speicherelementen, Speichern (250) einer Identifizierung der ausgewählten Speicherelemente, die den ausgewählten Eingangsströmen entsprechen, Empfangen einer Entlade-Anforderung (Unload(n)), die einen identifizierten der ausgewählten Eingangsströme (n) identifiziert, und Bereitstellen des empfangenen Datenelements von dem ausgewählten Speicherelement, das dem identifizierten der Eingangsströme zugeordnet ist, auf der Grundlage einer Identifikation (d_n) des ausgewählten Speicherelements, das dem identifizieren der Eingangsströme (n) entspricht, dadurch gekennzeichnet, dass der Schalter (210) dafür konfiguriert ist, empfangene Datenelemente von den Eingangsströmen gleichzeitig zu den mehreren Speicherelementen zu leiten.
Verfahren nach Anspruch 11, das des Weiteren Folgendes enthält: Zuordnen mehrerer ausgewählter Speicherelemente der mehreren Speicherelemente (220) zu mehreren ausgewählten Eingangsströmen des einen oder der mehreren Eingangsströme, Speichern eines empfangenen Datenelements von jedem der mehreren ausgewählten Eingangsströme in einem entsprechenden der mehreren ausgewählten Speicherelemente, und Speichern einer Identifikation jedes der mehreren ausgewählten Speicherelemente, die jedem der mehreren ausgewählten Eingangsströme entsprechen.
Verfahren nach Anspruch 11, wobei: das Speichern (250) der Identifikation des ausgewählten Speicherelements Folgendes enthält: Anordnen der Identifikation in einer First-in-First-out-Schlange (355), die dem ausgewählten Eingangsstrom zugeordnet ist, und das Bereitstellen des empfangenen Datenelements Folgendes enthält: Entfernen der Identifikation aus der First-in-First-out-Schlange, die dem ausgewählten Eingangsstrom zugeordnet ist.
Verfahren nach Anspruch 11, wobei: jedes Speicherelement der mehreren Speicherelemente (220) dynamisch als momentan genutzt und momentan ungenutzt klassifizierbar ist, das Zuordnen des ausgewählten Speicherelements Folgendes enthält: Identifizieren eines der mehreren Speicherelemente (220), das als momentan ungenutzt klassifiziert ist, als das ausgewählte Speicherelement, und Klassifizieren des ausgewählten Speicherelements als momentan genutzt, und das Bereitstellen des empfangenen Datenelements Folgendes enthält: Klassifizieren des ausgewählten Speicherelements als momentan ungenutzt.