應用知識發現與資料探勘技術的功能性測試向量產生方法設計

Abstract

實務性功能驗證主要依賴測試平台(testbench)模擬。功能驗證用測試向量的產 生主要由隨機測試程序生成法 (random test program generation, RTPG)或是人工撰 寫法來完成。給定一個指定目標，決定性驗證測試向量生成法 (deterministic functional test pattern generation, FTPG)要求產生一個能保證含括此一驗證目標的 測試序列。然而，決定性生成驗證測試向量本身是一項非常難解的公開問題[1]也因 此本計畫並非以此為目標。相對的，我們的目標是希望能夠 (1)補充隨機測試程序 生成法涵蓋率(coverage)的不足，以及 (2)節省人工撰寫法所需耗費的資源。為了 決定性生成驗證測試向量，許多的研究早已提出提高驗證層次的方法(例如:行為層 (behavior-level)測試向量生成法)以及研發功能更強的測試向量搜尋技術(例如: 混合領域解決引擎(hybrid-domain solvers))。雖然這些技術的開發是基本而且重要 的，但是我們相信在實務上模擬資料的再運用將會可以有效的來輔助決定性驗證測 試向量生成法。 為了更有效的利用模擬資料，我們需要開發一系列計算智能方法能在這些模 擬資料上進行邏輯推理(reasoning)與抽像化處理(abstraction)。本質上，我們所 面對的問題非常類似於計算學習領域中的黑盒子問題(Black-Box problems)。雖然 許多的計算學習技術能為我們借鏡，但是兩個領域的問題們存在一個根本的差異 性。傳統計算學習技術的目的是為了能導出一個模型用來仿真底層結構的行為並且 高準確地用它來推測新輸入樣本的輸出結果。然而，在我們的情況中高準確度的要 求被大幅的放寬了，但是卻多了另一項向量反推(Justification)的要求。換言之， 給定一個目標的輸出結果，為了能成功的在輸入端產生一組測試向量，我們所演繹 的模型必須要能夠產生多組的試驗樣本(trial instances)。只要其中一組試驗樣本能 成功驅動目標輸出端結果，我們的任務就完成了。從這個觀點來看，這個計畫的獨 創性就在於發展多樣計算智能技術以有效地從模擬資料中擷取資訊並進階地協助 驗證測試向量生成的工作。 本計畫的最後目標是希望能完成一個軟體套件。它應用許多知識發現與資料 探勘技術來幫助表現隱藏在模擬資料中的有用資訊。我們的工具把模擬資料當作輸 入然後把發現的知識轉換成學習模型放進資料庫裡。應用性來說，使用者或者是測 試向量搜尋引擎可以向我們的工具來查詢。例如：一個時序性自動測試向量產生器 (ATPG)想要嘗試為一條關鍵路徑產生一組測試向量。他在邏輯反推過程中停在一個 邏輯模組(module)M 的輸出端向我們的工具查詢。我們的工具將會用從測試模版 (template)導出的模型L 中產生多組的嘗試樣本(trial pattern)。接著我們使用 這些嘗試樣本做正向模擬並且在邏輯模組M 上觀察是否任一樣本能成功產生自動 測試向量產生器(ATPG)想要的結果。另外一方面對於人工撰寫測試樣本來說，使用 者可能想要知道如何在多個週期下控制某一訊號。於是使用者送出了他欲觀察的訊 號以及輸出值向我們的工具詢問，然後我們的工具將會進行學習然後檢驗每一個模 版的時序模型(temporal model)看看是否能在多個週期之中成功的驅動此目標訊 號。總結來說，從應用的觀點來看，我們的知識發現與資料探勘軟體套件以將大量 的模擬資料重新組織成新的有效率的表示法來方便使用者和其他的工具查詢有用 的資訊以協助完成其工作。

Practical functional verification mainly relies on testbench simulation. Generation of functional patterns relies on either random test program generation (RTPG) approach [1] or manual effort. Given a specific target, deterministic functional test pattern generation (FTPG) is to produce a test sequence that guarantees to cover this target. However, deterministic FTPG problem is a very difficult open problem[2] and thus this project does not intend to solve the deterministic FTPG problem. Instead, our objective is to (1) supplement the coverage of RTPG and (2) alleviate the burden of manual TPG process. For solving FTPG, many researchers have proposed either going into a higher level such as behavior-level TPG or developing more powerful test searching techniques, such as hybrid-domain solvers. While these techniques are essential and important, we believe that re-use of simulation data to guide FTPG can also be quite effective in practice. To better utilize simulation data, we need a set of computational intelligence techniques that can perform reasoning and abstraction on top of these simulation results. Fundamentally, this forms a set of problems highly similar to black-box problems in the area of computational learning. While computational learning techniques may be useful to our needs, there exists a fundamental difference between the formulation of a typical computational learning problem and the formulation of a problem in our contexts. The objective of traditional computational learning techniques is to derive a model which can mimic the behavior of the underlying mechanism and predicts its result with high accuracy for a given new instance. However, in our case, the requirement of high accuracy is substantially relaxed but a justification requirement is added. In order to successfully generate a test pattern at the input, given a target output result, our derived model should be able to generate multiple trial input instances. As long as one of these trials excites the target output result, our mission is completed. From this perspective, the novelty of this project is to develop computational intelligence techniques that can effectively extract information from simulation data and further assist functional TPG justification. The goal of this project is to deliver a software package that employs a set of data mining and machine learning techniques to efficiently help represent the information implicitly hidden in the simulation data. Our tool takes simulation data and converts the discovered knowledge into a database of learned models. Then, either a user or a TPG search engine can send a query to our tool. For example, a sequential ATPG may try to produce a test pattern for a critical path. The ATPG stops at a module M』s outputs. Then, it performs a query to our tool. Our tool takes the learned model L from each template and try to map the test to the module M』s inputs. Each L may result in 1K patterns and forward simulation of these patterns on M validates if any of them actually produce the required test by ATPG. In manual TPG, a user may want to know how to control a signal across multiple cycles. The user sends a query to our tool by giving a signal name to be observed and a signal name to drive the value. Our tool examines the temporal model for each template to see if this is possible, and reports the relationship learned from the simulation data about how to drive the signal value across cycles. To sum up, from the application perspective, the knowledge discovery and data mining software package it to re-model and re-organize vast amount of simulation data into efficient representations to allow users as well as other tools to perform queries to extract information useful to them.