Next: About this document
Up: A Parallel Algorithm for
Previous: 4 Remarks
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.
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
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
C. P. Kruskal and M. Snir.
The performance of multistage interconnection networks for
IEEE Transactions on Computers, C-32(12):1091-1098,
C. P. Kruskal and M. Snir.
A unified theory of interconnection network structure.
Theoretical Computer Science, 48:75-94, 1986.
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.
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.
C. E. Leiserson.
Fat-trees: universal networks for hardware-efficient supercomputing.
IEEE Transactions on Computers, C-34(10):892-901, October
A. Lubotzky, R. Phillips, and P. Sarnak.
Combinatorica, 8(3):261-277, 1988.
B. M. Maggs and R. K. Sitaraman.
Simple algorithms for routing on butterfly networks with bounded
In Proceedings of the 24th Annual ACM Symposium on the Theory
of Computing, pages 150-161, May 1992.
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.
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
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.
Mon Jul 22 19:56:03 EDT 1996