以迴圈基礎進行動態邏輯合成之最佳化

Cycle-based Logic Optomization in Dynamic Logic Synthesis

陳欣杰(Shin-Chieh Chen)

指導教授 ： 王俊堯

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

摘要

骨牌式電路(domino logic)是目前最常見的動態邏輯設計，它可以實現高速且低使用空間之電路•但是骨牌式電路因為其天生的構造限制，必須沒有反向邏輯閘(inverter gates)，這代表了骨牌式電路的設計必須移除所有的反向邏輯閘•然而，移除反向邏輯閘意味著部分之邏輯區塊必須要被複製(logic duplication)以同時提供正、反向的信號，這會造成電路空間成本的大幅增加，因此設法複製最少的邏輯區塊是很重要的課題。
在以往的方法中最簡單的方式是以狄摩根定理(De Morgan's law)來進行移除反向邏輯閘，並且進行必要的複製；而後Ruchir Puri提出了設定輸出狀態(output phase assignment)之理論，它可以進一步降低了複製邏輯閘的數量。
我們的研究是以迴圈的角度來觀察反向邏輯閘為何不能利用狄摩根定理來移除，並且進一步把整個邏輯電路轉換成一個簡單的抽象圖形。並且利用找出圖形中所有擁有奇數個反向邏輯閘之簡單迴圈，來公式化這個問題，我們的作法能夠完全涵蓋設定輸出狀態理論，且較為容易理解。最後我們將每個這種迴圈當成一個二元條款(boolean clause)，並且將如何符合這些二元條款視為一個加權含蓋問題(weighted covering problem)。然後我們利用啟發式(heuristic)的方法來找出複製最少的邏輯區塊之較佳解。
實驗結果顯示使用我們的複製方法比利用狄摩根定理推演並進行必要複製的方法減少約14%的複製成本，也較Ruchir Puri利用設定輸出狀態(output phase assignment)方式之結果為佳。

關鍵字

邏輯複製 ； 動態電路 ； 骨牌式電路

並列摘要

Domino logic is one of the most popular dynamic circuit configurations for implementing high-performance and small-area logic designs. Since domino logic is inherently non-inverting, it presents a fundamental constraint of implementing logic functions without any intermediate inversions. Removal of inter-mediate inverters requires logic duplication for generating both the negative and positive signal phases, which results in significant area overhead. Therefore, it is important topic to minimize logic duplication for making a circuit inverter-free.
In previous work, it is simply duplicating all the multi-fanouts nets on the way of pushing all the inverters to the primary inputs by De Morgan’s law called non-optimized logic duplication. Then, Ruchir Puri proposed the area overhead can be substantially reduced by selecting an optimal output phase assignment.
In this paper, we present a previously unaddressed cycle-based logic optimization for minimum area duplication in dynamic logic synthesis. We formulated this problem as finding all the simple cycles with odd inverters in an undirected graph and then there is a constraint formula is made for representing these cycles. Satisfying this formula could be taken as an unate weighted covering problem. In addition, this paper also presents a heuristic algorithm for solving the unate boolean constraint formula.
Our experiment results show that in average there is about 14% improvement from the non-optimized logic duplication; moreover, they are also better than the results using the output phase assignment.

並列關鍵字

Logic Duplication ； Dynamic Circuit ； Domino Circuit

參考文獻

[1] R. H. Krambeck, C. M. Lee, and H. S. Law, “High Speed Compact Circuits with CMOS.” IEEE Journal of Solid State Cicuits, SC-17(3):614-619, June 1982.

[2] S. M. Reddy, “Complete Test Sets for Logic Functions.” IEEE Transaction on Computers, C-22(11):1016-1020, Nov 1973.

[3] Ruchir Puri, Andrew Bjorksten, and Thomas E. Rosser, “Logic optimization by output phase assignment in dynamic logic synthesis.” Proc. IEEE/ACM ICCAD, Jan 1997.

[4] Min Zhao and Sapatnekar, S.S, “Dual-monotonic domino gate mapping and optimal output phaseassignment of domino logic.” Proc. ISCAS, 309-312 vol.2, 2000.

[5] James C. Tiernan, “An efficient search algorithm to find the elementary circuits of a graph”, Communications of the ACM, v.13 n.12, p.722-726, Dec. 1970