一種組合邏輯環轉化方法

邸志雄,史江義,馬佩軍,張 譯,袁 莉,郝 躍,許 釗

(西安電子科技大學寬帶隙半導體國家重點實驗室,陜西西安 710071)

一種組合邏輯環轉化方法

邸志雄,史江義,馬佩軍,張 譯,袁 莉,郝 躍,許 釗

(西安電子科技大學寬帶隙半導體國家重點實驗室,陜西西安 710071)

組合邏輯環能夠減少電路邏輯資源,降低電路功耗,但是其難以被靜態時序分析工具分析和計算,且難以生成功能驗證向量和自動測試圖形向量.針對此問題,提出一種組合邏輯環轉化方法,以解決硬件描述語言以及高級語言邏輯綜合階段所面臨的組合邏輯環拆分問題.不同于采用三值仿真策略的現有文獻,引入了布爾可滿足引擎對組合邏輯環電路進行了表征,使用靜態邏輯蘊涵完成了環形電路的拆分.同時,根據環形電路的形成機理,提出了拆分組合邏輯環結構的規則,用于冗余向量優化以及非環電路的邏輯推理.實驗結果表明,這種算法能夠正確地拆分組合邏輯環結構,且轉化時間短,轉化后的電路規模小.

組合邏輯環;邏輯綜合;SAT引擎;靜態邏輯蘊涵

組合邏輯環能夠減少電路邏輯資源、降低電路功耗等,常被用于低功耗電路中[1].此外,隨著電子系統級設計方法學[2-4]在SoC設計中的大規模應用,高級語言綜合工具[5]也可將高級語言轉化為含有組合邏輯環的門級網表[6-8].但是,組合邏輯環電路存在較多缺陷:(1)難以被靜態時序分析工具分析和計算;(2)驗證向量生成較為復雜,且占用大量內存空間,導致短時間內覆蓋率難以收斂[9-10].因此,亟待提出一種組合邏輯環拆分方法,解決邏輯綜合階段無法避免的拆環問題,以滿足靜態時序分析工具的需求,適應現有SoC設計的自動化流程.

基于以上研究背景,筆者提出一種組合邏輯環轉化方法,期望在邏輯綜合階段轉化組合邏輯環結構,并減小轉化結果的電路資源.筆者以布爾可滿足引擎[11-12]和靜態邏輯蘊涵為基礎,完成了對電路的表示和邏輯功能推理.同時,根據實際應用需求對蘊涵規則進行了定制,使得在計算過程中,能夠不斷地對冗余向量和目標函數進行優化,減少了轉化結果的電路資源.

1 組合邏輯環定義及相關研究

定義1 非邏輯環電路中至少有一個輸出信號不依賴于其他任何輸出信號.非此種情況的電路,則稱為組合邏輯環電路[6].

圖1 邏輯環電路示例

如圖1[13]所示,根據定義1可知,若存在門g5與g1之間的反饋環路,則該電路的任意一個輸出fi均取決于其他輸出,該電路為組合邏輯環電路;若門g5與g1之間不存在反饋,則輸出f1不依賴于其他任何輸出信號,該電路為非環電路.文獻[14]通過資源共享的方法對邏輯環進行拆分,但是只能應用于某些特定的電路.文獻[15]將環形反饋點轉化為多路選擇器和鎖存器,但是鎖存器的引入使得電路由組合電路轉化為時序電路,打亂了電路規定的時序.文獻[6,13]采用三值仿真的方法對組合邏輯環電路進行了識別,并且采用尋找邊界邏輯門控制值的方法完成了對環的拆分.綜合以上現有的研究狀況,都采用了基于三值仿真的思想.隨著環形電路規模不斷增大,仿真向量難以完備地生成.同時,現有文獻未能考慮拆環后盡可能地降低電路邏輯資源數量問題.

2 邏輯環轉化方法

2.1 理論基礎

文獻[16-18]均充分利用了非環電路中的各目標函數都依賴于相同的輸入變量的特點,將其轉化為互相依賴的環形結構.據此,結合定義1,筆者給出了環形結構可拆分的假設.

假設1 若目標函數fi為環形電路C內部的輸出節點,其滿足fi=f(P,F),其中P表示外部輸入信號集合(P={x1,x2,…,xn})或其子集,F表示內部輸出節點集合(F={f1,f2,…,fi-1,fi+1,…,fn})或其子集.若以fi為拆分點,則拆分結果滿足fi=f(P).

定義2 假設一個電路信號的邏輯值只取決于外部輸入向量,則稱之為確定信號,用符號⊥表示.若一個信號的邏輯值不僅取決于電路外部輸入向量,同時還取決于電路內部其他信號,則稱之為不確定信號,用符號⊥表示.

對于環結構,若輸入向量使得其中每個邏輯門均為未確認信號,則環結構中每個輸出節點均無法得到一個確定的蘊涵值,環結構處于振蕩狀態.如圖1所示,若輸入向量為{a=1,b=1,c=1},則該電路無法輸出一個確定信號.反之,若輸入向量使得至少一個門為確認門,則該環結構可輸出確認的蘊涵值[13].據此,對假設1進一步細化,得到假設2.

假設2 若目標函數fi為環形電路C內部的輸出節點,則有:如果(P,pj)→(fi,sj),則fi=f(s0,s1,…,sj,…,sn),0≤j≤n.(P,pj)→(fi,sj),表示輸入向量P等于pj時,目標函數fi蘊涵值為確定信號sj;fi= f(s1,…,sj,…,sn),表示等效非環結構中,目標函數fi為所有確定信號集合(s1,…,sj,…,sn)的運算結果.

為了正確地求出拆環后的目標函數fi,筆者提出了以下運算規則.

定義3 一個子句是由一個或者多個文字構成.如果文字取值為1,則稱為正文字;如果文字取值為0,則稱它為負文字.

基于以上定義和假設2,給出目標函數fi求解所遵循的運算規則.

規則1 若存在(P,pj)→(fi,sj),則

規則2 若存在(P,pj)→(fi,sj),(P,pm)→(fi,sm),(P,pn)→(fi,sn),子句sj滿足子句sm和sn等于構成子句sj的文字,則子句sm和sn為冗余項,可刪去.即若一個子句是滿足的,則它的每個文字都是可滿足的.若子句sj由其余子句構成,則fi=sj.

規則3 若存在(P,pj)→(fi,sj),且,則

規則1用于求解非環結構電路的目標函數.規則2用于去除冗余項,對求解過程進行優化,降低求解過程的數據量和復雜度.規則3用于優化某些特殊結構的電路(某變量所對應的正文字和負文字均會使環結構電路中的目標函數的蘊涵值為一確定值),如文獻[8,16-18].

2.2 算法實現

拆分算法如下.

算法1 函數Find_p(C).

輸入:環形組合邏輯電路C.

輸出:滿足假設2的所有輸入向量P.

算法2 子函數impl_front.

算法3 子函數impl_back.

算法4 函數:Fin d_s(P).

輸出:P引起的目標函數f的蘊涵值s.

筆者提出的拆分算法主要分為3個步驟:(1)如算法1所示,函數Fin d_p(C)提取電路C中滿足假設2的所有輸入向量P;(2)如算法4所示,函數Find_s(P),通過P推導目標函數f的蘊涵值s;(3)根據上述規則,得到最終結果電路.其中函數Fin d_p(C)和Fin d_s(P)分別以布爾可滿足引擎和靜態蘊涵邏輯為基礎,推斷并生成所有滿足假設2的輸入向量P,并且計算由此向量生成的目標函數蘊涵值s.

若fi被選為拆分的目標函數,則在環形結構中fi的邏輯值按先后順序由fi+1…fn和f1…fi-1依次推導得出.因此,函數Find_p(C)的求解過程分別采用兩個循環體遍歷所有目標函數.此外,筆者采用結合前向蘊涵和后向蘊涵的方法,使得有些僅靠正向蘊涵不能被發現的輸入向量也能被發現,實現方法見子函數impl_front和impl_back,如算法2和算法3所示.其中,前向蘊涵和后向蘊涵計算結果可能存在交集,因此,需刪除后向蘊涵計算結果中的交集部分.函數Find_s(P)的實現過程采用了尋求負文字的策略,對環形結構中的函數以及目標函數進行了求解.由于布爾可滿足表達式中任何字句都是可滿足的,若給定文字為負文字,則其他文字必定為正文字.基于以上計算結果,根據2.1節定制的規則,即可得出正確的目標函數.由于筆者所提出的規則刪除了向量P和字句s中的冗余項,因此,相比現有文獻,其計算結果較為精簡,邏輯資源使用率較低.

2.3 實例說明

圖2 組合邏輯環電路實例

對圖2(a)、筆者提出方法的結果及文獻[13]的拆分結果進行了仿真,見圖3.其中后綴為“_1”、“_2”和“_ 3”的信號分別表示目標函數f1、f2和f3;信號名稱為“oc*”表示圖2(a)仿真結果;信號名稱為“os*”表示文獻[13]仿真結果;信號名稱為“noc*”表示筆者提出方法的仿真結果.如圖3所示,筆者提出方法的結果與原環形結構邏輯功能完全一致.而文獻[13]在輸入向量為{a=1,b=1,c=0,d=0,e=0,f=0,g=1}時,目標函數值與拆分前的環形電路不同.此外,筆者僅使用了8個邏輯門,比文獻[13]的降低了50%;同時,筆者僅經過3級邏輯即可獲得目標函數f3,而文獻[13]需經過6級才能求解出正確的目標函數f3.

實例2 見圖1.表1給出了圖1拆分后,各文獻拆分結果所占用的邏輯門數量.通過實例1,證明了筆者在2.1節中提出的假設1和假設2正確.相比現有文獻,筆者提出的方法不僅能夠正確地對邏輯環進行拆分,且減少了拆分結果所占用的邏輯資源.

表1 各方案占用邏輯門數量對比

圖3 拆分前后仿真結果對比

3 實驗結果

筆者提出的算法用C語言編程實現,所用的硬件配置為Intel Pentium Dual E2180 2.00 GHz.所用電路實例均來源于所從事的科研項目和Opencores,且僅包含一個組合邏輯環.為了能夠說明筆者提出的算法的實用性和完備性,采用的電路實例類型覆蓋了數字電路常見類型[21].由表2知,筆者所用的拆分時間小于現有文獻.主要原因在于:(1)文獻[13,22]采用三值仿真的方法,效率較低;(2)筆者引入了布爾可滿足引擎對電路進行了表示,較為簡捷地確定輸入向量是否能夠使目標函數為確定值;同時使用靜態邏輯蘊涵完成了電路的邏輯推理,快速地得到了目標函數的邏輯表達式.由表2知,當電路規模較大時,筆者得出的電路占用資源小于文獻[13]的.其原因在于,筆者根據實際應用需求對蘊涵規則進行了定制,使得在計算過程中,能夠不斷地對冗余向量和目標函數進行優化.

表2 拆分時間及拆分后規模對比

4 總 結

筆者提出一種組合邏輯環轉化方法,以解決硬件描述語言以及高級語言在邏輯綜合階段所面臨的拆分組合邏輯環的問題.相比現有文獻,筆者提出的方法的優點在于:(1)引入了布爾可滿足引擎對電路進行了表征,能夠較為簡捷地確定輸入向量是否能夠使目標函數為確定值;(2)使用靜態邏輯蘊涵完成了電路的邏輯推理,得以快速地得到目標函數的邏輯表達式;(3)根據實際應用需求對蘊涵規則進行了定制,使得在計算過程中,能夠不斷地對冗余向量和目標函數進行優化.實驗結果表明,相比文獻[13],筆者提出的方法的轉化時間約為其72%,且轉化后的電路規模僅為其84%.

[1]Mukherjee B,Dandapat A K.Design of Combinational Circuits by Cyclic Combinational Method for Low Power VLSI[C]//2010 International Symposium on Electronic System Design.Piscataway:IEEE Computer Society,2010:107-112.

[2]Chan T.A Robust Multithreaded HDL/ESL Simulator for Deep Submicron Integrated Circuit Designs[C]//IEEE Asia Pacific Conference on Circuits and Systems.Piscataway:IEEE,2012:416-419.

[3]Huang H Y,Huang C Y,Chen C H.Tile-based GPU Optimizations through ESL Full System Simulation[C]//IEEE International Symposium on Circuits and Systems.Washington:IEEE Computer Society,2012:1327-1330.

[4]Chen Weiwei,D?mer R.An Optimizing Compiler for Out-of-order Parallel ESL Simulation Exploiting Instance Isolation[C]//17th Asia and South Pacific Design Automation Conference.Piscataway:IEEE,2012:461-466.

[5]Yoshikawa Y.A Binding Algorithm in High-level Synthesis for Path Delay Testability[C]//18th Asia and South Pacific Design Automation Conference.Piscataway:IEEE,2013:546-551.

[6]Neiroukh O,Edwards S A,Song Xiaoyu.An Efficient Algorithm for the Analysis of Cyclic Circuits[C]//Proceedings of IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures.Piscataway: IEEE,2006:303-308.

[7]Shiple T R,Berry G,Touati H.Constructive Analysis of Cyclic Circuits[C]//Proceedings of European Design and Test Conference.Los Alamitos:IEEE,1996:328-333.

[8]Riedel M D,Bruck J.The Synthesis of Cyclic Combinational Circuits[C]//Proceedings of IEEE Design Automation Conference.Piscataway:IEEE,2003:163-168.

[9]Agarwal V,Kankani N,Rao R,et al.An Efficient Combinationality Check Technique for the Synthesis of Cyclic Combinational Circuit[C]//Proceedings of the Asia and South Pacific Design Automation Conference.Piscataway: IEEE,2005:212-215.

[10]Raghunathan A,Ashar P,Malik S.Test Generation for Cyclic Combinational Circuits[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1995,14(11):1408-1414.

[11]Larouche M,MasséA B,Goboury S,et al.Solving Equations on Words through Boolean Satisfiability[C]//28th Annual ACM Symposium on Applied Computing.New York:Association for Computing Machinery,2013:104-106. [12]Wang J,Chen J L,Yu C F,et al.A Quantum Method to Test the Satisfiability of Boolean Functions[C]// Proceedings-2012 IEEE 11th International Conference on Solid-State and Integrated Circuit Technology.Piscataway: IEEE,2012:1-5.

[13]Neiroukh O,Edwards S A,Song Xiaoyu.Transforming Cyclic Circuits Into Acyclic Equivalents[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,2008,27(10):1775-1787.

[14]Stok L.False Loops through Resource Sharing[C]//IEEE/ACM International Conference on Computer-Aided Design.Los Alamito:IEEE,1992:345-348.

[15]Gupta A,Selvidge C.Acyclic Modeling of Combinational Loops[C]//Proceedings of the ICCAD-2005:International Conference on Computer-Aided Design.Piscataway:IEEE,2005:343-347.

[16]Riedel M D,Bruck J.Cyclic Boolean Circuits[J].Discrete Applied Mathematics,2012,160(13-14):1877-1900.

[17]Backes J D,Riedel M D.The Synthesis of Cyclic Dependencies with Boolean Satisfiability[J].ACM Transactions on Design Automation of Electronic Systems,2012,17(4):1-24.

[18]Rivest R L.The necessity of feedback in Minimal Monotone Combinational Circuits[J].IEEE Transactions on Computers,1977,26(6):606-607.

[19]Mohanty S P.Shortest String Containing All Permutations[J].Discrete Mathematics,1980,31(1):91-95.

[20]Bouràoncle F.Efficient Chaotic Iteration Strategies with Widenings[C]//International Conference on Formal Methods in Programming and Their Applications.Berlin:Springer,1993:128-141.

[21]潘偉濤,謝元斌,郝躍,等.二同構擴展數字集成電路規律性提取算法[J].西安電子科技大學學報,2009,36(3): 452-462. Pan Weitao,Xie Yuanbin,Hao Yue,et al.Two-isomorphic Extending Algorithm for Regularity Extraction in Digital Integrated Circuits[J].Journal of Xidian University,2009,36(3):452-462.

[22]Edwards S A.Making Cyclic Circuits Acyclic[C]//Proceedings of the 40th Design Automation Conference. Piscataway:IEEE,2003:159-162.

(編輯:郭 華)

Method for transforming cyclic circuits into acyclic equivalents

DI Zhixiong,SHI Jiangyi,MA Peijun,ZHANG Yi,YUAN Li,HAO Yue,XU Zhao
(State Key Lab.of Wide Bandgap Semiconductor Technology Disciplines,Xidian Univ.,Xi’an 710071,China)

The cyclic circuit is capable of reducing the area and power consumption,but it is difficult for tools such as static timing analyzers to analyze and compute.Furthermore,the simulation and DFT for the cyclic circuit are more expensive and complicated.Thus,a method for transforming cyclic circuits into acyclic equivalents based on the SAT(Boolean Satisfiability)is presented in this paper in order to remove the unwanted cycles in the highlevel synthesis process.Different from the available researches,the SAT and static logic implication are introduced in this paper.Meanwhile,by analyzing the structure and mechanism of the cyclic circuits,some novel rules are presented to obtain the acyclic equivalents more precisely and effectively.Experiments are performed in our scientific research projects and the IPs which come from Opencore.And the transforming time and the area are decreased by 28%and 16%.

cyclic circuit;synthesis;Boolean Satisfiability(SAT);static logic implication

TP391.72

A

1001-2400(2014)01-0075-06

10.3969/j.issn.1001-2400.2014.01.014

2013-04-23 < class="emphasis_bold">網絡出版時間:

時間:2013-09-16

中央高校基本科研業務費專項資金資助項目(K5051325010)

邸志雄(1984-),男,西安電子科技大學博士研究生,E-mail:dizhixiong2@126.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20130916.0926.201401.95_010.html