面向AIC结构的FPGA映射工具

江政泓 林 郁 黄志洪 杨立群 杨海钢

①（中国科学院电子学研究所可编程芯片与系统研究室 北京 100190）

②（中国科学院大学 北京 100049）

面向AIC结构的FPGA映射工具

江政泓①②林 郁①黄志洪①杨立群①②杨海钢*①

①（中国科学院电子学研究所可编程芯片与系统研究室 北京 100190）

②（中国科学院大学 北京 100049）

探索新的现场可编程门阵列（FPGA）逻辑单元结构一直是FPGA结构研究的重点方向，与非逻辑锥（AIC）作为一种新的逻辑结构成为FPGA新结构的希望。然而实现高效且灵活的映射工具同样是研究FPGA新结构中的重点环节。该文实现了一个面向AIC结构的FPGA映射工具，与当前映射工具相比，具有更高的灵活性，能够支持AIC结构参数的调节，辅助支持进行AIC单元结构的探索改进。同时，该文提出的AIC映射工具与原工具相比，面积指标提高了33%～36%。

现场可编程门阵列；与非逻辑锥；映射

1 引言

在现场可编程门阵列（Field Programmable Gate Arrays，FPGAs）的技术发展中，改善面积、性能和功耗等指标一直是研究的重点［1］。很多新的嵌入模块结构和研究结果被不断提出，例如嵌入式存储器［2］（BRAM）和数字处理器单元（DSP）等，甚至功能更加强大的微处理器核心［3，4］（MCU）也被作为组件嵌入到FPGA芯片中。然而，查找表（Look-Up Table，LUT）作为FPGA的最基本最核心的单元，二三十年来却没有根本性的变化。

传统的查找表通过合理的SRAM配置来实现特定功能，具有非常高的灵活性。对于一个K输入的LUT，一共有2K个SRAM配置位，因此存在 22K种不同的配置方案，可以实现 22K种不同的功能。如此庞大的功能集合，可以实现K输入下的任意逻辑功能，并且极大地简化了FPGA自动流程CAD（Computer-Aided Design）中的映射过程。但是，传统查找表具有如此强大的灵活性是以电路面积、延迟和功耗为代价的。学术界和工业界都一直研究如何有效地改善LUT结构［57］-。

2012年，瑞士洛桑理工大学的Parandeh-Afshar等人提出了一种新的逻辑结构来替代查找表作为FPGA的基本逻辑单元［8］，这种新的逻辑结构称为“与非逻辑锥”（And-Inverter Cones，AIC）。AIC逻辑单元在某些应用电路的性能评价指标上优于查找表，成为查找表作为FPGA基本单元的有力挑战者［9］。然而，在最新的研究［10］中发现，AIC逻辑结构在实际的电路结构中仍存在众多的不足之处，仍有许多方面需要进一步的研究和探索。

针对AIC的结构特点以及未来的结构探索需求，本文提出并实现了一款新的FPGA映射工具，与文献［8，9］中所使用的映射工具相比较，新的映射工具具有以下特点：（1）支持查找表或者AIC逻辑单元两种不同结构FPGA的映射，同时还能实现两种单元混合的异质结构FPGA的映射。（2）支持AIC逻辑单元的不同参数约束，能够有效支持AIC逻辑单元的结构参数探索。（3）与现有的AIC映射工具相比，新映射工具实现相同功能的用户电路可以平均少使用33%的逻辑单元数，具有更好的面积指标。

2 AIC逻辑单元结构参数

文献［8，9］中所采用的与非逻辑锥（AIC）结构如图1所示，是一种二进制与非门树，采用两输入与门和非门作为基本结点，每个与门的输出都有一个多路选择器（MUltipleXor，MUX）选择是否对信号进行反向，如A节点所示。通过多层级的与非门单元结构的级联，构成了一个完整的与非门逻辑锥。为了提高与非门逻辑锥的灵活性，对每个逻辑锥的第1层可配置与非门进行了强化，在与门的输入端也增加了一组可配置MUX和非门单元，如B节点。同时，AIC单元结构中的每一个A类型节点都能够输出到单元外部，因此，与传统的查找表结构相比，除了内部结构的不同，AIC单元结构还有多输入与多输出的端口特征。

通过图1中的结构展示和以上对AIC单元结构的描述，我们可以了解AIC具有多个不同的结构参数，通过对这些结构参数的实验探索，可以精简现有结构的冗余，提高单元结构的性能和面积指标。表1总结了当前AIC单元结构中可以直接探索的结构参数。

3 AIC逻辑单元的映射原理与实现

本文所采用的AIC映射工具是在伯克利的开源软件ABC上实现的［11］，仍然采用传统查找表的映射方法和流程，结合AIC逻辑单元的结构特点，实现AIC逻辑单元的映射过程。

图1 AIC逻辑单元结构

表1 AIC单元的结构参数

3.1 映射中的基本概念

对于任何一个逻辑电路的组合逻辑部分，都可以抽象成一个有向无环图（Directed Acyclic Graph，DAG），图中每一个结点v都代表一个逻辑门或者输入/输出端口，其中CIs （Combinational Inputs）代表组合逻辑电路的输入端口（包括电路的原始输入PI和电路中寄存器的输出端口），COs （Combinational Outputs）代表组合逻辑电路的输出端口（包括电路的原始输出PO和电路中寄存器的输入端口），node表示具有实际逻辑功能的逻辑门。

传统映射算法的本质就是使用割子图（Cut）来对DAG图进行分割，将整个电路网络划分成一个个独立的Cut，而每个Cut实际对应成一个查找表单元，实现从门级网表电路到以查找表为单元的电路的转变。一般习惯上，使用Cv代表以结点v为根节点的Cut，Input（Cv）代表Cut的所有输入结点。在传统的查找表结构映射过程中，由于一个K输入的查找表仅能实现K个输入下的任意逻辑功能，因此，要求如果一个Cut满足该端口数目约束条件，那么就称该Cut为“K-feasible”。

3.2 基于枚举方法的AIC映射算法

与传统的穷尽枚举映射方法不同，ABC工具采用的是Priority-Cuts算法。该算法在与传统的穷尽枚举算法相比，能够在不损失性能和面积的前提下，有效地降低PC的内存使用率，减少整个映射过程的运行时间［12］。

3.2.1 枚举过程（Cut enumeration）枚举过程是整个映射算法的基础，为网络中所有的结点 v生成Cuts，后续的前向遍历和后向遍历步骤以枚举过程生成的Cuts为基础，进行筛选排序和递归组合等过程实现逻辑网表到 FPGA逻辑单元网表的转换。Priority-Cuts算法中采用文献［13］描述的方法来实现Cuts的枚举过程。

在传统的查找表映射中，要求所有的Cuts都是满足输入数目小于K的约束，即“K-feasible”。然而如图1所示，对于AIC结构来说，仅有输入个数的约束是不够的，因为，D-AIC结构中最多只有D层可配置与非门，如果一个Cut内部包含的AIG（And-Inverter Graph）级数超过D就无法使用D-AIC单元来实现，因此，在输入约束之外，AIC的Cut枚举过程还需要增加一个Cut内部AIG子图的深度约束，即aigdepth（u∪v）≤D，称之为“D-feasible”。

3.2.2 映射的前向遍历（forward traversal）在传统的映射方法中，Cuts的枚举过程是独立的，是首先计算出整个网络中所有结点的所有符合输入约束条件的Cuts，然后保存下来，再开始进行前向遍历过程，计算出每个Cut的逻辑深度和逻辑面积值，最终为每个结点v获取其最优的Cut，即BestCv。Cut的逻辑深度使用式（1）计算获得，而逻辑面积使用经典的“Area-Flow”方法进行评估，由式（2）获得

AIC映射工具在Priority Cuts算法前向遍历方法的基础上，增加了AIC结构特有的约束，实现了AIC映射的前向遍历过程。首先，每个结点不再保存所有的Cuts，而是仅保存排序后的前（4C≤C≤8）个有效Cuts。那么，根据3.2.1节中描述的Cuts枚举方法，每个结点根据其扇入结点的Cuts集合进行Cuts枚举，如此，由于扇入结点Cuts集合的不完备，每个结点并未实现Cuts的穷尽枚举，减小了程序的计算量，同时降低了内存的占用。然而，Cuts集合的不完备并不会降低映射的性能［12］。其次，和传统的查找表映射不同，除了要求Cuts符合输入数目约束之外，还要符合Cuts内部可配置与门级数约束（a igdepth （Cv）≤ D）。

3.2.3 映射的后向遍历（backward traversal）

完成前向遍历之后，电路网络中的每个结点v均获得了自己的BestCv及其对应的逻辑深度和面积值。后向遍历则以前向遍历获得的BestCv信息，完成逻辑网表到FPGA单元网表的最终转换过程。

后向遍历从电路网表的输出（COs）开始，以反拓补顺序向输入端口（CIs）进行。在整个后向遍历的初始阶段，整个网路中仅有输出端口（COs）具有可见性，映射队列（frontier）为空。然后，将COs加入映射队列F，从F中取出一个结点，选择该结点的BestCv作为该结点的映射方案（mapping solution），该BestCv将作为一个真实的AIC单元（或查找表）出现在最终电路中。而BestCv的输入结点作为AIC单元（或查找表）的输入端口，需要和其他的AIC单元（或查找表）进行连接，因此，具有可见性，添加到映射队列F中。最后，不断地重复上述过程，直到映射队列为空。

4 实验结果

本文在ABC程序的基础上，进行开发实现了一款全新的AIC映射工具。新映射工具能够支持AIC逻辑层数，独立输入数目，最低输出层次和有效输出数目等参数的可配置，而原映射工具却不支持，因此，仅采用6-AIC为对象进行实验对比，比较两个映射工具映射结果的面积和速度指标。

实验从学术界公认的两个测试集VTR［14］和MCNC［15］中各挑选出5个具有代表性的电路作为实现的测试电路集。实验将测试电路输入到新/旧映射工具中得到映射结果，然后再将映射结果送到VPR［14］程序中进行物理综合，最后得到一个面积和延时的数据值。面积恢复优化是FPGA映射过程中用于减少面积的一种有效手段，常常在进行首轮映射过程后，在进行一次或多次带有面积恢复优化功能的映射迭代过程，从而改善映射结果的面积指标。

4.1 不带面积恢复（area-recovery）的实验对比

图2展示了经过新旧两种映射工具映射后电路在关键路径延迟和占用面积值上的比较。

从图2的可以看出，和文献［8，9］的映射工具相比，新映射工具在电路映射结果的性能指标比原映射工具要略逊一筹，关键路径延迟平均增加了4%。而图2中展示的映射电路的面积指标却显示出了完全不同的趋势，新的AIC映射工具在所有的被测电路上都具有更优的面积结果，新映射工具在映射结果的面积指标上平均提高了35%。

仔细对两个映射工具的电路映射结果进行分析，得到以下结论：

（1）AIC单元结果具有多输出的特性，新的映射工具在映射过程中采用贪婪算法，尽可能地去对AIC的输出引脚进行使用，大大提高了AIC单元的利用率，从而减少了最终映射结果中6-AIC单元的总数，提高了面积指标。

（2）由于采用贪婪算法来提高AIC多输出引脚的利用率，导致映射过程中忽略了其对关键路径的影响，使得映射反向过程中造成关键路径改变，从而导致关键路径指标的下降。

4.2 采用面积恢复优化的实验对比

作为映射过程提高面积性能的重要手段，新的映射工具也支持采用面积恢复优化功能来进一步提高映射结果的面积指标。图3展示了新映射工具在开启面积恢复优化功能前后映射结果的对比。

从图3的数据可以看出，面积恢复优化功能确实能非常有效地提高映射结果的面积，与前一节中未使用面积恢复优化功能的映射结果相比，面积恢复优化功能平均提高了40%的面积指标。如果对映射结果数据进行深入分析，会发现与前一节的映射结果比较，开启面积恢复优化功能后，映射工具更加偏向于选择小的AIC单元来实现映射结果，以期进一步提升6-AIC单元的内部利用率，减少最终映射结果中所使用到6-AIC数目，提高映射结果的面积指标。然而，更好的面积指标是以降低电路的总体性能为代价的，从图3可以看出，开启面积恢复优化功能后，映射电路的平均性能下降了9%。

因此，从上述的数据和结果分析来看，如果设计者是以时序性能为优先设计约束，那么采用无面积恢复优化功能的映射流程能获得相对较好的性能指标。而如果设计者更加侧重于整体结果的面积参数，那么采用带有面积恢复优化功能的映射流程会带来非常优异的面积指标。

5 结束语

本文以开源软件ABC的映射程序为基础，结合AIC单元的结构特征，实现了一款全新的AIC结构映射工具。与文献［8］中使用的映射工具相比，新的AIC映射工具具有更高的灵活性，能够支持AIC结构单元进行更多的结构参数探索改进。除了灵活性上的改进，新的AIC映射工具在映射结果上还有35%的面积性能提升。目前映射结果与原映射工具相比，虽然在面积之比上有了很大的提高，但是在速度指标上却略有损失，后续需要进一步改善映射结果的速度结果。

图2 新旧映射工具的映射结果对比

图3 新映射工具在开启面积恢复优化功能前后电路性能和面积的对比

［1］ Ian K and Rose J. Measuring the gap between FPGAs and ASICs［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2007，26（2）：271-285.

［2］ Ngai T，Rose J，and Wilton S. An SRAM programmable field-configurable memory［C］. Proceedings of the IEEE Custom Integrated Circuits Conference，Santa Clara，CA，1995：499-502.

［3］ Rui Jia， Lin Y，Guo Z，et al.. A survey of open source processors for FPGAs［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL），Munich，2014：521-526.

［4］ Altera Corporation. Excalibur device overview DSEXCARM-2.0［OL］. http：//media.digikey.com/pdf/Data Sheets/Altera PDFs/EPXA1，4，10 Excalibur.pdf，2002.

［5］ Hutton M，Schleicher J，Lewis D， et al.. Improving FPGA performance and area using an adaptive logic module［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL），Belgium，2004：135-144.

［6］ Lewis D，Ahmed E，Baeckler G，et al.. The stratix II logic and routing architecture［C］. Proceedings of the 2005 ACM/ SIGDA 13th ACM International Symposium on Field-Programmable Gate Grrays，Monterey，2005：14-20.

［7］ Jiang Z，Lin Y，Yang L，et al.. Exploring architecture parameters for dual-output LUT based FPGAs［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL），Munich，2014：436-441.

［8］ Parandeh-Afshar H，Benbihi H，Novo D，et al.. Rethinking FPGAs：elude the flexibility excess of LUTs with and-inverter cones［C］. Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays，Monterey，2012：119-128.

［9］ Parandeh-Afshar H，Zgheib G，Novo D，et al.. Shadow and-inverter cones［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL），Porto，2013：1-4.

［10］ Zgheib G，Yang L，Huang Z，et al.. Revisiting and-inverter cones［C］. Proceedings of the 2014 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays，ACM，Monterey，2014：45-54.

［11］ Brayton R and Mishchenko A. ABC：an academic industrialstrength verification tool［C］. Computer Aided Verification，Edinburgh，2010：24-40.

［12］ Mishchenko A， Cho S，Chatterjee S，et al.. Combinational and sequential mapping with priority cuts［C］. IEEE International Conference on Computer-Aided Design，San Jose，2007：354-361.

［13］ Cong J，Wu C，and Ding Y. Cut ranking and pruning：enabling a general and efficient FPGA mapping solution［C］. Proceedings of the 1999 ACM/SIGDA Seventh International Symposium on Field Programmable Gate Grrays，Monterey，1999：29-35.

［14］ Luu J， Goeders J，Wainberg M，et al.. VTR 7.0：Next generation architecture and CAD system for FPGAs［J］. ACM Transactions on Reconfigurable Technology and Systems（TRETS），2014，7（2）：DOI：10.1145/2617593.

［15］ Yang S. Logic synthesis and optimization benchmarks User Guide， version 3.0［OL］. http：//ddd.fit.cvut.cz/prj/ Benchmarks/LGSynth91.pdf，1991.

江政泓： 男，1990年生，博士生，研究方向为FPGA架构开发、FPGA的映射算法.

林 郁： 男，1982年生，助理研究员，研究方向为FPGA架构开发、FPGA的CAD辅助设计、FPGA高层综合、高性能计算等.

黄志洪： 男，1984年生，助理研究员，研究方向为可编程逻辑结构研究、嵌入式存储器结构研究.

杨立群： 女，1989年生，博士生，研究方向为FPGA架构开发.

杨海钢： 男，1960年生，研究员，研究方向为数模混合信号集成电路设计、超大规模集成电路设计等.

Mapper for AIC-based FPGAs

Jiang Zheng-hong①②Lin Yu①Huang Zhi-hong①Yang Li-qun①②Yang Hai-gang①

①（System on Programmable Chip Research Department， Institute of Electronics，Chinese Academy of Sciences，Beijing 100190，China）
②（University of Chinese Academy of Sciences，Beijing 100049，China）

Exploring a new logic element of Field Programmable Gate Array （FPGA） is always a key field in FPGAs' research，while And-Inverter Cones （AIC） is the most promising one. Implementing a highly-efficient and highly-flexible mapping tool is also an important part of exploring new FPGA architecture. In this paper，a new mapper for AIC-based FPGA is implemented. Compared with an existing mapper，the new mapper has much higher flexibility，and supports adjustments of AICs' architectural parameters to assit the design space exploration of AIC. Meanwhile，the new mapper provides area results 33%～36% better than the original mapper.

Field Programmable Gate Array （FPGA）；And-Inverter Cones （AIC）；Technology mapping

TN402

A

1009-5896（2015）07-1769-05

10.11999/JEIT141403

2014-11-20收到，2015-03-16改回，2015-06-01网络优先出版

国家自然科学基金（61404140，61271149，61106033）资助课题

*通信作者：杨海钢 yanghg@mail.ie.ac.cn