CANONIC AND GENERALIZED MAPPING FROM ALGORITHMS TO ARRAYS - A GRAPH BASED METHODOLOGY.

This paper develops a methodology of mapping regular computations onto special-purpose, algorithm-oriented processor arrays. A canonic mapping method, proposed in this paper, is shown to be suitable for shift invariant Dependence Graphs (DGs). This mapping method consists of three design stages, each utilizing an appropriate canonic form. For example, in order to represent the regularity inherent in algorithms, a Locally Recursive Algorithm (LRA) expression is developed to express the computation. Then a generalised mapping method, which is able to handle a broader class of algorithms, is developed. The design of a systolic architecture for Gauss-Jordan elimination is used to illustrate these techniques. Lastly, a multi-projection technique, which applies the mapping method multiple times, is developed to make the mapping methodology complete.