（信号与信息处理专业论文）非曼哈顿结构通道布线算法研究.pdf

摘要 摘要 本文论述了v l s i 物理设计中两种基于非曼哈顿结构的通道布线优化算法 研究和实验结果及分析。文中分析了在当前集成电路产业向深亚微米工艺推进， 集成度和电路复杂度不断提高，工艺日益进步的条件下，采用非曼哈顿模型进 行布线时，可以明显减小芯片面积，缩短布线长度，减小串扰等方面的必要性 和可行性，重点研究了以下两个算法： 1 、在分析了基于冒泡排序的非曼哈顿结构通道布线中，由排序结果到布线 段的映射特点的基础上，提出了二分改进优化算法，通过允许在同一排序步骤 中采用不同的交换方向，进一步减小了通道高度( 轨道数) ，减小了总线。跃。 2 、提出了一种采用m d ( 曼哈顿一对角线) 模型的非曼哈顿结构通道布线 贪婪算法。算法“贪婪”的使用最少的布线轨道，并且通过启发式拓扑排序最小 化轨道数和线长，该算法同时适用于规则与不规则通道，还可以不经修改的用 于l 型通道布线。 上述算法均在p c 机上编程实现，并应用于些经典的b e n c h m a r k 布线例 予，实验结果是令人满意的。 关键词：v l s i 电路物理设计、通道布线、非曼哈顿、冒泡排序、 不规则通道、l 型通道 电子科技大学硕士学位论文 a b s t r a c t t h i st h e s i sd e a l sw i t ht w o o p t i m a la l g o r i t h m s o fn o n - m a n h a t t a nc h a n n e l r o u t i n gi nv l s ip h y s i c sd e s i g n n o wi n t e g r a t e dc k c u ri n d u s t r y i s p r o g r e s s i n g r a p i d l yi nd e e ps u b - m i c r o nt e c h n o l o g y , t h es c a l eo fi n t e g r a t i o n a n dt h ed e g r e eo f c o m p l e x i t y o fc i r c u i ti n c r e a s e r a p i d l y , i t i sn e c e s s a r ya n df e a s i b l e t o a d o p t n o n m a n h a t t a nm o d e lf o rc h a n n e lr o u t i n g ，i no r d e rt or e d u c er o u t i n ga r e a ，w i r e l e n g t h e na n d t h u st or e d u c ec r o s s t a l k b a s eo nt h o s eo b j e c tj u s tm e n t i o n e d ，o u rf o c u s i sp l a c e do nt w o a l g o r i t h m s a sf o l l o w ： b ya n a l y s i n g t h ec h a r a c t e r i s t i co ft h em a p p i n gw h i c hf r o ms o r t i n gv e c t o r st o r o u t i n gw i r es e g m e n ti n b u b b l es o r tb a s e dn o n - m a n h a t t a nc h a n n e lr o u t i n g , w e p r e s e n t a d i c h o t o m ya l g o r i t h m t o i m p r o v e t h e o p t i m a l b u b b l es o r tb a s e d n o n m a n h a t t a nc h a n n e lr o u t i n g t h ed i c h o t o m ya l g o r i t h ma l l o w sd i f f e r e n ts w a p d i r e c t i o ni nas a m es o r t i n gs t e p , a n dc a l ld e c r e a s ec h a n n e lh e i ：g h t ( t r a c k s ) a n dw i r e l e n g t h a g r e e d yr o u t i n ga l g o r i t h m f o ri r r e g u l a rc h a n n e lb a s eo nan o b m a n h a t t a n a r c h i t e c t u r ec a l l e dm d ( m a n h a t t a n - d i a g o n a l ) m o d e li s p r o p o s e d t h ea l g o r i t h m g r e e d l y t ou s el e s su a c k s ，a n dm i n i m i z e st h ev i a sn u m b e ra n dw i r el e n g t hb y e m p l o y i n gah e u r i s t ct o p o l o g i cs o r e i td e a l sw i t hb o t ht h er e g u l a ra n di r r e g u l a r c h a n n e lr o u t i n gc a s e s ，a n de x t e n di t sd o i l i t yt ol - s h a p e dc h a n n e lw i t h o u ta m e n d ， w h e r et h ei r r e g u l a rc h a n n e la n dl - s h a p e dc h a n n e lo f t e no c c u ri nb b l l a y o u t t h e s et w oa l g o r i t h m sa r ci m p l e m e n t e do np ca n da p p l i e dt os o m eb e n c h m a r k e x a m p l e s ，t h ee x p e r i m e n t a lr e m i t sa r es a t i s f a c t o r y k e y w o r d s ：v l s ic i r c u i t sp h y s i c a ld e s i g n 、c h a n n e l r d a t i n g 、n o n - m a n h a t a n 、 b u b b l e s o r t i n g 、i r r e g u l a rc h a n n e l 、l - s l 獬- dc h a n n e l i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文扣 作了明确的说明并表示谢意。 签名：丝叁堡日期：删，年r , 9 ，二口 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丝垒堡 导师签名： 日期：i 印舛矿月1 2 日 第一章引言 第一章引言 1 1 发展e d a 的战略意义 自从1 9 5 8 年集成电路( 1 c ) 发明以来，为了提高电子集成系统的性能，降 低成本，集成电路的特征尺寸不断缩小，制造工艺的加工精度不断提高，同时 硅片的相对面积不断增大。4 0 多年来，集成电路芯片的发展基本上遵循了摩尔 定律，即每1 8 个月集成度增加1 倍。集成电路经历了小规模集成( s s l ) 、中规 模集成( m s i ) 、大规模集成( l s l ) 的发展阶段，目前己进入超大规模集成( v l s i ) 和特大规模集成( u l s l ) 阶段，是一个片上系统( s o c ，s y s t e mo nc h i p ) 的时 代。 1 1 1 超大规模集成电路( 、嘲) 是人类社会进入信息时代的重要硬件基础 在当今的信息时代，信息技术( i n f o r m a t i o nt e c h n o l o g y ，i t ) 作为强大的科 技第一生产力，在推动社会经济发展、社会的产业结构和生活方式的变革中的 作用日益增长。i t 产业是2 0 世纪以来发展最为迅速的产业，其核心和基础是 集成电路( i c ，i n t e g r a t e dc i r c u i t ) 产业。据报道，世界国民生产总值的增值部 分的6 5 与i c 有关，i t 和l c 的发展水平已经成为衡量一个国家综合国力的重 要标志。为了加强基础性i c 制造业的建设，以“信息化带动工业化”，我国在 2 0 世纪9 0 年代就启动了“9 0 9 ”工程。2 l 世纪初的“十五计划”里，更是明确地把 软件产业和集成电路产业作为中国高科技发展的两个重点方向。国际上先进的 半导体工艺正被迅速地直接引入到我国，制造工艺技术正在由0 3 5 y m 、 0 2 舡m 、0 1 即m 向0 1 珈m 和0 0 q u m 的生产线工艺水平发展，因此可以说我 国l c 产业已经进入了一个跳跃式发展阶段。国际上为抢占这一产业制高点的争 夺战更是此起彼伏。从国防科技、社会经济到日常生活，l c 给人类社会生产和 生活所带来的变革与冲击是科学技术史上空前的、最具影响力的技术革命。 1 1 2e d a 技术和糖遣工艺支撑着v l s i 的发展 伴随l c 诞生和发展辅助电子产品设计的e d a ( e l e c t r i cl 斌i g na u t o m a t i o n ) 技术是以计算机和微电子技术为先导汇集了计算机图形学，拓扑、逻辑学、 电子科技大学硕士学位论文 微电子工艺与结构学和计算数学等多种计算机应用学科最新成果的先进技术。 e d a 技术以计算机为工具，代替人完成数字系统的逻辑综合、布局布线和设计 仿真等工作。利用e d a 工具，设计人员可以极大的提高设计效率。 v l s i 制造工艺的发展，目前已进展到超深亚微米阶段，可以在几平方厘米 的芯片上以几十纳米线宽的工艺集成数以亿计的晶体管。没有e d a 技术的支 持，想要完成上述超大规模集成电路的设计制造是不可想象的，反过来，生产 制造技术的不断进步又必将对e d a 技术提出新的要求。 1 1 3 物理设计是超大规模集成电路e d a 中重要的一环 物理设计或称为版图设计是整个集成电路设计过程中与产品研制和制造直 接相关的一个设计过程，直接关系芯片设计周期，生产成本和产品质量。现今 物理设计要在几十平方毫米的硅片上设计出线条只有零点几微米且数以百万上 亿计的器件的整个电子系统，这只靠手工设计是完全不可能的，必须借用设计 自动化( d e s i g na u t o m a t i o n ) 或者计算机辅助设计( c a d ，c o m p u t e ra i d e dd e s i g n ) 技术和工具。因此，版图设计是i c 设计中耗时最多，差错率最高的设计过程之 一。它也是近年来e d a 工具中发展最快，自动化程度最高的领域之一。而且， 随着v l s i 电路向深亚微米推进，它也是受工艺影响最大、面临的机遇和挑战 晟大的领域之一。 1 1 4 通道布线是v l s i 物理设计中重要和基本的一环 v l s i 物理设计的输入是电路的元件说明和网表，输出是设计好的版图，即 根据电路和工艺要求完成芯片上单元或功能块的安置，实现它们之间所需要的 互连。其过程包括划分( p a r t i t i o n ) ，布图规划( f l o o r p l a n n i n g ) ，布局( p l a c e m e n t ) ， 布线( r o u t i n g ) ，压缩( c o m p a c t i o n ) 等。 通道布线的基本目标是要在通道内实现指定模块间豹互连。主要的优化日 标是布线的通道面积最小，线长最短，线网间串扰最小。 1 1 5e d a 发展妁逾朝需要 当今飞速发展的电子设计领壤，配技术向着更高集成瘴、超小型化、高性 能、高可靠性的方向迅速发展。长远来讲，一个芯片上可集成高达几亿、甚至 几十亿个晶体管，雷菏v t s i 电路i e 力翔突破6 5 n m 至躺蛳线宽大关。v l s i 电路技术的飞速发展使得它面摘着史无前铆的技术挑战，包括工艺技术和生产 2 第一章引言 技术( 设备和材料) 和设计生产率等诸多方面问题。尽管目前已进入第三代 e d a ，但e d a 技术一般还是要落后于工艺进展；另一方面，随着v l s i 电路的 复杂性越来越高，其设计已愈来愈依赖于先进的e d a 工具和先进的设计方法。 i c 芯片的发展从封装形式来看，芯片体积越来越小、引脚数越来越多。同 时，由于近年来i c 工艺的发展，使得其工作速度越来越高。由此可见，由i c 芯片构成的电子系统是朝着大规模、小体积、高速度的方向飞速发展的，而且 发展速度越来越快。如何在缩小电子系统体积的同时，保持并提高系统的速度 与性能成为摆在设计者面前的一个重要课题。所以研究在深亚微米工艺下性能 驱动的v l s i 电路的e d a 工具中的应用，无疑是十分必要、十分适时的，具有 重要的战略意义。 正是在这样的背景下，与“十五计划”相呼应，在开发大西部的倡导下，电 子科技大学电子工程学院5 7 0 教研室e d a 课题组申请到了四川省科技厅的计 算智能在超大规模集成电路物理设计中的应用科研项目。本文的工作是这个 项目课题延续研究的一部分，主要对v l s i 电路物理设计中的布线问题进行了 探讨。 1 2 物理设计的定义、流程及主要模式和基本问题 1 2 1 v l s i 电路设计流程 v l s i 电路设计过程从给出芯片的设计要求开始，包括了功能设计( f u j l c t i o n d e s i g n ) 、逻辑设计( 1 0 舀cd e s i g n ) 、电路i 发g f ( c i r c u i td e s i g n ) 、版图设计( 或者物 j 里设i - t - - - p h y s i c a ld e s i g n ) 、设计验证( d e s i 印v e r i f i c a t i o n ) 、制造( f a b t c a t i ) 和封 装测试曲c k a g e a n d t e s t ) 等过程【1 】。其漉程如图1 - 1 所示。 划分 上 1布圈搜捌和布局 土 总体布线 土 f详角布馥 图1 - 1v l s i 电路设计及物理设计流程 3 电子科技大学硕士学位论文 1 2 2 物理设计的定义 v l s i 电路物理设计( p h y s i c a ld e s i g n ) 也称为布图设计( l a y o u td e s i g n ) 。 其输入是电路的元件说明和网表( 可用原理图表示) ，输出是设计好的版图，即 根据电路和工艺要求完成芯片上单元或功能块的安置，实现它们之间所需要的 互连。它要把每个元件的电路表示转换成几何表示，同时，元件问的连线也要 被转换成几何连线图形。我们把电路的几何表示叫做版图，而把版图的设计称 为布图。版图设计要符合与制造工艺有关的设计规则的所有要求。 1 2 3 物理设计的流程 如前所述由于布图的复杂性，整个布图过程往往被分成划分、布图规划、 布局、布线和压缩等若干个子步骤，每一个子步骤完成布图的一部分。一个芯 片可以包含数以百万计的晶体管。划分过程将整个电路分组形成多个模块 ( b l o c k ) ，各模块的大小和在芯片上的精确位置由布图规划和布局算法确定。 布图规划和布局算法的目标是最小化芯片的面积同时满足其它约束如模块间的 完全互连等。布局完成之后将进入线网布线阶段。线网布线一般划分为总体布 线和详细布线这两个布线过程，总体布线确定一个线网的大致走线，它将各线 网合理地分配到各布线区域中，以确保尽可能高的布通率；详细布线则最终产 生线网在芯片上的实际走线，及生成各线网的几何版图。布线阶段的任务是在 考虑性能驱动的前提下准确无误地完成模块问的完全互连，其次是在完成线网 布通的前提下作进一步优化处理。压缩的任务是从各个方向上压缩芯片的版图 以期将芯片的总面积减小。布图过程( 见图1 - 1 虚线框内) 是个反复迭代求解 的过程。例如，为了得到一个好的布图结果，需要反复进行总体布线和详细布 线，而后一个步骤的结果又依赖于前一个步骤的结果。一个不好的布局结果一 定不会获得好的布线结果。因此，必须注意布图中各个步骤算法闯目标函数的 一致性，前面阶段的算法要尽可能考虑至8 对后续阶段的影响。 1 2 4 目前物理设计豹囊要粳式 目前芯片的设计主要以下几种常用模式( 既图1 2 ) 1 、标准单元设计模式( s t a a d a r d 硼獭确弹s t y l e ) ：设计者可以上千种标 准单元，这些单元模块已经定义_ 好逻辑符号、拓扑和物理舨雷并存储在单元库 中，其版图具有相同的高度，布线区域在各单元行问。 4 第一章引言 2 、门阵列设计模式( g a t ea r r a yd e s i g ns t y l e ) ：预先设计好的单元具有相 同的宽度和高度，设计者使用这些单元排成门阵列，通过水平和垂直的布线通 道连接单元完成不同的电路功能。 3 、积木块模式( b l o c k b u i l d i n gl a y o u t ，b b l ) ：又称宏单元模式( m a c r o c e l l ) ，是设计中最灵活的一种设计方法。在这种布图模式中，单元或模块可以 有任意的形状和尺寸，可以安排在芯片的任意位置上而且没有固定的布线区域。 4 、现场可编程门阵列( f i e l dp r o g r a m m a b l eg a t e a r r a y , f p g a ) ：是一种 可编程器件( p r o g r a m m a b l el o g i cd e v i c e ，p l d ) ，提供预先设计好的片内功能模 块及垂直和水平通道上的连线资源，用户可以通过编程实现线网连接构筑自己 的功能电路。 基于上述的不同设计方法，设计者可以根据产品的性能、批量和现有的工 艺设备状况，采用混合设计模式和分级设计策略。其中的b b l 布图模式中模块 可以有任意的形状和尺寸，可以安排在芯片的任意位置上而且没有固定的布线 区域。显然，这种布图模式接近人工的设计方法，因此可望得到比门阵列和标 准单元模式更高的布图质量。b b l 布图因为其的灵活性也给设计工具带来极大 的挑战，是我们研究重点。 ( a ) 标准单元( b ) 门阵列 图1 - 2v l s i 物理设计的主要模式 5 电子科技大学硕士学位论文 1 2 4 目前物理设计的基本问题 所有模式中实现互连都是其最终目的。在当今的i c 设计中，随着芯片的集 成度和工作频率的提高、工艺向深亚微米的不断发展，互连线越来越细，互连 线的间距越来越小，给信号的完整性带来极大的挑战。很多v l s i 电路布图设 计的布线问题归根到底都是组合优化问题，其计算和存储空间在v l s i 电路规 模下无限膨胀。其中许多问题已被证明是n p 完全闻题。同时，随着v l s i 电路 技术的发展，传统的曼哈顿互连线结构也在发生变化，近年来迅速发展的非曼 哈顿互连结构，给v i s i 电路的布图设计带来新的机遇和挑战。在考虑性能驱 动的前提下，寻求有效的优化算法以解决诸多非曼哈顿布图n p 困难问题己成 为当务之急。 1 a 深亚微米工艺与e d a 技术的发展趋势 1 4 1 布局布线仍然是塔i 设计自动化中的重要问题 在2 0 0 2 年8 月发布的s r c p h y s i c a ld e s i g nc a dt o p l on e e d s ”中，指出当 前物理设计急待解决的十大问题( “p l a c e m e n ta n dr o u t i n g 、“s y n t h e s i sa n d l a y o u ti n t e g r a t i o n ”、“p o w e rd i s t r i b u t i o nd e s i g n a n da n a l y s i s ”、“h i 曲l e v e l p l a n n i n g a n de s t i m a t i o n ”、“c l o c k d e s i g n a n d a n a l y s i s a b o v e1 5 g h z ”、 “i n t e r c o n n e c t s y n t h e s i s a n d a n a l y s i s ”、“t u n i n ga n a l y s i s a n dv e r i f i c a t i o n ”、 “r e s e a r c hd i r e c t i o n si nc o r r e c tb yc o n s t r u c t i o nd e s i g n ”、“d e s i g na n dv e r i f i c a t i o n s o nm i x s i g n a ld e s i g n ”、“d e s i g nf o re m b e d d e ds y s t e mo n c h i p ) 之中，布局布线 ( p l a c e m e n ta n dr o o t i n g ) 首当其冲，在芯片尺寸和容量上，布局布线要解决面 对几千个大模块和上百万个小模块的电路规模并且在可行帕对问内得到结果。 其它需求中的定时、互连分析等也与布线密切相关。 布局布线的发展方向如下； 1 ) 设计模式以互连为中心：对深亚微米v l s i 电路而言，特征尺寸不断缩 小，器件本身的时延不断减小，而连线长度、密度迅速增加。连线时延和线间 串扰及信号的完整性也将成为影响电路性能的重要因素。v l s i 电路设计将从以 器件为中心的模式，逐步过渡到器件与连线并重，并以互连为中心的设计模式。 2 ) 设计目标以性能优化为核心：物理设计将从使版图面积最小化的单一 6 第一章引言 目标，不得不转向在面积和设计竞争能力的各项性能指标：速度、功耗、串扰、 信号完整性和成品率等之间寻求平衡。 3 ) 设计模型不断演变：多层工艺和系统集成( s o c ) 己成为了v l s i 电路 发展的必然趋势，单一的网格模型已难以满足新的需求，各种更优的设计模型 和数据结构应运而生，如超立方体、无网格模型、角勾链结构等都是极有潜力 的新途径，有待大力发展系统深入的研究。 1 4 2 非曼哈顿结构的迅速发展 1 9 9 1 年，b u r m a n 等【3 】提出了k - g e o m e t r y 理论，完善了有关互连线结构 的理论。连线结构可以概括为传统的曼哈顿结构( 水平垂直布线结构) 和非曼哈 顿结构。新的互连线结构( 如x 、y 结构) 给v l s i 电路的布图规划、布局、布线、 数据结构等带来新的设计方法。4 , 5 ，6 1 等相继提出了各种非曼哈顿结构的布局 布线算法。 以互连为中心的发展趋势和新的非曼哈顿结构使得本来就在v l s i 电路物 理设计中占重要地位的通道布线( c h a n n e lr o u t i n g ) l h 题显得更加重要起来。非曼 哈顿布线结构的引入，使通道的高度和总线长减小，另外在性能优化方面也得 到改善1 1 5 1 1 6 1 1 9 1 。据1 1 5 】统计，采i g x = p 4 的非曼哈顿结构，平均可以减少 线长2 0 ，减少通孔3 0 ，减小布线区域面积1 0 ，从而使功耗减小2 0 ， 工作频率提高1 0 。 同时该文指出，非曼哈顿结构布局布线的研究仍然很不完善，学术研究往 往不能在业界实用。尽管如此，非曼哈顿在v l s i 工业界的应用仍然快速发展。 2 0 0 1 年，c a d e n c e 、t o s h i b a 、a r m 、a p p l i e dm a t e r i a l s 等涵盖了i c 工具、设 计、生产各领域的著名厂商组建了推动x 结构发展的开放论坛( x i n i t i a t i v e o p e nf o r u m ，x i o f ) 1 1 7 1 ，提出了称为x 结构的非曼哈顿l c 布线模式。并在 2 0 0 2 年，确认了x 结构i c 的可生产性。2 0 0 3 年6 月3 日，x i o f 的成员之一， a m t c 公司生产出第一块采用x 结构布线技术的9 0 纳米测试芯片。2 0 0 4 年 t o s h i b a 公司生产了第一块实用化的x 结构的芯片如图1 3 。 现在的x 结构芯片，均采用传统工艺生产，如果能够开放出对非曼哈顿结 构优化的薪设备、新工艺，以及成熟的非曼哈顿理论和算法，预计可给集成电 路工业带来更大的好处。在这种情况下，非曼哈顿结构布局布线研究是十分必 要和有意义的。 7 电子科技大学硕士学位论文 图1 3 x 结构芯片及布线区版图 1 5 论文完成的工作和内容安排 电子科技大学电子工程学院5 7 0 教研室的e d a 课题组，现专注于研究计 算智能在深亚微米v l s i 电路物理设计中的应用问题。本文工作研究的是v l s i 电路物理设计中详细布线阶段的非曼哈顿结构通道问题。 论文内容安排如下：第二章介绍了v i s i 电路物理设计及通道布线的常用 算法等；第三章通过分析基于冒泡排序的非曼哈顿通道布线算法中序列到布线 段这一泛函映射过程的特点，提出并实现了二分改进优化算法；第四章针对 b b l 布局中经常出现的不规则通道，提出并实现了一种适用于不规则通道非曼 哈顿结构通道布线的贪婪算法，并用一些b e n c h m a r k 例子验证了算法的可行性； 最后在第五章，对作者所做的工作进行了总结和展望。 8 第二章v l s i 布图算法及通道布线算法介绍 第二章v l s i 布图算法及通道布线算法介绍 v l s i 电路物理设计也称为布图设计，大多数布图设计可归结到组合优化问 题。所谓组合优化问题，通常可描述为：令o = 5 - , s 2 ，) 为所有状态构成的 解空间，( s i ) 为状态& 对应的目标函数值，要求寻找最优解s b 。，使得s i g o ， 有f 岱h ) = m i n 仁仁；l f = 1 j l 。v l s i 电路物理设计的组合优化问题往往涉及 到排序、筛选寻优、分类等问题。有很多通用的算法、几何原理及数学技巧可 用于物理设计( 布图设计) 的算法开发上，其中算法的时间和空间复杂度是布 图设计的重点，布局布线的最伍化是n p - 困难问题，通常需要用启发式算法解 决。 本章首先介绍了一些布图设计中常用的基本算法，其中包括图论算法、计 算几何算法、计算智能优化算法等，然后介绍了作为本文研究对象的通道布线 的发展历史和研究现状。 2 1v l s i 布图算法 2 1 1 图论算法 很多v l s i 电路布图问题都归结于图论问题，因此图论算法在布图中有着 广泛的应用。常见的有图搜索、最短路、最小生成树和斯坦纳树算法。 多图论中的问题都与图搜索有关，例如从一个图中找树、网络的关键路径、 求最大延迟等都需要搜索树，最常用的搜索算法有深度优先搜索( d f s ) 、广度优 先搜索( b f s ) 和拓扑搜索( t s ) 等。著名的l e e 氏算法及其改进算法形成了一系列 的布线算法，统称为迷宦算法。 很多v l s i 电路布图设计中的布线问题都是与一个特殊图上的最短路径 ( s h o r t e s tp a t h ，s p ) 有关的问题。因此，最短路径算法在布线中占有重要地位。随 着v l s i 电路超大规模化和相应的e d a 的研究发展，最短路径的概念已经有了 更深一层的涵义，它不仅指点与点之闾的实际物理距离，还被抽象成各种意义 上的权重：如费用，性能或性能综合指标等。 最小生成树( m i n i m u ms p a n n i n g t r e e ，m s t ) 闯题是一个边选择问题。有三个 基本求解m s t 问题的算法：b o r u v k a 算法、k r u s k a i 算法和p r i m 算法【1 1 。 9 电子科技大学硕士学位论文 最小斯坦纳树( m i n i m u ms t e i n e r t r e e ，s m t ) j 司题是一个n p 困难问题。s m t 在v i _ s i 电路布图中有着广泛的应用，多端线网的总体布线和详细布线都涉及 到求解斯坦纳最小树问题。 另外的一些图论算法还包括：在布图设计的布局、引线端和走线道分配等 问题中有着重要应用的匹配算法；与图的顶点集划分有关的最小割和最大割算 法；以及在划分、分配和布线中有着广泛应用的最大网络流、最小费用网络流 算法，等等。 2 2 2 计算几何算法 计算几何是对几何外形信息的表示、分析和综合，它是数学和计算机科学 相交叉的前沿学科。在v i s i 电路的版图设计中，是要把每个元件的电路表示 转换成几何表示，同时元件间的连线也要被转换成几何连线图形。因而计算几 何算法在版图设计里应用较多。典型的计算几何算法有扫描线算法、线探索法 等等。 2 2 3 基于运筹学的算法 运筹学根据解决问题的主要特征分为两大类，一类为确定型，包括：线 性规划、整数规划、动态规划、非线性规划等；另一类为概率型，包括：回归 分析、决策论、排队论、马尔可夫链、蒙特卡罗法和模拟退火等。 2 2 4 计算智能优化算法 所谓优化算法，其实质就是一种搜索过程或规则，它是基于某种思想和机 制，通过一定的途径或规则来得到满足要求的问题的解。许多v i _ s i 电路物理 设计问题都可归结为n p 复杂度的优化问题。随着v l s i 电路翻深亚微米推进， 系统规模扩大，问题空间维数随之剧增。传统优化算法要么面临计算量爆炸( 如 穷举法，线性规划等) ，要么易陷入局部极值，无法接近全局最优解( 如最陡下 降法，贪婪算法等) 。于是近代许多行之有效的计算智能优化算法，如神经网络、 遗传算法、模拟退火算法、蚁群算法、禁忌搜索算法等，梭引入到v l s i 电路 物理设计领域中。随着基于计算智能的v l s i 电路版图设计算法的大力发展， 这些研究工作在e d a 中也渐趋成熟。 这里先简要介绍一些常用的计算智能优化算法1 4 7 。 一、神经网络算法( n l 吼) 】0 第二章v l s i 布图算法及通道布线算法介绍 神经网络优化算法就是利用神经网络中神经元的协同并行计算能力来构造 的优化算法，它将实际问题的优化解与神经网络的稳定状态相对应，把对实际 问题的优化过程映射为神经网络系统的演化过程。 神经物理算法从2 0 世纪4 0 年代开始发展，到1 9 8 8 年由美国加州l e o n 0 c h u a 教授提出了细胞神经网络( o 咐) 。它的局部互连性非常有利于用当前 的v l s i 电路芯片实现。大量研究和应用结果表明，c n n 非常适合于一大类图 像及图形处理问题。而求图中环路就是布图设计中经常要遇到的一个问题。因 此可以预料c n n 在这一类问题中是有应用前景的。 二、遗传算法( g a ) 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 e n e t i ca l g o r i t h m s ) 。g a 是基于“适者生存”的一种高度并行、随机 和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过 “染色体”群的一代代不断进化，包括复制、交叉、变异等操作，最终收敛到“最 适应环境的个体”，从而求得问题的最优解。g a 的两个显著特点是隐含并行性 和全局解空间搜索。目前，g a 作为实用而有效的优化和搜索方法广泛应用于 v l s l 电路设计、计算机科学，社科领域，已成为国际学术界跨学科研究热点之 一。 三、模拟退火( s a ) 模拟退火算法( s i m u l a t e da n n e a l i n 西的思想最早是由m e t r o p o l i s 等( 1 9 5 3 ) 人提 出的。1 9 5 8 年k i r k p a t r i c k 等将其用于组合优化。s a 算法是基于m e n t oc a r l o 迭 代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程 与一般组合优化阎蘧之问的相似性。模拟退火算法在某一初温下，伴随温度参 数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解， 即在局部优解能概率性地跳出并最终趋于全局最优。s a 是一种非常简单而且 有效的通用随秽l l 优化方法。不仅在离散的组合优化伺题上有广泛应用前景，而 且同样可应用于求解连续多交量最优化词题。它将组合优化河驻与统计力学中 热平衡问题类比，开辟了求解组合优化目题的新途径。 该算法实质是对多极值非凸函数，通过设置温度参量，并按正比于温度的 概率接收比现行解较差的解，以跳出局部极值。从理论上来说，它可以达到最 优解，但是要达到最优解，温度必须下洚得足够幔，且每个温瘦下迭代的次数 1 1 电子科技大学硕士学位论文 足够多，这样一来就使得收敛的速度慢，但它的各种改进以及与其它方法的结 合在v l s i 电路物理设计中得到了大量广泛而深入的研究应用。 四、蚁群算法( a c s ) 蚁群算法是近年来发展迅速的一种仿生算法。1 9 9 7 年d o r i g o 和 g a n b a r d e l l o u 基于蚂蚁仿生算法体系发展而成，应用此法求解t s p 问题，获得 了较遗传算法，模拟退火及进化规划为优的结果。该算法是模拟蚁群通过协同 学习高效寻找食物源这生物行为的随机搜索算法。它区别于g a ，s a 等算法 的最大特点之一是将已搜索空间的历史经验和优秀可行解间的相互影响巧妙而 分布式地存储在解空间的各独立分量中，不同可行解信息被整合后反映在同一 条边权信息中，具有很高的空间存储效率和高效的蚁群信息交换机制。对它的 研究才刚刚起步，其成果还远远不及g a ，s a ，a n n 等那么丰富。 五、禁忌搜索算法( t s a ) 禁忌搜索( t a b us e a r c h ) 的思想最早是由g l o v e r ( 1 9 8 6 ) 提出，它是对局部邻域 搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。 t s 算法通过引入个灵活的存贮结构和相应的禁忌规则来避免迂回搜索，并通 过藐视规则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终 实现全局优化。相对于模拟退火和遗传算法，t s 是又一种搜索特点不同的 m e t a h e u r i s t i c 算法。迄今为止，t s 算法在v l s i 电路物理设计中取得了很大的 成功。 2 2 通道布线算法介绍 超大规模集成电路的通道布线问题是一个n p 完全闯题，目前，在通道布线 方面的研究已有丰富的理论和成果，大最的学术论文见诸于学术期刊和学术会 议。本章首先介绍了通道布线及其布线结构中的k - g e o m e t r y 理论，然后在这基 础上讨论了通道布线豹研究现状和一些有代表性的算法，最后提出的新的理论 和算法。 2 2 1 通道布线的基本摄念 通常有两种策珞来实现布局后的稚线，卸喜按豹区域布线和分两步实现的 总体布线和详细布线。 1 2 第二章v l s i 布图算法及通道布线算法介绍 区域布线是直接在个区域内( 线网引脚在布线区域内) 进行布线，典型 的区域布线有迷宫布线和线探索布线两种。 - 而分步布线是布局完成后形成布线区域，总体布线把线网分配给布线区域， 规定线网要经过的路线；布线区域戈0 分为各个通道 2 3 ，2 4 ，通道布线实现线网 在通道内的互连。两步结合从而完成整个芯片内线网最后定位。如图3 - 1 n ) 中 粗黑线组成整体布线的布线网络图，( b ) 中各编号区域是划分好的通道。 嚣圜 ( a ) 布局后的总体布线围( b ) 捌分后的通道 图3 - 1 通道划分的例子 一、通道布线概述 通道布线和开关盒布线是详细布线中的两类典型的布线结构，如图3 2 所 示。通道布线问题中，线网引脚分布在通道的上下两侧；开关盒也称为四边通 道，在四边通道布线中，线网引脚分布在布线区域的四周。 鬈 ( a ) 直通道( b ) 开关盒 图3 - 2 布线区域分为通道与开关盒 布线时，根据布线工艺的要求分为单层布线和多层布线，但不同线网不能 电子科技大学硕士学位论文 在同一层相交。分布在不同层上的同一线网通过通孔( v i a ) 相连接。 二、通道布线的目标 一般而言，布线的目的是完成所有线网的互连，优化目标是通道面积最小 ( 即通道的高度最小化) ，连线总长最短，通孔的数目最少等。对于当今高性能 的芯片设计，需要晟小化线网问的串扰、时延( 或者通过最小化某些关键线网的 连线长度从而最小化它们的时延) 等性能，以实现整个芯片的性能优化目标。 三、网格通道布线模型 为了便于解决通道布线问题，需要建立它的抽象模型。根据走线方式( 有 网格无网格) 、布线层数、布线模式( 曼哈顿非曼哈顿) 、布线层分配( 重叠 非重叠) 、终端性质( 固定、可移动或可交换) 等的不同，通道布线何以划分为 很多种模型。 使用得最广泛的是基于网格的模型( g r i d - b a s e dm o d e l ) ，在这种模型下，通道 被水平和垂真地划成许多网格，引脚、连线和通孔在网格上。水平的线称为道 ( t r a c k ) ，而垂直的线称为列( c o l u m n ) 。而不基于网格的模型都称为无网格模型。 在这种模型中，引脚、连线和通孔都可任意放置，连线的线宽和线间距也可变 化。显然，无网格模型的布线可通过预处理转化成有网格模型的布线。 狗腿 圈3 - 3 通道和线网表示以及一些定义 孔 对网格通道布线模型，不失一般性，假设通道的引脚行是水平的，上边行 称为顶边( t o pb o u n d a r y ) ，下边行称为底边( b o t t o mb o u n d a r y ) ，引脚用线网号 来标识所属线网。线网号零值的引脚称空端点或空引脚，它们不与任何线网相 1 4 第二章v l s i 布图算法及通道布线算法介绍 连。通道的水平长度称为通道长度( c h a n n e ll e n g t h ) ，布线后的垂直尺寸称为通 道高度( c h a n n e lh e j l g h t ) 。通道中的水平走线称为干( t r u c k ) ，而连接引脚的垂 直走线称为枝( b r a n c h ) 。能水平走线的通道空间称为轨道( t r a c k ) ，连接在不 同轨道上的两个干的垂直线段称为“狗腿 ( d o g t e 曲。如图3 - 3 所示。 2 2 2 通道布线中的k g e o m e t r y 理论 1 9 9 1 年，b u r m a n 等【3 】提出了x - g e o m e t r y 理论，完善了有关布线结构 的理论。在 - g e o m e t r y 理论中，布线的方向为i 眠i 为一任意数，k 为一正整 数。通过对矫i 的不同取值，可得到不同的布线方向。下面通过对k - g e o m e t r y 理 论的分析，不难得出工业上在用的或者有研究前景的几种布线结构。 特别地，当l = 2 时，布线的方向为i 州2 。不妨取j 为2 n ( n 为自然数) 时， 布线的方向为n ，即水平布线：取i 为2 n + 1 时，布线的方向为n 兀+ 兀陀，即垂 直布线；所以，九一2 对应为传统的曼哈顿布线结构( m a n h a t t a n a r c h i t e c t u r e ) 。 同理，当九= 3 时，布线的方向为i x 3 。不妨取i 为3 n 时，布线的方向为 觚，即水平布线：当取i 为3 n + 1 时，布线的方向为肌+ x 3 ；当取i 为3 n + 2 时，靠线的方向为n 冗+ 2 7 帕；所以，九= 3 对应为y 型布线结构( y - - a r c h i t e c t u r e ) 。 以此类推，当l = 4 时，布线的方向为i n 4 。取i 为4 n 时，布线的方向为 n j r ，即水平布线；当取i 为4 n + 1 时，布线的方向为嬲+ x 4 ；当取j 为4 n + 2 时，布线的方向为n 托+ x 2 ，即为垂直布线；当取i 为4 n + 3 时，布线的方向为 n t + 3 7 t 4 ；所以，九= 4 对应为x 型布线结构( x - - a r c h i t e c t u r e ) 。 最后，一种极限情况是：当b + 8 时，对应为欧几里德几何( e u c l i d e a n g e