TY - JOUR
T1 - On the benefit of supporting virtual channels in wormhole routers
AU - Cole, Richard J.
AU - Maggs, Bruce M.
AU - Sitaraman, Ramesh K.
N1 - Funding Information:
1Supported in part by NSF Grants CCR-92-02900 and CCR-95-03309. 2Supported in part by NSF National Young Investigator Award CCR-94-57766, with matching funds provided by NEC Research Institute, and by ARPA Contract F33615-93-1-1330. 3Supported in part by NSF Grant CCR-94-10077 and by NSF CAREER Award CCR-97-0317.
PY - 2001/2
Y1 - 2001/2
N2 - This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We study wormhole routing on network in which each physical channel, i.e., communication link, can support up to B virtual channels. We show that it is possible to route any set of messages with L flits each, whose paths have congestion C and dilation D in O((L+ D) C(D log D)1/B/B) flit steps, where a flit step is the time taken to transmit B flits, 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≥B+1 and L=(1+Ω(1))D, we show how to construct a network and a set of L-flit messages whose paths have congestion C and dilation D that require Ω(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 significantly larger than B. We also present a simple randomized wormhole routing 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) log1/B n log log(qn)/B) flit steps. We present a nearly-matching lower bound that holds for a broad class of algorithms.
AB - This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We study wormhole routing on network in which each physical channel, i.e., communication link, can support up to B virtual channels. We show that it is possible to route any set of messages with L flits each, whose paths have congestion C and dilation D in O((L+ D) C(D log D)1/B/B) flit steps, where a flit step is the time taken to transmit B flits, 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≥B+1 and L=(1+Ω(1))D, we show how to construct a network and a set of L-flit messages whose paths have congestion C and dilation D that require Ω(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 significantly larger than B. We also present a simple randomized wormhole routing 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) log1/B n log log(qn)/B) flit steps. We present a nearly-matching lower bound that holds for a broad class of algorithms.
UR - http://www.scopus.com/inward/record.url?scp=0035251054&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035251054&partnerID=8YFLogxK
U2 - 10.1006/jcss.2000.1701
DO - 10.1006/jcss.2000.1701
M3 - Article
AN - SCOPUS:0035251054
SN - 0022-0000
VL - 62
SP - 152
EP - 177
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 1
ER -