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

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

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

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

參考文獻
[1] 謝希仁.計算機網絡（第4版）[M].北京：電子工業(yè)出版社，2003：2-8.
[2] 杜慧敏，李宥謀，趙全良.基于Verilog的FPGA設計基礎[M].西安：西安電子科技大學出版社，2006：134-136.
[3] 任宇，王以伍.VLSI設計中一種新型的功能驗證方法[J]. 微計算機信息，2006，12(2)：285-287.
[4] 馮曉慧，劉三陽.工程設計中的最優(yōu)化計算方法[M].西安：西安電子科技大學出版社，2006：219-222.
[5] 張良，陳全潤，張明暉.等.“一人多事”的分派問題[R].山東：教育部精品課山東大學運籌，2002：8-9.