（电路与系统专业论文）深亚微米工艺下串扰优化的布线算法分析与实现[电路与系统专业优秀论文].pdf

浙江大学硕i 学位论文 摘要 随着超大规模集成电路向深亚微米工艺的发展，高速度、高集成度、低功耗 成为当今集成电路的主要特点。设计如此高性能的芯片使我们面临新的挑战，总 结起来有两点：速度越来越快，尺寸越来越小；系统越来越复杂，同时要求系统 更加稳定。这使得在低速系统设计中的二级效应上升为主要矛盾，其中的信号完 整性问题成为最突出的因素之一。 随着集成电路工艺尺寸的减小，互连线之间靠的更近。此外线宽的减小，也 使得线间距相对于厚度越来越小，如同一堵又高又窄的墙，线间的耦合电容甚至 超过了它们的对地电容。耦合电容对电路的影响主要表现在两个方面：耦合电容 引起串扰噪声( c r o s s t a l kn o i s e ) ，严重的时候会造成邻近线网上传播的信号出 现逻辑错误；耦合电容引起串扰时延( c r o s s t a l kd e l a y ) ，增大了信号传播的时 间延迟，造成s e t u pt i m ev i o l a t i o n 或者h o l dt i m ev i o l a t i o n 。正是上述原 因，人们在不断的研究减小串扰的稚线算法。 文中，我们首先分析了计算串扰延迟和串扰噪声的数学模型。随后在分析比 较减小串扰的非曼哈顿结构布线算法及曼哈顿结构布线算法的摹础上，提出一种 无网格减小串扰的布线算法，该算法基于把水平网段分为各子段，以取得更好的 摄动效果。我们详细分析了算法的数学模型、实现过程及算法的时l h j 复杂度和空 间复杂度，认为它是可行的。我们可以看到实现的算法同时考虑了垂直网段和水 平网段对串扰的影响，在取得较好的优化结果的同时，其执行速度相比较文献中 的算法快很多。最后我们从两个不同方面对实现的算法作了测试。第一种方法是 参考相关文献中的测试方法，输入布线图，不但可以比较优化前后线网串扰值的 不同，也可以比较布线结构的变动；第二种方法结合自己的专业方向，用后端工 具来验证算法对串扰的改进。这主要是通过算法的优化结果在布局布线工具上改 动布线结构，然后用时序分析工具分析比较优化前后串扰时延s l a c k 值的改进和 串扰噪声s l a c k 值的改进。 关键字：深亚微米工艺，串扰时延，串扰噪声，曼哈顿结构，非曼哈顿结构 浙江丈学硕 。学位论文 a b s t r a c t w i t ht h ed e v e o p m e n to fv e r yl a r g es c a l ei n t e g r a t e dc i r c u i t ( v l s l ) e n t e r i n gi n t ot h es t a g eo fd e e ps u b m i c r o nt e c h n o l o g y ，h i g h e rs p e e da n d l o w e rp o w e rh a v eb e e nt h em a i n - f e a t u r eo ft h ec u r r e n ti n t e g r a t e dc i r c u i t w ea r ec o n f r o n t e dw i t hn e wc h a l l e n g ei no r d e rt od e s i g ns u c hh i g h p o w e r e d c h i p s t h a ti s ，c h i p sr u nw i t hh i g h e rs p e e dw h i l et h e i rs i z er e d u c ea n d t h es y s t e mi sm o r ec o m p l i c a t e db u tc a ns t i l lw o r ks t a b l y i nt h i sc a s e ， s o m es e c o n d a r yn e g a t i v ee f f e c ti nt h el o w e rs p e e ds y s t e md e s i g nb e c o m e s n o t a b l ys u c ha ss i g n a li n t e g r i t y t h es p a c eb e t w e e nw i r e sh a sb e e nr e d u c e da n dt h es a m ea st h er e l a t i v e s p a c eb e c a u s eo ft h ei n c r e a s e dw i r et h i c k n e s s t h ec o u p l e dc a p a c i l a n c e o ft w oa d j a c e n tw i r e se v e ne x c e e d st h eg r o u n dc a p a c i t a n c e o n eo ft h e e f f e c to fc o u p e dc a p a c i t a n c ei sc r o s s t a l k n o i s e i tm a ya r o s el o g i e e r r o r s a n o t h e re f f e c ti sc r o s s t a l kd e l a y ，i tm a ya c c e l e r a t eo rs l o w e r t h es i g n a ip r o p a g a t i o ns oa st oc a u s es e t u pt i m ev i o l a t i o no rh o l dt i m e v i o l a t i o n s oal o to fp e o p l ea r er e s e a r c h i n gv a r i o u sa l g o r i t h mt os o l v e t h ea b o v ep r o b le m i nt h isp a p e r ，w ea n a l y z em o d e l so fc r o s s t a l kd e l a yc a l c u l a t i o na n d c r o s s t a l kn o i s ec a l c u l a t i o nf i r s t l y t h e n ，w ea n a l y z et y p i c a lo p t i m a l a l g o r i t h mb a s e do nb o t hn o n m a n h a t t a na n dm a n h a t t a nc h a n n e lr o u t i n g a c c o r d i n gt ot h ea b o v ea f l a l y s i s ，w eg iv ean o n g r i do p t i m a la l g o r i t h m t or e d u c et h ec r o s s t a l ke f f e c tw h i c hi sb a s e do ns p l i t t i n gh o r i z o n t a l1 i n e i n t os u b l i n e s w ea n a l y z et h em o d e lo ft h i sa l g o r i t h m 、t h ep r o c e s so f h o wt or e a li z ei t 、t h et j m ec o m p l e x i t ya n ds p a c ec o m p l e x i t y 1 i ec a ng e t g o o dr e s u l t i na d d i t i o nt om o r eq u i c k l y r u n n i n gt i m e t h a na n o t h e r a l g o r it h m tl a s t ，w el e s tt h ea l g o r jt h mw it ht w od if f e r e n tm e t h o d s o n e i st r a d i t i o n a lm e t h o di nt h er e f e r e n c ep a p e rd e s c r i b e da sf o l l o w s ：i n p u t t h es a m p el a y o u ta n dc o m p a r et h ei n i t i a lc r o s s t a l kw i t hc r o s s t a l ka f t e r o p t i m i z a t i o n a n o t h e rm e t h o di sa sf o l l o w s ：w ea n a l y z ec r o s s t a l kd e l a y s l a c ka n dc r o s s t a kn o is es 】a c kr e p o r t e db yb a c k e n dt i m i n ga n a l y s ist o o l t os e et h ej m p r o v e m e n ta f t e ra p p y i n gt h ea l g o r i t h m k e yw o r d s ：d e e ps u b m i c r o nt e c h n o l o g y ，c r o s s t a lkd e l a y ，c r o s s t a l kn o i s e m a n h a t t a ns t r u c t u r e ，n o n m a n h a t t a ns t r u c t u r e n 沥江人学硕f 1 学位论文 图形目录 图1 1 高v t 器件产生较大噪声3 图i 2 低v t 器件传播噪声最大3 图2 1 串扰噪声产生机理及现象8 图2 2 耦合噪声电路模型：8 图2 3 计算串扰峰值的典型互连结构9 图2 4 计算串扰峰值的典型互连结构电路图1 0 图2 5 随机噪声波形图1 2 图2 6 计算噪声峰值波形图，1 3 图2 7 典型的r c 结构电路图1 4 图2 8 双线性模型1 7 图2 9 指数模型，1 7 图2 1 0 串扰时延产生机理及现象1 9 图2 1 l 信号跳变时间对耦合电容的影响2 0 图2 1 2 邻近线信号不同到达时问对时延的影响2 1 图2 1 3 未考虑串扰的时序分析2 3 图2 1 4 考虑串扰的时序分析2 4 图3 1 布线区域分为开关盒与通道2 5 图3 2 通道和线网的表示，2 6 图3 3 互连线的r c 物理模型2 9 图3 4 非曼哈顿布线中4 5 度布线段3 0 图3 5 非曼哈顿布线中i 角形优化法3 1 图3 6 曼哈顿布线串扰计算3 3 图3 7 互连线电容发展趋势3 4 图3 8 垂直网段串扰的计算3 8 图3 9 迭代参数线性规划法的负作用4 0 图3 1 0 网段a 串扰的计算4 1 图3 1 l 摄动区间的划分4 2 图3 1 2s 】a c k 在摄动区问内的变化4 3 图3 1 3 水平网段分为子嘲段4 4 图3 1 4 算法的输入4 6 图4 1 测试例子一优化的布线图形4 8 图4 2 测试例子一优化后前，线图形4 9 图4 3 测试例子二优化莳布线图形5 1 图4 4 测试例子二优化后白线图形5 1 图4 5s t a r r c x t 流稗阿5 5 图4 6p r i m e t i i n e 流桦图5 6 图4 7 后端验证流程图5 6 图4 8 关键线网优化前靠线图形6 0 图4 9 关键线嘲优化后向线图形6 0 l i i 浙江大学硕0 学位论文 表格目录 龃印鼹 一一一较较一响比比一一影值值一值的扰扰一容延串串电时的的一合对网网势耦问线线趋的时各各展应达后后发对到前静术阿同化化技时不优优艺变号中中 工跳信一二 路号网子子电信线例例成同近试试集不邻测测 l l 2 l 2l 色互屯乱 表表表表表 浙江大学硕i ：学位论文 1 1 集成电路发展历程 第一章绪论 自从本世纪初，真空电子管发明后，到现在电子器件已经经历了五代的发展。 集成电路的诞生，使电子技术出现了划时代的革命，它是现代电子与计算机发展 的基础，也是微电子技术发展的标志之一。 集成电路规模的划分，目前在国际上还没有严格的定义。一般人们将单块芯 片上包含1 0 0 个元件或者1 0 个逻辑门以下的集成电路称为小规模集成电路。元 件数在1 0 0 个以上、1 0 0 0 个以下或者逻辑门在1 0 个以上、1 0 0 个以下的称为中 规模集成电路。元件数在1 0 0 0 到】0 0 0 0 0 个的称为大规模集成电路。门数超过 5 0 0 0 个，或者元件数高于1 0 万个的则称为超大规模集成电路( v l s i ) 。 1 9 5 8 年，美国德克萨斯仪器公司的一位工程师制造成了世界上第一块集成 电路。同一年，另一家美国著名的仙童电子公司也宣称研制成功了集成电路。1 9 5 9 年，德克萨斯仪器公司宣布建立了世界上第一条集成电路生产线。1 9 6 2 年，世 界上出现了第一块集成电路商品。这预示着第三代电子器件正式登上历史舞台。 不久，世界上掀起了集成电路研制热。早期的典型硅片为1 2 5 平方毫米。 6 0 年代初，国际上集成电路产品每个硅片上元件数在1 0 0 个左右；1 9 6 7 年已经 达到1 0 0 0 个晶体管；进入8 0 年代，一个硅片上几万个晶体管的大规模集成电路 已经很普遍了。如今，已经出现属于第五代产品，在不到5 0 平方毫米的硅片上 集成电路的晶体管数目激增到2 0 0 万个以上。 1 1 表1 1 简要给出美国半导体工艺协会( s i a ) 1 9 9 9 年对国际微电子技术发展趋 势的预测，其中芯片面积和器件密度的预测是针对高性能、低产量m p i j 芯片的。 1 2 1 3 年代 1 9 9 92 0 0 02 0 0 12 0 0 22 0 0 3 2 0 0 42 0 0 5 2 0 0 82 0 1 12 0 1 4 特征尺寸 1 8 01 3 01 0 07 05 03 5 ( r i m ) 最低电压1 51 5 1 21 21 2o 9o 90 6o 5o 3 源( v ) 工作频率 1 2 5 0 1 4 6 81 7 6 72 1 0 02 4 9 0 2 9 5 23 5 0 0 6 0 0 01 0 0 0 01 3 5 0 0 f m h z ) 芯片由i 积 4 5 04 5 05 6 76 2 27 1 38 1 79 3 7 ( c m ) 浙江大学硕】鸣 位论文 1 2i c 设计中信号完整性分析的挑战【1 4 】 过去几年里，由于i c 设计从1 3 0 纳米发展到9 0 纳米再到6 5 纳米，信号完 整性( s i ) 问题变得日益复杂，现今，s 1 分析需要从三个截然不同的方向进行： i r 压降分析、功能噪声分析、以及噪声对时序影响的分析。由于主流分析及实 现工具都已经集成s 1 分析的功能，很容易让人误以为信号完整性问题已经得到 解决。但是事实上，必须对现有的s 1 分析技术作出重大改进。如今对低功耗设 计的侧重，以及工艺技术向4 5 纳米的发展，都催生了更多急待解决的问题。 1 2 ，16 5 纳米带来的s l 问题挑战 在向6 5 纳米变迁过程中，迫切需要低功率设计，但是随之而来的是新的信 号完整性挑战。其原因首先是由于低功耗设计一般都采用多种电压，可能导致不 同电压信号之间的耦合。相比较相同电压信号之间的耦合，从较高电压到较低电 压的耦合要强的多。多电源电压设计还需要使用电平转换器。由于电路的复杂性， 要使电平转换器不受噪声影响变得更加困难。 此外，低功耗设计使用多闽值电压值门电路。高阈值电压值的器件往往具有 更高的保持阻抗，从而更加容易受串扰的影响。另一方面，阈值电压较低的器件 作为干扰传递者情形更糟糕，因为它们的转换速度比较快。而且它在输入端，往 往对波形影响更加敏感。 图i 1 显示的是受干扰线( v i c t i m ) 驱动器门电路v t 为低、中、高时，产生 的噪卢波形。显然作为被干扰者，高v t 器件是最差的单元，产生的串扰噪声最 大。低v t 器件产生的噪声最小，中v t 器件在两者之间。 图1 2 显示，在低、中、高v t 器件的输入端加上相同的输入噪声的时候， 低v t 器件由于驱动能力大，传播的噪声也最大，而高v t 器件传输的噪声最小。 总而言之，低功率设计过程中，需要谨慎处理时序、功率、噪卢之l 日j 的取舍问题。 浙江大学硕上学位论文 4 0 0 3 0 0 2 0 0 1 0 0 12345 图1 1 高v t 器件产生较大噪声 值对应的 驱动器的 响 图1 2 低v t 器件传播噪声最大 所对应的 播 低功率设计的另一个要素，是为了节省电力的消耗，需要对芯片不同部分进 行导通和关断。导通和关断过程会产生瞬时效应，这呵能对电路中仍在工作的其 它部分造成影响。 l 暴 姗 珊 姗 啪 啪 如 浙江人学颀i 。学位论文 动态电压和频率调整是一种旨在降低功耗、延长电池寿命的技术。利用这种 技术，设计人员能在芯片运行的同时动态的为不同模板设置不同的电压值或不同 的频率值。当采用动态电压和频率调整技术的时候，要求设计人员对不同模板的 电压和频率进行各种可能的组合，以对芯片性能迸行验证。这将大大增加电气分 析的复杂性和时间要求。而使用传统分析解决方案的另一项考虑因素，是每一个 电压点都需要不同的库。 除了低功耗方面的考虑，其它的一些信号完整性问题也开始涌现出来。v t 和v d d 问的电压差距随电压调整在不断减小。由于( v d d v t ) 2 对性能的影响较大， 故电压的变化对门电路的延迟和抗干扰能力有很大的影响。 电压变化也以非线性方式影响延迟。此外，温度也对门电路的延迟产生显著 的影响。在高密度集成电路中，芯片上的温度变化可达到5 0 摄氏度。这种变化 对信号的保真度产生负面的影响。 目前设计人员采用芯片变异因素( o c v ) 来计算芯片上v d d 和温度的变化。然 而，在6 5 纳米或者更小节点时，由于变化量的增大，o c v 因数极可能非常大。 在这种情况下，需要一种能处理电压和温度变化特定实例的方案。 尽管一直以来大量注意力都集中在工艺变异及其对纯时序的影响面上面。但 实际上，工艺变异对集成电路上所有信号的保真度都有影响。因此，所有信号的 保真度和完整性必须在这些工艺变异的环境中进行分析。 1 2 2 探索解决方案 如果所有的这些新的挑战都存在，那我们应该如何改进现有的s 1 分析技术， 以应对6 j 纳米或者4 5 纳米芯片的设计? 一种好的开端就是减轻对工艺技术预想 的悲观情绪。尽管对利用现有技术进行功能性噪声分析的评估还不算过分悲观， 但是在计算噪声对时序的影响时却太过悲观。 一般而言，分析工具都确立了种假设，即所有的布线路径都存在最坏的情 况。工具将分析设计中每个网格被其它相邻网格干扰的最严重的情况。但是在 大多数设计中，最坏的情况并不会发生。较高级别的算法可以防止许多干扰源聚 集在一起相互交换的情况发生。 减轻设计人员在解决s i 问题中的悲观情绪的方法之一，就是在任何可能的 地方都考虑逻辑关系。这样一来，那此明显不能聚集在一起交换的信号就不能被 视为同时干扰者。另一种方法是朋随机分析技术柬模拟实际的环境情况而不是非 绝对的最坏情况。虽然这种方法本身存在风险，但是对建立分析仍然不失安全性。 还有一种减轻信号完整性分柝悲观情绪的方法，就是采用更实际的模型来计 算串扰引起的延迟变化。考虑到某。特定噪声肘路径的总体影响而4 i 只是对出现 4 浙江人学硕e 学位论文 串扰的网格的影响。这种方法通过产生最坏情况下路径的延迟变化，可显著降低 悲观情绪。 在分析i r 压降的影响的时候，分析工具考虑的也是最坏的情况。当对噪声 或者时序进行分析的时候，采用动态i r 压降分析，并考虑到i r 压降事件和噪声 时问之间的暂时关系，可有助于利用唯一的实际i r 压降值来减小悲观情绪。 当串扰问题变得很严重时，分析工具需要改变它们的计算模型，增加一些静 态时序分析量，比如d e l t a 延迟，以此获得更加接近真实的电气行为。随着设计 技术发展到纳米级，主要基础架构和计算模型将需要保有更多的电气信息。 如果上述所有因数都存在，我们需要对信号完整性的概念进行重新定义。必 须考虑到影响信号保真度的所有事件。并开发出能在实际电路中传播波形的技 术。大多数信号完整性的影响可以被认为是影响在电路中移动的“虚拟”波形的 事件。目前执行的检查中，大多数都可以改为检查这些波形即可。 总的来说，高性能部件往往泄漏较高，耗能较大，而具有低泄漏和功率标记 的部件性能都较低。考虑到设计工艺参数的敏感性，分析工具必需能够提供一种 以内部关联的方式评估实际范围和功率及性能分在的方法。虽然存在这么多困 难，有一点却很清楚，我们已经开始向真正的信号完整性发展。尽管挑战不断， 但把握s 1 分析技术的发展历程，将能够推动i c 设计向6 5 纳米、4 5 纳米以及更 先进工艺的变迁。 1 3 主要研究内容和论文结构 串扰最小化既可在物理设计布线过程中加以考虑，也可以在后处理步骤中单 独解决。然而，由于串扰依赖于线网及其相邻关系，在相邻线网未能完全确定时， 考虑串扰的布线均需要对可能的串扰影响作出某种半h 略估计。另一方面，尽管后 处理算法在线网调整范围上欠灵活，但它可以采用更准确的串扰估值以获得更加 优化的结果。因此，即使是考虑了串扰的布线结果，也往往需要通过后处理进一 步减小串扰。我们将集中研究在后处理阶段串扰的优化问题。 1 5 全文共分五个章节： 第一章绪论。简要说明了集成电路的发展历程以及超亚微米工艺下信号完整 性带来的挑战，最后提出本文的研究内容。 第二章信号完整性概述。主要介绍信号完整性的基本概念：串扰时延产生的 机理、现象描述及估算的一般方法；串扰噪声的产生机理、现象及估算串扰噪声 的模型。最后我们通过后端时序分析工具p r i m e t i m e 来看一下串扰对一d e s i g n 的影响。 第三章一种尤嘲格串扰最小化算法的实现。我们首先介绍通道布线的基本概 浙江人学硕j 一学位论文 念，随后分析比较了非曼哈顿结构减小串扰的布线算法及曼哈顿结构减小串扰的 布线算法。由于非曼哈顿结构布线算法还不成熟，故我们实现的算法是基于对三 个典型的曼哈顿结构布线算法的分析比较( 3 2 2 ， 3 2 7 ， 3 2 8 j ) 。通过分析比 较发现，文献 3 2 2 中的算法不能直接处理垂直网段，丽文献 3 2 7 中的算法时 间复杂度随着线网的增加而剧增，不利于推广 1 5 。文献 3 2 8 中的算法较前 两种好，但是我们发现通过把水平网段分成子网段，则网段的移动更加灵活。在 这个想法的基础上，我们实现了一种减小串扰的无网格的布线算法，我们将看到 实现的算法在取得较好的优化结果的同时，其运行速度比文献 3 2 8 1 中的算法要 快的多。 第四章优化算法的验证。我们从两个不同的角度对实现的算法作了验证。方 法一是相关文献中常用的，即用典型的布线图形输入到算法中，再比较算法执行 前后线网的串扰量的不同。我们的验证中用了两个较复杂的布线图形，不但可以 看到串扰值的改进，也可以看到优化前后布线结构的变动。第二个方法是结合了 我们的专业方向，取出d e s i g n 中关键路径的布线结构，输入到算法中，输出改 进的布线结构，并在后端布局布线工具中改动相应的布线结构，然后通过后端时 序分析工具来看优化前后串扰s l a c k 值的不同，这在后面将有详细的分析。 第五章全文总结和展望未来。 6 灏江人学顽i + 学位论文 第二章信号完整性分析概述 2 1 信号完整性基本概念 信号完整性( s i g n a li n t e g r i t y ) 顾名思义指的是信号通过传播路径后能否 保持完整性，其较精确的定义是指信号在电路中以正确的时序和电压做出响应的 能力。如果电路中信号能够以要求的时序、持续时间和电压幅度达到输出端，则 该电路具有良好的信号完整性。反之，当信号不能正常响应时，就出现了信号完 整性问题。 一个信号在传输线上( 通常被称为干扰线，a g g r e s s o rn e t ) 传输的时候，因 耦合而对相邻的互连线产生影响，被干扰线( v i c t i m n e t ) 表现为被注入了一定的 耦合电压和耦合电流，这就是串扰。一般来说，串扰是通过两种途径产生的：电 容耦合和电感耦合。电容耦合是因为干扰源上的电压变化在被干扰对象上引起感 应电流从而导致的电磁干扰，而电感耦合是由于干扰源上的电流变化产生的磁场 在被干扰对象上引起感应电压从而导致的电磁干扰。 2 2 串扰噪声( c r o s s t a ikn ois e ) 2 2 1 产生机理及现象描述 信号串扰引起的时延是由于攻击线的信号与被攻击线的信号同时转换引起 的。另一种情况则如下图所示： e n 口r 7 浙江人学硕l 学位论文 图2 1 串扰噪声产生机理及现象 从图中可以看出，在这种情况下，受攻击线的电乎是保持稳定的，即保持高 电平l 或者低电平0 。当攻击线电平转换的时候，由于它们之间耦合电容的作用， 被攻击线的电平出现畸变，会出现高于原电平或者低于原电平的瞬时脉冲。如果 是信号线上发生这种情况，则接收端可能会读取错误的信号逻辑状态。如果是时 钟线上发生这种情况，则出现的瞬时脉冲可能会被当作时钟信号的到来，同样引 起读取的数据不正确。 2 2 2 串扰噪声计算模型 在时序分析中，随着时序分析向关键路径的收敛，可以选用精确度高的模型 来提高时序分析的精度。但是噪声分析不同于时序分析，无论是关键路径还是非 关键路径上的噪声分析都必须是高精度的。近年来有不同的噪声模型出现，甚至 出现了如h a r m o n y ，c l a r i n e t 等专门分析芯片噪声的工具 2 1 。由于现在串扰 噪声的模型众多，我们不可能对所有的模型都进行详细的分析介绍，因此我们将 对一些有代表意义的模型进行比较。 a n i r u d hd e v g a n 噪声模型 2 2 一般来说，v i c t i mn e t s 和a g g r e s s o rn e t s 可能不止一对。但是可以先分 析简单的一对干扰线与被干扰线的情况，然后推广到多对的情况。 v 图2 2 耦合噪卢电路模型 上面的电路图可以写成如下的公式： v 1 浙江大学硕 学位论文 罴懈| 2 黝孙阱 汜t ， 上面的公式中，v l 是a g g r e s s o rn e t 的节点电压向量，v 2 是v i c t i mn e t 上 的节点电压向量，v s 是a g g r e s s o rn e t 的输入电压，c l 表示a g g r e s s o rn e t 的 电容值，c 2 表示v i c t i mn e t 的电容值，c c 表示两根n e t s 之间的耦合电容值。尽 管如此，引起串扰噪声的互连网络有其自身的特征。文献中指出，a 1 2 、a 2 1 、 b 2 的值都应该为零。故公式( 1 ) 可变为如下的公式 窿懈v i = 黝吲+ 卧s 眨z ， 根据以上方程式，对于给定的线性电路，也就是a 1 1 、a 2 2 、c 1 、c 2 以及c c 的值，还有输入斜率u 的值，文献 2 2 中给出了v i c t i mn e tv 2 上可能产生的 最大的噪声值为 v 2 ，m a x - - - 一a - c c a ，i 一1 b l u( 2 3 ) 下面我们对多对a g g r e s s o rn e t s 和v i c t i mn e t s 的模型作简单的分析。图 2 3 给出了计算最大串扰噪声的典型互连线结构。 v i c t i mn e t 图2 3 计算串扰峰值的典型互连结构 通过对典型互连结构的观察，我们考虑图2 4 中的3 r c 电路结构束阐明最大 串扰噪声的计算。 9 浙江大学硕士学位论文 i r 3 + 图2 4 计算串扰峰值的典型互连结构电路图 对于上图，每个节点的最大的串扰噪声如下所示： n m a x ，l = v 2 1 ：- - r 1 ( 1 1 + 1 2 + 1 3 )( 2 4 ) n m a x ，2 = v 2 2 = - - r 1 ( 1 1 + 1 2 + 1 3 ) 一r 2 1 2( 2 5 ) n m a x 3 = v 2 3 = - - r i ( 1 1 + 1 2 + 1 3 ) 一r 3 1 3( 2 6 ) 上述耦合噪声公式也可以书写成如下公式： n m a x 。l = 一r 1 ( c c l + c c 2 + c c 3 ) u( 2 7 ) n m a x 。2 = - - r i ( c c l + c c 2 + c c 3 ) u r 2 c c 2 u( 2 8 ) n m a x ，3 = 一r l ( c c l + c c 2 + c c 3 ) u r 3 c c 3 u( 2 9 ) 一般来说，对于一个树形结构，在节点i ，最大的串扰噪声值n m a x ，j 计算如 下：n m a x ，i = r iy 仃+ 、m x ，i l 。公式中l 表示v i c t i mn e t 节点上的所有 了 耦合电流。 d e v g a n 较早提出了基于互连线r c 网络参数的串扰噪声模型。但是文献 2 1 指出，在o e v g a n 的模型中，原始公式的表达式罩没有出现瞬念而直接是包含r c 参数的矩阵。在把原公式表达式表达成瞬态表达公式后，可以看出在线形倾斜信 号向阶跃信号逼近的时候，瞬念表达式的值会趋予无穷大。这说明该公式会在较 大范围内产生误差。 v i t t a l a 串扰喙声模型 2 3 噪声响应的s 域两数f 公弋( 2 1 0 ) 给出。我们假设输入剑输出之f b j 没有直接 1 0 浙江人学硕f 学位论文 的耦合通路( s = 0 ) ，因此s = 0 抵消了输入1 s 。注意到脉冲响应正是表达式( 2 1 0 ) 乘以s 。 v o ( 垆k 告竽等= = 等 ( 2 1 0 ) 2* l + 6 l s + 6 2 s + + 6 。s ” 式( 2 1 0 ) 对应的频域噪声脉冲宽度函数为： k = f 1 2o d t ( 2 1 1 ) 有效的噪卢脉冲宽度为： j t v 。d t b 1 一口1 = = _ 一 ( 2 1 2 ) j v 。d t 因此我们假设有效的噪声峰值表达式为： 矿p = 志( 2 1 3 ) 这等价于： 2 “( 帆d ( 2 1 4 ) 矿p = j ) _ 一 喵m j v 。d ， 0 图2 5 中给出了典型的中值m 和平均值m 的噪声波形。平均值是： l 础 m ：l 一 f v o d , ( 2 1 5 ) 中值【“下面的积分方程给出： m 0 ( 2 f v o d t = 0 51 1 ；o d t ( 2 1 6 ) oo 淅汀人学硕 j 学位论文 v v m a x mm 图2 5 随机噪声波形图 注意到图2 5 中的波形是弯斜的，也就是说，阴影部分的面积大于直到中值 为止的曲线下的面积。我们用数学表达式表示如下： 。：与f t v o d t ：j v 。 ( z ) m “：尘一1 ， 【l h 囊0 v 0 5d t 2 左边的表达式是矩形下的面积( 平均时问与峰值电压的乘积) ，右边的表达式 是从零到m 为止的曲线下的面积( 总面积的一半) 。这表明： v m a x 堡 ( 2 1 8 ) 现在让我们来考虑一下图2 6 中三角形的面积。三角形的下的面积是v m a x x m 2 。假设这是一个凹形函数，三角形下的面积小于原点与i n 之问的曲线下的 面积，也就是说 下v m a x 肌了1 ， ( 2 1 9 ) 下肌j 1 ， ( 2 1 9 ) 浙江人学硕j 。学位论文 v v m a x mm 图2 6 计算噪声峰值波形图 式子( 2 1 9 ) 的右边部分可写成如下形式： k 胪了v 肘l j v ：o s k + 了v 。 则公式( 2 1 9 ) 变换为： v m a x 堡+ 也 ( 2 2 1 ) 显然，j v f l t 线性叠加法 2 9 串扰引起的时问延迟的变化依赖f 受j 每线信号到达时间( v s a t ) 和攻击线信 号达到时| h j ( a s a t ) 。如图2 1 2 及表2 2 所示，受害线一h 信号延迟的增加是i 1 众 浙江大学颂f 学位论文 多的v s a t 和a s a t 的组合仿真得到的。 a s a t 一o 5一o 2o0 2 v s a t o o 0 2 0 0 8o 1 3 0 0 8 0 20 o oo 0 3o 0 8o 1 3 o 40 0 00 o lo 0 30 0 8 o 60 0 0 0 o o0 o o 0 0 3 表2 2 邻近线网信号不同到达时间对时延的影响 v s a t a s a t 图2 1 2 邻近线信号不同到达时间对时延的影响 当受害线上信号的到达时蝴与攻。 线卜信号的到达时间一样的时候，串扰对 时l 、日】延迟的影响就越大。尽管表格2 2 中给出的结果是通过二维的形式给出的， 但是也可以通过测镀受害线与攻击线达到时h j 的相对值( r s a t ) 来计算串扰时延。 文中作者分析指出：1 串扰时延的增加l r s a t 的关系非常密切；2 r s a t 对串扰 时延的影响限制在某一特定的区域内；串扰时延依赖于驱动能力。上面的第一点 说明用w o r s tc a s ( j 来计算串扰时延是没有必要的。第二点说明即使电路中存在 浙江大学硕 学位论文 攻击线( a g r e s s o rn e t ) ，如果它们的r s a t 在相关的影响范围外，我们就不需要 考虑这些攻击线的影响。第三点说明在分析串扰的时阅延迟的影响的时候必须考 虑攻击线和受害线的驱动强度。 通过使用r s a t ，我们在不需要考虑w o f s t c a s e 的情况下就能得到准确的串 扰时延的结果。但是，我们必须知道攻击线和受害线信号达到时问的精确值。不 幸的是，在实际情况中不可能处理所有的v s a t 与a s a t ，这是因为信号到达的时 间随着输入向量的不同而变化。因此，我们不能直接用r s a t 来计算串扰引起的 延时。我们只能通过静态时序分析得到受害线上的信号与攻击线的信号最早的到 达时间及最晚的到达时间。尽管如此，即使不知道准确的r s a t ，我们仍然能够 通过静态时序分析知道r s a t 的最大值与最小值。 最后文中指出，这个方法能有效、准确的分析串扰引起的时间延迟，并对逻 辑综合与物理设计中解决串扰问题也能起作用。具体可参考文献 2 9 。 2 4 串扰对电路性能的影响 上面我们对信号完整性的现象、产生机理及模型作了介绍，接下来我们通过 一个实际的d e s i g n ( 1 3 0 纳米) 来看一下串扰对i c 设计的影响。 土 木 宰 木 木 木 宰术 丰 宰木 宰木 术牟 车丰 木枣 木幸 木木宰 宰术掌丰 丰 木事 拳事 木术 木术 勉矾龇m明粥砑矾坫似勉忸叭 麒删坳珀博m埔l三m m m 汜挖m 浙江大学五雯j 学位论文 a0 9 2 0 t0 8 4 9 h0 7 7 9 0 7 0 8 c0 6 3 7 00 5 6 7 t j0 4 9 6 n0 4 2 5 t0 3 5 5 0 2 8 4 0 2 1 3 0 1 4 2 0 0 7 2 0 0 0 1 丰丰掌奉 木半 书拳木木丰木 母术丰水术 卑木阜奉丰木 宰半木木车枣木 宰术枣宰宰术木 木车木枣木拳术 宰牛半木宰宰术幸 丰年聿木木母事誊木 卑术率术丰丰木宰木 车车木宰木木丰枣木母丰 木丰车宰木术术丰掌宰术木 木掌木 木枣术掌宰木丰车车木木宰拳事 木术木 木木拳术木 掌术术宰宰宰幸宰木木宰术术木宰宰木掌术木木术幸奉木宰拳术掌 一一一一一一一一一一一一 0 0 0 3 0 0 p a t hs l a c k 图2 1 3 未考虑串扰的时序分析 图2 1 3 是s y n o p s y s 的p r i m e t i m e 对一个d e s i g n 的时序分析，从图中可以 看出所有的p a t h 都满足时序的要求。让我们来看一下图2 1 4 。 1 5 8 5 1 5 3 4 1 4 8 3 1 4 3 2 1 3 8 l 1 3 3 0 1 2 7 9 1 2 2 7 1 1 7 6 1 1 2 5 l2 8 7 5t o t a lp a t h s 5 0v i o l a t i n gp a t h s 一6 7 6t o t a ln e g a t iv es 】a c k 木木 车术 木木宰 木木j c 木木木 枣木木 丰丰木丰 ：| 木丰奉 浙江大学硕：学位论文 1 0 7 4 1 0 2 3 0 9 7 2 0 9 2 1 0 8 7 0 0 8 1 9 0 7 6 8 0 7 1 6 0 6 6 5 0 6 1 4 0 5 6 3 0 5 1 2 0 4 6 1 0 4 1 0 0 3 5 9 0 3 0 8 0 2 5 7 0 2 0 5 0 1 5 4 0 1 0 3 0 0 5 2 0 0 0 1 斗：乖术牛 术宰木水 术术丰木 牛枣木木 堆幸术枣 堆牛木木 宰掌木丰 冰宰葺：宰 堆宰宰掌 章木宰木 宰 毒 木 枣木 木木 术丰 木术 木木 木木 幸木 琦c 宰木木幸宰牛孛术 幸牛木幸木宰宰宰木拳 术木木木乖牛 # 车水术 木丰木宰母牛牛幸牟牛 丰宰木枣木木幸木木幸牛 丰木车丰丰宰木枣木木宰宰 i 木半堆木木掌掌宰事奉幸牛母 】术术丰木木术术幸半木车车木奉 术木木木木枣拳术术卡车掌 孝乖隼掌 i 术宰枣木术木术术术术术术木奉丰掌术术木爿c 母术木木术拳术枣术枣木水拳术木宰木卡车丰木木丰半 木幸木辜枣木木枣木木木术木木丰掌拳拳木拳章奉木木木拳宰宰丰 一0 7 2 一一一一一一一一 o p a t hs l a c k 图2 1 4 考虑串扰的时序分析 3 0 0 图2 1 4 是用s y n o p s y s 的p r i m e t i m e 对同一d e s i g n 的时序分析，这个时候 考虑了串扰的影响。从图中可以看到有几条p a t h 出现了t i m i n gv i o l a t i o n 。其 总的t i m i n gs l a c k 为一6 7 6 n s 。从这个例子中我们可以看到在深亚微米工艺下， 串扰的影响是不能被忽略的。因此在本文的后嘶部分，我们将分析实现种减小 串扰的优化算法。 2 4 p a t h c o u n t 浙江大学硕上学位论文 第三章一种无网格串扰最小化算法的实现 3 1 布线基本概念 我们都知道超大规模集成电路的通道布线问题是n p 完全问题。本文实现的 减小串扰的优化算法是通道布线中的无网格布线。故我们先对布线的基本概念作 一个简单的介绍。 3 4 通常有两种方法来实现布线，一种是直接区域布线，另一种是分两步实现的 总体布线( g l o b a lr o u t i n ) 和详细布线( d e t a ilr o u t i n g ) 。典型的区域布线有线 探索布线和迷宫布线，具体可参考文献e 3 1 3 2 3 3 。总体布线的任务是把线 网分配给布线区域，规定线网要走过的路径；而详细布线的任务则是确定各个线 网在布线区域内的具体位置，从而完成布线。通道布线和开关盒布线是详细布线 中两种典型的布线方式。在通道布线中，线网的引脚分别分布在通道的上端和下 端。开关盒布线也称为四边通道布线，即它的引脚分别分布在布线区域的四周。 如图3 1 所示。 i 通