Proceedings of the 26th Annual Symposium on Foundations of Computer Science
Portland, OR, USA, USA
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.
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.
© 1985 IEEE.