Supporting the hypercube programming model on mesh architectures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Supporting the hypercube programming model on mesh architectures: (a fast sorter for iWarp tori)

Full text

Pdf (1.11 MB)

Source

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

San Diego, California, United States

Pages: 148 - 157

Year of Publication: 1992

ISBN:0-89791-483-X

Author

Thomas M. Stricker

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): 4, Downloads (12 Months): 16, Citation Count: 3

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

	AKS83	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	Bat68	K. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computing Conference, volume 32, pages 307-314, 1968.
	BCC+88	S. Borkar , R. Cohn , G. Cox , S. Gleason , T. Gross, Warp: an integrated solution of high-speed parallel computing, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.330-339, November 12-17, 1988, Orlando, Florida, United States
	BCC+90	Shekhar Borkar , Robert Cohn , George Cox , Thomas Gross , H. T. Kung , Monica Lam , Margie Levine , Brian Moore , Wire Moore , Craig Peterson , Jim Susman , Jim Sutton , John Urbanski , Jon Webb, Supporting systolic and memory communication in iWarp, Proceedings of the 17th annual international symposium on Computer Architecture, p.70-81, May 28-31, 1990, Seattle, Washington, United States
	Bla90	T. Blank. The MasPar MP-I architecture, in 35th IEEE Computer Society International Conference, pages 20- 40, Spring 1990.
	BLM+91	Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
	BS78	G. Baudet and D. Stevenson. Optimal sorting algorithms for parallel computers. IEEE Transactions on Computers, C-27:84-87, 1978.
	CLR90	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	CTH89	S.L. Johnson C. T. Ho. Embedding meshes in boolean cubes by graph decomposition. Computer science technical report, Yale University, New Haven, CT 06520, 1989.
	Gro89	T. Gross, Communication in iWarp systems, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.436-445, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76311]
	Hoa61	C.A.R. Hoare. Quicksort. Computing Journal, 5, 1961.
	KH88	B. Kahle and D. Hillis. The connection machine model cm-1 architecture. IEEE Systems, Man, and Cybernetics Special Issue, March 1988.
	Knu73	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
	Kun91a	M. Kunde. Routing and sorting on grids. Habilitationsschrift, Fakultaet fuer Mathematik und informatik der TU Muenchen, 1991.
	Kun91b	M. Kunde. Sorting on meshes. In Proceedings of the 32st Annual Symposium on Foundations of Computer Science, October 1991.
	LSBD88	S. LakshmivarahanL. S. Barasch andS. K. Dhall. Generalized gray codes and their properties. In Third International Conference on Supercomputing, May 1988.
	MS89	Y. Mansour and L. Schulman. Sorting on a ring of processors. Technicalreport, Laboratory of Computer Science, Massachusetts Inst. of Technology, Cambridge MA, 1989.
	Pat90	M.S. Paterson. imporoved sorting networks with O(log n) depth. Algorithm&a, 5:75-92, 1990.
	Pri91	J. Prins. Efficient bitonic sorting of large arrays on the MasPar MP-1. Technical Report TR91-041, University of North Carolina, Chapel Hill NC, 1991.
	RR89	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]
	Sch92	Eric Schwabe. Personal Communication, January 1992.
	She91	Jonathan Shewchuk. Personal Communication, August 1991.
	SS88	C P Schnorr , A Shamir, An optimal sorting algorithm for mesh connected computers, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.255-263, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12156]
	TK77	C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, v.20 n.4, p.263-271, April 1977 [doi>10.1145/359461.359481]
	ZB91	Marco Zagha , Guy E. Blelloch, Radix sort for vector multiprocessors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.712-721, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126164]

CITED BY 3

	Thomas M. Stricker , Jonathan C. Hardwick, From AAPC algorithms to high performance permutation routing and sorting, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.200-203, June 24-26, 1996, Padua, Italy
	Anja Feldmann , Thomas M. Stricker , Thomas E. Warfel, Supporting sets of arbitrary connections on iWarp through communication context switches, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.203-212, June 30-July 02, 1993, Velen, Germany
	Anja Feldmann , Thomas Gross , David O'Hallaron , Thomas M. Stricker, Subset barrier synchronization on a private-memory parallel system, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.209-218, June 29-July 01, 1992, San Diego, California, United States