Static and dynamic virtual channel allocation for high performance, in-order communication in on-chip networks

Most routers in on-chip interconnection networks (OCINs) have multiple virtual channels (VCs) to mitigate the effects of head-of-line blocking. Multiple VCs necessitate VC allocation schemes since packets or flows must compete for channels when there are more flows than virtual channels at a link. Conventional dynamic VC allocation, however, raises two critical issues. First, it still suffers from a fair amount of head-of-line blocking since all flows can be assigned to any VC within a link. Moreover, dynamic VC allocation compromises the guarantee of in-order delivery even when used with basic variants of dimension-ordered routing, requiring large reorder buffers at the destination core or, alternatively, expensive retransmission logic. In this thesis, we present two virtual channel allocation schemes to address these problems: Static Virtual Channel Allocation and Exclusive Dynamic Virtual Channel Allocation (EDVCA). Static VC allocation assigns channels to flows by precomputation when oblivious routing is used, and ensures deadlock freedom for arbitrary minimal routes when two or more VCs are available. EDVCA, on the other hand, is done at runtime, not requiring knowledge of traffic patterns or routes in advance. We demonstrate that both static VCA and EDVCA guarantee in-order packet delivery under single path routing, and furthermore, that they both outperform dynamic VC allocation (out-of-order) by effectively reducing head-of-line blocking. We also introduce a novel bandwidth-sensitive oblivious routing scheme (BSORM), which is deadlock-free through appropriate static VC allocation. Implementation for these schemes requires only minor, inexpensive changes to traditional oblivious dimension-ordered router architectures, more than offset by the removal of packet reorder buffers and logic.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2010

Author dc:creator

• Shim, Keun Sup

Advisor dc:contributor.advisor

• Srinivas Devadas.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/60185

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/60185