（电路与系统专业论文）逻辑综合中的工艺映射算法研究[电路与系统专业优秀论文].pdf

! 童奎堕查兰堡主兰竺兰二旦一 逻辑综合中的工艺映射算法研究 摘要 本论文的主要研究方向为“逻辑综合”中的“工艺映射”算法研 究。期间，作者先后将研究成果撰写成了十一篇学术论文，且大多 已先后被国家中文核心期刊录用( 详情请见附在论文后的“攻读硕 士期间发表论文情况”) 。本硕士论文的主要内容就是基于以上研究 成果撰写而成。 本文所讨论的“工艺映射”也被称作“库单元绑定”，它是超大 规模集成电路设计过程中非常重要的一环。它的目标是：通过特定 的方法，把一组布尔网络表述的逻辑功能用具体的库单元实现。具 体讲，也就是把一些实际工艺库中的单元( 元素) 相互连接，以实 现所需的逻辑功能。 “工艺映射”提供了一种用物理结构完全表达电路逻辑功能的设 计途径，在实际的工艺技术和逻辑功能设计之间搭起了桥梁。基于 “工艺映射”方法的电子设计自动化软件是超大规模集成电路的基 本设计工具。而映射过程中所采用算法的可靠性和对电路的优化效 果，对于最终设计出的电路性能有非常重要的影响。 本论文中，作者首先对工艺映射的基本原理和过程做了比较详细 的论述和分析。在此基础上，做了以下工作： 1 ) 在分析了现有“工艺映射”方案的缺点后，在原有流程的基 础上，提出了自己的全新的“工艺映射”设计流程。 2 ) 针对“主题图”分解后的优化问题，提出了“再分解”这一 新的优化技术。该算法首先在现有逻辑运算规则的基础上，推导出 圭查奎望奎兰竺主兰些堡三一 了一套非常全面的逻辑变换。接着以此为基础，针对主题图的速度 优化和面积优化问题提出了“速度优化设计方法”和“面积优化设 计方法”。速度优化设计方法尽量减小“最大延时路径”上门的数量， 并使主题图中从基本输入到基本输出的各条线路延时的差距尽量缩 小，达到减少整个主题图延时的目的。面积优化设计方法使主题图 中门的数量尽量减少，从而达到减小实际网表面积目的。同时，为了 使该方法能适应不同的匹配算法，我们还提供了一些衍生的设计工 具。 3 ) 提出了一种新的覆盖方法，我们称它为“可选择覆盖”。这种 新的“覆盖”方法把传统的”覆盖”和“匹配”两个步骤加以融合， 并采用了一种新的“可选择结点”。这种虚拟结点在该方法中的使用， 使该“覆盖”方法可以灵活的组合不同匹配算法生成的结果。 4 ) 最后，我们在“逻辑综合”过程的最后一个步骤中提出了“逻 辑加速优化”设计方法。该方法以“多级逻辑变换”技术为核心，集中 了各种优化变换，并合理的加以安排。其突出的优点是：在优化过 程中，既考虑了与工艺无关的优化，也考虑了工艺库单元的实际延 时性能；并且，由于对原电路进行了较大规模的重建，所以该方法 可以得到传统“分解”技术无法生成的逻辑结构0 关键词：逻辑综合， 工艺映射，逻辑分解，布尔网络，主题图 ：i 二童奎里茎兰堡主兰j 星兰l 三一 s t u d i e so n a l g o r i t h mo ft e c h n o l o g y m a p p i n gi nl o g i c s y n t h e s i s a b s t r a c t t h er e s e a r c hd i r e c t i o no ft h i sp a p e ri s t e c h n o l o g ym a p p i n g o f l o g i c s y n t h e s i s ”d u r i n gt h er e s e a r c h ，t h ea u t h o rh a sw r i t t e ne l e v e np a p e r st o r e p o r tt h er e s e a r c ha c h i e v e m e n t s ，m o s to f w h i c hh a v eb e e na c c e p t e db y n a t i o n a lc o r ej o u r n a l s t h i sm a s t e rd e g r e et h e s i s i sb a s e do nt h e s e a c h i e v e m e n t s t e c h n o l o g ym a p p i n gd i s c u s s e d i nt h i s p a p e ri s a l s oc a l l e d “c e l l l i b r a r yb i n d i n g i ti s av e r yi m p o r t a n ts t e pd u r i n gt h ed e s i g no fv l s i t h e p u r p o s eo fc e l l l i b r a r yb i n d i n g i st oi m p l e m e n tt h el o g i cf u n c t i o n so f ag r o u po fb o o l e a nn e t w o r k sb yu s i n gs o m el i b r a r yc e l l s i nf a c t ，i ti st h e p r o c e d u r e t o i m p l e m e n tt h el o g i c f u n c t i o n s t h r o u g hc o n n e c t i n g s o m e l i b r a r yc e l l st oo t h e r s t e c h n o l o g ym a p p i n gi s ad e s i g nm e t h o dt oi m p l e m e n tt h ec i r c u i t s l o g i cf u n c t i o n sw i t hp h y s i c a ls t r u c t u r e s i ti su s e d a sa b r i d g eb e t w e e n t h e t e c h n o l o g y a n d l o g i c f u n c t i o n s t h ee d as o f t w a r eb a s e do nt h e t e c h n o l o g ym a p p i n gi st h eb a s i cd e s i g nt o o lo fv l s i t h ec a p a b i l i t yo f t h ea l g o r i t h mo f t e c h n o l o g ym a p p i n gd i r e c t l ya f f e c t st h ef i n a lr e s u l to f t h e d e s i g n i nt h i st h e s i s ，t h et e c h n o l o g ym a p p i n g st h e o r ya n di t sa l g o r i t h ma r e a n a l y z e d a n dt h ef o l l o w i n gw o r ki sd o n e ： 1 ) a c c o r d i n gt o t h ed r a w b a c k so ft h e t e c h n o l o g ym a p p i n g ，n e w t e c h n o l o g ym a p p i n g sf l o wb a s e d o nt h eo l do n ei sg i v e n 圭童銮望查兰堡主兰竺堡苎 2 1an e wt e c h n o l o g yn a m e d “l o g i cr e d e c o m p o s i t i o n ”w h i c ha i m sa t t h eo d t i m i z a t i o no ft h es u b j e c t g r a p hi sp r e s e n t e d t h i sa l g o r i t h m f i r s t b u i l d s an e wk i n d 。o fl o g i c t r a n s f o r m a t i o n s t h e n p u t f o r w a r da o d t i m i z a t i o nm e t h o dt h a ta i m s a tt h ea r e a s o p t i m i z a t i o n a n dd e l a y s o p t i m i z a t i o no f t h es u b j e c tg r a p h t h e s et w ok i n d so fo p t i m i z a t i o na r e c a l l e d a s “d e s i g na p p r o a c h o f s p e e do p t i m i z a t i o n a n d d e s i g n a p p r o a c ho fa r e ao p t i m i z a t i o n ”l o g i c t r a n s f o r m a t i o n t e c h n o l o g y i s u s e d i n d e s i g na p p r o a c h o f s p e e do p t i m i z a t i o n ”t o r e d u c et h e d i f f e r e n c eo ft h ed e l a y so fe a c hp a t hf r o mp r i m a r yi n p u tt op r i m a r y o u t p u t b y t h i s w a y , t h ed e l a y o ft h ew h o l es u b j e c t g r a p hw i l lb e d e c r e a s e d l o g i ct r a n s f o r m a t i o nt e c h n o l o g y i su s e di n “d e s i g na p p r o a c h o fa r e ao p t i m i z a t i o n ”t or e d u c et h en u m b e ro ft h eg a t e so ft h es u b j e c t g r a p h b y t h i sw a y , t h ea r e ao ft h ec i r c u i tw i l lb ed e c r e a s e d a tt h es a m e t i m e ，s o m ed e s i g n t o o l st h a td e r i v ef r o mo l do n e sa r ep r o v i d e ds ot h a tt h i s m e t h o dc a nb eu s e dw i t hd i f f e r e n tm a t c h i n ga l g o r i t h m 3 ) a n e wd e s i g nm e t h o dc a l l e d “o p t i o n a lc o v e r i n g ”i sp r e s e n t e d t h i sn e w d e s i g n m e t h o d i n c o r p o r a t e s m a t c h i n g ”a n d c o v e r i n g ” t o g e t h e r b yu s i n gan e wt y p eo fo p t i o n a ln o d e ，t h em e t h o dc a nf l e x i b l y c o m b i n et h es c h e m e st h a ta r eg a i n e df r o md i f f e r e n tk i n d so fm a t c h i n g m e t h o d s 4 ) a tl a s t ，an e wm e t h o dc a l l e d “l o g i cs p e e d - u po p t i m i z a t i o n ”i s p r e s e n t e d t h ek e ys t e p o ft h em e t h o di s m u l t i l e v e l l o g i c t r a n s f o r m a t i o n ”，i t h a st w ov i r t u e s ：f i r s t ，i tc o n s i d e r sn o t o n l y t h e t e c h n o l o g yi n d e p e n d e n to p t i m i z a t i o nb u ta l s ot h ec e l ll i b r a r y sc a p a b i l i t y ； s e c o n d ，i tr e c o n s t r u c t st h ec i r c u i t s s t r u c t u r es ot h a tt h ec i r c u i tc a ng e t s o m en e w l o g i cs t r u c t u r e sw h i c hc a nn o tb eo b t a i n e df r o mc o n v e n t i o n a l l o g i cd e c o m p o s i t i o n 圭查窒望盔兰堡圭堂焦堡兰一 k e yw o r d s ：l o g i cs y n t h e s i s ，t e c h n o l o g ym a p p i n g ，l o g i c d e c o m p o s i t i o n ，b o o l e a n n e t w o r k ，s u b j e c tg r a p h 前言 前言 目前，电子信息产业已经成为现代代信息社会文明与进步的标志，它也是本 世纪以来发展得最快的产业。可以预计在未来的20 年中，电子信息技术将依然 是推动人类社会生产力向前发展的强大动力和源泉。 电子信息技术的硬件载体是超大规模集成电路( v l s i ) ，其中又分为通用集成 电路和专用集成电路两类。存储器等大量生产且设计规则的电路被称为通用集成 电路，面向某一应用背景而专门设计的集成电路被称为专用集成电路( a s i c ) 。 目前，专用集成电路的设计复杂度不断提高，这就对a s i c 芯片的设计能力 提出了极高的要求。统计表明，对于个规模较大的专用集成电路设计，通常需 要15 20 人用18 个月以上的时间完成，每个设计者的平均设计能力大约为 每天十几个器件。于此同时，专用集成电路的设计复杂度却成指数增加。1 98 4 年专用集成电路的设计所要求的电路规模大致在几十万个晶体管，目前已经达 到了百万量级的晶体管数量，估计到20 10 年，这个数字将上升到千万量级的 晶体管。这就意味着如果不改变设计方法，提高设计能力，目前的设计能力将远 远不能满足需要。在这种情况下e d a ( 电子设计自动化) 技术和产品应运而生， 它的出现大大提高了劳动生产率，使大规模，高速度，高质量的完成超大规模集 成电路的设计成为可能 1 。 据统计，目前世界电子信息产业的总市场额度超过1 0 0 0 0 亿美元，而支撑整 个电子信息产业的硬件载体一微电子产品大约有2 0 0 0 亿美元的市场，其中专用 集成电路( a s i c ) 的市场大约为3 5 0 亿美元，而e d a 产品的市场份额大约2 0 亿美 元。也就是说，仅仅2 0 亿美元的e d a 产品支撑起了超过万亿的整个电子信息产 业。目前e d a 产品的发展非常迅猛，在发达国家，有大约6 0 的芯片设计采用 了e d a 自动设计工具。e d a 设计技术融合了计算机技术、微电子技术和智能化 技术，复杂的电子产品开发越来越依赖于强大的e d a - 1 - 具。 可惜的是，我国目前在微电子领域严重落后于发达国家。在e d a 工具领域 更是受制于人。目前使用的e d a 设计软件基本上完全被s y n o p s y s 和a v a n t 等少 数几个跨国公司所控制。在这种背景下，越来越多的的高校和科研院所加强了对 e d a 设计工具的研究和开发 2 。 在这种背景下，上海交通大学大规模集成电路研究所的全体老师和同学分为 前言 三个课题小组，在林争辉教授的带领下，对电子设计自动化这一重要领域展开了 研究工作，并已经取得了一定成果。 本论文的主要研究方向即为e d a 设计工具中的逻辑综合部分。强大的e d a 工具包括非常多的功能模块，而每一部分都有特定的开发难度和庞大的编程工作 需要完成。而本人在e d a 研究第- d , 组中的主要任务是“工艺映射”部分算法 的研究开发工作。 由于硕士生的研究时间非常有限，我的硕士论文难免存在问题和不足，甚至 可能有错误。不过，作为国家培养的硕士生，能在学习期间为祖国的e d a 工具 开发领域贡献微不足道的力量还是使我感到了莫大的安慰和满足。 第一章逻辑综合概述 第一章逻辑综合概述 前言： 本论文的研究目标是“逻辑综合”中“工艺映射”。为了清楚明了的阐述整个 论文工作的原理和意义，在介绍我们具体研究的内容之前，必须首先剖析目前主 要的e d a 工具的工作过程、运行原理和其局限性。 1 1 设计综合 目前，e d a 工具开发的热点是自动综合工具 7 】 1o 】。设计综合是不同层次和 不同形式的设计描述之间的转换，自动综合工具可以帮助设计师自动完成转换。 在综合过程中，设计者的任务是把各种设计要求作为一种约束条件加给设计并按 指定工艺库做映射转换。综合器将通过各种综合算法并以一种具体的工艺背景实 现设计目标所规定的优化设计。 设计综合的流程一般是高层设计语言输入，经高层次综合、r t l 级综合产生 r t l 结构，再经逻辑综合后输出实际网表，最后由版图综合完成布局布线。具体 流程见图1 1 。 图1 1 数字系统设计流程图 f i g1 1d e s i g nf l o w o f d i g i t a ls y s t e m 设计综合的研究从逻辑综合开始【3 。同时，逻辑综合也是本论文的研究重点。 第一章逻辑综合概述 - - _ _ _ _ _ _ - - _ - _ _ 一一 从上图我们可以看出，逻辑综合将在选定r t l 结构的基础上完成硬件的设计流图 向门级结构描述的转换。它与版图综合相衔接，即逻辑综合的结果将作为版图综 合的输入数据，也就是说它包括工艺库单元组成的网表信息和要满足的约束条件 与目标集合。这些约束条件和目标主要有： 1 ) 关键路径的延时 4 】； 2 ) 芯片总面积； 3 ) 功耗： 4 ) 负载能力； 这样，版图综合系统可以根据这些约束条件和目标进行以性能优化为目标的版图 设计了。 1 2 逻辑综合 逻辑综合是指从寄存器传输级描述或从布尔方程、真值表、状态表等描述到 逻辑级网表描述的综合过程。无论设计目标是最小化延时时间、或是最小化面积、 或是二者的折衷、逻辑综合都力图能提供较为优化的逻辑网表描述。 逻辑综合通常用来处理纯组合逻辑、可以对从寄存器传输级描述语言中抽取 的逻辑进行综合( 见图1 2 ) 。如果该描述包括有存储结构，则通常将对其划分成组 合逻辑块和存储单元两类。对划分出的各个组合逻辑模块分别进行逻辑综合，最 后将综合结果重新连接，从而得到个完整的设计结果。 图1 2 组合逻辑图 f i g1 2c o m b i n e dl o g i cg r a g h 逻辑综合的目标就是：根据信号达到时间、请求时间等信息及描述产生一个 正确的实现方案。我们可以用图1 3 来描述这种过程： 蔓二兰堡望堑笪竖堕一 综合进程若输入r t l 级的v h d l 描述，对设计电路加约束、属性以及工艺库 后，将用所有这些输入产生一个优化的门级网表。本论文中讨论的逻辑综合都是 建立在r t l 设计的基础上，即设计的r t l 结构已经规定，在这种情况下研究它 的门级网表的生成 5 1 。 1 3 逻辑综合过程分析 图1 3 逻辑综合 f i g1 3l o g i cs y n t h e s i s 逻辑综合分为二级逻辑综合和多级逻辑综合两种。 二级逻辑综合通常以布尔方程、真值表或状态表作为输入，用布尔代数等方 法来进行优化。尽管二级逻辑综合取得了令人满意的结果，但是，二级逻辑网络 的扇入数会按初始输入数的指数量级增加，而且二级逻辑网络在多数情况下不如 多级逻辑网络节省面积。多级逻辑综合是实现数字逻辑的另一种方法，他适用于 多种目标技术，且适用面更广f 8 】。 多级逻辑也称为随机逻辑。由于子逻辑重用的可能性增大，多级逻辑的设计 空间比二级逻辑具有更大的自由度。所以，多级逻辑综合更加困难。多级逻辑综 合的目标是： 1 ) 最小化总体版图面积； 2 ) 最小化关键路径上的延迟时间； 多级逻辑综合分为两个阶段，第一个阶段是将寄存器传输级的描述转化为逻 辑级的描述，即将数据流描述转化为相对应的结构描述，用基本元器件、互连、 第一章逻辑综合概述 真值表来表示：第二个阶段为将这些结构描述转化为具体的电路描述形式，在这 个阶段，首先是对结构描述进行优化，得到依某种指标较优的逻辑结构表示形式， 再将这种逻辑结构映射为具体的电路，得到电路的网表。 本文研究的主要目标集中在逻辑综合的第二个阶段，这一部分的主要内容也 被称做工艺映射。由于本章是对逻辑综合总体的描述，所以在下面的小节中，我 们会对工艺映射的每一步进行大略的介绍。具体其中每一步骤的缺点、优点和我 们对其的改进将在以后的章节中详细讨论。 工艺映射的具体流程见图1 4 。 1 3 ，1 划分 f布尔网络 f划分 i工艺匹配 t f覆盖 i实际网表 图1 4 工艺映射流程图 f i g1 4d e s i g n f l o w o f t e c h n o l o g ym a p p i n g “划分“也是工艺映射的第一个步骤( 也有的算法把划分放在逻辑分解后执 行) 。“划分”将多输出网络转化为一组单输出子网来简化映射。“划分”的含义 有两重：一是使映射问题规模减小，再者将电路的组合部分和时序逻辑部分、i o 分开，后者需要特殊的映射方法。 “划分”完成后，电路可由一组单输出布尔子网络表示。根据以后算法的不 同需要，原电路可由有向无环图或树来表示。它们分别对应于其后将要提到的基 于图和基于数的匹配算法。 第一章逻辑综合概述 1 3 2 逻辑分解 工艺映射的输入是布尔网络，输出是实际网表，我们在完成从布尔网络到实 际( 也就是和具体工艺相结合) 网表的转化过程中，在“划分”后还要对布尔网 络做“分解”处理以利于以后的步骤 6 【9 。 所谓的布尔网络是一组逻辑表达式，它的各个结点可以是任意的逻辑功能组 合单元。“逻辑分解”的作用则是把布尔网络中的复杂结点单元用基本函数的形 式( 两输入的与门，与非门，或门，单输入的非门等) 表达，以便于以后的匹配和映射。 1 3 3 匹配 在“划分”之后，“工艺映射”的步骤是“匹配”。在此之前进行的“逻辑分 解”和“划分”都是对布尔网络进行与工艺无关的处理。而匹配则要把布尔网络 和实际的库单元相联系了。 匹配有两种方法：结构匹配和布尔匹配。 结构匹配是利用结构的特点来匹配。在布尔式进行代数分解后，关系式可用 树或图来表示。这样，表达式之间的匹配就可以转化为图之间的同构验证。结构 匹配分为三种：基于树的匹配、基于图的匹配和基于树的自动机匹配。匹配问题 的规模一般受限于库单元输入数的最大值。 布尔匹配可以克服上述结构匹配的缺点。利用逻辑函数可以方便地对无关项 进行操作，也就可以考虑所有匹配。而且由于启发式算法地应用，以使布尔匹配 的运算时间大大减少，逐渐可以和结构映射相比较。 不过由于算法时间和速度的考虑，大多数的商用e d a t 具依然使用的是基于树 的结构匹配算法。 1 3 4 覆盖问题 网络的“覆盖”是“工艺映射”的最后一个步骤。它的作用就是在多种可行的 匹配中，根据实际电路的要求，找到符合性能需要的最优匹配方案，并以实际网表 的形式输出。 虽然结构匹配和布尔匹配方法迥然不同，但“覆盖”过程基本相同。“覆盖” 塑= 兰堡塑堡垒壁竺 一 在所有节点的可匹配集合中选出足够的匹配来覆盖整个网络的所有顶点a 对每一 选出的匹配中，要保证每个库单元的输入和其它匹配库单元的输出相连，即覆盖 完成后，整个网络都被匹配库单元覆盖而且匹配库单元间又不相互重叠。最后从 可完成覆盖的各组匹配中选出指标( 面积、功耗等) 最优的一组匹配。 1 4 结论 在本章中，我们详细讨论了整个e d a 工具的组成和各部分的功能。并阐述了“工 艺映射”在e d a 工具中所处的地位和作用。具体介绍了“工艺映射”的全过程和 每一步骤的作用，为以后研究内容的深入做好了准备。 笙三兰堑型望塑堡垒堕望 一 第二章新型逻辑综合流程 在上一章里，我们分析了现有“工艺映射”流程的具体步骤和方法。在这一 章中，我们将简要归纳现有逻辑综合流程的缺点和我们的改进方法。传统的设计 流程见图2 1 所示： 图2 1 工艺映射流程图 f i g 2 1d e s i g nf l o wo ft e c h n o l o g ym a p p i n g 传统的逻辑分解的目的是找出较好的逻辑结构 11 。以便在以后的匹配和覆 盖中得到较优的门级网表。所以在分解的同时开发了些逻辑优化算法。目前使 用较多的逻辑分解方法有：布尔分解，代数分解和弱化分解几种。 其中，代数分解速度最快，应用简单，而且易于操作，目前大部分的综合工具 都使用这种分解方法。但是，代数分解受到分解手段的限制，无法得到全部主题 图，因而在分解的过程中往往只能得到较差的结果。 布尔分解可以得到最多的主题图，但由于方法复杂，而且分解结果本身的多 样性，所以运算速度慢。而且一个非常现实的问题是：即使分解手段允许，由于 组合方案数量很多，也根本不可能对所有的主题图都进行优化和匹配。 弱化分解则是代数分解和布尔分解的折中方案。 除了以上提到的各种分解方法的问题。在实际使用中，现有的分解方法还有 其它的不如意之处。我们把所有的问题总结归纳如下： 嚣壶煮 笙三兰堑型望塑堡垒亟堡一一一 一)受分解手段的限制，分解后得到的主题图有遗漏，优化方法可能根本 无法找到“最优的主题图”： 二)即使手段允许，找到了所有的主题图，由于组合方案数量很多，也不 可能对所有的主题图都进行优化和匹配： 三)由于这些优化算法都是建立在“工艺无关”的逻辑变换基础上，和实 际工艺库脱节，所以，逻辑上最优的主题图，在“工艺相关”的匹配中不一 定是最好的选择： 四)由于逻辑分解和匹配过程完全分离，所以，逻辑分解无法使用匹配算 法中的优化成果。 为了克服以上问题，我们提出了“逻辑再分解设计方法”和“逻辑加速优化方法”。 作为对原有设计方法的改进 1 2 。 除了对传统的分解算法进行改进和优化外，我们还分析了现有匹配和覆盖算 法的优缺点。传统的匹配和覆盖算法是相对独立的它们分为两个不同的步骤先 后完成。即，先用一种匹配算法得到几种匹配方案，再针对这些匹配方案对其进行 覆盖，找到性能最好的结果。虽然匹配的算法有很多种( 如：图匹配，自动机匹配， 树匹配和布尔匹配等等) ，但是传统的覆盖算法只能把覆盖的目标锁定为由单一 匹配算法得到的数种匹配结果。这种设计方法，无法在覆盖时灵活的利用不同匹 配算法产生的不同匹配方案 1 3 。 陈i 五一 划分 逻辑分解 逻辑再分解 可选择覆盖 逻辑加速 lr 1 级网表l 、- 。_ 。_ _ _ _ _ 。- _ 。- 。_ 。_ - 。_ _ _ _ 一 图2 2 新型工艺映射流程图 o 第二章薪型逻辑综合流程 f i g 2 2n e w d e s i g n f l o wo ft e c h n o l o g ym a p p i n g 为了解决以上问题，我们提出了“可选择覆盖”设计方法。这种算法可以根据 我们的需要和希望，搭建一个设计平台，使大多数的匹配算法都能够在上面运行， 且可以自由的组合这些匹配算法生成的结果：这样就可以有较大的解空间来进行 选择。此方法的匹配和覆盖对象是以树形数据结构表达的主题图。这种新的设计 方法把覆盖和匹配这两个步骤进行融合。在过程中引入了新型的“可选择结点”， 使覆盖原电路时，可以灵活的组合不同匹配算法提供的结果。这样，就使最后输出 的实际网表有可能是由多种匹配算法共同应用得到的。 在完全采用了本文的设计方法后，现有的设计流程就会有非常大的变化。这 种全新的设计流程见图2 2 。在以后的章节中，我们将逐项讨论我们提出的这些 新的设计方法。 第三章适应树型再分解算法的划分 第三章适应树型再分解算法的划分 前言： 从上一章的新型“工艺映射”流程我们知道，在对有向无环图( d a g s ) 应 用新型再分解算法进行优化之前，我们首先需要对其进行划分处理。 目前的划分算法很多，基于不同的优化和匹配算法，把主题图划分成多种不 同的形式。不过由于树型匹配算法的快速简单等特点，大多树商用e d a 软件都 是采用的树型匹配。所以，划分算法的目标也是把原主题图划分成为树的形式。 在本文的以后步骤中，由于我们的优化算法和新型的匹配算法都是基于树结 构主题图的。所以本章将论述把d a g 分割为一组树的形式的具体方法。划分有 两种方法，我们分别介绍如下 1 8 】。 3 1 多输出结点划分 多输出结点划分的目标是把主题图划分成一组大小，级数都各异的树。具体 步骤如下。请参考图3 1 。 图3 1 划分图 第三章适应树型再分解算法的划分 f i g 3 f g r a p ho f p a r t i t i o n 从多输出的结点开始划分。我们把这些多输出的结点分割开，它们的输出演 化为其它树的输入。而这些多输出的结点自己则成为另一棵树的“根结点”。经 过划分后的d a g 图变成了一组互不相连的树，我们可以形象的把它们比比喻为 “树林”。这种划分的缺点是限制了优化的范围，我们只能分别对这些子树进行 优化，而不能在树和树之间进行优化。 这种划分技术划分出的树的大小非常依赖于原主题图的“自然结构”，如果 这个主题图含有大量的多输出结点，则划分的结果将把主题图分成非常多的小 树。而如果原主题图的树型结构比较好，也就是很少有多输出结点，则主题图将 被划分成几个较大的树结构。 3 2 基本输出划分 另一种对d a g 图的划分方法是，我们不把多输出的结点作为子树的根结点， 而是把d a g 图的每一个“基本输出”作为根结点。我们做的划分从基本输出开 始遍历整个d a g 图，如果碰到“基本输入”则结束遍历。如果碰到其它已经“映 射”好的结点则有两种情况，一种是这个已“映射”好的结点恰好是“已映射好 单元”的输出，这时我们可以直接把它看作是“正在遍历树”的“叶子”结点； 第二种是这个结点是“已匹配好单元”的内部结点，如果这种情况发生，我们则 继续“遍历”直到找到这个“已匹配好单元”的输入为止。 3 3 结论 本章详细描述了两种快速，实用的划分方法。多输出结点划分方法将把主题 图划分成一组树，而基本输出划分方法把主题图划分成一组图。 由于以后优化方法的需要，我们的整套逻辑综合工具将使用多输出结点划分 方法。也就是，以后的逻辑再优化目标是一组已经完成划分的树。 第四章速度优化再分解设计方法 第四章速度优化再分解设计方法 前言： 在上一章中我们提到：我们希望能在划分和分解后，对布尔网络进行进一步 的优化。本章针对主题图中的延时问题，提出了“速度优化再分解”这一新设计方 法。该方法采用“逻辑变换”技术，使主题图中从基本输入到基本输出的各条线路 延时的差距尽量缩小，从而达到减小整个主题图延时的目的。 4 1 基本思想 初步的逻辑分解和划分后，布尔网络成为只含有基本函数的“树形”主题图， 即所有的简单门都只有一个输出端。传统的映射方法将直接对该主题图进行匹 配。匹配目标对匹配结果的影响是不言而喻的。不过，我们必须指出的是：同样 的布尔网络会有多种完全不同的分解方案。 具体情况见例4 1 和图4 1 ： ( 上) ( 下) 图4 1 主题图 f i g 4 1 s u b j e c tg r a p h 图4 1 都是例4 1 中布尔网络的分解方案，( 上) 图对应例4 1 中的( 1 ) 式，( 下) 第四章速度优化再分解设计方法 图对应例4 1 中的( 2 ) 式。显然，同个布尔网络的可以拥有完全不同的逻辑 实现方式。 例4 1 ：这是一个标准的布尔网络，含有两个结点，分别是f u 和f v f u n d o f v + a ef v = a b + a c 我们现在对这个布尔网络进行逻辑分解，这是分解后的两种结果： f u = d f v + a ef v = f w + f xf w = a bf x = a c( 1 ) f u = d f v + a ef v = a f wf w ：b + c( 2 ) 经过逻辑分解后的布尔网络分别含有三个和四个结点，且每个结点都只有 基本逻辑函数关系 而采用不同的分解方案进行匹配或覆盖会产生完全不同的门级网表。这些不 同的门级网表的质量会有很大的差异 1 4 。 例4 2 ：步尔网络芦a + b c + b c ( 注：c7 代表c 的非) ，有两种分解方案： f l = a + x lx l = 了l + z 1y l = b c z l = b c ( 1 ) f 2 = z 2 + x 2x 2 = a + y 2y 2 = b c z l = b c ( 2 ) 在第一种分解方案中，可以使用“异或”门进行匹配( 实现) 逻辑功能。 而第二种分解方案则无法使用“异或”门。 从上例中不难看出，同一个布尔网络可能有完全不同的分解方案，而不同的 分解方案又可能导致不同的门级网表 1 5 。 传统分解算法受分解手段的限制，无法对原布尔网络做较大规模的优化。而我 输出 输入输入 第四蕈速度优化再分解设计方法 图4 2 延时图 f i g4 2d e l a yg r a p h 们则针对主题图的延时性能，在划分后，运用“逻辑变换”的方法对主题图进行再分 解。在得到更加优化的主题图后才进行匹配。这样匹配出的实际网表质量应该好 于或至少相当于f 这种情况发生在无法对主题图进一步优化的时候) 由传统方法 匹配出的结果。 下面我们就具体描述一下这种以延时为优化目标的逻辑再分解设计方法。此 时我们再分解的对象是已经划分过的一组树形主题图。树形主题图每一条路径的 延时，等于输入延时加路径上每一个门延时的和，如图4 2 。图中实线代表“路径1 ”， 虚线代表“路径2 ”整个图的延时等于各条路径中的最大延时。在图4 2 中，这个 由三个结点构成的主题图的延时即是“路径1 ”的延时和“路径2 ”的延时中较大的 一个。 图4 3 算法流程图 f i g 4 3f l o wo f a r i t h m e t i c 如果能够通过种方法，有效的减少“最大延时路径”上的延时( 主题图中，实际是 减少路径上门的数量) ，将对提高整个主题图的速度有利。 图4 3 是这一方法的流程图。图中显示，能否有效的优化“最大延时路径，是 算法是否可行的关键。本文采用一种简单高效的方法来完成对“最大延时路径， 兰婴兰望鏖垡垡要坌坚堡生查鲨一 的优化，且并不改变原电路逻辑功能我们称之为“高速逻辑变换”。 4 2 高速逻辑变换 4 2 1 适用于以与门及非门为匹配目标的速度优化高速逻辑变换 为了能对分解和划分后的主题图进行优化。我们迫切需要开发一种实用的优 化技术来满足进一步优化的要求。传统的逻辑变换方法有很多种，但是都不够全 面和系统，而且针对不同的优化目标，优化的方法也不同。 逻辑代数的变换非常多。但是最根本的变换，本质上都是由：结合率，分配 率和反演率构成。它们就是我们进行优化的基本工具和基石。下面是这三种逻辑 变换的表达式。f 注：a7 代表a 的非) 结合率的逻辑代数表达式是： ( a + b ) + c = a + ( b + c )( 1 ) ( a b ) ca ( b 。c ) ( 2 ) 分配率的逻辑代数表达式是： a b + a c = a ( b + c )( 3 ) ( a + b ) 。( a + c ) = a + b c( 4 ) 反演率的逻辑代数表达式是： ( a + b ) - a b ( 5 ) a = a ” ( 6 ) 在匹配步骤中，无论采用的是树匹配还是自动机匹配，匹配算法都对主题图 中的门有固定的要求。不同的匹配算法要求主题图中含有一些门而不能含有一些 门。这一节，我们讨论适用于以与门及非门为匹配目标的速度优化方法。 这种匹配算法决定了在主题图中只有“与门”和“非门”。这是因为：如果主题 图中只有“与门”和“非门”。则匹配算法可以这样考虑：非门被看作是单输入 的与非门与门被看作是一个两输入与非门加一个单输入的与非门。这样，匹配 算法就只需考虑实际库单元和被映射“主题图”的结构是否相同，结构相同就是匹 配的。而不用再考虑各个单元的逻辑功能是否相同。 这就要求我们把( 1 ) - ( 6 ) 式统一成只有“与门”和“非门”的形式。我们把( 5 ) 式分 第四章速度优化再分解设计方法 别代入( 1 ) ( 4 ) 式。经过整理，我们发现：交换率，反演率和结合率的“逻辑变换”功能 可以只用以下三种变换表示： ( a 。b ) 。c = a ( b c ) ( 丰) a = a ( 桕i ) ( a b ) ( a c ) = ( a ( ( b c ) ) ) ( 桕# 半) 这时我们再来考虑实际主题图中的情况，我们发现归纳起来主题图也只有三 种情况： 第一种：一个与门直接驱动另一个与门； 第二种：一个与门驱动另一个非门； 第三种：一个非门直接驱动另一个非门； 而( + ) ，( + ) ，( + + ) 式所描述的逻辑变换恰好覆盖了所有这三种可能的情况，我们分 别用图4 4 中的( a ) ，( b ) ，( c ) 来描述： ；王d 日；面d ( a ) 日a ( b ) b r l c ( c ) a 图4 4 逻辑变换 f i g 4 , 4l o g i ct r a n s f o r m a t i o n s 从以上三图中我们不难看出，当需要对主题图中与门驱动与门情况做优化 时，我们可以使用( a ) 图；当需要对主题图中非门驱动非门做优化时，我们可以 使用( b ) 图：当需要对主题图中的与门驱动非门做优化时，我们则使用( c ) 图。 我们假设输入a 经过的路径是“最长延时路径”。( a ) 图中，箭头左端的输入a 要经过两个与门，箭头右端的a 只需要经过一个与门。 兰堕兰望鏖垡些曼坌竺堡生互堡一 ( b ) 图中，箭头左端的输入a 要经过两个非门，箭头右端的a 不经过任何门。 ( c ) 图中，箭头左端的输入a 要经过两个与门和一个非门，箭头右端的a 只经 过一个与门和一个非门。不难看出，当a 输入经过的路径是“最长延时路径”时，右 端的逻辑实现过程比左端有较大优势。 以上三种逻辑变换就是我们对“最大延时路径”进行优化的工具。我们称之为 “高速逻辑变换”。对应( a ) ，( b ) 和( c ) 图的变换我们分别命名为“结合变换”，“反演变 换”和“分配变换”。该逻辑变换系统的归纳并覆盖了逻辑变换的所有三神情况。 而且和“主题图”中的三种情景相配合。 4 2 2 以与非门为匹配目标的速度优化高速逻辑变换 上一节介绍了适用于以与门及非门为匹配目标的速度优化再分解设计方法。 这一节，我们要讨论适用于以与非门为匹配目标的速度优化高速逻辑变换。 以与非门为匹配目标的匹配算法针对的匹配目标主题图只含有非门和与非 门。匹配算法是这样考虑的：非门的性能可以直接用单输入的与非门代替，与非 门的功能直接由一个两输入与非门实现。这样，匹配算法就只需考虑实际库单元 和被映射“主题图”的结构是否相同，结构相同就是匹配的。而不用再考虑各个单 元的逻辑功能是否相同 2 3 】。 为了适应以与非门和非门为匹配目标的匹配算法，我们的高速逻辑变换需要 进行改进。不过该设计方法的基本思想和算法实现和上一节完全相同。我们在这 里不再冗述。 不同点就在于它们所采用的“高速逻辑变换”有所不同。这也是本节我们要 研究的问题。在只有与非门的主题图中，我们可以应用的“逻辑变换”公式依然 是以下六个等式： 结合率的逻辑代数表达式是： ( a + b ) + c = a + ( b + c )( 1 ) ( a 。b ) c = a ( b c ) ( 2 ) 分配率的逻辑代数表达式是： a b + a 。c = a ( b + c )( 3 ) ( a + b ) 。( a + c ) 2 a + b c( 4 ) 兰堕兰垄鏖垡些垦坌塑堡生查鲨 反演率的逻辑代数表达式是： f a + b ) = a b ( 5 ) a = a ”( 6 ) 在实际的主题图中，归纳起来只有三种情况： 第一种：一个与非门门直接驱动另一个与非门； 第二种：一个非门直接驱动另一个非门； 第三种：一个非门驱动一个与非门； 在总结了以上情况后，我们发现有两种“逻辑变换”可以用于对主题图的再次优 化。我们分别用图4 5 中的( a ) ，( b