A constructive solution to the juggling problem in systolic array synthesis

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.Nous présentons une méthode constructive permettant de résoudre le problème bien connu de l'ordonnancement sans conflits du partitionnement localement séquentiel, globalement séquentiel (LSGP) de la synthèse de réseaux systoliques. Les techniques proposées antérieurement conduisent à des solutions comportant quelques inconvénients pratiques majeurs que nous discutons. Ici, nous donnons une expression analytique des solutions qui nous permet d'énumérer tous les ordonnancements valides. La seconde partie du rapport discute d'un autre aspect pratique: comment réduire le coût du matériel dont le rôle est de contrôler le flot des données, d'activer ou de désactiver les unités fonctionnelles et de générer les adresses mémoire. Nous montrons comment maîtriser la complexité de ces calculs de maintenance du circuit. Ces deux techniques ont été intégrées dans un logiciel de synthèse automatique d'accélérateurs matériels, développé dans les laboratoires de Hewlett-Packard