An efficient graph algorithm for FSM scheduling

摘要

This paper presents a new algorithm for schedulingncontrol-dominated designs during high-level synthesis. Our algorithm cannschedule systems with arbitrary control flow, including conditionalnbranches and multiple loops. It can handle both upper bound and lowernbound timing constraints. The timing constraints can cross basic blocknboundaries, span different iterations of a loop, and form interlockingncycles in the control flow. A scheduling problem is described by thenbehavior finite-state machine model, an automaton model for thenbehavioral specification and synthesis of control-dominated systems. Wenoptimize the performance of the produced digital circuit implementationnby minimizing the execution time of each state transition in the statentransition graph. The finite-state machines (FSM) scheduling algorithmnis based on previous work on cylindrical layout compaction; we extendnthat work to handle upper bound constraints, allow multiple loops, andnnot require an initial feasible solution. Experimental results fornexamples derived from real designs and benchmark descriptionsndemonstrate that the algorithm can handle complex combinations ofnconstraints very efficiently