Iterated interpolation using a systolic array

ABSTRACT

An implementation using systolic array logic of Aitken's method of iterated interpolation is described. The proposed design has a simple, linear topology, requires no clock, and makes only modest demands on the host computer. By overlapping the computation of successive function values, a processing element utilization of approximately 1/2 is achieved. The paper illustrates how “mathematical hardware” packages, as well as software library routines, may be part of the mathematical problem solver's tool kit in the future.

REFERENCES

• 1: ARNOLD, C. P., PARR, M. I., AND DEWE, M.B. An efficient parallel algorithm for the solution of large sparse linear matrix equations. IEEE Trans. Comput. C-26 (1983), 265-272.
• 2: BRENT, R. P., AND LUK, F.T. A systolic architecture for almost linear-time solution of the symmetric eigenvalue problem. Report TR-CS-82-10. Dept. of Comput. Sci., Australian National Univ., Canberra, Aug. 1982.
• 3: Richard P. Brent , H. T. Kung , Franklin T. Luk, Some Linear-Time Algorithms for Systolic Arrays, Cornell University, Ithaca, NY, 1983
• 4: Linda Kaufman, Banded Eigenvalue Solvers on Vector Machines, ACM Transactions on Mathematical Software (TOMS), v.10 n.1, p.73-85, March 1984 [doi>10.1145/356068.356074]
• 5: KUNG, H. T., AND LEISERSON, C. Algorithms for VLSI processor arrays. In Introduction to VLSI Systems, C. Mead and L. Conwa,, Eds. Addison-Wesley, Reading, Mass., 1980, pp. 271-292.
• 6: D H. Lawrie , A H. Sameh, The computation and communication complexity of a parallel banded system solver, ACM Transactions on Mathematical Software (TOMS), v.10 n.2, p.185-195, June 1984 [doi>10.1145/399.401]
• 7: LIDDELL, H. M. Numerical software for the ICL DAP. TR-2.15. DAP Support Unit, Queen Mary College, London, 1983.
• 8: R. E. Lord , J. S. Kowalik , S. P. Kumar, Solving Linear Algebraic Equations on an MIMD Computer, Journal of the ACM (JACM), v.30 n.1, p.103-117, Jan. 1983 [doi>10.1145/322358.322366]
• 9: G. P. McKeown, A special purpose MIMD parallel processor, Information Processing Letters, v.20 n.1, p.23-27, Jan. 1985 [doi>10.1016/0020-0190(85)90125-5]
• 10: MISSIRLlS, N. M. Convergence of a parallel Jacobi-type method. Int. d. Comput. Math. 14 (1983), 371-384.
• 11: W L. Miranker , A Winkler, Spacetime representations of computational structures, Computing, v.32 n.2, p.93-114, 1984 [doi>10.1007/BF02253685]
• 12: Robert Schreiber, Computing generalized inverses and eigenvalues of symmetric matrices using sytolic arrays, Proc. of the sixth int'l. symposium on Computing methods in applied sciences and engineering, VI, p.285-295, June 1985, Versailles, France
• 13: SCHREIBER, R. Systolic arrays: High performance parallel machines for matrix computation. In Elliptic Problem Solvers, G. Birkhoff and A. ~;choenstadt, Eds. Academic Press, Orlando, Fla., 1984.

INDEX TERMS

Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Cellular arrays and automata

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design