An Efficient General-Purpose Parallel Computer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Efficient General-Purpose Parallel Computer

Full text

Pdf (1.60 MB)

Source

Journal of the ACM (JACM) archive
Volume 30 , Issue 2 (April 1983) table of contents

Pages: 360 - 387

Year of Publication: 1983

ISSN:0004-5411

Authors

Zvi Galil	Department of Computer Science, Columbia University, New York, NY and Tel-Aviv University, Israel
Wolfgang J. Paul	IBM Research Laboratory, 5600 Cottle Road, San Jose, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 45, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/322374.322382 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	Dana Angluin , Leslie G. Valiant, Fast probabilistic algorithms for hamiltonian circuits and matchings, Proceedings of the ninth annual ACM symposium on Theory of computing, p.30-41, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803393]
	3	BARZDIN, YA M., AND KALNIN'SH, YA.YA A universal automaton with vanable structure Automatic Control and Computer Science 8, 2 (1974), 9-17 {Engl traits available from Allerton Press, New York, pp. 6-121
	4	BaTCHER, K.E Sorting networks and their applications. In Proc AFIPS Spring Joint Computer Conference Vol 32 (April 1968), AFIPS Press, Arlington, Va,, 1968, pp. 307-314.
	5	BORODIN, A.On relating time and space to stze and depth. SIAM ~ Comput. 6, 4 (1977), 733-744.
	6	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	7	COLE, S.N. Real-time computation by Lterative array of finite state machines. Ph D. Dissertation, Harvard Umv, Cambridge, Mass., August 1964.
	8	COOK, S.A. Towards a complexity theory of synchronous parallel computatton. Presented at Int. Syrup tiber Logtk und Algortthmik zu Ehren von Professor Ernst Specker, Zurich, Swttz., Feb. 1980.
	9	DYMOND, P, AND COOK, S.A.,Hardware complexity and parallel computation In Conf. Rec. 21th Ann. IEEE Syrup on Foundations of Computer Science (Syracuse, N Y., Oct 1980), IEEE, New York, 1980, pp 360-372
	10	GALIL, Z., AND PAUL, W.J. An effioent general-purpose parallel computer Unpubhshed manuscript, Tel-Aviv Univ., Aug 1980 (first version Apr 1980)
	11	Leslie M. Goldschlager, A unified approach to models of synchronous parallel machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.89-94, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804336]
	12	GUIBAS, L J, KtlNG, H T, ANt) TMOMPSON, C.D Direct VLSI implementation of oombinatoml algorithm Res Rep, Dep of Computer Soence, Carnegie-Mellon Univ., Pittsburgh, Pa., Mar. 1979.
	13	HoovER, H J Some topics m ctrcuit complexity Tech. Pep. 139/80, Dep. of Computer Science, Univ of Toronto, Toronto, Ont., Canada, Dec. 1979.
	14	JA'JA', J , AND SIMON, J Parallel algorithms in graph theory' Planarity testing. SlAM d. Comput. 11, (May 1982), 314-328
	15	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
	16	KRAPCHENKO, V.M Asymptotic esumattoa of addgion time of a parallel adder. Probl. KIbern. 19, 107-122 {Engl. transl in Syst Theory Res 19 (1970), 105-122}
	17	KUNG, H T., AND LEISERSON, C E Systolic arrays (for VLSI) In 1978 Sparse Matrix Computations Syrup. (Knoxville, Tenn, Nov 1978), SIAM, Phdadelphia, Pa., 1979, pp. 256--282.
	18	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	19	LEv, G, PIPPENGER, N., AND VALIANT, L.G, A fast parallel algonthm for routing in permutation networks. IEEE Trans. Comput C-30, 2 (Feb. 1981), 93-100.
	20	K. N. Levitt , W. H. Kautz, Cellular arrays for the solution of graph problems, Communications of the ACM, v.15 n.9, p.789-801, Sept. 1972 [doi>10.1145/361573.361576]
	21	NASSIMI, D., AND SAHNI, S.B~tomc sort on a mesh-connected parallel computer. IEEE Trans. Comput C-28, 1 (Jan 1979), 2-7
	22	David Nassimi , Sartaj Sahni, An optimal routing algorithm for mesh-connected Parallel computers, Journal of the ACM (JACM), v.27 n.1, p.6-29, Jan. 1980 [doi>10.1145/322169.322172]
	23	NASSIMI, D., AND SAHNI, S A self-routing Benes network and parallel permutation algorithms. IEEE Dans Comput C-30, 5 (May 1981), 332+340
	24	OFMAN, Ju.P A universal automaton. Trans of the Moscow Math See. 14 (1965), 186-199 {Engl. tran8 ARN. Math Soc, Providence, R I (1967), 200-215}
	25	PAUL, W J., AND REISCItUK, R On alternauon, II Acta lnf 14, 4 (1980), 391-403.
	26	PIPPENGER, N On simultaneous resource bounds In Conf. Rec 20th Ann. IEEE 3ymp. on Founda. ttons of Computer Saence (Puerto Rico, Oct. 1979), IEEE, New York, 1979, pp. 307-311.
	27	PREPARATA, F P.New parallel sorting schemes. IEEE Trans. Comput C-27 (1978), 669-673,
	28	PREPARATA, F P., AND VUILLEMIN, J.The cube-connected-cycles A versatile network for parallel computation In Conf Rec 20th Ann IEEE Syrup on Foundatwns of Computer Science (Puerto Rico, Oct 1979), IEEE, New York, 1979, pp 140--147
	29	SAVAOE, C., AND JA'JA', J Fast, efficient parallel algorithms for some graph problems. Unpublished manuscript, Dep. of Computer Science, Permsylvama State Univ., University Park, Pa., 1979.
	30	SCHONHAGE, A.Storage modificauon machines Tech Rep., Tubingen Univ., West Germany, 1979.
	31	SOtONHAGE, A., AND STRASSEN, V.SctmeUe Multtplakattoa grosser Zalden. Cemput 7 (1971), 281-292.
	32	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
	33	TUNG, C Arithmetic. In Computer Saence, A F Cardenas, L Presser, and M.A. Matin, Eds., Wdley-Intersclence, New York, 1972.
	34	Eli Upfal, Efficient schemes for parallel communication, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.55-59, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806682]
	35	Leslie G. Valiant, Universal circuits (Preliminary Report), Proceedings of the eighth annual ACM symposium on Theory of computing, p.196-203, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803649]
	36	Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]
	37	WALLACE, C.S. A suggesuon for a fast multtpher IEEE Trans Electron Circ. EC.13 (1964), 14-17
	38	WYLUE, J C.The complexity of parallel computations Ph D Dissertation, Computer Science Dep., Cornell Univ., Ithaca, N Y., Aug. 1981.

CITED BY 8

	Friedhelm Meyer auf der Heide , Martin Storch , Rolf Wanka, Optimal trade-offs between size and slowdown for universal parallel networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.119-128, June 24-26, 1995, Santa Barbara, California, United States
	Eli Upfal, A probabilistic relation between desirable and feasible, models of parallel computation, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.258-265, December 1984
	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
	Yukon Chang , Janos Simon, Continuous routing and batch routing on the hypercube, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.272-281, August 11-13, 1986, Calgary, Alberta, Canada
	Abdelaziz Fellah , Sheng Yu, Iterative tree automata, alternating Turing machines, and uniform Boolean circuits: relationships and characterization, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.1159-1166, March 1992, Kansas City, Missouri, United States
	Moon Jung Chung , Edward J. Toy , Aarti Gupta, A parallel computer based on cube connected cycles for wafer scale integration, Proceedings of 1986 ACM Fall joint computer conference, p.325-335, November 1986, Dallas, Texas, United States
	Eric W. Allender, P-uniform circuit complexity, Journal of the ACM (JACM), v.36 n.4, p.912-928, Oct. 1989
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984