HP Labs Technical Reports
Click here for full text:
A Constructive Solution to the Juggling Problem in Processor Array Synthesis
Schreiber, Robert; Rau, B. Ramakrishna; Darte, Alain; Vivien, Frederic
HPL-2000-30
Keyword(s): systolic array synthesis; affine scheduling
Abstract: 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.
7 Pages
Back to Index
| 
