A Constructive Solution to the Juggling Problem in Systolic Array Synthesis
Alain Darte, Robert Schreiber, B. Ramakrishna Rau, Frédéric Vivien, 69 - Lyon (France). Lab. de l'Informatique du Parallelisme Centre National de la Recherche Scientifique (CNRS), 69 (France). Lab. de l'Informatique du Parallelisme Ecole Normale Superieure de Lyon, 69 (France). Lab. de l'Informatique du Parallelisme Lyon-1 Univ. · 1999
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. Previous solutions have an important practical disadvantage. Here we provide a closed form solution that enables the enumeration of all conflict-free schedules. The second part of the paper discusses reduction of the cost of hardware whose function is to control the flow of data, enable or disable functional units, and generate memory addresses. We present a new technique for controlling the complexity of these housekeeping functions in a systolic array.