王潤 蔣劍飛 王琴

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

關鍵詞：功能驗證;貝葉斯網(wǎng)絡;機器學習;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]。目前，在完整的芯片開發(fā)周期中，70%的設計開發(fā)時間和資源被用于功能驗證[2]。功能驗證已經(jīng)成為芯片和系統(tǒng)設計領域的一項主要挑戰(zhàn)，當工程師需要在日益密集的芯片上設置越來越多的功能時，成功驗證芯片和系統(tǒng)功能所需要的時間也越來越長，這就需要開發(fā)新的驗證技術，在資源有限的情況下，為驗證人員提供快速實現(xiàn)其目標的方法。目前，以覆蓋率為導向的測試用例生成技術有兩個主要缺點[3]：①覆蓋率反饋中包含了人的參與、調(diào)整激勵的生成和分析所需的大量人為勞動，因此增加了成本;②整個驗證流程的反饋發(fā)生在仿真之后。首先需要進行仿真，然后才發(fā)現(xiàn)激勵沒有命中的感興趣的覆蓋點，這樣才能調(diào)整激勵。

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

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

1 覆蓋率驅(qū)動的測試用例生成

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

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

2 基于貝葉斯網(wǎng)絡的面向覆蓋的測試生成

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

2.1 貝葉斯網(wǎng)絡

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

可以看出，該式實際上隱含了上文圖形結(jié)構(gòu)的條件獨立性。公式表明，貝葉斯網(wǎng)絡指定的聯(lián)合分布可以用單個局部交互模型的乘積表示。因此，雖然貝葉斯網(wǎng)絡可以表示任意的概率分布，但它們?yōu)槟切┛梢杂煤唵谓Y(jié)構(gòu)表示的分布提供了計算優(yōu)勢。

貝葉斯網(wǎng)絡可以有效解決通過貝葉斯規(guī)則產(chǎn)生一個節(jié)點（或一組節(jié)點）的值[X]的后驗概率，如式（2）所示。

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

2.2 基于貝葉斯網(wǎng)絡的CDG

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

2.3 基于貝葉斯網(wǎng)絡的CGRA驗證

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

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

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

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

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

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

3 結(jié)語

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

參考文獻：

[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].北京：機械工業(yè)出版社，2017.

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

[13] TASIRAN S，F(xiàn)ALLAH 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īng)倫. 貝葉斯網(wǎng)絡在可靠性分析中的應用[J].系統(tǒng)工程理論與實踐，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] 譚國蘋.含有隱藏變量的貝葉斯網(wǎng)絡的學習與應用[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.

（責任編輯：孫 娟）