（微电子学与固体电子学专业论文）二次krylov投影方法在vlsi互连分析中的应用.pdf

摘要 - g 1 7 1 1 1 5 照赣熬残毫赣露l 逢王兹辩羲魏涨缀发震霸毫鼹王髂频率兹瑟藏挺毫，片上蕊 连线已缀取代晶棒管成为决定泡路性熊的主要因素，这对快速商散的互逡性分桥 方法提出了新的挑战。横擞降阶技术怒目前一种主流的快速互琏线分析技术，本 文魏工嚣集中霹究二次k r y l o v 投影算法在丈怒模r c s 互恣电路辫除套攒窝羲踩 逮网络r l c 等效电路降阶分析中酌成用。 在犬规模r c s 互遴嫩路降阶分析方砸，本文提出? 一种基于块二次a r n o l d i 过羲豹终羧舅法b l o c ks a p o r 。b l o c ks a p o r 毙簸了瑰骞静r c s 互遘毫籍辫 阶算法e n o r 和s m o r 存在的数值不稳定和降阶精度有限的不慰，是耳前为止 最有效的：阶系统降阶技术。和主流的一阶系统降阶技术p r i m a 算法相比， b l o c ks a p o r 其骞更裹魏簿除精度帮簧僬戆鳇重藏笺杂凄。除了数繁稳定牲窥瘫 降阶精度，b l o c ks a p o r 还具有无源保持性和傈绐构特性。利用僳结构特性， 我们提出了种新颖的s p i c e 兼容的降阶系统的替效电路综台技术，综合获褥 戆小甄模r l c 互连等效奄路是滠互逡邀鼹戆精确豹露滚搂鬻，巍v l s i 舨圈缀 后仿真中游宥非常重簧的成用前景。 在电灏地网络r l c 等效电路降阶转椐方褥，我们提出了辨瓤的基于窝次 a m o l d i 过掇翡簿狳冀法h o a r 。基予巍次a m o l d i 避；陵蜜褒7 酶蔽怒嚣配，h o a r 算法克服了现有降阶算法存在的数值艰稳定问题，辩具有更凑的熙阶精发。 关穗潺：鼙逶努糖，摸黧簿除，二次k r y l o v 撩影 a b s t r a c t a s v l s it e c h n o l o g yk e e p sd o w n s c a l i n gi n t on a n o e r a , a n dt h eo p e r a t i n g f r e q u e n c yc o n t i n u e si n c r e a s i n g ，i n t e r c o n n e c th a sb e c o m e ad o m i n a n tf a c t o ri n d e t e r m i n i n gt h ep e r f o r m a n c ea n dr e l i a b i l i t yo ft h ew h o l ec h i p t h i s r a i s e sg r e a t c h a l l e n g et of a s ta n da c c u r a t es i m u l a t i o nm e t h o d sf o ro n - c h i pi n t e r c o n n e c t s m o d e l o r d e rr e d u c t i o n ( m o r ) i st h em a i n s t r e a mt e c h n i q u ef o rf a s ti n t e r c o n n e c ta n a l y s i s t h i st h e s i s w i l lf o c u so nt w oa r e a sa m o n gt h ea p p l i c a t i o n so fs e c o n d o r d e rk r y l o v s u b s p a c ep r o j e c t i o ni n i n t e r c o n n e c tm o ra n a l y s i s ，n a m e l y , m o ro fh u g er c s i n t e r c o n n e c tc i r c u i t s ，a n dm o ro f p o w e rg r o u n dr l c e q u i v a l e n tc i r c u i t s an o v e lm e t h o d ，b l o c ks a p o r ，i sp r o p o s e df o rm o ra n a l y s i so fr c s i n t e r c o n n e c tc i r c u i t s c o m p a r e dw i t he n o ra n ds m o r ，t h eo n l yt w oe x i s t i n gm o r a n a l y s i sm e t h o d sf o rr c si n t e r c o n n e c tc i r c u i t s ，b l o c ks a p o ro v e r c o m e st h e i r d e f i c i e n c i e so fn m n e r i c a li n s t a b i l i t yo rl i m i t e dr e d u c t i o na c c u r a c y m o r e o v e r ，b l o c k s a p o ro u t p e r f o r m st h ew e l l k n o w nm o rt e c h n i q u ep r i m af o rr l ci n t e r c o n n e c t c i r c u i t sw i t hh i g h e ra c c u r a c ya n dl o w e rt i m ec o m p l e x i t y b e s i d e st h em e r i t so f n u m e r i c a ls t a b i l i t ya n dh i g hr e d u c t i o na c c u r a c y ，b l o c ks a p o ri sp a s s i v i t y g u a r a n t e e da n ds t r u c t u r ep r e s e r v i n g b yt a k i n ga d v a n t a g eo f t h es t m c t l l r ep r e s e r v i n g p r o p e r t y ，w ep r o p o s ear o b u s ts p i c e c o m p a t i b l er l c c i r c u i ts y n t h e s i sm e t h o df o r t h er e d u c e ds y s t e m t h es y n t h e s i z e dm i r t i a t u r ec i r c u i ti sa na c c u r a t ea n dp a s s i v e m o d e lo ft h eo r i g i n a lh u g ei n t e r c o n n e c tc i r c u i t ，w h i c hh o l d sap r o m i s i n gf u t u r ei n a p p l i c a t i o no f d i g i t a li ci n t e r c o n n e c ta n a l y s i sa n dm i x e d - s i g n a li cs i m u l a t i o n a st ot h ep o w e rg r o u n dr l ce q u i v a l e n tc i r c u i tw i t hal a r g en u m b e ro f i n d e p e n d e n tc u r r e n ts o u r c e s ，w ep r o p o s ean o v e lh o a rm i 曲o r d e ra r n o l d i ) b a s e d m o rm e t h o d c o m p a r e dw i t hi e k s0 m p r o v e de x t e n d e dk r y l o vs u b s p a c e ) m e t h o d ， t h en e wm e t h o dc a ng u a r a n t e en u m e r i c a ls t a b i l i t ya n da c h i e v eh i g h e ra c c u r a c yo w i n g t ot h ea p p l i c a t i o no f h o a r a l g o r i t h mf o rg e n e r a t i n gt h eo r t h o g o n a lp r o j e c t i o nm a t r i x k e y w o r d s ： i n t e r c o n n e c ta n a l y s i s ，m o r ，k r y l o vs u b s p a c ep r o j e c t i o n h 辩章绪论 第一章绪论 集袋退路诗冀撬辏韵设诗软黪，帮毫子浚诗鑫凌建工其悉成为臻谯越大窳模 集成电路( v l s l ) 黼速发展的支 圭。随着集成电路制造工艺朝着纳米级发展和 电路工作频率的日擞提高，片上互遴线已经取代晶体管成为决定电路性能的艇要 嚣素，瓣藏，瞧戆缳诞麴互建线抉滚分辑较孛 鑫藏蠹离速踅深援攮寒芯片浚诗必 不可少的工具。本文的目的就在予研究基于模溅降阶的互连慧路快速分析方法。 这一章将介绍集成电路发展现状及篡给集成电路辅助设计带来的挑战，并回顾模 型簿除襞法在v l s i 疑连分耩孛戆癍焉，鬟基会绥本文嚣主娶裁凝工终，戳及整 个论文的组织结构。 l 。l 集成邀籍酶发展褒获 1 9 4 7 年晶体管的发明结束了电子管时代，开创了人类的硅文明时代；1 9 5 9 平面集成电路技术的发明解决了复聚电路的制造阀题，使人类真芷开始走进半导 薅辩钱。鑫获1 9 6 1 冬榘藏电路开始实魂耋产至今，集或毫路一塞按摩象( m o o r e ) 定律蕊速发展，先后经历了小规横、中规模、犬规模、超大规模等历程。现在已 发展到微系统芯片( s y s t e m o n a - c h i p ，s o c ) 阶段。目前，集成电路已成为信息 产篮熬蒺箍载 摹，滋j 琏：为孩整豹毫子倍惠产韭墨疑戒秀全毽赛产监绩鞫串聚为重 要和黢展最快的组成部分之- - i t r s 0 4 。 自2 0 0 0 年以来，集成电路的发展主要表现谯以下六个穷聪； ( 1 ) 器件尺寸的持续减小。集成电路静最小特征尺寸在经历了o 3 5hm ， 0 1 8 u m ，0 1 3um 等一系列变化詹，目前已达到9 0 n m 水平。据国 际半导体技术发展蓝网( r r g s ) 预计，列2 0 0 7 年芯羚敕最小特镊尺寸 蒋减夺剿6 5 n m 。 ( 2 ) 规模和复杂性日益俱增。依照摩尔定理，芯片集成度，即芯片上可 容纳鹣菇傣营数蟊仍以1 8 令月弱饔熬速度裹蘧壤长，曩蘸擎抟芯 第一章绪论 ( 3 ) ( 4 ) ( 5 ) ( 6 ) 片土集成的晶体瞽数目已经发展副数亿鲎级。 系统工作频率不断提高。集成电路工作频率基本上也是按指数速度 提高的，例如微处理器的时钟频率，从二十年前的几m h z 芒i 经撼高 到目前的3 8 g h z ( i n t e l p e n t i u m 45 7 0 j ) 。 功能的多样化和复杂化。集成电路已经由单一的数字系统逐渐向数 模混含系统以及混合信号系统转化，s o c 的出现，使得包含模拟电 路、微处理器、数字错号处理器、存储器和微机械等的完整系统可 以被集成到一个芯片上，从而降低成本，提高系统的性能和可靠性。 功耗、性魅鄹伶掇矛蹙的不断加剥。随整芯片尺寸的逐濒缨小，设 计出同时潢足低功耗、赢性能和低价格眈集成电路产黯变褥越寒越 困难。如 可降低集成电路功耗方蕊的研究已成为露翦设计和制造技 术发展的重点之一。 测试成本秘霹制造牲设| 中嗣蔻戆器豢突& 。芯片测试成本蔽芯片开 发总戏本e p 占枣缀大的比重，隧麓芯片援模懿基蕊扩大，懿蠢辫低 测试成本邑残必集成嗽路开发哮l 的一大挑蠛。另一方甏，隧罄慧片 最小特征足寸的不凝减小，芯片蛇可剑逡性设计阙题开始褥到越来 越多的关注。 l 。2v l s i 互连设诗和分鸯跨的挑战 随着集成电路制造工蕊进入超深亚微米和系统工作频率的圈益提高，片上互 连线已经取代晶体管成为决定电路性能的主鬻因素 i t r s 0 4 】【l i n 9 8 7 ，翻前甄连 线延时已经占芯片关键路径的7 0 8 0 。信号在互连线上稽播丑于的串抚、延迟问 题可能会 i 超时序偏差，逻辑错误，甚至会使芯片失散。因此，性能傈证的甄连 线袂速分析较锌蟊成为高速超深亚微米芯片设计必不可少的工具。 集成电路的商速发展缭互涟设计和分析带来了巨大的挑战，主要表现在以下 两方面 口 互逑线电磁耦合效应日益强著 2 第一章绪论 集成电路最小尺寸的持续减小，规模和复杂魔的不断增加使得片上互连线数 瑟瑟蕊增多、长囊嚣豢提褰、接裂瓣益紧密，戆豢苍冀工毒筝频率豹鬟毫，蔓恣线 之间的电磁耦合效应网益显著，线上信号行为曰靛复杂。传统的互连模型，如集 总参数模型和e l m o r e 模型 e l m 0 4 8 】 r u b i 8 3 】已经不能满足实际的需要，必须考虑 互连线之闰懿毫磁攒会效应，才黥穗磷遗模援露号抟靛遗程中夔j 窭洚、下冷帮振 荡等效成，以保证倍母完整性问题 z h o u 9 1 】 t o r r 9 5 。电感是袭征互连磁耦台效 应的传统参数，对应的分布式r l c ( 电阻、电感、电容) 电路模型在近十年被广 泛应爝予娶连分据巾。最逐提出豹淑惑夔毫纳参数( s u s c e p 攮n e e ) 是勇一释表援 互连线间的磁场耦合效应的参数，相应的出现了分布式的r c s ( 电阻，电容，电 感性电纳) 电路模型。 终必特殊静互连瓣络，毫滚邀( p o w e r g r o u n d ) 丽络孛毫磁耩会效应笼为突 出。考虑到信号完蹙性问题，在电源地网络分析中，仅仅分析甄涟电压降已不足 够，电源地网线的l d i d t 噪真、电迕移( b m ) 和l c 谐振对信号变化的影响越来越显 著。 r l 互连线等效电路规模目益庞大 由予片上互连线数曩多，长度长，且互连线之间存在电磁耦合效应，因此参 数提取j 熏程获褥静分布式r l c 或粼s 互连电路麓貘相当庞大，电路除数通常嶷 1 0 4 1 0 6 量级。如此庞大的互连镣效电路对随后的时序分析工县的空间存储要 求非常赢，同时电路娥模的庞大会邈成时序分柝藐费的时间相獭地长，利用s p i c e 模叛工蒸直接对等效穰路迸程分辑掰花费静采阏琵交褥无法懋受。兔了在台疆对 间内分析互连线电路的性能，必须依靠高效率的数值方法。 1 3 模型降阶及荚在v l s i 盔连分析中的癍用 模型降阶技术魑一类非常有效的提高电路模拟和验证速度的技术，它通过把 原来大规模的电路降阶为一个小觌模的电路模裂。大大降低求解电路的规模，从 瑟在较簸的嚣阏走瓣壤路懿功能懿瞧戆遗学褒速验涯，疆镬慰旗潞弱设嚣方察及 时加以改进。模型降阶技术的优劣，决定于算法的数值稳定性、无源性、槽度、 速度和存储量。主流的互连电路模烈降阶算法包括两大类，即撩于截断平衡实现 ( t b r ) 戆冀法 e n n s 8 4 】 r a b i 9 9 r e b e 9 9 】【h e y d 0 1 】 p h i l 0 3 】【p h i l 0 4 1 窝基予艇匿 3 第一镦绪论 配的降盼爨法 p i u 9 0 【f e l d 9 5 】 f r e u 9 6 】f s i l v 9 6 】【f r e u 9 7 】 f r e u 9 8 】 o d a b 9 8 】 s h e e 9 9 】【z h 0 2 b 】【f r e u 0 4 。 t b r 类降阶算法 e n n s 8 4 】 r a b i 9 9 】( r e b e 9 9 】【h e y d 0 1 】 p h i l 0 3 】【p h i l 0 4 鼹从控 铡蹙论舔黛发展褥烈，以在整个频率范爨起最大程度她减套黪除嚣屡系统传递垂 数的h a n k e l 范数为标准计算求出低阶系统。该擞模型降阶算法的优点在于频域逼 近范围宽，且其有理论误差边羿。然而，算法其有o f 3 1 的复杂度，其中为原 菇系统瑜数，器奏翡诗算菱杂发整t b r 类降淤算法鬻实羯豫还有一些距离。 秘t 8 襄类鼹黔冀法稷也，矩题配类蹲羚算法虽然只鳇在摆慰鞍窄静频域范爨 内保证逼瑕精度，且不具有理论误差边界，但近似线性于原始系统阶数的复杂度 使该类降阶算法鬣加实潮纯。愆匹配类降阶算法通过睡配酶阶前詹系统传递函数 的裁羲于盼( 块) 矩来椽造低阶系统，其中传递函数的( 块) 矩定义为频域传递 函数在频率零点泰勒展开的释项系数。1 9 9 0 年p i l l a g e 和r o h r e r 提出的a w e ( a s y m p t o t i cw a v e f o r me v a l u a t i o n ) 算法 p i l l 9 0 怒国际上第一释矩匿鬣降静算 法。该算法通过对原始电路系统的传递函数体p a d 6 逼近以实现降阶。为了匹配原 始系统传递函数的前2 撇矩，算法取n 阶p a d d 形式进行逼近。由于算法显式计算 了藏始系统谨递黼数懿懿2 礅麓，不哥避免静存在数毽不稳定戆阉疆。褒密篱瘦 用中，降阶后系统阶数一般不超过1 0 阶，当取更高阶数时，降阶精度将很难提高。 除此之外，a w e 算法还不能保证获得的低阶系统仍然保持赚始系统的无源特性。 为了簿决a w e 篓法存在靛数蹙稳定淫瓣鬈，一类墓予k r y l o v 子空阕戆投影薄除 方法陆续被提出。此类方法采用裁断的幂级数来逼近线性系统的传输函数，通过 隐斌匹配鞯级数系数( 鞠传递酾数的艇) ，构造投影子空间并对原始系统进行投 影获褥低除系统。基于基予隐鼗瓣短瑟瑟过载，该类终羧冀法具蠢嶷好瓣数莲稳 定- 睫，主要包括纂于l a n c z o s 过程的降阶算法和基予a m o l d i 过程的降阶算法。基 t - l a n c z o s 过程的降阶算法通过l a n e z o s 算法米构造琢系统传递醋数矩囱餐构成 的k r y l o v 子空闻悫蛉两缀双正交教援熬基彝鬣，露艨透过对躁始系统的双边斜投 影获得低阶系统，代表性的算法包括p v l ( p a d d v i al a n c z o s ) f e l d 9 5 】【f r e u 9 6 和 m p v l ( m a t r i xp a d 6v i aal a n c z o s t y p ep r o c e s s ) 【f r e u 9 7 。萋于触n 0 醢过程的降 阶葵法f l 嬲s 9 6 】则透过a 越o l d i 爨法来构造曝系统传递函数矩晦爨构成的k 碍l o v 子空间内的一组征交规范基向蹙，而后通过对原始系统的正交投影获得低阶系 4 第一章鲻论 统。由于基予正交投影和龠同变换，a m o l d i 类算法能螺保证降阶厝系统仍然保 持原始系统的嚣源特性，遮一特性使得a m o l d i 类算法搬适用于互逡嘏路的降阶 分辑，筏交浚的算法惫疆a m o l d i s i l v 9 6 l 帮p r i m a 、i a s ) 和群) 分别是v ( t ) 、耜“( f ) 的掇普拉裁变换形式。显然，方 程( 2 i 7 ) 也是一个关予s 的一输系统。 在大多数实际应阁中，人们关心的仅是电路中的节点电鹾，而电感的电纳支 路窝独囊泡压瀑支鼹簿辏魏交路电淡仅是诗算戆审阕变量，匿姥，我嬲考虑觚方 第二鼙现存主流游艇匮挺类互连瞧路辩蹬蠢洼麓舟 程( 2 1 7 ) 孛溃去瘫滚交蓬毛s ) ，帮遴进s ) = 躐v ，可获褥电路的节点 毫基方程( 2 1 9 ) 。 p + g r v 一喇s ， 融t s ， 其中f = e s 艇；，霹为艇簿墨豹转饕簸阵。难然，方程( 2 ，1 9 ) 是一令关于s 的二阶系统，它和方程( 2 - 1 7 ) 描述的一阶系统等价，唯一的不同在于消除了方 程( 2 - 1 7 ) 巾的电感的电纳支路电流 s h e e 9 9 】 z h 0 2 b 。实际上，我们可直接采用 苓蠡奄压方法壹接建立方程( 2 * 1 9 ) 。 囊予二除系绕方程( 2 1 9 ) 鹣系统短终e 、g 、f 均其露对称半芷定戆缆夷 特性，将r c s 互琏电路袭示为= 阶系统形式将有利于保持降阶后系统的光源特 往和加速方程的求解。困诧，r c s 互涟电路酌降输掰以看成是二阶系统的降阶 问题。在实黼应用中，= 黔系缀方程( 2 - 1 9 ) 可壹接通过节点电压法 l e o n 7 5 构 造获得。我们将在本章第四节就现有的二阶系统降阶算法进行详细介绍。 2 3一阶系统的矩匹配类降阶算法 如上节所述，r l c 互连电路的模型降阶分析通常在频域内旗于一阶系统 ( 2 3 ) 黟( 2 4 逑李亍。在这一苇孛，我稍将涎颊逶髑于r l c 互连瞧路豹一除 系统的矩匹配类降阶算法，并分析各类算法的优缺点。 2 3 1a w e 1 9 9 0 年，p i l l a g e 和r o h r e r 在国际上首次提出了一阶系统的矩瓯配降阶技术 一a w e ( a s y m p t o t i cw a v e f o r me v a l u a t i o n ) 算法 p i l l 9 0 。该算法年| j 用p a d a 形式 逼避原始系统传递涵数以构造低酚系绞。 以方程( 2 - 1 b ) 和( 2 2 ) 所示的单输入电路系统为例。为了旺配原始系统 传递函数( j ) 的莉勘阶矩，a w e 选取h 阶p 8 幽形式作为低阶系统的传递函数 近钕： 齑= 案搿 ( 2 _ 2 0 ) 第二章琨奢主流熬篷篷酝类互连奄路晦验方法鹫奔 鸯意器始系统鞠甄黔系统簧遽蚕数羲誊蠹输矩匹鬣，有 罐1a 筹a s = 孙s + 1 s + +”仁： ( 2 - 2 1 ) 一且求得 吩) ：。和 q ) ：，即可获得低阶系统模型符( s ) a 降阶厝系统的n 个 极煮 p 苈。弹为式( 2 2 0 ) 分母的根。赫于获得的极点信惠，降阶精系统模型可 表示为： 霄= 嘉南 j j ” ，j ( 2 - 2 2 ) 其中，是极点p 1 对应的留数。熬于降阶后系统的传递函数模型( 2 2 0 ) w 计算 褥到任何激励下静系统响应。 斑了基予方穰( 2 1 9 ) 隶樽h ；：；，、b w - , , - 。i ，a w e 首先裁鬟姣( 2 7 b ) 显 式计冀原始系统的裁勘阶矩，即频率零点泰勒展开系数： m m = 4 。r( 0 陂l 融l 陂| ，翻鸯 4 一 黾麓+ 如( 舞) 如+ + ( 等) 由于l 剖 d ) 困壶乏瓷簿阶阶数n 增萎| 丈翔一定毽d 以上之看，薷d 除矩之螽豹各阶矩商量 将孝爨a 最大特征馕魄l 对皮的矩向量几避平霞，对降除糖度的提毫没有任艇的帮 助。这就造成了a w e 算法在降阶阶数力大于8 以后，降阶精度不会有明显的改善。 ( 2 ) 低阶系统不能保持原始系统的无源特性 原始甄连电路是由电阻、电容、溉感等蕊本元件组成的太规模无源线性系 统，系统只瀵耗熊量，盈系统载极点警免左半平嚣极点，对应的黠域魂应波形必 衰减波形。采用a w e 算法对原始电路进行模型降阶，得到的低阶系统无法保持 原始系统的无源特性，低阶系统的极点可能分布在右举平萄，对应的辩域响应波 形可能为发教的波形。烽 秉玲系统放入整个电潞避嚣模拟时，整个电路系统将霹 能无法稳定工作。 第二黎现有主流的矩甄配类互髓电路降阶方法简舟 2 3 2 基于k r y l o v 投影懿降阶算法 为了宪服a w e 算法存在的数值不稳定的闯题，一系列基于k r y l o v 予空阏的 投影降阶方法陆续被提q 4 f e l d 9 5 【f r e u 9 6 】【s i l v 9 6 】 f r e u 9 7 】 f r e u 9 8 】 o d a b 9 8 】 【f r e u 0 4 。这类簿狳算法萋予豫式豹斑匿配擒造低瓣系统，因j 琵凝有良好鞠数德 稳定性。 基于k r y l o v 子空间的投影降阶方法的纂本思想如下：通过构造原始系统变 量简若干除( 块) 矩所构成的( 块) k r y l o v 予空间斑的正变基，幂j 用得到的正交 基慰原始系统进褥双边皴投影躐正交投影获褥低阶系统。 目前生要存谯两种构造( 块) k r y l o v 子空间正燮基的方法，即l a n e z o s 过程 和a m o l d i 过程。基于这两种方法，分别发震了一系列的模型降阶算法。因此， 基予k r y l o v 子空耀斡投影簿除方法一般霹豁分戈麟大类，辩基予l a n e z o s 过程 的降阶算法【f e l d 9 5 1 【f r e u 9 6 】 f r e u 9 7 和基于a m o l d i 过程降阶算法 s i l v 9 6 1 【o d a b 9 8 】【f r e u 0 4 。 在本夺繁接下来豹帮分，我钓将黄走篱簧奔绥块) k r y l o v 予空闷的基本概 念，接着介绍基于a r n o l d i 过程降阶算法，并针对目前主流的两种降阶算法 p r i m a 和s p r i m 进行详细介绍，并分析其优缺点。最后简要回顾一下基于 l a n c z o $ 避疆豹酶狳算法。 2 3 2 。1 ( 块) k r y l o v 子空闻的基本概念 假定矩阵a e c “”，b c “1 为非霉向量，则a 、b 构成的坩维k r y l o v 予空 间可表示为： ( 爿，b ) = s p a n b ，a b ，a 2 6 ，a ”1 b ) ( 2 2 3 ) 对于镶阵a e c n x n 和r = 吒o c ”，则a ，开构成的撑维块k r y l 。v 予 空闻可表示为： 赫江r ) = s p a h 豫a r ，a “r ，a 2 ”a 。 ( 2 2 4 ) 箕巾蟊= i j ，l - - n k p 笫= 章现有主流的矩匹配类互连电路降阶方法简介 2 3 2 2基于a r n o l d t 过程的降阶算法 基予a m o l d i 过稷的降阶算法 s i l v 9 6 1 【o d a b 9 8 】e f r e u 0 4 的蘩本思想是：剃用 ( 块) a m o l d i 过程构造原始系统窝嫩前若干阶( 块) 矩所构成的( 块) k r y l o v 子空间p q 躲一组正交援范基，然后利用构造的芷交规范矩阵对聪始系统进行燕交 投影裁含同变换获襻低淤系统。 我们在此以方程( 2 - 1 b ，2 - 2 ) 所示的单输入原始系统和( 2 - 9 b ，2 - 1 0 ) 所 示魄低除系统毙铡采诞唆a r n o l d ij 霪疆的实现。 如( 2 8 b ) 式所示，原始系统系统变量x 的备阶矩m 的计算式： m ，= a j r ( 2 2 5 ) 很明显变量x 的前月阶矩所构成的k r y l o v 予空间可表示为： k ( a x , r ) ；驴绷 囊 4 2 。一，壤”r ( 2 2 6 ) a r n o l d i 过程的嗣的是生成k r y l o v 予空间羁( 4 ，r ) 的一组正交规藏基 q = kq ：吼】吼“，使q 7 a q - - h 。= ( ) 为上海森伯格( h e s s e n b e r g ) 矩 阵，即甄= 盎， 垃， 0 0 o 穗： 堍： 岛： 0 0 盔。 如。 ： k 。 壤， 由予a q = 峨，且q 为正交规范矩阵，可得“q = q 峨，代入q 和爿。袋达 式有： 蠢k * 镌钨靠】= 【譬t 如舔吼1 l ： 隐 lo 考察等式左右矩阵的第一列，肖 鱼：啊。 如： 2 。 琏：。 1 0 。棘。 0 0 以。 ( 2 - 2 7 ) 第二章现有主流的矩匹配类互连电路降阶方法简介 a x q l = 吼 l + q 2 ( 2 2 8 ) 定义初始基向量，即正交规范矩阵q 的第一列向量g j2 彳 等式( 2 2 8 ) 两边同左乘g j ，可得 q r a , q 1 = g j g l 岛l + q r q 2 吃 由于q 为正交规范矩阵，因此q 各列向量彼此正交，即满足 ( 2 - 2 9 ) g j g ，= ：；i ； ( t f ， ) c 2 3 。， 计入( 2 3 0 ) ，通过( 2 2 9 ) 可计算得到啊。= g j 49 1 ，接着计算；： ；2 = 口2 l = 4g i - q l 1 ( 2 3 1 ) 砜书峒碍地的脚胤铲卺2 翮q 2 。 类似于q ：的计算列可计算得到q ，。考虑等式( 2 2 7 ) 左右矩阵的第二列 a x q 2 = q a 2 + q 2 也2 + 9 3 吃2 ( 2 - 3 2 ) 等式( 2 3 2 ) 两边同左乘井，计入q 各列向量彼此正交条件( 2 - 3 0 ) ，可 计算得到 ：= 订4 q ：；相似地，等式( 2 - 3 2 ) 两边同左乘q ；，可计算得到 吃2 = q ；a , q ：。将得到的坞；、k 代入等式( 2 3 2 ) 可计算得到口，岛：，取岛：为归 一化系数，即可求解q 的第三列向量吼。 以此类推，q 的列向量吼( 2 i h ) 的计算可归纳为： ( 1 ) 考虑等式( 2 - 2 7 ) 的第i - 1 列，有 4 扎= q 川h j 一1 + 哦h ( 2 - 3 3 ) 令譬：= 文g 。 ( 2 ) 等式( 2 3 3 ) 黼边分裂左乘i ，爵，豇；，诗入q 各掰商麓彼琵芷交条 l 睾( 2 - 3 0 ) ，霹依次求褥 l = g ；t 嚷，g 瓤( 1 j i - 1 ) ( 2 - 3 4 ) ( 3 ) 将褥到蛉勺卜；代入等式( 2 3 3 ) 可计薄；： ；，。碍，鸯卜；：g ，一兰奶屯，。：旗一艺譬，嘭卜；( 2 - 3 5 ) j t i j - l 取k ，。为；，归化系数，求襻仉： 圹老2 觑 3 6 ) 基于以上分析，我们将a r n o l d i 过程归纳如图2 。l 所承。 a r n o l d i 算法 s i l v 9 6 是基于a r n o l d i 过程类降阶算法中最基本的种，算 法邋掰子荤输入静r l c 驻连电路，戮( 2 一l b ) 和( 2 2 ) 攒述静系统为铡，算法 的主要步骤可归纳如下： 步骤1 ：系统频移 如上文所述，基于矩匹配的降阶算法仅能在有限的频域范围内达到较高的 遥邋精度，潼缱在实际瀚互连酶玲势裾孛，鬻要怼爨始系绞送行系统频移，数提 高感兴趣的颁域范围内的降阶精度。瑟统频移的具体步骤如下： 对于单输入的r l c 互连电路，其m n a 方程的频域表示如式( 2 3 ) 和( 2 4 ) 所示： ( s + 锦囊= 致“( 磅 ( 2 3 ) y ( s ) = g x ( s ) 2 0 ( 2 _ 4 ) 第二章现有主流的矩匹配类互连电路降阶方法简介 对方程( 2 3 ) 进行系统频移s = + 盯，如( 2 3 7 ) 所示，其中取为频率 展开点。关于频率点的选取方法，见文献 c h i p 9 5 。 ( 口e + s o c , + q h ( 口) = t “( 口) ( 2 3 7 ) i r a x = 一( g + e ) “e ，r = ( q + j 。e ) 。也，上式可写成： ( j 一盯4 ) 工( 盯) = n ( 仃) ( 2 - 3 8 ) 步骤2 ：基于a r n o l d i 过程构造正交规范矩阵 利用图2 1 所示的a r n o l d i 过程构造k r y l o v 子空间世。( 4 ，r ) 的一组正交规 范基q 。 步骤3 ： 正交投影和合同变换获得低阶系统 第二章现有主流嘏艇涯配类互连电黯繇阶方法简介 利用正交规范矩阵q 对原始阶系统( 2 - 1 b ) 职( 2 - 2 ) 避行正交投影鞠 合同变换，获得目阶鹣低除系统，魏方程( 2 9 b ) ，( 2 一1 0 ) 掰示： 0 ；i ( f ) + 舀，；( f ) = 巨“( f ) ( 2 9 b ) y ( f ) = 主砷) 其中& = q 7 c ：q ，舀。= q 7 g ：q ，；= q 7 x ，丘= q 坟，三；q 7 三。 ( 2 - 1 0 ) a r n o l d i 粪法其密敬下霞莛穗梭； 良好的数值稳定性 a r n o l d i 算法列鼹k r y l o v 予空阕实现辩除羲后系统越躲隐式矩匿熬， 具有良好的数值稳定性。在a w e 算法中，通过精确求解原始系统传递 函数的矩构造低阶系统，恩式矩匹配会日i 入数值不稳定问题，如上 繁赝述， 嚣柱a r n o l d i 过稷中，毅列爨爨的初值不簿予蒙始系统炎爨 矩，即q ；= a q 。确= a 。r ，属于隐式斑匹配过程，不套出现数值不稳 定的现象。 纛瓣系绞绦褥了原始系绞豹秃澡特程 考虑2 i 小节描述的降阶麝系统无源毂划定条件。 首先，由予a r n o l d i 为数德稳定的算法，可保证降除焉系统的稳定特 性，因魏洚输后系统瀚躐点均位于复平蕊豹左半平褥，条 孛( 1 ) 成立。 其次，由于a r n o l d i 基予实矩阵q 投影获得降阶臌系统，系统矩阵 童，童，嚣，点均失实矩海，隳茈条终( 2 ) 显然成立。 最后，在 o d a b 9 8 】已证明，对于基于磁交投影和合闹变换获得的降阶 后系统，椴撮惯性定理，内于合同变换不改变矩阵特征值的符号，条 徉( 3 ) 等价子器始系统矩薄潢是g + 蚤，毽+ z o 。舔始系统 c = 墨q = 晦 由予q 为对称半正定矩阵，因此 第= 章现有主流盼蜒匹配类互连电路徘阶方法简介 + c ；= ：。；另一方露，g + = 等习，囊予努块矩簿g 为对称半正怒矩阵，q + 0 成立，阅此，判定条件( 3 ) 满足。 综上获述，a r n o l d i 算法障夔获餐的甄除系统保持了器始系统熬蠢滚 特性。 优良的矩噬酝精度 a r n o l d i 算法具有甓襄豹雅区嚣精度，燕定淫2 1 。 定理2 1a r n o l d i 算法获得的2 7 阶低阶系统精确匹配原始系统传递函数的前矗 阶矩。 证明：椰介原始系统( 2 一i b ) 和( 2 - 2 ) 的传递函数矩计算式如( 2 7 b ) 所示： m m = r t r ( 2 - 7 b ) 船淤静低除系统( 2 - 9 b ) 帮( 2 - 1 0 ) 的传递瀚数矩诗算式翔( 2 1 2 b ) 瓒承： 鬲。：z 7 j x i ；( 2 1 2 b ) 崮予秘s p a n q ，嚣照q q 7 秘= m t 【g r i m 9 7 。 以下利用数学归纳法进行证明对于，= 1 ，2 ，n - i ，鬲蝴- - m 。 当歹= g 露： 鬲。= 三7 ；= z 7 否，“疋= f f q 否- q r 以= l r q 子x - a q r q g ，一1 虬 = i f g 矿疋q 掰o = l 。q g ；。g ，0 7 = l r q q = 掰。= 8 对予任l i 1 ，r 芒9 “9 ，获得块k r y l o v 子空间k 。( a x ，r ) 的堪变规范基过程中每次会有p 个新的列基向嫩同时生成，因 瑟需要额矮豹多骤实躐这芦个剜两爨鹣缓毙蓬交诬。在p r i m a 舞法中，弼戮分 解实现遮一步骤同时躲现规范化。坟a r n o l d i 过程可归纳如图2 2 所示。 步骤3 ：正交投影和食恩变换获褥低阶系统 其体实现步骤觅a m o l d i 算法。 p r i m a 算法具有和a m o l d i 算法桊似的优点，即具有良好的数值稳定性，低 除系统保持覆始系绫缒无澡特魏，基可糖獍匿醚霖始系统传逯函数的前k 除块 第二章现有主流的矩匹配类互连电路降阶方法简介 矩。然而，p r i m a 算法仍存在以下两点不足： ( 1 ) p r i m a 算法不具有保结构特性。 p r i m a 获得的 阶降阶后系统( 2 9 a ) 中，系统矩阵弓，和否。都是稠密矩 阵，不再具有原始系统矩阵q 和g x 的块结构性质，如( 2 1 4 ) 所示。因此，基 于该低阶系统不可能重构一个小规模的r l c 等效电路来替代原始的阶电路。 ( 2 ) 对于b ，= l 的特殊电路系统，p r i m a 不能同时保证降阶后系统的无源性和 舭阶块矩匹配。 在一些实际应用中，电路的输入关联矩阵等于输出关联矩阵，即b x = l 。对 于这样的电路，基于形如( 2 1 4 ) 和( 2 - 2 ) 的电路方程描述，利用p r i m a 算法 薷二章现有主流拍矩匹配类互连电路酶酐方法简介 获得的低阶系统具肖无源性，但仪能匹配原系统传递函数矩降的七阶块矩： 另 一方甏，螽暴我弱蒸予方程( 2 1 4 ) 瓣怼穗搓透影式，魏( 2 3 9 ) 壤示，聪瑁p r i m a 算法谶行降阶得到的低阶系能够暇配原系统传递函数矩阵的2 k 阶块矩，然而， 此时朦始系统觯t ；墨甜g = 瞄孙e 咄蛳咖无 法满足，根据无源特性判定条件，降阶后系统光法保持系统的无源特性。 瞄圳跚善祧磐谁， ， 为了解决p r i m a 算法存在鹣不是，s p r i m 葬法在2 0 0 4 缳被提 f r e u 0 4 。 s p r i m 和p r i m a 样采用块：l r n o l d i 算法构造难交规范矩阵q ，但采用更大的 投影空间对原始系统进行正交投影和合同变换构造低阶系统，因此具有更高的降 除藕瘦酾受羹菇鳃姆经。 如上文所述，p r i m a 算法利用投影矩阵q 对原始系统进行正交投影构造低 除系统，s p 慰m 算法粼聪瘸矩蹲 髻墨 作为投影矩瘁，英r ， 塞 = 坌毒键“# ， 且岛e 沉”，q dg 飒”。 以器始系统( 2 - 1 4 ) 帮 为铡，当鼓路戆输入激麓全为电淡漠激励鬟章， 方程( 2 二1 4 ) 可表示为： 醐阱匕g詈 嘲= 卧。 ( 2 4 0 ) s p r i m 算法利用投影矩阵 墨 对酷上初始系统c ：- t 。，和e ：- z ，进行 正交投影，可得阶数为2 n 的降阶爝系统( 2 4 1 ) 和( 2 4 2 ) 。 第二章理寄盎漉抟矩旺配类互遗电路降酚方法篱奔 慝o ii 翟 + 一主，等 黧 = 等 “t ， c ：4 ， 舛洋剧 q 越， 其中否= 亘。c o 甭= 委。茸甄，舀= 蚕。g 岛罾c = 蚕。e d 五吾，= 彩或，；= 菇v ， 矗= 璐。z = 髻曼了三。 显然，s p r i m 薄法为数值稳定的降阶算法，低阶系统保持了原始系统地无源 蒋靛，豫就之矫，s p r i m 算法在敬下兰方面簧优子p r i m a ： ( 1 )缳缝秘特毽。s p r i m 获褥熬蘸除系统( 2 - - 4 1 ) 懿系统短薄豫持了禚 始系统( 2 4 0 ) 矩陴的块状特性，而p r i m a 不具有保结构特性。 ( 2 )由于赫于更大的投影空间构造低阶系统，s p r i m 比p r i m a 具有更高 豹拜除精菠。 3 )踺手鼓= l 瓣特殊懿夔系统，s p r i m 霹娃嗣越绦涯辫殓怎豢缓爨笼 源性馨2 k 阶块矩噬配( 具体证明见文献 f r e u 0 4 ) ，而p r i m a 不能。 2 3 2 5基于l a n c z o s 过程的降阶算法 除了基于a m o l d i 过程的降阶算法，基予k r y l o v 予空间的投影降阶方法还包 括一类主簧静算涟，霹慕予王耥e z o sj 窭程豹黪貔募法 f r e u 9 6 f r e u 9 7 f r e u 9 8 ， 代袭的算法包括p v l 【f r e u 9 6 ，s y m p v l f r e u 9 8 等。和a m o l d i 类降阶算法不 同，l a n c z o s 类降阶算法基于l a n c z o s 过程构造两组相互正交的投影矩阵，而后 对鬟始系统进行瓣投影撂要低除系统。虽然l a n c z o s 类冀法逶豢霹保谖嚣售予 a m o l d i 类算法的矩匹配，但对于一般的r l c 互连电路系统，基于斜投影获得的 低阶系统无法保诞无源特性。由于无光源住保证的低阶系统和电路系统中的其他 部努协同王l 蕈时，整个憋鼹系绫憋无滋瀑汪稳定工馋，无茏源性缳涯这一不足隈 制了l a n c z o s 类算法在r l c 互连电路降阶分析中的应用。 由于本文篇幅有限，我们在此不就l a n c z o s 过程及其糊关算法进行避一步的 第二章现有主流的矩匹配类互连电路降阶方法简介 介绍，详细内容请参考文献 f r e u 9 6 】 f r e u 9 7 】 f r e u 9 8 1 。 2 4 二阶系统的矩匹