College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
|Title: ||Some Linear-Time Algorithms for Systolic Arrays|
|Authors: ||Brent, Richard P.|
Kung, H. T.
Luk, Franklin T.
|Keywords: ||computer science|
|Issue Date: ||Jan-1983|
|Publisher: ||Cornell University|
|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.|
|Appears in Collections:||Computer Science Technical Reports|
Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.