An FSM Re-Engineering Approach to Sequential Circuit Synthesis by State Splitting
An FSM Re-Engineering Approach to Sequential Circuit Synthesis by State Splitting
Loading...
Files
Publication or External Link
Date
2008
Authors
Lin, Yuan
Qu, Gang
Villa, Tiziano
Sangiovanni-Vincentelli, Alberto
Advisor
Citation
DRUM DOI
Abstract
We propose Finite State Machine (FSM) re-engineering, a
performance enhancement framework for FSM synthesis and
optimization. It starts with the traditional FSM synthesis procedure,
then proceeds to re-construct a functionally equivalent
but topologically different FSM based on the optimization
objective, and concludes with another round of FSM synthesis
on the re-constructed FSM. This approach explores a larger
solution space that consists of a set of FSMs functionally
equivalent to the original one, making it possible to obtain
better solutions than in the original FSM. Guided by the result
from the rst round of synthesis, the solution space exploration
process can be rapid and cost-ef cient.
We apply this framework to FSM state encoding for power
minimization and area minimization. The FSM is rst minimized
and encoded using existing state encoding algorithms.
Then we develop both a heuristic algorithm and a genetic
algorithm to re-construct the FSM. Finally, the FSM is reencoded
by the same encoding algorithms. To demonstrate
the effectiveness of this framework, we conduct experiments
on MCNC91 sequential circuit benchmarks. The circuits are
read in and synthesized in SIS environment. After FSM
re-engineering are performed, we measure the power, area
and delay in the newly synthesized circuits. In the powerdriven
synthesis, we observe an average 5.5% of total power
reduction with 1.3% area increase and 1.3% delay increase.
This results are in general better than other low power state
encoding techniques on comparable cases. In the area-driven
synthesis, we observe an average 2.7% area reduction, 1.8%
delay reduction, and 0.4% power increase. Finally, we use
integer linear programming to obtain the optimal low power
state encoding for benchmarks of small size. We nd that the
optimal solutions in the re- engineered FSMs are 1% to 8%
better than the optimal solutions in the original FSMs in terms
of power minimization.