VLSI and Circuits, Embedded and Hardware Systems Commons^™

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …