可擴展的數字電路在線演化架構設計

聶 鑫，李元香

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

0 引 言

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

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

1 虛擬可重構電路

1.1 基于LUT的演化模塊

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

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

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

此處設定每一個演化模塊的LUT都是1 bit的n輸入1輸出，且模塊的輸入都能夠與處于其前列的模塊的輸出相連接，這樣，就需要在LUT前配置n個多路選擇器(multiplexer，MUX)。一個由n個1 bit輸入和1個1 bit輸出的LUT，一共可以表示22n種函數。因此，考慮到函數功能的復雜程度和配置串的長度對搜索空間的影響，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 可重構模塊陣列

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

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

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

系統開發的總體過程[16]與使用的各種軟件工具如圖3所示。

圖3 系統開發總體

(1)加法器的演化

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

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

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

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

(2)乘法器的演化

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

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

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

(3)實驗結果分析

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

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

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

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

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

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

2.1 相對節點位置編碼

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

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

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

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

圖4 固定連接深度的虛擬可重構陣列圖

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

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

圖5 改進后的邏輯單元結構

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

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

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

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

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

圖6 染色體的組成

2.2 不等概率變異算子

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

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

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

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

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

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

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

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

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

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

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

3 實驗與分析

3.1 實驗與算法設計

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

(1)加法器的演化

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

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

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

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

(2)乘法器的演化

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

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

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

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

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

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

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

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

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

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

3.2 實驗分析

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

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

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

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

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

4 結束語

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