Constructing time optimal schedules for pdimensional fixed-size systolic array

An improved method for solving the well-known conflict-free scheduling problem for the locally sequential, globally parallel (LSGP) case of systolic array synthesis is proposed. A loop nest and a linear mapping to virtual processors is given, as is the clustering of rectangular arrangements of virtual processors into physical processors. A solution to the scheduling problem is a linear map of iteration indices to time that satisfies linear inequality constraints determined by data dependences. The schedule is conflict-free if no two iterations are scheduled simultaneously on the same processor. Say such a schedule juggles. It is tight if it juggles and, in the steady state, all processors are busy every cycle. Darte had provided a closed form solution that enables the enumeration of all tight schedules when the dimension of the array is (n-1). Based on the (n-1) dimensional tight scheduling algorithm (DTSA), this paper presents a 2-step construction algorithm (2SCA) for the scheduling of any p pn-1 of ??, the enumeration searching time for 2SCA is reduced to IICpn-1 for the DTSA. Moreover, the execution time corresponding to all the schedules in ?? have the same most significant coefficient item, thus enumeration of ?? for a time-optimal schedule is eliminated, which further reduces the complexity. Finally, by the regulations property of 2SCA, the schedules in ?? lead to simpler and more efficient hardwaredescription code and hardware interface implementation. ? 2006 IEEE.EI