Deterministic distribution sort in shared and distributed memory multiprocessors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic distribution sort in shared and distributed memory multiprocessors

Full text

Pdf (1.01 MB)

Source

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

Velen, Germany

Pages: 120 - 129

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Mark H. Nodine
Jeffrey Scott Vitter

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 40, Citation Count: 18

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/165231.165247 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.

	AAC	A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
	ACSa	Alok Aggarwal, Ashok K. Chandra, and Marc Snir, "Hierarchical Memory with Block Transfer," Proceedinos of #8th Ann#tal IEEE #yrnposium on Foundations of Computer Science (October 1987), 204-216.
	AgV	Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
	ACF	Bowen Alpern, Larry Carter, and Ephraim Feig, "Uniform Memory Hierarchies," Proceedings of the 31s# Annual IEEE Symposium on Foundations of Computer Science (October 1990), 600-608.
	Arg	Lars Arge, January 1993, private communication.
	BFP	Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan, "Time Bounds for Selection," J. Computer and System Sciences 7 (1973), 448-461.
	Col	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	CyP	Robert Cypher , C. Greg Plaxton, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Journal of Computer and System Sciences, v.47 n.3, p.501-548, Dec. 1993 [doi>10.1016/0022-0000(93)90043-V]
	Flo	Robert W. Floyd, "Permuting Information in Idealized Two-Level Storage," in Compleziiy of Computer Computations, R. Miller and J. Thatcher, ed., Plenum, 1972, 105-109.
	GHK	Garth A. Gibson , Lisa Hellerstein , Richard M. Karp , Randy H. Katz , David A. Patterson, Coding Techniques for Handling Failures in Large Disk Arrays, University of California at Berkeley, Berkeley, CA, 1988
	GiS	David Gifford , Alfred Spector, The TWA reservation system, Communications of the ACM, v.27 n.7, p.650-665, July 1984 [doi>10.1145/358105.358192]
	GoS	Mark Goldberg , Thomas Spencer, Constructing a maximal independent set in parallel, SIAM Journal on Discrete Mathematics, v.2 n.3, p.322-328, August 1989 [doi>10.1137/0402028]
	HoK	Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
	IsS	Amos Israeli , Y. Shiloach, An improved parallel algorithm for maximal matching, Information Processing Letters, v.22 n.2, p.57-60, 1986 [doi>10.1016/0020-0190(86)90141-9]
	Jil	W. Jilke, "Disk Array Mass Storage Systems: The New Opportunity," Amperif Corporation, September 1986.
	Lei	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	Luba	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	Lubb	Michael G. Luby, "'Removing l%andomness in a Parallel Computation Without a Processor Penalty," International Computer Science Institute, TR-89-044, July 1989, also appears in Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science, (October 1988), 162-173.
	Mag	Ninamary Buba Maginnis, "Store More, Spend Less: Mid-Range Options Around," Computer. world (November 16, 1987), 71-82.
	NoV	Mark H. Nodine , Jeffrey Scott Vitter, Large-scale sorting in parallel memories (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.29-39, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113382]
	PGK	David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
	RaR	S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
	Uni	Proposal (NSF Institutional Infrastructure, Massive Information Storage, Management, and Use, University of California at Berkeley, Berkeley, CA, 1989
	ViN	Jeffrey Scott Vitter , Mark H. Nodine, Large-scale sorting in uniform memory hierarchies, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.107-114, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1008]
	ViSa	Jeffrey Scott Vitter and Elizabeth A. M. Shriver, "Algorithms for Parallel Memory I: Two-Level Memories," Algorithmica, to appear.
	ViSb	Jeffrey Scott Vitter and Elizabeth A. M. Shriver, "Algorithms for Parallel Memory II: Hierarchical Multilevel Memories," Algoriihmica, to appear.

CITED BY 18

	Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
	Jeffrey Scott Vitter , David A. Hutchinson, Distribution sort with randomized cycle, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.77-86, January 07-09, 2001, Washington, D.C., United States
	Mark H. Nodine , Jeffrey Scott Vitter, Greed sort: optimal deterministic sorting on parallel disks, Journal of the ACM (JACM), v.42 n.4, p.919-933, July 1995
	Rakesh D. Barve , Edward F. Grove , Jeffrey Scott Vitter, Simple randomized mergesort on parallel disks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.109-118, June 24-26, 1996, Padua, Italy
	Jeffrey Scott Vitter, External memory algorithms, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.119-128, June 01-04, 1998, Seattle, Washington, United States
	Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States
	Hui Li , Kenneth C. Sevcik, Parallel sorting by over partitioning, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.46-56, June 27-29, 1994, Cape May, New Jersey, United States
	Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001
	Leonard F. Wisniewski, Structured permuting in place on parallel disk systems, Proceedings of the fourth workshop on I/O in parallel and distributed systems: part of the federated computing research conference, p.128-139, May 27-27, 1996, Philadelphia, Pennsylvania, United States
	Jop F. Sibeyn, External selection, Journal of Algorithms, v.58 n.2, p.104-117, February 2006
	Alok Aggarwal , C. Greg Plaxton, Optimal parallel sorting in multi-level storage, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.659-668, January 23-25, 1994, Arlington, Virginia, United States
	Jeffrey Scott Vitter, External memory algorithms, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Roman Dementiev , Peter Sanders, Asynchronous parallel disk sorting, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Juha Kärkkäinen , Peter Sanders , Stefan Burkhardt, Linear work suffix array construction, Journal of the ACM (JACM), v.53 n.6, p.918-936, November 2006
	Jeffrey Scott Vitter , David Alexander Hutchinson, Distribution sort with randomized cycling, Journal of the ACM (JACM), v.53 n.4, p.656-680, July 2006
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
	Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008
	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