A Deadlock-free Routing Algorithm for Dynamically Reconfigurable Networks-on-Chip

Chris R Jackson, SJ Hollis

Research output: Contribution to journalArticle (Academic Journal)peer-review

16 Citations (Scopus)


We address routing in Networks-On-Chip (NoC) architectures that use irregular mesh topologies with Long-Range Links (LRL). These topologies create difficult conditions for routing algorithms, as standard algorithms assume a static, regular link structure and exploit the uniformity of regular meshes to avoid deadlock and maintain routability. We present a novel routing algorithm that can cope with these irregular topologies and adapt to run-time LRL insertion and topology reconfiguration. Our approach to accommodate dynamic topology reconfiguration is to use a new technique that decomposes routing relations into two stages: the calculation of output ports on the current minimal path and the application of routing restrictions designed to prevent deadlock. In addition, we present a selection function that uses local topology data to adaptively select optimal paths. The routing algorithm is shown to be deadlock-free, after which an analysis of all possible routing decisions in the region of an LRL is carried out. We show that the routing algorithm minimises the cost of sub-optimally placed LRL and display the hop savings available. When applied to LRLs of less than seven hops, the overall traffic hop count and associated routing energy cost is reduced. In a simulated 8 × 8 network the total input buffer usage across the network was reduced by 6.5%.
Translated title of the contributionA Deadlock-free Routing Algorithm for Dynamically Reconfigurable Networks-on-Chip
Original languageEnglish
Pages (from-to)139-151
Number of pages32
JournalMicroprocessors and Microsystems
Issue number2
Publication statusPublished - Sept 2010

Bibliographical note

Publisher: Elsevier
Other: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0X-512K1S9-1&_user=121739&_coverDate=09%2F21%2F2010&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1570984769&_rerunOrigin=google&_acct=C000010018&_version=1&_urlVersion=0&_userid=121739&md5=23b27d04017413ac7ab38b93eb1ea6fd&searchtype=a


Dive into the research topics of 'A Deadlock-free Routing Algorithm for Dynamically Reconfigurable Networks-on-Chip'. Together they form a unique fingerprint.

Cite this