Document Type
Conference Proceeding
Publication Date
10-1985
Publication Title
Proceedings of the 26th Annual Symposium on Foundations of Computer Science
Pages
241-249
Publisher Name
IEEE
Publisher Location
Portland, OR, USA, USA
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+lgnlglgn) with probability 1-O(1/n). The best previous bound was O(lambdalgn) for the off-line 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.
Recommended Citation
Greenberg, Ronald I.. Randomized Routing on Fat-trees. Proceedings of the 26th Annual Symposium on Foundations of Computer Science, , : 241-249, 1985. Retrieved from Loyola eCommons, Computer Science: Faculty Publications and Other Works, http://dx.doi.org/10.1109/SFCS.1985.46
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Copyright Statement
© 1985 IEEE.
Presentation slides from 26th FOCS conference
GreenbergL1985_expanded_slides.pdf (7774 kB)
Expanded version of slides from talk at MIT seminar shortly before conference
MITseminarnotice.PDF (25 kB)
MIT seminar notice
Included in
Computer and Systems Architecture Commons, OS and Networks Commons, Systems Architecture Commons, Theory and Algorithms Commons, VLSI and Circuits, Embedded and Hardware Systems Commons
Comments
Author Posting. © 1985 IEEE. This is the author's version of the work. It is posted here for personal use, not for redistribution. The definitive version was published R. I. Greenberg and C. E. Leiserson, "Randomized routing on fat-tress," 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), Portland, OR, USA, 1985, pp. 241-249. doi: 10.1109/SFCS.1985.46 http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4568147&isnumber=4568116
A revised version can be found at http://ecommons.luc.edu/cs_facpubs/94.