（计算机软件与理论专业论文）动态可重构fpga布局算法的研究与改进.pdf

at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e rs o f t w a r ea n dt h e o r y 燃 r e s e a r c ha n di m p r o v e m e n to fp l a c e m e n t a l g o r i t h m f o rd y n a m i c a l l yr e c o n n g u r a b l e f p g a b yh a nj u n f a n g s u p e r v i s o r ：p r o f e s s o ry u g e n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 ：亡巴 思0 学位论文作者签名：韩磅方 日期：口0 7 、7 6 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年一年半口 学位论文作者签名：鲰裙方 签字e t 期：w 万7 两年口 导师签名：孑戈 签字日期：7 脚扩7 石 东北大学硕士学位论文 摘要 动态可重构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 ea r r a y ) 为代 表的可编程逻辑器件得到了广泛的应用。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 布局是一个n p 难问题，通常需要采用启发式算法对布局进行迭代求解，目前已有一些布局工具如v p r 采用模拟退火算法来进行求解。本文研究了f p g a 布局问题的模拟退火解决方案，并对 其局限性进行了分析，在此基础上提出了遗传算法解决方案和自动控温的改进模拟退火 算法解决方案，通过实验对三者的性能进行了对比，分析了算法的效率和扩展性问题。 最后利用自动控温的模拟退火算法对v p r 布局工具进行了改进。测试结果显示，改进 后的v p r 布局工具能够在不牺牲布局质量的情况下，高效率的完成布局，并且很好的 解决了原布局算法所存在退火进度控制问题，建立起退火进度和布局优化速度的联系， 具有良好的扩展性和可用性。 关键词：嵌入式系统；f p g a ；布局算法；布局评价方法；v p r 工具；模拟退火算法 1 东北大学硕士学位论文 a b s t r a c t r e s e a r c ha n di m p r o v e m e n to fp l a c e m e n t a l g o r i t h mf o rd y n a m i c a l l yr e c o n f i g u r a b l ef p g a a b s t r a c t w i t ht h ei n c r e a s eo ft h ec o m p l e x i t yo fe m b e d d e ds y s t e m s ，f i e l dp r o g r a m m a b l eg a t e a r r a y s ( f p g a s ) a r eg a i n i n gp o p u l a r i t y i ne m b e d d e ds y s t e md e s i g n f p g ap r e s e n t sa c o n v e n i e n tw a yf o r t h ed e s i g no fh a r d w a r ec i r c u i t s ，a n dt h ew h o l ed e s i g nf l o wo fh a r d w a r e c i r c u i tc a nb ea c c e l e r a t e dt h r o u g hc o m p u t e ra i d e dd e s i g ns o f t w a r e i nt h ed e s i g nf l o wo ft h e f p g ac i r c u i t s ，p l a c e m e n ti st h em o s tt i m e c o n s u m i n gs t e p ，a n da l s oh a sas t r o n gi m p a c to n t h eq u a l i t yo ft h ef i n a lf p g ac i r c u i t i m p r o v i n gt h ee f f i c i e n c yo fp l a c e m e n tc a nr e d u c et h e d e s i g nc y c l es i g n i f i c a n t l y , t h u sf p g ap l a c e m e n tb e c o m e st h er e s e a r c hh o t p o ti nr e c e n ty e a r s t h e r ea r et w om a j o rr e s e a r c hi s s u e so nf p g ap l a c e m e n t ：p l a c e m e n te v a l u a t i o nm e t h o d a n dp l a c e m e n ta l g o r i t h m p l a c e m e n te v a l u a t i o nm e t h o d sd e t e r m i n et h ed i r e c t i o no fp l a c e m e n t o p t i m i z a t i o n c u r r e n tp l a c e m e n t t o o l su s u a l l ye m p l o yw i r i n gl e n g t ht oe v a l u a t et h eq u a l i t yo f p l a c e m e n t h o w e v e r , a st h ed e v e l o p m e n to fd y n a m i c a l l yr e c o n f i g u r a b l ef p g a ，t h eo l d e v a l u a t i o nm e t h o dc a n ta c c o m m o d a t ew i t hn e ws i t u a t i o n sw e l l i nt h i sp a p e rw ep e r f o r m r e s e a r c ho nt h et r a d i t i o n a lm e t h o d ，a n db a s e do nt h ea n a l y z i n go fi t sd e f i c i e n c yp r e s e n tan e w p l a c e m e n te v a l u a t i o nm e t h o d ，w h i c hc o n s i d e r sb o t hw i r i n g a n da r e ac o s to fp l a c e m e n t e x p e r i m e n tr e s u l t ss h o wt h en e wp l a c e m e n te v a l u a t i o nm e t h o dh a sg o o dp e r f o r m a n c e p l a c e m e n ta l g o r i t h mh a sas t r o n gi m p a c to nt h ee f f i c i e n c yo ff i n d i n gt h eb e s ts o l u t i o n a n dt h eq u a l i t yo ft h ef i n a lf p g ac i r c u i t f p g ap l a c e m e n ti sa nn p c o m p l e t ep r o b l e m ，t h u s h e u r i s t i ca l g o r i t h m sa r eu s u a l l ya p p l i e d ，f o re x a m p l e ，v e r s a t i l ep l a c ea n dr o u t e ( v p r ) e m p l o y ss i m u l a t e da n n e a l i n g ( s a ) t ot r e a tp l a c e m e n tp r o b l e m s i nt h i sp a p e rw ec o n s i d e r p l a c e m e n t a l g o r i t h m sb a s e do ns a w ea l s op r e s e n tam e t h o dt h a tu s i n gg e n e t i ca l g o r i t h m ( g a ) o nt h ep l a c e m e n tp r o b l e m ，a n dg i v ea ni m p r o v e da l g o r i t h mb a s e do ns a ，a n dt h e n c o m p a r et h e i re f f i c i e n c ya n de x p a n s i b i l i t y f i n a l l y , t h en e wa l g o r i t h mi si m p l e m e n t e di nt h e v p rt o o la n de x p e r i m e n tr e s u l t ss h o wt h i ss o l u t i o nh a sa h i g h e re f f i c i e n c yt h a nt h ei n i t i a lo n e ， a n di t sa n n e a l i n gs c h e d u l ec a na d j u s ti t s e l fa u t o m a t i c a l l ya c c o r d i n gt oo p t i m i z a t i o nr a t e a sa r e s u l t ，t h en e wa l g o r i t h ms i m p l i f i e st h eh a r dt a s ko fp a r a m e t e ra d j u s t m e n ta n de n h a n c e st h e e f f i c i e n c yo fp l a c e m e n ta n dh a sg o o de x p a n s i b i l i t y i i i a b s t r a c t a c e m e n ta l g o r i t h m ；p l a c e m e n te v a l u a t i o nm e t h o d ； 一i v 一 东北大学硕士学位论文 目录 目录 声明i 中文摘要i i a b s l 风c t i i i 第1 章引言1 1 1 论文研究背景1 1 2f p g a 布局问题研究现状3 1 3 论文研究内容及组织结构6 第2 章f p g a 基本结构和设计流程9 2 1f p g a 的基本结构9 2 2f p g a 的设计流程一1 2 2 2 1 逻辑综合1 2 2 2 2 工艺映射1 3 2 2 3 布局一1 3 2 2 4 布线”1 3 2 2 5 比特流的生成一1 4 2 3f p g a 布局原理1 4 2 4 本章小结1 6 第3 章f p g a 布局评价方法的研究1 7 3 1f p g a 布局的基本目标1 7 3 2f p g a 布局中的线长估计：17 3 2 1 常用的线长估计法17 3 2 2 线长估计法的选择19 3 3 基于线网半周长的布局评价方法1 9 3 3 1 线网半周长的基本概念1 9 3 3 2 线长代价函数2 1 一v 目录 2 2 2 4 2 4 2 5 2 6 2 9 与改进3 1 31 3 1 - 3 2 3 4 3 5 3 5 3 6 3 6 3 7 4 0 4 1 4 2 4 3 3 交叉操作4 2 4 3 4 变异操作4 4 4 3 5 控制参数的选取4 5 4 3 6 算法流程4 6 4 4 基于自动控温退火算法的改进方案4 7 4 4 1 新解接受策略的设计4 7 4 4 2 布局质量调整系数k 的确定4 7 4 4 3 退火进度表的设计4 8 4 4 4 算法流程4 9 4 5 实验结果对比5 0 一v i 东北大学硕士学位论丈 目录 4 5 1 算法时间性能对比5 0 4 5 2 算法可扩展性对比5 l 4 5 3 结果分析5 l 4 6 本章小结5 2 第5 章改进算法在v p r 布局工具中的实现5 3 5 1v p r 布局工具简介5 3 5 2v p r 布局算法分析5 4 5 3 对v p r 布局工具改进5 6 5 3 1 布局工具基本结构5 6 5 3 2 符号表生成模块的设计5 7 5 3 3 布局模块的设计一一5 9 5 4 系统调试与测试6 3 5 4 1 输入文件格式6 3 5 4 2 运行结果6 5 5 4 3 结果分析与对比6 7 5 5 本章小结6 9 第6 章总结和展望7 1 6 1 论文工作总结7 l 6 2 未来工作及展望7 2 参考文献7 3 致谢7 7 科研项目和论文发表情况7 9 一v l i 东北大学硕士学位论文 第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 ) 得到了广泛的应用，越来越多的嵌入 式系统设计开始使用f p g a 作为底层硬件平台。本章介绍了课题的研究背景，阐述了当 前f p g a 布局问题的研究现状，对论文的研究内容和组织结构进行了概述。 1 1 论文研究背景 f p g a ( f i e l dp r o g r a m m n a b l eg a t e a 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 ) 、f - 1 阵列逻辑g a l ( g a t ea r a yl o g i c ) 、可编程逻辑器件 p l d ( pr o g r a m m a b l el o g i cd e v i c e ) 等可编程器件的基础上进步发展的产物。它是作为 专用集成电路a s i c ( a p p l c a t i o ns p e c i f i ci n t g r a t e dc i r c u i t ) 领域中的一种半定制电路而出 现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。f p g a 能完成任何数字器件的功能，上至高性能c p u ，下至简单的7 4 系列电路。工程师可以通 过传统的原理图输入法，或是硬件描述语言自由设计一个数字系统，利用e d a 工具进行 仿真，可以事先验证系统设计的正确性。在p c b 等硬件电路完成以后，还可以利用f p g a 的在线修改能力，随时修改设计而不必改动既定硬件电路。使用f p g a 来开发数字电路， 可以大大缩短设计时间，减少p c b 电路面积，提高系统的可行性和稳定性。自1 9 8 5 年 x i l i n x 公司推出第一片f p g a 芯片x c 2 0 0 己有2 0 多年的时间，在这2 0 多年中，f p g a 技术 取得了惊人的发展，f p g a 从最初的1 2 0 个可利用门，到现在数百万门的单片f p g a ，以 致不同的硬件算法可以在同一块芯片上实现【l j ，很多系统具有自恢复、自组织和自适应 的功能【2 】【3 1 。由于f p g a 具有开发周期短、开发软件投入少、芯片价格不断降低等优点， 促使f p g a 越来越多地取代a s i c 市场，特别针对小批量、多品种的产品需求，f p g a 已 成为首选。 动态可重构计算技术【4 】【5 】的出现和快速发展，进一步扩展了f p g a 的应用领域。动态 可重构f p g a 能够在电子系统工作的状态下，动态地改变电路的结构，这种配置方式灵 活而高效，通过硬件描述语言h d l ( h a r d w a r ed e s c r i p t i o nl a n g u a g e ) 以可编程的方式来完 成并实现电路的构建。通过引入动态可重构计算技术，整个嵌入式系统既保持了设计灵 活性，同时也获得了专用硬件电路的等价性能，使得系统逻辑电路资源既定的条件下， 能够对系统的逻辑电路资源在时间轴方向上分时复用，大大扩展了f p g a 使用和配置的 灵活性。作为可重构系统的基石，f p g a 的发展支撑着可重构系统的发展，它是可重构 e d a 软件一般使用诸o i v e r i l o g ，v h d l ，s y s t e mc 等硬件描述语言作为输入，经过 高级综合，逻辑综合，物理综合等步骤，最后生成f p g a 可配置比特流文件。其主要处 理流程如图1 1 所示。 其中，物理综合是e d a 软件极其重要的部分，它的好坏直接影响到整个e d a 系统的 质量和执行效率。物理综合包括布局和布线两个部分： 布局( p l a c e m e n t ) ：主要是决定电路网表中的元件在芯片中的位置。布局是指将标准 元件按照一定的约束条件( 线长短，串扰小等) 分布到f p g a 区域中，获得一个分布结 果，以供布线使用。 布线( r o u t i n g ) ：布线是在布局的基础上，按照网表的约束决定如何走线。一般采 用最短路径算法进行布线。布线完成后，生成f p g a l , 特流配置文件，下载到芯片中， 形成特定的功能电路。 布局和布线是f p g a 设计过程中对电路进行优化的最后一个阶段，直接影响到所生 成电路的质量。布局和布线紧密相连，布局的主要目标之一是得到一个利于布线的器件 一2 东北大学硕士学位论文 第1 章引言 分布。关于f p g a 布局问题的研究是近年来热点。 比特流配置文件 图1 1e d a 软件流程 一 f i g 1 1f l o wo f e d a s o f t w a r e 1 2f p g a 布局问题研究现状 布局是f p g a 的e d a 设计过程中最耗时的一个阶段，也是对最终生成的硬件电路质 量影响较大的一个阶段。提高布局的效率和质量往往能够较大程度的缩短f p g a 的设计 周期，改善最终所生成的电路的质量。因而关于f p g a 布局问题的研究一直是近年来的 热点，主要集中在如下两个方面。 ( 1 ) 布局评价方法的研究 布局评价方法用于指导布局的优化方向，决定什么样的布局更容易被布局算法所接 受。关于布局评价方法的研究主要集中在两个方面：全局布线长和关键路径延迟。 全局布线长度是一个传统的布局优化目标，也是最早展开研究的优化目标【7 】。通过 经验总结和分析，研究表明带权线网总长( w e i g h t e dt o t a lw i r e l e n g t h ) 最短化能综合反映 “使芯片面积最小化”、“缩短信号时延”等目利8 1 。这类全局线长估计函数主要有半周长 线长估计法【9 1 、线性最小生成树线长估计法【1 0 】和线性斯坦纳树线长估计法【l l 】【1 2 1 等。半周 长是以低精度的代价换得高执行效率，线性斯坦纳树则是以低效率来获得高精度。但是 还是可以通过一些方法来使得两个目标尽可能得到满足，例如用空间获得执行效率的提 高等，这也是研究的重点之一。通常情况下f p g a 辅助设计软件对时间比较敏感，因此 常采用半周长全局线长估计法。 3 一 东北大学硕士学位论文 笫i 章引言 随着集成电路特征尺寸的同趋减小和电路工作频率的不断提高，电路设计中的时序 约束即关键路径延迟，成为保证电路正常工作的重要因素。由于特征尺寸的减小和芯片 面积的增大，一方面使得连线电阻和电容增大而造成线网充放电时间增加；另一方面又 使得输入输出之问的路径增长，这样，当连线电阻和电容与驱动电阻电容相当时，互连 线的延迟( i n t e r c o n n e c td e l a y ) 就成为电路路径时延的一个重要因素。据统计，在高密度、 高速度的超大规模集成电路中，内部互连线延迟平均已达到时钟的5 0 到7 0 以上【13 1 。 因此，芯片内部互连线延迟已经越来越成为决定电路性能的一个主要因素。布局是决定 连线分布和线长的重要环节，其结果直接影响到电路内部互连线延迟，虽然全局布线长 度的优化在一定程度上能够减小总体平均的路径延迟，但是无法对一些关键路径的延迟 进行优化。现在以路径延迟为优化目标的时延驱动( t i m i n gd r i v e n ) 布局已经成为布局理 论研究中的热点问题，一些有效的时序估算模型女1 ：i e l m o r e 模型【1 4 】等已被证明拥有良好的 效果。 另外，随着f p g a 器件的发展和应用领域的不断扩展，一些新的布局评价方法被相 继提出。传统的布局评价方法没有考虑到布局分布的均匀性，可能使局部布局密度过大， 进而造成温度分布不均匀，局部温度过高等问题，文献【l5 】提出了一种考虑了温度分布的 布局评价方法，通过在评价方法中加入器件分布均匀度函数，改善了散热性能，使高温 区域的温度下降了3 3 。文献f l6 】则考虑到了功耗问题，提出了一种在布局阶段评价功耗 的算法。 总之，布局评价方法是布局首先需要解决的问题，决定了布局的优化方向。很多情 况下需要根据具体应用，对电路的某方面特征进行优化，特别是随着动态可重构技术的 发展，许多新的优化目标需要在布局中综合考虑。关于布局评价方法的研究，具有较大 的现实意义。 ( 2 ) 布局算法的研究 布局算法完成的任务是在各项电学和工艺要求的约束下，在给定的区域内将f p g a 基本逻辑单元安置到芯片的特定位置上，并尽可能满足各项布局优化目标。布局算法近 几年得到了广泛的关注和研究，并且产生了大量的科技文献和有效的布局工具【1 7 】【1 8 】。 i e e e 有专门的刊物讨论包括布局在内的集成电路设计自动化问题。国际上每年就此专题 要举行多个研讨会，女h i e e ep r o c e e d i n gd e s i g na u t o m a t i o nc o n f e r e n c e ，i n t e r n a t i o n a l c o n f e r e n c ec o m p u t e r - a i d e dd e s i g n ，i n t e r n a t i o n a ls y m p o s i u mo np h y s i c a ld e s i g n 等。国外 许多大学的电子工程系和计算机科学系都有这一研究领域的研究小组，如u n i v e r s i t yo f c a l i f o r n i aa tl o s a n g e l e sa n ds a nd i e g o ，u n i v e r s i t yo fb i n g h a n t o n ，n o r t h w e s t e r nu n i v e r s i t y - 4 东北大学硕士学位论文 第1 章引言 等。国内也有清华大学等高校一直从事该领域的研究和教学工作。 布局算法研究的主要目标是提高布局的质量和减少布局花费的时间。常用的布局算 法主要有三类：迭代法( i t e r r a t i v em e t h o d ) 、数学归纳法( m a t h e m a t i cp r o g r a m m i n gm e t h o d ) 和最小分割法( m i n c u tm e t h o d ) 。 迭代法【侈】是从一个已有布局状态出发，通过反复调整一个或者多个单元的位置，从 而不断地修改布局状态，最终得到一个比初始状态好很多的布局结果。与其它两类布局 方法相比，迭代法有很大的搜索域，可以得到高质量的布局结果，但执行效率比较低。 典型的迭代法如模拟退火算法，以美国加州大学伯克利分校的t i m b e r w o l f 为剜2 0 】。 数学归纳法【2 l 】是将布局问题抽象成为一个数学归纳问题，如二次规划问题，然后对 该模型进行数学求解。此类方法的一个非常好的特性是可以基于严格的数学分析证明它 的求解质量，但是由于该类方法是将布局问题抽象为数学模型，因此不得不采用一些非 精确模型进行近似，从而造成过分的约束，影响了最终的布局效果。数学规划法对布局 质量和花费时间进行了折中。文酬2 2 】提出了一种快速增量布局算法，算法采用单元行划 分的方法处理布局约束，然后将布局调整归结为单元依次插入单元行的问题，并构造了 一个数学规划求解最佳的插入方案，比简单启发式算法的执行效率要高很多，但有一定 偏差。 最小分割法【2 3 】是一种构造性的布局方法，它首先将电路分割成两个或更多个子电 路，同时将芯片的布局面积相应地分割成若干子区域，每个分割所得的子电路对应一个 子区域，如此反复分割下去，直到电路中的每个单元都有唯一的位置。分割法的优化目 标是：在分割过程中，使得分割所得的子电路之间的连线个数最少，或称割线最少。该 类方法具有优化速度快的特点，能够很好地适应集成电路规模不断增大的需要，但是由 于分割法的最终优化目标是割线最少，这与布局所追求的线网总长度最短的目标有偏、 差，影响了布局质量。另外，由于分割法是通过强行分割电路并在局部区域进行布局， 造成在早期不完整和不准确的信息条件下就做出了不可逆转的决定，因而缺乏全局观 念，很难获得布局的最优解。典型的最小分割算法如d r a g o n 2 0 0 0 2 4 】，其主要思想是先 将电路表示成超 蛩( h y p c t g r a p h ) ，然后按照一定要求进行超图分割。 由于后两种方法实现复杂度较高，针对较大规模的电路设计建模也比较困难，因此 应用较多的是迭代法，对布局算法的研究也多集中在迭代法框架内。模拟退火算法【2 5 1 是目前运用较为广泛的布局迭代求解算法，它是一种基于概率的解空间搜索算法，能够 以一定概率临时接受恶化解，从而避免了在搜索过程中陷入局部最优解。但是模拟退火 算法的性能常常受到退火策略和初始温度设置的影响，其退火策略和初始温度的设置通 5 上提出了一种综合考虑了布线长度和布局面积布局评价方法。针对当前f p g a 布局普遍 所采用的模拟退火算法存在的问题，本文提出了基于遗传算法的布局解决方案和基于自 动控温的退火算法的解决方案，并对三个算法的性能进行了实验对比，从中选出性能最 优的算法，将其实现在v p r 布局工具之中。最后使用基准电路对改进后的布局工具进行 了测试，结果显示，改进后的布局工具能够得到较高质量的布局结果，布局速度和可扩 展性都有了显著的提高。 本论文的内容安排如下： 第1 章为引言，介绍了课题的研究背景，概述了当前关于f p g a 布局问题的研究现状， 给出了本文的工作内容和组织结构。 第2 章主要介绍了可重构系统的核心原件- f p g a 。包括其基本原理、概念和分类， 介绍了基于查找表结构的岛状f p g a 的基本结构和实现原理。在此基础上分步骤阐述了 f p g a 的设计实现流程，详细分析了f p g a 的布局问题，为后面研究做了铺垫。 第3 章介绍了现有的f p g a 稚局评价方法，对常用的线长估计方法进行了讨论。重点 一6 一 东北大学硕士学位论文第1 章引言 介绍了基于线网半周长的线长估计方法，分析了其局限性，提出一种综合考虑布线长度， 面积代价和的多目标布局评价方法，并对其进行了扩展。 第4 章给出了f p g a 布局算法的模拟退火解决方案，在对其局限性进行分析的基础 上，提出遗传算法和自动控温的退火算法解决方案。研究了解空间编码、解调整策略、 交叉变异操作和参数设置等因素对布局性能的影响。并将三个算法的性能进行了实验对 比，从中得到性能最优的算法，为布局工具的改进奠定了理论基础。 第5 章介绍了v p r 布局工具布局算法的实现原理和局限性，并将改进的算法实现在 v p r 布局工具中，较详细的的阐明了利用改进模拟退火算法实现一个实际的布局工具的 过程。最后用基准电路对改进后的布局工具进行了测试，分析和对比了改进前后布局工 具的效率和性能。 第6 章为总结和展望，对遇到的问题做了总结，对未来工作做了展望。 7 学硕士学位论文 第1 章引言 一8 一 东北大学硕士学位论文第2 章f p g a 基本结构和设计流程 第2 章f p g a 基本结构和设计流程 f p g a 器件是可重构计算技术中最具代表性且使用最为广泛的器件之一，本文所做 的一切工作都是基于此物理器件的，本章首先介绍了f p g a 的原理和结构，接着分步骤 地介绍了f p g a 的基本设计流程，阐述了f p g a 设计过程中各阶段的主要工作，最后说 明了f p g a 布局的基本功能和原理，为后面的研究做了铺垫。 2 1f p g a 的基本结构 f p g a 一般由可配置逻辑模块c l b ( c o n f i g r a b l el o g i cb l o c k ) ，输入输出模块l 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 l l e c t i o nr e s o u r c e ) 以及一个用于存放编程数据 的s r a m 组成【2 7 1 。现在多数f p g a 都采用了岛型( i s l a n ds t y l e ) 结构，其结构如图2 1 所示。 叫“v 一 】 门口厂厂 】i _ j1 _ j 】 口口口 厂 】i _ j 】 厂厂厂口 】 i _ j i _ j1 ，j 】 口口 厂口 】i _ j 图2 1f p g a 结构 f i g 2 1s t r u c t u r eo ff p g a c l b 是f p g a 实现逻辑功能的基本单元，其基本结构如图2 2 所示，主要是由若干个 基本逻辑单元b l e ( b a s i cl o g i ce l e m e n t ) 通过门电路串联而成。b l e 是由一个基于查找表 l u t ( l o o k u pt a b l e ) 结构的k 输入逻辑函数发生器、触发器f f ( f l i p f l o p ) 和数据选择器 ( m u x ) 组成的。b l e 能够实现任意k 输入、单输出函数，同时可以选择输出是寄存器类 型或非寄存类型，其基本结构如图2 3 所示。 9 和设计流程 图2 3b l e 结构 f i g 2 3s t r u c t u r eo fb l e 每个c l b 含有b l e 的个数n 以及基本逻辑元素含有l u t 的输入端个数k 对f p g a 的速 度、面积、功耗等性能有很大的影响。文献四研究了l u t 对f p g a 面积和速度性能的影 响，文献【2 9 1 研究了每个c l b 中含有b l e 个数n 以及每个b l e 中含有的l u t 个数k 对f p g a 性能的影响，指出了实现高性能f p g a 的最优n 值和k 值，研究表明：单个c l b 中含有4 个b l e 的f p g a 性能最优；在l u t 数目一致的f p g a 中四输入的l u t 较其它输入具有更优 的性能。 i o b 提供了f p g a 内部逻辑阵列与外围器件之间的连接，通常排列在芯片的四周，主 要是由输入触发器、输入缓冲器、输出触发锁存器和输出缓冲器组成，i o b 可以被配置 成输入、输出或输入输出。 i r 包括各种长度的金属连线和可编程连接开关，主要实现c l b 与c l b ，c l b 与l o b 之间的连接，将f p g a 组合成一个整体。在f p g a 内部，其水平方向的连线和垂直方向的 1 0 图2 4f p g a 布局布线结构图 f i g 2 4p l a c e m e n ta n dr o u t i n gs t r u c t u r eo ff p g a f p g a 的可编程通过三种方式来实现【3 0 】【3 1 1 。使用最多的是利用s r a m 单元来控制传 输门、多路选择器和三态缓冲器把可编程布线和逻辑块配置成所需要的形式。图2 5 中给 出了三种基于s r a m 的开关。 ，? j j 一7 一? ，? 、 ：s p , _ a r c f 。：纠 j 。7 。，? 张 d 。斗 ：，幺， 传输门 选择器 三态缓冲器 图2 5f p g a 的s r a m 开关 f i g 2 5s r a ms w i t c ho f f p g a 东北大学硕士学位论文 第2 章f p g a 基本结构和设计流程 2 2f p g a 的设计流程 在f p g a 中实现一个电路需要将成千上万个可编程开关和配置位c b ( c o n f i g r u a t i o n b i t ) 设置成合适的状态，电路设计者一般需要采用高级的抽象语言来描述电路，例如使 用硬件描述语言( 如v h d l ，v e r i l o g 等) 或原理图输入。计算机辅助设计软件将这些高级语 言描述的电路转化为编程位流文件，用来设置f p g a d p 的可编程开关状态。这个过程是 十分复杂的，需要将其分为几步来完成，每一步完成特定的功能，如图2 6 所示。 2 2 1 逻辑综合 电路描述( h d l ) 上 逻辑综合 上 工艺映射 上 布局 上 布线 上 生成比特流 图2 6 f p g a 实现流程 f i g 2 6f l o wo ff p g ai m p l e m e n t i n g 逻辑综合是将较高层次的电路描述自动转换到较低抽象层次描述的一种方法。其基 本功能是将r t l 级的描述转换为门级网表的过程。 逻辑综合要求的输入除r t l 描述的程序模块或者原理图文件或波形文件外，还需要 另外两个输入文件，一个输入文件是综合工具支持的工艺库( 如c m o s i 艺库) ，这些工 艺库中包括一些标准的单元。在综合时，综合工具会将r t l 级代码描述的设计用工艺库 中的标准单元转化为逻辑电路。另一个输入文件是约束条件，用于决定综合过程中的逻 辑优化方法。约束条件中一般包括时间，面积，速度，功耗，负载要求和优化方法等， 有时还包括设计规则。逻辑综合的输出结果是门级网表。 1 2 东北大学硕士学位论文 第2 章f p g a 基本结构和设计流程 2 2 2 工艺映射 根据综合生成的网表，将用户设计嵌入f p g a 芯片。这里的嵌入是在一个芯片数据 库( d e v i c ed a t a b a s e ) 上进行的，这个芯片数据库提供了f p g a 芯片的所有细节。 工艺映射可以分为一下三个步骤： 1 分解( d e c o m p o s i t i o n ) ：分解的目的是将综合生成的等式( 即两级