基于貝葉斯網絡的驗證激勵向量生成研究

王潤 蔣劍飛 王琴

摘 要：為了解決傳統數字芯片驗證環節中基于仿真的驗證（或動態驗證）功能覆蓋率收斂速度慢的缺點，提出一種新的以功能覆蓋為導向的測試用例生成方法，該方法基于貝葉斯網絡和機器學習技術，可實現從覆蓋模型到測試用例生成器反饋回路的自動關閉，在DUT的驗證過程中，使用該方法為所測試的設計生成新的激勵。實驗結果表明，基于貝葉斯網絡的CDG技術測試用例使用較少，覆蓋率收斂更快，與傳統基于仿真的驗證技術相比，測試用例數量減少了43%。基于貝葉斯網絡的CDG技術提高了覆蓋率的收斂速度，縮短了驗證周期，相比于傳統動態驗證技術而言其芯片功能驗證更完善。

關鍵詞：功能驗證;貝葉斯網絡;機器學習;CDG;覆蓋率

DOI：10. 11907/rjdk. 192567 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP301文獻標識碼：A 文章編號：1672-7800（2020）007-0001-04

Research on Generation of Verification Incentive Vector Based on Bayesian Network

WANG Run，JIANG Jian-fei，WANG Qin

（Microelectronics Institute，Shanghai Jiao Tong University， Shanghai 200240，China）

Abstract：In order to solve the problem of slow convergence rate of functional coverage of simulation based verification （or dynamic verification） in the traditional verification of digital chips，this paper proposes a new method of test case generation based on function coverage. Based on Bayesian network and machine learning technology， this method provides an effective method to automatically close the feedback loop from coverage model to test case generator. In the verification process of DUT （design under test）， this method is used to generate new incentives for the tested design. The experimental results show that the CDG （coverage driven test case generation） technology based on Bayesian network uses fewer test cases， and the coverage convergence is faster. Compared with the traditional simulation based verification technology， the number of test cases is reduced by 43%. CDG technology based on Bayesian network improves the convergence rate of coverage and reduces the verification cycle. Compared with the traditional dynamic verification technology， the chip function verification is more complete.

Key Words：functional verification; Bayesian network; machine learning; CDG; coverage

0 引言

功能驗證被廣泛認為是硬件設計周期中的瓶頸[1]。目前，在完整的芯片開發周期中，70%的設計開發時間和資源被用于功能驗證[2]。功能驗證已經成為芯片和系統設計領域的一項主要挑戰，當工程師需要在日益密集的芯片上設置越來越多的功能時，成功驗證芯片和系統功能所需要的時間也越來越長，這就需要開發新的驗證技術，在資源有限的情況下，為驗證人員提供快速實現其目標的方法。目前，以覆蓋率為導向的測試用例生成技術有兩個主要缺點[3]：①覆蓋率反饋中包含了人的參與、調整激勵的生成和分析所需的大量人為勞動，因此增加了成本;②整個驗證流程的反饋發生在仿真之后。首先需要進行仿真，然后才發現激勵沒有命中的感興趣的覆蓋點，這樣才能調整激勵。

常見的測試用例有幾個來源[4]：①編寫定向的直接測試用例[5]，存在的問題是仿真效率低下，對于復雜設計，固定場景的定向測試被認為是無效的[6];②小部分測試用例通過手工隨機約束設計[7]，包括覆蓋設計邊界情況，存在的問題是，邊界情況需要對設計有比較充分的理解才能覆蓋到，如果對設計不甚了解，則覆蓋邊界情況需要耗費大量時間;③運行現有的測試用例集（遺留測試或商業測試套件）[8]，顯然，當所驗證的設計是比較成熟的模塊，有比較完備的測試用例，這種方法才起作用。

以上方法都存在覆蓋率收斂速度慢的缺點，鑒于此，本文提出一種面向覆蓋的測試用例生成方法。本文方法是在一個統計推斷的框架中映射CDG（Coverage Driven Testcase Generation）[9]，并應用機器學習技術實現CDG目標。具體而言，使用貝葉斯網絡建模覆蓋率信息和測試用例之間的關系，可以提高功能覆蓋率收斂速度。

1 覆蓋率驅動的測試用例生成

一般而言，CDG的目標是自動向測試用例生成器提供基于覆蓋率分析的指令。這可以進一步分解為兩個子目標：①向測試生成器提供有助于實現困難情況（即未覆蓋或很少覆蓋的任務）的指令，實現此子目標可以縮短完成測試計劃所需時間，并減少手動編寫指令的數量;②盡可能使用一組不同的指令，為任何覆蓋率模型[10]提供更容易到達的指令，實現該子目標使驗證過程更加健壯，因為它增加了驗證過程中任務被覆蓋的次數。此外，如果通過不同的方向到達覆蓋率任務，則會大大增加發現與此激勵相關的隱藏錯誤的機會。

以覆蓋率為驅動的激勵生成有幾種不同風格，可以根據覆蓋率反饋回路在調整過程中的位置對它們進行歸類[11]，包括動態覆蓋率控制激勵生成、基于模型的覆蓋率驅動測試生成、自動覆蓋率控制生成等。圖1為驗證流程中對覆蓋率分析的反饋回路，首先編碼激勵參數和偏置約束信息，通過PRNG（偽隨機數發生器）生成滿足特定約束條件的激勵，通過模擬仿真將生成好的激勵驅動到DUT（Design Under Test）的端口上，仿真工具會根據覆蓋模型自動統計功能覆蓋率，并將不同測試用例的覆蓋率數據整合到一起，得到積累的覆蓋率數據，然后通過人為的覆蓋率分析，進一步調整約束偏置，生成修改后的新測試用例，繼續仿真，直到達到覆蓋率收斂為止，這樣即可完成功能驗證。有兩種常用的CDG方法：基于反饋的CDG和基于構造的CDG。基于反饋的CDG依賴于來自覆蓋率分析的反饋實現對測試生成器指令的自動修改。例如，在文獻[12]中，使用遺傳算法選擇和修改測試用例以增加覆蓋率;在文獻[13]中，覆蓋分析數據用于修改表示DUT的馬爾科夫鏈的參數，然后使用馬爾可夫鏈生成設計的測試用例;在文獻[14]中，覆蓋率分析結果觸發一組修改測試指令的生成規則。相反，在基于構造的CDG中，DUT的外部模型用于生成測試指令，這些指令旨在準確地命中覆蓋率任務。例如，在文獻[15]中，一個流水線設計的FSM模型用于生成覆蓋流水線中指令及相關性測試。

2 基于貝葉斯網絡的面向覆蓋的測試生成

貝葉斯網絡是一組變量聯合概率分布的圖形表示，這種表達最初是為了編碼變量間的不確定關系，最初由遺傳學家蘇厄爾·賴特[16]提出。貝葉斯網絡將CDG映射到一個統計推斷的框架中，可以概率方式表示CDG成分之間的復雜（可能是隨機的）關系，是一種有效的建模方案。

2.1 貝葉斯網絡

貝葉斯網絡由兩部分組成。第一個是有向無環圖，其中每個頂點對應一個隨機變量。該圖反映所表示分布的一組條件獨立屬性：在給定其父級狀態的圖中，每個變量可能與其非子級無關。該圖可表示概率分布的定性結構，并用于有效的推理和決策[17]。第二部分是局部交互模型的集合，描述每個變量[Xi]的條件概率[p（Xi|Pai）]。這兩個分量共同代表一組變量[X][18]上唯一的聯合概率分布。聯合概率分布如式（1）所示。

可以看出，該式實際上隱含了上文圖形結構的條件獨立性。公式表明，貝葉斯網絡指定的聯合分布可以用單個局部交互模型的乘積表示。因此，雖然貝葉斯網絡可以表示任意的概率分布，但它們為那些可以用簡單結構表示的分布提供了計算優勢。

貝葉斯網絡可以有效解決通過貝葉斯規則產生一個節點（或一組節點）的值[X]的后驗概率，如式（2）所示。

因此，可以通過選擇最大后驗概率[max p（X|E）]的形式進行統計推斷[19]。

2.2 基于貝葉斯網絡的CDG

CDG過程從構建貝葉斯網絡模型開始，該模型描述測試指令與覆蓋空間之間的關系。圖2展示了一個簡單但典型的貝葉斯網絡，它對CDG的一小部分進行了建模。貝葉斯網絡描述了影響生成的命令類型（cmd_type）的指令與CPU內活動內核（core_enable）之間的關系，以及生成的命令（cmd）、其響應（resp）和生成命令的內核（core）的覆蓋屬性。網絡由輸入節點（左邊的白色圓圈）和定義覆蓋空間的覆蓋節點（右邊的白色方塊）組成，除上述可以物理觀測到的節點之外，網絡還可能包含隱藏的節點，即沒有任何物理證據（觀測）證明它相互作用的變量，這些變量在圖中表示為陰影橢圓。在貝葉斯網絡結構中加入隱藏節點主要是為了反映關于隱藏節點的專家領域的知識[20]。

2.3 基于貝葉斯網絡的CGRA驗證

可重構計算架構CGRA（Coarse-Grained Reconfigurable? Architecture）是指能根據變換的數據流或控制流，對硬件結構進行動態配置的一種體系結構[21]。CGRA最大的優勢是能通過硬件結構組織不同粒度和不同功能的計算資源，通過運行過程中的硬件配置，調整硬件功能，根據數據流的特點，讓功能配置好的硬件資源互連形成相對固定的計算通路，從而以接近“專用電路”的方式進行數據驅動下的計算[22]。當算法和應用變換時，再次通過配置，使硬件重構為不同的計算通路去執行，是一種高效而靈活的計算架構，因而能在算力和能耗上取得很好平衡，達到更高的能效比[23]。

對于CGRA的運算單元PE（Process Element），本文使用基于貝葉斯網絡的CDG驗證其功能覆蓋率。使用的PE單元主要由3個子模塊組成，如圖3所示：輸入Buffer單元，ALU和輸出Buffer單元。輸入端有時鐘和復位信號、數據信息、配置信息和來自下層PE的反壓信號。為了簡化分析，對單個PE進行驗證，每條指令由4個輸入變量組成，第1個變量表示指令的第1個數據（1 bit valid + 2 bit tag + 32 bit data），第2個變量表示指令的第2個數據（1 bit valid + 2 bit tag + 32 bit data），第3個變量表示數據輸出是否有效（1bit valid + 2bit tag + 1bit bool），valid位代表數據輸入是否有效，每筆數據包含一個tag位，表示數據是否處于亂序執行模式。為了簡化分析，對數據位和tag位分別進行處理，單條輸入指令包括6筆數據信息。由于tag位是2bit位寬，PE有4個不同的tag以區分每筆數據，因此，將每4筆數據劃分為一個transfer，使用tag表示每個transfer中的不同數據，如果上一個transfer的一筆數據在inbuffer里沒有處理完，在下一個transfer輸入形同tag的數據時會引起tag沖突。第4個變量表示PE的配置。

本實驗對輸入變量進行組合限制，使用100個直接測試用例，如圖4所示。每組測試用例由6個輸入變量，5個功能點組成，共11個變量，使用直接測試用例對網絡模型進行訓練。

使用一個覆蓋模型檢查PE狀態及其指令屬性，覆蓋模型由7個屬性組成：數據一的輸入屬性（dp1+tag）、數據二的輸入屬性（dp2+tag）、數據三的輸入屬性（dp3）、PE的配置狀態（op）、PE的輸出屬性（state），目的是生成覆蓋上述覆蓋模型的指令流。在指定貝葉斯網絡結構后，使用數據樣本和相應的覆蓋任務對其進行訓練。為此，根據使用的指令和生成的覆蓋任務構建一個訓練集，然后使用許多已知學習算法中的一種估計貝葉斯網絡參數（條件概率分布集）。訓練完成的貝葉斯網絡模型如圖5所示，可以看出功能點State與4個輸入變量相關聯，分別為：Data1、H1、H2、Data2。

在評估階段，訓練好的貝葉斯網絡可以通過后驗概率確定期望覆蓋任務的指令。例如，在該模型中，指令是測試生成器中內部繪制的可能結果的權重，可以為覆蓋節點（例如state）的某個bin計算指令節點（例如data1、data2、H1、H2）的后驗概率分布，后者直接轉換為要寫入測試生成器參數文件中的權重集，調整前后的激勵變量權重分布對比如圖6所示。

實驗結果表明，使用CDG技術能夠實現34個測試用例之后覆蓋100%的功能點，而用戶自定義的測試用例在60個測試用例之后才能實現功能點的全覆蓋[14-15]。使用CDG技術的測試用例數量與使用隨機測試用例技術的測試用例數量對比如圖7所示。該建模技術能夠有效實現覆蓋率的目標，對難以覆蓋的情況更容易達到，覆蓋率可以實現更快收斂，節省了時間。

3 結語

本文提出了一種面向覆蓋的測試用例生成方法，實驗結果表明，該建模技術利用節點的先驗概率與后驗概率，可以在毫不了解設計的情況下有目的地修正覆蓋率漏洞，達到覆蓋率快速收斂的效果。該建模技術能夠有效實現CDG的目標，即邊界情況更容易覆蓋到，覆蓋率更容易收斂。本文研究為芯片的功能驗證提供了切實可行的新思路，未來還可以繼續深入研究動態貝葉斯網絡，即將時間對貝葉斯網絡結構的影響考慮進來，從而對隨機過程中的時間依賴性進行建模。此外，可進一步集成專家領域知識，確定貝葉斯網絡中的隱藏節點，精細化貝葉斯網絡結構，從而實現覆蓋模型的不同路徑覆蓋，提高芯片隱藏漏洞發現幾率。

參考文獻：

[1] BERGERON J. Writing testbenches： functional verification? of HDL models[M]. Dordrecht： Kluwer Academic Publishers，2000.

[2] ANDREW P. Functional verification[M].Functional Verification Coverage Measurement and Analysis. 2004.

[3] CIEPLUCHA M. Metric-driven verification methodology with regression management[J]. Journal of Electronic Testing，2019，35（1）：101-110.

[4] GLENN S，MEIL G，RODRIGUEZ E，et al. Functional design verification for the PowerPC 601 microprocessor[C].Proceedings of 12th IEEE on VLSI Test Symposium，1994.

[5] KANTROWITZ M，NOACK L M. I'm done simulating; now what？ verification coverage analysis and correctness checking of the DECchip 21164 Alpha microprocessor[C].Proceedings of 33rd IEEE，Design Automation Conference，1996：325-330.

[6] MEYER，ANDREAS.Principles of functional verification[M]. Oxford： Newnes，2003.

[7] CHEN W，WANG L C，BHADRA J，et al. Simulation knowledge extraction and reuse in constrained random processor verification[C]. 2013 50th ACM/ EDAC/IEEEDesign Automation Conference，2013：1-6.

[8] GANAPATHY G，NARAYAN R，JORDEN G，et al. Hardware emulation for functional verification of K5[C].33rd Design Automation Conference，1996：315-318.

[9] STAATS M，GAY G，WHALEN M，et al. On the danger of coverage directed test case generation[J]. Macromolecules，2012，31（15）：409-424.

[10] GRINWALD R，HAREL E，ORGAD M，et al. User defined coverage——a tool supported methodology for design verification[C].California：Proceedings of the 35th Design Automation Conference，1998：158-165.

[11] WILE B， GOSS J C， ROESNER W.全面的功能驗證[M].北京：機械工業出版社，2017.

[12] BOSE，MRINAL. Automatic bias generation for biased random instruction generation[C].Seoul： CEC2001： Congress on Evolutionary Computing，2001.

[13] TASIRAN S，FALLAH F，CHINNERY D G，et al. A functional validation technique： biased-random simulation guided by observability-based coverage[C].19th International Conference on Computer Design， 2001：82-88.

[14] NATIV G，MITTENNAIER S，UR S，et al.Cost evaluation of coverage directed test generation for the IBM mainframe[C].Proceedings of International Test Conference，2001：793-802.

[15] UR S，YADIN Y.Micro-architecture coverage directed generation of test programs[C].Proceedings of the 36th Design Automation Conference，1999：175-180.

[16] MUSTAIN，BRIAN C.Correlation and Causation[J]. Science News，2013，121（24）：387.

[17] 周忠寶，董豆豆，周經倫. 貝葉斯網絡在可靠性分析中的應用[J].系統工程理論與實踐，2006，26（6）：95-100.

[18] PEARL J.Probabilistic reasoning in intelligent systems：network of plausible inference[M].San Francisco：Morgan Kaufmann Publishers，1988.

[19] RUPPERT，DAVID.Probabilistic networks and expert systems[J].Journal of the American Statistical Association，2001，96（456）：1524-1524.

[20] 譚國蘋.含有隱藏變量的貝葉斯網絡的學習與應用[D].北京：中央民族大學，2015.

[21] ZION K， STEVEN J E，WILTON S J E. Register file architecture optimization in a coarse-grained reconfigurable architecture[C].Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines，2005：1-10.

[22] YANG C，LIU L B，WANG Y S，et al. Configuration approaches to enhance computing efficiency of coarse-grained reconfigurable array[J]. Journal of Circuits，Systems and Computers，2015，24（3）：1550043.

[23] GANGHEE L，SEOKHYUN L，KIYOUNG C，et al. Routing-aware application mapping considering steiner points for coarse-grained reconfigurable architecture[C].6th International Workshop on Applied Reconfigurable Computing，2010： 231-243.

（責任編輯：孫 娟）