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

摘要

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