可擴(kuò)展的數(shù)字電路在線演化架構(gòu)設(shè)計(jì)

聶 鑫，李元香

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

0 引 言

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

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

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

1.1 基于LUT的演化模塊

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

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

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

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

圖2 基于LUT的演化模塊

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

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

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

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

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

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

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

(1)加法器的演化

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

表1 演化設(shè)計(jì)二位加法器的實(shí)驗(yàn)結(jié)果

表2 演化設(shè)計(jì)三位加法器的實(shí)驗(yàn)結(jié)果

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

(2)乘法器的演化

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

表3 演化設(shè)計(jì)二位乘法器的實(shí)驗(yàn)結(jié)果

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

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

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

1)對(duì)于邏輯簡(jiǎn)單的加法器電路，LUT級(jí)演化所需要的平均代數(shù)要小于函數(shù)級(jí)演化，但是如果虛擬可重構(gòu)電路的規(guī)模或電路的輸入輸出數(shù)量增大，見表3，這種優(yōu)勢(shì)會(huì)明顯下降。因?yàn)閷?duì)于簡(jiǎn)單的組合邏輯而言，隨機(jī)變動(dòng)函數(shù)功能會(huì)對(duì)目標(biāo)電路的生成起到促進(jìn)作用，但是當(dāng)虛擬可重構(gòu)陣列的規(guī)模擴(kuò)大時(shí)，優(yōu)于代表函數(shù)功能的染色體所參與的隨機(jī)變異行為，會(huì)使得算法的收斂性呈下降趨勢(shì)。

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

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

2 電路演化效率的關(guān)鍵因素

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

2.1 相對(duì)節(jié)點(diǎn)位置編碼

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

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

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

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

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

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

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

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

這樣改進(jìn)了連線方式與編碼方案有以下幾個(gè)優(yōu)點(diǎn)：

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

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

(3)能在一定程度上減少活動(dòng)節(jié)點(diǎn)的覆蓋率，這同樣是因?yàn)楸ＷC了一定的高連接深度的目標(biāo)電路的生成。

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

圖6 染色體的組成

2.2 不等概率變異算子

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)與算法設(shè)計(jì)

通過以上對(duì)邏輯單元的連接深度、染色體編碼和變異算子3個(gè)方面的改進(jìn)，其目的是在既保證生成電路的多樣性的同時(shí)，也能提高電路演化的收斂速度。下面通過3個(gè)目標(biāo)電路的演化實(shí)驗(yàn)來(lái)驗(yàn)證這一新的電路演化設(shè)計(jì)方法的有效性。

(1)加法器的演化

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

表4 改進(jìn)后演化設(shè)計(jì)二位全加器的實(shí)驗(yàn)結(jié)果

圖8比較了演化設(shè)計(jì)二位全加器時(shí)，改進(jìn)后的算法與標(biāo)準(zhǔn)CGP編碼在算法收斂性上的差異。

圖8 演化設(shè)計(jì)二位全加器的算法收斂性

(2)乘法器的演化

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

表5 改進(jìn)后演化設(shè)計(jì)二位乘法器的實(shí)驗(yàn)結(jié)果

圖9比較了演化設(shè)計(jì)二位乘法器時(shí)，改進(jìn)后的算法與標(biāo)準(zhǔn)CGP編碼在算法收斂性上的差異。

圖9 演化設(shè)計(jì)二位乘法器算法收斂性

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

奇偶校驗(yàn)電路也是目前最常用的用于演化硬件測(cè)試的組合邏輯電路。下面以四位奇偶校驗(yàn)電路為例來(lái)進(jìn)行實(shí)驗(yàn)。

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

表6 改進(jìn)后演化設(shè)計(jì)四位奇偶校驗(yàn)電路的實(shí)驗(yàn)結(jié)果

圖10比較了演化設(shè)計(jì)四位奇偶校驗(yàn)電路時(shí)，改進(jìn)后的算法與標(biāo)準(zhǔn)CGP編碼在算法收斂性上的差異。

圖10 演化設(shè)計(jì)四位奇偶校驗(yàn)電路的算法收斂性

3.2 實(shí)驗(yàn)分析

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

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

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

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

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

4 結(jié)束語(yǔ)

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