基于NSGA-II算法的IP核測試優化研究

黃俊

（湖南鐵道職業技術學院 湖南 株洲 412001）

基于NSGA-II算法的IP核測試優化研究

黃俊

（湖南鐵道職業技術學院 湖南 株洲 412001）

IP核集成化的SoC測試，測試時間與測試功耗是兩個相互影響的因素。多目標進化算法能夠處理相互制約的多目標優化問題。在無約束條件下，對IP核的測試時間與測試功耗建立聯合優化模型，并采用多目標進化算法中的改進型非劣分類遺傳算法（Non-dominated Sorting Genetic Algorithm II，NSGA-II）對模型進行求解。通過應用ITC'02標準電路中的h953做應用驗證，結果表明該方法能夠給出模型的均衡解，證明了模型的實用性和有效性。

NSGA-II算法；IP核；測試時間；測試功耗

當今，復雜的SoC芯片由大量結構功能復雜的IP核構成，而且其設計采用了新的工藝技術。在整個芯片產品的開發設計過程中，為了提高芯片系統的優良率及可靠性，SoC的測試技術成為了必要的研究課題[1-3]。在基于IP核的SoC測試調度的研究中，為了整個芯片的安全性，功耗問題必須要考慮。對于SoC測試時間與測試功耗的協同優化研究，也是在將測試功耗作為約束條件下，考察測試時間的優化問題[4-7]。

文中在無測試時間及測試功耗的約束限制條件下，建立IP核測試時間與測試功耗的聯合優化模型，研究NSGA-II算法實現過程，將NSGA-II算法應用到SoC的測試優化模型中，最后采用ITC’02 Benchmark中的h953電路來進行算法驗證，并給出優化結果[8-13]。

1 IP核測試的多目標優化問題的描述

對基于IP核的SoC總測試時間及總測試功耗的優化問題可以轉化為：對于給定的SoC，包含N個IP核，在SoC的測試過程中，每個IP核有測試和空閑兩個狀態，那么總共有2N個測試方案，這是典型的NP 問題[14-15]。

1）最小化SoC的整體測試時間，其表達式為：

Tj（1≤j≤N）表示每個 IP 核的測試時間，xij（1≤j≤N）表示每個IP核的狀態，IP核j為測試狀態時，xij=1；或者IP核j為空閑狀態時，xij=0。在2N個測試方案中，至少存在一種方案使式（1）中的目標函數值F1取得最小值，即獲得SoC最短的測試時間。

2）在IP核的并串測試方式內，瞬時的SoC總測試功耗表示為：

其中Pj為測試IP核j所需功耗；xij同上。Pi為SoC測試時的總功耗。在2N個測試方案中，至少存在一種方案使式（2）中的F2取得最小值，即獲得SoC最小的測試功耗。

3）此外，還需要滿足以下約束條件：

即所有的IP核分k組測試完，并且各組之間測試的IP核不會重復測試。式中i、j、k和xij取值相同于式（1）。

2 基于NSGA-II算法的IP核的測試時間與測試功耗的優化

文中綜合考慮測試時間和測試功耗，從中找到IP核測試的最優解。NSGA-II算法是多目標進化算法的一種，多目標進化算法主要解決多目標聯合優化問題，可以不受決策者的預先偏好信息的影響，對于建立的多目標值數學模型，給出結果是一組均衡解，即Pareto最優解。

2.1 算法主要流程

圖1所示內容為非支配排序進化算法 （NSGAII）的主要運算流程。

圖1 NSGA-II算法的流程圖

2.2 IP核測試分配問題的算法實現過程

通過MATLAB編程實現NSGA-II算法及求解本文建立的數學模型，程序實現NSGA-II算法的代碼文件調用流程如圖2所示，包含以下10項：

1）父代種群初始化：initialize_variables.m

主要對初始父代種群Po的個體隨機初始化。根據算法初始設置種群個體數N，隨機初始化每個個體。對于單個染色體的編碼初始化，設定染色體長度L，限定染色體編碼值的范圍，并生成染色體的編碼值。

用MATLAB編程，隨機生成一個N×L階的矩陣P，其中，矩陣的每一行為一條染色體編碼。此外，本文建立的模型所要求解的目標函數有2個，將矩陣P擴展為N×（L+2）階的矩陣P'，后2列存儲各染色體對應的2個目標函數值。

2）確定目標函數值：evaluate_objective.m

該文件根據建立的數學模型，確定目標函數的個數及各目標函數的具體表達式。對于給定的每條染色體，計算出其目標函數值。應用到本文模型求解中，就是計算出每條染色體的2個目標函數值，存儲在矩陣P'的后兩列中。

圖2 NSGA-II算法的代碼文件調用流程圖

3）輸入初始數據：input_data.m

該文件代碼用于對優化對象原始數據的輸入。包括IP核的個數，特定TAM總線寬度下各個IP核的測試時間數據矩陣，及測試功耗數據矩陣。

4）目標函數值非支配排序：non_domination_sort_mod.m

非支配排序文件是NSGA-II算法的核心部分。其對當前種群所有個體的目標函數值進行非支配排序，設定相應個體非支配的等級。調整矩陣P'中每個個體的排列順序，將個體及其相應的目標函數值按等級從高到低進行排序，同時將矩陣P'擴展成P″，增加第L+3列存儲所有個體的非支配等級值。

5）目標函數值擁擠度計算：crowding_distance.m

該文件完成對當前種群的各排序前端的個體設定擁擠度值。并將矩陣P″擴展，增加第L+4列存儲各個體的擁擠度值。擁擠度值為種群個體選擇做準備。

6）錦標賽選擇：tournament_selection.m

該文件用來完成對當前種群個體的選擇，其中的競賽規模設置為2，選擇操作進行遵循錦標賽選擇規則。

7）交叉操作：crossover_operator.m

對進行選擇后的種群個體染色體交叉，并且設置交叉概率Pc的參數值。

8）變異操作：mutation_operator.m

對進行選擇和交叉操作后的種群個體染色體變異，并且設置變異概率Pm的參數值。

9）種群更新：replace_chromosome.m

種群更新的作用即為精英保留策略。對父代種群Pt和子代種群Qt合并后得新種群Rt，參照非支配排序等級及擁擠度值，選擇N個優良個體作為新種群。對于矩陣P″來說，種群更新參考其第L+3列非支配等級值和第L+4列擁擠度值。

10）NSGA-II算法主函數：nsga2_main.m

完成對其他子程序文件（1）-（9）的調用，設置種群個體數N和算法進化代數gen。此外，精英保留策略中的父代與子代種群合并的操作在主文件中完成。

3 IP核測試分配問題的應用實例及結果分析

文中采用的NSGA-II算法對IP核測試分配，以期獲得IP核測試時間與測試功耗的聯合優化。為了對算法做出驗證并且使算法具有普遍應用性，采用國際標準SoC電路ITC’02 SoC Test Benchmark[4]來進行分析，在ITC’02各個SoC中，h953具有測試功耗的信息，可以作為應用實例來進行研究。h953的相關信息如表1所示。

表1 h953的測試數據

表1中第一列是h953中各個IP模塊的名字。第二列是各模塊的原始輸入輸出端口總數，第三列是各個模塊的測試矢量數，第四列是各個模塊的內部掃描鏈數量。其中，符號“-”表示沒有掃描鏈，即組合邏輯模塊。第五和第六列分別表示各模塊中最短和最長掃描鏈長度。第七列是各模塊在測試狀態下的功耗值。

本文的驗證條件為，對于給定的測試電路h953有8個IP模塊，為了計算方便，將各個IP模塊的測試功耗值取整表示：h953_test_time=[119357，3279，1319，2194，14094，34585，1373，120869]；h953_test_power=[56586，575380，590，332，1788，204252，14208，302520]；設測試時間的單位為 μs，測試功耗的單位為mW。對于NSGA-II算法的參數，考慮h953基準電路中包含8個IP核，文章設定初始種群個體數為80；遺傳操作中的交叉概率Pc=0.9，變異概率Pm=0.1；錦標賽選擇規模參數設置為2；設算法運行代數為50代。經過運算后得到一組最佳測試方案解。Pareto最優解，F1和F2分別為h953測試方案優化后測試時間與測試功耗的目標函數值。對于h953內部所有IP模塊，編碼1表示分4組進行測試：

表2 Pareto編碼集及目標函數值

第1組：{Module1、Module4、Module5、Module6、Module8}；

第2組：{Module2}；

第3組：{Module3}；

第4組：{Module7}；

此方案的測試時間與測試功耗分別為575 386 μs，126 788 mW。

編碼2表示分2組進行測試：

第1組：{Module1、Module5、Module6、Module8}；

第2組：{Module2、Module3、Module4、Module7}；

此方案的測試時間與測試功耗分別為590 498 μs，124 150 mW。

編碼3表示分3組進行測試：

第1組：{Module1、Module2、Module4、Module5、Module6、Module8}；

第2組：{Module3}；

第3組：{Module7}；

此方案的測試時間與測試功耗分別為1140912μs，123 573 mW。

編碼4表示對于分4組進行測試：

第1組：{Module1、Module5、Module6、Module8}；

第2組：{Module2、Module4}；

第3組：{Module3}；

第4組：{Module7}；

此方案的測試時間與測試功耗分別為575 680 μs，125 503 mW。

表2中我們可以看到，經過優化后獲得的目標函數值具有多樣性，而在實際測試應用中，可以根據測試功耗或測試時間的限制來選擇不同測試方案。同樣的，根據表2所示數據，我們可以考慮在功耗約束下，測試時間的最優解。將表2中F2作為約束條件，功耗約束強時，測試時間相應長，功耗約束弱時，測試時間相應短，這驗證了測試時間及測試功耗的相互制約性。

4 結 論

文中介紹了一種基于NSGA-II算法的IP核測試優化方案，對于不同的功耗及時間要求，均可采用本文提出的方法獲得一組Pareto解集，根據實際需求選擇不同的解方案，驗證了此方案的實用性和可行性。

[1]汪瀅，許東寧.SoC測試時間與測試功耗協同優化[J].微計算機信息，2009（32）:27-29.

[2]張建勝.變長重復播種BIST和SoC測試[D].上海:復旦大學，2007:36-54.

[3]王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安:西安交通大學出版社，2002.

[4]E.J.Marinissen,V.Iyengar,K.Chakrabarty.ITC’02 SOC Test Benchmarks[EB/OL].http://itc02socbenchm.pratt.duke.edu/.2008.

[5]解光軍，肖晗.基于遺傳算法的運算放大器建模與自動設計 [J].電子測量與儀器學報，2009，23（1）：91-95.

[6]林峰.SoC測試功耗優化技術研究 [D].上海:上海大學，2009.

[7]孔民秀，陳琳，杜志江，等.基于NSGA_II算法的平面并聯機構動態性能多目標優化 [J].機器人，2010，32（2）:271-275.

[8]朱國俊.基于NSGA_II算法的軸流式葉片優化設計[D].西安:西安理工大學，2009.

[9]冷冰，談恩民.基于IEEE1500標準的IP核內建自測試設計[J].國外電子測量技術，2015，34（9）:75-79.

[10]賀顯龍，雷加．層次型IP核測試環單元的設計[J].國外電子測量技術，2010，29（5）:56-59.

[11]朱敏，楊春玲，孔德晶．模擬電路內建自測試故障特征提取與優化[J]．儀器儀表學報，2013，34（1）:200-207.

[12]趙麗麗，談恩民，王海超 ．優化SOC測試時間的掃描鏈平衡 及NSGA-ll設 計 [J].國外電子測量技術，2014，33（7）:32-35.

[13]喬立巖，向剛，俞洋，等．基于IEEE 1500標準的IP核測試殼設計[J]．電子測量技術，2010，33（7）:88-91.

[14]許川佩.帶分復用的三維片上網絡測試規劃研究[J]．儀器儀表學報，2015，36（9）:2120-2127.

[15]歐陽一鳴，賀超，梁華國，等．NoC架構下異構 IP核的并行測試方法 [J]．電子學報，2013，41（12）:2391-2396.

Optimization of IP cores test based on NSGA-II algorithm

HUANG Jun
（Hunan Railway Professional Technology College，Zhuzhou 412001，China）

In the test of SoC integrated IP cores，test time and test power were in the restrict condition to each other.The multi-objective evolutionary algorithm can achieve the simultaneous optimization.The paper constructed the combined optimization model for IP cores'test time and test power under no constraining，applied NSGA-II to deal with the combined optimization model，and adopted ITC'02 Benchmark circuit h953 to verify the algorithm.The results show that the NSGA-II algorithm can generate balance solutions，and the test model is practical and effective.

NSGA-II； IP cores； test time； test power

TN108

A

1674－6236（2017）17-0058-04

2016-07-30稿件編號：201607218

黃 俊（1969—），男，湖南株洲人，碩士，講師。研究方向：控制系統與控制理論、電氣工程。