摘  要： 討論了分配問(wèn)題匈牙利法在網(wǎng)絡(luò)芯片功能驗(yàn)證中的應(yīng)用，在建立了網(wǎng)絡(luò)芯片模型的基礎(chǔ)上提出驗(yàn)證需求，針對(duì)網(wǎng)絡(luò)芯片驗(yàn)證的實(shí)際問(wèn)題對(duì)匈牙利法進(jìn)行了擴(kuò)展和改進(jìn)，提出了適應(yīng)于分級(jí)流水芯片提高其功能驗(yàn)證效率的有效方式，改進(jìn)后的匈牙利法具有更好的適用性。芯片驗(yàn)證結(jié)果證明了其可行性及其優(yōu)越性。
關(guān)鍵詞： 包交換；功能驗(yàn)證；匈牙利法；覆蓋率

    包交換又稱(chēng)分組交換，是一種傳送數(shù)據(jù)的方法，將用戶(hù)傳送的數(shù)據(jù)包劃分成一定長(zhǎng)度的單元，每個(gè)單元稱(chēng)為一個(gè)分組。在每個(gè)分組的前面加上一個(gè)分組頭，用以指明該分組發(fā)往何地址，然后由交換機(jī)根據(jù)每個(gè)分組的地址標(biāo)志，將他們轉(zhuǎn)發(fā)至目的地，這一過(guò)程稱(chēng)為分組交換。包交換處理分組的一般過(guò)程是：將收到的數(shù)據(jù)包先放入緩存，再查找轉(zhuǎn)發(fā)表，找出到某個(gè)目的地址應(yīng)從哪個(gè)端口轉(zhuǎn)發(fā)，然后由交換機(jī)構(gòu)將該數(shù)據(jù)包傳遞給適當(dāng)?shù)亩丝谵D(zhuǎn)發(fā)出去[1]。由于包交換功能復(fù)雜，其硬件設(shè)計(jì)達(dá)到百萬(wàn)門(mén)級(jí)，而驗(yàn)證百萬(wàn)門(mén)的設(shè)計(jì)是一件非常難的事情。目前進(jìn)行功能驗(yàn)證有效的策略主要有兩種[2]：一種是傳統(tǒng)的功能驗(yàn)證方法，包括模擬驗(yàn)證、形式驗(yàn)證、基于斷言的驗(yàn)證三種方法，其特點(diǎn)是基于特定測(cè)試向量的針對(duì)特定功能的定向功能驗(yàn)證；另一種是基于偽隨機(jī)向量的針對(duì)覆蓋率的隨機(jī)功能驗(yàn)證。當(dāng)然兩種驗(yàn)證方法又有交叉。但針對(duì)一般的設(shè)計(jì)，其驗(yàn)證策略通常先進(jìn)行定向功能驗(yàn)證，保證設(shè)計(jì)滿(mǎn)足設(shè)計(jì)規(guī)范的功能要求，但其很難避免設(shè)計(jì)之外的缺陷及錯(cuò)誤，也很難滿(mǎn)足代碼覆蓋率的要求，所以需要進(jìn)一步用隨機(jī)測(cè)試向量進(jìn)行隨機(jī)驗(yàn)證[3]。但無(wú)論哪種策略在進(jìn)行驗(yàn)證時(shí)，在頂層testbench加載激勵(lì)時(shí)，不同的數(shù)據(jù)必然有自己特定的數(shù)據(jù)通道，但不同的數(shù)據(jù)通道在進(jìn)行功能驗(yàn)證時(shí)，其效率是不同的，因而有必要從數(shù)據(jù)通道方面針對(duì)驗(yàn)證進(jìn)行研究，以提高功能驗(yàn)證效率。
    本文首先根據(jù)以上包交換工作過(guò)程構(gòu)造定向功能驗(yàn)證模型，根據(jù)驗(yàn)證需求提出如何在滿(mǎn)足需求的基礎(chǔ)上高效地進(jìn)行定向功能驗(yàn)證，并對(duì)結(jié)果進(jìn)行分析。
1 模型概述
    本文將整個(gè)包交換系統(tǒng)劃分成三個(gè)部分，分別是輸入緩存管理、查找管理和輸出管理。模塊之間數(shù)據(jù)通道采用分級(jí)流水管理的方式，假定輸入緩存管理模塊分為兩個(gè)獨(dú)立的功能模塊，以分別處理不同類(lèi)型的輸入數(shù)據(jù)。數(shù)據(jù)處理完成后存入緩存，查找管理模塊從緩存中讀出數(shù)據(jù)包頭信息進(jìn)行分類(lèi)管理，假定其同樣有兩個(gè)獨(dú)立的功能模塊。輸出管理模塊從查找模塊讀出包頭信息，再?gòu)木彺婺K讀出輸出的數(shù)據(jù)包信息，并將此數(shù)據(jù)包信息轉(zhuǎn)發(fā)出去，在此假定模塊也有兩個(gè)獨(dú)立的功能模塊，此時(shí)建立系統(tǒng)模型輸出管理如圖1所示。

    以上式（1）～式（3）為適用標(biāo)準(zhǔn)型用匈牙利法求解過(guò)程，但此處又有不同于匈牙利法的地方，有如下兩點(diǎn)：
    (1)求解過(guò)程遵照匈牙利法則，匈牙利法中未出現(xiàn)對(duì)無(wú)窮大數(shù)據(jù)的處理，而本例中效率系數(shù)出現(xiàn)無(wú)窮大數(shù)據(jù)。針對(duì)無(wú)窮大數(shù)據(jù)，其處理方式為其減去任何一個(gè)有限的數(shù)據(jù)保持不變?nèi)詾闊o(wú)窮大數(shù)據(jù)。
    (2)對(duì)于虛構(gòu)的行或列在適用法則時(shí)不用減去本身，因?yàn)闇p去自身則成為0，這樣就會(huì)出錯(cuò)。如以上式（2）在進(jìn)行行減，即將系數(shù)矩陣C的各行元素依次減去所在行的最小元素時(shí)，不適用于最后兩行。如果適用則進(jìn)行列減，即將系數(shù)矩陣C的各列元素依次減去所在列的最小元素時(shí)，不能得出有效的0元素，因?yàn)樽詈髢尚刑摌?gòu)行所有元素為0元素。
    由式（3）可以看出此式中有效行中獨(dú)立零元素的個(gè)數(shù)不等于矩陣的行數(shù)，不滿(mǎn)足定理2，而式（3）此時(shí)也不適用于匈牙利法的計(jì)算步驟，針對(duì)此情況解決方案如下：
    (1)對(duì)本文中構(gòu)造的矩陣獨(dú)立零元個(gè)數(shù)只需等于虛構(gòu)前行、列中的小者即可得到一個(gè)最優(yōu)方案；
    (2)用圈0法找C′中獨(dú)立的零元素；
    (3)找C′中含未加標(biāo)記的零元素個(gè)數(shù)最少的行(列)，從該行（列）中選效率系數(shù)最小的一個(gè)零元素加圈；
    (4)把該圈0元素所在的行、列中的其他零元素劃去。劃去的0元素不計(jì)入式（1）統(tǒng)計(jì)每行、每列的0元素；
    (5)反復(fù)執(zhí)行式（1）～式（2）直到所有行、列的零元素全部被加了標(biāo)志；
    (6)去掉虛構(gòu)的行或列，此時(shí)便得到最優(yōu)解決方案。
    具體如下所示：

4 結(jié)果分析
    以上從系統(tǒng)的角度分析和提出如何最優(yōu)地針對(duì)分級(jí)流水單一模塊功能的驗(yàn)證方法，如果不進(jìn)行最優(yōu)化估算則會(huì)浪費(fèi)大量資源進(jìn)行無(wú)用的重復(fù)工作。以下將從驗(yàn)證效率、驗(yàn)證效果兩個(gè)方面對(duì)比隨機(jī)分配的驗(yàn)證和最優(yōu)的驗(yàn)證效率之間的差別。驗(yàn)證效果主要從功能覆蓋率和代碼覆蓋率兩個(gè)方面進(jìn)行說(shuō)明。因?yàn)楸疚尼槍?duì)功能驗(yàn)證因而首先保證功能覆蓋率，其次代碼覆蓋率主要包括以下五個(gè)方面：
    (1)語(yǔ)句覆蓋率：指驗(yàn)證程序能覆蓋代碼的行數(shù)與代碼的全部行數(shù)之比。
    (2)路徑覆蓋率：指驗(yàn)證程序通過(guò)的if…else或case結(jié)構(gòu)的可能路徑與設(shè)計(jì)中所有可能路徑之比。
    (3)表達(dá)式覆蓋率：執(zhí)行過(guò)的if…else分支或case分支與其所有分支之比。
    (4)觸發(fā)覆蓋率：分析敏感變量中的信號(hào)是否唯一觸發(fā)一個(gè)過(guò)程。

參考文獻(xià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] 馮曉慧，劉三陽(yáng).工程設(shè)計(jì)中的最優(yōu)化計(jì)算方法[M].西安：西安電子科技大學(xué)出版社，2006：219-222.
[5] 張良，陳全潤(rùn)，張明暉.等.“一人多事”的分派問(wèn)題[R].山東：教育部精品課山東大學(xué)運(yùn)籌，2002：8-9.