Skip to Main content Skip to Navigation
New interface
Reports (Research report)

A constructive solution to the juggling problem in systolic array synthesis

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. Earlier attempts to solve this problem provided a solution with an important practical disadvantage, which we discuss. Here, we provide a closed form solution that enables the enumeration of all valid schedules. The second part of the paper discusses another practical issue: reducing 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. Both of these techniques have been incorporated into a software system for the automatic synthesis of hardware accelerators developed by HP Labs.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:29 AM
Last modification on : Wednesday, October 26, 2022 - 8:15:40 AM


Files produced by the author(s)


  • HAL Id : hal-02101947, version 1



Alain Darte, Robert Schreiber, B. Ramakrishna Rau, Frédéric Vivien. A constructive solution to the juggling problem in systolic array synthesis. [Research Report] LIP RR-1999-15, Laboratoire de l'informatique du parallélisme. 1999, 2+22p. ⟨hal-02101947⟩



Record views


Files downloads