References

1

R. I. Greenberg and C. E. Leiserson. Randomized routing on fat-trees. In Silvio Micali, editor, Randomness and Computation. Volume 5 of Advances in Computing Research, pages 345-374. JAI Press, Greenwich, CT, 1989.

2

N. Kahale. Better expansion for Ramanujan graphs. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 398-404. IEEE Computer Society Press, October 1991.

3

R. R. Koch. Increasing the size of a network by a constant factor can increase performance by more than a constant factor. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 221-230. IEEE Computer Society Press, October 1988.

4

C. P. Kruskal and M. Snir. The performance of multistage interconnection networks for multiprocessors. IEEE Transactions on Computers, C-32(12):1091-1098, December 1983.

5

C. P. Kruskal and M. Snir. A unified theory of interconnection network structure. Theoretical Computer Science, 48:75-94, 1986.

6

F. T. Leighton and B. M. Maggs. Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks. IEEE Transactions on Computers, 41(5):578-587, May 1992.

7

T. Leighton, C. L. Leiserson, and M. Klugerman. Theory of parallel and VLSI computation. Research Seminar Series Report MIT/LCS/RSS 10, MIT Laboratory for Computer Science, May 1991.

8

C. E. Leiserson. Fat-trees: universal networks for hardware-efficient supercomputing. IEEE Transactions on Computers, C-34(10):892-901, October 1985.

9

A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988.

10

B. M. Maggs and R. K. Sitaraman. Simple algorithms for routing on butterfly networks with bounded queues. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, pages 150-161, May 1992.

11

R. D. Rettberg, W. R. Crowther, P. P. Carvey, and R. S. Tomlinson. The monarch parallel processor hardware design. Computer, 23(4):18-30, April 1990.

12

E. Upfal. An deterministic packet routing scheme. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 241-250, May 1989.

Andrew V. Goldberg received the S.B. degree in mathematics from the Massachusetts Institute of Technology in 1982, the S.M. degree in computer science from the University of California at Berkeley in 1983, and the Ph.D. degree in computer science from the Massachusetts Institute of Technology in 1987. Currently he is an Associate Professor of Computer Science at Stanford University. His research interests include sequential and parallel algorithms and combinatorial optimization.

Bruce Maggs (M'92) received the S.B., S.M., and Ph.D., degrees in computer science from the Massachusetts Institute of Technology in 1985, 1986, and 1989, respectively. Currently he is a Research Scientist at the NEC Research Institute in Princeton, NJ. His research interests include parallel computing systems and parallel algorithms.

Serge Plotkin received the Ph.D. degree in computer science from the Massachusetts Institute of Technology in 1988. In 1988 he joined the Department of Computer Science at Stanford University. His main research interests include parallel and distributed computation, high-speed interconnection networks, and combinatorial optimization.