An efficient graph algorithm for FSM scheduling

This paper presents a new algorithm for scheduling control-dominated designs during high-level synthesis. Our algorithm can schedule systems with arbitrary control flow, including conditional branches and multiple loops. It can handle both upper bound and lower bound timing constraints. The timing constraints can cross basic block boundaries, span different iterations of a loop, and form interlocking cycles in the control flow. A scheduling problem is described by the behavior finite-state machine model, an automaton model for the behavioral specification and synthesis of control-dominated systems. We optimize the performance of the produced digital circuit implementation by minimizing the execution time of each state transition in the state transition graph. The finite-state machines (FSM) scheduling algorithm is based on previous work on cylindrical layout compaction; we extend that work to handle upper bound constraints, allow multiple loops, and not require an initial feasible solution. Experimental results for examples derived from real designs and benchmark descriptions demonstrate that the algorithm can handle complex combinations of constraints very efficiently.