一種組合邏輯環(huán)轉(zhuǎn)化方法

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

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

一種組合邏輯環(huán)轉(zhuǎn)化方法

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

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

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

組合邏輯環(huán);邏輯綜合;SAT引擎;靜態(tài)邏輯蘊涵

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

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

1 組合邏輯環(huán)定義及相關(guān)研究

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

圖1 邏輯環(huán)電路示例

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

2 邏輯環(huán)轉(zhuǎn)化方法

2.1 理論基礎(chǔ)

文獻[16-18]均充分利用了非環(huán)電路中的各目標函數(shù)都依賴于相同的輸入變量的特點,將其轉(zhuǎn)化為互相依賴的環(huán)形結(jié)構(gòu).據(jù)此,結(jié)合定義1,筆者給出了環(huán)形結(jié)構(gòu)可拆分的假設(shè).

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

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

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

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

為了正確地求出拆環(huán)后的目標函數(shù)fi,筆者提出了以下運算規(guī)則.

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

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

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

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

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

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

2.2 算法實現(xiàn)

拆分算法如下.

算法1 函數(shù)Find_p(C).

輸入:環(huán)形組合邏輯電路C.

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

算法2 子函數(shù)impl_front.

算法3 子函數(shù)impl_back.

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

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

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

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

2.3 實例說明

圖2 組合邏輯環(huán)電路實例

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

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

表1 各方案占用邏輯門數(shù)量對比

圖3 拆分前后仿真結(jié)果對比

3 實驗結(jié)果

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

表2 拆分時間及拆分后規(guī)模對比

4 總 結(jié)

筆者提出一種組合邏輯環(huán)轉(zhuǎn)化方法,以解決硬件描述語言以及高級語言在邏輯綜合階段所面臨的拆分組合邏輯環(huán)的問題.相比現(xiàn)有文獻,筆者提出的方法的優(yōu)點在于:(1)引入了布爾可滿足引擎對電路進行了表征,能夠較為簡捷地確定輸入向量是否能夠使目標函數(shù)為確定值;(2)使用靜態(tài)邏輯蘊涵完成了電路的邏輯推理,得以快速地得到目標函數(shù)的邏輯表達式;(3)根據(jù)實際應(yīng)用需求對蘊涵規(guī)則進行了定制,使得在計算過程中,能夠不斷地對冗余向量和目標函數(shù)進行優(yōu)化.實驗結(jié)果表明,相比文獻[13],筆者提出的方法的轉(zhuǎn)化時間約為其72%,且轉(zhuǎn)化后的電路規(guī)模僅為其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]潘偉濤,謝元斌,郝躍,等.二同構(gòu)擴展數(shù)字集成電路規(guī)律性提取算法[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">網(wǎng)絡(luò)出版時間:

時間:2013-09-16

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

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

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