（电路与系统专业论文）基于vpr的fpga布局算法研究与改进.pdf

武汉理工大学硕士学位论文 摘要 f p g a 是八十年代中期出现的新型可编程逻辑器件，在f p g a 芯片设计研究 上，现有的布局算法日渐成熟，但仍然存在很多问题。布局布线是f p g a 芯片 设计中最耗时的阶段，能够设计出更加快速、更小面积、时延少、低功耗的算 法是学术界研究的热点和趋势。广泛应用于学术界研究的v p r 软件是一款f p g a 布局布线的通用软件，它提出了相对较完整的布局布线方法的解决方案。v p r 布 局算法使用的是模拟退火法，模拟退火法的优点是能跳出迭代过程中的局部最 优解而得到接近于全局的最优解，但缺点是需花费较长的时间。 为解决f p g a 的布局问题，本文以v p r 为基础，提出和实践了快速模拟退 火算法布局法，推广型模拟退火算法布局法，力矢量退火算法布局法，渐升温 回火退火算法布局法。与经典模拟退火算法相比，快速模拟退火算法模型的接 收概率是按广义g i b b s 分布给出的，其扰动模型类似c a u c h y 分布，降温方式为 丁( k ) = t o a “，采用新的模型收敛速度更快。推广型模拟退火算法也是以广义 g i b b s 分布为基础，扰动模型为t s a l l i s s t a r i o l o 跃迁分布形式，它在目标函数多， 局域极小值也较多时比经典模拟退火算法更为有效。经典模拟退火算法和快速 模拟退火算法都是推广型模拟退火算法的特例。力矢量混合退火算法布局是把 力矢量松弛法和模拟退火法结合起来的布局方法，力矢量松弛法的核心是每次 交换时与当前单元受力最小的理想位置交换，结合模拟退火法就是用模拟退火 法的接受策略来判断是否接受交换后的解。渐升温回火退火算法改变退火的降 温策略，先用较低的温度退火，把优化后的解作为下一次退火的初始解，初始 温度逐渐上升，反复执行退火策略得到最后结果。 实验结果表明，与v p r 相比，在大规模电路布局中：快速模拟退火算法可 以提高速度为原来的1 9 倍，但是布局质量下降4 ；推广型模拟退火算法可以 提高速度为原来的6 3 倍，但是布局质量下降1 5 左右；力矢量混合退火算法基 本没有改变效果；渐升温回火退火算法可以提高速度为原来的3 倍，而且布局 质量不下降。上述算法在f p g a 的布局速度方面做出了一定的改进。 关键字：布局；现场可编程门阵列；电子设计自动化；v p r 武汉理工大学硕士学位论文 a b s t r a c t f p g aa p p e a r si nt h em i d - 19 8 0 sa san e wt y p eo fp r o g r a m m a b l el o g i cd e v i c e a l t h o u g ht h ep l a c e m e n to ft h ee x i s t i n ga l g o r i t h m si sv e r ye f f e c t i v e ，t h e r ea r es t i l l m a n yp r o b l e m sf o rf p g ad e s i g n f p g ap l a c e m e n ta n dr o u t i n gi st h em o s t t i m e - c o n s u m i n gs t a g ei nc h i pd e s i g n t od e s i g nf a s t e r , s m a l l e rs i z e ，l e s sd e l a y , a n d l o w - p o w e ra l g o r i t h mi sav e r yh o tr e s e a r c ht o p i c t h ev p r i sc o m m o ns o f t w a r ef o r t h ef p g a p l a c e m e n ta n dr o u t i n g i tp u t sf o r w a r dac o m p r e h e n s i v em e t h o do ff p g a p l a c e m e n ta n dr o u t i n gs o l u t i o n s i m u l a t e da n n e a l i n ga l g o r i t h mi sa p p l i e dt ov p r t h ea d v a n t a g eo fa l g o r i t h mi st h a ti tc a nj u m po u to fl o c a lo p t i m a ls o l u t i o nt ob e c l o s et ot h eo p t i m a ls o l u t i o n ，b u tt h ed r a w b a c ki st h a ti tt a k e sal o n gt i m e i no r d e rt oa d d r e s st h ei s s u e ，s o m ea l g o r i t h m s ，s u c ha sf a s ts 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 r a ls i m u l a t e da n n e a l i n ga l g o r i t h m ，f o r c ed i r e c t e da n n e a l i n ga l g o r i t h m a n da s c e n d i n gt e m p e r a t u r et e m p e r i n ga n n e a l i n ga l g o r i t h m ，a r ea p p l i e di nt h ef p g a p l a c e m e n t c o m p a r e dt oc l a s s i c a ls i m u l a t e da n n e a l i n ga l g o r i t h m ，f a s ts i m u l a t e d a n n e a l i n ga l g o r i t h mm o d e li s b a s e do nt h e r e c e p t i o np r o b a b i l i t yg i v e nb yt h e g e n e r a l i z e dg i b b sd i s t r i b u t i o n i t sd i s t u r b a n c em o d e li ss i m i l a rt ot h ec a u c h y d i s t r i b u t i o n i t sc o o l i n gm o d e li s 丁( k ) = 瓦口t h en e wa l g o r i t h mc o n v e r g e n c er a t e i sf a s t e rt h a nt h eo l da l g o r i t h m g e n e r a ls i m u l a t e da n n e a l i n ga l g o r i t h mi sa l s ob a s e d o nt h eg e n e r a l i z e dg i b b sd i s t r i b u t i o n i t sd i s t u r b a n c em o d e li st s a l l i s - s t a r i o l o d i s t r i b u t i o n i ti sm o r ee f f e c t i v et h a nc l a s s i c a ls i m u l a t e da n n e a l i n ga l g o r i t h mw h e n t h e r ea r em u l t i o b j e c t i v ef u n c t i o na n dl o t so fl o c a lm i n i m u m c l a s s i c a ls i m u l a t e d a n n e a l i n ga l g o r i t h ma n df a s ts i m u l a t e da n n e a l i n ga l g o r i t h ma r eas p e c i a lc a s eo f g e n e r a ls i m u l a t e da n n e a l i n ga l g o r i t h m f o r c ed i r e c t e da n n e a l i n ga l g o r i t h mi sf o r c e d i r e c t e dr e l a x a t i o nm e t h o dc o m b i n e dw i t hs i m u l a t e da n n e a l i n gm e t h o d t h ec o r eo f f o r c ed i r e c t e dr e l a x a t i o nm e t h o di st h a tt h ec u r r e n tu n i te x c h a n g et ot h el o c a t i o n w h e r ei th a ss m a l l e s tf o r c e c o m b i n a t i o no fs i m u l a t e da n n e a l i n gm e t h o di st ou s e s i m u l a t e da n n e a l i n ga c c e p t a n c es t r a t e g yt od e t e r m i n ew h e t h e ro rn o tt oa c c e p tt h e s o l u t i o na f t e rs w a p a s c e n d i n gt e m p e r a t u r et e m p e r i n ga n n e a l i n ga l g o r i t h mc h a n g e s 武汉理工大学硕士学位论文 t h ec o o l i n gs t r a t e g y f i r s t l y ，i tu s e sl o wt e m p e r a t u r ea n n e a l i n g ，t h eo p t i m i z e ds o l u t i o n i sa st h ei n i t i a ls o l u t i o no ft h en e x ta n n e a l i n g t h e nt h ei n i t i a lt e m p e r a t u r eg r a d u a l i n c r e a s ea n d r e p e a t e da n n e a l i n g t h ee x p e r i m e n t a lr e s u l t so fl a r g e s c a l ec i r c u i tp l a c e m e n ts h o wt h a tf a s t s i m u l a t e da n n e a l i n ga l g o r i t h mc a nr u n1 9t i m e st h a nt h a to fv p rw h i l et h eq u a l i t y o fs o l u t i o nr e d u c e s4 g e n e r a ls i m u l a t e da n n e a l i n ga l g o r i t h mc a n r u n1 9t i m e st h a n t h a to fv p r ，w h i l et h eq u a l i t yo fs o l u t i o nr e d u c e s15 a n da s c e n d i n gt e m p e r a t u r e t e m p e r i n ga n n e a l i n ga l g o r i t h mr u n s3t i m e sf a s t e rw i t ht h es a m eq u a l i t yo fv p r t h e r e s u l to ff o r c ed i r e c t e d a n n e a l i n ga l g o r i t h m i st h es a m ea sv p r a s c e n d i n g t e m p e r a t u r et e m p e r i n ga n n e a l i n ga l g o r i t h mc a nr u n3t i m e st h a nt h a to fv p r ，w h i l e t h eq u a l i t yo fs o l u t i o nd o e s n tr e d u c e t h ea b o v ea l g o r i t h m sc a l ls p e e du pt h ef p g a p l a c e m e n t k e y w o r d ：p l a c e m e n t ；f p g 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 ；v p r i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名： 日期：学 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) 7 导师( 签名) 百旨日期 9 峰 武汉理工大学硕士学位论文 第1 章绪论 1 1 本文研究背景及其意义 自产生第一个集成电路以来，集成电路的集成度，特征尺寸都沿着著名的“摩 尔定律”所预测的那样突飞猛进的发展。据摩尔定律预测：单个芯片内所集成的 晶体管数量每1 8 个月翻一番，特征尺寸每2 3 年降为7 0 ，同时速度翻一番， 而单位成本减半。作为半导体产业最新技术代表的存储器和微处理器，也同样 沿着摩尔定律发展。电子学进入了一个崭新的时代，其特征是电子技术的应用 以空前规模和速度渗透到各行各业。各行业对自己专用集成电路( a p p l i c a t i o n s p e c i f i ci n t e r g r a t e dc i r c u i t s ，a s i c ) 的设计要求日趋迫切，现场可编程器件的广 泛应用，为各行业的电子系统设计工程师自行开发本行业专用的a s i c 提供了技 术和物质条件。集成电路技术正迅速向着更高集成度、更高速度、更高性能和 更高可靠性的方向发展。传统的电路设计手段和方法远远不能满足日益复杂的 设计要求，如图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 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 a t ea r r a yl o g 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 ) 等可 编程器件的基础上进一步发展的产物。应用电子设计自动化( 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 ) 工具对f p g a 编程可以立刻把一个通用的f p g a 芯片配置成 用户需要的硬件数字电路。与单片机系统开发相比，利用e d a 技术对f p g a 的 开发，通常是一种借助于软件方式的纯硬件开发，因而大大加快了电子产品的 研发周期，降低了研发成本，缩短了产品上市时间。f p g a 以其特有的特征得到 了非常广泛的推广和运用。f p g a 在过去的2 0 年内一直呈指数级的增长，在上 世纪8 0 年代中后期出现的首款f p g a ，x i l i n xx c 2 0 6 4 只有6 4 个l u t ( l o o ku p t a b l e ) ，而现在x i l i n xv i r t e x 一4 系列的l u t 数量已经超过2 0 万个，并且嵌入了 多种硬模块：存储器，d s p ，嵌入式处理器，高速i o 等。为了充分发挥这些高 武汉理工大学硕士学位论文 密度，高集成度的功能和弥补传统设计方法的设计能力的不足，针对f p g a 设 计的e d a 工具的开发就成为必然。随着电路规模的越来越大，电路设计所需的 编译仿真时间也越来越长，一般达数小时至数天，设计出快速有效的算法是e d a 工具的一个发展方向。布局布线是f p g a 芯片设计中最耗时的阶段，也对电路 性能有着关键影响。设计出更加快速、更小面积、时延少、低功耗的算法是学 术界研究的热点和趋势。这也是本论文的研究目标。 10 ，0 0 0 ，0 0 1 0 0 0 ，0 0 一电路复杂性- - 一设计能力 靠瓣麓瓣 薹 1 1 0 0 0 术 鐾 伽 k1 0 l - l - 一一伽，o o 。l 一 。 ：；：；：；：j：j：鬣。-。：_- 一：鬈鞣乏一一： 十年增加7 倍： 设 计 能 力 1 ，0 0 0 人 1 0 0 父 1 0 月 1 9 9 01 9 9 52 0 0 02 0 0 52 0 1 0 图1 1集成电路的发展和设计能力的差距 1 2 相关领域国内外研究现状 自从f p g a 问世以来，f p g a 布局研究一直是电子设计自动化研究的热点， 有很多大学、研究机构以及一些产品开发部门已经对此进行了相关研究。在工 业界，a l t e r a 与x i l n x 这两家大型f p g a 产商，有自己比较完善的布局算法， 而且在相应的软件开发工具i s e 和q u a r t e r s 中都已经得到了较好的应用， 但这些布局算法对外开放的比较少。 f p g a 布局是一个n p h a r d 问题，需要通过多次迭代才能找到一个相对较优 的布局方案。布局算法大致可分为两类：构造型算法和迭代型算法。构造型算 法是根据电路的结构按一定的布局策略可以直接得到布局结果，因此所需的时 间很短，对于同一策略的构造型划分算法，其最后得到结果基本保持稳定，但 其布局效果不佳是该算法最大的缺点。迭代型算法是首先有一个初始布局结果， 然后在在一个初始解的基础上不断优化，直到得到满意的结果。这类算法花费 的运行时间较长，但是能得到比较好的近似最优解。迭代型算法中比较典型的 2 武汉理工大学硕士学位论文 有基于划分的算法、模拟退火算法以及数学规划算法【1 】等。 基于划分的布局算法是自上而下的算法。这种算法是在一定的约束条件下， 把一个大的布局图划分成两个或者多个小的布局子集，把这些小的布局实例分 配n d , 的布局区域中。然后再对各个区域单独进行划分，直到达到每一个的区 域都小于一个阈值。划分算法可以分为二划分算法和多划分算法，其中二划分 算法是多划分算法的基础。著名的划分算法有k e r n i g h a l l l i n 算法，f m 算法和 h m e t i s 算法 2 , 3 1 。 k l 算法是一种迭代改善的二划分法，它通过在不同区域定点的交换来实现 划分的最小割，具有以下特征： ( 1 ) 划分的两个子区域包含相同数量的顶点； ( 2 ) 每次选择收益最大的顶点对进行交换，并且交换后固定这两个交换的 顶点，也就是说这个顶点对不再参与以后的交换。 ( 3 ) 允许接受一定的收益为负的交换，这使得k l 算法具有一定的爬坡能力。 k l 算法最大的特色就是采用顶点对交换和允许爬坡，当然，它要求划分的 两部分规模相同，会在运用的过程中有很大的局限性，后期逐渐产生了一些非 平衡k l 算法。 与k l 算法类似，f m 算法也是一种二划分的方法，其算法流程如下： ( 1 ) 产生一个平衡的划分； ( 2 ) 重复：从整个划分区域中活动的点中，选择移动到对方区域能够获得 最大收益的点，移动到对方区域，并记录这次的收益和固定该点；在移动的过 程中尽量保持两个区域的平衡。 ( 3 ) 以所有移动中某次以及它以前各次得到的收益总和最大的结果为最后 的划分结果。 f m 算法以顶点移动为基础，尽可能的使每次移动能够获得最大的收益，它 不需要一直维持两个划分区域的平衡，从而可以处理非平衡的点路，其运行时 间是线性的，因此f m 算法对于大电路来说比较适用，f m 算法得到的结果还有 很大的改进空间。 模拟退火算法s a 越来越广泛的运用于布局算法中，t i m e rw o l f 就是其中的 代表，著名的v p r ( v e r s a t i l ep l a c ea n dr o u t e ) 也是基于模拟退火算法布局【4 】o 模拟退火算法s a 由m e t r o p o l i s 等人- z 1 9 5 3 年提出【5 ，6 】，它结合交换技术实现从 一个可行解到另外一个可行解。模拟退火布局算法的核心是交换，通过交换来 武汉理工大学硕士学位论文 实现解的更新和优化。因为模拟退火算法在一定概率上接受较差解，并且温度 越高，其接受差解的可能性就越大，使其具有了一定的爬坡能力，可以在解空 间内跳出局部最优解而具有更大可能找到全局最优解，因而具有比较高的稳定 性和鲁棒性。由于模拟退火算法的速度非常慢，随着集成电路规模的急剧上升， 模拟退火算法越来越不能满足大规模电路的布局要求，但是通过和其他算法组 合使用，从而可以达到运行时间少，并且同时获得近似最优解的目标，例如： d r a g o n 2 0 0 0 ，p p f f 等等。 数学规划求解布局问题的算法最大的特点是能够基于严格的数学分析证明 求解质量。数学规划的方法多是基于二次线长模型，二次规划的布局方法首先 定义了一个凸规划，然后解这个凸规划问题就可以得到全局最优解。目标函数 是二次线长的加权和【3 】： = 萎莓( ( t z ，) 2 + ( 乃一y ，) 2 ) ( 1 1 ) 其中：( t ，只) 代表单元m 的坐标，心表示单元f 、歹之间的连接权重。将上 式改写成矩阵： 毗力弓地+ 弓内+ ( 1 - 2 ) 在二次规划的布局方法中，影响布局速度的最重要因素是二次规划问题的 求解方法，一般采用拉格朗日乘子方法进行求解。二次规划的布局算法不依赖 于初始解，能并行求出所有单元位置，求解速度快，尤其适用于处理问题规模 大、单元相对小的标准单元布局。因此数学规划算法广泛运用于全局优化和划 分如：c a s h 、v e a p 等等。 1 3 本文主要工作及内容安排 本文的研究目标是改变v p r 中的布局算法，提高v p r 的布局性能，如减少 线长，减少电路最大延时，提高算法运行效率。论文主要包括如下三个方面： ( 1 ) 介绍f p g a 的内部结构，f p g a 的c a d 设计流程，研究了v p r 的布局算 法，布局细节，介绍模拟退火算法。 ( 2 ) 提出几种新的用于f p g a 布局的算法，分析理论模型与在v p r 布局平 台上的实际应用模型。 ( 3 ) 实验测试。代码实现各种算法，用2 0 个m c n c 电路做实验与v p r 的实 4 武汉理工大学硕士学位论文 验结果比较。实验证明推广型模拟退火算法和渐升温回火退火算法对软件运行 效率有显著的提高。 本文内容安排如下： 第一章介绍了课题研究的背景和选题意义，国内外的研究现状及本文研究 的主要内容。 第二章介绍了f p g a 的内部逻辑单元结构，布线结构，可编程开关结构和 f p g a 设计流程。 第三章对本论文的实验平台v p r 做了详细的研究并介绍了v p r 中用到的模 拟退火算法。 第四章分别用非常快速的模拟退火算法、推广型模拟退火算法、力矢量退 火算法、渐升温回火退火算法改进v p r 中的布局算法，做实验验证效果，分析 原因。 第五章对全文进行了总结，并对进一步的研究工作进行了展望。 5 武汉理工大学硕士学位论文 第2 章f p g a 结构与设计流程 f p g a 芯片在现代数字电路设计中发挥着越来越重要的作用。从设计简单的 接口电路到设计复杂的状态机，甚至设计“s y s t e mo nc h i p ( 片上系统) ”，f p g a 芯 片所扮演的角色已经不容忽视。f p g a 已经历了二十几年的发展历史。在这二十 几年的发展过程中，以f p g a 为代表的数字系统现场集成技术取得了惊人的发 展，纵观现场可编程逻辑器件的发展历史，其之所以有巨大的市场吸引力，根 本在于：f p g a 不但可以解决电子系统小型化、低功耗、高可靠性等问题，而且 它的开发周期短、开发软件投入少、芯片价格不断降低，促使f p g a 越来越多 地取代了a s i c 的市场，特别是对小批量、多品种的产品需求，使f p g a 成为首 选。 2 1f p g a 结构 f p g a 的核心部分通常由逻辑单元阵列及布线资源两部分组成。逻辑单元 可以被配置成组合或者时序逻辑，不同逻辑单元间的输入输出端口通过布线资 源进行连通，从而实现一个完整的电路设计。图2 1 是一个最常见的岛型f p g a 结构示意图 7 1 。图中间的黑色正方形表示可配置逻辑单元( c o n f i g u r a b l el o g i c b l o c k ，c l b ) 。各条直线组成布线资源，用于实现各个逻辑单元输入输出端口 之间的互连。线之间由可编程开关矩阵连接。f p g a 还包含有可编程i o 资源， 可编程i o 资源围绕在f p g a 核心周围并与芯片的p a d 相连。可编程i o 单元 可以被配置成输入端口或者输出端口，负责f p g a 核心与芯片引脚之间的数据 交换。 6 武汉理工大学硕士学位论文 2 1 1 逻辑单元 图2 1f p g a 结构示意图 逻辑单元可以被配置实现一些规模不大的组合或时序逻辑。因此，逻辑单 元内部可以大致分为可配置组合逻辑及可配置时序逻辑两部分。在逻辑单元的 输入端、输出端、组合逻辑及时序逻辑部分之间通常还有一些简单的可配置连 线资源用于这几部分之间信号的选通。如今f p g a 中的逻辑块种类非常多，但 大多数商业f p g a 都使用基于l u t 的逻辑块。一个k 输入的l u t 需要2 ks r a m 单元和一个2 k 输入的多路选择器，它能实现k 输入的任何功能，只要将2 ks r a m 单元按照需要功能的真值表进行设置就可以了。 大多数商业f p g a 是基于4 输入查找表的。多数现代的f p g a 都不是由单 一查找表组成，而是由一组或多组查找表和寄存器及它们之间的互连线组成的。 逻辑单元中的可配置时序逻辑部分通常由若干个d 触发器组成。逻辑单元 的输入或者是组合逻辑部分的输出可以通过逻辑单元内部的布线开关送到触发 器的输入端。而触发器的输出也可以通过布线开关送到逻辑单元的输出或者反 馈给组合逻辑部分的输入。为了提高f p g a 芯片的性能，现在很多f p g a 芯片 在逻辑单元内还加入了一些专用的电路模块如快速进位链、存储器单元等。 7 武汉理工大学硕士学位论文 2 1 2 布线资源 布线资源分为水平通用连线、垂直通用连线、水平长线、垂直长线、全局 连线等几种。这些互连线经可编程的连接点与c l b 、i o 和开关矩阵相连。其中 的通用连线主要用于c l b 之间的连接，长线主要用于长距离或多分支信号的传 送，全局连线则用于输送一些公共信号( 如公用的r e s e t 信号) 等。 ( 1 ) 通用单长度长线 单长度长线提供最大的互连灵活性和相邻功能块之间的快速布线，这些线 用于连接位于c l b 每行和每列中的开关矩阵，单长度长线是用可编程开关矩阵 ( s w i t c hb l o c k ，s m ) 的方式连接的。单长度长线每当它们通过开关矩阵总要传 输一个延时，所以它们不适合为长距离的信号布线，它们通常用于在局部区域 内引导信号，为扇出大于一个的网线提供分支。 ( 2 ) 通用双长度长线 双长度长线为单长度长线的两倍，在进入一个开关矩阵之前穿行两个c l b 。 双长度长线是与开关矩阵交错成对分组，以使每根线在c l b 的另一行或列通过 开关矩阵。双长度长线是由可编程开关矩阵连接的。 ( 3 ) 水平垂直长线 在通用单双长度长线的旁边还有从阵列的一头连到另一头的线段，称之水 平长线和垂直长线。这些长线不经过可编程开关矩阵，信号延迟时间小，长线 主要用于长距离或多分支信号的传送。 ( 4 ) 全局网线和缓冲器 全局连线主要用于传送一些公共信号，如全局时钟信号、公用控制信号。 全局网线可以由两类全局缓冲器：主要的全局缓冲器和次要的全局缓冲器来驱 动，在器件的每个角有一个主要的全局缓冲器和一个次要的全局缓冲器。 2 1 3 可编程开关矩阵 水平和垂直的单或双长线交叉在称为s m 的方阵中。每个s m 由可编程传输 晶体管组成，用来建立线之间的连接例如，在开关矩阵右边进入的单长度信号 可以布线到上部、左边或下部的单长度线，如果要求多个分支时可以按其组合。 类似地，双长度信号可以布线到可编程开关矩阵其他三边的任何一边或所有边。 为了充分利用已有的逻辑单元，互连网络必须灵活并且必须避免布线瓶颈。 速度要求则是另一个前提，因为互连延时往往决定了这类设计的性能。同时应 8 武汉理工大学硕士学位论文 当了解到，可编程互连的代价是明显损失了性能，包括面积、速度和功耗损失。 在现场可编程结构中的大部分功耗是由互连网络引起的。 2 2f p g a 设计流程 f p g a 设计流程分为设计输入、综合、功能仿真( 前仿真) 、实现、时序仿 真( 后仿真) 、配置下载等六个步骤，设计流程如图2 2 所示。下面分别介绍各 个设计步骤。 ( 1 ) 设计输入 设计输入包括使用硬件描述语言h d l 、状态图与原理图输入三种方式。h d l 设计方式是现今设计大规模数字集成电路的良好形式，除i e e e 标准中v h d l 与v e r i l o gh d l 两种形式外，尚有各自f p g a 厂家推出的专用语言，如q u a r t - u s 下的a h d l 。 ( 2 ) 设计综合 综合，就是针对给定的电路实现功能和实现此电路的约束条件，如速度、 功耗、成本及电路类型等，通过计算机进行优化处理，获得一个能满足上述要 求的电路设计方案。也就是说，被综合的文件是h d l 文件( 或相应文件等) ， 综合的依据是逻辑设计的描述和各种约束条件，综合的结果则是一个硬件电路 的实现方案，该方案必须同时满足预期的功能和约束条件。对于综合来说，满 足要求的方案可能有多个，综合器将产生一个最优的或接近最优的结果。因此， 综合的过程也就是设计目标的优化过程，最后获得的结构与综合器的工作性能 有关。 9 武汉理工大学硕士学位论文 i 必要的修改设计输入必要的修改 l jl 1r 1r i 功能仿真设计综合 i 7 “ 1 r 设计实现 土 1r1 r i 位流文件 报告文件仿真网表 iii l 配置器件 时序分析时序仿真 l 图2 2f p g a 设计流程图 ( 3 ) 仿真验证 从广义上讲，设计验证包括功能与时序仿真和电路验证。仿真是指使用设 计软件包对已实现的设计进行完整测试，模拟实际物理环境下的工作情况。前 仿真是指仅对逻辑功能进行测试模拟，以了解其实现的功能否满足原设计的要 求，仿真过程没有加入时序信息，不涉及具体器件的硬件特性，如延时特性； 而在布局布线后，提取有关的器件延迟、连线延时等时序参数，并在此基础上 进行的仿真称为后仿真，它是接近真实器件运行的仿真。 ( 4 ) 设计实现 实现可理解为利用实现工具把逻辑映射到目标器件结构的资源中，决定逻 辑的最佳布局，选择逻辑与输入输出功能连接的布线通道进行连线，并产生相 应文件( 如配置文件与相关报告) 。通常可分为如下五个步骤。 转换：将多个设计文件进行转换并合并到一个设计库文件中。 映射：将网表中逻辑门映射成物理元素，即把逻辑设计分割到构成可编 程逻辑阵列内的可配置逻辑块与输入输出块及其它资源中的过程。它是在芯片 数据库( ( d e v i c ed a t a b a s e ) 上进行的，而这个芯片数据库提供了f p g a 芯片的 所有细节。 1 0 武汉理工大学硕士学位论文 布局与布线：布局是指从映射取出定义的逻辑和输入输出块，并把它们 分配到f p g a 内部的物理位置；布线是指利用自动布线软件使用布线资源选择 路径试着完成所有的逻辑连接。最新的设计实现工具是时序驱动的，即在器件 的布局布线期间对整个信号通道执行时序分析，因此可以使用约束条件操作布 线软件，完成设计规定的性能要求。在布局布线过程中，可同时提取时序信息 形成报告。 时序提取：产生一反标文件，供给后续的时序仿真使用。 配置：产生f p g a 配置时的需要的位流文件。 ( 5 ) 时序分析 在设计实现过程中，在映射后需要对一个设计的实际功能块的延时和估计 的布线延时进行时序分析；而在布局布线后，也要对实际布局布线的功能块延 时和实际布线延时进行静态时序分析。从某种程序来讲，静态时序分析可以说 是整个f p g a 设计中最重要的步骤，它允许设计者详尽地分析所有关键路径并 得出一个有次序的报告，而且报告中含有其它调试信息，比如每个网络节点的 扇出或容性负载等。与综合过程相似，静态时序分析也是一个重复的过程，它 与布局布线步骤紧密相连，这个操作通常要进行多次直到时序约束得到很好的 满足。 ( 6 ) 下载验证 下载是在功能仿真与时序仿真正确的前提下，将综合后形成的位流下载到 具体的f p g a 芯片中，也叫芯片配置。将位流文件下载到f p g a 器件内部后进 行实际器件的物理测试即为电路验证，当验证结果正确就证明了设计的正确性。 武汉理工大学硕士学位论文 第3 章v p r 中的布局算法研究 本研究所使用的仿真平台v p r 是v a u g h nb e t z 等人开发的可广泛用于f p g a 架构研究的布局布线工具，适用于仿真很多不同架构的f p g a ，现在关于f p g a 布局布线的学术研究基本都是基于这个仿真平台进行的。v p r 所用的布局算法 基于模拟退火算法，本章详细介绍了v p r 实验平台，然后介绍了模拟退火算法 的算法思想，物理退火过程，算法应用模型。 3 1v p r 介绍 v p r 是国际上权威的布局布线工具，也是本文的主要研究基础。图3 1 给出 了v p r 在c a d 流程中的位置【8 】。它的输入是逻辑块网表文件和描述f p g a 结构 的文件。v p r 布局布线结束后可以反馈出电路在某种特定结构f p g a 中的关键 路径延时和布线资源通道数。v p r 的布局器能够实现电路布局或者仅读取己经 布局完成的方案，然后进入布线环节；布线器可以完成全局布线( g l o b a lr o u t i n g ) 或者全局细节布线( g l o b a ld e t m lr o u t i n g ) 。布局布线过程完成后，v p r 会输出相 应的布局、布线结果和中间过程产生的统计文件，这些统计文件中包含的信息 包括总布线长度、网线数量以及最大网线长度等。 v p r 实现f p g a 布局布线分为两个阶段，先实现f p g a 布局，布局成功后 再进行布线操作。在布局实现过程中会充分考虑到布线阶段的优化目标，会对 不利于布线的c l b 进行调整。在该过程中，c l b 的端口被抽象为节点( n o d e ) ， 相互之间的连接被定义为边( e d g e ) ，这样就抽象为一个有向图。在实现过程中， v p r 设定了一定的优化目标，用户可以依据自己的要求来优化f p g a 系统，其 中有减小互连模块的连线长度，即连线长度驱动布局( w i r el e n g t hd r i v e n p l a c e m e n t ) ；或者使电路速度最大化，时序驱动布局( t i m i n gd r i v e np l a c e m e n t ) ， 实际上往往是这两个优化目标的综合【9 】。 v p r 的布局算法是典型的双循环的模拟退火算法；它借鉴了学术界研究的 成果，从实用角度出发，最终开发出一个适合于f p g a 的模拟退火布局算法， 并在学术界广泛应用，对f p g a 理论研究有着深刻的影响【l0 1 。 1 2 武汉理工大学硕士学位论文 逻辑块 参数 电路 逻辑优化( s i s ) 工艺映射到l u t ( f l o w m a p ) u 兀和触发器组成 的。b l i f 格式豹网袭 将f f 和l u t 聚合形成逻辑块( t - v p a e k ) 逻辑块组成的n e t 格式的网表 v p r t 布局电路或者溪入一个存在的布局 执行全局布线或者全局+ 局部布线 布局布线文件 布玛在线晌出统计 图3 1v p r 的c a d 实现 ，一- 、 f ，存在的、 、 在局 ， 、l i m i t ， v p r 的布局算法如以下： s = r a n d o m p l a c e m e n to ； t = i n i t i a l t e m p e r a t u r eo ； r l i m i t = i n i t i a l r l i m i to ； c r i t i c a l i t y _ e x p o n e n t = c o m p u t e n e w e x p o n e n t 0 ； c o m p u t e d e l a y m a t r i x 0 ； w h i l e ( e x i t c r i t e r i o n0 一f a l s e ) 严“o u t e rl o o p ”木 t i m i n g a n a l y z e 0 ；| 却p e r f o r mat i m i n g a n a l y s i sa n du p d a t ee a c hc o n n e c t i o n s c r i t i c a l i t y | 1 3 武汉理工大学硕士学位论文 p r e v i o u s _ w i r i n g _ c o s t = w i r i n g _ c o s t ( s ) ； w i r e l e n g t hm i n i m i z a t i o n n o r m a l i z a t i o nt e r m 卑| p r e v i o u s j i m i n g _ c o s t = t i m i n g _ c o s t ( s ) ；乖d e l a ym i n i m i z a t i o nn o r m a l i z a t i o n t e r m w h i l e ( i n n e r l o o p c r i t e r i o n0 一f a l s e ) i n n e rl o o p ”事 s n e w = g e n e r a t e v i a m o v e ( s ，r l i m i o ； a t i m i n g _ c o s t = t i m i n g _ c o s t ( s n e w ) - t i m i n g _ c o s t ( s ) ； a w i r i n g _ c o s t = w i r i n g _ c o s t ( s n e w ) - w i r i n g _ c o s t ( s ) ； c = 名( at i m i n g _ c o s t p r e v _ _ t i m