Constructing Time Optimal Schedules for p-dimensional Fixed-size Systolic Array
Hui Li, Muyi Chen, Peng Yi, Bingqiang Wang · 2006
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 ppn-1of Psi, the enumeration searching time for 2SCA is reduced to 1/Cpn-1for the DTSA. Moreover, the execution time corresponding to all the schedules in Omega have the same most significant coefficient item, thus enumeration of Omega for a time-optimal schedule is eliminated, which further reduces the complexity. Finally, by the regulations property of 2SCA, the schedules in Omega lead to simpler and more efficient hardware-description code and hardware interface implementation