Low Power State Assignment Algorithm for FSMs Considering Peak Current Optimization

Finite state machine (FSM) plays a vital role in the sequential logic design. In an FSM, the high peak current which is drawn by state transitions can result in large voltage drop and electromigration which significantly affect circuit reliability. Several published papers show that the peak current can be reduced by post-optimization schemes or Boolean satisfiability (SAT)-based formulations. However, those methods of reducing the peak current either increase the overall power dissipation or are not efficient. This paper has proposed a low power state assignment algorithm with upper bound peak current constraints. First the peak current constraints are weighted into the objective function by Lagrangian relaxation technique with Lagrangian multipliers to penalize the violation. Second, Lagrangian sub-problems are solved by a genetic algorithm with Lagrangian multipliers updated by the subgradient optimization method. Finally, a heuristic algorithm determines the upper bound of the peak current, and achieves optimization between peak current and switching power. Experimental results of International Workshop on Logic and Synthesis (IWLS) 1993 benchmark suites show that the proposed method can achieve up to 45.27% reduction of peak current, 6.31% reduction of switching power, and significant reduction of run time compared with previously published results.