辅助优化FPGA综合效果的测试例自动生成方法

刘 佩，惠 锋

（无锡中微亿芯有限公司，江苏无锡 214072）

1 引言

FPGA设计流程包括综合、装箱、布局、布线、码流生成等环节，而这一切的基础是综合。FPGA综合的主要目的是将用硬件描述语言（Hardware Description Language,HDL）描述的电路设计转换成逻辑网表并进行优化，主要包括HDL语言解析、寄存器级（Resistor Transistor Logic,RTL）网表转换、逻辑优化和目标映射4个部分。

FPGA设计工具的开发存在诸多难点，比如需处理的输入数据庞大且复杂，人工生成测试例对综合结果进行功能验证将耗费大量时间和人力物力[1]。因此，提出一种有效的测试例自动生成方法来辅助优化FPGA综合效果是很有意义的，可以加快软件的开发速度，提高软件的质量。目前已有一些测试例自动生成方法，例如通过XML（Extensible Markup Language）定义功能来描述生成RTL代码的测试例生成方法[2]，还有对于已经完成RTL功能描述并采用自动生成激励信号对其进行功能验证的方法。过去一二十年对数字系统设计测试自动化的研究和开发，侧重于对数字系统设计的正确性予以验证[3]，目前鲜有辅助FPGA设计工具开发的测试例自动生成方法。本文提出了一种优化FPGA综合效果的测试例自动生成方法。

2 逻辑优化介绍

FPGA设计平台全流程重要的指标包括电路延时、面积与功耗、布通率以及运行时间。其中FPGA综合的关键为逻辑优化，其作用是将电路进行分解，以满足查找表（Look up Table，LUT）输入的要求，包含合并冗余节点、删除无效节点、节点分解等步骤，其目标是在保持电路逻辑等价的前提下，根据用户约束平衡面积、时序以及功耗。

2.1 基本概念的定义

功能确定的数字电路，其输出、输入间的关系可抽象为逻辑函数。“乘积项之和（Sum of Product,SOP）”是常用的逻辑函数表示方法，其中变量的相乘、相加分别和逻辑“与”、逻辑“或”等操作对应，每个乘积项的变量组合均可使逻辑函数输出为1，且原变量与反变量不会同时在一个乘积项中出现。式（1）即为SOP形式的1个3变量逻辑函数，abc、ab′c′、bc′均为1个乘积项。若乘积项包含所有输入变量，便将其称为最小项（Minterm）[4]，式（1）中的abc即为1个最小项。

N个布尔变量定义一个N维的布尔空间（Boolean Space），其中存在2N个最小项。若一个逻辑函数包含2N个最小项，则这个逻辑函数包含了100%的N维布尔空间[5]。式（2）即为一个包含100%三维布尔空间的逻辑函数，其中包含三维布尔空间所有的8个最小项。

2.2 逻辑优化方法介绍

逻辑综合是将电路的RTL级描述转换成优化的门级网表的过程。目前有多种完备的算符集来表示任意门级网表，比如基于与、或、非的传统布尔逻辑（Traditional Boolean,TB），以及探索用不同的数据结构来表达和优化逻辑函数（Boolean Function），具体表现形式为BDD（Binary Decision Diagrams）[6]，AIG（And-Inverter Graphs）[7]和MIG（Majority-Inverter Graph）等[8]。对现有综合技术的扩展以及新技术的开发在文献[9]中也有更多详细描述。

多层次逻辑优化存在多种基本方法[10]，如代数逻辑优化（Algebraic Logic Optimization）、布尔逻辑优化（Boolean Logic Optimization）和布尔函数分解（Decomposition of Boolean Functions）。有学者提出关于多层次逻辑优化的4个方面的算法[11]，分别是：分解逻辑函数（Factoring Logic Function）、简化逻辑函数（Simplification of Logic Functions）、全局相位分配（Global Phase Assignment）和 时 序 优 化（Timing Optimization）。由上述方法衍生的方法还有利用MIGs研究序列优化[12]、网络重构、节点最小化[13]等。

代数逻辑优化指对逻辑表达式执行代数操作，包括分解、提取、因式分解、置换和消去。

布尔逻辑优化和布尔函数分解是指处理由布尔空间构成的相关输出无关项，达到简化逻辑表达式的目的。

上述方法都是逻辑优化的重要方式，并且可以同时使用，或者在优化过程分阶段使用，而测试例自动生成技术可以更高效地对各优化策略进行评估，达到辅助开发的目的。

3 测试例自动生成流程介绍

3.1 主要功能介绍

本文介绍的测试例自动生成工具主要功能如下。

1)自动测试例生成工具接受如下参数。

(a)PI_cnt：输入信号的个数。

(b)PO_cnt：输出信号的个数。

(c)LgLv_cnt：最高逻辑层级。

(d)Fanout_max：最高扇出个数的限制。

(e)ExprV_max：逻辑表达式中“与”最大变量数。

(f)ExpTerm_max：逻辑表达式中“或”最大变量个数。

(g)B_cnt：注入布尔空间表达式的个数。

(h)Dim_max：注入布尔空间最大维数。

(i)Seq_ctrl：控制是否加入时序逻辑。

(j)Arithm_ctrl：控制是否加入算数单元。

2)可以随机生成纯组合逻辑测试例，供代数型优化策略的测试。

3)在随机生成的组合逻辑上，注入可控规模的由布尔空间构成的输出“无关项”或“冗余项”，供布尔型优化策略测试。

4)在测试例中添加时序逻辑，供时序驱动优化策略的测试。

5)在测试例中添加算数运算单元和数据总线结构，供算数单元的综合、优化策略的测试。

3.2 测试例生成流程介绍

基于布尔优化和代数型优化两种形式，测试例自动生成流程分为两种模式，一种是纯随机生成的组合逻辑测试例，用来测试代数型优化，当然，其中也会包含可布尔优化的空间，但不明显，所以为了达到测试布尔优化的目的就需要使用另外一种模式，这种模式指的是有意识地在测试例中注入可被布尔型优化的布尔空间。测试例一般可使用语言有Verilog和VHDL，本文测试例的生成采用Verilog语言。

测试例生成流程说明如下。

根据Verilog语法，将测试例分为几个模块，然后按照需求决定是否使用。模块分为必选模块和可选模块。必选模块包括module申明模块、变量例化模块和module结束模块。module申明模块主要用来申明module名字，格式如下：“module moduleName”；变量例化模块主要用来申明输入输出变量，格式如下：“input A,B,C;output F1,F2;”；该处具体格式取决于Verilog版本，1995版本和2001版本存在些许差别；module结束模块则只有“endmodule”。

可选模块包括变量申明模块和语句执行块。变量申明模块顾名思义即用来申明中间变量；语句执行块是整个生成方法的主体。根据Verilog语法，语句执行块组成存在几种可能供选择：

1)是否只生成纯组合逻辑块；

2)是否添加其他模块测试例，如算数运算单元；

3)是否添加always语句块；

4)添加always语句块后是否添加if/case语句块。测试例结构示意图如图1所示。

图1 测试例结构示意图

3.3 纯随机组合逻辑生成说明

生成纯随机组合逻辑测试例时，通过可控变量控制组合逻辑的规模，可控变量包括输入输出变量个数、逻辑层数，该参数可用来控制Logic Level，创建语句执行块步骤如下。

1)根据PI_cnt和PO_cnt，生成输入输出变量列表，将输入输出变量列表中所有变量放入可选变量列表中。

2)生成L级逻辑层级的逻辑表达式，L=LgLv_cnt。从m=1到m=L，生成第m层级的逻辑表达式，具体过程如下。

(a)将输入变量PI列表中所有变量加入到可选变量列表VarList中。

(b)从VarList中选N个变量，要求：N≤PI_cnt且N≤ExprV_max。

(c)从（b）选出的N个变量中，随机选出n≤N个变量，生成一个逻辑“与”的项，每个变量在该项中的相位随机取正相或反相。

(d)按照（c）中的方法，生成K个这样逻辑“与”的项，要求：K≤ExprTerm_max。

(e)将K个“与”的项，做逻辑“或”，生成m=i层级的逻辑表达式Wi，即SOP（Sum of Products）的形式。

(f)生成R个这样的逻辑表达式，即在m=i层级生成了R个逻辑表达式。R是随机产生的数字。

(g)将R个新生成的逻辑函数WiR加入到可选变量列表VarList中。

(h)重复（b）~（g）的操作，生成m=2到m=L-1的逻辑表达式。在（b）中添加要求：保证N个变量中最少存在上一层级（m=i－1）中生成的R个逻辑函数中的一个。

(i)重复（b）~（g）的操作，生成m=L的逻辑表达式。在（b）中添加要求：保证N个变量中最少存在上一层级（m=L－1）中生成的R个逻辑函数中的一个。同时对（f）添加要求：R=PO_cnt。

3)将m=L层级生成的R个逻辑函数Wi对应输出给PO_cnt个输出变量。

4)测试例生成的最后进行校验，若存在未使用的变量，会按照相同的规则添加在最后一个输出变量的后面，构成SOP。

该方法可以通过控制输入输出参数个数和逻辑层级来达到预估测试例规模的目的，可以比较明显地比较代数型优化的效果，较好地驱动对于代数型优化策略的优化效果。

3.4 注入布尔空间说明

同样关于面积优化的还有布尔型优化，即处理由布尔空间构成的输出“无关项”或“冗余项”，达到优化面积的效果，所以本文的测试例生成方法也可以注入可控规模的可被布尔型优化的布尔空间，达到测试布尔型优化的目的。

测试布尔型优化的语句执行块思路与测试代数型优化相似，不同之处在于是否注入可布尔优化的逻辑部分，即有目的性地创建由布尔空间构成的输出“无关项”或“冗余项”的组合逻辑表达式。注入可布尔优化语句执行块步骤与生成纯随机组合逻辑测试例语句执行块步骤一致，仅需要在纯随机组合逻辑测试例语句执行块步骤2）的（e）中添加注入可被布尔型优化的布尔空间的逻辑部分，注入布尔空间的逻辑部分步骤示例如下。

1)由测试代数型优化的语句执行块步骤2）中的（e）得到式（3）。

式中W51表示生成的逻辑函数，a、b、c、d表示输入参数，W12和W21表示前文测试代数型优化的语句执行块步骤2）中m=1和m=2时所得到的一个逻辑函数。

2)从逻辑式（3）中随机选取一个逻辑“与”的项acW21，从输入变量PI列表随机选取T个变量，要求：T≤Dim_max。该处示例取T=2，即从输入变量PI列表选取e、f两个变量。

3)将e、f和选取的项acW21构成可被布尔型优化的布尔空间的逻辑注入到逻辑式（3）中，注入后结果如逻辑式（4）所示。

4)在语句执行块执行到步骤2）的（e）时，将步骤1）~3）一共重复B_cnt次，即在这个生成的纯随机组合逻辑测试例中注入B_cnt个布尔空间。

通过上述4个步骤，可以生成一个注入B_cnt个可被优化的布尔空间，且注入的布尔空间最大维数不超过Dim_max的测试例。可较明显地比较布尔型优化的效果，较好地驱动对于布尔型优化策略的优化效果。语句执行块生成流程如图2所示。

图2 语句执行块生成流程

4 其他部分介绍

纯组合逻辑块主要用来测试布尔型优化效果及代数型优化的效果，即面积优化的效果，当然仅使用纯面积优化可能会影响性能，这时需要在面积和性能之间取得一个平衡，而该平衡由时序驱动的优化来决断，影响时序的因素包括逻辑层次和扇出的数目，太高的逻辑层次和太多的扇出数目都会极大地影响时序的效果。

需要测试时序驱动的效果时，需要有寄存器存在，所以可以在输入端口后输出端口前添加寄存器，如此可以将组合逻辑块置于寄存器之间，可以通过时序去驱动面积优化，寻找平衡，当然，也可以在此基础上在组合逻辑中间添加寄存器，以寄存器的输出作为边界划分，再行优化，使测试例可以更贴近实际情况。

5 测试结果及分析

根据上述介绍的方法，生成了一些测试例在自主研究的FPGA综合工具开发过程中使用，辅助判断综合工具的优化效果。

为测试不同代数型优化策略的效果，利用前文介绍的方法生成纯组合逻辑的待测试例，然后用这些待测试例在不同的策略下进行综合，将得到综合后的LUT数目进行比较，依此来抉择代数型优化策略，依此创建测试集1，简称集1，测试结果如表1所示。

由表1可知，集1中测试例随着输入数、输出数、逻辑层次的增加，测试例综合所得的LUT数目也随之增加，即表明本文所述方法可以通过可控制的输入数、输出数、逻辑层次来提供不同面积大小和复杂程度的纯组合逻辑测试例。表1中策略1是直接将逻辑表达式映射成6输入LUT的结果，策略2采用了代数型优化策略，即应用代数型的逻辑网表的分解（Decomposition）和公共表达式的提取（Factorization）。策略3在策略2的基础上，添加了代数型的网络重构（Re-Decomposition）和重新提取公共表达式（Re-Factorization）。由表1可知，相对于策略1而言，策略2和策略3较明显地降低了综合后的LUT数目。

表1 测试例在代数型优化策略下综合后的LUT数目

为测试布尔型优化策略的效果，选择一个组合逻辑的测试例，注入不同个数可被优化的布尔空间，且这些布尔空间由不同数量的变量构成不同的规模，最后生成一组新的待测试例集2，简称集2。例如表2中的测试例3是在待测试例中注入1个由9个变量构成的布尔空间，测试例12则是在测试例中注入6个布尔空间，这些布尔空间总共用到41个变量。将这组待测试例在不同策略下进行综合，所选策略除了代数型优化外还添加了布尔型逻辑优化，最后利用综合后的LUT数目比较找到更优的优化策略，测试结果如表2所示。

表2 同一测试例注入不同规模布尔空间在不同策略下综合后的LUT数目

表2中策略1和策略2与表1中所用策略相同。策略3和策略4除了代数型优化外，还添加了布尔型逻辑优化的策略。策略4和策略3的不同点在于策略4加强了对布尔空间的搜索与识别，使之能更有效地发现可被优化的布尔空间并对其进行优化。由表2可以看出，策略3优化效果要明显好于策略1和策略2，策略4可以较好地识别布尔型优化和代数型优化，因而优化效果优于策略3。并且由表2可以看到，随着注入的布尔空间个数增多，构成布尔空间的变量增多，产生冗余项也会越来越多，具体体现就是随着注入的布尔空间个数的增多和构成布尔空间变量的增多，策略1、策略2、策略3的综合后LUT数目也越来越多，表中数据呈上升趋势，而与之相对应的是，在策略4下综合后的LUT数目基本趋于稳定。在这种情况下，如果没有布尔型优化或者布尔型优化不佳，将对综合结果产生极大影响。

基于FPGA大容量的特点，对大容量测试例的测试是有必要的，同时代数型优化和布尔型优化应该是同时存在才符合更优的目标。依照前文的方法，生成一组较大容量的待测试例，使用的输入数为30，输出数为15，逻辑层次为7，在此基础上随机生成不同逻辑的具有较大面积的纯组合逻辑，并添加各种规模的可被优化的布尔空间，将这组待测试例在代数型优化和布尔型优化的组合优化策略下进行综合，比较综合后的LUT数目，可以选择更优的组合优化策略，依此创建测试集3，简称集3，测试结果如表3所示。

表3 较大面积组合逻辑测试例在不同策略下综合后的LUT数目

表3中的策略与表2中所用策略相同。由表3中可以看出，4种策略测试集3的测试例综合结果的变化趋势也与表2相似，即策略3优化效果要明显好于策略1和策略2，策略4优化效果优于策略3，即生成的大容量测试例可满足验证优化策略效果的目的，可以依此判断优化策略的好坏。

需要说明的是，虽然从表3中可以看出策略4比策略3的优化效果更好，但是还存在测试例在策略4下综合时间过长无法得到综合结果、而已有测试例都可以在策略3下得到综合结果的情况，所以目前利用代数型优化和布尔型优化组合的优化策略还有待进一步开发。

通过上述表格可以看出，在不停调整优化策略的过程中，优化效果在不断提升，这说明生成的测试例可以很好地辅助工具在开发过程中对于策略的抉择。

6 结论

本文介绍了一种优化FPGA综合效果的测试例自动生成方法，该方法通过可控制的输入数、输出数、逻辑层次，以及注入可被优化的布尔空间构成的可控制规模的“无关项”和“冗余项”实现生成测试例。该方法可以提供不同面积大小和复杂程度的纯组合逻辑测试例，也可以提供具有不同规模可被优化的布尔空间的测试例。生成的测试例可以用来测试FPGA综合中逻辑优化使用的各种策略是否得到预期的结果，依此选择最优策略优化电路面积，以协助FPGA综合工具的开发。

实验结果证明了本文所介绍的测试例自动生成方法所生成的测试例可以有效地测试和判断在FPGA综合工具开发过程中优化策略的优劣，可以对综合工具逻辑优化效果的开发提供有效驱动，辅助提高FPGA设计工具的质量。现有生成的测试例主要都是对于面积的优化，后续将主要针对综合性能的优化进行开发，针对逻辑层次和扇出进行规范，帮助FPGA设计工具实现面积和性能之间的优化平衡。