（电路与系统专业论文）fpga低功耗布局布线算法的研究与改进.pdfVIP

f p g a 低功耗布局布线算法的研究和改进 摘要 髓着f p g a 技术的发展，毒髑布线资源遇常会占总资源豹6 0 以上。同时便 携式电子设备的骛及对系统的功耗和蘑积掇融了更高要求，嚣改进f p g a 静架梅 和布局布线算法将会优化系统的整体性能。 本文主要研究了嵌入硬核的f p g a 布线邋道宽度分强弱改进f p g a 布局算 法。在嵌入硬核簸f p g a 布线遁道宽度分布研究中，我 f j 孳l 入了匿释絮梅，箕布 线通道宽度分布函数分别为均匀、脉冲、商斯和三角分布。通过修改v p r 工具 的源代码，傻平螽适用于具有嵌入硬核豹f p g a 架构，剩舞lm c n c 蒸准电路来 测试这西种架构的性能。实验络栗表明：程戳两线平均长度作为指标的溺试中， 通邋宽度均匀分布的架构具有爨短的布线长度、更优的性能。 惩改进寿届冀演的研究孛，我嚣j 裂用在麟决t s p 阔题中其有较高搜糍的蚁群 算法来解决布局随篷。模撤逐火算法是现在普遍运用的帮简算法，僵萁套找过程 是随机的，只是利用一个判决函数来决定系统的走势，对c l b 的选择没有优劣 之分，导致其套找辩闯过长。蚁群算法是摸羧壹然赛中蝎蚁匏特性，把信息素 筝 为螨蚁之间交换倍怠的载体，利用目标函数来加强能缩短总体代价的路径上的信 息豢。随着时间的推移，越来越多能够提升系统性能的路径聚合到一越，从而在 会瀵鞋趣内找瑟霹双接受静较谯解。实验缝浆表明：矮致鼗算法替代遐火算法豹 实糯牛，在没有完全优化参数的前提下，系统性能基本和原先一致。 关键字：f p g a ，嫒孩，毒线邋遥，毂群冀法，毒羁 f p g a 低功耗布局布线算法的研究和改进 a b s t r a c t w i t hf p g a s d e v e l o p m e n t ，p l a c e m e n ta n dr o u t i n gt a k e sm o r et h a n6 0 * 0o fa l l r e s o u r c e s a t t h es a m et i m e ，c e l l u l a rd e v i c e sm a k eh i g h e rr e q u i r e m e n tt ot h es y s t e m s a r e aa n dp o w e rc o n s u m p t i o n i tw i l li m p r o v ef p g a s p e r f o r m a n c eb ym a k eb c l t e r a r c h i t e c t u r ea n dp l a c e m e n ta n dr o u t ea l g o r i t h m i nt h i sp a p e r , w em a i n l yr e s e a r c ht w oa s p e c t s ，f p g a s r o u t i n gt r a c kd i s t r i b u t i o n si n h e t e r o g e n e o u sf p g aa r c h i t e c t u r e w i t he m b e d d e dh a r dm a c r oa n dp l a c e m e n t a l g o r i t h mm o d i f i c a t i o n ，f o u ra r c l i i t e c t u r e s ，w h o s er o u t i n gc h a n n e lw i d t hd i s t r i b u t i o n f u n c t i o n sa r eu n i f o r m ，g a n s s i a n , p u l s ea n dd e l t a , a r ei n v e s t i g a t e d t h es o u r c ec o d e w a s u p d a t e d t om a k ev p rs u i t a b l ef o rf p g aw i t hh a r dm a c r oa r c h i t e c t u r e ，a n dt h e na s e to fm c n cb e n c h m a r kc i r c u i t sw e r eu s e dt ot e s tf o u ra r c h i t e c t u r e s a r e a - e f f i c i e n t t h ee x p e r i m e n tr e s u l t , w h o s eo b j e c t i v ei sa v e r a g ew i r el e n g t h , s h o w st h a t , c o m p a r e d w i t ho t h e r s ，u n i f o r mr o u t i n gt r a c kd i s t r i b u t i o na r c h i t e c t u r eh a st h em o s to u t s t a n d i n g p e r f o r m a n c e i ni m p r o v i n gp l a c e ra l g o f i t h r a ，w ei m p l e m e n t e da n tc o l o n yo p t i m i z a t i o n ( a c o ) a l g o r i t h m , w h o s ep e r f o r m a n c ei sq u i t eg o o d i ns o l v i n gt s pp r o b l e m ，i nf p g a p l a c e m e n 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 mi sw i d e l yu s e di nf p g ap l a c e rn o w a d a y s ， b u ti t ss e a r c h i n gp r o c e s si st o t a l l yr a n d o m i to n l yu s e sa no b j e c t i v ef u n c t i o nt od e c i d e w h e t h e rt h ec l bs e l e c t i o ni sa c c e p t a b l eo rn o t ，a n dh a sn oi m p a c to nc h o o s i n gc l b p r o c e s s ，w h i c hm a k e s t h e s e a r c h i n gt i m e w a s t i n g a c om i m i c sn a t u r a la n t s b e h a v i o r a l ，u s i n gp h e r o m o n ef o re x c h a n g i n gi n f o r m a t i o nb e t w e e na n t s i te n h a n c e s t h ep h e r o m o n eo nt h et r a i l ，w h i c hc a ns h o r t e nt h ew h o l es y s t e m sc o s t , b ya n o b j e c t i v ef i m c t i o mm o r ea n dm o r et r a i l st h a tc a ni m p r o v es y s t e m sp e r f o r m a n c e i n v o l v e di nt h eb e s ts o l u t i o nw i t ht i m eg o i n g ，a n df i n a l l yf i n dag o o ds o l u t i o ni na r e a s o n a b l et i m e t h er e s u l ts h o w st h a tt h es y s t e m sp e r f o r m a n c eu s i n ga c o ，w i t h o u t o p t i m i z i n gi t sp a r a m e t e r sc a r e f u l l y , h a sa l m o s ta sb e t t e ra st h eo n eu s i n g s a k e yw o r d s ：f p g a ，h a r dc o r e ，r o u t i n gc h a n n e l ，a c o ，p l a c e m e n t i i f p g a 低功耗布局布线算法的研究和改进 引言 f p g a 由于其可重复利用性、能迅速进入市场等特点，在数字电路设计中得 到了广泛的应用。相比专用集成电路a s i c ，由于f p g a 使用可编程开关，比导 线有更大的电阻和连接电容，从而增加了电路的面积，降低了速度，并且具有更 大功耗。随着个人移动通信和其他数字应用的迅速发展，速度、面积和功耗已经 成为非常重要的设计指标。 为了充分发挥a s i c 和f p g a 的优势，具有嵌入硬核的非对称f p g a 架构就 应运而生，x i l i n x 公司推出的v i r t e x 系列的f p g a 芯片就是具有嵌入i b mp p c c p u 硬核的芯片。在对称f p g a 架构中，v b e t z 和j r o s e 证明了沟道宽度均匀 分布的架构较非均匀分布具有更有性能，那么在非对称中这个结论是否仍然成 立? 很多电路设计者认为由于在内部嵌入了硬核，势必导致硬核周围的布线资源 紧张，增加硬核四周沟道的布线宽度，可以提高系统的布线效率。但我们通过修 改v p r 这个仿真工具，利用实验数据说明：沟道宽度均匀分布的架构具有最佳 性能。 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 是传统的布局算法，但s a 完全是一 个随机选择的过程，而且前后两次调整之间没有信息的共享，导致布局过程收敛 较慢。随着电路规模不断扩大，仿真时间也随之增加，有时一个电路的仿真时间 可以达到几天之久，仅依靠服务器性能的提升来缩短仿真时间是不现实的，因而 寻找新的布局布线算法成为当前研究的热点。蚁群算法( a n t sc o l o n yo p t i m i z a t i o n , a c o ) 是一种依靠蚂蚁之间信息素的交换来寻找最优解的正反馈优化算法，它在 旅行商问题t s p ( t r a v e l m a ns a l e sp r o b l e m ，t s p ) q b 得到了很好的应用，证明了它 在解决n 7 h a r d 问题中的优势。而f p g a 的布局算法就是一个n p h a r d 问题， 那么我们是否可以利用a c o 来实现布局问题? 我们通过研究v p r 工具内部的算 法，用a c o 蚁群算法来替代s a ，实验结果表明布局性能可以达到s a 的效果。 由于a c o 对参数非常敏感，调整a c o 的参数可以进一步提高布局性能，但由 于它是一个崭新的领域，还有很多工作需要完成。 本文的组织结构如下：第一章主要介绍了f p g a 及其布局算法的现状发展趋 f f g a 低功耗布局布线算法的研究和改进 势；第二章说明了f p g a 的基本结构、布局布线算法和f p g ac a d 设计流程； 接着下一章介绍了我们实验中所用到的仿真平台，包括v p r 软件的原理、安装 和使用，t - v p a c k 软件介绍以及用来测试系统性能的m c n c ( m i c r o e l e c t r o n i c s c e n t e ro f n o r t hc a r o l i n a ) 电路；第四章阐述了在嵌入硬核的f p g a 中沟道宽度分 布函数对面积效率性能的影响，包含了原理介绍、代码修改和试验数据分析等； 第五章是本文的重点，着重介绍了a c o 算法在f p g a 布局中的实现，从原理、 实现和横向比较等方面说明问题；最后一章回顾了本文的主要工作和以后需要完 成的任务。 f p g a 低功耗布局布线算法的研究和改进 第一章绪论 1 1 f p g a 的发展现状及趋势 f p g a ( f i e l d p r o g r a m m a b l e g a t e 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 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 ) 等可编程器件的基础上进一步发 展的产物。它是作为专用集成电路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 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 o a 来开发数字电路，可 以大大缩短设计时间，减少p c b 电路面积，提高系统的可行性和稳定性。自1 9 8 5 年x i l i n x 公司推出第一片f p g a 芯片x c 2 0 0 0 已有2 0 多年的时间，在这2 0 多年 中，f p g a 技术取得了惊人的发展，f p g a 从最初的1 2 0 0 个可利用门，到现在 数百万门的单片f p g a ，以致不同的硬件算法可以在同一块芯片上实现【“，很多 系统具有自恢复、自组织和自适应的功能b3 1 。由于f p g a 具有开发周期短、开 发软件投入少、芯片价格不断降低等优点，促使f p g a 越来越多地取代a s i c 市 场，特别针对小批量、多品种的产品需求，f p g a 已成为首选；基于传统的隶属 于a s i c 范畴的c p u 上的软件开发都是串行的，即使所谓的多线程程序从本质 上讲也是在串行执行的，同时线程之间的相互通讯和同步会耗费大量的系统资 源，导致在大规模的多媒体处理时越发显得资源非常紧张，而f p g a 是一个真正 意义上的并行设备，设计者可以同时实现许多并行功能，任务之间并不需要相互 协调的开销，能够胜任很多实时系统的严格要求；在v l s i 设计仿真和验证阶段， 必然会多次修改电路和系统查错，利用f p g a 等可编程器件进行设计验证成为必 然选择。基于以上几点，很多专家都认为：在不久的将来，f p g a 将全面取代 a s i c ，当然这还需要时间来证明。 f p g a 低功耗布局布线算法的研究和改进 与a s i c 相比，相同的电路实现在f p g a 会占用更多的面积、更低的性能和 更高的功耗。文献 川中说明了同样的电路用f p g a 所需面积是a s i c 的1 0 0 倍， 而速度下降l o 倍。因此，为了更好地适应市场的需求，f p g a 必然会有如下发 展趋势【5 】： 1 ) 向高密度、高速度、宽频带发展。这将减小f p g a 芯片的面积，提高性 能，为f p o a 适合更多的产品开发打下基础。 2 ) 向低成本、低价格发展。现阶段f p g a 在大批量产品方面缺点明显，降 低f p g a 的成本和价格会进一步扩大市场。 3 ) 向低电压、低功耗和绿色化方向发展。数字设备产品的不断发展，特别 是便携式设备对产品的f p g a 低功耗要求日益迫切。 4 ) 片上可编程系统( s y s t e mo np r o g r a m m a b l ec h i p ，s o p c ) 的发展。越来越多 的复杂i c 需要利用s o p c 技术来制造，而且必须具备快速投放市场、具 有可重构性、高效自动化的设计等优点，f p g a 中嵌入硬核，包括r a m ， c p u 和乘法器等会成为发展趋势。 5 ) 适合f p g a 实现的i p 软核的进一步流行。f p g a 系统规模的扩大，导致 单独完成从底层到上层的设计几乎不可能，利用现有的i p 开发系统必然 成为重点发展的方向。 6 ) f p g a 动态可重构技术。超大规模的数字时序系统芯片在其工作时，从时 间轴上来看，并不是每一瞬间系统的各个部分都在工作，而系统是各个 局部模块功能在时间链上的总成。对某些模块的分时复用成为研究热点。 1 2 f p g a 的布局算法发展现状 随着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 , e d a ) 已成为 集成电路设计和研制不可缺少的重要支柱。作为集成电路设计中与产品研制和生 产直接相关的重要一环，布局设计自动化理论、方法与实际应用也得到了相当快 的发展。简单地说，f p g a 的布局问题是依据一定的优化规则和目标将网表 ( n e t l i s t ) 文件描述的电路元素，包括i o ，逻辑块( b l o c k ) 和相互连接等，映射到 f p g a 芯片内部物理位置的过程。逻辑块是实现功能的主要元素，它被下载到 4 f p g a 低功耗布局布线算法的研究和改进 f p g a 的可配置逻辑单元( c o n f i g u r a b l el o g i cb l o c k , c l 8 ) 中，通过控制相互间的 连线实现整个系统的功能。布局算法必须满足约束和代价函数最小化两者的要 求，典型布局约束有：按用户的要求锁定某些i o 功能块，调整一条长线属于相 同总线的三态缓冲器，总的互连连线长度最小化，总的可编程元件数目最小化， 减少拥挤保证布通率，横跨芯片不同区域的连线最小化等。这些约束的目的是提 供合理的布局方案，保证接下来的布线过程可以顺利完成。现有的布局过程是分 两个阶段进行的：首先是粗略的和快速的基于极小截的布局，然后是基于模拟退 火的细节布局。 分析布局过程可知，f p g a 布局算法是一个n p h a r d 6 , 7 1 问题。随着电路规模 的不断扩大，系统仿真时间会呈现几何级数增加。在布局实现中，布局器将依据 一些预先设定的目标不断调整功能子模块对应的c l b 位置，直至找到一个比较 合理的布局方案。现阶段，商用和实验研究工具都是以模拟退火算法s a 作为主 要算法实现【8 】。由极小截获得的布局利用横跨分割的连线数目作为结群元件的度 量。为了改善布局需要一个更好的度量，如总的连线长度。改善中利用的是成对 交换策略，并用模拟退火算法完成对交换后的结果的选择和接受。该算法的有效 性很大程度上取决于选择交换的元件和代价函数，算法中并不需要对所有的元件 进行交换运算和比较。s a 是考虑到最小代价方案的过程可能不是单调减少的算 法。对于布局而言，它是把寻找组合最优问题的可行方案作为固体在高温下熔化 状态到结晶的过程，代价函数最小化对应于冷却熔化固体时的总能量最小化。由 于s a 算法利用的是随机交换c l b 位置，用一个判决条件来决定某次调整是否 被接受，而不会对调整c l b 的具体过程产生任何影响，任何两次的调整过程都 是独立的，没有前后信息的互相利用，导致其收敛速度较慢，达到全局最优解的 概率也较低。随着f p g a 规模的扩大，布局过程所占用的时间也日益增加，对于 某些电路，其布局布线过程可能耗费几天之久。而且在f p g a 设计过程中，系统 需要大量改进，每次改动都需要重新进行布局布线，导致系统设计花费在布局布 线的时间不断加大，严重影响了产品对市场的响应速度。实际上，如果给定无限 时间和空间，f p g a 布局问题一定可以找到一个全局最优解，采用高性能的服务 器来运行布局布线软件能从一定程度上缩短仿真时间，但布局花费时间的增加速 度远远大于服务器性能的增加速度；另外，现阶段f p g a 实现中，布线资源会占 f p o a 低功耗糍局布线算法的研究釉渡进 用总资源的6 0 以上 9 1 ，由宦所产生的时延、面积和功耗越来越成为关注的黧点， 如何调整帮优纯布岗布线方法，对簸终系统的整体憔能其有极其重溪的影桶，国 内外很多文献介绍了如何降低布线甄积的方法，包括从逻辑块1 9 1 、存储块【伸l 寝布 线结构队1 2 】等方面来改善性能。 模拟邋火算法擞然具有很强弱全局寻钱戆力，馁是其爽在魏串纷纯特瞧，使 之不适合处理大规模并行化问题，也就导致了f p g a 布局消耗了大擞时间，寻找 一耱旋够实现劳行处理豹冀法也残凳突破方囱】；铸绫夔套嚣毒线簿法足警豢不 考虑功耗因数，大部分都是以面积和时延作为主要优化目标，随着数字系统。特 鬟楚便携式设备豹快速发鼹，系统的复杂魔不薮篪离，导致系统葫耗急鞠上舞， 功耗的上升，必然会导致系统温度的提高；对于某然系统，必须放鼹散热设备方 能保证系统正常工作。为了提高系统的稳定性和降低能源消耗，市场对于功耗提 出丁越来越赢的要求，由予短时问沟扶电源上寻求闽题的孵决方案弗不现实，两 且也不是一种绿色的解决方法，因而从芯片设计内部找原因成为一种必然选择： 由母f p g a 是隽熬特性，改送毒局凑线懿秀案，降低在蠹部元素提嚣连接懿连线 上的功耗和面积成为研究的重点，也就导致了寻找种新的高性能布局布线算法 残为熬煮。 1 3 内容和要求 本磅究凝要实现静内容主要毯蒲： 一、搭建仿真平台，包括v p r ，t - v p a c k 和s i s 等软件的安裟和使用，了 解m c n c 电路静使用方法，熬悉仿真流磋。 二、功耗日盏成为系统设计者关心的热点，丽嵌入硬核是实现低功耗的一种 有效手段。为了使v p r 能够仿真嵌入硬核的f p g a 架构，我们需要修改v p r 源 代码，蚨卷局_ 秘毒线嚣方鬣改进，生或四耱海遭宽度分蠢爨数，鄹褰孥、三焦、 脉冲和均匀分布，调查这四种沟道分布架构的效率。 三、麓毁嚣算法实凌f p g a 帮翳。瑗除段f p g aj 寿是蒸本都莛翔摸羧逡火算 法实现的，但蚁群算法在解决n p 。h a r d 问题上体现了良好的性能，而且具有天 然的并行瞧，这将会给鑫蘸复杂静布局闯邃提供新的解决思路。 6 f p g a 低功耗毒局布线算浃辨研究和改进 第二章f p g a 基本缩构和布局布线 本章主要介绍了现场可编程门阵列f p g a 的原理和结构，其主要由可配援逻 辑坟、连线资源和竣入输出模块等三部分缝成：同孵滋骥了凌戬屠耄第孛爰戮黪 一憋专业术语；接鬻阐述了f p g ac a d 设计的基本流程；最后说明了f p g a 布 爨蠢线除段实瑗瓣凌裁及冀蜜现琢壤，在其实现过鬟孛会有定稳稳住嚣拣佟为 优化对象，同时兼顾布通率。 2 1f p g a 结构 f p g a 一般由可配置逻辑单块c l b ，输入输出模块( i n p u to u t p u tb l o c k ，i o b ) 嚣蕊连资源( 矗蜘糙e c t i 勰r e s o u r c e , 鳓戳及一令爱予存教缡程数攒豹s r a m 成【1 4 1 。现在绝大部分的f p g a 都采用了删( i s l a n ds t y l e ) 结构，如嘲2 1 所示。 当然也有r o w - b a s e d 的f p g a 架构，僵其实现原理相似。 辩配 圈 i 口 _ _ _ _ 一 一 口 u口口 口口口口口口口口 图2 1 岛型f p g a 结构 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 所示。b l e 是由一个基于查找表( l o o k t t a b l e , l t r r ) 缝携戆k 输入逻疆瓣数发生器、融麟( f l i p * f l o p , f f ) 帮数据选择 器( m u x ) 组成的。b l e 能够实现任意k 输入、单输出函数，同时可以选择输出 7 f p g a 低功耗布局布线算法的研究和改进 是寄存器类型或非寄存类型，如图2 3 所示。每个c l b 含有b l e 抟个数n 默及 基本逶瓣元素含有l u t 豹输入端个数k 对f p g a 缒速度、瑟积、功耗等性鼹有 很大的影响。在 1 5 1 中分析了逻辑簇与l u t 对f p g a 面积和速度性能的影响， 在d 6 l q u 分椽了每个逻辑块会有b l e 令数与每个蒸本逻辑元素b l e 含有l u t 输 入个数辩f p g a 箍襁效率的影喻，貔出了实现低功耗的最优n 僵和k 值，研究 表明：单个c l b 中含宵4 个b l e 的f p g a 性能最优；在u ，r 数目一致的f p g a 中四输入熬l u t 较其它输入具有爨撬的性能。1 0 暇提供了f p g a 内部逻辑阵列 与井邂器件之闻的连接，通常蠹 捌程芯片豹遥周，主要是由输入触发器、输入缓 冲器、输出触发锁存器和输出缓冲器组成，i o b 可以被配置成输入、输出或输 入输出。双包括各种长度的金属逑线( l i n e ) 和可编程连接开美，主要实现c l b 与c l b ，c l b 与i o b 之间的连磺，将f p g a 缝奁成一个整俸。在f p g a 内部， 其水平方向的连线和瓣直方向的连线通过开关盒( s w i t c h b o x ，s b ) 实现连接。为了 溅少由逡线产生鲶延嚣尊鞍电阻，遗豢在f p g a 中设置长线和矮线，在不浪费资源 豹前提下，尽可能地减少了系统静两积和功耗，提高了速度。 r 一1 f 输入 时钟 潮2 2 c l b 结构 圈2 3 b i l e 结构 鬈 f p g a 低功耗稚禺布线算_ 老的研究和改进 蛋2 4 基于滋辑块鹃f p g a 稚绫结构 影响f p g a 性能的因絮除了基本逻辑块结构以外，布线结构也决定着f p g a 豹往能，教交f p g a 布线缩构参数褥会得掰不同性能的f p g a 。圈2 4 为蒸子逻 辑块结构的f p g a 布线结构图。每个逻辑块的弓l 脚w 以通过连接块中的连接开关 和线段相逑。水平布线轨道和竖直布线轨道相交的地方称作开关盒，开关盒由传 输门和三态缓冲嚣缀成，接制传浚门和三杰缓冲爨兹歼、美来实瑷霹编程裙线。 f p g a 的稚线结构可用一些参数来描述，它们是： 1 ) 帮线宽度( w ) ：每个布线逶道孛雹禽豹线段的数蠢。 2 ) 舞关块复杂度( f s ) ：开关块中，每条输入导线可以连接其他是线的数基。 3 ) 连接块复杂度( f c ) ：连接块中，每个逻辑块可以连接导线的数目。 蓟线段长度：每条线段耩跨越逻辑块盼个鼗等。 这些参数对f p g a 的藤积、速度和功耗等性能有较大的影响。 凰 酝玉蕊潮圈固 妙妙矽节 薅辕妇露耩器毛惫凌津器 匿2 5f p g a 的$ r a m 歼失 9 f p g a 低功耗布局布线算法的研究和改进 f p g a 的可编程通过三种方式来实现【1 7 1 8 1 。使用最多的是利用s r a m 单元 来控制传输门、多路选择器和三态缓冲器把可编程布线和逻辑块配置成所需要的 形式。图2 5 中给出了三种基于s r a m 的开关。 2 2f p g a 设计流程 笋 图2 6f p g a 开发流程 f p g a c a d 设计流程是将一个电路的高级描述转换为可配置f p g a 的比特流 ( b i t s t r e a m ) 的过程。整个设计流程如图2 6 所示。f p g a 厂商往往会提供与其产 品配套的开发工具，如x i l i n x 提供的i s e ，a l t e r a 的m a x p l u si i 等。通常f p g a 设计是以电路设计与输入开始的，现在硬件描述语言( h a r d w a r ed e s c r i p t i o n l a n g u a g e ，h d l ) 已成为大部分工程师的首选，当然还可以利用原理图的方式进行 设计。为确保描述的电路准确无误，在设计实现时需要不断进行软件仿真，包括 逻辑仿真，前仿真和后仿真等。 逻辑仿真无误后就是逻辑优化( l o g i co p t i m i z a t i o n ) 。常常被称为与技术无关 的优化，因为在这个阶段，目标是简化逻辑功能而没有考虑实际的目标技术。冗 l o f p g a 低功耗稚扁布线算法的研究和改进 余逻辑被去除，减少了网络的面积。 接麓是技术浃射( t e c h n o l o g ym a p ) 。多数商弱f p g a 包含l u t 作为基本鹃逻 辑单元。技术映射是一个将用户电路映射到l u t 的过程。一个k 输入的l u t 是一个数字存储器，能实现任意k 输入、单输出的奄尔函数；因此，一个k 输 入豹l l t 能完成任意一个2 2 不同的布尔函数。崩逻辑模块包含多于一个l u t 的f p ( 3 a 时，l u t 的网表将封装到与每个逻辑块l u t 数相关的簇中去。技术映 射与最终瞧鼹实瑗翁转g a 平台穗芙。 第三步称为布局葡线。用于决定每个功能模块的位置以及宦们之间的相反连 接。布局布线成功实现后，可编獠信息于是被翻译成位流( b i t s t r e a m ) ，对应于 f p g a 孛s 姒m 单元麴聚萋整。至蔻，可以逶i 妻爹载篷浚文 譬柬酝雯f p g a ，实 现具体电路功能。 2 。3f p g a 布局布线 f p g a 布局用于决定每个逻辑块的物理位置，图2 7 说明了一个电路网袭映射 到f p g a 巾的过程。典型的布局工舆应该努力达副以下目标： 卜最，l 、纯逻辑块之闯要求互连静连线数。 卜平衡使用交叉的f p g a 的布线以避免拥塞。 卜放置时闯院较关键的逻糖块尽可能靠近| 三l 优化关键鼹径鲍时楚。 电路网袭 漱射到f p g a 、 ，姒 图2 7f p g a 布局过稷 f p g a 的整体架构会对布局布线效率产生很大影响。j r o s e 等人将每个c l b f p g a 低功耗布局布线算法的研究和改进 所能连接的线道数定义为连通模块的毒线灵活度如将开关模块弓l 出端所能逡接 到其德弓| 懑矮数定义为歼关模块蠢线灵活度f ，稳们的实验h 9 1 缀果表稿，f s 一3 的开关模块配以高灵活度的连通模块是较好的选撵，能获得最少的布线开关总 数。连通模块和开关模块晦开关分布的据拎结构j c 重农通率的影响摄丈，d ew o n g 等人在溯对开关模竣籀矜结构进行了深入研究，援出了用最少开关构造遗溺嚣 关模块( u n i v e r s a ls w i t c hm o d u l e ，u s m ) 的算法，并藻于网络流理论分析了开关模 块的可靠逶性。对于簿边都有w 弓l 敬獭豫方形开关模块，如果对于任何不越j 蕊模 块弓| 密端豹网线均能稚通，就称之为u s m 。 在f p g a 设计时，布局布线优化目标往往是以上几个目标的综合，也就是需 要在延辩、面积等方凝俸下折中( t r a d e o f f ) 。许多纂名的算法邑经弓l 用到解决毒 局兹闽题上来了。模拟退火算法用簌了通用囊弱布线v p r 工其，我们将魏c a d 软件作为本研究的仿舆工具。模拟遐火算法源于正业上的退火疋艺原理，用于冷 却熔化舱金属。初始孵，系统随枫选择一个可行方案，朝逻辑块随机建被教在 f p g a 的c l b 上，同辩选择一个蘸瀑蕈。通过随机交换c l b 逐渐敬进布局状况。在 每次交换之后，与导线的长度、拥寨情况和逻辑的网线延时等相莱的代价函数e 来信计这秘移动。接蓑执行残对的交换，如果它的代伶函数值爨小，耨鲍方豢技 接受，它们的差为：雠；0 一，如果缸 o ，则= k ，否则按b o l t z m a n n 概率接受此新的方案，即取决于当前的温度和以前接受的代价函数与当前慎的 差，帮e x p ( - t 匹l r ) 。警凝夔方案嚣好瓣，更藜蓐。，在令特定静澄度下耋爱成 对交换的过程直到无法检测到性能的改善为止，此时系统处于平衡状态。按照熔 化物体邋火戆过程逐步降低温度，农赢温时e x p ( - a e i ) 装近于l ，大部分交换是 可接受的。当t 降低，只有少数成对交换是可接受的。最终系统达到一个设定的 退出条件，布局过程络束。在布局过程中之所以用b o l t z m a n n 概率接受一个较差 夔或对交换是戈了遭受f p g a 毒局j 霪攀熬整入蜀罄最小篷，藤寒找到囊正意义主 的全局较优解。 f p g a 布线资源怒为逻辑块之间连接分派好的，典型的稚线器试图做到。 卜连接爨毒要求魏嚣线，熏霹髑矮戆毒线资源，_ 筹基薅藏 至嚣建突。 通过用较短鼠快速的路径逐接关键网线到达优化关键路径的时延。 f p g a 低功耗布局布线算法的研究和改进 布线是实现电路中c l b 与c l b 、c l b 与l o b 之间连线上的开关盒的配置。 在f p g a 布线中，经常用有向图( d i r e c t e dg r a p h ) 表示。在有向图中，c l b 的引 脚和i o b 均表示为节点( n o d e ) ，而潜在的连线表示为边( e d g e ) ，布线就变成有向 图中某些节点之间的连接过程。为了避免有限的连线资源被过多的占用，我们希 望两个节点之间的边尽可能地短。同时，一个节点不能完全占用另一个节点所需 的资源，这就要求大多数布线器需要堵塞避免机制来解决布线资源竞争问题。另 外一个优化目标是使用快速布线资源和使用较短路径来优化关键路径。 f p g a 低功耗布尚布线算法的研究和改进 第三章仿真平台介绍 本耄童要分绍本研究所使用的仿囊平台，包撼v p r 、t - v p a c k 仿真软佟稆 m c n c 电路。v p r , t - v p a c k 是学术器广泛应用静，用于研究f p g a 布局番线和 架构的仿真软件，它们能够模拟大量的f p g a 架构。m c n c 电路是通用的标准 数字电路，通常用于测试被修改后的架构帮布局奄线算法的性能。 3 1v p r 简介 焉产壤瓣 结 奄撼逑 佰计 隧3 1v p r 仿真模溅 v p r ( v e r s a t i l ep l a c ea n dr o u t e ) 2 h 莛v a u g h nb e t z 等久歼发豹可广泛臻子 f p g a 架构研究的布局布线工具，遁用于仿真很多不同架构的f p g a ，现在关于 f p g a 布局布线的学术研究基本都是基于这个仿真平台进彳亍的。v p r 是爨于 l i n u x 系统嚣发懿，爨畜盈形纯鹊撩捧赛嚣。它黟逻辑袭封装王其t - v p a c k 结 合使用。v p r 包括两个部分：布局布线工具和一个详细描述丽积和延时模裂， 如图3 1 所示。布局布线工具映射电路到f p g a ，面积和延时模型在布局布线工 兵戆结象基琏主 鑫诗褥积震关穗路径延霹。两个都分籀互俸丽决定电路煞最佳 布局和布线。图3 2 怒v p r 的实现过程，它首先读取与实现技术有关的融被映 射的电鼹网表文件和f p g a 架构攒述文传( a r c h i t e c t u r ed e s c r i p t i o nf i l e ) ，v p r 黔 布局嚣熊够实臻毫鼹布局或者设读取已经鑫弱完成靛方案，然后进入毒线环节； 布线器可以完成全局布线( g l o b a lr o u t i n g ) 或者全局细节布线( g l o b a l - d e t a i l r o u t i n g ) 。布局布线过程完成后，v p r 会输出相应的布局、耀线结果和中阍造程 产生熬统诗文件，这撩统计文伴中包含豹信惠镪括总布线长液、弼线数鬃戳及 最大网线长度等。在v p r 的架构描述文件中可以声明很多架构参数，包括：输 f p g a 低功耗布局布线算法的研究和改进 入输出逻辑块数量、逻辑块的输入输出端、f p g a 每行( 列) 中包含的i o 、f p g a 的规模；如果布线方式为全局布线，还可以声明水平( 垂直) 沟道的相对宽度、不 同区域的沟道相对宽度；如果为全局细节布线方式，还需要描述开关盒的架构、 每个逻辑块能连接的输入网线数 c ) 等。 - 7 e x i s t i n gp l a c e m 、e n t 、 、 o rp l a c e m e n tf r o m ； a i i o t l l 口c a dt e a l 一， 图3 2v p r 的c a d 实现流程 v p r 起初是为岛型f p g a 设计的，现在也可以仿真基于行的f p g a ，但还 不适用于多层次( h i e r a r c h i c a l ) 的f p g a 。它的可视化界面除了能够使用户可以直 接控制布局布线过程外，同时也能直观的感受布局布线过程以及查看当前f p g a 中可利用的资源，包括i o 和c l b 的分配状况，可以通过点击某个c l b 查看与 该c l b 相连的其他模块及其走线，它会对c l b 的输入输出用不同颜色进行标 注。v p r 的仿真目标是基于s r a m 的f p g a 。s r a m 单元用于控制沿着布线轨 道的传输晶体管开关( p a s s - t r a n s i s t o r ) 和三态缓冲器，同时也用于储存由每个l u t 实现的逻辑功能和充当逻辑块中多选器的选择信号，v p r 假设每个s r a m 元胞 ( c e l l ) 有六个体积最小的晶体管，见图3 3 。储存在元胞中的d a t a 和d a t a 非的值 没有任何隔离反相器能直接与其他导线相连。n m o s 传输晶体管由于体效应只 能传输一个弱的逻辑1 ，输出电压减少了一个v 廿i 。为解决这个问题，这些传 输晶体管的门电压常常进行升压来克服这种体效应。 由于f p g a 的具体架构有很大差别，导致对应的网表文件也有很多不同， 这时我们就需要借助t - v p a c k 这个工具，具体参见3 4 节。 f p g a 低功耗榷局布线算法盼醑究和激进 3 2v p r 实现原理 圈3 3 六管s r a m 单元原理圈 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 ) ，这样裁糖象兔一令奏两霆。节轰懿 电容是节点的特征袭示，如果节点怒一条导线，它的电容包括导线电容和歼关电 骞。絮采节赢是一个输入或建输窭孳 辞，毫察毽捂连接开关电容帮萼 脚奄各。每 个节点的电容对于功耗估计很重要。对于每条边，记录储存麓有关农布线结构中 每个开关豹信息，阮如用予专门连援的开关类型。遮个信息对于计算没有使用的 开关数量怒必要的，这需要用于在f p g a 申怙算泄濑功耗。在实现j 建程中，v p r 设定了一定的优化嗣标，用户可以依据自己的要求来优化f p g a 系统，其中有减 夸羹连模袋戆连线长度，鼗连线长发驱动枣蜀( w i r e - l e n g t h - d r i v e np l a c e m e n t ) ：骞 时也会为了平衡这个f p g a 的邂线密度，布线驱动布局( r o u t a b i l i t y - d r i v e n p a c e n l c n t ) 或者馊电路速度最大纯，露藤驱动奄嚣( 髓m i n g * d r i v e np l a c e m e n t ) ， 而实际上，往往是这几个优化目标的综合。 3 2 1v p r 布局算法 v p r 使用模拟退火算法s a 来完成布局。它使用一个线性阻塞( l i n e a r 1 6 f p g a 低功耗磷禺毒线冀法照研究和数进 c o n g e s t i o n ) 代价函数作为寻优目标，其表达残为： 加警m ，r 器+ 器， * ；lo ，o “， 武中c o s t 怒对所有网络( 脯0 求和；对于每个n e t ，6 以和6 巩分别代袭整个限制盒 $ o 瑚盛n gb o x ) 联鑫熬本乎、垂壹长度( s p a n ) ；譬 燕一个於馔因子，恶于蛰镶睫 着端口递增而导致网线的非线性增加；c 矗。例盒巴。i n ) 是在限制盒，l 上的横向、 缀趣平穗滋遘容量。该段徐滋数霹较窄酌沟遴孛进行大量蠢线豹行蔻透行了逶当 限制。 在模羧运火算法串，一个合理静递 程谲) 蔓( s c h e d u l e ) 算法对予在合理的计算对 间内获得离质量的仿真结果是必需的。v p r 中使用了新的调度算法，它的s a 参 数念随着电路规模芹叠代价醋数而改变。它采用类似于 2 2 】的方式来计算s a 的初 始瀑度。；定义越妇幽为电路中