（微电子学与固体电子学专业论文）电路中电源地网络的优化研究.pdf

中文摘要 摘要：近年来随着集成电路工艺的发展，集成电路的规模变得日益庞大，然 而其工艺的特征尺寸在不断的减小，芯片的集成度、复杂度和工作频率快速提高， 电源地网络分析的可靠性在电路设计中显得尤为重要。 同时，深度亚微米技术的高速发展也使得功率传输噪声不可忽略，因为电源 线压降过大也会导致芯片内部逻辑错误，因此在分析p g 网络时要将以上问题作 为约束条件来认真考虑，让其在保障正常供电的前提下对布线作了最大的优化， 具有一定的现实价值。 在本文中，研究了一种电源地网络( p o w e r g r o u n dn e t w c r k ，p g ) 分析的 e k o s ( e x t e l l d e dl 叫o vo f s u b s p a c e ，扩展妁矶o v 子空间) 优化算法。e k o s 优化 技术是一项有效的模拟方法，将被广泛的应用在电源地网络分析中。与现有的随 机行走算法相比，这种新的算法能够估算出瞬态反应，能够快速产生稳定的结果， 因此该研究具有实用的研究意义。 本文先对电源地网络噪声问题进行了可靠性分析，明确了电源地网络的研究 内容，并且对现有的降低电源地网络电压降算法进行了分析，讨论了这些算法的 优点和缺点，最后引入e k o s 方法。在e k o s 设计过程中，首先研究了一类非常 有效的大型线性代数方程组解法，如k r y l o v 子空间算法；在此基础上，把电源 地网络分析应用到了扩展k 珂l o v 子空间算法，把大规模的电源地网络简化成易于 求解的系统，再把结果返回到原系统中。有效的达到电源地网络分析的目的。同 时本文提出的e k o s 算法，已经用c + + 语言进行编程实现，程序的运行结果表明 通过对已有的电路的分析和优化，e k o s 完全达到了对电源地网络的优化的目的。 关键词：电源地网络；e k o s 算法；扩展子空间；瞬态反应；优化技术 分类号：t n 4 7 ：t n 7 1 0 9 a b s t r a c t a b s t r a c t ：w i mn l ed e v e l o p n l e n to fi n t e g r a t e dc i r c u i tt e c h n o l o 鳜t h es c a l eo f c i r c u i ti n c r c a s i i l gd a ya f t e rd a y ， t h e s ec h a r a c t 甜s t i c so ft h ec o n s t a n td e c r e a s ei n 也e s i z e ，c h i pi n t e g r a t i o n ，c o m p l e x i 够a n d 仔e q u e n c y 蚰b s t a n t i a l l yi n c r e a s e ，p o w e r 铲o u n d n e t 、) l ，o r ka n a l y s i st 0m er e l i a b i l i t yo fm ec i r c u i td e s i g ni se v e nm o r ei m p o 砌n t m e a n w l l i l e ，r a p i dd e v e l o p m e n t0 ft h ed e 印s u b m i c r o nt e c l l i l o l o g ym a d en l ep o w e r d e l i v e 巧n o i s ec a l l n o tb en e g l e c t e da sw e l l b e s i d e s ，i r d r o p st h a tb e y o n dl i m i t sc a n a l s oc a u s ew r o n gl o g i ct om ec h i p h e n c c ，w h e nd e s 远n i n gap gn e t w o r k ，o n ei n u s t c o n s i d e ra nt h o s ep r o b l e m sa b o v ea sp r o - d e s i g n i n gc o n s 仃a i n t s o n l yb yd o i l l gt h i sc a n w ea t t a i nm em i n i r m l m r o u t i n ga r e ao nt h ep r e n l i s eo fs u p p l yg u a r a n t e e d i nt h i sp a p e r ，i tp r e s e n t sa ne k o s ( e x t e n dk r y l o vo fs u b s p a c e ) m e t h o df o r p o w e r 留o u n dn e t w o r ka n a l y s i s e k sm e t h o di sa ne 脆c t i v es i m u l a t i 锄；i tw a s 、) l ，i d e l y u di np o w e r 分0 u n dn e t 、) l ，o r ka n a l y s i s c o m p a r e dt ot h e e x i s t i n gr a n d o m - w a l km e t h o d ， t 1 1 i sn e wm e t h o dc a ne s t i m a t et h e 仃a n s i e n tr e s p o n s e ，c a np r o d u c es t a b l er e s u l t s s o ，t h i s r e s e a r c hh a sp r a c t i c a ls i g l l i 丘c a n c e t 1 1 i sp a p e rf i r s ts t u d i e st h ee ) 【i s t i i 培p o w e r g r o u n dn 酿) l r o r ka m l y s i sm e t h o d c l e a u r t 1 1 er e s e 2 u r c ho f p o w 既7 伊o u n d ，c o m p a r e 廿l ea d v a n t a g e 锄dd i s a d v a n t a g eo fe a c hm e t h o d a n a l y s e sm e 自c i i l gp r o b l e m s a n dt h e ni n 仃o d u c t i o nt h ee k sm e t h o 也i ne k sr e s e a r c l l ， w ea n a l y s e sav e r ye 毹c t i v el a 喀e s c a l el i n e a ra l g e b r ae q u a t i o n ss 0 1 u t i o n ： i ( r y l o v s u b s p a c e g o r i t h m b a s eo nm i s ；印p l ye x t e n dk 巧l o vs u b s p a c ei np o w 咖n d n e t w o r k 锄l y s i s m a k et h el a r g e - s c a l ep o w e r 伊o u n dn e t w o r kt os i m p l es y s t e m t h e n l e a dt h er e s u l tb a c kt ot h eo r i g i i l a l 掣s t e m c o m et 0 也ep u 印o s eo fp o w e r 黟0 u 1 1 d n e t w o r ka n a l y s i s ，ia l s om 狄ee d as o f h 张r et om a k es u r et l l ee k o s t h et i l e s i su s e s m ec + + l a n g u a g et om a k es u r e 也ee k o sm e m o d s k e y w o r d s ：p gn e 啊o r k ；e k o sa l g o r i t h m ；e x t e n d e ds u b s p a c e ；仃a n s i e n tr e s p o n s e ； o p t i m i z a t i o n c i 。a s s n o ：t n 4 7 ：t n 7 1 0 9 致谢 本论文的工作是在我的导师袁小龙副教授的悉心指导和帮助下完成的，他对 于我的论文的完成给予了很大的帮助，并提出了许多的宝贵意见，在此表示衷心 的感谢! 袁小龙副教授悉心指导我完成了实验室的科研工作，在生活和学习上都给予 了我很大的关心和帮助，他严谨的治学态度给了我极大的影响。在此衷心感谢两 年半来袁老师对我的关心和指导。 再次感谢袁老师为我提供了去北京晶智意达有限公司完成论文前期调研的机 会和晶智意达公司黄国勇博士对我的指导! 在实验室工作及撰写论文期间，关楠楠学姐、阮孝莉同学、唐磊同学、郭倩 同学和周旋同学等对我论文中的研究工作给予了热情帮助，在此向他们表达我的 感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 1 引言 1 1 电源地网络分析方法的介绍 1 1 1集成电路工艺技术的发展概括 集成电路诞生于上世纪的五十年代，自从诞生以来得到了飞速的发展，已经 从小规模集成电路( 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 m o n c h i p ) 片上系统的领 域。深亚微米( d s m ) 及超深亚微米( v d s m ) 技术使实现s o c 成为可能。从1 9 8 5 年代的2 p m 大小，到2 0 0 0 年的o 1 8 _ o 1 3 p m ，最近几年的发展更为迅速。工艺手 段已经可以达到或接近o 0 4 p m 的级别，所以集成电路已经进入到了深亚微米工艺 时代。在1 9 6 0 年，i n t e l 公司gm 0 0 r e 语言的集成电路发展规律指数“摩尔定律” ( 集成电路最小尺寸以每三年减少7 0 的速度下降，集成度每年翻一番，其价格 每两年将一半) 已经得到了很好的验证。随着特征尺寸的减小，单芯片系统的集 成度从一千万门晶体管的大小，到如今的上亿门晶体管的集成度，集成电路技术 的飞速发展让人诧异的同时，更要向着更高集成度、超小型化、高可靠性、高性 能、的方向发展。 当前，集成电路的发展方向主要集中在两个方面：一方面，在已有的微细加 工技术上，超高速、超集成度、超微型的集成芯片：另一方面，利用先进的艺术 工艺、设计技术、封装和测试技术发展多种专用集成电路。也就是人们常说的a s i c 。 特别是发展更为复杂的s o c 系统成为主要的发展方向，不断地缩短产品的上市时 间，也是产品有利的竞争手段。若产品的上市时间延长一年，那么产品的损失将 是其收益的2 陪。这样的产品就没有了开发的意义。因此，集成电路的要求就是： l 、设计周期短；2 、设计正确性高；3 、低功耗，低电压：4 、速度快、测试性好； 5 、价格低。自动工具的使用和发展应适应于集成电路的发展复杂性并同时要满足 其上市的时间。相反，复杂度的在集成电路设计的需求上又使得工程师们越来越 依赖于先进的自动化仿真软件和其中的先进算法的实现。 集成电路的发展离不开工艺技术的发展，最近几年的工艺发展特点主要体现 在六个方面。如下： ( 1 ) 晶圆尺寸越来越大； ( 2 )晶体管的特性尺寸越来越小； ( 3 ) 电源的电压越来越低： ( 4 ) 布局布线越来越复杂； ( 5 ) i o 引脚越来越多； ( 6 ) 芯片内部的资源越来越丰富，集成度也就越来越高。 1 1 2集成电路的布线技术 上节中已经提到，i c 技术已经进入到超大规模集成的高度，这就意味着相同 大小的芯片内可以包含更多的c m o s 场效应管，更多的门阵列。因此为了保证芯 片模块能够正确的链接，芯片内部的布线技术变得更显得尤为重要。如今的物理 设计要在几十平方毫米的芯片上设计出线条只有零点几微米且数以百万计的器件 的整个电子系统，面临着巨大的机遇和挑战。 集成电路设计流程包含有系统描述一功能设计一逻辑设计一电路设计一物理 设计一芯片制造一测试封装，在这个过程中，物理设计是重要的一个环节，它是 整个集成电路设计过程与生产过程的一个总体实现，由于深亚微米技术的发展， 如今的物理设计更加的重要起来。 物理设计的布图设计( l a y o u td e s i g l l ) 其输入是电路的元件的说明和网表，输 出是设计好的版图。即根据电路和工艺要求完成芯片上单元或功能块的安置，实 现它们之间所需要的互连。版图设计要符合与制造工艺相关的设计规划。物理设 计过程如图： 图1 1 物理设计过程 f i g1 1p r o c e s so f p h y s i c a ld e s i 印 2 目前芯片的实现主要有门阵列( g a t e 加t a y ) ，标准单元( s t a n d a mc e l l ) 和积 木块( b u i l d i n gb l o c kl a y o u t ，b b l ) 等几种布图模式。门阵列和标准单元又常被 称为基于行排列( r o wb a s e d ) 的模式。 1 1 3集成电路噪声的分析 在集成电路中，能够影响电路功能的噪声大致可以分为两类：本征噪声和开 关噪声，其中本证噪声是半导体材料固有的物理现象，对电路的影响又是非常有 限的，所以开关噪声才是电路的主要噪声。开关噪声是一种逻辑变化期间由微小 电流所引起的微小变化，如杂波电流。虽然单级别的这种杂波不能引起比较严重 的电路错误，但是在积累到一定程度达到质变的时候，就可能影响到集成电路的 时序功能，甚至产生功能验证的错误。所以开关噪声的分析主要集中在电源线和 地线中，其中大部分直接注入到衬底当中，注入的噪声和开关的衬底耦合噪声。 是因为衬底噪声能在衬底传输。 1 1 4电源地网络分析的必要性 在超大规模集成电路设计时，电源地( p g ) 网络分析是一个必要而且非常重 要的分析过程。随着这种尺寸的不断缩小，芯片的集成度和复杂度、工作频率大 幅的提高，电源地网络的可靠性的分析更加的重要。在高端的芯片处理器中，电 源地网络所能够承受的最大电流负荷是多少，在一些情况下这种电流可能出现因 电源地网络供电不稳定而导致的电路逻辑功能的错误，从而给整个芯片带来致命 的问题呢? 这就是要分析电源土也网络噪声的原因。 通过实验的总结得出影响噪声的因素： 1 、电源地网线的l 刮d t 噪声； 2 、电压降( 静态或动态) ： 3 、l c 振荡和电迁移( e m ) 等会引起时序偏差； 4 、逻辑错误，功耗过大等现象。 电源地网络的信号完整性传输已经成为设计电路的严峻挑战。如果电源地网 络的信号完整性能够受到重视，那么高效电源地网络分析模拟技术就能快速精确 的求解电源地网络上的电压波动，所以设计一个稳定而有效的电源地网络为这种 设计提供必要的验证指导，所以电源地网络分析是现在主要的设计思想。在整个 电源地网络分析模拟中，静态分析是最为重要和基础的一步，这个分析直接影响 到整个瞬态分析的正确性和复杂度。 3 1 2电源地网络分析的现状 电源地网络分析的重要性在于求解电路的速度、计算的精确度和c p u 占用内 存方面寻求适应的算法和求解策略。 目前，电源地网络分析的方法已经从较为简单的直流分析转化成为复杂的瞬 态分析。电源地网络的分析方法主要分为两步【2 】：1 首先对网络的非线性负载器件 进行模拟和计算，这种模拟方法是根据模拟结构的成果将器件负载等效成为分段 式线性( p w l ) 的电流源，就可以将电源地网络的分析方法等效成为带有大量独 立电流源的大集成规模的线性电路分析问题；2 利用各种快速的计算方法对等效的 带有大量的独立电流源的大规模线性电路进行分析。这种方法将要面临的问题主 要体现在等效电路的庞大性方面，传统的模拟电路工具如h s p i c e ，s s p i c e 等对 如此庞大的集成网络已经不能够良好的解决方案，因为它们在计算速度上和内存 管理上都不能够实现这种方法的计算和验证。 电源地网络最主要的作用是给在芯片各个焊点到芯片内部单元的供电。在 v l s i 物理设计中，芯片的供电网络的设计就非常重要的。在对芯片进行布线的同 时，首先，要完成电源地网络的布线工作；然后是考虑时钟线和信号线的布局问 题，在芯片布局布线完成之后，总体布线之前就要进行了电源地网络的布线工作。 电源地布线的好坏将直接影响到芯片的速度、稳定性及其可靠性。这些参数也是 分析电路的关键性指标，同时也是集成电路设计与产品直接相关的重要的一环【2 】。 在芯片中，设计电源地网络的内容主要包括三个方面： 电源线：给单元供电的，一般都是用底层的金属来设计； 电源环：一种用于给宏观模块供电的设计，主要分布在m a c r o 的周围，形成一 个环路。这个一般使用中间层的金属布线。 电源网：其功能主要是用于给顶层供电，电源通过p o w e rm e s h 和p o w e rm n g 、 p o w e fr a i l 连接，以此来达到对整个芯片的供电的效果。p o w e rm e s h 一般是用顶 层的两层金属来完成的。 由此可见，电源线和地线的连接是两条几乎涉及到整个芯片的全局线网而完 成的。其电性能和布线面积将会对整个芯片的设计和功能性产生直接的影响。由 于电流流过电源地线网络时，基本都会带来不同的电压降和金属线电迁移问题。 所以，电源地网络的设计和分析、优化将成为i c 设计的一个重要而且关键的技术 环节。 近几十年来，国内外的专家对电源地网络的分析越来越多，同时也带了更多 的方法，每个方法都有它的优点和缺点，在不同的分析场合会用到不同的计算方 法，这就要求能够准确的认识影响到这个网络的主要原因。在现阶段看重的是如 4 何建立电源地网络等效模型的设计、简化网络模型和求解网络方程组等方面。国 内对电源地网络的分析方法研究是比较少的，但是近几年来国内的i c 厂商已经认 识到这个问题，投入和分析工作也有了显著的提高。本文做这个题目的意义是降 低电源地网络的电压降问题，在完成分析和设计的同时也与在美国加州大学滨河 分校的专家们一起的讨论。清华大学、浙江大学等国内知名院校的专家们分析和 设计，本文也从他们的设计中得到了很多启示，根据他们的研究成果和论述，本 文可以更好的完成电源地网络的设计工作，总而言之，现在对于电源地网络的研 究主要集中在三个方面： ( 1 ) 电源地网络的布局布线方法； ( 2 ) 电源地网络电压降，电迁移等效分析； ( 3 ) 电源地网络布线的优化工作。 1 3论文结构 在集成电路飞速发展的今天，对电源地网络的分析是有必要的，同时本文认 识到电源地网络的分析方法和算法是一个漫长的过程。在集成电路快速发展的今 天，芯片的大小趋于小型化，因此噪声的分析也是一个很重要的环节，为了解决 这个问题，本文在电源地网络的分析技术基础上，提出了一种有效地模拟方法： e l s 优化技术。 所谓的e k o s ( e x t e i l d 硒r l o v0 f s u b s p a c e ，扩展i c 时l o v 子空间算法) 是一种 优化技术的提高和改进，这种改进也只是针对部分电路设计的。它是基于芯片上 的电源地( p g ) 网络的现有分析算法，经过对随机行走法和k 巧l o v 子空间算法 分析和结合总结出来的。论文第一大部分的工作是电源地网络现有算法分析；第 二大部分将要研究e k o s 中使用到的i ( r y l 0 v 子空间算法和设计如何有效的扩展 k r y l o v 子空间；第三部分则是对e k o s 优化技术进行重点的分析和算法代码的完 成。 本文具体章节的安排如下： 第二章是对现有算法的总结和分析：主要进行了这些算法的提出过程和算法的 优缺点，并对其中本文要用到的随机行走算法进行了更加详细的分析和计算。指 出现有的方法在大电路网络中存在的问题，为后面提出的e k o s 算法优化技术做 出了铺垫。 第三章分析了运用图论方法分析p g 网络布线问题的思想。并对p g 网络布 线问题提出了优化。第一步、通过对拓扑结构的建立，重点研究了无网格式路径 图的构建；第二步、针对块式( b b l ) 芯片绕障碍布线路径图问题进行了详细的 5 探讨。 第四章是对e k o s 优化技术中用到的硒，l o v 子空间算法的概念和算法的分类 进行了总结，并且提出m l o v 子空间算法的优点，和分析改进这种方法的意义， 从而更加有效地为e k o s 的提出做出基础性的分析。 第五章对电源地网络优化算法e k o s 进行了分析和总结。在此基础上，提出 了算法分析的基本理论，并且对要优化的电路进行了分析和相关代码的编写，并 且对其方法的延伸做了分析，在本章的最后具体介绍了代码编写和实现过程，通 过p g s i m 软件在l i i m x ( u b u n t u ) 下的运行，将s p i c e 文件导入到系统中，并且分析 了系统的输出结果，这个结果表明本文提出的方法达到了对电源地网络优化工作。 第六章对全文进行了总结，总结了目前国内外电源地网络的e k o s 优化技术 的研究和对其未来发展方向进行了一个展望。 6 2 电源地网络分析方法和设计 2 1 电源地网络布线概述 在i c 布图设计中，布线设计是连接各模块以实现芯片功能的关键环节。布线 设计不仅包括芯片内部各个功能模块的连接，还包括了各模块供电网络的连接。 没有正常的供电，芯片就不能正常工作，因此可以说，电源地线网络的布线设计 与优化问题是十分重要的研究课题。 电源地网络是由两条几乎涉及到整个芯片各个位置的全局网线构成的，对电 源地网络的设计一般可以分成两个部分【4 】： 1 确定网络的拓扑结构； 2 面积优化。 电源地线的主要的特征为电流较大，由此引起的电压降问题、金属电迁移、 功率传输噪声等现象，这些问题都会影响到开关的速度，器件的使用寿命，甚至 可能影响到芯片的逻辑错误。为此，使芯片能够具有较高的可靠性，稳定性是研 究电源地网络的主要问题。 增加线宽能够减小传输线的电阻，从而减小线上的电压降，因为电源地网络 的线宽比一般信号的线宽要大，这样一来就要占用更多的芯片面积。所以应该尽 量减少它占用芯片的面积，这也是电源地网格设计的优化目标。可以说，电源地 网络的布线面积与其他的设计是密切相关的；约束越严格，性能就越可靠。需要 的面积也就可以降低了。因此，在进行优化的同时，优化设计必须要在保证芯片 可靠性和占用面积最小化两者之间找到权衡点，要在满足约束条件下使得总的布 线面积达到最小。 2 2电源地网络分析的主要内容 在电源地网络结构模型中，一般使用dg r i d 表示电源网格，g n dg r i d 表 示地线网格，p a c k a g e 为封装引脚5 1 。如图2 1 所示： 7 图2 1 电源地网络结构模型 f i 9 2 1m o d c lo fp o w e r g r o u n dn e 铆o r k 造成芯片上电压变化的主要原因可以表示为f 5 】：v - i r + l d i d t ，其中r 和l 都是金属互联线的电阻和电感。所以，关于电源地网络设计，主要有四个关键因 素，其原理如下： 1 电压降：它是由于电源地网络互线网电阻引起的，当电流流过互联网时， 由于互联线电阻的存在导致在互联线上产生一个电压的降低。但是随着这种特性 不断传递和互联网宽度越来越小，伴随着金属层的增加进而造成了通孔数目的快 速增长，形成了相当数目的电阻和电容；这些因素给电路分析带来了内存和时间 上的问题。 2 l d i d t ：这种噪声的形成是因为互联线电压降而引起和封装引脚上的电感引 起的。当电流流过金属线时，如果电流的大小发生改变那么就会引起金属线和与 之相邻的金属线上产生一个电源突变，这就是l 耐d t 噪声 3 l c 振荡：它与l d i d t 不同，后者是一个高频现象，而l c 振荡是在低频领 域发生的，并且影响电路的正常工作。 4 电迁移效应：在电源网上金属层上会有高密度的电流，这种电流所可以引 起的金属线和其他连线的短路。因此在对e m ( 电迁移效应) 产生的影响的研究是 有必要的，而且这种情况的分析在近几年也是受到了相当大的重视。高的电流密 度和窄的金属连线是引起这个问题的最主要原因，当工艺小于0 3 5 u m 时，这种影 响就更加的明显，所以电迁移问题已经是一个必须受到重视的问题。 2 3 电源地网络分析方法 电源地网络分析在超大规模集成电路设计和s o c 中日益重要起来，这一问题 8 也逐渐成为近几年来国际和国内比较重要的研究热点。 电源地网络分析可以大致分为两个方面：静态分析和瞬态分析。静态分析主 要看的是一个静态的系统，仅仅考虑的是静态电流源和电阻对于电路的影响。如 果考虑到电路中的电容和电感问题，即全部的动态元器件，就必须考虑各个单元 模块在吸纳电流随着时间的连续变化而引起的模块电压的变化。这就是对电源地 网络的瞬态分析，在时域分析中，瞬态分析有一个基本的方法：如设定一个足够 小的时间步长( 可以根据标准) ，将一个周期内的分析问题转化成为足够多步的静 态直流求解问题，在每一个时间步长求解电路，产生一个输出电路中的节点动态 波形。 随着i c 的发展，电路的工作频率也在迅速的提高，电路中的寄生问题如寄生 电感和寄生电容和封装问题，将对电路产生逐渐扩大的影响，所以这个部分已经 是一个不可以忽略并且必须得到重视的问题，这都使得电源地网络的复杂度呈现 指数级的增长，所以电迁移问题已经必须得到重视。现有的工具如s p i c e 软件分析 电路模拟器已经不能够满足当前的分析方法。 从公开的文献来看，现有的电源地网络分析方法主要有层次划分分析法 ( h i e m r c h i c a la m l y s i s ) 、降压法( r e d u c t i o n 旬r d e r ) 、多重网格法( m u l t i 毛一d ) 、 预优共轭梯度法( p r e c o n d i t i o nc o r l j u g a t eg h d i e n t ) 、等效电路法( e q u i v a l e n tc i r c u i t m e t h o d ) 、t l m a d i 法、衬底噪声电阻宏模型分析方法、和随机行走法等【6 】。 2 3 1电源地网络分析方法的介绍 现有处理这个问题的设计方法如下： ( 1 ) 层次分析法( h i e m r c l l i c a l 知1 a l y s i s ) ：层次分析法是美国运筹学家s a a 够教 授于二十世纪8 0 年代初期提出的，它是一种实用的多方案或多目标的决策方法。 特征主要是，能够合理地将定性与定量的决策结合起来，按照思维、心理的规律 把决策过程层次化、数量化。 它又被称为嵌套法，是在大规模集成电路设计问题中比较常见的方法，其思 想是将一个大规模的问题分解为多个规模较小的子系统，这些系统问题相互之间 有时是互相独立的并且可以保持原问题性质相同性，由于分支方法产生的子问题 比较原问题规模较小，所以子系统用分治法可以再次得到更小规模的问题，反复 的使用这种方法，可以使得子系统快速的减小。如果一个大规模的网络结构可以 分成若干个小的子系统网络，即将整个大的网络分成若干个小的子网络，一直到 子网络可以得到直接解决，就是像是c + + 语言中嵌套语句一样。优点主要集中在 占用内存和运算速率上比传统的方法有优势。缺点是：网络的划分是一个多项式 9 非确定性问题【o j 。 ( 2 ) 等效电路法：等效电路法主要是根据数据结构中的拓扑结构与链状拓扑结 构的特点而形成的，它将电源地网络所有的参数等效到二叉树的根节点上，或者 是将电源地网络链上中间节点的电参数等效到链的两端节点上面。这种方法由于 采用的是精确等效，所以增加了电路的求解过程，如要把分析元素反复的在树的 叶子节点回复。当然这种方法求出的电源地网络节点电压向量是精确，这就使得 这种方法适应于树的拓扑机构【7 】。 ( 3 ) 隐含交错的迭代方法：它的时间复杂度在理论上是线性的，而且是无条件 收敛的，能够很有效的处理整个网格电路。缺点是对电路拓扑结构的分析要求过 于严格。 对于m e s h 机构的电源地网络，可以采用偏微分方程数值解的交叉隐含方法 ( t l m a d i ) 来求解电路。t l m - a d i 方法由于是对两个方向进行的交替隐含，是 绝对稳定的格式，可以对差分时间布局没有限制，从而克服了显示格式的时间布 局减小，缺点就是计算复杂度比较低：如关于时间与存储空间的线性复杂度的计 算精度比较低，同时在一阶精度还是可以正常运行的，但是要是在中等精度却有 待提高，因为这种方法必须采用一种较小的步长分析。 ( 4 ) 预优共轭梯度法：它是一种快速的线性方程组的迭代方法，充分利用了电 源地网络电路系数矩阵，经过离散和变化后得到对称、正定、稀疏和对角占有等 特点，有利于提高求解速度，但是这种方法也是存在缺点的，它并没有对电路进 行压缩，从而限制了其能够求解的电路规模，对于一个比较稀疏的正定阵的线性 方组来说，可以用共轭梯度法来求解这个方程，但是当系数矩阵比较大时，其收 敛速度会比较慢，因此要采用预优共轭梯度法来提高收敛速度，这种方法的关键 是要求待解的线性方程组的系数矩阵是一个优秀的预优矩阵。 ( 5 ) 随机行走法【8 】：此类方法是一种基于概率统计的分析法，首先将r c h o 西 方程化减为一个随机行走的过程，利用未知的几点和已知的节点在不同的路径上 有不同的概率，并且逐个求解每个未知的节点的值。此方法依赖的是开始时的v d d 节点( 初始节点) 数目。在初始时节点数是非常有限的。所以这种求解的方法是 比较慢的。 总体来说这些算法的主要思想可以分为两大类【7 】： 1 在原始电路的求解之前，首先把电路简化，缩小电路规模； 2 直接提出求解大规模线性方程组的算法，以提高模拟分析的效果。 随着电路规模的越来越大，电源地网络分析算法的总体发展方向应将这两种 思想结合在一起，首先把电路缩小到子电路，然后再利用高效的方程组来求解这 个小电路。 1 0 2 3 2随机行走法 随机行走法( r a n d o mw a l l ( ) 是2 0 0 4 年由h a i f e n gq i a n ，n a s s i 、s a p a 协e k a r 等 提出，它是一种解决电源地网络分析的新方法【8 】。这种算法充分利用了一次行走 可以获得的信息，将这些节点的一次行走化解为经过这些节点的若干次随机行走， 当到达一个未知节点时，电压值就等效成为该节点一次随机行走的开始，随机行 走法是统计学中的经典问题，通过概率模拟方法可以直接求解网络节点的电压。 随机行走法是建立在随机行走与电路网络关系基础上的，它的目的在于解决电子 系统的分析统计学方法。这种方法的一个显著的优势就是能够对其中的一个节点 产生一个可靠的分析。当仅仅需要分析一个小电路时，这种方法是非常有效的， 但是这种方法在计算整个瞬态过程中同时也存在缺点旧3 。 s 图2 2 电源地网络的局部节点 f i 9 2 2 l o c a ln o d e so f p o w c r g r o l m d 北t w o r k 在随机行走算法中，主要的应用是用电源地网络的节点电压方程与随机行走 问题的相似度进行分析，将已有的概率论知识引入到电源地网络，从而考虑从某 个节点出发到达已知的节点( 或者电源的p a d 节点) 的概率，这是该节点到临近 的节点概率的线性函数，把这个方程组的求解等效成为随机行走的问题来处理。 如上图2 2 所示，电路的节点电压是按照陆c h o 行定律和电压方程来做出公式【1 0 】： 仫昏一昏协：一五( 2 1 ) 通过移项可以得到： 阢鸯n 专 亿2 ， 从公式可以推导出，任意节点的电压都是跟其相邻节点电压的线性函数有关 的，对于一个有n 个非v d d 节点的电路，可以得到n 个不同但是类似的线性方 程组。 一 令式( 2 2 ) 中系数黟昏为肛，使得乙肛，= l 。电压和式( 2 2 ) 中的常 量一纠己黟对应于坟i ) 和m i ，则可以转化成随机行走的“收入”形式。得出公式 ( x ) = p ，! 厂( f ) + m j ( 2 3 ) 其中，f 【i ) 表示的是节点f 出发最终得到的收入，系数弘，t 代表了从节点工走到 节点f 的概率，m t 是行走过程在节点工的支付。当到达已知节点时，可以将终点的 已知电压作为一笔额外获得的收入，这种采用随机行走的方法来计算得到的结果 就是起点的待求电压。 2 4现有电源地网络分析方法的优缺点 目前电源地网络分析和设计所面临的难题主要有三个方面【l o 】： 1 网络规模不断的变大，现在可以达到上亿个节点的规模，这个求解大了难 度，通过用传统电路模拟工具( s p i c e ) 根本不可能完成这个大的规模。 2 网络存在很多非线性的器件如( 电感、电容、m o s 管) ，使得电源地网络 成为一个非线性的网络，这就需要采用更加复杂的电路分析模型这增加了分析的 难度。 3 芯片网络中电压和电流的分布依赖于处理器的指令，其为动态值，给电路 的模拟带来了许多不确定的因素。 由于这些问题的存在，电源地将要面对的是一个巨大的挑战，电源地网络的 设计优化成为近几年来国际和国内i c 电路设计界一个比较严峻的话题，随着工艺 的改进这个问题的影响程度也在不断地加深。受到学术界和工业界的高度重视。 作为一个i c 设计人员，必须分析这个问题所带来的后果，这样才能使得在生产出 的芯片能够更好的完成其应该完成的功能。 本文主要讨论的是随机行走法的优点和缺点： 按照数学上的概率论和统计学规律，可以知道随机行走法每当从相同的起始 点出发的时候，进行了n 次行走后，对得到的结果都要求其平均值，再将其作为 该节点的电压。总体来说，每次行走的终止条件可以有两种： 1 行走过程终止于一个已知的电压节点，这个电压节点包括两个方面：1 电 源p a d 节点；2 地节点( g n d ) 。 2 当行走数目超过一定的上限时候，行走过程终止，本次行走的结果不加入 到最后的平均值计算中。 在现有的相关算法分析中，随机行走算法和传统的直流分析方法只是做了简 单的比较，这种算法把其他特性基本都给忽略了，所以它是一个缺乏实验结果支 1 2 持的算法，例如：从随机行走的算法精度的分析来看，该如何选择算法中的参数 其中也包含实验次数和参数上限。 随机行走算法是把概率统计的方法带入到电源地网络中求解，主要是和传统 数值计算方法区分开来。这种算法有很好的线性时间复杂度，控制器的平均运算 时间也比较短，并且具有定位计算的优势( 只要求计算小系统的电路时他的算法 比较出色) 。但是当遇到大规模的集成电路就会出现前面提到的问题，它的应用基 础是建立在这样一个现象上一这个电路有许多已知的电源地r 网络为这个电 路供电】。总结起来主要的三个缺点是： 1 它在计算整个电源地网络时效率比较低； 2 它是根据整个网络中已知的节点来计算未知的节点，这样必然会带来误差， 从而影响了精度； 3 通过实验的验证，这种方法基本依赖于p a d 的数目，由于p a d 数目比较 少( 如一个百万点的电源地网络不可能有l 万个p a d ，即1 ) ，当遇到大规模的 电路网络时，可以想象得到这种方法的效率非常低。 2 5本章小结 本章主要介绍了近几年关于电源地网络的主要算法，和这些算法的分析过程， 并且给出了几种常见方法的意思和运算实践过程，同时指出了它们的缺点，以此 来分析目前所面临的困难。 在这几种分析方法中，层次化分析法要求的节点数目最多，计算速度也是比 较快的一种，而且发展比较迅速，相对其他算法来说也比较成熟、但是它要求子 网要被分割成几个多项式非确定性( n p ) 问题，分割过程消耗的时间完全依赖于 电源地网络的拓扑结构。与此同时，这种方法主要是针对r c 网络的，它忽略了 电感效应。考虑电感效应后，方程中的导纳矩阵的稀疏性变差，很难求解。多重 网格法能够很好的减小计算量和加速网络运算速度，但存在不能有效压缩电路的 问题。 预优共轭梯度法是用快速的线性方程来求解，但同时也存在一个问题，就是 要受到电路大小的影响，关键是为了待解的线性方程组的系数矩阵必须是一个较 好的预优矩阵。 等效法对树的拓扑结构和链式拓扑结构的电源地网络求解要求高效精确。这 个基本的隐含交错法的迭代方法能够有效的处理规整的网络电路，但是对电路的 结构要求特别的严格，这就是电路的规整度要达到这个方法可以计算的效果。最 后，本文谈到的随机行走算法。当随机行走求解比较少的节点时，能够表现的比 较好，但是当遇到比较大的电路时，对瞬态分析相对较慢，这种方法有待改进。 总结这些算法的目的是为了在以后的算法分析中，避免它们的缺点，而要充 分发挥这些算法的先进思想。 1 4 3 电源地网络及其路径的构建 讨论算法优化的前提是必须要知道电源地网络的路径。这章将要讨论这个问 题。在i c 设计的问题中，电源地网络的优化一直是一个比较重要的研究课题。它 能够直接影响到整个电路的性能表现，本章将在第一节中介绍这个布线的注意事 项、布线设计布线的步骤。在第二节提出运用图论的知识进行布线，并作为前提 详细的描述如何在芯片的内部来建一个路径图模型，同时也表达了无网格绕障碍 布线的思路和方法，为以后的章节打下一个良好的研究背景和思路。 3 1电源地网格布线的问题 i c 芯片的物理线网一般可以分成电源地和信号时钟线两种类型。其中，电源 地线的网格布线受到工艺的影响，但是随着工艺的技术不断发展，工艺技术已经 到了深亚微米范围，所以这个问题必须得到高度的重视，因此，在布线的时候它 具有优先权。其布线的结果要影响到整个芯片的性能和逻辑是否是正确的【l2 1 。 产生这种现象的主要原因是： 1 电源地网络是一个涉及到两条线的全局网络，他们的电性能会造成对芯片 的直接影响 2 电源地网络是在电阻小的金属层上优化的。这是因为金属层与多晶层的电 导特性差异很大，因此必须先在电阻小的金属层上布线，以减小功耗。 3 电源地网络尽可能的布在同一金属层上。在单层平面上布线必须满足互不 产生交叉的所谓平面性要求。 由此可见，在电源地网络布线优化的过程中实现芯片的性能在实现i c 设计上 上占有举足轻重的地位，为此，电源地的布线非常的重要。 根据现有的分析方法一般把电源地网络的布线问题分成两步： 1 建立一个适当的拓扑结构； 2 在现有拓扑结构基础上进行线宽的优化。 如前所述，电源地线网络的布局首先需要建立拓扑结构。 在介绍如何建立拓扑结构之前，需要说明一下芯片的供电方式：在芯片边界 的p g 引脚上设置有压焊块，英文简写为只仍，是整个芯片的供电设施，负责对 芯片运作提供稳定的电压。因此，在给芯片供电的网络布线的问题中，就是一个 连接优化外部p 、g 引脚到内部多个模块的问题。如图： 图3 1p a d 的供电格式 f i 辱3 1 p 0 w e rs u p p l yo f p a d 3 2 电源地网络布线问题的转化 电源地网络布线是一个区域布线问题，面向的是线网。而对于处理电路线和 节点集合的问题，图论的知识发展的已经很成熟。因此可以想到将电源地网络问 题转化成为一个图论问题【”】，然后用图论的知识寻找最好的路径，主要的解题分 为两个部分： 1 问题转换成图论问题，也就是构造一个保证含有目标路径的图： 2 应用任何适当的图论搜索方法来寻找最优的目标路径。 所以，在求解电源地网络布线的问题，首先要建立一个适合的路径，在芯片 设计上，把它分成大小形状相同的模块。 3 2 1网格路径图的构建原则 根据布线图的理论方案，构建一个含有目标路径的图的方式有两种：有网格 模式和无网格模式。网格式，即把芯片划分为若干网格，网格即布线路径，从源 点到目标点沿网格走线，这种方法的优点就是非常简单直观，但是缺点就是布线 精度低。所以本文主要的是研究无网格构建。 3 3 无网格格式的构建模型 根据上面一节的描述，网格式布线方式虽然简单直观，但也有比较明显的缺 点。由于此种方式沿网格走线，布线选择精密度受网格精密度影响牵制。尽可以 1 6 通过缩小网格大小来提高网格的精确度，以减小网格的方法可以达到布线的精度 ( 最小线宽与最小间距之和) ，但网格变小就势必会增大问题的规模，从而增加问 题的复杂程度。并且，随着深亚微米技术的高度发展，对于特大规模电路来说， 使用网格图已变得不切实际。而且网格图的通道布线模式限制连线引出端的位置 和走线的位置，造成了布线空间的浪费和降低了布通率。 所以，i c 设计会选择无网格的形式，如果不用网格就可以充分的利用布线区 域，以此来实现可变宽度，可变间距布线，这样才有利于提高布线的优化。无网 格布线直接考虑图形的几何形状，除了要求和设计规则的大小外，对于路径没有 其它的额外限制；再者对于复杂的设计规则，它有更高的灵活性，的确能提高布 通率。前面已经提到，电源地线网络布线是一个绕障碍线网布线问题，下面就绕 障碍线的网布线问题来建立无网格模式构造路径图。 3 3 1无网格布线模式的讨论 如何找到合适的图论模型，就可以把问题转化为一图论问题，图论的分析是 寻求最优化算法的前提。很多专家在这