Realization of Fixed-Size Algorithm-Specific Arrays

In this chapter, we have discussed the process of realizing the multi-mesh graph of an algorithm as an application-specific systolic-type array, for a problem of a given fixed size. We have presented a procedure for these purposes, which consists of grouping the nodes in the MMG by prisms, scheduling the nodes in each prism, and allocating each prism to one cell of an array. The proposed schedule of nodes consists of three nested loops, which takes advantage of the existence of transmitted data in a way that allows the efficient use of pipelined cells and of small fixed-size internal storage per cell. These aspects are directly related to the features of the pseudosystolic model of computation introduced in Chapter 2. Consequently, the multimesh graph makes it easy to obtain the characteristics of an implementation, including the array topology, the cell bandwidth, the internal storage and its organization. Moreover, the procedure allows the evaluation of performance and cost measures, as well as the evaluation of different tradeoffs that arise while deriving an implementation.