An efficient ILP-based scheduling algorithm for control-dominated VHDL descriptions

To adopt behavioral synthesis techniques in existing design flows, the synthesis methodology must provide the designer with a mechanism to specify a component's interface timing. This will permit pre- and postsynthesis validation through cosimulation with other subsystems or even through formal verification. In control-flow dominated designs, additional timing constraints will result in a complex specification/constraint system for which the scheduling problem has been shown to be NP-complete. In this article, we present a mathematical framework for solving a special instance of the scheduling problem in control-flow dominated behavioral VHDL descriptions given that the timing of I/O signals has been completely or partially specified. It is based on a code-transformation approach that fully preserves the VHDL semantics. The scheduling problem is mapped onto an integer linear program (ILP) solvable in polynomial time assuming a restricted partial order on selected statements. It captures both control-flow and timing constraints in a single model and also exploits dataflow information to optimize the statement sequence across basic block boundaries.