運用結構關係以進行迴路化電路之組合性檢驗之研究

Using Structural Relations for Checking Combinationality of Cyclic Circuits

翁婉禎(Wan-Chen Weng)

指導教授 ： 王俊堯

國立清華大學/電機資訊學院/資訊工程學系/碩士(2014年)

摘要

檢測功能性(functionality) 和組合性(combinationality) 是處理迴路化組合電路的兩大議題。在所有輸入組合下，如果電路所有輸出端的值皆為固定且唯一，則此電路便是組合電路。而在驗證電路功能性之前，我們必須先檢測組合電路在經過迴路化之後，是否仍保有組合性。此篇論文提出兩階段驗證演算法，驗證迴路化電路的組合性。我們利用IWLS 2005之測試電路進行實驗，演示整個驗證方法之效能。與目前最新的驗證方法比較之後，我們的演算法平均加速超過4000倍以上。

關鍵字

迴路化組合電路 ； 迴路化 ； 組合電路 ； 組合性檢測

並列摘要

Functionality and combinationality are two main issues that have to be dealt with in cyclic combinational circuits, which are combinational circuits containing loops.
Cyclic circuits are combinational if nodes within the circuits are denite values under all input assignments. For a cyclied circuit, we have to check whether it is combinational or not. Thus, this paper proposes an ecient two-stage algorithm to verify the combinationality of cyclic circuits. A set of cyclied IWLS 2005 benchmarks are
performed to demonstrate the eciency of the proposed algorithm. Compared to the state-of-the-art algorithm, our approach has a speedup of about 4000 times on average.

並列關鍵字

cyclic combinational circuits ； cyclify ； combinational circuits ； combinationality checking

參考文獻

[1] J. Backes, B. Fett, and M. D. Riedel, “The analysis of cyclic circuits with Boolean satisfiability,” in Proc. International Conference on Computer-Aided Design, 2008, pp. 143–148.

[3] J. Backes and M. D. Riedel, “The synthesis of cyclic dependencies with Boolean satisfiability,” ACM Trans. Des. Autom. Electron. Syst., vol. 17, pp. 44:1–44:24,

[7] Y.-C. Chen and C.-Y. Wang, “Fast node merging with don’t cares using logic implications,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 11, pp. 1827–1832, 2010.

[8] E. Craig, “Mathematical techniques in electronics and engineering analysis,” in Proc. of the IEEE, vol. 52, no. 11, pp. 1390–1390, 1964.

[9] S. Edwards, “Making cyclic circuits acyclic,” in Proc. Design Automation Con- ference, 2003, pp. 159–162.