Imperial College London

Professor Peter Y. K. Cheung

Faculty of EngineeringDyson School of Design Engineering

Head of the Dyson School of Design Engineering



+44 (0)20 7594 6200p.cheung Website




Mrs Wiesia Hsissen +44 (0)20 7594 6261




910BElectrical EngineeringSouth Kensington Campus






BibTex format

author = {Mak, T and Cheung, PYK and Luk, W and Lam, KP},
doi = {10.1145/1629435.1629452},
pages = {119--127},
title = {A DP-network for optimal dynamic routing in network-on-chip},
url = {},
year = {2009}

RIS format (EndNote, RefMan)

AB - Dynamic routing is desirable because of its substantial improvement in communication bandwidth and intelligent adaptation to faulty links and congested traffics. However, implementation of adaptive routing in a network-on-chip (NoC) system is not trivial and further complicated by the requirements of deadlock-free and real-time optimal decision making. In this paper, we present a deadlock-free routing architecture which employs a dynamic programming (DP) network to provide on-the-fly optimal path planning and network monitoring for packet switching. Also, a new routing strategy called k-step look ahead is introduced. This new strategy can substantially reduced the size of routing table and maintain a high quality of adaptation which leads to a scalable dynamic routing solution with minimal hardware overhead. Our results based on a cycle-accurate simulator demonstrate the effectiveness of the DP-network, which outperforms both the deterministic and adaptive routing algorithms in average delay on various traffic scenarios by 22.3%. Moreover, the hardware overhead for DP-network is insignificant based on the results obtained from the hardware implementations. Copyright 2009 ACM.
AU - Mak,T
AU - Cheung,PYK
AU - Luk,W
AU - Lam,KP
DO - 10.1145/1629435.1629452
EP - 127
PY - 2009///
SP - 119
TI - A DP-network for optimal dynamic routing in network-on-chip
UR -
ER -