A scheduling and resource allocation algorithm for hierarchical signal flow graphs

Abstract

The paper describes a new algorithm for the scheduling and resource allocation problem in high-level synthesis. The algorithm can not only efficiently treat flattened signal flow graphs, but also handles graphs with embedded control constructs such as conditional branches and loops. Based on simple and clear, but powerful principles, the algorithm simultaneously minimizes the number of execution units, the number of registers and the amount of interconnections. The algorithm has been implemented and we present the first results, which are very promising.