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
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101947
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:29 AM
Last modification on : Friday, May 17, 2019 - 1:39:21 AM

File

RR1999-15.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101947, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

2

Files downloads

7