（信号与信息处理专业论文）复合分层详细布线算法和非曼哈顿otc布线算法研究.pdf

摘要 摘要 v ls 1m 蹦物j ! ! i f i j 址v 1 s ii 没汁阻个重要环节，尤其是在当前v l s i i l 路砹汁i 川，j ；采、1 k 微水：岂小排迎，集j j 3 ；= 度和复杂度4 i 断提高的情况下，物理 设训更足整个v l s ij 、1 i 、尚机遇和挑战最大的领域之一。本文f 是在这样的 背景f 对v 1 s i1 h 路物理设计q 、的详细柿线问题展丌了一些研究工作。 水文, j i - l , k f t , i1 ：要l i 仆如卜： 1 、4 ：第3 t 挺 j l 了刊，新f 0 多层洋细硝j 线模型复合分层布线模型，作为 对传统详细钿线模型的补充，从一个新的角度对详细稚线问题进行了研究。和传 统通道币】线梭j t 比，该模j 性复合采用通道仰线层和区域柿线层，通过层问线网 转移的。法，i tj 吼兜j j | ；2 f 0 统迎逊呐一线并法t l i 处理循环约束问题和处理不相邻模块 问i j 迕川越的i , 1 4 雕，适川以j l ! ! j l 垃j n k 域处娜为满足荇神通道印线算法的理想模型， j i ：。j 以父衍处j = | f ! 些总体加线r l - 的小理想之处。文中为该模型设计了实现算法， 并通过实例进仃了验证，结果表明作为一种新的详细布线模型，复合分层布线模 t ，弘具钉定的川川。h ! 币l i 仃效m 是刈v l s lr 乜路详细和线研究的一个有益补充。 2 、引刈“dv i ，s i l 女j s j l ! 设计的热止i 一m 坚哈顿互连结构，文中第4 章提出 j 。种走 二非曼阶顷斫j 线结构：j jj 、f 元l ( o v e v i h e c e l l ，0 1 c ) 布线算法。结合通道 1 爱域所用非曼哈顺前，线算刘珀q 特点，通过采用线网段有效控制列技术、列密度深 艘探 t j ! 1 1 j 支术及跚* 刹川拽术埘r - j c l f ：i l - 一，线嘲进行柯效选择成功地实现了该非 世i l a - if 。巾线竹浊，i j o j ij 训。小j 绛虬的b e n c h m a r k 中，干翻前文献中 j b , t t j 。钾法川比愀r 虹侦的d i i f 结玳。 关键词：1 t 细们线，通道自i 线，复合分层如线模型，单元上布线，非曼哈顿 a b s t r a c t a b s t r a c t v i s ip h y s i c a ld e s i g ni sa r li m p o r t a n ts t e pi nv l s id e s i g np r o c e s si n t e g r a t e d c i r c u i ti n d u s t r yi sp r o g r e s s i n gr 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 ，w h i c hb r i n g su s g r e a tc h a l l e n g e sf o rt h ea v a i l a b l et o o l so fe l e c t r o n i cd e s i g na u t o m a t i o ne s p e c i a l l yi n t h ef i e l do fp h y s i c a ld e s i g n u n d e rt h i sb a c k g r o u n dt h ed i s s e r t a t i o ni si n t e n d e dt o d e v e l o ps o m ea l g o r i t h m sf o rv l s ip h y s i c a ld e s i g nd e t a i l e dr o u t i n g t h em a i nc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s ： an o v e lm u l t i l a y e rd e t a i l e dr o u t i n ga p p r o a c hb a s e do nan e wc o m b i n e dl a y e r a s s i g n m e n tm o d e li sp r o p o s e di ns e c t i o n3 a sas u p p l e m e n tt ot r a d i t i o n a ld e t a i l e d r o u t i n gm o d e li t r e s e a r c h e so nd e t a i l e dr o u t i n gp r o b l e mf r o man e wp o i n to f v i e w u s i n gt h i sd e t a i l e dr o u t i n gm o d e lc a ne a s i l yh a n d l et h ec y c l ec o n s t r a i n t si n c h a n n e lr o u t i n ga n di n t e r c o n n e c t i o n so fc i r c u i tm o d u l e sw h i c hd o n tb o r d e ru p o nb y t r a n s f e r r i n g n e t sf r o ml a y e rt o l a y e r b ys i m i l a rm e t h o d s ，c h a n n e la r e ac a nb e t r a n s f o r m e di n t oa ni d e a la l g o r i t h mm o d e lt om e e tu s e dc h a n n e lr o u t i n ga l g o r i t h ma n d s o m ee r r o ro f g l o b a lr o u t i n gc a na l s ob ea m e n d e d a no p t i m i z a t i o na l g o r i t h mb a s e do n t h ea b o v e m e n t i o n e dc o m b i n e dl a y e r a s s i g n m e n tm o d e li sd e s i g n e da n dv e r i f l e d t h r o u g he x p e r i m e n t s r e s u l t so fs i m u l a t i o nd e m o n s t r a t et h a to u ra l g o r i t h mi s p r o m i s i n gi nv l s id e t a i l e dr o u t i n g i n d e e ps u b m i c r o nt c c b a l o l o g y ，t h e s c a l eo fi n t e g r a t i o na n dt h ed e g r e eo f c o m p l e x i t yo f c i r c u i ti n c r e a s e r a p i d l y , i t i s n e c e s s a r y a n df e a s i b l et o a d o p t n o n m a n h a t t a nm o d e lf o rd e t a i l e dr o u t i n gi nv i 。s ip h y s i c a ld e s i g n a i m i n ga tt h e c u r r e n tp o pp o i n tan o v e ln o n m a n h a t t a no t cr o u t e ri s p r o p o s e di ns e c t i o n4 a c c o r d i n gt ot h er o u t i n ga l g o r i t h mo fc h a n n e la r e at h el l e wo t cr o u t e rs e l e c t sn e t so n c e l lb yu s i n gn e ts e g m e n tv a l i dc o n t r o l l i n gc o l u m nt e c h n o l o g y ，d e e ps e a r c h i n gt o c o l m n nd e n s i t yt e c h n o l o g ya n du t i l i z a t i o no fv a c a n tt e r m i n a l st e c h n o l o g y a f t e r i i i a b s t r a c t ，_。_-h。1。_+一 s u c c e s s f u ls e l e c t i o nn e t so nc e l li tr o u t e sc h a n n e la r e aw i t ha ni m p r o v e dm d c h a n n e l r o u t e r t h eo t cr o u t e ri sa p p l i e dt os o m eb e n c h m a r ke x a m p l e sa n dt h es i m u l a t i o n r e s u l to b t a i n e db yt h en e wr o u t e ri ss u p e r i o rt ot h eo l d t h i sf a c ti m p l i e st h a tt h e n o n m a n h a t t a no t cr o u t e ri se f f e c t i v ea n dp r a c t i c a l k e yw o r d s ：d e t a i l e dr o u t i n g ，c h a n n e lr o u t i n g ，c o m b i n e d l a y e ra s s i g n m e n t m o d e l ，o t cr o u t i n g ，n o n m a n h a t t a n v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 签名：j 单l 日期：施中月咖 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：边丛导师签名：i 量i 釜盏 日期：妒百年v 月烨日 第一章绪论 第一章绪论 人类社会已进入到高度发达的信息化社会，信息社会的发展离不开电子产品 的进步。现代电子产品在性能提高、复杂度增大的同时，价格却一直呈下降趋势， 而且产品更新换代的步伐也越来越快，实现这种进步的主要原因就是生产制造技 术和电子设计技术的发展。前者以微细加工技术为代表，目前己进展到深亚微米 阶段，可以在几平方厘米的芯片上以几十纳米线宽的工艺集成数数以亿计的晶体 管；后者的核心就是e d a ( e l e c t r i cd e s i g na u t o m a t i c ，电子设计自动化) 技术。 e d a 环境是指以计算机为工作平台，融合了应用电子技术、计算机技术、智能化 技术最新成果而研制成的电子c a d 通用软件包，主要能辅助进行三方面的设计工 作：电子电路设计、集成电路芯片及其版图设计和p c b 设计。没有e d a 技术的 支持，想要完成上述超大规模集成电路的设计制造是不可想象的，反过来，生产 制造技术的不断进步又必将对e d a 技术提出新的要求。 自从1 9 6 5 年英特尔公司主要创始人摩尔提出了“随着芯片上电路的复杂度提 高，元件数目必将增加，每个元件的成本将每年下降一半”，这个被称为“摩尔定律” 的预言。成为了以后几十年指导集成电路技术发展的最终法则。目前v l s l 电路已经 突破9 0 r i m 大关，采用9 0 n m 工艺的芯片已经在2 0 0 5 年实现量产，英特尔的6 5 纳米制程技术于2 0 0 5 年正式投入使用，进一步延伸了摩尔定律的优势【2 j 【。这是 集成电路制造工艺上一个质的飞跃，因为在向9 0 n m 和6 5 n m 进化过程中遇到的挑 战也远远高于以前的技术升级，采用多项新技术和新工艺。这些所谓的“重大挑 战”包括工艺及生产技术( 微细加工，新材料等) 和设计生产率等诸方面问题。 在八十年代和九十年代初，e d a 工具一般要落后工艺进展l 2 年。但从当前 看来，工艺方面在向深亚微米推进中不断取得成功，几乎每三年更新一代。而e d a 产业落后就较多了，因此e d a 设计工具的开发有必要尽快跟上半导体集成工艺的 发展。由于半导体生产工艺的极大进步，使得设计师们必须借助于先进的e d a 工 具和先进的设计方法进行产品设计。因此，与半导体生产工艺相配套的e d a 设计 工具的研发工作，具有重要的战略意义。本文的工作正是在这样的背景下进行的。 电子科技大学硕士学位论文 1 1i c 及e d a 技术的发展 1 1 1l c 是信息时代的重要硬件基础 在当今的信息时代，信息技术( i n f o r m a t i o nt e c h n o l o g y ，i t ) 作为强大的科技 第一生产力，在推动社会经济发展、社会的产业结构和生活方式的变革中的作用 | 二1 盏增长。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 c 的发展水平已经成为衡量一个国家综合国力的重要标志。为了加强基础 性i c 制造业的建设，以“信息化带动工业化”，我国在2 0 世纪9 0 年代就启动了“9 0 9 ” 工程。2 l 世纪初的“十血训划”里，更是明确地把软件产业和集成电路产业作为中 国高科技发展的两个重点方向。国际上先进的半导体工艺正被迅速地直接引入到 我国，制造工艺技术正在出o 3 5 p m 、o 2 5 p m 、0 1 8 9 m 向0 1 3 p m 和o 0 9 9 m 的生 产线工艺水平发展，因此可以说我国i c 产业已经进入了一个跳跃式发展阶段。国 际上为抢占这一产业制高点的争夺战更是此起彼伏。从国防科技、社会经济到日 常生活，i c 给人类社会生产和生活所带来的变革与冲击是科学技术史上空前的、 最具影响力的技术革命。 1 1 2l c 的发展历史 自从1 9 5 8 年集成电路发明以来，为了提高电子集成系统的性能，降低成本， 集成电路的特征尺寸不断缩小，制造工艺的加工精度不断提高，同时硅片的相对 面积不断增大。4 0 多年来，集成电路芯片的发展基本上遵循了摩尔定律，即每隔 三年集成度增加4 倍，特征尺寸缩小2 倍。集成电路经历了小规模集成( s s l ) 、中 规模集成( m s i ) 、大规模集成( l s i ) 的发展阶段，目前已进入超大规模集成( v l s i ) 和 特大规模集成( u l s i ) 阶段，是一个片上系统( “s y s t e mo nc h i p ”) 的时代。 1 1 3e d a 技术的发展状况 伴随i c 诞生和发展，产生了辅助电子产品没计的e d a ( e l e c t r i cd e s i g n a u t o m a t i o n ) 技术，e d a 技术是以计算机和微电子技术为先导，汇集了计算机图 形学、拓扑、逻辑学、微电子工艺与机构学和计算数学等多种计算机应用学科最 新成果的先进技术。e d a 技术以计算机为工具，代替人完成电子系统的逻辑综合、 兰二垩堑堡 布局布线和设计仿真等工作。利用e d a 工具，设计人员可以极大的提高设计效率。 伴随电路理论和半导体工艺的发展以及i c 集成度的提高，e d a 技术的发展大致分 为三个阶段1 4j 。 1 1c a d 阶段( 2 0 世纪6 0 年代中期2 0 世纪8 0 年代初期) ：这个阶段的特 点是开发一些单独的工具软件，主要有p c b 布线、电路模拟、逻辑模拟及版图的 绘制等，通过计算机的使用，从而将设计人员从大量烦琐重复的计算和绘图工作 中解脱出来。 2 ) c a e 阶段( 2 0 世纪8 0 年代初期一2 0 世纪9 0 年代初期) ：这个阶段在集成 电路与电子设计方法学以及设计工具集成化方面取得了许多成果。各种设计工具， 如原理图输入、编译与连接、逻辑模拟、测试码生成、版图自动布局以及各种单 元库已经齐全，并且组成一个c a e ( c o m p u t e r a i d e de n g i n e e r i n g ) 系统。按照设计方 法学制定的设计流程，可以实现从设计输入到版图输出的全程设计自动化。 3 ) e d a 阶段( 2 0 世纪9 0 年代以来) ：此阶段出现了以高级语言描述、系统仿真 和综合技术为特征的第三代e d a 技术，它具有如下特征： 高层综合的理论与方法耿得较大的进展，将e d a 设计层次提高到系统级 ( 又称行为级) ，并划分为逻辑综合和测试综合。 执采用硬件描述语言h d l 柬描述1 0 刀门以上的电路的设计，并形成了v h d l 和v e r i l o gh d l 两种标准硬件描述语言。 c 采用平面规划伊l o o r p l a n n i n g ) 技术对逻辑综合和物理版图设计进行联合管 理，做到在逻辑设计综合早期设计阶段就考虑到物理设计信息的影u 向。这样，设 计者能更迸一步进行综合与优化，并保证所做的修改只会提高性能而不会对版图 设计带来负面影响。 正可测性综合设计。 巴为带有嵌入i p 模块的a s i c 设计提供软硬件协同系统设计工具。协“司验证 弥补了硬件设计和软件设计流程之阳j 的空隙，保证软硬件之间的同步协调工作。 ，建立并行设计工程c e ( c o n c u r r e n te n g i n e e r i n g ) 框架结构的集成化设计环境， 以适应当今a s i c 的如下特点：数字与模拟电路并存，硬件与软件设计并存，产品 上市要快。 虽然i cc a d 发展是伴随着i c 的发展而发展的，但是它的发展速度还是远远 落后工业| 二对它的要求以及v l s i 电路工艺的发展速度。 电子科技人学硕十学位论文 1 1 4e d a 发展的迫切需要 当今飞速发展的电子设计领域，i c 技术向着更高集成度、超小型化、高性能、 高可靠性的方向迅速发展。长远来讲，一个：西片上可集成高达几亿、甚至几十亿 个晶体管，目前v l s i 电路正力图突破6 5 r i m 至4 5 r i m 线宽大关。在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 课题组申请到了四川省科技厅的计算智能在超 大规模集成电路物理设计。l _ 1 的应用科研项目。本文的研究工作就是这个项目课 题延续研究的一部分，主要对v l s i 电路物理设计中的详细布线问题进行了研究。 1 2v l s i 电路物理设计概述 121v l s i 电路设计流程 v l s i 电路设计过程从给出芯片的设计要求开始，包括了功能设计( f u n c t i o n d e s i g n ) 、逻辑设计( 1 0 9 i cd e s i g n ) 、电路设i t ( c i r c u i td e s i g n ) 、版图设计( 或者物理设 i - - - - p h y s i c a ld e s i g n ) 、设计验证( d e s i g nv e r i f i c a t i o n ) 、制造( f a b r i c a t i o n ) s 1 1 封装测试 ( p a c k a g ea n dt e s t ) 等过程，其流程如图1 - 1 所示。v l s i 电路设计可能会在一个步骤 中或在几个步骤之问反复交替进行，实际上，v l s i 电路c a d 的目标就是要尽量 减少这种反复次数以缩短产品进入市场的时间。 第一章绪论 图卜1v l s i 电路设计流群 122 物理设计的定义和流程 v l s i 电路物理设计( p h y s i c a ld e s i g n ) 也称为布图设i , - ( l a y o u td e s i g n ) 。其输 入是电路的元件说明和网表，输出是设计好的版图。即根据电路和工艺要求完成 芯片上单元或功能块的安置，实现它们之间所需要的互连。 在整个集成电路设计过程中，物理设计是与产品研制和生产直接相关的一个 设计过程，直接关系芯片设计周期，生产成本和产品质量。这一步骤也是以往人 工设引中耗时最多，差错率最高的设计过程之一。因此，它也是近年来e d a 工具 中发展最快，自动化程度最高的领域之一。而且，随着v l s i 电路向超深亚微米推 进，它也是受工艺影响最大，面临的机遇和挑战最大的领域之一。物理设计流程 可概括如图1 2 所示。 物理设计 7 l划分 + f u 路设计l 布刚规划和布局 1 出片制造 l 总体布线 t 1 羊细布线 图卜2 物理设计过程 圜 电子科技大学硕十学位论文 1 2 3 物理设计的主要模式和基本问题 目前芯片的设计主要以下几种常用模式： 1 全定制模式( f u l l c u s t o md e s i g ns t y l e ) ：整个电路被划分为一些子电路，每 个子电路是一个模块。最通常情况下，模块的外形和放置位置都没有限制。主要 有三种c a d 工具：交互图形编辑( i n t e r a c t i v eg r a p h i ce d i t o r ) 、符号法版图设计方法 ( s y m b o l i cl a y o u ta p p r o a c h ) 、积木块自动布图( b l o c kb u i l d i n gl a y o u t ，b b l ) 。 2 标准单元设计模式( s t a n d a r dc e l ld e s i g ns t y l e ) ：系统事先已准备好几百种 包括有逻辑符号、拓扑和物理版图的“标准单元”存入单元库中，以供用户设计 不同的芯片。这些单元的逻辑功能、电路性能及几何设计规则都经过验证和分析。 杯准单元模式的布图可以利用自动布局和自动布线技术来完成，效率高且设计周 期短，是目前应用最广泛的设计方法之一。 3 门阵列设计模式( g a t ea r r a yd e s i g ns t y l e ) ：又称为母片( m a s t e rs l i c e ) 法。 它预先设计和制作好各种规模的母片，其上除金属连线和通孔外的单元图形是固 定不变日以阵列排列，母片上单元之间区域是水平和垂直的布线通道。所以母片 上的单元和通道固定。每个这样的单元可以经过不同的金属连线得到不同功能的 单元电路。 4 门海设计模式( s e a o f - g a t e sd e s i g ns t y l e ) ：进一步改进了宏单元阵列的版 图结构。它取消了水平方向的通道，成为一种无通道( c h a n n e l l e s s ) 的门阵列。 一般的，功能块的形状如矩形，长宽比和位置由布图规划和布局算法决定。母片 预制，不同功能的电路只需要改变金属连线。 5 现场可编程门阵列( 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 ) ，它是近几年迅速发展用于a s i c 设计的 一种新方法。f p g a 提供了用户可编程和自己制造的能力。 具中跟e d a 设计相关的主要有门阵列( g a t e a r r a y ) ，标准单元( s t a n d a r d c e l l l 和积木块( b u i l d i n g b l o c kl a y o u t ，b b l ) 等几种布图模式。标准单元( 见图1 - 3 ( a ) ) 和门阵列( 见图1 3 ( b ) ) 又常被称为基于行排列( r o wb a s e d ) 的模式。在这两种 巾图模式中，电路的基本单元有规则地成行排列，单元行之间的区域作为御线通 道( c h a n n e l ) 。由于单元行排列比较规则，问题相对比较简单。所以布图设计技术 6 第一章绪沦 首先在fj 阵列和标准单元模式上得到了比较充分的发展。b b l 模式，又称宏单元 模式( m a c r oc e l l ) ( 见图1 - 3 ( c ) ) ，是设计中最灵活的一种设计方法。在这种布图 模式中，单元或模块可以有任意的形状和尺寸，可以安排在芯片的任意位置上而 且没有固定的布线区域。 f a ) b j i 准单儿 ( b ) 阵列 、 一 l 厂 r ? f 】l l il 【l 【| _ l 1 - j ! | | i i ii i 。= - ll r i 一 ；rl1 l j 【 u i l j ( c ) b b l 图1 - 3 主要布图模式 基于上述的不同设计方法，设计者可以根据产品的性能、批量和现有的工艺 设备状况，采用混合设计模式和分级设训策略。 所有模式中实现互连都是其最终目的。在当今的i c 设计中，随着芯片的集成 度和工作频率的提高、工艺向深亚微米的不断发展，互连线越来越细，互连线的 i a j g e 越来越小，给信号的完整性带来极大的挑战。很多v l s l 电路布图设计的布线 问题归根到底都是组合优化问题，其计算和存储空i h j 在v l s i 电路规模下无限膨胀， 其中许多问题已被证明是n p 完全问题。同时，随着v l s i 电路技术的发展，传统 的曼哈顿互连线结构也在发生变化，目前已有学者提出了非曼哈顿互连结构，给 v l s i 电路的布图设计带来新的机遇和挑战。在考虑性能驱动的前提下，寻求有效 的优化算法以解决诸多非曼哈顿布图n p 困难问题已成为当务之急。 1 3v l s i 电路物理设计的发展趋势 2 0 0 2 年8 月发布的s r c “p h y s i c a l d e s i g n c a d t o p l 0 n e e d s ”中指出当前物理设 计急待解决的十大问题，机局布线( p l a c e m e n ta n dr o u t i n g ) 问题首当其冲，在芯 ：|：=：|口一 _=p：=：_口-一 ：_口一【：二：口， |瓣一 苗盎 、l 一r，1i 皇王型堇查堂堡主堂篁丝壅 片尺寸和容量上，布局布线要解决面对几千个大模块和上百万个小模块的电路规 模，并且在可行的时间内得到结果。其它需求中的定时、互连分析等也与枷线密 切相关。可见，物理设计，即布局布线，仍然是v l s l 电路设计自动化中的重要问 题。 和局布线的发展方向如下： 1 ) 设计模式以互连为l ：p 心：对深亚微米v l s i 电路而言，特征尺寸不断缩小， 器件本身的时延不断减小，而连线长度、密度迅速增加。连线时延和线洲串扰及 信号的完整性也将成为影响电路性能的重要因素。v l s i 电路设计将从以器件为中 心的模式，逐步过渡到器件与连线并重，并以互连为中心的设汁模式。 2 ) 设计目标以性能优化为核心：物理设计将从使版图面积最小化的单一目标 不得不转向在面积和设计竞争能力的各项性能指标：速度、功耗、串扰、信号完 整性和成品率等之间寻求平衡。 3 ) 设计模型不断演变：多层工艺和系统集成( s o c ) 已成为了v l s i 电路发 展的必然趋势，单一的网格模型已难以满足新的需求，各种更优的设计模型和数 据结构应运而生，如超立方体、无网格模型、角勾链结构等都是极有潜力的新途 径，有待进一步系统深入的研究。 4 ) 非曼哈顿柿线结构的发展：1 9 9 1 年，b u r m a n 等【5 】提出了x - g e o m e t r y 理 论，完善了有关互连线结构的理论。连线结构可以概括为传统的曼哈顿结构( 水平 垂直前j 线结构) 和非曼哈顿结构。新的互连线结构( 如x 、y 结构) 给v l s i 电路的布 图捌划、布局、布线、数据结构等带来新的设汁方法。文献 6 7 】 8 】等相继提出了 各种非曼哈顿结构的布局布线算法。文献 9 1 0 j 1 1 非曼哈顿布线结构的引入使物 理设计的诸多性能得到改善，成为当前v l s i 电路物理设计研究的热点。 1 4 论文完成的工作和内容安排 论文完成的主要工作和内容安排如下：第二章介绍了v l s l 电路物理设计中常 用算法和模型，着重对详细布线算法和模型以及研究状况进行了阐述；第三章结 合当6 uv l s i 电路多层夼线工艺的发展，通过对传统多层通道布线模型的分析，提 出了一种复合分层详细布线模型。和传统通道布线模型相比，浚模型复合采用通 道柿线层和区域布线层，通过层问线网转移的方法，可以克服传统通道布线算法 第一章绪论 中处理循环约束问题和处理不相邻模块间的互连问题的困难，还可以把通道区域 处理为满足各种通道布线算法的理想模型，并且可以灵活处理一些总体布线中的 不理想之处。第四章结合非曼哈顿布线结构的发展，第一次提出了一种基于非曼 哈顿御线结构的单元上布线算法。结合通道区域所用非曼哈顿布线算法的特点， 通过采用线网段有效控制列技术、列密度深度探测技术及空端利用技术对单元区 可布线网进行有效选择，成功地实现了该非曼哈顿单元上柿线算法，并将其应用 于一些经典的b e n c h m a r k 中，和目前文献中现有算法相比取得了更优的币j 线结果。 最后在第五章对全文进行了总结和展望。 电子科技大学硕士学位论文 第二章v l s i 电路详细布线主要模型和算法介绍 v l s i 电路物理设计也称为布图设计，是v l s i 设计中最费时的一步。它要将 电路设计中的每一个元器件以及它们之间的连线转换成集成电路制造所需要的版 图信息。物理设计过程包括划分、布图规划、稚局、布线和压缩。划分就是把整 个电路分成若干个模块，将处理问题的规模缩小。布图规划是根掘模块包含的器 件数估计其面积，再根据该模块和其它模块的连接关系以及上一层模块或芯片的 形状估计出该模块的形状和相对位置：布局是要确定模块在芯片上的位置；布线 则是要完成模块间的互连，在完成互连的前提下进一步优化向线结果，布线分为 总体布线和详细布线两个阶段完成；压缩是布线完成后的优化处理过程，它试图 进一步减小芯片的面积。 物理设计问题大都可归结到组合优化问题。往往涉及到排序、筛选寻优、分 类等问题。有很多通用的算法、几何原理及数学技巧可用于物理设计的算法开发 上。由于v l s i 电路物理设计的复杂性，对物理设计的研究分为很多方面，本文研 究的重点是详细布线方面的问题。基于此，本章首先简要介绍一些布图设计中常 用的基本算法，然后重点介绍了详细布线的典型布线模型和算法。 2 1v l s i 电路物理设计布图算法介绍 首先介绍一些布图设计中常用的基本算法，其中包括图论算法、计算几何算 法、计算智能优化算法等 2 1 1 图论算法 很多v l s l 电路布图问题都归结于图论问题l 】“，因此图论算法在布图中有着广 泛的应用。常见的有图搜索、最短路、最小生成树和斯坦纳树算法。 很多图论中的问题都与图搜索有关，例如从一个图中找树、网络的关键路径、 求最大延迟等都需要搜索树，最常用的搜索算法有深度优先搜索( d f s ) 、广度优先 搜索( b f s ) 和拓扑搜索( t s ) 等。这些图搜索算法大致上都采用一种递归过程，其策 略是把后继节点按照某种优先度放在集合中，然后“尽可能深”或“尽可能广” 地去搜索图，算法复杂度均为0 伽+ n j ，其中所为图中的边数， 为节点数。这种 o 筇母v i s il u 跺详细布线t 要模删和算法介 f j “j s l 叮能源”或“尽w 能广”的搜索思想是一种很基础的图论解决问题方案，著 私n 1 【c e 氏算浊及je 改进舛法j 眵j j l i ：的一系列称为迷宫算法的御线算法的根据就是 这样的j 。丛恕。 徽多v l s ii u 路nj 倒改汁- i 一的们线问题都是与一个特殊图上的最短路径 ( s h o r t e s tp a t h ，s p b ；f 关的题。凶此，最短路径算法在粕线中占有重要地位。通常有 一i 类最尽本的最短路径问题：单点对最短路径问题，单源点最短路径问题和全点 埘最觚路行问题，j p t 点列最短路径问题是最基本的问题。迷宫算法首次在v l s i i u 路面，0 确，线上的成功应川，就是刚来求解单点对最短路径。随着v l s i 电路超大 规模化和相应的e d a 的研究发展，最短路径的概念已经有了更深一层的涵义，它 不仅指点与点之间的实际物理距离，还被抽象成各种意义上的权重，如费用，性 能等l 。 最小牛成树( m i n i m u ms p a n n i n gt r e e ，m s t ) i f i 题是一个边选择问题。有三个基 小求解m s t 问题的算法：b o r u v k a 算法、k r u s k a l 算法和p r i m 算法。 最小生成树( m s r 用j 单点对之阳j 最短路( s p s p ) 问题是两种边选择问题1 3 1 。它 们的变形最小斯坦纳树( m i n i m u ms t e i n e rt r e e ，s m t ) 问题却是一个n p 一困难问 题。s m t 问题7 1 iv i 。s ii u 蹄4 1 i i - n h 1f 着广泛的应用，多端线网的总体布线和详细 枷线都涉及到求解最小斯j _ | ：l 纳树问题。 另外的一些图沦算法还包括：在物理设计的布局、引线端和走线道分配等问 题中有着重要应用的匹配算法：与图的顶点集划分有关的最小割和最大割算法： 以及在划分分配和碲j 线中柯着广泛应用的最大网络流、最小费用网络流算法等。 21 2 计算几何算法 训算j c _ f i , j 是数学_ j f l i “s ：7 ：机科学相交义的前沿学科，它是对几何外形信息的表 石i 、分析和综合。礼：v i ，s ii 乜蹄的版图设计中，是要把每个元件的电路表示转换成 儿f i l 袭j j ，州时儿仆州的琏线【h 要被转换成几何连线圈形。因而计算几何算法在 版劁改训1 i 川较多。媲1 0 算儿们3 ：t 法靠f 1 描线算法、线探索法等。 2 1 3 基于运筹学的算法 有很多撼于运筹学九勺算法存物理设计中广泛应用。通常根据解决问题的主要 特征分为两大类，类为确定型包括：线性规划、整数规划、动态规划、非线 + 陀舰划等；另类为概率魁，包括：回归分析、决策论、排队论、马尔可夫链、 u 1 7 科技人学硕十学何论文 蒙特k 罗法垌i 授拟巡火等。 2 1 4 计算智能优化算法 很多物理i 殳计问题的实质一卜是一个寻找最优解的过程，而寻找优化问题的优 化解可以转化成对合法构形；己i 训的搜索问题。所渭优化算法，其实质就是一种搜 索过= l 或枞! j ! l j ，它址j ，叫：某种思想和机制，通过一定的途径或规则来得到满足要 求的问题的蒯。随着v i 。s i u 蹄向深亚微米推进，系统规模扩大，问题空间维数随 之刷增。传统优化钟：法要么i n i i i i ：l 算量爆炸( 如穷举法，线性规划等) ，要么易陷 入局部极值，无法接近令局最优解( 如最陡下降法，贪婪算法等) 。而近年来出现 的i ， ：多计算智能优化算法，如神经网络、模糊逻辑、演化规划( 含遗传算法) 、仿 牛掉泄i 则l 眨脱j l 斛决此矛盾的卜) ：大潜力。这类优化算法的目标是寻求满意 或次优解，花f 犍多0 u 题j 之有效，： 二是被引入到v l s l 电路物理设计领域中。这 驰简要介绍些常川的汁算智能优化算法1 1 “。 l 、神经网络算法( n n a ) 神经物珊算法从2 01 1 j ：# 2 , 4 0 年代丌始发展，该算法是利用神经网络中神经元 的 ：j j 制并行汁竹能力来构造的优化辩：法，它将实际问题的优化解与神经网络的稳 j 已状态干对盹，把刑。爻际问题的优化过程映射为神经网络系统的演化过程。 到1 9 8 8 年由美国加州l e o no c h u a 教授提出了细胞袢经网络( c n n ) 。它的 局部可连t 1 - ：l l - 常秆利于用j _ 前的v l s i 电路芯片实现。大量研究和应用结果表明， c n n - 阶l 适j 7 川人类闲像及1 刘形处理问题。而求圈中环路就是布图设计中经常 嘤趔j 刈n q 个题。 此j 以预料c n n 在这一类问题中是有应用前景的。 2 、遗传算法( g a ) 遗传算法( g e n c t i ca l g o r i t h m ，g a ) ，它是山美国m i c h i g a n 大学的jh o l l a n d 教 授1 j1 9 7 5 - 1 - n 先捉f i j 。j j ，g a 作为实j _ = | 丽有效的优化和搜索方法广泛应用 j 钟：机科学，1 榭技术，十怫! 城，已成为蚓m ；学术界跨学科研究热点之一。 g a 足。叫迅揣、r 仃”的种高度并行、随机和自适应的优化算法，它将问题 的求蝌表1 成“染也体”f 一适者生存过程，通过“染色体”群的一代代不断进化，包括 复制、交叉、变异等操作，最终收敛到“最适应环境的个体”，从而求得问题的最优 解。g a 的阳个j 1 1 1 = 著特点是隐食并行性和全局解空涮搜索。 3 、模拟退火( s a ) 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 思想是l9 5 3 年m e t r o p o l i s 等人提出的。他 第二章v l s i 电路详细布线主要模型和算法介绍 们给出了固体退火过程中物质内部状态变化的模拟算法。这方面的研究本质上属 于统计物理范畴。 s a 是一种非常简单而且有效的通用随机优化方法【8 1 。不仅在离散的组合优化 问题上有广泛应用前景，而且同样可应用于求解连续多变量最优化问题。它将组 合优化问题与统计力学中热平衡问题类比，开辟了求解组合优化问题的新途径。 该算法实质是对多极值非凸函数，通过设置温度参量，并按正比于温度的概率接 收比现行解较差的解，以跳出局部极值。该温度参量由高温向低温下降的过程巾， 整个进程在状态空间由随机搜索向确定性搜索转化，从而使整个进程接收较差解 的可能性越来越小，直至最后收敛到最优解。理论上说，只要有足够长的时间， 随着温度的下降，它可以达到最优解。 s a 收敛速度慢，但它的各种改进以及与其它方法的结合得到了大量广泛而深 入的研究，其中在v l s i 电路物理设计中也得到了大量广泛的研究应用。 4 、人工蚁群算法( 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 等那么丰富。 5 、禁忌搜索算法( t s