Asymptotically tight bounds for performing BMMC permutations on parallel disk systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Asymptotically tight bounds for performing BMMC permutations on parallel disk systems

Full text

Pdf (1.00 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: 130 - 139

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Thomas H. Cormen
Leonard F. Wisniewski

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): 8, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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.165248 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.

	ACS87	Alok Aggarwal, Ashok K. Chandra, and Marc Snir. Hierarchical memory with block transfer. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 204-216, October 1987.
	AV88	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]
	Cor92	Thomas H. Cormen, Virtual memory for data-parallel computing, Massachusetts Institute of Technology, Cambridge, MA, 1993
	Cor93	Thomas H. Cormen, Fast permuting on disk arrays, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.41-57, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1004]
	EHJ92	Alan Edelman, Steve Heller, and S. Lennart Johnsson. Index transformation algorithms in a linear algebra framework. Technical Report LBL-31841, Lawrence Berkeley Laboratory, 1992.
	Flo72	Robert W. Floyd. Permuting information in idealized two-level storage. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, pages 105-109. Plenum Press, 1972.
	JH91	S. Lennart Johnsson and Ching-Tien Ho. Generalized shuffle permutations on boolean cubes. Technical Report TR-04-91, Harvard University Center for Research in Computing Technology, February 1991.
	NV90	Mark H. Nodine , Jeffrey S Vitter, Greed Sort: An Optimal External Sorting Algorithm for Multiple Disks, Brown University, Providence, RI, 1991
	NV91	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]
	NV92	Mark H. Nodine , Jeffrey S Vitter, Optimal Deterministic Sorting on Parallel Disks, Brown University, Providence, RI, 1992
	VS90	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]
	VS92	Jeffrey S Vitter , Elizabeth A.M. Shriver, Algorithms for Parallel Memory I: Two-Level Memories, Brown University, Providence, RI, 1992

CITED BY 5

	Thomas H. Cormen , Kristin Bruhl, Don't be too clever: routing BMMC permutations on the MasPar MP-2, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.288-297, June 24-26, 1995, Santa Barbara, California, 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
	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
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
	Garth A. Gibson , Jeffrey Scott Vitter , John Wilkes, Strategic directions in storage I/O issues in large-scale computing, ACM Computing Surveys (CSUR), v.28 n.4, p.779-793, Dec. 1996