（通信与信息系统专业论文）一种基于线网关键性判别的fpga总体布线算法.pdf

西南交通大学硕士研究生学位论文 摘要 随着千差万别的系统用户提出不同的设计要求，出现了一种新的可以 由用户自行定义配置的高容量密度的a s i c 一用户现场可编程门阵列器 件( f p g a ) ，f p g a 以其高密度、高速率、系列化、标准化、小型化、多功能、 低功耗、低成本，设计灵活方便，可无限次反复编程，并可现场模拟调试 验证等特点，在国内外得到了飞速发展 当前集成电路产业向深亚微米工艺不断推进，f p g a 芯片布线时的面积 约束便成为了影响整个芯片性能的最重要的因素之一，尤其是其关键线网 布线时的布通率和面积约束是一对矛盾体。本文充分利用f p g a 芯片本身具 有的固定的规则的布线资源这一特点，提出在对每一个线网布线之前将待 布的线网进行关键性分析，再根据关键性大小对关键性相对大的线网进行 布线，即n c j ( n e tc r i t i c a l i t yj u d g e ) 算法；此算法有效地在保证芯片 性能的同时，提高了布线资源的利用率，同时考虑到深亚微米时布线时延 是影响芯片性能的一个重要因素，因此充分利用芯片的中长线布线资源以 减少通过编程开关的几率。 本文建立了n c j 算法的布线模型，用c + 十语言实现了基于n c j 算法的 总体布线和s e g a 详细布线的f p g a 布线器，并与目前经典的基于l o c u s r o u t 的总体布线算法和s e g a 详细布线算法的结果进行比较，结果证明了基于 n c j 的布线算法在提高布线资源的利用率方面是非常有效的。 高密度器件的另一个重要问题是相邻线阀的串扰影响，论文还对串扰 进行了定性分析，提出了改进措施。 关键词f p g a ；线两关键性判断；布线资源；布汪率；时延；串扰 西南交通大学硕士研究生学位论文 i l a b s t r a c t an e wk i n do f h i g h - d e n s i t ya s i c ，e g f p g aw a se m e r g e d t o c o p e w i t h d i f f e r e n tu s e r s d e f f e r e n t d e m a n d s h i g h d e n s i t y ，h i g h s p e e d ，s e r i z e d ，s m a l l s i z e ， m u l t i f u n c t i o n ，l o w p o w e r ，c o s t - e f f e c t i v e n e s s ，f l e x i b i l i t i e s i n d e s i g n a r et h em o s t c r u c i a lc h a r a c t e r so fa nf p g a a l s oi td e v e l o p e sr a p i d l yt h r o u g h o u tt h ew o r l db e c a u s e i ti sl i m i t l e s sp r o g r a m m a b l e n o w i n t e g r a t e d c i r c u i t i n d u s t r y i s p r o g r e s s i n gr a p i d l y i n d e e p s u b m i c r o n t e c h n o l o g y t h i st r e n dh a sp u tg r e a tc h a l l e n g e s f o rt h e r e c e n t l y a v a i l a b l et o o l so f e l e c t r o n i cd e s i g na u t o m a t i o n a r e ac o n s t r a i n tw h e nr o u t i n gh a sb e c o m eo n eo ft h ek e y f a c t o r sw h i c hh a sg r e a te f f e c t so nf p g a c h i p s p e r f o r m a n c e s ，e s p e c i a l l yt h et r a d e o f f b e t w e e nr o u t a b i l i t ya n da r e as h o u l db ec o n s i d e r e d c a r e f u l l y t h i sp a p e rt a k e s t h e a d v a n t a g e so ff p g a sr e g u l a rr o u t i n gr e s o u r c e st oj u d g et h ec r u c i a l i t i e so fe a c hn e tt o b er o u t e d ，a i m sa t d e t e r m i n i n gt h er o u t i n go r d e r ，w h i c hg r e a t l yh e l p st oi m p r o v et h e r o u t a b i l i t yb a s e d0 na r e a - c o n s t r a i n e da n dr e d u c et i m ec o s ta tt h es a m et i m e w h e n t a k i n gn e t s h i g hd e m a n df o rd e l a yi n t oa c c o u n t ，t h i sp a p e rt a k e sf u l lu s eo fm i d - l e n g t h s e g m e n t s t h i sp a p e rb u i l d sa nn c ja l g o r i t h mr o u t i n gm o d e l ，t h e ns h o w e sar o u t e rc o n s i s t s o fn c j g l o b a lr o u t e ra n ds e g ad e t a i l e dr o u t e rw h i c hi si m p l e m e n t e db yc + + p r o g r a m l a n g u a g e e x p e r i m e n tr e s u l to f t h a tr o u t e ri sc o m p a r e dt ot h a to fa n o t h e rr o u t e rc o n s i s t s o fl o c u s r o u t eg l o b a lr o u t e ra n ds e g a d e t a i l e dr o u t e r ，a n dt h ea l g o r i t h mb a s e do nn c j a c h i e v e sa ne x c e l l e n tr e s u l ti nt e r m so ft h eu t i l i z a t i o no f r o u t i n gr e s o u c e se f f i c i e n t l y 。 a n o t h e ri s s u ec o u l dn o tb e i n g o r e d i n d e s i g n i n g o n h i g h d e n s i t yd e v i c e s i s c r o s s t a l k sc a u s e db yn e i g h b o r i n gp a r a l l e l s e g m e n g t s t h i sp a p e ra n a l y s e sc r o s s t a l k s n e g a t i v ee f f e c t so nc i r c u i tp e r f o r m a n c ea n ds h o w e ss o l u t i o n sa c c o r d i n g l y k 。yw o r d s ：f p g a ，g l o b a lr o u t i n g ，n e tc r u c i a l i t yj u d g e ，r o u t i n gr e s o u r c e s a r e a c o n s t r a i n t ，d e l a y ，c r o s s t a l k 西南交通大学硕士研究生学位论文 第l 页 第1 章绪论 1 1 课题的背景、意义和目标 i 1 1 大规模集成电路设计与e d a 工具 自从1 9 5 8 年集成电路发明以来。为了提高电子集成系统的性能，降低 成本，集成电路的特征尺寸不断缩小，制造工艺的加工精度不断提高，同时 硅片的相对面积不断增大。4 0 多年来，集成电路芯片的发展基本上遵循了 摩尔定律，即每隔三年集成度增加4 倍，特征尺寸缩小了2 倍。在经历了 小规模集成( s s i ) 、中规模集成( m s i ) 、大规模集成( l s i ) 的发展阶段之 后，目前已经进入超大规模集成( v l s i ) 和特大规模集成( u l s i ) 阶段，进 入一个片上系统( s o c ，s y s t e mo nc h i p ) 的时代。微电子科学技术在短短 半个世纪的时间里已经形成了有一千五佰亿美元的i c 产业，i c 制造的特征 尺寸已达到0 1 3 肛m 及0 1 3 u m 以下，芯片集成度及速度等已至3 t 时代 ( t e r as c a l e ，1 0 2 ) 。 表i - i 目前国际集成系统芯片情况及来来发展预测 年份 1 9 9 92 0 0 22 0 0 52 0 0 82 0 1 02 0 1 4 工艺设计规则 m mo 1 80 1 3o 1 00 0 7o 0 5o 0 3 5 新逻辑占面积的比 6 4 3 21 68 4 2 再利用逻辑面积比 1 61 61 3964 存储器占面积比 2 05 27 18 39 09 4 晶体管逻辑密度m t c m 2 2 05 41 3 33 2 88 1 12 0 0 0 新逻辑产能m t ，p y 1 4 2 ，l2 94 2 6 o8 6 再利用逻辑产能 m t ，p y2 94 ，15 98 41 2 01 7 1 最大功耗( 便携)w 1 422 422 22 4 i 最大功耗( 商性能)w 9 01 3 01 6 01 7 01 7 41 8 3 2 0 世纪9 0 年代初，e d a 技术伴随者计算机、集成电路、电子系统设计 的发展，在经历了计算机辅助设计( c o m p u t e ra s s i s td e s i g n ，简称c a d ) ， 计算机辅助工程设计( c o m p u t e ra s s i s te n g i n e e r i n gd e s i g n ，简称c a e ) 之 后，进入了一个崭新的发展阶段，这一阶段就是以e d a 软件工具为开发环境， 以硬件描述语言为设计语言，以可编程器件为实验载体，以a s i c 、s o c 芯片 西南交通大学硕士研究生学位论文第2 页 为设计目标，以电子系统设计为应用方向的电子产品自动化设计过程。 e d a 工具的主要服务对象是超大规模集成电路( v l s i ) ，怎样对一片v l s i 进行功能划分、行为描述、逻辑综合、时序分析、故障测试、形式验证是 e d a 工具需要解决的主要问题。 1 1 2f p g a 新技术使e d a 工具面临的挑战 随着微电子技术的发展，设计与制造集成电路的任务已不完全由半导 体厂商来独立承担。系统设计师们更愿意自己设计专用集成电路( a s i c ) 芯 片，而且希望a s i c 的设计周期尽可能短，最好是在实验室里就能设计出合 适的a s i c 芯片，并且立即投入实际应用之中，因而出现了现场可编程逻辑 器件( f p l d ) ，其中应用最广泛的当属现场可编程门阵列( f p g a ) 和复杂可编程 逻辑器件( c p l d ) 。 先进的p l d 使设计技术面临新的挑战，p l d 加工工艺已经达到极深亚微 米，在极深亚微米工艺中，互连比逻辑单元对时序延迟的影响要大。传统的 工具和设计流程以逻辑单元来描述时序延迟，因而不能在设计初期描述互连 效应( i n t e r c o n n e c te f f e c t ) ，尽管它们能执行物理模型的自动设计，但 p l d 的互连架构非常独特，对p l d 来说，即使采用经过验证韵a s i c 设计技 术仍不能解决问题，工程师需要的是面向p l d 的全新自动化设计技术，特别 要求p l d 物理综合工具与物理设计工具结合起来，从而实现复杂p l d 设计。 今天的f p g a 最大的瓶颈是时序收敛( t i m i n gc o n v e r g e n c e ) 、f p g a 资 源的预算，对a s i c 和f p g a 综合的控制以及布局布线工具。为突破这一瓶颈， 许多研究人员投入了大量精力进行相关方面的研究，以期用更好的算法进一 步提高f p g a 性能。既然线网连接情况决定f f g a 的面积，既然信号时延依赖 于可用的布线资源，额外通过增加芯片面积而增加可用布线资源得造价太 高，f p g a 生产厂商更愿意在采用合理的布线算法和对最大限度利用布线资 源和保证线网性能方面进行研究。 基于以上原因，成都华徽电子系统有限公司在其多年的集成电路研制开 发经验的基础上，在其研制c p l d 芯片取得突破性避展的基础上，前瞻性地 提出以x i l i n x 公司的x c 4 0 0 0 系列结构作为模型对对称型f p g a 芯片布线算 法进行研究。该论文正是此项目的一部分。 堕堕奎堕奎兰塑主婴里竺兰焦望茎 蔓! 墨 1 2 课题完成的工作 课题主要完成了阻下几个方面的工作： 提出一种基于f p g a 蟊积约束戆布线分拆算法。 创造性地提出基于n c j ( n e tc r u c i a l i t yj u d g e ) 的总体布线算法， 通过对以线网的端点连线为对角线的矩形范围内布线资源可能占 有的情况进行分析，得到一个线网的关键性大小值，以此决定一个 线网的布线顺序。 基于n c j 的总体布线与s e g a 详细布线算法结合起来成为一个完 整的布线算法，通过实现这一布线算法，得到布线线阙关于布线总 体长度、布线资源占有率和布线通遂密度均方值等面积约束布线算 法的相关参数，并且与基于l o c u s r o u t e 总体布线与s e g a 详细布 线相结合的布线算法相关参数进行比较。 分析串扰对深亚微米情况下的f p g a 布线的影响以及相关的预防 措擒。 1 3 论文的组织结构 论文共分为八章，其内容组织如下： 第一章，绪论，阐述课题的背景、意义和目标，以及论文完成的工作。 第二章，不同的f p g a 结构对f p g a 布线的影昀，给出基于面积约束的 对称型f p g a 布线的约束条件。 第三章，介绍对称型f p 6 a 结构布线算法中经典的l o c u s r o u t e 总体布 线算法和s e g a 详细布线算法。 第四章，提出一种应用于f p g a 总体布线的线网关键性判别算法，即 n c j 算法分析过程。 第五章。提出基于n c j 的总体森线算法。 第六章， 实现基于n c j 的总体布线和s e g a 详细布线算法，给出相关 函数及中间过程，给出实验结果数据并对实验结果进行分析。 第七章， 分析串扰对布线算法的影响，并提出算法的优化措施。 第八章，结论。 亘南奎壅查堂塑主婴塞生兰篁笙塞篁! 夏一 - - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ - _ _ 一一 第2 章f p g a 结构对布线的影晌 f p g a 器件起源于美国x i l i n x 公司的制造，在国际上，f p g a 技术至今 仍以x i l i n x 公司为代表。x i l i n x 公司于1 9 8 5 年推出世界上第一个现场可 编程门阵列器件，在之后的二十年时间星，x i l i n x 连续推出一系列f p g a 的 新品种，其f p g a 器件具有十分突出的特色：基于s r a m 构架，可“无限次” 编程；l u t 可配置为分布式r a m , 块r a m 可配置为多种类型的用途；全数字 式的时钟管理系统，可提供灵活精确的时钟信号：v e r s a r i n g 提供了i o b 与 c l b 的连接。可以更便利的实现p i n 锁定；高端产品如v i r t e x i ip r o ， v i r t e x i ip r ox 嵌入微处理器和专用乘法器，功能更加强大等。各系列产 品主要参数见表2 一l 。 表2 - i x jii n x 公司f p g a 产晶主要参数 系统门 电 产品系列 c l b工艺压 ( x ) ( v ) x c 4 0 0 0 e2 “4 51 0 0 1 ，0 2 4 0 6 u m c m o s3 层金属5 x c 4 0 0 0 e x1 8 6 51 0 2 r 1 2 9 6o 。5 u m c i o s4 层金属5 x c 4 0 0 0 x l3 1 8 0 6 4 3 ，1 3 6 0 3 5 u m s r a ms 层金属 3 3 x c 4 0 0 0 x l a3 0 1 8 05 7 6 3 ，1 3 60 3 5 u m c m o s5 层金属 3 3 x c 4 0 0 0 x v2 2 0 5 0 0 4 ，0 9 6 9 ，4 6 4 0 2 5 u m c m o s5 层金属2 5 s p a r t a n 5 “4 01 0 0 7 8 40 5 u m c m o s4 层金属 5 s p a r t a n x l 5 。4 0i 0 0 7 8 40 3 5 u m c m o s5 层金属3 3 0 2 2 u m o 1 8 混合c m o s s p a r t a n i i 1 5 “2 0 0 9 6 i ，1 7 6 2 、5 6 层金属 s p a r t a n l i e5 0 6 0 01 3 8 4 3 。4 5 60 1 8 u m c m o s6 层金属 1 ，8 s p a r t a n 一3 5 0 5 0 0 1 9 2 “8 ，3 2 0 9 0 n m8 层金属1 2 v i r t e x s o 1 ，0 9 83 8 4 6 ，1 4 4 0 2 2 u m c m o s5 层金属2 5 v i r t e x - e7 0 3 9 8 0 3 8 4 1 6 ，2 2 4 0 1 8 u m c m o s6 层金属1 8 v i r t e x - i i 4 0 “8 ，0 0 0 6 4 i l 。6 4 80 1 5 u m c m o s8 层金属1 5 v i r t e x - i ip r o3 5 2 “1 3 。9 0 40 1 3 u m c m o s9 层铜1 5 v i r t e x i ip r ox 2 ，4 4 8 8 ，2 7 2 0 1 3 u m c m o s9 层铜1 5 西南交通大学硕士研究生学位论文 弟5 贝 了不可忽略的地位。 a l t e r a 公司器件系列丰富，产品应用范围广。除了早期型号f l e x 系列 没有内嵌存储器之外，后来的系列都内嵌了存储逻辑块，部分高端产品还嵌 入d s p 或者a r m 微处理器。集成度、性价比都较高，其中以c y c l o n e 系列最 突出。 a c t e l 公司直是世界反熔丝技术f p g a 的领先供应商，其逻辑块之间 的连接是利用a c t e l 专利金属一金属可编程反熔丝内联元素实现的，它是一 种无源的两端常开开关，但加上足够的电压时也能永久闭合。 在研究f p g a 布线算法时，f p g a 提供给布线软件的是逻辑上的模型，这 个模型是从多层物理结构中提炼出来的。对于f p g a 布线而言，对逻辑模型 的研究比对物理模型的研究要相对简单；布线段反殃的只是逻辑连接两非物 理版图，布线段可能由不同金属层上的布线段组成，因此它们可以相互跨越 而不造成干扰。 f p g a 按照编程方式可以分为：一次性编程和可重复编程。一次性编程 型采用反熔丝开关( a n t i f u s e ) 元 牛，具有体积小、集成度赢、互连沮抗低、 寄生电容小和高速度的特点，但只能一次编程，适合定型产品和大批量应用； 可重复编程型f p g a 采用s r a m 开关元件或f l a s he p r o m 控制的开关元件，配 置数据存储在s r a m 或f l a s he p r o m 中，它的突出优点是可以反复编程，参 照图2 1 。 图2 1两种常用的f p g a 编程连接技术 表2 2 给出了目前世界上几家著名的f p g a 芯片生产厂商具有代表性的 f p g a 结构。图2 2 分别给出了这四种结构的具体表现形式以及它们的布线 资源分布，其中( a ) ( b ) ( c ) ( d ) 分别为对称型结构、行排列结构、门海结构和 层次结构。 西南交通大学硕士研究生学位论文第6 页 表2 - 2 商用f p g a 器件结构 公司 可编程结构逻辑模块类型编程技术典型产 逻辑器件 a c t e l f p g ar o w b a s e d m u l t i p l e x e r a n t i f u s ea c t 3 l u c e n tf p g a s y m m e t r i c a ll o o k u p s r a m o r c a 3 a r r a y t a b l e m o t o r o l a f p g ah i e r a r c h i c a lb a s i c s r a mm p a ；0 0 0 g a t e s q u i c kf p g a s y m m e t r i c a l m u l t i p l e x e r a n t i f u s ep a s i c 2 l o g i c a r r a y x i l i n xf p g a s y m m e t r i c a ll o o k u p s r a m x c 4 0 0 0 a r r a yt a b l e s e a - o f g a t e s m u l ti p l e x e r s r a m x c 6 2 0 0 s e a 。o f g a t e s b a s i c a n t i f u s ex c 8 1 0 0 g a t e s 口i | 口口口 口8 | 口口州口 口| i | 口 口哪口 口| | | 口 口口 黯 斡 袖 围2 - 2 四种主要的f p g a 结构 一 堕塑至望奎耋堕主竺塞竺耋堡堡茎里：堕一 2 1对称型f p g a x i l i n x 公司的x c 4 0 0 0 系列是对称型f p g a 的典型代表，其结构如图2 - 3 所示； 图2 - 3 对称型f p g a 结构 对称型结构的f p g a 包含了行和列排的c l b ，水平和垂直的布线通道包 含不同长度的布线段。对称型结构在基于s r a m 编程方式的f p g a 中较为常见， s r a m 单元通过控制连通晶体管( p a s st r a n s i s t o r ) 达到线间互连的目的。 理想情况下，在每一个开关模块( s w i t c hb o x ) 中，对称型结构的f p g a 应 该能够为任何两个布线轨道( t r a c k ) 在交汇处提供一个连按开关；同样， 也应该能够在布线通道( c h a n n e l ) 上为逻辑模块( 1 0 9 i cb l o c k ) 的每个引 脚( p i n ) 与布线通道的连接提供连接开关。 事实上，由于f p g a 的结构越来越紧凑，信号通过晶体管电容性负载等 因素的影响。并非布线通道中酶每一个轨道都能移和逻辑模块的每一个引脚 进行连接，实际的连接情况参见图2 4 ，有短斜线的交叉处表示存在逻辑开 关。 对称型结构的f p g a 所体现出来的特点决定了在布线时将受到一定的约 束。对于待布的线网，布线通道上有限的开关数目限制了逻辑模块各个引脚 到布线轨道之间的连接；开关模块处有限的连接方式限制了详细布线时一个 布线通道与另一个布线通道之间的轨道分配。总之，对称型的f p g a 布线问 题不能够简单地分割为空间问题( 在典型的门阵列布线中，总体布线器总是 将详细布线分成几个独立的问题) 。针对这种结构的布线算法必须要同时考 西南交通大学硕士研究生学位论文 第8 页 虑通道选择和通道中的线轨选取。 a ( a )( b ) 图2 - 4 对称型f p g 中的实际连接情况( a ) 连接模块处( b ) 开关模块处 另一方面，对称型的f p g a 结构具有相当大的灵活性。例如在图2 - 4 ( b ) 中，开关模块中四条轨道中可能的六种连接方式都是相对独立的。开关模块 允许两个信号无相互干扰地跨越一个开关模块，也允许x 型布线，例如，轨 道a 和b 可以连接属于个线网，而轨道c 和d 可以连接形成另外个线网 最后，既然f p g a 的所有布线资源都是预先定义好且固定不变的，根据 已经使用了的布线资源就可以衡量剩余可用的资源。这就为最大程度地利用 布线资源提供了可能，为基于线网关键性判别的总体布线算法的提出提供了 依据。 2 2 行排列f p g a a c t e l 公司的a c t 2 系列是行捧列结构f p g a 的典型代表。行排列结构 f p g a 主要是通过反熔丝实现连接。反熔丝是一种一次性编程器件，大电流 通过时导通。反熔丝尺寸小，电容低，使用较自由f p g a 可以在每一个 水平或垂直线段的交汇处使用。除其尺寸小之外，反熔丝还具有很好的连续 阻抗特性，因此各种分段的通道可以连接构成不同长度的布线通道，这就是 行排列结构的f p g a ，又称为分段通道式的f p g a ，其结构如图2 5 所示。当 然，与前面提到的对称型f p g a 类似，这也是一个逻辑上的视图，而从物理 上来讲，布线通道完全育可能在逻辑模块的上方。 图2 5 显示的分段通道式的f p g a 结构中，布线通道包括每一条水平 和垂直线段交叉点上的反熔丝。另外。小圆圈表示可以连接短的轨道为长 的走线轨道。布线通道中各分段的轨道长度对整个f p g a 系列都是固定不变 西南交通大学硕士研究生学位论文 第9 页 的。为方便使用，人们希望轨道是由各种不同长度的分段轨道连接而成； 然而，虽然反熔丝的电容和内阻很小，但是如果很多反熔丝串接起来的话 就不可避免的会增加线网的布线时延。在一些商用的这类f p g a 结构中，轨 道分段的情况还要受到反熔丝编程情况的限制，所以这类结构的f p g a 器件 上每一个轨道上的分段数是有限制的( 即最多不能够超过某一数值) 。因而 一个轨道总是包括不同长度的分段。而且每个轨道分段模式经常是不规则 的。 烈，口 n 。m t l i i _ 吲 | l l一i l i i | i i l i | f ji | i j i | l i 【 i l i i l il l i i i l i l l i i i il i i lj l i l | j二l ij i l i l il i i l l li l i l一i i l l - 肖。 必 “ i 1 f阡 i - l i f l1 订。汀耐 1 ii i l l l l i i i ll i i l l l | l l l l | l i l一| | | j l | l i l l i l i i ii i i i i l i l i i i i五l i i i l i i | lj | i i | i| l | i l fi i i l l | q ! 一 q 阻o肖： l j 一 l j 一 搬 c l 蛐e l o u t p u tp t m 图2 - 5 分段逼道式的f p g 结构 因为反熔丝尺寸小的特点，几乎所有的交叉点处都可以采用。在这样的 分段通道结构中，布线可以完全从空间上分为总体布线和详细布线两部分， 其中总体布线是指从所有布线通遵中选取一条合适的布线通道，而详细布线 则是在一个通道中选取一条布线轨道。 2 3 小结 从2 1 和2 2 可以看到，f p g a 包括三种类型布线资源：输入输出模块 ( i o b ，逻辑模块和布线通道。i o 容量和逻辑模块的使用情况都很容易度 最，而对布线通道容量的度量却非常困难，因此f p g a 布线算法设计中度量 布线通道的容量及相关参数成为了最重要的问题之一。 西南交通大学硕士研究生学位论文 第1 0 页 第3 章对称型f p g a 结构布线算法介绍 f p g a 的一般布线流程如图3 - 1 所示： 图3 - 1对称型f p g a 布线算法流程 其中，总体布线和详细布线两个步骤是算法流程中最关键的两个步骤。 而且，对称型f p g a 总体布线和详细布线是未能完全割裂开的。 近年来，关于对称型结构f p g a 的布线算法有很多，各种算法的侧重点 和性能优化的方面各有不同。总的来说侧重点主要在于两个大类，类是基 于时间约束”o l ，二类是基于面积约束 9 , 1 l 1 4 l ，也有布线算法同时考虑面积约 束和时间约束 2 2 1 。 无论哪一种算法，只要它的目标相同，刚主要步骤都是类似的。对于基 于面积约束的f p g a 布线而言，主要目标及步骤如下： 1 总体布线。总体布线的目标有两个： ( 1 ) 在目前的布线资源已经被部分占用的情况下，准确地描述对一个线网进 行布线的相对困难程度大小； ( 2 ) 为一个待布的线网描述出一个有效的布线路径图。 2 详细布线。 ( 1 ) 线网分解。将每一个多端线网( k t e r m i n a ln e t ，k 2 ) 分解成若干个 两端线网( t w o t e r m i n a ls u b n e t ) ： 西南交通大学硕士研究生学位论文 第l l 页 ( 2 ) 布线资源分配。 任务：将从第一步得到的两端子线网分配到可用的布线资源中去。 目标：尽可能少地占用布线通道中的轨道数目。同时尽可能少地占用( 或 者说尽可能有效地利用) 连接模块和开关模块的资源。 ( 3 ) 合并 任务；将占用在不同连接模块和开关模块处的布线尽可能地往同一连接 模块和开关模块进行合并。 目标：最大程度地实现资源共享。共享轨道就意味着减少了对可编程开 关的占用( 直接减小线网的布线时延) 和对布线资源的占用。 其中，线网分解可能会在总体布线中完成，也有可能在详细布线中完成， 因为本身f p g a 的总体布线与详细布线并不是能够完全割裂开来的。 由于本文的主要工作在于提出了一种基于面积约束的布线算法。基于面 积约束的布线最终目标是要减少布线的慧体长度，提高森线资源的利用率和 平衡布线通道的密度。在给出本文论点之前先分别介绍一种常用的总体布线 算法l o c u s r o u t e 算法和详细布线算法s e g a 算法。 3 1 l o c u s r o u t e 总体布线算法介绍 l o c u s r o u t e 算法是j o n a t h a nr o s e 于1 9 9 0 年提出来的用于标准单元 布线的总体布线算法1 2 l l 。此总体布线算法是将多端线潮分解成为两端线 网，并为每一个两端线网在布线通道中找到一个最短距离的路径。算法的 主要目的是将线网在布线通道中尽可能的均匀分布以平衡各通道的布线密 度，而且要求路径有尽可能少的拐点，这一目标正好与f p g a 的目标一致。 f p g a 的布线通道的容量是受到严格限制的，且为了更好地利用中长线资 源，也要求路径中有尽可能更少的拐点。p a t e l l 4 0 l 首次将l o c u s r o u t e 算法 应用于门阵列的布线中。 3 1 1 l o c u s r o u t e 布线方法 总体布线器的功能是通过为每一个连接寻找一系列布线通道，并以此 为目标定义一个粗略的布线路径。图3 2 展示了总体布线器为一个连接定 义的路径图。 西南交通大学硕士研究生学位论文 第1 2 页 厂 ? ! 厂 - f 1 j 口 掣i i 型弧 t ： 口田口 !j 口 圈圈 甄k ：j 口口口蹬! 旧 m 舭“ 自- n n ( a ) 坐标图( b ) 粗略图( c ) 扩展图 图3 - 2 总体布线器为连接定义的路径图 在图3 2 中，l ( 0 ，4 ) 所在的模块称为图的根结点，l ( 4 ，o ) 所在的模块称 为叶予结点。根结点和叶子结点在接入路径之前首先要通过一个连接模块 再接入交换模块。 由于总体布线器将所有线网分解成为两端线网，但是一个粗略的布线 路径图却只有一个输出。这就意味着，同一线网的某些连接可能会占有相 同的布线资源，即可能在某些布线通道上会交叉重叠，当出现这样的情况 时，可以通过详细布线中台并此类布线以达到减少布线资源浪费的目的。 3 1 2 l o c u s r o u t e 算法的特点 l o c u s r o u t e 算法有两个重要的特点： ( 1 ) l o c u s r o u t e 算法只寻找那些有一个或两个拐点的路径。如图3 2 ( a ) 就是一条只有一个拐点的布线路径。更多的一个或两个拐点的路径可以参照 图6 7 和图6 。8 。 ( 2 ) l o c u s r o u t e 算法采用迭代布线。即在第一次布线完成之后，所有的 布线均有可能被拆掉重布，一直到达到最佳的布线效果为止( 比如，最小布 线密度，或最小的资源占有率) 。 实验表明，l o c u s r o u t e 算法一般在迭代四次时就可以得到很好的效果， 而两次迭代以后的优化程度就已经很小了。迭代过程中更好地考虑了先布线 嘲 蹴。 “ ” ” 玷 聃 付 0t工vint工vnt工uiyo占 c i c e l c t i t _ 置 西南交通大学硕士研究生学位论文 第1 3 页 网对后布线网的影响，最优结果比首次布线可以优化5 一1 0 。迭代减小了 线网对布线顺序的依赖性，线网根据输入的顺序输出。 3 1 3l o c u s r o u t e 算法实现 l o c u s r o u t e 算法在实现时，是对每一个两端线网按照输入顺序进行布 线，不去考虑先布线网对此次布线线网的影响，也不考虑此次布线的路径选 择对未布线网的影响。在第一次布线完毕后，拆掉那些导致布线密度增大的 线网，重新为其选择路径进行稚线。图3 3 为l o c u s r o u t e 的布线算法流程。 图3 - 3l o o u s r o u t e 布线算法流程 西南交通大学硕士研究生学位论文 第1 4 页 3 2 详细布线算法介绍 目前对详细布线算法研究时，主要有侧重如下两个方面进行考虑。 第一、考虑开关模块容量的详细布线算法； 第二、考虑对不同长度布线段的选取的算法。 3 ，2 1 考虑开关模块容量的布线算法 传统意义上的a s i c 布线，只要是在有效的布线区域内，走线方式可以 是任意的，根据通道的布线密度就可以分析布线可行性。然而，在f p g a 的 布线中，布线可行性不仅要受到布线通道的限制，还要受到开关模块物理结 构的限制( 如图3 - 4 ) 。尽管布线密度没有超过通道的最大值2 ，线网4 由于 开关模块的限制仍然无法布通，因为开关模块1 和3 没有能够上下导通的连 接。 图3 - 4 没有超过通道量大布线容却不可仔的布线方案 对称型结构f p g a 中一个开关点的连接方式有六种，建模如图3 5 所示： 。 爻。x 。 州 斗 一i 木井 图3 - 5 开关模块的六种连接方式 西南交通大学硕士研究生学位论文 第1 5 页 通过开关模块上下端的数目。根据图3 - 5 的六种连接方式定义了六种连接， 分别用t y p e ( 1 i 6 ) 来表示。一个布线需求矢量( r o u t i n gr e q u i r e m e n t v e c t o r ，简称r r v ) 元是一个六维矢量( n l ，n2 ，n3 ，n4 ，n5 ，n6 ) 。则，0 n 1 w l ，o n2 w2 ，o n3 ，n4 ，n5 ，n6 m i n 彬，职) 。对于一个 给定的开关模块和r r v ，n ，表示有n 个第i 种连接方式。此算法认为，如果 开关s 上存在一个亓的布线方式，则认为此r r v 在s 上是可以布通的( 或者 说具有可布性) 。 开关模块的占用是此模块当前已经被占用和将来可能占用情况的函数， 为估计还有多少线网可以通过此模块，分以下几个步骤：首先。计算得到并 贮存一系列极大可布( m a x i m a l l yr o u t a b l e ) 的r r v ，然后衡量这些极大可 布r r v 之间的距离，以及它们与当前待布线网需要通过此开关模块的r r v 之间的距离，以此决定一个开关模块布线资源的消耗情况。 3 2 2 考虑不同的布线段选取方案在f p g a 布线中的意义 图3 - 6 的例子表明选取不同长度布线段在f p g a 布线过程中的重要性。 在图3 - 6 中，a 类布线表示两个c l b 只能够与线轨2 和3 进行连接，b 类布线表示c l b 只能够与线轨1 和2 进行连接，c 类布线表示c l b 只能够与 线轨1 和2 相连接；即此结构的f p g a 只有轨道2 和3 支持a 类连接，轨道 1 和2 支持b 类和c 类连接( 其中轨道1 、2 、3 中间的虚线部分表示需要可 编程开关才能够连通) 。 假设一个布线器先完成了a 类布线。如果在轨道2 上布a 型布线，则b 和c 型的布线必然失败因为8 和c 的布线都必须依赖轨道2 才能够进行。另 一方面，如果a 类布线选择的是轨道3 ，则b 可以选择轨道1 而c 可以选择 轨道2 ( 或b 选择轨道2 而c 选择轨道1 ) 。这个简单的例子表明，即使是一 个简单如三种类型的布线闯题，不合理的布线都会造成布线阻塞。 西南交婆查兰塑主塑窒竺兰堡丝窒 塑! ! 垩 r o u t i n g o p t i o n s f o r c o n n e d i o l la r o u t 旧 o p t i o n s f o r o o n n e d i o nb r o u t i n g o 嘲i o 璐f o r o o n n d l m nc 田田田田 固3 - 6 一个f p g a 布线问题的倒子 虽然以上两种分配方式( a - 3 ，b - 2 ，p l a 一3 。b - i ，c - 2 ) 可以完成三 种布线这一要求，但只认为其中第一种方法( a - 3 ，b - 2 ，c - 1 ) 是合理的。 为b 分配轨道2 丽为c 分配轨道1 ，这样b 和c 郝只需要布线到同一段线轨， 而若为c 分配轨道2 则c 必须要跨越甄条线轨( 比前面的分配方式多跨越一 个可编程开关) 。 3 3s e g a 算法 s e g a ( s e g m e n t e da l l o c a t i o n ) 算法a o l 是一种典型的考虑对不同长度 布线段进行布线的详细布线算法。s e g a 算法可以看成是由其先驱c g e 算法 组阍演变丽来。c g e 算法也获锝了很好的基于面积约柬的布线效果，但是其 局限在于其布线模型中只考虑了单长线( 即短线的布线) ，而改进后的s e g a 算法则在考虑不同长度的布线资源利用方面迈出了非常重要的一步。由于 近年来f p g a 结构中长度不同的布线资源越来越丰富。s e g a 算法被证实为 一种行之有效的考虑对不同长度布线段进行选取的详细算法，在f p g a 布线 中得到了广泛的认可。 s e g a 算法有两个最重要的特点： 第一、保证电路1 0 0 的布通率； 第二、 为不同长度的连接分配不同长度的布线段，合理而有效地利 用布线资源。 西南交通大学硕士研究生学位论文 第1 7 页 3 3 1s e g a 算法模型 圈3 - 7s e g a 算法的f p b a 模型 图3 - 7 为s e g a 算法的模型。 s e g a 算法的f p g a 模型比c g e 算法中的模型更具有通用性。此模型包括 n m 个逻辑模块，水平和垂直的布线通道。逻辑模块的每一边都有都有两 个引脚，每一个布线通道中有三个线轨。通道中有两种模块，一种是开关模 块s ( s w i t c hb l o c k ) ，一种是连接模块c ( c o n n e c t i o nb l o c k ) 。s 模块连 接不同的布线段( 线轨) ，c 模块连接线轨与逻辑模块引脚。 s e g a