Large-scale sorting in parallel memories (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Large-scale sorting in parallel memories (extended abstract)

Full text

Pdf (899 KB)

Source

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

Hilton Head, South Carolina, United States

Pages: 29 - 39

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Mark H. Nodine	Dept. of Computer Science, Brown University, Providence, R. I.
Jeffrey Scott Vitter	Dept. of Computer Science, Brown University, Providence, R. I.

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): 6, Downloads (12 Months): 17, Citation Count: 10

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/113379.113382 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	A. Aggarwa/, A. Chandra and M. Snir, "Hierarchica/Memory with Block Transfer," Proceedings of 28th Annum IEEE Symposium 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	B. Alpern, L. Carter and E. Feig, "Uniform Memory Hierarchies," Proceedings of the 3}st Annual IEEE Symposium on Foundations of Computer Science (October 1990), 600-608.
	ACSb	Bowen Alpern , Larry Carter , Ted Selker, Visualizing computer memory architectures, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
	Flo	R. W. Floyd, "Permuting Information in idealized Two-Level Storage," in Complexity of Computer Calculations, 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]
	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]
	Jil	W. Jilke, "Disk Array Mass Storage Systems: The New Opportunity," Amperif Corporation, September 1986.
	Knu	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
	Lei	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]
	LiV	E. E. Lindstrom and J. S. Vitter, "The Design and Analysis of BucketSort for Bubble Memory Secondary Storage," IEEE Transactions on Computers C-34 (March 1985), 218-233.
	LuP	F. Luccio and L. Pagli, "A Model of Sequential Computation Based on a Pipelined Access to Memory," Proceedings of the 27th Annual Allerton Conference on Communication, Control, and Computing (September 1989).
	Mag	N. B. Maginnis, "Store More, Spend Less: Mid- Range Options Around," Computerworld (November 16, 1986), 71.
	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
	ReV	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]
	Uni	Proposal (NSF Institutional Infrastructure, Massive Information Storage, Management, and Use, University of California at Berkeley, Berkeley, CA, 1989
	ViS	J. S. Vitter , E. A. M. Shriver, Optimal disk I/O with parallel block transfer, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.159-169, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100234]

CITED BY 10

	Peter F. Corbett , Dror G. Feitelson, The Vesta parallel file system, ACM Transactions on Computer Systems (TOCS), v.14 n.3, p.225-264, Aug. 1996
	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
	Sanguthevar Rajasekaran, A framework for simple sorting algorithms on parallel disk systems (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.88-97, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Thomas H. Cormen , Leonard F. Wisniewski, Asymptotically tight bounds for performing BMMC permutations on parallel disk systems, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.130-139, June 30-July 02, 1993, Velen, Germany
	Sanguthevar Rajasekaran, Sorting and selection on parallel disk models, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Mark H. Nodine , Jeffrey Scott Vitter, Deterministic distribution sort in shared and distributed memory multiprocessors, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.120-129, June 30-July 02, 1993, Velen, Germany
	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
	Sanguthevar Rajasekaran, Out-of-core computing on mesh connected computers, Journal of Parallel and Distributed Computing, v.64 n.11, p.1311-1317, November 2004
	James B. Sinclair , Jay Tang , Peter J. Varman, Instability in parallel I/O systems, ACM SIGARCH Computer Architecture News, v.22 n.4, p.11-16, Sept. 1994
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993