Ensemble representation and techniques for exact control-dependent scheduling

Abstract

Describes a new exact formulation of control/data-flow scheduling. Unlike current techniques, a closed form solution set is generated in which all satisfying schedules for arbitrary forward branching control/data paths and resource constraints are encapsulated in a compressed ordered binary decision diagram (OBDD) based representation. A robust, iterative construction strategy is presented along with benchmark results. An advantage of this construction is that initial bounds for the number of clock cycles are no longer needed for exact formulations. This strategy also allows the simple formulation of several set-based heuristics as well as controlling the growth of the BDD representation. >