基于NSGA-II算法的IP核測(cè)試優(yōu)化研究

黃俊

（湖南鐵道職業(yè)技術(shù)學(xué)院 湖南 株洲 412001）

基于NSGA-II算法的IP核測(cè)試優(yōu)化研究

黃俊

（湖南鐵道職業(yè)技術(shù)學(xué)院 湖南 株洲 412001）

IP核集成化的SoC測(cè)試，測(cè)試時(shí)間與測(cè)試功耗是兩個(gè)相互影響的因素。多目標(biāo)進(jìn)化算法能夠處理相互制約的多目標(biāo)優(yōu)化問(wèn)題。在無(wú)約束條件下，對(duì)IP核的測(cè)試時(shí)間與測(cè)試功耗建立聯(lián)合優(yōu)化模型，并采用多目標(biāo)進(jìn)化算法中的改進(jìn)型非劣分類(lèi)遺傳算法（Non-dominated Sorting Genetic Algorithm II，NSGA-II）對(duì)模型進(jìn)行求解。通過(guò)應(yīng)用ITC'02標(biāo)準(zhǔn)電路中的h953做應(yīng)用驗(yàn)證，結(jié)果表明該方法能夠給出模型的均衡解，證明了模型的實(shí)用性和有效性。

NSGA-II算法；IP核；測(cè)試時(shí)間；測(cè)試功耗

當(dāng)今，復(fù)雜的SoC芯片由大量結(jié)構(gòu)功能復(fù)雜的IP核構(gòu)成，而且其設(shè)計(jì)采用了新的工藝技術(shù)。在整個(gè)芯片產(chǎn)品的開(kāi)發(fā)設(shè)計(jì)過(guò)程中，為了提高芯片系統(tǒng)的優(yōu)良率及可靠性，SoC的測(cè)試技術(shù)成為了必要的研究課題[1-3]。在基于IP核的SoC測(cè)試調(diào)度的研究中，為了整個(gè)芯片的安全性，功耗問(wèn)題必須要考慮。對(duì)于SoC測(cè)試時(shí)間與測(cè)試功耗的協(xié)同優(yōu)化研究，也是在將測(cè)試功耗作為約束條件下，考察測(cè)試時(shí)間的優(yōu)化問(wèn)題[4-7]。

文中在無(wú)測(cè)試時(shí)間及測(cè)試功耗的約束限制條件下，建立IP核測(cè)試時(shí)間與測(cè)試功耗的聯(lián)合優(yōu)化模型，研究NSGA-II算法實(shí)現(xiàn)過(guò)程，將NSGA-II算法應(yīng)用到SoC的測(cè)試優(yōu)化模型中，最后采用ITC’02 Benchmark中的h953電路來(lái)進(jìn)行算法驗(yàn)證，并給出優(yōu)化結(jié)果[8-13]。

1 IP核測(cè)試的多目標(biāo)優(yōu)化問(wèn)題的描述

對(duì)基于IP核的SoC總測(cè)試時(shí)間及總測(cè)試功耗的優(yōu)化問(wèn)題可以轉(zhuǎn)化為：對(duì)于給定的SoC，包含N個(gè)IP核，在SoC的測(cè)試過(guò)程中，每個(gè)IP核有測(cè)試和空閑兩個(gè)狀態(tài)，那么總共有2N個(gè)測(cè)試方案，這是典型的NP 問(wèn)題[14-15]。

1）最小化SoC的整體測(cè)試時(shí)間，其表達(dá)式為：

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

2）在IP核的并串測(cè)試方式內(nèi)，瞬時(shí)的SoC總測(cè)試功耗表示為：

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

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

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

2 基于NSGA-II算法的IP核的測(cè)試時(shí)間與測(cè)試功耗的優(yōu)化

文中綜合考慮測(cè)試時(shí)間和測(cè)試功耗，從中找到IP核測(cè)試的最優(yōu)解。NSGA-II算法是多目標(biāo)進(jìn)化算法的一種，多目標(biāo)進(jìn)化算法主要解決多目標(biāo)聯(lián)合優(yōu)化問(wèn)題，可以不受決策者的預(yù)先偏好信息的影響，對(duì)于建立的多目標(biāo)值數(shù)學(xué)模型，給出結(jié)果是一組均衡解，即Pareto最優(yōu)解。

2.1 算法主要流程

圖1所示內(nèi)容為非支配排序進(jìn)化算法 （NSGAII）的主要運(yùn)算流程。

圖1 NSGA-II算法的流程圖

2.2 IP核測(cè)試分配問(wèn)題的算法實(shí)現(xiàn)過(guò)程

通過(guò)MATLAB編程實(shí)現(xiàn)NSGA-II算法及求解本文建立的數(shù)學(xué)模型，程序?qū)崿F(xiàn)NSGA-II算法的代碼文件調(diào)用流程如圖2所示，包含以下10項(xiàng)：

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

主要對(duì)初始父代種群Po的個(gè)體隨機(jī)初始化。根據(jù)算法初始設(shè)置種群個(gè)體數(shù)N，隨機(jī)初始化每個(gè)個(gè)體。對(duì)于單個(gè)染色體的編碼初始化，設(shè)定染色體長(zhǎng)度L，限定染色體編碼值的范圍，并生成染色體的編碼值。

用MATLAB編程，隨機(jī)生成一個(gè)N×L階的矩陣P，其中，矩陣的每一行為一條染色體編碼。此外，本文建立的模型所要求解的目標(biāo)函數(shù)有2個(gè)，將矩陣P擴(kuò)展為N×（L+2）階的矩陣P'，后2列存儲(chǔ)各染色體對(duì)應(yīng)的2個(gè)目標(biāo)函數(shù)值。

2）確定目標(biāo)函數(shù)值：evaluate_objective.m

該文件根據(jù)建立的數(shù)學(xué)模型，確定目標(biāo)函數(shù)的個(gè)數(shù)及各目標(biāo)函數(shù)的具體表達(dá)式。對(duì)于給定的每條染色體，計(jì)算出其目標(biāo)函數(shù)值。應(yīng)用到本文模型求解中，就是計(jì)算出每條染色體的2個(gè)目標(biāo)函數(shù)值，存儲(chǔ)在矩陣P'的后兩列中。

圖2 NSGA-II算法的代碼文件調(diào)用流程圖

3）輸入初始數(shù)據(jù)：input_data.m

該文件代碼用于對(duì)優(yōu)化對(duì)象原始數(shù)據(jù)的輸入。包括IP核的個(gè)數(shù)，特定TAM總線寬度下各個(gè)IP核的測(cè)試時(shí)間數(shù)據(jù)矩陣，及測(cè)試功耗數(shù)據(jù)矩陣。

4）目標(biāo)函數(shù)值非支配排序：non_domination_sort_mod.m

非支配排序文件是NSGA-II算法的核心部分。其對(duì)當(dāng)前種群所有個(gè)體的目標(biāo)函數(shù)值進(jìn)行非支配排序，設(shè)定相應(yīng)個(gè)體非支配的等級(jí)。調(diào)整矩陣P'中每個(gè)個(gè)體的排列順序，將個(gè)體及其相應(yīng)的目標(biāo)函數(shù)值按等級(jí)從高到低進(jìn)行排序，同時(shí)將矩陣P'擴(kuò)展成P″，增加第L+3列存儲(chǔ)所有個(gè)體的非支配等級(jí)值。

5）目標(biāo)函數(shù)值擁擠度計(jì)算：crowding_distance.m

該文件完成對(duì)當(dāng)前種群的各排序前端的個(gè)體設(shè)定擁擠度值。并將矩陣P″擴(kuò)展，增加第L+4列存儲(chǔ)各個(gè)體的擁擠度值。擁擠度值為種群個(gè)體選擇做準(zhǔn)備。

6）錦標(biāo)賽選擇：tournament_selection.m

該文件用來(lái)完成對(duì)當(dāng)前種群個(gè)體的選擇，其中的競(jìng)賽規(guī)模設(shè)置為2，選擇操作進(jìn)行遵循錦標(biāo)賽選擇規(guī)則。

7）交叉操作：crossover_operator.m

對(duì)進(jìn)行選擇后的種群個(gè)體染色體交叉，并且設(shè)置交叉概率Pc的參數(shù)值。

8）變異操作：mutation_operator.m

對(duì)進(jìn)行選擇和交叉操作后的種群個(gè)體染色體變異，并且設(shè)置變異概率Pm的參數(shù)值。

9）種群更新：replace_chromosome.m

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

10）NSGA-II算法主函數(shù)：nsga2_main.m

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

3 IP核測(cè)試分配問(wèn)題的應(yīng)用實(shí)例及結(jié)果分析

文中采用的NSGA-II算法對(duì)IP核測(cè)試分配，以期獲得IP核測(cè)試時(shí)間與測(cè)試功耗的聯(lián)合優(yōu)化。為了對(duì)算法做出驗(yàn)證并且使算法具有普遍應(yīng)用性，采用國(guó)際標(biāo)準(zhǔn)SoC電路ITC’02 SoC Test Benchmark[4]來(lái)進(jìn)行分析，在ITC’02各個(gè)SoC中，h953具有測(cè)試功耗的信息，可以作為應(yīng)用實(shí)例來(lái)進(jìn)行研究。h953的相關(guān)信息如表1所示。

表1 h953的測(cè)試數(shù)據(jù)

表1中第一列是h953中各個(gè)IP模塊的名字。第二列是各模塊的原始輸入輸出端口總數(shù)，第三列是各個(gè)模塊的測(cè)試矢量數(shù)，第四列是各個(gè)模塊的內(nèi)部掃描鏈數(shù)量。其中，符號(hào)“-”表示沒(méi)有掃描鏈，即組合邏輯模塊。第五和第六列分別表示各模塊中最短和最長(zhǎng)掃描鏈長(zhǎng)度。第七列是各模塊在測(cè)試狀態(tài)下的功耗值。

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

表2 Pareto編碼集及目標(biāo)函數(shù)值

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

第2組：{Module2}；

第3組：{Module3}；

第4組：{Module7}；

此方案的測(cè)試時(shí)間與測(cè)試功耗分別為575 386 μs，126 788 mW。

編碼2表示分2組進(jìn)行測(cè)試：

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

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

此方案的測(cè)試時(shí)間與測(cè)試功耗分別為590 498 μs，124 150 mW。

編碼3表示分3組進(jìn)行測(cè)試：

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

第2組：{Module3}；

第3組：{Module7}；

此方案的測(cè)試時(shí)間與測(cè)試功耗分別為1140912μs，123 573 mW。

編碼4表示對(duì)于分4組進(jìn)行測(cè)試：

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

第2組：{Module2、Module4}；

第3組：{Module3}；

第4組：{Module7}；

此方案的測(cè)試時(shí)間與測(cè)試功耗分別為575 680 μs，125 503 mW。

表2中我們可以看到，經(jīng)過(guò)優(yōu)化后獲得的目標(biāo)函數(shù)值具有多樣性，而在實(shí)際測(cè)試應(yīng)用中，可以根據(jù)測(cè)試功耗或測(cè)試時(shí)間的限制來(lái)選擇不同測(cè)試方案。同樣的，根據(jù)表2所示數(shù)據(jù)，我們可以考慮在功耗約束下，測(cè)試時(shí)間的最優(yōu)解。將表2中F2作為約束條件，功耗約束強(qiáng)時(shí)，測(cè)試時(shí)間相應(yīng)長(zhǎng)，功耗約束弱時(shí)，測(cè)試時(shí)間相應(yīng)短，這驗(yàn)證了測(cè)試時(shí)間及測(cè)試功耗的相互制約性。

4 結(jié) 論

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

[1]汪瀅，許東寧.SoC測(cè)試時(shí)間與測(cè)試功耗協(xié)同優(yōu)化[J].微計(jì)算機(jī)信息，2009（32）:27-29.

[2]張建勝.變長(zhǎng)重復(fù)播種BIST和SoC測(cè)試[D].上海:復(fù)旦大學(xué)，2007:36-54.

[3]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社，2002.

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

[5]解光軍，肖晗.基于遺傳算法的運(yùn)算放大器建模與自動(dòng)設(shè)計(jì) [J].電子測(cè)量與儀器學(xué)報(bào)，2009，23（1）：91-95.

[6]林峰.SoC測(cè)試功耗優(yōu)化技術(shù)研究 [D].上海:上海大學(xué)，2009.

[7]孔民秀，陳琳，杜志江，等.基于NSGA_II算法的平面并聯(lián)機(jī)構(gòu)動(dòng)態(tài)性能多目標(biāo)優(yōu)化 [J].機(jī)器人，2010，32（2）:271-275.

[8]朱國(guó)俊.基于NSGA_II算法的軸流式葉片優(yōu)化設(shè)計(jì)[D].西安:西安理工大學(xué)，2009.

[9]冷冰，談恩民.基于IEEE1500標(biāo)準(zhǔn)的IP核內(nèi)建自測(cè)試設(shè)計(jì)[J].國(guó)外電子測(cè)量技術(shù)，2015，34（9）:75-79.

[10]賀顯龍，雷加．層次型IP核測(cè)試環(huán)單元的設(shè)計(jì)[J].國(guó)外電子測(cè)量技術(shù)，2010，29（5）:56-59.

[11]朱敏，楊春玲，孔德晶．模擬電路內(nèi)建自測(cè)試故障特征提取與優(yōu)化[J]．儀器儀表學(xué)報(bào)，2013，34（1）:200-207.

[12]趙麗麗，談恩民，王海超 ．優(yōu)化SOC測(cè)試時(shí)間的掃描鏈平衡 及NSGA-ll設(shè) 計(jì) [J].國(guó)外電子測(cè)量技術(shù)，2014，33（7）:32-35.

[13]喬立巖，向剛，俞洋，等．基于IEEE 1500標(biāo)準(zhǔn)的IP核測(cè)試殼設(shè)計(jì)[J]．電子測(cè)量技術(shù)，2010，33（7）:88-91.

[14]許川佩.帶分復(fù)用的三維片上網(wǎng)絡(luò)測(cè)試規(guī)劃研究[J]．儀器儀表學(xué)報(bào)，2015，36（9）:2120-2127.

[15]歐陽(yáng)一鳴，賀超，梁華國(guó)，等．NoC架構(gòu)下異構(gòu) IP核的并行測(cè)試方法 [J]．電子學(xué)報(bào)，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稿件編號(hào)：201607218

黃 ?。?969—），男，湖南株洲人，碩士，講師。研究方向：控制系統(tǒng)與控制理論、電氣工程。