Randomized Routing on Fat-trees
Fat-trees are a class of routing networks for hardware-efficient paralle 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 t...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149116 |
| _version_ | 1810975264080920576 |
|---|---|
| author | Greenberg, Ronald I. Leiserson, Charles E. |
| author_facet | Greenberg, Ronald I. Leiserson, Charles E. |
| author_sort | Greenberg, Ronald I. |
| collection | MIT |
| description | Fat-trees are a class of routing networks for hardware-efficient paralle 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 cyles (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 )(lambda lg n) for the off-line problem where switch settings can be determined in advance. In a VLSI-like model where hardware cost is equated with physical volume, the routing algorithm demonstrates that fat-trees are universal routing networks in the sense that any routing network can be efficiently simulated by a fat-tree of comparable hardward cost. |
| first_indexed | 2024-09-23T08:36:36Z |
| id | mit-1721.1/149116 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:36:36Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491162023-03-30T04:20:04Z Randomized Routing on Fat-trees Greenberg, Ronald I. Leiserson, Charles E. Fat-trees are a class of routing networks for hardware-efficient paralle 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 cyles (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 )(lambda lg n) for the off-line problem where switch settings can be determined in advance. In a VLSI-like model where hardware cost is equated with physical volume, the routing algorithm demonstrates that fat-trees are universal routing networks in the sense that any routing network can be efficiently simulated by a fat-tree of comparable hardward cost. 2023-03-29T14:28:29Z 2023-03-29T14:28:29Z 1986-05 https://hdl.handle.net/1721.1/149116 MIT-LCS-TM-307 application/pdf |
| spellingShingle | Greenberg, Ronald I. Leiserson, Charles E. Randomized Routing on Fat-trees |
| title | Randomized Routing on Fat-trees |
| title_full | Randomized Routing on Fat-trees |
| title_fullStr | Randomized Routing on Fat-trees |
| title_full_unstemmed | Randomized Routing on Fat-trees |
| title_short | Randomized Routing on Fat-trees |
| title_sort | randomized routing on fat trees |
| url | https://hdl.handle.net/1721.1/149116 |
| work_keys_str_mv | AT greenbergronaldi randomizedroutingonfattrees AT leisersoncharlese randomizedroutingonfattrees |