請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/73996
標題: | 針對電路最佳化問題之二階量化布林公式解答 Two-QBF Solving for Circuit Optimization Problems |
作者: | An-Wei Hsu 許安薇 |
指導教授: | 黃鐘揚(Chung-Yang Huang) |
關鍵字: | 二階量化布林公式,全稱量詞,最佳化問題,最佳解,電路問題,電子設計自動化, two-QBF formula,universal quantifier,optimization problem,optimum solution,circuit problem,Electronic Design Automation, |
出版年 : | 2019 |
學位: | 碩士 |
摘要: | 在電子設計自動化的研究領域中,有許多問題可以用二階量化布林公式表示。在二階量化布林公式的限制下找尋最佳解也因此成為一個重要的研究。現存的正式最佳化方法仍僅限於布林公式或以存在量詞開頭的量化布林公式,並不足以支援像工程改變命令這樣的電子設計自動化問題。
有鑑於現存最佳化演算法的不足,我們針對以全稱量詞開頭的二階量化布林公式的最佳化提供了一個新的二階布林公式解答器。根據我們所提供的第一階賦值解答,使用者可以藉由不斷增加限制來獲得客製化的最佳解。 針對由電路轉化的二階布林公式限制,我們應用電路所提供的資訊優化解答器,與現今最強的二階布林公式解答器遞迴摘要精煉演算法相比,我們在電路問題的單次二階布林公式解答獲得可比較的性能。 Two-QBF formula is an effective framework for many problems in the field of Electronic Design Automation (EDA). The optimum solution heuristic of two-QBF formula hence becomes an important topic for research. Previous works are limited to solutions on quantifier-free or two-QBF formula leaded by an existential quantifier, which are not applicable to some EDA problems such as ECO. We propose a two-QBF solving heuristic which enables users to obtain first-level solutions, to incrementally add extra constraint clauses, and to get an optimum solution with customized cost. These functions are quite helpful for many EDA problems. For formula transformed from circuit problems, with the aid of circuit information we can achieve performance comparable to CEGAR-based solvers, which are the most powerful solvers on QBF problems. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/73996 |
DOI: | 10.6342/NTU201903034 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 1.75 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。