利用高層次設計資訊和不變量自動化萃取技術改進模擬和正規驗證效率

在此論文之中，我們建構了一個開放原始碼暫存器轉換階層(RTL)的架構－QuteRTL，在暫存器轉換階層的合成與驗證相關研究裡，它能作為一個前端處理器。使用者可以利用此架構解析出暫存器轉換階層的Verilog硬體設計，獲得此設計的控制與資料流程圖(CDFG)，並且得到高層次的設計資訊(例如:有限狀態機)，此外亦可利用QuteRTL合成出階層或展平式的邏輯電路，隨後與邏輯合成最佳化工具(例如:Berkeley ABC)搭配可得到最佳化後的邏輯電路。有許多的研究機會因QuteRTL而變的可行，諸如暫存器轉換階層的偵錯、解法器、設計抽象化…等。另外與開放源的邏輯合成最佳化工具搭配，可形成一個完整且開放源的暫存器轉換階層合成至最佳化邏輯電路工具組。在QuteRTL的架構下，我們進一步的提出系統化且健全的高階設計資訊萃取演算法，進而自動化地萃取資訊並應用在改善暫存器轉換階層的模擬與正規驗證上。在幫助改善模擬驗證方面，本論文提出一套自動產生目標限制方程式的演算法技術，此技術能自動化地產生簡潔有效用的限制方程式來引導隨機測試向量的產生過程。在隨機向量的產生過程之中，設計者人工地撰寫測試環境與限制式為最花費時間且易錯的步驟，本技術目的即是為了改善此驗證瓶頸而生。我們自動化此耗時易錯的步驟，因而大大地降低設計者在人工撰寫測試限制式的重擔。我們實驗此技術在眾多不同設計之中，結果佐證了此技術在模擬時間與驗證完整度上皆能夠比隨機測試向量與設計者自行撰寫的測試向量還為優良。另一方面，在改善正規驗證上，本論文提出了一套與驗證命題相關的循序不變量萃取演算法，並利用萃取出的不變量幫助改善歸納式證明演算(UMC)的效益。藉由分析驗證命題的組成述部，我們可以找出與其相關的有限狀態機與計數器，進而快速地找出相關的循序不變量，由於此不變量與欲驗證命題具有高度的關連性，往往能夠大大地幫助此命題的歸納證明。在傳統式歸納證法(induction-based UMC)之中，我們萃取出的不變量精練了歸納前提(inductive hypothesis)；在內插式歸納證法(interpolation-based UMC)，此不變量改善了可到達狀態集合的內差精準度。實驗結果顯示在大多數的證明命題中，我們所提出的技術勝過許多先進的證明解法器，特別在困難的證明命題更有顯著的效益。

關鍵字

限制方程式；隨機模擬驗證；驗證平台；正規驗證

並列摘要

In the dissertation, we build an open source RTL framework, QuteRTL, which can serves as a front-end for the researches in RTL synthesis and verification. Users can use our framework to read in RTL Verilog designs, obtain CDFGs, extract high-level design information (e.g. FSM), generate hierarchical or flattened gate-level netlists, and link with logic synthesis tools (e.g. Berkeley ABC). Various research opportunities will be made possible by this framework, such as RTL debugging, word-level formal engines, design abstraction, and a complete open-source RTL-to-gate tool chain, etc. In addition, we also devise systematic and robust algorithms that can automatically extract high level design intents from complex RTL Designs, and then utilize them to assist both simulation and formal verification. For simulation, we proposed an Automatic Target Constraint Generation (ATCG) technique to automatically generate compact and high-quality constraints for the guided random simulation environment. Our objective is to tackle the biggest bottleneck of the entire constrained random simulation process ─ the time-consuming and error-prone manual testbench composition process. The proposed approach alleviates the users’ burden in manually writing constraints for the constrained random simulation environment. Our experimental results show that ATCG can outperform both directed and random simulations in both coverage and simulation runtime for a variety of designs. For formal verification, we propose a property-specific sequential invariant extraction algorithm to improve the performance of the SAT-based unbounded modeling checkers (UMCs). By analyzing the property-related predicates and their corresponding high-level design constructs such as FSMs and counters, we can quickly identify the sequential invariants that are useful in improving the property proving capabilities. We utilize these sequential invariants to refine the inductive hypothesis in induction-based UMCs, and to improve the accuracy of reachable state approximation in interpolation-based UMCs. The experimental results show that our tool can outperform a state-of-the-art UMC in most cases, especially for the difficult true properties.

並列關鍵字

Constraint generation ； constraint guided simulation ； function verification ； testbench authoring ； model checking

參考文獻

3.Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. Release 70930.

4.S.Amellal and B.Kaminska. ”Scheduling of a control and data flow graph”. In IEEE Int. Symp. on Circuits and Systems, volume 3, pages 1666–1669. May 1993.

5.H.-H. Yeh and C.-Y. Huang, "Automatic Constraint Generation for Guided Random Simulation", in Proc. Asia South Pacific Design Automation Conference (ASPDAC), 2010.

7.K. Nanshi and F. Somenzi, “Guiding simulation with increasingly refined abstract traces”, in Proc. Design Automation Conference (DAC), pp 737-742. ACM/IEEE, 2006

8.H.-H. Yeh, C.-Y. Wu and C.-Y. Huang, “Property-Specific Sequential Invariant Extraction for SAT-based Unbounded Model Checking”, in Proc. International Conference on Computer-Aided Design (ICCAD), pp. 674-678. , 2011

國際替代計量

利用高層次設計資訊和不變量自動化萃取技術改進模擬和正規驗證效率

全文下載

主題瀏覽