一种高效fpga技术映射算法
一种高效fpga技术映射算法
【技术领域】
[0001] 本发明设及计算机技术领域，可用于FPGA中与电路结构无关的口级网络向与电路 结构有关的LUT网络转换的技术映射问题。
【背景技术】
[0002] 近年来，随着集成电路技术的飞速发展，现场可编程口阵列（FPGA，Field Programmable Gate Array)因其具有集成度高、逻辑资源丰富、设计灵活W及使用范围广 等特点在数字系统设计中得到了广泛的应用。
[0003] FPGA的设计流程，主要包括设计输入、行为综合、工艺映射、打包、布局和布线。其 中，作为FPGA支持软件中关键的一步，技术映射引起了广泛的研究。
[0004] -个布尔电路的组合部分可W表示成一个046,6=(￥(6)，6(6))，八6巧蛇(6)分别 表示DAG的节点集合和有向边集合，图中的一个节点veV(G)表示一个逻辑口、原始输入节 点（PI)或者原始输出节点（P0);图中的一条有向边eEE(G)，Wu = head(e)为头，v = tail (e)为尾，表示逻辑电路中节点u的输出和节点V的输入的一个信号；Wv为尾的边的集合成 为节点V的输入边iedge(v); Wv为头的边的结合成为节点V的输出边oedge(v) ;PI节点没有 输入边，P0节点没有输出边;支撑节点V的输入边的尾节点称为节点V的输入节点，表示为 inode(v);节点V的输出边的头节点称为节点V的输出节点，表示为onode(v);如果I inode (V) I卽，则称V是k-可行的；如果图中的每一个节点都是k-可行的，那么图就是k-约束的。
[0005] 每一个边有一个相关的延时delay(e);-条路径的长度就是沿该路径的所有边的 延时之和；节点V的深度depth(v)是从PI节点到V的最长路径的长度;节点V的高度height (V)是从P0节点到V的最长路径的长度;PI节点的深度W及P0节点的高度都是0;边e的深度 depth(e)是从PI节点到e的最长路径的长度，边e的高度是从P0节点到e的最长路径的长度， 边的深度W及高度包含它自身的延时；图中最长路径的长度成为图的深度或者高度。
[0006] 图中的每个节点每条边都有一个面积流来表示在其之前的子图的面积的估计值， 表示为af，边e的面积流定义为：
[0007]
[000引节点V的面积流定义为：
[0009]
[0010]对PI或P0节点Αν等于0,对内部节点Αν等于l;v的一个锥图Cv被定义为包含节点V和 它的某些非PI前驱节点的DAG的子图，节点V称为Cv的根。尾部在Cv内，头部在Cv外的边的集 合称为Cv的输入边集记做iedge(Cv) ; Wv为头的边的集合称为Cv的输出边集记做oedge (Cv)，实际上Cv可W被当做一个节点，用于节点的inode，onode，height，(kpth，af，k-可行等 定义都适用于锥图Cv。一个K-LUT可W用一个k-可行锥图实现，因此技术映射问题可W简化 成为电路DAG(图G)选择一组k-可行锥图来覆盖，图1为一个将电路DAG转换为LUT网络的实 例。
[00川划分(义.Υ)为图G中节点的划分，任意一条穿越划分的边e都有head(e)在集合X 中，tail (e)在集合玄中，划分的体积VO/(式支)为X集合中节点的个数，划分的面积流 口/;义；0为穿越划分的边的面积流之和。
[0012] 在有关基于LUT(Look化化ble)的FPGA技术映射算法，主要的一些研究成果也是 来自于国外。根据研究的目标，FPGA的技术映射算法大致可分为W下四类：
[0013] 1.延迟优化算法，其优化目标为尽可能的使实现电路的LUT的级数最小，国外运类 算法中比较经典的算法包括F1 owMap，MI S-pga-de lay，DAG-map和EdgeMap等。
[0014] 2.面积优化算法，其优化目为尽可能的是使实现电路的LUT的数量最少，国外运类 算法中比较典型的算法有 Prac tor，Vi sMap，Xmap，Mi s-pga，Qior 11 e-crf 等。
[001引 3 .功率优化算法，国外运类现有的经典算法有DvMap，Emap，PowerMac， Power iMinMap 等。
[0016] 4.延迟和面积同时优化，通常情况下，面积优化和延迟优化往往相互矛盾、相互制 约，因此往往是在延迟和面积中找一个平衡点来进行同时优化，运类算法中比较著名的主 要包括化tMap，DAOMap、F1 owMap-r 等。
[0017] FlowMap算法是经典的W延时为优化目标的技术映射算法。该算法主要分为两个 阶段:节点标记和LUT覆盖;在标记阶段，根据动态规划的思想，按照PI-P0的拓扑顺序对节 点进行逐个标记，标记的值为该节点所在LUT的最小高度;在LUT覆盖阶段，根据标记阶段的 结果，为节点选择最小高度划分，来进行LUT的覆盖，从而使得电路的关键路径最短。 FlowMap算法可W再0(n)的时间内求得延时最优的划分，但是其对面积的优化却不够理想。 [001引化tMap算法是对FlowMap算法的改进。CutMap算法也分为节点标记和LUT覆盖两个 阶段;在LUT覆盖阶段的划分选择时，化tMap算法把关键路径上的节点和非关键路径上的节 点区别对待:对关键路径上的节点求min-hei曲t划分，对非关键路径上的节点求min-cost 划分，在保证延时最优的前提下，尽可能的提高对面积的优化。
[0019] ABC工具为加利福尼亚大学伯克利分校开发的一款集综合和技术映射为一体的 FPGA综合工具，该工具主要使用了 balance jewrite jefactor、if W及fpga技术对电路进 行综合和技术映射，其主要W效率为优化目标，大大提高了 FPGA综合及技术映射的速度，并 得到了广泛应用。由于ABC是一款追求效率的工具，而技术映射的质量优化又比较耗费时 间，使得ABC不得不牺牲质量W换取技术映射效率的提高，因此ABC对技术映射的质量优化 并不明显。
【发明内容】
[0020] 针对现有技术的不足，本发明旨在提供一种高效FPGA技术映射算法，将技术映射 分为逻辑优化和结构优化，逻辑优化部分采用AIGW及对应的操作将电路分解为二输入电 路，结构优化部分基于一种迭代的启发式思想，通过一次一次的迭代，不断优化技术映射的 结果；另外，结构优化部分还采用一种自适应的迭代次数，减少了不必要的迭代，优化了技 术映射的效率。同时，结构优化部分对求取节点V的面积流公式进行了修正，W提高技术映 射划分选择过程的随机性。
[0021 ]为了实现上述目的，本发明采用如下技术方案：
[0022] -种高效FPGA技术映射算法包括如下步骤：
[0023] S1逻辑优化：
[0024] 1.1)初始化:为电路建立AIG图；
[0025] 1.2)对步骤1.1)中得到的AIG图进行分解优化，得到二输入电路；
[00%] S2结构优化：
[0027] 2.1)为步骤S1逻辑优化后得到的电路建立DAG图G，并设置最大迭代次数IMAX和执 行结果连续不变的最大次数M;
[0028] 2.2)为图G中每一个节点产生所有的k-可行划分，作为划分选择的集合；
[0029] 2.3)判断是否已经达到迭代次数IMAX，如果是，则转至执行步骤2.8)，否则执行步 骤2.4);
[0030] 2.4)判断执行结果是否连续Μ次不变，如果是，则转至执行步骤2.8)，否则执行步 骤2.5);
[0031 ] 2.5)按照Pi-ro的拓扑顺序向前遍历，为每一个节点选择最优划分；
[0032] 2.6)按照P0-PI的逆拓扑顺序向后遍历，选择可W作为LUT root的节点；
[0033] 2.7)返回执行步骤2.3);
[0034] 2.8)利用划分选择的结果进行LUT映射。
[0035] 需要说明的是，步骤1.2)的具体方法如下：
[0036] 1.2.1)采用平衡(balance)技术，在保证面积不变的情况下优化电路时延。平衡技 术包含两部分:基于树的布尔函数双分解(bi-decomposition)技术和布尔函数的树高化简 技术，首先按照从AIG图的根节点到叶子节点的顺序利用双分解技术构造树，然后利用布尔 代数的交换律、结合律和分配律对树高进行化简，在整个过程中，树的节点个数保持不变。
[0037] 1.2.2)采用重写(rewrite)技术，删除电路中的冗余节点W及无效节点。rewrite 首先要保证布尔函数功能不变，在此基础上，通过迭代，利用计算过的更小的子图来代替节 点处的子图，W达到面积优化的目的。
[0038] 1.2.3)采用重分解(refactor)技术，在保证时延不变的情况下优化电路的面积。 refactor技术是rewrite技术的一种扩展，在rewr ite技术之后，增加了重替代 (resubstitution)技术和冗余去除（redundancy removal)技术。其中重替代技术是利用网 络中已经存在的节点来表达当前节点的功能;而冗余去除技术是删除那些与布尔网络功能 无关的节点。运两项技术在rewri te技术的基础上进一步优化了电路的面积。
[0039] 需要说明的是，步骤2.1)中所建立的DAG图G中，每个节点为一个口电路、PI节点或 P0节点。
[0040] 需要说明的是，步骤2.2)的具体方法如下：
[0041] 从PI节点开始，按照PI-P0的拓扑顺序为每一个节点产生所有k-可行划分，产生k-可行划分具体按照下式：
[0042]
[0043] 其中，像代表与，+代表或，k为LUT的输入限制，input(v)表示节点V的输入集，U为 节点V输入集中的一个节点，f化，V)表示节点V的所有k-可行划分，fXk，u)表示节点U的所有 k-可行划分。
[0044] 需要说明的是，步骤2.5)的具体方法如下：
[0045] 2.5.1)向前遍历初始化:将所有PI节点的深度初始化为0，对应的面积流初始化为 0 ;PI节点输出边的深度初始化为1，对应的面积流初始化为0;
[0046] 2.5.2)判断是否图G中所有的节点均已被访问，如果是，结束步骤2.5)，转至步骤 2.6)，否则继续执行步骤2.5.3);
[0047] 2.5.3)按照PI-P0的拓扑顺序向前遍历，在图G中取未被访问的节点V，在节点V所 有满足下式的划分中选择面积流最小的划分Xv作为最优划分：
[004 引 d邱th(x)<Odepth-hei曲t(v);
[0049] X表示节点V的一个划分，depth(x)表示划分X的深度，Odepth表示最优深度， hei曲t(v)表示节点V的高度；
[0050] 其中，节点V的划分的面积流计算如下：
[0化1 ]
[0052] 其中，ξ为任意小的随机数，i edge (V)表示节点V的输入边集合，Αν表示节点V本身 对面积的影响；
[0053] 2.5.4)更新节点v的深度和面积流分别为d邱th(Xv)和af(Xv);
[0054] 2.5.5)更新节点v的任意一条输出边e的深度为depth(Xv)+delay(e)，面积流为
,其中，(161曰7(6)表示输出边6的相关时延，06(1旨6(>)表示节点￥的输出边集合;返 回执行步骤2.5.2)。
[0055] 需要说明的是，所述步骤2.6)的具体方法如下：
[0056] 2.6.1)向后遍历初始化:初始化root集合为所有Ρ0节点，并将所有Ρ0节点的高度 初始化为1;
[0057] 2.6.2)判断是否图G中所有节点均已被访问，如果是，则结束步骤2.6)，否则继续 执行步骤2.6.3);
[005引2.6.3)按照P0-PI的逆拓扑顺序，从图G中取出未被访问的节点V，如果V在集合 root内，计算：
[0059] h=max{height(e): e ￡〇edge(v)}；
[0060] 其中，hei曲t(e)为节点V的输出边集合oedge(v)中的任意边的高度，h则为节点V 的输出边集合中所有边的高度的最大值；
[0061] 2.6.4)更新节点V在步骤2.5)中得出的最优划分Xv内的任意节点U的高度为 height(U) =max化eight(U) ,h}，对于Xv的任意输入边e更新其高度height(e) = max 化eight(e) ,delay(e)+h}，更新集合root为root U inode(Xv)，inode(Xv)表示支撑节点V的 最优划分Xv的输入边的尾节点;然后返回步骤2.6.2)。
[0062] 需要说明的是，步骤2.8)的具体方法为:采用最终得到的集合rootW及集合内每 个节点的最优划分，对DAG图G进行LUT映射，形成最终的LUT网络。
[0063] 本发明的有益效果在于：
[0064] 1、本发明基于启发式算法，将技术映射划分为逻辑优化与结构优化，结构优化部 分采用DAG模型，分为划分产生、划分选择W及LUT映射Ξ步，划分产生采用了动态规划的思 想，快速为每一个节点产生所有k-可行划分;划分选择基于一种迭代次数可W自适应改变 的迭代启发式思想，通过多次向前遍历与向后遍历的迭代，不断优化技术映射的结果，并减 少了不必要的迭代，优化了技术映射的效率，最终选择出延时和面积同时被优化的划分集 合，相比与现有的延迟和面积同时优化的FPGA技术映射算法，本发明无论在技术映射的质 量还是技术映射的效率上都有较大提高；
[0065] 2、本发明修正了节点面积流计算公式，提高了划分选择的随机性。
【附图说明】
[0066] 图1为技术映射概念的实例示意图；
[0067] 图2为本发明的实施流程图；
[0068] 图3为图2中的向前遍历步骤的实施流程图；
[0069] 图4为图2中的向后遍历步骤的实施流程图。
【具体实施方式】
[0070] W下将结合附图对本发明作进一步的描述，需要说明的是，本实施例W本技术方 案为前提，给出了详细的实施方式和具体的操作过程，但本发明的保护范围并不限于本实 施例。
[0071 ]如图2所示，一种高效FPGA技术映射算法包括如下步骤：
[0072] S1逻辑优化：
[0073] 1.1)初始化:为电路建立AIG图；
[0074] 1.2)对步骤1.1)中得到的AIG图进行分解优化，得到二输入电路并输出；
[00巧]S2结构优化：
[0076] 2.1)为步骤S1逻辑优化后得到的电路建立DAG图G，并设置最大迭代次数IMAX和执 行结果连续不变的最大次数M;
[0077] 2.2)为图G中每一个节点产生所有的k-可行划分，作为划分选择的集合；
[0078] 2.3)判断是否已经达到迭代次数IMAX，如果是，则转至执行步骤2.8)，否则继续执 行步骤2.4);
[0079] 2.4)判断执行结果是否连续Μ次不变，如果是，则转至执行步骤2.8)，否则继续执 行步骤2.5);
[0080] 2.5)按照pi-ro的拓扑顺序向前遍历，为每一个节点选择最优划分；
[0081 ] 2.6)按照P0-PI的逆拓扑顺序向后遍历，选择可W作为LUT root的节点；
[0082] 2.7)返回执行步骤2.3);
[0083] 2.8)利用划分选择的结果进行LUT映射。
[0084] 需要说明的是，步骤1.2)的具体方法如下：
[0085] 1.2.1)采用平衡(balance)技术，在保证面积不变的情况下优化电路时延。平衡技 术包含两部分:基于树的布尔函数双分解(bi-decomposition)技术和布尔函数的树高化简 技术，首先按照从AIG图的根节点到叶子节点的顺序利用双分解技术构造树，然后利用布尔 代数的交换律、结合律和分配律对树高进行化简，在整个过程中，树的节点个数保持不变。
[0086] 1.2.2)采用重写（rewrite)技术，删除电路中的冗余节点w及无效节点。rewrite 首先要保证布尔函数功能不变，在此基础上，通过迭代，利用计算过的更小的子图来代替节 点处的子图，W达到面积优化的目的。
[0087] 1.2.3)采用重分解(refactor)技术，在保证时延不变的情况下优化电路的面积。 refactor技术是rewrite技术的一种扩展，在rewrite技术之后，增加了重替代 (resubstitution)技术和冗余去除（redundancy removal)技术。其中重替代技术是利用网 络中已经存在的节点来表达当前节点的功能;而冗余去除技术是删除那些与布尔网络功能 无关的节点。运两项技术在rewri te技术的基础上进一步优化了电路的面积。
[0088] 需要说明的是，步骤2.1)中所建立的DAG图G中，每个节点为一个口电路、PI节点或 P0节点。
[0089] 需要说明的是，步骤2.2)的具体方法如下：
[0090] 从PI节点开始，按照PI-P0的拓扑顺序为每一个节点产生所有k-可行划分，产生k-可行划分具体按照下式：
[0091]
[0092] 其中，?代表与，+代表或，k为LUT的输入限制，input(v)表示节点V的输入集，U为 节点V输入集中的一个节点，f化，V)表示节点V的所有k-可行划分，fXk，u)表示节点U的所有 k-可行划分。
[0093] 需要说明的是，如图3所示，步骤2.5)的具体方法如下：
[0094] 2.5.1)向前遍历初始化:将所有PI节点的深度初始化为0，对应的面积流初始化为 0 ;PI节点输出边的深度初始化为 1，对应的面积流初始化为0;
[00M] 2.5.2)判断是否图G中所有的节点均已被访问，如果是，结束步骤2.5)，转至步骤 2.6)，否则继续执行步骤2.5.3);
[0096] 2.5.3)向前遍历按照PI-P0的拓扑顺序，在图G中取未被访问的节点V，在节点V所 有满足下式的划分中选择面积流最小的划分Xv :
[0097] d邱th(x) < Odepth-hei曲t(v);
[009引 X表示节点V的一个划分，depth(x)表示划分X的深度，Odepth表示最优深度， hei曲t(v)表示节点V的高度；
[0099] 其中，节点V的划分的面积流计算如下：
[0100]
[0101 ]其中，ξ为任意小的随机数，iedge(v)表示节点V的输入边集合，Αν表示节点V本身 对面积的影响，一般取值为1;
[0102] 2.5.4)更新节点v的深度和面积流分别为d邱th(Xv)和af(Xv);
[0103] 2.5.5)更新节点v的任意一条输出边e的深度为depth(Xv)+delay(e)，面积流为
,其中，delay(e)表示输出边e的相关时延，oedge(v)表示节点V的输出边集合;返 回执行步骤2.5.2)。
[0104]需要说明的是，如图4所示，所述步骤2.6)的具体方法如下：
[0105] 2.6.1)向后遍历初始化:初始化root集合为所有PO节点，并将所有PO节点的高度 初始化为1;
[0106] 2.6.2)判断是否图G中所有节点均已被访问，如果是，则结束步骤2.6)，否则继续 执行步骤2.6.3);
[0107] 2.6.3)按照P0-PI的逆拓扑顺序，从图G中取出未被访问的节点V，如果V在集合 root内，计算：
[010引 h=max{height(e) :eE0edge(v)};
[0109]其中，hei曲t(e)为节点V的输出边集合中的任意边的高度，h则为节点V的输出边 集合中所有边的高度的最大值；
[0110] 2.6.4)更新节点v的最优划分Xv内的任意节点u的高度为height(u)=max化eight (U)，h}，对于Xv的任意输入边e更新其高度hei曲t(e)=max化eight(e)，delay(e)+h}，更新 集合root为root U inode(Xv)，inode(Xv)表示支撑节点V的最优划分Xv的输入边的尾节点； 然后返回步骤2.6.2)。
[0111] 需要说明的是，步骤2.8)的具体方法为:采用最终得到的集合rootW及集合内每 个节点的最优划分，对DAG图G进行LUT映射，形成最终的LUT网络。
[0112] 对于本领域的技术人员来说，可W根据W上的技术方案和构思，作出各种相应的 改变和变形，而所有的运些改变和变形都应该包括在本发明权利要求的保护范围之内。
【主权项】
1. 一种高效FPGA技术映射算法，其特征在于，包括如下步骤： Sl逻辑优化： 1.1) 初始化:为电路建立AIG图； 1.2) 对步骤1.1)中得到的AIG图进行分解优化，得到二输入电路； S2结构优化： 2.1) 为步骤Sl逻辑优化后得到的电路建立DAG图G，并设置最大迭代次数頂AX和执行结 果连续不变的最大次数M; 2.2) 为图G中每一个节点产生所有的k-可行划分，作为划分选择的集合； 2.3) 判断是否已经达到迭代次数MAX，如果是，则转至执行步骤2.8)，否则执行步骤 2.4) ； 2.4) 判断执行结果是否连续M次不变，如果是，则转至执行步骤2.8)，否则执行步骤 2.5) ； 2.5) 按照PI-PO的拓扑顺序向前遍历，为每一个节点选择最优划分； 2.6) 按照PO-PI的逆拓扑顺序向后遍历，选择可以作为LUT root的节点； 2.7) 返回执行步骤2.3); 2.8) 利用划分选择的结果进行LUT映射。2. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤1.2)的具体方法如 下： 1.2.1) 采用平衡(balance)技术，在保证面积不变的情况下优化电路时延； 1.2.2) 在步骤1.2.1)的基础上，采用重写(rewrite)技术，优化电路面积； 1.2.3) 在步骤1.2.2)的基础上，采用重分解(refactor)技术，在保证时延不变的情况 下进一步优化电路的面积。3. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤2.1)中所建立的 DAG图G中，每个节点为一个门电路、PI节点或PO节点。4. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤2.2)的具体方法如 下： 从PI节点开始，按照PI-PO的拓扑顺序为每一个节点产生所有k-可行划分，每个节点产 生k-可行划分具体按照下式进行：其中，€>代表与，+代表或，k为LUT的输入限制，input(V)表示节点V的输入集，u为节点V 输入集中的一个节点，f (k，V)表示节点V的所有k-可行划分，f (k，u)表示节点u的所有k-可 行划分。5. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤2.5)的具体方法如 下： 2.5.1) 向前遍历初始化:将所有PI节点的深度初始化为0，对应的面积流初始化为0; PI 节点输出边的深度初始化为1，对应的面积流初始化为〇; 2.5.2) 判断是否图G中所有的节点均已被访问，如果是，结束步骤2.5 )，转至步骤2.6)， 否则继续执行步骤2.5.3); 2.5.3) 按照PI -PO的拓扑顺序向前遍历，在图G中取未被访问的节点v，在节点v所有满 足下式的划分中选择面积流最小的划分Xv作为最优划分： depth(x)< Odepth-height(v)； x表示节点v的一个划分，depth(x)表示划分x的深度，Odepth表示最优深度，height (V) 表示节点V的高度； 其中，节点V的划分的面积流计算如下：其中，ξ为任意小的随机数，i edge (V)表示节点V的输入边集合，Av表示节点V本身对面积 的影响； 2.5.4) 更新节点V的深度和面积流分别为depth(Xv)和af (Xv); 2.5.5) 更新节点￥的任意一条输出边6的深度为(16口1：11(乂￥)+(16 137(6)，面积流为,其中，delay (e)表示输出边e的相关时延，oedge(v)表示节点V的输出边集合;返 回执行步骤2.5.2)。6. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，所述步骤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) :eE〇edge(v)}; 其中，height (e)为节点v的输出边集合oedge(V)中的任意边的高度，h则为节点v的输 出边集合中所有边的高度的最大值； 2.6.4) 更新节点V在步骤2.5)中得到的最优划分Xv内的任意节点u的高度为height(u) = max{height(u)，h}，对于Xv的任意输入边e更新其高度height(e) = max{height(e)， delay(e)+h}，更新集合root为root U inode(Xv)，inode(Xv)表示支撑节点v的最优划分Xv的 输入边的尾节点;然后返回步骤2.6.2)。7. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤2.8)的具体方法 为:采用最终得到的集合root以及集合内每个节点的最优划分，对DAG图G进行LUT映射，形 成最终的LUT网络。
【专利摘要】本发明公开了一种高效FPGA技术映射算法，将技术映射划分为逻辑优化与结构优化，逻辑优化部分采用AIG模型以及balance、rewrite以及refactor等技术对电路进行优化；结构优化部分采用DAG模型，分为划分产生、划分选择以及LUT映射三步，划分产生采用了动态规划的思想，快速为每一个节点产生所有k-可行划分；划分选择基于一种迭代次数可以自适应改变的迭代启发式思想，通过多次向前遍历与向后遍历的迭代，最终选择出延时和面积同时被优化的划分集合，与此同时，本发明修正了节点面积流计算公式，提高了划分选择的随机性；LUT映射将划分选择产生的划分结合映射成为LUT网络。
【IPC分类】G06F17/50
【公开号】CN105488285
【申请号】CN201510883669
【发明人】段振华, 杨凯强, 黄伯虎, 田聪, 张南, 王小兵
【申请人】西安电子科技大学
【公开日】2016年4月13日
【申请日】2015年12月4日
【技术领域】
[0001] 本发明设及计算机技术领域，可用于FPGA中与电路结构无关的口级网络向与电路 结构有关的LUT网络转换的技术映射问题。
【背景技术】
[0002] 近年来，随着集成电路技术的飞速发展，现场可编程口阵列（FPGA，Field Programmable Gate Array)因其具有集成度高、逻辑资源丰富、设计灵活W及使用范围广 等特点在数字系统设计中得到了广泛的应用。
[0003] FPGA的设计流程，主要包括设计输入、行为综合、工艺映射、打包、布局和布线。其 中，作为FPGA支持软件中关键的一步，技术映射引起了广泛的研究。
[0004] -个布尔电路的组合部分可W表示成一个046,6=(￥(6)，6(6))，八6巧蛇(6)分别 表示DAG的节点集合和有向边集合，图中的一个节点veV(G)表示一个逻辑口、原始输入节 点（PI)或者原始输出节点（P0);图中的一条有向边eEE(G)，Wu = head(e)为头，v = tail (e)为尾，表示逻辑电路中节点u的输出和节点V的输入的一个信号；Wv为尾的边的集合成 为节点V的输入边iedge(v); Wv为头的边的结合成为节点V的输出边oedge(v) ;PI节点没有 输入边，P0节点没有输出边;支撑节点V的输入边的尾节点称为节点V的输入节点，表示为 inode(v);节点V的输出边的头节点称为节点V的输出节点，表示为onode(v);如果I inode (V) I卽，则称V是k-可行的；如果图中的每一个节点都是k-可行的，那么图就是k-约束的。
[0005] 每一个边有一个相关的延时delay(e);-条路径的长度就是沿该路径的所有边的 延时之和；节点V的深度depth(v)是从PI节点到V的最长路径的长度;节点V的高度height (V)是从P0节点到V的最长路径的长度;PI节点的深度W及P0节点的高度都是0;边e的深度 depth(e)是从PI节点到e的最长路径的长度，边e的高度是从P0节点到e的最长路径的长度， 边的深度W及高度包含它自身的延时；图中最长路径的长度成为图的深度或者高度。
[0006] 图中的每个节点每条边都有一个面积流来表示在其之前的子图的面积的估计值， 表示为af，边e的面积流定义为：
[0007]
[000引节点V的面积流定义为：
[0009]
[0010]对PI或P0节点Αν等于0,对内部节点Αν等于l;v的一个锥图Cv被定义为包含节点V和 它的某些非PI前驱节点的DAG的子图，节点V称为Cv的根。尾部在Cv内，头部在Cv外的边的集 合称为Cv的输入边集记做iedge(Cv) ; Wv为头的边的集合称为Cv的输出边集记做oedge (Cv)，实际上Cv可W被当做一个节点，用于节点的inode，onode，height，(kpth，af，k-可行等 定义都适用于锥图Cv。一个K-LUT可W用一个k-可行锥图实现，因此技术映射问题可W简化 成为电路DAG(图G)选择一组k-可行锥图来覆盖，图1为一个将电路DAG转换为LUT网络的实 例。
[00川划分(义.Υ)为图G中节点的划分，任意一条穿越划分的边e都有head(e)在集合X 中，tail (e)在集合玄中，划分的体积VO/(式支)为X集合中节点的个数，划分的面积流 口/;义；0为穿越划分的边的面积流之和。
[0012] 在有关基于LUT(Look化化ble)的FPGA技术映射算法，主要的一些研究成果也是 来自于国外。根据研究的目标，FPGA的技术映射算法大致可分为W下四类：
[0013] 1.延迟优化算法，其优化目标为尽可能的使实现电路的LUT的级数最小，国外运类 算法中比较经典的算法包括F1 owMap，MI S-pga-de lay，DAG-map和EdgeMap等。
[0014] 2.面积优化算法，其优化目为尽可能的是使实现电路的LUT的数量最少，国外运类 算法中比较典型的算法有 Prac tor，Vi sMap，Xmap，Mi s-pga，Qior 11 e-crf 等。
[001引 3 .功率优化算法，国外运类现有的经典算法有DvMap，Emap，PowerMac， Power iMinMap 等。
[0016] 4.延迟和面积同时优化，通常情况下，面积优化和延迟优化往往相互矛盾、相互制 约，因此往往是在延迟和面积中找一个平衡点来进行同时优化，运类算法中比较著名的主 要包括化tMap，DAOMap、F1 owMap-r 等。
[0017] FlowMap算法是经典的W延时为优化目标的技术映射算法。该算法主要分为两个 阶段:节点标记和LUT覆盖;在标记阶段，根据动态规划的思想，按照PI-P0的拓扑顺序对节 点进行逐个标记，标记的值为该节点所在LUT的最小高度;在LUT覆盖阶段，根据标记阶段的 结果，为节点选择最小高度划分，来进行LUT的覆盖，从而使得电路的关键路径最短。 FlowMap算法可W再0(n)的时间内求得延时最优的划分，但是其对面积的优化却不够理想。 [001引化tMap算法是对FlowMap算法的改进。CutMap算法也分为节点标记和LUT覆盖两个 阶段;在LUT覆盖阶段的划分选择时，化tMap算法把关键路径上的节点和非关键路径上的节 点区别对待:对关键路径上的节点求min-hei曲t划分，对非关键路径上的节点求min-cost 划分，在保证延时最优的前提下，尽可能的提高对面积的优化。
[0019] ABC工具为加利福尼亚大学伯克利分校开发的一款集综合和技术映射为一体的 FPGA综合工具，该工具主要使用了 balance jewrite jefactor、if W及fpga技术对电路进 行综合和技术映射，其主要W效率为优化目标，大大提高了 FPGA综合及技术映射的速度，并 得到了广泛应用。由于ABC是一款追求效率的工具，而技术映射的质量优化又比较耗费时 间，使得ABC不得不牺牲质量W换取技术映射效率的提高，因此ABC对技术映射的质量优化 并不明显。
【发明内容】
[0020] 针对现有技术的不足，本发明旨在提供一种高效FPGA技术映射算法，将技术映射 分为逻辑优化和结构优化，逻辑优化部分采用AIGW及对应的操作将电路分解为二输入电 路，结构优化部分基于一种迭代的启发式思想，通过一次一次的迭代，不断优化技术映射的 结果；另外，结构优化部分还采用一种自适应的迭代次数，减少了不必要的迭代，优化了技 术映射的效率。同时，结构优化部分对求取节点V的面积流公式进行了修正，W提高技术映 射划分选择过程的随机性。
[0021 ]为了实现上述目的，本发明采用如下技术方案：
[0022] -种高效FPGA技术映射算法包括如下步骤：
[0023] S1逻辑优化：
[0024] 1.1)初始化:为电路建立AIG图；
[0025] 1.2)对步骤1.1)中得到的AIG图进行分解优化，得到二输入电路；
[00%] S2结构优化：
[0027] 2.1)为步骤S1逻辑优化后得到的电路建立DAG图G，并设置最大迭代次数IMAX和执 行结果连续不变的最大次数M;
[0028] 2.2)为图G中每一个节点产生所有的k-可行划分，作为划分选择的集合；
[0029] 2.3)判断是否已经达到迭代次数IMAX，如果是，则转至执行步骤2.8)，否则执行步 骤2.4);
[0030] 2.4)判断执行结果是否连续Μ次不变，如果是，则转至执行步骤2.8)，否则执行步 骤2.5);
[0031 ] 2.5)按照Pi-ro的拓扑顺序向前遍历，为每一个节点选择最优划分；
[0032] 2.6)按照P0-PI的逆拓扑顺序向后遍历，选择可W作为LUT root的节点；
[0033] 2.7)返回执行步骤2.3);
[0034] 2.8)利用划分选择的结果进行LUT映射。
[0035] 需要说明的是，步骤1.2)的具体方法如下：
[0036] 1.2.1)采用平衡(balance)技术，在保证面积不变的情况下优化电路时延。平衡技 术包含两部分:基于树的布尔函数双分解(bi-decomposition)技术和布尔函数的树高化简 技术，首先按照从AIG图的根节点到叶子节点的顺序利用双分解技术构造树，然后利用布尔 代数的交换律、结合律和分配律对树高进行化简，在整个过程中，树的节点个数保持不变。
[0037] 1.2.2)采用重写(rewrite)技术，删除电路中的冗余节点W及无效节点。rewrite 首先要保证布尔函数功能不变，在此基础上，通过迭代，利用计算过的更小的子图来代替节 点处的子图，W达到面积优化的目的。
[0038] 1.2.3)采用重分解(refactor)技术，在保证时延不变的情况下优化电路的面积。 refactor技术是rewrite技术的一种扩展，在rewr ite技术之后，增加了重替代 (resubstitution)技术和冗余去除（redundancy removal)技术。其中重替代技术是利用网 络中已经存在的节点来表达当前节点的功能;而冗余去除技术是删除那些与布尔网络功能 无关的节点。运两项技术在rewri te技术的基础上进一步优化了电路的面积。
[0039] 需要说明的是，步骤2.1)中所建立的DAG图G中，每个节点为一个口电路、PI节点或 P0节点。
[0040] 需要说明的是，步骤2.2)的具体方法如下：
[0041] 从PI节点开始，按照PI-P0的拓扑顺序为每一个节点产生所有k-可行划分，产生k-可行划分具体按照下式：
[0042]
[0043] 其中，像代表与，+代表或，k为LUT的输入限制，input(v)表示节点V的输入集，U为 节点V输入集中的一个节点，f化，V)表示节点V的所有k-可行划分，fXk，u)表示节点U的所有 k-可行划分。
[0044] 需要说明的是，步骤2.5)的具体方法如下：
[0045] 2.5.1)向前遍历初始化:将所有PI节点的深度初始化为0，对应的面积流初始化为 0 ;PI节点输出边的深度初始化为1，对应的面积流初始化为0;
[0046] 2.5.2)判断是否图G中所有的节点均已被访问，如果是，结束步骤2.5)，转至步骤 2.6)，否则继续执行步骤2.5.3);
[0047] 2.5.3)按照PI-P0的拓扑顺序向前遍历，在图G中取未被访问的节点V，在节点V所 有满足下式的划分中选择面积流最小的划分Xv作为最优划分：
[004 引 d邱th(x)<Odepth-hei曲t(v);
[0049] X表示节点V的一个划分，depth(x)表示划分X的深度，Odepth表示最优深度， hei曲t(v)表示节点V的高度；
[0050] 其中，节点V的划分的面积流计算如下：
[0化1 ]
[0052] 其中，ξ为任意小的随机数，i edge (V)表示节点V的输入边集合，Αν表示节点V本身 对面积的影响；
[0053] 2.5.4)更新节点v的深度和面积流分别为d邱th(Xv)和af(Xv);
[0054] 2.5.5)更新节点v的任意一条输出边e的深度为depth(Xv)+delay(e)，面积流为
,其中，(161曰7(6)表示输出边6的相关时延，06(1旨6(>)表示节点￥的输出边集合;返 回执行步骤2.5.2)。
[0055] 需要说明的是，所述步骤2.6)的具体方法如下：
[0056] 2.6.1)向后遍历初始化:初始化root集合为所有Ρ0节点，并将所有Ρ0节点的高度 初始化为1;
[0057] 2.6.2)判断是否图G中所有节点均已被访问，如果是，则结束步骤2.6)，否则继续 执行步骤2.6.3);
[005引2.6.3)按照P0-PI的逆拓扑顺序，从图G中取出未被访问的节点V，如果V在集合 root内，计算：
[0059] h=max{height(e): e ￡〇edge(v)}；
[0060] 其中，hei曲t(e)为节点V的输出边集合oedge(v)中的任意边的高度，h则为节点V 的输出边集合中所有边的高度的最大值；
[0061] 2.6.4)更新节点V在步骤2.5)中得出的最优划分Xv内的任意节点U的高度为 height(U) =max化eight(U) ,h}，对于Xv的任意输入边e更新其高度height(e) = max 化eight(e) ,delay(e)+h}，更新集合root为root U inode(Xv)，inode(Xv)表示支撑节点V的 最优划分Xv的输入边的尾节点;然后返回步骤2.6.2)。
[0062] 需要说明的是，步骤2.8)的具体方法为:采用最终得到的集合rootW及集合内每 个节点的最优划分，对DAG图G进行LUT映射，形成最终的LUT网络。
[0063] 本发明的有益效果在于：
[0064] 1、本发明基于启发式算法，将技术映射划分为逻辑优化与结构优化，结构优化部 分采用DAG模型，分为划分产生、划分选择W及LUT映射Ξ步，划分产生采用了动态规划的思 想，快速为每一个节点产生所有k-可行划分;划分选择基于一种迭代次数可W自适应改变 的迭代启发式思想，通过多次向前遍历与向后遍历的迭代，不断优化技术映射的结果，并减 少了不必要的迭代，优化了技术映射的效率，最终选择出延时和面积同时被优化的划分集 合，相比与现有的延迟和面积同时优化的FPGA技术映射算法，本发明无论在技术映射的质 量还是技术映射的效率上都有较大提高；
[0065] 2、本发明修正了节点面积流计算公式，提高了划分选择的随机性。
【附图说明】
[0066] 图1为技术映射概念的实例示意图；
[0067] 图2为本发明的实施流程图；
[0068] 图3为图2中的向前遍历步骤的实施流程图；
[0069] 图4为图2中的向后遍历步骤的实施流程图。
【具体实施方式】
[0070] W下将结合附图对本发明作进一步的描述，需要说明的是，本实施例W本技术方 案为前提，给出了详细的实施方式和具体的操作过程，但本发明的保护范围并不限于本实 施例。
[0071 ]如图2所示，一种高效FPGA技术映射算法包括如下步骤：
[0072] S1逻辑优化：
[0073] 1.1)初始化:为电路建立AIG图；
[0074] 1.2)对步骤1.1)中得到的AIG图进行分解优化，得到二输入电路并输出；
[00巧]S2结构优化：
[0076] 2.1)为步骤S1逻辑优化后得到的电路建立DAG图G，并设置最大迭代次数IMAX和执 行结果连续不变的最大次数M;
[0077] 2.2)为图G中每一个节点产生所有的k-可行划分，作为划分选择的集合；
[0078] 2.3)判断是否已经达到迭代次数IMAX，如果是，则转至执行步骤2.8)，否则继续执 行步骤2.4);
[0079] 2.4)判断执行结果是否连续Μ次不变，如果是，则转至执行步骤2.8)，否则继续执 行步骤2.5);
[0080] 2.5)按照pi-ro的拓扑顺序向前遍历，为每一个节点选择最优划分；
[0081 ] 2.6)按照P0-PI的逆拓扑顺序向后遍历，选择可W作为LUT root的节点；
[0082] 2.7)返回执行步骤2.3);
[0083] 2.8)利用划分选择的结果进行LUT映射。
[0084] 需要说明的是，步骤1.2)的具体方法如下：
[0085] 1.2.1)采用平衡(balance)技术，在保证面积不变的情况下优化电路时延。平衡技 术包含两部分:基于树的布尔函数双分解(bi-decomposition)技术和布尔函数的树高化简 技术，首先按照从AIG图的根节点到叶子节点的顺序利用双分解技术构造树，然后利用布尔 代数的交换律、结合律和分配律对树高进行化简，在整个过程中，树的节点个数保持不变。
[0086] 1.2.2)采用重写（rewrite)技术，删除电路中的冗余节点w及无效节点。rewrite 首先要保证布尔函数功能不变，在此基础上，通过迭代，利用计算过的更小的子图来代替节 点处的子图，W达到面积优化的目的。
[0087] 1.2.3)采用重分解(refactor)技术，在保证时延不变的情况下优化电路的面积。 refactor技术是rewrite技术的一种扩展，在rewrite技术之后，增加了重替代 (resubstitution)技术和冗余去除（redundancy removal)技术。其中重替代技术是利用网 络中已经存在的节点来表达当前节点的功能;而冗余去除技术是删除那些与布尔网络功能 无关的节点。运两项技术在rewri te技术的基础上进一步优化了电路的面积。
[0088] 需要说明的是，步骤2.1)中所建立的DAG图G中，每个节点为一个口电路、PI节点或 P0节点。
[0089] 需要说明的是，步骤2.2)的具体方法如下：
[0090] 从PI节点开始，按照PI-P0的拓扑顺序为每一个节点产生所有k-可行划分，产生k-可行划分具体按照下式：
[0091]
[0092] 其中，?代表与，+代表或，k为LUT的输入限制，input(v)表示节点V的输入集，U为 节点V输入集中的一个节点，f化，V)表示节点V的所有k-可行划分，fXk，u)表示节点U的所有 k-可行划分。
[0093] 需要说明的是，如图3所示，步骤2.5)的具体方法如下：
[0094] 2.5.1)向前遍历初始化:将所有PI节点的深度初始化为0，对应的面积流初始化为 0 ;PI节点输出边的深度初始化为 1，对应的面积流初始化为0;
[00M] 2.5.2)判断是否图G中所有的节点均已被访问，如果是，结束步骤2.5)，转至步骤 2.6)，否则继续执行步骤2.5.3);
[0096] 2.5.3)向前遍历按照PI-P0的拓扑顺序，在图G中取未被访问的节点V，在节点V所 有满足下式的划分中选择面积流最小的划分Xv :
[0097] d邱th(x) < Odepth-hei曲t(v);
[009引 X表示节点V的一个划分，depth(x)表示划分X的深度，Odepth表示最优深度， hei曲t(v)表示节点V的高度；
[0099] 其中，节点V的划分的面积流计算如下：
[0100]
[0101 ]其中，ξ为任意小的随机数，iedge(v)表示节点V的输入边集合，Αν表示节点V本身 对面积的影响，一般取值为1;
[0102] 2.5.4)更新节点v的深度和面积流分别为d邱th(Xv)和af(Xv);
[0103] 2.5.5)更新节点v的任意一条输出边e的深度为depth(Xv)+delay(e)，面积流为
,其中，delay(e)表示输出边e的相关时延，oedge(v)表示节点V的输出边集合;返 回执行步骤2.5.2)。
[0104]需要说明的是，如图4所示，所述步骤2.6)的具体方法如下：
[0105] 2.6.1)向后遍历初始化:初始化root集合为所有PO节点，并将所有PO节点的高度 初始化为1;
[0106] 2.6.2)判断是否图G中所有节点均已被访问，如果是，则结束步骤2.6)，否则继续 执行步骤2.6.3);
[0107] 2.6.3)按照P0-PI的逆拓扑顺序，从图G中取出未被访问的节点V，如果V在集合 root内，计算：
[010引 h=max{height(e) :eE0edge(v)};
[0109]其中，hei曲t(e)为节点V的输出边集合中的任意边的高度，h则为节点V的输出边 集合中所有边的高度的最大值；
[0110] 2.6.4)更新节点v的最优划分Xv内的任意节点u的高度为height(u)=max化eight (U)，h}，对于Xv的任意输入边e更新其高度hei曲t(e)=max化eight(e)，delay(e)+h}，更新 集合root为root U inode(Xv)，inode(Xv)表示支撑节点V的最优划分Xv的输入边的尾节点； 然后返回步骤2.6.2)。
[0111] 需要说明的是，步骤2.8)的具体方法为:采用最终得到的集合rootW及集合内每 个节点的最优划分，对DAG图G进行LUT映射，形成最终的LUT网络。
[0112] 对于本领域的技术人员来说，可W根据W上的技术方案和构思，作出各种相应的 改变和变形，而所有的运些改变和变形都应该包括在本发明权利要求的保护范围之内。
【主权项】
1. 一种高效FPGA技术映射算法，其特征在于，包括如下步骤： Sl逻辑优化： 1.1) 初始化:为电路建立AIG图； 1.2) 对步骤1.1)中得到的AIG图进行分解优化，得到二输入电路； S2结构优化： 2.1) 为步骤Sl逻辑优化后得到的电路建立DAG图G，并设置最大迭代次数頂AX和执行结 果连续不变的最大次数M; 2.2) 为图G中每一个节点产生所有的k-可行划分，作为划分选择的集合； 2.3) 判断是否已经达到迭代次数MAX，如果是，则转至执行步骤2.8)，否则执行步骤 2.4) ； 2.4) 判断执行结果是否连续M次不变，如果是，则转至执行步骤2.8)，否则执行步骤 2.5) ； 2.5) 按照PI-PO的拓扑顺序向前遍历，为每一个节点选择最优划分； 2.6) 按照PO-PI的逆拓扑顺序向后遍历，选择可以作为LUT root的节点； 2.7) 返回执行步骤2.3); 2.8) 利用划分选择的结果进行LUT映射。2. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤1.2)的具体方法如 下： 1.2.1) 采用平衡(balance)技术，在保证面积不变的情况下优化电路时延； 1.2.2) 在步骤1.2.1)的基础上，采用重写(rewrite)技术，优化电路面积； 1.2.3) 在步骤1.2.2)的基础上，采用重分解(refactor)技术，在保证时延不变的情况 下进一步优化电路的面积。3. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤2.1)中所建立的 DAG图G中，每个节点为一个门电路、PI节点或PO节点。4. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤2.2)的具体方法如 下： 从PI节点开始，按照PI-PO的拓扑顺序为每一个节点产生所有k-可行划分，每个节点产 生k-可行划分具体按照下式进行：其中，€>代表与，+代表或，k为LUT的输入限制，input(V)表示节点V的输入集，u为节点V 输入集中的一个节点，f (k，V)表示节点V的所有k-可行划分，f (k，u)表示节点u的所有k-可 行划分。5. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤2.5)的具体方法如 下： 2.5.1) 向前遍历初始化:将所有PI节点的深度初始化为0，对应的面积流初始化为0; PI 节点输出边的深度初始化为1，对应的面积流初始化为〇; 2.5.2) 判断是否图G中所有的节点均已被访问，如果是，结束步骤2.5 )，转至步骤2.6)， 否则继续执行步骤2.5.3); 2.5.3) 按照PI -PO的拓扑顺序向前遍历，在图G中取未被访问的节点v，在节点v所有满 足下式的划分中选择面积流最小的划分Xv作为最优划分： depth(x)< Odepth-height(v)； x表示节点v的一个划分，depth(x)表示划分x的深度，Odepth表示最优深度，height (V) 表示节点V的高度； 其中，节点V的划分的面积流计算如下：其中，ξ为任意小的随机数，i edge (V)表示节点V的输入边集合，Av表示节点V本身对面积 的影响； 2.5.4) 更新节点V的深度和面积流分别为depth(Xv)和af (Xv); 2.5.5) 更新节点￥的任意一条输出边6的深度为(16口1：11(乂￥)+(16 137(6)，面积流为,其中，delay (e)表示输出边e的相关时延，oedge(v)表示节点V的输出边集合;返 回执行步骤2.5.2)。6. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，所述步骤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) :eE〇edge(v)}; 其中，height (e)为节点v的输出边集合oedge(V)中的任意边的高度，h则为节点v的输 出边集合中所有边的高度的最大值； 2.6.4) 更新节点V在步骤2.5)中得到的最优划分Xv内的任意节点u的高度为height(u) = max{height(u)，h}，对于Xv的任意输入边e更新其高度height(e) = max{height(e)， delay(e)+h}，更新集合root为root U inode(Xv)，inode(Xv)表示支撑节点v的最优划分Xv的 输入边的尾节点;然后返回步骤2.6.2)。7. 根据权利要求1所述的高效FPGA技术映射算法，其特征在于，步骤2.8)的具体方法 为:采用最终得到的集合root以及集合内每个节点的最优划分，对DAG图G进行LUT映射，形 成最终的LUT网络。
【专利摘要】本发明公开了一种高效FPGA技术映射算法，将技术映射划分为逻辑优化与结构优化，逻辑优化部分采用AIG模型以及balance、rewrite以及refactor等技术对电路进行优化；结构优化部分采用DAG模型，分为划分产生、划分选择以及LUT映射三步，划分产生采用了动态规划的思想，快速为每一个节点产生所有k-可行划分；划分选择基于一种迭代次数可以自适应改变的迭代启发式思想，通过多次向前遍历与向后遍历的迭代，最终选择出延时和面积同时被优化的划分集合，与此同时，本发明修正了节点面积流计算公式，提高了划分选择的随机性；LUT映射将划分选择产生的划分结合映射成为LUT网络。
【IPC分类】G06F17/50
【公开号】CN105488285
【申请号】CN201510883669
【发明人】段振华, 杨凯强, 黄伯虎, 田聪, 张南, 王小兵
【申请人】西安电子科技大学
【公开日】2016年4月13日
【申请日】2015年12月4日
最新回复(0)