References

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.