易思靜

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

0 引言

演化硬件能夠在演化算法的控制下改變自身結構演化得到目標電路?；贔PGA 的片上可編程系統(tǒng)(system programmable on chip，SPOC)設計可以對硬件資源的配置進行反復修改，在保證電路功能不變的情況下改變自身結構，實現演化?；趧討B(tài)部分重構(dynamic partialr reconfiguration，DPR)的演化方法作為主流演化方法的一種，通過位流文件對模塊功能進行配置，實現系統(tǒng)的粗粒度演化[1]。由于DPR方法演化粒度大多著眼于模塊級別，有相當一部分的資源冗余，且進行系統(tǒng)容錯時，往往會造成一整塊資源被棄用，導致資源浪費[2]。因此，通過位流操作進行細粒度的演化方式已逐漸成為研究熱點。早期實現位流操作的工具主要有JBits[3]和GeneticFPGA[4]等，這些工具可以根據需求對FPGA生成的位流文件直接進行修改。然而，這些工具僅支持部分老舊型號FPGA，且需要借助于外部PC機運行，不利于嵌入式實現。另外，GLETTE K提出以LUT作為演化對象，來提高資源的利用率[5]，但其無法對布線進行演化操作。細粒度演化的研究中，大多都只針對邏輯資源或者布線資源中的一環(huán)進行，不能做到資源的任意利用；同時，也未擺脫需要借助外部EDA工具進行設計所帶來的時間消耗問題。

為此，本文提出了對FPGA資源-配置位流關系進行建模，并利用所建模型在線生成位流的方法，開發(fā)可嵌入式實現的位流在線生成算法。通過操作位流的方式對邏輯功能和布線資源進行細粒度編程，實現電路結構的修改。本文使用該方法設計演化系統(tǒng)，并以演化2位乘法器電路進行驗證。

1 FPGA資源-位流信息建模

1.1 FPGA資源與配置數據幀位置映射建模

配置數據幀囊括了FPGA設計過程中所使用到的資源信息，其大小與劃分的重構區(qū)域大小相關聯。FPGA的最小重構區(qū)域包含一行、一列的Tile資源，最小重構區(qū)域內資源與配置數據幀關系模型如圖1所示。其對應部分位流包括N個配置數據幀，前R幀為布線資源配置數據。邏輯功能的配置信息共計2L幀+M幀，其中左右兩側SLICE中的邏輯資源分別對應L幀配置信息。

圖1 最小重構區(qū)域資源與配置數據幀關系模型

1.2 FPGA資源與配置信息位置關系建模

1)邏輯資源與配置信息位置關系建模

邏輯功能主要通過LUT的真值表變換來實現[6-7]，每個LUT的配置信息共有4處，分別位于連續(xù)4幀內，且相對幀起始地址的偏移量相同。定義LUTSTART表示LUT配置信息的基地址，其值為R+1；Col_offset為LUT所屬CLB在重構區(qū)域的列偏移量；slice為該LUT所屬SLICE類型(0代表右側SLICE，1代表左側SLICE)；lut表示該LUT的位置(0代表A、B LUT；1代表C、D LUT)；introffset表示幀內偏移量。則LUT對應配置幀地址為

Col_offset×(N-1)+LUTSTART+slice(L+M)。

設每個最小可重構區(qū)域包含CLBsPerRR個CLB，以底部CLB坐標為零點，當垂直方向向上使用第Y個CLB時，所在幀內偏移量introffset為

introffset=2×Y+lut(Y<10)，introffset=2×Y+1+lut(10≤Y≤19)。

設一幀內有Num個字，故該LUT的第一個配置字的起始地址為

Staddr=(Col_offset×(N-1)+LUTSTART+slice(L+M))×Num+introffset

2)布線資源與配置信息關系建模

與邏輯資源的配置信息位置建模類似，定義變量frame和frame_offset分別表示布線資源配置信息的起始幀地址和兩幀配置數據間的幀偏移量，introffset代表幀內偏移量。定義變量index表示需修改的配置信息起始字，index1、index2分別為第一處及第二處配置信息字位置。對單段連線進行修改時，其配置字地址為

index=frame×Num，index1=index+introffset，index2=index1+frame_offset×Num。

由于布線資源的數目太龐大，無法像邏輯資源那樣用統(tǒng)一的函數來描述其配置信息內容[8]。因此，本文通過建立布線資源庫來描述其配置信息內容。布線資源庫中每一條布線路徑均可通過三段轉折的形式實現，即初始段L1、中間轉折段L2以及終止段L3。經由布線約束對電路布線路徑進行規(guī)劃，使L2段與初始段L1位于同一列資源。布線資源庫包含的信息有：{起始幀位置；兩幀之間的偏移量；第一幀內的位流數據(32 bit)；第二幀內的位流數據(32 bit)}。

2 基于位流在線生成的高效演化系統(tǒng)設計

2.1 演化系統(tǒng)的總體結構

演化系統(tǒng)總體結構如圖2所示。其中，演化區(qū)域作為功能區(qū)IP核，可以根據需要配置為不同的功能；MicroBlaze作為系統(tǒng)控制器，用于運行演化算法和實現位流在線生成算法；SystemACE用于控制位流數據傳輸，HWICAP用于將其配置到系統(tǒng)功能區(qū)；UART用于實現FPGA和PC機的通信。

圖2 演化系統(tǒng)總體結構圖

2.2 演化區(qū)域規(guī)劃與染色體編碼方式

為方便演化過程中對資源進行編、解碼和實現高效演化，采用圖3所示模型描述演化區(qū)域。將邏輯資源抽象為M行N列的K輸入1輸出網格節(jié)點陣列。整體演化區(qū)域由3個部分組成，分別是輸入列、演化列以及輸出列。其中，輸入列與輸出列功能固定，作為緩沖實現與外部的通信；中間部分的資源用于生成電路拓撲。演化列內的每一個演化節(jié)點都可配置為不同功能。

圖3 演化區(qū)域結構圖

某一候選電路拓撲所實現的功能由各節(jié)點功能和節(jié)點之間的連接共同確定，采用染色體編碼的形式進行描述。如圖4所示，本文采用多參數級聯的CGP編碼方式，將整條染色體分成兩段。圖4(a)中StringA段的作用是確定不同節(jié)點之間的連線關系，稱之為連線編碼；圖4(b)中StringB是用來確定節(jié)點所表達的功能，稱之為節(jié)點功能編碼；編碼示意情況如圖4(c)所示。

圖4 多參數級聯分段編碼方法

圖4中節(jié)點功能的編碼用負數表示，節(jié)點連線的編碼用非負數表示。對連線進行編碼時，先對其輸入和輸出引腳進行獨立編號(圖3)，輸入引腳的標號作為染色體的基因位，將連接到該輸入引腳的某功能節(jié)點輸出引腳標號作為其基因值。

2.3 位流在線生成算法設計

使用代表候選電路拓撲的染色體配置演化區(qū)域時，首先要根據圖4所示編碼規(guī)則對染色體進行解碼，確定各節(jié)點所對應的邏輯資源位置與功能以及節(jié)點之間的布線資源連接路徑，然后采用邏輯資源與布線資源位流在線生成算法生成配置位流。

1)邏輯資源位流在線生成算法

通過對LUT功能及其對應配置信息的研究，本文提出了一種基于最小項表達式的LUT功能編程算法。首先將某LUT需要實現的功能規(guī)范化為最小項表達式，其位流配置信息可根據式(1)和式(2)進行計算。m為定義的布爾型數組中的某一位，變量fl為字選擇標志，il為位選擇標志。

fl=m%8

(1)

il=m/4

(2)

定義4個字符型數據cf0-cf3來描述LUT功能的位流數據，其內容確定方法如圖5所示。k用于確定配置幀。通過計算fl與il的值，按照不同的位置將修改后的位流插入到配置信息中。

圖5 基于最小項的LUT功能編程算法

邏輯資源通過按位插入的方法在線生成位流，邏輯資源位流在線生成算法主要步驟如下。

步驟1：經1.2節(jié)可計算出需要修改的初始位流字地址startaddr。

步驟2：經式(1)、式(2)計算fl、il的值，并判斷k的值，定位需將配置信息具體寫入哪一處位置中。

步驟3：讀取配置數據，保存在以字數為第一維度，字長為第二維度的二維數組Bitstr[m][n]中。

步驟4：根據變量k的不同取值，k=0時將數組cf3[il]內的數值插入LUT配置信息對應4處修改的最后一處，即Bitstr[Staddr+ 3×Num][il]處；k=1時將數組cf2[il]內的數值插入倒數第二處，即Bitstr[startaddr+2×Num][il]處，以此類推，實現配置信息的按位插值。

步驟5：按照最小項布爾型數組的個數進行循環(huán)操作，當數組取值為真時進行插值操作，取值為假則繼續(xù)進行循環(huán)。修改完畢后再將配置信息寫回原位流文件。

2)布線資源位流在線生成算法

布線資源位流在線生成算法主要步驟如下。

步驟1：計算每條布線路徑的列偏移量Col_offset和introffset值。定義L1段的起始CLB坐標為(sourceCLBrow，sourceCLBcol)，L3段目的CLB坐標為(sinkCLBrow，sinkCLBcol)，則布線路徑中3條線段的Col_offset計算為Col_offset=sinkCLBrow(L3段)，Col_offset=sourceCLBcol(L1/L2段)。L1段及L2/L3段的幀內偏移量introffset可計算為introffset=2×sourceCLBrow + 1 +sourceCLBrow/(A/2)，introffset=2×sinkCLBrow+1+sinkCLBrow/(A/2)。

步驟2：讀取位流文件并存儲到二維數組中。

步驟3：對待修改字進行數值判斷并覆蓋。首先對待修改第一幀中index1處的內容進行判斷，自第一位開始循環(huán)，若該位為“0”，則使用資源庫中對應的幀中第1位內容與之替換；若該位為“1”，則不進行替換，循環(huán)次數為該字的長度。對需修改的第二幀中的index2處位流重復上述操作。

步驟4：最后把修改后的配置數據幀數組Bitstr[m][n]寫回原位流文件中。

3 演化系統(tǒng)板級驗證及結果分析

下面以演化2位乘法器電路為例對基于位流在線生成的高效演化系統(tǒng)進行驗證。實驗在Xilinx Virtex-5 ML507 FPGA上進行。

3.1 硬件框架設計

在對2位乘法器演化區(qū)域進行設計時，如圖6所示，把中間用于電路結構設計LUT之間的連線以及功能去除，僅留下第一列和最后一列作為框架支撐，中間部分的電路通過電路編碼來進行自由組合設計。將該結構生成初始位流進行演化操作。

圖6 底層電路框架

3.2 電路驗證

系統(tǒng)演化成功后，電路連接情況以及功能節(jié)點的內容如圖7所示。按圖7中所示連接方式以及節(jié)點邏輯功能配置情況進行電路連接，該電路整體即能實現2bit乘法器功能，電路驗證成功。

圖7 2位乘法器實際電路連接結構

3.3 與其他演化方法對比

采用預先生成位流的DPR演化方法實現2位乘法器，需要劃分16個重構區(qū)域來表示演化列中的功能節(jié)點，至少需要320個CLB來組成重構區(qū)域；而本文方法只需24個LUT，其資源消耗比DPR方法減少了99.06%。

采用將EDA工具并入演化環(huán)的方法設計2位乘法器，產生每條染色體時均需調用EDA工具從頂層電路開始進行重新設計。反復的調用操作將會使演化時間大大拉長。采用該方法與本文方法設計2位乘法器時，時間消耗對比如表1所示。由表1可見，使用EDA設計方法產生一個電路個體的配置位流需要17 s，而本文方法僅需0.1 s，比EDA工具法速度提高了將近170倍。

表1 EDA設計方法與本文設計方法消耗時間對比 單位：s

4 結語

本文采用基于位流在線生成的DPR方法設計了演化系統(tǒng)，給出了演化嵌入式系統(tǒng)的總體結構，通過演化2位乘法器驗證本方法的有效性。本文所提出方法在演化粒度上達到了FPGA板級可操作資源的最小級別LUT級，通過操作位流的方式實現對邏輯功能和布線資源的在線編程。實驗結果表明：本文方法具有更低的資源代價和更高的演化速度。