Power/area/delay aware FSM synthesis and optimization

In this paper, we present novel state minimization and state assignment techniques to synthesize Finite State Machines (FSMs) including novel state minimization and state assignment to optimize power, area, and delay in designing sequential circuits for future low power system application such as cell phones, PDAs, etc. The goal is to reduce the number of gates and literals relevant to power and area, and furthermore to shorten the critical-path delay in FSM simultaneously. In the first step, we try to target the optimal solution for state minimization in efficiency by applying (i) the technique of binary-tree algorithm, heuristic algorithm (or ILP model) to determine the minimized groups covering all state variables where these groups are allocated at different Riversides (here, Shiue's River is introduced for readers to understand easily), (ii) the technique of edge-identification algorithm to determine the edges and impossible edges, which help targeting the solution at lower bound, (iii) Boolean Expression Effects due to alternative ways of minimized states, such that the required number of flip-flops is minimum for completely (or incompletely) specified state tables. Next, our novel state assignment techniques consisting of (i) edge-covering algorithm, (ii) block-reordering algorithm, (iii) cost calculation, (iv) ping-pong gray-codes assignment, and (iv) design space exploration, are developed to target the best state assignment. Espresso is then run to determine the Boolean expressions and choose the best state assignment with the minimal sum-of-product (SOP) terms and literals. Finally, the performance metrics in power, area, and delay are calculated based on the developed cell libraries for those optimal solutions having the same number of terms and literals. Our solutions provide engineers and designers to choose the best state assignment having less power, area, and delay to meet their system specification. Our experiments show that our approach results in quarter reduction (≈25%) in power, area, and delay, respectively, for FSM MCNC benchmarks.