（电路与系统专业论文）蚁群算法在深亚微米vlsi电路绕障碍布线问题中的应用.pdf

电子科技大学硬士论文 y 7 g s s l 彳 蚁群算法在深亚微米v l s i 电路 绕障碍布线问题中的应用 ( 硕士论文) 学位申请人：刘良萍导师：虞厥邦教授 ( 电子科技大学) 摘要 f 当前集成电路产业向深亚微米工艺不断推进，正力图突破1 0 0 n m 大 关。现有e d a 工具难以应付复杂度呈指数增长的诸多v l s ! 设计难题，也 缺乏对深亚微米工艺下一系列新问题的考虑。另一j j 面，在计算智能领域， 各种优化技术日新月异，为解决非n p 和n p 复杂度的大规模、超大规模问 题展示了广阔的前景。在我国2 l 世纪初的“十五计划”里，明确地把软件 产业和集成电路产业作为中国高科技的两大重点发展方向。本文正是在这 样的背景下基于四川省科技厅基金项目，研究计算智能方法在深亚微米 工艺下性能驱动v i , s i 生产工序中关键环节物理设计中的应用。 随着v l s i 的工艺向深亚微米的推进，物理设计中的布线问题f ( 无论 是非n p 问题、n p 完全问题和n p 困难问题j ，由于问题规模的急剧增大。 都迫切衙要更有效的优化算法解决方案。本文我们就物理设计中b b l 模式 刘良 l f f ：蚁群苒法在踩业微米v l s ! 也i ! 苦绕障碍市线f a j 题t p 的应用 f 典型的两端绕障碍伽线问题，茸先提f l jr 解决小m 条件下实际问题的两 种理论模型，模型分别丛于图沦和汁算儿何学方法，减少j ，问题的u 、空复 杂度。然后，介绍了一种基于生物仿生特性的蚁群算法，通过选择适当的 模型表述该算法可采用蚁群任务调度策略，模仿蚁群的协同学习机制 米解决两端绕障碍的布局面i 线问题，并能给f l l 较优的解。最后探讨丫蚁群 算法用于开发性能驱动优化布线软件的可行性。 廷键词：v l s r 物理波i f v 深妲微米i ：业f i 钟：智能、绕障碍矾i 葩幽论 模型：蚁群系豌、性能驱动、计算几何v 电f 科技大学坎j ：论史 a p p l i c a t i o n o f c o m p u t a t i o n a l i n t e l l i g e n c em e t h o d s i np h y s i c a l d e s i g n f o r d e e p s u b - m i c r o nv l s ic i r c u i t s a u t h o r ：l i a n g p i n g l i u a d v i s o r ：p r o f j u e b a n g y u a b s t r a c t n o wi n t e g r a t e dc i r c u i t i n d u s t r y i s e v o l v i n gr a p i d l yi nd e e ps u b m i c r o n t e c h n o l o g ya i m e d a to v e r c o m i n gt h eb a r r i e ro fw i r ew i d t ha t1 0 0 n m t h i st r e n d h a sp u tg r e a tc h a l l e n g e sf o rt h e r e c e n t l y a v a i l a h l et o o l so fe l e c t r o n i c d e s i g n a u t o m a t i o n o n eo ft h e c h a l l e n g e s i st h a tf o rv l s ic i r c u i t s ，m a n yn p h a r d p r o b l e mi si m p o s s i b l eo rv e r yd i f f i c u l tt ob es o l v e du s i n gt r a d i t i o n a lo p t i m u m a l g o r i t h m s ；t h eo t h e ri st h a tm a n yn e w a n ds p e c i f i cd e e ps u b - m i c r o nt e c h n o l o g y p r o b l e m sh a d n o tb e e nc o n s i d e r e d w h i c hw i l li n f l u e n c ec h i p s p e r f o r m a n c e a n da tt h es a m et i m e ，i nt h ef i e l do fc o m p u t a t i o n a li n t e l l i g e n c e ，an u m h e ro f o p t i m i z a t i o nt e c h n i q u e sh a v es h ( ) w nt h e i rg r e a tp o w e ra n dp o t e n t i a li ns o l v i n g l a r g e s c a l ec o m p l e xp r o b l e m s i n “t h e t e n t hf i v e y e a rp l a n ”o f c h i n a s o f t w a r ei n d u s t r ya n di ci n d u s t r yw e r es e tt ob et h et w om o s t i m p o r t a n tf i e l d so f c h i n e s eh i g h t e c hd e v e l o p m e n tp r o g r a m s u n d e rt h i sb a c k g r o u n da n ds u p p o r t o fs i c h u a ns c i e n c ea n dt e c h n o l o g yb u r e a u f o u n d a t i o n ，t h i sd i s s e r t a t i o ni s i n t e n d e dt or e p o r ts o m eo fo u rr e s e a r c hr e s u l t so n p e r f o r m a n c e - d r i v e np h y s i c a l d e s i g no ft h ev l s i c i r c u i t sb a s e do nc o m p u t a t i o n a li n t e l l i g e n c em e t h o d o l o g y i j 刘良拌；蚁群算法枉摊亚微米v l s i 电路绕障蝌市线问艟中的肢用 w i t ht h e r a p i dp r o g r e s s 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 ，m o s to ft h e t r i n gp r o b l e m sr a i s e di np h y s i c a ld e s i g no fv l s ic h i p s ，w h a t e v e rt h e ya r e t n ph a r d ，n p c o m p l e t eo rn p d i f f i c u l t ，a r ed e m a n d i n gm o r ee f f i c i e n tr o u t i n g o r i t h m s t h i sd i s s e r t a t i o ni s m a i n l yd e v o t e dt of i n das h o r t e s tp a t hb e t w e e n od i s t i n g u i s h e dp o i n t sa m o n gr e c t i l i n e a ro b s t a c l e su n d e rb b l m o d e f o rb o t h i d e da n dg r i d l e s sm o d e l t w ok i n d so fg r a p h i cm o d e lb a s e do ng r a p h i c t h e o r y i d c o m p u t a t i o n a l g e o m e t r ya r ep r e s e n t e d t h en e wm o d e l sa r e ：c a p a b l eo f g n i f i c a n t l yr e d u c i n gt h es p a t i a l t e m p o r a lc o m p l e x i t yo ft h er o u t i n ga l g o r i t h m s h e na ne f f i c i e n t r o u t i n ga l g o r i t h m ，i n t e n s i f i e da c s ( a n tc o l o n ys y s t e m ) i g o r i t h m 。i sp r e s e n t e di nt h i st h e s i s b yu s i n gt h em e c h a n i s mo fc o o p e r a t i v e a r n i n ga n dw o r k i n g t h ea c sa l g o r i t h ma l l o w su st or o u t en e t sy i e l d e df r o m a f o r e m e n t i o n e d g r a p h m o d e l s e f f i c i e n t l y f i n a l l y ，p e r f o r m a n c e 。d r i v e n , u t i n ga l g o r i t h m sw i t hp h y s i c a lc o n s t r a i n t sb ya p p l y i n ga c sa r ed i s c u s s e d i e yw o r d s ：p h y s i c a ld e s i g no fv l s ic i r c u i t s d e e ps u b m i c r o nt e c h n o l o g y c o m p u t a t i o n a li n t e l l i g e n c e r e c t i l i n e a ro b s t a c l e s ，n e tr o u t i n g g r a p h i cm o d e l ， a n t c o l o n ys y s t e m ( a c s ) p e r f o r m a n c e - d r i y e n r o u t e r , c o m p u t a t i o n a lg e o m e t r y 电f 科技火学硕：t ：i e 文 第一章引言 1 1 发展e d a 的战略意义 1 1 1i c 的发展历史 当今信息时代，信息技术( i t , i n f o r m a t i o nt e c h n o l o g y ) 技术作为强大 的社会生产力，红推动经济发展、社会产业结构和生活方式的变革中的作 用日益增长。i t 产业足2 0 世纪以来展最为迅速的产业，其核心和基础是集 成电路( i c 。i n t e g r a t e dc i r c u i t ) 产业。i c 1 i 仪改变着以i f 箅机和通汛为代表 的整个现代电子一i ：业，l ：t ! t 被称为现代：i ：业的“食粮”。据报道，世界国民 生产总值的增值部分的6 5 与i c 有关，i t 和i c 的发腱水平已经成为衡量 一个国家综合国力的重要标志，我困l c 产、l p i l ：处1 t - l m 速发展的前夕为加 强基础性制造业的建设。枉2 0 世纪9 0 年代就启动r “9 0 9 ”。l ：程。2 1 世纪 初的“十五计划”里! ，蜓足明确地把软p l ：产业和集成电路产业作为l 】国高 科技的两大重点发展力向。日前上海、北京等地已经陆续建立了微电子产 业基地，正在由o 3 5 p m 向0 2 5 p m 、0 1 8 p m 的设计技术和o 2 5 p m 的 ，l ! 产线水平发腱。i 国际i - 为抢i j 这一产业制高柱的争夺战更足此起彼伏。 从国防尖端到 i 常生浙，i c 所带来的变革与冲i 打足墩具影响力的技术革命。 自从1 9 5 8 年集成电路( i c ) 诞生以米，已经历了小规模集成( s s i ) 、 中规模集成( m s i ) 、大规模集成( l s i ) 的发展阶段，日前已进入超大规模集成 ( v l s i ) 和特大规模架成( u l s ! ) 阶段，址一个系统架成( s y s t e m o n c h i p ”) 的时代。以最酱遍的个人i f 算= 机微处理器为例，第一代1 6 位的8 0 8 6 芯片， 共容纳了2 8 万个晶体管，到r3 2 位以i 二的8 6 系列微处理器( 如“奔腾) ， 刘良萍：蚁群算法在深亚微米v l s i 电路绕障碍问题中的应用 ：占片内的晶体管元件数已经高达5 0 0 万以上。同前商业化半导体制造技术 的主流已逐渐跨过0 2 5 u r n 的线宽限制正向0 1 8 u r n 过渡并试图突破0 i u m 即i c 已进入深皿微水( d e e ps u b - m i c r o ) 的工艺时代。 1 1 2e d a 发展的迫切需要 l c 技术迅速向符更离集戚度、超小型化、高性能、高可靠性的方向发 展。长远来讲，一个芯片l z i i r 集成高达几亿、甚至；t , - t 亿个晶体管，目前 v l s i 正力图突破1 0 0 n m 大关。v l s i 技术的飞速发展使得它面i 瞄着史无前 例的技术挑战，包括。l ：艺技术和生产技术( 殳备和材料) 和设计生产牢等 诸多方词问题。一方面c a d ( c o m p u t e r a i d e dd e s i g n ，计算机辅助设计) 的 发展，尽管目前已进入第三代一e d a ( e l e c t r o n i cd e s i g na u t o m a t i c ) ，一般还 是要落后于工艺进展；另一方面随着v l s i 的复杂性越来越高，其设计已 愈来愈依赖于先进的e d a 工具和先进的设f | | 方法。 传统的优化算法i l i f i i i 临着i f 算量爆炸、容易陷入局部极值和无法接近 全局最优的难题，而各种计算智能优化方法的迅速发展为解决随问题规模 丽剧增的复杂问题提供了崭新的思路和广阔的前景。所以研究在深亚微米 工艺下计算智能方法的性能驱动的v l s i 的e d a 工具中的应用，无疑是十 分必要、十分适n 寸的，具有重要的战略意义。 正是在这样的背景下，与“十五计划”相呼应，在开发大西部的倡导 下，在范明钰博士后的中国博士后基金课题基础上，电子科技大学光电子 技术系5 7 0 教研室e d a 课题组申请到了四川省科技厅的 1 0 9 门) 时的诸多非n p 、n p 完伞问题、n p 困难问题已成为当务之急。 1 4v l s i 深亚微米工艺的发展趋势与e d a 技术发展 e d a 工具的，f ：发小断向设汁前端发展着。在工艺、算法：结构三者中， ：l ：艺足电子设 f i f i 最f 跃的因索，最终的物理实现更是与：i ：艺密切相关。 从推动设汁方法学的匹新i f = 新i ：艺推动新的 殳”方法产生。近十年来随 着工艺以每3 年一代的速度朝深弧微米( 0 1 斗m 0 5 斗m ) 方向的迅速发展， 物理设计也d l 原来的版闱设i f 一+ 设汁分析、验证与可制造性一h d l ( 硬件 描述语言) 的逻辑综合和优化系统设计一发展到系统集成( s y s t e m o n c h i p s o c ) 。v l s i 的朝向1 0 0 n m 的突破势头，为e d at o o l 设计带来r 史无前例 的机遇和挑战。其| l i 与物理设计密切相关的部分概括如下： 1 )设计模式以互连为中心： 对深弧微米v l s i 而青特征尺寸不断缩小。器件本身的时延不断 减小i f | i 连线k 度、街度迅速增j j | i 。连线时延和线问窜扰也将成为 影响电路性能的蘑要阏素。v i s i 设计将从以器件中心的模式，逐 步过度到器件与连线井雨，并以瓦连为1 1 1 心的设计模式。 2 )设计目标以性能优化为核心： 物理设计将从使版图面积最小化的单一闷标，不得不转向在面积和 设计竞争能力的各项性能指标：速度、功耗、信号完整性和成品率 等之间寻求平衡。 3 )设计模型不断演变： 多层工艺和系统集成( s o c ) 已成为了v l s i 发展的必然趋势，单 一的网格模型已难以满足新的需求，各种更优的设计模型和数据结 构应运而生如超立方体、无网格模型、角勾链结构等都是极有潜 力的新途径，有待大力发展系统深人的研究。 电子科技大学明士论文 以互连为中心的发展趋势使得本来就在v l s i 物理设计中占重要地位 的最短路径( s h o r t e s tp a t h ) 问题显得更加重要起来。而在实际的布线过程中， 线网数只会是越来越多，除了必须考虑线网需要满足的电学、工艺要求外， 还要考虑实际布线环境的影响，即绕障碍问题。因为在v l s i 布线设计中， 金属布线层上的电路元件，已经布好的互连线。甚至待连接的电路端点都 可看作是障碍如何去绕过这些障碍找到互连的路径或对今后布线最有利 的路径，并达到总线长及时延的最小化，则正是我们所面临的难题。可以 说，实际布线的过程也正是绕障碍并寻找线网最短路径的过程。传统的布 线算法的时空复杂度随着v l s i 的规模变得非常之大，已经满足不了工艺发 展的衙要，另外在性能优化方面有时也难于达到许多日新月异的布线性能 要求，而计算智能优化方法的迅速发展，为解决随问题规模剧增而复杂度 剧增的问题提供了崭新的思路和广阔的前景。本文就是对一种计算智能优 化方法基于仿生机制的蚁群算法在物理设计布线中的绕障碍寻目标路 径问题进行应用研究。 在v l s i 芯片设计中积木块( b b l ) 模式布线问题已越来越受到重视。 b b l 模式的布线区比较复杂，通常要先把它们划分成矩形的通道区。然后 再按一定次序逐个进行布线。b b l 模式既具有布图密度高和布图灵活的优 点。又具有自动设计的高效率的优点它是一种很理想的设计方法，总体 来讲。其布图算法和布图系统较其它设计方法复杂。对于在b b l 模式下的 面向两端线网绕障碍寻目标路径问题将是本论文关注的重点问题。 1 5 论文完成的工作和内容安排 电子科技大学光电子技术系5 7 0 教研室的e d a 课题组，现专注于研究 计算智能在深甄微米v l s i 物理设计中的应用问题。本文工作研究的是v l s i 9 刘良萍：蚁矸算法在深亚徽米v l s i 电路绕障碍闸腰巾的应用 物理设计巾布线阶段的问题。对面向两端线网的绕障碍寻目标路径问题， 首先提出了解决不同条件下实际问题的两种图论模型，模型基于计算几何 学方法和图沦，较大氍度的减少j 问题的时夺复杂度。然后，提出了一种 艇于生物仿m 特性的蚁群竹= 法，该箅法通过选扦适当的模型袭述和蚁群任 务调度策略，模仿蚁群的协同学习机制，来解决两端线网绕障碍司闷标路 径的布线问题，f ：得到较优的解。最后探讨厂蚁群算法用于性能驱动优化 的可行性。 论文内容安排如一f ：第二帝介绍了v l s ! 物理 殳i f 的常用的些传统和 汁算智能布线算法；第三章探讨了绕障碍寻目标路径的有关布线问题的现 行研究情况，并详细介绍了蚁群算法的原理；第四章提出绕障碍网格化布 线的连接图解决方案；第f i 帝进一步提 l i 绕障碍无网格布线的路径图解决 方案，最后探讨了蚁群算法用于性能驱动优化布线问题的可行性；第六章， 总结与展望。 0 电子科技大学硬士论文 第二章v l s i 物理设计的算法介绍 有很多通用的算法和数学技巧可用于物理设计( 布图设计) 的算法开 发上。在布图设计中，我们面对着的处理对象是v l s i 芯片上的几万直至几 千万个图形，算法的时间和空间复杂度是布图设计的重点，因为哪怕是二 次方量级的算法都有可能是无法实现的。如果遇到的是n p 一困难问题，则会 对算法提出了更新更高的求。 本章介绍了一些布围设计中常用的基本算法，其中包括图论算法、计 算几何算法等，它们是新算法发展的基础和思路来源的重要部分；另外对 把新旧算法结合起来并采用计算智能的新的优化算法也作了概要介绍。 2 1 图论算法 很多v l s i 布图问题都归结于图论问题，因此图论算法在布图中有着广 泛的应用。常见的有图搜索、最短路、最小生成树和斯坦纳树算法。 2 1 1 田搜索算法 很多图论中的问题都与图搜索有关。例如从一个图中找树、网络的关键 路径、求最大延迟等都需要搜索树，最常用的搜索算法有深度优先搜索 ( d f s ) 、广度优先搜索( b f s ) s j 拓扑搜索( t s ) 等。它们的搜索都是一科，递归过 程，其策略是把后继点按照某种优先度放在集合中，然后“尽可能深”或 “尽可能广”的去搜索图，算法复杂度均为o ( i v j + i e 0 ，其中i v | 为节点数。 l e l 为边数。这种“尽可能深”或“尽可能广”的搜索思想是种很基础的 图论解决问题方案。著名的l e e 氏算法及其改进算法形成了系列的布线 刘良捭：蚊酣算法在深弧微米v l s i 电蹄绕障碍问题巾的应用 算法，统称为迷宙算法。l e e 氏算法及改进箅法形成的刚于线网布线的迷 宫算法系列其核心就足广度优先算法。 2 1 2 量短路径 很多v l s i 布| 冬i 殳i f t i ，的布线问题都足与一个特殊图上的最短路径 ( s h o r t e s tp a t h ，s p ) 柯火( 1 j m 题。闪此最短路径苒法在布线巾占有熏要地位。 有三类最堆小的最短路径问题：币点对最短路径( s i n g l e p a i r s h o r t e s t p a t h s p s p ) i h i 题，| 丫1 源点最短路径问题( s i n g l e s o u r c es h o r t e s t - p a t h ， s s s p ) l l 全点对最短路衽( a j i p a i r s s h o r t e s t p a t h a p s p ) i ) i j 题。迷宫算法首次 在v l s ! 布局布线i ：g l l 成功应用，就是用来求解荦点对最短路径( s p s p ) 。 随着v l s l 超大规模化和村i 应的e d a 的研究发展最短路径的概念已 经有了更深一层的涵义，它不仅指点与点之问的实际物理距离，还被抽象 成符种意义上二的权承：如费用，性能或性能综合指标等。最短路径的算法 研究不仅要考虑问题规模带来的算法复杂度问题。还要同时考虑实际应用 i i i 对性能要求越来越商的符项优化指标和约束条件。 2 1 3 最小生成榭 最小生成树( m i n i m u ms p a n n i n gt r e e m s t ) i 司题是一个边选择问题。它 的定义如下： 定义最，j 、生廖树：给定一个具有边权的图g = ( v e ) 选择一个边集 合e 的子集e 0 ，使得构成一棵树，并且其边的总费用。即w t ( e ) 最小。其 i | i 毗r e j 足边e 的赞川或权限。 电子科技大学磺士论文 有三个基本求解m s t 问题的算法：b o m v k a 算法、k r u s k a l 算法和蹦m 算法，其算法复杂性为o ( m l 0 9 2 n ) 。 2 1 4 斯坦纳( s t e i n e r ) 树算法 最小生成树( m s t ) 和单点对之间最短路( s p s p ) 问题是两种边选择问题。 它们的求解时间复杂度为多项式的，但这两个问题的变形最小斯坦纳 ( m i n i m u ms t c i n c rt r e c s m t ) 问题却是一个n p 困难问题。s m t 在v l s i 布 图中有着广泛的应用，多端线网的总体布线和详细布线都涉及到求解斯坦 纳最小树问题。 定义最小斯坦纳树：给定一个带边杈的图g = ( v e ) 和一个e 的节点 子集r ，选择一个点集合v 0 ( v 0 足v 的子集) ，使得r 是v d 的子集、并 且由v 0 构成一棵最小费用的树。其中r 是要求斯坦纳连接的节点集，v o r 是斯坦纳点集。 当r = v 时，s m t 等价于m s t ，当i r i = 2 时，s m t 等价于s p s p 。由 于s m t 是一个n p 困难问题，通常采用启发式算法求解，上面提到的k r u s k a l 算法和p r i m 算法也可用于来求解s m t 。 2 1 5 其他田论算法 另外的一些图论算法还包括：在布图设计的布局、引线端和走线道分 配等问题中有着重要应用的匹配算法；与图的顶点集划分有关的最小割和 最大割算法；以及在划分、分配和布线中有着广泛应用的最大网络流、最 小费用网络流算法，等等。 刘良萍：蚊群苒法在深证傲米v l s i 电路绕障碍问题中的应用 2 2 计算几何算法 2 2 1 计算几何算法简介 一 汁算几何足刈儿何外形信息的表示、分忻干综合，它足数学和i f 算机 科学相交叉的l j 订f 学科。 在v l s i 的版| 冬| 波l f l l 足要把僻个兀f ，l ：的电路表示转换成儿何表示。 同时元件问的连线也璎被转换成几何连线图形。冈而汁算儿何算法在版图 设i l 里应用较多。 2 2 2 扫描线算法 扫描线算法是一个典型的汁算几何算法，它的基本思想是对平面上按 横坐标或纵坐标排序的线段进行扫描，寻找其在各种条作下的线段或线段 延伸线交点。它可以求一条或n 条线段的所阿交点 扫描线算法已经柱版图验证巾得到rj “泛的应用，是其他版图验证算 法的基础另外它还可_ r f j 于v l s i 版图的设i f 规则检查、版图的拓扑运算和 布尔运算。近来把它的算法思想用在建市| 哥沦模型的分析研究也卓有成效。 2 2 3 线探索法 寻找连接源点及目标的路径，可以应用迷宫算法。但是其时间和空间 复杂度较高，由h i g h t o w e r 在1 9 6 9 年、m i k a m i 和t a b u c h i 在1 9 8 6 年分别 提出的线探索法，其基本思想就是根据障碍，用线探索的方法减少存储空 间和计算时间，其时空复杂度均为0 ( l ) ，l 为算法所产生的线数。 如果在布线区内存在许多规则的障碍物，那么就需要较多探索线才能完 成探索任务。在这种情况下探索线不一定采用汽线，而可以采用u 形或 电子科技大学磺士论文 z 形的探索线。当布线区中不规则图形增多h 寸，迷宫算法就比线探索法优越。 近年来，出现了一种图论框架的计算几何算法思路，本论文中布线问 题即两端绕障碍寻目标路径的布线问题的转化，就是基于计算几 何算法基础上建立的图论模型。 2 3 基于运筹学的算法 运筹学根据解决问题的主要特征分为两大类，一类为确定型，包括：线 性规划、整数规划、动态规划、非线性规划等；另一类为概率型，包括： 回归分析、决策论、排队论、马尔可夫链、蒙特卡罗法和模拟退火等。 2 4 计算智能优化算法 布图实质上是一个寻找最优解的过程。而寻找优化问题的优化解可以 转化成对合法构形空间的搜索问题。许多v l s i 物理没 f 问题都可归结为 n p - 复杂度的优化问题。随着v l s i 向深亚微米推进，系统规模扩大，问题 空间维数随之剧增。传统优化算法要么面临计算量爆炸( 如穷举法，线性 规划等) ，要么易陷入局部极值，无法接近全局最优解( 如最速下降，贪心 法等) 。因此研究近代许多行之有效的计算智能优化算法，如神经网络、模 糊逻辑、演化规划( 含遗传算法) 、仿生算法，以及把各种算法相结合后用 于v l s i 电路物理设计领域中，就是极富挑战性的课题。 这里先简要介绍一些常用的计算智能优化算法。 2 4 1 神经网络算法( n n a ) 在4 0 年代，人f d x , t 智能问题开始感兴趣。人工神经网络( a r t i f i c i a ln e u r a l n e t w o r k ，a n n ) 最初的研究动机正是模拟人脑神经括动。以m c c u l l o c h 为 刘良萍：蚁群算法在睬亚傲米v l s i 电路绕障碍问题中的应用 首的一批神经生物学家通过模拟神经活动来模拟人类的大脑工作机理。 而另一条路线是f 1 1h e r b e r ts i m o n 和a l i e nn e w e l l 倡导的在7 0 一8 0 年代取得 了很大成功的逻辑路线。后山于a n n 研究自身的弱点，曾受到m a r v i n m i n s k y 和s e y m o u rp a p e r 等人的悲观论点的沉l l i = 打击。直到8 0 年代，当人 工橱能的基于逻辑的路线遇到很大困难，并转而求助于新提出的p d p ( p a r a l l e ld i s t r i b u t e dp r o c e s s i n g 并行分布处朋! ) 模删之后，a n n 才重新引 起注意。 1 9 8 2 美国加州理i ：学院生物物理学家l t o p f i e l d 挺f l j 了h n n 模型。他引 入“i f 箅能斤t 甬数”概念给f l i 了网络稳定忭判据。1 9 8 4 年h o p f i e l d 设计 与研制了他所提出的a n n 模型的电路，并提出网络r l l 每一神经元可用运放 实现，所有神经元连接可用电子线路模拟。这一方案为a n n 工程实现指 明了方向，同时他也进行了应用研究，成功解决了复杂度为n p 的旅行商问 题( t s p ) j r 拓厂a n nj f j 于联想记忆和优化 f 箅的新途径。从事并行分 布处理的科学家，如h i n t o n ，s e j n o w s k y 等于1 9 8 5 年对h o p f i e l d 模型引 人随机机制提出了能获得全局最优的b o l z m a n 机。但是统计模拟退火 ( s t a t i s t i c a ls i m u l a t e da n n e a l i n g s s a ) 继承了m o n t ec u r i o 法固有的慢收敛速 度和高计算复杂性。鉴于此，近年来国内外专家、学者提l 了用平均场理 论逼近法。即平均场模拟退火( m f a ) 算法训练b o l z m a n n 机类a n n ，收 到较好效果。所有这些算法大都是建立在统计物理中系统自由能减少的概 念之上的。 细胞神经网络( c n n ) 是1 9 8 8 年由美国加州l e o no c h u a 教授提出 的一种网孔型神经网络。它的局部互连性非常有利于用当前的v l s i 芯片实 现。大量研究和应用纺果表明，c n n 非常适合于一大类图像及图形处理问 题。而求图中环路就足布图设计中经常要遇到的一个问题。因此可以预料 6 电子科技大学硬士论文 c n n 在这一类问题中是有应用前景的。 2 4 2 遗传算法( g a ) 5 0 年代末6 0 年代初，一些生物学家基于进化理论，开始利用计算机对 生物遗传系统进行模拟。1 9 6 2 年，美国m i c h i g a n 大学h o l l a n d 教授及其学 生提出了遗传算法( g a ，g e n e t i ca l g o r i t h m ) 的基本思想：利用类似自然选 择的方式设计计算机程序。6 0 年代末，形成了g a 的模式理论及数学框架。 h o l l a n d 认为群体搜索方法要优于当时普遍的单个结构到单个结构的方法。 一一 1 9 7 5 年，h o l l a n d 出版了( a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m ) 引起 了大量学者对g a 的广泛研究兴趣。目前，g a 作为实用而有效的优化和搜 索方法广泛应用于计算机科学，工程技术，社科领域，已成为国际学术界 跨学科研究热点之一。 2 4 3 模拟退火( s a ) 模拟退火思想是1 9 5 3 年m e t r o p o l i s 等人提出的。m e t r o p o l i s 等人给出了 固体退火过过程中物质内部状态变化的模拟算法，这一工作属于统计物理 学的范畴。s a 是一种非常简单而且有效的通用随机优化方法。不仅在离散 的组合优化问题上有广泛应用前景，而且同样可应用于求解连续多变量最 优化问题。它将组合优化问题与统计力学中热平衡问题类比，开辟了求解 组合优化问题的新途径。 该算法实质是对多极值非凸函数，通过设置温度参量，并按正比于温度 的概率接收比现行解较差的解，以跳出局部极值。该温度参量由高温向低 温下降的过程中，整个进程在状态空间由随机搜索向确定性搜索转化，从 而使整个进程接收较差解的可能性越来越小，直至最后收敛到最优解。从 理论上来说，它可以达到最优解，但是要达到最优解，温度必须下降得足 刘良伴：蚊群算法在探亚微米v l $ 1 电路绕障碍问题中的应用 够慢，日每个温度下迭代的次数足够多这样一来就使得收敛的速度慢， 但它的各种改进以及与其它方法的结合得到了_ 大最广泛而深人的研究。 由s a 所秘来的随机优化思想已渗透到f j l 乎各种新的优化技术i | 了， 如前面所述的b o l z m a n n 机，均匀场退火遗传算法以及下面将要重点讨论 的蚁群算法，无一例外地都作檗利t 程度i ：采j f ir 随机搜索的优化机制。 2 4 4 蚁群算法( a c sj 蚁群算法是近年来发展迅速的一剃，仿生算法。1 9 9 7 年d o r i g o 和 g a n b a r d e l l o u 攮予 - 5 虫1 5 仍巾算法体系发展而成心用此法求解t s p 问题 获得了较遗传算法，模拟退火及进化规划为优的结果。该算法是模拟蚁群 通过协同学习高效寻找食物源这一生物行为的随机搜索算法。它区别于 g a ，s a 等算法的最大特点之一是将已搜索空问的历史经验和优秀可行解 问的栩百影响巧妙i i i i 分布式地存储在解夺问的符独市分最巾不同可行解 信息被整合后反映在同一条边权信息中，具有很高的空间存储效率和高效 的蚁群信息交换机制。这些特点表明它是一种很有前途的优化方法。但对 它的研究才刚刚起步，其成果还远远不及g a ，s a a n n 等那么丰富。 本文所依托的项f = j ，就足从事计算智能算法在v l s i 物理设 i 的应用 方面研究的。我们借鉴了生物界巾蚂蚁觅食的仿生特性，提出了将其应用 到求解v l s l 布图布线问题的优化算法。本论文的工作是把仿生机制的蚁群 算法应用于解决v l s i 砀理设i f 巾的两端绕障碍寻目标路径的布线问题。 木文将在第i 书1 1 1 详细介绍绕障碍寻同标路径的布线问题研究现状 和蚁群算法的原理。 电子科技大学硪士论文 第三章绕障碍寻目标路径布线问题的研究现状 及其求解的蚁群算法 3 1 绕障碍寻目标路径布线问题的研究现状 3 1 1 绕碍耳目标路径布线问题现状 绕障碍寻目标路径布线问题，就是在一个平面上，给定一组障碍和两 个不同的端点，求满足一定优化目标的这两个端点间的一条路径。这在许 多领域都是一个非常重要的问题：如器人的运动规划。城市交通路径规划， v l s i 布图设计( l a y o u t ) 等。本文讨论的“绕障碍寻目标路径布线问题” 的障碍，指的是在v l s i 布线中只由水平和垂直线段组成的规则多边形障 碍。在v l s i 领域内，随着布线环境、优化目标函数的发展变化，求解该问 题时应注意的要点可概述如下1 2 ”。 i b b l 模式既具有布图密度高和布 图灵活的优点又具有自动设计的高效率 的优点，是一种很理想的设计方法，总体 来讲，其布图算法和布图系统较其它设计 方法复杂，所以目前绕障碍布线问题的研 究多半是针对b b l 模式进行的。图3 1 绕障碍的阿点最短路径问题 2 在单层布线模型中，连线路径的总长度通常被做为优化目标它主 要影响着布线的费用和总时延；与此同时。连线上的拐点数目也影响着电 路阻抗从而影响着额定时间和电压的准确值。在双层定向布线模型中，拐 9 刘良萍：蚁群算法在探哑傲米v l s l 电路绕障碍问题中的应用 点数成为了一个m 要的i j 察闪为一个拐点就意味着一个过孔，而过孔越 多将不仅带来更火的m 抗值和更高的制造费用还将降低巨连的可靠性。 张实际订i 线一l i ，璎怂i 川寸最小化路径k 度和扔点数r 1 儿甲足不可能的 只能是寻找“最好路径”：或只优化一个参数或限定一参数值而对另一参 数进行优化。 3 和实际的竹i 线过张i i i 金属锕线层l ：的电路元件，已经布好的互连 线，捉至待连结的电蹄端， 邯有作足障碍。如果已经连好的线被发现可以 被穿过或重布却只需付f i j 较小代价或者障碍可以被穿过，只要折算出相 应的代价。那么给障碍j j i ii ：表示不同代价的权艰。i l 算总布线代价时就将 包括这些额外的代价 4 两层或多层n i 线模型一l i 我们限定每一层l ：布线的方向来简化问题。 连线长度最短和拐点数| 最少足期望的优化日标，这跟v 1 3 i 设计中实际布 线的情形有砦不符，i i 随荇v l s i 的规模增大此差别将1 1 益明显。通常每一 布线层的材料足不同的如金属层、硅层电流在金属层一1 - 的传输速度远 远快：j ：往砘层1 ：。i ) 4 此分j j i j 对每一层1 ：予路径线进行最小化以及加强硅层 子路径长度的晟短化具有明硅的实际意义。从发展的角度来看最小化连 线路径的实际总时延而非实际总线长度，将具有更好的优化效果。 3 1 2 绕障碍寻目标路径布线问曩的算法研究 就布线对象来说，布线问题可分为面向线网布线和面向区域布线。面 向区域的布线主要是以布线区域作为考虑对象，如两边通道布线和开关盒 布线。而面向线网的布线主要以线网作为考虑对象，如总体布线和区域布 线都属于而向线网的布线。区域布线就是在一个区域内( 可多层) 进行布 线。它常常以一种顺序方式布线。本文所研究的绕障碍寻目标路径布线问 题，就属于区域布线类型。该布线问题同前已经有了一些算法解决方案， l a 予科技大学硬士论文 如迷宵算法、线探索n f 线、甲而 r i 描法、罔沦办案、波的端法以及动态搜 索法等，对此可分别简介如f ： 3 1 2 1 迷宫算法 狸最韧的、常规的v l s i 佑线没汁1 1 1 布线环境是f f l 垂直和水平线组成 的网格的平面。因此，两端线网的布线n u 题，可看成足在一有网格的平面 巾求两端点之间的绕障碍的最短路径，其l f i ，路径和障碍均由垂直和水平 线奎l l 成。迷宵算法( m a z er u n n i n ga p p r o a c h ) 是最早j 1 1 = j ：求解有网格平而的两 点之问最短路径n q 题的竹：法。 m o o r e 在1 9 5 9 l ：捉厂迷寅的最短路径的算法，也就是b f s 算法。l e e 于1 9 6 1 年首次成功运用于布图设i f t f ，网格市线的两端布线，实际是图论中 最短路径问题f f j l , i z j l j j e 赁。法思想也可描述为对波传导过程的模拟。图2 1 所示为l e e 氏算法的一个例子。所有与源点栩邻的网格点被标为“l ”并扩 展，除了被障碍物( 模块) 所占有的点外所有扩展的点被标为“2 ”并继 续扩展。这个过程一陌进行到i 标点被标记或者无法再进行扩展为止。k e 氏算法能保证找到这条最短( 如果存在) 的路住，可以说是具有极强的绕 障碍能力，足一利t 最雏本的算法。 656789 54567 89 _ _ _ _ _ _ _ _ _ _ 43456 789 356789 23456789 lsl23456 _ t 1 61 71 8 1 92 02 l2 22 3 1 51 31 0987 2 4 1 4sl234 5 6 t 陌3 2l e e 氏算法的两点线网竹i 线 罔33s o u k u p 的对l e e 氏算法的改进算法 型垦苎!些壁苎堕壅堡垩丝鲞垡! 皇堕塑壁堡! ! 曼! 塑瘗旦 l e e 氏算法的时间和窄问复杂度为d f ，i j 最坏情况的复杂度为o ( 1 2 j 其巾n 和，1 分别为网格的高和宽方向上的网格数，f 为网格点数。此后虽有 ，| ：多对该算法的改进来挺尚j - f l f i l l 及减少j e i f 箅复杂度，如s o u k u p 定向搜 索策略、双向填数策略、预1 胃= 扩展外框策略、以及定义新的波扩展代价优 先度( 扩展代价：f ( c ) = c o s t ( s ，c