SOME LINEAR-TIME ALGORITHMS FOR SYSTOLIC ARRAYS

R. P. BRENT, H. T. KUNG, AND F. T. LUK

Abstract

We survey some recent results on linear-time algorithms for systolic arrays. In particular, we show how the greatest common divisor (GCD) of two polynomials of degree n over a finite field can be computed in time O(n) on a linear systolic array of O(n) cells; similarly for the GCD of two n-bit binary numbers. We show how n by n Toeplitz systems of linear equations can be solved in time O(n) on a linear array of O(n) cells, each of which has constant memory size (independent of n). Finally, we outline how a two-dimensional square array of O(n) by O(n) cells can be used to solve (to working accuracy) the eigenvalue problem for a symmetric real n by n matrix in time O(nS(n)). Here S(n) is a slowly growing function of n; for practical purposes S(n) can be regarded as a constant. In addition to their theoretical interest, these results have potential applications in the areas of error-correcting codes, symbolic and algebraic computations, signal processing and image processing. For example, systolic GCD arrays for error correction have been implemented with the microprogrammable “PSC” chip.

Comments

Only the Abstract is given here. The full paper appeared as [4]. For related work, see [1, 2, 3, 5, 6, 7, 8, 9]. It is conjectured in [8] that S(n) = O(log n).

References

1. R. P. Brent and H. T. Kung, “Systolic VLSI arrays for polynomial GCD computation”, IEEE Transactions on Computers C-33 (1984), 731–736. rpb073.

2. R. P. Brent and H. T. Kung, “A systolic VLSI array for integer GCD computation”, in ARITH-7, Proceedings Seventh Symposium on Computer Arithmetic (edited by K. Hwang), IEEE/CS Press, 1985. rpb077.

3. R. P. Brent and F. T. Luk, “A systolic array for the linear-time solution of Toeplitz systems of equations”, J. of VLSI and Computer Systems 1 (1983), 1–23. CR 8405-0339. rpb078.

4. R. P. Brent, H. T. Kung and F. T. Luk, “Some linear-time algorithms for systolic arrays” (invited paper), in Information Processing 83 (edited by R. E. A. Mason), North-Holland, Amsterdam, 1983, 865–876. Preliminary version appeared as Report TR-CS-82-15, DCS, ANU, December 1982; TR 83-541, DCS, Cornell University; and Report CMA-R01-83, CMA, ANU, December 1982, 46 pp. rpb079.

5. R. P. Brent, F. T. Luk and C. F. Van Loan, “Computation of the singular value decomposition using mesh-connected processors”, J. of VLSI and Computer Systems 1, 3 (1983–1985), 242–270. MR 86m:65033. rpb080.

1991 Mathematics Subject Classification. Primary 65Y10; Secondary 15A18, 47B35, 65F15, 65H17, 65Y05, 68Q22, 68Q25, 68Q35, 94B99.

Key words and phrases. Systolic arrays, parallel computation, parallel algorithm, greatest common divisor, GCD, Toeplitz system, linear equations, symmetric eigenvalue problem, Hestenes method, Jacobi method, error correction.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1983, IFIP. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb079a typeset using AMS-L^{A}TEX 6. R. P. Brent and H. T. Kung, “Systolic VLSI arrays for linear-time GCD computation”, in VLSI 83

(edited by F. Anceau and E. J. Aas), North-Holland, Amsterdam, 1983, 145–154. rpb082.

7. R. P. Brent, F. T. Luk and C. F. Van Loan, “Computation of the generalized singular value decomposition using mesh-connected processors”, Proceedings SPIE, Volume 431, Real Time Signal Processing VI (edited by Keith Bromley), SPIE, Bellingham, Washington, 1983, 66–71. rpb083.

8. R. P. Brent and F. T. Luk, “The solution of singular-value and symmetric eigenvalue problems on multiprocessor arrays”, SIAM J. Scientific and Statistical Computing 6 (1985), 69–84. MR 86i:65089. rpb084.

9. A. W. Bojanczyk and R. P. Brent, “A systolic algorithm for extended GCD computation”, Comput. Math. Applic. 14 (1987), 233–238. MR 88m:11110. rpb096.

(Brent) Department of Computer Science and Centre for Mathematical Analysis, Australian National University, Canberra, ACT 2600, Australia

(Kung) Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213, USA

(Luk) Department of Computer Science, Cornell University, Ithaca, NY 14853, USA