侯緒彬

(桂林電子科技大學(xué) 電子工程與自動(dòng)化學(xué)院，廣西 桂林541004)

隨著片上系統(tǒng)(System－on－Chip，SoC)集成度越來(lái)越高，如何保證IP核之間快速高效的通信已經(jīng)成為阻礙SoC發(fā)展的新瓶頸［1］。于是一種以通信為核心的復(fù)雜SoC的IP核的集成方法，即片上網(wǎng)絡(luò)(Networkon－Chip，NoC)被提出。NoC采用基于包交換的方法和分層傳輸方法來(lái)替代原先的傳統(tǒng)總線［2］，從體系結(jié)構(gòu)上有效解決了多核通信問(wèn)題。

在NoC測(cè)試過(guò)程中，往往用多條TAM(Test Access Mechanism，測(cè)試訪問(wèn)機(jī)制)進(jìn)行并行測(cè)試。但為了防止功耗過(guò)大損壞芯片，必須限制并行測(cè)試的TAM的條數(shù)，控制測(cè)試功耗［3］。如何在一定功耗限制下，將IP核合理地分配到各條TAM上，優(yōu)化測(cè)試時(shí)間，是NoC測(cè)試中的一個(gè)重要課題。

文中利用基于云模型的進(jìn)化算法對(duì)NoC調(diào)度規(guī)劃問(wèn)題進(jìn)行了研究，使得在功耗限制下優(yōu)化NoC的測(cè)試時(shí)間。

1 NoC測(cè)試調(diào)度問(wèn)題

1.1 基于NoC重用的測(cè)試訪問(wèn)機(jī)制

在SoC測(cè)試中，測(cè)試向量通過(guò)TAM進(jìn)行傳輸［4］。而在NoC系統(tǒng)中，重用NoC系統(tǒng)中的路由(Router)和通道(Channel)等資源作為TAM，不僅能夠避免增加額外的硬件開銷，還能有效提高測(cè)試效率［5］。

1.2 NoC并行測(cè)試

在文中，采用XY路由方式，在測(cè)試過(guò)程中采用非搶占式測(cè)試機(jī)制。具體的測(cè)試流程為［6］:外部測(cè)試設(shè)備ATE通過(guò)I/O端口連接到NoC，測(cè)試向量通過(guò)input端口輸入到網(wǎng)絡(luò)中，通過(guò)路由輸送到待測(cè)IP核中;測(cè)試響應(yīng)同樣通過(guò)路由輸送到output端口，被外部測(cè)試響應(yīng)分析機(jī)制接收:這樣就完成了一個(gè)IP核的測(cè)試。圖2給出了d695中對(duì)8號(hào)和6號(hào)IP核進(jìn)行并行測(cè)試時(shí)的測(cè)試路徑。

1.3 NOC測(cè)試規(guī)劃問(wèn)題描述

在NoC測(cè)試中，如何在眾多IP核的分配方案中尋找最優(yōu)方案，是NoC調(diào)度規(guī)劃的關(guān)鍵。如圖2所示，將10個(gè)待測(cè)IP核，按照A、B兩種規(guī)劃調(diào)度方式分別分配到3條TAM上進(jìn)行測(cè)試，B種調(diào)度方式的測(cè)試時(shí)間T2＜A種調(diào)度方式的測(cè)試時(shí)間T1。任務(wù)是在眾多調(diào)度方案中找到最優(yōu)方案，使測(cè)試時(shí)間最短。

圖1 d695上兩條TAM并行測(cè)試

圖2 NoC測(cè)試規(guī)劃

2 功耗約束下NoC測(cè)試規(guī)劃數(shù)學(xué)模型

假設(shè)在一個(gè)NoC中，有a條TAM，TAMj上有k個(gè)待測(cè)IP核，第i號(hào)待測(cè)IP核測(cè)試時(shí)間為Ti，則TAMj的測(cè)試時(shí)間為

則NoC總的測(cè)試時(shí)間為測(cè)試時(shí)間最長(zhǎng)的那條TAM的測(cè)試時(shí)間

NoC的測(cè)試功耗為當(dāng)前所有TAM上功耗的總和

3 基于云進(jìn)化算法的測(cè)試規(guī)劃

基于云模型的進(jìn)化算法利用云模型C(Ex，En，He)描述進(jìn)化過(guò)程［7－8］，其中Ex成為優(yōu)良種子個(gè)體;En成為進(jìn)化熵;He成為進(jìn)化超熵。Ex正態(tài)云發(fā)生器產(chǎn)生下一代云滴。

3.1 算法編碼

根據(jù)IP核在TAM上的分配編碼，如圖1(b)所示，可以得到此個(gè)體的編碼為010202101，表示編號(hào)為3、9、5、1的IP核在0號(hào)的TAM上;編號(hào)為2、7、8、10的IP核在1號(hào)TAM上;編號(hào)為6、4的IP核在2號(hào)的TAM上。

3.2 算法實(shí)現(xiàn)

算法包括以下步驟:初始化種群、適應(yīng)度值計(jì)算、個(gè)體更新和終止判斷。

(1)初始化種群。對(duì)于一個(gè)有N個(gè)待測(cè)IP核的NoC系統(tǒng)。隨機(jī)生成一個(gè)N位的整數(shù)代碼串，表示各待測(cè)IP核在TAM上的分配方式。

(2)適應(yīng)值計(jì)算。分析種群中每個(gè)個(gè)體的染色體信息，通過(guò)式(2)計(jì)算方案的測(cè)試時(shí)間作為此個(gè)體的適應(yīng)值。選取當(dāng)代個(gè)體中適應(yīng)度值最優(yōu)的n_s個(gè)個(gè)體作為種子，利用種子進(jìn)化生成新一代個(gè)體。

(3)個(gè)體更新。分為進(jìn)化和變異兩部分。

圖3 算法流程圖

種群進(jìn)化采用云進(jìn)化策略和自然進(jìn)化策略相結(jié)合的方法。

云進(jìn)化策略指利用n_s個(gè)種子，運(yùn)用一維正向云發(fā)生器產(chǎn)生新一代個(gè)體。將種子個(gè)體的代碼串如0102021021作為一個(gè)整數(shù)，此整數(shù)即為正態(tài)云期望Ex;Ex的取值范圍ε≥(a－1)×109(a為TAM個(gè)數(shù))，令En=ε/6;He=En/c2，c2一般取5～15之間的整數(shù)［9］，根據(jù)實(shí)驗(yàn)數(shù)據(jù)比較分析，取c2=10時(shí)算法具有較好的收斂性。

當(dāng)連續(xù)φ1代出現(xiàn)跨代精英時(shí)，算法可能找到了新的極值領(lǐng)域或更加逼近原有極值領(lǐng)域，這時(shí)令減小En和He的值降低算法搜索范圍，并提高搜索精度。輸入數(shù)字特征值Ex、En、He，產(chǎn)生nc個(gè)云滴。

自然進(jìn)化策略是指采用輪盤賭的方式，隨機(jī)選擇種子個(gè)體進(jìn)行交叉變異，生成新個(gè)體。

假設(shè)算法的連續(xù)平凡帶數(shù)為λ，閾值為λ1、λ2和λ3(λ1＜λ2＜λ3)。當(dāng)λ＜λ1時(shí)，只采用云進(jìn)化策略更新個(gè)體;當(dāng)λ＞λ1時(shí)，云進(jìn)化策略和自然進(jìn)化策略聯(lián)合更新個(gè)體，其中云進(jìn)化策略更新nc個(gè)新個(gè)體，自然進(jìn)化策略更新ne個(gè)新個(gè)體，k=ne/nc。當(dāng)λ＞λ2時(shí)，增大k以提高自然進(jìn)化算法生成新個(gè)體的數(shù)目;同時(shí)提高En、He，增大搜索范圍。當(dāng)λ＞λ3時(shí)，對(duì)部分種子個(gè)體進(jìn)行變異操作。若最大迭代次數(shù)為λmax，本文取λ1=λmax/10，λ2=2λ1，λ3=5λ1時(shí)，算法的效率較高。

變異操作針對(duì)種子個(gè)體進(jìn)行。針對(duì)適應(yīng)度值最好的前h個(gè)種子個(gè)體的編碼串，逐位求平均數(shù)然后4舍5入取整，作為新的種子。

(4)終止判斷。如果進(jìn)化代數(shù)達(dá)到最大的迭代次數(shù)，或達(dá)到進(jìn)化最大平凡代數(shù)，則終止迭代輸出結(jié)果;否則轉(zhuǎn)到步驟(2)。

4 結(jié)果及分析

文中采用ITC'02 SoC標(biāo)準(zhǔn)電路中的d695電路作為實(shí)驗(yàn)對(duì)象，其作為3×4網(wǎng)格結(jié)構(gòu)的NoC系統(tǒng)，有10個(gè)待測(cè)IP核。測(cè)試的基準(zhǔn)時(shí)鐘為fT=1 GHz，限制功耗設(shè)置為測(cè)試總功耗的50%。實(shí)驗(yàn)環(huán)境為:Intel(R)(CoreTM)－2410M i5 2.3 GHz CPU，4 GB內(nèi)存;程序源代碼通過(guò)C++語(yǔ)言編寫，并在VC 6.0上編譯運(yùn)行，其中正向云發(fā)生器用Matlab 7.0的MCC方式與VC混編實(shí)現(xiàn)，程序在Windows XP操作系統(tǒng)下運(yùn)行。

表1 d695單時(shí)鐘最佳測(cè)試規(guī)劃方案

實(shí)驗(yàn)分別對(duì)NoC系統(tǒng)上有2條、3條和4條TAM進(jìn)行測(cè)試，且有功耗限制和無(wú)功耗限制兩種情況。并將得到的測(cè)試數(shù)據(jù)和文獻(xiàn)［10］中基準(zhǔn)測(cè)試數(shù)據(jù)作比較。文獻(xiàn)［10］將待測(cè)IP核按照測(cè)試時(shí)間進(jìn)行排序后，根據(jù)資源空閑和功耗約束，將IP核依次分配到各TAM上，屬于傳統(tǒng)的測(cè)試規(guī)劃方案。二者對(duì)d695電路的測(cè)試數(shù)據(jù)比較如表1所示。

通過(guò)表中數(shù)據(jù)可以看出，當(dāng)TAM的數(shù)量增多時(shí)，由于并行測(cè)試IP核的數(shù)量增加，相應(yīng)的總測(cè)試時(shí)間是逐漸降低的;相比于無(wú)功耗限制和50%功耗限制兩種情況，無(wú)功耗限制時(shí)的測(cè)試時(shí)間更小。

對(duì)比本文中的測(cè)試方法和文獻(xiàn)［10］的基準(zhǔn)測(cè)試數(shù)據(jù)可以發(fā)現(xiàn)，應(yīng)用云進(jìn)化算法的應(yīng)用明顯提高了測(cè)試效率，其中最大的優(yōu)化幅度達(dá)到了28.8%。

由以上測(cè)試數(shù)據(jù)可得，由于云進(jìn)化算法擁有搜索范圍大且收斂快的特點(diǎn)，將其運(yùn)用到測(cè)試規(guī)劃中，相對(duì)比與傳統(tǒng)的測(cè)試規(guī)劃方案能夠有效地降低測(cè)試時(shí)間，提高了測(cè)試的效率。

5 結(jié)束語(yǔ)

文中在功耗限制下對(duì)NoC中待測(cè)IP核的測(cè)試進(jìn)行規(guī)劃。在2D網(wǎng)格結(jié)構(gòu)下，重用NoC的路由和通道作TAM進(jìn)行測(cè)試，并用XY路由方式選擇測(cè)試路徑，運(yùn)用云進(jìn)化算法對(duì)待測(cè)IP核在TAM上分配方式進(jìn)行尋優(yōu)。實(shí)驗(yàn)結(jié)果表明，通過(guò)本文設(shè)計(jì)的方法所得到的測(cè)試方案能有效降低測(cè)試時(shí)間，提高NoC系統(tǒng)待測(cè)IP核并行測(cè)試的效率。

［1］DALLY W，TOWLES B.Router packets，not wires:on－chip interconnection networks［C］.Las Vegas，NV:Proc.The Design Automation Conference，2001:684－689.

［2］ 譚耀東，劉有耀.NoC系統(tǒng)研究綜述［J］.西安郵電學(xué)院學(xué)報(bào)，2008，13(1):5－9.

［3］ 許川佩，姚芬，胡聰.基于云進(jìn)化算法的NoC資源節(jié)點(diǎn)優(yōu)化測(cè)試研究［J］.電子測(cè)量與儀器學(xué)報(bào)，2012，26(3):192－196.

［4］ 許川佩，胡紅波.基于量子粒子群算法的SoC測(cè)試調(diào)度研究［J］.儀器儀表學(xué)報(bào)，2011，32(1):113－119.

［5］LIU Chunsheng，LINK Z，PRADHAN D K.Reuse－based test access and integrated test scheduling for network－onchip［J］.Computer Science，2006(2):90－95.

［6］ 歐陽(yáng)一鳴，張嵐，梁華國(guó).一種時(shí)間優(yōu)化的NoC低功耗測(cè)試調(diào)度方法［J］.中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2010，40(5):540－545.

［7］ 葉瓊，李紹穩(wěn)，張友華，等.云模型及應(yīng)用綜述［J］.計(jì)算基礎(chǔ)工程與設(shè)計(jì)，2011，32(12):4198－4201.

［8］ 張光衛(wèi)，何銳，劉禹，等.基于云模型的進(jìn)化算法［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31(7):1082－1091.

［9］ 許川佩，覃上洲.基于云子粒子群算法的SoC測(cè)試規(guī)劃研究［J］.桂林電子科技大學(xué)學(xué)報(bào)，2010，30(5):463－468.

［10］COTA E，LIU CH SH.Constraint－driven test scheduling for noc－based systems［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，2006，25(11):2465－2478.