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

所属专题： Computer Architecture and Systems

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

考虑峰值电流优化的低功耗有限状态机状态分配算法

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

  • 收稿日期:2013-01-23 修回日期:2013-06-19 出版日期:2013-11-05 发布日期:2013-11-05
  • 作者简介: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.

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.

PDF (PC)

1707

有限状态机在时序电路设计中起着至关重要的作用。在有限状态机中,由状态跳变引起的高峰值电流会导致较大的电压降以及电迁移问题,对电路的可靠性带来较大威胁。一些已发表的文章表明峰值电流可以通过后优化方式或者布尔可满足性(SAT)建模而有效降低。但它们在降低峰值电流的同时,有些增加了整体的功耗,而另外一些求解效率不高。本文提出了一种峰值电流上界约束下的低功耗状态分配算法。首先,通过拉格朗日松弛技术将峰值电流约束包含到目标函数中,并设定拉格朗日乘子惩罚不满足约束的解。然后,采用次梯度优化方法更新拉格朗日乘子,以此求解拉格朗日子问题。最后,采用启发式算法确定峰值电流的上界,使峰值电流和功耗得到优化。与之前发表的文章在IWLS'93基准测试电路的测试数据进行比较,提出的算法能平均降低峰值电流45.27%,降低功耗6.31%,并且求解时间有较大幅度改进。

Abstract: 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!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 冯玉琳;. Hierarchical Protocol Analysis by Temporal Logic[J]. , 1988, 3(1): 56 -69 .
[2] 蔡士杰; 张福炎;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[3] 付斌; 李琼章;. The Expressibility of First Order Dynamic Logic[J]. , 1992, 7(3): 268 -273 .
[4] 吴信东;. 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; 王镭;. R-Technology of Programming: Basic Notions and Implementation[J]. , 1992, 7(4): 345 -355 .
[6] 王晖; 刘大有; 王亚飞;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[7] 应明生;. Putting Consistent Theories Together in Institutions[J]. , 1995, 10(3): 260 -266 .
[8] 应明生;. Institutions of Variable Truth Values:An Approach in the Ordered Style[J]. , 1995, 10(3): 267 -273 .
[9] 陈彬; 洪家荣; 王亚东;. The Minimum Feature Subset Selection Problem[J]. , 1997, 12(2): 145 -153 .
[10] 张永越; 彭振云; 游素亚; 徐光佑;. A Multi-View Face Recognition System[J]. , 1997, 12(5): 400 -407 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：