The Suboptimal Routing Algorithm for 2D Mesh Network
- 22 November 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 67 (5) , 704-716
Abstract
Due to the huge routing algorithm search space for 2D mesh based Network-on-Chip (NoC), Divide-Conquer method is presented to effectively explore the search space. When using Divide-Conquer method, a large number of routing algorithms will be created. In order to get the final results in acceptable time, a precise metric is needed to measure routing performance and discard the poor performance routings. In this paper, we propose a new routing performance metric, namely, network pressure. Network pressure has the following three advantages: (1) it could measure the whole network congestion state; (2) network pressure of a network and that of its partial component is highly related, under the same routing; (3) it is more related with routing performance than the traditional routing performance metrics. Based on network pressure and Divide-Conquer method, high performance routing could be achieved. The obtained routing is called suboptimal routing due to the following two reasons: (1) there is only a little gap between its performance and that of the fully adaptive routings under both transpose1 and transpose2 traffics. (2) the search space of routing algorithms is systematically and widely exploited.Keywords
Funding Information
- Natural Science Foundation of Guangdong Province (2017A030313391)
This publication has 27 references indexed in Scilit:
- An Offline Method for Designing Adaptive Routing Based on Pressure ModelIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014
- Network-on-Chip Routing Algorithms by Breaking Cycles2010
- Efficient implementation of distributed routing algorithms for NoCsIET Computers & Digital Techniques, 2009
- Instruction set synthesis with efficient instruction encoding for configurable processorsACM Transactions on Design Automation of Electronic Systems, 2007
- A scalable high-performance computing solution for networks on chipsIEEE Micro, 2002
- Networks on chips: a new SoC paradigmComputer, 2002
- The odd-even turn model for adaptive routingIEEE Transactions on Parallel and Distributed Systems, 2000
- A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1995
- The turn model for adaptive routingJournal of the ACM, 1994
- A new theory of deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1993