基于列分转弯模型的片上网络路由算法

摘要

针对现有的判断片上网络路由算法是否含有死锁的方法都比较复杂,以及传统转弯模型存在不足的问题,提出了一种更简单更直观的判断路由算法是否包含死锁的算法,并证明了该算法的正确性,然后提出了一种列分转弯模型。列分转弯模型能实现针对二维mesh网络的基于虚跨步交换技术的无死锁、最短路径部分自适应路由,并且不需要额外的虚拟通道。该模型会在网络节点处限制某些转弯,从而避免死锁,类似于奇偶转弯模型。模拟实验结果表明:基于该模型的路由算法与基于奇偶转弯模型的路由算法相比,在不同的流量模式下平均延迟都有所降低,饱和点有所上升,从而提高了整个网络的性能。