FSM re-engineering and its application in low power state encoding

We propose finite state machine (FSM) re-engineering, a performance enhancement framework for FSM synthesis and optimization procedure. We start with any traditional FSM synthesis and optimization procedure; then reconstruct a functionally equivalent but topologically different FSM based on the optimization objective; and conclude with another round of FSM synthesis and optimization (can be the same procedure) on the newly constructed FSM. This allows us to explore a larger solution space that includes synthesis solutions to the functionally equivalent FSMs instead of only the original FSM, making it possible to obtain solutions better than the optimal ones for the original FSM. Guided by the result of the first round FSM synthesis, the solution space exploration process can be rapid and cost-efficient. To demonstrate this framework, we develop a genetic algorithm and a fast heuristic to reengineer a low power state encoding procedure POW3 (Benini and Micheli, 1995). On average, POW3 can reduce the switching activity by 12% over nonpower-driven state encoding schemes on the MCNC FSM benchmarks. We then reengineer these benchmarks by the proposed genetic algorithm and heuristic respectively. When we apply POW3 to the reengineered FSMs, we observe an additional 8.9% and 6.0% switching activity reduction. This translates to an average of 7.9% energy reduction with little area increase. Finally, we obtain the optimal low power coding for benchmarks of small size from an integer linear programming formulation. We find that the POW3-encoded original FSMs are 27.0% worse than the optimal, but this number drops to 6.7% when we apply POW3 to the reengineered FSMs.