Fault-aware load-balancing routing for 2D-mesh and torus on-chip network topologies

Pengju Ren, Michel A. Kinsy, Nanning Zheng

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


Routing algorithm design for on-chip networks (OCNs) has become increasingly challenging due to high levels of integration and complexity of modern systems-on-chip (SoCs). The inherent unreliability of components, embedded oversized IP blocks, and fine-grained voltage-frequency islands (VFIs) management among others, raise several challenges in OCNs: (a) network topologies become irregular or asymmetric making circular route dependencies that lead to deadlock hard to detect; and (b) routing algorithms that lack strong load-balancing properties often saturate prematurely. In order to address the aforementioned deadlock and load-balancing problems, we propose the traffic balancing oblivious routing (TBOR) algorithm. It is a two-phase routing algorithm consisting of: (1) construction of the weighted acyclic channel dependency graph (CDG) for the OCN to efficiently maximize available resource utilization; and (2) channel ordering across turn models to keep the underlying CDG cycle-free to guarantee deadlock-freedom using one or more turn-models. Channel bandwidth utilization and traffic balancing are achieved through static virtual channel allocation according to residual bandwidth of healthy links. In addition, we introduce in this work two schemes of different granularity of fault detection and analysis while guaranteeing in-order packet delivery by assigning a unique path to each flow. Extensive experiments demonstrate the proposed routing methodology outperforms previous algorithms.

Original languageEnglish (US)
Article number7115095
Pages (from-to)873-887
Number of pages15
JournalIEEE Transactions on Computers
Issue number3
StatePublished - Mar 1 2016
Externally publishedYes


  • channel dependency graph.
  • Fault-tolerant routing
  • irregular network
  • load balance
  • resource utilization

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Fault-aware load-balancing routing for 2D-mesh and torus on-chip network topologies'. Together they form a unique fingerprint.

Cite this