一种基于时序的加/减法器组优化方法

胡平科　余建德

摘要：针对现场可编程门阵列（Field Programmable Gate Array，FPGA）电路模块中混合加/减法器组的时序优化问题，本文提出了一种在寄存器传输级（Register-Transfer-Level，RTL）综合优化阶段考虑加/减法器的输入端口数据位时延的正负矩阵优化方法，有效地利用了FPGA芯片中的进位链结构。在FPGA公司软件工具平台上的算法实现和芯片测试结果显示，这种正负矩阵优化方法相比于传统方法取得了很好的时序优化效果。

关键词：混合加/减法器组；RTL综合；输入端口数据位时延；正负矩阵

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）18-0221-02

近年来云计算、人工智能等方面的技术越来越火热，在性能、上市时间、成本、稳定性和长期维护方面拥有先天优势的FPGA也备受关注。

EDA（Electronic design automation）工具作为FPGA电路设计的核心工具，采用自顶向下的设计方法。使用行为级描述语言（verilog HDL或VHDL）将用户的需求转换成EDA工具的输入，再通过EDA工具的RTL综合优化、门级优化、布局布线、仿真与调试等步骤，完成整个电路模块的设计。

针对加/减法器的优化是EDA工具在RTL综合优化过程中不可或缺的一部分。目前已有的针对加法器优化的方法主要分两类：一类是针对两输入端口加法器的内部实现进行优化，如超前进位加法器、进位保留加法器、进位选择加法器等，通过优化进位链上的结构来达到优化时序的目的；另一类是针对多输入端口加法器的输入端口进行优化，如树型加法、Sklansk加法、Kogge-Stone加法、Brent-Kung加法等，通过树型化的思想来减少路径上的延时。本文针对电路模块中混合加/减法器组的时序问题，提出了一种基于输入端口数据位时延对加/减法器进行优化的方法。它通过考虑一组可重构的加/减法器中的每一个输入端口数据位的时延（即数据的到达时间），重新构建一组加/减法器，并替代原加/减法器组，优化电路模块的时序，使从加/减法器组的输入到输出的最大延时最小。

1加/减法器优化时的时序问题

在RTL电路综合过程中，对一组加/减法器进行优化是一个很常见的问题。通常对一组加/减法器的优化方法是，将一组加/减法器树型化，使得逻辑电路的物理级数最小化，达到优化RTL逻辑电路的目标。例如，有一组链状的加/减法器“al+a2-a3-a4”树型化后如式1所示：

（a1+a2）-（a3+a4） （1）

然而一个物理级数最少的电路在时序上却不一定是最好的。例如，式1中若‘al+a2计算出结果时，a3的数据已经到达，但a4的数据仍未到达。则此时先用‘al+a2的结果减去a3，然后再和a4相减，电路级数会多一级，但时序反而变好。如式2所示：

（（a1+a2）-a3）-a4 （2）

更进一步地，如果式2中的输入端都为6位，a4[2：0]的数据比a3[2：0]先到达；a3[5：3]的数据比a4[5：3]先到达。此时式2的时序也将不再是最好的。其最好时序的运算顺序如式3所示：

（（al+a2）-{a3[5：3]，a4[2：0]}）-{a4[5：3]，a3[2：0]} （3）

由此可见，在加/减法器树型化思想的基础之上，需要一种基于输入端口数据位时延的加/减法器的化优化方法，考虑每一位输入的时延对RTL电路时序的影响，最大化地优化RTL电路中的时序。

2基于时延的加法器进行优化

该优化过程是将一组加/减法器的所有输入端口数据位放人正值和负值两个矩阵上；然后对这两个矩阵进行一些优化处理（如优化连续相同值、抵消正负值等）；最后根据输入端口数据位的时延排序并生成多个两输入端加法器。其中，输入端口数据位矩阵中的一行相当于是加法器的一个输入端口，且高位在前；而它的列则包含了同一位置上的所有输入端口数据位。其具体实现步骤如算法2-1所示。

3实验结果分析

本文中提到的所有算法都使用C++程序设计语言实现。为了对比，同时实现了基于最短路径的树型加/减法器优化算法和基于输入端口数据位时延的加/减法器优化算法。算法在上海安路信息科技有限公司的商用FPGA软件工具TangDynas-ty3.0（TD3.0）上进行测试。为了测试本文中提出的算法在实际应用中的可适应性，考虑实际应用中的各种可能的情况，在本次实验中增加了测试用例的随机性。从两个方面对算法的优化结果进行对比：

一方面，加/减法器个数（num=4）不变；所有输入端口的位宽在指定的范围（[1，bits]）内随机生成，bits取值范围为[4，128]；输入端口的时序约束在[1ns，12ns]内随机生成；测试随着指定的位宽范围（即bits值）增大时，其时序优化结果将如何变化。其最终的优化结果如图1所示。

另一方面，加/减法器的所有输入端口的位宽在指定的位宽范围（[1，bits]）内随机生成，取bits=8；输入端口的时序约束在[1ns，10ns]内随机生成；测试随着加/减法个数（hum）在[4，128]范围内增长时，其时序优化结果将如何变化。其最终的优化结果如图2所示。

上述两个方面的测试是在上海安路信息科技有限公司的FPGA软件平台TD3.0下完成的。从图1和图2中可以看出，slack（Timing）折线基本都在slack（Tree）折线之上，这表明在不同输入端口的位宽或者不同加/减法器个数的情况下，基于输入端口数据位时延的加/减法器优化算法优化后的最小slack普遍都要大于基于最短路径的树型加/减法器优化算法优化后的最小slack；而slack值越大说明电路模块的时序优化得越好。因此，基于输入端口数据位时延的加/减法器优化能得到更好的时序电路。

4结束语

本文针对EDA工具中的RTL综合优化问题展开研究。在加/减法器的时序优化问题上，做出了以下贡献。一方面，与针对单个加减法内部进行优化的超前进位加法器、进位保留加法器、进位选择加法器等优化方法不同，本文提出的优化方法是针对相关联的一组加减法器进行优化。另一方面，与一组加减法器进行输入端口重新组合的树型加法、Sklansk加法、Kogge-Stone加法、Brent-Kung加法等方法不同，本文提出的優化方法是基于所有输入端口中的每一个数据输入位时序来驱动优化的，同时利用了FPGA器件中的进位链延时短的优点。在FP-GA公司软件工具平台上的算法实现和芯片测试结果显示，这种正负矩阵优化方法相比于传统方法取得了很好的时序优化效果。endprint