Microprogramming instruction systolic arrays

ABSTRACT

The instruction systolic array (ISA) is a programmable parallel architecture suitable for VLSI implementation. This paper presents a generalization of the ISA, called the microprogrammed ISA, which uses simple microprogramming techniques. Microprogrammed ISAs use dynamic microcodes whose length and contents are tailor made to the current program to be executed, and this can be efficiently implemented in VLSI. Here, microprogramming has the novel advantage of extending the range of algorithms that can be implemented on a given ISA. In particular, microprogramming can extend an ISA's effective communication abilities. Also, the reduction of the program input bandwidth (and pinout) afforded by microprogramming is even more important on large-scale MIMD architectures, such as the ISA. This paper also presents a weakest precondition semantics for the (microprogrammed) ISA model, which provides a means for verifying microprogrammed ISA programs. The semantics is modeled at the micro level, and has potential in the optimization of the microcodes of ISA programs.

REFERENCES

• 1: ChenM.,YaoK., OnR ea azu 1. t ions of Least-Squares Estimation and Kdmun Filtering by Systolic Arrays, in: Moore W. (ed.), Systolic Arrays, Adam-Hildiger, 1987.
• 2: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 3: Dittrich A., S c h meek H., Givens Rotation on an Instruction Systolic Array, Inst fiir Informatik u. P.M., Universitat Kiel, West Germany. Technical Report nr. 8602, 1987.
• 4: W. Daniel Hillis, The connection machine, MIT Press, Cambridge, MA, 1986
• 5: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 6: Kunde M., Lang H.W., Schimmler M., Schmeck H., Schrijder H., The Instruction Systolic Array and its Relation to other Models of Parallel Computers, in: Feilmeier et al eds., Parallel Computing 85, North Holland, 1986.
• 7: Kung H.T., Why Systolic Architectures, Computer Magazine 15, pp 37-46, 1982.
• 8: S. Y. Kung, VLSI array processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 9: Lang H.W., The Instruction Systolic Array, a Parallel Architecture for VLSI, Bericht 8502, Institut fiir Informatik und Praktische Mathematik, Unversitat Kiel, 1985.
• 10: Lang H.W., ISA and SISA: Two Variants of a General Purpose Systolic Array Architecture, Proc. Second Int. Conf. on Supercomputing, Vol. I, 460-465 1987.
• 11: Leiserson C.E., Saxe J.B., Optimizing Synchronous Systems, Proc. Twenty-Second Annual IEEE Symposium on Foundations of Computer Science, pp.23-36, 1981.
• 12: Lenders P., Schriider H., A Semantics for Instruction Systolic Arrays, submitted to: Journal of Parallel and Distributed Computing, 1989.
• 13: Lyall A. et al., Implementation of Inexact String Matching on the ICL DAP, in: Feilmeier et al eds., Parallel Computing 85, North Holland, 1986.
• 14: Moore W., McCabe A., Urquhart R. (eds.) Proceedings, International Workshop on Systolic Arrays, Oxford, England, June 1986
• 15: Robert A. Mueller , Joseph Varghese, Retargetable microcode synthesis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.257-276, April 1987 [doi>10.1145/22719.23717]
• 16: Murthy V.K., Schroder H., Systolic Arrays for Parallel G-Inversion and Finding Petri Net Invariants, to appear in Parallel Computing, 1989.
• 17: Schimmler M., Schriider H.., A simple systolic method to find all bridges in undirected graphs, to appear in Parallel Computing, 1989.
• 18: H. Schmeck, A comparison-based instruction systolic array, Proceedings of the international workshop on Parallel algorithms & architectures, p.281-292, November 1986, Luminy, France
• 19: Heiko Schröder, Instruction systolic array—tradeoff between flexibility and speed, Computer Systems Science and Engineering, v.3 n.2, p.83-90, April, 1988
• 20: Schrijder H., K ris h namurthy E.V., Instruction Systolic Array Computation of the Characteristic} Polynomial of a Hessenberg Matrix, submitted to Integration: the VLSI journal, 1987.
• 21: SchrSder H., Strazdins P., Program Compression on the Instruction Systolic Array, Australian Computer Science Conferenece ACS-12, February 1989.
• 22: Schimmler M., (private communications), 1988.
• 23: Harold S. Stone, Introduction to Computer Architecture, Sra, 1980
• 24: Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.5 Microcode Applications
          Subjects: Firmware support of operating systems/instruction sets**

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.1 Control Design Styles
          Subjects: Microprogrammed logic arrays**
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

General Terms:
Algorithms, Design, Languages, Performance