AN EFFICIENT GRAPH ALGORITHM FOR FSM SCHEDULING

This paper presents a new algorithm for scheduling control-dominated d esigns during high-level synthesis, Our algorithm can schedule systems with arbitrary control flow, including conditional branches and multi ple loops, It can handle both upper bound and lower bound timing const raints, The timing constraints can cross basic block boundaries, span different iterations of a loop, and form interlocking cycles in the co ntrol flow, A scheduling problem is described by the behavior finite-s tate machine model, an automaton model for the behavioral specificatio n and synthesis of control-dominated systems. We optimize the performa nce of the produced digital circuit implementation by minimizing the e xecution time of each state transition in the state transition graph, The finite-state machines (FSM) scheduling algorithm is based on previ ous work on cylindrical layout compaction; we extend that work to hand le upper bound constraints, allow multiple loops, and not require an i nitial feasible solution, Experimental results for examples derived fr om real designs and benchmark descriptions demonstrate that the algori thm can handle complex combinations of constraints very efficiently.