A Survey of Parallel Machine Organization and Programming
ACM Computing SurveysPublished 1 March 1977
David J. Kuck
Citations201
SJR quartileQ1
SJR score5.80
SNIP11.03
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper is a survey of parallel machine organizations and programming, and various aspects of machine organization are discussed, including processors, memories, and alignment networks.
Abstract
article A Survey of Parallel Machine Organization and Programming Share on Author: David J. Kuck Department of Computer Science, University of Ilinois at Urbana-Champaign, Urbana, Illinois Department of Computer Science, University of Ilinois at Urbana-Champaign, Urbana, IllinoisView Profile Authors Info & Claims ACM Computing SurveysVolume 9Issue 1March 1977 pp 29–59https://doi.org/10.1145/356683.356686Online:01 March 1977Publication History 170citation1,288DownloadsMetricsTotal Citations170Total Downloads1,288Last 12 Months10Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Keywords
Computer Science
Validity of the single processor approach to achieving large scale computing capabilities
4,200 Citations1967Gene M. Amdahl
IEEE Transactions on ComputersSome Computer Organizations and Their Effectiveness
1,644 Citations1972Michael Flynn
A hierarchical model of computer organizations is developed, based on a tree model using request/service type resources as nodes, which indicates that saturation develops when the fraction of task time spent locked out approaches 1/n, where n is the number of processors.
IEEE Transactions on ComputersAccess and Alignment of Data in an Array Processor
1,119 Citations1975Duncan H. Lawrie
This paper discusses the design of a primary memory system for an array processor which allows parallel, conflict-free access to various slices of data, and subsequent alignment of these data for processing, and a network based on Stone's shuffle-exchange operation is presented.
Operations ResearchParallel Sequencing and Assembly Line Problems
895 Citations1961T. C. Hu
This paper deals with a new sequencing problem in which n jobs with ordering restrictions have to be done by men of equal ability, and how to arrange a schedule that requires the minimum number of men to complete all jobs within a prescribed time T.
Journal of the ACMThe Parallel Evaluation of General Arithmetic Expressions
818 Citations1974Richard P. Brent
It is shown that arithmetic expressions with n ≥ 1 variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4 log 2 + 10(n - 1) using processors which can independently perform arithmetic operations in unit time.
Software Practice and ExperienceAn empirical study of FORTRAN programs
682 Citations1971Donald E. Knuth
The principal conclusion which may be drawn is the importance of a program ‘profile’, namely a table of frequency counts which record how often each statement is performed in a typical run; there are strong indications that profile‐keeping should become a standard practice in all computer systems, for casual users as well as system programmers.
Communications of the ACMThe parallel execution of DO loops
605 Citations1974Leslie Lamport
Methods are developed for the parallel execution of different iterations of a DO loop and practical application to the design of compilers for such computers is discussed.
IEEE Transactions on ComputersThe ILLIAC IV Computer
524 Citations1968Greg Barnes, Rebecca M. Brown +4 more
The structure of ILLIAC IV, a parallel-array computer containing 256 processing elements, is described, special features include multiarray processing, multiprecision arithmetic, and fast data-routing interconnections.
Banyan networks for partitioning multiprocessor systems
512 Citations1998L. Rodney Goke, G. Jack Lipovski
Journal of the ACMAn Adaptation of the Fast Fourier Transform for Parallel Processing
380 Citations1968Marshall C. Pease
A modified version of the Fast Fourier Transform is developed and described and it is suggested that this form is of general use in the development and classification of various modifications and extensions of the algorithm.
Journal of the ACMAn Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
319 Citations1973Harold S. Stone
An efficient parallel algorithm is presented in which computation time grows as log 2, which can be used to solve recurrence relations of all orders.
IEEE Transactions on ComputersThe Organization and Use of Parallel Memories
288 Citations1971Paul P. Budnik, David J. Kuck
As computer CPUs get faster, primary memories tend to be organized in parallel banks, and important questions of design and use of such memories are discussed.
Bell System Technical JournalOn a Class of Rearrangeable Switching Networks Part I: Control Algorithm
251 Citations1971D. C. Opferman, N. Tsao-Wu
An algorithm is developed to control a class of rearrangeable switching networks, particularly with the base-2 structure, and system organization and processing time for rearranging the network are studied and are shown to be practical.
IEEE Transactions on ComputersOn the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting Speedup
226 Citations1972David J. Kuck, Yuki Muraoka +1 more
Algorithms are presented for handling arithmetic assignment statements, DO loops and IF statement trees, and evidence is given that for very simple Fortran programs 16 processors could be effectively used operating simultaneously in a parallel or pipeline fashion.
IEEE Transactions on ComputersAnalysis of Memory Interference in Multiprocessors
218 Citations1975Dileep Bhandarkar
This paper presents Markov chain models for analyzing the extent of memory interference in multiprocessor systems with a crosspoint switch for processor-memory communication and the results predicted are compared with some simulation results and some actual measurements on C.mmp, a multipROcessor system being built at Carnegie-Mellon University.
IEEE Transactions on ComputersData Manipulating Functions in Parallel Processors and Their Implementations
162 Citations1974Tse-Yun Feng
It is shown that the data manipulator designs presented in this paper are extremely flexible to suit the requirements of various parallel processors.
Communications of the ACMInterference in multiprocessor computer systems with interleaved memory
143 Citations1976Forest Baskett, Alan Jay Smith
The model results provide a good indication of the performance that should be expected from real systems of this type and suggest that the results are valid for a much larger class of models, including those more nearly like real systems than the simple model.
Journal of the ACMOn the Time Required to Perform Addition
112 Citations1965S. Winograd
If the group operation is adding integers modulo t~, it is shown that the lower bound behaves as log log a(t~), where a(,) is the largest power of a prime which divides ~.4bslracl.
IEEE Transactions on ComputersILLIAC IV Software and Application Programming
109 Citations1968David J. Kuck
An overview of the ILLIAC IV system is given and its software plans are discussed.
Journal of the ACMForm and Content in Computer Science (1970 ACM turing lecture)
105 Citations1970Marvin Minsky
This essay suggests form-content confusion in theory of computation, in programming languages, and in education, and argues that an excessive preoccupation with formalism is impeding the authors' development.
ACM eBooksForm and content in computer science
98 Citations2007Marvin Minsky
Form-content confusion is discussed relative to three areas: theory of computation, programming languages, and education.
IEEE Transactions on ComputersOn the Effective Bandwidth of Parallel Memories
97 Citations1977Chang, Kuck +1 more
The object of this paper is to bring together several models of interleaved or parallel memory systems and to expose some of the underlying assumptions about the address streams in each model.
IEEE Transactions on ComputersTime and Parallel Processor Bounds for Linear Recurrence Systems
94 Citations1975Shyh-Ching Chen, David J. Kuck
By a simple transformation, the results can also be applied to the solution of any triangular linear system of equations Ax̄ = b̄, and the computer need only perform one type of operation at each time step.
ACM Computing SurveysAssociative and Parallel Processors
90 Citations1975Kenneth J. Thurber, Leon D. Wald
This paper covers the topics of system categorizations, applications, main tradeoff issues, historically important architectures, and the architectures of systems that are currently available on the subject of parallel and associative processors.
An analysis of the instruction execution rate in certain computer structures
81 Citations1970William D. Strecker
A simple automatic design program is proposed which optimally configures computer structures from a set of available components and relates the instruction execution rate to the memory and processor speeds, their number, and their interconnection.
Journal of the ACMOn the Time Required to Perform Multiplication
75 Citations1967S. Winograd
A lower bound on the time required to perform multiplication, as well as multiplication modulo N, is derived and it is shown that these lower bounds can be approached.
ComputerMeasurements of parallelism in ordinary FORTRAN programs
67 Citations1974David J. Kuck, Paul P. Budnik +8 more
This paper contains experimental measurements of a rather wide class of algorithms, which should be helpful in establishing some parameters of machine organization.
A study of interleaved memory systems
57 Citations1970G. J. Burnett, E. G. Coffman
In these investigations the properties of addresses generated by instructions and data have been distinguished and results of mathematical analyses of models of interleaved memory systems are discussed.
ComputingParallel Poisson and Biharmonic solvers
50 Citations1976Ahmed Sameh, Shuning Chen +1 more
This paper develops direct and iterative algorithms for the solution of finite difference approximations of the Poisson and Biharmonic equations on a square, using a number of arithmetic units in parallel.
IEEE Transactions on ComputersOn the Addition of Binary Numbers
48 Citations1970Richard P. Brent
An upper bound is derived for the time required to add numbers modulo 2n, using circuit elements with a limited fan-in and unit delay, and assuming that all numbers have the usual binary encoding.
Journal of the ACMNew Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
46 Citations1976H. T. Kung
It is shown that by using parallelism the evaluation of any first-order rational recurrence of degree greater than 1 can be sped up at most by a constant factor, no matter how many processors are used and how large the size of the problem is.
IEEE Transactions on ComputersOn the Bandwidth and Interference in Interleaved Memory Systems
45 Citations1972C. V. Ravi
A model to estimate the bandwidth and interference in an interleaved memory system in a multiprocessor system is described and allows queuing on busy modules, and the results obtained show that previous results are rather pessimistic.
Journal of the ACMUpper Bounds for the Total Path Length of Binary Trees
45 Citations1973Chris K.C. Wong, J. Nievergelt
Two upper bounds for the total path length of binary trees are obtained, one is for node-trees, and bounds the internal (or root-to-node) path length; the other is for leaf-t trees, and limits the external path length.
IEEE Transactions on ComputersA Fast Poisson Solver Amenable to Parallel Computation
42 Citations1973B.L. Buzbee
The matrix decomposition Poisson solver is developed for the five-point difference approximation to Poisson's equation on a rectangle and its suitability for parallel computation, its simplicity, and its performance relative to successive overrelaxation are discussed.
IFIP CongressCompilation of arithmetic expressions for parallel computations.
41 Citations1968Jean-Loup Baer, Daniel P. Bovet
Plant bacterial diseases are routinely managed with scheduled treatments based on heavy metal compounds or on antibiotics; to reduce the negative environmental impact due to the use of such chemical compounds, as pollution or selection of antibiotic resistant pathogens, the integrated control management is required.
Journal of the ACMRestructuring of Arithmetic Expressions For Parallel Evaluation
38 Citations1976David E. Muller, Franco P. Preparata
The authors conjecture that the present coefficients are the best possible, since they have exhibited expressions which seem to require these times within an additive constant.
Journal of the ACMAn axiomatic approach to code optimization for expressions
37 Citations1972James C. Beatty
An axiomatic approach is proposed as a means of specifying precisely what liberties are permitted in evaluating expressions, and two algorithms are given for finding optimal equivalent forms of an expression not having multiple references to any variable.
IEEE Transactions on ComputersInterconnections for Parallel Memories to Unscramble p-Ordered Vectors
32 Citations1974R. C. Swanson
This paper considers the problem of unscrambling vectors when the vectors belong to a class called p-ordered vectors, defined in such a way that elements that should be adjacent in an unscrambled vector are p elements apart in the p- ordered vector.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Parallel Computation of Eigenvalues of Real Matrices
30 Citations1971David J. Kuck, Ahmed Sameh
The implementation of three standard matrix eigenvalue computation methods on an array machine with high efficiency is described, including Jacobi and Householder algorithms for real symmetric matrices, and the QR algorithm for real nonsymmetricMatrices.
IEEE Transactions on ComputersOn the Performance of Certain Multiprocessor Computer Organizations
26 Citations1975Kuchibhotla Venkatachalapati Sastry, Richard Y. Kain
Analytic models are developed to evaluate the performance of a multiprocessor computer system and Markov chain techniques are used to model memory conflicts when the memory is modularized.
SIAM Journal on ComputingTime Bounds on the Parallel Evaluation of Arithmetic Expressions
25 Citations1975David J. Kuck, Kiyoshi Maruyama
It is shown that if more information than the number of operations (or operands) is known, sharper bounds may be given in certain cases, and generalizations of polynomials and generalization of continued fractions are shown to have improved bounds.
Journal of the ACMA Combinatorial Problem Related to Interleaved Memory Systems
24 Citations1973G. J. Burnett, E. G. Coffman
The principal result of the paper is a recursive procedure for computing the expected number of states of a Markov chain of interleaved memory systems through which the system passes before returning to a state previously entered.
Mathematics of ComputationA Bell Telephone Laboratories’ computing machine. II
20 Citations1948Franz L. Alt
The largest and youngest member is a machine which has been built in the past two years in duplicate, one unit for the National Advisory Committee for Aeronautics and one for the Ordnance Department of the U. S. Army (Aberdeen Proving Ground, Md.).
IEEE Transactions on ComputersOn the Performance of Interleaved Memories with Multiple-Word Bandwidths
18 Citations1971E. G. Coffman, G. J. Burnett +1 more
Past studies of the performance of interleaved memory systems are extended in this note by adopting a more general model that assumes a system of N memory modules, each of which is made up of b submodules.
IEEE Transactions on ComputersImproved Time and Parallel Processor Bounds for Fortran-Like Loops
18 Citations1982Heuft, Little
Improved estimates of time and processor bounds are provided for two of the example programs presented in the above-mentioned paper.
Acta InformaticaBounds on the parallel evaluation of arithmetic expressions using associativity and commutativity
11 Citations1974David J. Kuck, Yoichi Muraoka
It is shown that any arithmetic expression with n operands and parentheses nested to depth d can be evaluated in at most 1+2d+ [log2n] steps, assuming that only associativity and commutativity are used to transform the expression.
IEEE Transactions on ComputersCombinational Circuit Synthesis with Time and Component Bounds
11 Citations1977Shyh-Ching Chen, Kuck
An algorithm for the synthesis of equivalent combinational logic using gates as well as IC's as components is discussed and the time and component bounds given compare favorably with traditional results.
ComputerUniform shift networks
8 Citations1974Robert L. Davis
This paper will discuss combinatorial uniform shift networks that can shift a binary word a variable number of bit positions.
Transactions of the American Institute of Electrical Engineers Part I Communication and ElectronicsDINA, a digital analyzer for Laplace, poisson, diffusion, and wave equations
6 Citations1952Cornelius T. Leondes, Morris Rubinoff
Communications of the ACMACM President's Letter
4 Citations1974Anthony Ralston
The reasons why the ACM Council's action to adopt the Code of Professional Conduct as an ACM bylaw is at best a quite modest triumph for professionalism are conveyed.