A Survey of Parallel Machine Organization and Programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Survey of Parallel Machine Organization and Programming

Full text

Pdf (2.54 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 9 , Issue 1 (March 1977) table of contents

Pages: 29 - 59

Year of Publication: 1977

ISSN:0360-0300

Author

David J. Kuck

Department of Computer Science, University of Ilinois at Urbana-Champaign, Urbana, Illinois

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 90, Citation Count: 38

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/356683.356686 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	FLYNN, M. "Some computer organizations and their effectiveness," IEEE Trans. on Computers C-21, 9 (Sept. 1972), 948-960.
	2	KUCK, D. "Multioperation machine computational complexity," in Proc Symposium on Complexity of Sequential and Parallel Numemcal Algomthms, Academic Press, New York, 1973, pp. 17-47.
	3	BAER, J. L.; AND BOVET, D P. "Compilation of arithmetic expressions for parallel computations," in Proc IFIP Congress, 1968, North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 340-346
	4	James C. Beatty, An axiomatic approach to code optimization for expressions, Journal of the ACM (JACM), v.19 n.4, p.613-640, Oct. 1972 [doi>10.1145/321724.321728]
	5	KucK, D ; AND MURAOKA, Y. "Bounds on the p. arallel evaluation of arithmetic expressmns using assoc:atlvity and commutativity," Acta lnformatica 3, 3 (1974), 203-216.
	6	BRENT, R.; AND TOWLE, R. "On the time reqmred to parse an arithmetic expression for parallel processing," Proc. 1976 Internatl. Conf. on Parallel Processing, IEEE Press, New York, 1976, 254.
	7	Yoichi Muraoka, Parallelism exposure and exploitation in programs, 1971
	8	Paul William Kraska, Parallelism exploitation and scheduling, 1972
	9	KUCK, D.; AND MARUYAMA, K "Time bounds on the parallel evaluation of arithmetic expressions," SIAM J. Computing 4, 2 (June 1975), 147-162.
	10	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	11	David E. Muller , Franco P. Preparata, Restructuring of Arithmetic Expressions For Parallel Evaluation, Journal of the ACM (JACM), v.23 n.3, p.534-543, July 1976 [doi>10.1145/321958.321973]
	12	Shyh-Ching Chen, Speedup of iterative programs in multiprocessing systems., 1975
	13	CHEN, S. C.; AND KUCK, D. "Time and parallel processor bounds for linear recurrence systems," IEEE Trans. Computers C-24, 7 (July 1975), 701-717.
	14	KNUTIt, D. E. "An empirical study of FORTRAN programs," Stanford Univ., Stanford, Cahf., Dept. of Computer Science, Report CS-186, 1970.
	15	KUCK, D ; MURAOK,~, Y.; A~) CHEN, S. C. "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up," IEEE Trans Computers C-21 (Dec 1972), 1293- 1310.
	16	CHEN, S C.; AND SAMEH, A.H. "On parallel triangular system solvers," in Proc. 1975 Sagamore Computer Conf. on Parallel Processing, IEEE Press, New York, 1975, 237-238.
	17	SAMEH, A. H ; CHEN, S. C.; AND KUCK, D. "Parallel Poisson and biharmonic solvers," Computing, 1976.
	18	Hu, T. C "Parallel sequencing and assembly line problems," Operatwns Research 9 (Nov.-Dec. 1961), 841-848.
	19	Edward Willmore Davis, Jr., A multiprocessor for simulation applications., 1972
	20	Ross Albert Towle, Control and data dependence for program transformations., 1976
	21	Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
	22	H. T. Kung, New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences, Journal of the ACM (JACM), v.23 n.2, p.252-261, April 1976 [doi>10.1145/321941.321945]
	23	K~cK, D.; BUDNIK, P.; CHEN, S. C.; D~v:s, E. JR.; HAN, J.; KRASKA, P.; LAWRIE, D.; MURAOKA, Y.; STREBI~NDT, R.; AND TOWLE, R. "Measurements of parallelism in ordinary FORTRAN programs," Computer, (Jan. 1974) 37-46.
	24	CHEN, S. C.; KUCK, D.; TOWLE, R.; AND BANERJEE, U. "Time and parallel processor bounds for Fortran-like loops," to appear m IEEE Trans. Computers.
	25	CHEN, S. C.; KUCK, D.; AND TOWLE, R. "Control and data dependence in ordinary programs,"
	26	Harold S. Stone, An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations, Journal of the ACM (JACM), v.20 n.1, p.27-38, Jan. 1973 [doi>10.1145/321738.321741]
	27	SAMEH, A. H.; AND KUCK, D. "Linear system solvers for parallel computers," Report 75-701, Univ. of Illinois at Urbana- Champaign, Dept. of Computer Science, Feb. 1975.
	28	KUCK, D. J.; AND SAMEH, A.H. "Parallel computation of eigenvalues of real matrices," in Information Processing 71 Proc. IFIP Congress 71, Vol. II, North-Holland Publ. Co., Amsterdam, The Netherlands, 1972, pp. 1266-1272.
	29	SAMs~, A. H.; AND KUCK, D. "A parallel QR-algonthm for symmetric tridmgonal matrices," in Proc. of Second Langley Conf. on Scienhfic Computing,. Also, Univ. of illinois at Urbana Champaign, Dept of Computer Science, Report 75-700, Feb. 1975.
	30	BUZBEE, B. L. "A fast Poisson solver amenable to parallel computation," IEEE Trans. Computers C-22, 8 (1973), 793-796.
	31	HELLER, D. "A survey of parallel algorithms m numerical linear algebra," Dept. of Computer Science, Report, Carnegie- Mellon Univ, Pittsburgh, Pa., Feb. 1976.
	32	MORmSON, P.; AND MORRISON, E. Charles Babbage and his calculating engines, Dover Inc., N. Y., 1961.
	33	ALT, F.L. "A Bell Telephone Laboratories' computing machine~II," Mathematzcal tables and other aids to computation, Vol. 3, The National Research Council, 1948- 1949, pp. 21-28.
	34	LEONbES, C.; AND RUmSOFF, M. "DINA, a digital analyzer for Laplace, Poisson, diffusion, and wave equatmns," AIEE Trans. Commun~catwn and Electromcs 71, (Nov. 1952), 303-309.
	35	ZUSE, K. "Din Feldrechenmaschine," Mathematzk, Technib, W~rtschaft-Mztteilungen 4 (1958), 213-220.
	36	HINTZ, R. G.; AND TATE, D.P. "Control Data STAR-lOOprocessor design," in Proc. ~Compcon 72, IEEE Computer Society Conf. 1972, IEEE, New York, 1972, pp. 1-4.
	37	WATSON, W. J.; AND CARR, H.M. "Operatmnal experiences wlth the T! advanced sc'entific computer, in Proc. 197~ AFIPS National Computer Conf., Vol. 43, AFIPS Press, Montvale, N. J, 1974, pp. 389-397.
	38	BARNES, G.; :BRowN, R.; KATO, M.; KucK, D.; SLOTNICK, D; AND STOKES, R. "The ILLIAC IV Computer," IEEE Trans. Computers C-17, 8 (August 1968), 746-757.
	39	BATCHER, K. E. "STARAN/RADCAP hardware architecture," in Proc. 1973 Sagamore Conf. on Parallel Processing, IEEE Press, New York, 147-152.
	40	AMDAHL, G. M. "Validity of the single processor approach to achieving large scale computing capabilities," in Proc. AFIPS 1967 Sprang Jt. Computer Conf., Vol. 30, Thompson Books, Washington, D.C., 1967, pp. 483-485.
	41	Marvin Minsky, Form and Content in Computer Science (1970 ACM turing lecture), Journal of the ACM (JACM), v.17 n.2, p.197-215, April 1970 [doi>10.1145/321574.321575]
	42	S. Winograd, On the Time Required to Perform Addition, Journal of the ACM (JACM), v.12 n.2, p.277-285, April 1965 [doi>10.1145/321264.321279]
	43	S. Winograd, On the Time Required to Perform Multiplication, Journal of the ACM (JACM), v.14 n.4, p.793-802, Oct. 1967 [doi>10.1145/321420.321438]
	44	BRENT, R. "On the addition of binary numbers," IEEE Trans. Computers Co19 (1970), 758-759.
	45	CHEN, S. C.; AND KUCK, D "Combinational circuit synthesis with time and component bounds," IEEE Trans Computers (July, 1977).
	46	BRENT, R. "The parallel evaluation of arithmetic expressmns in logarithmic time," in Complexity of sequential and parallel numerical algorithms, J. F. Traub, (Ed.), Academic Press, N. Y., 1973, pp. 83-102.
	47	Werner Buchholz, Planning a computer system: Project Stretch, McGraw-Hill, Inc., Hightstown, NJ, 1962
	48	DAvis, E. W. jR., "Concurrent processing of conditmnal jump trees," in Compcon 72, Proc. IEEE Computer Soczety Conf. IEEE, N Y, 1972, pp. 279-281.
	49	KUCK, D. "ILLIAC IV software and application programming," IEEE Trans. Computers C.17, 8 (Aug. 1968), 758-770
	50	BUDNIK, P.; AND KUCK, D. "The organization and use of parallel memories," 1EEE Trans. Computers C.20 (Dec. 1971), 1566-1569.
	51	SWANSON, R. C. "Interconnections for parallel memories to unscramble p-ordered vectors," IEEE Trans. Computers C.23, 11 (Nov. 1974), 1105--1115.
	52	LAWRIE, D. "Access and alignment of data in an array processor," IEEE Trans. Computers C.24, 12 (Dec. 1975), 1145--1155.
	53	I-IELLERMAN, H. D~gital computer system pmnc~ples, McGraw-Hill Inc., N. Y., 1967.
	54	G. J. Burnett , E. G. Coffman, Jr., A Combinatorial Problem Related to Interleaved Memory Systems, Journal of the ACM (JACM), v.20 n.1, p.39-45, Jan. 1973 [doi>10.1145/321738.321742]
	55	~URNETT, G. J.; AND COFFMAN, E. G. JR., "A study of interleaved memory systems," in Proc., AFIPS 1970 Spring Jt. Computer Conf. Vol. 36, AFIPS Press MontvaIe, N.J., 1970, pp. 467-474.
	56	COFFMAN, E. G. JR.; BURNETT, G. J.; X~D SNOWDON,R. A. "On the performance of interleaved memories with multiple-word bandwidths," 1EEE Trans. Computers C-20, pp. 1570-1572
	57	William Daniel Strecker, An analysis of the instruction execution rate in certain computer structures, 1970
	58	RxvI, C V. "On the bandwidth and interference in interleaved memory systems," IEEE Trans. Computers, C-21 (August 1972), 899-901.
	59	CHANG, D.; KUCK, D.; AND LAWaIE, D. "On the effective bandwidth of parallel memories," to appear in 1EEE Trans. Computers, 1977.
	60	SASTRY, K. V.; AND KAXN, R.Y. "On the performance of certain multlprocessor computer orgamzations," IEEE Trans. Computers C-24, 11 (Nov. 1975), 1066-1073.
	61	BHANDARKAR,.D.P. "Analysis of memory interference in multiprocessors," IEEE Trans. Computer C-24, 9 (Sept. 1975), 897- 908.
	62	Forest Baskett , Alan Jay Smith, Interference in multiprocessor computer systems with interleaved memory, Communications of the ACM, v.19 n.6, p.327-334, June 1976 [doi>10.1145/360238.360243]
	63	DAvis, R. L. "Uniform shift networks," Computer 7 (Sept. 1974), 60-71.
	64	BENES, V. E. Mathematical theory of connect~nq networks and telephone tragic, Academic Press, N. Y., 1965.
	65	OPFERMAN, D. C.; AND TsAo-Wu, N. W. "On a class of rearrangeable switching networks," Bell Syst. Tech J. 50 (May-June 1971), 1579-1618.
	66	BATCHER, K. E. "Sorting networks and their apphcations," in Proc. AFIPS 1968 Sprzng Jt. Computer Conf., Vol. 32, Thompson Book Co., Washington, D. C. 1968, pp. 307-314.
	67	Marshall C. Pease, An Adaptation of the Fast Fourier Transform for Parallel Processing, Journal of the ACM (JACM), v.15 n.2, p.252-264, April 1968 [doi>10.1145/321450.321457]
	68	FENG, T. Y. "Data manipulating functions in parallel processing and their implementations," IEEE Trans. Computers C-23, 3 (March 1974), 309-318.
	69	L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973
	70	SIEGEL, H. J. "Analysis techniques for SIMD machine interconnectmn networks and the effects of processor address masks," in Proc. 1975 Sagamore Computer Conf. on Parallel Processing, IEEE Press, New York, 106-109.
	71	BATCHER, K. E. The Fl~p network in STARAN, Goodyear Aerospace Report GER-16344, 1976.
	72	William Howard Stellhorn, A specialized computer for information retrieval., 1974
	73	MOULDER, R. "A data management system utilizing the STARAN associative processor," in Proc. 1973 Sagamore Conf. on Parallel Processing, IEEE Press, New York, p. 161.
	74	Kenneth J. Thurber , Leon D. Wald, Associative and Parallel Processors, ACM Computing Surveys (CSUR), v.7 n.4, p.215-255, Dec. 1975 [doi>10.1145/356654.356659]
	75	KUCK, D. "On the speedup and cost of parallel computation," Proc. on the Complexity of Computatwnal Problem Solving, 1974.

CITED BY 38

	Zhiyuan Li , Pen-Chung Yew, Efficient interprocedural analysis for program parallelization and restructuring, ACM SIGPLAN Notices, v.23 n.9, p.85-99, Sept. 1988
	P. G. Hipes , A. Kuppermann, Gauss-Jordan inversion with pivoting on the Caltech Mark II hypercube, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1621-1634, January 1989, Pasadena, California, United States
	R. H. Perrott , A. Zarea-Aliabadi, Supercomputer languages, ACM Computing Surveys (CSUR), v.18 n.1, p.5-22, March 1986
	T. S. Anantharaman , R. Bisiani, A hardware accelerator for speech recognition algorithms, ACM SIGARCH Computer Architecture News, v.14 n.2, p.216-223, June 1986
	Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987
	David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994
	Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982
	P. Jouvelot, Semantic parallelization: a practical exercise in abstract interpretation, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.39-48, January 21-23, 1987, Munich, West Germany
	Myron Ginsberg, Supercomputers: Challenges to designers and users, Proceedings of the ACM '82 conference, p.121-123, January 1982
	S. S. Leung , M. A. Shanblatt, A conceptual framework for designing ASIC hardware, Proceedings of the 24th ACM/IEEE conference on Design automation, p.592-595, June 28-July 01, 1987, Miami Beach, Florida, United States
	M. Chen , Y. Choo , J. Li, Crystal: from functional description to efficient parallel code, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.417-433, January 19-20, 1988, Pasadena, California, United States
	Bassel R. Arafeh, Vectorization and parallelization interactive assistant, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.573-577, February 1988, Atlanta, Georgia, United States
	John R. Allen , Ken Kennedy, Automatic loop interchange, ACM SIGPLAN Notices, v.19 n.6, p.233-246, June 1984
	Anna R. Karlin , Eli Upfal, Parallel hashing: an efficient implementation of shared memory, Journal of the ACM (JACM), v.35 n.4, p.876-892, Oct. 1988
	Augustus K. Uht , Constantine D. Polychronopoulos , John F. Kolen, On the combination of hardware and software concurrency extraction methods, Proceedings of the 20th annual workshop on Microprogramming, p.133-141, December 01-04, 1987, Colorado Springs, Colorado, United States
	A. Pietracaprina , F. P. Preparata, A practical constructive scheme for deterministic shared-memory access, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.100-109, June 30-July 02, 1993, Velen, Germany
	A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States
	Leslie L. Miller , Tyne Liang, The role of parellelism in file organization, Proceedings of the 1985 ACM thirteenth annual conference on Computer Science, p.381-388, March 1985, New Orleans, Louisiana, United States
	K. Onaga , T. Takechi, On design of rotary array communication and wavefront-driven algorithms for solving large-scale band-limited matrix equations, ACM SIGARCH Computer Architecture News, v.14 n.2, p.308-315, June 1986
	Eli Upfal , Avi Wigderson, How to share memory in a distributed system, Journal of the ACM (JACM), v.34 n.1, p.116-127, Jan. 1987
	G. Chroust , J. R. Mühlbacher, Rivalling multiprocessor organization: a hardware/speed trade-off, ACM SIGARCH Computer Architecture News, v.8 n.5, p.7-10, August 1980
	J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas
	Randy Allen , Ken Kennedy, Automatic loop interchange, ACM SIGPLAN Notices, v.39 n.4, April 2004
	M. S. Anastas , R. F. Vaughan, Direct architectural implementation of a requirements-oriented computing structure, ACM SIGMICRO Newsletter, v.10 n.4, p.93-100, Dec. 1979
	Jacques Cohen , Timothy Hickey , Joel Katcoff, Upper Bounds for Speedup in Parallel Parsing, Journal of the ACM (JACM), v.29 n.2, p.408-428, April 1982
	A. K. Uht , J. F. Kolen, On the combination of hardware and software concurrency extraction methods, ACM SIGMICRO Newsletter, v.19 n.1-2, p.53-57, June 1988
	Dilip Sarkar , Narsingh Deo, Estimating the Speedup in Parallel Parsing, IEEE Transactions on Software Engineering, v.16 n.7, p.677-683, July 1990
	Tsung-Chuan Huang , Slo-Li Chu, A statement based parallelizing framework for processor-in-memory architectures, Information Processing Letters, v.85 n.3, p.159-163, 14 February 2003
	V. Kumar , S. Shekhar , M. B. Amin, A Scalable Parallel Formulation of the Backpropagation Algorithm for Hypercubes and Related Architectures, IEEE Transactions on Parallel and Distributed Systems, v.5 n.10, p.1073-1090, October 1994
	Slo-Li Chu , Tsung-Chuan Huang, SAGE: an automatic analyzing system for a new high-performance SoC architecture-processor-in-memory, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.1, p.1-15, January 2004
	Basile Kamdoum, Speeding up the primal simplex algorithm on parallel computer, ACM SIGMAP Bulletin
	Slo-Li Chu , Tsung-Chuan Huang , Lan-Chi Lee, Improving workload balance and code optimization on processor-in-memory systems, Journal of Systems and Software, v.71 n.1-2, p.71-82, April 2004
	D. L. Eager , J. Zahorjan , E. D. Lozowska, Speedup Versus Efficiency in Parallel Systems, IEEE Transactions on Computers, v.38 n.3, p.408-423, March 1989
	Peter Hibbard, Multiprocessor software design, Proceedings of the ACM 1980 annual conference, p.527-536, January 1980
	David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986
	Walid Abu-Sufah , Alex Y. Kwok, Performance prediction tools for Cedar: a multiprocessor supercomputer, ACM SIGARCH Computer Architecture News, v.13 n.3, p.406-413, June 1985
	Hamed Fatemi , Bart Mesman , Henk Corporaal , Twan Basten , Richard Kleihorst, RC-SIMD: Reconfigurable communication SIMD architecture for image processing applications, Journal of Embedded Computing, v.2 n.2, p.167-179, April 2006
	Benjamin W. Wah , Y. W. Ma, The architecture of MANIP: a parallel computer system for solving NP-complete problems, Proceedings of the May 4-7, 1981, national computer conference, May 04-07, 1981, Chicago, Illinois