Automatic design of systolic computing structures
Omar Wing, Chung Kon Ko · 1988
We investigate the feasibility of automatic design of systolic computing structures suitable for VLSI implementation to be used in a special-purpose computer to do computationally intensive tasks. We present a mapping strategy based on representing the algorithm and the implementation using differentials in an n-dimensional space of integers. Algorithms are specified in terms of data dependency and identity, and the implementations are specified in terms of data propagation and sequence. We show that the sequence behavior, essential to finding how to schedule the data, is the data identity transformed in the space and time domain observed in the frame of propagation. Our notation can represent a class of data bahaviors present in both systolic and non-systolic designs. The optimal design process consists of two steps: the first step of finding the linear transformation and the second step of fitting the design into the given area and time using space and time multiplexing. Based on the relation of data propagation and sequence, the problem of finding a linear transformation which maps a given algorithm to the implementation of desired data propagation and sequence is reduced to the problem of solving a set of linear equations so that the standard techniques in linear algebra such as least-square fit can be used. This approach provides a uniform framework to design a variety of VLSI computing structures including bit-serial architecture. Based on the mapping methodology, we have developed an automatic design system which takes as its input an algorithm specification in the problem space and produces as its output a layout of a VLSI chip in CMOS optimized with respect to area and time. Also presented are CAM systolic systems to do sparse matrix processing efficiently by incorporating Content Addressable Memory (CAM) with systolic processing. Particular implementations are shown to realize the direct method with numerical stability control and the Gauss-Seidel method to solve large sparse linear equations. The parallel speedup is shown to be achieved via two levels of parallelism: systolic processing among processing elements and parallel searching inside the CAM connected to each processing element.