A deadlock-free fully adaptive minimal routing algorithm for meshes that is optimal in the number of virtual channels required and in the number of restrictions placed on the use of these virtual channels is presented. It is also proved that, ignoring symmetry, this routing algorithm is the only fully adaptive routing algorithm with uniform routers that achieves both of these goals. This new algorithm requires only 4n-2 virtual channels for an n-dimensional mesh. In additional channels with the fewest possible number of restrictions. The proofs are first presented for the 2D mesh and then generalized to n-dimensional meshes.

1. Introduction

Partially adaptive routing algorithms do not allow all message to use any shortest path.

Fully adaptive routing algorithms do allow all messages to use any shortest path.

2. Optimal Minimal Routing

This configurations has sixteen 90°turn and four 0°turns.

Unrestricted turns are indicated by solid lines, restricted turns by dashed line, and prohibited turns by dotted lines.

The constrains imposed by the Optimal Fully Adaptive routing algorithm, referred to as opt-y, can be summarized succinctly: a message that needs to route further in the West direction cannot use VC1n or VC1s.

Opt-y has the following two sets of constraints(Figs. 1b and 1c):

• Two 90°turns, N-W using VC1n and S-W using VC1s are prohibited.
• The 0°turns form VC2n to VC1n and form VC2s to VC1s are allowed only when the message does not need to route further West.
• The 90°turns W-S using VC1s and W-N using VC1n are allowed only when the message does not need to route further West. These turns are restricted only because the N-W turn from VC1n and S-W turn form VC1s are prohibited.
• The 0°turns form VC1n to VC2n and form VC1s to VC2s are allowed only when the message does not need to route further West, because VC1n and VC1s are not used until the message has completed routing West.
• VC1n and VC1s cannot be used by the router at the source if the message needs to route West.

Using Duato’s terminology , the routing algorithm is denoted R and the set R and the set of channels used by R is denoted C. There is some subset of channels, C1Í C, that define a routing algorithm R1Í R; i.e., R1 is the routing algorithm R restricted to using the set of channels C1.When there are cycles in the channel dependency graph, it is not possible to provide a numbering of the channels that guarantees the channels are used in always increasing or always decreasing order. Instead, Duato has shown that any routing algorithm of the form R:N×N® Cp is deadlock-free if it satisfies the following three conditions:

The channels C1 is deadlock-free ,because it’s routing is acyclics.

Lemma 4. At least two 90°turns must be prohibited to make the routing algorithm deadlock-free.

Theorem 4. Ignoring symmetry, opt-y prohibits fewer 90°turns than any other deadlock-free fully adaptive routing algorithm that uses only six virtual channels.