基于KFDD與進(jìn)化算法的可逆電路優(yōu)化算法

卜登立，劉 歡，劉宇安

(1.井岡山大學(xué) 電子與信息工程學(xué)院，江西 吉安 343009；2.流域生態(tài)與地理環(huán)境監(jiān)測(cè)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，江西 吉安 343009)

0 引 言

可逆計(jì)算是信息無損的計(jì)算模式，在量子計(jì)算等新興技術(shù)領(lǐng)域有著重要應(yīng)用。隨著芯片制造工藝的發(fā)展，單個(gè)晶體管的尺寸接近原子規(guī)模，已經(jīng)無法再通過縮小晶體管尺寸進(jìn)一步降低功耗[1]，再加上芯片復(fù)雜度的上升，功耗問題已經(jīng)成為計(jì)算機(jī)芯片向更小更快方向發(fā)展的障礙[2]。信息無損的可逆計(jì)算可以實(shí)現(xiàn)理論上的近似零功耗[3]，因此，越來越多的研究者也將可逆電路作為低功耗設(shè)計(jì)的一種替代方案[2,4]。

決策圖(decision diagram, DD)作為函數(shù)高層次、層次化的表示模型，已被廣泛應(yīng)用于可逆電路的綜合。用于可逆電路綜合的DD有二元決策圖(binary decision diagram, BDD)[5]、正Davio決策圖(positive Davio decision diagram, PDD)[6]和Kronecker功能決策圖(Kronecker functional decision diagram, KFDD)[7-8]，其中，BDD僅對(duì)函數(shù)的輸入變量進(jìn)行香農(nóng)分解，PDD僅對(duì)輸入變量進(jìn)行正Davio分解，而KFDD則對(duì)輸入變量分別進(jìn)行香農(nóng)分解和正、負(fù)Davio分解，因此，BDD和PDD可以看作是特殊類型的KFDD。借助DD進(jìn)行可逆電路綜合屬于結(jié)構(gòu)化的綜合方法[9]，將DD結(jié)點(diǎn)視為構(gòu)造塊，根據(jù)所建立的可逆門庫(kù)將結(jié)點(diǎn)函數(shù)綜合為可逆子電路，并根據(jù)邏輯關(guān)系進(jìn)行可逆子電路的級(jí)聯(lián)，從而實(shí)現(xiàn)可逆電路的綜合[5]。因此，DD的結(jié)點(diǎn)數(shù)將影響由之綜合所得可逆電路的成本。輸入變量的順序以及輸入變量的分解類型對(duì)KFDD的結(jié)點(diǎn)數(shù)均有影響[10]，不同的輸入變量順序和不同的輸入變量分解類型有可能得到不同大小的KFDD，也會(huì)得到具有不同量子成本和量子位數(shù)的可逆電路?；贙FDD的可逆電路優(yōu)化方法借助Sifting技術(shù)來改變輸入變量的順序和分解類型進(jìn)行可逆電路的量子成本優(yōu)化或者量子位數(shù)優(yōu)化[11]，僅搜索了解空間中的部分區(qū)域，難以保證得到全局最優(yōu)解。因此，為在借助KFDD進(jìn)行可逆電路綜合時(shí)能夠得到全局最優(yōu)解，需要使用全局優(yōu)化算法進(jìn)行可逆電路優(yōu)化。

本文在可逆電路的KFDD綜合方法基礎(chǔ)之上，針對(duì)KFDD的輸入變量分解類型和輸入變量順序問題，設(shè)計(jì)基于進(jìn)化算法的可逆電路優(yōu)化算法。該算法通過優(yōu)化KFDD輸入變量的分解類型以及順序來實(shí)現(xiàn)可逆電路的優(yōu)化，分別采用離散值和整型值編碼輸入變量的分解類型和順序，利用遺傳算法進(jìn)行搜索，并設(shè)計(jì)策略來避免過早收斂問題。給出了算法描述，并使用一組RevLib函數(shù)[12]對(duì)算法進(jìn)行了驗(yàn)證。

1 可逆電路的KFDD綜合方法

對(duì)于n輸入變量的函數(shù)f(xi|1≤i≤n)，其KFDD是由依次對(duì)函數(shù)f的n個(gè)輸入變量分別實(shí)施的香農(nóng)分解和正、負(fù)Davio分解得到[13]

(1)

KFDD使用終端結(jié)點(diǎn)表示常量，非終端結(jié)點(diǎn)表示變量，稱之為變量結(jié)點(diǎn)，每個(gè)變量結(jié)點(diǎn)有2個(gè)子結(jié)點(diǎn)，左子結(jié)點(diǎn)Vl和右子結(jié)點(diǎn)Vh，Vl,Vh∈V。補(bǔ)邊的采用有助于降低KFDD的復(fù)雜度，而標(biāo)準(zhǔn)形表示的KFDD僅允許連接Vk與Vh的邊Ek,h∈E為補(bǔ)邊[13]?，F(xiàn)假設(shè)結(jié)點(diǎn)Vk是xi變量結(jié)點(diǎn)，其結(jié)點(diǎn)函數(shù)為Fk，Vl的結(jié)點(diǎn)函數(shù)為Fl，Vh的結(jié)點(diǎn)函數(shù)為Fh，那么根據(jù)變量xi的分解類型di，以及Ek,h是否為補(bǔ)邊，F(xiàn)k可以由Fl和Fh來描述，如表1所示。

表1 Vk結(jié)點(diǎn)函數(shù)描述Tab.1 Node function of Vk

可逆電路的KFDD綜合方法通過深度優(yōu)先遍歷G，逐結(jié)點(diǎn)綜合，根據(jù)Vk的結(jié)點(diǎn)函數(shù)將Vk綜合為可逆子電路，再級(jí)聯(lián)所有的子電路實(shí)現(xiàn)可逆電路的綜合[14]。借助KFDD進(jìn)行可逆電路綜合的算法如算法1所示。

算法1可逆電路綜合算法。

1)QC←0，QB←n；

2)深度優(yōu)先方式訪問G；

3)對(duì)每一個(gè)Vk∈V，根據(jù)Fk從NCT門庫(kù)中選取可逆門，并通過適當(dāng)增加Lk條輔助線將之級(jí)聯(lián)為可逆子電路，統(tǒng)計(jì)量子成本和量子位數(shù)：QC←QC+QCk，QB←QB+Lk；

4)級(jí)聯(lián)所有的子電路從而構(gòu)建實(shí)現(xiàn)函數(shù)f的可逆電路。

2 基于進(jìn)化算法的可逆電路優(yōu)化算法

輸入變量的順序以及分解類型會(huì)影響KFDD的結(jié)點(diǎn)數(shù)量，從而影響由算法1綜合所得可逆電路的量子成本和量子位數(shù)。因此，可逆電路成本優(yōu)化問題可以轉(zhuǎn)化為輸入變量順序以及輸入變量分解類型優(yōu)化問題。

函數(shù)有n個(gè)輸入變量，每個(gè)輸入變量的分解類型有3種，因此，可逆電路成本優(yōu)化的解空間大小為3n×n!。本文在大小為3n×n!的解空間內(nèi)進(jìn)行全局搜索，搜索成本最小的可逆電路。

2.1 進(jìn)化算法模型

遺傳算法具有與問題域無關(guān)、并行潛質(zhì)以及搜索過程簡(jiǎn)單等特點(diǎn)[16]，因此，本文基于遺傳算法模型設(shè)計(jì)進(jìn)化算法。

2.1.1 適應(yīng)度函數(shù)

可逆電路的成本包括量子成本QC和量子位數(shù)QB，本文在進(jìn)行可逆電路優(yōu)化時(shí)將量子成本作為主要優(yōu)化目標(biāo)，而量子位數(shù)則作為次要優(yōu)化目標(biāo)，即先比較2個(gè)電路解Si與Sj的量子成本QC(Si)與QC(Sj)，如果量子成本相同，再比較2個(gè)解的量子位數(shù)QB(Si)與QB(Sj)。本文可逆電路優(yōu)化所采用的成本函數(shù)為

(2)

可逆電路優(yōu)化是成本最小化問題，因此，本文進(jìn)化算法所采用的適應(yīng)度函數(shù)如(2)式所示。

2.1.2 遺傳編碼

個(gè)體的遺傳編碼分為2個(gè)部分：D=[d,v]，其中d=[d1,d2,…,dn]為輸入變量分解類型列表，采用離散值編碼di∈{0,1,2}，分別表示輸入變量的分解類型為香農(nóng)分解和正、負(fù)Davio分解；v=[v1,v2,…,vn]為輸入變量順序，vj∈[1,n]，采用整型值編碼，變量順序?qū)儆谥脫Q碼。遺傳編碼中d和v的編碼長(zhǎng)度都為n，遺傳編碼的總長(zhǎng)度為2×n。

2.1.3 遺傳算子

遺傳算子包括選擇、交叉、變異和再生。選擇采用錦標(biāo)賽選擇策略，假設(shè)錦標(biāo)賽規(guī)模為T：在種群中隨機(jī)抽取T個(gè)個(gè)體，然后選擇其中的最優(yōu)個(gè)體作為后續(xù)交叉運(yùn)算的父?jìng)€(gè)體。

為遺傳編碼中的分解類型列表d和變量順序v設(shè)計(jì)不同類型的交叉運(yùn)算。對(duì)于d，采用單點(diǎn)交叉：隨機(jī)生成一個(gè)位置c1(1≤c1≤n)，對(duì)2個(gè)父?jìng)€(gè)體中的d進(jìn)行交叉；對(duì)于v，為保證實(shí)施交叉運(yùn)算后能夠得到有效的變量順序，采用基于順序的交叉(order-based crossover)[17]：隨機(jī)生成2個(gè)位置c1和c2(1≤c1,c2≤n)，將父?jìng)€(gè)體1和2遺傳編碼的v中位于c1和c2之間的基因分別復(fù)制到子個(gè)體1和2遺傳編碼的v，而子個(gè)體1和2遺傳編碼的v中其余的基因則分別通過掃描父?jìng)€(gè)體2和1遺傳編碼的v來進(jìn)行填充，正向掃描和逆向掃描會(huì)得到不同的結(jié)果，如圖1所示。

圖1 基于順序的交叉運(yùn)算舉例Fig.1 Example for order-based crossover

變異運(yùn)算則采用交換變異[18]：隨機(jī)生成2個(gè)不同位置c1和c2(1≤c1,c2≤n)，將位于c1和c2的基因交換?；蚓幋a中的d和v獨(dú)立實(shí)施交換變異運(yùn)算，圖2給出了基因編碼中的v在c1=1和c2=3時(shí)的交換變異運(yùn)算。

圖2 交換變異運(yùn)算舉例Fig.2 Example for swap mutation

再生采用穩(wěn)態(tài)再生策略，經(jīng)選擇、交叉、變異運(yùn)算后生成新種群，并將上一代種群的最佳個(gè)體與新種群的最差個(gè)體進(jìn)行競(jìng)爭(zhēng)替換，然后將新種群作為下一代種群。

2.1.4 進(jìn)化算法描述

根據(jù)以上所述的適應(yīng)度函數(shù)、遺傳編碼以及選擇、交叉、變異和再生運(yùn)算，設(shè)計(jì)如算法2所示的進(jìn)化算法，算法2僅給出了一次進(jìn)化過程。其中，P表示種群，Pi和Qi均表示個(gè)體，Pi.D表示個(gè)體Pi的遺傳編碼，Pi.QC和Pi.QB分別表示個(gè)體Pi所對(duì)應(yīng)可逆電路的量子成本和量子位數(shù)。

算法2進(jìn)化算法。

輸入：上一代種群P={Pi|1≤i≤|P|}。

輸出：下一代種群P。

2)for(i←1;i≤|P|;i←i+2) {

3)k←tour_select(P);l←tour_select(P);

4)cross(Pk.D,Pl.D,Qi.D,Qi+1.D);

5)mut(Qi.D);mut(Qi+1.D);

6)eval(Qi.D);eval(Qi+1.D);

8) if(Po.QC

(Po.QC=Qw.QC∧Po.QB

9)Qw←Po;

10)P←;

算法2中的|P|表示種群P中的個(gè)體數(shù)，為個(gè)體集合，作為進(jìn)化過程中的新種群。tour_select為錦標(biāo)賽選擇函數(shù)，需要進(jìn)行2次錦標(biāo)賽選擇，得到種群P中2個(gè)個(gè)體的索引k和l；cross為交叉函數(shù)，遺傳編碼D中的d和v分別以交叉概率pc實(shí)施單點(diǎn)交叉和基于順序的交叉運(yùn)算，在實(shí)施v的交叉運(yùn)算時(shí)，分別以0.5的概率進(jìn)行正向掃描和逆向掃描；mut為變異函數(shù)，編碼D中的d和v分別以變異概率pm實(shí)施交換變異運(yùn)算。eval為成本計(jì)算函數(shù)，根據(jù)Qi.D中的輸入變量分解類型列表d和輸入變量順序v改變KFDD圖G中輸入變量的分解類型和輸入變量順序，然后運(yùn)行算法1計(jì)算可逆電路的量子成本QC和量子位數(shù)QB，關(guān)于如何改變G中輸入變量的順序以及輸入變量的分解類型請(qǐng)參閱文[13]。算法2的第8)至10)步則進(jìn)行種群再生，第8)和9)步使用上一代種群P中的最優(yōu)個(gè)體Po與新種群中的最差個(gè)體Qw進(jìn)行競(jìng)爭(zhēng)，第10)步則形成下一代種群P。錦標(biāo)賽選擇、種群中最優(yōu)個(gè)體和最差個(gè)體的判定都采用了如(2)式所示的判定方法。

雖然遺傳編碼D中的d和v作為2個(gè)部分獨(dú)立進(jìn)行交叉和變異運(yùn)算，但在計(jì)算個(gè)體對(duì)應(yīng)可逆電路的成本時(shí)卻同時(shí)使用這兩部分，因此，所設(shè)計(jì)的進(jìn)化算法同時(shí)解決了輸入變量順序問題和輸入變量分解類型問題。

2.2 可逆電路優(yōu)化算法描述

種群多樣性的缺失是導(dǎo)致遺傳算法過早收斂的重要原因。為維持種群多樣性，在搜索過程的前期階段，采用小生境方法，劃分多個(gè)子群，每個(gè)子群搜索解空間中的不同區(qū)域，擴(kuò)大搜索空間。但是隨著子群搜索的進(jìn)行，各個(gè)子群內(nèi)的個(gè)體逐漸趨同，容易導(dǎo)致算法陷入局部極小。因此，為避免算法陷入局部極小，在搜索過程的后期階段，將多個(gè)子群合并為整體種群，利用整體種群進(jìn)行集中搜索。子群的搜索以及整體種群的搜索均采用如算法2所示的進(jìn)化算法模型。本文基于KFDD和進(jìn)化算法的可逆電路優(yōu)化算法如算法3所示。

算法3可逆電路優(yōu)化算法。

1)讀取函數(shù)，轉(zhuǎn)換為KFDD圖G；

2)初始化算法參數(shù)，包括子群數(shù)s，子群規(guī)模Ns，錦標(biāo)賽規(guī)模T，交叉概率pc和變異概率pm，子群搜索最大迭代次數(shù)t1，整體種群搜索最大迭代次數(shù)t2；

3)迭代次數(shù)變量t←0，隨機(jī)生成s個(gè)子群{Pi|1≤i≤s}，每個(gè)子群Pi包含Ns個(gè)個(gè)體，并計(jì)算每個(gè)個(gè)體所對(duì)應(yīng)可逆電路的量子成本和量子位數(shù)；

4)對(duì)每一個(gè)子群Pi，運(yùn)行算法2；t←t+1；

5)如果t≤t1，轉(zhuǎn)步驟4)；否則轉(zhuǎn)步驟6)；

6)P←∪{Pi|1≤i≤s}；t←0；

7)對(duì)整體種群P運(yùn)行算法2；t←t+1；

8)如果t≤t2，轉(zhuǎn)步驟7)；否則轉(zhuǎn)步驟9)；

9)得到種群最優(yōu)Po∈P；

10)根據(jù)Po.D中的d和v改變G中輸入變量的分解類型以及輸入變量的順序；

11)運(yùn)行算法1將G綜合為可逆電路。

算法3的第3)-5)步為子群搜索階段，第6)-8)步為整體種群搜索階段，整體種群P的種群規(guī)模為s×Ns。算法3已在可逆邏輯綜合工具RevKit[11]中實(shí)現(xiàn)，關(guān)于第1)步中如何由函數(shù)構(gòu)建KFDD以及第10)步的詳情請(qǐng)參考文獻(xiàn)[11，13]。

3 算法驗(yàn)證及結(jié)果分析

算法3采用C++語言實(shí)現(xiàn)，在Linux操作系統(tǒng)下使用g++編譯器編譯。算法參數(shù)通過對(duì)一組RevLib函數(shù)[12]進(jìn)行可逆電路優(yōu)化并對(duì)結(jié)果進(jìn)行評(píng)價(jià)確定：子群數(shù)s=6，子群規(guī)模Ns=10，錦標(biāo)賽規(guī)模T=5，交叉概率pc=0.6，變異概率pm=0.4，子群搜索最大迭代次數(shù)t1=100，整體種群搜索最大迭代次數(shù)t2=50。

為驗(yàn)證算法3，在配置為Intel Core i3-2350M CPU 6GB RAM的個(gè)人計(jì)算機(jī)上對(duì)14個(gè)RevLib函數(shù)進(jìn)行可逆電路優(yōu)化，并與RevKit[11]中使用Sifting技術(shù)的基于KFDD的可逆電路優(yōu)化算法(稱之為RevKit_KFDD算法)的結(jié)果進(jìn)行比較，結(jié)果如表2所示，其中,“I/O”表示函數(shù)的“輸入數(shù)/輸出數(shù)”。

由于算法3具有一定隨機(jī)性，因此，對(duì)每個(gè)函數(shù)都使用算法3進(jìn)行50次優(yōu)化，并統(tǒng)計(jì)50次優(yōu)化所得結(jié)果的最小值和平均值，如表2中的第5和6列所示的QB的最小值和平均值，以及第7和8列所示的QC的最小值和平均值，同時(shí)統(tǒng)計(jì)50次算法3運(yùn)行所需CPU時(shí)間的平均值，如表2第9列所示，時(shí)間的單位是秒。而表2中的“Imp”則表示對(duì)每個(gè)函數(shù)，相對(duì)于算法RevKit_KFDD的結(jié)果，算法3的“平均”結(jié)果分別將量子位數(shù)和量子成本減少的百分比。

表2 可逆電路優(yōu)化結(jié)果Tab.2 Optimization results for reversible circuits

由表2可以看出，對(duì)于這些函數(shù)，算法3結(jié)果QB的均值都非常接近于QB的最小值，QC的均值也比較接近于QC的最小值。將算法3結(jié)果QB和QC的均值分別與RevKit_KFDD算法結(jié)果的QB和QC進(jìn)行比較可以看出，對(duì)于所有函數(shù)而言，算法3均能夠減少量子成本，最大減少了51.05%(函數(shù)radd_193)，最小減少了4.03%(函數(shù)hwb8_64)；對(duì)于大部分函數(shù)而言，算法3能夠減少量子位數(shù)，只有3個(gè)函數(shù)，算法3結(jié)果的量子位數(shù)有所增加，這是因?yàn)樗惴?將量子成本作為主要優(yōu)化目標(biāo)，量子位數(shù)作為次要優(yōu)化目標(biāo)，而“基于KFDD進(jìn)行可逆電路綜合，可逆電路在量子位數(shù)和量子成本之間存在著折中”。從表2最后一行的平均結(jié)果來看，相對(duì)于RevKit_KFDD算法，算法3將量子位數(shù)減少了6.21%，量子成本減少了12.67%，這驗(yàn)證了算法3的有效性。

表2也給出了算法3對(duì)每一個(gè)函數(shù)優(yōu)化50次所需時(shí)間的平均值。對(duì)于大部分函數(shù)，算法3所需時(shí)間均小于10 s，有2個(gè)函數(shù)：clip_124和hwb8_64，盡管其輸入變量數(shù)小于10，但是算法3運(yùn)行花費(fèi)的時(shí)間卻相對(duì)較多，這是因?yàn)檫@2個(gè)函數(shù)在優(yōu)化過程中算法3所搜索到的KFDD的結(jié)點(diǎn)數(shù)相對(duì)較多，導(dǎo)致在優(yōu)化過程中改變KFDD中輸入變量的順序和分解類型所花費(fèi)的時(shí)間較長(zhǎng)。

為進(jìn)一步對(duì)算法3進(jìn)行評(píng)價(jià)，統(tǒng)計(jì)了算法3對(duì)每一個(gè)函數(shù)優(yōu)化50次所得結(jié)果的變異系數(shù)(coefficients of variation, CV)，CV=結(jié)果標(biāo)準(zhǔn)差×100/結(jié)果平均值，用來評(píng)價(jià)算法結(jié)果的穩(wěn)定性[19]。結(jié)果如圖3所示。

圖3 算法3結(jié)果的變異系數(shù)Fig.3 CV of results obtained by algorithm 3

由圖3可以看出，對(duì)于表2中的函數(shù)，算法3結(jié)果的變異系數(shù)均較小，QC結(jié)果的最大變異系數(shù)僅為5.95%(函數(shù)pcler8_190)，QB結(jié)果的最大變異系數(shù)僅為3.8%(函數(shù)pcler8_190)，這說明算法3有較好的結(jié)果穩(wěn)定性。

圖4給出了算法3優(yōu)化函數(shù)clip_124時(shí)的收斂曲線。

圖4 算法3優(yōu)化函數(shù)clip_124的收斂曲線Fig.4 Convergence curve of algorithm 3 when optimizing clip_124

圖4中的第1～100次迭代是子群搜索階段，第101～150次迭代是整體種群搜索階段。由圖4可以看出，由于算法3在前期階段利用多個(gè)子群同時(shí)搜索解空間中的不同區(qū)域，因此，算法3具有較快的收斂速度。在子群搜索階段，算法3在第33次迭代搜索到量子成本為431(量子位數(shù)為58)的局部最優(yōu)解，第66次迭代搜索到量子成本為431、量子位數(shù)為57的局部最優(yōu)解，并且到子群搜索階段結(jié)束時(shí)(第100次迭代)，尋優(yōu)結(jié)果的量子成本和量子位數(shù)一直沒有得到改善，算法3陷入了局部極小。當(dāng)算法3進(jìn)入整體種群搜索階段，在整體種群搜索的第6次迭代(圖4中的第106次迭代)搜索到量子成本得到改善的解(量子成本為423，量子位數(shù)為58)，并且在整體種群搜索的第14次迭代，算法3開始收斂于量子成本為417、量子位數(shù)為58的最優(yōu)解。這驗(yàn)證了算法3所采用的“在搜索的前期階段利用多個(gè)子群進(jìn)行搜索，擴(kuò)大搜索空間，而在搜索的后期階段利用整體種群進(jìn)行集中搜索”策略的有效性。

可見，算法3具有較強(qiáng)的全局尋優(yōu)能力，并且有較好的結(jié)果穩(wěn)定性，能夠降低由KFDD綜合所得可逆電路的量子成本和量子位數(shù)。

文獻(xiàn)[20]設(shè)計(jì)了一種結(jié)合Reed-Muller邏輯與DD模型進(jìn)行可逆電路優(yōu)化的Reed-Muller decision diagram synthesis，RMDDS算法。該算法通過對(duì)Reed-Muller邏輯進(jìn)行分解并借助BDD和KFDD進(jìn)行可逆電路優(yōu)化，同時(shí)，在NCT門庫(kù)的基礎(chǔ)之上結(jié)合基本Peres門來改善可逆電路的量子成本。使用RMDDS算法對(duì)表2中的函數(shù)進(jìn)行了可逆電路的量子成本優(yōu)化，結(jié)果如表3所示。其中，“Imp”表示對(duì)每個(gè)函數(shù)相對(duì)于RMDDS算法的結(jié)果，表2中算法3的“平均”結(jié)果分別將量子位數(shù)和量子成本減少的百分比。

從表2和表3中的量子位數(shù)角度來看，有7個(gè)函數(shù)算法3結(jié)果的量子位數(shù)優(yōu)于RMDDS，另外7個(gè)函數(shù)RMDDS結(jié)果的量子位數(shù)優(yōu)于算法3，從平均角度來看，RMDDS結(jié)果的量子位數(shù)略占優(yōu)勢(shì)。但從量子成本角度來看，在這14個(gè)函數(shù)中，僅有2個(gè)函數(shù)算法3的結(jié)果劣于RMDDS的結(jié)果，對(duì)于其他函數(shù)，算法3的結(jié)果均優(yōu)于RMDDS的結(jié)果。從表3最后一行的平均角度來看，與RMDDS相比，算法3盡管使量子位數(shù)增加了2.70%，但卻將量子成本降低了16.34%。從時(shí)間角度來看，對(duì)于絕大多數(shù)電路，算法3均有較高的時(shí)間效率，從時(shí)間的平均角度看，與RMDDS相比，算法3的時(shí)間效率提高了一個(gè)數(shù)量級(jí)。

表3 RMDDS算法結(jié)果Tab.3 Results of RMDDS algorithm

綜上所述，本文所設(shè)計(jì)的基于進(jìn)化算法的可逆電路優(yōu)化算法具有較強(qiáng)的全局尋優(yōu)能力，能夠降低可逆電路的量子成本。

4 結(jié)束語

可逆邏輯在量子計(jì)算以及低功耗電路設(shè)計(jì)等領(lǐng)域中的重要應(yīng)用，使得可逆電路的綜合與優(yōu)化得到了廣泛關(guān)注，降低可逆電路的成本則有助于進(jìn)一步推動(dòng)可逆電路的應(yīng)用。本文在可逆電路的KFDD綜合方法基礎(chǔ)之上，通過優(yōu)化KFDD的輸入變量順序和輸入變量分解類型來進(jìn)行可逆電路的成本優(yōu)化，并設(shè)計(jì)了基于進(jìn)化算法的可逆電路優(yōu)化算法。使用一組RevLib函數(shù)對(duì)所設(shè)計(jì)算法進(jìn)行了驗(yàn)證，結(jié)果表明，所設(shè)計(jì)算法具有較強(qiáng)的全局尋優(yōu)能力，并有較好的結(jié)果穩(wěn)定性，能夠降低可逆電路的量子成本。

參考文獻(xiàn)：

[1] MACK C. Themultiple lives of Moore's law [EB/OL]. [2015-12-20]. http://spectrum.ieee.org/semiconductors/processors/the-multiple-lives-of-moores-law.

[2] CAMPOS-AGUILLN C O, CELIS-CORDOVA R, HNNINEN I K, et al. A mini-MIPS microprocessor for adiabatic computing[C]//IEEE. Proceedings of the IEEE International Conference on Rebooting Computing. San Diego, CA: IEEE Press, 2016: 1-7.

[3] BENNETT C H. Logical reversibility of computation[J]. IBM Journal of Research and Development, 1973, 17(6): 525-532.

[4] MORRISON M, RANGANATHAN N. Synthesis of dual-rail adiabatic logic for low power security applications[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(7): 975-988.

[5] WILLE R, DRECHSLER R. BDD-based synthesis of reversible logic for large functions[C]//ACM. Proceedings of the 46th ACM/IEEE Design Automation Conference. San Francisco, CA: ACM Press, 2009: 270-275.

[6] PANG Y, YAN Y, LIN J, et al. An efficient method to synthesize reversible logic by using positive Davio decision diagrams[J]. Circuits, Systems, and Signal Processing, 2014, 33(10): 3107-3121.

[7] SOEKEN M, WILLE R, DRECHSLER R. Hierarchical synthesis of reversible circuits using positive and negative Davio decomposition[C]//IEEE. Proceedings of the 5th IEEE International Design and Test Workshop. Abu Dhabi: IEEE Press, 2010: 143-148.

[8] 王友仁, 沈先坤, 周影輝. 基于KFDD的可逆邏輯電路綜合設(shè)計(jì)方法[J]. 電子學(xué)報(bào), 2014, 42(5): 1025-1029.

WANG Youren, SHEN Xiankun, ZHOU Yinghui. Synthesis design method of reversible logic circuit based on Kronecker functional decision diagram[J]. Acta Electronic Sinica, 2014, 42(5): 1025-1029.

[9] ZULEHNERA, WILLE R. Skipping embedding in the design of reversible circuits[C]//IEEE. Proceedings of the IEEE 47th International Symposium on Multiple-Valued Logic. Novi Sad: IEEE Press, 2017: 173-178.

[10] BECKERT B, DRECHSLER R, THEOBALD M. OKFDDs versus OBDDs and OFDDs[C]//Springer. Proceedings of the 22nd International Colloquium on Automata, Languages and Programming. London, UK: Springer Press, 1995: 475-486.

[11] SOEKEN M, FREHSE S, WILLE R, et al. RevKit: an open source toolkit for the design of reversible circuits[J]. Lecture Notes in Computer Science, 2012(7165): 64-76.

[12] WILLE R, GRO?E D, TEUBER L, et al. RevLib: an online resource for reversible functions and reversible circuits[C]//IEEE. Proceedings of the 38th IEEE International Symposium on Multiple-Valued Logic. Dallas, TX: IEEE Press, 2008: 220-225.

[13] DRECHSLER R, BECKER B. Ordered Kronecker functional decision diagrams - a data structure for representation and manipulation of Boolean functions[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(10): 965-973.

[14] SCHONBORN E, DATTA K, WILLE R, et al. Optimizing DD-based synthesis of reversible circuits using negative control lines[C]//IEEE. Proceedings of the 17th IEEE International Symposium on Design and Diagnostics of Electronic Circuits & Systems. Warsaw: IEEE Press, 2014: 129-134.

[15] NIELSEN M A, CHUANG I L. Quantum computation and quantum information[M]. 10th anniversary edition. New York: Cambridge University Press, 2010.

[16] 袁琴琴,呂林濤. 基于改進(jìn)蟻群算法與遺傳算法組合的網(wǎng)絡(luò)入侵檢測(cè)[J].重慶郵電大學(xué)學(xué)報(bào): 自然科學(xué)版, 2017, 29(1): 84-89.

YUAN Qinqin,LV Lintao. Network intrusion detection method based on combination of improved ant colony optimization and genetic algorithm[J]. Journal of Chongqing University of Post and Telecommunications: Natural Science Edition, 2017, 29(1): 84-89.

[17] BURKE E K, KENDALL G. Search methodologies: introductory tutorials in optimization and decision support technique[M].New York: Springer Press, 2005.

[18] FINDER A, DRECHSLER R. An evolutionary algorithm for optimization of pseudo Kronecker expressions[C]//IEEE. Proceedings of the 40th IEEE International Symposium on Multiple-Valued Logic, Barcelona: IEEE Press, 2010: 150-155.

[19] 卜登立. 基于SADPSO的MPRM最小化算法[J]. 重慶郵電大學(xué)學(xué)報(bào): 自然科學(xué)版, 2016, 28(2): 226-232.

BU Dengli.MPRM minimization algorithm based on SADPSO[J]. Journal of Chongqing University of Post and Telecommunications: Natural Science Edition, 2016, 28(2): 226-232.

[20] LIN C C, JHA N K. RMDDS: Reed-Muller decision diagram synthesis of reversible logic circuits[J]. ACM Journal on Emerging Technologies in Computing Systems, 2014, 10(2):14:1-14:25.