An Efficient Adaptive Deadlock-Free Routing Algorithm for Torus Networks
An Efficient Adaptive Deadlock-Free Routing Algorithm for Torus Networks
复制标题
DOI：
10.1109/tpds.2011.145
复制
发表时间：
2012-05
影响因子：
5.3
通讯作者：
D. Xiang;W. Luo
中科院分区：
文献类型：
--
作者：
D. Xiang;W. Luo
提出了一种适用于VCT（虚拟直通）交换环的无死锁最小路由算法。只需要两个虚拟通道。一个通道被应用在基于已知的基本路由方案的网状子网的无死锁路由算法中，例如，负优先或维序路由。另一个信道类似于自适应信道。这种组合提出了一种新的完全自适应的最小路由方案，因为第一通道不提供路由路径的每个源-目的地对。提出了流控线索和虫孔线索两种算法。针对VCT交换环提出了一种流控线索，该线索是完全自适应的最小无死锁的，没有虚拟通道。每个输入端口需要至少两个缓冲区，每个缓冲区都能够保存一个数据包。提出的流控线索路由算法中使用了一个简单但设计良好的流控函数来避免死锁。针对虫洞切换环提出了虫洞线索。它是部分自适应的，因为我们添加了一些约束的自适应通道的死锁避免。结果表明，线索和流量控制的线索工作优于气泡流量控制方案在几个流行的交通模式在三维（3D）环面。在虫洞交换环中，虫洞线索相对于Duato协议的优势也非常明显。
A deadlock-free minimal routing algorithm called clue is first proposed for VCT (virtual cut-through)-switched tori. Only two virtual channels are required. One channel is applied in the deadlock-free routing algorithm for the mesh subnetwork based on a known base routing scheme, such as, negative-first or dimension-order routing. The other channel is similar to an adaptive channel. This combination presents a novel fully adaptive minimal routing scheme because the first channel does not supply routing paths for every source-destination pair. Other two algorithms named flow controlled clue and wormhole clue are proposed. Flow controlled clue is proposed for VCT-switched tori, which is fully adaptive minimal deadlock-free with no virtual channel. Each input port requires at least two buffers, each of which is able to keep a packet. A simple but well-designed flow control function is used in the proposed flow controlled clue routing algorithm to avoid deadlocks. Wormhole clue is proposed for wormhole-switched tori. It is partially adaptive because we add some constraints to the adaptive channels for deadlock avoidance. It is shown that clue and flow controlled clue work better than the bubble flow control scheme under several popular traffic patterns in 3-dimensional (3D) torus. In a wormhole-switched tori, the advantage of wormhole clue over Duato's protocol is also very apparent.