Mapping algorithms to linear systolic arrays for wafer scale integration

A general methodology to map computations carried out on two-dimensional systolic arrays onto one-dimensional arrays is developed. The basic idea of the technique is to map computations of two-dimensional systolic arrays onto one-dimensional arrays in such a way that they satisfy the dependencies in the original problem. Using the technique, the two-dimensional arrays that have been developed for a large class of problems can be translated into one-dimensional arrays with the designs which can be implemented in wafer-scale integration (WSI). Compared to known designs in the literature, the methodology is an improvement in that it leads to modular systolic arrays with contrast hardware in each processing element, few control lines, lexicographic data input/output format, and improved delay time