研究文章|开放获取
基于bdd的低功耗DTIG FinFET电路拓扑优化
摘要
提出了一种基于二叉决策图表示的逻辑综合方法。该方法针对双阈值独立门(DTIG) FinFET电路进行了优化。详细阐述了基于bdd的拓扑优化算法。通过提取算法提取BDD的几种特征子图结构,再将其反馈到映射算法中,最终得到基于预定义DTIG FinFET逻辑门的优化电路。通过与ABC、直流工具的比较,对几种MCNC基准电路进行了测试。仿真结果表明,所提出的综合方法可以提高DTIG FinFET电路的性能。
1.介绍
作为一种3D晶体管,FinFET比传统器件更高效,因为它可以抑制短通道效应(SCE)和漏极诱导势障降低(DIBL) [1- - - - - -6]。FinFET可以在common-gate (CG)模式下,两个门是联系在一起的自然,可以像一个传统的单扇设备性能改善,或在门阀(IG)模式下,两个盖茨可以作为两个分离的单扇系列设备并行或特殊条件(2]。
现今的超大规模集成电路通常采用“标准单元”方法设计[7]。在设计流程中,综合是将高层设计转换为由标准单元组成的低层网络表的一个重要过程。目前,标准单元库基本上是在CMOS或CG FinFET器件的基础上构建的。综合工具,如商业工具如Synopsys设计编译器(DC),公共领域工具如ABC [8和合成算法,如基于因数分解的方法,通常利用这些单门标准单元库来优化电路拓扑。然而,根据我们的研究,基于DTIG finfet的电路具有优异的性能,可以用于现代VLSI电路[9- - - - - -11]。因此,开发一种基于DTIG FinFETs的综合检测方法显得尤为迫切。
二值决策图作为一种强大的逻辑函数表示,在计算机科学中被广泛应用于求解图算法、矩阵运算甚至人工智能问题。也可应用于VLSI设计中,构建电路拓扑,检测和优化电路[12- - - - - -14]。BDD的效率总是由函数的可变顺序决定的。由于变量排序问题是一个np完全问题[15,16,已经发现有许多近似启发式方法可以有效地解决这个问题[12,17- - - - - -19]。
本文描述了一种基于BDD技术的电路拓扑优化方法,利用预定义的DTIG FinFET基本逻辑单元组成DTIG FinFET电路。它是这样组织的。节2,简要介绍了预先定义的DTIG FinFET逻辑门3.给出了BDD图中特征模块提取的一些定理和算法。映射算法也包括在部分3.。而在部分4通过MCNC基准测试,验证了算法的有效性。最后,我们在部分结束5。
2.DTIG FinFET单元库
与CMOS或CG FinFET等单栅器件相比,DTIG FinFET利用低门限(low- -)可以设计出更灵活的电路 )和高阈值(高收入 )设备(2,3.,9,11,20.]。我们已经构建了一个用于进一步使用的迷你DTIG FinFET逻辑单元库,如图所示1是两个例子和他们的CG比较。DTIG FinFET逻辑单元比CG FinFET逻辑单元具有更紧凑的结构,因此在晶体管计数、延迟和功耗方面比CG FinFET单元具有更多的优势,如表中所示的例子1。图书馆的所有大门,都是由矮门组成的晶体管和高从TCAD仿真中提取参数的,已经被Hspice使用UC Berkeley的BSIMIMG模型验证[21]。
|
(a)与非
(b),也不
3.DTIG逻辑电路的合成算法
首先给出了BDD和特性结构的一些定义。然后,给出了一些与BDD子图提取相关的定理并加以证明。最后介绍了基于bdd的提取算法和映射算法的实现。
3.1。定义
二元决策图由Akers提出[22作为逻辑函数的一种表示方法。基于BDD的方法在超大规模集成电路的表示和设计中得到了广泛的应用[23]。为了便于进一步讨论,我们首先介绍了与BDD及其子图提取相关的几个定义。
定义1(二进制决策图(BDD))。BDD的定义载于[22,24详细的;这里我们简要描述一些概念。一个BDD,如图所示2(a),是一个有根有向无环图,用来表示一个布尔函数为 BDD图可以用形式语言表示为 ,其中V和E分别为节点集和边集。V包含两种节点,分别为非终端节点(图中为圆形)和终端节点(图中为块状)。每个非终端节点,标记一个输入变量 ,有两个孩子,低 和高 ,两个相对边,其他的 和然后 ,分别连接到两个子节点。在这张纸上其他的 和然后 图中边分别用虚线和实线表示。一个终端节点 没有任何子边和传出边,只标记了一个值 。
当使用BDD计算逻辑函数时 ,我们从根节点(这里假设是根节点)递归计算函数 )到终端节点0或1: 在哪里互补逻辑是什么 。因为0和任何逻辑的生成都是0,所以我们可以省略从根到0终端的路径,而保留从根到1终端的计算。
本文中提到的BDD实际上是指简化有序二值决策图(ROBDD) [25- - - - - -27],它是一种变量BDD,输入变量特别有序,结构简化,节点不同。文献中通过对变量进行有效排序和去除冗余变量,从BDD中得到ROBDD的算法很多[15- - - - - -19]。
定义2(特征结构)。特征结构是BDD中的一种特殊子图, ,它可以映射到DTIG FinFET基本逻辑门,如和/NAND,或/NOR, AOI, XOR,和MUX。在这里子图在吗根植于以及它的子孙后代。
从图2(a),我们可以提取一些BDD子图,如图所示2(b) -2(f)其中,以数字表示的子图2(c) -2(e)可通过DTIG FinFET逻辑门实现,分别为AOI、OAI和NOR。因此,这些结构都是特征结构。例如,图2(b)是从图中提取的子图2(a)可由AOI细胞实现的,并图2(c)可通过OAI实现,如图所示2(h)图中结构2(f)不能映射到任何逻辑单元;因此,它不是一个特征结构。
另一方面,对于BDD中的非终端节点,我们总是可以通过一个MUX单元直接实现[22,28]。因此,我们可以将BDD映射到(1)到一个基于mux的网络列表,如图所示2(g)。
3.2。提取算法的定理
定理3。用于非终端节点对于BDD,我们假设它的两个子组件是与节点功能和与节点功能 。如果非终端节点与函数它的两条向外的边之一连接着另一条边连接到或 ,节点组 可以构造为AND/NAND/OR/NOR的特征结构。
证明。假设==
,
=和=
,如图3.(一)。
根据定义1,有一个函数显示在(3.)及衍生词(4)和(5)从图3.(一)。
从(4)和(5),我们可以将BDD子图映射到NAND、AND、OR和NOR的四个特性结构之一,如图所示3.(b) -3.(e)。
类似地,其它情况也满足定理的条件3.会得到类似的结果,也很容易证明。
定理4。对于节点组
满足定理的条件3.,假设存在非终端节点与函数和是一个普通的孩子吗和和只是个孩子的吗
,当一个外向边连接节点另一条边连接到node
,然后节点
,
,
,
,
它们的相对边缘构成了三输入与/NAND/OR/NOR逻辑的特征结构。
否则,当一个外向边连接节点另一条边连接到node或
,节点
,
,
,
,
它们的相对边缘构成了三输入AOI/OAI逻辑的特征结构。
证明。首先我们考虑如图所示的第一种情况4(一)。
假设=高=低=低和=低
,根据(2)定义1,有6)及其推导如下:
从(7)和(8,我们可以得到如图所示的结果4(b) -4(e)。
现在我们考虑定理中的另一种情况4;假设=
,
=
,
===和=
,根据(2)定义1,有9)及其推导如下:
从(10)和(11,我们可以得到定理的结果4。
定理5。为两个节点 , 在BDD图中,假设是低孩子和高的孩子同时,如果低孩子有两条向外的边,然后和其他的,连接到和 ,分别为,高孩子有两条向外的边,然后和其他的,连接到和 ,分别。子图包括 , , , 可以构造为XOR/XNOR逻辑的特性结构。
证明。从定理5,我们可以用图形来表示5。
根据(2)定义1,我们有
从(13),子图可以构建为XOR/XNOR逻辑,如图所示5(b)和5(c)。
3.3。基于bdd的节点提取算法
根据上述定义和定理,我们开发了一个给定BDD的特征结构提取算法,该算法包含四个子程序来完成提取过程。子程序1从一个输入逻辑函数f中输出BDD图的降阶排序形式,通过子程序2到子程序4依次得到特征结构的BDD子图。在每个子例程中,BDD的某些部分被标记为不同的特性结构。算法流程的顺序是经过精心安排的。如表所示1在DTIG FinFET单元库中,NAND/NOR单元比单栅门减少更多的晶体管数量,AOI/OAI/NAND3/NOR3单元减少第二,XOR单元最少。特征结构的提取顺序就是这样,以得到最大的改进。当整个算法过程完成后,我们将得到优化后的BDD和特征结构,并将其输入到映射算法中进行进一步处理。
在算法的子程序1中,如算法所示1,我们使用与传统排序算法类似的排序算法从输入逻辑函数生成一个初始的降阶BDD冒泡排序算法。当子程序1完成后,将得到最优有序BDD形式。
算法的子程序1: | |
输入: | |
输出: :BDD形式的节点集 | |
1:←bdd_init | |
2:sum_src←bdd_nodecount ( ) | |
3:为i = 1来n做 | |
4:为j =我来n做 | |
5:bdd_swapvar | |
6:sum_ex←bdd_nodecount ( ) | |
7:如果sum_ex≤sum_src然后 | |
8:sum_src←sum_ex | |
9:其他的 sum_ex > sum_src | |
10:bdd_swapvar | |
11:如果 | |
12:结束了 | |
13:结束了 |
子程序2,如算法所示2,寻找父亲每个节点的在最优有序的BDD从子例程1。
subroutine2算法: | |
输入: :子例程1中的节点集 | |
输出: :和/NAND2子图的集合 | |
输出: :OR/NOR子图的集合 | |
1:为每一个v我在 做 | |
2:←儿童(v我) | |
3:为每一个vj在 做 | |
4:如果低然后 | |
5:如果高(vj) = vx或高(vj) = vy则 | |
6:马克 | |
7:静止 | |
8:如果 | |
9:其他的如果高然后 | |
10:如果低或低然后 | |
11:←马克 | |
12:Gsa | |
13:如果 | |
14:如果 | |
15:结束了 | |
16:结束了 |
我们纪念作为一个父亲和 , 作为两个孩子 。如果节点组( , , , )满足定理的条件3.,即,两个和(或 )是…的孩子我们提取包含节点的子图 , , , 和它们的相对边,然后将子图标记为OR/NOR的特征结构和/或与非 。当这个子程序完成时,OR/NOR或AND/NAND的所有特征结构被提取并存储在集合中静止和Gsa,分别。
算法的子程序3,如算法所示3.,搜索节点组( , , , , )哪一个满足定理的条件4。首先检查结果集中的每个子图Gsa从子程序2和原始BDD图集从子程序1;如果一个节点存在于哪个满足定理的情况4,我们提取一个包含节点的新子图 ,以及集合中对应的子图Gsa并将新子图标记为AND3/NAND3或AOI的新特征结构。然后,我们将这个特征结构存储到集合中Gsa3用于AND3/NAND3或设置Gsaoi分别所有。最后是集合中对应的子图Gsa应该被删除,因为它已经被新生成的特性结构覆盖了。
根据定理5,子程序4的算法,如算法所示4,从子例程1中搜索排序最优BDD中的特殊节点组,并将其构造为新的特征结构。如果一个群的节点满足定理的条件5, (a)一个节点(记为 )其他两个节点的父节点(表示为?和 )对于同一个变量,(b)存在两个相同子节点和 ,和(c)=和= ,然后提取组及其边缘作为异或逻辑的特征结构,并存储到集合中Gsxor。
子程序4的算法 | |
1:输入:G :子例程1中源BDD的节点集 | |
2:输出:Gsxor :XOR/NXOR子图的集合 | |
3:为每一个vk在G做 | |
4:为每一个v我在G做 | |
5:为每一个vj在G做 | |
6:如果低(vk)=v我和高(vk)=vj或 | |
高(vk)=v我和低(vk)=vj然后 | |
7:如果值(vj)=值(v我)然后 | |
8:如果低(v我)=高(vj)和高(v我)=低(vj)然后 | |
9:(vx,vy)←儿童(v我,vj) | |
10: | |
11:Gsxor← | |
12:如果 | |
13:如果 | |
14:如果 | |
15:结束了 | |
16:结束了 | |
17:结束了 |
当这些子程序全部完成后,该提取算法生成给定逻辑函数的最优有序BDD形式,并得到BDD中的所有特征结构。
3.4。映射算法
上面描述的提取算法只是为了简化布尔函数。在接下来的逻辑合成步骤中,我们需要使用映射算法将逻辑门替换为单元库中的物理单元。提出了四步特征结构映射算法。在步骤1中,在从提取算法中读取BDD及其子图之后,我们排除冗余或被覆盖的子图。然后,在步骤2中,我们将源BDD映射到一个完全由MUXs组成的电路,并将特征结构映射到IG FinFET逻辑门。在第三步中,我们用逻辑单元替换一些MUXs子电路,给出最终的优化电路。步骤1到步骤3显示为图中的示例2(一)-2(h),结果如图所示2(我)。
4.算法实现
提取和映射等综合算法均在MATLAB平台上实现,为了比较电路优化效果,还将ABC和直流综合工具应用于同一电路中。为了进行公平的比较,所有方法都使用我们在Section中构建的相同的DTIG FinFET单元格库2。最后,利用Hspice和UC Berkeley的BSIMIMG模型对ABC、DC和所提方法的所有电路进行了仿真[21]。数字6给出了MCNC基准电路的仿真结果。
(一)
(b)
(c)
(d)
如图所示6(一),对于几乎所有被测试的电路,通过这项工作优化的电路中的晶体管数量在比较中是最少的。因此,在大多数情况下,该方法可以得到最有效的面积,因为面积的占用是由晶体管的数量决定的。
平均功耗可表示为 在哪里为电路的平均功率,N是电路中的晶体管计数,Pav1是晶体管的平均功率,P低和P高一个的平均功率低吗和高- - - - - -分别是IG FinFET和p低和p高有低的可能性吗和高- - - - - -IG FinFET在一个电路中,分别。
从(14)时,如果各种电路中晶体管的数量相近,则电路的平均功率是由电路中晶体管的数量决定的。从图6 (b),我们可以看到功耗的趋势接近图中所示的晶体管计数趋势6而几乎所有由本工作合成的电路功耗都是最小的,符合(14)很好。时延分析比功耗分析复杂得多。电路的最大延迟取决于关键路径。关键路径上的晶体管越多,延迟就越大。对于DTIG FinFET电路,高阈值器件具有更大的延迟,因为它具有较低的通流,这进一步降低了开关速度,增加了延迟。如图所示6 (c)结果表明,该电路在延时方面没有明显的优势。
功率延迟产品(PDP)可以更全面地评估电路,因为它既考虑延迟,又考虑功耗。如图所示6 (d)所合成的电路与ABC和直流电路相比,都具有PDP的明显优势。
5.结论
本文提出了一种基于bdd的合成方法来优化DTIG FinFET电路。我们搜索输入逻辑的BDD图,以找到特征结构并将其映射到DTIG FinFET基本逻辑门。通过对MCNC基准电路的仿真,将该算法与ABC和DC算法进行了比较。结果表明,该方法可以显著提高DTIG FinFET电路的占地面积、功耗和PDP性能。
数据可用性
所有用于支持这项研究的数据都已包含在论文中,可以免费访问。
的利益冲突
作者声明,本论文的发表不存在任何利益冲突。
致谢
本研究以国家自然科学基金61671259号和浙江省自然科学基金(浙江省自然科学基金61671259号)资助的研究为基础。LY19F010005)。本研究得到国家自然科学基金的资助61671259浙江省自然科学基金[LY19F010005]。
参考文献
- "最先进的硅器件微型化技术及其挑战,"IEICE电子表达第11卷,no。10,文章编号20142005,2014。视图:出版商的网站|谷歌学术搜索
- 《FinFETcircuit design》,P. Mishra, A. Muttreja, N. K. Jha,纳米电子电路设计,第23-54页,2011年。视图:谷歌学术搜索
- M. Rostami和K. Mohanram,“用于低功率逻辑电路的双vth独立门finfet,”集成电路和系统的计算机辅助设计第30卷,no。3,第337-349页,2011。视图:出版商的网站|谷歌学术搜索
- s.chaudhuri和N. K. Jha,“不同FinFET风格的FinFET逻辑电路优化:在较高的电源电压下可能的低功率”,in超大规模集成电路设计国际会议和2014嵌入式系统国际会议论文集,第476-482页,2014。视图:谷歌学术搜索
- 多阈值电压FinFET时序电路,"超大规模集成(VLSI)系统的IEEE会刊第19卷,no。1, 2011年151-156页。视图:出版商的网站|谷歌学术搜索
- “基于稳健和低数据依赖的ffet的SRAM阵列的层次设计”,台北IEEE/ACM纳米尺度架构国际研讨会论文集,第63-68页,2015年。视图:谷歌学术搜索
- 王,崔,廖,“基于混合背偏技术的低功耗高性能FinFET标准电池”,电子交易E99卷。C,没有。8,第974-983页,2016年。视图:出版商的网站|谷歌学术搜索
- R. Brayton和A. Mishchenko,“ABC:学术性的工业实力验证工具”,刊于计算机辅助验证会议,国际会议,第6174卷,第24-40页,英国爱丁堡,CAV 2010。视图:出版商的网站|谷歌学术搜索
- "用于小型低功耗逻辑电路的双阈值独立门ffet的优化",李建民,2002第16届IEEE纳米技术国际会议论文集- IEEE NANO 20162016年8月,日本仙台,529-532页。视图:谷歌学术搜索
- “利用双阈独立门ffets的新型SRAM细胞”,国立中山大学生物工程研究所硕士论文2017年第17届IEEE纳米技术国际会议论文集,第358-359页,美国宾夕法尼亚州匹兹堡,2017年7月。视图:谷歌学术搜索
- 倪,胡,杨,朱,“双阈独立门fet和SRAM细胞的综合优化”,有源和无源电子元件,第2018卷,文章编号4512924,10页,2018年。视图:出版商的网站|谷歌学术搜索
- 王建民,“二元决策图变序问题之遗传演算法”,台北遗传算法基础国际会议论文集, 2005年第1-20页。视图:谷歌学术搜索
- 《利用并行遗传算法减少bdd的进展》,载于美国科大、莫雷拉、达尔比、C. Universitrio和L. Nova出版社IEEE第10届逻辑与综合国际研讨会论文集(IWLS2001),第84-89页,2001。视图:谷歌学术搜索
- P. Porwik, K. Wrobel,和P. Zaczkowski,《关于二元决策图尺寸缩减的一些实用评论》,IEICE电子表达第3卷,no。3,第51-57页,2006。视图:出版商的网站|谷歌学术搜索
- “二元决策图之最优变数排序问题之复杂性”,国立台湾科技大学资讯工程学研究所硕士论文算法与计算学报,国际学术研讨会,931993年12月,香港。视图:谷歌学术搜索
- B. Bollig和I. Wegener,“改进OBDDs的变量排序是np完备的,”IEEE计算机汇第45卷,no。9日,页。993 - 1002。视图:出版商的网站|谷歌学术搜索
- 刘建民,“基于交错的可变排序方法的二值决策图”,台北IEEE/ACM计算机辅助设计国际会议论文集,1993年。视图:出版商的网站|谷歌学术搜索
- 罗柏之静态分离遗传演算法之研究>,载于科学计算的符号和数字算法国际研讨会论文集,2011年。视图:谷歌学术搜索
- “IDGBDD:用ID3改进BDD重排序中的遗传算法”,M. Takapoo和M. B. ghaznavio - ghoushchi,《BDD重排序中的遗传算法》电气工程/电子计算机通信与信息技术国际会议论文集,2010年。视图:谷歌学术搜索
- “双阈值独立门式光纤场效应元件之低功率逻辑电路之拓扑优化方法”,国立中山大学电子科学与工程研究所硕士论文第27届电力与时序建模、优化与仿真国际研讨会论文集,PATMOS 2017, 1-6页,希腊,2017年9月。视图:谷歌学术搜索
- N. Paydavosi, S. Venugopalan, Y. S. Chauhan等," BSIM-SPICE模型使FinFET和UTB IC设计成为可能"IEEE访问,第1卷,第201-215页,2013年。视图:出版商的网站|谷歌学术搜索
- s·b·埃克斯,《二元决策图》,IEEE计算机汇第27卷第2期1978年,第509-516页。视图:出版商的网站|谷歌学术搜索
- 南道一,“BDD/ZDD技术:简史与近期活动”,信息和系统交易E96卷。D,没有。2013年,1419-1429页。视图:出版商的网站|谷歌学术搜索
- R. Drechsler和D. Sieling,“二元决策图的理论和实践”,国际技术转让软件工具杂志第3卷,no。2,第112-136页,2001。视图:谷歌学术搜索
- 布尔函数操作的基于图形的算法,"IEEE计算机汇,第C-35卷,no。1986年,第677-691页。视图:出版商的网站|谷歌学术搜索
- M. Raseen, P. Chandana Prasad,和A. Assi,《ROBDD复杂性的有效估计》,集成,VLSI杂志第39卷,no。3,第211-228页,2006。视图:出版商的网站|谷歌学术搜索
- “一个BDD包的有效实现”,北京第27届ACM/IEEE设计自动化会议论文集1990年6月,第40-45页。视图:谷歌学术搜索
- j.m. Rabaey A. P. Chandrakasan和B. Nikolic,数字集成电路-设计的视角,普伦蒂斯-霍尔公司,2003年。
版权
倪海燕等版权所有这是一篇开放获取下发布的文章知识共享署名许可,允许在任何媒体中不受限制地使用、发布和复制原创作品,只要原稿被正确引用。