時序邏輯電路在片進(jìn)化設(shè)計與實現(xiàn)

婁建安，李川濤，常小龍，滿夢華

(1．軍械工程學(xué)院 電氣工程系，河北 石家莊050003;2．軍械工程學(xué)院 靜電與電磁防護(hù)研究所，河北 石家莊050003)

0 引言

演化硬件技術(shù)可根據(jù)環(huán)境變化改變電路內(nèi)部結(jié)構(gòu)，從而實現(xiàn)電子電路的結(jié)構(gòu)自組織、環(huán)境自適應(yīng)以及故障自修復(fù)功能［1］． 全世界有許多機(jī)構(gòu)進(jìn)行了演化硬件的研究，并且成果豐碩，特別是姚新、Higuichi 等學(xué)者提出了基于FPGA 結(jié)構(gòu)可重配置特性的EHW 具體實現(xiàn)方法，將研究進(jìn)程大大加速［2］．之后，演化硬件在理論研究和工程應(yīng)用方面均發(fā)展迅猛．其中，在電路容錯運行和自修復(fù)方面，滿夢華等［3］利用演化硬件技術(shù)實現(xiàn)了邏輯門單元在線自修復(fù);在圖像處理方面，王瓏等［4］將演化硬件技術(shù)應(yīng)用到了圖像加密技術(shù)中;在信號傳輸和處理方面，F(xiàn)aleoner 等［5］使用內(nèi)部型可進(jìn)化硬件完成了高速數(shù)據(jù)線的信號完整性檢查．

1 時序邏輯電路演化模型設(shè)計

電路演化設(shè)計的關(guān)鍵在于設(shè)計結(jié)構(gòu)可重構(gòu)的電路演化模型，利用演化算法不斷變化電路結(jié)構(gòu)從而實現(xiàn)目標(biāo)功能．但目前此類研究多以加法器、乘法器等組合電路為對象，而時序電路的研究相對較少［6］．其主要原因在于時序電路內(nèi)部存在反饋連接，使得電路的染色體編碼更為復(fù)雜，而且，驗證測試評估困難，進(jìn)化成功率較低，仿真速度緩慢．有鑒于此，筆者專門設(shè)計并實現(xiàn)了一種通用的時序電路演化模型．

1．1 硬件演化平臺構(gòu)建

硬件進(jìn)化平臺主要包括基于Microblaze 軟核的CPU 設(shè)計、可重構(gòu)數(shù)字電路網(wǎng)絡(luò)模型設(shè)計兩部分內(nèi)容．Microblaze 軟核的主要功能是運行GA 算法，進(jìn)行VRC(Virtual Reconfigurable Circuit)矩陣演化． Microblaze 軟核可以根據(jù)實際需要予以裁剪，其GPIO 的數(shù)目不限，對VRC 的配置都是全并行的．如串口、DMA 控制器、CAN 控制器等諸多外部設(shè)備，均可十分方便地通過選擇而增刪．而并行配置方式最大的優(yōu)點就是VRC 配置速度快，不僅可以提高演化速度，而且設(shè)計簡單;它的缺點是演化電路的規(guī)模不易直接擴(kuò)充，如圖1 所示．

1．2 時序邏輯電路的全向連接演化模型

圖1 中的VRC 演化模型主要由兩部分組成，即邏輯組合電路和D 觸發(fā)器組．邏輯組合電路是由m×n 個PE(Programmable Element)單元構(gòu)成的陣列，PE 單元的運算結(jié)果只能前饋輸出到下一列．D 觸發(fā)器組的輸出既可以前饋也可以反饋，于是整個電路就可以成為一個全向連接的網(wǎng)絡(luò)． 實驗證明這種全向連接的方法對于提高電路的演化速度和成功率都有非常大的幫助．

PE 單元是VRC 演化模型的基本元素． 其結(jié)構(gòu)設(shè)計對電路的演化的成功率和演化算法的收斂速度都有很大的影響，其結(jié)構(gòu)如圖2 所示．

PE 中包含AND、OR、NOT 以及XOR 等基本單元，以便構(gòu)成各種復(fù)雜的組合電路功能．同時，PE 還添加了NAND、NOR 以及NXOR 等邏輯門，一旦用到時可以直接調(diào)用而不必通過基本單元的合成，以提高電路的演化速度，但是用不到時會降低FPGA 內(nèi)部邏輯資源的使用率．矩陣中每個PE單元相互連接構(gòu)成功能電路時，只會選擇上述其中一種邏輯門作為自己的運算功能．

圖中的chose_3_8_1 為8 選1 多路選擇器，從上到下其功能依次為輸入選擇、輸出選擇和功能選擇．DataInHigh 為該層單元的一個8 輸入數(shù)據(jù)．這8 個數(shù)據(jù)可能來自VRC 的輸入，也可以為上層PE 的輸出，或者為前層或者后層保存電路的輸出．HighDataInSel 端口為輸入選擇信號，選擇該PE 的輸入為DataInHigh(7:0)中的某一個．Functionsel(2:0)為功能選擇端口，選擇使用某一個邏輯門，端口signal_out 為該PE 的輸出．

用PE 可以組成一個可編程功能的矩陣． 該矩陣中存在大量冗余且可編程的資源，所以實現(xiàn)同樣功能的目標(biāo)電路可以有多種結(jié)構(gòu)形式． 當(dāng)有個別或相對較少的單元受損之后，通過重新配置電路結(jié)構(gòu)，完全可能避開損傷部分，從而使得該矩陣仍然可以繼續(xù)正常工作，即具有了容錯運行和自修復(fù)的功能．

時序邏輯電路內(nèi)進(jìn)化模型中必須有電路保存的部分，其結(jié)構(gòu)如圖3 所示．

圖3 電路保存部分Fig．3 Circuit’s temporary part

元件Chose4_16_1 是16 選1 的多路選擇器，控制信號為4 位，通過該元件選擇D 觸發(fā)器所要保存的數(shù)據(jù)．端口clk 和clr 分別為時鐘信號和D觸發(fā)器清零信號，在同步時序組合邏輯電路中，所有D 觸發(fā)器的clk 和clr 均連接在一起．D_out 的輸出既可當(dāng)做整個VRC 的輸出，也可做下層PE單元的輸入或者上層PE 單元的輸入，即保存部分輸出，使其既可反饋，也可向前傳輸．

2 演化模型在ISE 開發(fā)環(huán)境中的實現(xiàn)

在本文的VRC 模型設(shè)計中，選擇了原理圖和VHDL 代碼相結(jié)合的方式設(shè)計． 需要邏輯轉(zhuǎn)換的部分用VHDL 代碼編寫，如多路選擇器． 而在圖形化顯示更容易理解的地方，采用原理圖編輯的方法設(shè)計．筆者設(shè)計的內(nèi)進(jìn)化VRC 分別由12 個如圖4 所示的邏輯PE 層和4 個如圖5 所示的保存PE 層構(gòu)成．

圖4 邏輯PE 層Fig．4 Logic PE layer

如圖1 所示，12 個邏輯PE 層在前，4 個保存PE 層在后，共16 列．第n(n≤12)列可以接受Microblaze 輸出、保存PE 層的輸出、第m(m ＜n)列邏輯PE 輸出和FPGA 管腳的信號作為輸入．第n(n ＜13)列可以接受Microblaze 輸出信息、FPGA管腳的信號、m(m≠n)列的輸入信息或者輸出信息作為輸入．

演化陣列的列數(shù)要結(jié)合所要演化的目標(biāo)電路的規(guī)模大小而設(shè)定．若陣列規(guī)模過小，目標(biāo)電路可能演化不出來，而規(guī)模太大則演化時間可能過長．本設(shè)計中，所演化的電路都是以分為時間單位，一般目標(biāo)電路的演化都不會超過10 min． 在目標(biāo)電路難以確定的情況下，可以盡量擴(kuò)大演化層數(shù)．

圖5 保存PE 層Fig．5 Temporary PE layer

3 時序邏輯電路演化算法和演化結(jié)果分析

時序邏輯電路在片進(jìn)化設(shè)計的過程有兩個關(guān)鍵．一是在線進(jìn)化設(shè)計目標(biāo)電路，CPU 利用遺傳算法不停地改變電路結(jié)構(gòu)編碼，利用編碼配置VRC 演化陣列，直至滿足目標(biāo)電路要求． 二是目標(biāo)電路的配置，尋找到目標(biāo)電路后，把該電路對應(yīng)的染色體編碼重新配置VRC 陣列，最終形成正確的目標(biāo)電路．當(dāng)外部環(huán)境變化導(dǎo)致VRC 不能正常工作或任務(wù)變更時，兩者之間重新建立通信，運行進(jìn)化算法，對目標(biāo)電路進(jìn)行演化，直至滿足功能要求．

3．1 演化算法

目標(biāo)電路的搜索采用遺傳算法． 遺傳算法是通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，包含選擇、交叉、變異等基本操作．本實驗采用經(jīng)典的(1 +λ)演化策略，實現(xiàn)的步驟如下:

(1)根據(jù)VRC 結(jié)構(gòu)確定配置編碼的格式和長度． VRC 的配置編碼為一長串二進(jìn)制數(shù)，由VRC 的第一列開始編碼到最后一列組成如“b1b2b3b4b5b6…bn”，b 為1 或者0，其中n 為配置編碼的總位數(shù)． 配置編碼的排列遵循PE 單元的排列，如b1b2b3代表第一層PE 的功能配置位，b4b5b6代表第一層PE 左側(cè)的輸入信號選擇，b7b8b9代表第一層PE 右側(cè)的輸入信號選擇……，b146b147b148代表最后一層的左側(cè)信號輸入選擇．

(2)初始化種群． 在初始化種群的過程中需要注意的有兩個方面． 一方面是隨機(jī)數(shù)種子的選擇，經(jīng)驗證明隨機(jī)數(shù)種子對演化代數(shù)的影響非常大．第二是結(jié)合具體的VRC 設(shè)計，在利用隨機(jī)數(shù)初始化種群之后，需要適當(dāng)?shù)男薷?，如第一層VRC 的輸入端必需有外部輸入或者來自FPGA管腳的輸入．

(3)尋找最優(yōu)個體． 將種群的編碼配置到VRC 當(dāng)中去，根據(jù)目標(biāo)電路確定目標(biāo)輸入數(shù)組M與其對應(yīng)的目標(biāo)輸出數(shù)組N，給VRC 輸出目標(biāo)輸入數(shù)組M，讀取輸出數(shù)組I，將數(shù)組I 與數(shù)組N 比較，相同的值越多則說明適應(yīng)度越高．如果全部相同則停止演化．

(4)變異．令種群個數(shù)為n，利用找到的最優(yōu)個體變異出(n-1)個新個體．

(5)交叉．令種群個數(shù)為n，(n -1)個新個體之間進(jìn)行交叉．

(6)生成新種群．刪除適應(yīng)度最低的個體，并用最優(yōu)個體替換掉最差個體結(jié)合4，5 步生成的(n-1)個新個體，生成當(dāng)前種群;返回到第3 步．

3．2 結(jié)果分析

利用上述硬件演化平臺、演化模型和遺傳算法，分別演化了1001 序列檢測器、二分頻、四分頻以及八分頻等電路，相應(yīng)的演化代數(shù)分布情況如圖6 ～9 和表1 所示．

圖6 演化1001 序列檢測器Fig．6 Sequence detector evolution

表1 不同目標(biāo)電路的演化數(shù)據(jù)統(tǒng)計Tab．1 Statistics of difference target circuit evolution

可以看出，設(shè)計的演化模型能夠成功演化多種時序電路．演化的成功率證明，該模型特別適宜于演化分頻器電路．遺傳算法執(zhí)行時，需要利用偽隨機(jī)數(shù)發(fā)生器初始化種群．在實驗過程中發(fā)現(xiàn)，偽隨機(jī)數(shù)的種子對電路演化的收斂速度有十分重要的影響．為此，分別將隨機(jī)數(shù)種子從1 到70 依次進(jìn)行了電路演化． 種群的規(guī)模大小為5，變異率［7-8］都是用0．01，每個隨機(jī)數(shù)對應(yīng)的演化時間均未超過10 分鐘．需要說明的是，演化1001 檢波器時，其演化成功率為74%． 但是當(dāng)隨機(jī)數(shù)種子為73 時，演化代數(shù)只需要135 代．與此相同，在演化分頻電路時，不同的種子演化速度差別亦很大．因此，在實際演化電路時可以參照本實驗結(jié)果選取適當(dāng)?shù)碾S機(jī)數(shù)種子來初始化種群，提高電路演化的收斂速率．

4 結(jié)論

隨著嵌入式技術(shù)的發(fā)展，更多的電子系統(tǒng)都需要脫離PC 機(jī)運行，筆者只用一片F(xiàn)PGA 實現(xiàn)了片內(nèi)運行演化算法和實時配置全向連接的VRC矩陣．通過改變遺傳算法，利用同一個模型實現(xiàn)了二分頻、四分頻、八分頻和序列檢測器，驗證了本模型的通用性．由于時序電路的輸出不僅取決于當(dāng)前的輸入也與前一個狀態(tài)相關(guān)，所以其研究難度大，筆者結(jié)合其電路中間狀態(tài)有限的特點，成功的解決了這個問題． 時序邏輯電路利用演化硬件技術(shù)設(shè)計的研究較少，筆者詳細(xì)論述并實現(xiàn)了時序邏輯電路在片演化，將有效擴(kuò)展演化EHW 技術(shù)的應(yīng)用范圍．

［1］ 劉尚合，原亮，褚杰． 電磁仿生學(xué)——電磁防護(hù)研究的新領(lǐng)域［J］．自然雜志，2009，31(1):1 -7．

［2］ YAO Xin，HIGUCHI T． Promises and challenges of evolvable hardware［J］． IEEE Trans on Systems Man and Cybernetics-Part C:Applications and Reviews，1999，29(1):87 -97．

［3］ 滿夢華，原亮，巨政權(quán)．嵌入式系統(tǒng)門級在線自修復(fù)技術(shù)研究［J］．計算機(jī)工程，2011，37(19):9 -11．

［4］ 王瓏，李元香，金彤． 基于演化硬件的圖像加密技術(shù)研究［J］．計算機(jī)科學(xué)與工程，2009，31(12):31 -34．

［5］ FALEONER M C，KAMISETTY K，NORMAN A，et al． Using evolutionary algorithms for signal integrity checks of high speed data buses［C］//Proceedings of the 2007 IEEE Workshopon Evolvable and Adaptive Hardware(WEAH 2007)． Honolulu Hawaii:IEEE press，2007:35 -39．

［6］ ALI B，ALMAINI A E A，KALGANOVA T，et al．Evolutionary algorithms and their use in the design of sequential logic circuits ［J］． Genetic Programming and Evolvable Machines，2004(5):11 -29．

［7］ STOMEO E，KALGANOVA T，LAMBERT C． Mutation rate for evolvable hardware［C］// Proceedings of World Academy of Science，Engineering and Technology．［S．1．］:World Academy of Science Engineering and Technology，2005:117 -124．

［8］ KEYMEULEN D，STOICA A，ZEBULUM R，et al．Self-reconfigured mixed -signal integrated circuits architecture comprising a field programmable analog Array and a general purpose genetic algorithm IP core［C］//ICES．［S．1．］:［S．n．］，2008:225 -236．