对角网格中的无死锁自适应路由算法

A DEADLOCK-FREE ADAPTIVE ROUTING ALGORITHM ON DIAGONAL MESH

摘要: 网格是多计算机中应用广泛的直连结构，提出了一种新的互连结构──对角网格．并在这种结构上提出了一类自适应无死锁的路由算法──负优先算法，证明了此算法的无死锁性．对角网格是可平面图，其结构简单，可扩充性非常好．它的每个节点的度数是固定的，便于VLSI工艺实现．负优先自适应路由算法的突出优点是对硬件逻辑要求简单，无须增加虚拟通道即可达到无死锁和自适应．

Abstract: Mesh is a popular topology of multiprocessor interconnected network. A new topology, that is, diagonal mesh, and a new adaptive deadlock free routing algorithm based on it, are proposed in this paper. Diagonal mesh is a planar graph with fixed connection number per node.It allows a simple VLSI layout as well as scalability. The algorithm requires simple hardware. And, it do not need virtual channel to support adaptivity and deadlock freeness.