基于遺傳算法的可逆邏輯綜基合于方法及其CUDA并行化實(shí)現(xiàn)

陳麗萍，王子丹，趙曙光，白莉娟

（1.東華大學(xué)圖書館，上海 201620；2.東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海 201620；3.華南理工大學(xué)自動(dòng)化科學(xué)與信息學(xué)院，廣州 510640）

基于遺傳算法的可逆邏輯綜基合于方法及其CUDA并行化實(shí)現(xiàn)

陳麗萍1，王子丹2，趙曙光2，白莉娟3

（1.東華大學(xué)圖書館，上海 201620；2.東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海 201620；3.華南理工大學(xué)自動(dòng)化科學(xué)與信息學(xué)院，廣州 510640）

提出和實(shí)現(xiàn)了一種基于遺傳算法和CUDA（Compute Unified Device Architecture）技術(shù)的可逆邏輯并行綜合方法.其特點(diǎn)是預(yù)先求出并存儲(chǔ)可逆邏輯門的組態(tài)編碼和真值表，通過可逆邏輯門的“定軌級(jí)聯(lián)”構(gòu)成染色體暨可逆邏輯電路，在迭代中按照預(yù)期的邏輯功能和優(yōu)化目標(biāo)等部分并行地評(píng)估適應(yīng)度，再利用選擇、交叉、變異等部分并行化遺傳操作，逐步找到功能正確、性能優(yōu)化的可逆邏輯電路.實(shí)驗(yàn)結(jié)果證明了該方法的可行性、有效性，及其與同類傳統(tǒng)方法相比在運(yùn)算速度、求解能力等方面的顯著改進(jìn).

可逆邏輯電路；綜合；可逆邏輯門；遺傳算法；GPU并行計(jì)算；CUDA

可逆邏輯是研究和實(shí)現(xiàn)量子計(jì)算（機(jī)）、超低功耗集成電路的基礎(chǔ)和關(guān)鍵.可逆邏輯綜合是根據(jù)預(yù)期邏輯功能，按照可逆網(wǎng)絡(luò)無扇出、無反饋等約束條件和限制，利用可逆邏輯門構(gòu)成相應(yīng)的可逆邏輯電路并使之盡可能優(yōu)化，包括門數(shù)最少、量子代價(jià)最小等.目前研究者已提出多種可逆邏輯電路綜合方法.其中一類是先設(shè)法生成電路，而后在不改變電路功能的前提下，通過重組、替換等方式對(duì)其進(jìn)行優(yōu)化.另一類常用方法則將可逆邏輯電路的生成過程與優(yōu)化過程合二為一，基于遺傳算法的可逆邏輯綜合方法便屬于該類方法[1]，且具有靈活、普適等優(yōu)點(diǎn)，但其較大的算法復(fù)雜度限制了其可勝任的電路規(guī)模和復(fù)雜程度.基于GPU的并行計(jì)算架構(gòu)正是為計(jì)算密集型、高強(qiáng)度并行計(jì)算而開發(fā)，特別適用于基于遺傳算法的可逆邏輯綜合這類算法復(fù)雜度較高且可（部分）表達(dá)為并行計(jì)算的問題.NVIDIA公司基于其系列GPU和C語言而研發(fā)推出的CUDA編程模型[2]，為GPU通用計(jì)算提供了便捷的開發(fā)平臺(tái)，使得并行化程序的開發(fā)難度大大減小.本文研究基于遺傳算法的可逆邏輯綜合方法及其基于CUDA平臺(tái)的并行實(shí)現(xiàn)，旨在顯著提高其運(yùn)算速度、求解能力，即能夠勝任的電路規(guī)模和復(fù)雜程度.文中給出的進(jìn)化設(shè)計(jì)實(shí)驗(yàn)結(jié)果證明了該方法的可行性、有效性，以及CUDA并行實(shí)現(xiàn)所帶來的運(yùn)算速度、求解能力等方面的顯著改進(jìn).

1 可逆邏輯電路遺傳算法模型的建立

1.1 可逆邏輯門的編碼

本文不失一般性，以Toffoli門為例來說明可逆邏輯門的編碼原理和方法.其他種類的可逆邏輯門的具體編碼會(huì)有所不同，但編碼原理和方法與之類似.

通用Toffoli門是最常用的可逆邏輯門，用TOF（C；t）表示，設(shè)輸入變量集合為In={x1，x2，…，xn}，控制端集合為C={xi1，xi2，…，xik}，ik?{1，2，…，n}，受控端集合t={xj}，將輸出變量集合映射為：{x1，x2，…，xj-1，xj⊕xi1，xi2，…，xik，xj+1，…，xn}[3-5].

由Toffoli門的性質(zhì)可知，它只能有一個(gè)受控位，但可以有多個(gè)控制位和垃圾位.根據(jù)控制位、垃圾位的位置和數(shù)目的不同，以及受控位位置的不同，Toffoli門有多種不同的組態(tài).對(duì)于N位Toffoli門，受控位的位置有CN1種選擇，控制位和垃圾位的不同排列一共有2N-1種，故N位Toffoli門的組態(tài)總數(shù)為CN1×2N-1.

4位Toffoli門的組態(tài)總數(shù)為C41×24-1=32.為了區(qū)分不同的Toffoli門，須為每種Toffoli門組態(tài)分配一個(gè)不同的編號(hào)，32種組態(tài)共需要5位二進(jìn)制數(shù)進(jìn)行編碼.但在限定可逆邏輯電路所包含的可逆邏輯門的最大個(gè)數(shù)的情況下，考慮電路簡化等的需要，須允許空門（全線直通）的存在并預(yù)留相應(yīng)的編碼.因此，所有的四位Toffoli門加上空門，至少需要C41×24-1+1=33個(gè)編號(hào)，所以改用6位二進(jìn)制編碼，其中編號(hào)000000-011111對(duì)應(yīng)于4位Toffoli門的32種組態(tài)，編號(hào)100000-111111代表空門.4位Toffoli門編碼如圖1所示.

圖1 4位Toffoli門編碼圖Fig.1 Code map of 4-bits toffoli gate

1.2 Toffoli門真值表生成

為了評(píng)估個(gè)體（即可逆邏輯電路）的適應(yīng)度，需要根據(jù)真值表，從外部輸入到最終輸出，逐個(gè)計(jì)算其中所含各可逆邏輯門的輸出值.為生成某種組態(tài)的N位Toffoli門的真值表，須針對(duì)其輸入組合值0～2N-1，逐個(gè)計(jì)算其輸出值，共計(jì)2N次.N位Toffoli門共有CN1×2N-1種組態(tài)，所以共需計(jì)算CN1×2N-1×2N次.當(dāng)量子規(guī)模較小時(shí)，手工完成這些計(jì)算還算方便.但隨著Toffoli門位數(shù)（N）的增加，真值表的規(guī)模顯著增加，再依靠手工計(jì)算既麻煩也容易出錯(cuò)，因此需要編制程序自動(dòng)生成真值表.其思路是，先找出所有的可逆邏輯門組態(tài)，再逐個(gè)計(jì)算各組態(tài)可逆邏輯門的真值表，最后將其寫入文件備用.這樣可以避免重復(fù)計(jì)算，提高適應(yīng)度評(píng)估的速度.

對(duì)于N位Toffoli門，每根量子線都有3種可能狀態(tài)：受控位、控制位或垃圾位.受控位的個(gè)數(shù)只能為1，控制位和垃圾位的個(gè)數(shù)則為0～N-1.本文對(duì)量子線的編碼為：0代表受控位，1代表控制位，2代表垃圾位.例如1012代表一個(gè)4位Toffoli門，4根量子線依次為控制位、受控位、控制位和垃圾位.據(jù)此可尋找所有的Toffoli門組態(tài)，并按上述方式編碼，具體算法為：先不考慮受控位所在的量子線，將其余的量子線（1或者2）進(jìn)行全排列，得到控制位與垃圾位的所有組合；再將受控位（0）插入上述組合中的不同位置，即可得到所有的Toffoli門編碼.

對(duì)于N位Toffoli門，首先不考慮受控位所在量子線，剩下的N-1條量子線都可能為控制位或者垃圾位.對(duì)N-1條量子線進(jìn)行全排列，則有2N-1種排列，其排列算法為：設(shè)定N-1個(gè)數(shù)組，數(shù)組長度為2N-1，第1個(gè)數(shù)組存放的數(shù)字為121212…12121212，第2個(gè)數(shù)組存放11221122…11221122，第3個(gè)數(shù)組存放11112222…11112222，第k個(gè)數(shù)組存放（2k-1個(gè)1）（2k-1個(gè)2）…（2k-1個(gè)1）（2k-1個(gè)2）.然后在每個(gè)數(shù)組中的相同位置取一個(gè)元素，即可得到2N-1個(gè)全排列.全排列完畢后，將0依次插入各個(gè)量子線之間的可能位置，即可得到所有的N位Toffoli門組態(tài)編碼.

在此基礎(chǔ)上計(jì)算Toffoli門各組態(tài)的真值表.根據(jù)Toffoli門的性質(zhì)，只有受控位對(duì)應(yīng)的輸出是變化的，控制位與垃圾位均為直通.受控位對(duì)應(yīng)的輸出值受控制位的影響：若沒有控制位，則受控位對(duì)應(yīng)的輸出值取反；若有控制位，則受控位對(duì)應(yīng)的輸出值等于所有控制位輸入值的乘積與受控位輸入值的異或，即：當(dāng)所有控制位輸入值的乘積為1時(shí)，受控位對(duì)應(yīng)的輸出值將取反；當(dāng)所有控制位輸入值的乘積為0時(shí)，受控位對(duì)應(yīng)的輸出值不變.真值表計(jì)算流程如圖2所示.

圖2 真值表計(jì)算流程圖Fig.2 Flow chart of truth table calculation

通過上述計(jì)算，即可得到所有的Toffoli門組態(tài)對(duì)應(yīng)的真值表，并將其寫入一個(gè)頭文件中，使用時(shí)在C語言程序中直接包含該頭文件即可.同時(shí)為便于查看，每算出一種Toffoli門組態(tài)的真值表后，都將其Toffoli門編碼和對(duì)應(yīng)的真值表寫入另一個(gè)文件中，一種Toffoli門組態(tài)占用其中一行.

1.3 遺傳算法模型的建立

1.3.1 基本元素

基因：一個(gè)基因代表一個(gè)可逆邏輯門，以4位Toffoli門為例，用一個(gè)6位二進(jìn)制數(shù)表示一個(gè)基因，基因種類共64種.

染色體：一個(gè)染色體代表一個(gè)可逆邏輯電路，由若干個(gè)基因組成.

種群：一個(gè)種群代表一個(gè)可逆邏輯電路的集合，由若干個(gè)染色體組成，在種群中可能包含符合條件的可逆邏輯電路.

適應(yīng)度：適應(yīng)度是反應(yīng)染色體優(yōu)劣的度量函數(shù).在本文中代表可逆邏輯電路的功能符合度、優(yōu)化程度的總評(píng)分.

1.3.2 適應(yīng)度評(píng)估

以N位可逆邏輯電路為例，染色體的適應(yīng)度評(píng)分規(guī)則如下.

規(guī)則1：將輸入值迭代加載到染色體的各個(gè)基因（可逆邏輯門），即每個(gè)基因都以其之前（左側(cè)）的基因的輸出作為其輸入（第一個(gè)基因以初始輸入值作為其輸入），根據(jù)相應(yīng)的真值表求出其輸出.最后一個(gè)基因的輸出為電路的最終輸出，若其等于預(yù)期輸出則適應(yīng)度增加1.

規(guī)則2：若按規(guī)則得出的適應(yīng)度小于2N，說明當(dāng)前染色體（電路）的最終輸出與預(yù)期輸出不能完全匹配，即可逆邏輯電路的邏輯功能不完全正確，則以該適應(yīng)度作為最終的染色體適應(yīng)度.

規(guī)則3：在按規(guī)則求出的染色體適應(yīng)度等于2N，即當(dāng)前染色體（電路）的最終輸出與預(yù)期輸出完全匹配的前提下，按以下方法化簡電路并得到最終的染色體適應(yīng)度.

①若染色體中所含空門的個(gè)數(shù)為a，則適應(yīng)度增加a.并且去掉所有空門，繼續(xù)計(jì)算染色體適應(yīng)度.②若存在相鄰且組態(tài)相同的可逆邏輯門，則這2個(gè)可逆邏輯門可以消去.故可將其等價(jià)為2個(gè)空門，將適應(yīng)度增加2，繼續(xù)計(jì)算染色體適應(yīng)度.③不符合以上2種情況時(shí)，以當(dāng)前適應(yīng)度作為最終的染色體適應(yīng)度.評(píng)估流程如圖3所示.

圖3 染色體適應(yīng)度評(píng)估流程Fig.3 Flow chart of chromosome fitness evaluation

2 CUDA并行化實(shí)現(xiàn)

2.1 遺傳算法的并行化模型

對(duì)于計(jì)算能力為1.0的顯卡，CUDA允許每個(gè)線程塊中最多開辟512個(gè)線程；對(duì)于計(jì)算能力為2.0的顯卡，則允許最多開辟1 024個(gè).當(dāng)種群中的個(gè)體（染色體）過多時(shí)，必須啟動(dòng)多個(gè)線程塊同時(shí)運(yùn)行.鑒于各線程塊之間無法進(jìn)行數(shù)據(jù)通信，而遺傳算法中選擇、交叉和變異操作均涉及數(shù)據(jù)交換，本文將種群分為多個(gè)子種群，由線程塊完成子種群的進(jìn)化任務(wù)，而后再將子種群中的最優(yōu)個(gè)體遷移到相鄰的子種群中去，取代其中的最差個(gè)體（只能單方向遷移）.對(duì)于各子種群，每代的最優(yōu)個(gè)體都與上一代的最優(yōu)個(gè)體相比較，若前者的適應(yīng)度低于后者，則以后者（即上一代的最優(yōu)個(gè)體）取代前者，從而避免最優(yōu)個(gè)體在進(jìn)化過程中被淘汰[6].

設(shè)種群大小為512×128=65 536，子種群大小為512.相應(yīng)地在每個(gè)線程塊中開辟512個(gè)線程，共開啟128個(gè)線程塊.每個(gè)線程塊負(fù)責(zé)一個(gè)子種群的進(jìn)化任務(wù).進(jìn)化完成后，由CPU串行代碼完成最優(yōu)染色體的遷移任務(wù).相應(yīng)的種群結(jié)構(gòu)模型如圖4所示.

圖4 種群結(jié)構(gòu)模型Fig.4 Structure model of population

2.2 遺傳算子的并行化實(shí)現(xiàn)

2.2.1 并行選擇算子

本文選用輪盤賭選擇法，其中有2個(gè)步驟可以并行化實(shí)現(xiàn)，具體操作流程如圖5所示.

首先是求適應(yīng)度的總和，可以利用歸約算法并行實(shí)現(xiàn).當(dāng)子種群規(guī)模為512時(shí)，其串行實(shí)現(xiàn)需要執(zhí)行511次加法操作，花費(fèi)時(shí)間為511次加法運(yùn)算的時(shí)間總和.若利用并行算法實(shí)現(xiàn)，只需9次循環(huán)求解即可，因此理論上，其計(jì)算速度是串行實(shí)現(xiàn)的511/9倍.現(xiàn)舉例說明規(guī)約求和的具體過程：設(shè)c[512]為GPU內(nèi)的共享內(nèi)存，保存著每個(gè)個(gè)體的適應(yīng)度.按需開啟多個(gè)線程進(jìn)行并行計(jì)算，第1次開啟256個(gè)線程，在第n（1≤n≤256）個(gè)線程中實(shí)現(xiàn)c[n-1]=c[n-1]+c[n-1+256]，第1次求和結(jié)果存放在c[n-1]中；第2次開啟128個(gè)線程，在第n（1≤n≤128）個(gè)線程中實(shí)現(xiàn)c[n-1]= c[n-1]+c[n-1+128]，第二次求和結(jié)果存放在c[n-1]中；依此類推，第m次開啟256/2m-1個(gè)線程，在第n（1≤n≤256/2m-1）個(gè)線程中實(shí)現(xiàn)c[n-1]=c[n-1]+ c[n-1+256/2m-1]，第m次求和結(jié)果存放在c[n-1]中；最終m=9時(shí)開啟1個(gè)線程，計(jì)算c[0]=c[0]+c[1]，即得到存放于c[0]中的適應(yīng)度總和.

圖5 并行化選擇操作流程圖Fig.5 Flow chart of parallel selecting operation

其次是求個(gè)體的相對(duì)適應(yīng)度.對(duì)于含512個(gè)個(gè)體的子種群，開啟512個(gè)線程同時(shí)運(yùn)行，因而僅需一次運(yùn)算即可得到全體個(gè)體的相對(duì)適應(yīng)度.從理論上講，其計(jì)算速度是串行計(jì)算的512倍.

2.2.2 并行交叉算子

交叉操作的CUDA并行實(shí)現(xiàn)的具體步驟是：首先利用隨機(jī)數(shù)，將子種群中的512個(gè)染色體打亂順序；然后產(chǎn)生隨機(jī)數(shù)并與交叉率Pc相比較，以判斷是否需要進(jìn)行交叉操作.當(dāng)需要時(shí)，在線程塊中開啟256個(gè)線程分別進(jìn)行交叉操作.讓第1個(gè)染色體和第256個(gè)染色體交叉，第2個(gè)染色體和第257個(gè)染色體交叉，依此類推，一次即可完成整個(gè)種群的交叉操作.理論上，其速度是串行化實(shí)現(xiàn)的256倍.具體操作流程如圖6.

2.2.3 并行變異算子

變異是對(duì)種群中的染色體的某些基因的基因值作變動(dòng)的操作.本文采用二進(jìn)制編碼和對(duì)應(yīng)的二進(jìn)制變異.在具體的CUDA并行實(shí)現(xiàn)上，利用多個(gè)線程同時(shí)、分別完成一個(gè)個(gè)體的變異操作.首先產(chǎn)生隨機(jī)數(shù)并與變異概率Pm做比較，若其值較小則表示某個(gè)基因的某一位達(dá)到了變異條件，因而立即對(duì)該位取反；否則保持不變.對(duì)于規(guī)模為512的子種群，開啟512個(gè)線程同時(shí)進(jìn)行上述變異操作.理論上，其執(zhí)行速度是串行實(shí)現(xiàn)的512倍.具體流程如圖7所示.

圖6 并行化交叉操作流程圖Fig.6 Flow chart of parallel cross operation

圖7 并行化變異操作流程圖Fig.7 Flow chart of parallel mutation operation

3 實(shí)驗(yàn)結(jié)果及分析

本文利用CUDA C語言，在VS2010平臺(tái)上編程實(shí)現(xiàn)了上述算法，并針對(duì)一組可逆邏輯測(cè)試基準(zhǔn)問題進(jìn)行了實(shí)驗(yàn).下面給出二個(gè)實(shí)驗(yàn)結(jié)果并稍加分析，其中，種群規(guī)模均選定為128×512=65 536，染色體長度均選定為20個(gè)基因（即電路中最多包含20個(gè)可逆邏輯門）.所用顯卡為NVIDIA公司的GeForce GT610，其核心頻率為810 MHz，顯存容量為1 024 MB，顯存頻率為1 800 MHz，顯存帶寬為14.4 Gbit/s.

3.1 量子電路4_49設(shè)計(jì)實(shí)驗(yàn)

該電路為四輸入四輸出，故選用4位Toffoli門，其基因長度為6位，相應(yīng)的染色體長度為120.預(yù)先按照2.3節(jié)所述方法，生成4位Toffoli門的真值表及其組態(tài)編號(hào).編譯并運(yùn)行程序后，得到的最優(yōu)染色體為：011101，101100，011111，111101，101011，000011，000 001，011110，000101，000101，111100，010100，001010，011001，101111，000001，100100，011111，010110，001110.對(duì)應(yīng)的十進(jìn)制數(shù)為：29，44，31，61，43，3，1，30，5，5，60，20，10，25，47，1，36，31，22，14.將其中編號(hào)32以上的空門消去，化簡為29，31，3，1，30，5，5，20，10，25，1，31，22，14.再將其中組態(tài)相同且相鄰的門消去，化簡為29，31，3，1，30，20，10，25，1，31，22，14.根據(jù)圖1所示的4位Toffoli門編碼圖，轉(zhuǎn)換得到的可逆邏輯電路如圖8所示.

圖8 4_49量子電路設(shè)計(jì)結(jié)果Fig.8 4_49 quantum circuit designed

3.2 Decod24-enable設(shè)計(jì)實(shí)驗(yàn)

該電路為六輸入六輸出，故選用6位Toffoli門，如2.2節(jié)所述，6位Toffoli門的受控位位置有C61種變化，控制位和垃圾位的位置共有26-1種變化，故6位Toffoli門的組態(tài)總數(shù)為C61×26-1=192，其基因長度需選為8，相應(yīng)的染色體長度為160位（20門）.

預(yù)先按照2.3節(jié)所述方法，生成六位Toffoli門的真值表及其組態(tài)編號(hào).編譯并運(yùn)行程序后，得到的最優(yōu)染色體為：01110101，11000111，00100110，01010110，00000110，00001111，00001111，00010101，01010110，01101011，11010001，00011011，01100110，00011011，00010101，00010101，00110011，01110101，01001011，01101011.對(duì)應(yīng)的十進(jìn)制數(shù)為：117，199，38，86，6，15，15，21，86，107，209，27，102，27，21，21，51，117，75，107.將其中編號(hào)192以上的空門消去后，得到117，38，86，6，15，15，21，86，107，27，102，27，21，21，51，117，75，107.再將其中組態(tài)相同且相鄰的Toffoli門消去，得到117，38，86，6，21，86，107，27，102，27，51，117，75，107.其對(duì)應(yīng)的Toffoli門組態(tài)分別為210212，112201，212021，112210，212120，212021，120122，221220，110221，221220，211202，210212，121 022，120122.因?yàn)槿缜八觯?、1、2分別代表受控位、控制位和垃圾位，據(jù)此還原各Toffoli門的組態(tài)，最終得到的可逆邏輯電路如圖9所示.

圖9 Decod24-enable量子電路設(shè)計(jì)結(jié)果Fig.9 Decod24-enable quantum circuit designed

3.3 CUDA并行實(shí)現(xiàn)效率分析

在實(shí)驗(yàn)中，針對(duì)4位Tottoli門構(gòu)成電路開發(fā)了CPU串行實(shí)現(xiàn)程序，該程序完全由C語言實(shí)現(xiàn)，僅在CPU上運(yùn)行，其功能和參數(shù)與CUDA并行實(shí)現(xiàn)程序完全一致.針對(duì)相同的種群規(guī)模，分別運(yùn)行CPU串行程序和CUDA并行程序并記錄它們的單次進(jìn)化任務(wù)所用時(shí)間，如圖10所示.

從圖10可以看出，CUDA并行化實(shí)現(xiàn)的執(zhí)行效率大大優(yōu)于CPU串行實(shí)現(xiàn)，且其優(yōu)勢(shì)隨著種群規(guī)模的增大而愈加顯著，可以達(dá)到上百倍的加速比.因此對(duì)于相同的進(jìn)化次數(shù)，CUDA并行實(shí)現(xiàn)所花費(fèi)的時(shí)間顯著減少，所以有可能完成較大規(guī)模、較復(fù)雜可逆邏輯電路的進(jìn)化設(shè)計(jì).

圖10 CPU串化實(shí)現(xiàn)與CUDA并行實(shí)現(xiàn)的運(yùn)行效率對(duì)比圖Fig.10 Efficiency comparison between CPU realization and CUDA parallel realization

4 結(jié)束語

本文研究了一種基于遺傳算法的可逆邏輯綜合方法，并利用CUDA技術(shù)對(duì)其進(jìn)行了并行化改造和編程實(shí)現(xiàn)，獲得了基于遺傳算法和CUDA技術(shù)的可逆邏輯并行綜合算法和程序.進(jìn)化設(shè)計(jì)實(shí)驗(yàn)結(jié)果表明該算法具有可行性和有效性，且求解的速度和能力均有顯著改進(jìn).從原理上講該算法適用于各種可逆邏輯門及其構(gòu)成的電路，因而具有一定的參考和推廣價(jià)值.

[1]張舒，褚艷麗.GPU高性能運(yùn)算之CUDA[M].北京：北京水利水電出版社，2009.

[2] 管致錦.可逆邏輯綜合[M].北京：科學(xué)出版社，2011.

[3]MASLOV D，DUECK G W，MILLER D M.Toffoli network synthesis with templates[J].IEEE Transactions on CAD，2005，24（6）：807-817.

[4]MASLOV D，DUECK G W，MILLER D M.Techiques for the synthesis of reversible Toffoli networks[J].ACM Trans Des Autom Electron Sys，2007，68（12）：42-46.

[5]MILLER D M，MASLOV D，DUECK G G.A transformation based algorithm for reversible logic synthesis[C]//Design Autom Conf.2003：318-323.

[6]譚彩鳳，馬安國，邢座程.基于CUDA平臺(tái)的遺傳算法并行實(shí)現(xiàn)研究[J].計(jì)算機(jī)工程與科學(xué)，2009，31（A1）：68-72.

Reversible logic synthesis method based on genetic algorithm and its

CUDA parallel implementation CHEN Li-ping1，WANG Zi-dan2，ZHAO Shu-guang2，BAI Li-juan3
（1.Library，Donghua University，Shanghai 201620，China；2.College of Information Science and Technology，Donghua University，Shanghai 201620，China；3.School of Automation Science and Engineering，South China University of Technology，Guangzhou 510640，China）

A parallel synthesis method for reversible logic based on the genetic algorithm and the CUDA technique is discussed.It features the configuration encodings and truth tables prepared and stored in advance for reversible logic gates，chromosomes comprised of encodings of reversible logic gates contained in individuals（reversible logic circuits），partly parallel fitness evaluation according to logic expected logic functions and optimization objectives，and partly parallel genetic operations such as selection，crossover，and mutation.With these steps assembled together and executed iteratively，functionally correct and performance optimal reversible logic circuits can be probably obtained.The experimental results show feasibility and effectiveness of the method proposed，and its advantages over existing non-parallel methods in operation speed and solving ability.

reversible logic circuits；synthesis；reversible logic gates；genetic algorithm；GPU parallel computing；CUDA

TP312.8；TP331.1

A

1671-024X（2014）03-0069-06

2013-12-2

國家自然科學(xué)基金面上項(xiàng)目(61271114)；上海市教委科研創(chuàng)新重點(diǎn)項(xiàng)目(14ZZ068)

陳麗萍（1965—），女，碩士，工程師.

趙曙光（1965—），男，教授.E-mail：sgzhao@dhu.edu.cn