Deterministic sorting and randomized median finding on the BSP model

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic sorting and randomized median finding on the BSP model

Full text

Pdf (1.08 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures table of contents

Padua, Italy

Pages: 223 - 232

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Alexandros V. Gerbessiotis	Programming Research Group, Computing Laboratory, Oxford University, Parks Road, Oxford OX1 3QD, UK
Constantinos J. Siniolakis	Programming Research Group, Computing Laboratory, Oxford University, Parks Road, Oxford OX1 3QD, UK

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237502.237561 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Micah Adler , John W. Byers , Richard M. Karp, Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215431]
	2	D. Angluin and L. G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Computer and System Sciences, 18:155-193, 1979.
	3	K. Batcher. Sorting Networks and their applications. In Proceedings of the AFIPS Spring Joint Computing Conference, pp. 307-314, 1968.
	4	M. Blum, R. W. Floyd, V. 1%. Pratt, 1%. L. 1%ivest and R. E. Tarjan. Time bounds for selection. J. Computer and System Sciences, 7:448-461, 1973.
	5	Walter Cunto , J. Ian Munro, Average case selection, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.369-375, December 1984 [doi>10.1145/800057.808702]
	6	B@la Bollob~s. Random Graphs. Academic Press, New York, 1985.
	7	Robert W. Floyd , Ronald L. Rivest, Expected time bounds for selection, Communications of the ACM, v.18 n.3, p.165-172, March 1975 [doi>10.1145/360680.360691]
	8	Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct bulk-synchronous parallel algorithms, Journal of Parallel and Distributed Computing, v.22 n.2, p.251-267, Aug. 1994 [doi>10.1006/jpdc.1994.1085]
	9	J. S. Huang and Y. C. Chow, Parallel Sorting and Data Partitioning by Sampling. Proceedings of the IEEE Computer Soczety's 7-th Internatwnal Computer Software and Applications Conference, pp. 627-631, 1983.
	10	L. Hyafil. Bounds for selection. SIAM Journal of Computing 5:109-114, 1976.
	11	David G. Kirkpatrick, A Unified Lower Bound for Selection and Set Partitioning Problems, Journal of the ACM (JACM), v.28 n.1, p.150-165, Jan. 1981 [doi>10.1145/322234.322245]
	12	D. E. Knu#h. The Art of Computer Programming. Volume I: Fundamental Algorithms. Addison-Wesley, Reading, 1969.
	13	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	14	Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
	15	W. F. McColl, General purpose parallel computing, Lectures on parallel computation, Cambridge University Press, New York, NY, 1993
	16	W. F. McColl. Scalable parallel computing: A grand unified theory and its practical development. In Proceedings of IFIP World Congress, 1:539-546, Hamburg, August 1994.
	17	J. I. Munro and P. V. Poblete. A lower bound for determining the median. University of Waterloo Research Report CS-82-21, 1982
	18	Sanguthevar Rajasekaran, Randomized parallel selection (extended abstract), Proceedings of the tenth conference on Foundations of software technology and theoretical computer science, p.215-224, November 1990, Bangalore, India
	19	R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SIAM Journal on Computzng, 14(2):396-409, 1985.
	20	A. Schonhage, M. Paterson, and N. Pippenger. Finding the median. J. Computer and System Sciences, 13:184- 199, 1976.
	21	Hanmao Shi , Jonathan Schaeffer, Parallel sorting by regular sampling, Journal of Parallel and Distributed Computing, v.14 n.4, p.361-372, April 1992 [doi>10.1016/0743-7315(92)90075-X]
	22	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	23	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

CITED BY 17

	Mark W. Goudreau , Kevin Lang , Girija Narlikar , Satish B. Rao, BOS is boss: a case for bulk-synchronous object systems, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.115-125, June 27-30, 1999, Saint Malo, France
	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States
	Micah Adler , Wolfgang Dittrich , Ben Juurlink , Mirosław Kutyłowski , Ingo Rieping, Communication-optimal parallel minimum spanning tree algorithms (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.27-36, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Daniel Jiménez-González , Juan J. Navarro , Josep-L. Larrba-Pey, Fast parallel in-memory 64-bit sorting, Proceedings of the 15th international conference on Supercomputing, p.114-122, June 2001, Sorrento, Italy
	Micah Adler , Tom Leighton, Compression using efficient multicasting, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.153-162, May 21-23, 2000, Portland, Oregon, United States
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Architecture independent parallel selection with applications to parallel priority queues, Theoretical Computer Science, v.301 n.1-3, p.119-142, 14 May 2003
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Randomized selection in n + C + o(n) comparisons, Information Processing Letters, v.88 n.3, p.95-100, 15 November 2003
	Pat Morin, Coarse grained parallel computing on heterogeneous systems, Proceedings of the 1998 ACM symposium on Applied Computing, p.628-634, February 27-March 01, 1998, Atlanta, Georgia, United States
	Andrew Sohn , Yuetsu Kodama, Load balanced parallel radix sort, Proceedings of the 12th international conference on Supercomputing, p.305-312, July 1998, Melbourne, Australia
	David R. Helman , Joseph JáJá , David A. Bader, A new deterministic parallel sorting algorithm with an experimental evaluation, Journal of Experimental Algorithmics (JEA), 3, p.4-es, 1998
	Mark W. Goudreau , Kevin Lang , Satish B. Rao , Torsten Suel , Thanasis Tsantilas, Portable and Efficient Parallel Computing Using the BSP Model, IEEE Transactions on Computers, v.48 n.7, p.670-689, July 1999
	E. L. G. Saukas , S. W. Song, Efficient selection algorithms on distributed memory computers, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-26, November 07-13, 1998, San Jose, CA
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.943-958, September 1997
	S. A. Jarvis , J. M. D. Hill , C. J. Siniolakis , V. P. Vasilev, Portable and architecture independent parallel performance tuning using BSP, Parallel Computing, v.28 n.11, p.1587-1609, November 2002
	Jeff Hightower , Marcia Talkmitt, 3D in the Pines and on the Plains, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-26, November 07-13, 1998, San Jose, CA
	Alexandros V. Gerbessiotis , Seung-Yeop Lee, Remote memory access: A case for portable, efficient and library independent parallel programming, Scientific Programming, v.12 n.3, p.169-183, August 2004
	Lars Arge , Michael T. Goodrich , Michael Nelson , Nodari Sitchinava, Fundamental parallel algorithms for private-cache chip multiprocessors, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany