一种高效FPGA技术映射算法

摘要

本发明公开了一种高效FPGA技术映射算法，将技术映射划分为逻辑优化与结构优化，逻辑优化部分采用AIG模型以及balance、rewrite以及refactor等技术对电路进行优化；结构优化部分采用DAG模型，分为划分产生、划分选择以及LUT映射三步，划分产生采用了动态规划的思想，快速为每一个节点产生所有k-可行划分；划分选择基于一种迭代次数可以自适应改变的迭代启发式思想，通过多次向前遍历与向后遍历的迭代，最终选择出延时和面积同时被优化的划分集合，与此同时，本发明修正了节点面积流计算公式，提高了划分选择的随机性；LUT映射将划分选择产生的划分结合映射成为LUT网络。

说明书

技术领域

本发明涉及计算机技术领域，可用于FPGA中与电路结构无关的门级网络向与电路结构有关的LUT网络转换的技术映射问题。

背景技术

近年来，随着集成电路技术的飞速发展，现场可编程门阵列(FPGA，FieldProgrammableGateArray)因其具有集成度高、逻辑资源丰富、设计灵活以及使用范围广等特点在数字系统设计中得到了广泛的应用。

FPGA的设计流程，主要包括设计输入、行为综合、工艺映射、打包、布局和布线。其中，作为FPGA支持软件中关键的一步，技术映射引起了广泛的研究。

一个布尔电路的组合部分可以表示成一个DAG，G＝(V(G),E(G))，V(G)和E(G)分别表示DAG的节点集合和有向边集合，图中的一个节点v∈V(G)表示一个逻辑门、原始输入节点(PI)或者原始输出节点(PO)；图中的一条有向边e∈E(G)，以u＝head(e)为头，v＝tail(e)为尾，表示逻辑电路中节点u的输出和节点v的输入的一个信号；以v为尾的边的集合成为节点v的输入边iedge(v)；以v为头的边的结合成为节点v的输出边oedge(v)；PI节点没有输入边，PO节点没有输出边；支撑节点v的输入边的尾节点称为节点v的输入节点，表示为inode(v)；节点v的输出边的头节点称为节点v的输出节点，表示为onode(v)；如果|inode(v)|≤K，则称v是k-可行的；如果图中的每一个节点都是k-可行的，那么图就是k-约束的。

每一个边有一个相关的延时delay(e)；一条路径的长度就是沿该路径的所有边的延时之和；节点v的深度depth(v)是从PI节点到v的最长路径的长度；节点v的高度height(v)是从PO节点到v的最长路径的长度；PI节点的深度以及PO节点的高度都是0；边e的深度depth(e)是从PI节点到e的最长路径的长度，边e的高度是从PO节点到e的最长路径的长度，边的深度以及高度包含它自身的延时；图中最长路径的长度成为图的深度或者高度。

图中的每个节点每条边都有一个面积流来表示在其之前的子图的面积的估计值，表示为af，边e的面积流定义为：

$>af\left(e\right)=\frac{af\left(head\right(e))}{\left|oedge\left(head\right(e)\right)|};$>

节点v的面积流定义为：

$>af\left(v\right)=A_v+\underset{i\in iedge\left(v\right)}{\Sigma }af\left(i\right);$>

对PI或PO节点A_v等于0，对内部节点A_v等于1；v的一个锥图C_v被定义为包含节点v和它的某些非PI前驱节点的DAG的子图，节点v称为C_v的根。尾部在C_v内，头部在C_v外的边的集合称为C_v的输入边集记做iedge(C_v)；以v为头的边的集合称为C_v的输出边集记做oedge(C_v)，实际上C_v可以被当做一个节点，用于节点的inode,onode,height,depth,af,k-可行等定义都适用于锥图C_v。一个K-LUT可以用一个k-可行锥图实现，因此技术映射问题可以简化成为电路DAG(图G)选择一组k-可行锥图来覆盖，图1为一个将电路DAG转换为LUT网络的实例。

划分为图G中节点的划分，任意一条穿越划分的边e都有head(e)在集合X中，tail(e)在集合中，划分的体积为X集合中节点的个数，划分的面积流为穿越划分的边的面积流之和。

在有关基于LUT(LookUpTable)的FPGA技术映射算法，主要的一些研究成果也是来自于国外。根据研究的目标，FPGA的技术映射算法大致可分为以下四类：

1.延迟优化算法，其优化目标为尽可能的使实现电路的LUT的级数最小，国外这类算法中比较经典的算法包括FlowMap，MIS-pga-delay，DAG-map和EdgeMap等。

2.面积优化算法，其优化目为尽可能的是使实现电路的LUT的数量最少，国外这类算法中比较典型的算法有Practor，VisMap，Xmap，Mis-pga，Chortle-crf等。

3.功率优化算法，国外这类现有的经典算法有DvMap，Emap，PowerMap，PoweriMinMap等。

4.延迟和面积同时优化，通常情况下，面积优化和延迟优化往往相互矛盾、相互制约，因此往往是在延迟和面积中找一个平衡点来进行同时优化，这类算法中比较著名的主要包括CutMap，DAOMap、FlowMap-r等。

FlowMap算法是经典的以延时为优化目标的技术映射算法。该算法主要分为两个阶段：节点标记和LUT覆盖；在标记阶段，根据动态规划的思想，按照PI-PO的拓扑顺序对节点进行逐个标记，标记的值为该节点所在LUT的最小高度；在LUT覆盖阶段，根据标记阶段的结果，为节点选择最小高度划分，来进行LUT的覆盖，从而使得电路的关键路径最短。FlowMap算法可以再O(n)的时间内求得延时最优的划分，但是其对面积的优化却不够理想。

CutMap算法是对FlowMap算法的改进。CutMap算法也分为节点标记和LUT覆盖两个阶段；在LUT覆盖阶段的划分选择时，CutMap算法把关键路径上的节点和非关键路径上的节点区别对待：对关键路径上的节点求min-height划分，对非关键路径上的节点求min-cost划分，在保证延时最优的前提下，尽可能的提高对面积的优化。

ABC工具为加利福尼亚大学伯克利分校开发的一款集综合和技术映射为一体的FPGA综合工具，该工具主要使用了balance、rewrite、refactor、if以及fpga技术对电路进行综合和技术映射，其主要以效率为优化目标，大大提高了FPGA综合及技术映射的速度，并得到了广泛应用。由于ABC是一款追求效率的工具，而技术映射的质量优化又比较耗费时间，使得ABC不得不牺牲质量以换取技术映射效率的提高，因此ABC对技术映射的质量优化并不明显。

发明内容

针对现有技术的不足，本发明旨在提供一种高效FPGA技术映射算法，将技术映射分为逻辑优化和结构优化，逻辑优化部分采用AIG以及对应的操作将电路分解为二输入电路，结构优化部分基于一种迭代的启发式思想，通过一次一次的迭代，不断优化技术映射的结果；另外，结构优化部分还采用一种自适应的迭代次数，减少了不必要的迭代，优化了技术映射的效率。同时，结构优化部分对求取节点v的面积流公式进行了修正，以提高技术映射划分选择过程的随机性。

为了实现上述目的，本发明采用如下技术方案：

一种高效FPGA技术映射算法包括如下步骤：

S1逻辑优化：

1.1)初始化：为电路建立AIG图；

1.2)对步骤1.1)中得到的AIG图进行分解优化，得到二输入电路；

S2结构优化：

2.1)为步骤S1逻辑优化后得到的电路建立DAG图G，并设置最大迭代次数IMAX和执行结果连续不变的最大次数M；

2.2)为图G中每一个节点产生所有的k-可行划分，作为划分选择的集合；

2.3)判断是否已经达到迭代次数IMAX，如果是，则转至执行步骤2.8)，否则执行步骤2.4)；

2.4)判断执行结果是否连续M次不变，如果是，则转至执行步骤2.8)，否则执行步骤2.5)；

2.5)按照PI-PO的拓扑顺序向前遍历，为每一个节点选择最优划分；

2.6)按照PO-PI的逆拓扑顺序向后遍历，选择可以作为LUTroot的节点；

2.7)返回执行步骤2.3)；

2.8)利用划分选择的结果进行LUT映射。

需要说明的是，步骤1.2)的具体方法如下：

1.2.1)采用平衡(balance)技术，在保证面积不变的情况下优化电路时延。平衡技术包含两部分：基于树的布尔函数双分解(bi-decomposition)技术和布尔函数的树高化简技术，首先按照从AIG图的根节点到叶子节点的顺序利用双分解技术构造树，然后利用布尔代数的交换律、结合律和分配律对树高进行化简，在整个过程中，树的节点个数保持不变。

1.2.2)采用重写(rewrite)技术，删除电路中的冗余节点以及无效节点。rewrite首先要保证布尔函数功能不变，在此基础上，通过迭代，利用计算过的更小的子图来代替节点处的子图，以达到面积优化的目的。

1.2.3)采用重分解(refactor)技术，在保证时延不变的情况下优化电路的面积。refactor技术是rewrite技术的一种扩展，在rewrite技术之后，增加了重替代(resubstitution)技术和冗余去除(redundancyremoval)技术。其中重替代技术是利用网络中已经存在的节点来表达当前节点的功能；而冗余去除技术是删除那些与布尔网络功能无关的节点。这两项技术在rewrite技术的基础上进一步优化了电路的面积。

需要说明的是，步骤2.1)中所建立的DAG图G中，每个节点为一个门电路、PI节点或PO节点。

需要说明的是，步骤2.2)的具体方法如下：

从PI节点开始，按照PI-PO的拓扑顺序为每一个节点产生所有k-可行划分，产生k-可行划分具体按照下式：

$>f(k,v)={\otimes }_{u\in input\left(v\right)}^k\left[u+f\left(k,u\right)\right];$>

其中，代表与，+代表或，k为LUT的输入限制，input(v)表示节点v的输入集，u为节点v输入集中的一个节点，f(k,v)表示节点v的所有k-可行划分，f(k,u)表示节点u的所有k-可行划分。

需要说明的是，步骤2.5)的具体方法如下：

2.5.1)向前遍历初始化：将所有PI节点的深度初始化为0，对应的面积流初始化为0；PI节点输出边的深度初始化为1，对应的面积流初始化为0；

2.5.2)判断是否图G中所有的节点均已被访问，如果是，结束步骤2.5)，转至步骤2.6)，否则继续执行步骤2.5.3)；

2.5.3)按照PI-PO的拓扑顺序向前遍历，在图G中取未被访问的节点v，在节点v所有满足下式的划分中选择面积流最小的划分X_v作为最优划分：

depth(x)≤Odepth-height(v)；

x表示节点v的一个划分，depth(x)表示划分x的深度，Odepth表示最优深度，height(v)表示节点v的高度；

其中，节点v的划分的面积流计算如下：

$>af\left(v\right)=A_v+\underset{i\in iedge\left(v\right)}{\Sigma }af\left(i\right)+\xi ;$>

其中，ξ为任意小的随机数，iedge(v)表示节点v的输入边集合，A_v表示节点v本身对面积的影响；

2.5.4)更新节点v的深度和面积流分别为depth(X_v)和af(X_v)；

2.5.5)更新节点v的任意一条输出边e的深度为depth(X_v)+delay(e)，面积流为其中，delay(e)表示输出边e的相关时延，oedge(v)表示节点v的输出边集合；返回执行步骤2.5.2)。

需要说明的是，所述步骤2.6)的具体方法如下：

2.6.1)向后遍历初始化：初始化root集合为所有PO节点，并将所有PO节点的高度初始化为1；

2.6.2)判断是否图G中所有节点均已被访问，如果是，则结束步骤2.6)，否则继续执行步骤2.6.3)；

2.6.3)按照PO-PI的逆拓扑顺序，从图G中取出未被访问的节点v，如果v在集合root内，计算：

h＝max{height(e):e∈oedge(v)}；

其中，height(e)为节点v的输出边集合oedge(v)中的任意边的高度，h则为节点v的输出边集合中所有边的高度的最大值；

2.6.4)更新节点v在步骤2.5)中得出的最优划分X_v内的任意节点u的高度为height(u)＝max{height(u),h}，对于X_v的任意输入边e更新其高度height(e)＝max{height(e),delay(e)+h}，更新集合root为root∪inode(X_v)，inode(X_v)表示支撑节点v的最优划分X_v的输入边的尾节点；然后返回步骤2.6.2)。

需要说明的是，步骤2.8)的具体方法为：采用最终得到的集合root以及集合内每个节点的最优划分，对DAG图G进行LUT映射，形成最终的LUT网络。

本发明的有益效果在于：

1、本发明基于启发式算法，将技术映射划分为逻辑优化与结构优化，结构优化部分采用DAG模型，分为划分产生、划分选择以及LUT映射三步，划分产生采用了动态规划的思想，快速为每一个节点产生所有k-可行划分；划分选择基于一种迭代次数可以自适应改变的迭代启发式思想，通过多次向前遍历与向后遍历的迭代，不断优化技术映射的结果，并减少了不必要的迭代，优化了技术映射的效率，最终选择出延时和面积同时被优化的划分集合，相比与现有的延迟和面积同时优化的FPGA技术映射算法，本发明无论在技术映射的质量还是技术映射的效率上都有较大提高；

2、本发明修正了节点面积流计算公式，提高了划分选择的随机性。

附图说明

图1为技术映射概念的实例示意图；

图2为本发明的实施流程图；

图3为图2中的向前遍历步骤的实施流程图；

图4为图2中的向后遍历步骤的实施流程图。

具体实施方式

以下将结合附图对本发明作进一步的描述，需要说明的是，本实施例以本技术方案为前提，给出了详细的实施方式和具体的操作过程，但本发明的保护范围并不限于本实施例。

如图2所示，一种高效FPGA技术映射算法包括如下步骤：

S1逻辑优化：

1.1)初始化：为电路建立AIG图；

1.2)对步骤1.1)中得到的AIG图进行分解优化，得到二输入电路并输出；

S2结构优化：

2.1)为步骤S1逻辑优化后得到的电路建立DAG图G，并设置最大迭代次数IMAX和执行结果连续不变的最大次数M；

2.2)为图G中每一个节点产生所有的k-可行划分，作为划分选择的集合；

2.3)判断是否已经达到迭代次数IMAX，如果是，则转至执行步骤2.8)，否则继续执行步骤2.4)；

2.4)判断执行结果是否连续M次不变，如果是，则转至执行步骤2.8)，否则继续执行步骤2.5)；

2.5)按照PI-PO的拓扑顺序向前遍历，为每一个节点选择最优划分；

2.6)按照PO-PI的逆拓扑顺序向后遍历，选择可以作为LUTroot的节点；

2.7)返回执行步骤2.3)；

2.8)利用划分选择的结果进行LUT映射。

需要说明的是，步骤1.2)的具体方法如下：

1.2.1)采用平衡(balance)技术，在保证面积不变的情况下优化电路时延。平衡技术包含两部分：基于树的布尔函数双分解(bi-decomposition)技术和布尔函数的树高化简技术，首先按照从AIG图的根节点到叶子节点的顺序利用双分解技术构造树，然后利用布尔代数的交换律、结合律和分配律对树高进行化简，在整个过程中，树的节点个数保持不变。

1.2.2)采用重写(rewrite)技术，删除电路中的冗余节点以及无效节点。rewrite首先要保证布尔函数功能不变，在此基础上，通过迭代，利用计算过的更小的子图来代替节点处的子图，以达到面积优化的目的。

1.2.3)采用重分解(refactor)技术，在保证时延不变的情况下优化电路的面积。refactor技术是rewrite技术的一种扩展，在rewrite技术之后，增加了重替代(resubstitution)技术和冗余去除(redundancyremoval)技术。其中重替代技术是利用网络中已经存在的节点来表达当前节点的功能；而冗余去除技术是删除那些与布尔网络功能无关的节点。这两项技术在rewrite技术的基础上进一步优化了电路的面积。

需要说明的是，步骤2.1)中所建立的DAG图G中，每个节点为一个门电路、PI节点或PO节点。

需要说明的是，步骤2.2)的具体方法如下：

从PI节点开始，按照PI-PO的拓扑顺序为每一个节点产生所有k-可行划分，产生k-可行划分具体按照下式：

$>f(k,v)={\otimes }_{u\in input\left(v\right)}^k\left[u+f\left(k,u\right)\right];$>

其中，代表与，+代表或，k为LUT的输入限制，input(v)表示节点v的输入集，u为节点v输入集中的一个节点，f(k,v)表示节点v的所有k-可行划分，f(k,u)表示节点u的所有k-可行划分。

需要说明的是，如图3所示，步骤2.5)的具体方法如下：

2.5.1)向前遍历初始化：将所有PI节点的深度初始化为0，对应的面积流初始化为0；PI节点输出边的深度初始化为1，对应的面积流初始化为0；

2.5.2)判断是否图G中所有的节点均已被访问，如果是，结束步骤2.5)，转至步骤2.6)，否则继续执行步骤2.5.3)；

2.5.3)向前遍历按照PI-PO的拓扑顺序，在图G中取未被访问的节点v，在节点v所有满足下式的划分中选择面积流最小的划分X_v：

depth(x)≤Odepth-height(v)；

x表示节点v的一个划分，depth(x)表示划分x的深度，Odepth表示最优深度，height(v)表示节点v的高度；

其中，节点v的划分的面积流计算如下：

$>af\left(v\right)=A_v+\underset{i\in iedge\left(v\right)}{\Sigma }af\left(i\right)+\xi ;$>

其中，ξ为任意小的随机数，iedge(v)表示节点v的输入边集合，A_v表示节点v本身对面积的影响，一般取值为1；

2.5.4)更新节点v的深度和面积流分别为depth(X_v)和af(X_v)；

2.5.5)更新节点v的任意一条输出边e的深度为depth(X_v)+delay(e)，面积流为其中，delay(e)表示输出边e的相关时延，oedge(v)表示节点v的输出边集合；返回执行步骤2.5.2)。

需要说明的是，如图4所示，所述步骤2.6)的具体方法如下：

2.6.1)向后遍历初始化：初始化root集合为所有PO节点，并将所有PO节点的高度初始化为1；

2.6.2)判断是否图G中所有节点均已被访问，如果是，则结束步骤2.6)，否则继续执行步骤2.6.3)；

2.6.3)按照PO-PI的逆拓扑顺序，从图G中取出未被访问的节点v，如果v在集合root内，计算：

h＝max{height(e):e∈oedge(v)}；

其中，height(e)为节点v的输出边集合中的任意边的高度，h则为节点v的输出边集合中所有边的高度的最大值；

2.6.4)更新节点v的最优划分X_v内的任意节点u的高度为height(u)＝max{height(u),h}，对于X_v的任意输入边e更新其高度height(e)＝max{height(e),delay(e)+h}，更新集合root为root∪inode(X_v)，inode(X_v)表示支撑节点v的最优划分X_v的输入边的尾节点；然后返回步骤2.6.2)。

需要说明的是，步骤2.8)的具体方法为：采用最终得到的集合root以及集合内每个节点的最优划分，对DAG图G进行LUT映射，形成最终的LUT网络。

对于本领域的技术人员来说，可以根据以上的技术方案和构思，作出各种相应的改变和变形，而所有的这些改变和变形都应该包括在本发明权利要求的保护范围之内。