References

1

A. Alexandrov, M. Ionescu, K. Schauser, and C. Scheiman. LogGP: Incorporating Long Messages into the LogP Model - One step closer towards a realistic model for parallel computation. In 7th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 95-105, Santa Barbara, CA, July 1995.

2

R.H. Arpaci, D.E. Culler, A. Krishnamurthy, S.G. Steinberg, and K. Yelick. Empirical Evaluation of the CRAY-T3D: A Compiler Perspective. In ACM Press, editor, Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 320-331, Santa Margherita Ligure, Italy, June 1995.

3

D.A. Bader, D.R. Helman, and J. JáJá. Practical Parallel Algorithms for Personalized Communication and Integer Sorting. CS-TR-3548 and UMIACS-TR-95-101 Technical Report, UMIACS and Electrical Engineering, University of Maryland, College Park, MD, November 1995. To appear in ACM Journal of Experimental Algorithmics.

4

D.A. Bader and J. JáJá. Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study. Technical Report CS-TR-3384 and UMIACS-TR-94-133, UMIACS and Electrical Engineering, University of Maryland, College Park, MD, December 1994. To appear in Journal of Parallel and Distributed Computing.

5

D.A. Bader and J. JáJá. Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study. In Fifth ACM SIGPLAN Symposium of Principles and Practice of Parallel Programming, pages 123-133, Santa Barbara, CA, July 1995.

6

D.A. Bader and J. JáJá. Practical Parallel Algorithms for Dynamic Data Redistribution, Median Finding, and Selection. Technical Report CS-TR-3494 and UMIACS-TR-95-74, UMIACS and Electrical Engineering, University of Maryland, College Park, MD, July 1995. Presented at the 10th International Parallel Processing Symposium, pages 292-301, Honolulu, HI, April 15-19, 1996.

7

D. Bailey, E. Barszcz, J. Barton, D. Browning, R. Carter, L. Dagum, R. Fatoohi, S. Fineberg, P. Frederickson, T. Lasinski, R. Schreiber, H. Simon, V. Venkatakrishnan, and S. Weeratunga. The NAS Parallel Benchmarks. Technical Report RNR-94-007, Numerical Aerodynamic Simulation Facility, NASA Ames Research Center, Moffett Field, CA, March 1994.

8

V. Bala, J. Bruck, R. Cypher, P. Elustondo, A. Ho, C.-T. Ho, S. Kipnis, and M. Snir. CCL: A Portable and Tunable Collective Communication Library for Scalable Parallel Computers. IEEE Transactions on Parallel and Distributed Systems, 6:154-164, 1995.

9

K. Batcher. Sorting Networks and Their Applications. In Proceedings of the AFIPS Spring Joint Computer Conference 32, pages 307-314, Reston, VA, 1968.

10

G.E. Blelloch, C.E. Leiserson, B.M. Maggs, C.G. Plaxton, S.J. Smith, and M. Zagha. A Comparison of Sorting Algorithms for the Connection Machine CM-2. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, pages 3-16, July 1991.

11

W.W. Carlson and J.M. Draper. AC for the T3D. Technical Report SRC-TR-95-141, Supercomputing Research Center, Bowie, MD, February 1995.

12

H. Chernoff. A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations. Annals of Math. Stat., 23:493-509, 1952.

13

Cray Research, Inc. SHMEM Technical Note for C, October 1994. Revision 2.3.

14

D.E. Culler, A. Dusseau, S.C. Goldstein, A. Krishnamurthy, S. Lumetta, T. von Eicken, and K. Yelick. Parallel Programming in Split-C. In Proceedings of Supercomputing '93, pages 262-273, Portland, OR, November 1993.

15

D.E. Culler, A.C. Dusseau, R.P. Martin, and K.E. Schauser. Fast Parallel Sorting Under LogP: From Theory to Practice. In Portability and Performance for Parallel Processing, chapter 4, pages 71-98. John Wiley & Sons, 1993.

16

D.E. Culler, R.M. Karp, D.A. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian, and T. von Eicken. LogP: Towards a Realistic Model of Parallel Computation. In Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May 1993.

17

A.C. Dusseau. Modeling Parallel Sorts with LogP on the CM-5. Technical Report UCB//CSD-94-829, Computer Science Division, University of California, Berkeley, 1994.

18

T. Hagerup and C. Rüb. A Guided Tour of Chernoff Bounds. Information Processing Letters, 33:305-308, 1990.

19

D.R. Helman, D.A. Bader, and J. JáJá. Parallel Algorithms for Personalized Communication and Sorting With an Experimental Study. In Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 211-220, Padua, Italy, June 1996.

20

W.L. Hightower, J.F. Prins, and J.H. Reif. Implementations of Randomized Sorting on Large Parallel Machines. In Proceedings of the 4th Symposium on Parallel Architectures and Algorithms, pages 158-167, San Diego, CA, July 1992.

21

J.S. Huang and Y.C. Chow. Parallel Sorting and Data Partitioning by Sampling. In Proceedings of the 7th Computer Software and Applications Conference, pages 627-631, November 1983.

22

F.T. Leighton. Tight Bounds on the Complexity of Parallel Sorting. IEEE Transactions on Computers, C-34:344-354, 1985.

23

H. Li and K.C. Sevcik. Parallel Sorting by Overpartitioning. Technical Report CSRI-295, Computer Systems Research Institute, University of Toronto, Canada, April 1994.

24

X. Li, P. Lu, J. Schaeffer, J. Shillington, P.S. Wong, and H. Shi. On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19:1079-1103, 1993.

25

J.M. Marberg and E. Gafni. Sorting in Constant Number of Row and Column Phases on a Mesh. Algorithmica, 3:561-572, 1988.

26

Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. Technical report, University of Tennessee, Knoxville, TN, June 1995. Version 1.1.

27

C.G. Plaxton. Efficient Computation on Sparse Interconnection Networks. Technical Report STAN-CS-89-1283, Department of Computer Science, Stanford University, Stanford, CA, September 1989.

28

M.J. Quinn. Analysis and Benchmarking of Two Parallel Sorting Algorithms: Hyperquicksort and Quickmerge. BIT, 29:239-250, 1989.

29

J.H. Reif and L.G. Valiant. A Logarithmic Time Sort for Linear Sized Networks. Journal of the ACM, 34:60-76, 1987.

30

S. Saini and D.H. Bailey. NAS Parallel Benchmarks Results 12-95. Report NAS-95-021, Numerical Aerodynamic Simulation Facility, NASA Ames Research Center, Moffett Field, CA, December 1995.

31

H. Shi and J. Schaeffer. Parallel Sorting by Regular Sampling. Journal of Parallel and Distributed Computing, 14:361-372, 1992.

32

A. Tridgell and R.P. Brent. An Implementation of a General-Purpose Parallel Sorting Algorithm. Techical Report TR-CS-93-01, Computer Sciences Laboratory, Australian National University, Canberra, Australia, February 1993.

33

L.G. Valiant. A Bridging Model for Parallel Computation. Communications of the ACM, 33(8):103-111, 1990.

34

S.C. Woo, M. Ohara, E. Torrie, J.P. Singh, and A. Gupta. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 24-36, June 1995.