On the benefit of supporting virtual channels in wormhole routers

This paper analyzes the impact of virtual channels on the performance of wo rmhole routing algorithms. We study wormhole routing on network in which ea ch physical channel, i.e. communication link, can support up to B virtual c hannels. We show that it is possible to route any set of messages with L fl its each, whose paths have congestion C and dilation D in O((L + D) C(D log D)(1/B)/B) nit steps, where a nit step is the time taken to transmit B fli ts: i.e., one flit per virtual channel, across a physical channel. We also prove a nearly matching lower bound; i.e., for any values of C. D, B, and L , where C, D greater than or equal to B + 1 and L = (1 + Ohm (1)) D, we sho w how to construct a network and a set of L-flit messages whose paths have congestion C and dilation D that require Ohm (LCD1/B/B) flit steps to route . These upper and lower bounds imply that increasing the buffering capacity and the bandwidth of each physical channel by a factor of B can speed up a wormhole routing algorithm by a superlinear factor, i.e., a factor signifi cantly larger than B. We also present a simple randomized wormhole routine algorithm for the butterfly network. The algorithm routes any q-relation on the inputs and outputs of an n-input butterfly in O(L(q + log n) log(1/B) n log log(qn)/B) flit steps. We present a nearly-matching lower bound that holds for a broad class of algorithms. (C) 2001 Academic Press.