Low Power State Assignment Algorithm for FSMs Considering Peak Current Optimization
-
摘要: 有限状态机在时序电路设计中起着至关重要的作用。在有限状态机中,由状态跳变引起的高峰值电流会导致较大的电压降以及电迁移问题,对电路的可靠性带来较大威胁。一些已发表的文章表明峰值电流可以通过后优化方式或者布尔可满足性(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.
-
Keywords:
- finite state machine /
- peak current /
- switching activity /
- Lagrangian relaxation
-
-
[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.
计量
- 文章访问数: 31
- HTML全文浏览量: 0
- PDF下载量: 1698
下载:
