TU Darmstadt / ULB / TUbiblio

Microarchitecture and Implementation of Networks-on-Chip with a Flexible Concept for Communication Media Sharing

Samman, Faizal Arya (2010)
Microarchitecture and Implementation of Networks-on-Chip with a Flexible Concept for Communication Media Sharing.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

This thesis proposes a concept, VLSI microarchitecture and implementation of a network on-chip (NoC) supporting a flexible communication media share methodology. The concept and methodology are based on a variable dynamic local identity tag (ID-tag) management technique, where different messages can be interleaved at flit-level on the same communication channel. Each message is multiplexed and allocated to a local ID slot on the shared channel. In order to implement the concept and methodology, a special packet format will be introduced, where additional two control bit fields, i.e. an ID-tag field and a flit-type field, are attached on every flit of the message in line with a data word. The reserved ID slot number, to which the message is allocated, is attributed in the ID-tag field. The flit-type field together with the ID-tag field is used to identify the messages and the type of every message flit, and to control the behavior of certain components in the NoC switch (NoC router) at runtime (during application execution time). The type of the flits is classified into a header used to open the ID-tag reservation, a databody, or a tail flit that is used to terminate the ID-tag reservation. When entering a new communication channel, the ID-tag of a message is updated. Each message is allocated to a new local ID slot and organized in such a way, that flits belonging to the same message will have the same ID-tag on every communication channel. Therefore, an ID management unit is integrated in a switch multiplexor component at every output port of the NoC router to organize the ID-tag reservation or the ID slot allocation procedure. In order to guarantee a correct routing path configuration at runtime, a routing engine component consisting of a routing state machine and a routing reservation table is implemented on each input port. The routing engine routes the interleaved different messages based on their ID-tag. The proposed concept and methodology have impacts on the implementation of advantageous and extensive features in the NoC router compared with the existing NoC concepts presented in the literature. The basic advantageous application of the proposed concept and methodology is the ability to implement a new wormhole switching method called wormhole flit-level cut-through switching method to overcome the head-of-line blocking problems commonly occur when using traditional wormhole switching method. The problem is solved by allowing the flits of the competing wormhole messages to be interleaved at flit level in the same communication link without using virtual channels. The proposed concept allows us to implement a new deadlock-free tree-based multicast routing methodology with static or adaptive routing algorithm, where the routing engines used to route the unicast and multicast messages are the same, resulting in a low-area overhead multicast routing engine. The thesis introduces also a new theory for deadlock-free multicast routing suitable for NoCs. The theory is formulated based on a new simple and smart mechanism to handle multicast contentions called hold-release tagging mechanism. The multicast deadlock configuration problem in the tree-based multicast routing is solved without the use of virtual channels. Beside (1) the new wormhole switching method and (2) the new deadlock-free multicast routing method mentioned before, the proposed concept allow us, (3) to develop a new adaptive routing selection strategy (contention- and bandwidth-aware adaptive routing selection strategy), (4) to develop a switched virtual circuit configuration method based on the ID-division multiple access technique for implementing a runtime connection-oriented guaranteed-bandwidth service, and (5) to combine the connectionless best-effort and the connection-oriented guaranteed-bandwidth services in a single NoC router prototype. This doctoral thesis introduces in general a NoC router prototype called XhiNoC (eXtendable Hierarchical Network-on Chip). The VLSI microarchitecture of the XhiNoC routers is flexible and extendable, in which the generic components of the NoC router can be simply replaced by extended components. If needed, a number of new signal paths is added. Hence, a new NoC router prototype with the aforementioned extensive services, such as adaptive routing service, multicast routing service and connection-oriented guaranteed-bandwidth service can be designed from the basic VLSI microarchitecture of the XHiNoC Router.

Typ des Eintrags: Dissertation
Erschienen: 2010
Autor(en): Samman, Faizal Arya
Art des Eintrags: Erstveröffentlichung
Titel: Microarchitecture and Implementation of Networks-on-Chip with a Flexible Concept for Communication Media Sharing
Sprache: Englisch
Referenten: Glesner, Prof. Dr. Manfred ; Eveking, Prof. Dr.- Hans
Publikationsjahr: 7 August 2010
Datum der mündlichen Prüfung: 8 Juni 2010
URL / URN: urn:nbn:de:tuda-tuprints-22566
Zugehörige Links:
Kurzbeschreibung (Abstract):

This thesis proposes a concept, VLSI microarchitecture and implementation of a network on-chip (NoC) supporting a flexible communication media share methodology. The concept and methodology are based on a variable dynamic local identity tag (ID-tag) management technique, where different messages can be interleaved at flit-level on the same communication channel. Each message is multiplexed and allocated to a local ID slot on the shared channel. In order to implement the concept and methodology, a special packet format will be introduced, where additional two control bit fields, i.e. an ID-tag field and a flit-type field, are attached on every flit of the message in line with a data word. The reserved ID slot number, to which the message is allocated, is attributed in the ID-tag field. The flit-type field together with the ID-tag field is used to identify the messages and the type of every message flit, and to control the behavior of certain components in the NoC switch (NoC router) at runtime (during application execution time). The type of the flits is classified into a header used to open the ID-tag reservation, a databody, or a tail flit that is used to terminate the ID-tag reservation. When entering a new communication channel, the ID-tag of a message is updated. Each message is allocated to a new local ID slot and organized in such a way, that flits belonging to the same message will have the same ID-tag on every communication channel. Therefore, an ID management unit is integrated in a switch multiplexor component at every output port of the NoC router to organize the ID-tag reservation or the ID slot allocation procedure. In order to guarantee a correct routing path configuration at runtime, a routing engine component consisting of a routing state machine and a routing reservation table is implemented on each input port. The routing engine routes the interleaved different messages based on their ID-tag. The proposed concept and methodology have impacts on the implementation of advantageous and extensive features in the NoC router compared with the existing NoC concepts presented in the literature. The basic advantageous application of the proposed concept and methodology is the ability to implement a new wormhole switching method called wormhole flit-level cut-through switching method to overcome the head-of-line blocking problems commonly occur when using traditional wormhole switching method. The problem is solved by allowing the flits of the competing wormhole messages to be interleaved at flit level in the same communication link without using virtual channels. The proposed concept allows us to implement a new deadlock-free tree-based multicast routing methodology with static or adaptive routing algorithm, where the routing engines used to route the unicast and multicast messages are the same, resulting in a low-area overhead multicast routing engine. The thesis introduces also a new theory for deadlock-free multicast routing suitable for NoCs. The theory is formulated based on a new simple and smart mechanism to handle multicast contentions called hold-release tagging mechanism. The multicast deadlock configuration problem in the tree-based multicast routing is solved without the use of virtual channels. Beside (1) the new wormhole switching method and (2) the new deadlock-free multicast routing method mentioned before, the proposed concept allow us, (3) to develop a new adaptive routing selection strategy (contention- and bandwidth-aware adaptive routing selection strategy), (4) to develop a switched virtual circuit configuration method based on the ID-division multiple access technique for implementing a runtime connection-oriented guaranteed-bandwidth service, and (5) to combine the connectionless best-effort and the connection-oriented guaranteed-bandwidth services in a single NoC router prototype. This doctoral thesis introduces in general a NoC router prototype called XhiNoC (eXtendable Hierarchical Network-on Chip). The VLSI microarchitecture of the XhiNoC routers is flexible and extendable, in which the generic components of the NoC router can be simply replaced by extended components. If needed, a number of new signal paths is added. Hence, a new NoC router prototype with the aforementioned extensive services, such as adaptive routing service, multicast routing service and connection-oriented guaranteed-bandwidth service can be designed from the basic VLSI microarchitecture of the XHiNoC Router.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Diese Dissertation stellt ein Konzept für eine VLSI-Mikroarchitektur und Implementierung eines On-Chip Netwerks vor, welches eine flexible Nutzung von Routing-Ressourcen unterstützt. Das Konzept und die Methodologie basieren auf einer variablen lokalen Identität (ID-Tag) von Datenpaketen auf den einzelnen Segmenten des Routing-Netzwerks, wodurch eine gleichzeitige gefaltete Übertragung (Interleaving) mehrerer Datenpakete auf einem Datensegment ermöglicht wird. Hierfür wurde ein spezielles Format für die Flits eines Datenpakets entworfen, welches als zusätzliche Steuerungsinformationen für den Datenfluss Informationen über den Pakettyp und die lokale ID (ID-Tag) des Pakets auf dem aktuell betrachteten Routing-Segment enthält. Mit diesen Zusatzinformationen wird das Verhalten der On-Chip Router des Network-on-Chip (NoC) lokal gesteuert. Datenpakete bestehen aus Datenheader, Payload und einem Deskriptor für das Ende des Pakets. Wenn ein Router einen Datenheader empfängt, trifft die aus einer kombinierten Routing-Zustandsmaschine und einer Routingtabelle bestehende Routing-Engine am Eingang des Routers eine Entscheidung für die Richtung der Weiterleitung des Pakets und ein eingebauter ID-Manager ordnet dem Paket eine freie ID auf dem ausgehenden Routing-Segment zu. Alle nachfolgenden Flits des Datenpakets werden über deren ID auf dem Dateneingangssegment erkannt, automatisch auf dieses Ausgangs-Routingsegment geschaltet (Switching) und mit derselben lokalen ID versehen, die auch dem Header des Pakets zugeordnet wurde. Passiert ein Paketende einen Router, so wird die für das Paket verwendete lokale ID wieder freigegeben. Die ID-Verwaltung und -Vergabe wird mit Hilfe eines Steuerungsmoduls realisiert, das in den Multiplexern des On-Chip Routers integriert ist. Im Vergleich zu Konzepten der anderer bekannter On-Chip Netzwerke, haben das vorgeschlagene Konzept und die implementierte Methodologie Vorteile im Hinblick auf eine effiziente Implementierung der On-Chip-Router. Basierend auf dem vorgeschlagenen Konzept können Wormhole-Routingverfahren mit wesentlicher Reduktion der hierbei üblichen Warteschlangen-Blockierungsprobleme implementiert werden. Flits verschiedener Datenpakete können auf dem gleichen Übertragungskanal gemischt werden, wofür keine expliziten virtuellen Datenkanäle benötigt werden, was zu einer erheblichen Reduktion der Größe von Datenpuffern führt. Das vorgeschlagene Konzept ermöglicht es weiterhin, eine blockierungsfreie Multicast-Routingsmethode mit einem statischen oder adaptiven Routingsalgorithmus zu implementieren. In der vorliegen Dissertationsschrift wird auch eine neue blockierungsfreie Multicastroutingstheorie vorgestellt, die sich für On-Chip Netzwerke eignet und auf dem beschriebenen Grundkonzept basiert. Die hiervon abgeleitete Methodik ist als sogenannter “Hold-Release-Tagging-Mechanismus” implementiert, und löst das Problem einer möglichen gleichzeitigen Konkurrenz von Datenwörtern um eine bestimmte Ausgangsressource eines Netzwerkrouters. Letzteres stellt insbesondere bei Multicast-Datenkommunikation ein schwerwiegendes Problem dar und wird hier ohne Verwendung virtueller Kanäle gelöst. Neben (1) der neuen Wormhole-Paketvermittlungsmethode und (2) dem neuen Multicastroutingverfahren, wird unter Verwendung des vorgeschlagenen Konzepts ermöglicht, (3) eine lastabhängige Bandbreitensteuerung lokal in den Routern vorzunehmen, (4) virtuelle Leitungsverbindungen ohne Notwendigkeit einer zentralen Steuereinheit für die Bereitstellung einer verbindungsorientierten Datenübertragung (Quality of Service) bereitzustellen, und (5) kombinierte verbindungslose (Datenpakete) und verbindungsorientierte (Streaming) Datenübertragung in einem on-Chip Router zu implementieren. In dieser Dissertation wird die NoC-Prototypenarchitektur XHiNoC (eXtendable Hierarchical Network-on Chip) vorgestellt. Die VLSI-Mikroarchitektur des XHiNoC-Routers ist flexibel und erweiterbar, wobei die generische Komponenten des NoC Routers einfach mit anderen erweiterten Komponenten ersetzt werden können. Daher können problemlos neue NoC-Routerprototypen generiert werden, die zusätzliche Dienste, wie die oben genannten Dienste (adaptive Routingsverfahren, Multicast-Routingsverfahren oder verbindungsorientierte Datenübertragung mit Bandbreitengarantie) bereitstellen. Basierend auf der XHiNoC-Architektur können in kürzester Zeit bedarfsangepasste Router erstellt werden, die nur die benötigten Dienste bei minimiertem Overhead abbilden. Da die ganze Architektur auf einen globalen Controller verzichtet, ist sie beliebig skalierbar. Aufgrund der verwendeten Steuerung der Dateninjektion werden die im Netzwerk injizierten Datenmengen der verfügbaren Übertragungskapazität angepasst, womit eine wesentliche Reduktion der Datenpuffer und routerinternen Steuerungsmechanismen einhergeht.

Deutsch
Schlagworte:
Einzelne SchlagworteSprache
Network-on-ChipEnglisch
VLSI MicroarchitectureEnglisch
Wormhole Cut-Through SwitchingEnglisch
Theory for Deadlock-Free Multicast RoutingEnglisch
Tree-based Multicast RoutingEnglisch
Runtime Adaptive Routing Selection StrategyEnglisch
Contention- and Bandwidth-Aware Adaptive RoutingEnglisch
Connection-Oriented CommunicationEnglisch
Guaranteed-Bandwidth ServiceEnglisch
Zusätzliche Informationen:

Tag der Einreichung: 26.01.2010

Sachgruppe der Dewey Dezimalklassifikatin (DDC): 600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften und Maschinenbau
600 Technik, Medizin, angewandte Wissenschaften > 600 Technik
Fachbereich(e)/-gebiet(e): 18 Fachbereich Elektrotechnik und Informationstechnik > Mikroelektronische Systeme
18 Fachbereich Elektrotechnik und Informationstechnik
Hinterlegungsdatum: 14 Aug 2010 11:33
Letzte Änderung: 05 Mär 2013 09:36
PPN:
Referenten: Glesner, Prof. Dr. Manfred ; Eveking, Prof. Dr.- Hans
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 8 Juni 2010
Schlagworte:
Einzelne SchlagworteSprache
Network-on-ChipEnglisch
VLSI MicroarchitectureEnglisch
Wormhole Cut-Through SwitchingEnglisch
Theory for Deadlock-Free Multicast RoutingEnglisch
Tree-based Multicast RoutingEnglisch
Runtime Adaptive Routing Selection StrategyEnglisch
Contention- and Bandwidth-Aware Adaptive RoutingEnglisch
Connection-Oriented CommunicationEnglisch
Guaranteed-Bandwidth ServiceEnglisch
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen