Document Type

Article

Publication Date

1989

Publication Title

Advances in Computing Research

Volume

5

Pages

345-374

Publisher Name

JAI Press

Abstract

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 bound was O(lambda lg n) for the offline problem in which the set of messages is known in advance. In the context of a VLSI model that equates hardware cost with physical volume, the routing algorithm can be used to demonstrate that fat-trees are universal routing networks. Specifically, we prove that any routing network can be efficiently simulated by a fat-tree of comparable hardware cost.

Comments

Formatting here is very different from the published version which is a revised version of the conference paper that can be found along with presentation slides at http://ecommons.luc.edu/cs_facpubs/183

Author Posting. © Ronald Greenberg, 1989. This is the author's version of the work. It is posted here for personal use, not for redistribution. The definitive version was published in n Silvio Micali, editor, Randomness and Computation. Volume 5 of Advances in Computing Research, pages 345-374, JAI Press, 1989.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.

Download

Share

COinS