|
|
- 2018
基于列分转弯模型的片上网络路由算法
|
Abstract:
针对现有的判断片上网络路由算法是否含有死锁的方法都比较复杂，以及传统转弯模型存在不足的问题，提出了一种更简单更直观的判断路由算法是否包含死锁的算法，并证明了该算法的正确性，然后提出了一种列分转弯模型。列分转弯模型能实现针对二维mesh网络的基于虚跨步交换技术的无死锁、最短路径部分自适应路由，并且不需要额外的虚拟通道。该模型会在网络节点处限制某些转弯，从而避免死锁，类似于奇偶转弯模型。模拟实验结果表明：基于该模型的路由算法与基于奇偶转弯模型的路由算法相比，在不同的流量模式下平均延迟都有所降低，饱和点有所上升，从而提高了整个网络的性能。
Abstract：Existing methods cannot easily determine whether a routing algorithm for a network-on-chip contains a deadlock and the traditional turn model has serious limitations. This paper presents a simple, intuitive algorithm to determine whether the routing algorithm is deadlock-free. This paper gives a proof of the algorithm's correctness. Then, a column-partition turn model is given to implement deadlock-free minimal partially adaptive routing for a virtual cut-through (VCT)-switched 2-D mesh without extra virtual channels. This algorithm avoids deadlocks by restricting the locations for certain turns, which is similar to the odd-even turn method. Simulations show that this routing algorithm reduces the average latency and increases the saturation points compared to routing algorithms based on the odd-even turn model for various traffic patterns. Therefore, this column-partition turn model improves the performance of the whole network.
| [1] | XIANG D. Deadlock-free adaptive routing in meshes with fault-tolerance ability based on channel overlapping[J]. IEEE Transactions on Dependable and Secure Computing, 2011, 8(1):74-88. |
| [2] | KHAN H U R, SHI F, JI W X, et al. Computationally efficient locality-aware interconnection topology for multi-processor system-on-chip (MP-SoC)[J]. Chinese Science Bulletin, 2010, 55(29):3363-3371. |
| [3] | XIANG D, ZHANG Y L, PAN Y, et al. Deadlock-free adaptive routing in meshes based on cost-effective deadlock avoidance schemes[C]//Proceedings of International Conference on Parallel Processing. Xi'an, China, 2007:41-48. |
| [4] | DALLY W, TOWLES B. Principles and practices of interconnection networks[M]. San Francisco, USA:Morgan Kaufmann, 2003. |
| [5] | DUATO J, YALAMANCHILI S, NI L. Interconnection networks:An engineering approach[M]. San Francisco, USA:Morgan Kaufmann, 2002. |
| [6] | VERBEEK F, SCHMALTZ J. A decision procedure for deadlock-free routing in wormhole networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(8):1935-1944. |
| [7] | GLASS C J, NI L M. The turn model for adaptive routing[J]. Journal of the ACM, 1994, 41(5):874-902. |
| [8] | CHIU G M. The odd-even turn model for adaptive routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(7):729-738. |
| [9] | DUATO J. A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(8):841-854. |
| [10] | XU Y, DU Y, ZHAO B, et al. A low-radix and low-diameter 3D interconnection network design[C]//Proceedings of the 15th International Symposium on High Performance Computer Architecture. Raleigh, USA, 2009:30-42. |
| [11] | 李晨, 马胜, 王璐, 等. 三维片上网络体系结构研究综述[J]. 计算机学报, 2016, 39(9):1812-1828. LI C, MA S, WANG L, et al. A survey on architecture for three-dimensional networks-on-chip[J]. Chinese Journal of Computers, 2016, 39(9):1812-1828. (in Chinese) |
| [12] | ALLEN F, ALMASI G, ANDREONI G, et al. Blue gene:A vision for protein science using a petaflop supercomputer[J]. IBM Systems Journal, 2011, 40(2):310-327. |
| [13] | MUKHERJEE S S, BANNON R, LANG S, et al. The Alpha 21364 network architecture[J]. IEEE Micro, 2002, 22(1):26-35. |
