A universal interconnection pattern for parallel computers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A universal interconnection pattern for parallel computers

Full text

Pdf (660 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 4 (October 1982) table of contents

Pages: 1073 - 1086

Year of Publication: 1982

ISSN:0004-5411

Author

Leslie M. Goldschlager

Basser Department of Computer Science, University of Sydney, N.S.W. Australia, 2006

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 32, Citation Count: 17

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/322344.322353 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	CHAtqDgA, A K., AND STOCK.MEYER, L J Alternation Proc. 17th Ann IEEE Symp on Foundations of Computer Science, Houston, Texas, Oct. 1976, pp. 98-108.
	3	COOK, S A Linear time simulation of determmlstm two-way pushdown automata. Proc. IF1P 1971, North Holland, Amsterdam, 1971, pp 75-80
	4	FLYNN, M Very high-speed computing systems Proc IEEE 54 (Dec 1966), 1901L1909
	5	GOLDSCHLAGER, L M Synchronous parallel computation Tech Rep No 114, Dep of Computer Science, Univ. of Toronto, Toronto, Ontario, Canada, Dec 1977.
	6	HARTMANIS, J, AND SIMON, J. On the power of mult~phcation m random access machines. Proc. Ann IEEE Symp on Switching and Automata Theory, New Orleans, La, Oct 1974, pp 13-23
	7	KOZEN, D. On parallelism m Turmg machines. Proc 17th Ann. IEEE Syrup on Foundations of Computer Science, Houston, Texas, Oct 1976, pp 89-97
	8	PRATT, V R, AND STOCKMEYER, L J A characterization of the power of vector machines J Comput. Syst Sct. 12, 2 (Apr. 1976), 198-221
	9	S^VlTCH, W J., AND STIMSOr% M.J.Time bounded random access machines with parallel processing Tech Rep. lW 67/76, Mathematlsch Centrum, Amsterdam, Nov 1976
	10	STONE, H S.Parallel proeessmg with the perfect shuffle IEEE Trans Comput C-20. 2 {Feb. 1971), 153-161
	11	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]

CITED BY 17

	Faith E. Fich , Prabhakar L. Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.179-189, August 27-29, 1984, Vancouver, British Columbia, Canada
	Patrick W. Dymond , Walter L. Ruzzo, Parallel RAMs with owned global memory and deterministic context-free language recognition, Journal of the ACM (JACM), v.47 n.1, p.16-45, Jan. 2000
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
	F E Fich , F Meyer auf der Heide , P Ragde , A Wigderson, One, two, three . . . infinity: lower bounds for parallel computation, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.48-58, May 06-08, 1985, Providence, Rhode Island, United States
	Eric W. Allender, P-uniform circuit complexity, Journal of the ACM (JACM), v.36 n.4, p.912-928, Oct. 1989
	C. Slot , P. van Emde Boas, On tape versus core an application of space efficient perfect hash functions to the invariance of space, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.391-400, December 1984
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	Stephen A. Cook, An overview of computational complexity, Communications of the ACM, v.26 n.6, p.400-408, June 1983
	Joseph Gil , Yossi Matias, Fast hashing on a PRAM—designing by expectation, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.271-280, January 28-30, 1991, San Francisco, California, United States
	I. Parberry, A Note on Nondeterminism in Small, Fast Parallel Computers, IEEE Transactions on Computers, v.38 n.5, p.766-767, May 1989
	C.-W. Ho , R. C. T. Lee, A Parallel Algorithm for Solving Sparse Triangular Systems, IEEE Transactions on Computers, v.39 n.6, p.848-852, June 1990
	D. A. Carlson, Modified-Mesh Connected Parallel Computers, IEEE Transactions on Computers, v.37 n.10, p.1315-1321, October 1988
	G. E. Blelloch, Scans as Primitive Parallel Operations, IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989
	A. Dal Palú , E. Pontelli , D. Ranjan, Sequential and parallel algorithms for the NCA problem on pure pointer machines, Theoretical Computer Science, v.352 n.1, p.108-135, 7 March 2006
	Véronique Terrier, Low complexity classes of multidimensional cellular automata, Theoretical Computer Science, v.369 n.1, p.142-156, 15 December 2006
	Petr Sosík, The computational power of cell division in P systems: Beating down parallel computers?, Natural Computing: an international journal, v.2 n.3, p.287-298, 2003
	I Parberry, Parallel speedup of sequential machines: a defense of parallel computation thesis, ACM SIGACT News, v.18 n.1, p.54-67, Summer 1986