Regular Partitioning for synthesizing fixed-size systolic arrays

Extending the projection method for the synthesis of systolic arrays, we present a procedure for the design of fixed-size systolic arrays using a technique called "locally sequential globally parallel" (LSGP) partitioning. Our main result, which gives a necessary and sufficient condition to characterize the boxes in which cells can be merged without conflict, is the key to the procedure presented here. 1 Introduction Recent work has shown that the usual synthesis method for systolic arrays based upon a projection vector and a scheduling vector can be extended to generate systolic implementations on a fixed number of processors. The main idea of all these extensions is to merge many cells into a single processor, so as to compress the array. This step is called partitioning and can take two different forms: the LPGS (locally parallel globally sequential) form and the LSGP (locally sequential globally parallel) form. The first approach, studied by Moldovan [MF86], is to partition the ar..