徐 輝， 李丹青， 應(yīng)健鋒， 李 揚(yáng)

(1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001;2.合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院，安徽 合肥 230009;3.江蘇商貿(mào)職業(yè)學(xué)院 信息系，江蘇 南通 226011)

計(jì)算與測(cè)試

基于關(guān)鍵路徑與改進(jìn)遺傳算法的最佳占空比求解*

徐 輝1， 李丹青1， 應(yīng)健鋒2， 李 揚(yáng)3

(1.安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽淮南232001;2.合肥工業(yè)大學(xué)電子科學(xué)與應(yīng)用物理學(xué)院，安徽合肥230009;3.江蘇商貿(mào)職業(yè)學(xué)院信息系，江蘇南通226011)

納米工藝下，負(fù)偏置溫度不穩(wěn)定性(NBTI)成為影響電路老化效應(yīng)的主導(dǎo)因素。多輸入向量控制(M-IVC)是緩解由于NBTI效應(yīng)引起電路老化的有效方法，而M-IVC的關(guān)鍵是最佳占空比的求解。在充分考慮時(shí)序余量的設(shè)計(jì)與電路實(shí)際操作情況下，對(duì)電路采用了靜態(tài)時(shí)序分析，精確定位電路中關(guān)鍵路徑。對(duì)關(guān)鍵路徑采用改進(jìn)的自適應(yīng)遺傳算法求解最佳占空比。實(shí)驗(yàn)結(jié)果表明：在時(shí)序余量為5 %時(shí)，電路的平均老化率相比現(xiàn)有方案降低了1.49 %，平均相對(duì)改善率為18.29 %。

集成電路； 老化效應(yīng)； 最佳占空比； 負(fù)偏置溫度不穩(wěn)定性； 多輸入向量控制； 遺傳算法

0 引 言

應(yīng)集成電路的發(fā)展需求，晶體管的特征尺寸不斷按比例縮放，使得負(fù)偏置溫度不穩(wěn)定性(negative bias temperature instability,NBTI)成為引起電路老化的主導(dǎo)因素[1]。NBTI效應(yīng)主要作用于PMOS晶體管。據(jù)研究表明，在32nm工藝尺寸下，10年內(nèi)最壞情況可導(dǎo)致晶體管閾值電壓增加20mV，電路時(shí)延增長20%[2],最終可能造成電路因時(shí)序違規(guī)而功能失效。如今，緩解NBTI引起的老化效應(yīng)的方法有多種[3～9]，本文主要研究通過控制電路的輸入引腳狀態(tài)來緩解電路老化的方法：輸入向量控制(input vector control,IVC)方法[9,10]、多輸入向量控制(multiple input vector control,M-IVC)方法[11～14]。后者對(duì)電路內(nèi)部節(jié)點(diǎn)的狀態(tài)控制力表現(xiàn)出顯著的優(yōu)勢(shì)，并一定程度上克服了其對(duì)大型電路的不適用性，且操作簡單，保留了電路的完整。但現(xiàn)有的M-IVC方法的最佳占空比的遺傳算法(genetic algorithm,GA)求解仍存在不足。文獻(xiàn)[12]采用對(duì)整個(gè)電路的輸入信號(hào)端實(shí)施經(jīng)典遺傳算法求解最佳占空比，耗時(shí)且精確度有待提高。

本文提出基于關(guān)鍵路徑的方法，通過考慮電路實(shí)際工作負(fù)載，預(yù)測(cè)整個(gè)電路最大老化率[15]，從而進(jìn)一步精簡了關(guān)鍵路徑集合，最終對(duì)找到的關(guān)鍵路徑采用改進(jìn)的自適應(yīng)的遺傳算法搜索最佳占空比組合，不僅提高了算法精確度，也降低了算法時(shí)間復(fù)雜度。

1 準(zhǔn)備工作

1.1 NBTI老化延時(shí)退化模型

當(dāng)對(duì)晶體管的柵氧層施加電場(chǎng)時(shí)，會(huì)在Si-SiO2層形成陷阱(懸空鍵)，閾值電壓變化模型與時(shí)間和占空比相關(guān)，文獻(xiàn)[16]給出了長期老化預(yù)測(cè)模型

(1)

式中Kv為與溫度和電源電壓相關(guān)的參數(shù)， K；α為負(fù)載周期,亦即PMOS輸入為低電平的概率；Tclk為時(shí)鐘周期；βt為與電路的溫度、Tclk、α、電路操作時(shí)間以及工藝參數(shù)綜合相關(guān)的參數(shù)；n為經(jīng)驗(yàn)常數(shù)，其取值范圍為0.25或0.16，當(dāng)晶體管為H2擴(kuò)散模型時(shí)，n取值0.16[17]。在給定的特定工藝參數(shù)下，ΔVth為閾值電壓增量，mV，可簡化為冪率關(guān)系[18]

ΔVth=A×αn×tn

(2)

式中A為工藝技術(shù)參數(shù)；t為電路操作時(shí)間，ps。門延時(shí)隨閾值電壓的增大而增大?；陂L期老化模型，在NBTI影響下，經(jīng)過t時(shí)間門的傳播延時(shí)增量ΔDt,ps，可以近似為[6]

ΔDt=B×αn×tn

(3)

式中B為由門的類型和制造工藝決定的常數(shù)，通過HSPICE仿真數(shù)據(jù)擬合得到。

1.2 基于NBTI的靜態(tài)時(shí)序分析

現(xiàn)有的快速篩選潛在關(guān)鍵路徑的方法為靜態(tài)時(shí)序分析法，如圖1。假設(shè)所有路徑均可能影響電路的時(shí)延，首先使用靜態(tài)時(shí)序分析得到每個(gè)路徑老化前的延時(shí)Dp(i)與最長路徑的時(shí)延Dmax，考慮設(shè)計(jì)預(yù)留的時(shí)序余量Tc和電路的老化率上限值Rmax，則滿足式(4)的路徑均被識(shí)別為潛在關(guān)鍵路徑

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

(4)

圖1 基于NBTI的靜態(tài)時(shí)序分析框架

表1 精簡關(guān)鍵路徑分析表

2 本文方法

2.1 最佳占空比問題模型

電路的最佳占空比指一組能使電路的時(shí)延達(dá)到最小的占空比向量。電路原始輸入端的占空比按照邏輯門的功能傳播[19]，傳播公式如表2。因此,根據(jù)電路的拓?fù)漤樞?，電路中每個(gè)門的占空比均可使用表2計(jì)算得到，則每個(gè)邏輯門的理論延時(shí)可通過式(1)計(jì)算得出。

表2 占空比傳播公式

2.2 優(yōu)化目標(biāo)函數(shù)建立

電路中的門Gi經(jīng)過t時(shí)間的老化之后，Gi的傳播延時(shí)(忽略連線上的傳播時(shí)延)

(5)

式中 Δdi基于式(3)采用靜態(tài)時(shí)序分析計(jì)算得到；d0(i)為邏輯門Gi的固有延時(shí)(老化前的門延時(shí))，利用HSPICE仿真得到。設(shè)電路原始端信號(hào)從時(shí)刻0開始傳播，該邏輯門Gi的扇入門有k個(gè)，老化前信號(hào)到達(dá)該門輸出節(jié)點(diǎn)的時(shí)間

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

(6)

老化后信號(hào)到達(dá)該門輸出節(jié)點(diǎn)的時(shí)間

(7)

設(shè)電路的第i條實(shí)際關(guān)鍵路徑輸出端邏輯門Output(i)有m個(gè)扇入門，老化前Output(i)的到達(dá)時(shí)間

(8)

老化后電路的輸出端Output(i)的到達(dá)時(shí)間

(9)

設(shè)電路有N條實(shí)際關(guān)鍵路徑，則電路老化前傳播時(shí)延

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

(10)

電路的老化前傳播時(shí)延

(11)

電路老化前、后的時(shí)延增量

ΔD=D′-D

(12)

電路老化率

(13)

2.3 改進(jìn)的自適應(yīng)遺傳算法搜索最佳占空比

設(shè)電路的每個(gè)原始輸入節(jié)點(diǎn)的信號(hào)占空比取值范圍為[0,1]，精度取0.01。對(duì)一個(gè)具有n個(gè)輸入端的電路來說，占空比向量的維度為n。不同的占空比向量對(duì)電路產(chǎn)生不同的負(fù)載，從而引起不同程度的老化，導(dǎo)致不同的延時(shí)增量。為了搜索到使電路延時(shí)最小的占空比向量，適合采用將每個(gè)占空比組合看做一個(gè)解決方案。本文提出的基于關(guān)鍵路徑與改進(jìn)的遺傳算法步驟：

輸入:基準(zhǔn)電路網(wǎng)表文件;

輸出:最優(yōu)輸入占空比αopt與電路老化率η。

1)讀入基準(zhǔn)電路網(wǎng)表文件。

2)隨機(jī)產(chǎn)生種群P中個(gè)體基因位，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};迭代次數(shù)i=0,迭代總次數(shù)M=1 000，αopt=αl。

3)計(jì)算每個(gè)個(gè)體適應(yīng)度η。

4)更新最佳個(gè)體：如果ηmin(α1,α2,…,αl)<ηopt(αopt),則ηopt(αopt)=ηmin(α1,α2,…,αl)。

5)將個(gè)體按照適應(yīng)度賦予選擇概率p_select，按照p_select自適應(yīng)的選擇參與交叉的父代。

6)父代個(gè)體兩兩交叉，將滿足交叉概率p_inters的基因位實(shí)施基因位交換，得到新的子代個(gè)體，并保存到子代種群中。

7)產(chǎn)生的子代種群中個(gè)體按適應(yīng)度排序，適應(yīng)度優(yōu)的進(jìn)行最佳變異，其余自帶個(gè)體進(jìn)行基因位隨機(jī)突變。

8)保留原始種群的10 %精英個(gè)體，剩下的個(gè)體與新的子代個(gè)體進(jìn)行比較和替換。

9)i=i+1,如果i

最后，算法進(jìn)行M次迭代后將適應(yīng)度最小的個(gè)體(最佳占空比)與其適應(yīng)度值(電路老化率)作為算法的輸出。

圖2 變異概率系數(shù)函數(shù)隨最優(yōu)值停留周期變化曲線

2.4 算法的時(shí)間復(fù)雜度分析

由于算法中電路的靜態(tài)時(shí)序分析最耗時(shí)，本文僅分析靜態(tài)時(shí)序分析的復(fù)雜度。假設(shè)實(shí)驗(yàn)電路含有n條路徑，其中關(guān)鍵路徑有r條，則靜態(tài)時(shí)序分析的時(shí)間復(fù)雜度為O(n+r)，改進(jìn)的自適應(yīng)遺傳算法共循環(huán)m次，種群大小為l，因此，算法整體復(fù)雜度為O(mlr)。文獻(xiàn)[12]的時(shí)間復(fù)雜度為O(mln)。由表1可知，r?n，因此，本文的時(shí)間復(fù)雜度O(mlr)小于文獻(xiàn)[12]的復(fù)雜度O(mln)。

3 實(shí)驗(yàn)設(shè)置與結(jié)果分析

實(shí)驗(yàn)基于32 nm工藝庫的ISCAS85與ISCAS89基準(zhǔn)電路，將電路中的門扁平化為僅含INV，NAND，NOR的電路網(wǎng)表格式；將時(shí)序電路轉(zhuǎn)換為組合電路，其中的觸發(fā)器的輸入端設(shè)為組合電路的原始輸出，輸出端設(shè)為組合電路的原始輸入。

首先由HSPICE仿真分別得到每個(gè)類型的邏輯門的固有延時(shí)用于靜態(tài)時(shí)序分析；再采用MOSRA方法得到老化后的邏輯門的延時(shí)；以10年為操作周期；最后利用Matlab對(duì)式(3)進(jìn)行擬合得到系數(shù)B。其中,電源電壓Vdd=0.8 V，溫度設(shè)置為378 K。靜態(tài)是時(shí)序分析實(shí)驗(yàn)采用VS2017實(shí)驗(yàn)平臺(tái)進(jìn)行C++編程，實(shí)現(xiàn)對(duì)電路網(wǎng)表的靜態(tài)時(shí)序分析，得到實(shí)際關(guān)鍵路徑，并得到優(yōu)化目標(biāo)，最后采用基于關(guān)鍵路徑與改進(jìn)的遺傳算法得到最優(yōu)占空比組合。

圖3所示為分別對(duì)ISCAS85與ISCAS89基準(zhǔn)電路中的C880A,C1908,S1196,S9234電路采用本文算法得到的最佳占空比組合所引起電路老化延時(shí)增長率優(yōu)化結(jié)果。算法相關(guān)參數(shù)設(shè)置為：迭代次數(shù)M=1 000，種群大小l=20。從圖中可以看出，電路老化率收斂速度很快，不斷跳出局部最優(yōu)值，最小達(dá)到4.7 %。不失一般性，其他電路與也表現(xiàn)出類似的結(jié)果，表明本文提出的算法在求解最佳占空比的明顯優(yōu)勢(shì)。

圖3 本文算法對(duì)ISCAS基準(zhǔn)電路老化率優(yōu)化結(jié)果

分別對(duì)ISCAS基準(zhǔn)電路中的組合電路與邏輯電路進(jìn)行了仿真與實(shí)驗(yàn)，結(jié)果如表3所示。

表3 本文方法的延時(shí)增加率與文獻(xiàn)[12]對(duì)比

表3中，第二列為電路老化前的固有延時(shí)；第3列為電路在本文方法所得到的最優(yōu)占空比組合作為輸入時(shí)電路的老化時(shí)延增量，第4列為延時(shí)的增加率，采用式(13)得到。為了表征本文對(duì)電路老化率的改善情況，定義以下符號(hào)

(14)

式中R為采用本文方法相對(duì)采用文獻(xiàn)[12]的方法的改善率；η0為采用本文方法得到的電路老化率；η1為采用文獻(xiàn)[12]的方法得到的電路老化率。相對(duì)文獻(xiàn)[12]，采用本方法得到的占空比組合可以達(dá)到更小的老化率，平均6.56 %，平均相對(duì)改善率為18.29 %。

4 結(jié) 論

M-IVC方法用于緩解待機(jī)狀態(tài)下電路的NBTI老化效應(yīng)，通過輸入以最佳占空比作為約束的向量組來緩解電路老化，其中最佳輸入占空比組合成為影響整體緩解效果的關(guān)鍵。本文提出了考慮關(guān)鍵路徑與改進(jìn)的遺傳算法，在獲得較低的時(shí)間復(fù)雜度的基礎(chǔ)上，提高了算法的精確度。實(shí)驗(yàn)表明：電路時(shí)序余量為5 %時(shí)，在經(jīng)歷10年的老化后，電路的平均老化率為6.56 %，相對(duì)經(jīng)典遺傳算法平均改善了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] 靳 松,韓銀和,李華偉,等.考慮工作負(fù)載影響的電路老化預(yù)測(cè)方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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

國家自然科學(xué)基金資助項(xiàng)目(61404001，61306046)；安徽省高校省級(jí)自然科學(xué)研究重大項(xiàng)目(KJ2014ZD12)；淮南市科技計(jì)劃資助項(xiàng)目(2013A4011)；國家自然科學(xué)基金面上資助項(xiàng)目(61371025)

TN 407

A

1000—9787(2017)10—0124—05

徐 輝(1979-)，男，副教授，研究方向?yàn)榍度胧较到y(tǒng)的綜合與測(cè)試、高可靠性集成電路設(shè)計(jì)。李丹青(1991-)，女，通訊作者，碩士，研究方向?yàn)榍度胧较到y(tǒng)的綜合與測(cè)試、高可靠性集成電路設(shè)計(jì)，E—mail:dancing0301@163.com。