（计算机应用技术专业论文）fpga布局算法研究与设计.pdf

中文摘要 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 ) ，即现场可编程门阵列，具有集成 度高、逻辑资源丰富、设计灵活以及使用范围广等特点，因此在数字系统设计中 得到了广泛的应用。f p g a 设计流程主要包括设计输入、逻辑综合、逻辑优化、 技术映射、打包、布局和布线。在f p g a 设计中，布局是极为重要的一个环节， 它直接影响到后续布线的质量和整个电路的性能。在f p g a 芯片逻辑资源中，布 线资源占到整个芯片资源的6 0 以上，因此如何在布局阶段对布线资源进行合理 的估算并有效降低布线的拥挤度成为布局算法重要研究方向。 基于布线拥挤度的f p g a 布局算法的研究主要分为两个方面：首先是如何使 现有的优化算法适应于f p r 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 著名开 源软件v p r 为研究平台，将布线拥挤度作为启发因子引导算法，实验表明基于布 线拥挤度的蚁群布局算法能够获得较好的结果。 布线拥挤度估算模型是基于布线拥挤度的布局算法的一个重要研究方向。本 文对主流拥挤度估算算法的特点进行了分析，提出一种等概率的拥挤度估算模 型。该模型基于b o u n d i n gb o x 结构构建，不依靠具体的布线路径来进行布线资 源估算，而是将布线资源的估算等概率分配给每个待布局区域，因此不会造成布 局时间的显著增加。实验结果表明该模型的估算精确度与x i l i n xi s e 基本一致， 将该模型融于布局算法中在不显著增加f p g a 布局时间的情况下降低了布线拥挤 度，从而改善了电路的性能。 关键词：f p g a 布局算法，布线拥挤度，蚁群算法，拥挤度估算模型 a b s t r a c t s i n c ef 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 st h ec h a r a c t e r i s t i c so fh i g h i n t e g r a t i o n ，r i c hl o g i c a lr e s o u r c e ，f l e x i b l ed e s i g na n daw i d e l yu s a g e ，i th a sb e e n w i d e l yu s e di nt h ed e s i g no fd i g i t a ls y s t e m s f p g ad e s i g nf l o wi n c l u d e sd e s i g ne n t r y ， l o g i cs y n t h e s i s ，l o g i co p t i m i z a t i o n ，t e c h n o l o g ym a p p i n g , p a c k i n g , p l a c e m e n ta n d r o u t i n g i nt h ef l o wo ff p g ad e s i g n ，t h ep l a c e m e n ti se x t r e m e l yi m p o r t a n tb e c a u s ei t d i r e c t l ya f f e c t st h eq u a l i t yo fr o u t i n ga n dt h ep e r f o r m a n c eo fw h o l ec i r c u i t r o u t i n g r e s o u r c e sa c c o u n tf o ro v e r6 0 o fo v e r a l lr e s o u r c e si nf p g ac h i p s ，s oh o wt od oa r e a s o n a b l ee s t i m a t i o nf o rt h er o u t i n gr e s o u r c ea n de f f e c t i v e l yr e d u c et h er o u t i n g c o n g e s t i o nb e c o m e s a ni m p o r t a n tr e s e a r c hd i r e c t i o nf o r p l a c e m e n ta l g o r i t h m t h er e s e a r c ho fp l a c e m e n ta l g o r i t h mb a s e do nr o u t i n gc o n g e s t i o ni sd i v i d e di n t o t w oa s p e c t s t h ef i r s ta s p e c t si sh o wt oa d a p tt h ee x i s t i n go p t i m i z a t i o na l g o r i t h mt o f p g aa r c h i t e c t u r ea n dm e r g er o u t i n gc o n g e s t i o nf u n c t i o ni n t ot h ea l g o r i t h ms t r u c t u r e ， s oa st oa c h i e v et h er e d u c t i o no fr o u t i n gc o n g e s t i o ni nt h ep l a c e m e n t s e c o n d l y ，t h e r e s e a r c hh a sb e e nf o c u s i n go nt h er o u t i n gc o n g e s t i o ne s t i m a t i o nm o d e l i nt h e s e a l g o r i t h m s ，t h er o u t i n gc o n g e s t i o ne s t i m a t i o nm o d e lc a na c c u r a t e l ye s t i m a t e t h e r o u t i n gr e s o u r c eu t i l i z a t i o n t h e nt h ec o s to fr o u t i n gc o n g e s t i o na sap a r to ft h ec o s t f u n c t i o nc a ng u i d et h ep l a c e m e n ta l g o r i t h mf o rr e d u c i n gt h eu s eo fr o u t i n gr e s o u r c e s t h i st h e s i sc a r r i e do u tad e t a i l e da n a l y s i so nt h em a i np l a c e m e n ta l g o r i t h mb a s e d o nr o u t i n gc o n g e s t i o n , i n c l u d i n gp a r t i t i o n - b a s e da l g o r i t h m ，s i m u l a t e da n n e a l i n g a l g o r i t h m ，g e n e t i ca l g o r i t h ma n da n tc o l o n ya l g o r i t h m w i t ht h ec o m p a r i s o no ft h e s e o p t i m i z a t i o na l g o r i t h m s a c o ( a n tc o l o n yo p t i m i z a t i o n ) i sa p p l i e d t of p g a p l a c e m e n tc o n s i d e r i n gr o u t i n gc o n g e s t i o n e x p e r i m e n t s s h o wt h a ta c o - b a s e d p l a c e m e n ta l g o r i t h mc a n o b t a i nb e t t e rr e s u l t st h a nt h a to fv p r r o u t i n gc o n g e s t i o ne s t i m a t i o nm o d e li sv e r yi m p o r t a n tf o rp l a c e m e n ta l g o r i t h m w ep r o p o s e dae q u i p r o b a b l e - e s t i m a t i o nm o d e lb a s e do nb o u n d i n gb o xs t r u c t u r e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h ea c c u r a c yo ft h i sm o d e li sc o m p a r a b l ew i t h x i l i n xi s e t h i sm o d e lw h i c hw a si n t e g r a t e di n t op l a c e m e n ta l g o r i t h mc a l li m p r o v e t h ec i r c u i tp e r f o r m a n c ew i t h o u ta s i g n i f i c a n ti n c r e a s i n go f r u nt i m eo fp l a c e m e n t k e yw o r d s ：f p g ap l a c e m e n ta l g o r i t h m ，r o u t i n gc o n g e s t i o n ，a n tc o l o n y o p t i m i z a t i o n , c o n g e s t i o ne s t i m a t i o nm o d e l n 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：日 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ： 导师( 签名) ：么合手日期p q 譬7 武汉理工大学硕士学位论文 第1 章引言 1 1 可编程逻辑器件简介 随着数字集成电路技术的发展，可编程逻辑器件( p l d ，p r o g r a n 咀n a b l el o g i c d e v i c e ) 已经成为一种有生命力的新型集成电路。它可以完全由用户通过软件进 行配置和编程来完成某种特定的逻辑功能。设计人员可利用e d a 软件工具快速开 发和仿真，然后将设计编程到器件中在实际运行的电路中对设计进行测试。由于 原型中使用的p l d 器件与正式生产最终设备时所使用的p l d 完全相同，这样就没 有了非重发性工程成本，最终的设计也比采用定制固定逻辑器件时完成得更快。 p l d 的另一个优点是在设计阶段中客户可根据需要修改电路，直到对设计工作感 到满意为止。这是因为p l d 基于可重写的存储器技术，如果用户改变设计只需要 简单地对器件进行重新编程即可。一旦设计完成，只需要利用最终软件设计文件 简单地编程所需要数量的p l d 就可以完成设计。 半导体行业协会( s i a ) 的研究数据表明：在过去几年时间里，p l d 的销售增 长速度超过了整个半导体行业的平均销售增长速度，可编程逻辑已经成为半导体 行业中增长最快的领域之一。 相比固定逻辑器件而言，p l d 具有如下优点： ( 1 ) p l d 在设计过程中为客户提供了更大的灵活性。对于p l d 来说，设计 反复只需要简单地改变编程文件即可，而且设计改变的结果可立即在工作器件中 看到。 ( 2 ) p l d 不需要漫长的前置时间来制造原型或正式产品。p l d 器件已经放在 分销商的货架上并可随时付运。 ( 3 ) p l d 不需要客户支付高昂的n r e 成本和购买昂贵的掩模组。p l d 供应商 在设计其可编程器件时已经支付了这些成本，并且可通过p l d 产品线延续多年的 生命期来分摊这些成本。 ( 4 ) p l d 允许客户在需要时仅订购所需要的数量，从而使客户可控制库存。 采用固定逻辑器件的客户经常会面临需要废弃的过量库存，而当对其产品的需求 高涨时，他们又可能为器件供货不足所苦，并且不得不面对生产延迟的现实。 ( 5 ) p l d 甚至在设备付运到客户那儿以后还可以重新编程。由于有了可编 武汉理工大学硕士学位论文 程逻辑器件，一些设备制造商现在正在尝试为已经安装在现场的产品增加新功能 或者进行升级。要实现这一点，只需要将新的编程文件上载到p l d 就可以在系统 中创建出新的硬件逻辑。 可编程逻辑器件缩短了电子产品制造商开发周期，同时能够帮助设计人员更 快地将产品推向市场。可编程逻辑器件不断提高的单片器件逻辑门数量使之集成 了更多的功能，这也大大改善最终系统的体积、功耗、性能、可靠性和成本。随 着p l d 供应商继续致力于在可编程逻辑器件中集成更多的功能、降低其成本并提 高能够节约时间的i p 核心的可用性，可编程逻辑将会成为数字系统设计的重要 工具。 1 2f p g a 发展现状及趋势 典型的p l d 由“与 、“非一阵列组成，用“与或”表达式来实现任意组 合逻辑，所以p l d 能以乘积和形式完成大量的逻辑组合。p l d 按照结构和功能可 以分成五种基本类型：现场可编程逻辑阵列f p l a ( f i e l dp r o g r a m m a b l el o g i c a r r a y ) 、可编程阵列逻辑p a l ( p r o g r a m m a b l ea r r a yl o g i c ) 、通用阵列逻辑g a l ( g e n e r i ca r r a yl o g i c ) 、可擦除的可编程逻辑器件e p l d ( e r a s a b l e p r o g r a m m a b l el o g i cd e v i c e ) 、现场可编程门阵列f p g a ( f i e l dp r o g r a m m a b l e g a t ea r r a y ) 。其中，f p g a 是在p a l 和g a l 基础上进一步发展的产物。p a l 由一 个可编程的“与平面和一个固定的“或 平面构成，或门的输出可以通过触发 器有选择地被置为寄存状态。p a l 器件是现场可编程的，它的实现工艺有反熔丝 技术、e p r o m 技术和e e p r o m 技术。还有一类结构更为灵活的逻辑器件是可编程 逻辑阵列( p l a ) ，它也由一个“与 平面和一个“或一平面构成，但是这两个平 面的连接关系是可编程的。p l a 器件既有现场可编程的，也有掩膜可编程的。g a l 是在p a l 的基础发展起来的又一种通用阵列逻辑，它采用了e e p r o m 工艺，实现 了电可按除、电可改写，其输出结构是可编程的逻辑宏单元，因而它的设计具有 很强的灵活性。这些早期的p l d 器件的一个共同特点是可以实现速度特性较好的 逻辑功能，但其过于简单的结构也使它们只能实现规模较小的电路。为了弥补这 一缺陷，2 0 世纪8 0 年代中期a l t e r a 和x i l i n x 分别推出了类似于p a l 结构的扩 展型c p l d 和与标准门阵列类似的f p g a ，它们都具有体系结构和逻辑单元灵活、 集成度高以及适用范围宽等特点。这两种器件兼容了p l d 和通用门阵列的优点， 可实现较大规模的电路，编程也很灵活。与门阵列等其它a s i c 相比，它们又具 有设计开发周期短、设计制造成本低、开发工具先进、标准产品无需测试、质量 2 武汉理工大学硕士学位论文 稳定以及可实时在线检验等优点，因此被广泛应用于产品的原型设计和产品生产 ( 般在i 0 ，0 0 0 件以下) 之中。几乎所有应用门阵列、p l d 和中小规模通用数字 集成电路的场合均可应用f p g a 和c p l d 器件。 随着电子产品的不断更新换代，用户对其性能的要求也不断提高，这也促使 f p g a 向高密度、高速度、宽频带、低功耗方向发展。如今，f p g a 芯片集成了更 多的逻辑单元( 例如b r a n ，嵌入式i p 核等) ，其性能大幅提高，使之适应于更 多高性能产品的开发。同时随着工业界对p l d 研究的不断深入，出现了s o p c 和 s o c 技术。s o p c 和s o c 技术是p l d 和a s i c 技术融合的结果，它涵盖了实时化 数字信号处理技术、高速数据收发器、复杂计算以及嵌入式系统设计技术的全部 内容。著名的f p g a 产商x i l i n x 和a l t e r a 也推出了相应s o cf p g a 产品，其制 造工艺达到6 5 n m ，系统门数也超过百万门。并且，这些逻辑器件内嵌了硬核高 速乘法器、g b i t s 差分串行接口、时钟频率高达5 0 0 e h z 的p o w e r p c t m 微处理器、 软核m i c r o b l a z e 、p i c o b l a z e 、n i o s 以及n i o s l i ，不仅实现了软件需求和硬件 设计的结合，还实现了高速与灵活性的结合，使其已超越了a s i c 器件的性能和 规模，也超越了传统意义上f p g a 的概念。从f p g a 的发展可以看出，f p g a 的应 用范围已经从单片级扩展到系统级，在未来必将成为数字系统设计的重要平台。 1 3f p g a 布局算法发展现状 f p g a 设计流程主要包括设计输入( d e s i g ne n t r y ) ，逻辑综合( l o g i c s y n t h e s i s ) ，逻辑优化( l o g i co p t i m i z a t i o n ) ，技术映射( t e c h n o l o g ym a p p i n g ) ， 打包( p a c k i n g ) ，布局( p l a c e m e n t ) 和布线( r o u t i n g ) 。f p g a 的布局是基于一定的 优化和约束准则将网表( n e t l i s t ) 文件描述的电路元素( 包括 o ，逻辑块b l o c k 和布线资源等) 映射到f p g a 芯片内部物理位置的过程。布局算法必须满足约束 规则，同时使代价函数最小化。布局的优化目标包括总线长最小化、时延最小 化2 1 3 m 1 副、拥挤度最小化6 3 7 1 8 3 9 1 等。 在f p g a 设计中，布局是极为重要的一个环节，它直接影响到后续布线的质 量和整个电路的性能。根据算法的特性可以把布局算法分为两类：初始布局和改 善布局。初始布局常采用构造性方法，根据电路的特点在较短时间内直接得到版 图结果。改善布局在初始布局的基础上不断迭代优化，直到得到满意的结果，通 常需要花费较长的时间，但布局结果比初始布局理想。改善布局算法中典型的有： 基于划分的布局算法1 0 1 、模拟退火算法1 2 h 1 朝、遗传算法、数学规划 方法1 7 1 n 8 1 、蚁群算法等。 3 武汉理工大学硕士学位论文 基于划分算法本身并不直接面向布局，只是在一定条件下将大的布局实例划 分成小的布局实例，把这些小的布局实例分配到更小的布局区域中，然后修改约 束条件，再把每一个小的布局实例进行相类似地划分。著名的k l 算法和f m 算法 常被用作划分的策略。基于划分的布局算法并不能保证得到全局最优解，容易陷 入局部最优，这是基于划分算法的主要缺点。 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 算法由m e t r o p o l i s 等人于1 9 5 3 年 提出，s a 算法的出发点是基于固体物质的退火过程与一般组合优化问题的相似 性。将固体加温至充分高，再让其徐徐冷却，加温时，固体内部都达到平衡态， 最后在常温时达到基态，内能减为最小。用固体退火过程模拟组合优化问题，将 内能e 模拟为目标函数值f ，由初始解i 和控制参数初值t 开始，对当前解重复 进行“产生新解、计算目标函数差、接受或舍弃的迭代，并逐步衰减t 值，算 法终止时的当前解即为所得近似最优解。模拟退火算法在某一初始温度下，伴随 温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最 优解，即在局部优化时能跳出局部最优解，并最终趋于全局最优解。科研界流行 的f p g ac a d 软件工具v p r ( v e r s a t i l ep l a c ea n dr o u t e ) 在布局中使用s a 算 法，实验证明该算法能获得较好的优化结果u 。 遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，具有很强的可并 行性和全局搜索能力。但由于选择操作对当前群外的解空间没有搜索能力，当种 群中各个体的分布“畸形 时交配操作的进化能力有限，小概率的变异操作也很 难增加种群的多样性，因此如果算法收敛准则设计不好，g a 经常会出现进化缓 慢或“早熟 收敛的现象。某些文献尝试将遗传算法的思想应用于对称结构的 f p g a 布局中，得到了较好的布局结果，但是它只能应用于规模较小的电路且算 法收敛性不好。 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) u 训是近年来发展迅速的一种 仿生算法。它是d o r i g o 和g a n b a r d e l l o u 在1 9 9 9 年通过模拟蚁群协同学习高效 寻找食源的生物行为提出的一种随机搜索算法，该算法应用于求解t s p 问题获得 了较遗传算法、模拟退火及进化规划更优的结果。它区别于g a 、s a 等算法的最 大特点之一是将已搜索空间的历史经验和优秀可行解间的相互影响巧妙而分布 式地存储在解空间的各独立分量中，不同可行解信息被整合后反映在同一条边权 信息中，具有很高的空间存储效率和高效的蚁群信息交换机制。这些特点表明它 是一种很有前途的优化方法。 f p g a 布局问题属于n p 难问题，因此基于一定的优化目标，寻找一种有效的 布局算法优化f p g a 布局和电路性能是f p g a 布局算法研究的热点。 4 武汉理工大学硕士学位论文 1 4 本文主要工作 在f p g a 芯片逻辑资源中，布线资源占到整个资源的6 0 以上，在布局阶段 对布线资源的使用进行合理的估算并有效降低布线的拥挤度将大大的缩短后续 布线的时间，提高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 著名开 源软件v p r 为研究平台，将布线拥挤度作为启发因子引导算法，实验表明基于布 线拥挤度的蚁群布局算法能够获得较好的结果。 布线拥挤度估算模型是基于布线拥挤度的布局算法一个重要研究方向。本文 对主流拥挤度估算算法的特点进行了分析，提出一种等概率的拥挤度估算模型， 此模型融于布局算法中在不显著增加f p g a 布局时间的情况下降低了布线拥挤度 改善了电路性能。 1 5 论文组织架构 本文组织结构如下： 第二章对f p g a 进行简要的介绍，主要对f p g a 结构、设计流程进行概述，同 时对论文所涉及的研究平台进行简要的介绍，包括科研界的f p g a 研究工具v p r 和工业界的主流f p g a 设计软件x i li n xi s e 。 第三章对基于拥挤度的f p g a 布局算法进行分析，首先引入布线拥挤度的概 念，然后对主流的基于布线拥挤度的f p g a 的算法进行分析，以此为理论基础对 f p g a 布局算法的设计进行探讨。 第四章和第五章是本论文的重点，第四章介绍蚁群算法在f p g a 布局中的应 用，在本章中基于蚁群算法完成了f p g a 布局的建模，并在布局中引入拥挤度因 子引导布局过程，该算法较v p r 获得了较优的实验结果。 第五章在对比分析主流布线拥挤度估算模型的基础上提出了一种等概率的 5 武汉理工大学硕士学位论文 布线拥挤度模型，该模型融入布局算法中获得了较好的效果。 第六章结论部分对本文的主要工作进行了回顾，提出对以后工作的展望。 6 武汉理工大学硕士学位论文 2 1f p g a 的结构 第二章f p g a 简介 f p g a 主要由可编程逻辑块( c l b ，c o n f i g u r el o g i cb l o c k ) 、可编程输入 输出单元( i o b ，i n p u to u t p u tb l o c k ) 和互连线资源( i r ，i n t e r c o n n e c t i o n r e s o u r c e ) 三大部分组成，如图2 - 1 所示。 i ，o b l o c k ， c o n f i g u r el o g i cb l o c k f l |l ll l i i lll |l i| i lff | | l l i i 、 i n t e r c o n n e c t i o nr e s o u r c e 图2 - 1f p g a 结构图 2 1 1 可编程逻辑块c l b ( c o n f i g u r el o g i cb i o c k ) 可编程逻辑块c l b 是f p g a 实现逻辑功能的基本单元，它由若干个基本逻辑 单元( b a s i cl o g i ce l e m e n t ，b l e ) 组成，如图2 - 2 所示。一个逻辑块可以包含一 个或多个基本逻辑单元，若基本逻辑单元数目超过两个，通常在逻辑阵列块内部 7 武汉理工大学硕士学位论文 提供一组局部互连线以减轻连线单元的负担2 0 1 。 d l c - c 溆 b 图2 - 2c l b 结构图 l ：o 基本逻辑单元b l e 是f p g a 中最小的功能单元，它通常包含一个查找表 ( l o o k u pt a b l e ) 和一个由时钟控制的触发器等，可以实现简单的组合或时序逻 辑电路功能，如图2 - 3 所示。 k o l n p u t l i 一 l u t d f l i p h o p r l f 0 - 图2 - 3b l e 结构图 根据数字电路的基本知识可以知道，对于一个n 输入的逻辑运算，不管是 与或非运算还是异或运算等，最多只可能存在2 n 种结果。所以如果事先将相应 的结果存放于一个存贮单元，就相当于实现了与非门电路的功能。b l e 实现可编 程的原理正是如此，它通过烧写文件去配置查找表的内容，从而在相同的电路情 况下实现了不同的逻辑功能。 查找表( l o o k u p t a b le ，l u t ) 是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 开发软件会自动计算逻辑电路的所有可能的结果，并把结果事 8 武汉理工大学硕士学位论文 先写入r a m ，这样，每输入一个信号进行逻辑运算就等于输入一个地址进行查表， 找出地址对应的内容，然后输出即可。 如图2 - 4 所示的一个实际的四输入一输出的与门逻辑电路，其逻辑输出端 o u t 共有1 6 种结果，如表2 - 1 所示。使用l u t 来实现该电路，即将a b c d 看成一 个1 6 1 的r a m 的地址线，如图2 - 5 所示。 a b c d 图2 - 4 四输入一输出与门逻辑电路图 地址线 l u t o l ( 1 6 幸1r a m ) t o u t 图2 - 5l u t 实现图 对于一个l u t 无法完成的电路，就需要通过进位逻辑将多个单元相连，在 f p g a 中通过互连线资源可以将l u t 连接实现复杂的逻辑功能。 9 武汉理工大学硕士学位论文 表2 - 1 实际电路与l u t 结果对比 实际逻辑电路l u t 实现 a b c do u t地址 l u t 输出 0 0 0 000 0 0 00 0 0 0 100 0 0 1 0 0 0 1 000 0 1 00 0 0 1 100 0 1 10 0 1 0 0 0 0 1 0 0 0 0 1 0 100 1 0 10 0 1 1 000 1 1 00 0 1 1 1 00 1 1 1 0 1 0 0 001 0 0 00 1 0 0 101 0 0 10 1 0 1 001 0 1 00 1 0 1 101 0 1 10 1 1 0 001 1 0 00 1 1 0 101 1 0 10 1 1 1 001 1 1 00 1 1 1 111 1 1 11 2 1 2 可编程l o b ( i n p u t o u t p u tb i o c k ) 可编程输入输出单元i ob l o c k 是芯片与外界电路的接口部分，完成不同 电气特性下对输入输出信号的驱动与匹配要求，实现芯片内部与外围电路的通 信。f p g a 内的i o 按组分类，每组都能够独立地支持不同的i o 标准。通过软 件的灵活配置，可适配不同的电气标准与i o 物理特性。目前，i o 口的频率 也越来越高，一些高端的f p g a 通过d d r 寄存器技术可以支持高达2 g b p s 的数据 速率。 2 1 3 互连线资源i r ( i n t e r c o n n e c t i o nr e s o u r c e ) f p g a 芯片内部有着丰富的互连线资源，根据工艺、长度、宽度和分布位置 的不同而划分为4 类不同的类别。第一类是全局布线资源，用于芯片内部全局时 1 0 武汉理工大学硕士学位论文 钟和全局复位置位的布线；第二类是长线资源，用以完成芯片b a n k 间的高速 信号和第二全局时钟信号的布线；第三类是短线资源，用于完成基本逻辑单元之 间的逻辑互连和布线；第四类是分布式的布线资源，用于专有时钟、复位等控制 信号线。在f p g a 设计中，确定合理的连线元长度及其构成比例对于f p g a 结构 设计至关重要。 另外，随着f p g a 的发展，商用的f p g a 芯片为了满足更高性能的要求集成了 更多的逻辑单元，例如b r a m 和内嵌的专用硬核等等。b r a m 可被配置为单端口r a m 、 双端口r a m 、内容地址存储器( c a m ) 以及f i f o 等常用存储结构，这大大拓展了 f p g a 的应用范围和灵活性。除了b r a m ，为了提高f p g a 性能，芯片生产商在芯 片内部集成了一些专用的硬核。例如：为了提高f p g a 的乘法速度，主流的f p g a 中都集成了专用乘法器；为了适用通信总线与接口标准，很多高端的f p g a 内部 都集成了串并收发器( s e r d e s ) ，可以达到较高的收发速度。 2 2f p g a 设计流程 f p g a 的设计流程就是利用e d a 开发软件和编程工具对f p g a 芯片进行开发 的过程。典型f p g a 的开发流程包括设计输入、功能仿真、综合优化、逻辑优化、 技术映射、综合后仿真、布局布线、时序仿真、芯片编程与调试，如图2 - 6 所示。 ( 1 ) 设计输入 设计输入( d e s i g ne n t r y ) 是将所设计的系统或电路以某种形式表示出来， 并输入给e d a 工具的过程。目前在实际开发中应用最广的就是h d l 语言输入法， 主流h d l 语言为v e r i l o gh d l 和v h d l 。该类语言与芯片工艺无关，利于自顶向 下设计，便于模块的划分与移植，可移植性好，具有很强的逻辑描述和仿真功能， 而且输入效率很高。 ( 2 ) 功能仿真 功能仿真也称为前仿真是在编译之前对用户所设计的电路进行逻辑功能验 证，此时的仿真没有延迟信息，仅对初步的功能进行检测。 ( 3 ) 逻辑综合 所谓综合就是将较高级抽象层次的描述转化成较低层次的描述。综合优化根 据目标与要求优化所生成的逻辑连接，使层次设计平面化，供f p g a 布局布线软 件进行实现。就目前的层次来看，综合优化( s y n t h e s i s ) 是指将设计输入编译成 由与门、或门、非门、r a m 、触发器等基本逻辑单元组成的逻辑连接网表，而并 非真实的门级电路。真实具体的门级电路需要利用f p g a 制造商的布局布线功 武汉理工大学硕士学位论文 能，根据综合后生成的标准门级结构网表来产生。为了能转换成标准的门级结构 网表，h d l 程序的编写必须符合特定综合器所要求的风格。由于门级结构、r t l 级 的h d l 程序的综合是很成熟的技术，所有的综合器都可以支持到这一级别的综 合。常用的综合工具有s y n p l i c i t y 公司的s y n p l i f y s y n p l i f yp r o 软件以及各 个f p g a 厂家自己推出的综合开发工具。 ( 4 ) 逻辑优化 逻辑优化( l o g i co p t i m i z a t i o n ) 常常被称为与技术无关的优化，在这个阶 段，目标是简化逻辑功能而没有考虑实际的电路技术。冗余逻辑被去除，减少了 网络的面积。 ( 5 ) 技术映射 技术映射是一个将用户电路映射到l u t 的过程。一个k 输入的l u t 是一个数 字存储器，能实现任意k 输入、单输出的布尔函数。因此，一个k 输入的l u t 能完成任意一个2 的k 次个不同的布尔函数。当逻辑模块包含多于一个l u t 的 f p g a 时，l u t 的网表将封装到与每个逻辑块l u t 相关的簇中去。技术映射与最终 电路实现的f p g a 平台相关。 ( 6 ) 布局布线 布局布线可理解为利用实现工具把逻辑映射到目标器件结构的资源中，决定 逻辑的最佳布局，选择逻辑与输入输出功能链接的布线通道进行连线，并产生相 应文件( 如配置文件与相关报告) ，实现是将综合生成的逻辑网表配置到具体的 f p g a 芯片上，布局布线是其中最重要的过程。 布局将逻辑网表中的硬件原语和底层单元合理地配置到芯片内部的固有硬 件结构上，并且往往需要在速度最优和面积最优之间折中。 布线根据布局的拓扑结构，利用芯片内部的各种连线资源，合理正确地连接 各个元件。布线一般分为全局布线和详细布线，全局布线只确定具体的走线路径， 而详细布线需要优化目标确定具体的导线类型，开关盒类型等。布线结束后，软 件工具会自动生成报告，提供有关设计中各部分资源的使用情况。 ( 7 ) 时序仿真 时序仿真，也称为后仿真，是指将布局布线的延时信息反标注到设计网表中 来检测有无时序违规( 即不满足时序约束条件或器件固有的时序规则，如建立时 间、保持时间等) 现象。时序仿真包含的延迟信息最全，也最精确，能较好地反 映芯片的实际工作情况。由于不同芯片的内部延时不一样，不同的布局布线方案 也给延时带来不同的影响。因此在布局布线后，通过对系统和各个模块进行时序 仿真，分析其时序关系，估计系统性能，以及检查和消除竞争冒险是非常有必要 的。在功能仿真中介绍的软件工具一般都支持综合后仿真。 1 2 武汉理工大学硕士学位论文 ( 9 ) 芯片编程与调试 设计的最后一步就是芯片编程与调试。芯片编程是指产生使用的数据文件 ( 位数据流文件，b i t s t r e a mg e n e r a t i o n ) ，然后将编程数据下载到f p g a 芯片中 实现电路功能。 图2 - 6f p g a 设计流程图 2 3f p g a 研究工具及平台 随着f p g a 应用的不断普及，对f p g ac a d 工具的要求也被提出，科研界和工 业界都对f p g ac a d 工具展开了积极的研究。本节介绍f p g a 科研界主流研究工具 v p r 和工业界著名的f p g a c a d 软件x i l i n xi s e ，包括它们的基本原理和设计思路， 武汉理工大学硕士学位论文 本文的后续研究就是基于这两个工具进行的。 ( 1 ) v p r ( v e r s a t il ep l a c ea n dr o u t e ) v p r ( v e r s a t i l ep l a c ea n dr o u t e ) u 1 是由多伦多大学v a u g h nb e t z 和 j o n a t h a n 等人基于l i n u x 平台开发的适用于不同f p g a 架构研究的布局布线工 具，目前大多数f p g a 布局布线的学术研究都是基于此工具进行的。 v p rc a d 流程如图2 - 7 所示。它以f p g a 架构描述文件( a r c h i t e c t u r e d e s c r i p t i o nf i l e ) 和已被技术映射的电路网表文件( t e c h n o l o g y m a p p e d n e t l i s t ) 作为输入，布局器( p l a c e r ) 对电路架构文件进行分析提取相关架构 参数后按照用户的优化目标进行布局，目前v p r 布局器支持三种优化目标的布 局，即互连线长度最小化( w i r e l e n g t h d r i v e n p l a c e m e n t ) ，拥挤度最小化 ( r o u t a b i l i t y - d r i v e np l a c e m e n t ) ，电路时延最小化( t i m i n g - d r i v e n p l a c e m e n t ) 。 图2 - 7v p rc a d 流程 v p r 使用模拟退火算法进行布局，它使用一种线性拥塞( l i n e a rc o n g e s t i o n ) 函数作为优化目标引导布局过程。该线性拥塞函数表达式如下： ( 2 - 1 ) 其中c o s t 是对网表( n e t l i s t ) 中所有线网( n e t ) 的代价函数进行求和，对 于每个线网( n e t ) 而言，6 以和b b , 表示该线网所覆盖的b o u n d i n gb o x 宽度和高 度，而。，和g ，表示该b o u n d i n gb o x 内水平和竖直方向的平均通道容量，即 1 4 武汉理工大学硕士学位论文 每个通道内所含有的布线t r a c k 的条数。q ( n ) 是一个补偿因子，用于补偿随着端 口递增而导致网线的非线性增加，该代价函数对较窄的通道中进行大量布线的行 为进行了适当限制。 布局器完成布局后进入布线环节，布线器( r o u t e r ) 提供两种模式的布线， 即全局布线( g l o b a lr o u t i n g ) 和全局细节布线( g l o b a l - d e t a i lr o u t i n g ) 。全 局布线是基于电路整体结构的布线过程，并不考虑导线类型和用于线网连接的相 关开关盒类型，而全局细节布线不仅要考虑具体的走线路径和方向，而且需要 为不同的线网选择合适的导线类型和开关盒。v p r 布局布线完成后将产生一系列 的统计文件供用户分析，其中