XDL网表的前向电路图生成算法

冷 明，孙凌宇，郭 晨

井冈山大学 计算机科学系，江西 吉安343009

随着超大规模集成电路（Very Large Scale Integration Circuit，VLSI）的制造工艺从深亚微米工艺时代进入纳米工艺时代，导致现场可编程门阵列（Field Programmable Gate Array，FPGA）的噪声容限日益减少[1]，对高能粒子辐射和噪声干扰愈发敏感，软错误率（Soft Error Rate，SER）呈指数增长[2]。XDL（Xilinx Design Language）[3]是Xilinx公司提供的一种描述FPGA设计内部结构信息的特征化物理设计语言，使用巴科斯范式（Backus-Naur Form，BNF）描述FPGA 实现特定功能硬件设计的网表级电路，其中的逻辑资源配置信息和布线资源互联信息，可用于准确分析SRAΜ（Static Random Access Μemory）型FPGA 器件的单粒子软错误敏感性，提升容错可靠性的计算精确度。本文基于SRAΜ型FPGA 器件的单粒子软错误传播机理[4]，构建XDL 网表级电路的信号传播模型“有向超图”，进而提出了基于有向超图的XDL网表的前向电路图生成算法。相比基于功能模块间近似耦合关系的单粒子软错误传播特性计算方法[5]，本文提出的XDL电路网表到前向电路图生成算法，精细刻画了信号的前向拓扑关系，反映了单粒子软错误在SRAΜ型FPGA器件中的传播特性，为计算软错误率提供了必要的传播模型。

本文采用有向超图构建网表级电路的信号传播模型：电路单元的有效管脚表示为有向超图中的结点，电路管脚间的外部连线、电路管脚内的电路逻辑功能表示为超图中的有向超边。本文阐述了XDL网表的前向电路图的生成算法步骤：首先，遍历电路网表的Inst 电路单元，抽取XDL 电路网表的逻辑配置信息以生成超图结点和有向超边；其次，遍历电路网表的Net电路信号，抽取XDL 电路网表的互联配置信息以生成有向超边；进而，遍历有向超图的每个超图结点，生成每个超图结点的直接前驱结点列表，并通过递归遍历直接前驱结点列表中的结点，生成超图结点的间接前驱结点列表；最后，在Windows 平台下基于RapidSmith 开源软件[6]和Java 语言设计实现了前向电路图生成算法，选用基于Virtex-4 型号FPGA 测试用例的XDL 网表，生成相应的前向电路图以验证前向电路图生成算法的有效性。

1 XDL网表级电路描述文件的解析

每个XDL 网表级电路描述文件对应一个FPGA 设计的硬件实现，使用BNF范式详细地描述了整个FPGA设计的基本信息以及布局布线信息，包含design、module、instance 和net 等语句，提供了FPGA 设计在芯片微观级别（网表级）逻辑资源的配置信息和布线资源的互联信息。表1 给出了XDL 网表级电路描述语言的EBNF 表达式语法规则。

定义1 design 语句采用“design”关键字表示，其生产 式 规 则

定义2 module 语句采用“module”关键字表示，其生产式规则

定义3 instance语句采用“inst”关键字表示，其生产式规则

定义4 net语句采用“net”关键字表示，其生产式规则

2 基于有向超图的XDL 网表的前向电路图生成算法

根据定义1～定义5，基于有向超图的XDL网表的前向电路图生成算法的主要思想是：（1）电路单元的有效管脚表示为有向超图中的结点。（2）电路管脚间的外部连线、电路管脚内的电路逻辑功能，表示为超图中的有向超边。（3）每条有向超边可以连接两个以上的结点，对应于电路单元间的连线可以连接两个以上的有效管脚，或电路逻辑功能可以连接多输入管脚。（4）在每条有向超边中，唯一的输出管脚对应于有向超边的尾端结点，其余输入管脚对应于有向超边源端子集结点，且有向超边的源端子集的每个结点属于该尾端结点的直接前驱结点。（5）通过递归遍历直接前驱结点列表中的结点，生成该超图结点的间接前驱结点列表。只有超图结点x的间接前驱结点列表中未包含前驱结点z，才会调用递归遍历生成前驱结点z 的间接前驱结点列表，巧妙地避免XDL电路网表的信号前向拓扑关系中存在有向环导致递归循环。

表1 XDL网表级电路描述语言的EBNF表达式

2.1 算法分析

基于有向超图的XDL网表的前向电路图生成算法伪代码如图1所示，其详细步骤如下：

第3行到第11行：遍历电路网表的Inst电路单元模块信息，依次处理每个Inst电路单元。抽取XDL电路网表的逻辑配置信息，获取有效管脚信息列表，为每个有效管脚生成一个超图结点；根据Inst电路单元的不同类型，配合CFG配置信息获取的底层电路配置状态，解析每个输出管脚的逻辑功能表达式，为每个输出管脚生成一条有向超边，且该有向超边的尾端结点为该输出管脚对应的超图结点；依据该输出管脚的逻辑功能表达式，输入管脚对应的超图结点加入到该有向超边的源端子集中。

第12 行到第17 行：遍历电路网表的Net 电路信号模块信息，依次处理每个Net 电路信号，为其生成一个超图结点。读取其INPUT 端点信息，依据信息中指定的Inst电路单元和管脚信息找到相应的超图结点，作为该有向超边的尾端结点；读取其每个OUTPUT 端点信息，依据信息中指定的Inst电路单元和管脚信息找到相应的超图结点，加入该有向超边的源端子集。

第18 行到第24 行：遍历压缩存储格式的有向超图的每个超图结点x，生成每个超图结点的直接前驱结点列表。遍历超图结点x 所在的每条有向超边e，如果超图结点x 是有向超边e 的尾端结点，则遍历有向超边e的源端子集的每个结点加入到超图结点x 的直接前驱结点列表中。

第25 行到第39 行：遍历压缩存储格式的有向超图的每个超图结点x，生成每个超图结点x 的间接前驱结点列表。遍历超图结点x 直接前驱结点列表中的每个前驱结点y，依次处理前驱结点y 的直接前驱结点列表中的每个前驱结点z；如果超图结点x 的间接前驱结点列表中未包含前驱结点z，则将前驱结点z 加入到超图结点x 的间接前驱结点列表中，递归生成前驱结点z的间接前驱结点列表，且遍历该超图结点z 直接前驱结点列表和间接前驱结点列表中的每个前驱结点p，如果超图结点x 间接前驱结点列表中未包含前驱结点p，则将前驱结点p 加入到超图结点x 间接前驱结点列表中。

图1 XDL网表的前向电路图生成算法伪代码

有向超图在不同的物理存储结构下会产生不同的算法时间复杂度和空间复杂度[7-8]。因此，本文的前向电路图生成算法采用压缩存储格式（Compressed Storage Format，CSF）[9-10]。CSF 存储格式使用数组hewgts 存储有向超边的信息，使用数组vwgts存储超图结点的信息，使用数组eind存储每条有向超边的邻接结点信息，使用数组eptr 存储每条有向超边对应邻接结点列表的起始位置信息。假设数组地址从零开始，结点编号从零开始，则第i 条有向超边的邻接结点列表存储在数组eind中，位置从eptr[i]开始，到eptr[i+1]-1 结束，即从数组eind[eptr[i]]到eind[eptr[i+1]-1]，且有向超边的尾端结点存储在数组元素eind[eptr[i]]中。

2.2 时空复杂度分析

设XDL 网表电路中#Instances 数为m ，#Pins 数为n，#Nets数为t。该前向电路图生成算法中第3行到第11行为每个Inst电路单元建立超图结点和有向超边，其循环次数为m，第6 行为每个管脚建立超图结点，其循环次数为n；第12 行到第17 行为每个Net 电路信号模块生成有向超边，其循环次数为t ，第15行到第16行为每个管脚建立超图结点，其循环次数最坏情况为t×n ；第18行到第24行为每个超图结点建立直接前驱结点列表，其循环次数为n，第19行到第23行为每个超图结点遍历所在的超边，其循环次数为(m+t)×n；第25 行到第39 行为每个超图结点建立间接前驱结点列表，其循环次数为n，第26 行到第38 行为每个超图结点遍历其直接前驱结点，第27 行到第37 行为每个直接前驱结点遍历其直接前驱结点，其循环次数最坏情况为n×n×n；因此算法总时间复杂度为Θ(m+n+2×t×n+m×n+t3)。该前向电路图生成算法的空间复杂度取决于有向超图的CSF存储空间。基于CSF存储结构，包含大小为m 的数组vwgts，大小为n 的数组eind，大小为t的数组hewgts和eptr，因此空间复杂度为Ω(m+n+2×t)。

3 基于有向超图的XDL 网表的前向电路图生成算法的实验及结果分析

3.1 实验设计

针对XDL 网表生成前向电路图的转换实验，本文基于Xilinx公司Virtex-4型号XC4VSX55 FPGA芯片对测试用例进行综合xst、转译ngdbuild、映射map、布局par（-r）、布线par（-p）、配置流生成bitgen 和网表转换xdl，实现硬件设计到FPGA 配置流的全步骤，并通过网表转换工具xdl 将布局布线后的NCD 二进制格式网表文件，转换为XDL 文本格式网表文件，具体流程如图2所示。进而，本文设计实现了基于有向超图的XDL 网表的前向电路图生成算法，将XDL 网表文件生成前向电路图并保存为前向电路图文件。

图3和图4分别给出了测试用例综合前和综合后的寄存器传输级电路原理图。图4保留了图3时序逻辑电路的寄存器FD 器件和组合逻辑电路的INV 求反器件，为输入输出信号pin增加了IBUF或OBUF器件，为时钟信号pin增加了BUFGP器件，并将组合逻辑电路映射到查找表LUT3器件。

Virtex-4 型号XC4VSX55 FPGA 芯片中每个CLB资源有两个TITLE，每个TITLE 资源中有两个SLICE，每个SLICE 资源有两个LUT。测试用例生成的FPGA电路网表，将综合后的gen0/lfsr_data_0_rspot和gen0/lfsr_data_1_rspot 两个三位查找表LUT3，gen0/lfsr_data_0 和gen0/lfsr_data_1两个一位寄存器器件FD整合后映射至电路结点gen0/lfsr_data，并布局布线在CLB_X33Y0 资源的SLICE_X46Y0器件中。

图2 FPGA设计映射到XDL网表文件的流程图

图3 FPGA测试用例的电路原理图（综合前）

图4 FPGA测试用例的电路原理图（综合后）

图5 SLICE电路结点gen0/lfsr_data的XDL网表控制配置位信息

图5 给出了器件SLICE_X46Y0 的cfg 控制配置位信息，映射至SLICE_X46Y0 内部信号传播路径图。其中，逻辑单元G 被配置为gen0/lfsr_data_1_rstpot:#LUT:D=（A3+（A2+A1）），即G 功能配置成gen0/lfsr_data_1_rspot的等价查找表LUT且连接输入信号管脚G1～G3；逻辑单元DYΜUX被配置为Y，即从Y端口将LUT输出信号D输出给后续寄存器FFY器件；逻辑单元FFY被配置为FF，即受时钟信号CLΚ 控制的flip-flop 将LUT 输出信号D输出给YQ。同时，逻辑单元F被配置为gen0/lfsr_data_0_rstpot:#LUT:D=（～A3*（A1*A2）），即F 功能配置成gen0/lfsr_data_0_rspot 的等价查找表LUT 且连接输入信号管脚F1～F3；逻辑单元DXΜUX被配置为X，即从X 端口将LUT 输出信号D 输出给后续寄存器FFX器件；逻辑单元FFX被配置为FF，即受时钟信号CLΚ控制flip-flop将LUT输出信号D输出给XQ。

3.2 实验结果分析

读取XDL 电路网表的10 个Inst 电路单元，抽取逻辑配置信息进行分析，获取29 个有效管脚生成29 个超图结点，并为其中的11 个输出管脚生成第1～11 条有向超边。读取XDL电路网表的9个Net电路信号，抽取互联配置信息进行分析，生成第12～20条有向超边。

该实验生成对应的有向超图文件通过了hΜeTiS超图优化划分软件包对有向超图的检测[9]。有向超图文件第1行显示超图结点数是29，有向超边数是20。第2～21行输出有向超边的结点信息，其中每行第1个编号为该有向超边的尾端结点，后续编号为其源端子集的结点。

该实验生成的前向电路图文件中超图结点数是29，文件中的每一行包含当前超图结点x 的编号、“：”分隔符、超图结点x 直接前驱结点列表中每个结点的编号、“||”分隔符、超图结点x 间接前驱结点列表中每个结点的编号。以生成的前向电路图的第一行为例，01表示当前结点，映射至输出信号管脚XQ；01 结点的直接前驱结点的编号映射至输入信号管脚F1～F3 和时钟信号管脚CLΚ，其敏感位翻转将直接导致信号管脚XQ的输出出现软错误。分析表明：前向电路图文件每一行，精细刻画了与当前结点存在直接和间接前向拓扑关系的信号，其敏感位翻转将直接或间接导致当前结点的映射信号出现软错误，反映了单粒子软错误在SRAΜ型FPGA器件中的传播特性，为计算软错误率提供了必要的传播模型。

4 结束语

本文采用有向超图的形式来构建XDL 网表级电路，描述Inst电路单元和Net电路信号，其中电路单元的有效管脚表示为有向超图中的结点，电路管脚间的外部连线、电路管脚内的电路逻辑功能表示为超图中的有向超边。本文解析XDL 网表级电路描述文件以获得FPGA设计的逻辑配置和互联配置信息：遍历电路网表的Inst电路单元，抽取XDL电路网表的逻辑配置信息以生成超图结点和有向超边；遍历电路网表的Net电路信号，抽取XDL 电路网表的互联配置信息以生成有向超边。进而，本文给出了XDL 网表级电路描述文件编译所需的EBNF表达式，提出了基于有向超图的XDL网表的前向电路图生成算法，并进行了算法的时空复杂度分析。最后，本文在Windows平台下基于RapidSmith开源软件和Java语言实现了前向电路图生成算法，并选用基于Virtex-4 型号FPGA 测试用例的XDL 网表，生成相应的前向电路图以验证前向电路图生成算法的有效性。