（计算机软件与理论专业论文）基于域操作的工艺映射系统.pdf

摘要 工艺映射流程中最重要并且也是最耗费时间的一步是划分列举，其完成的任 务主要是产生划分，从而为下一步的选择划分准备。传统的产生划分的方法是产 生所有的备选划分，然后从中找到挑选出满足约束条件的最优的结果。本文中所 提出的算法d m a p 采用了目前为止最有效的电路表达形式：最简有序二分决策图 ( r o b d d ) 。基于这种r o b d d 的结构特性以及各种基于r o b d d ( r e d u c e do r d e r e d b i n a r yd e c i s i o nd i a g r a m ) 的域操作，包括算术域操作( 0 一d o m i n a t o r , 1 - d o m i n a t o r 和 x d o m i n a t o r ) 和布尔域操作( x d o m i n a t o r , g e n e r a l i z e dd o m i n a t o r 和g e n e r a l i z e d x d o m i n a t o r ) ，d m a p 可以高效而迅速的产生相对数量少的划分，从来使整个工 艺映射的运行时间得到了显著减少。同时本文还提出了面向延迟和面积优化的启 发式方法。最后用m c n c 的标准电路进行了实验对d m a p 进行了验证，与经典 的工艺映射算法f l o w m a p 和目前最先进的工艺映射算法a b c 进行了比较，结 论是：d m a p 的平均运行时间减少到了a b c 的1 3 ，同时面积和延迟仅有少量的 增加。 关键字：工艺映射域操作划分产生现场可编程门阵列 a b s t r a c t c u te n u m e r a t i o n ，a st h ec r u c i a la n dm o s tt i m e - c o n s u m i n gs t e po ft e c h n o l o g ym a p p i n g ， i st op r e p a r ec a n d i d a t ec u t sf o rc u ts e l e c t i o n t r a d i t i o n a lm e t h o d sf o rc u te n u m e r a t i o n a r et oc o m p u t ea l lt h ec a n d i d a t ec u t sf o re a c hl o g i cg a t ea n dt h e nf i n dad e p t h o p t i m a l m a p p i n gs o l u t i o n t h ea l g o r i t h md m a p i nt h et h e s i sa d o p t st h em o s te f f i c i e n tb o o l e a n l o g i cr e p r e s e n t a t i o n f o u n ds of a r ：r e d u c e do r d e r e db i n a r yd e c i s i o nd i a g r a m ( r o b d d ) b a s e do nt h es t r u c t u r a lc h a r a c t e r i s t i c sa n dv a r i o u sd o m i n a t o r s ，i n c l u d i n g a r i t h m e t i cd o m i n a t o r s ( 0 一d o m i n a t o r , 1 - d o m i n a t o r , x - d o m i n a t o r ) a n db o o l e a no p e r a t o r s ( g e n e r a l i z e dd o m i n a t o ra n dg e n e r a l i z e dx - d o m i n a t o r ) ，d m a pc a np r o d u c el e s sc u t s e f f i c i e n t l ya n de f f e c t i v e l y a l s o ，t h et h e s i sp r e s e n t ss o m eh e u r i s t i c sa p p r o a c h e s c o m p a r e d t os t a t e o f - t h e a r t t e c h n o l o g ym a p p e ra b c ，o u rp r o p o s e dm a p p i n g a l g o r i t h mo f f e r su pt o3 xa v e r a g er u n t i m er e d u c t i o nw i t hn e g l i g i b l ea r e ap e n a l t y k e y w o r d ：t e c h n o l o g ym a p p i n g ，d o m i n a t o r , c u te n u m e r a t i o n ，f p g a 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本学位论文属于保密，在_ 年解密后适用本授权书。 本人签名：墨置呜 鼍7 擘i i 导师签名： 二二 躁j 薯 虹o “：，一： 匿釜乙翻 日期2 ：呈：至 日期兰兰：墨：圣= ! ： 第一章绪论 第一章绪论 1 1 问题的提出 随着微电子技术的发展，系统设计师们更愿意自己设计专用集成电路( a s i c ) 芯片，而且希望a s i c 的设计周期尽可能短，最好是在实验室罩就能设计出合适的 a s i c 芯片，并且立即投入实际应用中去，因而出现了现场可编程逻辑器件p l d ( p r o g r a m m a b l el o g i cd e v i c e ) 。 p l d 是2 0 世纪8 0 年代发展起来的器件，是一种由用户根据自己的需求来设计逻 辑功能并对此器件进行编程后实现的，其中现在应用最广泛的当属现场可编程门 阵列( f p g a ) ，关于f p g a 的内容将在第2 章中进行详细讲述。 现场可编程门阵列( f p g a ) 是实现复杂数字系统的可编程器件。在f p g 久上实现 数字系统可以使设计者测试和修改设计而不用去象专用集成电路( a s i c ) 那样制造 出实际的芯片，这样就节省了时间和资金，使产品可以在第一时间面向市场，这 些特点使f p g a 成为数字设计的主流平台。随着对f p g a 的需求的增加，对计算机辅 助设计( c a d ) 工具的需求也在增加，因此推动了f p g a 的c a d 工具的研究。 在传统的a s i c 的设计过程中，自动化和智能化程度还不高，并没有真正的使 设计者从繁重的设计中解脱出来。再加上f p g a 自己独有的结构上的特点，比如其 基本的逻辑单元一一查找表，以及连线的可编程性等，使其c a d 工具的开发更具难 度和挑战性。 本文所要处理的问题就是f p g a 的c a d 工具开发中的一个重要步骤：工艺映射。 关于f p g a 的c a d i 具开发的具体内容将在第2 章详细讲述。工艺映射的定义如下： 给定一个描述布尔网络的网表n 。，经过工艺映射产生一个网表n ，n ，是根据给 定的设备数据库l ，定义的组件而产生的。如图1 1 。 图1 1 映射过程 基于域操作的r 岂映射系统 1 2 国内外现状 美吲从2 0 世纪8 0 年代初就进行r 可编程芯片的研究，儿乎同时外始了可编稃 芯片支持软件的研究，加拿大也进行了支持软件的研究。到目前为1 r ，无论是学 术界还是工业界，都以美国和加拿大最为领先。学术界，些著名的理论都是由 美国和加拿大的研究人员提出，t l o i l 经典的工艺映射算法：f l o w m a p 1 ；布同 市线算法：模拟退火等算法2 1 。其巾以加拿大多伦多大学，荚h ) jr l ) 火学伯克利 分校的研究最为m 色。加拿人多伦多大学 友了著名的布局布线上具：v p r ，被 应用到了许多商业的f p g a 支持软件t 且中。美国加、i l 大学伯克利分校外发了综合 工具：s l s 3 ，被学术界广泛使用。丁业界，全球最著名的曲家可编程芯片。家： a l t e r 气x i l i n x 都是美国公司。他们占据了仝球可编程芯片市场的8 0 以上的份 额，如图1 2 。 2 0 0 3 $ 2 6 b 幽122 0 0 3 年全球可编程芯片市场的分布 现在业界最流行的f p g a 系列有a l t e r a 的s t r a t i x1 1 ，x i l i n x 的v i r t e x 都是9 0 r i m 工艺的，基本门至少百万n 最新的有t 万门。其中v i r t e x 系列是业 界最流行的高性能f p g a ，在15 v 和更低电压的f p g a 产品中，年度份额更是接 近8 0 4 。 f p g a 的支持软件的开发也是以这两家公司为首。a l t e r a 开笈的f p g a 史持 第一章绪论 3 软件有：m a x p l u si i 和q u a r ny si i 。m a x p l u si i 是免费使用的，适合中小规 模的电路；q u a r t u si i 是商业产品，适合大规模的电路。x i l i n x 开发的支持软件 有：i s e 7 0 。 从在国际项级的可编程芯片杂志和会议上发表的文章来看，国外在该领域也 是占绝对的主导地位。而国内无论是工业界还是学术界，都没有对这方面进行深 入的研究工作，几乎是一片空白。因此可以说，f p g a 及其支持软件在我国有很大 的发展潜力。 1 3 前人研究结果 作为f p g a 支持软件中关键的一步，工艺映射吸引了广泛的研究。根据研究的 目标，各种工艺映射算法可大致分为4 类，面积最小化 5 6 7 ，延迟最小化 1 8 9 儿l o ，功率最小化 1 1 1 2 1 3 ，面积和延迟综合考虑的最小化 1 4 1 1 5 。其中著名的f l o w m a p 算法，第一次从理论上找到了工艺映射的最优解，从而 为以后的工艺映射算法开发提供了理论基础；而 1 6 证明了面积最小化问题是 n p c 复杂度， 1 7 证明了功率最小化问题是n p c 复杂度的。 近年来一些先进的工艺映射算法的目标则分化为两个方向，第一个是继续关 注面积和延迟，力求将面积和延迟进一步的压缩，比如【1 8 】【1 9 】【2 0 】，主要关注的是 面积和延迟综合考虑的方法，这个方向的进展近年来不是很大；另外一个方向则 认为面积和延迟已经到达了近似最优的结果，应该将重心转移到速度方面的考虑， 比女h 2 1 1 1 2 2 】【2 3 ，主要关注的是运行速度。实验结果也说明了第二个方向有更大的 研究空间：目前为止工艺映射的运行时间平均降低了2 0 倍，而且还有进一步降低 速度的可能。本文所提到的方法主要是面向第二个方向。 目前在f p g a c a d 领域主要用到的工具有s i s ，v i s ，b d s ，f b d d 等。其中s i s 在 学术界最为人所赞誉，是由美国加州大学伯克利分校开发的工具，全称是时序交 互系统，可以用来进行输入的处理，逻辑门的化解和优化，是一个功能完整并且 强大的综合和工艺映射系统。另外一个具有著名的工具是b d s p g a 2 2 ，由麻省大 学v l s ic a d 研究小组开发，其数据结构完全不同于s i s ，是基于二分决策图 2 4 】( b d d ) 的，关于b d d 的概念，将会在第三章进行详细的介绍。这个工具是完全 开源的，任何人可以自由下载源代码，并且修改和使用。本文的算法实现就是在 b d s p g a 基础上进行的。 1 4 工作概要及章节安排 本文所提出的方法利用二分决策图及其域操作( d o m i n a t o r ) 来改进工艺映射 4 基于域操作的工艺映射系统 中关键的一步一划分列举，来进行工艺映射，在面积和延迟为近似最优的情况下， 实现运算速度的提高。实验结果也证明了本文所提出方法的有效性，相比于a b c ( 目 前为止运行速度最快的工艺映射算法) ，虽然面积和延迟有了一定程度的增加，但 是速度减少至u a b c 的1 3 由于b d s - p g a 是一个开源的代码，所以可以在其基础之上进行裁减，来实现各 种工艺映射算法。本文的实现就是在基于b d s p g a 的基础上，实现了工艺映射系统 d m a p 。 具体的内容安排如下：第一章为绪论，介绍了一下本文所要研究的问题，国 内外现状，前人所做的结果以及本人的成果等；在第二章将介绍f p g a 以及其支持 软件的背景以及工艺映射的简要过程；第三章描述了本文所提出工艺映射算法的 理论基础：最简有序二分决策图及其域操作；第四章给出了基于域的工艺映射算 法以及优化延迟和面积的策略；第五章给出了实验结果并对实验结果进行了详细 的分析。 第二章背景知识 5 第二章背景知识 2 1 现场可编程门阵列及其结构 2 1 1 现场可编程门阵列 f p g a 是英文f i e l dp r o g r a m m a b l eg a t ea r r a y 的缩写，即现场可编程门阵列， 它是在p l d ( 可编程逻辑器件) 等基础上进一步发展的产物。它是作为专用集成电路 ( a s i c ) 领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服 了原有可编程器件门电路数有限的缺点，具有体系结构和逻辑单元灵活、集成度 高以及适用范围宽等特点。新一代的f p g a 甚至集成了中央处理器( c p u ) 或数字信号 处理器( d s p ) 内核，在一片f p g a 上进行软硬件协同设计，为实现片上可编程系统 ( s o p c ，s y s t e mo np r o g r a m m a b l ec h i p ) 提供了强大的硬件支持。 2 1 2f p g a 的结构 f p g a 采用了逻辑单元阵列l c a ( l o g i cc e l la 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 ) 输出输入模块1 0 b ( i n p u to u t p u tb l o c k ) 内部连线( i n t e r c o n n e c t ) 在基于查找表的f p g a 芯片中，基本的可编程逻辑块是k 输入的查找表，这 个查找表可以实现最多有k 个变量的布尔函数( 以k - l u t 来表示) 。c l b 中包 含可编程的k - l u t s 。如图2 1 所示。 嚣酗ftu苗o蜜oo圣e目o目 0 0 0 0 门门门一 事c 【融 l j u u ；j 0 0 0 0 0 0 0 0 o o 聪0 0 0 嚣话 图2 1x i l i n xs p a r t a n i i 芯片内部结构 d瞪墨罡 ，lliillilillllitifijj：一 一 ：搿￥uo一蝣i|列一 酲固j 6 基于域操作的工艺映射系统 随着工艺的进步和应用系统需求，一般在f p g a 中还包含以下可选资源： 存储器资源( b l o c kr a m 和s e l e c tr a m ) 数字时钟管理单元( 分频倍频、数字延迟) i o 多电平标准兼容( s e l e c ti o ) 算数运算单元( 乘法器、加法器) 特殊功能模块( m a c 等硬i p 核) 微处理器( p p c 4 0 5 等硬处理器) f p g a 的结构主要分为两类：基于乘积项( p r o d u c t t e r m ) 技术，e e p r o m ( 或f l a s h ) 工艺的中小规模p l d ( 可编程逻辑器件) ；以及基于查找表( l o o k u p t a b l e ) 技术，s r a m 工艺的大规模p l d 。e e p r o m 工艺的p l d 密度小，多用于 5 , 0 0 0 门以下的小规模设计，适合做复杂的组合逻辑，如译码。s r a m 工艺的p l d ， 密度高，触发器多，多用于1 0 ，0 0 0 门以上的大规模设计，适合做复杂的时序逻辑， 如数字信号处理和各种算法等。本文中所用的f p g a 为基于查找表结构的，因此 以下主要对查基于找表结构的f p g a 进行介绍。 采用基于查找表结构的f p g a 有a l t e r a 的a c e x ，a p e x 系列，x i l i n x 的s p a r t a n ， v i r t e x 系列等。 2 1 3 查找表 查找表简称为l u t ( l o o k u p t a b l e ) ，l u t 本质上就是一个r a m 。目前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 ，这样，每输入一个信号进行逻辑运 算就等于输入一个地址进行查表，找出地址对应的内容，然后输出即可。 实际逻辑电路 l r _ r t 的实现方式 地址线 输出 b 厂1 广) o u c b 1 6 x l 列啪 c d 正u t ) a i) a jb ，d 输入逻辑输出地址煳中存储的态容 0 0 0 0o0 0 0 0 0 0 0 0 lo0 0 0 l o 0 o i111lllll i 图2 24 输入与门 第二章背景知识 7 图2 2 是一个4 输入与门的例子。 一个k 输入的查找表( k l u t ) 是一个有k 个地址线的s r a m ，这个s r a m 有2 k 个 比特位并且可以实现k 变量的任意的布尔函数。一个k 输入的查找表可以实现2 乒个 不同的布尔函数。 下面看一个具体的芯片，a l t e r a 的f l e x a c e x 芯片的结构如图2 3 。 i 越螃 i 址圮2 垃 蛳锄籼 鞫蕾畦 i 磁粥# 络 l 盛比嘲簿 2 1 4f p g a 的特点和功能 铆hq 瞄蠲幽 如l 图2 3f l e x a c e x 的结构 f p g a 的基本特点主要有： 1 ) 采用f p g a 设计a s i c 电路，用户不需要投片生产，就能得到合用的芯片。 2 ) f p g a 可做其它全定制或半定制a s i c 电路的中试样片。 3 ) f p g a 内部有丰富的触发器和i 0 引脚。 4 ) f p g a 是a s i c 电路中设计周期最短、开发费用最低、风险最小的器件之一。 5 ) f p g a 采用高速c h m o s 工艺，功耗低，可以与c m o s 、t t l 电平兼容。 f p g a 是由存放在片内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 的使用非常灵 基于域操作的j 艺映射系统 凼此，叮以蜕，f p g a 芯片是系统提高系统集成度、可靠性的最佳选择之。 22 可编程门阵列的支持软件 f 面是典型的f p g a 支持软件的设训流程 图24f p g a 支持软件垃计流程 下面简要的将各个步骤介绍一下： 1 输入：土要有四种：v h d l ，v e f i l o g h d l 原理图，和第二方工具生成的 e d i f 文件。 2 综合：将较高层次的描述自动转换到较低抽象层次描述的一种力法。这里 是指将r r l ( 寄存器级) 缴的描述转换为门级网表的过程。 3f 艺映射：根掘综合，十成的网表，将用户设计嵌八f p g a 芯片。这罩的嵌 入，实际上是在一个芯片数拼库( i ) e v l c ed a l a b a s e ) r 进i r 的，而这个芯片数据库提供tf p g a 芯片的所有细节。 第二章背景知识 9 4 布局：布局决定电路中不同的逻辑块在f p g a 芯片中的分布，结果应该是： 互相关联的逻辑块放在一起，这样可以尽可能的减少和缩短连线。 5 布线：布线确定逻辑块之间的选择连线和开关。 6 时序分析：对布局布线的结果进行时序分析，目的是验证电路的时序性能， 以确定电路的速度。 7 功耗分析：使动态功率消耗最小。 8 仿真：通过仿真对设计进行全面测试，保证设计在各种可能的条件下都有 j 下确的响应，以满足系统设计要求。 9 汇编：汇编模块将适配过程的器件逻辑单元和引脚分配信息转换为器件的 编程 图像，并将这些图像以目标器件的编程对象文件( p o f ) 或s r a m 对象文件 ( s o f ) 的形式保存为编程文件，也即b i t s t r e a m 文件。 1 0 编程：这个过程的目的是将b i t - s t r e a m 下载到f p g a 芯片。 设备数据库中描述了特定的组件的工艺，这些工艺描述了组件的详细信息， 比如组件大小，时延等信息。设备数据库是整个f p g a 支持软件的基础，任何步骤 的操作都是在其基础上形成的。 下面看一下工艺映射的具体过程。 2 3 工艺映射 2 3 1 问题描述 工艺映射就是将一个电路的抽象描述( 门级描述) 翻译为硬件表示，即使用 给定的特定工艺的组件来描述一个电路。特定工艺的组件可以实现具体的布尔函 数。在这种情况下给定电路必须被划分为子电路，只有这样每个子电路才可以被 给定的组件来实现。相反，给定的组件必须有可编程的部分来实现不同的布尔函 数。 设备数据库中描述了特定的组件的工艺，这些工艺描述了组件的详细信息， 比如组件大小，时延等信息。设备数据库是整个f p g a 支持软件的基础，任何步骤 的操作都是在其基础上形成的。在工艺映射阶段，是提供给划分后的查找表网络 用来映射的。 其中，电路的抽象描述称为布尔网络，布尔网络是由有向无环图来表示的组 合函数。在布尔网络中的节点代表布尔函数，每个节点有一个变量和局部函数关 联。划分的结果也是一个查找表网络( 如图2 5 ) ，即映射网络中的基本单位是查 1 0 基于域操作的工艺映射系统 找表。然后结合给定的设备数据库来进行映射，即将每个查找表用给定设备数据 库中的组件来实现。 图2 5 布尔网络映射到查找表网络 综上所述，工艺映射问题可以定义为： 给定一个描述布尔网络的网表n 。，经过工艺映射产生一个网表n ，n r 是根据 给定的设备数据库l t 定义的组件而产生的。如图2 6 。 2 3 2 映射过程 图2 6 映射过程 典型的工艺映射过程有3 个步骤 4 ，这3 个步骤是分解( d e c o m p o s i t i o n ) ，划 分( c o v e r i n g ) 和映射( m a p p i n g ) 。 分解：将综合生成的等式转化为只包含原子门( 与门，或门和非门) 的网 络。 划分：划分原子门网络为查找表网络，其中，每个查找表代表一个门。 映射：根据设备数据库，将查找表网络映射为设备数据库中的组件。 这3 个步骤完成之后，就得到了一个映射后的电路网络，可以提供给布局阶 段使用了。 第二章背景知识 1 分解 这一步的目的是将综合生成的等式转变成一个两输入原子电路门网络，原子 门是指与非门，或非门，反相器。这个阶段也划分为3 个步骤，分别是： 进行与或门替换。 将任意输入的与或门递归的转变为两输入的与或门，从而产生有向无环 图( d a g ) 。 将d a g 分解为小的子图。 2 划分 将只含有原子门的网络分划分为具有约束条件的块，每个块代表一个复杂门 ( c o m p l e xg a t e ) ，即查找表。其中约束条件主要是：时间延迟和查找表的个数。( 如 图2 7 1 。 f f 矗b cd 图2 7 划分实例 划分这个步骤是工艺映射的核心步骤，因为工艺映射的主要步骤就是将一个 给定的布尔网络划分为查找表网络。划分的具体过程有很多的具体算法，但大体 来说可以分为4 类：面积最小化，延迟最小化，功率最小化，面积和延迟综合考 虑的最小化。 近年来一些先进的工艺映射算法的目标则分化为两个方向，第一个是继续关 1 2 基于域操作的工艺映射系统 注面积和延迟，力求将面积和延迟进步的压缩， ：k p h 1 8 1 1 9 1 1 2 0 ，主要关注的是 面积和延迟综合考虑的方法，这个方向的进展近年来不是很大；另外一个方向则 认为面积和延迟已经到达了近似最优的结果，应该将重心转移到速度方面的考虑， l ：l 女n 2 1 2 2 】【2 3 。本文所提到的方法主要是面向第一i 个方向。 划分可以理解为2 个步骤： 划分产生 按照拓扑顺序遍历布尔网络中所有的节点，然后产生每个节点的划分。 划分选取 从输出节点开始，按照约束条件选择划分并实现为u j t 。 3 映射 利用上一步产生的划分来获得复杂门的具体实现，即调用设备数据库中的具 体组件来实现复杂门。 由划分产生查找表的器件说明。 分析器件说明然后根据设备数据库产生相应的查找表定义。 这些步骤完成后，就可将给定的描述与或门的等式映射为结合了具体工艺的 查找表网络。 综上所述，可以得到完整的工艺映射的过程： 图2 8 工艺映射详细过程 第二章背景知识 1 3 2 4 布尔网络 在电路表示中，经常用含有节点和有向边的图来表示一个逻辑电路。在图中 的节点对应于逻辑门。例如节点a 的输出是节点b 的输入的话，则可以表示为( a ，b ) 。 图的初级输入表示逻辑电路的初级输入，是没有输入边的。同样，图的初级输出 表示逻辑电路的初级输出，是没有输出边的。基于以上概念有以下d a g 定义： d a g ：含有有向边并且没有环的图称为有向无环图( d i r e c t e d a c y c l i cg r a p h ) 。 布尔网络即为d a g 。在本文中，只处理完全定义了的门表示，并且是单输出 的门。此处完全定义的门表示意思为对任意一个输入都有一个输出值对应。布尔 函数即为一个从n 个输入信号到单输出信号的映射， 0 1 r 一 o ，1 ) 此处应注意 非完全定义的函数和完全定义的函数的区别，非完全定义函数为 0 ，驴_ 0 ，1 木) ， 水指输出值未确定。 布尔网络的有效表示就成为逻辑综合和工艺映射的一个重要的问题。第一种 被提出来的表示方法就是真值表。在真值表中，相当于每一组输入值都被映射到 一个输出，从而定义了一个输出函数。对这种表的处理通常采用卡诺图的方法。 但是卡诺图的不足性在于，当输入的个数大的时候，对真值表的操作就会变的非 常的不可行。因此，出现了一种比较可行的表示方法，c u b e s e t 表示法。c u b e s e t 表示法主要是利用了无关项的特性。具体是：当一个输入变量被标记为无关项后， 则输出变量的值不依赖于该输入变量。比如，输入变量为“1 0 1 1 和“1 0 0 1 ”时， 输出变量值都为“1 ，则输入可表示为“1 0 - 1 ，表示输出值与第三个输入变 量无关。这种方法应用非常的广泛，在过去的2 0 年中，所有的综合和工艺映射所 使用的电路表示都采用的是该方法。 2 0 0 2 年，一种新的电路表示方法被应用到了综合系统中 2 5 】。这种表示方法 是r o b d d ( 最简有序二分决策图) 。r o b d d 在1 9 8 6 年由b r y a n t 2 4 提出了可行的 操作方法，被广泛应用到了验证等领域。直到2 0 0 2 年才被应用到综合系统，并且 取得了很好的实验结果。同时，在b d s 中还提出了一个新的概念：域( d o m i n a t o r ) 。 域是基于r o b d d 的一种高效的操作。作为本文所提出的算法的基础，下一章将 对r o b d d 以及域进行详细介绍。 图2 9 给出了函数厂一a b c + a b c + a c 的各种表示形式。 1 4 基于域操作的工艺映射系统 abcs 00 01 00 10 0100 0l11 1000 】011 1100 ll1l abcs 0 00l 0l1l l ll 真值表 c u b e s e tr o b d d 图2 9 函数f = a b c + a b c + t i c 的不同表示形式 第三章最简有序二分决策图及其域操作 第三章最简有序二分决策图及其域操作 3 1 最简有序二分决策图 二分决策图( b d d ) 的概念首先由l e e 2 6 在1 9 5 9 年提出。l e e 指出一个函数 可以被表示为一系列的局部决策过程( tx ：a ，b ) ，当x 是0 的时候选取a 决策；当 x 是1 的时候，选取b 决策；在1 9 7 8 年，a k e r s 2 7 首先采用了“二分决策图 这个概念。同时他也给出了一系列的规则来化简b d d 但是直到1 9 8 6 年，b r y a n t 提出了一系列有效的操作之后，b d d 才得到了广泛的应用。几乎v l s ic a d 的所有 领域都得到了应用。同时也被证明是最有效的电路表达形式。 3 1 1 二叉决策图b d d 的构造 b d d 可以通过s h a n n o n s h a n n o n 表达式来构造： f = x ( x i ) + 可o )公式( 3 1 ) 一个b d d 与它所表示的布尔代数之间的关系可以按照如下递归定义： 1 如果节点v 是终端节点，则 ( a ) 如果v a l u e ( v ) = 1 ，则尤= 1 。 ( b ) 如果v a l u e ( v ) = 0 ，则f ，= 0 0 2 如果节点v 不是终端节点且它的i n d e x 为i ，则 厂“，x 2 ，) 一x j c r 瓴，x 2 ，) + 坑“，z ：，吒) 公式( 3 2 ) 在本文中，称指向函数l 的边为1 边，指向函数0 的边为0 边。如图3 1 所 示，布尔函数为f a c + b c + 口bc 。应当注意的是b d d 中每个节点都对应着一个 表达式。 图3 1 布尔函数厂= a c + b c + a b c 的b d d 1 6 基于域操作的工艺映射系统 3 1 2 最简有序二叉决策图r o b d d 的构造 【2 4 最重要的贡献就是r o b d d ( 最简有序二分决策图) ，将一个普通的 b d d 进行有序化( o r d e r e d ) ，化简( r e d u c e d ) 之后便得到r o b d d r o b d d 最重要的 特性便是唯一表示性，对于任意两个等价的布尔代数，当指定了变量顺序之后， 如果它们的b d d 表示形式是唯一的，则它们的b d d 表示形式必然是同构的。这 条特性使得判断两个布尔代数的等价性变的简单，只要知道了它们相应的 r o b d d ，则等价性问题就可以转换为两个r o b d d 的同构问题，其时间复杂性与 r o b d d 中所包含的节点个数成正比。 最简有序二叉决策图r o b d d 具体的化简步骤如下： 1 如果节点v 的左右子节点都指向同一个节点，则删除节点v 2 如果一个节点的b d d 表示与另外一个节点的b d d 表示是同构的，则删除 其中一个节点的b d d 表示。 这两条规则其实是和布尔运算相关联的。规则1 相当于a 厂+ a 一f ；规则2 对应于口厂+ 够。( 口+ 6 ) 厂因此r o b d d 的化简的理论基础就是布尔运算的规则。 图3 2 ( a ) 所示的r o b d d 是经过图3 1 中的b d d 经过化简和有序化之后得到 的。相比与图3 1 中的b d d ，节点的数量从1 5 个减少到了6 个，由此可见r o b d d 极大的减少了逻辑网络表示的存储空间。 利用补边的概念，可以进一步的减少b d d 中节点的数量。补边的概念首先 是在 2 7 中提出，然后在 2 4 得到实现。补边即为指向一个函数( b d d 节点) 的补 形式。图3 2 ( b ) 中的b d d 即为图3 2 ( a ) 的带补边的r o b d d 此处需要注意的是补 边只有一个终端节点1 ，而没有终端节点0 。 ( a )( b ) 图3 2r o b d d 与带补边的r o b d d 第三章最简有序二分决策图及其域操作 1 3 1 3 最简有序二叉决策图r o b d d 的重排序 由于r o b d d 的唯一性依赖于它的顺序，所以必须注意到r o b d d 的排序是 非常重要的一步。如图3 3 所示，图3 3 ( a ) 所示的是一种顺序的r o b d d ，节点的 数目非常的多，而图3 3 ( b ) 所示的是另外一种顺序的r o b d d ，节点的数目极大的 减少。由此可见r o b d d 的变量顺序的重要性。一个随机选择的顺序将会导致 r o b d d 节点数目的指数级增加。 掌警j 、一。、j 一：。= = 了蚤，鬈，j 0 ，7 ， 。心j 。夕7 二? ：? 书 j 一一j j j 心j 。“ 口口口田 ，7 褂：i ， r ，r一 ：一0 ，茹、，。， ， 夕：；? 7 i 4 簿：、| 。， ， !) j 易#tq” jji 毫鼻j ， 。 一、乎孕、口 ( a )( b ) 图3 3 不同变量顺序产生的r o b d d ( z 4 m 1 b l i f ) 目前为止，提出了许多关于r o b d d 重排序的算法 2 8 2 9 【3 0 1 1 3 1 3 2 ，主要 是基于拓扑结构，变量依赖性分析和相邻变量交换三种方法，其中最有效的算法 是相邻变量交换 3 2 ，同时在 3 2 中还提出一种动态变量交换的技术，使b d d 在 构造过程中可以动态的排序，从而有效的避免了由于局部b d d 过多而产生的内存 耗尽问题。 3 2 基于r o b d d 的域操作 域操作构成了本文所提出算法的基础，所以将会在这里详细的叙述。 表3 1 域操作和对应的布尔函数 域操作关系 0 d o m i n a t o r 算术或 1 - d o m i n a t o r 算术与 x d o m i n a t o r 算术同或 g e n e r a l i z e dd o m i n a t o r 布尔与或 g e n e r a l i z e dx - d o m i n a t o r 布尔同或 1 8 基于域操作的工艺映射系统 域操作的概念首先是在 3 3 被提出，提出的域操作有1 - d o m i n a t o r 和 o - d o m in a t o r 在 3 4 中提出了x d o m in a t o r ，g e n e r a liz e dd o m in a t o r 和 g e n e r a l i z e dx d o m i n a t o r 目前已提出的域操作和它们对应的关系如表3 1 所 示。具体的定义会在下面部分进行详细的陈述。 3 2 1 算术域操作 叶子边表示直接连接到b d d 终端节点( 1 节点和0 节点) 的边。令表示叶子 边的集合。表示直接连接到终端节点0 的叶子边的集合。表示直接连接到终 端节点1 的叶子边的集合。q 。表示从根节点到终端节点1 的路径的集合。q 。，表 示从根节点到终端节点0 的路径的集合。所以，q = q 。uq 。是所有路径的集合。 d = a + bq = c + d 图3 41 - d o m i n a t o r 节点以及1 - d o m i n a t o r 域操作 1 - d o m i n a t o r 节点定义为：一个节点v e v ，并且节点v 属于任何一条路径p eq ， 简而言之，1 - d o m i n a t o r 节点即为所有的通往终端节点1 的路径上的公共点。图3 4 即为一个1 - d o m i n a t o r 节点的例子，节点c 位于所有的通往终端节点1 的路径上， 所以是1 - d o m i n a t o r 节点。同时，1 - d o m i n a t o r 节点暗含了布尔函数的运算：与运 算。 1 - d o m i n a t o r 域操作定义如下： 给定一个b d d ，当确定它的1 - d o m i n a t o r 节点之后，可以将该函数f 表示为 函数d 和函数q 的与，并且这2 个函数都是函数f 的子函数。其中函数d 是由 函数f 的b d d 中的1 - d o m i n a t o r 节点以上的节点构成，函数q 是由函数f 的b d d 中的1 - d o m i n a t o r 节点以下的节点( 包含1 - d o m i n a t o r 节点) 构成。 如图3 4 ( b ) 所示，对3 4 ( a ) 中的函数f = ( a + b ) ( c + d ) ，节点c 是1 - d o m i n a t o r 节 点，所以根据d o m i n a t o r 域操作的定义，函数f 被分为2 个子函数：d = ( a + b ) ，q = ( c + d ) 第三章最简有序二分决策图及其域操作 1 9 由此可见，1 - d o m i n a t o r 域操作可以将一个函数分为与原函数等价的两部分， 并且两部分的函数互不相交，即没有公共变量。称这样的操作为算术操作。相反， 如果分解后的函数有公共变量，则称之为布尔操作。1 - d o m i n a t o r , 0 一d o m i n a t o r , x d o m i n a t o r 都属于算术操作，对应的关系分别为算术与，算术或，算术同或。 类似，0 d o m i n a t o r 节点定义为：一个节点v e v ，并且节点v 属于任何一条路 径p eq 。简而言之，0 - d o m i n a t o r 节点即为所有的通往终端节点0 的路径上的公 共点。 0 d o m i n a t o r 域操作定义如下： 给定一个b d d ，当确定它的0 d o m i n a t o r 节点之后，可以将该函数f 表示为 函数d 和函数q 的或，并且这2 个函数都是函数f 的子函数。其中函数d 是由 函数f 的b d d 中的0 d o m i n a t o r 节点以上的节点构成，函数q 是由函数f 的b d d 中的0 d o m i n a t o r 节点以下的节点( 包含0 d o m i n a t o r 节点) 构成。 同样，x d o m i n a t o r 节点定义为：一个节点v ( e v ，并且节点v 属于任何一条路 径p eq 简而言之，x d o m i n a t o r 节点即为所有的通往终端节点o 或是终端节点1 的路径上的公共点。 x d o m i n a t o r 域操作定义如下： 给定一个b d d ，当确定它的x d o m i n a t o r 节点之后，可以将该函数f 表示为 函数d 和函数q 的同或，并且这2 个函数都是函数f 的子函数。其中函数d 是 由函数f 的b d d 中的x d o m i n a t o r 节点以上的节点构成，函数q 是由函数f 的 b d d 中的x d o m i n a t o r 节点以下的节点( 包含x d o m i n a t o r 节点) 构成。 以上这些域操作符一旦确定后，便可以轻易的将2 个函数分为2 个部分，这 就意味着在进行划分的时候，可以容易的产生出备用划分。所以这3 个域操作是 最有效的域操作。下