考量布林關係於邏輯電路最佳化的研究

Logic Optimization with Considering Boolean Relations

李東原(Tung-Yuan Lee)

指導教授 ： 王俊堯

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

摘要

布林關係可以用來表達兩域之間的多對多映射。
在邏輯化簡時考量布林關係可以利用邏輯電路中潛在的彈性最佳化電路。
在本文中，我們提出了考量布林關係邏輯最佳化的方法。
我們的方法會找出適合的子電路，並透過布林關係改變區域性的電路功能同時進行最佳化，而不改變原本電路整體功能。
我們在MCNC的電路上進行實驗，這些測試電路已經沒辦法透過ABC中的resyn2最佳化。
實驗結果顯示，透過我們的方法，已經高度優化電路中的節點個數可以進一步地降低。
此外，當我們的方法跟ABC 中的resyn2輪流重複執行的話，平均可以減少6\%的電路節點．

關鍵字

布林關係 ； 邏輯最佳化

並列摘要

Boolean Relation (BR) is a many-to-many mapping between two domains. Logic optimization considering BR can exploit the potential flexibility existed in logic networks to minimize the circuits. In this paper, we present a logic optimization approach considering BR. The approach identifies a proper sub-circuit and locally changes its functionality by solving the corresponding BR in the sub-circuit without altering the overall functionality of the circuit. We conducted experiments on a set of MCNC benchmarks that cannot be further optimized by the resyn2 script in ABC. The experimental results show that the node counts of the highly optimized benchmarks can be further reduced. Additionally, when we apply our approach followed by the resyn2 script repeatedly, we can obtain 6\% improvements in average.

並列關鍵字

Boolean relation ； Logic optimization

參考文獻

[1] D. Baneres, J. Cortadella, and M. kishinevsky, “A recursive paradigm to solve boolean relations,” in Proc. DAC, pp. 416-421, June 2004.

[3] R. Brayton and F. Somenzi. “An exact minimizer for Boolean relations,” in Proc. ICCAD, pp. 316-319, 1989.

[4] Y. C. Chen, and C. Y. Wang, “Fast node merging with don’t cares using logic implications,” in Proc. TCAD, vol. 29, no. 11, pp. 1827–1832, Nov. 2010

[5] O. Coudert, J. Madre, and H. Fraisse, “A new viewpoint on two-level logic minimization,” in Proc. DAC, pp. 625-630, June 1993.

[6] A. Ghosh, S. Devadas, and A. Newton, “Heuristic minimization of boolean relations using testing techniques.” in Proc. TCAD, 1990.