An Efficient Adaptive Deadlock-Free Routing Algorithm for Torus Networks

摘要

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.