How To Juggle
Rob Schreiber
HP Labs, Palo alto
We describe a new, practical, constructive method for solving the well-known
conflict-free scheduling problem for the locally sequential, globally parallel
(LSGP) case of systolic array synthesis. A loop nest and a linear mapping to
virtual processors is given, as is a 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 loop carried-dependences. The schedule
is conflict-free if no two iterations are scheduled simultaneously on the same
processor. It is tight if it juggles and, in the steady state, all processors
are busy every cycle.
Earlier attempts to solve this problem by Darte and Delosme provided a
solution with an important practical disadvantage, which we discuss below.
Megson and Chen later used Darte's analytic technique to provide a partial
solution to the problem. Here, we provide a closed form solution that enables
the enumeration of all tight schedules. The new method has been incorporated
into a software system for the automatic synthesis of hardware accelerators
developed by HP Labs.
Further info and related paper(s):