-
BEREICH DER ERFINDUNG
-
Die
vorliegende Erfindung bezieht sich auf eine integrierte Schaltung
mit einer Anzahl Verarbeitungsmodule und einem Netzwerk, vorgesehen
zur Kopplung der Verarbeitungsmodule, und auf ein Verfahren zur Zeitlagenzuordnung
in einer derartigen integrierten Schaltung, und auf ein Datenverarbeitungssystem.
-
HINTERGRUND DER ERFINDUNG
-
Systeme
auf Silizium werden immer komplexer, und zwar wegen des immer wachsenden
Bedürfnisses
nach Implementierung neuer Merkmale und Verbesserungen bestehender
Funktionen. Dies wird dadurch ermöglicht, dass die Dichte, mit
der Schaltungselemente auf einer integrierten Schaltung integriert
werden können,
immer größer wird.
Gleichzeitig nimmt die Taktgeschwindigkeit, mit der Schaltungsanordnungen
betrieben werden, auch zu. Die höhere
Taktgeschwindigkeit in Kombination mit der gesteigerten Dichte der
Schaltungselemente hat das Gebiet, das synchron innerhalb der gleichen
Taktdomäne
arbeiten kann, reduziert. Dies hat das Bedürfnis nach einer modularen
Annäherung
geschaffen. Entsprechend einer derartigen Annäherung umfasst das Verarbeitungssystem
eine Anzahl relativ unabhängiger,
komplexer Module. Bei herkömmlichen Verarbeitungssystemen
kommunizieren die Systemmodule meistens über einen Bus miteinander.
Da aber die Anzahl Module immer ansteigt, ist diese Art von Kommunikation
nicht länger
praktisch, und zwar aus dem nachfolgenden Grund. Einerseits bildet
die Vielzahl von Modulen eine zu schwere Busbelastung und der Bus bildet
einen Kommunikationsengpass, da dieser jeweils nur einer einzigen
Anordnung die Möglichkeit
bietet, dem Bus Daten zuzusenden.
-
Ein
Kommunikationsnetzwerk bildet eine effektive Art und Weise diese
Nachteile zu überwinden.
Netzwerke auf Chip (NoC) sind zur Zeit als Lösung für das Kommunikationsproblem
in sehr komplizierten Chips interessant. Der Grund ist zweifach.
Erstens helfen NoCs die elektrischen Probleme in neuen Tiefsubmikrontechnologien
zu lösen,
da sie allgemeine Verdrahtung strukturieren und verwalten. Gleichzeitig
teilen sie sich Verdrahtung, verringern die Anzahl Drähte und
steigern die Ausnutzung derselben. NoCs können auch energieeffizient
sein und zuverlässig
und sind im Vergleich zu Bussen skalierbar. Zweitens entkoppeln
NoCs auch Rechnen von Kommunizieren, was in der Ver waltung des Entwurfs
von Chips mit unzähligen
Transistoren wesentlich ist. NoCs erreichen diese Entkopplung, weil
sie auf herkömmliche
Art und Weise unter Anwendung von Protokollstapeln entworfen wurden,
die gut definierte Schnittstellen schaffen, die Kommunikationsdienstgebrauch
von Dienstimplementierung trennen.
-
Das
Einführen
von Netzwerken als "On
Chip" Verbindungen ändert die
Kommunikation im Vergleich zu direkte Verbindungen, wie Bussen oder
Schaltern gründlich.
Dies ist wegen der Vielfachsprungart eines Netzwerkes, wobei Kommunikationsmodule
nicht direkt verbunden sind, sondern durch einen oder mehrere Netzwerkknoten
voneinander getrennt sind. Dies ist im Gegensatz zu den vorherrschenden
bestehenden Verbindungen (d. h. Bussen), wo Module direkt verbunden
sind. Die Implikationen dieser Änderung
liegen in der Beurteilung (die von zentralisiert zu verteilt ändern muss),
und in den Kommunikationseigenschaften (beispielsweise Reihenfolge,
oder Flusssteuerung), die entweder durch den Block "geistiges Eigentum" (IP) oder durch
das Netzwerk erledigt werden soll.
-
Die
meisten dieser Punkte sind bereits Thema der Forschung im Bereich
der örtlichen
und Großbereichsnetzwerke
(Computernetzwerke) und als Verbindung für parallele Maschinenverbindungsnetzwerke
gewesen. Beide bilden eine starke Beziehung zu On-Chip Netzwerken,
und viele der Ergebnisse in diesen Bereichen sind auch On-Chip anwendbar.
Aber NoCs Räumlichkeiten
sind auch anders als Off-Chip Netzwerke und deswegen müssen die
meisten der Netzwerkentwurfswahlen neu bewertet werden. On-Chip
Netzwerke haben andere Eigenschaften (beispielsweise festere Kopplungssynchronisation)
und Beschränkungen
(beispielsweise höhere
Speicherkosten), was zu verschiedenen Entwurfswahlen führt, was
letztendlich die Netzwerkdienste beeinträchtigt.
-
NoCs
weichen von Off-Chip Netzwerken vorwiegend in den Beschränkungen
und in der Synchronisation ab, Typischerweise sind Mittelbeschränkungen
bei On-Chip strenger als bei Off-Chip. Speicher-(d. h. Speicher)
und Rechenmittel sind relativ teurer, während die Anzahl Punkt-zu-Punkt
Verbindungen bei On-Chip größer ist
als bei Off-Chip. Speicherung ist teuer, weil Allzweck-On-Chip-Speicher,
wie RAM, eine große
Fläche belegen.
Wenn der Speicher über
die Netzwerkelemente in relativ kleinen Größen verteilt werden, ist dies
noch schlimmer, da die Gesamtfläche
in dem Speicher dann dominant wird.
-
Off-Chip
Netzwerke benutzen typischerweise Paketumschaltung und bieten Dienste
nach bestem Wissen. Bei jedem Netzwerkknoten können Streitigkeiten auftreten,
was es sehr schwierig macht, Latenzgarantien anzubieten. Durchflussgarantien
können
unter Anwendung von Schemen, wie ratenbasiertem Schalten oder fristbasiertem
Paketschalten dennoch geboten werden. Eine Alternative zum Schaffen
derartiger zeitrelatierter Garantien ist die Verwendung von TDMA-Schaltungen
("rime-division
multiple access"),
wobei jede Schaltungsanordnung einer Netzwerkverbindung zugeordnet
ist. Schaltungsanordnungen schaffen Garantien zu relativ niedrigen
Speicher- und Rechenkosten. Benutzung von Netzwerkmitteln nimmt
zu, wenn die Netzwerkarchitektur es erlaubt, dass gewisse übrig gebliebene
garantierte Bandbreite für
Kommunikation nach bestem Können
verwendet wird.
-
Ein
Netzwerk an-Chip (NoC) besteht typischerweise aus einer Anzahl Router
und Netzwerkschnittstellen. Router dienen als Netzwerkknoten und
werden zum Transportieren von Daten von einer Quellennetzwerkschnittstelle
zu einer Zielnetzwerkschnittstelle verwendet, und zwar durch Lenkung
von Daten über
eine einwandfreie Strecke zu dem Ziel auf statischer Basis (d. h.
die Route ist vorher bestimmt und ändert sich nicht), oder auf
dynamischer Basis (d. h. die Route kann sich ändern, und zwar je nach beispielsweise
der NoC Belastung um heiße
Stellen zu vermeiden). Router können
auch Zeitgarantien implementieren (beispielsweise ratenbasiert,
fristbasiert, oder durch Verwendung von Pipelineschaltungen auf
eine TDMA Weise). Mehr Einzelheiten über eine Routerarchitektur
lassen sich finden in: "A
router architecture for networks an silicon", von Edwin Rijpkema, Kees Goossens
und Paul Wielage, in "PROGRESS", Oktober 2001.
-
Die
Netzwerkschnittstellen sind mit einem IP Block ("intellectual property") verbunden, der
jede Art von Datenverarbeitungseinheit darstellt oder auch ein Speicher,
eine Brücke
usw. ist. Insbesondere bilden die Netzwerkschnittstellen eine Kommunikationsschnittstelle
zwischen den IP Blöcken
und dem Netzwerk. Die Schnittstelle ist meistens kompatibel mit
den bestehenden Busschnittstellen. Auf entsprechende Art und Weise werden
die Netzwerkschnittstellen entworfen zum Abwickeln von Datensequentialisierung
(das Einpassen des angebotenen Befehls, der Merker, der Adresse
und der Daten über
ein Signalgruppe mit einer festen Breite (beispielsweise 32 Bits)
und durch Paketierung (Hinzufügung
der Paketheader und Trailer, intern erforderlich für das Netzwerk).
Die Netzwerk schnittstellen können
auch Paketplanung implementieren, was Zeitgarantien und Erlaubnissteuerung
umfassen kann.
-
On-Chip
Systeme erfordern oft Zeitgarantien für die Verbindungskommunikation.
Deswegen wird eine Kommunikationsklasse geschaffen, in der Durchfluss,
Latenz und Jitter garantiert werden, und zwar auf Basis einer Idee
von allgemeiner Zeit (d. h. einer Idee von Synchronisation zwischen
Netzwerkelementen, d. h. Router und Netzwerkschnittstellen), wobei
die Basiszeiteinheit als Schlitz oder Zeitschlitz (Zeitlage) bezeichnet wird.
Alle Netzwerkelemente umfassen meistens eine Schlitztabelle gleicher
Größe für jeden
Ausgangsport des Netzwerkelementes, in der Zeitlagen für verschiedene
Verbindungen reserviert sind und die Schlitztabellen schreiten in
Synchronisation fort (d. h. sie sind alle gleichzeitig in demselben
Schlitz). Die Verbindungen werden benutzt zum Identifizieren verschiedener
Verkehrsklassen und assoziieren mit denselben Eigenschaften.
-
Eine
kosteneffektive Art und Weise zeitrelatierte Garantien zu schaffen
(d. h. Durchfluss, Latenz und Jitter) ist die Verwendung von Pipeline-Schaltungen
auf TDMA-Weise,
was vorteilhaft ist, da dies im vergleich mit ratenbasierten und
fristbasierten Schemen bei Systemen an Chip (SoC), die eine feste
Synchronisation haben) weniger Pufferraum erfordert.
-
Bei
jedem Schlitz wird ein Datenitem von dem einen Netzwerkelement Zuordnungsinformation
dem nächsten
verlagert, d. h. zwischen Router oder zwischen einem Router und
einer Netzwerkschnittstelle. Deswegen muss, wenn ein Schlitz an
einem Ausgangsport reserviert ist, der nächste Schlitz bei dem nächsten Ausgangsport
längs der
Strecke zwischen einem Master- und einem Sklavenmodul reserviert
werden, usw.
-
Wenn
mehrere Verbindungen mit Zeitgarantien aufgebaut werden, muss die
Schlitzzuordnung derart durchgeführt
werden, dass es keine Konflikte gibt (d. h. es gibt keinen Schlitz,
der mehr als nur einer Verbindung zugeordnet wurde). Die Aufgabe,
eine optimale Schlitzzuordnung für
eine bestimmte Netzwerktopologie zu finden, d. h. eine bestimmte
Anzahl Router und Netzwerkschnittstellen, und einen Satz Verbindungen
zwischen IP Blöcken
ist ein Problem mit sehr hohem Rechenaufwand (NP komplett), da dies
das Finden einer optimalen Lösung
betrifft, die gründliche
Rechenzeit erfordert.
-
Aus
der Veröffentlichung: "Trade offs in the
design of a router with both guaranteed and best-effort services
for networks an chip" von
Rijpkema E u. a. in: "IEE
Proceedings-Computers and Digital Techniques", Heft 150, Nr. 5, September 2003, Seiten 294–302, ist
bereits ein Datenverarbeitungssystem bekannt, das Folgendes umfasst:
- – eine
Anzahl Verarbeitungsmodule und ein Netzwerk, vorgesehen zur Kopplung
der genannten Module;
- – eine
Anzahl Netzwerkschnittstellen, die je zwischen einem der genannten
Verarbeitungsmodule und dem genannten Netzwerk gekoppelt sind,
wobei
das genannte Netzwerk eine Anzahl Router aufweist, die über Netzwerkverbindungen
mit benachbarten Router gekoppelt sind, und
wobei die genannten
Verarbeitungsmodule über
Verbindungen miteinander kommunizieren, und zwar unter Verwendung
von Verbindungsstrecken durch das Netzwerk hindurch,
wobei
jede der genannten Verbindungsstrecken wenigstens eine Netzwerkverbindung
für eine
erforderliche Anzahl Zeitschlitze benutzt, und - – wenigstens
eine Zeitschlitzzuordnungseinheit zum Zuordnen von Zeitschlitzen
zu den genannten Netzwerkverbindungen.
-
Deswegen
ist es u. a. eine Aufgabe der vorliegenden Erfindung, eine verbesserte
Schlitzzuordnung in einem Netzwerk an Chip Umgebung zu schaffen.
-
Diese
Aufgabe wird erfüllt
durch eine integrierte Schaltung nach Anspruch 2 und durch ein Verfahren zur
Zeitschlitzzuordnung nach Anspruch 7, sowie durch ein Datenverarbeitungssystem
nach Anspruch 1.
-
Deswegen
wird eine integrierte Schaltung mit einer Anzahl Verarbeitungsmodule
und einem Netzwerk, vorgesehen zur Kopplung der genannten Module
vorgesehen. Die genannte integrierte Schaltung umfasst weiterhin
eine Anzahl Netzwerkschnittstellen, die je zwischen einem der genannten
Verarbeitungsmodule und dem genannten Netzwerk gekoppelt sind. Das
genannte Netzwerk umfasst eine Anzahl Router, die über Netzwerkverbindungen
mit benachbarten Routern gekoppelt sind. Die genannten Verarbeitungsmodule
kommunizieren über
Verbindungen miteinander, und zwar unter Verwendung von Verbindungsstrecken
durch das Netzwerk hindurch, wobei jede der genannten Verbindungsstrecken
wenigstens eine Netzwerkverbindung für eine erforderliche Anzahl
Zeitschlitze benutzt. Wenigstens eine Zeitschlitzzuordnungseinheit
ist vorgesehen zum Zuordnen von Zeitschlitzen zu den genannten Netzwerkverbindungen
zum Ermitteln unbenutzter Zeitschlitze und zum Zuordnen der ermittelten
nicht benutzten Zeitschlitze zu einer oder mehreren Verbindungen,
und zwar unter Verwendung der genannten Netzwerkverbindungen nebst
den bereits zugeordneten Zeitschlitzen.
-
Auf
entsprechende Art und Weise können
diejenigen Zeitschlitze, die nach der Zeitschlitzzuordnung nicht
benutzt werden, für
einige der Verbindungen benutzt werden, so dass die Latenz dieser
Verbindungen reduziert wird.
-
Die
vorliegende Erfindung bezieht sich auf ein Verfahren zur Zeitschlitzzuordnung
in einer integrierten Schaltung mit einer Anzahl Verarbeitungsmodule,
einem Netzwerk, vorgesehen zur Kopplung der genannten Module, und
mit einer Anzahl Netzwerkschnittstellen, die je zwischen einem der
genannten Verarbeitungsmodule gekoppelt sind. Das genannte Netzwerk
umfasst eine Anzahl Router, die über
Netzwerkverbindungen mit benachbarten Routern gekoppelt sind. Die
Kommunikation zwischen Verarbeitungsmodulen erfolgt über Verbindungen,
wobei Verbindungsstrecken durch das Netzwerk hindurch verwendet
werden, wobei jede der genannten Verbindungsstrecken wenigstens
eine Netzwerkverbindung für
eine erforderliche Anzahl Zeitschlitze benutzt. Die Zeitschlitze,
die während
der Zuordnung der Zeitschlitze nicht verwendet wurden, werden ermittelt und
einer oder mehreren der Verbindungen zugeordnet, und zwar unter
Verwendung der genannten Netzwerkverbindung, nebst den bereits zugeordneten
Zeitschlitzen.
-
Die
vorliegende Erfindung bezieht sich weiterhin auf ein Datenverarbeitungssystem
mit einer Anzahl Verarbeitungsmodule und mit einem Netzwerk, vorgesehen
zur Kopplung der genannten Module. Die genannte integrierte Schaltung
umfasst weiterhin eine Anzahl Netzwerkschnittstellen, die je zwischen
einem der genannten Verarbeitungsmodule und dem genannten Netzwerk
gekoppelt sind. Das genannte Netzwerk umfasst eine Anzahl Router,
die über
Netzwerkverbindungen mit benachbarten Routern gekoppelt sind. Die
genannten Verarbeitungsmodule kommunizieren über Verbindungen miteinander,
und zwar unter Verwendung von Verbindungsstrecken durch das Netzwerk
hindurch, wobei jede der genannten Verbindungsstrecken wenigstens eine
Netzwerkverbindung für
eine erforderliche Anzahl Zeitschlitze benutzt. Wenigstens eine
Zeitschlitzzuordnungseinheit ist vorgesehen zum Zuordnen von Zeitschlitzen
zu den genannten Netzwerkverbindungen, zum Ermitteln nicht Benutzer
Zeitschlitze und zum Zuordnen der ermittelten nicht benutzten Zeitschlitze
zu einer oder mehreren der Verbindungen, und zwar unter Verwendung
von Netzwerkverbindungen nebst bereits zugeordneten Zeitschlitzen.
-
Auf
entsprechende Art und Weise kann die Zeitschlitzzuordnung auch in
einem Mehrchip-Netzwerk oder in einem System oder einem Netzwerk
mit verschiedenen einzelnen integrierten Schaltungen durchgeführt werden.
-
Der
vorliegenden Erfindung liegt die Erkenntnis zugrunde, diejenigen
Zeitschlitze zu benutzen, die nach der Zeitschlitzzuordnung nicht
benutzt wurden, und zwar durch Zuordnung dieser nicht benutzten
Zeitschlitze zu Verbindungen in der Netzwerk an Chip Umgebung, nebst
den bereits zugeordneten Zeitschlitzen, damit die Latenz derartiger
Verbindungen reduziert wird.
-
Andere
Aspekte der vorliegenden Erfindung sind in den Unteransprüchen definiert.
-
Ausführungsbeispiele
der vorliegenden Erfindung sind in der Zeichnung dargestellt und
werden im Folgenden näher
beschrieben. Es zeigen:
-
1 die
Basisstruktur eines Netzwerkes an Chip nach der vorliegenden Erfindung,
-
2 eine
Basisschlitzzuordnung für
eine Verbindung in einem Netzwerk nach 1,
-
3 eine
detaillierte Darstellung einer Schlitzzuordnung in einem Netzwerk
nach 1,
-
4 eine
detaillierte Darstellung der Schlitzzuordnung nach der vorliegenden
Erfindung,
-
5 eine
detaillierte Darstellung der Schlitzzuordnung nach der vorliegenden
Erfindung,
-
6 eine
detaillierte Darstellung der Schlitzzuordnung nach der vorliegenden
Erfindung,
-
7 eine
Netzwerk an Chip Umgebung nach einer ersten Ausführungsform,
-
8 einen
Teil der Netzwerk an Chip Umgebung nach 7,
-
9 eine
Darstellung eines Verfahrens zum Finden freier Schlitze,
-
10 ein
Netzwerk an Chip mit verschiedenen Verbindungen,
-
11 ein
Netzwerk an Chip nach 9 mit einer berechneten Koppelgewichtung,
-
12 ein
Netzwerk an Chip nach 10 mit berechneten Verbindungsgewichtungen,
und
-
13 eine
detaillierte Schlitzzuordnung für
alle Verbindungen nach 10.
-
BESCHREIBUNG DER BEVORZUGTEN
AUSFÜHRUNGSFORMEN
-
Die
nachfolgenden Ausführungsformen
beziehen sich auf Systeme an Chip, d. h. eine Anzahl Module auf
demselben Chip kommunizieren miteinander über eine Art von gegenseitiger
Verbindung. Diese Verbindung ist als Netzwerk an Chip (NoC) verkörpert. Das
NoC kann Drähte,
einen Bus, Zeitmultiplex, Schalter, und/oder Router innerhalb eines
Netzwerkes umfassen. In der Transportschicht des genannten Netzwerkes erfolgt
die Kommunikation zwischen den Modulen über Verbindungen. Eine Verbindung
wird als einen Satz von Kanälen
betrachtete, die je einen Satz von Verbindungseigenschaften haben,
und zwar zwischen einem ersten Modul und wenigstens einem zweiten
Modul. Für
eine Verbindung zwischen einem ersten Modul und einem einzigen zweiten
Modul kann die Verbindung zwei Kanäle aufweisen, und zwar einen
von dem ersten Modul zu dem zweiten Modul, d. h. den Antragskanal,
und einen zweiten Kanal von dem zweiten Modul zu dem ersten Modul,
d. h. den Reaktionskanal. Der Antragskanal ist für Daten und Nachrichten von
dem ersten zu dem zweiten Modul reserviert, während der Reaktionskanal für Daten
und Nachrichten von dem zweiten zu dem ersten Modul reserviert ist.
Wenn keine Reaktion erforderlich ist, kann es sein, dass die Verbindung
nur einen einzigen Kanal aufweist. Wenn aber die Verbindung einen
ersten und N zweite Module betrifft, werden 2*N Kanäle vorgesehen.
Deswegen umfasst eine Verbindung oder die Strecke der Verbindung
durch das Netzwerk, d. h. die Verbindungsstrecke wenigstens einen
Kanal. Mit anderen Worten, ein Kanal entspricht der Kommunikationsstrecke
der Verbindung, wenn nur ein einziger Kanal verwendet wird. Wenn
zwei Kanäle
verwendet werden, wie oben erwähnt,
wird der eine Kanal die Verbindungsstrecke bilden, beispielsweise
von dem Master zu dem Sklaven, während
der zweite Kanal die Verbindungsstrecke von dem Sklaven zu dem Master bildet.
Auf entsprechende Art und Weise wird für eine typische Verbindung
die Verbindungsstrecke zwei Kanäle
aufweisen. Die Verbindungseigenschaften können eine Reihenfolge (Datentransport
in Reihenfolge), eine Flussteuerung (ein Fernpuffer ist für eine Verbindung
reserviert, und ein Datenerzeuger darf Daten nur dann senden, wenn
gewährleistet
ist, dass für
die erzeugten Daten Raum verfügbar
ist), Durchfluss (eine untere Grenze des Durchflusses ist gewährleistet),
Latenz (eine obere Grenze für
die Latenz ist gewährleistet),
die Verlierbarkeit (Fortfallen von Daten), Übertragungsbeendigung, Transaktionsvervollständigung,
Datenkorrektheit, Priorität,
oder Datenlieferung.
-
1 zeigt
ein Netzwerk an Chip nach der vorliegenden Erfindung. Das System
umfasst verschiedene sog. IP Blöcke
(Rechenelemente, Speicher oder ein Subsystem, das intern Verbindungsmodule
enthalten kann), die mit je einem Netzwerk N verbunden sind, und
zwar über
eine Netzwerkschnittstelle NI. Das Netzwerk N umfasst eine Anzahl
Router R, die über
jeweilige Verbindungen mit benachbarten Routern R verbunden sind.
-
Die
Netzwerkschnittstellen NI werden als Schnittstellen zwischen den
IP Blöcken
und dem Netzwerk N verwendet. Die Netzwerkschnittstellen NI sind
vorgesehen zum Verwalten der Kommunikation der betreffenden IP Blöcke und
des Netzwerkes N, so dass die IP Blöcke ihre spezielle Arbeit leisten
können,
ohne dass sie sich mit der Kommunikation mit dem Netzwerk N oder
anderen IP Blöcken
befassen müssen.
Die IP Blöcke können als
Master wirksam sein, d. h. einen Antrag stellen, oder sie können als
Sklave wirksam sein, d. h. die können
einen Antrag von einem Master empfangen und den Antrag auf entsprechende
Art und Weise verarbeiten.
-
2 zeigt
ein Blockschaltbild einer Verbindung und einer Basisschlitzzuordnung
in einem Netzwerk an Chip nach 1. Insbesondere
ist die Verbindung zwischen einem Master M und einem Sklaven S dargestellt.
Diese Verbindung wird durch eine Netzwerkschnittstelle NI assoziiert
mit dem Master M, zwei Routern und einer Netzwerkschnittstelle NI
assoziiert mit einem Sklaven S verwirklicht. Die Netzwerkschnittstelle
NI assoziiert mit dem Master M umfasst eine Zeitschlitzzuordnungseinheit
SA. Auf alternative Weise kann die Netzwerkschnittstelle NI assoziiert
mit dem Sklaven S auch eine Zeitschlitzzuordnungseinheit Schaltungsanordnung
aufweisen. Eine erste Verbindung L1 gibt es zwischen der Netzwerkschnittstelle
NI assoziiert mit dem Master M und einem ersten Router R, eine zweite
Verbindung L2 gibt es zwischen den zwei Routern R, und eine dritte
Verbindung L3 gibt es zwischen einem Router und der Netzwerkschnittstelle
NI, assoziiert mit dem Sklaven S. Drei Schlitztabellen ST1–ST3 für die Ausgangsporte
der betreffenden Netzwerkelemente sind ebenfalls dargestellt. Diese
Schlitztabellen werden vorzugsweise an der Ausgangsseite, d. h.
an der Datenerzeugungsseite, der Netzwerkelemente, wie Netzwerkschnittstellen
und Routern implementiert. Für
jeden beantragten Schlitz wird ein Schlitz in jeder Schlitztabelle
der Verbindungen längs
der Verbindungsstrecke reserviert. All diese Schlitze müssen frei
sein, d. h. nicht von anderen Kanälen reserviert. Da die Daten
von dem einen Netzwerkelement zum anderen fortschreiten, muss jeder
Schlitz, ausgehend von dem Schlitz s = 1, dem nächsten Schlitz längs der
Verbindung bei dem Schlitz s = 2 und danach bei dem Schlitz s =
3 reserviert werden.
-
Die
Eingaben für
die Schlitzzuordnungsbestimmung durch die Zeitschlitzzuordnungseinheit
SA sind die Netzwerktopologie, wie Netzwerkelemente, mit ihrer gegenseitigen
Verbindung, und die Schlitztabellengröße und der Verbindungssatz.
Für jede
Verbindung werden die Strecken und die Bandbreite, Latenz, Jitter und/oder
Schlitzanforderungen gegeben. Eine Verbindung besteht aus wenigstens
zwei Kanälen
oder Verbindungsstrecken (einem Antragskanal von dem Master zu dem
Sklaven, und einem Reaktionskanal von dem Sklaven zu dem Master).
Jeder dieser Kanäle
wird auf eine einzelne Strecke gesetzt und kann verschiedene Verbindungen
mit verschiedene Bandbreite, Latenz, Jitter, und/oder Schlitzanforderungen
aufweisen. Um zeitrelatierte Garantien zu schaffen. Müssen Schlitze
für die
Verbindungen reserviert werden. Verschiedene Schlitze können für verschiedene
Verbindungen reserviert werden, und zwar mit Hilfe von TDMA. Daten
für eine
Verbindung werden danach über
aufeinander folgende Verbindungen in aufeinander folgenden Schlitzen
transportiert.
-
3 zeigt
eine detaillierte Darstellung der Tabellenimplementierung der 2.
In diesem Fall sind zwei Netzwerkschnittstellen NI1, NI2 und zwei
Router R1, R2 und die drei Verbindungen L1–L3 zwischen der Netzwerkschnittstelle
NI1 und dem Router R1, zwischen dem Router R1 und dem Router R2,
und zwischen dem Router R1 und der Netzwerkschnittstelle NI2 dargestellt.
Die IP Blöcke
sind nicht dargestellt. Die Schlitztabellen ST1–ST3 sind für jede der gekennzeichneten
Verbindungen L1–L3
dargestellt. Diese Verbindungen sind bidirektional und folglich
gibt es für
jede Verbindung eine Schlitztabelle jede der zwei Richtungen; die Schlitztabellen
ST1–ST3
sind nur für
eine einzige Richtung dargestellt. Außerdem sind drei Verbindungen c1–c3 dargestellt.
Nebst den oben stehenden drei Schlitztabellen ST1–ST3 sind
weitere Schlitztabellen ST4–ST6
dargestellt. Nun sind alle Schlitztabellen ST1–ST6 dargestellt, die sich
auf die drei Verbindungen c1–c3
beziehen. Die erste Verbindung c1 erstreckt sich von der Netzwerkschnittstelle
NI1 zu der Netzwerkschnittstelle NI2, und zwar über die Router R1 und R2. Die
zweite Verbindung c2 erstreckt sich von der Netzwerkschnittstelle
NI1 zu dem Router R1 und danach zu einem weiteren (nicht dargestellten)
Netzwerkelement, und zwar unter Anwendung der Schlitztabelle ST4.
Die dritte Verbindung c3 kann von einem nicht dargestellten Netzwerkelement
herrühren
und von dem Router R1 zu dem Router R2 und weiter hin zu einem anderen
nicht dargestellten Netzwerkelement gehen, und zwar unter Anwendung
der Schlitztabelle ST6. Die Verbindung c1 reserviert einen Schlitz
in jeder der drei Verbindungen L1–L3 und benutzt (NI1 zu R1,
R1 zu R2, und R2 zu NI2). Die Schlitze in diesen Verbindungen müssen aufeinander
folgend sein (Schlitz 2, Schlitz 3 bzw. Schlitz 4). Aus dem Gesichtspunkt
des Routers empfängt
in einem Zeitschlitz der Router Daten von Eingangsverbindungen bei
der Verbindung c1–c3
sind dazu die Verbindungen L1–L3
reserviert. Die Daten werden in dem Router gespeichert. Gleichzeitig
sendet der Router die Daten, die er im vorigen Schlitz empfangen
hat, zu den Ausgangsverbindungen. Diesem Modell entsprechend müssen die
Schlitze einer Verbindung, da die Daten während wenigstens eines Schlitzes
in einem Router gespeichert sind, nacheinander reserviert werden.
-
Eine
mögliche
Verallgemeinerung oder eine Alternative des Schlitzzuordnungsproblems
wäre das
Erlauben, dass Daten länger
als eine einzige Schlitzdauer in den Routern gespeichert werden.
Dadurch wird die Schlitzzuordnung flexibler, was zu einer besseren
Linkbenutzung führen
kann, und zwar auf Kosten von Mehr Pufferung und möglicherweise
längerer
Latenz.
-
Schlitze
müssen
derart reserviert werden, dass es bei Links keine Konflikte gibt.
Das heißt,
es gibt keine zwei Verbindungen, die denselben Schlitz für denselben
Link reservieren. Deswegen reserviert C1 den Schlitz 2 für den Link
zwischen NI1 und R1. Folglich kann C2 den Schlitz 2 nicht für denselben
Link verwenden.
-
4 zeigt
eine unkomplizierte Schlitztabellenimplementierung, indem für den ersten,
den zweiten und den dritten Link L1–L3 eine Tabelle implementiert
wird, die spezifiziert, welche Schlitze für welche Verbindung reserviert
sind. Insbesondere sind nur diejenigen Schlitztabellen ST1–ST3 dargestellt,
die von den drei Verbindungen c1–c3 für die drei Links L1–L3 erforderlich
sind. Eine bevorzugte Stelle zum Speichern dieser Tabelle ist in
der Router/Netzwerkschnittstelle, die Daten für diesen Link erzeugt, d. h.
in dem Ausgangsport, weil die Router/Netzwerkschnittstelle wissen
muss, ob ein Link reserviert ist oder nicht, damit sie Daten für diesen
Link erzeugen kann. Die Tabelle kann auch ein Teil der Zeitschlitzzuordnungseinheit
SA sein.
-
5 zeigt
eine effizientere Schlitzzuordnungscodierung. Hier sind auch nur
diejenigen Schlitztabellen ST1–ST3
dargestellt, die für
die drei Verbindungen c1–c3
für die
drei links L1–L3
erforderlich sind. Die Information, zu welcher Verbindung ein Schlitz
gehört,
ist in der Netzwerkschnittstelle NI gespeichert und insbesondere
in der Zeit schlitzzuordnungseinheit SSA, während die Schlitztabellen ST1–ST3 in
den Routern nur markieren, ob ein Schlitz für die Links reserviert ist
oder nicht. Die Router brauchen nicht die Verbindungen zu kennen,
die mit Schlitzen assoziiert sind, da sie nur Daten von dem einen
Netzwerkelement zu einem anderen und letztendlich zu dem richtigen
Ausgang verlagern, und zwar auf Basis der Paketheader (die eine
Zieladresse oder eine Strecke zum Ziel enthalten).
-
In 6 ist
eine etwaige Variation der oben stehenden Codierung nach 4 und 5 dargestellt. Hier
ist die Routinginformation in dem Router selber gespeichert (statt
des Paketheaders). In den Ausgangsportschlitztabellen ST1–ST3 geben
die Schlitze an, von welchem Eingang Daten konsumiert wurden. Auf
diese Art und Weise kann aucf den Paketheader verzichtet werden,
was zu mehr Durchfluss führt,
und zwar auf Kosten größerer Schlitztabellen
in den Routern.
-
7 zeigt
ein Netzwerk an Chip nach der bevorzugten Ausführungsform, der vorliegenden
Erfindung. Das Netzwerk an Chip umfasst zwei Router R7, R4, einen
7 × 7
Router bzw. einen 4 × 4
Router. Diese zwei Router sind über
acht Netzwerkschnittstellen NI1–NI8
mit weiteren IP Blöcken
verbunden. Die IP Blöcke sind
eine decomp Einheit (Dekompression), eine L0 Speichereinheit, eine
ME/MC Einheit (Bewegungsschätzung/Bewegungskompensation),
eine comp Einheit (Kompression), ein Speicher MEM, eine weitere
decomp Einheit und eine weitere ME/MC Einheit. Da die spezielle
Funktion der betreffenden IP Blöcke
zum Beschreiben der Grundlagen der vorliegenden Erfindung nicht
wichtig ist, wird auf eine detaillierte Beschreibung verzichtet.
-
Außerdem zeigt 7 zwei
Schlitztabellen für
jeden Link zwischen den Netzwerkschnittstellen NI und dem Router
R7, R4. Insbesondere ist eine Schlitztabelle in Vorwärtsrichtung
und es ist eine Schlitztabelle in der umgekehrten Richtung vorgesehen.
Weiterhin sind die zwei Schlitztabellen bei dem Link zwischen den Routern
zur Kommunikation zwischen den zwei Routern R7, R4 vorgesehen, d.
h. einen in der Vorwärtsrichtung
und einen in der umgekehrten Richtung. Auf diese Art und Weise sind
insgesamt 18 Schlitztabellen für neun
Links in diesem Netzwerk an Chips dargestellt. Es sei bemerkt, dass
18 Schlitztabellen in der Figur dargestellt sind, dass es aber physikalisch
nur 8 Schlitztabellen geben kann, da nur eine einzige Schlitztabelle (beispielsweise
vorwärts)
für eine
einzige Netzwerkschnittstelle notwendig ist und dass ein Router überhaupt keine
Schlitztabellen braucht.
-
In 7 ist
eine Situation dargerstellt, nachdem eine Zeitschlitzzuordnung für einige
Verbindungen innerhalb dieses Netzwerk an Chip durchgeführt worden
ist. Es ist ersichtlich, dass einige der Schlitztabellen völlig reserviert
sind (beispielsweise die Schlitztabelle der Vorwärtsrichtung, assoziiert mit
der zweiten Netzwerkschnittstelle NI2 und der dritten Netzwerkschnittstelle
NI3 sowie die Schlitztabellen der umgekehrten Richtung, assoziiert
mit der vierten und achten Netzwerkschnittstelle NI4, NI8). In einigen
der anderen Schlitztabellen beispielsweise den Schlitztabellen der
Vorwärtsrichtung
und der umgekehrten Richtung, assoziiert mit der fünften Netzwerkschnittstelle
NI5, ist lediglich 1 der 20 Zeitschlitze reserviert worden.
-
In
den 18 Schlitztabellen ist der reservierte Schlitz durch einen grauen
Kasten angegeben, während freie
Zeitschlitze durch einen weißen
Kasten angegeben sind. Hier umfassen alle 18 Schlitztabellen 20
Zeitschlitze um sie synchronisiert zu halten. So umfasst beispielsweise
die Schlitztabelle der Vorwärtsrichtung
in dem Link zwischen der ersten Netzwerkschnittstelle NI1 17 reservierte
und 3 freie Zeitschlitze. Von den 17 reservierten Zeitschlitzen
können
16 dieser Zeitschlitze mit einer einzigen Verbindung assoziiert
sein, während ein
einziger reservierter Zeitschlitz mit einer weiteren Verbindung
assoziiert sein kann. Außerdem
umfasst die Schlitztabelle der Vorwärtsrichtung in dem Link zwischen
der achten Netzwerkschnittstelle NI8 und dem Router R7 vier reservierte
und 16 leere Schlitze.
-
Der
Grund, weshalb viele der 18 Schlitztabellen leer Schlitze haben,
d. h. die nicht reserviert worden sind, ist, dass die Datenrate,
erforderlich für
die verschiedenen IP Blöcke
kleiner ist als die verfügbare
Datenrate. Die Schlitztabellengröße bildet
ein Kompromiss um die Verbindungsbedingungen für alle Verbindungen in diesem
Netzwerk an Chip zu erfüllen.
Der zum Zuordnen der betreffenden Zeitschlitze in den Schlitztabellen verwendete
Schlitztabellenzuordnungsalgorithmus ist entworfen zum Minimieren
der Schlitztabellenfragmentierung, d. h. die leeren Schlitze in
den verschiedenen Schlitztabellen, für alle Schlitztabellen. Auf
entsprechende Weise bildet dieser Algorithmus alle Verbindungen
innerhalb des Netzwerkes an Chip auf den verfügbaren Schlitztabellen ab,
wodurch die völlig
unbrauchbaren Schlitze minimiert werden. Aus dem Blockwinkel der
Benutzung wird eine derartige Zeitschlitzzuordnung bevorzugt, da
dies eine minimale Anzahl Zeitschlitze in den Schlitztabellen benutzt.
Die durch eine derartige Zeitschlitzzuordnung eingeführte Latenz
ist in einigen Fällen alles
andere als optimal. So umfasst beispielsweise die Schlitztabelle
der Vorwärtsrichtung,
assoziiert mit der achten Netzwerkschnittstelle NI8 vier reservierte
Zeitschlitze von den 20 verfügbaren
Zeitschlitzen. Folglich wäre,
da 16 Zeitschlitze frei sind, das schlimmste Szenario, dass sie
bis zu 16 Zyklen warten müssen.
Die nicht benutzen oder freien Zeitschlitze werden aber benutzt
um die Latenz einer Verbindung von dem einen IP Block mit einem
anderen IP Block zu reduzieren.
-
8 zeigt
selektierte Elemente von dem Netzwerk an Chip nach 7.
Folglich ist in 8 auf alle Elemente, die nicht
erforderlich sind, verzichtet. Insbesondere sind die zwei Router
R7, R4, die zweite, sechste und achte Netzwerkschnittstelle NI2,
NI6, NI8 sowie ihre betreffenden Schlitztabellen der Vorwärts- und
Rückwärtsrichtung
dargestellt. Außerdem
sind die mit den zwei Routern R7, R4 assoziierten Schlitztabellen
der Vorwärts-
und Rückwärtsrichtung
in 8 dargestellt. Weiterhin sind auch zwei Verbindungen
C1, C2 in 8 dargestellt. Die erste Verbindung
C1 erfordert 3 Zeitschlitze um von dem ME/MC zu dem L0 Speicher
zu kommunizieren, und zwar über
die achte Netzwerkschnittstelle NI8, über die assoziierte Schlitztabelle
ST1-F und ST1-R, die Schlitztabelle 2, ST2-F und ST2-R, assoziiert
mit der zweiten Netzwerkschnittstelle, und die Netzwerkschnittstelle
NI2. Die zweite Verbindung C2 erfordert einen einzigen Zeitschlitz
um von dem MEC/MC über die
achte Netzwerkschnittstelle NI8, deren assoziierte Schlitztabelle
in Vorwärtsrichtung
ST1-F, den Router R7, die Schlitztabelle ST3-F assoziiert zwischen
den zwei Router, R7, R4, die Schlitztabelle ST4-R, die sechste Netzwerkschnittstelle
NI6 zu dem Speicher MEM.
-
Da
die Verbindung C1 nur durch den Router R7 geht, brauchen nur zwei
Schlitztabellen in der Vorwärtsrichtung,
und zwar die Schlitztabellen ST1-F und ST2-F, sowie zwei Schlitztabellen
in der Rückwärtsrichtung,
und zwar ST1-R und ST2-R ausgerichtet zu werden, damit die erforderliche
Latenz sowie der Durchfluss gewährleistet
wird. Im Falle der zweiten Verbindung C2 müssen drei Schlitztabellen in
der Vorwärtsrichtung, und
zwar ST1-F, ST3-F und ST4-F und drei Schlitztabellen in der Rückwärtsrichtung,
und zwar ST1-R, ST3-R und ST4-R ausgerichtet werden.
-
Wie
oben erwähnt,
ist die Latenz einer Verbindung abhängig von dem Abstand zwischen
zwei zugeordneten Zeitschlitzen in der Schlitztabelle. Auf entsprechende
Weise werden die noch immer nicht benutzten Zeitschlitze einigen
der bestehenden Verbindungen zugeordnet, damit die Latenz der Verbindung
reduziert wird. Die Anzahl zusätzlicher
Zeitschlitze, d. h. die nicht benutzten oder freien Zeitschlitze,
die einer Verbindung als Mittel zur Latenzreduktion zugeordnet werden
können,
ist die minimale Anzahl Schlit ze, die in jeder Schlitztabelle längs einer
Verbindungsstrecke zum Transportieren von Daten von der einen Seite
des Netzwerkes an Chip zu der anderen Seite verfügbar sind. Wie oben erwähnt, sollen
aufeinander folgende Zeitschlitze längs der Schlitztabelle in der
Verbindungsstrecke reserviert werden.
-
Da
nur ein einziger Zeitschlitz in der mit der zweiten Netzwerkschnittstelle
NI2 assoziierten Schlitztabelle ST2-R verfügbar ist, während 16 Zeitschlitze in der
Schlitztabelle ST1-F verfügbar
sind, kann nur ein einziger Schlitz zur Latenzreduktion innerhalb
der ersten Verbindung C1 verwendet werden. Innerhalb der drei Schlitztabellen
ST1-F, ST3-F, ST4-R sind 15, 16 und 16 Schlitze für die zweite
Verbindung C2 verfügbar.
-
Auf
entsprechende Weise kann nur ein einziger zusätzlicher Schlitz der ersten
Verbindung C1 zugeordnet werden und 15 zusätzliche Schlitze können der
zweiten Verbindung C2 zugeordnet werden. Deswegen wird die Wartezeit
der Latenz für
den schlimmsten Fall, d. h. die gesamte Anzahl Schlitze in der Schlitztabelle weniger
der Anzahl zugeordneter Zeitschlitze für die erste Verbindung C1 von
17 (20 Zeitschlitze – 3
reservierte Schlitze) auf 16 (20 Schlitze – (3 zugeordnete Schlitze +
1 Latenzreduktionsschlitz)) reduziert. Die Wartezeit in dem schlimmsten-Fall-Szenario
für die
zweite Verbindung C2 wird von 19 (20 Schlitze–1 zugeordneter Schlitz) auf
4 (1 zugeordneter Schlitz + 15 Schlitze zur Latenzreduktion)) reduziert.
Auf entsprechende Art und Weise ist die Effizienz der Latenzreduktion
weitgehend abhängig
von dem Betrag an freien oder unbenutzten Zeitschlitzen nach Durchführung der
Schlitzzuordnung. Die Benutzung der unbenutzten oder freien Zeitschlitze nach
der Schlitzzuordnung ist in sofern vorteilhaft, dass diese Technik
keine Kosten oder Komplexität
mit sich bringt, da nur diejenigen Schlitze benutzt werden, auf
die verzichtet werden kann, wenn diese Technik nach der vorliegenden
Erfindung nicht durchgeführt
wird.
-
Obschon
die Grundlagen der bevorzugten Ausführungsform nur für die Verbindungen
einer einzigen Schlitztabelle beschrieben worden ist, ist dieselbe
Technik auch für
jede beliebige Verbindung innerhalb der Schlitztabelle innerhalb
eines Netzwerkes an Chip anwendbar. Wenn die Technik der Benutzung
der unbenutzten Schlitze zur Latenzreduktion innerhalb des Netzwerkes
an Chip mit einer Anzahl Schlitztabellen durchgeführt worden
ist, sollen die nicht benutzten und freien Schlitze, die zur Latenzreduktion
verfügbar
sind, unter Verwendung der Schlitztabellen mit unbenutzten Schlitzen
oder Latenzredundanzschlitzen verteilt oder gemeinsam benutzt werden.
-
Vorzugsweise
können
mit den Verbindungen innerhalb des Netzwerkes an Chip verschiedene
Prioritäten
assoziiert werden, so dass diese Verbindungen, die eine zunehmende
Latenzreduktion erfordern, als erste verwendet werden können. Dies
kann durch Speicherung einer Prioritätsliste in der Zeitschlitzzuordnungseinheit
erreicht werden.
-
Zur
weiteren Verbesserung der Identifikation nicht benutzter Schlitze,
die zur Latenzreduktion verwendet werden können, kann die Schlitzzuordnungseinheit
SA die betreffenden Zeitschlitze, als verwendet, nicht verwendet
oder zur Latenzreduktion reserviert, markieren. Für eine derartige
Implementierung einer Markierungseinheit MU innerhalb der Zeitschlitzzuordnungseinheit
SA muss ein Markierer mit drei Werten statt zwei vorgesehen werden.
Der dritte Wert, d. h. zur Latenzreduktion reserviert, kann die
Benutzung dieser Schlitze für
andere Zwecke erlauben. Eine derartige Implementierung des Markierers
wird den garantierten Durchfluss der Verbindung nicht beeinträchtigen.
-
Es
sei bemerkt, dass die wirklich verfügbare Reduktion der Latenz
von der Schlitzzuordnung für
eine bestimmte Verbindung und der Lage nicht benutzter Schlitze
in den Schlitztabellen in der Netzwerk an Chip Umgebung abhängig ist.
Die Vorteile der oben beschriebenen verbesserten Schlitzzuordnungstechnik
sind, dass die Latenz einer Verbindung zum Übertragen von Daten reduziert
wird. Diese Implementierung der Latenzreduktion wird nicht mit zusätzlichen
Kosten oder einer größeren Komplexität einher
gehen. Die einzige Zunahme in der Komplexität erfolgt durch ein Reduzierlatenzbit.
Dieses Bit kann in die Schlitztabellen innerhalb der Netzwerk-on-Chip-Umgebung
oder innerhalb einer zentralisierten Verwaltungseinheit gesetzt
werden, welche die Eigenschaften der Verbindungen speichert. Außerdem ist
ein weiterer Markierer vorgesehen um anzugeben, dass die markierten
Schlitze für
andere Zwecke benutzt werden können,
d. h. sie können
konfiguriert werden um für
eine andere Verbindung verwendet zu werden.
-
Die
Latenzreduktionsschlitzzuordnung kann nach einer Schlitzzuordnung
durchgeführt
oder kann parallel von dem Start einer Schlitzzuordnung an verwendet
werden. Diese Latenzreduktionsschlitzzuordnung kann in vielen synchronisierten
TDMA Systemen aber auch in einem einzigen TDMA System (beispielsweise "Sonics back plane") verwendet werden.
-
Nachstehend
wird nun die wirkliche Zuordnungsfunktion beschrieben, die in der
Zeitschlitzzuordnungseinheit SA vor der oben genannten Ermittlung
der nicht benutzten Schlitze implementiert werden kann. Das Ergebnis
führt zu
einer Schlitzzuordnung, die mit den Schlitzanforderungen übereinstimmt.
Für jeden
Link in der Strecke der Verbindung wird eine Gewichtung als eine
Funktion von Bandbreite, Latenz, Jitter, Priorität und/oder Anzahl Schlitze,
erforderlich für
jeden Kanal chi in der Verbindungsstrecke,
die diesen Link verwendet, berechnet: Gewichtung
(Link) = f(Bandbreite(chi), Latenz(chi), Jitter(chi),
Priorität(chi), Schlitze(chi)) ∀chi derart, dass Link ∊ chi
-
Auf
alternative Weise wird für
jeden Link in dem wenigstens einen Kanal in der Verbindungsstrecke eine
Gewichtung als eine Summe der Anzahl beantragter oder für jede Verbindungsstrecke
erforderlicher Schlitze berechnet, d. h. für jeden Kanal, der diesen Link
verwendet:
-
Danach
wird für
jeden Kanal in einer Verbindungsstrecke eine Gewichtung als eine
Funktion (beispielsweise die Summe) der Gewichtungen der Links in
der Kanalstrecke als Teil der Verbindungsstrecke) berechnet, und
möglicherweise
anderer Eigenschaften des Kanals (beispielsweise Bandbreite, Latenz,
Priotität): Gewichtung (ch) = f(Gewichtung (linki),
Bandbreite(ch), Latenz(ch), Jitter(ch), Priorität (ch), Schlitze(ch))
∀ linki ∊ ch
-
Oder
auf alternative Weise wird für
jeden Kanal (d. h. jede4 Verbindungsstrecke) eine Gewichtung als eine
Summe der Gewichtungen der Links in der Kanalstrecke berechnet:
-
Für die alternativen
oben stehenden einfachen Funktionen:
-
Kann
dieser Algorithmus durch den nachfolgenden Pseudocode implementiert
werden:
-
Die
Schlitze werden den Kanälen
in der abnehmenden Reihenfolge deren berechneter Werte zugeordnet.
Für jeden
beantragten Schlitz wird ein Schlitz in jeder Schlitztabelle der
Links längs
der Kanalstrecke reserviert. All diese Schlitze müssen frei
sein, d. h. nicht vorher von anderen Kanälen reserviert. Diese Schlitze können durch
Ausprobieren zugeordnet werden: ausgehend von einem bestimmten Schlitz,
wird eine Anzahl Schlitze überprüft, bis
in allen Links längs
der Strecke ein freier Schlitz gefunden wird.
-
Schlitze
können
versucht werden für
Zuordnungen, und zwar unter Anwendung verschiedener Verfahren. Beispiele
sind aufeinander folgende Schlitze, oder gleichmäßig verteilte Schlitze. Der
Grund, dass viele Verfahren erforderlich sind ist, dass verschiedene
Eigenschaften mit verschiedenen Verfahren optimiert werden können. So
können
beispielsweise aufeinander folgende Schlitze Headergesamtkosten
reduzieren, während
gleichmäßig verteilte
Schlitze Latenz reduzieren können.
-
Die
vorgeschlagene Technik hat eine niedrige Komplexität von O
(C × L × S), wobei
C die Anzahl Kanäle
ist, wobei L die Anzahl Links ist und wobei S die Schlitztabellengröße ist.
Die mit diesem Algorithmus erhaltenen Schlitzzuordnungen sind mit
dem Optimum (erhalten mit einer viel höheren Komplexität: O(SC)), vergleichbar und um einen Faktor 2 besser
als ein habgieriger Algorithmus (d. h. mit einer beliebigen Reihenfolge für Kanalzuordnung).
-
Ein
alternatives Beispiel eines Algorithmus wird nachstehend beschrieben.
Auch hier wird für
jeden Link eine Gewichtung als die Summe der Anzahl für jeden
Kanal, der diesen Link benutzt, beantragter Schlitze:
-
Danach
wird für
jeden Kanal eine Gewichtung berechnet, und zwar als die Summe der
Gewichtungen der Links der Kanalstrecke:
-
Schlitze (Kanal)
-
Wobei
a1, a2 und a3 Konstanten sind (dies ist ein Beispiel
von Gewichtungsformeln, aber andere sind auch möglich).
-
Dieses
Beispiel eines Algorithmus kann durch den nachfolgenden Pseudocode
implementiert werden:
-
Die
Berechnung der Linkgewichtungen nach der zweiten Ausführungsform
ist wie in dem ersten Code beschrieben, aber die Kanalgewichtungen
werden anders berechnet. Der Gedanke hinter dieser Kanalgewichtungsformel
ist, die Planung mit den Kanälen
zu starten, was mehr Schlitze erfordert, da diese durch oft verwendete
Links hindurch gehen, d. h. durch heiße Stellen hindurch gehend
(Links mit einer hohen Belastung und folglich einen großen Schlitz
zum Reservieren), und durch Kanäle
mit langen Strecken mit einer höheren Gewichtung,
so dass sie zuerst geplant werden. Der Grund ist, dass diese Verbindungen
mehr Beschränkungen
haben, und deswegen, wenn an dem Ende gelassen, weniger Möglichkeiten
haben, freie Schlitze zu finden. Im Gegensatz dazu haben kürzere Kanäle, die
durch weniger verwendete Links gehen, mehr Freiheit beim Finden
von Schlitzen, und können
auf diese Weise in der Nähe
des Endes der Schlitzzuordnung gelassen werden.
-
Schlitze
können
den Kanälen
zugeordnet werden (d. h. jeder Verbindungsstrecke) in der abnehmenden
Reihenfolge deren berechneter Gewichtungen. Für jeden beantragten Schlitz
wird ein einziger Schlitz in jeder Schlitztabelle der Links längs der
Kanalstrecke reserviert, wie in 2 dargestellt.
All diese Schlitze müssen
frei sein, d. h. nicht vorher von anderen Kanälen (d. h. jeder Verbindungsstrecke)
reserviert. Diese Schlitze werden durch Ausprobieren zugeordnet:
ausgehend von einem bestimmten Schlitz, werden Schlitze überprüft, bis
gefunden worden ist, dass die erforderliche Anzahl Schlitze in allen
Links längs
der Strecke frei sind. In dem nachfolgenden Abschnitt wird ein Beispiel
einer Algorithmusspur dargestellt.
-
9 zeigt
ein Verfahren zum Finden freier Zeitschlitze. Hier ist als Beispiel
eine Schlitztabelle der Größe 16 dargestellt.
Der Prozess, Schlitze zu finden, kann verschiedenartig durchgeführt werden.
Ein Beispiel ist das Finden von Schlitzen auf eine habgierige Weise,
d. h. die ersten N freien Schlitze. Ein anderes Beispiel ist das
Finden von Schlitzen, die in gleichen Abständen voneinander liegen, damit
der Pufferraum minimiert wird. Dies kann dadurch erfolgen, dass
ein erster freier Schlitz ffs gefundne wird, dass danach die Positionen
berechnet werden, die in einem gleichen Abstand in der Schlitztabelle
liegen, und dass daraufhin örtlich
die berechneten Positionen gesucht werden um die nächst freie
Position zu finden. Die Schlitze, die bereits reserviert sind, sind
in 9 mit einem Kreuz gemerkt. Der erste freie Schlitz
ffs ist der Schlitz 2. Da es 16 Schlitze gibt, sind die idealen
Positionen (die 2. Position ip2, die 3. Position ip3) für die anderen
zwei Schlitze der Schlitz 7 und 13 (um einen gleichen Abstand zwischen
denselben zu erhalten). Da der Schlitz 7 bereits reserviert ist,
wird in der Nähe
des Schlitzes 7 nach einem freien Schlitz gesucht. Der nächst gefundene
freie Schlitz ist der Schlitz 5. Auch der Schlitz 13 ist frei, und
dieser kann auch reserviert werden. Folglich sind die drei reservierten
Schlitze 2, 5 und 13 und sind mit einer schwarzen Kugel gemerkt.
-
Es
sei bemerkt, dass freie Schlitze für eine Verbindung diejenigen
sind, die längs
der ganzen Strecke frei sind, d. h. aufeinander folgende Zeitschlitze
sollen in aufeinander folgenden Links längs der Strecke frei sein.
Deswegen müssen
alle Schlitztabellen längs
einer Verbindungsstrecke geprüft
werden um einen freien Schlitz für
eine bestimmte Verbindung zu finden. Eine einfache Art und Weise,
freie Schlitze für
eine Verbindung zu finden ist, von dem ersten Link der Verbindung
zu starten und alle nachfolgenden Schlitztabellen längs der
Strecke zu versuchen, wobei die reservierten übersprungen werden. Um die
Suchzeit zu minimieren kann man auch von dem am schwersten belasteten
Link aus starten.
-
10 zeigt
eine andere Technik um die Suche nach freien Schlitzen zu beschleunigen,
und zwar für den
Fall, dass nur die Schlitzreservierung gespeichert ist (unter Verwendung
von nur 1 Bit), wie in 5 beschrieben. Die Basis dabei
ist die parallele Überprüfung vieler
Schlitze. Dies kann in Hardware (eine Einheit zum Überprüfen jeder
beliebigen festen Anzahl Bits, d. h. die Zeitschlitzzuordnungseinheit
SSA) und in Software (CPU Datenwörter
können
beispielsweise 16 oder 32 Schlitzreservierungen simultan speichern)
durchgeführt
werden. Auf der linken Seite der 10 sind
Schlitztabellen 1st für Links
L1 bis L4 als Beispiel dargestellt. Auf der rechten Seite sind freie
Schlitzwörter
fsw dargestellt, die zum Ermitteln der freien Schlitze längs der
Strecke dargestellt sind. Freie Schlitze werden dadurch gefunden,
dass die Schlitztabellen durchstöbert werden
und dass die reservierten gefiltert werden, und die gesuchten Schlitze
mit einer einzigen Position bei jedem Link verschoben werden (≫(1)) (entsprechend
der erforderlichen Schlitzausrichtung). Erstens wird der erste Link
L1 der Strecke gewählt,
der reservierte Schlitze 0, 1, 6, 9, 11, 12 und 14 aufweist. Diese
Schlitze sind als reserviert gemerkt, beispielsweise durch ein "X" in dem freien Schlitzwort. Danach wird
das freie Schlitzwort fsw um eine Position nach rechts verschoben
um die Schlitzausrichtung zu widerspiegeln, und wird Ge-OR-ed, d.
h. es wird ein ODER-Vorgang durchgeführt, um die reservierten Schlitze
des zweiten Links (Schlitze 3, 6, 10 und 12) hinzuzufügen. Diese
Schritte werden für
den dritten und vierten Link L3, L4 wiederholt, was zu einem Vektor
freier Schlitze in allen Links längs
der Strecke führt.
Um dies zu dem ersten Link L1 auszurichten wird er um drei Positionen
nach links verschoben. Das Ergebnis ist, dass die Schlitze 4, 8,
10 und 13 des ersten Links L1 in allen Links L1–L4 längs der bestimmten Strecke
frei sind. Insbesondere ist der Schlitz 4 für den Link L1 frei, während die
Schlitze 5, 6 und 7 für
die Links L2, L3 bzw. L4 frei sind. Der Schlitz 8 ist in dem Link
L1 frei, während
die Schlitze 9, 10 und 11 für
die Links L2, L3 bzw. L4 frei sind. Außerdem ist der Schlitz 10 in
dem Link L1 frei, während
die Schlitze 11, 12 und 13 für
die Links L2, L3 bzw. L4 frei sind. Der Schlitz 13 ist in dem Link
L1 frei, während
die Schlitze 14, 15 und 1 für
die Links L2, L3 bzw. L4 frei sind.
-
11 zeigt
ein Beispiel eines Netzwerkes an Chip, bestehend aus 4 Routern R1–R4 und
7 Netzwerkschnittstellen NI(NI1–NI7).
Der IP Block, mit dem die Netzwerkschnittstellen verbunden sind,
sind nicht dargestellt. Als Beispiel sind 12 Verbindungen C1–C12 selektiert.
Diese Verbindungen werden verwendet zum Transportieren von Daten
zwischen (den nicht dargestellten) IP Modulen, die an die Netzwerkschnittstellen
NIs angehängt
sind, und deswegen sind die Verbindungen immer zwischen zwei Netzwerkschnittstellen
NIs vorgesehen. Der Einfachheit halber wird vorausgesetzt, dass
alle Verbindungen unidirektional sind (bestehend aus nur einem einzigen
Kanal), obschon es in der Praxis auch bidirektionale Verbindungen
(zwei Kanäle)
geben kann. So startet beispielsweise die Verbindung C1 bei NI1,
und geht über
R1 und R4 um NI6 zu erreichen. Auf gleiche Weise geht die Verbindung
C2 über
NI1, R1, R2, R3 und NI4. Die Verbindung C3 geht über NI1, R1, R2 und NI2. Die
Verbindung C4 geht über
NI2, R2, R3, R4 und NI7. Die Verbindung C5 geht über NI2, R2 und NI3. Die Verbindung
C6 geht über
NI3, R2, R1 und NI1. Die Verbindung C7 geht über NI3, R2, R3 und NI5. Die
Verbindung C8 geht über
NI4, R3 und NI5. Die Verbindung C9 geht über NI5, R3, R4, R1 und NI1.
Die Verbindung C10 geht über
NI6, R4, R3, R2 und NI2. Die Verbindung C11 geht über NI7,
R4, R3, R2 und NI3. Die Verbindung C12 geht über NI7, R4, R1 und NI1. Für jede Verbindung
muss eine Anzahl Schlitze reserviert werden. Diese Anzahlen sind
auf der rechten Seite in 9 aufgelistet, d. h. die Verbindungen
C1–C12
erfordern 1, 1, 5, 2, 4, 3, 2, 6, 1, 2, 1 bzw. 2 Schlitze.
-
12 zeigt
ein Netzwerk an Chip nach 11. Der
Algorithmus startet durch Berechnung der Linkgewichtungen. Dies
geschieht dadurch, dass für
jeden Link die Anzahl für
alle diesen Link benutzenden Verbindungen beantragter Schlitze summiert
werden. Dies geschieht für
jede Richtung separat. Die Links sind umkreis und ein Linkgewichtungsergebnis
ist daneben angegeben. So werden beispielsweise für den Link
von R2 zu R3 die von den Verbindungen C2, C4 und C7 beantragten
Schlitze addiert. Dies führt
zu einer Linkgewichtung von 1(C2) + 2(C4) + 2(C7) = 5. Der Link
zwischen NI1 und R1 erfordert 7 Schlitze, der Link zwischen R1 und
NI1 6 Schlitze usw. Der Algorithmus berechnet die Verbindungsgewichtungen.
In der Verbindungsgewichtungsformel ist a1 = 1, a2 = 0 und a3 =
0 (d. h. Summierung der Linkgewichtungen). Auf alternative Weise
können
verschiedene Werte selektiert werden. Das Ergebnis der Verbindungsgewichtung
ist auf der rechten Seite in 11 dargestellt.
So ist beispielsweise die Gewichtung der Verbindung C1 die Summe
der Gewichtungen der Links NI1 zu R1, von R1 zu R4 und von R4 zu
NI10, was 7 + 1 + 1 = 9 ist. Die Verbindungen werden danach ablaufend
in Bezug auf den berechneten Gewichtungsfaktor berechnet, und in
dieser Reihenfolge geplant.
-
In 13 ist
die Zeitschlitzzuordnung für
alle Verbindungen C1–C12
dargestellt. Es wird vorausgesetzt, dass erstens die erforderlichen
freien Schlitze zugeordnet werden. So haben beispielsweise die Schlitztabellen
eine Größe von 9
Schlitzen. Die dargestellten Anzahlen in den Schlitztabellen entsprechen
den betreffenden Verbindungen C1–C12, denen diese Schlitze
zugeordnet wurden.
-
Für die Verbindung
C3, die 5 Schlitze erfordert, sind alle Schlitze frei, und folglich
die Schlitze 1 bis 5 des Links NI1 zu R1, die Schlitze 2–6 des Links
R1 zu R2, und die Schlitze 3–8
de Links R2 zu NI2 werden zugeordnet. Für die Verbindung C2, die einen
einzigen Schlitz erfordert, sind die ersten 5 Schlitze bereits in dem
ersten Link reserviert und folglich reserviert er die Schlitze 6,
7, 8 und 9 in den betreffenden Schlitztabellen längs der Strecke. Die Verbindung
C7, die 2 Schlitze erfordert, hat keine Konflikte in den ersten
zwei Schlitzen, und ordnet sie folglich zu. Die Verbindung C4, die
2 Schlitze erfordert, kann nur die Schlitze 3 und 4 reservieren,
da die erste zwei für
C7 in dem zweiten Link (R2 zu R3) reserviert sind. Die Verbindung
C11 hat wieder keine Konflikte, und reserviert den ersten Schlitz
in der Schlitztabelle in dem Link der Netzwerkschnittstelle NI7 und
den Router R4 sowie die nachfolgenden Schlitze in den Schlitztabellen
in den anderen Links.
-
Im
Falle der Verbindung C10, die 2 Schlitze erfordert, streiten sich
die ersten 4 Schlitze mit den für
C3 reservierten Schlitzen in dem Link R2 zu NI2, und folglich sind
die ersten freien Schlitze die Schlitze 5 und 6. Die Verbindung
C6 ordnet drei Schlitze zu, und zwar die Schlitze 3–5, in dem
Link der Netzwerkschnittstelle NI3 und des Routers R2; die Schlitze
4–6 in
der Schlitztabelle des Links von dem Router R2 zu dem Router R1;
und die Schlitze 5–7
in der Schlitztabelle des Links von dem Router R1 zu der Netzwerkschnittstelle
NI1. Die Verbindung C8 ordnet 6 Schlitze zu, und zwar die Schlitze
1, 4–8,
in dem Link von der Netzwerkschnittstelle NI4 zu dem Router R3;
und die Schlitze 2, 5–9
in der Schlitztabelle des Links von dem Router R3 zu der Netzwerkschnittstelle
NI5, da die Schlitze 3–4
in der Schlitztabelle des Links von dem Router R3 und der Netzwerkschnittstelle
NI5 bereits der Verbindung 7 zugeordnet oder für dieselbe reserviert sind.
-
Die
Verbindung C9 ordnet einen einzigen Schlitz, und zwar die Schlitze
1, in dem Link der Netzwerkschnittstelle NI5 und des Routers R3;
den Schlitz 2 in der Schlitztabelle des Links des Routers R3 und
des Routers R4; den Schlitz 3 in der Schlitztabelle des Links des
Routers R4 und des Routers R5; und den Schlitz 4 in der Schlitztabelle
in dem Link des Routers R1 und der Netzwerkschnittstelle NI1. Die
Verbindung C12 ordnet zwei Schlitze zu, und zwar die Schlitze 6–6 in dem
Link der Netzwerkschnittstelle NI7 und des Routers R4; die Schlitze
7–8 in
dem Link des Routers R4 und des Routers R1; und die Schlitze 8–9 in der
Schlitztabelle des Links des Routers R1 und der Netzwerkschnittstelle
NI1, da der Schlitz 4 und die Schlitze 5–7 in der Schlitztabelle des
Links des Routers R1 und der Netzwerkschnittstelle NI1 bereits der
Verbindung C9 bzw. C6 zugeordnet sind.
-
Die
Verbindung C5 ordnet 4 Schlitze zu, und zwar die Schlitze 1–2 und 5–6, in der
Schlitztabelle des Links der Netzwerkschnittstelle NI2 und des Routers
R2; und die Schlitze 2–3
und 6–7
in der Schlitztabelle des Links des Routers R2 und der Netz- Werkschnittstelle
NI3, da die Schlitze 3–4
in der Schlitztabelle des Links der Netzwerkschnittstelle NI2 und
des Routers R2 bereits der Verbindung C4 zugeordnet wurden. Zum
Schluss ordnet die Verbindung C1 einen einzigen Schlitz, und zwar
den Schlitz 7, in der Schlitztabelle des Links der Netzwerkschnittstelle
NI1 und des Routers R1 zu; den Schlitz 8 in der Schlitztabelle des
Links des Routers R1 und des Routers R4; und den Schlitz in der
Schlitztabelle des Links des Routers R4 und der Netzwerkschnittstelle
NI6. Auf entsprechende Weise ist das Endergebnis der Schlitzzuordnung
in 13 dargestellt.
-
Nachdem
die Schlitztabellenzuordnung durchgeführt worden ist, kann die Ermittlung
der noch immer nicht benutzten Bits auf dieselbe Art und Weise wie
oben beschrieben, durchgeführt
werden, und zwar zum Identifizieren derjenigen Zeitschlitze, die
zur Latenzreduktion durch Zuordnung dieser Zeitschlitze zu wenigstens
einer der Verbindungen verwendet werden können.
-
Obschon
oben stehend die Zeitschlitzzuordnungseinheit als in den Netzwerkschnittstellen
vorgesehen beschrieben worden ist, kann die Zeitschlitzzuordnungseinheit
auch in den Routern innerhalb des Netzwerkes vorgesehen sein.
-
Die
oben beschriebene Zeitschlitzzuordnung kann auf jede beliebige Datenverarbeitungsanordnung mit
verschiedenen separaten integrierten Schaltungen oder Mehrchip-Netzwerken
abgewandt werden, und nicht nur auf ein Netzwerk auf einem einzigen
Chip.
-
Es
sei bemerkt, dass die oben genannten Ausführungsformen die vorliegende
Erfindung illustrieren statt begrenzen, und dass der Fachmann imstande
sein wird, im Rahmen der beiliegenden Patentansprüche viele
alternative Ausführungsformen
zu entwerfen. In den Patentansprüchen
sollen eingeklammerte Bezugszeichen nicht als den Anspruch begrenzend
betrachtet werden. Das Wort "umfassen" schließt das Vorhandensein
von Elementen oder Verfahrensschritte anders als diejenigen, die
in den Ansprüchen
genannt sind, nicht aus. Das Wort "ein" vor
einem Element schließt
das Vorhandensein einer Anzahl derartiger Elemente nicht aus. In
dem Anordnungsanspruch, in dem verschiedene Mittel nummeriert sind,
können
verschiedene dieser Mittel von ein und demselben Hardware-Item implementiert
sein. Die Tatsache, dass bestimmte Maßnahmen in untereinander verschiedenen
Unteransprüchen
genannt worden sind, gibt nicht an, dass eine Kombination dieser
Maßnahmen
nicht mit Vorteil angewandt werden könnte.
-
Weiterhin
sollen Bezugszeichen in den Patentansprüchen nicht als den Rahmen der
Patentansprüche beschränkend betrachtet
werden.