采用輸入輸出分解的分區(qū)分段演化機(jī)制

姚睿，陳芹芹，孫艷梅，張砦，王友仁

(南京航空航天大學(xué)自動化學(xué)院，江蘇南京210000)

演化硬件(evolvable hardware，EHW)將演化算法與可編程邏輯器件有機(jī)結(jié)合［1］，能根據(jù)環(huán)境的變化自動、實(shí)時地調(diào)整其內(nèi)部結(jié)構(gòu)，以適應(yīng)內(nèi)部條件(如局部故障)和外部環(huán)境的變化，為有效設(shè)計新型仿生電子系統(tǒng)提供了新的方法。但由于演化設(shè)計的可擴(kuò)展性問題，應(yīng)用直接演化方法和現(xiàn)有計算資源較難演化規(guī)模較大的電路［2-8］。.

為解決EHW的擴(kuò)展性問題，文獻(xiàn)［9］設(shè)計了一種Cartesian進(jìn)化編程編碼的電路演化Memetic算法，提高了演化算法的搜索能力。文獻(xiàn)［10］將輸入轉(zhuǎn)換為輸出及雙向積累式進(jìn)化結(jié)合，提出了GDD演化方法，可進(jìn)化出多達(dá)17個輸入的復(fù)雜電路。但由于該方法是對分解后的子電路進(jìn)行逐個演化，總體所需演化代數(shù)很大。為此，文獻(xiàn)［11］提出了一種使用多核虛擬可重構(gòu)結(jié)構(gòu)(virtual reconfigurable architecture，VRA)加速組合邏輯電路演化設(shè)計過程的內(nèi)部演化方法。通過各子電路并行演化和利用演化完成的子電路對應(yīng)的空閑VRA演化相鄰的子電路，大大減少了演化時間。但由于演化過程中僅用了輸出分解，演化輸入個數(shù)較多的復(fù)雜邏輯電路時仍面臨挑戰(zhàn)。且各VRA模塊的調(diào)用關(guān)系由硬件平臺固定，第2階段的并行演化只能調(diào)用臨近的一個空閑VRA，不僅不利于硬件資源的有效利用，且演化不同的電路需要編寫不同的硬件平臺結(jié)構(gòu)，增加了設(shè)計工作量，使得設(shè)計靈活性受限。

為解決這些問題，本文提出了一種基于輸入、輸出分解的分區(qū)分段并行在線自演化機(jī)制。采用輸入、輸出分解策略將需演化電路分解為多個具有較少輸入、輸出的子電路。首先對各子電路單獨(dú)分配進(jìn)化區(qū)域進(jìn)行并行演化(即第1階段并行演化);某些子電路演化完畢時，釋放演化區(qū)域，并用其實(shí)現(xiàn)任意一個未演化完畢的子電路的并行演化(即第2階段并行演化);所有子電路均演化成功后，將其整合得到頂層電路。實(shí)驗(yàn)結(jié)果表明，該方法具有較大的靈活性，可進(jìn)化出多達(dá)21個輸入的組合邏輯電路。

1 輸入輸出分解策略

輸入輸出分解策略的基本思想如圖1所示:首先將復(fù)雜的原組合邏輯電路S經(jīng)輸入、輸出分解策略分解為n個具有更少輸入輸出的較簡單子電路S1，S2···Sn，對其分別進(jìn)行演化;n個子電路演化完畢，對其進(jìn)行整合，得到期望的頂層電路。

圖1 輸入輸出分解策略Fig.1 Inputs and outputs decomposition strategy

1.1 輸入分解

組合電路輸入分解采用真值表分解實(shí)現(xiàn)。分解的依據(jù)是任何組合邏輯電路的真值表均可根據(jù)其某一輸入的取值情況(0或1)分解為2個較簡單的真值表［12］。根據(jù)需要對原始真值表逐級分解，即可得到期望復(fù)雜度的子電路。以圖2(a)所示具有n輸入m輸出的原始組合邏輯電路F為例，其真值表如圖2(b)所示，包含p=2n個輸入輸出組合。

圖2 原組合邏輯電路及其真值表Fig.2 Original logic circuit and its truth table

如圖3(a)所示該電路可分解為r輸入s輸出、可進(jìn)化生成的新電路G以及s+n－r輸入m輸出、由選擇器組成的不參與進(jìn)化的固定電路部分M，其中s=m×2n-r［14］。對于原始電路F，在確定了子電路G的輸入個數(shù)之后，新電路G的真值表以及電路M的結(jié)構(gòu)即可確定。通過減少子電路G的輸入個數(shù)，可以減小其輸入輸出組合個數(shù)，降低電路進(jìn)化的復(fù)雜度。

子電路G的真值表產(chǎn)生過程如下:首先確定其輸入個數(shù)r的值，從而確定子電路G的輸入輸出組合個數(shù);其次對F的真值表進(jìn)行檢索，找出只與G的r個輸入和F中對應(yīng)輸入片段匹配的對應(yīng)于電路F的s/m個輸出組合;重復(fù)此過程，直至找到G的所有輸入輸出組合，如圖3(b)所示。

圖3 分解模型及新電路的真值表Fig.3 Decomposition model and truth table of the new circuit G

1.2 輸出分解

原組合電路F經(jīng)輸入分解得到的新可進(jìn)化電路G，雖然輸入個數(shù)有所減少，但輸出相對于F增加了2n-r倍。根據(jù)增量分解策略中的輸出分解，G可進(jìn)一步分解為多個具有相同輸入較少輸出的子電路。如圖4(a)所示4輸入4輸出原始組合邏輯電路，可分解為圖4(b)所示2個4輸入2輸出的子電路A與B，其真值表如圖4(c)所示。這樣只需先分別演化每個子電路對應(yīng)的2位輸出，然后將2個子電路整合即可正確表達(dá)2位乘法器。

圖4 兩位乘法器的輸出分解Fig.4 The outputs decomposition of 2-bit multiplier

1.3 整合電路的演化

各子電路分區(qū)分段并行演化完畢之后，將其整合為頂層電路，基本步驟為:首先將各子電路并聯(lián)在一起，得到可進(jìn)化電路G;然后將G和由多路選擇器構(gòu)成的固定電路M級聯(lián)起來，得到原始電路F。

2 分區(qū)分段并行演化機(jī)制

結(jié)合輸入、輸出分解策略，提出一種分區(qū)分段在線并行演化機(jī)制，以加速組合電路演化速度。其核心是把頂層電路經(jīng)輸入、輸出分解，拆分為多個較簡單子電路，對這些子電路進(jìn)行分區(qū)、分階段并行演化，以有效減少演化算法的計算復(fù)雜度、染色體長度及電路輸入輸出組合個數(shù)。

為便于說明，假設(shè)頂層組合邏輯電路分解后僅包含A與B2個子電路，且A先于B演化完畢，相應(yīng)分區(qū)分段并行演化機(jī)制如圖5所示。圖5(a)為分區(qū)并行演化機(jī)制示意圖，子電路A、B分別由其對應(yīng)的獨(dú)立進(jìn)化區(qū)域VRA1、VRA2并行演化。實(shí)驗(yàn)過程中將VRA1和VRA2封裝定制為一個虛擬可重構(gòu)IP核，由運(yùn)行于Microblaze軟核處理器上的演化算法控制，實(shí)現(xiàn)第1階段的并行演化，其演化流程圖如圖5(c)下方的虛線框所示。圖5(b)為第2階段并行演化示意圖，子電路A演化成功后，對應(yīng)的空閑進(jìn)化區(qū)域VRA1被用于與VRA2并行演化未演化完成的子電路B，其演化流程圖如圖5(c)上方的虛線框所示。

圖5 分區(qū)分段并行演化機(jī)制Fig.5 Parallel evolution mechanism by partition in stages

各子電路個體適應(yīng)度計算方法為:使用同或門將其實(shí)際輸出值與真值表中期望輸出進(jìn)行比較，若二者的某一位相同，適應(yīng)度值增1;否則，適應(yīng)度值保持不變。圖5(c)上方虛線框中，檢測到子電路A演化成功時，首先記錄成功染色體，然后將VRA1的適應(yīng)度單元輸入切換為子電路B的真值表，即可使用VRA1演化子電路B，從而使VRA1和VRA2以并行演化子電路B，完成第2階段的并行演化。分區(qū)分段并行演化步驟如下:1)初始化種群POPA和POPB;

2)分別評價其適應(yīng)度;

3)記錄最佳染色體的適應(yīng)度bestfitA和bestfitB與最佳染色體bestA和bestB;

4)若bestfitA與子電路A的最大適應(yīng)度相同(即演化出期待結(jié)果子電路A)，bestfitB與子電路B的最大適應(yīng)度不相同，跳到6);否則進(jìn)入5);

5)對種群POPA和POPB中個體進(jìn)行均勻變異得到新的個體，跳到2);

6)評價最佳染色體bestB的適應(yīng)度以及VRA1在演化子電路B時bestA的適應(yīng)度;

7)記錄最佳染色體的適應(yīng)度bestfitA和bestfitB與最佳染色體bestA和bestB;

8)若bestfitA或者bestfitB與子電路B的最大適應(yīng)度相等，跳到10);否則，進(jìn)入9);

9)變異得到新的個體，進(jìn)入6);

10)子電路A與子電路B的演化同時停止。

若原始組合邏輯電路分解后包含多個簡單子電路，某子電路演化成功后，通過切換其對應(yīng)VRA核心的適應(yīng)度單元的真值表輸入，該空閑VRA核心可用于演化未演化完畢的任意子電路;多個子電路演化成功后，亦可使用2個以上的空閑VRA同時并行演化某個未演化完成的子電路。

文獻(xiàn)［11］中，每個VRA只能調(diào)用其臨近的一個VRA資源實(shí)現(xiàn)并行演化，2個以上的子電路并行運(yùn)行時，不能充分利用硬件資源;且由于其硬件資源的調(diào)用在硬件平臺上實(shí)現(xiàn)，演化不同電路時需要構(gòu)造不同的硬件結(jié)構(gòu)，增加了設(shè)計工作量，限制了設(shè)計的靈活性。本文將多個VRA在ISE上以VHDL語言編程實(shí)現(xiàn)，演化不同電路時，只需在軟件中修改電路的輸入、輸出以及真值表特性，而不需要修改硬件架構(gòu)，因此本文的方法具有極大的靈活性。另外，由于本文的并行算法是軟件實(shí)現(xiàn)的，任何多個非鄰近空閑VRA核心均可并行演化未演化完成的子電路，有效提高了演化效率。

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

本文使用Xilinx公司的Virtex-5 ML507開發(fā)板作硬件平臺。首先在Xilinx ISE12.4開發(fā)環(huán)境下使用VHDL語言編寫分解后各子電路對應(yīng)的VRA結(jié)構(gòu)，作為可進(jìn)化模塊，并生成RTL模型進(jìn)行自我診斷。接著在EDK中把這些模塊封裝、定制成IP核，掛接到PLB總線上，構(gòu)成自演化系統(tǒng)，同時作為系統(tǒng)的驗(yàn)證評估平臺。然后在SDK中，使用C語言對染色體長度、適應(yīng)度評估及各模塊之間的相互調(diào)用等進(jìn)行編程，并調(diào)用搭建好的硬件平臺。最后，將PC機(jī)中的比特流文件下載到FPGA中，實(shí)現(xiàn)分區(qū)、分階段并行演化，并將演化結(jié)果通過UART通信在PC機(jī)的超級終端顯示。演化算法選擇標(biāo)準(zhǔn)遺傳算法，為了降低計算復(fù)雜度，僅采用了均勻變異操作，未使用交叉操作。

3.1 本文方法與其他方法對比

3位無進(jìn)位加法器、2位乘法器和Con1是EHW研究中常用的3種基準(zhǔn)測試電路。為評估本文提出方法的性能，分別采用直接演化、文獻(xiàn)［10］、文獻(xiàn)［11］和本文方法在搭建的驗(yàn)證評估平臺上對3種基準(zhǔn)電路進(jìn)行了對比實(shí)驗(yàn)。其中遺傳算法的種群規(guī)模為128，均采用聯(lián)賽選擇機(jī)制和均勻變異、變異比率為2/256;最大演化代數(shù)為50 000。直接演化時所采用演化區(qū)域功能單元陣列大小為8行×5列，其他方法中功能單元陣列大小為4行×5列。

4種演化方法下的染色體長度、硬件代價、平均演化代數(shù)以及平均演化時間如表1所示。其中每組實(shí)驗(yàn)結(jié)果是20次成功進(jìn)化的平均值。文獻(xiàn)［10］和本文方法對原電路進(jìn)行了輸入輸出分解，文獻(xiàn)［11］方法僅進(jìn)行了輸出分解。Con1和Adder3*3經(jīng)輸入分解后的新可進(jìn)化子電路G的輸入為4;對G進(jìn)行輸出分解，分解為2n－4個具有4輸入m輸出的較簡單子電路以分別演化(其中n、m分別為原電路的輸入、輸出個數(shù))。Mult2*2電路具有4輸入4輸出，實(shí)驗(yàn)中僅進(jìn)行輸出分解，分解為2個具有4輸入2輸出的子電路分別進(jìn)行演化。

表1 不同演化方法實(shí)驗(yàn)結(jié)果對比Table 1 Experimental result of different evolutionary methods

由表1可見，對于Mult2*2、Adder3*3和Con1電路，相較于直接演化，本文方法演化時間分別提升了3.9倍、19.5倍以及122.8倍。這是由于3種電路的復(fù)雜程度以及頂層電路的分解程度不同，在此實(shí)驗(yàn)中具有4輸入4輸出的Mult2*2只采用輸出分解策略分解為2個子電路并行演化;具有6輸入4輸出的Adder3*3經(jīng)過輸入輸出分解后分解為4個4輸入6輸出的子電路并行演化;具有7輸入2輸出的Con1經(jīng)過輸入輸出分解后分解為8個4輸入2輸出的子電路并行演化。由此可知，相對于直接演化，本文方法在演化時間上提高的倍數(shù)與原組合電路的復(fù)雜程度以及原頂層電路的分解程度密切相關(guān)。原組合電路的輸入輸出越多(尤其是輸入)以及其分解越精細(xì)，相較于直接演化，本文方法在演化性能上提高的倍數(shù)越大。

對于Mult2*2、Adder3*3和 Con1電路，相對于文獻(xiàn)［10］的GDD方法，本文方法在演化時間性能上分別提升了3.2倍、10.9倍和3.8倍。這是因?yàn)镚DD方法是將分解后的多個子電路逐個單獨(dú)演化，系統(tǒng)的總演化時間為所有子電路演化時間之和。

對于Mult2*2、Adder3*3和 Con1電路，相對于文獻(xiàn)［11］的多核VRA演化方法，本文方法演化時間性能分別提升了1倍、3.5倍和30.8倍。這是因?yàn)殡S著原組合電路輸入個數(shù)的增加，輸入輸出組合個數(shù)以近似指數(shù)的規(guī)律增長，相應(yīng)計算復(fù)雜度增大，演化時間隨之迅速增大。文獻(xiàn)［11］中僅采用了輸出分解策略，同時當(dāng)分解后的某些子電路演化成功后，其對應(yīng)的空閑VRA核心只能用來演化相鄰子電路;這樣，在某一時刻，系統(tǒng)最多只能實(shí)現(xiàn)相鄰的2個VRA核心并行演化同一子電路。表1中，本文方法對Mult2*2進(jìn)行分解時，由于只采取了輸出分解策略，分解為2個子電路進(jìn)行演化，故本文演化方法與文獻(xiàn)［11］方法在相同實(shí)驗(yàn)參數(shù)下，演化結(jié)果相同。

綜上，本文演化方法演化時間上總體優(yōu)于其他演化方法。其根本原因在于本文方法不僅結(jié)合了輸入、輸出分解技術(shù)，而且采用了分區(qū)分段并行演化技術(shù)。輸入輸出分解策略有效減少了每個子電路的計算復(fù)雜度和演化算法的搜索空間;在FPGA上多個子電路分區(qū)分段并行演化大大減小了演化時間。從表1可知，相較于分解前，子電路染色體的長度幾乎都減少1倍。同時，每個VRA核心都能對任意多個子電路實(shí)現(xiàn)雙階段并行演化。這樣，通過在FPGA上實(shí)現(xiàn)分區(qū)分段并行演化機(jī)制，方便數(shù)據(jù)流水線處理，提高演化性能。

從硬件代價上分析，由表1可見，本文方法相對于直接演化，硬件資源消耗只增長了1倍左右。這是因?yàn)獒槍斎胼敵鰝€數(shù)較小的子電路，可使用更小的功能單元陣列對子電路進(jìn)行演化。采用本文、文獻(xiàn)［10］及文獻(xiàn)［11］方法時，對于 Mult2*2、Adder3*3和 Con1電路，為了使實(shí)驗(yàn)結(jié)果更具有說服力，硬件資源設(shè)置相同。注意表1中資源消耗是指進(jìn)化區(qū)域的虛擬可重構(gòu)結(jié)構(gòu)消耗的總體資源，實(shí)際上最終演化出的電路僅使用了這些資源的一部分。

3.2 其他基準(zhǔn)電路進(jìn)化結(jié)果

為了證明本文提出的基于輸入輸出分解的分區(qū)分段并行演化機(jī)制能夠?qū)崿F(xiàn)演化比較復(fù)雜組合邏輯電路，以乘法器電路以及10個MCNC基準(zhǔn)電路為例，在搭建的驗(yàn)證評估平臺上對提出的觀點(diǎn)進(jìn)行了驗(yàn)證。各種電路的實(shí)驗(yàn)參數(shù)如表2所示。

表2 實(shí)驗(yàn)參數(shù)Table 2 Experimental parameters

表3給出了3個乘法器以及10個MCNC基準(zhǔn)電路的輸入個數(shù)、輸出個數(shù)、每個電路的輸入輸出組合個數(shù)以及在驗(yàn)證評估平臺上的最高工作頻率fm、平均演化時間以及平均演化代數(shù)。其中每組實(shí)驗(yàn)結(jié)果是20次成功進(jìn)化的平均值。組合電路5xp1、Add2_7、Majority、Con1、Mult2、Mult3、Mult4、Adder3*3以及 Alu4經(jīng)輸入分解后的新可進(jìn)化子電路G的輸入為4，再對G進(jìn)行輸出分解，分解為2n－4個4輸入m輸出的較簡單子電路(n、m分別為原電路的輸入、輸出個數(shù))。組合電路Parity經(jīng)輸入分解后的新可進(jìn)化子電路G的輸入為8。這里之所以選擇8而不選擇4是由于奇偶校驗(yàn)器只有一個輸入，其分解后的8輸入1輸出子電路并不復(fù)雜;若將其輸入再進(jìn)一步分解，會使演化過程過于復(fù)雜。

由表3可見，本文方法可以進(jìn)化出多達(dá)21位輸入的組合邏輯電路，且所有應(yīng)用中系統(tǒng)都能以大于84 MHz的頻率運(yùn)行。

本文中依據(jù)輸入輸出分解策略理論上可將任意組合電路分解為多個期望復(fù)雜度的簡單子電路，但分解后子電路并非越簡單越好，其規(guī)模視電路復(fù)雜度而定。一般情況下，若原組合電路的輸出數(shù)較多，對其進(jìn)行輸入分解時可進(jìn)化子電路的輸入可選為4;而當(dāng)原組合電路的輸出數(shù)較少時(比如Parity)，輸入分解時可進(jìn)化子電路的輸入個數(shù)可適當(dāng)增加。采用基于輸入輸出分解的分區(qū)分段并行演化方法，在硬件資源消耗變化不大的情況下，可以較好地演化出較大規(guī)模的組合邏輯電路。

表3 乘法器電路以及MCNC基準(zhǔn)電路的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of multiplier and MCNC benchmark circuits

4 結(jié)束語

本文提出一種基于輸入輸出分解的分區(qū)分段并行演化機(jī)制以演化復(fù)雜組合邏輯電路。該方法首先采用輸入分解策略，將頂層電路的輸入轉(zhuǎn)換為輸出，再對此可進(jìn)化子電路進(jìn)行輸出函數(shù)分解，將其分解為多個具有較少輸出的子電路，對每個子電路單獨(dú)分配進(jìn)化區(qū)域，以并行演化的方式進(jìn)行演化，有子電路演化成功后，其對應(yīng)的VRA核心即可釋放，用來并行演化其他未演化完畢的任意子電路。以加法器、乘法器和部分MCNC基準(zhǔn)電路為例在Xilinx Virtex-5 FX上進(jìn)行了驗(yàn)證，結(jié)果表明該方法可大大提高演化時間性能，有效解決EHW的可擴(kuò)展性問題。目前，該方法僅適用于組合電路的演化，未來將進(jìn)一步研究復(fù)雜時序電路的演化機(jī)制。

［1］LIN B，IRIE M.Evolvable hardware［J］.CIT595 Research Project，2008，4(8):162-164.

［2］平建軍，王友仁，高桂軍，等.數(shù)字演化硬件的函數(shù)級在線進(jìn)化技術(shù)研究［J］.高技術(shù)通訊，2009，19(1):61-65.PING Jianjun，WANG Youren，GAO Guijun，et al.Research on the technology for on-line evolution of digital hardware at function level［J］.Chinese High Technology Letters，2009，19(1):61-65.

［3］吳江，唐常杰，李太勇，等.基于多目標(biāo)并行基因表達(dá)式編程的電路演化算法［J］.武漢大學(xué)學(xué)報:工學(xué)版，2012，45(4):532-538.WU Jiang，TANG Changjie，LI Taiyong，et al.Evolutionary algorithm of circuits based on multi-objective parallel gene expression programming［J］.Engineering Journal of Wuhan University，2012，45(4):532-538.

［4］何國良，李元香，史忠植.基于精英池演化算法的數(shù)字電路在片演化方法［J］.計算機(jī)學(xué)報，2010，33(2):365-372.HE Guoliang，LI Yuanxiang，SHI Zhongzhi.Elitist pool evolutionary algorithm for on-line evolution of digital circuits［J］.Chinese Journal of Computers，2010，33(2):365-372.

［5］BIDLO M.Evolutionary design of generic combinational multipliers using development［C］//7th International Conference Evolvable Systems:from Biology to Hardware.Wuhan，China，2007:77-88.

［6］STOMEO E，KALGANOVA T，LAMBERT C.Generalized disjunction decomposition for evolvable hardware［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，2006，36(5):1024-1043.

［7］王婷.基于演化硬件的可重構(gòu)技術(shù)研究［D］.鄭州:解放軍信息工程大學(xué)，2012:24-32.WANG Ting.Research on reconfigurable technology based on evolvable hardware［D］.Zhengzhou:The PLA Information Engineering University，2012:24-32.

［8］ZHAO S，JIAO L.Multi-objective evolutionary design and knowledge discovery of logic circuits based on an adaptive genetic algorithm［J］.Genetic Programming and Evolvable Machines，2006，7(3):195-210.

［9］莫宏偉，徐立芳.基于Memetic算法的電路演化設(shè)計研究［J］.電子學(xué)報，2013，41(5):1036-1040.MO Hongwei，XU Lifang.Research on evolvable hardware design based on memetic algorithm［J］.Acta Electronica Sinica，2013，41(5):1036-1040.

［10］STOMEO E，KALGANOVA T.Improving EHW performance introducinga new decomposition strategy［C］//2004 IEEE Conference on Cybernetics and Intelligent Systems.Singapore，2004:439-444.

［11］王進(jìn)，李麗芳，任小龍.多核虛擬可重構(gòu)結(jié)構(gòu)加速邏輯電路演化設(shè)計的研究［J］.高技術(shù)通訊，2012，22(4):340-347.WANG Jin，LI Lifang，REN Xiaolong.Using MuViRaC to accelerate evolutionary design of combinational logic circuits［J］.Chinese High Technology Letters，2012，22(4):340-347.

［12］ZHANG X，LUO W.Evolutionary repair for evolutionary design of combinational logic circuits［C］//2012 IEEE Congress on Evolutionary Computation(CEC).Brisbane，Australia，2012:1-8.