Universal wormhole routing
Open Access
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cd/spl eta/ + cL/spl eta/log P) time, where L is the number of flits in a packet, and /spl eta/ = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area /spl Theta/(A) can simulate wormhole routing on any network of comparable area with O(log/sup 3/ A) slowdown, when all worms have the same length. Variable-length worms are also considered. We run some simulations on the fat-tree which show that not only does wormhole routing tend to perform better than the more heavily studied store-and-forward routing, but that performance superior to our provable bound is attainable in practice.<>Keywords
This publication has 13 references indexed in Scilit:
- On bit-serial packet routing for the mesh and the torusPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The Network Architecture of the Connection Machine CM-5Journal of Parallel and Distributed Computing, 1996
- Packet Routing in Networks with Long WiresJournal of Parallel and Distributed Computing, 1995
- Randomized Routing and Sorting on Fixed-Connection NetworksJournal of Algorithms, 1994
- The fat-pyramid and universal parallel computation independent of wire delayIEEE Transactions on Computers, 1994
- Average case analysis of greedy routing algorithms on arraysPublished by Association for Computing Machinery (ACM) ,1990
- Universal packet routing algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- The torus routing chipDistributed Computing, 1986
- Fat-trees: Universal networks for hardware-efficient supercomputingIEEE Transactions on Computers, 1985
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977