基于位流在线生成的高效演化系统设计方法

易思静

(南京航空航天大学 自动化学院，江苏 南京 210016)

0 引言

演化硬件能够在演化算法的控制下改变自身结构演化得到目标电路。基于FPGA 的片上可编程系统(system programmable on chip，SPOC)设计可以对硬件资源的配置进行反复修改，在保证电路功能不变的情况下改变自身结构，实现演化。基于动态部分重构(dynamic partialr reconfiguration，DPR)的演化方法作为主流演化方法的一种，通过位流文件对模块功能进行配置，实现系统的粗粒度演化[1]。由于DPR方法演化粒度大多着眼于模块级别，有相当一部分的资源冗余，且进行系统容错时，往往会造成一整块资源被弃用，导致资源浪费[2]。因此，通过位流操作进行细粒度的演化方式已逐渐成为研究热点。早期实现位流操作的工具主要有JBits[3]和GeneticFPGA[4]等，这些工具可以根据需求对FPGA生成的位流文件直接进行修改。然而，这些工具仅支持部分老旧型号FPGA，且需要借助于外部PC机运行，不利于嵌入式实现。另外，GLETTE K提出以LUT作为演化对象，来提高资源的利用率[5]，但其无法对布线进行演化操作。细粒度演化的研究中，大多都只针对逻辑资源或者布线资源中的一环进行，不能做到资源的任意利用；同时，也未摆脱需要借助外部EDA工具进行设计所带来的时间消耗问题。

为此，本文提出了对FPGA资源-配置位流关系进行建模，并利用所建模型在线生成位流的方法，开发可嵌入式实现的位流在线生成算法。通过操作位流的方式对逻辑功能和布线资源进行细粒度编程，实现电路结构的修改。本文使用该方法设计演化系统，并以演化2位乘法器电路进行验证。

1 FPGA资源-位流信息建模

1.1 FPGA资源与配置数据帧位置映射建模

配置数据帧囊括了FPGA设计过程中所使用到的资源信息，其大小与划分的重构区域大小相关联。FPGA的最小重构区域包含一行、一列的Tile资源，最小重构区域内资源与配置数据帧关系模型如图1所示。其对应部分位流包括N个配置数据帧，前R帧为布线资源配置数据。逻辑功能的配置信息共计2L帧+M帧，其中左右两侧SLICE中的逻辑资源分别对应L帧配置信息。

图1 最小重构区域资源与配置数据帧关系模型

1.2 FPGA资源与配置信息位置关系建模

1)逻辑资源与配置信息位置关系建模

逻辑功能主要通过LUT的真值表变换来实现[6-7]，每个LUT的配置信息共有4处，分别位于连续4帧内，且相对帧起始地址的偏移量相同。定义LUTSTART表示LUT配置信息的基地址，其值为R+1；Col_offset为LUT所属CLB在重构区域的列偏移量；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)。

设每个最小可重构区域包含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。

由于布线资源的数目太庞大，无法像逻辑资源那样用统一的函数来描述其配置信息内容[8]。因此，本文通过建立布线资源库来描述其配置信息内容。布线资源库中每一条布线路径均可通过三段转折的形式实现，即初始段L1、中间转折段L2以及终止段L3。经由布线约束对电路布线路径进行规划，使L2段与初始段L1位于同一列资源。布线资源库包含的信息有：{起始帧位置；两帧之间的偏移量；第一帧内的位流数据(32 bit)；第二帧内的位流数据(32 bit)}。

2 基于位流在线生成的高效演化系统设计

2.1 演化系统的总体结构

演化系统总体结构如图2所示。其中，演化区域作为功能区IP核，可以根据需要配置为不同的功能；MicroBlaze作为系统控制器，用于运行演化算法和实现位流在线生成算法；SystemACE用于控制位流数据传输，HWICAP用于将其配置到系统功能区；UART用于实现FPGA和PC机的通信。

图2 演化系统总体结构图

2.2 演化区域规划与染色体编码方式

为方便演化过程中对资源进行编、解码和实现高效演化，采用图3所示模型描述演化区域。将逻辑资源抽象为M行N列的K输入1输出网格节点阵列。整体演化区域由3个部分组成，分别是输入列、演化列以及输出列。其中，输入列与输出列功能固定，作为缓冲实现与外部的通信；中间部分的资源用于生成电路拓扑。演化列内的每一个演化节点都可配置为不同功能。

图3 演化区域结构图

某一候选电路拓扑所实现的功能由各节点功能和节点之间的连接共同确定，采用染色体编码的形式进行描述。如图4所示，本文采用多参数级联的CGP编码方式，将整条染色体分成两段。图4(a)中StringA段的作用是确定不同节点之间的连线关系，称之为连线编码；图4(b)中StringB是用来确定节点所表达的功能，称之为节点功能编码；编码示意情况如图4(c)所示。

图4 多参数级联分段编码方法

图4中节点功能的编码用负数表示，节点连线的编码用非负数表示。对连线进行编码时，先对其输入和输出引脚进行独立编号(图3)，输入引脚的标号作为染色体的基因位，将连接到该输入引脚的某功能节点输出引脚标号作为其基因值。

2.3 位流在线生成算法设计

使用代表候选电路拓扑的染色体配置演化区域时，首先要根据图4所示编码规则对染色体进行解码，确定各节点所对应的逻辑资源位置与功能以及节点之间的布线资源连接路径，然后采用逻辑资源与布线资源位流在线生成算法生成配置位流。

1)逻辑资源位流在线生成算法

通过对LUT功能及其对应配置信息的研究，本文提出了一种基于最小项表达式的LUT功能编程算法。首先将某LUT需要实现的功能规范化为最小项表达式，其位流配置信息可根据式(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节可计算出需要修改的初始位流字地址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：按照最小项布尔型数组的个数进行循环操作，当数组取值为真时进行插值操作，取值为假则继续进行循环。修改完毕后再将配置信息写回原位流文件。

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处的内容进行判断，自第一位开始循环，若该位为“0”，则使用资源库中对应的帧中第1位内容与之替换；若该位为“1”，则不进行替换，循环次数为该字的长度。对需修改的第二帧中的index2处位流重复上述操作。

步骤4：最后把修改后的配置数据帧数组Bitstr[m][n]写回原位流文件中。

3 演化系统板级验证及结果分析

下面以演化2位乘法器电路为例对基于位流在线生成的高效演化系统进行验证。实验在Xilinx Virtex-5 ML507 FPGA上进行。

3.1 硬件框架设计

在对2位乘法器演化区域进行设计时，如图6所示，把中间用于电路结构设计LUT之间的连线以及功能去除，仅留下第一列和最后一列作为框架支撑，中间部分的电路通过电路编码来进行自由组合设计。将该结构生成初始位流进行演化操作。

图6 底层电路框架

3.2 电路验证

系统演化成功后，电路连接情况以及功能节点的内容如图7所示。按图7中所示连接方式以及节点逻辑功能配置情况进行电路连接，该电路整体即能实现2bit乘法器功能，电路验证成功。

图7 2位乘法器实际电路连接结构

3.3 与其他演化方法对比

采用预先生成位流的DPR演化方法实现2位乘法器，需要划分16个重构区域来表示演化列中的功能节点，至少需要320个CLB来组成重构区域；而本文方法只需24个LUT，其资源消耗比DPR方法减少了99.06%。

采用将EDA工具并入演化环的方法设计2位乘法器，产生每条染色体时均需调用EDA工具从顶层电路开始进行重新设计。反复的调用操作将会使演化时间大大拉长。采用该方法与本文方法设计2位乘法器时，时间消耗对比如表1所示。由表1可见，使用EDA设计方法产生一个电路个体的配置位流需要17 s，而本文方法仅需0.1 s，比EDA工具法速度提高了将近170倍。

表1 EDA设计方法与本文设计方法消耗时间对比 单位：s

4 结语

本文采用基于位流在线生成的DPR方法设计了演化系统，给出了演化嵌入式系统的总体结构，通过演化2位乘法器验证本方法的有效性。本文所提出方法在演化粒度上达到了FPGA板级可操作资源的最小级别LUT级，通过操作位流的方式实现对逻辑功能和布线资源的在线编程。实验结果表明：本文方法具有更低的资源代价和更高的演化速度。