基于关键路径与改进遗传算法的最佳占空比求解*

徐 辉， 李丹青， 应健锋， 李 扬

(1.安徽理工大学 计算机科学与工程学院，安徽 淮南 232001;2.合肥工业大学 电子科学与应用物理学院，安徽 合肥 230009;3.江苏商贸职业学院 信息系，江苏 南通 226011)

计算与测试

基于关键路径与改进遗传算法的最佳占空比求解*

徐 辉1， 李丹青1， 应健锋2， 李 扬3

(1.安徽理工大学计算机科学与工程学院，安徽淮南232001;2.合肥工业大学电子科学与应用物理学院，安徽合肥230009;3.江苏商贸职业学院信息系，江苏南通226011)

纳米工艺下，负偏置温度不稳定性(NBTI)成为影响电路老化效应的主导因素。多输入向量控制(M-IVC)是缓解由于NBTI效应引起电路老化的有效方法，而M-IVC的关键是最佳占空比的求解。在充分考虑时序余量的设计与电路实际操作情况下，对电路采用了静态时序分析，精确定位电路中关键路径。对关键路径采用改进的自适应遗传算法求解最佳占空比。实验结果表明：在时序余量为5 %时，电路的平均老化率相比现有方案降低了1.49 %，平均相对改善率为18.29 %。

集成电路； 老化效应； 最佳占空比； 负偏置温度不稳定性； 多输入向量控制； 遗传算法

0 引 言

应集成电路的发展需求，晶体管的特征尺寸不断按比例缩放，使得负偏置温度不稳定性(negative bias temperature instability,NBTI)成为引起电路老化的主导因素[1]。NBTI效应主要作用于PMOS晶体管。据研究表明，在32nm工艺尺寸下，10年内最坏情况可导致晶体管阈值电压增加20mV，电路时延增长20%[2],最终可能造成电路因时序违规而功能失效。如今，缓解NBTI引起的老化效应的方法有多种[3～9]，本文主要研究通过控制电路的输入引脚状态来缓解电路老化的方法：输入向量控制(input vector control,IVC)方法[9,10]、多输入向量控制(multiple input vector control,M-IVC)方法[11～14]。后者对电路内部节点的状态控制力表现出显著的优势，并一定程度上克服了其对大型电路的不适用性，且操作简单，保留了电路的完整。但现有的M-IVC方法的最佳占空比的遗传算法(genetic algorithm,GA)求解仍存在不足。文献[12]采用对整个电路的输入信号端实施经典遗传算法求解最佳占空比，耗时且精确度有待提高。

本文提出基于关键路径的方法，通过考虑电路实际工作负载，预测整个电路最大老化率[15]，从而进一步精简了关键路径集合，最终对找到的关键路径采用改进的自适应的遗传算法搜索最佳占空比组合，不仅提高了算法精确度，也降低了算法时间复杂度。

1 准备工作

1.1 NBTI老化延时退化模型

当对晶体管的栅氧层施加电场时，会在Si-SiO2层形成陷阱(悬空键)，阈值电压变化模型与时间和占空比相关，文献[16]给出了长期老化预测模型

(1)

式中Kv为与温度和电源电压相关的参数， K；α为负载周期,亦即PMOS输入为低电平的概率；Tclk为时钟周期；βt为与电路的温度、Tclk、α、电路操作时间以及工艺参数综合相关的参数；n为经验常数，其取值范围为0.25或0.16，当晶体管为H2扩散模型时，n取值0.16[17]。在给定的特定工艺参数下，ΔVth为阈值电压增量，mV，可简化为幂率关系[18]

ΔVth=A×αn×tn

(2)

式中A为工艺技术参数；t为电路操作时间，ps。门延时随阈值电压的增大而增大。基于长期老化模型，在NBTI影响下，经过t时间门的传播延时增量ΔDt,ps，可以近似为[6]

ΔDt=B×αn×tn

(3)

式中B为由门的类型和制造工艺决定的常数，通过HSPICE仿真数据拟合得到。

1.2 基于NBTI的静态时序分析

现有的快速筛选潜在关键路径的方法为静态时序分析法，如图1。假设所有路径均可能影响电路的时延，首先使用静态时序分析得到每个路径老化前的延时Dp(i)与最长路径的时延Dmax，考虑设计预留的时序余量Tc和电路的老化率上限值Rmax，则满足式(4)的路径均被识别为潜在关键路径

Dp(i)×(1+Rmax)≥Dmax×(1+Tc)

(4)

图1 基于NBTI的静态时序分析框架

表1 精简关键路径分析表

2 本文方法

2.1 最佳占空比问题模型

电路的最佳占空比指一组能使电路的时延达到最小的占空比向量。电路原始输入端的占空比按照逻辑门的功能传播[19]，传播公式如表2。因此,根据电路的拓扑顺序，电路中每个门的占空比均可使用表2计算得到，则每个逻辑门的理论延时可通过式(1)计算得出。

表2 占空比传播公式

2.2 优化目标函数建立

电路中的门Gi经过t时间的老化之后，Gi的传播延时(忽略连线上的传播时延)

(5)

式中 Δdi基于式(3)采用静态时序分析计算得到；d0(i)为逻辑门Gi的固有延时(老化前的门延时)，利用HSPICE仿真得到。设电路原始端信号从时刻0开始传播，该逻辑门Gi的扇入门有k个，老化前信号到达该门输出节点的时间

T0(i)=max{T0(1),T0(2),…,T0(i)}+d0(i)

(6)

老化后信号到达该门输出节点的时间

(7)

设电路的第i条实际关键路径输出端逻辑门Output(i)有m个扇入门，老化前Output(i)的到达时间

(8)

老化后电路的输出端Output(i)的到达时间

(9)

设电路有N条实际关键路径，则电路老化前传播时延

D=max{TOutput(1),TOutput(2),…,TOutput(N)}

(10)

电路的老化前传播时延

(11)

电路老化前、后的时延增量

ΔD=D′-D

(12)

电路老化率

(13)

2.3 改进的自适应遗传算法搜索最佳占空比

设电路的每个原始输入节点的信号占空比取值范围为[0,1]，精度取0.01。对一个具有n个输入端的电路来说，占空比向量的维度为n。不同的占空比向量对电路产生不同的负载，从而引起不同程度的老化，导致不同的延时增量。为了搜索到使电路延时最小的占空比向量，适合采用将每个占空比组合看做一个解决方案。本文提出的基于关键路径与改进的遗传算法步骤：

输入:基准电路网表文件;

输出:最优输入占空比αopt与电路老化率η。

1)读入基准电路网表文件。

2)随机产生种群P中个体基因位，P={α1,α2,…,αl} 且α1={α1,1,α1,2,…,α1,k},α2={α2,1,α2,2,…,α2,k},αl={αl,1,αl,2,…,αl,k};迭代次数i=0,迭代总次数M=1 000，αopt=αl。

3)计算每个个体适应度η。

4)更新最佳个体：如果ηmin(α1,α2,…,αl)<ηopt(αopt),则ηopt(αopt)=ηmin(α1,α2,…,αl)。

5)将个体按照适应度赋予选择概率p_select，按照p_select自适应的选择参与交叉的父代。

6)父代个体两两交叉，将满足交叉概率p_inters的基因位实施基因位交换，得到新的子代个体，并保存到子代种群中。

7)产生的子代种群中个体按适应度排序，适应度优的进行最佳变异，其余自带个体进行基因位随机突变。

8)保留原始种群的10 %精英个体，剩下的个体与新的子代个体进行比较和替换。

9)i=i+1,如果i

最后，算法进行M次迭代后将适应度最小的个体(最佳占空比)与其适应度值(电路老化率)作为算法的输出。

图2 变异概率系数函数随最优值停留周期变化曲线

2.4 算法的时间复杂度分析

由于算法中电路的静态时序分析最耗时，本文仅分析静态时序分析的复杂度。假设实验电路含有n条路径，其中关键路径有r条，则静态时序分析的时间复杂度为O(n+r)，改进的自适应遗传算法共循环m次，种群大小为l，因此，算法整体复杂度为O(mlr)。文献[12]的时间复杂度为O(mln)。由表1可知，r≪n，因此，本文的时间复杂度O(mlr)小于文献[12]的复杂度O(mln)。

3 实验设置与结果分析

实验基于32 nm工艺库的ISCAS85与ISCAS89基准电路，将电路中的门扁平化为仅含INV，NAND，NOR的电路网表格式；将时序电路转换为组合电路，其中的触发器的输入端设为组合电路的原始输出，输出端设为组合电路的原始输入。

首先由HSPICE仿真分别得到每个类型的逻辑门的固有延时用于静态时序分析；再采用MOSRA方法得到老化后的逻辑门的延时；以10年为操作周期；最后利用Matlab对式(3)进行拟合得到系数B。其中,电源电压Vdd=0.8 V，温度设置为378 K。静态是时序分析实验采用VS2017实验平台进行C++编程，实现对电路网表的静态时序分析，得到实际关键路径，并得到优化目标，最后采用基于关键路径与改进的遗传算法得到最优占空比组合。

图3所示为分别对ISCAS85与ISCAS89基准电路中的C880A,C1908,S1196,S9234电路采用本文算法得到的最佳占空比组合所引起电路老化延时增长率优化结果。算法相关参数设置为：迭代次数M=1 000，种群大小l=20。从图中可以看出，电路老化率收敛速度很快，不断跳出局部最优值，最小达到4.7 %。不失一般性，其他电路与也表现出类似的结果，表明本文提出的算法在求解最佳占空比的明显优势。

图3 本文算法对ISCAS基准电路老化率优化结果

分别对ISCAS基准电路中的组合电路与逻辑电路进行了仿真与实验，结果如表3所示。

表3 本文方法的延时增加率与文献[12]对比

表3中，第二列为电路老化前的固有延时；第3列为电路在本文方法所得到的最优占空比组合作为输入时电路的老化时延增量，第4列为延时的增加率，采用式(13)得到。为了表征本文对电路老化率的改善情况，定义以下符号

(14)

式中R为采用本文方法相对采用文献[12]的方法的改善率；η0为采用本文方法得到的电路老化率；η1为采用文献[12]的方法得到的电路老化率。相对文献[12]，采用本方法得到的占空比组合可以达到更小的老化率，平均6.56 %，平均相对改善率为18.29 %。

4 结 论

M-IVC方法用于缓解待机状态下电路的NBTI老化效应，通过输入以最佳占空比作为约束的向量组来缓解电路老化，其中最佳输入占空比组合成为影响整体缓解效果的关键。本文提出了考虑关键路径与改进的遗传算法，在获得较低的时间复杂度的基础上，提高了算法的精确度。实验表明：电路时序余量为5 %时，在经历10年的老化后，电路的平均老化率为6.56 %，相对经典遗传算法平均改善了18.29 %。

[1] Chen X,Wang Y,Yang H,et al.Assessment of circuit optimization techniques under NBTI[J].IEEE Design & Test,2013,30(6):40-49.

[2] NBTI-aware bit line voltage control with boosted supply voltage for improvement of 6T SRAM cell read stability[C]∥Interna-tional Conference on Synthesis,Modeling,Analysis and Simulation Methods and Applications to Circuit Design (SMACD),Istanbul,2015:1-4.

[3] Paul B C,Kang K,Kufluoglu H,et al.Temporal performance degradation under NBTI:Estimation and design for improved relia-bility of nanoscale circuits[C]∥Proceedings of the Conference on Design,Automation and Test in Europe:Proceedings of European Design and Automation Association,2006:780-785.

[4] Kumar S V,Kim C H,Sapatnekar S S.Adaptive techniques for overcoming performance degradation due to aging in digital circuits[C]∥2009 Asia and South Pacific 2009 Design Automation Conference,ASP-DAC 2009,IEEE,2009:284-289.

[5] Kang K,Gangwal S,Park S P,et al.NBTI induced performance degradation in logic and memory circuits:How effectively can we approach a reliability solution[C]∥2008 Asia and South Pacific Design Automation Conference,ASPDAC 2008，IEEE,2008:726-731.

[6] Wang Y,Chen X,Wang W,et al.Leakage power and circuit aging cooptimization by gate replacement techniques[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2011,19(4):615-628.

[7] Lin I C,Lin C H,Li K H.Leakage and aging optimization using transmission gate-based technique[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2013,32(1):87-89.

[8] Wu K C,Marculescu D.Joint logic restructuring and pin reordering against NBTI-induced performance degradation[C]∥Proceedings of the Conference on Design,Automation and Test in Europe,European Design and Automation Association,2009:75-80.

[9] Ghane M,Zarandi H R.Gate merging:An NBTI mitigation method to eliminate critical internal nodes in digital circuits[C]∥Parallel,Distributed,and Network-Based Processing (PDP),IEEE,2016:786-791.

[10] Wang Y,Luo H,He K,et al.Temperature-aware NBTI modeling and the impact of input vector control on performance degrada-tion[C]∥Proceedings of the Conference on Design,Automation and Test in Europe,EDA Consortium,2007:546-551.

[11] Jin S,Han Y H,Zhang L,et al.M-IVC:Using multiple input vectors to minimize aging-induced delay [C]∥Proceedings of Asian Test Symposium,Washington D C:IEEE Computer Society,2009:437-442.

[12] Yi M,Liu X,Wu Q,et al.NBTI mitigation by M-IVC with input duty cycle and randomness constraints[C]∥2016 IEEE East-West Design & Test Symposium (EWDTS),IEEE,2016:1-5.

[13] Konoura H,Kameda T,Mitsuyama Y,et al.NBTI mitigation method by inputting random scan-in vectors in standby time[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,2014,97(7):1483-1491.

[14] Abdollahi A,Fallah F,Pedram M.Leakage current reduction in CMOS VLSI circuits by input vector control[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2004,12(2):140-154.

[15] 靳 松,韩银和,李华伟,等.考虑工作负载影响的电路老化预测方法[J].计算机辅助设计与图形学学报,2010,22(12):2242-2249.

[16] Wang W,Yang S,Bhardwaj S,et al.The impact of NBTI on the performance of combinational and sequential circuits[C]∥Proceedings of the 44th Annual Design Automation Conference，ACM,2007:364-369.

[17] Krishnan A,Chancellor C,Chakravarthi S,et al.Material depen-dence of hydrogen diffusion:Implications for nbti degradation[C]∥IEEE International Electron Devices Meeting,IEEE,2005:691-695.

[18] Wang W,Wei Z,Yang S,et al.An efficient method to identify critical gates under circuit aging[C]∥IEEE/ACM International Conference on Computer-Aided Design,2007:735-740.

[19] Hiroaki K,Toshihiro K.Stress probability computation for estimating NBTI-induced delay degradation [J].IEICE Transactions on Fundamentals,2011,E94-A(12):2545-2553.

Optimaldutycyclesolutionbasedoncriticalpathandimprovedgeneticalgorithm*

XU Hui1, LI Dan-qing1, YING Jian-feng2, LI Yang3

(1.SchoolofComputerScienceandEngineering,AnhuiUniversityofScienceandTechnology,Huainan232001,China;2.SchoolofElectronicScienceandAppliedPhysics,HefeiUniversityofTechnology,Hefei230009,China;3.DepartmentofInformation,JiangsuVocationalCollegeofBusiness,Nantong226011,China)

Under the nanometer process,the negative bias temperature instability (NBTI) is the dominant factor affecting the aging effect of the circuit.Multi input vector control (M-IVC) is an effective method to mitigate the NBTI effect,and the key to M-IVC is the solution of the optimal duty cycle.After fully considering the original design of the time margin and the actual operation of the circuit,the static timing analysis is used to accurately locate the critical path in the circuit.The improved adaptive genetic algorithm is used to solve the critical path for the best duty cycle.The experimental results show that when the time margin is5%,the average aging rate of the circuit is reduced by1.49% compared with the existing scheme,and the average relative improvement rate is18.29%.

integrated circuit; aging effect; optimum duty cycle; negative bias temperature instability(NBTI); multiple input vector control(M-IVC); genetic algorithm (GA)

10.13873/J.1000—9787(2017)10—0124—05

2017—08—01

国家自然科学基金资助项目(61404001，61306046)；安徽省高校省级自然科学研究重大项目(KJ2014ZD12)；淮南市科技计划资助项目(2013A4011)；国家自然科学基金面上资助项目(61371025)

TN 407

A

1000—9787(2017)10—0124—05

徐 辉(1979-)，男，副教授，研究方向为嵌入式系统的综合与测试、高可靠性集成电路设计。李丹青(1991-)，女，通讯作者，硕士，研究方向为嵌入式系统的综合与测试、高可靠性集成电路设计，E—mail:dancing0301@163.com。