（微电子学与固体电子学专业论文）集成电路分析中的模型降价方法研究.pdf

摘要 随着集成电路设计和制造技术的不断进步，互连延迟超过器件延迟成为了主宰芯 片性能的主要因素，互连电路的快速分析算法已成为现代电子设计自动化必不可少的 基本技术之一。但是，日益增加的工作频率和电路规模对互连电路建模和分析带来了 很大挑战。模型降阶技术是大规模互连电路分析的有效方法，而基于矩匹配的模型降 阶技术是其中主流的技术。本文针对矩匹配模型降阶方法中的两个重要问题，k r y l o v 子空间降阶模型的r l c 等效电路综合问题和具有大量端口的互连电路的模型降阶问 题，进行了研究。 在k r y l o v 子空间降阶模型的r l c 等效电路综合方面，本文提出了k r y l o v 子空间 降阶模型的纯r l c 等效电路综合方法r l c s y n 。为了能够综合出纯r l c 元件组成的 等效电路，降阶模型必须同时保持原始系统的块结构和输入输出关联矩阵结构。在 r l c s y n 方法中，提出了一种保持降阶系统的输入输出关联矩阵结构的i o p o r 方法， 并通过组合保持块结构的s p r i m s a p o r 方法和i o p o r 方法来同时保持降阶模型的 输入输出关联矩阵结构和块状结构，从而保证可以综合得到不包含受控源的纯r l c 等 效电路。为了增强电感综合的稳定性，在r l c s y n 方法中还提出了保持输入输出关联 矩阵结构的对角化技术和正则化技术来消除等效电路综合中出现的电感环问题。通过 r l c s y n 方法综合得到的i u c 等效电路不包含受控源，具有高精度、无源性和s p i c e 模拟稳定等特点，可以直接应用到现有电路分析工具中，对数字电路分析及数模混合 电路模拟具有重要意义。 在具有大量端口的互连电路的模型降阶方面，现有的基于输入相关的矩匹配方法 中，e k s i e k s 方法虽然计算复杂度低，但是数值不稳定，无法达到很高精度；而基 于线性化的降阶方法e x p l i n 和s a m s o n 虽然通过a m o l d i 类的方法消除了 e k s i e k s 中的数值不稳定问题，但是线性化系统规模很大，计算复杂度极高。本文 提出了一种计算复杂度低、数值稳定、精度高的降阶方法n h a r 。在n h a r 方法中， 提出了一种可以极大减小计算复杂度的线性化方法，得到的线性化系统与原始r l c 或 r c s 系统规模相当，并提出了数值稳定的部分正交化的方法p o a r 用于数值稳定的构 造正交投影矩阵进行模型降阶。n h a r 方法与基于增量正交化过程的e k s 和i e k s 方 法相比，具有近似相同的计算复杂度，但计算过程数值稳定，可以达到很高精度：与 基于线性化的e x p l i n 和s a m s o n 方法相比，具有近似相同的计算精度，却极大地 降低了计算复杂度。 关键词：互连电路，模型降阶，等效电路，线性化，非齐次a m o l d i 中图法分类号：t n 4 7 a b s t r a c t a st 1 1 ei cf a b r i c a t i o nt e c h n o l o g ya d v a n c e s ，i n t e r c o n n e c td e l a yb e c o m e sad o m i n a n t f a c t o rf o rd e t e r m i n i n gt h ep e r f o r m a n c eo ft h ew h o l ec h i p t h ef a s te v a l u a t i o nt o o l sf o r o n c h i p i n t e r c o n n e c t sb e c o m ea ni n d i s p e n s a b l ep a r to fc u r r e n tv l s ie d as o f t w a r e h o w e v e r ，t h ee v e r i n c r e a s i n gs i g n a lf r e q u e n c ya n dc i r c u i tc o m p l e x i t yt o g e t h e rp o s eg r e a t c h a l l e n g e st oi n t e r c o n n e c tm o d e l i n ga n ds i m u l a t i o nt e c h n i q u e s m o d e lo r d e rr e d u c t i o no v l o r ) t e e l m i q u e sh a v eb e e nw e l li n v e s t i g a t e di nt h el a s t d e c a d et oa c c e l e r a t et h es i m u l a t i o no fl a r g es c a l e l i n e a rc i r c u i t sa n ds y s t e m s t h e m o m e n t m a t c h i n gb a s e dm e t h o d sa r et h es t a t e o f - t h e a r tt e c h n i q u e sf o rm o r t h e r ee x i s t t w oi m p o r t a n tp r o b l e m sf o rt h em o m e n t m a t c h i n gb a s e dm o rm e t h o d s ，i e ，p u r er l c e q u i v a l e n tc i r c u i ts y n t h e s i sp r o b l e mf o rt h es t r u c t u r e - p r e s e r v i n gm o r m e t h o d s ，a n dm o r m e t h o d sf o ri n t e r c o n n e c tc i r c u i t sw i t hl a r g en u m b e ro ft e r m i n a l s f o rt h e s et w op r o b l e m s ， t w oa l g o r i t h m sh a v e b e e np r o p o s e di nt h i sd i s s e r t a t i o n f o rt h ep u r er l ce q u i v a l e n tc i r c u i ts y n t h e s i sp r o b l e mf o rt h es t r u c t u r e - p r e s e r v i n g m o r m e t h o d s ，ap u r er l ce q u i v a l e n tc i r c u i ts y n t h e s i sm e t h o dr l c s y ni sp r o p o s e di n t h i sd i s s e r t a t i o n t og u a r a n t e ep u r er l ce q u i v a l e n tc i r c u i t sc a l lb es y n t h e s i z e d ，b o t ht h e s t r u c t u r e so fi n p u ta n do u t p u ti n c i d e n c em a t r i c e sa n dt h eb l o c ks t r u c t u r eo ft h ec i r c u i t m a t r i c e ss h o u l db ep r e s e r v e di nt h er e d u c e d - o r d e rm o d e l s i nt h i sr l c s y nm e t h o d ，a n e m b e d d a b l ei n p u t o u t p u ts t r u c t u r ep r e s e r v i n go r d e rr e d u c t i o n ( i o p o r ) t e c h n i q u ei s p r o p o s e dt op r e s e r v et h es t r u c t u r e so fi n p u ta n do u t p u ti n c i d e n c em a t r i c e s b yc o m b i n i n g b l o c ks t r u c t u r ep r e s e r v i n gm o rm e t h o d sa n di o p o rt e c h n i q u e ，b o t ht h eb l o c ks t r u c t u r e a n dt h es t r u c t u r eo ft h ei n p u t o u t p u tm a t r i xc a nb ep r e s e r v e d p u r er l ce q u i v a l e n tc i r c u i t c a nb es y n t h e s i z e df r o mt h i sb l o c ks t r u c t u r ea n di n p u t - o u t p u ts t r u c t u r ep r e s e r v e dr e d u c e d o r d e rm o d e l i n l i n ed i a g o n a l i z a t i o na n dr e g u l a r i z a t i o nt e c h n i q u e sr r es p e c i f i c a l l yp r o p o s e d t oe n h a n c et h er o b u s t n e s so fi n d u c t a n c es y n t h e s i s t h ep u r er l cm o d e l ，h i g hm o d e l i n g a c c u r a c y ，p a s s i v i t yg u a r a n t e e dp r o p e r t ya n ds p i c es i m u l a t i o nr o b u s t n e s sm a k er l c s y n m o r ea p p l i c a b l ei ni n t e r c o n n e c ta n a l y s i s ，e i t h e rf o rd i g i t a li cd e s i g no rm i x e ds i g n a li c s i m u l a t jo n f o rt h em o ro ft h ei n t e r c o n n e c t m e t h o d sb a s e do n i n p u t d e p e n d e n t c i r c u i t sw i t i ll a r g en u m b e ro ft e r m i n a l s ，t h ee x i s t i n g m o m e n t m a t c h i n gt e c h n i q u e e i t h e rs u f f e r sf r o m n u m e r i c a lp r o b l e m si ne k sa n di e k s ，o ru n b e a r a b l em e m o r yc o n s u m p t i o na n dc p ut i m e i ne x p l i na n ds a m s o n i nt h i sd i s s e r t a t i o n ，an o n h o m o g e n o u sa m o l d i ( n h a r ) m e t h o de o n s i s t i n go fam e m o 巧一s a v i n ga n dc o m p u t a t i o ne f f i c i e n tl i n e a r i z a t i o nm e t h o da n d ap a r t i a lo r t h o g o n a l i z a t i o na m o l d ip r o c e d u r e ( p o a r ) i sp r o p o s e df o rm o ro fl i n e a r s y s t e mw i t hl a r g en u m b e ro ft e r m i n a l s w i t ht h ep r o p o s e dl i n e a r i z a t i o nm e t h o d ，t h e d i m e n s i o no ft h el i n e a r i z e ds y s t e mi sg r e a t e l yr e d u c e d a sar e s u l t ，t h ec o m p u t a t i o n a lc o s t a n dm e m o r y c o n s u m p a t i o n o ft h en h a r i sr e m a r k a b l yl o w f u r t h e r m o r e ，s i n c et h ep o a r p r o c e d u r ei sn u m e r i c a l l ys t a b l e ，n h a rm e t h o dc a l la c h i e v eh i 曲e ra c c u r a c yw h e nt h e r e d u c e do r d e ri n c r e a s e s c o m p a r e d 、i t l le k s f l e k s ，n h a rm c k l e st h en u m e r i c a lp r o b l e m s a n dc a na c h i e v eh i g h e ra c c u r a c y ，w h i l er e s e r v i n ga l m o s tt h es r n l ec o m p u t a t i o n a lc o s t c o m p a r e d 谢ie x p l i na n ds a m s o n ，n h a rc a l ls i g n i f i c a n t l yr e d u c et h em e m o r ya n d c p uc o s tw i t ha l m o s tt h es a l t l ea c c u r a c y 。 k e y w o r d s ：i n t e r c o n n e c t ，m o r , e q u i v a l e n tc i r c u i t ，l i n e a r i z a t i o n ，n o n h o m o g e n o u s a m o l d i 中图法分类号：t n 4 7 v 第一章引言 第一章引言弟一早jii 集成电路是整个信息产业发展的基础，而电子设计自动化( e d a ) 贝i j 是支持集成电 路高速发展的支柱。随着集成电路制造工艺朝着纳米级发展和电路工作频率的同益提 高，片上互连线已经取代晶体管成为决定电路性能的主要因素，性能保证的互连线快 速分析软件已成为芯片设计必不可少的工具 1 3 】 5 。模型降阶是解决电子设计自动化 中大规模互连电路分析的关键技术【2 】。本章将首先介绍集成电路的发展现状及其对互 连电路分析的影响，并回顾模型降阶方法及其在集成互连电路分析中的应用，最后介 绍本文的研究内容和主要贡献及论文的组织结构。 1 、集成电路的发展现状 集成电路的出现，开创了人类的硅文明时代，为人类开启了信息化时代的大门。 集成电路作为信息产业的基石，在国民经济中占有举足轻重的作用。自上世纪中叶第 一块集成电路诞生到现在，集成电路技术经历了从小规模，大规模和超大规模，直到 今天片上系统( s o c ) 的阶段。集成电路技术的发展主要体现在以下几个方面【4 】： ( 1 ) 电路规模和复杂性日益增大。依照摩尔定理，芯片集成度，即芯片上可容纳的晶 体管数目以1 8 个月翻一番的速度高速增长，目前单片芯片上集成的晶体管数目 已经发展到数亿量级。而片上系统( s o c ) 可以在一块芯片上集成包括c p u 、存储 器、控制器、a d 转换器的整个系统。 ( 2 ) 工作频率不断提高。集成电路工作频率提高迅速，例如微处理器的时钟频率由八 十年代的数m h z 发展到了目前的数( 3 h z 。 ( 3 ) 器件特征尺寸持续减小。近十年来，集成电路的最小特征尺寸经历了从0 1 8 9 m 、 0 1 3 9 i n 、9 0 n m 到6 5 n m 、4 5 r i m 的发展历程。集成电路已经进入纳米时代。 ( 4 ) 功耗、性能和价格矛盾的不断加剧。随着芯片尺寸的逐渐缩小，设计出同时满足 低功耗、高性能和低价格的集成电路产品变得越来越困难。如何降低集成电路功 耗方面的研究已成为目前设计和制造技术发展的重点之一。 ( 5 ) 测试成本和可制造性设计问题的日益突出。芯片测试成本在芯片开发总成本中占 有很大的比重，随着芯片规模的日益扩大，如何降低测试成本已成为集成电路开 发中的一大挑战。另一方面，随着芯片最小特征尺寸的不断减小，芯片的可制造 性设计问题开始得到越来越多的关注。 第一章弓i 言 2 、集成电路的设计流程与互连电路分析的挑战 集成电路设计通常可简单分为高层设计、r t l 级设计、物理设计三个过程。高层 设计是由设计理念到系统描述的设计过程，通过符号或高级语言对所需实现的系统行 为进行描述。完成系统的高层设计后，可以通过高层次综合或人工设计实现高层设计 到r t l 设计的转换，在r t l 级，集成电路的系统行为被分解为多个流水线、状态机 等寄存器传输级模块来实现。通过逻辑综合，r t l 级设计可以转换为门级网表。最后， 通过物理设计的布局、布线，实现门级网表到芯片版图的转换。在上述设计流程中， 模拟验证过程则贯穿从高层设计到物理设计的整个设计过程，通过模拟验证可以保证 设计的正确性。 在物理设计过程中，通常需要反复的迭代才能实现时序收敛，时序分析在物理设 计及物理设计之后的“后验证”中具有重要意义。随着集成电路器件特征的不断减小， 互连延迟超过器件延迟成为了主宰芯片性能的因素，互连线的分析在时序分析中占有 重要地位。互连电路的快速分析已成为现代电子设计自动化必不可少的基本技术之 一。集成电路的高速发展对互连电路分析的挑战主要表现在以下两个方面： ( 1 ) 互连线的电磁耦合严重。在集成电路发展的初级阶段，互连线实现了器件之间的 连通，电信号可以通过互连线实现理想传输。随着芯片工作频率的提高，互连线 间的电磁耦合越来越严重，电信号通过互连线传输会产生延迟、振荡和衰减等非 理想效应，严重影响集成电路的性能【6 】。为了精确分析互连线的电磁行为，通常 通过参数提取来获得互连线的等效r l c ( 电阻、电感、电容) 模型【7 1 3 1 6 1 。近年 来提出的基于电感的电纳参数( s u s c e p t a n c e ) 的r c s ( 电阻，电容，电感电纳) 模型 【1 4 1 1 1 5 1 ，由于电感电纳参数( s u s c e p t a n c e ) 矩阵具有对称性、稀疏性和正定性等优 良特性，己被广泛应用到互连线分析中 4 8 5 l 】。 ( 2 ) 互连线规模日益庞大。由于芯片内互连线规模庞大，互连线之间的耦合众多，互 连线的等效r l c 或r c s 电路规模庞大，电路阶数通常可达数万到数十万阶 6 】 7 。 传统的电路模拟工具无法实现对如此大规模互连电路的有效分析 5 【6 】。对大规模 互连电路的快速分析，是目前以及将来集成电路性能分析和验证所需要解决的基 本问题之一【6 】。 3 、 集成电路互连分析中的模型降阶方法 模型降阶方法是分析大规模互连电路的有效方法之一。互连电路的r l c 和r c s 模型可以通过一阶或二阶微分方程组来描述【1 5 1 7 1 9 。这些微分方程组的状态变量 个数可达数万到数十万。描述互连电路的微分方程组，一方面从数学上描述了电路的 行为；另一方面，由于互连电路是真实的物理系统，电路的实际物理特性如无源性【2 2 】、 物理结构 7 】【1 4 】在微分方程组中也有所反映。这些物理特性主要体现在微分方程系数 2 第一章引言 矩阵的特有矩阵结构和性质上。模型降阶方法的基本思想是寻找一个小规模的降阶系 统来代替原始大规模系统。降阶系统不仅要在数学上能代替原始大规模系统，在物理 上也应能代替原始大规模系统。从数学角度出发，降阶系统应逼近原始大规模系统输 入输出关系。从物理角度出发，降阶系统应保持原始大规模系统的无源性、系统结构 等物理特性。系统的无源性保证了降阶系统的耗尽性，可以保证降阶系统仿真时的稳 定性【2 2 】。降阶系统保持原系统的物理系统结构，则为降阶系统的物理实现提供了可 能。同时，模型降阶方法是一种数值计算方法，所以模型降阶需要考虑的另一关键问 题就是计算中的数值稳定性问题。数值稳定的模型降阶算法，由于算法设计合理，可 以极大地减小数值舍入误差对计算的影响，从而达到很高的计算精度，保证降阶系统 对原始大规模系统的逼近精度。相反数值不稳定的模型降阶算法，因为舍入误差的影 响，则无法提高降阶系统的逼近精度【3 1 7 1 【7 3 。 模型降阶算法的发展正是围绕着精确逼近原系统输入输出关系、保持原系统无源 性、保持原系统结构和数值稳定这几个方面展开的。在互连电路分析中主流的模型降 阶方法包括两大类：平衡截断类算法( t b r ) 和矩匹配类算法。 平衡截断类算法来源于控制理论 5 5 5 6 】。对于线性系统，一方面其内部状态可以 通过外部输入的驱动而改变：另一方面内部状态对系统输出会产生一定的影响。线性 系统的输入输出关系正是因内部状态而联系在一起的。通过外部输入控制内部状态改 变的难易程度可以理解为系统状态的可控制性，而内部状态对系统输出的影响的难易 程度则可以理解为系统状态的可观性。平衡截断法【5 5 】【5 6 】的基本思想就是舍弃那些对 系统输入输出关系影响较小的内部状态。但是，在这些内部状态中，可能某些状态具 有很强的可控制性，却具有很弱的可观性，或者相反。这些状态难以判断是否应该舍 弃。在控制理论中，可以通过可控性和可观性的g r a m m i a n 来定量衡量系统的可控性 和可观性 5 5 1 。在平衡截断法中，首先通过对原系统进行线性变换，使得系统的可控 性和可观性的g r a m m i a n 相同，从而系统所有内部状态的可控制性和可观性相等，得 到的系统是一个可控可观“平衡的 系统。对于“平衡的”系统，可以通过简单的舍 弃那些可控性和可观性都不强的系统内部状态达到降阶目的。这一“截断 过程对系 统输入输出关系的影响较小，可以保持模型降阶的精度。平衡截断法具有理论的误差 界，可以保证降阶系统传递函数在全频范围内与原系统的传递函数误差在一定范围之 内【5 5 【5 6 】。但是，平衡截断法需要通过求解两个l y a p u n o v 方程来求解系统的可控性 和可观性o r a m m i a n ，计算复杂度达到d 帕，其中n 是原始系统阶数 6 6 。 平衡截断法具有极高的复杂度，无法直接应用于大规模互连电路降阶问题。学术 界提出了许多基于迭代的快速平衡截断方法，这些方法多通过组合k d , l o v 子空间方法 和平衡截断法来近似求解系统可控性和可观性g r a m m i a n 5 7 6 4 】。近年来，也有学者 提出基于数值积分求解系统可控性和可观性o r a m m i a n 的快速平衡截断方法【6 5 】 6 6 】。 第一章引言 这些快速平衡截断法，采用的是近似的方法来求解系统可控性和可观性g r a m m i a n ， 虽然降低了计算复杂度，但是却无法保证理论上的误差界，失去了平衡截断法的最大 优势。保持系统的无源性也逐渐成为了平衡截断类算法的关注热点【6 7 】【6 8 】。这一类算 法通过求解代数r i c c a t i 方程来获得投影矩阵对系统进行降阶，可以保证降阶系统的无 源性，同时也具有理论的误差界。直接求解r i e c a t i 方程计算复杂度很高，在文献【6 8 】 中提出了近似求解r i c c a t i 方程的快速方法。总的来说，平衡截断类算法虽然在计算复 杂度和无源性方面都取得了一定的突破，但是却未能在互连分析领域得到广泛应用， 其中一个重要的原因是平衡截断类算法在理解和实现上较为复杂 6 6 】。 在互连分析领域应用最为广泛的模型降阶算法是矩匹配类的算法 【2 3 2 6 3 1 - 4 0 4 3 5 1 】。线性系统的输入输出关系可以通过传递函数来完全刻画，这些 传递函数实际上是具有特定形式的有理多项式函数。矩匹配类算法的理论基础是p a d 6 逼近【3 0 】。p a d 6 逼近通过有理多项式去逼近被逼近函数，并保证有理多项式与被逼近 函数的若干阶泰勒展开系数相等。对于矩匹配的模型降阶方法，从传递函数的角度去 分析，就是采用低阶的有理多项式函数去逼近高阶的有理多项式函数，并保证两者的 若干阶泰勒展开系数相等，由于传递函数的泰勒展开系数也被称之为矩，所以这一过 程又被称为“矩匹配。矩匹配实际上是一种p a d 类的逼近 3 0 】。 对于r l c 电路一阶系统的模型降阶，l p i l l a g e 等人于1 9 9 0 年首次提出了 a w e ( a s y m p t o t i cw r a v e f o r me v a l u a t i o n ) 的矩匹配降阶算法【2 3 】，这算法通过显式计算 原系统的传递函数的矩，并通过矩匹配直接计算降阶系统的传递函数的有理多项式的 系数。a w e 方法在上世纪九十年代得到了广泛应用 2 4 2 6 】，但是a w e 方法中显式计 算传递函数的矩包含一个矩阵向量的幂迭代，有严重的数值问题，在实际应用中，降 阶系数阶数超过1 0 阶后，降阶精度很难提高【3 1 】。为了解决a w e 算法存在的数值稳 定问题，基于k r y l o v 子空间的投影的方法陆续被提出 3 1 4 0 4 3 5 1 】，逐渐成为基于矩 匹配的模型降阶的主流算法。基于k r y l o v 子空间投影的降阶方法，首先通过数值稳定 的a m o l d i 2 9 或l a n c z o s 2 7 2 8 过程构造由原系统状态变量矩构成的k r y l o v 子空间的 正交双正交基，然后利用这些正交双正交基对原始系统进行正交双正交投影得到降 阶系统，代表性的算法包括基于l a n c z o s 过程的p v l 类算法【3 1 】【3 2 】 3 4 】【3 5 【4 0 】和基 于a m o l d i 过程的降阶算法【3 7 】 4 3 】【4 4 4 5 】。采用k r y l o v 子空问投影的方法也可以保 证降阶系统传递函数与原始系统传递函数的矩匹配，这种矩匹配是通过投影实现的， 所以也被称为“隐式 矩匹配【3 l 】。为了进一步保持降阶系统的无源性，学术界提出 了p r i m a 算法 4 5 】。p r i m a 算法也是一种k r y l o v 子空间的降阶方法，它通过a r n o l d i 过程构造投影空间，并借助合同变换来保持降阶系统的无源性【4 l 】【4 2 】。合同变换保持 无源性的思想对以后的模型降阶算法发展产生了较大影响，p r i m a 之后的模型降阶算 法多通过这一思想来保持无源性【4 7 5 1 。p r i m a 算法因为其算法实现容易、计算复杂 4 第一章引言 度较低、数值稳定性好具有较高精度、且可以从理论上保证降阶系统的无源性，在工 业界得到了广泛应用。近年来，保持系统结构又成为了模型降阶的研究热点。在文献 【4 7 】中，r w f r e u n d 等人提出采用分块投影的方法来保持降阶系统的块状结构的 s p r i m 算法。s p r i m 算法保持了系统块结构，有利于降阶系统的物理实现。分块投 影的方法是保持系统结构的一种重要技术，可以在模型降阶中获得更广泛的应用 因为有了一阶系统模型降阶的研究基础，r c s 电路二阶系统的降阶方法的发展具 有较高的起点，二阶系统降阶方法发展初期就采用了合同变换投影降阶的方法【4 8 】， 这一方法一方面保持了系统的块结构，另一方面也保持了系统的无源性【4 8 】。所以r c s 电路二阶系统的降阶方法的研究主要集中在精确的矩匹配和数值稳定性两个方面。在 文献【4 8 】中，e n o r 算法提出采用显式计算矩的方法来构造投影空间。由于显式计算 矩的数值不稳定性，e n o r 算法与a w e 算法一样无法达到较高降阶精度【5 0 】。在文献 【4 9 】中，s m o r 算法对二阶系统的矩递推过程进行了简化，并采用k r y l o v 子空间方法 构造二阶系统投影空间。s m o r 算法由于采用k r y l o v 子空间构造投影空间，具有较高 数值稳定性，但是由于其对矩递推过程进行了简化，无法保证降阶系统与原系统的精 确矩匹配，降阶系统与原系统具有较大误差【5 0 】。在文献1 5 0 5 1 7 2 ，提出了采用 数值稳定的二次a m o l d i 过程 5 2 5 3 1 1 5 4 1 构造二阶k l y l o v 投影空间的s a p o r 方法。 s a p o r 方法数值稳定，可以保证精确的矩匹配，在降阶精度上要远远超过e n o r 4 8 1 和s m o r 4 9 算法，是r c s 电路二阶系统降阶最好的算法。 4 、本文的研究内容和主要贡献 虽然模型降阶方法在互连电路模型降阶中取得了巨大成功。但是模型降阶方法仍 然有许多困难需要解决。其中就包括： 1 降阶模型的r l c 等效电路综合问题。r l c 或r c s 电路经过模型降阶后得到 的是低阶的一阶或二阶系统的数学表示形式。这些低阶的一阶或二阶系统的数学表示 形式无法直接应用于静态时序分析、动态仿真、噪声分析、电路检查、功耗分析等分 析和验证过程 7 4 7 8 1 。这些应用都希望直接得到低阶的r l c 或r c s 电路形式，而不 是数学表示形式。在文献 3 4 】中，r w f r e u n d 等人提出了单输入单输出r c 电路的降 阶模型的等效电路综合技术。对于基于p r i m a 方法的多输入多输出r l c 电路的降阶 模型的等效电路综合方法在文献 8 0 1 有很好的总结，由于p r i m a 方法无法保持电路 的结构，在综合得到的等效电路中不可避免的存在众多的受控源，无法应用于静态时 序分析、动态仿真、噪声分析等分析和验证过程【7 4 7 8 1 。 2 具有大量端口互连电路的模型降阶问题。在互连电路中有很多具有大量端口电 路的例子，如电源地网络、时钟树网络和大型总线电路 8 3 8 5 8 9 】。矩匹配的模型降 第一章引言 阶方法受到输入端口数目的限制，这是因为在匹配相同矩数目的条件下，矩匹配降阶 的降阶系统阶数与输入端口个数成正比【8 6 】。因此，具有大量端口的互连电路对矩匹 配的模型降阶算法提出了很大的挑战。为解决具有大量端口的互连电路模型降阶的问 题，学术界提出了两类方法。第一类方法利用了互连线的规整性或者输入波形的相关 性来构造紧凑的降阶模型【8 4 】【8 5 】【8 6 】。在文献【8 5 】【8 6 】中，由于具有大量端口电路互连 电路的规整性，其传递函数矩阵的各项之间存在很强相关性，通过奇异值分解的技术 可以得到相对低阶的降阶模型；在文献【8 4 】中，利用输入波形的相关性，可以通过输 入相关的平衡截断算法得到紧凑的降阶模型。另一类针对具有大量端口互连电路的模 型降阶算法是输入相关的矩匹配算法【8 7 9 1 】。这一类算法，在构造投影矩阵空间时考 虑了电路输入，这样投影空间的大小就不再受到输入数目的影响 8 7 】。但这一类方法 涉及到一类扩展的k r y l o v 子空间的投影空间的构造问题 8 7 】。学术界目前提出了两类 方法来解决这一问题，第一类方法包括e k s 8 7 和i e k s 8 8 8 9 方法，通过增量的正 交化过程来构造扩展的k r y l o v 子空间的正交基。这一类方法计算复杂度低，但是存在 数值稳定性的问题，无法得到高精度的降阶模型。第二类方法包括e x p l i n 9 1 和 s a m s o n 9 0 方法，通过线性化的方法将扩展的k r y l o v 子空间的投影空间的构造问题 转化为标准的k r y l o v 子空间投影空间构造问题，避免了数值稳定性的问题，但是由于 线性化系统的维度很高，计算复杂度极高，无法应用于大规模系统。 本论文主要针对上述模型降阶方法存在的两大问题开展了研究： 1 针对降阶模型的r l c 等效电路综合问题，本文提出了k r y l o v 子空间降阶模型 的纯r l c 等效电路综合方法r l c s y n 。为了能够综合出纯r l c 元件组成的等效电路， 降阶模型必须同时保持原始系统的系统矩阵块结构和输入输出关联矩阵结构。在 r l c s y n 方法中，提出了一种保持降阶系统的输入输出关联矩阵结构的i o p o r 方法， 并通过组合保持块结构的s p r i m 4 7 s a p o r 5 0 5 1 和i o p o r 方法来同时保持降阶模 型的输入输出关联矩阵结构和系统矩阵块状结构，从而保证可以综合得到不包含受控 源的纯r l c 等效电路。为了增强电感综合的稳定性，在r l c s y n 方法中还提出了保 结构的对角化技术和正则化技术来消除等效电路综合中出现的电感环问题。通过 r l c s y n 方法综合得到的r l c 等效电路不包含受控源，具有高精度、无源性和 s p i c e s 1 8 2 模拟稳定等特点，可以直接应用到现有电路分析工具中对数字电路分 析及数模混合电路模拟具有重要意义。该成果发表在s c i e 收录期刊c o m m u n i c a t i o n si n c o m p u t a t i o n a lp h y s i c s 2 针对具有大量端口互连电路的模型降阶问题，本文提出了一种计算复杂度低、 数值稳定、计算精度高的具有大量端口互连电路的模型降阶方法n h a r 。n h a r 方法 基于输入相关的矩匹配方法，提出了一种可以极大减小计算复杂度的线性化方法，得 到的线性化系统维数极大减小，与原始r l c 或r c s 系统规模相当；基于这一线性化 6 第一章引言 方法，还提出了数值稳定的部分正交化的a r n o l d i 方法p o a r 用于数值稳定的构造正 交投影矩阵进行模型降阶。n h a r 方法与基于增量正交化过程的e k s 8 7 】和 i e k s 8 8 8 9 方法相比，具有近似相同的计算复杂度，但计算过程数值稳定，可以达 到很高精度：与基于线性化的e x p l i n 9 1 和s a m s o n 9 0 方法相比，具有近似相同 的计算精度，却极大地降低了计算复杂度。n h a r 方法计算复杂度低、数值稳定、计 算精度高，可以有效的对具有大量端口电路，如电源地网络、时钟树网络和大型总线 电路进行降阶分析。该成果已投稿s c i e 收录期干i ji n t e m a t i o n a lj o u r n a lo fc i r c u i tt h e o r y a n d a p p l i c a t i o n s ，已通过第一轮审稿，正在修订中。 5 、 本文的组织结构 本论文的组织结构如下，第二章将对主流的基于矩匹配的模型降阶算法进行总结 回顾。第三章将提出降阶模型的等效电路综合方法r l c s y n 。我们将首先提出保持输 入输出的模型降阶算法i o p o r ，然后提出降阶模型的等效电路综合技术。第四章中将 提出针对具有大量端口互连电路的模型降阶降阶方法n h a r 。我们将首先介绍输入相 关的矩匹配理论，并回顾输入相关的矩匹配方法，包括增量正交化的方法e k s 8 7 和 i e k s 8 8 8 9 ，以及基于线性化的e x p l i n 9 1 和s a m s o n 9 0 方法，然后提出可以极 大减小计算复杂度的线性化方法和数值稳定的部分正交化的a m o l d i 方法p o a r 。在 第五章中，将对全文进行总结，并对未来研究工作做出展望。 7 第二章集成电路分析中的矩匹配模型降阶方法回顾 第二章集成电路分析中的矩匹配 模型降阶方法回顾 矩匹配的模型降阶方法在集成电路互连分析中应用较为广泛，本章将首先介绍 r l c 和r c s 电路的数学模型、投影降阶的的数学框架、矩匹配定理及无源性的数学定 义，然后对主流的矩匹配的模型降阶方法进行回顾。 l 、r l c 和r c s 电路的数学模型 互连线可以通过r l c 和r c s 的电路模型来建模，本小节将对互连线r l c 和r c s 电路模型的数学描述进行介绍。 i i 、r l c 电路的数学模型 互连电路经过参数提取后，可以得到由电阻、电容和电感组成的r l c 电路模型。 对于一个p 输入g 输出的r l c 的电路可以通过以下的改进的节点电压方程去描述【1 9 】， p 卜咧端毛 ， 这里，甜和y 向量分别表示输入和输出向量。而 q 兰瞄司q 三 渊 r v x 三1 i o 和任意的复向量z ，满足 z 叮( q ( j ) + r ( s 幸) ) z o 。 二次系统( 2 1 4 ) ，其无源性定义与定义2 - 1 相似，这里不再给出具体定义，可以 参考文献 4 8 】。 3 、投影降阶框架 互连电路的模型降阶方法大多基于投影的方法【2 0 】 2 l 】，在本小节将介绍投影降阶 的框架。投影降阶的方法实际上基于g a l e r k i n 投影原理【7 1 】。对于一阶线性系统( 2 3 ) 而言，投影降阶首先寻找一个“表示空间”，我们假设“表示空间 的基为y r 肌打， 状态变量x p 用“表示空间”的基来近似表示可得 x ( s ) 厩( s ) ( 2 - 1 7 ) 将( 2 1 7 ) 式带a ( 2 3 ) ，可得采用y 来近似表示工之后的系统残量如下 = ( q + 5 e ) 路( j ) 一色“( s ) ( 2 1 8 ) 根据g a l e r k i n 投影方法的原理，应寻找另外一个“测试空间使得系统残量与这 一测试空间垂直，假设这一测试空间的基为w r 胀厅，使系统残量与之垂直，可 以得到 形7 = 0 ( 2 1 9 ) ( 2 1 9 ) 式可以进一步写成 矽7 ( q + s e ) 坛( s ) = 形7 只“( s ) 因此，( 2 3 ) 式所表示的阶系统，经过g a l e r k i n 投影之后， 表示为 ( 2 - 2 0 ) 得到的降阶系统可以 ( 童+ s 皇) 曼( s ) = 劫( s ) ( 2 - 2 。) 【夕( s ) = 丘7 舅( 了) 、。 这一降阶系统的阶数为丹，其中童= 矿7 q y ，皇= w7 e y ，豆= 形r 色， 丘= 矿7 t 。如果肜v ，这一投影过程为斜投影；如果肜= y ，这一投影过程为正 投影。同样，我们可以得到线性系统( 2 2 1 ) 的传递函数 岛( s ) = 舞= 丘r ( 童+ s 盯最 ( 2 - 2 2 ) 值得一提的是，在一阶系统投影降阶方法发展的早期阶段 3 1 1 1 3 3 1 ，采用的是如下 以) x ( s ) y ( s ) 1 2 裂， 陋2 3 ， 惭 影，1 投行进来统系 的 价等 、j 0 q 统系与 第二章集成电路分析中的矩匹配模型降阶方法回顾 这里4 = q - 1 c ，r = q _ 1 最。对系统( 2 2 3 ) 通过矿和矿两个空间来投影降阶 得到 ，+ & 砬； 三；三乏墨翟， c 2 2 其中盈= 形7 4 矿，最= 形7 疋。与对系统( 2 3 ) 降阶相比，对( 2 2 3 ) 式降阶的好 处在于不需要计算j ，= 矽7 以y 的过程，因为五可以在构造渺和矿两个空间正交基 时直接得到，但是降阶系统( 2 2 4 ) 却失去了原始系统( 2 3 ) 的结构，系统的无源性也无 法保证。 对于二阶系统( 2 1 5 ) ，我们有类似的结果。假设表示空间”的基为p r m ， 而“测试空间”的基为q r ”，经过投影的过程，我们可以得到二阶系统( 2 一1 5 ) 的 俾阶系统 j ( g + s 。+ 喜f ) 移( s ) = 雪“( s ) 。2 2 5 ， i夕