龙源期刊网 http://www.qikan.com.cn
一种基于ＳＡＴ的ＦＰＧＡ映射优化算法
作者：陆华奇
来源：《电脑知识与技术》2008年第35期
摘要：为了提高FPGA技术映射算法的质量，提出了一种基于布尔可满足性（SAT）的算法，在实现系统功能的前提下，可以将一个子电路映射到数量最少的查看表中。通过将该算法迭代应用于已经完成映射的电路局部，在许多情况下，可以使用更少的查看表来完成。 关键词：布尔可满足性；FPGA；再综合；映射优化；查看表
中图分类号：TP331文献标识码：A 文章编号：1009-3044(2008)35-2502-02 An Optimality of FPGA Mapping Algorithms Based on SAT LU Hua-qi
(Department of Computer Engineering, Huaiyin Institute of Technology, Huai’an 223003, China) Abstract: This paper attempts to quantify the optimality of FPGA technology mapping algorithms. We develop an algorithm, based on Boolean satisability (SAT), that is able to map a small subcircuit into the smallest possible number of lookup tables (LUTs) needed to realize its functionality. We
iteratively apply this technique to small portions of circuits that have already been technology mapped by the best available mapping algorithms for FPGAs. In many cases, the optimal mapping of the subcircuit uses fewer LUTs than is obtained by the technology mapping algorithm.
Keywords: Boolean Satisability; Resynthesis; Mapping Optimization; FPGA, Lookup Table 1 引言
FPGA是可重构的集成电路，其特点是由大量可编程的布线结构包围的可编程逻辑模块。目前大部分FPGA器件都包含基于K个输入查看表(K-LUT)的可编程逻辑模块，一个K-LUT含有2K个真值表配置位，因此K-LUT可以实现任意的K个输入功能。对于一个给定电路而言，实现给定电路的LUT数量决定了基于FPGA实现的尺寸和代价。因此，在FPGA CAD流程中最重要的的阶段之一就是技术映射，技术映射将一个优化过的电路描述映射到目标FPGA体系结构中的一个LUT网络中。
龙源期刊网 http://www.qikan.com.cn
在技术映射过程中，常常将技术映射看为覆盖问题。例如，在图1中给出了将一个电路映射到LUT的过程。图1a是初始的门级网络，图1b是使用4-LUT对初始网络的可能覆盖，图1c给出了由覆盖产生的LUT网络[1]。在所给出的映射中，标号为x的门同时属于两个LUT，即复制了x。有时，为了最小化LUT网络面积，必须复制门电路。
对于小的子电路来说，实现面积优化没有问题。设f(i0,i1,…,in)是任意函数，如果以3-LUT或2-LUT实现，可以使用图2所示的可配置虚拟网络（Configurable Virtual Network, CVN）来实现面积的优化。CVN是由连接到变量i0,i1,…,in的输入线与三个2-LUT组成。交叉位置允许LUT输入选择来自其它LUT的任意输入线或输出线。交叉点上的每一个“开关”由一个虚拟配置位进行配置，其中0代表交叉点是不连接的，而1表示交叉点是连接的。如同为每个2-LUT设置真值表配置位一样，通过控制虚拟配置位，可以枚举包含三个2-LUT的每一种可能的电路配置[2]。
在式(1)及(2)中，可以看到网络fnet的输出作为布尔表达式，其中表达式中包括变量i0, i1…, in、虚拟配置位V1…Vm及真值表配置位L1…Lo。在这两个式中，需要提出的是，对于i0,…, in所有的值来说，V1…Vm及L1…Lo的赋值对fnet(i0, i1…, in，V1…Vm，L1…Lo)引起的变化是否等同于f(i0, i1…, in)，这个问题可以从布尔可满足性（Boolean Satisfiability, SAT）中获得确切的答案[2]。给定在交集范式（Conjunctive Normal Form, CNF）中的一个布尔表达式，其中表达式是由句子的一个乘积组成的，而每个句子是由文字的和组成的，试图对变量进行赋值，使每个句子至少有一个文字的值为真。
2 对面积的再综合
所谓针对面积的再综合，必须以原有的LUT电路为基础，其目的是在维持原有功能的基础上，试图降低电路图中的LUT数量。 2.1 将综合问题转化为布尔可满足性
确定一个n可达的锥面是否能用X个n-LUT实现的方法将其进行再综合到用X-1个或更少的n-LUT的n可达锥面中，验证的方法是使用SAT。完成的过程时首先生成一个比初始的锥面所包含的LUT数量更少的n可达的没有扇出的锥面（Fanout Free Cone, FFC），然后，将代表初始锥面功能的真值表赋给CNF表达式。如果该CNF表达式是可满足的，再综合成一个新的FFC是可行的。
为了更清晰地表达这个过程，图3中的3a是由三个2-LUT组成的初始锥面，其功能实现了一个三输入。由于该锥面只有三个输入，将图3a再综合成图3b并节省一个LUT是可行
龙源期刊网 http://www.qikan.com.cn
的。为了确定是否可以从图3a再综合到图3b，图3b必须转换成一个CNF表达式，如果表达式是满足的，则再综合是可行的[3]。
CNF等式能够表达电路的所有合法向量，例如，在图4中，当且仅当图4a中的信号A、B及Z与一个AND门的功能相对应时（如（A=0, B=X, Z=0）、（A=X, B=0, Z=0）或（A=1, B=1, Z=1）），式(1)才满足。与此相同，只有类似（A=1, B=1, C=0, Z=1, Y=0）的合法向量时，式(2)才满足。
F1(A,B,Z)=(A+Z)·(B+Z)·(A+B+Z) （1）
F2(A,B,C,Z,Y)=(A+Z)·(B+Z)·(A+B+Z)·(Z+Y)·(C+Y)·(Z+C+Y) （2）
为了实现这种再综合的检查，首先应该形成CNF的等式，其次，应该根据锥面的真值表在CNF等式中的输入与输出变量。最后，利用一个SAT解决器来检查可满足的赋值[4]。例如，将一个两输入的锥面映射到图4b的电路上，将C设置为配置位。为了检查两输入的函数f(1,1)=1是可达的，可以通过判断是否满足F2(A=1,B=1,C,Z,Y=1)=1来实现。很明显，当C=1时其返回值为真值。但是，这只能说明f(1,1)=1是可行的，即只是一个真值表的值。为了在整个锥面上验证一个再综合的电路，即验证整个真值表，其CNF等式将反复计算2n次，以形成一个新的CNF等式，其中n为所映射锥面的扇入数量。基本电路CNF等式的每一次重复计算都对应着锥面真值表中的一个值。因此，需要强调的是，为了检查初始的锥面是否能够与再综合的电路相匹配，可以通过在一个新的CNF式上完成SAT的检验来实现。
再返回到图3中初始的LUT例子，下面的步骤将给出如何实现这些转换。图5是图3b的细节图，该图清楚地给出了CNF构造的内部连线及配置位。在这些步骤中，f代表需要进行再综合的锥面的函数，Xi代表输入向量x1x2x3=i和fi=f(Xi)。
步骤1：针对再综合电路中的每一个元素各生成一个CNF等式，见式(3)及(4)。 （3） （4）
步骤2：从式(3)及式(4)中形成电路CNF等式。式(5)是一个与电路的输入与输出（x1-3, f）、内部连线(M)及配置位(L1-8)变量相关的表达式。 Gresynth(Xi，fi)=GLUT1·GLUT2 （5）
步骤3：重复式(5)并根据f函数对输入与输出变量进行约束。
龙源期刊网 http://www.qikan.com.cn
（6）
在式(6)中，使用在每一个Gresynth(Xi,fi)实例中的同一变量（L1-8）来代表配置位，在每一个实例中的所有其他信号都有不同的变量[5]。这就保证了在每一个真值表的值都有唯一的配置位。最后，如果锥面与再综合的结构是对应的，式(6)通过SAT检验后将返回真值。 2.2 生成锥面
许多算法可以生成并存储图中所有的再综合锥面，其中有一种算法是从PI到PO按照拓扑排序遍历图来生成再综合锥面。在每一个内部LUT中，通过与输入LUT的锥面结合来产生新的锥面。本文中，如果锥面所有的输入不超过(n+e)，其中n为最大的再综
合锥面扇入数，e为扩充值，则锥面产生算法与其他锥面结合。只有将e设为足够高的数值，该启发式算法才可以加速锥面生成的过程，而不会严重影响再综合解决方案的质量。 对于有1个以上扇出的锥面必须特别处理。例如图6，如果将a到e的LUT再综合到f到g的LUT，则必须将c到e的LUT复制，以保持LUT c的扇出。这样，该再综合算法总的节约只有1个，而如果LUT c没有扇出，则会节约3个。 3 结束语
本文提出一种可以帮助理解最新FPGA映射算法最优性的方法，主要思想是将电路的每个部分再综合，直到其达到最优状态。下一步的工作是寻找改进该局部优化再综合的方法。通过测试自定义硬件加速方法以改善锥面再综合的运行时间，研究使用don’t care来降低CNF的复杂度并增加再综合研究领域的敏捷性。
参考文献：
[1] Altera.Component selector guide[S].ver 18.0,2007.
[2] Chai D,Jiang J,Jiang Y,et al.MVSIS 2.0 Programmer's Manual[R].UC Berkeley,Technical report,2003.
[3] Farrahi,Sarrafzadeh M.Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2003,13(11):1319-1332.
龙源期刊网 http://www.qikan.com.cn
[4] Cong J,Wu C,Ding Y.Cut ranking and pruning: Enabling a general and efficient FPGA mapping solution[C].FPGA,2007:29-35.
[5] Xilinx.Virtex-ii complete data sheet[S].ver 5.3,2007.
