基于網(wǎng)絡(luò)芯片功能驗(yàn)證效率的探析*

楊 飛，蔣 林

(西安郵電學(xué)院 電子工程學(xué)院，陜西 西安710061)

包交換又稱分組交換，是一種傳送數(shù)據(jù)的方法，將用戶傳送的數(shù)據(jù)包劃分成一定長度的單元，每個單元稱為一個分組。在每個分組的前面加上一個分組頭，用以指明該分組發(fā)往何地址，然后由交換機(jī)根據(jù)每個分組的地址標(biāo)志，將他們轉(zhuǎn)發(fā)至目的地，這一過程稱為分組交換。包交換處理分組的一般過程是：將收到的數(shù)據(jù)包先放入緩存，再查找轉(zhuǎn)發(fā)表，找出到某個目的地址應(yīng)從哪個端口轉(zhuǎn)發(fā)，然后由交換機(jī)構(gòu)將該數(shù)據(jù)包傳遞給適當(dāng)?shù)亩丝谵D(zhuǎn)發(fā)出去[1]。由于包交換功能復(fù)雜，其硬件設(shè)計(jì)達(dá)到百萬門級，而驗(yàn)證百萬門的設(shè)計(jì)是一件非常難的事情。目前進(jìn)行功能驗(yàn)證有效的策略主要有兩種[2]：一種是傳統(tǒng)的功能驗(yàn)證方法，包括模擬驗(yàn)證、形式驗(yàn)證、基于斷言的驗(yàn)證三種方法，其特點(diǎn)是基于特定測試向量的針對特定功能的定向功能驗(yàn)證；另一種是基于偽隨機(jī)向量的針對覆蓋率的隨機(jī)功能驗(yàn)證。當(dāng)然兩種驗(yàn)證方法又有交叉。但針對一般的設(shè)計(jì)，其驗(yàn)證策略通常先進(jìn)行定向功能驗(yàn)證，保證設(shè)計(jì)滿足設(shè)計(jì)規(guī)范的功能要求，但其很難避免設(shè)計(jì)之外的缺陷及錯誤，也很難滿足代碼覆蓋率的要求，所以需要進(jìn)一步用隨機(jī)測試向量進(jìn)行隨機(jī)驗(yàn)證[3]。但無論哪種策略在進(jìn)行驗(yàn)證時，在頂層testbench加載激勵時，不同的數(shù)據(jù)必然有自己特定的數(shù)據(jù)通道，但不同的數(shù)據(jù)通道在進(jìn)行功能驗(yàn)證時，其效率是不同的，因而有必要從數(shù)據(jù)通道方面針對驗(yàn)證進(jìn)行研究，以提高功能驗(yàn)證效率。

本文首先根據(jù)以上包交換工作過程構(gòu)造定向功能驗(yàn)證模型，根據(jù)驗(yàn)證需求提出如何在滿足需求的基礎(chǔ)上高效地進(jìn)行定向功能驗(yàn)證，并對結(jié)果進(jìn)行分析。

1 模型概述

本文將整個包交換系統(tǒng)劃分成三個部分，分別是輸入緩存管理、查找管理和輸出管理。模塊之間數(shù)據(jù)通道采用分級流水管理的方式，假定輸入緩存管理模塊分為兩個獨(dú)立的功能模塊，以分別處理不同類型的輸入數(shù)據(jù)。數(shù)據(jù)處理完成后存入緩存，查找管理模塊從緩存中讀出數(shù)據(jù)包頭信息進(jìn)行分類管理，假定其同樣有兩個獨(dú)立的功能模塊。輸出管理模塊從查找模塊讀出包頭信息，再從緩存模塊讀出輸出的數(shù)據(jù)包信息，并將此數(shù)據(jù)包信息轉(zhuǎn)發(fā)出去，在此假定模塊也有兩個獨(dú)立的功能模塊，此時建立系統(tǒng)模型輸出管理如圖1所示。

圖1 包交換系統(tǒng)結(jié)構(gòu)圖

2 驗(yàn)證需求

針對系統(tǒng)技術(shù)規(guī)范要求，在系統(tǒng)頂層需要定向測試6個模塊的功能，這樣在頂層從數(shù)據(jù)包進(jìn)入系統(tǒng)到數(shù)據(jù)包輸出系統(tǒng)，根據(jù)遺傳學(xué)數(shù)據(jù)從輸入到輸出共有8條通路，每條通路均可進(jìn)行3個模塊的功能測試。根據(jù)實(shí)際測試來看，要想完全測試一個模塊的功能，必然很難保證其余模塊測試功能的完整性，由于每條驗(yàn)證通路針對某一模塊的測試效率是不同的，這樣有必要針對某一模塊的功能選擇一條最高效的驗(yàn)證通路來測試此模塊的功能，此條通路主要保證測試模塊功能的完整性，可以輔助測試其他兩個模塊的部分功能。以下將介紹如何來選取最為高效的驗(yàn)證通路的方法。

3 驗(yàn)證策略

表1 系統(tǒng)驗(yàn)證通道

以上討論了模型的建立以及驗(yàn)證需求，下面將建立驗(yàn)證問題的數(shù)學(xué)模型并計(jì)算出最優(yōu)策略。

3.1 構(gòu)造模型

首先根據(jù)系統(tǒng)結(jié)構(gòu)圖，得出系統(tǒng)的驗(yàn)證通路共有8條，如表1所示。

假定針對某一模塊每條通路的測試效率系數(shù)，即每條測試通道完成某一模塊功能測試所需的時間（h），由于一條通道并不能覆蓋所有模塊，所以對于不能測試的模塊認(rèn)為其效率系數(shù)無限大，用字母a表示。其效率系數(shù)分布如表2所示。

設(shè)Cij為第i條通道測試第j個模塊的效率：

則完成6個模塊的測試最優(yōu)效率為：

表2 測試效率系數(shù)分布

從而其模型如下：

而標(biāo)準(zhǔn)型分派問題的數(shù)學(xué)模型如下：

設(shè)第i個人完成第j項(xiàng)工作所需要的時間或資源為Cij，稱為效率系數(shù),引入 0-1變量 xij：

從而其數(shù)學(xué)模型如下：

3.2 解決策略

由以上的對比可以發(fā)現(xiàn)此問題非標(biāo)準(zhǔn)形式的分派問題，解決的思想是：將成本矩陣化為方陣，n×m矩陣化為 n×n或 m×m矩陣。

（1）匈牙利法的基本原理[4]

定理1：設(shè)分派問題的效率矩陣為C=(Cij)n×n，若將該矩陣的某一行或某一列的各元素都減去同一常數(shù)，得矩陣C′=(Cij)n×n。則以C′為效率矩陣的分派問題與原分派問題的最優(yōu)解相同。

定理2：若效率矩陣 C′中每行、每列中至少有一個零元素，且存在位于不同行、不同列的n個零元素（稱獨(dú)立零元素），則令n個獨(dú)立0元素位置的決策變量為1，其余決策變量為0，得到一個最優(yōu)方案。

（2）參考文獻(xiàn)[5]針對最大化問題的收益問題不是方陣的情況提出補(bǔ)0轉(zhuǎn)換為方陣，而本文要針對最小化問題不是方陣的情況，因而提出補(bǔ)∞轉(zhuǎn)換為方陣的策略。具體如下：

①當(dāng)模塊數(shù)m多于測試通道數(shù)n時，增添虛構(gòu)的m-n行，補(bǔ)成方陣，但對應(yīng)的 Cij=∞，即這些虛構(gòu)的通道測試模塊的效率系數(shù)取為∞，仍可按標(biāo)準(zhǔn)式采用匈牙利法來求解，只是在最后的結(jié)果中應(yīng)去掉虛行的解。

②當(dāng)模塊數(shù)m少于測試通道數(shù)n時，增添虛構(gòu)的n-m列，補(bǔ)成方陣，但對應(yīng)的Cij=∞，即這些虛構(gòu)的模塊被測試通道測試的效率系數(shù)取為∞，此時同樣只是在最后的結(jié)果中應(yīng)去掉虛列的解。

（3）以上針對實(shí)際問題不是方陣進(jìn)行了增補(bǔ)，以便和標(biāo)準(zhǔn)的分派問題統(tǒng)一，但在此文中實(shí)際測試時，由于一條通道實(shí)際覆蓋路徑的不同，形成了以上表2的情況，即不僅其不是方陣而且原矩陣某些位置無效率系數(shù)，考慮實(shí)際問題，此時通道沒有覆蓋某些模塊，其不能進(jìn)行某些模塊的測試，因而可以認(rèn)為其效率系數(shù)為無窮大，這樣在運(yùn)用標(biāo)準(zhǔn)模型求解時，就始終不會取到此通路。

3.3 驗(yàn)證實(shí)例

根據(jù)表 2設(shè) Ai(i=1，…，6)為需要測試的功能模塊，Bj(j=1，…，8)為 8條驗(yàn)證通路，表中 ∞ 均用字母 a表示，則有：

以上式（1）～式（3）為適用標(biāo)準(zhǔn)型用匈牙利法求解過程，但此處又有不同于匈牙利法的地方，有如下兩點(diǎn)：

(1)求解過程遵照匈牙利法則，匈牙利法中未出現(xiàn)對無窮大數(shù)據(jù)的處理，而本例中效率系數(shù)出現(xiàn)無窮大數(shù)據(jù)。針對無窮大數(shù)據(jù)，其處理方式為其減去任何一個有限的數(shù)據(jù)保持不變?nèi)詾闊o窮大數(shù)據(jù)。

(2)對于虛構(gòu)的行或列在適用法則時不用減去本身，因?yàn)闇p去自身則成為0，這樣就會出錯。如以上式（2）在進(jìn)行行減，即將系數(shù)矩陣C的各行元素依次減去所在行的最小元素時，不適用于最后兩行。如果適用則進(jìn)行列減，即將系數(shù)矩陣C的各列元素依次減去所在列的最小元素時，不能得出有效的0元素，因?yàn)樽詈髢尚刑摌?gòu)行所有元素為0元素。

由式（3）可以看出此式中有效行中獨(dú)立零元素的個數(shù)不等于矩陣的行數(shù)，不滿足定理2，而式（3）此時也不適用于匈牙利法的計(jì)算步驟，針對此情況解決方案如下：

(1)對本文中構(gòu)造的矩陣獨(dú)立零元個數(shù)只需等于虛構(gòu)前行、列中的小者即可得到一個最優(yōu)方案；

(2)用圈0法找C′中獨(dú)立的零元素；

(3)找C′中含未加標(biāo)記的零元素個數(shù)最少的行(列)，從該行（列）中選效率系數(shù)最小的一個零元素加圈；

(4)把該圈0元素所在的行、列中的其他零元素劃去。劃去的0元素不計(jì)入式（1）統(tǒng)計(jì)每行、每列的0元素；

(5)反復(fù)執(zhí)行式（1）～式（2）直到所有行、列的零元素全部被加了標(biāo)志；

(6)去掉虛構(gòu)的行或列，此時便得到最優(yōu)解決方案。

具體如下所示：

所以最優(yōu)的測試效率是：C13+C28+C35+C47+C51+C62=2+5+1+0+2+3=13

4 結(jié)果分析

以上從系統(tǒng)的角度分析和提出如何最優(yōu)地針對分級流水單一模塊功能的驗(yàn)證方法，如果不進(jìn)行最優(yōu)化估算則會浪費(fèi)大量資源進(jìn)行無用的重復(fù)工作。以下將從驗(yàn)證效率、驗(yàn)證效果兩個方面對比隨機(jī)分配的驗(yàn)證和最優(yōu)的驗(yàn)證效率之間的差別。驗(yàn)證效果主要從功能覆蓋率和代碼覆蓋率兩個方面進(jìn)行說明。因?yàn)楸疚尼槍δ茯?yàn)證因而首先保證功能覆蓋率，其次代碼覆蓋率主要包括以下五個方面：

(1)語句覆蓋率：指驗(yàn)證程序能覆蓋代碼的行數(shù)與代碼的全部行數(shù)之比。

(2)路徑覆蓋率：指驗(yàn)證程序通過的 if…else或 case結(jié)構(gòu)的可能路徑與設(shè)計(jì)中所有可能路徑之比。

(3)表達(dá)式覆蓋率：執(zhí)行過的 if…else分支或case分支與其所有分支之比。

(4)觸發(fā)覆蓋率：分析敏感變量中的信號是否唯一觸發(fā)一個過程。

(5)自動機(jī)覆蓋率：分析仿真用例是否覆蓋了所有的狀態(tài)。

為方便計(jì)算，以下假定系統(tǒng)六大模塊語句均等、路徑均等、表達(dá)式均等、敏感變量均等、自動機(jī)狀態(tài)均等，系統(tǒng)模塊間數(shù)據(jù)流共有8條路徑，只有驗(yàn)證所有路徑才能保證以上代碼覆蓋率的100%覆蓋。

方案1：最優(yōu)方案保證了驗(yàn)證效率的同時最大地覆蓋了驗(yàn)證通路，假定每條驗(yàn)證通路的驗(yàn)證效率取3個模塊中最大的一個，這樣在同時覆蓋6大模塊和8條路徑后的效率為：C13+C28+C35+C47+C51+C62+l4+l6=2+5+1+0+2+3+8+4=25。

在綜合考慮驗(yàn)證效率和驗(yàn)證路徑時，對于模塊數(shù)大于等于路徑數(shù)的情況依然適用，但對模塊數(shù)小于路徑數(shù)的情況要得到最優(yōu)的驗(yàn)證方案需對解決方案中用圈0法找C′中獨(dú)立的零元素的步驟做一定修正：

找C′中含未加標(biāo)記的零元素個數(shù)最少的行（列），若該行（列）中只有一個獨(dú)立零元素則直接選擇，有兩個及以上獨(dú)立零元素時，則將零元素行兩兩組合，其中一個取零元素對應(yīng)的效率系數(shù)，另一個取該零行最大的效率系數(shù)（不包括無窮大），將兩者相加，零元素在其中最小的組合中取得。

方案2：根據(jù)修正后方法有：

其在覆蓋6大模塊和8條路徑后的效率為：

方案3：隨機(jī)分配：

以上三種方案效率對照如表3所示。

從表3明顯可以看出修正后的效率較之未作修正和隨機(jī)方案有明顯的提高和改善。

表3 三種方案效率對比

本文從網(wǎng)絡(luò)數(shù)據(jù)交換芯片的系統(tǒng)級分析了分級流水式芯片功能測試，建立了系統(tǒng)級模型，針對模型提出驗(yàn)證需求，在滿足需求的基礎(chǔ)上提出了驗(yàn)證策略，結(jié)合實(shí)例論證了驗(yàn)證方法的正確性及優(yōu)勢。其結(jié)果證明有效的分配策略對整個定向功能驗(yàn)證的效率影響很大。本文只是建立了一般的簡化的系統(tǒng)模型，但驗(yàn)證策略和方法卻具有普遍適用性，針對一般的系統(tǒng)均可建立此種模型，通過預(yù)算提出最優(yōu)的驗(yàn)證策略。

[1]謝希仁.計(jì)算機(jī)網(wǎng)絡(luò)（第 4版）[M].北京：電子工業(yè)出版社，2003：2-8.

[2]杜慧敏，李宥謀，趙全良.基于 Verilog的FPGA設(shè)計(jì)基礎(chǔ)[M].西安：西安電子科技大學(xué)出版社，2006：134-136.

[3]任宇，王以伍.VLSI設(shè)計(jì)中一種新型的功能驗(yàn)證方法[J].微計(jì)算機(jī)信息，2006，12(2)：285-287.

[4]馮曉慧，劉三陽.工程設(shè)計(jì)中的最優(yōu)化計(jì)算方法[M].西安：西安電子科技大學(xué)出版社，2006：219-222.

[5]張良，陳全潤，張明暉.等.“一人多事”的分派問題[R].山東：教育部精品課山東大學(xué)運(yùn)籌，2002：8-9.