Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 853))
Included in the following conference series:
134Accesses
Abstract
Multistage networks are important in a wide variety of applications. Expander-based networks, such as multibutterflies, are a tremendous improvement over traditional butterflies in both fault and congestion tolerance. However, multibutterflies cost at least twice as much in chips and wiring as butterflies. It is also impossible to build large multi-butterflies due to their wiring complexity.
We show that we can build an expander-based network that has comparable cost to a butterfly with the same number of endpoints, yet has substantially better fault and congestion performance. Specifically, we introduce a hierarchical construction that dramatically reduces wiring complexity and makes large expanders buildable. We are able to exploit the hierarchical structure to find large numbers of logical wires to multiplex over a smaller number of physical wires. Since many of the wires in an expander-based network are used to provide alternate paths, not useful bandwidth, substantial multiplexing can be done without significantly degrading performance. We present simulation results to support our conclusions. In comparing a butterfly with the comparable 2-to-1 multiplexed metabutterfly, we found that the metabutterfly performed better by nearly a factor of two on random traffic and greater than a factor of five on worst-case traffic.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arora, T. Leighton, and B. Maggs. On-line algorithms for path selection in a non-blocking network. InProceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 149–158, May 1990.
Thomas E. Anderson, Susan S. Owicki, James B. Saxe, and Charles P. Thacker. High-speed switch scheduling for local-area networks.ACM Transactions on Computer Systems, 11(4):319–352, November 1993.
Eric A. Brewer, Frederic T. Chong, and F. Thomson Leighton. Scalable expanders: exploiting hierarchical random wiring. InProceedings of the 26nd Annual ACM Symposium on Theory of Computing, pages 144–152, May 1994.
L. A. Bassalygo and M. S. Pinsker. Complexity of optimum nonblocking switching networks without reconnections.Problems of Information Transmission, 9:64–66, 1974.
Frederic Chong, Eran Egozy, and André DeHon. Fault tolerance and performance of multipath multistage interconnection networks. In Thomas F. Knight Jr. and John Savage, editors,Advanced Research in VLSI and Parallel Systems 1992, pages 227–242. MIT Press, March 1992.
Frederic T. Chong and Thomas F. Knight, Jr. Design and performance of multipath MIN architectures. InSymposium on Parallel Architectures and Algorithms, pages 286–295, San Diego, California, June 1992. ACM.
André DeHon. Robust, high-speed network design for large-scale multiprocessing. Master's thesis, MIT, 545 Technology Sq., Cambridge, MA 02139, February 1993.
Charles E. Leiserson. Fat-trees: Universal networks for hardware efficient supercomputing.IEEE Transactions on Computers, C-34(10):892–901, October 1985.
Tom Leighton and Bruce Maggs. Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. InIEEE 30th Annual Symposium on Foundations of Computer Science, 1989.
Tom Leighton and Bruce Maggs. Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks.IEEE Transactions on Computers, 41(5):1–10, May 1992.
Nicholas Pippenger. Self-routing superconcentrators. In25th Annual ACM Symposium on the Theory of Computing, pages 355–361. ACM, May 1993.
E. Upfal. AnO(logN) deterministic packet routing scheme. In21st Annual ACM Symposium on Theory of Computing, pages 241–250. ACM, May 1989.
Avi Wigderson and David Zuckerman. Expanders that beat the eigenvalue bound: explicit construction and applications. In25th Annual ACM Symposium on the Theory of Computing, pages 245–251. ACM, May 1993.
Author information
Authors and Affiliations
MIT Laboratory for Computer Science, 545 Technology Square, 02139, Cambridge, MA
Frederic T. Chong, Eric A. Brewer, F. Thomson Leighton & Thomas F. Knight Jr.
MIT Artificial Intelligence Laboratory, 545 Technology Square, 02139, Cambridge, MA
Frederic T. Chong, Eric A. Brewer, F. Thomson Leighton & Thomas F. Knight Jr.
- Frederic T. Chong
You can also search for this author inPubMed Google Scholar
- Eric A. Brewer
You can also search for this author inPubMed Google Scholar
- F. Thomson Leighton
You can also search for this author inPubMed Google Scholar
- Thomas F. Knight Jr.
You can also search for this author inPubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chong, F.T., Brewer, E.A., Leighton, F.T., Knight, T.F. (1994). Packaging and multiplexing of hierarchical scalable expanders. In: Bolding, K., Snyder, L. (eds) Parallel Computer Routing and Communication. PCRCW 1994. Lecture Notes in Computer Science, vol 853. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58429-3_38
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-58429-2
Online ISBN:978-3-540-48787-6
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative