（微电子学与固体电子学专业论文）用于fpga的新型混合布线算法的研究.pdf

摘要 摘要 现场可编程门阵列( f p g a ) 是一种包含有可配置逻辑模块和布线模块的数字集成 电路，它支持可编程重复配置，并且节省了流片时间和费用，因此以灵活、风险低、开 发周期短等优势在通信、工业控制、汽车电子、数据处理、消费电子等领域得到了广泛 应用。然而，随着f p g a 内部可配置资源容量的增加，对应的计算机辅助设计( c a d ) 工具也需要升级和优化。随着设计复杂程度的提高，将一个设计配置到f p g a 上往往需 要c a d 工具计算很长时间( 如数小时) 方可满足各种参数要求。布线阶段通常消耗整 个c a d 流程近3 0 的时间，因此，高效的布线算法对缩减整个f p g a 开发流程的时耗 和满足各种约束条件至关重要。 当今广泛采用的f p g a 布线算法主要包括基于几何查找的布线算法和基于布尔可 满足性( s a t ) 的布线算法；两者各有优缺点。基于几何查找的布线算法均由基本迷宫 ( m a z e ) 算法演化而来，它虽然可经过优化提高布线速度，但由于一次只能布一根线， 可布线性较难确定，通常依靠设定运行时间上限来实现算法终止。另外，其它由迷宫算 法优化而来的各种几何查找算法也均存在依赖布线顺序的缺点。相比之下，基于s a t 的算法由于可同时给所有线网布线，因此能从理论上证明可布线性。但是，这种算法需 要大量变量和约束条件公式，所以可扩展性并不好。 最近，一种基于伪布尔可满足性( p b s a t ) 的布线算法成为f p g a 布线算法的研 究热点。和布尔s a t 算法类似，p b s a t 算法可同时给所有线网进行布线，因此也能准 确判断可布线性。和布尔s a t 算法不同的是，它将约束条件用精简的表达式予以表示， 需要的布线变量和式子大大减少，因此显著降低了内存需求，提高了扩展性。但是， p b s a t 算法在布线速度上仍然慢于传统的几何查找算法。为了吸收几何布线算法和伪 布尔布线算法的优点，本文又提出了一种新型的混合算法( p p b s a t ) 。下面归纳本文 的主要研究工作和结论。 介绍了f p g a 的特点，并与专用集成电路( a s i c ) 进行了比较；分析了常见的f p g a 编程工艺、架构及特点；在此基础上确定了采用x i l i n x 的岛状f p g a 架构作为研 究的布线对象。 详细介绍和比较了三种几何算法，即l e e 迷宫算法、a 木算法和基于协商的性能驱 动的布线算法p a t h f i n d e r ；分析了两种基于布尔s a t 的详细布线算法，即基于轨线 的详细布线s a t 算法( t - s d r ) 和基于路线的详细布线s a t 算法( r - s d r ) 。实验 结果表明，在总布线时间和稳定性方面上r - s d r 略弱于p a t h f i n d e r ，分别为 p a t h f i n d e r 的11 7 9 、0 9 0 1 倍。然而在不可布线的电路布局基准上，r - s d r 能够 准确判定可布线性，而p a t h f i n d e r 则不能。 研究了最新的p b s a t 布线算法，并在约束表示方面和布尔s a t 算法进行了比较。 实验结果表明，p b s a t 算法在布线时间和稳定性方面的表现处于r s d r 和 p a t h f i n d e r 之间：p b s a t 算法在总时间上分别是r s d r 的8 9 5 和p a t h f i n d e r 的 摘要 1 0 5 5 ；在总体稳定性方面，p b s a t 分别为r - s d r 的1 0 4 2 倍和p a t l f f m d e r 的0 9 3 9 倍；p b s a t 判定不可布线的总时间为r s d r 的9 1 9 。 最后，基于p b s a t 和几何算法的结合，提出了p p b s a t 新型混合算法。实验结 果表明，p p b s a t 算法在时间和稳定性上都优于p a t h f i n d e r 、r - s d r 、p b - s a t 。 在总布线时间上，p p b s a t 分别为p a t h f i n d e r 、r - s d r 和p b s a t 的5 5 3 、4 7 4 、 5 2 5 ；在稳定性方面，分别为三者的1 6 5 、1 8 3 、1 7 6 倍；p p b - s a t 判定不可布 线的总时间分别为p b s a t 和r s d r 的8 8 2 、8 1 0 ；证明了该新型混合算法的 高效性。 关键词：现场可编程门阵列；布线；几何查找布线算法；布尔可满足性布线算法； 伪布尔可满足性布线算法；混合算法 a b s t r a c t a b s t r a c t 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 ) i sd i g i t a l i n t e g r a t e d c i r c u i t sc o n t a i n i n g r e c o n f i g u r a b l el o g i cb l o c k sa n dr o u t i n gr e s o u r c e s t h ep r o g r a m m a b l er e c o n f i g u r a t i o n ，a sw e l l a st h eg r e a ts a v i n gi np r o c e s s i n gc o s ta n dt i m e ，l e a d st ow i d ea p p l i c a t i o n sf o rf p g ai n c o m m u n i c a t i o n s ，i n d u s t r yc o n t r o l ，a u t o m o t i v ee l e c t r o n i c s ，d a t ap r o c e s s i n g a n dc o n s u m e r e l e c t r o n i c s ，d u et oi t sf l e x i b i l i t y , l o wr i s ta n ds h o r tr e s e a r c ha n dd e v e l o p m e n tp e r i o d h o w e v e l t h ec o r r e s p o n d i n gc o m p u t e ra i d e dd e s i g n ( c a d ) t o o l sh a v et ob eu p g r a d e da n do p t i m i z e d w i t l lt h ei n c r e a s i n gn u m b e ro fr e c o n f i g u r a b l eb l o c k si nf p g a a st h ed e s i g nb e c o m e sm o r e a n dm o r ec o m p l i c a t e d ，i tu s u a l l yt a k e sm u c hl o n g e rt i m e ( e g ，ac o u p l eo fh o u r s ) f o rc a d t o o l st om a pad e s i g nt ot h ef p g ad e v i c ea n dm e e tt h er e q u i r e m e n t so fv a r i o u sp a r a m e t e r s s i n c et h er o u t i n gs t a g eo f t e nc o n s u m e sn e a r l y3 0 o ft h ew h o l ec a df l o wt i m e ，i ti so fg r e a t i m p o r t a n c et oe x p l o r eah i g he f f i c i e n c yr o u t i n ga l g o r i t h mt or e d u c et h ew h o l ef p g a f l o w t i m ea n ds a t i s f ya l lc o n s t r a i n t s c u r r e n t l y , m o s tf p g ar o u t i n ga l g o r i t h m sa r em a i n l yb a s e do nt h eg e o m e t r ys e a r c h i n g a n db o o l e a ns a t i s f i a b i l i t y ( s a t ) b o t ht y p e so fa l g o r i t h m sh a v et h e i ro w na d v a n t a g e sa n d d r a w b a c k s t h eg e o m e t r ys e a r c h i n gr o u t i n ga l g o r i t h m s ，a l le v o l v i n gf r o mt h eb a s i cm a z e a l g o r i t h m ，c a nb eo p t i m z e dt or a i s et h er o u t i n gs p e e d ，b u tt h e yo n l yr o u t eo n ew i r ee a c ht i m e ， m a k i n gi t d i f f i c u l tt od e t e r m i n et h er o u t a b i l i t y t h ea l g o r i t h m sa r et h u sn o r m a l l yt e r m i n a t e d b ya nu pt i m el i m i ts e t t i n g m e a n w h i l e ，a l lt h eo t h e rs i m i l a ra l g o r i t h m sd e v e l o p e df r o mt h e m a z ea l g o r i t h mh a v et h ed i s a d v a n t a g eo fh i g l lr o u t i n gs e q u e n c ed e p e n d e n c e s a t - b a s e d a l g o r i t h m s ，h o w e v e r , c a nr o u t ea l lt h ew i r e sa to n et i m e ，m a k i n gt h er o u t a b i l t yt h e o r e t i c a l l y p r o v a b l e t h ep r o b l e mi st h a tt h e s ea l g o r i t h m su s u a l l yr e q u i r eal a r g en u m b e ro f v a r i a b l e sa n d c o n s t r a i n tc l a u s e s ，m a k i n gt h es c a l a b i l i t yr e l a t i v e l yp o o r r e c e n t l y , ar o u t i n ga l g o r i t h mb a s e do np s e u d o b o o l e a ns a t i s f i a b i l i t y ( p b - s a t ) b e c o m e s ah o tt o p i c s i m i l a rt oc o m m o ns a t - b a s e da l g o r i t h m s ，t h ep b s a ta l g o r i t h mc a nr o u t ea l lt h e w i r e sa tt h es a m et i m e ，a n dt h er o u t a b i l i t yb e c o m e sd e t e r m i n a b l e t h eg o o dt h i n gi st h a tt h e p b - s a tr o u t i n ga l g o r i t h mc a np r e s e n tt h ec o n s t r a i n t si nr o u t i n gp r o b l e mb ys i m p l ec l a u s e s ， r e d u c i n gt h en u m b e r so fv a r i a b l e s a n dc l a u s e ss i g n i f i c a n t l y t h e r e f o r e ，t h em e m o r y r e q u i r e m e n ti sg r e a t l yr e d u c e da n dt h es c a l a b i l i t yi so b v i s o u l yi m p r o v e d o nt h eo t h e rs i d e ， t h ep b s a tr o u t i n ga l g o r i t h ms t i l lh a sl o w e rr o u t i n gs p e e dt h a nt h et r a d i t i o n a lg e o m e t r y s e a r c h i n ga l g o r i t h m s t h u san e wh y b r i dr o u t i n ga l g o r i t h m ( p - p b - s a t ) ，c o m b i n gt h e a d v a n t a g e so ft h ep b s a ta l g o r i t h ma n dg e o m e t r ys e a r c h i n go n e s ，h a sb e e np r o p o s e d t h e m a j o rw o r ka n dc o n c l u s i o n so f t h i st h e s i sa r es u m m a r i z e da sb e l o w f e a t u r e so ff p g aw e r ef i r s t l yi n t r o d u c e da n dc o m p a r e dt oa p p l i c a t i o ns p e c i f i c i n t e g r a t e dc i r c u i t s ( a s i c s ) c o m m o np r o g r a m m i n gt e c h n o l o g i e s ，a r c h i t e c t u r e sa n d p r o p e r t i e so ff p g aw e r et h e na n a l y z e d f i n a l l y , t h ex i l i n x si s l a n d b a s e df p g a a r c h i t e c t u r ew a sd e t e r m i n e da st h er o u t i n go b j e c tf o rt h i sw o r k t h r e e g e o m e t r ys e a r c h i n gr o u t i n ga l g o r i t h m s ，l e em a z ea l g o r i t h m , a 宰a l g o r i t h ma n d p a t h f i n d e r ( an e g o t i a t i o n b a s e dp e r f o r m a n c ed r i v e na l g o r i t h m ) ，w e r ef i r s t l yi n t r o d u c e d i nd e t a i l t w ob o o l e a ns a tr o u t i n ga l g o r i t h m s ，t h et r a c k b a s e dd e t a i l e ds a tr o u t i n g i i i a b s t r a c t a l g o r i t h m ( t - s d r ) a n dt h er o u t e b a s e dd e t a i l e ds a tr o u t i n ga l g o r i t h m ( r - s d r ) ，w e r e t h e na n a l y z e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tb o t ht h er o u t i n gt i m ea n dt h es t a b i l i t y o fr s d ra r eal i t t l ew e a k e rt h a nt h o s eo fp a t h f i n d e r ( 1 17 9 a n d0 9 01 t i m e s ， r e s p e c t i v e l y ) h o w e v e r , r - s d rc a ne v a l u a t et h er o u t a b l i t ya c c u r a t e l yi nu n r o u t a b l e c i r c u i tb e n c hc a s e s ，w h i l ep a t h f i n d e rc a l ln o t t h el a t e s tp b s a tb a s e dr o u t i n ga l g o r i t h mw a sa l s os t u d i e da n dc o m p a r e dt o s a t b a s e do n e sf r o mt h ev i e w p o i n to fc o n s t r a i n tp r e s e n t a t i o n s t h ee x p e r i m e n t a lr e s u l t s i n d i c a t et h a tt h er o u t i n gt i m ea n dt h es t a b i l i t yo fp b s a t a l g o r i t h mf a l lb e t w e e n1 0 s d r a n dp a t h f i n d e r t h et o t a lr o u t i n gt i m eo fp b s a ta l g o r i t h mi sa b o u t8 9 5 o fr s d r a n dl0 5 5 o fp a t h f i n d e r , w h i l et h es t a b i l i t yo fp b - s a ta l g o r i t h mi sa b o u t1 0 4 2t i m e s o fr s d ra n d0 9 3 9t i m e so fp a t h f i n d e r ；t h et o t a lt i m eo fp b s a ta l g o r i t h mf o r e v a l u a t i n gu n r o u t a b l i t yi sa b o u t91 9 o fr s d r f i n a l l y , an e wh y b r i dr o u t i n ga l g o r i t h m ( p - p b s a t ) w a sp r o p o s e db yc o m b i n gt h e p b - s a ta l g o r i t h ma n dp a t h f i n d e r t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tb o t ht h er o u t i n g t i m ea n dt h es t a b i l i t yo ft h i sn e wa l g o r i t h ma r es u p e r i o rt op a t h f i n d e r , r s d ra n d p b - s a t t h et o t a lr o u t i n gt i m eo fp p b s a ti s o n l y5 5 3 4 7 4 a n d5 2 5 o f p a t h f i n d e r , r - s d ra n dp b s a t , r e s p e c t i v e l y , a n dt h es t a b i l i t yo fp p b s a ti sa b o u t 1 6 5 ，1 8 3a n d1 7 6t i m e so ft h el a t e rt h r e ea l g o r i t h m s ，r e s p e c t i v e l y b e s i d e s t h et i m eo f p - p b s a tf o re v a l u a t i n gu n r o u t a b l i t yi sa b o u t8 8 2 o fp b s a ta n d81 o o fr s d r a ut h e s er e s u l t sp r o v et h eh i g he f f i c i e n c yo ft h i sn e w h y b r i dr o u t i n ga l g o r i t h m k e y w o r d s ：f i e l d p r o g r a m m a b l eg a t ea r r a y ；r o u t i n g ；g e o m e t r i cs e a r c h i n gr o u t i n g a l g o r i t h m ；b o o l e a ns a t i s f i a b i l i t yr o u t i n ga l g o r i t h m ；p s e u d o b o o l e a ns a t i s f i a b i l i t yr o u t i n g a l g o r i t h m ；h y b r i da l g o r i t h m i v 独创性声明 本人声明所呈交的学位论文是恭人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签名： 一日期：一 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印，缩印或扫描等复制手段保存、汇编学位论文， 并丑苯人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名弛髯缁。导师签名：墨盟鱼生 j 日 期趔：星：丝一 第一章绪论 第一章绪论 自从现场可编程门阵列( f p g a ) 在2 0 世纪8 0 年代商业化并推出以来【l 弓】，数字电 路的设计方式发生了革命性变化。随着f p g a 逻辑容量的增加和c a d 工具的高效化， f p g a 芯片已成为众多电子工程师的首先方案，其市场越来越庞大。本章首先介绍课题 背景和意义，接着综述f p g a 的发展现状和趋势，最后列出全文的内容安排。 1 1 课题背景和意义 电子信息产业业已成为各国国民经济的支柱之一。随着3 g 时代的到来，以通信和 网络为代表的技术革命推动了信息产业又一轮新的发展浪潮。作为整个信息产业的根 基，集成电路( i c ) 技术在3 g 时代赢得了空前的快速发展机遇。i c 是信息产业的基础 和核心，已渗透到日常生活的各个环节。从普通家用电器的控制芯片，到名目繁多的各 种时尚便携式消费类电子产品，再到功能越来越强大复杂的计算机处理器【l 捌，i c 技术 和产品无所不在。 i c 产品一般可分为以下几种类型：通用和专用处理器( 如数字信号处理器、加密处 理器等) 、存储器( m e m o r y ) 、专用集成电路( a s i c ) ( 如m p 3 解码芯片、u s b 设备控 制器等) 和f p g a 芯片( 主要厂家有x i l i n x t 3 1 、a l t e r a 4 1 、a c t e l 5 】等) 。在各种信息系统 的设计中，通常要对硬件和软件进行平衡( 也称之为软硬件协同设计) 以满足费用和性 能上的要求。当协同设计满足不了性能要求或系统需求量非常庞大时，一般采用a s i c 来完成整个设计，即按照用户的定义和特定要求来设计、制造。由于a s i c 用硬件实现 系统的全部功能，因此具有高速的优点，并且适用于批量生产以降低单片价格。但是， a s i c 也有其不可忽视的缺点：( 1 ) a s i c 设计从用户提出需求到制造完成往往需要较长 的时间( 半年到数年) ，很难适应快速变化的市场；( 2 ) a s i c 往往缺乏灵活性，硬件电 路旦生产出来，功能就不能改变，不利于当前各种快速变化的功能需求；( 3 ) 随着现 代各种电路的复杂化，从设计、验证到制造，无论哪个环节出现小漏洞或缺陷都可能导 致整个芯片失败。由于a s i c 开发通常需要很多工程师共同完成，电子设计自动化( e d a ) 环节花费昂贵，再加上更加昂贵的制造费用，使得a s i c 开发在工业界被定义为风险最 大的领域之一。图1 1 给出了不同特征尺寸的工艺下a s i c 的掩膜费用。以目前国内比 较主流的1 3 0n l i l 工艺为例，仅掩膜费就高达近7 0 万美元1 6 】。 相比之下，f p g a 以其灵活、高速、开发周期短等优点受到了工业界的青睐。在灵 活性方面，因为f p g a 可以重复配置，即当电路用比特流配置好f p g a 之后，还能继续 修改，再次完成配置，这样有利于电路不断修改和升级，也避免了a s i c 设计到制造中 出现问题的风险。至于高速性，f p g a 是以电路实现各种功能的，所以速度比一般软件 执行要快，且能并行执行各种运算。最后，在开发周期上，f p g a 省去了制造流程。相 比于a s i c 项目动辄需要十个或数十个工程师一起完成，一个f p g a 项目由几个，甚至 一个工程师花数月时间即可以完成。所以，f p g a 既具有类似于软件的灵活性，也具有 扛南大学硕士学位论文 硬件实现的高速性，并且开发周期短、投资小、风险小，因而已成为众多开发商、电子 工程师的首选方案。 a s c 掩腱费用睐自p i p e r j l f f r a 帅 $ 4 0 0 0 0 0 0 0 0 $ 3 5 0 0 0 0 00 0 $ 3 0 0 0 0 0 00 0 $ 2 5 0 0 o 0 0 $ 2 0 0 0 00 0 $ 1 5 0 0 c 0 00 0 $ 1 , 0 0 0 6 0 00 0 $ 5 0 0 0 0 00 0 03 s l r n02 5 9 r n0 1 8 u r n 0 1 3 p r o 9 0 n m 6 5 n m 固i - l 各种工艺下专用集成电路蒋膜费用 f i g 1 - it h ec o s t o f a s i c m a s k i n d i f i e r c a t p r o c e s s e s 如今，f p g a 已经广泛用于信息产业中，如高速互联网、无线通信、现代军用设备、 视频和图像处理、航天航空以及汽车电子。图 - 2 列出了近年来f p g a 市场的分布和产 值情况门。随着f p g a 性能的日益提高和c a d 工具的发展，f p g a 将逐渐取代a s l c 市 场。 6 0 4 0 o 军事，航 空 - 2 0 0 2 6 2 0 0 8 。6 2 0 0 2 年产值2 3 亿美元 2 0 0 e 年产值髓亿美元 1 1 以 通信工业控制汽车屯子鼓据处理消费电子 1 4 0 1 6 6 3 3 1 8 田i - 2 f p g a 市场分布和产值 f i g 1 - 2 t h e d i a n d p r o d u c t i o n v a l u e o f f p g a m a r k e t 目前，我国在f p g a 领域的研究还处于初步发展阶段，应用到各种领域的f p g a 产 品基本来自国外公司。尤其是国防领域，均来自国外进口，这不仅耗费了大量的资金， 而且技术上也受到了约束，非常不利于我国国防事业的发展，更可能会带来潜在的危机。 因此，开发有独立知识产权的f p g a 产品和相应的c a d 工具显得十分必要和迫在眉睫。 第一章绪论 1 2f p g a 发展状况和趋势 1 2 1 可编程逻辑的历史 1 9 7 0 年出现的p r o m 是最早的可编程逻辑器件【引。在7 0 年代中期，可编程逻辑阵 列【8 】( p l a p r o g a m m a b l el o g i ca r r a y ) 诞生了，但由于基于它的设计流程相当复杂，因 此没有得到广泛使用。7 0 年代末期出现了基于与或门的可编程逻辑器件【8 】( p l d ) ，它 虽然具有高速、结构简单的特点，但是规模很小，不能实现复杂的数字设计。1 9 8 5 年， x i l i n x 公司推出了现场可编程门阵列【8 】( f p g a ) ，器件基于c m o s 工艺制作，具有密度 高、编程速度快、设计灵活、可重复配置等诸多优点。随后，f p g a 逐渐往高性能高集 成方向发展。在2 0 0 6 年，f p g a 的两大供应商x i l i n x 公司和a l t e r a 公司先后推出采用 6 5a m 工艺的f p g a 系列v i r t e x - 5 和s t r a t i xi i i ，其中v i r t e x 一5 包含3 3 万个逻辑单元，可 用的i o 多达1 2 0 0 个【3 】。s t r a t i xi i i 含有3 3 万个等效逻辑单元，5 0 0 多个1 8 x 1 8 乘法器， 可用i o 多达1 1 0 0 个 4 1 。 1 2 2f p g a 新产品 目前，世界上主要的f p g a 厂家x i l i n x 、a l t e r a 、a c t e l 等均可提供不同类型的f p g a 产品，并不断推出新产品。新产品主要有以下三方面的改进或创新： 第一，增加f p g a 可配置资源，采取新工艺，降低功耗。增加f p g a 可配置资源可 以依赖于更大的芯片面积或采用更小的集成工艺。表1 1 显示了一组来自x i l i n x 的典型 f p g a 的逻辑资源和i o 资源1 9 】。 表1 1 来自x i l i n x 的典型f p g a 的逻辑资源和i o 资源 t a b 1 - 1l o g i cr e s o u r c ea n di or e s o u r c eo f t y p i c a lx i l i n x sf p g a s 第二，增加f p g a 内部硬模块。现在诸多f p g a 内嵌了固化的处理器，如x i l i n x 的 v i r t e xi ip r o 已经嵌入了p o w e r p c 处理器来实现各种嵌入式开发【l 们，另外也有嵌入r a m 模块、乘法器、多重系统时钟、i o 系统等，这使得f p g a 的功能更强大，甚至可实现 片上系统( s o c ) 功能。 第三，优化f p g a 整体架构和c l b 架构。不同逻辑单元结构的改变将影响f p g a 整体架构和功能。随着可配置逻辑资源的增加，将一个庞大的设计配置到f p g a 中耗时 很长，并且极其复杂，这对c a d 工具要求很高。因为布线带来的时序延迟通常占信号 时延的5 0 6 0 【1 1 ，1 2 1 ，所以电路编制过程中为减少布线时延，大部分编制时间花费在 布线阶段。另外，一些特殊的长线已被设计到f p g a 中以减少长距离延迟。为方便c a d 江南大学硕士学位论文 设计，缩短整个流程耗时，f p g a 将会不断调整其架构来适应越来越庞大的芯片面积。 与此同时，也要求各个f p g a 厂商的c a d 工具不断更新以配合新的f p g a 芯片。 1 2 3f p g a 的特点 相比a s i c ，f p g a 具有很多有竞争力的优点： 1 开发周期短。在a s i c 设计流程中，完成一个项目、得到实际芯片通常需花费至 少半年、甚至几年时间( 其制造过程往往就得数月) 。而f p g a 设计流程不存在流片、 制造问题，所以一旦设计并通过验证，只需半天或一天时间就可将硬件描述语言( h d l ) 快速转换成比特流配置到f p g a 中实现系统，因此f p g a 设计流程更能适应快速进入市 场的要求。另外，各个主要f p g a 公司都提供了各种i p ( i n t e l l i g e mp r o p e r t y ) 模块来帮 助开发，甚至设计者可以不懂h d l ，只需用原理图将各个模块拼接起来，也能开发出 自己所需的基于f p g a 系统的功能。 2 设计风险低。在a s i c 设计流程中，从设计到验证到流片，都可能引入问题。 如果芯片已经制造出来，这些问题是不可修复的，也就意味着大量流片费用的损失。而 f p g a 支持可重复配置，一旦功能有误，可以立即修复、再次配置。f p g a 还支持在线 测试，因此风险可以降到最低。 3 可重复配置。可重复配置不仅能降低风险，还能支持各种硬件升级。当前市场 上大多f p g a 是基于s r a m 的( 如x i l i n x 的产品) 。由于产业动态不断在变化，新产品 往往在很短时间就要被更新，因此可重复配置性给系统设计者提供了巨大的灵活性。而 a s i c 在流片制造完成之后，却再也不能修改硬件。 f p g a 的灵活性是以面积、延时和功耗为代价换来的，在实现同样的逻辑功能条件 下，f p g a 需要比a s i c 多约2 0 到3 5 倍的面积，速度慢3 到4 倍，并且功耗多近1 0 倍。 f p g a 的主要缺点可归纳为两条： 1 逻辑密度低。在一块f p g a 上，绝大部分面积被互联逻辑所占据，而实际逻辑 面积仅占很小一部分，这也是可重复配置性带来的代价。当前的f p g a 结构调查显示： 在一个简单的f p g a 中，可配置逻辑面积仅仅为可配置互联面积的1 0 。 2 相对速度慢。相对于a s i c ，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 有这些缺点，但暇不掩瑜，在数字系统实现上面它已经成为一种广泛应 用的强大工具。尤其是对于小公司或者群体，f p g a 可以提供符合甚至打破摩尔定律 ( m o o r e sl a w ) i i3 j 的集成度和速度的发展。今天的( 超) 深亚微米工艺已使a s i c 设计 越来越困难和昂贵。制造一块a s i c 芯片在资金和人力上的耗费经常让规模不足的企业 难以承受，这些花费包括：( 1 ) 用于综合、布局、布线、提取、仿真、时序分析、功耗 分析的先进的a s i cc a d 工具非常昂贵；( 2 ) 仅芯片的掩膜板制造就常需耗费上百万美 4 第一章绪论 元( 当然，此项耗费能够通过将几个不同厂家的小电路放在一起来共享一块掩膜板或者 采用结构化的a s i c 来降低) ；( 3 ) 开发一个大的a s i c 芯片需要一个开发团体耗费数年， 因此人力费用也极其昂贵。a s i c 这些高花费的缺点迫使大部分数字设计都尽可能转为 f p g a 实现。 1 3 研究内容和论文构架 鉴于上文所述f p g a 及其布线的重要性，本论文着重于f p g a 布线算法的研究。目 前，最流行的f p g a 布线算法主要有几何查找布线算法 1 4 - 1 7 1 和布尔可满足性( s a t ) 布 线算法【1 8 。2 们。然而，这两种算法都存在各自缺点，不能完全满足复杂f p g a 布线特征的 要求。一方面基于s a t 的布线算法在可扩展性上有很大缺陷；而另一方面，几何查找布 线算法由于一次只能布一根线，需要不断拆线、重布线，因此当一个布线问题中具有严 格布线约束条件时，它在布线方案的收敛方面存在很大困难。本论文在分析一些常规布 线算法的基础上，深入研究了一种最新的伪布尔可满足性( p b s a t ) 布线算法【2 l 。2 引， 并且将此算法与一种几何算法( p a t h f m d e r ) 【1 6 】结合，提出了一种高效的混合算法 ( p p b s a t ) 。该算法既克服了s a t 算法在可扩展性方面的局限性，又弥补了传统的几 何查找布线算法在可布线性判定方面的缺陷。 论文的主要内容由如下几部分构成： 第2 章首先介绍了各种f p g a 的结构特征、结构模型以及不同产品供应商在f p g a 结构上的研究动态；接着介绍了整个f p g a 开发流程，并详细介绍了布线及其在整个流 程中的重要性；最后描述了本文实验中所采用的布线基准。 在第3 章中，研究了三种基于几何查找的布线算法，即基本迷宫布线算法l e e 、a 算法以及现今广泛采用的p a t h f i n d e r 算法；另外研究了基于轨线的布尔函数布线算法 ( t s d r ) ，并解释了该算法如何应用于f p g a 详细布线；接着研究了一种可替代的基 于路线的详细布线算法( r - s d r ) 。与基于轨线的公式相比，基于路线的公式产生了更加 紧密的s a t 实例，因此也更加有效。最后从实验上将r o s d r 和p a t h f i n d e r 进行比较， 分析了两种算法的优缺点。 第4 章研究了最新的p b s a t 布线算法，它利用了布尔变量的整数特性，使条件函 数更加简化，使运算时占用的内存资源大幅度减少，大大提高了算法的扩展性。另外， 通过实验结果将p b s a t 算法与r s d r 和p a t h f i n d e r 进行了比较和分析。 在第5 章中，基于p b s a t 算法和几何算法p a t h f i n d e r 的结合，提出了一种新型混 合算法p p b s a t ，详细描述了该算法的原理和特点。最后将p p b s a t 算法的实验结果 与p b s a t 、r - s d r 和p a t h f i n d e r 进行了一系列比较，证明了新算法的高效性。 第6 章总结了研究内容与结果，并对未来的研究方向做了展望。 江南大学硕士学位论文 第二章f p g a 基本结构和布局布线 2 1 前言 f p g a 的灵活性主要归功于其架构上具有可编程逻辑和可编程互联逻辑。f p g a 的 架构对器件速度、有效面积、功耗有很大影响。f p g a 高效的c a d 辅助开发工具也是 f p g a 受欢迎的原因之一。作为后文布线算法的基础及鉴于布线在f p g a 流程中的地位， 本章首先按可编程互连点( p i p s ) 的综合组建及实现技巧对f p g a 进行简单的分类，并 介绍相应的结构特征。接着重点介绍了一种基于s r a m 的f p g a 的详细结构特征及相 应的布线结构模型，并描述了基于f p g a 的整个设计流程。最后阐述了本文的布线基准。 2 2f p g a 的编程工艺 f p g a 是以二进制比特流配置实现电路的。根据不同的比特编程工艺，f p g a 可分 为不同类型。下面介绍基于静态随机存储( s r a m ) 【2 7 】、熔丝或反熔丝型【2 s 】、e p r o m 2 9 】、 e e p r o m t 3 0 1 以及f l a s h 3 1 1 配置比特的f p g a 。这些工艺均在商业化f