Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Engineering
Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson
Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson
Ronald Greenberg
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 …
Randomized Routing On Fat-Trees, Ronald I. Greenberg
Randomized Routing On Fat-Trees, Ronald I. Greenberg
Ronald Greenberg
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/ …
Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh
Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh
Ronald Greenberg
In this paper, 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η+cLηlogP) time with high probability, where L is the number of flits in a packet, and η=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 Θ(A) can simulate wormhole routing on any network of comparable area with O(log^3 A) …