（计算机系统结构专业论文）基于alm结构fpga的逻辑综合关键技术研究.pdf

基于a l m 结构f p g a 的逻辑综合关键技术研究 摘要 近些年来，f p g a 已经成为现代电子、半导体行业的最重要组成部分之一，针对f p g a 的综合技术 的研究是电子设计自动化技术的重要研究方向。逻辑综合是f p g a 综合的重要步骤，它包括逻辑优化 和工艺映射。本文主要研究了针对一种新型a l m ( a d a p t i v el o g i cm o d e l ) 结构f p g a 的工艺映射算法。 论文首先对已有f p g a 逻辑综合技术进行了全面的总结，从逻辑优化和工艺映射两个方面分析了传 统算法对a l m 结构f p g a 的适应性，通过分析我们得出结论，传统的逻辑优化算法仍然能够适用于 a l m 结构f p g a 的逻辑综合，而工艺映射算法则需要进行改进。 在以上分析的基础上，根据a l m 结构的特点，论文提出了一种以面积优化为主，同时考虑延迟的 针对a l m 结构f p g a 的工艺映射算法一a l m m a p 。该算法包括几个子算法，递减迭代装箱算法能够 很好的适应a l m 结构的灵活性；通过a l m 装箱算法并加入共享输入处理，将多个l u t 装a - - 个a l m 结构中；再汇聚路径的处理有助于提高效率和减少面积；算法在已有的多级分解算法基础上考虑了延迟 因素，在不降低面积优化效果的同时降低了延迟：通过全局优化从全局范围对面积进行了进一步的优化。 最后，我们对a l m m a p 算法与传统算法进行了测试与比较，通过实验数据表明，a l m m a p 能够很 好的发挥a l m 结构的灵活性，考虑延迟的多级分解算法能够很好的降低延迟，与传统基于k l o t 的 工艺映射算法相比，具有更好的面积与延迟综合性能。 关键词：a l m ，f p g a ，工艺映射， 逻辑优化，逻辑综合 t h ek e yt e c h n o l o g yo fl o g i c s y n t h e s i sf o ra l m b a s e df p g a a b s t r a c t i nt h ep a s td e c a d ey e a r s ，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 ) h a sb e e nt h em o s ti m p o r t a n tp a r to f m o d e m e l e c t r o n i ca n ds e m i c o n d u c t o ri n d u s t r y ，a n dt h es y n t h e s i st e c h n o l o g yi ne d a ( e l e c t r o n i cd e s i g na u t o m a t i o n ) b a s e do nf p g ah a sb e e nah o tr e s e a r c hf i e l d l o 舀cs y n t h e s i si sa ni m p o r t a n ts t e po fs y n t h e s i s ，i n c l u d i n g lo g i co p t i m i z a t i o na n dt e c h n o l o g ym a p p i n g an e wt e c h n o l o g ym a p p i n ga l g o r i t h m ，c a l l e da l m m a p ，i s p r o p o s e df o rt e c h n o l o g ym a p p i n go f a l m ( a d a p t i v el o g i cm o d e l ) b a s e df p g a f i r s t l y ，t h ep r e v i o u sl o g i cs y n t h e s i st e c h n o l o g i e sb a s e do nf p g a a r cs u m m a r i z e dc o m p r e h e n s i v e l y ，a n dt h e n , t h ea d a p t a b i l i t yo ft r a d i t i o n a la l g o r i t h m sf o ra l m b a s e df p g ai sa n a l y z e di nt e r m so fl o g i co p t i m i z a t i o n a n dt e c h n o l o g ym a p p i n g t h r o u g ht h o r o u g ha n a l y s i s ，w ec o n c l u d et h a tt r a d i t i o n a ll o g i co p t i m i z a t i o n a l g o r i t h m sc a na l s ob eu s e di nt h es y n t h e s i so fa l m - b a s e df p g a b u tt r a d i t i o n a lt e c h n o l o g ym a p p i n g a l g o r i t h m ss h o u l db ei m p r o v e d b a s e do nt h ea n a l y s i sa n df e a t u r eo fa l ms t r u c t u r e ，a l m m a pa l g o r i t h m , w h i c hi sa r e ao p t i m i z a t i o na i m e d w i t hd e l a yo p t i m i z a t i o nc o n s i d e r e di sp r e s e n t e d t h e r ea r ct h r e ep a r t si na l m m a p ，d e c r e a s i n g - i t e r a t i o nb i n p a c k i n ga l g o r i t h mi sp r o p o s e dt oa d a p tt h ef l e x i b i l i t yo fa l m , a l mp a c k i n ga l g o r i t h mc a np a c ks e v e r a l l u t si n t oo n ea l mw i t hs h a r e d i n p u t sh a n d l e d r e - c o n v e r g e n tp a t hh a n d l i n gc a nb eu s e dt oe n h a n c et h e e f f i c i e n c ya n dd e c r e a s et h e a r e ac o n s u m i n g , i m p r o v e dm u l t i l e v e ld e c o m p o s i t i o na l g o r i t h mc a nf u r t h e r e n h a n c ea r e ao p t i m i z a t i o nw i t h o u tm u c hd e l a yo p t i m i z a t i o nc o m p r o m i s e ；g l o b a lo p t i m i z a t i o ni m p r o v e sa r e a o p t i m i z a t i o ne f f e c ti nt h eg l o b a ls c o p e a tl a s t , e x p e r i m e n t sa r em a d et ot e s tt h ee f f e c to fa l m m a p t h ee x p e r i m e n tr e s u l t ss h o wt h a ta l m m a p c a n e f f e c t i v e l ye x e rt h ef l e x i b i l i t yo fa l m s t r u c t u r ea n dh a v eb e t t e ri n t e g r a t i v ep e r f o r m a n c eo fa r e aa sw e l la s d e l a yo p t i m i z a t i o nc o m p a r e dw i t ho t h e rt r a d i t i o n a lk o l u tb a s e df p g at e c h n o l o g ym a p p i n ga l g o r i t h m s - k e yw o r d s ：a l m ，f p g a ，t e c h n o l o g ym a p p i n g , l o g i co p t i m i z a t i o n , l o g i cs y n t h e s i s a l m ： a d a p t i v el o g i cm o d e l 英文缩略语对照表 a s i c ： a p p l i c a t i o ns p e c i f i ci n t e g r a t ec i r c u i t b d d ： b i n a r yd e c i s i o nd i a g r a m b l i f ： b e r k e l e yt , o g i ci n t e r c h a n g ef o r m a t c a d ： c o m p u t e ra i d e dd e s i g n c a m ： c o m p u t e ra i d e dm a n u f a c t u r e c a t ： c o m p u t e r a i d e dt e s t c l b ： c o n f i g n r a b l el o g i cb l o c k c p l d ： c o m p l e xp r o g r a m m a b l el o g i cd e v i c e d a g ：d i r e c t e d a c y c l i cg r a p h e d a ：e l e c t r o n i cd e s i g na u t o m a t i o n f p g a ： f i e l dp r o g r a m m a b l eg a t e a r r a y l u t ：l o o k u pt a b l e o b d d ： o r d e r e db d d p l d ：p r o g r a m m a b l el o g i cd e v i c e s o p ：s u m o f - p r o d u c t s p l d ： s i m p l ep r o g r a m m a b l el o g i cd e v i c e v l s i ： v e r yl a r g es c a l ei n t e g r a t i o n v 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了 谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办 理。 研究生签名：j 啦导师签名：蔓墨址日期：以夕易 1 1 课题背景 第l 章引言 第1 章引言 社会信息化正在对人类经济和社会生活产生革命性的影响，而半导体产业、电子技术的发展则是信 息化的基础与核心。2 0 世纪末以来，电子技术得到了飞速的发展，在其推动下，现代电子产品几乎渗 透了社会的各个领域，有力的推动了杜会生产力的发展和信息化程度的提高，同时也使现代电子产品的 性能进一步提高，产品更新换代的节奏也越来越快。 电子信息技术的硬件载体是超大规模集成电路( v l s i ) ，其中又分为通用集成电路和专用集成电路 ( a s i c ) 两类。随着集成电路技术的进步和向各行各业的渗透，专用集成电路技术得到了巨大的发展， 从系统设计规模上来看，已经由几十、几百门增加到了几百万、几千万门；从设计工艺上来看，已经由 9 0 年代的微米发展到了今天的深亚微米，甚至超深亚微米。如此大的系统规模与先进的设计工艺使得 原始的手工设计方法远远不能满足现代集成电路设计的需求，电子设计自动化技术也正是在这样的背景 下发展起来。 电子设计自动化( e d a ：e l e c t r o n i cd e s i g n a u t o m a t i o n ) ，简言之就是以计算机技术为平台，涵盖电 子设计中系统设计和综合、仿真、验证、制造全过程的自动化技术。e d a 技术融合了计算机辅助设计 ( c a d ) 、计算机辅助制造( c a m ) 、计算机辅助测试( c a t ) 、计算机辅助工程( c a e ) 等多项技术。 现代e d a 技术已经能够支持从系统高级描述，到物理层布局布线，为集成电路的设计提供了全方位的 有力支持。 2 0 世纪七、八十年代，集成电路进入t c m o s ( 互补场效应管) 时代，可编程逻辑器件( p l d ： p r o g r a m m a b l el o g i cd e v i c e ) 问世，它是在a s i c 设计基础上发展起来的，可以由用户通过软件进行配置 和编程，从而完成某种特定的逻辑功能。可编程逻辑器件可以细分为简单p l d ( s p l d ) 、复杂p l d ( c p l d ) 、以及f p g a 。8 0 年代末出现的f p g a ，由于其卓越的性能、灵活的设计模式、快速的生产周 期等优势，迅速发展起来，已经成为现代电子、半导体行业的最重要组成部分之一。 f p g a 的迅速发展，也促进了e d a 技术不断进步，大部分e d a 系统也都包含针对f p g a 的综合 ( s y n t h e s i s ) 工具。由于f p g a 与传统a s i c 相比存在结构上的特殊性，这使得许多传统基于a s i c 元 件库( c e l ll i b r a r y ) 的综合方法不再适用，从而促使了学术界对基于f p g a 的综合方法的研究，产生了 很多研究成果。 遗憾的是，目前为止我国在微电子领域的发展远远落后于西方发达国家，在e d a 工具方面基本上 被欧美企业如s y n o p s y s ，c a d e n c e ，m e n t o r 公司所垄断，国内还未见具有自主产权的完整的e d a 系统 问世。这对于经济、科技都处于高速发展阶段的中国来说，无疑是一个亟待解决问题。 1 2 论文主要内容 e d a 包括很多相关的技术，如高级综合( h i g h - l e v e ls y n t h e s i s ) 、r t l 综合( r t ls y n t h e s i s ) 、逻辑 综合( l o g i cs y n t h e s i s ) 、物理综合( p h y s i c a ls y n t h e s i s ) 等，本课题组对e d a 领域的关键技术进行了研 究。本文主要讨论了逻辑综合方向的相关技术，分析了传统基于k l u t 结构f p g a 的逻辑综合技术对 新型a l m 结构f p g a 的适应性问题，重点对作为逻辑综合关键技术之一的工艺映射进行了研究，并在 此基础上提出了个针对a l m 结构f p g a 的工艺映射算法一a l m m 叩。 1 3 论文章节安捧 论文共分为六章： 第1 章介绍了课题背景及论文主要内容。 l 东南大学硕士学位论文 第2 章从逻辑优化与工艺映射两个方面总结了基于f p g a 的逻辑综合技术。 第3 章分析了已有f p g a 逻辑综合技术对a l m 结构的适应性问题，并给出了分析结果a 第4 章提出了一种针对a l m 结构f p g a 的工艺映射算法，给出了算法所采用的主要技术与思路。 第5 章给出了a l m m a p 算法的实现细节并分析了实验结果 第6 章总结了论文的成果与创新点，并分析了存在的问题，提出了下一步工作的设想。 2 第2 章f p g a 逻辑综合技术介绍 2 1f p g a 简介 第2 章f p g a 逻辑综合技术介绍 f p g a ( f i e l dp r o g r a m m a b l eg a t e a r r a y ) 是近些年兴起的，可以用来替代传统a s i c ( a p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u s ) 设计的新技术。f p g a 由可编程的逻辑单元( l o g i ce l e m e n t ) ，可编程的 ( p r o g r a m m a b l ei oc o n n e c t i o n ) ，以及可编程布线资源( p r o g r a m m a b l er o u t i n ge l e m e n t s ) 组成。由于 支持设计者的现场编程，因此很好的弥补了传统a s i c 设计的成本高、生产周期长的缺点，而在业内受 到广泛欢迎。 为了实现现场可编程性，f p g a 中一般使用s r a m ( s t a t i c r a n d o m a c c e s s m e m o r y ) 来实现其可编程 逻辑单元及可编程布线资源。实现f p g a 中基本逻辑单元的最常用方法是通过2 。位个s r a m 元件实现的k 个输入、1 个输出的查找表( l u t ：l o o kl i pt a b l e ) ，记作k l u t - - + k l u t 可以实现任意一个不大于 k 输入的组合逻辑功能。除此之外还有使用多路器( m u l t i p l e x e r ) 构成的f p g a 。 基于l u t 结构的f p g a 是目前的一种主流产品对基于这种结构f p g a 综合技术的研究最多，本 文也主要讨论基于k l u t 结构f p g a 的逻辑综合技术。 2 2f p g a 综合流程分析 基于f p g a 的设计过程与传统a s i c 设计过程类似，要经过高级综合，r t l 综合，逻辑综合以及物 理综合几个步骤。其中高级综合从行为级出发，以电路的h d l 描述为输入，在算法级进行综合，生 成r t l 级电路；r t l 综合对r t l 电路进行优化，生成门级网表；逻辑综合主要包括两个步骤：逻辑优 化和工艺映射，其中逻辑优化的主要任务是对门级网表进行与工艺无关的分解与优化，得到最优的门级 电路；工艺映射将与工艺无关的结构映射到工艺相关的结构并满足一定硬件约束，使得高级综台系统抽 象的综合结果得以体现为一种具体的工艺实现，并在逻辑和结构上进一步优化设计；物理综合则考虑元 器件或逻辑单元的布局，以及最终的布线优化。 f p g a 综合流程如图2 - 1 所示： 逻辑优化 工艺映射 布局 布线 图2 1f p g a 综合的一般流程 逻辑综合是电子设计流程中重要的一步，逻辑综合的效果直接影响到最终实现电路的复杂性与性 3 东南大学硕士学位论文 能。传统的a s i c 设计中的逻辑综合主要基于特定单元库，以库单元作为目标网络的组件，通过匹配、 覆盖等技术构建一个目标网络，同时保证面积、延迟的最优化。对于k - l u t 结构的f p g a ，一个k 输 入的l u t ，可以实现任意不大于k 输入的组合逻辑功能因此有2 种逻辑功能，这使得当k 3 时， 所需元件库的规模将非常巨大”，例如若k 为5 ，则要求库单元的数目为4 , 2 9 4 ，9 6 7 ，2 9 6 个。因此，传统 的逻辑综合方法不能很好的适用于面向f p g a 的综合，这一问题也直接促使了近些年来对基于k - l u t 结构f p g a 逻辑综合方法的研究。 2 3 基本概念 为了后续讨论的方便，本节给出一些逻辑综合中常用的基本概念及其定义。 布尔变量( b o o l e a nv a r i a b l e ) ：代表一个布尔信号，用小写字母表示，只有0 、l 两个值。 字( 1 i t e r a l ) ：一个布尔变量及其非，如a 或万。 立方项( c u b e ) ：立方项c ，是字的集合。如果a e c ，则石c ，例如， 口，b ，c - - 是一个立方项，而 口，万) 则不是。一个立方项表示了它所包含的字的逻辑积，l c j 表示c 中字的个数。例如，立方项c = 口，b ，石) 表示一个逻辑积口坛，且i c 3 。 表达式( e x p r e s s i o n ) ：表达式是立方项的集合，一个表达式表示了它所包含的立方项的逻辑和。例如 “口) ，( 6 ，对 表示两个立方项 口) 和 6 ，刁的集合，记作口+ 6 - ，它以积之和( s o p ：s u m o f - p r o d u c t s ) 的形式，表示一个逻辑功能。 网络( n e t w o r k ) ：一个网络是用来表示逻辑功能的与工艺无关的结构，可以看成是一个有向无环图 ( d a g ：d i r e c t e d a c y c l i c g r a p h ) n = ( y ( ) ，e ( ) ) 。d a g 的每个节点v y ( ) 表示一个变量、门 电路或者较复杂的功能单元，边( v ，w ) ( ) 表示节点v 的输出是节点w 的输入，v 称为w 的扇入 ( f a n i n ) ，w 称为v 的扇出( f a n o u t ) 。p i ( p d m a r yi n p u t ) 节点是没有扇入的节点，p o ( p r i m a r yo u t p u t ) 节点是没有扇出的节点。一个简单网络如图2 - 2 所示。 图2 - 2 简单的网络 在图2 - 2 所表示的简单网络中，p i 是a ，b ，c ，d ，e ，e 舀，p o 是m ，l l ，q 。 4 第2 章f p g a 逻辑综合技术介绍 k - 可行( k - f e a s i b l e ) ：给定一个网络n = ( y ( ) ，e ( ) ) ，将节点v 矿( ) 的扇入的集合记作i n p u t ( v ) ， 将n 的子网络h 所包含节点的所有相异扇入集合记作i n p u t ( h ) 。如果存在一个正整数k 满足 j i n p u t ( v ) 匡k ，则称v 是k - 可行的，如果1 i n p u t ( h ) 苣k ，则称子网h 是k 一可行的。 k 有界( k - b o u n d e d ) ：如果一个网络n 中所有节点都是k 可行的，则称网络n 是k 一有界的。 f a n o u t _ f r e e ：给定一个网络n = ( 矿( ) ，e ( ) ) ，将任意节点v 矿( ) 扇出的集合记作o u t p u t ( v ) ，如 果l o u t p u t ( v ) 吕1 ，则称v 满足f a n o l i if r e e ，为了表述方便，记作v f a n o u tf r e e 锥体( c o n e ) ：给定个网络n = ( 矿( ) ，( ) ) ，节点v 的锥体c ，是网络n 的一个子网，并满足条件： 1 ) v 及其非p i 的前驱也属于c ，；2 ) 对于任意节点w ec v ，从w 到v 的路径完全包含在c ，中。 2 4f p g a 逻辑优化技术介绍 逻辑优化用来对网络进行转换与优化，使其更加适合映射到k l u t 结构中。首先，根据k l u t 的特点，不难证明，能够将一个网络映射到k l u t 的充分必要条件是，网络中的每个节点都具有k - 可行的锥体【2 j ，对于不满足条件的节点，则要对其进行分解：其次，由于对网络的分解有多种方式，要 使得分解后的网络经过工艺映射后具有最小的面积，则要对网络进行简化，通常的目标是使网络中不仅 门节点数量更少，而且门节点本身也更简单，同时具有较低的深度和更松散的连接。因此，从技术角度， 我们可以将f p g a 逻辑优化技术分为两类，即节点的分解技术与网络的简化技术。 网络中的每个节点代表一个简单或者复杂的逻辑函数，节点分解通过从若干节点所表示的函数表达 式中提取公共的子表达式，建立新的节点，从而使每个节点得到简化；网络简化则从整体出发，寻找一 组节点所表示函数的替代形式，从而使得网络中具有更少的节点数及更松散的连接。节点分解技术包括 基于平衡树的分解、提取、布尔分解、功能分解等，网络简化技术包括替代与消除、基于规则的简化等， 提取技术同样也可以简化网络。 2 4 ，1 平衡树分解 平衡树分解在m i s 1 1 t 中得到应用。它将每个节点v 的输入i n p u t ( v ) 分解为大小相同或相近的若干 组，引入k 个新节点，每个新节点以v 的一组输入作为其输入，然后将这k 个新节点作为节点v 的输 入。使用这种方法分解得到的网络具有最优的深度，但是使用的节点数却不是最少的。 图2 - 3 平衡树的分解 使用平衡树分解算法，图2 - 3 a 中节点i 的所有扇入节点被分为三组，并引入两个新节点，可以将 图2 - 3 a 中的所有节点都分解为3 - 可行的，如2 3 b 所示。 5 东南大学硕士学位论文 2 4 2 提取( e x n o n ) 提取( e x t r a c t i o n ) ：从多个表达式中找出公共子表达式，将公共子表达式用新的变量定义，然后依据新 的变量来重新定义所有的表达式称为提取。 从前面的介绍可以知道，网络中的每个节点都代表了一个逻辑表达式，通过提取多个节点的逻辑表 达式的公共子表达式，建立新的节点，可以使节点得到简化。例如，有两个节点，他分别表示逻辑函 数，：= c e + 出，t t = 口c + 口d + 缸+ + e ，显然我们很容易可以将石，t t 进行变换得到正= 0 十d ) e ， t ，= + 6 ) + d ) + e 。这时，我们如果引入一个新节点n ，并且让它表示逻辑表达式k = 0 + d ) ， 这样疋，t 2 可以通过k 化简为正= 妇，t 3 = a k + b k + e ，这时，网络中节点, i t l ，月2 同时都得到了简化， 字的个数也随之减少。 a 图2 4 提取 b 通过提取进行节点分解的过程如图2 - 4 一a 、2 - 4 一b 所示，节点n l 所含字的个数从4 降到2 ，节点n 2 所 含字的个数从9 降到5 ，字的总个数从4 + 9 = 1 3 ，降到2 + 5 + 2 = 9 。 很显然，要利用提取技术进行节点的分解与网络的简化，首先要找到若干节点所表示逻辑表达式的 公共子表达式。通常使用的方法是先将逻辑表达式变换为疋，2 的形式，然后再寻找公共子表达式， 其中一个关键技术称为除法( d i v i s i o n ) 。 除法( d i v i s i o n ) g 表达式，对表达式目的除法，用f q 表示，令p = f q 为商，r 为余数。可以将一 个函数厂表示为：f = p g + ，这里的g 通常称为因子( d i v i s o r ) ，当，= 0 时，称为整除。 根据是在代数领域还是在布尔领域进行除法运算，我们可以将除法分为两类，代数除和布尔除：在 表达式，= p q + ，中，当p q 为代数积时，称之为代数除，当p q 为布尔积时，称之为布尔除。所 谓的代数积是指表达式p ，q 中不包含同样的字，布尔积反之，例如厂q = ( a b + c ) ( d + p ) 为代数积， 而，_ q = ( a b + c ) ( 6 + c ) 为布尔积。通常使用布尔除比使用代数除更加彻底，但实现起来也较复杂。 已经证明，随着表达式中字的个数的增长，表达式可能包含的因子的个数呈指数增长，a r a y t o n 和 m c m u l l e n 引入了一类特殊的因子，称为核( k e m e l ) ，并且证明考虑表达式中的核与考虑表达式中的所 有因子一样有效1 4 j 。 核( k e r n e l ) ：表达式厂的核记作k ( 门= g d ( 力ig c u b e p e e 。其中，d 6 9 是指对应单个立 方项的商的集合，即d ( 力= f cic c u b e ) ；如果表达式g 不能被任何其他表达式整除，则称g 满足c u b ef r e e 记作g c u b e f r e e ，例如：a b + d c 是c u b e f r e e 的，而a b + b 则不是 6 a b c d e 第2 章f l e a 逻辑综合技术介绍 定理【4 j ：两个代数表达式，和g 有共同的因子d ，id 障2 ，当且仅当lk n k 除2 ， k k ( 厂) ，k 冬k ( g ) 。 根据定理，寻找具有多立方项因子的表达式的公共因子的问题，可以转换为求这些表达式的核的公 共立方项的问题，这比计算出表达式所有因子的问题要简单的多。 另外一种常用的提取方法，是基于b d d ( b i n a r yd e c i s i o nd i a g r a m ) 【5 l 的提取。b d d 是一种用来 表示逻辑函数的具有一个根的有向无环图( d a g ) ，它含有两种节点：一种是非终端节点( n o n t e r m i n a l v e r t e x ) ，每个非终端节点v 具有唯一的索引i n d e x ( v ) 1 , 2 ，埘 并且每个非终端节点v 具有两个子节 点，记作f o w ( v ) 、h i g h ( v ) ；另外一种是终端节点( t e m i n a lv e r t e x ) ，每个终端节点v 具有一个值，记作 v a l u e ( v ) 0 , 1 。b d d 的根节点代表一个函数，值为0 的终端节点表示函数厂的值为0 ，值为1 的终 端节点表示函数，的值为1 给定一个b d d 中的编号为j 的非终端节点v ，设节点v 表示的函数为g ， 则节点如以v ) 表示的函数为g i o ， f g 矗( v ) 表示的函数为g - i l 。连接节点v 和，d w ( v ) 的边标记为0 ， 连接节点v 和h i g h ( v ) 的边标记为i 。节点经过排序的b d d 称作o b d d ( o r d e r e db d d ) 嘲。 一个简单的函数f = a b + c 的b 叻如图2 - 5 所示： 图2 - 5 简单b d d 如果一个逻辑函数厂使用o b d d 表示，假设v 是网络中的一个非终端节点且表示函数 ，v 是工在 o b d d 中的根。在【6 】中提出了一种方法将工从，中分解出来：将v 以一个新节点v j 代替，v 的h i g h ( v ) 指向终端1 ，v 的l o w ( v ) 指向终端0 ，分解过程如图2 - 6 所示。 7 东南大学硕士学位论文 图2 - 6 基于o b d d 分解过程 图中：z = 万露+ 痂孑+ 勐葫+ 劭耐+ 刎+ 面五= 万砑+ 万石击+ 西，+ 万h ， x 。= 否a + c d 基于o b d d 的提取有众多优点：首先，总可以在常数时间内从一个o b d d 表示的网络中提取出子 函数，简单有效：其次，很容易从多个o b d d 中找出公共子函数；提取出来的函数还可以用作o b d d 的其他部分的优化m 。 2 4 3 布尔分解 根据香农表达式”1 ，任何一个逻辑函数，都可以表示为：厂= x 六+ ；正，其中正，正为分别与 丘1 ，正，o 相对应的e o n f a c t o r 。由于任何一个c o n f a c t o r 所包含的变量个数都比，少，因此反复使用香 农表达式进行分解，总可以将任何一个节点分解为k 可行的。 2 4 4 功能分解 对于任意逻辑函数f ( x l ，x 2 ，x ，) ，基于功能的分解可以描述为： f ( x l ，x 2 ，x ，) = g ( y l ( ，x 2 工) ，y ，( x l ，x 2 x ) ，x ，) 其中f ，l sr 。可以将功能分解理解为使用m 个新变量代替原有函数中的前- ，一1 个变量，因此弗， y 2 通常称为编码函数，占称为基函数。如果f = j - 1 ，则称为分离分解( d i s j u n c t i v e d e c o m p o s i t i o n ) ，否则称为非分离分解。变量而，x 2 x t 称为约束集( b o u n ds e t ) ，工，j ，称为自由集 ( f r e es e t ) 。当m = 1 时称为简单分解，否则为复杂分解。如果m 5 则实现一个l u t 的内部电路相对复杂，同时在映射简单逻辑功能时会造成资源的浪费；另一方面，如果k 4 则在映射 复杂结构时需要大量逻辑单元并产生较大的延迟脚。图3 - 3 很好的说明了以上观点。 a 初始网络 b 使用4 l u t 的映射结果 1 7 东南大学硕士学位论文 c 使用4 l u t ，5 ，l u t 混合的映射结果 d 使用5 l u t 的映射结果 图3 - 3 可变输入与固定输入l u t 映射的比较 图3 3 a 表示一个初始网络，如果完全使用4 l u t 来映射这个电路，如图3 - 3 一b ，则需要4 个4 l l r r ， 其中，编号为l 和4 的两个4 - l u t 只用来实现3 输入的逻辑功能，没有能够充分发挥其最大的逻辑容 量；如果完全使用5 l u t 来映射这个电路，如图3 3 一d ，则编号为l 和2 的两个5 - l u t 也没有充分利用 其最大逻辑容量。相比之下，使用4 l u t 和5 l u t 混合进行映射的结果在面积和延迟上的性能都要好， 如图3 3 - c 所示，所有的l u t 都充分的发挥了其逻辑容量。通常，我们称这种具有可变输入l u t 结构 的f p g a 为h e t e r o g e n e o u sf p g a 。由此可以预见，如果能够使用可变输入的l u t ，即k 的大小可以根 据需要配置，则会取得更好的效果。 对已有的基于l u t 的工艺映射算法进行调查可以发现，由于它们假设l u t 的输入数固定为k ，大 都不能很好的处理这种具有可变输入l u t 结构f p g a 的工艺映射。目前针对h e t e r o g e n e o u sf p g a 的算 法还比较少，而且大多只能处理包含有限种类l u t ，并且各种l u t 按一定比例存在的f p g a ，因此应 用受到限制。例如文献【5 5 】中，提出了一种以面积优化为目标的启发式算法，能够映射一个c l b ( c o n f i g u r a b l el o g i cb l o c k ) 中具有两种结构l u t 的f p g a ，该算法假设这两种l u t 按一定的比例存 在。国内方面，目前还没有这方面的成果公开发布。 当a l m 工作在正常模式下时，它可以完全兼容传统的基于k l u t ( k 6 ) f p g a 的工艺映射算 法，同时，a l m 结构可以实现多种l u t 的组合，具有极大的灵活性；另外，在一个a l m 中的l u t 可以通过共享输入提高a l m 的利用率与逻辑效率，如果仍然套用传统算法，将不能发挥a l m 结构的 优势。目前为止还没有发现公开文献讨论适合a l m 结构f p g a 的工艺映射算法。 8 茎! 兰堡竺望量竺全垫查翌! 些竺塑竺重些堡坌堑 一 3 4 结论 通过分析传统逻辑综合技术对a l m 结构的适应性，我们可以得出结论，传统基于k l u t 结构f p g a 的逻辑优化技术仍然适用于基于a l m 结构f p g a 的逻辑优化，而工艺映射技术则需要进行改进，以适 合a l m 结构的特点，便于发挥其优势。本文根据a l m 结构的特点，设计并实现了一种针对a l m 结 构f p g a 的工艺映射算法一a l m m a p 。 1 9 东南大学硕士学位论文 第4 章基于a l m 结构f p g a 的工艺映射算法a l m m a p 的设计 面积和延迟是工艺映射过程中要考虑的两个重要因素，根据a l m 结构的特点，我们设计了一种以 面积优化为主，同时考虑延迟的工艺映射算法a l m m a p 。核心算法包含三大部分：1 ) 二级分解。以面 积优化为目标，使用递减迭代装箱算法对网络进行分解，再通过a l m 装箱映射到a l m 结构中，同时 使用再汇聚路径，共享输入的处理进一步减少映射后a l m 的数量；2 ) 考虑延迟的多级分解。通过利 用a l m 中的空闲输入，可以进一步优化面积，但这会增加网络的深度，导致延迟增加，因此我们将考 虑延迟优化；3 ) 全局优化。由于前面都是以网络中单个节点及其直接前驱为基本分解、映射单位，没 有考虑全局信息，算法最后将进行全局优化。 4 1 二级分解 4 i 1 装箱算法在f p g a 工艺映射中的应用 装箱( b i n p a c k i n g ) 问题可简述如下：设有编号为0 、1 、n i 的n 种物品，体积分别为 o ，”l v ，一i 。将这n 种物品装到容量都为v 的若干箱子里。约定这n 种物品的体积均不超过v ， 即有o i 疗，0 v ，v 。不同的装箱方案所需要的箱子数目可能不同，装箱问题要求装完这n 种 物体所需要的箱子数最少。根据装箱所采取的不同策略可以将其分为以下几类： f i r s t o f i t ( f f ) 算法：从排在前面的箱子开始，对每个箱子的剩余体积逐一进行检查，一旦碰到第一个 能够装入当前物体的箱子时，就立即把该物体装入这个箱子 n e x t - f i t ( n f ) 算法：先把第一个空箱置为当前箱。然后依次把物品v o ，v l ，v “按下列方式装箱： 若当前所指的箱子里能放得下v f ，就把v ，放入箱中；若放不下，则把v ，放入下一个空箱，然后置放a v 。 的箱子为当前箱。 b e s t - f i t ( b f ) 算法：在已装有物品的箱子中，找一个既能放下v ，又能使剩余空间最小的箱子来放v ，。 f f d ( f i r s t - f i td e c r e a s i n g ) 算法：先将所有物品按体积从大到小排序，然后再使用f f 算法装箱。 c h o r t l e c f f 算法首先将装箱算法引入到基于k l u t 结构f p g a 的工艺映射中。c h o r t l e - c r f 算法以经 过逻辑优化与a n d o r 分解后的简单网络n = ( 矿( ) ，e ( ) ) 作为输入，按照从p l 到p o 的拓扑顺序， 对网络中的任意节点v 。v ( n ) 及其包括p i 节点在内所有前驱节点组成的锥体，利用装箱算法进行分 解，构建实现其逻辑功能的k l u t 树，要求所构建的k - l u t 树中的l u t 的数量最少。具体过程为： 给定网络中的一个节点v ，y ( ) ，将v 的直接前驱节点分别看成装满物品的b o x ，节点的输入数作为 b o x 的体积，将k l u t 看成容量为k 的b i n 。这时问题就可以转化为经典装箱问题，如果能将尽量多的 b o x 装入一个b i n ，那么装完所有的b o x 所需的b n 将是最少的，也就是l u t 数量最少。h 节点同样在 一个k l u t 中实现。当对v j 的后继节点v ，( v ，i n p u t ( v ，) ) 进行处理时，将实现v 节点的k - l u t 作为b o x ，重复上述过程，直到所有节点处理完毕。由于是按照从p i 到p o 的拓扑顺序进行，因此总可 以保证在处理网络中节点v 之前，v 的直接前驱节点要么就是p i ，要么就是已经分解过的节点。 例如，一个网络中的节点v 及其直接前驱节点w n ，w 3 ，w 4 ，w j 如图4 - 1 - a 所示，它以s o p 的 形式表示了逻辑函数f = a b c + d e c + g h + i j 4 - l m n 。 第4 章基于a i m 结构f p g 的工艺映射算法a l m m a p a b 图4 - l 装箱算法在f p g a 工艺映射中的应用 我们可以将作为节点v 的输入的直接前驱节点w j ，w 2 ，w 3 ，w 4 ，w j 看成装满货物的b o x ，每个节 点的输入数看成b o x 的体积。在图4 - 1 a 所示初始网络中，有5