Low Power State Assignment Algorithm for FSMs Considering Peak Current Optimization  

作　　者：王伦耀 储著飞 夏银水 

机构地区：[1]School of Information Science and Engineering,Ningbo University [2]IEEE

出　　处：《Journal of Computer Science & Technology》2013年第6期1054-1062,共9页计算机科学技术学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant Nos.61131001,61228105;the Doctoral Fund of Ministry of Education of China under Grant No.20113305110001;the Natural Science Foundation of Zhejiang Province of China under Grant No.LY12F01014;the Outstanding(Postgraduate)Dissertation Growth Foundation of Ningbo University of China under Grant No.PY20110001;the National Students’Innovation and Entrepreneurship Training Program of China under Grant No.201211646017;the K.C.Wong Magna Fund of Ningbo University of China

摘　　要：Finite state machine （FSM） plays a vital current which is drawn by state transitions can result in role in the sequential logic design. In an FSM, the high peak 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.Finite state machine （FSM） plays a vital current which is drawn by state transitions can result in role in the sequential logic design. In an FSM, the high peak 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.

关 键 词：finite state machine peak current switching activity Lagrangian relaxation 

分 类 号：TM714.2[电气工程—电力系统及自动化]