**1**-
M. Ajtai, J. Komlós, and E. Szemerédi.
Sorting in parallel steps.
*Combinatorica*, 3:1-19, 1983. **2**-
R. Aleliunas.
Randomized parallel communication.
In
*Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing*, pages 60-72, August 1982. **3**-
D. Angluin and L. G. Valiant.
Fast probabilistic algorithms for hamiltonian circuits and matchings.
*Journal of Computer and System Sciences*, 18(2):155-193, April 1979. **4**-
K. Batcher.
Sorting networks and their applications.
In
*Proceedings of the AFIPS Spring Joint Computing Conference*, volume 32, pages 307-314, 1968. **5**-
Butterfly Parallel Processor Overview.
BBN Report No. 6148, Version 1, BBN Advanced Computers, Inc.,
Cambridge, MA, March 1986.
**6**-
V. E. Benes.
*Mathematical Theory of Connecting Networks and Telephone Traffic*. Academic Press, New York, 1965. **7**-
J. L. Carter and M. N. Wegman.
Universal classes of hash functions.
*Journal of Computer and System Sciences*, 18(2):143-154, April 1979. **8**-
H. Chernoff.
A measure of asymptotic efficiency for tests of a hypothesis based on
the sum of observations.
*American Mathematical Society*, 23:493-507, 1952. **9**-
W. Dally and C. Seitz.
Deadlock free message routing in multiprocessor interconnection
networks.
*IEEE Transactions on Computers*, C-36(5):547-553, May 1987. **10**-
R. I. Greenberg and C. E. Leiserson.
Randomized routing on fat-trees.
In Silvio Micali, editor,
*5Randomness and ComputationAdvances in Computing Research*, pages 345-374. JAI Press, Greenwich, CT, 1989. **11**-
A. R. Karlin and E. Upfal.
Parallel hashing -- an efficient implementation of shared memory.
In
*Proceedings of the 18th Annual ACM Symposium on Theory of Computing*, pages 160-168, May 1986. **12**-
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. **13**-
D. Krizanc, S. Rajasekaran, and Th. Tsantilis.
Optimal routing algorithms for mesh-connected processor arrays.
In J. Reif, editor,
*319Aegean Workshop on Computing: VLSI Algorithms and ArchitecturesLecture Notes in Computer Science*, pages 411-422. Springer-Verlag, New York, NY, June 1988. **14**-
M. Kunde.
Routing and sorting on mesh-connected arrays.
In J. Reif, editor,
*319Aegean Workshop on Computing: VLSI Algorithms and ArchitecturesLecture Notes in Computer Science*, pages 423-433. Springer-Verlag, New York, NY, June 1988. **15**-
F. T. Leighton.
*Complexity Issues in VLSI*. MIT Press, Cambridge, MA, 1983. **16**-
F. T. Leighton.
Tight bounds on the complexity of parallel sorting.
*IEEE Transactions on Computers*, C-34(4):344-354, April 1985. **17**-
F. T. Leighton.
*Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes*. Morgan Kaufmann, San Mateo, CA, 1992. **18**-
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. **19**-
F. T. Leighton, F. Makedon, and I. Tollis.
A
*2N-2*step algorithm for routing in an mesh. In*Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures*, pages 328-335, June 1989. **20**-
T. Leighton, B. Maggs, and S. Rao.
Universal packet routing algorithms.
In
*Proceedings of the 29th Annual Symposium on Foundations of Computer Science*, pages 256-271, October 1988. **21**-
C. E. Leiserson.
Fat-trees: universal networks for hardware-efficient supercomputing.
*IEEE Transactions on Computers*, C-34(10):892-901, October 1985. **22**-
C. E. Leiserson and B. M. Maggs.
Communication-efficient parallel graph algorithms for distributed
random-access machines.
*Algorithmica*, 3(1):53-77, 1988. **23**-
B. M. Maggs.
*Locality in Parallel Computation*. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 1989. **24**-
R. Miller, V. K. Prasanna-Kumar, D. Reisis, and Q. F. Stout.
Meshes with reconfigurable buses.
In J. Allen and F. T. Leighton, editors,
*Advanced Research in VLSI: Proceedings of the Fifth MIT Conference*, pages 163-178, Cambridge, MA, April 1988. MIT Press. **25**-
D. Nassimi and S. Sahni.
Parallel permutation and sorting algorithms and a new generalized
connection network.
*Journal of the ACM*, 29(3):642-667, July 1982. **26**-
N. Pippenger.
Parallel communication with limited buffers.
In
*Proceedings of the 25th Annual Symposium on Foundations of Computer Science*, pages 127-136, October 1984. **27**-
P. Raghavan.
Probabilistic construction of deterministic algorithms: approximate
packing integer programs.
*Journal of Computer and System Sciences*, 37(4):130-143, October 1988. **28**-
A. Raghunathan and H. Saran.
Is the shuffle-exchange better than the butterfly?
Unpublished manuscript.
**29**-
A. G. Ranade.
How to emulate shared memory.
In
*Proceedings of the 28th Annual Symposium on Foundations of Computer Science*, pages 185-194. IEEE Computer Society Press, October 1987. **30**-
A. G. Ranade.
*Fluent Parallel Computation*. PhD thesis, Yale University, New Haven, CT, 1988. **31**-
A. G. Ranade, S. N. Bhatt, and S. L. Johnsson.
The fluent abstract machine.
In J. Allen and F. T. Leighton, editors,
*Advanced Research in VLSI: Proceedings of the Fifth MIT Conference*, pages 71-94, Cambridge, MA, April 1988. MIT Press. **32**-
J. H. Reif and L. G. Valiant.
A logarithmic time sort for linear size networks.
*Journal of the ACM*, 34(1):60-76, January 1987. **33**-
J. Spencer.
*Ten Lectures on the Probabilistic Method*. SIAM, Philadelphia, PA, 1987. **34**-
C. D. Thompson.
*A Complexity Theory for VLSI*. PhD thesis, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA, 1980. **35**-
C. D. Thompson and H. T. Kung.
Sorting on a mesh-connected parallel computer.
*Communications of the ACM*, 20(4):263-271, 1977. **36**-
E. Upfal.
Efficient schemes for parallel communication.
In
*Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing*, pages 55-59, August 1982. **37**-
E. Upfal.
An deterministic packet routing scheme.
In
*Proceedings of the 21st Annual ACM Symposium on Theory of Computing*, pages 241-250, May 1989. **38**-
L. G. Valiant.
A scheme for fast parallel communication.
*SIAM Journal on Computing*, 11(2):350-361, May 1982. **39**-
L. G. Valiant and G. J. Brebner.
Universal schemes for parallel communication.
In
*Proceedings of the 13th Annual ACM Symposium on Theory of Computing*, pages 263-277, May 1981. **40**-
A. Waksman.
A permutation network.
*Journal of the ACM*, 15(1):159-163, January 1968.

Mon Jul 22 22:57:44 EDT 1996