%0 Journal Article
%T 基于列分转弯模型的片上网络路由算法<br>Routing algorithm based on a column-partition turn model for a network-on-chip
%A 蔡源
%A 罗伟
%A 向东
%J 清华大学学报（自然科学版）
%D 2018
%R 10.16511/j.cnki.qhdxxb.2018.22.043
%X 针对现有的判断片上网络路由算法是否含有死锁的方法都比较复杂，以及传统转弯模型存在不足的问题，提出了一种更简单更直观的判断路由算法是否包含死锁的算法，并证明了该算法的正确性，然后提出了一种列分转弯模型。列分转弯模型能实现针对二维mesh网络的基于虚跨步交换技术的无死锁、最短路径部分自适应路由，并且不需要额外的虚拟通道。该模型会在网络节点处限制某些转弯，从而避免死锁，类似于奇偶转弯模型。模拟实验结果表明：基于该模型的路由算法与基于奇偶转弯模型的路由算法相比，在不同的流量模式下平均延迟都有所降低，饱和点有所上升，从而提高了整个网络的性能。<br>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.
%K 转弯模型
%K 虚跨步交换
%K 二维mesh网络
%K 无死锁
%K 部分自适应路由
%K &lt
%K br&gt
%K turn model
%K virtual cut-through switching
%K 2-D mesh
%K deadlock-free
%K partially adaptive routing
%U http://jst.tsinghuajournals.com/CN/Y2018/V58/I12/1051