Scheduling and binding algorithms for high-level synthesis

• Main Authors: Paulin, P. G., Knight, J. P.
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm design and analysis; Concurrent computing; Costs; Hardware; Hardware > Electronic design automation > High-level and register-transfer level synthesis; High level synthesis; Job shop scheduling; Mathematics of computing > Discrete mathematics > Graph theory; Partitioning algorithms; Permission; Scheduling algorithm; Theory of computation > Design and analysis of algorithms > Approximation algorithms analysis > Scheduling algorithms; Theory of computation > Design and analysis of algorithms > Online algorithms > Online learning algorithms > Scheduling algorithms; Theory of computation > Theory and algorithms for application domains > Machine learning theory > Reinforcement learning > Sequential decision making; Time factors
• ISSN: 0738-100X
• DOI: 10.1145/74382.74383

New algorithms for high-level synthesis are presented. The first performs scheduling under hardware resource constraints and improves on commonly used list scheduling techniques by making use of a global priority function. A new design-space exploration technique, which combines this algorithm with an existing one based on time constraints, is also presented. A second algorithm is used for register and bus allocation to satisfy two criteria: the minimization of interconnect costs as well as the final register (bus) cost. A clique partitioning approach is used where the clique graph is pruned using interconnect affinities between register (bus) pairs. Examples from current literature were chosen to illustrate the algorithms and to compare them with four existing systems.