A family of VLSI circuits is presented to perform open convolution, i.e., polynomial multiplication. The circuits are all based on a recursive construction and are therefore particularly well adapted to automated design. All the circuits presented are optimal with respect to the area–time2 tradeoff, and, depending on the degree of paralleism or pipeline, they range from a compact but slow convolver to a large but very fast convolver.

An analysis of the alpha-beta pruning algorithm is presented which takes into account both shallow and deep cut-offs. A formula is first developed to measure the average number of terminal nodes examined by the algorithm in a uniform free of degree n and depth d when ties are allowed among the bottom positions: specifically, all bottom values are assumed to be independent identically distributed random variables drawn from a discrete probability distribution. A worst case analysis over all possible probability distributions is then presented by considering the limiting case when the discrete probability distribution tends to a continuous probability distribution. The branching factor of the alpha-beta pruning algorithm is shown to grow with n as Θ(n/In n), therefore confirming a claim by Knuth and Moore that deep cut-offs only have a second order effect on the behavior of the algorithm.

A class of asynchronous lterative methods is presented for solving a system of equations Exlstmg lteratwe methods are identified in terms of asynchronous iterations, and new schemes are introduced corresponding to a parallel implementation on a multiprocessor system with no synchronization between cooperating processes A suffloent condlnon is given to guarantee the convergence of any asynchronous iterations, and results are extended to include lteratlve methods with memory Asynchronous lteratlve methods are then evaluated from a computational point of view, and bounds are dertved for the efficiency The bounds are compared with actual measurements obtained by running various asynchronous iterations on a mulnprocessor, and the experimental results show clearly the advantage of purely, as~,nchronous lterattve methods KEY WORDS AND PHRASES asynchronous algorithms, asynchronous muhiprocessors, parallel algorithms, lteratwe methods, chaotic relaxation, analysis of algorithms CR CATE6ORIES 5 14, 5.15, 5 25 contracting operators (see, for example, [9, p. 433])In [2,6,8] the motivation of defining chaotic relaxation is to account for the parallel implementation of iterative methods on a multIprocessor system so as to reduce communication and synchronization between the cooperating processes.This reduction is obtained by not forcing the processes to follow a predetermined sequence of computations, but simply by allowing a process, when starting the evaluation of a new General permission to make fair use in teaching or research of all or part of this material is granted to lndwIdual readers and to nonprofit hbrarles acting for them provided that ACM's copyright notice is given and that reference Is made to the pubhcatlon, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does republication, or systematic or multiple reproduction

The problem of sorting a sequence of n elements on a parallel computer with k processors is considered. The algorithms we present can all be run on a single instruction stream multiple data stream computer. For large n, each achieves an asymptotic speed-up ratio of k with respect to the best sequential algorithm, which is optimal in the number of processors used.