Some Linear-Time Algorithms for Systolic Arrays

Abstract

We survey some recent results on linear-time and almost linear-time algorithms for one and two-dimensional 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. Assuming that the systolic cells can perform floating-point arithmetic, 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 array of $O(n)$ by $O(n)$ cells with nearest-neighbor interconnections 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 can be implemented relatively easily and have potential applications in the areas of error-correcting codes, symbolic and algebraic computation, signal processing and image processing. For example, systolic GCD arrays for error correction have been implemented with the microprogrammable "PSC" chip.