周影輝,王友仁
(南京航空航天大學 自動化學院,江蘇 南京 210016)
隨著集成電路規(guī)模的增加,其能耗問題已經愈發(fā)引起研究者的注意。Bennett[1]最早證明能耗來源于計算過程中的不可逆操作,傳統(tǒng)數字電路由于不可逆計算導致信息的擦除導致能量的消耗,Landauer[2]指出,每一個信息位的丟失對應KT*Ln2 焦耳的熱量產生,式中K 是波爾茲曼常量,T 是絕對溫度。雖然單個信息位散失能量很少,但對于超大規(guī)模集成電路,功耗不能忽略。如果組成電路的所有門均能夠執(zhí)行可逆計算,即不存在信息位的擦除,理論上可以實現集成電路的零損耗。目前廣泛研究的量子運算是一種具體的可逆計算,即能夠從根本上解決集成電路功耗問題。
量子計算可以由可逆邏輯電路實現,現有的研究對可逆邏輯電路研究很多,但大都集中在可逆組合邏輯電路方面[3-5],時序邏輯電路方面研究的比較少[6-8],文獻[6]首次提出了可逆觸發(fā)器的設計方法,但沒有考慮電路的性能指標。文獻[7]提出了可逆主從觸發(fā)器的設計方法。文獻[8]設計了對數式移位寄存器設計方法,但是僅能適用于此類寄存器?,F在沒有通用的設計方法可以適用不同種類的可逆時序邏輯電路設計。
針對可逆邏輯電路現有的問題,提出了一種方法,將傳統(tǒng)的不可逆時序邏輯電路轉化為可逆時序邏輯電路。并且以典型的可逆時序邏輯電路中的脈沖分配器的設計方為例,設計了可逆脈沖分配器,通過將不可逆脈沖分配器中的基本邏輯門替換成可逆邏輯門,達到將不可逆時序電路轉換為可逆時序電路的目的。
量子計算機中,信息的基本單元是量子比特,即量子位,信息的基本操作元件是可逆邏輯門。量子比特是信息的載體,量子比特的信息經可逆邏輯門操作處理后,最后得到計算結果。
定義1 組成可逆邏輯電路的基本單元必須是可逆邏輯門,并且還需要滿足以下約束條件:1)電路中無扇入扇出操作,2)輸入與輸出位數相等,3)對應電路真值表滿足一一映射。
定義2 任何一個較復雜的可逆邏輯門均是由或基本可逆邏輯門構成。量子代價用來衡量一個量可逆邏輯電路的復雜性,用實現一個可逆邏輯電路所需要的或者 基本可逆邏輯門的數量表示,不管內部結構如何,一個基本可逆邏輯門的量子損耗是1。
定義3 在可逆邏輯電路中,除期望輸出外的剩余輸出稱為垃圾位。垃圾位是無用輸出位,也是電路能耗產生的根源。因此垃圾位數量的多少是評價可逆邏輯電路的一個最重要的性能指標。當添加垃圾位輸出后,為使量子可逆邏輯電路的輸入輸出位數相等,需在輸入端添加一定數量的常量輸入,常量輸入的位數也影響到可逆邏輯電路綜合的量子代價,常量輸入取0 或1。
常用可逆邏輯門如圖1 所示。
圖1 常用可逆邏輯門Fig.1 Common reversible logic gates
Feynman 門(FG 門)有兩個輸入量子比特,分別是控制量子比特和目標量子比特。它所實現的功能為當控制量子比特為0 時,目標量子比特不變;而當控制量子比特為1 時,目標量子比特將反轉。FG 門的線路如圖1(a)所示。其中,P、Q為FG 門的兩個輸出量子比特,FG 門能夠實現線路的復制功能。當B=0 時,可得到兩個相同的輸出A。因此,FG 門能夠實現可逆邏輯量子比特的復制。
F2G 門又叫做Feynman Double gate)F2G),有3個輸入比特,能完成輸入比特的兩位復制。
FRG 門,又稱受控交換門,是一種三輸入輸出的可逆邏輯門,如圖所示。當控制端為0 時,FRG為三輸入輸出的直通門,即P=A、Q=B、R=C。當控制端A 輸入信號為1 時,P=A,Q=C,R=B。
TG 門是最常用的多比特可逆邏輯門,輸入位由兩個控制比特位和一個被控比特來構建符合特定要求的可逆邏輯電路。此外,門可以通過修改控制位數量,構成具有不同數量控制位TG 門系列,以此來構建符合特定要求的可逆邏輯電路。
在傳統(tǒng)的不可逆時序電路中,使用的邏輯門是不可逆的。要設計可逆邏輯電路,就要使用可逆邏輯門進行構造。本文將傳統(tǒng)的不可逆時序電路中的邏輯門替換成可逆邏輯門,不改變原有電路的設計原理,從而將不可逆邏輯電路轉化為可逆邏輯電路。
傳統(tǒng)的可逆脈沖分配器主要是由計數器和相應的譯碼器組成,基于扭環(huán)計數器的脈沖分配器如圖2 所示。其中計數器又由觸發(fā)器級聯而成,所以要將其中的觸發(fā)器和基本的與門轉換成相應的可逆邏輯門,另外,由于可逆邏輯電路不能有扇入或者扇出,所以圖2 中的扇入扇出信號要用可逆邏輯門對信號進行復制。
首先要將傳統(tǒng)的D 觸發(fā)器轉化可逆D 觸發(fā)器??紤]到量子代價和量子門數的影響,設計了由圖1 中的FRG 門、F2G門構成的可逆D 觸發(fā)器,具體結構如圖3 所示。
由圖3(a)所示,當C 輸入為0 時,輸出Q 保持不變,當C輸入為1 時,輸出Q 和D 的信號相同。將圖3(a)中的電路封裝成圖3(b)所示的模塊。本文設計的可逆D 觸發(fā)器(圖3)的性能指標和文獻[7]中設計的可逆D 觸發(fā)器比較如表1 所示。
圖2 基于扭環(huán)計數器的脈沖發(fā)生器Fig.2 Pulse distributor based on twisted ring counter
圖3 可逆D 觸發(fā)器Fig.3 Reversible D flip-flop
表1 D觸發(fā)器性能指標比較Tab.1 The performance comparison of reversible D flip-flop designed by ours and others methods
由表1 可以看出本文設計的量子可逆D 觸發(fā)器比文獻[8]所用的量子門數減少了5個,量子代價減少了40,垃圾位減少了6個。在設計多位脈沖分配器時,量子門數、量子代價和垃圾位會有明顯降低。
圖2 所示的計數器是扭環(huán)計數器,根據設計原則,將計數器中的觸發(fā)器替換成可逆D 觸發(fā)器,從而設計出可逆扭環(huán)計數器。如圖4 所示。
圖4 可逆扭環(huán)計數器Fig.4 Reversible twisted ring counter
可逆扭環(huán)計數器和譯碼器共同組成脈沖分配器,譯碼器主要由與門構成,而可逆邏輯電路中沒有相應的與門,必須用常用可逆邏輯門構造,Toffoli 門可以完成此功能,兩輸入的與門要三輸入的Toffoli 門構成。另外,不可逆脈沖分配器的扇入扇出需要進行重新設計,每個扇入或者扇出的節(jié)點要用Feynman 門對信號進行復制。
結合圖2 所示的可逆扭環(huán)計數器和圖4 所示的可逆扭環(huán)計數器,構建的量子可逆脈沖分配器如圖5 所示。
圖5 可逆脈沖分配器Fig.5 Reversible pulse distributor
由圖5 可以看出,本文所設計的量子可逆脈沖分配器所用量子門數為32,量子代價為96,垃圾位24。
可逆脈沖分配器的結構在實驗中用VHDL 進行描述封裝,代碼通過Xilinx ISE9.1i 下載到Spartan-6 LX FPGA 芯片上進行運行仿真,目標器件為XC6SLX9??赡婷}沖分配器的仿真結果如圖6 所示。
圖6 可逆脈沖分配器仿真結果Fig.6 Simulation of reversible pulse distributor
由圖6 可以看出,本文設計的可逆脈沖分配器可以實現8 節(jié)拍脈沖輸出功能,并且無冒險與競爭現象。
目前已經提出了多種可逆邏輯電路的物理構建方法,如利用低功耗CMOS 晶體管構建可逆邏輯門,而利用電子波導Y-分支開關)Y-Branch Switch YBS)構建可逆邏輯門可以用更少的能量改變開關狀態(tài),它的打開和關閉是通過改變電子傳輸兩個方向中的一個,而不是切換當前的開關,在正常情況下,YBS 的一次開關動作大約散失0.6meV 的熱量,一個信息位丟失所損耗的能量為KT*Ln2,大約等價為18meV,利用YBS 作為基本單元構建可逆邏輯門會更加節(jié)能[9]。如圖7 所示,為利用YBS 作為基本單元構建的FG 門和Toffoli 門,由于所有的可逆邏輯電路都能有Toffoli 門實現,所以可逆脈沖分配器可以由圖7 所示的可逆邏輯門設計物理電路。
文中提出了一種可逆時序電路的設計方法,以不可逆脈沖分配器為例,將其轉化為可逆脈沖分配器,分析了所設計的可逆脈沖發(fā)生器的有關性能指標并對其功能進行了仿真。另外提出了可逆脈沖分配器的物理實現方法[10]。結果表明,設計的可逆脈沖分配器能完成脈沖輸出的功能。此方法還可以用于其它可逆時序邏輯電路的設計。
圖7 基于YBS 的可逆邏輯門實現Fig.7 The implementation of reversible logic gate based on YBS
[1]Laudauer R.Irreversibility and heat generation of the computing process[J].IBM Journal of Research and Development,1961,5(3):183-219.
[2]Bennett C H.Notes on Landauer’s principle,reversible computation and Maxwell’s demon[J].Studies In History and Philosophy of Science Part B:Studies In History and Philosophy of Modern Physics,2003,34(3):501-510.
[3]管致錦,秦小麟,陶濤,等.可逆門網絡的表示與級聯[J].電子學報,2010,38(10):2370-2376.GUAN Zhi-jin,QIN Xiao-lin,TAO Tao,et al.Representation and cascade for reversible gate network[J].Acta Electronica Sinica,2010,38(10):2370-2376.
[4]呂洪君,樂亮,韓良順,等.基于遺傳算法的量子可逆邏輯電路綜合方法研究[J].量子電子學報,2011,28(5):596-604.LV Hong-jun,YUE Liang,HAN Liang-shun,et al.Quantum reversible logic circuits synthesis based on genetic algorithm[J].Chinese Journal of Quantum Electronics,2011,28(5):596-604.
[5]Soeken M,Wille R,Hilken C,et al.Synthesis of reversible circuits with minimal lines for large functions [C].17th Asia and South Pacific Design Automation Conference,Sydney,Australia,2012:85-92.
[6]Rice J E.A new look at reversible memory elements[C]//IEEE International Symposium on Circuits and Systems,Island of Kos,Greece,2006:1243-1246
[7]Thapliyal H,Srinivas M B.A beginning in the reversible logic synthesis of sequential circuits[C]//Proc.of Military and Aerospace Programmable Logic Devices International Conference,Washington D.C.,2005,summision,1012.
[8]Rajmohan V,Ranganathan V.Design of counters using reversible logic [C]//2011 3rd International Conference on Electronics Computer Technology(ICECT),Kanyakumari,India,2011:138-142.
[9]CHUANG Min-lun,WANG Chun-yao.Synthesis of reversible sequential elements[J].ACM Journal on Emerging Technologies in Computing Systems,2008,3(4):1-19.
[10]張偉,陳鋒,馬軍強,等.軌/姿控發(fā)動機脈沖后效沖量快速算法的研究及應用[J].火箭推進,2012(1):51-56.ZHANG Wei,CHEN Feng,MA Jun-qiang,et al.Research and application of fast algorithm for pulse residual impulse of divert and attitude control engine[J].Journal of Rocket Propulsion,2012(1):51-56.