（微电子学与固体电子学专业论文）可编程ip核布图方法研究.pdf

y 6 5 2 3 1 1 摘要 现场可编程门阵列 ( f p g a )是八十年代中期出 现的新型可编程逻辑器件。 通过编程，可以把一个通用的可编程逻辑器件配置成为用户需要的硬件数字电 路， 从而大大加快电 路产品的研发周期， 降低研发成本， 缩短电子产品的上市时 间。随着 s o c技术的进步，可编程片上系统 ( s o p c )的发展日益得到人们的重 视。在s o c中嵌入 “ 可编程i p核” ，不仅可以降低开发s o c的风险，而且其可 重配置的灵活能力提供了将同一芯片用到不同应用中去的机会， 尤其适用于不断 变化和发展标准的产品开发中， 例如通讯和网络芯片产品等， 有效地缩短了产品 的开发和上市时间，并降低了产品的升级成本。 一套高效的c a d系统是使用可编程i p 核的必要条件。 和普通可编程逻辑器 件的c a d系统不同， 由 于可编程i p 核的供应商需要根据客户的需要， 定制各种 规模、结构不同的i p 核，所以可编程i p核的c a d系统处理的对象更加灵活。 可编程i p 核结构的灵活性， 对相应的c a d系统提出了新的挑战。 本论文提 出了 一 套适用于可编 程i p 核的 布图 系统p r p i c ( p l a c e m e n t a n d r o u t i n g s y s t e m f o r p r o g r a m m a b le i p c o r e ) ， 该 系 统 对 可编 程i p 核的 结 构 进 行 抽象 建 模， 并 根 据该 模 型生成用于布图的实际电路的有向资源图， 从而可以灵活地支持规模、 结构不同 的可编程i p 核。 在布图算法方面， 本文也根据可编程i p 核结构和应用等方面的 特殊性进行了优化。本文提出了能够处理多种布线资源的非线性拥挤度目 标函 数， 能对布局后的线网可布性做更精确的预测， 并利用改进的模拟退火算法来完 成硬模块、 软模块和简单模块的混合布局， 使布局的规模大大降低，同时充分利 用了可编程 i p核中的快速进位链等特殊结构。同时提出了兼顾布通率和时延驱 动的改进型迷宫布线算法，能够有效的支持可编程i p核中丰富的布线资源，从 而得到高质量的布图结果。 实验结果证明，p r p i c布图系统提出的一系列方法能够有效的改善布图 效 果，同时它的正确性和实用性也在实际的硬件系统中得到了验证。 关键词:可编程i p 核、现场可编程门阵列，布图、布局，布线 ab s t r a c t 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 s ( f p g a s ) , a n e w p r o g r a m m a b l e l o g i c d e v i c e , w a s i n t r o d u c e d i n 1 9 8 5 a n d h a v e b e c o m e o n e o f t h e m o s t p o p u l a r i m p l e m e n t a t i o n m e d i a f o r d i g i t a l c i r c u i t s . f p g a s c a n r e d u c e t h e n r e ( n o n - r e c u r r i n g e n g i n e e r i n g ) c o s t , d e s i g n r i s k , t i m e - t o - ma r k e t a n d m a i n t e n a n c e c o s t o f e le c t r o n i c s y s t e m . a s t h e c o m p l e x i ty o f s y s t e m - o n - a - c h i p ( s o c ) d e s i g n in c r e a s e s , t h e a b i l i t y t o m a k e p o s t - f a b r i c a t i o n c h a n g e s t o f ix e d s o c c h i p s w i l l b e c o m e m o re a n d m o r e a t t r a c t i v e . t h i s a b i l i ty c a n b e r e a l i z e d u s i n g e m b e d d e d p r o g r a m m a b l e i p c o r e s . a r e c o n f i g u r a b l e s o c c h i p c a n a c c o m m o d a t e l a s t - m i n u t e c h a n g e s w i t h o u t c h a n g i n g t h e c h i p d e s i g n , c a n i m p l e m e n t t h e c u s t o m e r - s p e c i f i c p o r t i o n o f s e v e r a l c u s t o m e r s a n d c a n e a s i l y c h a n g e b u i l d - i n t e s t c i r c u i t s . a n e f f i c i e n t c a d s y s t e m is d e s ir e d f o r u s i n g p r o g r a m m a b l e i p c o r e s . o t h e r t h a n t h e c a d s y s t e m o f f p g a s , t h e a r c h i t e c t u r e s o f p r o g r a m m a b l e i p c o r e s a r e m u c h m o r e fl e x i b l e . s o t h e c a d s y s t e m o f p r o g r a m m a b l e i p c o r e s h o u l d h a n d l e v a r i o u s a r c h i t e c t u r e s o f i p c o r e s . t h e fl e x i b i l i ty o f t h e p r o g r a m m a b l e i p c o r e b r i n g s a b o u t m a n y c h a l l e n g i n g t a s k s t o i t s c o r r e s p o n d i n g c a d s y s t e m s . t h i s t h e s i s i n t r o d u c e s a p l a c e m e n t - a n d - r o u t i n g c a d s y s t e m , n a m e d p r p i c ( p l a c e m e n t a n d r o u t i n g s y s t e m f o r p r o g r a m m a b l e i p c o r e ) , t h a t i s s u i t a b l e f o r p r o g r a m m a b l e i p c o r e . p r p i c s y s t e m b u i l d s a s t r u c t u r a l m o d e l f o r d i f f e r e n t p r o g r a m m a b l e i p c o re a r c h i t e c t u r e s . t h e n p r p i c c a n b e p e r f o r m e d o n t h e b a s e o f d i r e c t e d p 优化时延特性的映射将尽量减少信号经过的逻辑单元的数目。 布局阶段将各c l b和i o p a d放到适当的位置。一般情况下，由于可编程 逻辑器件布线资源的有限性， 布局阶段的优化目 标首先是布通率， 通道密度的均 匀性。 但是实用中还有一些其它问题要考虑。 例如用户对某些路径的时延提出限 制， 或指定一些线网的重要程度， 或要求管脚锁定。 这样布局算法就要综合考虑。 自 然， 各种约束条件和布通率之间是存在矛盾的， 怎样兼顾各方面的要求又能最 大程度的提高布通率是一个很值得研究的方向。 布线阶段实现c l b之间的连线。布线要求百分之百的布通率，否则就是布 图失败。 因为可编程逻辑器件布线资源的特殊性布线资源都己 确定， 布线实 际上只是确定哪些编程点接通而哪些不接通。 由于可编程逻辑器件布线资源的有 限性和多样性， 其布线算法也有特殊性， 与普通的布线算法有很大的不同， 相应 的也有许多值得研究的问题。 布线完成以后，各路径的时延值才能最后确定。这时，需要进行时序验证， 以检查电路在有时延的情况下工作是否正常。 如正常， 进入下一步编程下载; 如 不正常，需仔细检查各相关点， 找出问 题所在， 用适当的方法解决 ( 如加入时延 约束、 关键线网、 调整线网的重要程度、 指定某些逻辑单元的位置， 或人工干预， 拆除某些线网、 移动某些逻辑单元， 重新布线) 等。 这样的修改可能要反复多次。 时序验证确证无误， 即可进行编程下载。 通过编程器将编程信息固化在可编 程逻辑器件的某种存储介质上。 时延约束和其它约束 ( 如管脚位置约束等) 将根据需要， 在设计的各实现阶 段产生作用。 1 .3可编程i p 核的应用 随着s o c技术的进步， “ 可编程片上系统 ( s o p c ) ”的发展日益成为重要的 潮流。在s o c中嵌入f p g a核，不仅可以降低开发s o c的风险，而且其可重配 置的灵活能力提供了将同一硅片用到不同应用中去的机会， 尤其适用于不断变化 和发展标准的产品开发中例如通讯和网络芯片产品等有效地缩短了 产 品的开 发和上市时间 w a n g 0 4 。 目 前国 外己 有s o p c 产品。 例如a l t e r a 公司2 0 0 0 年发布了基于a r m和mi p s的e x c a l i b u r 系列产品，将微处理器、可编程逻辑、 存储器集成在同 一芯片中， 实现了 可编程片上系统 ( s o p c ) ; e a s i c公司 e a s i 的2 5 0 0 0 门的e a s i c o r e 模块， 将s r a m查询表f p g a单元和金属掩膜编程连 接用于片上系统( s o c ) 的设计， e s p ( e m b e d d e d s t a n d a r d p r o d u c t ) 产品q u i c k d s p 采用预布线a s i c和f p g a相融合的技术，使之兼有a s i c的经济、高速、高效 性和f p g a的灵活性。 此外， x i l i n x 公司也推出了与其f p g a相应的专用i p 核。 a 1 如2 0 0 0 年x i l i n x 公司与加拿大x e n t e c 公司联合发布用于v e r t e x - e 和s p a r t a n - i i 现场可编程门阵列的新产品a l l i a n c e - c o r e x i l i ， 该i p 核包括正反余弦变换和 一个j p e g编码器， 可应用于图像存储、 数据和影像压缩、 医学成像及工业系统。 a lt e r a 公司 还开发了多种宏核 ( m e g a c o r e ) a l t e 。 其中f f t宏核可以 为用户 提供快速准确的f f t运算芯片级实现方法，其性能可以和专用f f t芯片相比。 据i n s e a r c h 公司统计和预测， 全球嵌入式f p g a市场正逐年递增， 1 9 9 9 年为2 5 0 万美元;2 0 0 1 年为4 3 8 0万美元;2 0 0 2 年可达到 1 .6 4 7 亿美元;2 0 0 4 年将达到 1 1 . 8 3 亿美元 e e t i o i / o 如 g a n d i n t e r f a c e c i r c u 妞 行一业 e m b e d d e d ip p r o c e s s o r 一， co r e : 厂i co r eco r e 娜 珠 公 甲 叹布挤产沪一 川 手方研 书丫 户 吻 n - c 吩 p m e 功 劝 八i p c0 比 袱扮 programmableipcore 川 鳍 澳 羚 图1 .2可编程i p 核应用实例 图1 .2 是嵌入可编程i p核的一个实际的设计例子 wi l t 0 1 。 芯片中 包括一 个处理器i p核、一个存储器 i p核、几个其他固定功能的i p核以及一个可编程 i p核。 在s o c设计中嵌入可编程i p 核， 可以 为设计带来许多 优点 h a l l 0 1 o 冷 在 i c设计领域，尤其是通讯这种协议、规范不断发展、创新的领域， 芯片的设计需求常常会变化。而 i c设计周期长、投资大，对于需求变 化缺乏有效的反应手段。如果将可编程i p核嵌入 s o c的设计，用可编 程 i p核实现需求可能改变的部分，这样就可以满足设计需求的改变， 减少产品上市时间。 令 由于可编程i p 核的灵活性，将可编程i p核嵌入设计，厂家就可以用同 一种芯片方便的、 低成本的提供不同特性的产品， 以满足不同用户需要。 而且由于可编程 i p核可以现场编程，这样就方便了产品日后的升级。 如果芯片在功能上有问题， 也可以对原芯片进行修正， 而不用回收处理。 今 随着i c设计技术的发展，芯片规模的增大，芯片的测试成为一个难题， 芯片内 建测试电路受到人们的重视。如果在芯片中嵌入可编程 i p核， 可以方便的根据测试需要编程下载不同的测试电路， 方便的进行芯片内 测 试。 这 样 不 仅可以 提高 测 试效 率、 减 少测 试 代 价， 而 且 将大 大 节省 测 试 i oo 由于嵌入可编程i p核的这些优点，所以可编程 i p 核预计将在通信及网络、 数据处理、消费类电子产品等领域得到广泛的应用。 1 . 4主要的研究工作和内容 由于可编程 i p核的供应商需要根据客户的需要，定制各种规模、结构不同 的i p核， 所以可编程i p 核的c a d系统处理的对象更加灵活。可编程i p 核结构 的灵活性，对相应的c a d系统提出了新的挑战。 在实际使用的过程中，可编程 i p核将根据用户需要灵活定制，所以要求相 应的c a d系统能够处理结构多变的对象。我们需要提出一个相应的c a d系统 原型，能适应对象的变化。 为了c a d系统能够处理不同结构、 不同规模的可编程i p核， 我们需要对可 编程i p 核进行结构建模， 便于用高级语言描述。 可编程i p核一般规模较小，资源有限，对布图系统的布通率提出了更高的 要求。可编程i p 核为了提高性能或者布通率，一般会在i p 核中增加特殊的可编 程资源，布图系统需要能够充分利用这些资源并有较好的适应性。可编程 i p核 一般不像传统的可编程逻辑器件有非常规则的外形， 内部的可编程逻辑单元、 可 编程布线资源的分布也不一定均匀，这些都是在布图的时候需要考虑的问题。 =奚 集 彭 - 7 $俘堆 l c 珊 八 长线 可编程开关 固定连接点 输出连接 图2 .3宏单元结构 2 . 1 . 2布线资源 芯片的互连资 源采用层次式结构， 分成三个层次。 即: 全局层次的长线( l o n g l i n e ) ， 局 部连线 层次的 可分割长线 ( d i v i d a b l e l o n g l i n e ) 和相邻高 速互连 层次 的短线 ( s h o r t l i n e ) .短线具有最快的连线速度，c l b通过短线可以和相邻的 c l b进行连接。水平和垂直方向上的可分割长线能将可编程逻辑电路核中任何 c l b进行连接，并且其上的分隔开关可根据需要将可分割长线分割为较小的单 位， 提高互连资源的利用效率。 长线提供了大跨距的高速互连资源， 其结构与可 分割长线类似， 但这种固定长度的连线， 贯穿整个可编程逻辑电路核芯片， 不可 分割。引入了长线资源使得可编程逻辑电路核的连线布通率和速度性能得到提 局 . 分层次的可编程互连资源针对实际电路设计中不同层次的连线需求， 分别进 行了优化设计， 能够使可编程逻辑电路核在互连资源利用率和连线速度上获得良 好的表现。 9 ( 1 ) 短线结构 图2 .4 ( a ) 短线结构的逻辑连接关系 固定连接 可编程连接点 l c输出 l c输入 图2 .4 ( b ) 短线结构的电路实现 短线提供了一种专用的快速连线方式， 可在一个c l b和与其相邻的c l b间 ( 共有八个相邻c l b )进行连接，逻辑连接关系如图2 .4 ( a )所示。为了实现 这样的连接关系，设计了短线连线的电路结构，如图2 .4 ( b )所示。 由于可编程连线上编程开关越多， 可编程连线的时延越大，因此短线的结构 中为了提高连线速度， 每条短线只需通过一个开关控制。 另外因为短线连线长度 最短， 所以短线互连是层次式连线结构中信号时延最小的互连资源， 能实现最快 的信号传输。数据通路电路 特别是阵列式数据计算电路)的电路布局很规则， 信号主要都是相邻电路模块间的传递。 短线资源为布局规律性高、 信号传输局部 性强的数据通路电路提供优秀的性能支持，能很好地满足数据通路应用的要求。 而短线资源在实现一般的组合逻辑应用时，能实现高扇出、快速的组合逻辑。 ( 2 ) 可分割长线 可分割长线呈网格状结构，提供了跨若干个 c l b的可编程连接，结构如图 2 .s 所示。 c l b的输入端和输出端在水平和垂直方向上各通过一个可分割长线连 线盒与一组可分割长线连接。 两组相交的可分割长线在彼此相交处用可分割长线 开关盒相连。 一组可分割长线包括s 根可分割长线。 在同一个方向上， 相邻的可 分割长线单元可以用一组可编程分割开关控制相互的连接或断开， 这样获得所需 长 度的连线，将芯片内任意两个c l b之间用可分割长线连接。而通过可编程分 害 开关将整条可分割长线划分， 根据线网连接的要求形成合适长度的连线段， 这 不仅可减少连线的时延，而且还可提高连线的利用率和连线编程的灵活性。 图2 . 5可分割长线连线方式 ( 3 ) 长线结构 长线提供了高速，大跨距的连线结构， 它的结构和可分割长线比较相似，不 同的是长线的长度贯穿整个可编程逻辑电路核芯片， 并且以 宏单元 ( mc )为单 位进行连接。 每个宏单元水平和垂直方向各对应一组 ( 包括4 根) 长线， 长线通 过长线连接盒与宏单元中的一组水平可分割长线和一组垂直可分割长线进行连 接。 水平长线和垂直长线的相交处， 用一个长线开关盒进行连接。实现跨若干个 mc的信号连接时， 使用长线能减少连线中通过的可编程开关的数量， 从而提高 连线的性能。长线的结构如图2 .6 所示 ve n l c a l l o n g l in e - 一 一 今 一- h o r iz o n ta l l o n g l i n e / / 一 s ep nra b le l o ngl in e s e p a r a b l e l o n g l in e , m a 亡 门c e l l e 一 一wi n , 4 x 4 l c 图2 . 6长线结构 2 . 1 .3可编程i / o单元 可编程逻辑电路核的可编程i / 0模块的主要功能为: ( 1 )可编程双向/ 三态1 0 ; ( 2 )可编程输入、输出寄存器 ( 3 )带可编程倒相输入、输出 ( 4 )通过可编程互连资源与阵列中侮一个c l b可以 进行连接 可编程i / 0单元的结构示意图如图2 . 7 所示。 i n d a t a c r g c r o u t d a t a c k 图2 .7 v 0模块结构 2 .2 可编程逻辑器件布图方法 布图( 包括布局和布线) 是可编程逻辑器件编译过程中的重要环节， 也是可编 程逻辑器件的c a d系统中的重要组成部分。 可编程逻辑器件的布局就是当电路被综合并映射到可以放置到 c l b和 i o p a d中的一个个子电路后，根据c l b和i o p a d之间的互连关系将它们放到目 标可编程逻辑器件芯片上的 恰当 位置的过程 w a n g 0 4 。 布局阶段的 输入是一组 可以放置到c l b和 i o p a d中的子电路、子电路对应 c l b和 i o p a d的有效引 线端、以及它们之间的互连关系。 可编程逻辑器件布局问题与a s i c和门阵列的 布局问题非常相似， 所以很多通用可编程逻辑器件布局的算法也直接借用门阵列 的相关算法。由于可编程逻辑器件布局问题的规模比a s i c的规模要小得多， 这 使得那些非常耗时可是能够获得高效布局结果的算法 ( 比如模拟退火法) 的使用 成为 可能 f e w 1 1 . 可编程逻辑器件的布线是当布局阶段确定电路的各个子电路放置到芯片中 的c l b和1 0 p a d位置以后，根据它们之间的 线网 互连关系用合适的 布线资 源 进行 连通的 过程 w a n g 0 4 。 布线阶 段的 输入是 确定 位置的c l b 和1 0 p a d 、 它 们之间的互连关系、 以 及可编程逻辑器件布线资源的详细信息。 可编程逻辑器件 的布线问题与a s i c或门阵列的布线问题有很大的区别，在a s i c或门阵列的布 线过程中， 模块间空隙都是布线区， 可以随时增加布线密度或者加大布线区来增 加走线资源， 而在可编程逻辑器件布线时， 可用的布线资源已经由芯片的结构和 布局所确定， 这样， 布通率就成为一个需要着重考虑的问 题 z h o u 9 9 o 2 . 2 . 1可编程逻辑器件布局算法 可编程逻辑器件布局问题可正式的描述为: 1 、 给定一个代表电 路的超图g ( v , e ) ， 其中v是顶点集 代表c l b 和1 0 p a d ) , e 是边集 ( 代表线网) ， 对每条边e e e ， 其线网 权重w ( e ) e r + ( r + 是正实 数集) 。 顶点 数iv j= n 。 并给定一 个具 有长宽 格点阵 列为r x s的 可 编程 逻辑 器件， 其中r , s e n , n是正整数，同时满足r x s = n o 2 、 寻找一 个放置的 映 射， p:v - - i , r x 1 , s ， 使顶点集v在可 编 程逻 辑器件的格点集上一一对应 3 、 优化，即 最小化某个目 标函数c o s t ( p ) 。 此目 标函数是根据用户的需求对 某些资源费用的评估，比如线网总长最短，时延最小或者它们的组合。 布局的优化是一个典型的组合最优化问题。当完成初始布局后，改善布局总 是在某种优化算法的指导下通过布局迭代而得到的。初始布局一般采用构造算 法， 构造算法的特点理论上只能得到局部最优解， 布局结果不理想， 但速度很快。 改善布局使用得最多的是模拟退火算法， 模拟退火算法是一个非常耗时的优化算 法， 但是它在理 论上可以 得到与最优解充分逼 近的 解 s k i r 8 3 x i n g 9 8 。 在a s i c 或标准单元的布局算法中， 由于布局的目 标一般到门级， 规模常常达到百万门甚 至千万门级， 规模太大而使模拟退火算法耗时不能接受; 而在可编程逻辑器件布 局中，布局的最小目标是 c l b ，而时下业界最大规模的可编程逻辑器件也只不 过十 万c l b的级别，比如x i l i n x 公司的高端产品v i r t e x - 1 i p r o 系列， 其规模也 只不过为3 k到1 2 5 k个逻辑单元 x i l i ， 比同 级别的a s i c的规模要小一到两个 数量级，因此使模拟退火算法在可编程逻辑器件布局中变得可以接受。 模拟退火算法是模拟退火工艺的逐渐冷却过程的一种求解全局最优 解的方法。模拟退火用控制参数 t的一个递减有限序列 t k , k = 1 , 2 , 3 , . . . . , 以及与之对应的链长为 l k 的有限长齐次 ma r k o v链序列去控制算法的进 程，而这些参数的集合称之为冷却进度表。构造冷却进度表的核心概念就 是准平衡，所谓模拟退火达到准平衡。是指若在第k 个ma r k o v 链的l k 次 变换后，解的概率分布充分逼近t = t k 时的平稳分布。理论上己经证明， 算法至少要进行解空间规模的平方次变换才能达到准平衡。显然对准平衡 的任意逼近将导致模拟退火算法的指数执行时间。 t i m b e r w o l f c s e c 8 5 是 一 个 集成的 布 局 布线 工具， 它 可 用于 标准 单 元， 定 制宏以 及门阵列的布局， 是业界最早实现的模拟退火布局算法。 这一算法的中心 思想是基于这样的一个概念:由一个温度参量 t来引导在众多的布局构造中的 探索。 由此来决定这些降低了或减小了布局质量的构造在布局的搜索过程中是否 被接收的概率。 这一温度参量在整个被探索的搜索空间逐渐减小。 首先给出一个 初始布局， 随机选取一个源模块， 然后为这个源模块在约束机制所限定的布局区 域中， 随机确定一个目 标区域， 并且此目 标区域可以覆盖同样类型的模块。 如果 目 标区域已 被占， 则将目 标区域的模块与源模块交换， 然后评估交换后的布局结 果的费用; 如果目标区域本来就是空的， 则将源模块放置于目 标区域， 然后再评 估其费用。 无论是哪种情况， 如果新布局的费用少于交换前的费用， 那么这次交 换就被接收下来。 如果是费 用增加，则交换将按概率e x p ( - d c / t ) 来接受。其中， d c是由交换或移动引起的布局费用的变化， 而t是当前温度。 初始温度一般是 一个较高的温度值， 这意味着在最初的几乎所有的移动都被接收了下来。 随着布 局质量随移动积累而提高， 温度逐渐地降低， 使得降低布局质量的那些移动几乎 不再被接收。 最后， 温度降到足够低， 使得只有改进布局质量的移动才会被接受， 此时退化为贪婪算法。参量 t使得概率具有爬坡能力，从而避免了布局结果落 入局部最优的 “ 陷阱” 。温度下降的速率，在每个温度点的布局的探索次数，模 拟退火算法的结束判据和范围约束机制的行为这些要素都是由冷却进度表来规 定的。 c h a u 9 3 把布局与映 射结 合在 一起， 对电 路进行构造 布局。 算 法从整 个电 路的输出 端开始慢慢回溯到输入端。每完成一步，就考虑下一个 c l b的所有可 能的映射方案， 对每一个映射方案的每一个可能放的位置做出评价， 最后决定取 哪一种映射的哪一个位置。一旦一个 c l b的位置被确定，以后的考虑中就不再 移动位置。算法在评价一个方案时先考虑两个因素:将要形成的c l b包含的电 路数目 和映射包含的电路的级数。前者反映最少 c l b数目的要求;后者反映最 少c l b级数的要求 ( 性能要求) 。 这两个要求是互相矛盾的， 用一个权重系数来 平衡它们在总价格目 标函数中的分量。 此文的映射在布局过程中逐步完成， 考虑 布局的映射肯定会使映射的结果更合理，但是却制约了布局结果的进一步优化， 在实际使用中采用的很少。 v p r ( v e r s a t i l e p l a c e a n d r o u t e ) v a u g 9 7 是一个用 于f p g a布图 研究的 通用 算法，在布局阶段，采用了模拟退火算法。v p r参考并吸收了很多以前的相关 研究的 成果， 提出一 个自 适应退火 ( a d a p t i v e a n e a l i n g ) 模型， 定义每个温度下 交换 ( 移动)的次数， 温度进化的规律，退火结束判据。 首先，对于模拟退火起始温度 t s , v p r根据前人的研究结果，采用下述方 法获得: 设n 6 1o c k 为待布电路的c l b和i o p a d数目的和， 则起始温度设为电路 交换n b i、次目 标函数标准偏差的2 0倍，以 便对于所有在退火初始时刻的所有 交换刚刚能接受。对于每一个温度下交换的次数， v p r也采用已有的研究结果， 即: m o v e sp e r t e m p a ra tu r e 一 in n e rn u m x 伽 b lo c k s r ( 3 . 1 ) 式中i n n e r n u m 是一个布局时间线性调整因子，默认值为1 0 。减小或增大此 值将会有限地影响布局的结果。 对于退火结束条件， v p r 采取下式作为结束判据: : 0 . 9 6 0 . 5 0 . 8 a -0 . 9 6 0 . 9 0 . 1 5 a毛0 名 0 . 9 5 a蕊0 . 1 5 0 . 8 表3 . 1 v p r 温度进化表 容易想象， 当 温度很高， 几乎所有的交换都被接受时，目 标函数的改善并不 明显， 而相反，当温度很底， 接受概率很小的时候，目 标函数的改善也不大， 基 于这样的考虑， v p r 采取了上面的温度进化表。 在计算线网目 标函数的时候， v p r 采用了线性拥挤度目 标函数， 就是不但考 虑线网的长度， 而且考虑线网位置的平均资源费用。 与之对比的是非线性拥挤度 目标函数， 它将整个芯片划分为若干个资源区， 各个资源区根据布线宽度的不同 取不同的费用。 非线性拥挤度目 标函数详细地累加线网范围框覆盖的所有具有不 同资源费用的分区。 线性拥挤度目 标函数如下式所示: c o s t = 艺q ( n ) * ( b b x ( n ) 十 b 竺 y ( n ) q( n ) q( n ) ( 3 3) b b x 和 b b y 分 别表示线网 x 和 y 方向的 幅 度。 c x 和c y 分别表示线网 资 源平均 分布情况。 布线宽度越宽， 值越大。 q ( n ) 是多端线网 补偿因子，它由 下式决定: q ( i) = 1 n u m _ t e r m i n a l s 3 ( 3 . 5 ) 这是对半周长线长估计的一种改进。 最后， v p r 还引入了一个附加参数交换范围因子r , r 用于限定两个待交换 的c l b ( 或者1 0 p a d ) 之间的距离， 也就是说， 当待交换的两个c l b ( 或者1 0 p a d) 的第一个己 经确定的 前提下， 第二个必须在以 第一个c l b( 或者1 0 p a d )为中 心， 边长 为 r * f p g a r a n g e 的正 方形中 选取。 实 验证明， 这种方式比 没 有限制 框 的交换效率要高。v p r 中的r 由下式确定: r ,. i. = m in ( r 0rai .m 一 0 .4 4 + a ) ,1 ) ( 3 . 6 ) r在初始温度时等于 1 ，它保持不变直到。 等于 0 .4 4 ，随后 r逐渐减小，最 后随着温度降 低而使交换只能在相邻c l b( 或者1 0 p a d )间 进行。 从 v p r的线性拥挤度目 标函数中，我们可以得到某种提示:可编程逻辑器 件布线资源 ( 可引中到c l b资源)是固定的，要用足它们为其它要求服务，不 用是浪费。 以前普遍强调的可编程逻辑器件布图走线密度的均匀性实际上只是一 个手段，怕某些布线段被 “ 堵塞” ，而 “ 均匀”本身并不是目的。降低了某一方 面的要求必定会改善对其它方面的满足程度。可编程 i p核的结构比 传统的可编 程逻辑器件灵活的多， 本身的布线资源分布可能就不均匀， 如何确定一个合适的 c o s t 函数指导布局过程，以满足布线阶段的需要，是个需要重点考虑的问题。 2 . 2 .2可编程逻辑器件布线算法 可编程逻辑器件与a s i c或者门阵列的布线有很大的区别，可编程逻辑器件 的 布线是通过选择芯片上合适的 线段和开关资源将互连线网 连通， 与a s i c 布线 时资源可动态分配 ( 通过加大模块间距离) 不同， 这种走线是在有限的资源下进 行的， 所以可编程逻辑器件的布线算法强烈地依赖可编程逻辑器件的结构尤其是 布线资源结构，并且布通率是布线甚至布局开始就必须考虑的问 题 d w i g 9 1 g u y g 9 3 . 可编程逻辑器件布线算法可分为两大类: 基于通道的布线算法和基于线网的 布线算法。 基于通道的布线算法分总体布线和详细布线两步。总体布线借鉴标准元胞和 门阵列设计方法中己较为成熟的总体布线算法， 优化目 标偏重布线的均匀性， 避 免局部走线过密导致布不通。 详细布线算法和标准元胞、 门阵列的算法有很大不 同。 因为可编程逻辑器件布线资源和可编程开关资源己被限定， 详细布线实际上 是为每条连线找出一组可编程开关， 使这组开关连通它们所接的布线段， 构成所 需连线。 可编程逻辑器件详细布线是跨通道的，以线网为单位进行。 选择构成连 线段时为每一条可能用到的线段计算代价函数， 代价函数反映其它线网对被考察 线段的需用程度， 然后在众多可能的构成方案中选取线段代价总和最低的一组线 段。最优解的求解是 n p完全问题，所以必须采用启发式算法降低时间复杂度 h o n g 9 8 o 版图面积的有限性决定了s w i t c h b o x 不可能是全连通的， 即不可能在所有进 入开关盒的线段之间都有编程开关。 这就造成了这样的问题: 在总体布线阶段分 配的走线方向很可能在详细布线阶段不能实现， 即便有空闲布线段， 也没有编程 开关可以连接它们。 一般详细布线以 后通道密度往往大于原先总体布线阶段的设 想，这个在可 编程逻辑器件的布线中是不可接受的。 还有一种基于图 论的 详细布线算法【 y u l i 9 6 ， 适用于 某一类结构 ( 如x i l i n x 公司的x c 4 0 0 0系列) 。这种结构有一个特点: 所有布线资源可以分成若干个子 集， 处于不同子集中的线段永远不可能通过编程管相连， 而同一子集中的线段总 可以通过编程开关相连; 每个子集在每个通道中出现且仅出现一次。 总体布线决 定了每个布线通道内 将走的线网， 在同一通道中出现的不同线网显然不能用同一 子集来布线， 而布线通道不重叠的线网可以共用一个子集。 这样， 布线问题就化 成图论中的装箱问题: 将各个线网装进相当于子集数的箱子， 必须使不能共用一 个子集的线网装在不同的箱子里。 基于线网的 布线 算法【 a m i t 9 4 y a c h 9 3 y u h s 9 7 以 线网为 单 位， 采 用迷 宫算法布线。 迷宫算法的优点是对每一条线网而言， 能求得当时的 ( 针对线网长 度的) 最优解， 且如果存在通路， 总能找到解; 缺点是耗时太大。 所以一般v l s i 设计中总是用迷宫算法来解决其它算法不能解决而遗留下来的问题。 可编程逻辑 器件阵列不大， 迷宫算法得以广泛应用。 这里有两个值得研究的问题: 第一， 能 搜索到更多可供选择的路径方案无疑可以提高优化程度， 但算法复杂度也将随之 提高: 第二， 选择路径的准则将直接影响布线的质量，费用函数应尽可能准确地 估计未布线网的走向， 结合当前资源情况， 做出合理的判断， 使后布的线网容易 布通。 在可编程逻辑器件中不仅要考虑线网长度， 更要考虑众多线网对有限的布 线资源的需求程度。这些是可编程逻辑器件迷宫算法不同于普通迷宫算法之处。 此外， 基于线网的布线算法都无法避免布线顺序对布线质量的影响， 可以单独或 并用以下方法提高性能: 一、 布线之前为线网排序， 精心设计排序算法; 一 二 、 应 用“ 拆线重布” 算法， 通过几个循环的重布使结果收敛于较优解 z h o u 9 9 o c g e s t e p 9 2 是一个著名的 可编程逻辑器件详细布线算法。此算法在详细 布线前把线网都划分成二端线网，并己经过总体布线。将每个二端线网做扩展， 把二端线网从 “ 源”端到 “ 目的”端在指定通道内所有可能的走法都列举出来。 例如一个 c l b的输出端在一个通道内可能有两条布线段可连，这个通道通过 s w i t c h b o x 进入下一个通道时， 这两条布线段通过开关可能与下一个通道内的三 条布线段相连， 这样到此为止就己 有2 x 3 = 6 种走法。 所有二端线网 都做了 扩展以 后， 为每个被用到的线段计算 c o s t 值。 c o s t ( e ) = c f ( e ) + c t ( e ) o c f ( e ) 反映此线段被需求的 程度。 假如此线段被k条线网 用到， 则: c f ( e ) 一 k 1a lt(j) ( 3 石) a l t o ) 表示 在第j 条 线网中， 在e 所在 通道中 可用于 替代线 段e 的 线段数。 a l t o ) 越大， 表示e 被需求的 程度越小。 这样，c f ( e ) 就反映了 从均 匀性角 度对e 的 取舍标准。c t ( e ) 表示 此线段引 起的 信号时延。 把 每条候选的 路径上的 线段的 c o s t 值相加得到这条路径的c o s t 值， 选择最小的c o s t 值，决定当前应选择哪一 个二端线网的哪一种路径布线。 一旦一个二端线网布成， 就删去这个二端线网对 各通道内各线段的需求。重新求各通道内各线段的c o s t 值，再选择一条二端线 网直到所有二端线网都布完。 但任何时候， 如果某二端线网只剩下一种候选 的路径 ( 亦即别无选择)时，首先布这条二端线网。另外，如果对时延有要求， 则加大c t ( e ) 的 权值，即 主要从时延角度来决定取舍。 为了控制时间和空间复杂度， 做扩展时不是把所有可能的走法都列出来， 而 是只取其中一部分， 只有当某一二端线网在现有路径下都布不通时， 再重新做扩 展寻找其他可能的路径。 这是一个直观的、通用性较强的算法， 但正是由于它所处理的问题带有普遍 性， 也就没有考虑被处理的问题的特殊性。 例如对于有特殊连线的芯片， 或对时 延要求较高的场合，它没有对应的优化办法。 v p r ( v e r s a t i l e p l a c e a n d r o u t e ) v a u g 9 7 是 一个用于f p g a布图 研究的 通用 算法，在布线阶段采用了改进型迷宫布线算法。v p r在普通迷宫算法中另外加 入了用于指导布线的资源拥挤度预测， 以提高布通率。 在具体操作上它分两步完 成布线， 首先不管布线资源的重用， 以每条线网的最短路径为目 标对所有线网进 行布线， 计算所有布线资源的重用率， 每个布线资源的重用率作为拥挤度预测指 示而影响下一次迭代时使用此布线资源的费用。 第二步使用撕裂重布的办法进行 迭代重布线。 un c o n n e c t e d , i n k e x p a n s io n w a v e f r o n t r e - e x p a n d a r o u n d ne ww i r e e x p a n s io n wa v e f r o n t r 一， 。 j二 li勺 叭，l ll勺 1日jl甲叫 |口 二飞 aj 尸1曰 l_ _ _ j s ,04 . j j 火 r|j 尸1巨 c u r r e n t p a rt i a l r o u t in g s i n k r e a c h e d ( a ) 波前 扩 展到 达 新 端点 图 2 . 8 : 化 ) 传 统办法， _ 重新 开始彼前扩展 (c) 酚纂 墉鬓薇 v p r迷宫布线时波前扩展办法 为了减少布线耗时， 在v p r布线算法中采取了 两个办法以提高布线的速度。 首先， 线网布线时不允许线网从超过线网范围矩形3 个以上布线通道以外的地方 走线。 其次， v p r对d ij k s t r a迷宫算法作了另一点改 进， 如图2 . 8 ，当 波前到达 一个新端点， 得到这个端点的 连接后， d ij k s t r a 算法会重新开 始波前扩展， 而v p r 采取保留原扩展结果，只将新连线进行扩展的方法。 v p r的布线算法在自己 提出的f p g a结构模型中， 布线结果相当好。但是， v p r采用的f p g a结构模型过于简单，布线资源种类单一。而现代可编程逻辑 器件尤其是可编程 i p核中，结构会非常灵活。对于多种布线资源的混合布线问 题，v p r的布线算法并不适合。 第三章 可编程逻辑器件结构建模方法 3 . ， 可编程i p 核建模背景 一套高效的c a d系统是使用可编程逻辑器件的必要条件。 和普通v l s i 的 c a d系统不同， 可编程逻辑器件的c a d系统往往需要处理一系列或者不同系列 的可编程逻辑器件芯片;另外，可编程 i p核的供应商也需要根据客户的需要， 定制各种规模、 结构不同的i p 核， 所以可编程逻辑器件的c a d系统处理的对象 更加灵活。在