An improved systematic method for constructing systolic arrays from algorithms

ABSTRACT

An improved systematic method is introduced which reduces the number of ad hoc steps and provides all possible systolic solutions for a given algorithm. Algorithms are modeled using index space (geometric) representations where the index transformation matrices are determined systematically. Systolic arrays are produced by geometric projections.

REFERENCES

• 1: H. T. Kung, "Why Systolic Architectures?," Computer Magazine Vol. 15, No. 2, 1982, pp 37-,46.
• 2: J.L. Bentley and H. T. Kung, "An Introduction to Systolic Algorithm and Architectures," IVav. Res. Rev. (USA), Vol. 35, No. 2, 1983, pp 3-16.
• 3: J. A. B. Fortes, K. S. Fu and B. W. Wah, "Systematic Approaches to the Design of AlgorithmicaHy Specified Systolic Arrays," 1985 lnt'l Conf. on Acoustics, Speech, and Signal processing, Tampa, Florida, Mar. 1985, pp 300-303.
• 4: J.A.B. Fortes and D. I. Moldovan, "Parallelism Detection and Transformation Techniques Useful for VLSI Algorithms," J. of Parallel and Distributed Confuting, 1985, pp 277-301.
• 5: Oscar H. Ibarra , Sam M. Kim , Michael A. Palis, Designing systolic algorithms using sequential machines, IEEE Transactions on Computers, v.35 n.6, p.531-542, June 1986 [doi>10.1109/TC.1986.5009430]
• 6: D.I. Moldovan, "On the Design of Algorithms for VLSI Systolic Arrays," Proceedings of the IEEE, Vol. 71, No. 1, Jan. 1983, pp 113-120.
• 7: D.D. Gajski and R. H. Kuhn, "Guest Editors' Introduction New VLSI Tools," IEEE Computer, No. 12, Dec. 1983, pp 11-14.
• 8: P. R. Cappello and K. Steiglitz, "Unifying VLSI Array Designs with Geometric Transformations," Conf. on Parallel Procesaing, 1983, pp 448-457.
• 9: R. H. Kuhn, "Transforming Algorithms for Single-Stage and VI_.SI Archi~s," Workshop on Iruerconnection Networks for Parallel and Distributed Processing, 1980, pp 11-19,
• 10: Nikrouz Faroughi, A new methodology for systematic construction of systolic arrays, 1987
• 11: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 12: Kai Hwang and Yen-Keng Cheng, "VLSI Computing Structures for Solving Large-Scale Linear System of Equations," Conf. on Parallel Processing, 1980, pp 217- 227.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Algorithms, Design