Optimal disk I/O with parallel block transfer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal disk I/O with parallel block transfer

Full text

Pdf (1.04 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 159 - 169

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

J. S. Vitter	Dept. of Computer Science, Brown University, Providence, R.I.
E. A. M. Shriver	Bell Communications Research, 444 Hoes Lane, Piscataway, N.J.

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 40, Citation Count: 16

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/100216.100234 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	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]
	2	A. Aggarwal, A. Chandra & M. Snir, "Hierarchical Memory with Block Transfer," Proceedings of 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA (October 1987).
	3	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]
	4	B. Alpern, L. Carter & E. Feig, "Uniform Memory Hierarchies," November 1989, manuscript.
	5	J. Lawrence Carter , Mark N. Wegman, Universal classes of hash functions (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.106-112, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803400]
	6	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]
	7	L. Kleinrock, in Queueing Systems, Volume I: Theory, Wiley and Sons, New York, 1979.
	8	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
	9	E. E. Lindstrom & J. S. Vitter, "The Design and Analysis of BucketSort for Bubble Memory Secondary Storage," IEEE Transactions on Computers C-34 (March 1985), 218-233.
	10	Mark H. Nodine , Jeffrey S Vitter, Greed Sort: An Optimal External Sorting Algorithm for Multiple Disks, Brown University, Providence, RI, 1991
	11	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]
	12	J. Savage & J. S. Vitter, "Parallelism in Space- Time Tradeoffs," in Advances in Computing Research, Volume 4, F. P. Preparata, ed., JAI Press, 1987, 117-146, also appears in Proceedings of the International Workshop on Parallel Computing and VLSI, Amalfi, Italy (May 1984), P. Bertolazzi and F. Luccio, ed., Elsevier Science Press, 1985, 49-58.
	13	If. S. Stone, "Parallel Processing with the Perfect Shuffle," IEEE Transactions on ComputersC- 20 (February 1971), 153-161.
	14	Jeffrey Scott Vitter , Philippe Flajolet, Average-case analysis of algorithms and data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	15	J. S. Vitter & E. A. Shriver, "Optimal Disk I/O with Parallel Block Transfer," Department of Computer Science, Brown University, Technical Report, 1990.

CITED BY 16

	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
	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
	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
	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
	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
	Neil Immerman , Sushant Patnaik , David Stemple, The expressiveness of a family of finite set languages, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.37-52, May 29-31, 1991, Denver, Colorado, United States
	Paolo Ferragina , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Two-dimensional substring indexing, Journal of Computer and System Sciences, v.66 n.4, p.763-774, 1 June 2003
	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
	LuoQuan Zheng , Per-Åke Larson, Speeding Up External Mergesort, IEEE Transactions on Knowledge and Data Engineering, v.8 n.2, p.322-332, April 1996
	Luo Guangchun , Zhang Jun , Lu Xianliang , Lu Jun, Active block layout: a high performance disk layout mechanism, ACM SIGOPS Operating Systems Review, v.37 n.1, p.5-13, January 2003
	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
	Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
	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
	Francesco Silvestri, On the limits of cache-oblivious rational permutations, Theoretical Computer Science, v.402 n.2-3, p.221-233, August, 2008
	John E. Savage , Mohammad Zubair, A unified model for multicore architectures, Proceedings of the 1st international forum on Next-generation multicore/manycore technologies, November 24-25, 2008, Cairo, Egypt