基于演化硬件的硬件重構編碼方案及演化算法研究

王婷，蘭巨龍，鄔鈞霆

（國家數字交換系統工程技術研究中心, 河南 鄭州 450002）

1 引言

目前，以應用為驅動的互聯網正朝著高速化和寬帶化的方向發展。然而大量差異化業務的大規模部署及新型業務的不斷涌現，使得現有網絡無法滿足其服務需求，底層固有硬件的支撐也不堪重負[1]。面向服務提供的新型網絡技術體系的提出為解決上述問題提供了新的思路[2]。在該技術體系之下，對于網絡交換節點來說，就是要研究功能可重構、性能可編程的路由交換設備，將控制平面與數據平面相分離，通過重構實現控制平面上對多種路由協議的支持，運行多種路由算法，表象的更新與維護，系統的配置與管理等，通過編程實現數據平面上的線速查表、分類、加密、隊列管理等。然而數據平面的處理往往需要很強的實時性，傳統模式下依賴的固有硬件系統已經無法適應新功能變更的要求，一旦有新的功能出現，系統或模塊必須整體替換或升級，使得網絡交換節點的可擴展性及靈活性變得很差。

對于底層硬件設計人員來說如果將開放可編程的邏輯器件作為開發平臺，設計實現一系列具有基本功能的可重構硬件構件（硬件邏輯模塊），當系統需要對新業務進行服務時，只需找到相關功能的硬件構件加以組合或改進，就可實現對新業務服務要求的支持[2,3]。這種在原有硬件平臺上通過重構來支持新業務的方式，必然會在增強路由設備的靈活性及可擴展性、減小重構時隙、節約開發成本上具有很大的優勢。

隨著半導體工藝水平的迅速提高，單個可編程邏輯器件的片上資源越來越豐富，利用電子設計自動化（EDA）這類軟件工具進行硬件下載實現所需硬件電路的方法，與芯片高集成度間的差異越來越大，硬件程序員所設計的硬件功能不能通過EDA工具很好地詮釋于芯片之上，不僅對硬件資源的利用率不高，很大程度上影響了硬件設計者的初衷。與此同時，當電路功能需要重構來滿足新業務的需求時，上述硬件實現方法只能重新編寫或修改硬件程序，然后再通過EDA工具“翻譯”后下載到芯片上，必然會導致重構時隙開銷的增加，無法完成可重構路由交換節點的硬件重構要求。因此，利用演化硬件（EHW, evolvable hardware）來解決上述矛盾，成為可重構硬件重構技術研究的一個新熱點[4]。演化硬件利用自身的快速并行計算能力及其在解空間的尋優搜索能力，來實現硬件電路的自動設計。

演化硬件可以用下面的公式來定義：EAs+PLD=EHW。即：演化算法+可編程邏輯器件=演化硬件。演化硬件是一種黑盒設計技術，對硬件設計者的專業知識依賴程度不是很高，能夠最大程度的實現硬件設計的自動化。它的設計重點是讓演化來生成所需電路，硬件設計者只需告訴它做什么而不是怎樣做。演化硬件不僅可以對將要投入實現的硬件設計進行修改，而且可以對已經投入使用的電路進行修改，避免了替換已有硬件電路所需的開發成本，而且硬件程序員的設計錯誤也可以通過人工或進一步演化來修正，減小了設計風險和實現成本[5～9]。基于演化硬件的硬件重構技術可以解決快速發展的網絡業務多樣性的需求，同時可以節約研發及重復建設網絡的硬件成本，符合現今社會綠色網絡和低碳經濟的需求。將可編程邏輯器件作為開發平臺，實現可重構路由交換平臺硬件電路重構的原理如圖1所示。

圖1 基于PLD的硬件電路重構原理

由圖1可知，染色體編碼方案是實現硬件重構的基礎，決定了最終的硬件電路結構的好壞、遺傳操作的進化速度以及搜索空間的大小，進而影響整個硬件重構的效率。因此，設計合理的染色體編碼方案顯得尤為重要。目前，相關學者已經研究出一些成熟的染色體編碼方案[10]，大致可分為2大類：直接型編碼和間接型編碼。直接型編碼方式就是將下載到PLD中的二進制配置位串直接作為演化算法中的染色體，對其進行遺傳操作，以改變門級電路的連接，進而實現硬件電路結構的改變。然而電路規模的大小直接影響著PLD配置位串的長度，通常情況下其長度在幾萬位到幾十萬位之間[11]，如果直接將整個配置位串作為演化算法中的染色體進行編碼，當演化過程對存儲和計算資源的要求隨電路規模的增長呈指數性增長時，勢必會造成片上存儲空間的大量開銷以及處理器運算量的急劇增大，因此直接型編碼只適用于小規模的硬件電路的重構。間接型編碼則是對PLD的配置文件進行一種變換，然后再對其進行編碼，它將電路更高層次的表達方式作為遺傳中染色體進行編碼，在適應度評估和生成實際硬件電路配置時，需要經過逆變換后才能生成實際的 PLD配置位串。間接型編碼采用抽象表達的方法，其演化元素不是門電路，而是基本的硬件功能模塊。

本文將演化算法與可編程邏輯器件相結合，首先提出一種基于 LUT結構的二維映射函數增量染色體編碼方案（PMFICC, planar mapped function increments chromosome coding），在此方案的基礎上又提出了一種改進的差分演化算法，并證明了其有效性。

2 基于查找表LUT結構的二維映射函數增量染色體編碼方案（PMFICC）

基于二級映射的演化硬件體系結構在基因型平面與表現型平面之間采用中間硬件表示層，基因型平面的編碼只對中間層進行，而表現型平面的實際FPGA器件的配置位串是通過中間層進行轉換獲得的。中間硬件層的結構相對簡單，因而其染色體編碼表示比直接對FPGA配置編碼簡單，降低了演化過程中對存儲和計算資源的需求。同時，中間硬件層屏蔽了底層FPGA的硬件特性，使得演化的設計方法能夠適應普遍的條件和環境，能夠適用到普遍的電路規模和類型中。Arostegui等[12]提出了采用規整的功能單元構成二維可重構平面的結構，功能單元的數量可以任意增加，從而使得演化設計具有可擴展性。R. DeMara等[13]采用二級映射機制實現基因型／表現型映射，通過虛擬演化硬件 FPGA(virtual EHW FPGA)實現染色體編碼到FPGA配置位串的轉換，其映射過程如圖2所示。

圖2 基于虛擬演化硬件的染色體編碼

目前，硬件重構技術大多數是在基于SRAM工藝的 FPGA平臺上設計實現的，以 n-LUT的FPGA為例，每一個LUT都可以看成是nbit地址線的2 1n×的RAM，當輸入nbit地址信息時，輸出就是RAM中相應單元中的狀態值（2n種邏輯功能）。為了研究可重構路由交換平臺的硬件重構技術，首先將所需的實際硬件電路按照邏輯功能分成多個邏輯功能塊，這些邏輯功能塊由若干個LUT組成的二維陣列構成，LUT之間相互連接形成整個硬件電路。本文提出的基于 LUT結構的PMFICC編碼方案，是根據實際的底層硬件資源（LUT的個數）將二進制配置文件串（.bit文件）即Bitstream文件，映射到一維狀態平面（SP, status plane，）（也就是LUT的內部狀態）和二維排序平面（CP, connection plane）（也就是LUT之間的連接關系）中，從而將冗長的一維平面上的二進制編碼，映射為二維平面上的PMFICC編碼。以3輸入的LUT為例，片上資源由16個3-LUT組成，那么基于LUT結構的PMFICC編碼方案示意圖如圖3所示。

圖3 一種基于LUT結構的PMFICC編碼方案

一維狀態平面就可由邏輯功能函數 f(x)={a, b,c, d, e, f, g, h}，（其中，x表示LUT的輸入地址信息）的編碼組合進行表示，如表1所示。那么，圖3所示的電路結構在PMFICC編碼方案中SP平面的編碼表示為 f1f2f5f6f9f10。

表1 3-LUT邏輯功能

那么，該方案的編碼方法就將16個3LUT的二進制編碼表示簡化為6個LUT的函數表示，其SP平面編碼就可簡化為6個LUT的連接關系編碼。可以用一個無向圖G來繼續簡化圖3的電路結構，如圖4所示：頂點代表參與電路結構的6個LUT，LUT間的連接關系則由無向邊來表示。PMFICC編碼方案中CP平面的編碼表示為1-2 1-6 1-9 5-10 6-5 6-9。那么圖3所示的電路結構的PMFICC編碼表示為 f1f2f5f6f9f101-2 1-6 1-9 5-10 6-5 6-9。

圖4 CP編碼平面的無向圖

應用 PMFICC編碼方案重構電路結構時，分別對比重構前后2種電路結構 SP編碼和CP編碼的差異，如果是LUT內部有變化，只需對LUT的內存狀態進行修改得到相應的 f(x)編碼；如果是路由資源發生變化即LUT的連接關系發生變化，那么可對前一種電路結構的無向圖做邏輯運算（與、或、非、異或）得到所需的邊序列編碼。

在對 FPGA進行硬件設計時，80%左右的資源都被路由資源所占，因此基于PMFICC編碼進行動態重構研究時，首先要考慮CP編碼的重構，也就是無向圖的邏輯運算。為了減小重構時隙實現動態重構技術，首先在FPGA內部建立一系列可以完成基本功能的元素圖（EG, element graph）庫，當電路功能發生改變時，僅需從 EG庫中調取相應個數的 EG進行邏輯運算，就可得到重構后新的電路結構，這將大大提高動態重構的效率。如圖5所示：元素圖 G1和 G2，那么重構后的電路G1∪G2，G1∩G2以及G1⊕G2可由G1和G2的邏輯運算得到。

圖5 元素圖重構

通過前面的分析，知道PMFICC編碼方案是以增加染色體基因型到表現型的復雜性為代價，將冗長的一維平面上的二進制編碼映射到 SP平面和CP平面。CP平面的編碼只對無向圖進行重構，SP平面則對實際FPGA器件的配置位串是進行重構，降低了直接對FPGA配置位串進行演化的冗余，減少了演化過程中對存儲和計算資源的需求。該編碼方法特別適用于基于Bitstream的動態重構，重構后新的電路功能與重構前的電路功能差異（Bitstream差異）可以通過演化算法，將前后2代染色體的差異引入到演化過程中，進而得到新的最優染色體。下面將介紹一種改進的差分演化算法。

3 一種改進的差分演化算法

如何在上述編碼方案的基礎上有效、快速地實現目標方案的最優演化是本節研究的重點問題。差分演化（DE, differential evolution）算法是一種非常適用于基于函數增量的染色體編碼演化算法，具有操作簡單、收斂速度較快等特點，并且其在求解單目標優化問題方面已經取得了成功[14～16]。典型的差分演化算法包括以下幾個步驟。

1) 初始化：利用NP個維數為D的實數向量作為每一代的種群，每個個體表示為xi,G，其中，i=1,2, …, NP，i為個體在種群中的序列，G為演化代數，NP為種群規模。初始化種群的一個方法就是在給定邊界約束內的值中隨機選擇，一般假定所有隨機初始化種群均符合均勻概率分布。設參數變量的邊界條件為則

其中，j=1, 3,…, D。

2) 變異：對于每個目標向量 xi,C, 定義其變異向量為

其中，參數 r1、r2、r3互不相同，同時有NP≥4，變異算子F∈[0,2]。

3) 交叉：定義實驗向量其中，randb(j)用于在[0, 1]之間隨機產生第j個估計值，rnbr(i)∈ 1, 2,…, D。CR為交叉算法，取值范圍為[0,1]。

4) 選擇：決定實驗向量ui,G+1是否能夠成為下一代中的會員。差分演化算法按照貪婪準則將實驗向量與當前種群中的目標向量xi,G進行比較，并選擇更優的向量作為下一代種群中的向量。函數表示為

即如Δ f＞0，則接收新的實驗向量，否則不接受。

5) 邊界條件的處理。在存在邊界約束的環境中，差分演化算法將不符合邊界約束的新個體在可行域內隨機產生的參數向量代替，即若或則

差分演化算法彌補了遺傳算法編碼繁瑣、實現復雜的缺陷，但其搜索進程緩慢且易于“早熟”。出現上述缺陷的關鍵在于差分演化算法是在“優勝劣汰”準則下進行選擇操作的，這也就決定了算法后期的收斂速度較慢，甚至有可能陷入局部最優。

為了實現硬件重構中的快速演化，本文在差分演化過程中引入局部優化機制，提出一種改進的差分演化（MDE, modified differential evolution）算法。該算法基于Metropolis準則進行選擇操作，從而能夠獲得更優的收斂速度和全局優化效率。MDE算法步驟描述如下。

步驟1 初始化算法參數：確定種群大小NP，變異因子F及CR，初始化Metropolis準則參數T和降溫控制參數k，設定迭代次數D，令h=0。

步驟2 初始化可行解空間，隨機產生N個可行解。

步驟3 執行交叉、變異操作。

步驟4 執行選擇操作。執行過程中，隨機產生擾動Δ x，得到新節點 x*=x+Δ x，如果該節點優于x，則把該節點作為下一次迭代的可行節點；否則計算出該新節點的接受概率P=exp(-Δf/T)，并產生一個[0,1]區間上的偽隨機數r，若P≥r，則接受新節點作為下一次迭代的初始點；否則放棄新節點，仍選擇原節點作為下一次迭代的初始點。

步驟5 執行降溫操作T=T×k，令h=h+1。

步驟6 如h等于D，則跳回步驟3，否則終止算法。

4 仿真實驗與性能評價

為了進一步驗證MDE算法的性能，本文選擇2種典型函數對其進行仿真實驗。

函數1 （函數最優值為f*=-78.332 3）

函數2 （函數最優值為f*=-0.998）

給定初始參數 T=5 000，k=0.8，NP=12，CR=0.3，F=0.5，迭代次數為100次。表2分別給出了函數1和函數2運行6次時的結果對比。

表2 函數1和函數2的仿真結果（運行6次）

對上述仿真結果采用方差距離比較法進行驗證。假設函數的最優值為f*，迭代次數為K，DE算法第k次迭代結果為f1k，MDE算法第k次迭代結果為 f2k，DE算法最優值的方差距離之和為MDE算法最優值的方差距離之和為

計算函數1和函數2 6次迭代的1D和2D值，其結果都為1D大于2D。對函數1進行100次迭代，仿真結果如圖6所示，DE的方差距離大于MDE的方差距離。

圖6 DE與MDE的方差距離比較

由上述仿真結果可以看出，DE算法依然存在未收斂到最優解空間的情況，這就是由于DE算法存在陷入局部最優解的缺點，而仿真過程中MDE算法并未出現上述情況，說明MDE算法改進了差分演化算法陷入局部最優解的缺點，更加逼近實際最優解。

5 結束語

硬件重構技術為構建柔性網絡提供了新的研究方向。當現有網絡服務發生變化時，基于硬件重構技術的柔性網絡能夠采用本文所提出的演化硬件重構編碼方案及演化算法，實現服務能力平滑、快速的演變及升級，從而高效地利用網絡資源，提高網絡的多樣服務能力。

演化硬件以可編程邏輯器件(PLD, programmable logic device)為平臺，針對其可重復編程重復配置的特點，將下載到PLD上的二進制配置位串作為遺傳算法的染色體，模擬生物種群的演化過程來搜尋最優的配置，自適應地實現配置PLD上可重構邏輯資源并得到所需功能的硬件電路。目前，Xilinx公司已有多款FPGA不僅可以支持全局重構，還能夠提供部分重構 (PR, partial reconfiguration )[17]功能。PR是指在不影響系統總體運行的情況下，對系統的一部分結構進行重新配置以實現新的電路功能，如VirtexTM-II、VirtexTM-II Pro/X、VirtexTM-4/FX/LX/SX系列的FPGA都可支持電路的部分重構。這些芯片提供的PR功能可以分為2種模式：基于模塊(module-based)的 PR和基于差異(differencebased)的 PR[18]。基于模塊的 PR利用總線宏(bus macro)技術保證重構后模塊間的正常連接，而基于差異的PR通過比較重構前后電路功能的差異進行重構。

本文在基于SRAM結構的FPGA平臺上，提出一種基于 LUT結構的二維映射函數增量染色體編碼方案 PMFICC，該編碼方案可利用 Xilinx公司FPGA支持基于差異的 PR功能，對比重構前后 2種電路結構SP編碼和CP編碼的差異，即重構前后2種Bitstream文件的差異，通過改進的差分演化算法MDE將前后2代染色體的差異引入到演化過程中，進而得到新的最優染色體，實現電路的動態重構，快速有效地支持系統的新功能。仿真結果驗證了其性能。

[1] 姚愛紅, 張國印, 關琳. 基于動態可重構 FPGA 的自演化硬件概述[J].智能系統學報, 2008, 3(5): 436-440.YAO A H, ZHANG G Y, GUAN L. A survey of dynamically and partially reconfigurable FPGA-based self-evolvable hardware[J]. CAAI Transactions on Intelligent Systems, 2008, 3(5): 436-440.

[2] 蘭巨龍. 可重構信息通信基礎網絡體系研究.國家重點基礎研究發展計劃（973計劃）項目計劃任務書[R]. 2011.LAN J L. Reconfigurable Basic Network of Information and Commu-nication System[R]. National Key Basic Research and Development Program Project planTask(973 Project)[R]. 2011.

[3] 李玉峰, 邱菡, 蘭巨龍. 可重構路由器研究的現狀與展望[J]. 中國工程科學, 2008, 10(7): 83-87.LI Y F, QIU H, LAN J L. The study of reconfigurable router status and prospect[J]. China Engineering Science, 2008, 10(7): 83-87.

[4] 姚睿, 于盛林, 王友仁等. 采用主流FPGA的數字電路在線生長進化方法[J]. 南京航空航天大學學報, 2007, 39(5): 583-585.YAO R, YU S L, WANG Y R, et al. Online growing evolution and evaluation approach based on mainstream FPGA[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2007, 39(5): 583-585.

[5] KAUFMANN P, PLESSL C, PLATZNER M. Evocaches: application-specific adaptation of cache mappings[A]. NASA/ESA Conference on Adaptive Hardware and Systems[C]. 2009. 13-17.

[6] YANG H Q, CHEN L G, LIU S T, et al. A flexible bit-stream level evolvable hardware platform based on FPGA[A]. NASA/ESA Conference on Adaptive Hardware and Systems[C]. 2009. 51-58.

[7] LOHN J, HORNBY C. Evolvable hardware: using evolutionary computation to design and optimize hardware systems[J]. IEEE Computational Intelligence Magazine, 2006, 1(1):19-27.

[8] MAO N, MINORU W. A sixteen-context dynamic optically reconfigurable gate array[A]. NASA/ESA Conference on Adaptive Hardware and Systems[C]. 2009. 121-125.

[9] SHANG L H, ZHOU M, et al. A new application-tuned processor architecture for high-performance reconfigurable computing[A].NASA/ESA Conference on Adaptive Hardware and Systems[C]. 2009.139-145.

[10] 李敏強, 寇紀淞, 林丹等. 遺傳算法的基本理論與應用[M]. 北京:科學出版社, 2002.LI M Q, KOU J S, LIN D, et al. Genetic Algorithm is the Basic Theory and the Application[M]. Beijing: Science Press, 2002.

[11] XILINX I. Virtex-II platform FPGA user guide[EB/OL]. http://china.Xilinx.com/support/documentation/user_guides/ug002.pdf.

[12] AROSTEGUI M, SANCHEZ E，CABESTANY J. An in-system routing strategy for evolvable hardware programmable platforms[A].Proc of the 3rd NASA/DoD, Long Beach[C]. 2001. 157-166.

[13] OREIFEJ R, AIHADDAD R, HENG T, et al. Layered approach to intrinsic evolvable hardware using direct bit-stream manipulation of virtex-II prodevices[A]. International Conference on Field Programmable Logic and Applications(FPL 2007)[C]. Amsterdam, 2007.299-304.

[14] MUSRRAT A, PANT M, ABRAHAM A. Simplex differential evolution[J]. Acta Polytechnica Hungarica, 2009, 6(5): 95-102.

[15] MUSRRAT A, PANT M, et al. A modified differential evolution algorithm and its application to engineering problems[A]. International Conference of Soft Computing and Pattern Recognition[C]. 2009.196-200.

[16] YANG Z Y, TANG K, YAO X. Large scale evolutionary optimization using cooperative coevolution[A]. Information Sciences[C]. 2008.2986-2991.

[17] XILINX C. XILINX development system reference guide 8.li[EB/OL]. http://toolbox. xilinx. com/docsan/ xilinx8/ books/ docs/dev.pdf, Xilinx data sheet, 2007.

[18] XILINX C. XAPP290: two flows for partial reconfiguration: module based or difference based[EB/OL]. http://www. xilinx. com, 2004.