›› 2013, Vol. 28 ›› Issue (6): 1054-1062.doi: 10.1007/s11390-013-1397-2

Special Issue: Computer Architecture and Systems

• Architecture and VLSI Design • Previous Articles     Next Articles

Low Power State Assignment Algorithm for FSMs Considering Peak Current Optimization

Lun-Yao Wang (王伦耀), Zhu-Fei Chu* (储著飞), Student Member, IEEE, and Yin-Shui Xia* (夏银水)   

  1. School of Information Science and Engineering, Ningbo University, Ningbo 315211, China
  • Received:2013-01-23 Revised:2013-06-19 Online:2013-11-05 Published:2013-11-05
  • About author:Lun-Yao Wang received the B.S. degree in physics education from Ningbo University, China, in 1995, and the M.S. and Ph.D. degrees, both in circuits and systems, from Zhejiang University, Hangzhou, in 2003 and 2012, respectively. He is currently an associate professor at the School of Information Science and Engineering at Ningbo University. His research interests include low-power digital circuits design, logic synthesis and optimization.
  • Supported by:

    This work is 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, and the K. C. Wong Magna Fund of Ningbo University of China.

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.

[1] Jeong K, Kahng A B, Park C H, Yao H. Dose map and placement co-optimization for improved timing yield and leakage power. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2010, 29(7): 1070-1082.

[2] Anderson J H, Najm F N. Active leakage power optimization for FPGAs. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2006, 25(3): 423-437.

[3] Tan S X D, Shi C J R, Lee J C. Reliability-constrained area optimization of VLSI power/ground networks via sequence of linear programmings. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2003, 22(12): 1678-1684.

[4] Kumar A, Anis M. IR-Drop management in FPGAs. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2010, 29(6): 988-993.

[5] Benini L, De Micheli G. State assignment for low power dissipation. IEEE J. Solid-State Circuit, 1995, 30(3): 258-268.

[6] Roy K, Prasad S C. Circuit activity based logic synthesis for low power reliable operations. IEEE Trans. Very Large Scale Integrat. Syst., 1993, 1(4): 503-513.

[7] Tsui C Y, Pedram M, Despain A M. Low-power state assignment targeting twoand multilevel logic implementations. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1998, 17(12): 1281-1291.

[8] Almaini A E A, Miller J F, Thomson P, Billina S. State assignment of finite state machines using a genetic algorithm. IEE P-Comput. Dig. T., 1995, 142(4): 279-286.

[9] Xia Y, Almaini A E A. Genetic algorithm based state assignment for power and area optimisation. IEE P-Comput. Dig. T., 2002, 149(4): 128-133.

[10] Huang S, Chang C, Nieh Y. State re-encoding for peak current minimization. In Proc. ICCAD, Nov. 2006, pp.33-38.

[11] Lee Y, Kim T. State encoding algorithm for peak current minimisation. IET Comput. Digit. Tec., 2011, 5(2): 113-122.

[12] Gu J, Qu G, Yuan L, Zhou Q. Peak current reduction by simultaneous state replication and re-encoding. In Proc. the ICCAD, Nov. 2010, pp.592-595.

[13] Yuan L, Qu G, Villa T, Sangiovanni-Vincentelli A. An FSM reengineering approach to sequential circuit synthesis by state splitting. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2008, 27(6): 1159-1164.

[14] Hung W N N, Gao C, Song X, Hammerstrom D. Defecttolerant CMOL cell assignment via satisfiability. IEEE Sensors Journal, 2008, 8(6): 823-830.

[15] Wang K H, Wang W S, Hwang T T, Wu A C H, Lin Y L. State assignment for power and area minimization. In Proc. the ICCD, Oct. 1994, pp.250-254.

[16] Huang S H, Chang C M, Nieh Y T. Opposite-phase register switching for peak current minimization. ACM Trans. Des. Autom. Electron. Syst., 2009, 14(1): Article No. 14.

[17] Chu Z F, Xia Y S, Wang L Y. Cell mapping for nanohybrid circuit architecture using genetic algorithm. Journal of Computer Scienece and Technology, 2012, 27(1): 113-120.

[18] Fisher M L. The Lagrangian relaxation method for solving integer programming problems. Manage. Sci., 1981, 27(1): 1-18.

[19] Chen C P, Chu C C N, Wong D F. Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1999, 18(7): 1014-1025.

[20] Wang J, Das D, Zhou H. Gate sizing by Lagrangian relaxation revisited. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2009, 28(7): 1071-1084.

[21] Xia Y, Chu Z, Hung W N N et al. An integrated optimization approach for nanohybrid circuit cell mapping. IEEE Trans. Nanotechnology, 2011, 10(6): 1275-1284.

[22] Ma Q, Young E. Multivoltage floorplan design. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2010, 29(4): 607617.
No related articles found!
Full text



[1] Feng Yulin;. Hierarchical Protocol Analysis by Temporal Logic[J]. , 1988, 3(1): 56 -69 .
[2] Cai Shijie; Zhang Fuyan;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[3] Fu Bin; Li Qiongzhang;. The Expressibility of First Order Dynamic Logic[J]. , 1992, 7(3): 268 -273 .
[4] Wu Xindong;. A Frame Based Architecture for Information Integration in CIMS[J]. , 1992, 7(4): 328 -332 .
[5] I.V.Vel bitsky; A.L.Kovalev; I.V.Kasatkina; Wang Lei;. R-Technology of Programming: Basic Notions and Implementation[J]. , 1992, 7(4): 345 -355 .
[6] Wang Hui; Liu Dayou; Wang Yafei;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[7] Ying Mingsheng;. Putting Consistent Theories Together in Institutions[J]. , 1995, 10(3): 260 -266 .
[8] Ying Mingsheng;. Institutions of Variable Truth Values:An Approach in the Ordered Style[J]. , 1995, 10(3): 267 -273 .
[9] Chen Bin; Hong Jiarong; Wang Yadong;. The Minimum Feature Subset Selection Problem[J]. , 1997, 12(2): 145 -153 .
[10] Zhang Yongyue; Peng Zhenyun; You Suya; Xu Guangyou;. A Multi-View Face Recognition System[J]. , 1997, 12(5): 400 -407 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved