一种针对改进逻辑单元的集成电路的工艺映射方法

摘要

本发明涉及一种针对改进逻辑单元的集成电路的工艺映射方法。本发明方法首先将通用组合逻辑电路分解成2输入逻辑单元组成的电路；然后将该2输入逻辑单元作为一个节点，基于改进逻辑单元对该节点进行分割，再找出该节点的所有分割；然后将每种分割所覆盖节点数量(PGCN)，与实际使用改进逻辑单元数量(PRUN)之间比值最大值所对应的分割作为最优分割；最后将最优分割转换为相应改进逻辑单元。本发明充分利用改进逻辑单元结构上的优势，使改进后的电路在面积和时间上更有效率。本发明能够广泛应用于集成电路的工艺映射中。

说明书

技术领域

本发明涉及工艺映射技术，尤其涉及集成电路的工艺映射方法。

背景技术

FPGA(Field Programmable Gate Array，现场可编程门阵列)通常包 括大量的逻辑单元。图1示出了一种基本FPGA逻辑单元(logic cell，下 称LC)，其包括查找表(look-up table，LUT)和DFF(D触发器)。4 输入LUT示出具有一组配置存储单元，共16个，其可以被配置或编程以 用于计算任何4输入的组合逻辑功能。LUT的输出不仅仅直接连接到LC 的输出，而且还送入D触发器的D输入端，D触发器的Q输出可用作另一 个LC输出。在该逻辑单元内，可以提供多路选择器(multiplexer，即 MUX)及其它逻辑以便允许将触发器的Q输出端连接到LUT的某些输入 端。

改进逻辑单元是在图1基本逻辑单元基础上所作出的改进，图2a示 出了改进后的FPGA逻辑单元。为了便于软件建模，将此改进后的逻辑 单元分为两种，一种是组合型的改进逻辑单元fc_comb，另一种是时序 型的改进逻辑单元(即具备特定功能的寄存器单元)fc_reg。图2b是组 合型的改进逻辑单元fc_comb示意图，图2c是时序型的改进逻辑单元 fc_reg示意图。

组合型的改进逻辑单元可以通过两级LUT的级联方式有效地实现5 输入LUT、LUT或操作、LUT与操作，具体实现方式参见图3、图4、图5、 图6。图3、图4是分别利用wlut chain结构实现水平5输入LUT(H-LUT5) 以及垂直5输入LUT(V-LUT5)的示意图，图5是利用buddy chain结构实 现LUT或操作的示意图，图6是利用buddy chain结构实现LUT与操作的示 意图。通过具备特定功能的寄存器单元可以实现寄存器的同步功能，包 括实现寄存器的同步复位、寄存器的同步置位、寄存器的同步数据，具 体实现方式参见图7、图8、图9。图7是寄存器同步复位实现示意图，图 8是寄存器同步置位实现示意图，图9是寄存器同步数据实现示意图。

改进型逻辑单元能够实现不同LUT之间的快速逻辑运算。此外，改 进逻辑单元包含一个具备特定功能的寄存器单元，其可以有效支持同步 置位、复位或同步数据功能。改进型逻辑单元能完整地表示出符合芯片 结构的功能特性和设计模式(满足一定约束关系并有最优结构的电路)。 通过逻辑综合工具直接将用户设计映射成满足改进型逻辑单元功能的 结构化网表，保证面积和性能的最优。因此，图2所示的改进逻辑单元 在面积和时序方面能够得到更好的结果。

工艺映射(Technology Mapping)是FPGA设计流程中连接前端逻辑 综合和后端布局布线的重要桥梁，在这一阶段，与工艺无关的电路网表 在一定的硬件约束下映射到工艺库相关的结构，FPGA芯片性能在很大 程度上取决于逻辑单元的结构及其相应的工艺映射方法。

目前国内外学术界对FPGA工艺映射优化方法，大多集中在将一般 的布尔逻辑电路网表映射为由K输入LUT组成的电路，具体LUT的输入 数目由实际的工艺库决定，但这些方法只是针对于一个LC中单纯的包含 一个LUT结构，因此这些方法无法充分利用图2所示的改进型逻辑单元 在结构上的优势。

发明内容

本发明提供了一种能解决以上问题的针对改进逻辑单元的集成电路的 工艺映射方法，以解决改进型逻辑单元FPGA的工艺映射问题。

在第一方面，本发明提供了一种工艺映射方法，该方法首先将初始逻 辑网表中的通用组合逻辑电路分解成2输入逻辑单元组成的电路；然后将 该2输入逻辑单元作为一个节点，以该节点为根节点，并基于改进逻辑单 元对该节点进行分割，再找出该节点的所有分割；接着预估每种分割所覆 盖节点数量(PGCN)，并预估相应分割实际所使用的改进逻辑单元数量 (PRUN)，再将该覆盖节点数量(PGCN)与实际使用改进逻辑单元数量 (PRUN)之间比值的最大值所对应的分割作为最优分割；最后将该最优分 割转换为相应改进逻辑单元，以便完成由初始逻辑网表到改进逻辑单元级 别的逻辑网表的工艺映射。

进一步地，所述每种分割所覆盖节点数量(PGCN)为

$\mathrm{PGCN}=1+\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUT}1}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUT}1}}+......\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUTn}}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUTn}}}$

其中，PGCN_SUBCUTn是所述分割的第n子分割所覆盖节点数量，且n为正整 数，FANOUT_SUBCUTn是所述第n子分割SUBCUTn扇出单元的数量。

进一步地，所述实际使用改进逻辑单元数量(PRUN)为

$\mathrm{PRUN}=\mathrm{RUN}+\frac{{\mathrm{PRUN}}_{\mathrm{SUBCUT}1}-{\mathrm{RUN}}_{\mathrm{SUBCUT}1}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUT}1}}+......\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUTn}}-{\mathrm{RUN}}_{\mathrm{SUBCUTn}}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUTn}}}$

其中，RUN是所述分割实际所需查找表(LUT)数量，PRUN_SUBCUTn是所述 分割的第n子分割实际使用改进逻辑单元数量，RUN_SUBCUTn是所述第n子 分割实际所需查找表(LUT)数量，FANOUT_SUBCUTn是所述第n子分割 SUBCUTn扇出单元的数量。

进一步地，所述改进逻辑单元的组合包括LUT4、LUT5、LUTAND 和LUTOR。

本发明充分利用改进逻辑单元结构上的优势，将通用的布尔逻辑电路 转换为由改进基本逻辑单元构成的逻辑电路，使得改进后的电路设计在 面积上更好、性能上更优、有效地降低了后续布局布线问题的难度。

附图说明

下面将参照附图对本发明的具体实施方案进行更详细的说明，在附图 中：

图1是基本FPGA逻辑单元结构示意图；

图2是改进FPGA逻辑单元结构示意图；

图3是利用wlut chain结构实现水平5输入LUT(H-LUT5)的示意 图；

图4是利用wlut chain结构实现垂直5输入LUT(V-LUT5)的示意 图；

图5是利用buddy chain结构实现LUT或操作的示意图；

图6是利用buddy chain结构实现LUT与操作的示意图；

图7是寄存器同步复位实现示意图；

图8是寄存器同步置位实现示意图；

图9是寄存器同步数据实现示意图；

图10是本发明一个实施例的针对改进逻辑单元的集成电路工艺映射流 程图；

图11是分解前的4输入与门；

图12是分解成的深度为2的两输入与门；

图13是分解成的深度为3的两输入与门；

图14是本发明一个实施例的改进分割算法实现流程图；

图15是本发明一个实施例的Root节点分割示意图。

具体实施方式

图10是本发明一个实施例的针对改进逻辑单元的集成电路工艺映射流 程图。

在集成电路中，初始逻辑网表中的电路是与物理器件无关的通用逻 辑电路，该通用逻辑电路包括两种类型，一种是通用时序逻辑电路，另 一种是通用组合逻辑电路。以下所述步骤101是将通用时序逻辑电路映 射成特定功能的寄存器fc_reg，步骤102、步骤103、步骤104是将通用组 合逻辑电路映射成组合型的改进逻辑单元fc_comb。因此，步骤101可以 在步骤102之前，也可以在步骤104之后，还可以在步骤102到步骤104之 间任意位置。

在步骤101，根据初始逻辑网表，将其通用时序逻辑电路映射为寄 存器形式的相应同步电路fc_reg，包括映射成图7中的同步复位电路、 图8中的同步置位电路或图9中的同步数据电路。

在步骤102，采用二叉决策图(BDD)技术对初始逻辑网表中的通 用组合逻辑电路进行优化，以减少通用组合逻辑器件的数量，去除通用 组合逻辑电路的冗余。如对A and B and A进行优化得到A and B。

在步骤103，将所有通用组合逻辑电路分解为2输入的逻辑电路。

BDD优化后的逻辑网络包含多种类型的通用组合逻辑电路，如4输 入的与非门、多路选择器等，该步骤103就是将所有大于2输入的通用组 合逻辑电路分解成2输入的通用组合逻辑电路，该2输入通用逻辑电路包 括2输入与门、2输入或门、2输入异或门。

较佳地，将大于2输入的通用组合逻辑电路分解成深度最小的逻辑 电路，以便该逻辑电路具有最短时延。举例，将4输入与门分解成具有 两级深度的2输入与门，而不是分解成具有三级深度的2输入与门，如图 11、图12、图13所示，图11是分解前的4输入与门，图12是分解成的深 度为2的两输入与门，图13是分解成的深度为3的两输入与门。在步骤 104，对分解成的2输入通用组合逻辑电路进行工艺映射，以便转换成改 进逻辑单元级别的组合逻辑电路。具体地，采用改进型分割算法实现2 输入通用组合逻辑电路到改进逻辑单元级别的组合逻辑电路的工艺映 射，该改进分割算法是在分割枚举算法(Cut Enumeration)基础上所作 出的改进，后面内容有对该改进分割算法具体原理所作出的详尽阐述。

在步骤105，将所有改进逻辑单元转换为相应实际物理器件，以便 将通过逻辑电路转换为实际物理电路，该改进逻辑单元包括步骤101中 的具备特定功能的寄存器及步骤104中的改进逻辑单元级别的组合逻辑 电路。

下面详细阐述本实施例的改进分割算法，图14是本发明一个实施例 的改进分割算法实现流程图。

在步骤141，将由步骤103得到的每个2输入通用组合逻辑单元作为 一个节点，找出每个节点所有可能的分割(CUT)，包括4输入分割(对 应于CUT4)、5输入分割(对应于LUT5)、8输入分割(对应于LUTAND 和LUTOR)，并存储每个节点所有分割总数以及相应每种分割的形态， 该改进分割需要遍历每个节点。需要说明的是，所述分割是包含多个节 点的子网络。

在步骤142，针对每个节点，通过评价方法从相应节点的所有分割 中选择一个最优分割，下面详细阐述如何根据所述评价方法得到最优分 割。

该评价方法采用的评价函数包括两部分，一部分为累积节点覆盖数 量(Propagate Gate Cover Number，PGCN)，另一部分为累积资源使用 数量(Propagate Resource Usage Number，PRUN)。

(1)累积节点覆盖数量PGCN

某节点PGCN定义为，以该节点为根，在当前选择的分割条件下，该 当前分割所覆盖节点总数量的预估值，因此，PGCN仅是对当前分割所 覆盖节点总数的一个估计值，而不是确切值。

图15是本发明一个实施例的Root节点分割示意图，假设Root节点的当 前分割为CUT，则如图15所示，当前分割CUT由第一子分割SUBCUT1 和第二子分割SUBCUT2合并组成，则该Root节点当前分割CUT所对应的 PGCN可以表示为，

${\mathrm{PGCN}}_{\mathrm{CUT}}=1+\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUT}1}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUT}1}}+\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUT}2}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUT}2}}---\left(1\right)$

其中，PGCN_CUT是Root节点当前分割CUT对应的PGCN，PGCN_SUBCUT1是 Root节点第一子分割SUBCUT1对应的PGCN，PGCN_SUBCUT2是Root节点第 二子分割SUBCUT2对应的PGCN，FANOUT_SUBCUT1是第一子分割SUBCUT1 的扇出数目，FANOUT_SUBCUT2是第二子分割SUBCUT2的扇出单元的数量。 需要说明的是，若当前分割具有n个子分割(n为大于1的正整数)时， 则该当前分割对应的PGCN为，

${\mathrm{PGCN}}_{\mathrm{CUT}}=1+\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUT}1}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUT}1}}+......\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUTn}}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUTn}}}---\left(2\right)$

下面阐述公式(1)中各参数的获取方法。

本实施例采用网络拓扑结构顺序获取每一节点的PGCN，因此在计算 Root节点PGCN之前，该Root节点的所有前驱节点的PGCN已经计算完 成，即公式(1)中的PGCN_SUBCUT1、PGCN_SUBCUT2已经计算完成，而最小子 切割即网络拓扑结构中最外层节点的PGCN为1，因此通过该最外层节点 PGCN值就够顺序得到每个节点的PGCN。

某切割的扇出单元是指该切割的输出所对应的所有节点，图15中，第 一子切割SUBCUT1的扇出单元(即节点S1的扇出单元)是Root节点，因 此第一子切割具有一个扇出单元，即FANOUT_SUBCUT1＝1；第二子切割 SUBCUT2的扇出单元(即节点S2的扇出单元)为Root和N5，因此第二 子切割具有两个扇出单元，即FANOUT_SUBCUT2＝2。假设PGCN_SUBCUT1＝5， PGCN_SUBCUT2＝3，将FANOUT_SUBCUT1＝1，FANOUT_SUBCUT2＝2，PGCN_SUBCUT1＝5， PGCN_SUBCUT2＝3代入公式(1)，得到PGCN_CUT＝7.5。

(2)累积资源使用数量PRUN

某节点PRUN定义为，以该节点为根，在当前选择的分割条件下， 该当前分割实际所需使用的改进逻辑单元(包括LUT4、LUT5、LUTAN、 LUTOR)数量的预估值，因此，PRUN仅是对当前分割所需使用器件数 量的估计。

下面以图15中的Root节点为例，阐述PRUN计算方式，该Root节 点当前分割CUT所对应的PRUN可以表示为，

${\mathrm{PRUN}}_{\mathrm{CUT}}={\mathrm{RUN}}_{\mathrm{CUT}}+\frac{{\mathrm{PRUN}}_{\mathrm{SUBCUT}1}-{\mathrm{RUN}}_{\mathrm{SUBCUT}1}}{{\mathrm{FANOUT}}_{\mathrm{SUNCUT}1}}+\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUT}2}-{\mathrm{RUN}}_{\mathrm{SUBCUT}2}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUT}2}}---\left(3\right)$

其中，RUN_CUT是Root节点当前分割CUT实际所需使用LUT的数量。 由于LUT4由一个LUT构成，因此，对于具有4输入的CUT，其RUN_CUT值为1；同样，由于LUT5、LUTAND、LUTOR由两个LUT构成，因此 对于具有5输入的CUT5以及对应具有8输入的LUTAND、LUTOR， 其RUN_CUT值均为2。图15中，Root节点当前分割为4输入CUT，因此 RUN_CUT＝1。

类似于前文所述PGCN，在计算PRUN_CUT时，PRUN_SUBCUT1、PRUN_SUBCUT2已 计算完成，即PRUN_SUBCUT1、PRUN_SUBCUT2为已知。

公式(3)中，RUN_SUBCUT1、RUN_SUBCUT2分别是SUBCUT1、SUBCUT2实 际所需使用LUT的数量，其计算方式与RUN_CUT相同。此外，FANOUT_SUBCUT1、 FANOUT_SUBCUT2计算方法与公式(1)中的FANOUT_SUBCUT1、FANOUT_SUBCUT2计算 方法相同。

需要说明的是，若当前分割具有n个子分割(n为大于1的正整数) 时，则该当前分割对应的PRUN为，

${\mathrm{PRUN}}_{\mathrm{CUT}}={\mathrm{RUN}}_{\mathrm{CUT}}+\frac{{\mathrm{PRUN}}_{\mathrm{SUBCUT}1}-{\mathrm{RUN}}_{\mathrm{SUBCUT}1}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUT}1}}+......+\frac{{\mathrm{PGCN}}_{\mathrm{SUBCUTn}}-{\mathrm{RUN}}_{\mathrm{SUBCUTn}}}{{\mathrm{FANOUT}}_{\mathrm{SUBCUTn}}}---\left(4\right)$

(3)评价函数COST

评价函数COST是通过PGCN、PRUN选择当前节点所有分割中最优 分割的函数，因此评价函数COST可以表示为，

$\mathrm{COST}=\frac{\mathrm{PGCN}}{\mathrm{PRUN}}---\left(5\right)$

其中，PGCN为累积节点覆盖数量，PRUN为累积资源使用数量。

公式(5)中，评价函数COST值越高，与其相对应分割的评价越高， 因此选择具有最大COST值所对应的分割为当前节点的最优分割。

需要说明的是，评价函数COST计算方式不限于公式(5)，只要能 够表示出PGCN与PRUN之间大小差别关系的函数都可以作为评价函数 COST，如评价函数可以表示为其中，k1、a1、 k2、a2均为任意常数。

在步骤143，将每一节点的最优分割转换为相应改进逻辑单元，包 括转换为LUT4、LUT5、LUTAND、LUTOR。

在步骤144，去除步骤143中的冗余改进逻辑单元，包括去除冗余的 LUT4、LUT5、LUTAND或LUTOR，从而完成由通用组合逻辑电路到改进 逻辑单元级别电路的工艺映射。

显而易见，在不偏离本发明的真实精神和范围的前提下，在此描述的 本发明可以有许多变化。因此，所有对于本领域技术人员来说显而易见的 改变，都应包括在本权利要求书所涵盖的范围之内。本发明所要求保护的 范围仅由所述的权利要求书进行限定。