（计算机软件与理论专业论文）基于fpga的逻辑综合方法的研究与设计.pdf

摘要 逻辑综合是f p g a 支持软件中关键的一个优化步骤，其优化结果直接影响了 后续的布局布线等操作的性能。针对此问题，本文从工艺无关和工艺相关两个方 面对逻辑综合方法进行了研究与设计。在工艺无关的逻辑综合中，提出了一种基 于最大允许函数集的无关项优化方法，并与网络重构和两级逻辑优化进行实验对 比。在工艺相关的逻辑综合中，提出了一种基于可划分集合，对查找表网络进行 重连线的优化算法。算法中提出了相似度的概念和构造二部图的方法，以及面向 不同优化目标的启发式方法，并与其他的重连线算法进行对比。结果表明，基于 最大允许函数集的优化方法可以得到更好的优化效果，与网络重构操作结合使用 可得到局部最优解；重连线算法在与其他算法时间复杂度相同的情况下具有更高 的重连线能力和查找表优化能力。 关键词：逻辑综合网络重构无关项重连线 a b s t r a c t l o g i cs y n t h e s i sa sak e yo p t i m i z a t i o ns t e pi nf p g as u p p o r t i n gs o f t w a r e ，i t s o p t i m i z a t i o nr e s u l ta f f e c t st h ep e r f o r m a n c eo ft h ef o l l o w i n go p e r a t i o n sd i r e c t l y , s u c ha s p l a c e m e n ta n dr o u t i n g a i m i n ga ti t ，t h i st h e s i sr e s e a r c h e so nt h el o g i cs y n t h e s i sf r o m t w op h a s e s ：t e c h n o l o g yi n d e p e n d e n ta n dt e c h n o l o g yd e p e n d e n t1 0 9 cs y n t h e s i s i n t e c h n o l o g yi n d e p e n d e n tl o g i cs y n t h e s i s ，ad o n tc a r es e to p t i m i z a t i o nm e t h o db a s e do n m a x i m a ls e t so fp e r m i s s i b l ef u n c t i o n si si n t r o d u c e da n di m p l e m e n t e di nt h et h e s i s a c o m p a r i s o ni sc o n d u c t e da m o n gn e t w o r kr e s t r u c t u r i n g , t w o - l e v e ll o g i co p t i m i z a t i o na n d t h ea p p r o a c hi m p l e m e n t e di nt h et h e s i s i nt e c h n o l o g yd e p e n d e n tl o g i cs y n t h e s i s ，a r e w i r i n ga l g o r i t h m b a s e do ns e to fp a i r so ff u n c t i o n st ob ed i s t i n g u i s h e df o r p o s t - m a p p i n gl il ti sp r o p o s e d i nt h ea l g o r i t h m ，t h ed e f m i t i o no fs i m i l a r i t yd e g r e e ，t h e a p p r o a c ho fb u i l d i n gb i p a r t i t eg r a p h ，a n dt h ea r e a - o r i e n t e da n dd e l a y - o r i e n t e dh e u r i s t i c m e t h o d sa r ep r o p o s e da n dc o m p a r e dw i t ht h ee x i s t i n gr e w i r i n ga l g o r i t h m s t h er e s u l t s i l l u s t r a t et h a tt h em e t h o db a s e do nm s p fc a na c h i e v eb e t t e ro p t i m i z a t i o nr e s u l t sa n d l o c a lo p t i m a lr e s u l t so rn e a r - o p t i m a lr e s u l t sc a nb eo b t a i n e db ys o m ec o m b i n a t i o no f n e t w o r kr e s t r u c t u r i n ga n dn o d em i n i m i z a t i o no p e r a t i o n s ；t h er e w i r i n ga l g o r i t h m p r o p o s e di nt h i st h e s i sh a sh i g h e rr e w i r i n ga n dl u to p t i m i z a t i o na b i l i t yi nt h es a m e t i m ec o m p l e x i t yw i t ho t h e rr e w i r i n ga l g o r i t h m s k e y w o r d s ：l o g i cs y n t h e s i s n e t w o r kr e s t r u c t u r i n g d o n tf a r es e t r e w i r i n g 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本学位论文属于保密，在j 年解密后适用本授权书。 本人签名： 导师签名： 第一章绪论 第一章绪论弟一早三百t 匕 1 1 引言 白1 9 8 5 年x i l i n x 公司推出第一片现场可编程逻辑器件f p g a 至今，f p g a 已 经历了二十几年的发展历史。在这二十几年的发展过程中，以f p g a 为代表的数 字系统现场集成技术取得了惊人的发展：现场可编程逻辑器件从最初的1 2 0 0 个可 利用门，发展到9 0 年代的2 5 万个可利用门，2 0 0 4 年的2 0 0 万门，而现在国际上 的著名厂商a l t e r a 公司、x i l i n x 公司已研制出千万门以上的f p g a 芯片，设计工艺 达到了4 5 r i m ，将现场可编程器件的集成度提高到一个新的水平。 纵观现场可编程逻辑器件的发展历史，其之所以具有巨大的市场吸引力，根 本在于：f p g a 不仅可以解决电子系统小型化、低功耗、高可靠性等问题，而且其 开发周期短、开发软件投入少、芯片价格不断降低，促使f p g a 逐渐地取代了a s i c 的市场，特别是对小批量、多品种的产品需求，使f p g a 成为首选。 目前，f p g a 的主要发展动向是：随着大规模现场可编程逻辑器件的发展，系 统设计进入“片上可编程系统 的新纪元；芯片朝着高密度、低压、低功耗方向 挺进；国际各大公司都在积极扩充其口库，以优化的资源更好的满足用户的需求， 扩大市场；特别是引人注目的所谓f p g a 动态可重构技术的开拓，将推动数字系 统设计观念的巨大转变。另一方面，随着现场可编程逻辑器件的集成度越来越高， 加上对不断出现的i o 标准、嵌入功能、高级时钟管理的支持，使得设计人员开始 利用现场可编程逻辑器件来进行系统级的片上设计。 f p g a 的出现是超大规模集成电路技术和计算机辅助设计技术发展的结果。它 允许电路设计者利用基于计算机的开发平台，经过设计输入、仿真、测试和校验， 直至达到预期的结果。更吸引人的是，采用f p g a 器件可以很方便的对设计进行 在线修改。 现在市场上9 0 以上的芯片是由x i l i n x ，a l t e r a 和a c t e l 公司生产，各个公司 在推出各自芯片的同时，也会推出自己的设计支持软件，还有一些是第三方支持 软件。目前，市场上已经有很多辅助设计工具，主要由c a d e n c e ，s y n o p s y s ，m e n t o r ， m a g m a 等e d a 公司提供。随着f p g a 芯片的集成度的增大，以及系统趋向更加 复杂化发展，则对这些e d a 软件提出了更好的要求，而各大e d a 软件公司也正 为解决这些问题而努力。 1 2 课题来源 随着f p g a 芯片和相关支持软件的发展，f p g a 已逐渐应用到了各个领域，包 括通信、航空、航天、测控、雷达、卫星、军事以及其他一些方面。而f p g a 芯 2 基于f p g a 的逻辑综合方法的研究与设计 片朝着高密度、低压、低功耗方向挺进，相应的支持软件的发展也紧随其后。对 于我国，无论是民用还是军用上每年都需要数以万计的f p g a 芯片，而这些芯片 完全依靠进口，而使用的e d a 软件也是从国外买进。国内的现状是没有独立生产 的f p g a 芯片和属于中国的支持软件，更多的人是把精力放到了f p g a 的系统开 发上。没有自主产权的局面使中国的高新科技的发展，国防信息及国家安全等都 受到了一定的威胁。为了解决这个问题，提出了设计属于我国自主产权的f p g a 芯片及相关支持软件的项目。 1 3 研究背景和意义 现在e d a 软件的发展主要集中在美国，其他各国也在致力于设计新的e d a 工具，日本和韩国都有自己的支持软件，但是目前没有对外公开，而我国目前与 e d a 软件的发展还存在着一定的距离，因此需要认真向国外学习这方面的技术。 现在市场上使用的支持软件都涉及到使用权的问题，而且所有的商用软件都是无 法得到源代码的。而美国的加州大学柏克利分校及加拿大的多伦多大学等一些大 学已经对电路设计这方面有了几十年的研究历史，并公开研究成果，推出一些自 己研发的开源软件，如h s i s ，s i s ，v 1 2 m v ，m v s i s ，v p r 等等。而现在市场上的 一些商用的支持软件就是从这些开源软件发展而来，因此对于我国的现状，研究 这些开源软件对设计新的支持软件有很大的帮助。 逻辑综合，作为电路设计中的一个重要步骤，其优化的结果对综合后面的布 局布线等操作起着决定性的作用，因此，电路的综合优化一直受到了广泛的关注， 从最简单的代数处理方法，布尔操作，到无关项，函数的转换化简方法以及最近 提出的基于可划分集合s p f d 的方法等，逻辑综合的方法在面向不同的优化目标， 不同的芯片有了更多的可选性；数据结构从最早的以布尔表达式存储的方式到现 在的使用决策二叉图b d d 存储，这些使软件的运行速度和性能都有了很大的提高， 但是跟f p g a 芯片集成度和系统设计复杂度的增长还有段距离，因此在软件的设 计上还有很大的提升空间。 电路设计及优化的技术，包括逻辑综合，布局布线等关键技术及新方法都是 由国外的学者提出的，而且这些技术在国外已经非常成熟。而随着f p g a 芯片技 术的不断发展及在各方面的应用，f p g a 将会占芯片市场的主导地位，而高性能芯 片和相关支持软件的设计在国内还是空白，因此设计研发f p g a 芯片及支持软件 对中国的芯片市场有着重要的意义。 1 4 本文章节安排 本文主要研究并设计基于f p g a 的逻辑综合方法，将逻辑综合的过程在功能 第一章绪论 3 上分为工艺无关和工艺相关的逻辑综合两个部分，研究传统的方法并设计和实现 新的综合方法。 本论文主要内容安排如下： 第一章，绪论，介绍课题来源，目前发展现状，国内外发展情况等。 第二章，介绍f p g a 的基本结构类型及综合的概念。 第三章，逻辑综合中使用的基本概念。 第四章，工艺无关的逻辑综合方法的研究与实现，主要从网络重构和节点最 小化两个方面介绍了工艺无关的逻辑综合方法，实现了基于允许函数集的无关项 优化方法，并与其他优化方法进行实验对比。 第五章，工艺相关的逻辑综合方法的设计，主要针对工艺映射后的查找表网 络提出了一种基于可划分集合的重连线算法。 第六章，对当前工作的总结及将来工作的展望。 第二章f p g a 及综合的介绍 5 第二章f p g a 及综合的介绍 2 1f p g a 的介绍 2 1 1f p g a 的分类 f p g a 是在可编程逻辑器件p l d 等基础上进一步发展的产物。它是作为专用集 成电路a s i c 领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克 服了原有可编程器件门电路数有限的缺点，具有体系结构和逻辑单元灵活、集成 度高以及适用范围宽等特点。 f p g a 的发展非常迅速，形成了各种不同的结构。按逻辑功能块的大小分类， f p g a 可分为细粒度f p g a 和粗粒度f p g a 。细粒度f p g a 的逻辑功能块较小，资 源可以充分利用，但是连线和开关多，速度慢；粗粒度f p g a 的逻辑功能块规模 大，功能强，但资源不能充分利用。从逻辑功能块的结构上分类，可分为查找表 结构，多路开关结构和多级与非门结构。根据f p g a 内部连线的结构不同，可分 为分段互连型f p g a 和连续互连型f p g a 两类。分段互连型f p g a 中具有多种不 同长度的金属线，各金属线之间通过开关矩阵或反熔丝编程连接，走线灵活方便， 但走线延时无法预测l 连续互连型f p g a 是利用相同长度的金属线，连接与距离 远近无关，布线延时是固定的和可预测的。 根据编程方式，f p g a 可分为一次编程型和可重复编程型两类。一次编程型采 用反熔丝开关元件，具有体积小，集成度高，互连线特性阻抗低，寄生电容小和 高速度的特点，此外还具有加密位，防拷贝，抗辐射，抗干扰，不需外接p r o m 或e p r o m 的特点，但只能一次编程，比较适合于定型产品及大批量应用，a c t c l 公司和q u i c k l o g i c 公司提供此类产品。可重复编程型f p g a 采用s r a m 开关元件 或快闪e p r o m 控制的开关元件，配置数据存储在s r a m 或快闪e p r o m 中。s r a m 型f p g a 的突出优点是可反复编程，系统上电时，给f p g a 加载不同的配置数据 就可以完成不同的硬件功能，甚至在系统运行中改变配置，实现系统功能的动态 重构。快闪e p r o m 型f p g a 具有非易失性和可重复编程的双重优点，但不能动 态重构，功耗也较s r a m 型高。 2 1 2f p g a 的基本结构 f p g a 采用了逻辑单元阵列l c a ( l o g i cc e na r r a y ) ：这样一个概念，其内部包括 三个部分，可编程逻辑块c l b ( c o n f i g u r a b l el o g i cb l o c k ) ，输x 输出模块i o b ( i o b l o c k ) 和互连资源i r ( i n t e r c o n n e c tr e s o u r c e ) ，如图2 1 所示。 6 基于f p g a 的逻辑综合方法的研究与设计 圈弱啻雕掰黼掰l 量署勰麟蠹口 图2 1x h 心s p a r t a n - i i 芯片内部结构 c l b 是f p g a 的主要组成部分，是实现逻辑功能的基本单元。它主要由逻辑 函数发生器，触发器，数据选择器等电路组成。l o b 提供了器件引脚和内部逻辑 阵列之间的连接，通常排列在芯片的四周，主要由输入触发器，输入缓冲器，输 出触发锁存器和输出缓冲器组成。每个i o b 控制一个引脚，可被配置为输入，输 出或双通i o 功能。可编程互连资源包括各种长度的金属连线线段和一些可编程连 接开关，它们将各个c l b 之间和c l b 与i o b 之间互相连接起来，构成各种复杂 功能的系统。 f p g a 的结构主要分为两类：基于乘积项技术，e e p r o m ( 或n a s h ) i 艺的中小 规模p l d ；以及基于查找表技术，s r a m 工艺的大规模p l d 。e e p r o m i 艺的p l d 密度小，多用于5 ，0 0 0 门以下的小规模设计，适合做复杂的组合逻辑，如译码。s r a m 工艺的p l d ，密度高，触发器多，多用于1 0 ，0 0 0 门以上的大规模设计，适合做复杂 的时序逻辑，如数字信号处理和各种算法等。本文中所用的即g a 为基于查找表结 构的，因此以下主要对基于查找表结构的f p 雠行介绍。 2 1 3 查找表 f p g a 的逻辑块用来实现组合和时序逻辑。逻辑块可以用不同的方式实现。有 的用简单的2 输入的与非门实现，有的用比较复杂的结构，比如查找表( 如图2 2 ) ， 多路选择器或者是多输入的与或结构。研究发现：查找表由于它所实现的函数多 且容易而是目前为止最好的选择【1 1 。 r o 一1 血秘拄 c l o i c 堑 l j 图2 2 用查找表实现的f p g a 逻辑块 第二章f p g a 及综合的介绍 7 查找表( l o o k - u p t a b l e ) 简称为l u t ，l u t 本质上就是一个r a m 。由于l u t 主要适合s r a m 工艺生产，所以目前大部分f p g a 都是基于s r a m 工艺的，而 s r a m 工艺的芯片在掉电后信息就会丢失，一定需要外加一片专用配置芯片，在 上电的时候，由这个专用配置芯片把数据加载到f p g a 中，然后f p g a 就可以正 常工作，由于配置时间很短，因此不会影响系统正常工作。也有少数f p g a 采用 反熔丝或f l a s h 工艺，对这种f p g a ，就不需要外加专用的配置芯片。 目前f p g a 中多使用4 输入的l u t ，所以每一个l u t 可以看成一个有4 位地 址线的1 6 x l 的r a m 。当用户通过原理图或h d l 语言描述了一个逻辑电路以后， f p g a 支持软件会自动计算逻辑电路的所有可能的结果，并把结果事先写入r a m ， 这样每输入一个信号进行逻辑运算就等于输入一个地址进行查表，找出地址对应 的内容，然后输出即可。图2 3 是一个4 输入与门的例子。 实际逻辑电路l u g 的实现方式 地址缱 i 堇垄一一 输出 i 1 6 ，il 埔 c d n 册) a j b jc ，d 输入 逻辑输出地址r a m 中存储的内容 0 0 0 0o0 0 0 00 0 0 0 1 0 0 0 0 l 0 00 l l l ll1 1 l ll 图2 3 四输入与门 一个k 输入的查找表( k - u 田是一个有k 个地址线的s 黜蝴，这个s 洲有2 k 个 比特位并且可以实现k 变量的任意的布尔函数。一个k 输入的查找表可以实现2 声个 不同的布尔函数，图2 4 所示为其中一个函数： 图2 4f = a + b 接下来介绍一下查找表结构的f p g a 的逻辑实现原理。我们以图2 5 的这个示例 电路为例： o 般 b c d a 小 图2 5 示例电路 8 基于f p g a 的逻辑综合方法的研究与设计 a ，b ，c ，d 由f p g a 芯片的管脚输入后进入可编程连线，然后作为地址线连到 l u t ，l u t 中已经事先写入了所有可能的逻辑结果，通过地址查找到相应的数据 然后输出，这样组合逻辑就实现了。该电路中d 触发器是直接利用u j t 后面d 触 发器来实现。时钟信号c l k 由i o 脚输入后进入芯片内部的时钟专用通道，直接 连接到触发器的时钟端。触发器的输出与i o 脚相连，把结果输出到芯片管脚。以 上这些步骤都是由软件自动完成的，不需要人为干预。这个电路是一个很简单的 例子，只需要一个l u t 加上一个触发器就可以完成。对于一个l u t 无法完成的的 电路，就需要通过进位逻辑将多个单元相连，这样f p g a 就可以实现复杂的逻辑。 2 1 4f p g a 的特点和功能 f p g a 的基本特点主要有： 1 ) 采用f p g a 设计a s i c 电路，用户不需要投片生产，就能得到合用的芯片。 2 ) f p g a 可做其它全定制或半定n a s i c 电路的中试样片。 3 ) f p g a 内部有丰富的触发器和i o 引脚。 4 ) f p g a 是a s i c 电路中设计周期最短、开发费用最低、风险最小的器件之一。 5 ) f p 咪用高速c h m o s s e 艺，功耗低，可以与c m o s 、1 凡电平兼容。 f p g a 是由存放在片g q r a m 中的程序来设置其工作状态的，因此，工作时需要 对片内的r a m 进行编程。用户可以根据不同的配置模式，采用不同的编程方式。 加电时，f p g a 芯片将e p r o m 中数据读入片内编程r a m 中，配置完成后，f p g a 进入工作状态。掉电后，f p g a 恢复成白片，内部逻辑关系消失，因此，f p g a 能 够反复使用。f p g a 的编程无须专用的f p g a 编程器，只须用通用的e p r o m 、p r o m 编程器即可。当需要修改f p g a 功能时，只需换一片e p r o m 即可。这样，同一片 f p g a ，不同的编程数据，可以产生不同的电路功能。因此，f p g a 的使用非常灵 活。 f p g 泼有多种配置模式：并行主模式为一片f p g a 加一片e p r o m 的方式；主从 模式可以支持一片p r o m 编程多片f p g a ；串行模式可以采用串行p r o m 编程 f p g a ；外设模式可以将f p g a 作为微处理器的外设，由微处理器对其编程可以说， f p g a 芯片是系统提高系统集成度、可靠性的最佳选择之一。 2 2 系统综合的概念介绍 所谓综合，从某种意义上而言，是采用工具将系统的高层次描述转化为低层 次描述，其中包括相应的化简和优化。所以，将较高层次的描述转化为较低层次 描述的综合可以在不同层次上进行，通常综合分三个层次： 1 ) 高层次综合( h i 曲一l e v e ls y n t h e s i s ) 第二章f p g a 及综合的介绍 9 2 ) 逻辑综合( l o g i cs y n t h e s i s ) 3 ) 版图综合( l a y o u ts y n t h e s i s ) 高层次综合负责将系统算法层的行为描述转化为寄存器传输层的结构描述； 逻辑综合负责将寄存器传输层的结构描述转化为逻辑层的结构描述，以及将逻辑 层的结构描述转化为电路的结构描述；版图综合负责将系统电路层的结构描述转 化为版图层的物理描述。 2 3 大规模电路的设计 数字系统，尤其是大规模电路系统，其设计是一个复杂的过程，为了方便起 见，该过程被分为下面的几个步骤，见图2 6 【2 】。 嘲- a l b l + ( a t b l + 矾b l ) 1 2 b 2 】 图2 6 传统大规模电路设计过程 设计说明：系统得到的行为在不同的抽象等级被定义。在图2 6 中，是一个两 位的比较器，比较a q ，a 2 ) 和bi l l l ( b 1 ，b ：) ，如果d b 则输出为1 。 高层次设计：这个阶段将设计说明转化为用存储器，加法器，寄存器，控制 器等描述的形式，这种描述称为寄存器传输级( r r l ) 的描述。如果设计输入很大， 就将其分成更小一点的模块以减小复杂性。根据设计目标和约束条件，这个阶段 决定将用多少函数单元和寄存器，什么时候使用这些基本单元。对该比较器，这 季 一 占l 幸一 1 0 基于f p g a 的逻辑综合方法的研究与设计 一步产生关于输出的布尔等式。 逻辑设计：首先将r t l 级的描述用一个目标函数优化，例如芯片的面积最小， 性能约束的满足，低功耗等等，这一步被称为最优化过程。优化了的表示随后被 映射到存在一个库中的一些简单的单元中。执行后的结果是用门，函数单元，和 寄存器表示的互连网络。对这个比较器，得到的是一个简单的由门构成的互连网 络。 物理层设计：芯片中不同的模型的位置被确定下来( 布局) ，然后将电路的互连 网络，或是穿过，或是在已放置好的模型之间进行布线。 如果某一步的执行结果没有满足设计目标的要求，则这一步将要重新执行。 2 4f p g a 支持软件设计流程 f p g a 支持的软件设计的流程，是从用户的设计输入开始的，首先是进行逻辑 综合，将设计输入转化为网表文件并进行优化，之后是利用约束库进行技术映射， 再进行布局布线，时序分析，功耗分析，要解决的功耗有三种，静态功耗，动态 功耗和配置功耗。接下来是仿真和验证，进行汇编产生位流文件，最后下载到芯 片，其流程图见图2 7 。 ，： ；”，l “。一，。，i j 逻辑综合技术映射一布局布线一埘问分析 纛? “， i 弋、p 、a q 7 燃鼬詈 功耗分析 厶幻， 广f 岛。 l 设计输入 下载到种。一编程+ 。 茫编+ - 仿真和验证 图2 7f p g a 的一般软件设计流程图 第三章逻辑综合的基本概念 第三章逻辑综合的基本概念 3 1 什么是逻辑综合 逻辑综合，是将较高层次的描述自动地转换到较低抽象层次描述的一种方法。 这里是将r t l 级的描述转换为门级网表的过程。 逻辑综合要求的输入除r t l 描述的程序模块或者原理图文件或波形文件外， 还需要另外两个输入文件，第一个输入就是综合工具支持的工艺库( 如1 1 m 工艺库， m o s 工艺库，c m o s 工艺库) ，这些工艺库中包含一些标准的单元。在综合时，综 合工具会将r t l 级代码描述的设计用工艺库中的标准单元转化为逻辑电路。另一 种输入是约束条件，用于决定综合过程中的逻辑优化方法。约束条件中一般包含 时间，面积，速度，功耗，负载要求和优化方法等，甚至还包含综合时需要注意 的设计规则。 逻辑综合输出的结果是：门级网表。 逻辑综合的具体过程： 第一步：将r t l 描述转换成为未优化的门级布尔描述( 如与门，或门，触发器， 锁存器等) 。该过程不受用户控制，最终转换结果是一种中间结果，格式随不同综 合工具而异，对用户不透明，将r t l 描述中的i f ，c a s e ，l o o p 语句及条件信号 代入和选择信号代入语句等转换成中间的布尔表达式，我们使用的文件格式为。 b l i f 文件格式【3 j ，然后要么装配组成，要么由推论形成触发器和锁存器。 第二步：布尔优化过程，是将一个非优化的布尔描述转化成一个优化的布尔 描述的过程。主要是采用某种优化方法，如资源分配、公共子表达式、代码移位、 公因子提取、交换律和结合律的运用、死代码消除及常量合并等都是一些基本的 优化方法。这一步也称为工艺无关的综合。 ( ! ! 竺兰 ) 、- 一 转换i 丫 厂未优化的布、 。羔剁l 技术无关 、- ，_ _ _ _ _ 一 l 优化算赳 蘧鑫鑫蕃i ” 厂丽矾j ，优化的 、j 塑签苎堕1 映丑 蔓套鬈vl 砭再琢苜 厂门级网衰、j 图3 1 逻辑综合流程图 第三步：门级映射过程，取出经优化的布尔描述，并利用从工艺库中得到的 1 2 基于f p g a 的逻辑综合方法的研究与设计 逻辑和定时上的信息去生成门级网表，确保得到的门级网表能达到设计的性能和 面积要求。这一步也称为工艺相关的综合( 工艺映射) ，流程图如图3 1 。 我们最终将根据优化的布尔描述，工艺库和用户提出的约束条件，将输出一 个优化的网表，该网表的结果是以工艺库单元为基础而建成的。 3 2 1 逻辑函数及基本定义 3 2 基本定义 设b 一 0 册，y 。 0 工2 ) 。一个具有1 1 个输入变量毛，故，m 个输出变量 y 1 ，) ，。的逻辑函数仃可以表示为：疗：b “- y 辨，其中输a x - k ，x n 】e b “， 输出y 一【) ，。，y 。】。输出y ；除了取值为0 和1 外，还可以取值为2 ，表示为无关项， 即可取0 ，也可取1 ，我们仅用扩表示部分确定的逻辑函数。完全确定的逻辑函数 厂取值为 0 ，1 ) 肼，就是输出y ；取值要么为o ，要么为1 。对疗的每个蜣，i = 1 ，m ， 我们定义：真顶点( 0 n s e 0 x ；删，一组函数值为1 的点所构成的集合；无关顶点 ( o f f - s e t ) x ；鲫，一组函数值为0 的点所构成的集合；无关项顶点( d o n t - c a r e s e 0 x i d c ，一组函数值为2 的点所构成的集合1 4 】。 一个逻辑函数可以有多种的表示方法，其中，最简单的是真值表。在这种表 示形式中，输出值由输入序列的组合所指定。例如，矿：曰3 - y 2 可以有如下指 定： 毛 z 2玛 ) ，1 ) ，2 00 0 1 1 0o110 01001 011o1 10 0 l 0 10112 11011 11121 在这个函数中，x 。d 一 【0 ，0 ，o 】，【0 ，0 棚，n 0 ，o 】，n 0 ，1 】，【址o 】 ，x 1 簖一 【0 工0 】， 【0 ，驵】，x 。d c 一 【m 】- 。这种真值表的表示形式可以通过利用n 维布尔立方体将 其转换为几何形式的表示法。对上面的例子，我们可以用一个3 维立方体表示， 如图3 2 ( a ) ，立方体中的每个顶点都表示输入值。我们可以通过建立两个立方体来 表示7 , ( 图3 2 ( b ) ) 和历( 图3 2 ( c ) ) 。其中，x ；o ，五卿，x ；d c 与k d ，k 卿，k d c 是一一对应的。 第三章逻辑综合的基本概念 1 3 l r i o - ov 1 p c k d ， 甸011 1 1 1 m 001臼0111 1 1 1 锣0 1 1 1 1 1 。 图3 2 二输出函数的覆盖 3 2 2 逻辑函数的代数表示 考虑函数萨中的一个元素历，其代数表示f i 是一布尔表达式，对工；侧中的输 入都为1 ，x 。d ，中的输入都为0 ，而对x ；d c 中的输入，或者为1 ，或者为o ( 我们 不关心z ；d c 中函数值) 。函数的代数表达式f ( 有时也表示为f ( 扩) ) ，是一组m 元布尔表达式。 函数疗可以通过检查万的真值表或几何表示来建立其代数表示。例如，扩中 的第i 个输出的代数表达式可按下面的方法得到。考虑第i 个输出位置所对应的值 为1 的每一行，将其化为乘积( 逻辑与) 的形式，如果在真值表中n 个输入相应的位 置出现的是l ，则用变量z ，表示，若出现的是o ，则用z ，表示。显然，当输入组合 与真值表中该行的组合相对应时，其乘积值为1 ，而在其他的输入组合下值为0 。 将所有得到的乘积以布尔和( 逻辑或) 的形式组合在一起，得到了历的代数表达式。 对上面的例子，可得到下面的代数表达式： f j _ z l x 2 x 34 x i x 2 2 34 - x t x 2 屯+ x l x 2 x 34 x i x 2 x 3 f 2 - 工2 x 34 x x x 2 而+ 毛工2 毛4 x l x 2 屯+ 工i 茗2 x 3 式( 3 1 ) 可以看出，这些代数表达式都是以乘积和的形式表示的，这种形式可以用来表示 其他任何的函数，而且操作也比较简单。一个逻辑函数也可能有多种不同的代数 表达形式。值得注意的是，我们可以自由的将无关项的值赋值为o 或1 ，对不同的 赋值，我们可以得到不同的表达式。例如，我们将伉中无关项的值赋值为1 ，则 所得到的伉的代数表达式中将多一个乘积五工：x 3 。 仃的代数表达式可以经过处理得到更简洁的表达式，例如，利用标准的布尔 代数法则，上面的结果式( 3 1 ) 可以化简得到： f lnx 2 + x l x 3 f 2 。z 2 + x i x 3 式( 3 2 ) 鲫 瓣 眨匕 o 1 4 基于f p g a 的逻辑综合方法的研究与设计 非操作，或操作( 并集操作) ，与操作( 交集操作) 都被定义为简单的代数操作， 这些是通过普通的布尔规则操作的。例如f 的非f 是利用布尔表达式求非的规则得 到的，f 是厂的代数表达式。 厂的乘积和形式的代数表达式中的每个乘积，都决定着一个逻辑函数。例如， 在上例中，x ：决定的逻辑函数为三维布尔立方体中的顶点( o ，0 ，o ) ，( 1 ，0 ，1 ) ，( 0 ，0 ，1 ) ， ( 1 ，o ，0 ) 处的值为1 ；为为决定的逻辑函数为立方体中的顶点( 1 ，0 ，0 ) 和( 1 ，1 ，o ) 处的值为 1 。这些顶点都是以函数空间里的子空间的形式出现的，工，是该函数的一个二维子 空间，x l x ，是一个一维子空间。因此，在万维布尔空间中，所有的积代数都可以有 一个k 维子空间 墨n ) 与其一一对应。 3 3 布尔网络及节点的定义 3 3 1 布尔网络 布尔网络是一个有向非循环图( d a g ) ，其中包含基本输入，基本输出和中间节 点。基本输入只有向外指向的弧线，没有向内指向的弧线，基本输出只有向内指 向的弧线，没有向外指向的弧线。第i 个中间节点弘表示一个逻辑函数正。每个节 点处的逻辑都是用乘积和的形式存储的，在网络中，如果节点j 处的函数明确的用 到了节点i 处的弗或奶，则存在一条有向弧线从节点i 指向节点j 。函数y ，用到的 一组变量的集合称为载体函数( s u p p o r t ) ，记为s 。在这种情况下，i 称为j 的扇入， j 为i 的扇出。如果从节点i 到j 存在一条路径，则称为j 的一个传递扇入，j 为i 的一个传递扇出。 图3 3 布尔网络 图3 3 为一个具有4 个基本输入a ，b ，c ，d ，1 个基本输出z ，3 个中间节点y ， w ，z 的布尔网络，基本输入和基本输出用正方形表示，中间节点用圆形表示，a 和b 为y 的扇入，z 为y 的扇出，y 所相对应的函数为= a b ，z 的传递扇入为 a ， b ，c ，d ，w ，y ) ，b 的传递扇出为 w ，y ，z ) 。 第三章逻辑综合的基本概念 1 5 3 3 2 节点的表示 布尔网络中的每个节点都对应着一个逻辑函数的表示，函数的表示是很重要 的。尽管有很多正确的表示法，但是一些表示是首选的，因为它们： 1 ) 存储效率高 2 ) 最后执行得到的结果复杂度更容易表示 3 ) 操作效率高 在此我们仅讨论与工艺无关的三种节点。 多元化的节点：每个节点可以是任何逻辑函数的表示，这种表示的好处是该 理论的发展很容易。 类节点：网络中的每个节点都是相同的函数，例如，2 输入与非门。优点是每 个节点都比较简单，没有必要在节点处储存普通的逻辑函数，因为每个节点的函 数功能相同，只是输入不同。尽管比多元化节点中描述的节点多很多，但是对一 些操作，用这种结构是比较快的。缺点是网络分解是以一种特殊的方式，这可能 会使网络中一些普通的结构变得模糊。 离散节点：一个节点可以是逻辑函数的一小块，如与门，或门，非门，译码 器，加法器等，多个输出节点也是允许的。通常情况下，这种表示法只用于基于 规则的系统中。其中的一个优点，复杂的逻辑块，象编码译码函数，可以聚合在 一起并当作一个单元操作。 本文中用到的是多元化的节点表示形式。 网络节点的表示方法有： 【1 1 乘积和的形式 乘积和的表示形式是比较简单而且最常用的一种方式，因为这种形式下的逻 辑操作技术发展的很快，例如，用与、或等逻辑操作的二值型最小化，因式分解， 分解，重言式，组合逻辑函数等【5 】1 6 1f 7 1 。 f 2 1 因式表示形式 因式表示形式是一个加上括号的表达式，其定义如下： 1 ) 单独的字符就是一个因式表示式 2 ) 两个因式表示式的和是一个因式表示式 3 ) 两个因式表示式的乘积也是一个因式表示式 因式表示式的结构与树的结构类似，其内部节点可以是与操作和或操作，而 叶子节点是字符。例如，函数厂( a b + c d ) p + ( a b + c d ) t ( 该函数不是因式表示式， 因为( a b + 耐) 类型的结构是不允许出现的) ，可以利用因式表示式中求非的法则， 将要求非操作的因式中的与操作直接换成或操作，或操作换成与操作，便可得到 因式表示式为f 一( 口6 + 耐) p + ( a + 6 ) ( c + d ) g 。 1 6 基于f p g a 的逻辑综合方法的研究与设计 因式表示式中的字符数可以与函数的复杂性联系起来，也可以换算出所需要 的晶体管的数量。这只能间接的测量面积因为在总面积中布线也是需要一些面积 的。好一点的衡量方法可以是因式表示式中的字符数量在加上一定比例的门或节 点的数量，或者网络中终端节点的数量。 f 3 1 二叉决策图b d d - - y 决策图b d d ( b i n a r yd e c i s i o nd i a g r a m ) 是完全确定逻辑函数的标准表示。 b d d 是一个有向非循环图，每个非叶子节点都有一个关于本身的变量，有两个后 继。因为二叉决策图在数据结构的实现和对逻辑函数的操作上，具有占用空间小， 运算速度快等的特点，目前已逐渐取代了用乘积和表示形式的数据存储方法，并 已广泛使用。下一节将会具体介绍二叉决策图的概念和操作方法。 【4 1 多叉决策图m d d 多叉决策 m d d ( m u l t i v a l u e dd e c i s i o nd i a g r a m s ) 是由b d d 扩展得到的。在加 入无关项之后，b d d 扩展到有多值输入和多值输出的结构图，b d d 中每个节点有 两个后继，而在m d d 中，可以有多个后继。对m d d 进行类似的操作，也可得到类 似b d d 中的r m d d 和r o m d d 。传统电路中的逻辑值只有0 和1 ，而在多值型逻辑中， 使用的逻辑值还可有2 ，3 等，因此是电路的设计能力更强。随着电路设计规模的 不断扩大，m d d 将会使用越来越广泛嘲。 【5 】i f - t h e n e l s e 型d a g 表示 i f - t h e n e l s e 型d a g 表示与b d d 形式很相近，i f - t h e n e l s e 型d a g 表示由终结点和 非终结点组成，终结点的值为0 或1 ，非终结点是一个二选一选择器，由三个子节 点组成。第一个子节点与输入控制信号相连，第二个子节点和第三个子节点与选 择器的输入信号相连。节点的函数功能是，如果控制输入的表达式为真时，第二 个子节点将被选择，否则就选择第三个子节点。在b d d 中，节点也可以看作是二 选一选择器，而控制变量是直接与节点中的变量相关联的。因此i f - t h e n e l s e 型的 d a g 表示将比b d d 形式更全面，而且可以得到更简洁的表示 9 1 1 0 1 。 对于函数厂一a b + 口c + 如，在图3 4 中，a 作为b d d 的根结点，结果如在a - 0 和a 一1 的两个分枝中都得到了，而这种情况在i t e 表示中是可以避免的【1 1 l 。 图3 4b d d 与i t e 的对比 第三章逻辑综合的基本概念 1 7 3 4 基于图的布尔代数运算 3 4 1 二叉决策图 - - y 决策图b d d ( b i n a r yd e c i s i o nd i a g r a m ) 是一个包含一个根节点( r o o t ) 的有向 图。图中的节点可以分为两种类型：一种是非终端节点( n o n t e r m i n a ln o d e ) v ，它 有左右两个孩子，分别表示为l o w ( v ) 和h i g h ( v ) ；另一种是终端节点( t e r m i n a ln o d e ) ， 它的值为0 1 。每个节点的数据结构可以定义为如下所示【1 2 】： t y p ev e r t e x = r e c o r d l o w , h i g h ：v e r t e x ； i n d e x ：1 n + 1 ； v a l ：( 0 ，1 ，殉； i d ：i n t e g e r ； m a r k ：b o o l e a n ； e n d ； 其中，i n d e x 表示节点所代表的变量，可能存在某