SASCOM, an automated CAD tool for the design of systolic architecture is presented. It is built to automate the process of designing systolic architectures. Starting from a problem specified as systems of Affine Recurrence Equations (ARE), SASCOM can automatically gener­ate all systolic implementations for the problem. The mechanics behind its ability to generate systolic architectures include (1) data. pipelining of non-uniform dependencies, (2) generation of all valid and distinct space­time transformation functions, and (3) derivation of the final architecture specifications from the transformation functions. The fundamental the­ory and algorithms to perform each of these tasks are described in detail. The system currently runs on the Macintosh-II under the Ma.cScheme pro­ gramming environment. It has a front end editor and a back end graphical simulator. Tlte interface to these two parts will be briefly described.

Also included in the thesis is a new theory on the number of systolic architectures derivable for a problem specification. By analyzing a few constraints which characterize systolic arrays, an upper bound on the number of distinct systolic architectures is derived. This upper bound is found to be depended only on the dimension of the input recurrence. The result of tl1is theory is incorporated into SASCOM to make it a more complete automatic CAD tool as compared to other existing systems.