基于關鍵路徑與改進遺傳算法的最佳占空比求解*

徐 輝， 李丹青， 應健鋒， 李 揚

(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。