聶 鑫，李元香

(1.武漢工程大學 計算機科學與工程學院，湖北 武漢 430205； 2.武漢大學 計算機學院，湖北 武漢 430072)

0 引 言

演化硬件(evolvable hardware，EHW)[1]在電子設計自動化、自適應以及容錯[2]方面的優(yōu)越性，有望使它成為突破傳統(tǒng)電子設計領域瓶頸[3]的新技術。而基于虛擬可重構(gòu)電路(virtual reconfigurable circuit，VRC)[4]實現(xiàn)的在線演化是當前研究的主要方向。Kyrre Glette和Jim Torresen利用嵌入式處理器進行演化操作，連同VRC共同集成在單片F(xiàn)PGA中，實現(xiàn)了單芯片演化系統(tǒng)[5]。Wang J，Chen QS等則用VHDL語言[6]來描述電路的演化行為，從而實現(xiàn)了純硬件的電路在線演化，并且通過限制電路模塊之間的連接來減少編碼的長度[7]。Sekanina成功在FPGA platform-COMBO6 card上實現(xiàn)了圖像濾波器的在線演化[8]。VRC中的各個演化模塊目前均采用m×n的矩陣排列方式，各個模塊中一般只定義了有限幾個功能函數(shù)，在整個目標電路的演化過程中，各模塊的功能只能從這些函數(shù)中選取，不能動態(tài)調(diào)整為新的功能函數(shù)，而且通常需要先通過大量的實驗，確定一個較優(yōu)的函數(shù)集。

本文在已有的在線演化平臺模型[9,10]的基礎上，對VRC中的各個單元模塊提出了設計方法：①使用查找表(look-up-table，LUT)的方式來實現(xiàn)模塊的函數(shù)功能，并通過多路選擇器來連接位于其前列的模塊，從而豐富了各個模塊的連線與函數(shù)功能多樣性，乃至整個電路群體的多樣性；②針對基于CGP編碼[11]的數(shù)字電路演化設計的收斂性問題[12]，提出了一種節(jié)點相對位置編碼方式和不等概率的變異算子，使得不會由于染色體的隨機交叉和變異而產(chǎn)生“非法個體”，且能夠進一步淘汰掉節(jié)點連接深度較高的“較差個體”。實驗結(jié)果表明，這一設計架構(gòu)和算法的改進對提高數(shù)字電路演化的收斂性起到了良好的效果，并且同時能在較大程度上保證生成電路的多樣性。對規(guī)模不大的目標電路的演化設計具有優(yōu)勢，特別適合于電路的局部容錯與自修復[13]。

1 虛擬可重構(gòu)電路

1.1 基于LUT的演化模塊

LUT本質(zhì)上就是一個RAM，它的原理是把數(shù)據(jù)事先寫入RAM后，每當輸入一個信號，就等于輸入了一個地址進行查表，找出該地址對應的內(nèi)容，然后輸出。數(shù)字電路中的每一種組合邏輯都可以表示成一個LUT，如圖1將一個組合邏輯的真值表用LUT來表示。

圖1 組合邏輯電路的LUT表示法

當圖1(b)中的8位配置串取圖1(a)中的S序列時，該LUT就等效于這個組合邏輯電路所代表的功能。這種通過LUT來實現(xiàn)函數(shù)功能的方法，可以在電路演化過程中，通過改變配置串來動態(tài)調(diào)整該邏輯單元中所選擇輸出的函數(shù)功能。

此處設定每一個演化模塊的LUT都是1 bit的n輸入1輸出，且模塊的輸入都能夠與處于其前列的模塊的輸出相連接，這樣，就需要在LUT前配置n個多路選擇器(multiplexer，MUX)。一個由n個1 bit輸入和1個1 bit輸出的LUT，一共可以表示22n種函數(shù)。因此，考慮到函數(shù)功能的復雜程度和配置串的長度對搜索空間的影響，n的值通常取2或3，即演化模塊中LUT的設計大多采用2輸入或3輸入的形式。例如：某一個3輸入LUT的演化模塊設計為能從處于其前列的8個模塊中選擇連接通路，則需要在該模塊中配置3個8選1多路選擇器，如圖2所示。

圖2 基于LUT的演化模塊

每個8選1多路選擇器需要3位配置串來決定它的連線通路，所以對于這樣一個演化模塊，一共需要3×3+8=17 bits的配置串，即該模塊的染色體長度為17。

1.2 可重構(gòu)模塊陣列

由以上多個可配置的演化模塊組成的陣列便稱為虛擬可重構(gòu)電路。陣列的大小對硬件資源和系統(tǒng)性能都有著重要的影響，通常要經(jīng)過多次的實驗才能找到一個較優(yōu)的組合方案。由于在標準CGP編碼中，一個節(jié)點可以與其前面任意列上的節(jié)點連接，所以多路選擇器的數(shù)據(jù)寬度將會增大，因而會極大擴展染色體的編碼長度和搜索空間，不利于演化算法的最終收斂[14]，后面會對這一問題進行深入的探討。

將邏輯單元中的函數(shù)部分用LUT的形式來表示，其目的是為了使函數(shù)功能也能夠用配置串的形式來表示，進而編碼成染色體的一部分并執(zhí)行演化操作。它能夠使得在不需要先行設計具體函數(shù)模塊的情況下，自動演化出所需要的目標電路。為了說明這種演化方式與函數(shù)級演化具有同樣的有效性，首先通過在不同規(guī)模的虛擬可重構(gòu)電路上演化兩種測試電路來進行實驗。

本文使用的FPGA是Xilinx公司生產(chǎn)的Xilinx大學計劃Virtex-II Pro系列XC2VP30型開發(fā)板[15]。XC2VP30型開發(fā)板中提供了兩個硬核(PowerPC 405)，這兩個硬核都是32位的精簡指令集計算機(reduced instruction set computer，RISC)處理器。此外還提供了一個軟核(Micro-Blaze processor)，它的最高處理器頻率和總線頻率都是100 MHz，而PowerPC的處理器頻率最高可達300 MHz。

系統(tǒng)開發(fā)的總體過程[16]與使用的各種軟件工具如圖3所示。

圖3 系統(tǒng)開發(fā)總體

(1)加法器的演化

加法器是電路進化設計中常用的測試電路，分別用標準CGP編碼采用函數(shù)級演化和LUT級演化來進行二位全加器的演化實驗。函數(shù)級演化的函數(shù)集為{非,與,或,異或}。在上述兩種演化策略中，分別構(gòu)造4×4，5×5和6×6的演化陣列。設置的算法參數(shù)和演化算子完全相同，種群規(guī)模PopSize=128，最大迭代次數(shù)為20 000，變異概率Pm=0.1，采用大小為4的錦標賽選擇算子[17]。表1和表2是10次運行中演化硬件找到目標電路的平均代數(shù)、設計成功的次數(shù)以及10次實驗中最優(yōu)電路的成本(活動節(jié)點的個數(shù))。

表1 演化設計二位加法器的實驗結(jié)果

表2 演化設計三位加法器的實驗結(jié)果

從表1和表2可以看出，在兩種不同的演化平臺上，均可以成功演化出目標電路。LUT級演化的演化效率甚至要優(yōu)于函數(shù)級演化。這是因為在演化過程中，函數(shù)功能也能夠同時做自適應調(diào)整的原因，但是這種演化效率的優(yōu)勢會隨著目標電路邏輯功能的復雜以及演化平臺面積的增大而急劇下降。

(2)乘法器的演化

二位乘法器是一個四輸入、四輸出的組合邏輯電路，分別用標準CGP編碼采用函數(shù)級演化和LUT級演化來進行二位全加器的演化實驗。采用與加法器演化實驗相同的函數(shù)集。在兩種演化方式下分別采用5×5，6×6和7×7的演化平臺。演化算法的參數(shù)和算子完全相同，種群規(guī)模PopSize=128，最大迭代次數(shù)為50 000，變異概率Pm=0.1，采用大小為4的錦標賽選擇算子。表3中是10次運行中演化硬件找到目標電路的平均代數(shù)、設計成功的次數(shù)以及10次實驗中最優(yōu)電路的成本(活動節(jié)點的個數(shù))。

表3 演化設計二位乘法器的實驗結(jié)果

從表3可以看出，在兩種不同的演化平臺上，對于邏輯功能較復雜的乘法器電路，LUT級演化同樣具有很強的演化能力，其成功率往往高于函數(shù)級演化。但是演化平均代數(shù)卻弱于函數(shù)級演化，說明由于其編碼的特殊性，使得演化算法的收斂性降低。

(3)實驗結(jié)果分析

通過以上兩個實驗獲得的結(jié)果可以看出，基于LUT級的電路演化方法與基于函數(shù)級的電路演化方法具有同等的效力，最終均能夠演化出期望的目標電路。但是LUT級演化具有以下3個方面的特點：

1)對于邏輯簡單的加法器電路，LUT級演化所需要的平均代數(shù)要小于函數(shù)級演化，但是如果虛擬可重構(gòu)電路的規(guī)?；螂娐返妮斎胼敵鰯?shù)量增大，見表3，這種優(yōu)勢會明顯下降。因為對于簡單的組合邏輯而言，隨機變動函數(shù)功能會對目標電路的生成起到促進作用，但是當虛擬可重構(gòu)陣列的規(guī)模擴大時，優(yōu)于代表函數(shù)功能的染色體所參與的隨機變異行為，會使得算法的收斂性呈下降趨勢。

2)對于邏輯復雜的乘法器電路，LUT級演化所表現(xiàn)的這種收斂性下降趨勢就更加明顯。這時，預先定義基本函數(shù)單元的演化方式就比函數(shù)單元功能隨機變異的演化方式有了某種優(yōu)勢。然而在電路演化的成功率上卻相反，LUT級演化雖然收斂性下降，但是最終還是能演化出目標電路，而函數(shù)級演化由于函數(shù)單元的功能相對固定，因此在演化過程中容易陷入局部最優(yōu)，而導致長期處于適應值停滯階段，終而無法演化出目標電路。

3)在同等規(guī)模的虛擬可重構(gòu)電路基礎上，通過LUT級演化方式成功演化出的目標電路的種類要多于函數(shù)級演化方式，并且隨著虛擬可重構(gòu)電路規(guī)模的增大，生成電路的種類會更多。顯然是因為LUT級演化中，函數(shù)集并非確定的，在演化過程中，會有很多新穎的函數(shù)進來參與組合電路的生成，所以生成電路的多樣性大大的增強，而這一特性，對于將演化硬件用于容錯系統(tǒng)的設計有著非常積極的意義。

2 電路演化效率的關鍵因素

電路演化的效率體現(xiàn)在兩點：演化算法的收斂性和電路演化的成功率。其中算法的收斂性與染色體的編碼和演化算子的設計有密切的關系。在CGP編碼中，對節(jié)點的編碼方式和染色體的演化算子的改進，成為有效提高電路演化效率的方法之一。

2.1 相對節(jié)點位置編碼

演化算法在求解問題時，對潛在解采用的交叉和變異操作有可能會產(chǎn)生非法個體，即不滿足客觀環(huán)境的無效解。演化硬件同樣如此，在設計演化算子時如何避免產(chǎn)生非法個體是首要考慮的問題。在CGP編碼中，我們盡管在生成初始化種群的過程中采取措施保證隨機生成的所有個體都是合法的電路，但是隨后的演化過程卻極容易導致非法電路。

究其原因，在前文中已經(jīng)提到，是由于每個邏輯單元的連接編碼的變異范圍不一致所導致。因此，如果能夠使得連接編碼的范圍一致，這個問題便會迎刃而解。

文獻[18]證明了在組合邏輯中，任何的組合邏輯函數(shù)都可以通過增加了節(jié)點的連接層次但是不改變其邏輯功能，將節(jié)點的連接深度縮小，并不損害對目標電路的求解的完備性。因此，文獻[19]中將CGP函數(shù)級演化中節(jié)點的連接方式限制為逐列連接。這種逐列連接的方式結(jié)構(gòu)固然簡單，但很可能造成在最終的得出電路中大量的模塊沒有被實際利用。如前所述，由于每一個模塊的實際連接數(shù)一般為2或3，所以對于一個要求由m bits輸入的模塊組成的陣列，m的值越大，就越可能有更多的模塊沒有被實際連接。同時，每一個模塊由于只有一個輸出，且只能被緊隨其后的那一列模塊所連接，模塊的功能沒有被多列復用，也是造成許多模塊被“浪費”的重要原因，而且也會限制電路種群的多樣性。

采用相對節(jié)點位置編碼的一個必要條件是每個邏輯單元的連接深度必須一樣。因此，本文對虛擬可重構(gòu)電路中邏輯單元之間的連線方式做出了限制，令每個邏輯單元向前連接的最大深度為2，如圖4所示。

圖4 固定連接深度的虛擬可重構(gòu)陣列圖

設定每一列中的模塊都可以與其前兩列中的模塊相連，即每一列模塊的輸出，都可以被其后兩列的模塊所復用。這樣，在一個由m行n列構(gòu)成的陣列中，每個模塊的輸入就是2×m bits，每個模塊中的多路選擇器為2×m選1。

例如，設計一個8×5的虛擬可重構(gòu)電路，由于每列均可與前兩列相連，所以每個模塊中將是16選1的多路選擇器。對于第一列，由于輸入信號只有8位，所以需另外構(gòu)造8位數(shù)據(jù)，組成16位信號輸入到第一列，供多路選擇器選擇，這里采用加入一個非門的形式，先將輸入信號翻轉(zhuǎn)，然后再與原信號組合，輸入第一列；對于第二列，模塊的輸入信號則是第一列的輸出結(jié)果加上原始輸入信號；之后的各列，均由前一列的輸出信號加上更前一列的輸出信號組成輸入信號。如圖5所示。

圖5 改進后的邏輯單元結(jié)構(gòu)

這樣改進了連線方式與編碼方案有以下幾個優(yōu)點：

(1)可以保證每一個邏輯單元的連線部分的配置串，其取值范圍相同，這樣在進行演化操作時，不會產(chǎn)生非法個體，不需要浪費時間對其取值進行約束，和對該個體進行評價，有利于加快演化速度。

(2)從某種程度上保持生成電路的多樣性，不完全將高連接深度的目標電路從解空間中排除。

(3)能在一定程度上減少活動節(jié)點的覆蓋率，這同樣是因為保證了一定的高連接深度的目標電路的生成。

每個16選1多路選擇器需要4位配置串來決定它的連線通路，所以對于這樣一個演化模塊，一共需要3×4+8=20 bits的配置串，即該模塊的染色體長度為20，如圖6所示。

圖6 染色體的組成

2.2 不等概率變異算子

文獻[20]證明了越是邏輯功能復雜的數(shù)字電路，其節(jié)點的平均連接深度往往越低，即復雜的邏輯函數(shù)，需要靠更多層次的節(jié)點連接才能實現(xiàn)，因若能在演化過程中對符合這種特征的染色體進行優(yōu)先選擇將有利于提高收斂速度，有利于電路的快速生成。

因此，本文在采用演化策略時引入一種新的變異算子(unequal probability)，使得邏輯單元能以不同的概率與位于其前列的其它邏輯單元相連接，如果兩個邏輯單元離得較近，則連接的概率越高，反之越低，即每一個邏輯單元的變異策略均傾向于低連接深度。這種變異算子的改進能夠大大降低演化算法的搜索空間，排除出不符合這一特征的“較差個體”，從而加快電路演化的收斂速度，且同時能夠保持一定的生成電路的多樣性，也就是在創(chuàng)造性設計和演化收斂速度之間達到一種平衡。

這種變異算子的核心思想是在染色體變異時，并不是隨機地改變表示邏輯單元之間連接的基因位，而是那些在陣列中離的近的節(jié)點之間相互連接的概率就越大。設用于虛擬可重構(gòu)電路由m行n列的組成，為了防止反饋循環(huán)，故只允單向連接。

令Cj表示位于陣列中的第j列的邏輯單元； P(j,i) 表示第j列的邏輯單元連接到位于其前i列的邏輯單元的概率，有：

若i1>i2，則P(j,i1)

圖7展示了不同連接深度的基因位所具有的不同的遺傳概率，即連接深度較高的個體將具有較小的概率被選擇進入下一代種群。該算子在演化算法過程中的實現(xiàn)步驟為：

圖7 連接編碼的不同變異概率

(1)分析染色體的組成，找到每個染色體中，表示邏輯單元連接的基因位，如圖6所示的染色體中，第19～第8位這些基因，代表了邏輯單元的連接編碼；

(2)分析第(1)步中找到了每一位基因的值，是否大于某個值，此值表示的是前一列的輸出節(jié)點個數(shù)。例如2.1節(jié)提出的8×5的虛擬可重構(gòu)電路，如果基因位大于7，則表示該輸入接口連接的是前2列上的某個輸出節(jié)點，而如果基因位小于等于7，則表示該輸入接口連接的是前1列上的某個輸出節(jié)點；

(3)對于連接值偏大的基因，給予更高的變異概率，使其能夠調(diào)整為低連接深度，對于連接值偏小的基因，給予更低的變異概率，使其能夠保持當前的低連接深度；

(4)在演化算法選擇操作時，優(yōu)先選擇具有更多低連接深度基因的個體，例如采用錦標賽選擇算子時，可以將低連接深度基因的個數(shù)，作為錦標策略。

3 實驗與分析

3.1 實驗與算法設計

通過以上對邏輯單元的連接深度、染色體編碼和變異算子3個方面的改進，其目的是在既保證生成電路的多樣性的同時，也能提高電路演化的收斂速度。下面通過3個目標電路的演化實驗來驗證這一新的電路演化設計方法的有效性。

(1)加法器的演化

在前文提出的基于LUT設計的邏輯單元的基礎上，采用8×4的虛擬可重構(gòu)陣列結(jié)構(gòu)。種群規(guī)模PopSize=128，最大迭代次數(shù)MaxGeneration=50 000，與前一列節(jié)點連接的變異概率Pm=0.1，與前兩列節(jié)點連接的變異概率Pm=0.05，采用大小為4的錦標賽選擇算子。表4中是3種不同算法下演化硬件找到目標電路的演化算法平均運行代數(shù)、找到的不同電路結(jié)構(gòu)個數(shù)以及最優(yōu)電路的成本(活動節(jié)點的個數(shù))。

表4 改進后演化設計二位全加器的實驗結(jié)果

圖8比較了演化設計二位全加器時，改進后的算法與標準CGP編碼在算法收斂性上的差異。

圖8 演化設計二位全加器的算法收斂性

(2)乘法器的演化

在前文提出的基于LUT設計的邏輯單元的基礎上，采用8×8的虛擬可重構(gòu)陣列結(jié)構(gòu)。種群規(guī)模PopSize=128，最大迭代次數(shù)MaxGeneration=50 000，與前一列節(jié)點連接的變異概率Pm=0.1，與前兩列節(jié)點連接的變異概率Pm=0.3，采用大小為4的錦標賽選擇算子。與表4中的各項性能指標含義相同，實驗結(jié)果見表5。

表5 改進后演化設計二位乘法器的實驗結(jié)果

圖9比較了演化設計二位乘法器時，改進后的算法與標準CGP編碼在算法收斂性上的差異。

圖9 演化設計二位乘法器算法收斂性

(3)奇偶校驗電路的演化

奇偶校驗電路也是目前最常用的用于演化硬件測試的組合邏輯電路。下面以四位奇偶校驗電路為例來進行實驗。

在前文提出的基于LUT設計的邏輯單元的基礎上，采用8×4的虛擬可重構(gòu)陣列結(jié)構(gòu)。種群規(guī)模PopSize=128，最大迭代次數(shù)MaxGeneration=50 000，與前一列節(jié)點連接的變異概率Pm=0.1，與前兩列節(jié)點連接的變異概率Pm=0.05，采用大小為4的錦標賽選擇算子。實驗結(jié)果見表6。

表6 改進后演化設計四位奇偶校驗電路的實驗結(jié)果

圖10比較了演化設計四位奇偶校驗電路時，改進后的算法與標準CGP編碼在算法收斂性上的差異。

圖10 演化設計四位奇偶校驗電路的算法收斂性

3.2 實驗分析

通過比較分析上述3個實例的實驗結(jié)果，我們可以得出如下結(jié)論：

(1)對于相同規(guī)模的目標電路，改進后的算法比其它兩種演化能得到更多的不同結(jié)構(gòu)的目標電路。雖然連接深度的減少又會對生成電路多樣性產(chǎn)生負面影響，但邏輯單元所實現(xiàn)的具體的功能也在不斷的演化，所演化出的函數(shù)功能更加豐富，不拘泥于某幾個固定的函數(shù)，能夠同時搜索出最優(yōu)的連接與函數(shù)的組合。因此，對生成電路多樣性的保持起到了良好的作用。

(2)算法的收斂性上，逐列連接的效果是最好的，但卻以犧牲更多的冗余資源為代價，活動節(jié)點的個數(shù)最多，且生成電路的種類卻最少。而本文改進的方法在這兩個方面進行了折中考慮，既保持了電路的多樣性，在演化算法收斂性上，也比CGP編碼方式有了明顯提高。

(3)通過實驗發(fā)現(xiàn)，雖然有一些“較優(yōu)”的個體，只需要很少的連接深度即可以實現(xiàn)目標電路，對冗余資源的消耗最少，然而這樣的個體是很少數(shù)的，且要演化出這樣的結(jié)果，往往需要耗費大量的時間，因此，這樣的演化目標，是不適合于電路的容錯自修復的。而通過較少連接層次實現(xiàn)的目標電路，通過多消耗一定的冗余資源為代價，能夠快速提高電路演化的收斂性，這種在冗余資源的消耗量和電路收斂速度上的同時“優(yōu)化”，特別適合于電路的容錯與局部自修復。

最后。對于規(guī)模不大但邏輯較為復雜的電路，采用LUT級演化方法都能快速有效地得到相應功能的電路。但是隨著電路規(guī)模的增大，例如圖像空域濾波器電路，直接使用LUT級演化方法也不能得到理想的結(jié)果，原因主要有兩點：第一，因為每個邏輯單元中的LUT的輸入引腳和輸出引腳都是1 bit的，而圖像空域濾波器電路的輸入引腳共有8×9=72 bit，此時只有極大的擴充虛擬可重構(gòu)電路的規(guī)模，才能滿足運算的需要，但是圖像的每個像素點的8 bit數(shù)據(jù)是一個整體，在LUT上進行的運算的粒度太細，既無必要，也極大浪費搜索時間。第二，如果將LUT的輸入和輸出的位寬擴大，雖然擴大了LUT的運算粒度，但是其配置串會呈指數(shù)級增長，同樣無法演化出所期望的電路。但LUT級演化設計方法可以快速生成局部子電路，可以通過這種方式來動態(tài)調(diào)整函數(shù)的功能，易于跳出演化過程中局部最優(yōu)，這對解決電路的收斂性問題將發(fā)揮很大的積極的作用。并且將LUT級演化與本章提出的演化算法相結(jié)合，在演化小規(guī)模電路中所體現(xiàn)的優(yōu)越性，對于實現(xiàn)大規(guī)模電路中的局部容錯系統(tǒng)的設計有著積極的意義。

4 結(jié)束語

本文在對演化硬件在線演化方法已有研究的基礎上，提出了一種數(shù)字電路的函數(shù)級演化方法，將虛擬可重構(gòu)電路中邏輯單元的函數(shù)功能采用LUT的方式實現(xiàn)，可以使得函數(shù)功能也能編碼為染色體，進而參與演化操作。該方法可以在無需事先針對目標電路進行分析的前提下，實現(xiàn)數(shù)字電路的演化。實驗結(jié)果表明，這種實現(xiàn)方式與傳統(tǒng)函數(shù)級演化方法具有同樣的有效性，并且由于函數(shù)功能也能參與演化，因而有利于提高生成的目標電路的多樣性。從生成電路的多樣性和電路演化的收斂速度等方面考慮，設計了相應的虛擬可重構(gòu)電路結(jié)構(gòu)以及演化算子。最后，用3個實例驗證了上述方法的有效性，通過實驗分析比較得出改進后的電路演化設計方法，對規(guī)模不大的目標電路設計具有優(yōu)勢，特別適合于電路的局部容錯與自修復。最后文中分析并指出了下一階段要研究的目標，即在目標電路為邏輯較復雜的大規(guī)模電路時，可以采用電路分解模型，分解出一定數(shù)量的等效子電路集合，而利用LUT級演化設計方法可以快速生成這些局部子電路，其在演化小規(guī)模電路中所體現(xiàn)的優(yōu)越性，對于實現(xiàn)大規(guī)模電路中的局部容錯系統(tǒng)的設計有著積極的意義。