（计算机应用技术专业论文）基于boole过程的考虑互连效应的eda方法研究.pdf

基于b o o l e 过程的考虑互连效应的e d a 方法研究 摘要 在v d s m 工艺下，对i c 电路进行逻辑级模拟验证、测试生成、布局和 布线等技术处理时，均要考虑互连效应所产生的影响，只有这样才能较真实 地反映电路的特性。本文对b o o l e 过程论中的波形计算进行了扩展，运用该 理论研究上述四方面技术中的考虑互连效应的新算法。 互连效应，特别是其中的串扰问题对电路的逻辑和时序有着严重的影 响，仅凭传统的逻辑级模拟已经不能反映电路的真实情况。目前的模拟验证 技术必须考虑互连效应。而准确地考虑这些因素还必须要做模拟布图。耦合 电容和动态的信号跳变情况是产生串扰的两个重要因素，其中后者决定了串 扰能否发生，因此通过逻辑级模拟产生的波形关系对串扰估计和优化就具有 了重要作用。运用考虑互连效应的模拟所获得的信号跳变数可以较为准确地 估计电路的功耗。 本文提出了基于b o o l e 过程论的逻辑级模拟验证方法。针对冒险检测、 反馈环路的处理、伪路径识别和惯性延迟冲突等波形模拟中的关键问题，采 用基于b o o l e 过程的方法进行描述、分析和解决。冒险检测定理给出了通过 波形运算检测电路中冒险现象的形式化方法：分时片处理法和波形递增算法 解决了b 0 0 1 e 过程在处理电路中反馈环问题上的缺陷；伪路径识别算法能够 有效地发现电路网表中的冗余部分；而惯性冲突消除法能使信号波形的描述 更加准确。本文运用这些概念和结论设计了并行逻辑级模拟基本算法。该算 法不需要对初始数据进行划分，而是利用活动元件计算的高度并行性在模拟 过程中动态地形成活动元件队列的方法进行并行计算。本算法通过对队列中 的元素计算调度优先权的方法提高了并行加速比。 为了模拟互连效应下的逻辑波形，本文将互连线看作一个元件，定义了 其上的原始波形、串扰波形和互连传输门。在给定工艺和版图信息的条件下， 提出了基于b o o l e 过程中波形表示的互连线上的串扰波形计算方法。定义了 逻辑一串扰关系图，将逻辑级模拟基本算法和串扰计算结合起来，并通过该 图完成了考虑互连效应的逻辑波形模拟。本文使用v h d l 描述了互连线串 哈尔滨工程大学博士学位论文 扰延迟的计算方法。 对b o o l e 过程中的波形敏化概念，本文进一步定义了带时间窗口的敏化 波形集的运算规则，提出了在串扰条件下生成敏化测试波形的方法。 针对详细布线中的串扰优化问题，本文重新定义了b o o l e 过程中的波形 距离。将逻辑波形和耦合电容相结合，给出了线网间串扰的定义和网格模式 下双层通道布线中最小化串扰的目标函数，更加准确地反映了线间串扰的情 况，为布线的调整提供更大的余地。运用本文提出的布线生成树和改进的遗 传算法设计了串扰优化的通道布线方法，有效地减少了计算量。运用本文提 出的可变参数法设计了串扰优化的开关盒布线方法，充分利用了布线资源。 以上方法中各线网的优化是同时完成的，具有潜在的并行性。 本文采用基于b o o l e 过程中波形计算的考虑互连效应的逻辑模拟方法， 进行了更加准确的功耗估计，提出一秘同时完成线长优化和功耗均匀分布的 宏模块布局算法。它考虑了引脚的实际位置，使得线长的优化具有更大的灵 活性；通过确定功耗中心的方法方便了在功耗均匀约束时的功耗提取；通过 结群的方法将大规模的布局优化问题分层次求解：并通过单元合并的方法减 少了连线的数量。 关键词：b o o l e 过程；互连效应；逻辑模拟；详细布线；功耗估计 基于b o o l e 过程的考虑互连效应的e d a 方法研究 a b s t r a c t t h et e c h n o l o g yt r e a t m e n tw i t hi ci nv d s m f o re x a m p l el o g i cl e v e l s i m u l a t i o n ，a t p g ，r o u t i n ga n dp l a c e m e n t ，m u s tc o n s i d e rt h ei n t e r c o n n e c te f f e c t o t h e r w i s et h ec h a r a c t e r i s t i co fc i r c u i t sc a r ln o tb er e f l e c t e dm o r ef a c t u a l l y s o m e e x t e n s i o n sa r ed o n eo nt h ew a v e f o r mc o m p u t i n gi nb o o l e a np r o c e s si n t h i s d i s s e r t a t i o n ，b yw h i c hs o m en e wa l g o r i l r n sc o n s i d e r i n gi n t e r c o n n e c te f f e c ta r e d i s c u s s e di na b o v ef o u rt e c h n o l o g i e s i n t e r c o n n e c te f f e c t , e s p e c i a l l yc r o s s t a l kd i s t u r b st h el o g i ca n dt i m es e q u e n c e b a d l y , t h et r a d i t i o n a ll o 百cl e v e ls i m u l a t i o nc a nn o tr e f l e c tt h ef a c t u a ls t a t eo f c i r c u i t s oi n t e r c o n n e c te f f e c tm u s tb ec o n s i d e r e di ns i m u l a t i o nt e c h n o l o g y t h e l a y o u ts i m u l a t i o nm u s tb ed o n ef o rc o n s i d e r i n gt h ef a c t o r se x a c t l y c o u p l i n g c a p a c i t a n c ea n dd y n a m i cs w i t c h e so fs i g n a l sa r et w oi m p o r t a n tc r o s s t a l kf a c t o r d y n a m i cs w i t c h e s o fs i g n a l sd e c i d et h eg e n e r a t i o no fe r o s s t a l k 。s ot h e w a v e f o r m sr e l a t i o ng e n e r a t e db yl o g i cl e v e ls i m u l a t i o nh a si m p o r t a n te f f e c to nt h e e s t i m a t i o na n do p t i m i z a t i o no fc r o s s t a l k t h ep o w e ro fc i r c u i tc a nh ee s t i m a t e d m o r ee x a c t l yb yt h es u mo fs w i t c h e so fc i r c u i tg e n e r a t e db yt h es i m u l a t i o n c o n s i d e r i n gi n t e r c o n n e c te f f e c t ab o o l e a np r o c e s s - b a s e di c g i cl e v e ls i m u l a t i o nm e t h o di sp r e s e n t e di nt h i s d i s s e r t a t i o n s o m ec r i t i c a lp r o b l e m s ，f o re x a m p l eh a z a r d sf i n d i n g ，f e e d b a c kc y c l e t r e a t m e n t ，f a l s ep a t h sf i n d i n ga n di n e r t i a ld e l a yc o n f l i c t ，a r ed e s c r i b e d ，a n a l y s e d a n ds o l v e d t h eh a z a r d sf i n d i n gt h e o r yi saf o r m a lm e t h o dt of m dh a z a r d si n c i r c u i tb yc o m p u t i n gw a v e f o r m s t i m ep i e c em e t h o da n dw a v e f o r mi n c r e a s e a l g o r i t h ms o l v et h ed e f e c to fb o o l e a np r o c e s si nf e e d b a c kc y c l et r e a t m e n t f a l s e p a t hf i n d i n ga l g o r i t h m c a l lt h er e d u n d a n tp a r ti nn e t l i s t i n e r t i a lc o n f l i c t e l i m i n a t i o nc a nd e s c r i b ew a v e f o r m sm o r ee x a c t l y u t i l i z i n ga b o v ec o n c e p t sa n d r e s u l t s ，ap a r a l l e la l g o r i t h mf o rl o g i cl e v e ls i m u l a t i o ni sp r e s e n t e d i tn e e dn o t p a r t i t i o nt h ed a t a ，b u tf o r m st h ea c t i v ec o m p o n e n t sq u e u et o r e a l i z ep a r a l l e l c o m p u t i n gi ns i m u l a t i o n t h ea l g o r i t h mi m p r o v e sa c c e l e r a t i o nr a t i ob ys c h e d u l i n g p r i o r i 舭 1 1 1 哈尔滨工程大学博士学位论文 f o rs i m u l a t i n gt h el o g i cw a v e f o r m si ni n t e r c o n n e c te f f e c t , t h e i n t e r c o n n e c t c o m p o n e n t i sd e f m e d ，i n c l u d i n gi t so r i 百i l a lw a v e f o r n l ，c r o s s t a l kw a v e f o r ma n d i n t e r c o n n e c tt r a n s p o r tg a t e ab o o l e a np r o c e s s - - b a s e dc o m p u t i n gm e t h o df o r c r o s s t a l kw a v e f o r m so nn e t si sp r e s e n t e da f t e ro b t a i n i n gl a y o u ti n f o r m a t i o n n e l o r g i c c r o s s t a l kg r a p hi sd e f m e d i ti n t e g r a t e st h eb a s i ca l g o r i t h mo fl o g i cl e v e l s i m u l a t i o na n dc o r s s t a i kc o m p u t i n g ，b yw h i c ht h ew a v e f o r m ss i m u l a t i o n c o n s i d e r i n gi n t e r c o n n e c te f f e c tc a r b ep e r f o r m e d t h ec r o s s t a l kd e l a yc o m p u t i n g o f i n t e r c o n n e c ta r ed e s c r i b e di nv h d l a i m i n ga tt h es e n s i t i z a t i o nc o n c e p ti nb o o l e a np r o c e s s ，t h ec o m p u t i n gr u l e s o fs e n s i t i z a t i o nw a v e f o r m ss e t sw i t h t i m ew i n d o w sa r ed e f i n e d t h em e t h o d g e n e r a t i n gt e s tw a v e f o r m si nc r o s s t a l ki sp r e s e n t e d f o rm i n i m i z i n gc m s s t a l ki nd e t a i l e dr o u t i n g ，t h ed i s t a n c eb e t w e e nw a v e f o r m s i nb o o l e a np r o c e s si sd e f i n e dn e w l y i n t e g r a t i n gc o u p l i n g c a p a c i t a n c e ，t h e c r o s s t a l kb e t w e e nn e t si sd e f i n e d b a s e do na b o v ew o r k , t h eo b j e c tf u n c t i o nf o r m i n i m i z i n gc r o s s t a l ki nt w o l a y e rd e t a i l e dr o u t i n gi sp r e s e n t e d i tc a l lr e f l e c tt h e c r o s s t a l kb e t w e e nn e t sm o r ee x a c t l ya n da f f o r dm o r es p a c ef o ra d j u s t i n gr o u t i n g r o u t i n gg e n e r a t i n gt r e ea n di m p r o v e dg a a r ep r e s e n t e d ，b yw h i c ht h ec h a n n e l r o u t i n gm e t h o dw i 1m i n i m i z i n gc r o s s t a l ki sd e s i g n e d i tc a r lr e d u c et h ec o s to f c o m p u t i n g 。v a r i a b l ep a r a m e t e rm e t h o di sp r e s e n t e dt od e s i g nt h er o u t i n g a l g o r i t h mw i t ho p t i m i z i n gc r o s s t a l k ，a n dt h er o u t i n gr e s o u r c ei su t i l i z e df 1 1 1 l y a b o v em e t h o d sh a v ep o t e n t i a lp a r a l l e l i s mb e c a u s eo fc o m p u t i n go fa l ln e t si s p e r f o r m e ds i m u l t a n e i t y t h ew a v e f o r mc o m p u t i n gc o n s i d e r i n gi n t e r c o n n e c te r i e c tc a nb eu t i l i z e dt o e s t i m a t et h ep o w e ro fc i r c u i tm o r ee x a c t l ys oam a c r o c e l lp l a c e m e n ta l g o r i t h m t h a tb o t hm i n i m i z e sl e n g t ho fw i r e sa n dd i s t r i b u t e sp o w e re q u a b l yi sp r e s e n t e d i t c o n s i d e r st h ep o s i t i o no f c e l l p i n s ，m a k e st h em i n i m i z i n go f l e n g t ho f w i r e sm o r e f l e x i b l e t h ec o n f i r m i n go fp o w e rc e n t r em a k e st h ep i c k i n gu po fp o w e rm o r e c o n v e n i e n t a l g o r i t h md e c o m p o s e sb i gs c a l ep l a c e m e n to p t i m i z a t i o nb yg r o u p i n g a n dr e d u c e st h es u mo f w i r e sb yi n t e g r a t i n g k e y w o r d s ：b o o l e a np r o c e s s ，i n t e r c o n n e c te f f e c t ，l o g i cl e v e ls i m u l a t i o n ，d e t a i l e d r o u t i n g ，p o w e re s t i m a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献等的 引用已在文中指出，并与参考文献相对应。除文中已经注明 引用的内容外，本论文不包含任何其他个人或集体已经公开 发表的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 作者 签字) ：三墨型! 日 期：2 萨眸月 第1 章绪论 i ；j 宣；i i i i i , i ；= j ；= = ；常 1 1 课题的研究意义 第1 章绪论 随着i c 技术的发展，一个芯片上集成的晶体管数目己高达十亿的数量 级。a s i c ( a p p l i c a t i o ns p e c i f i ci c ) 已经演变为s o c ( s y s t e m o nac h i p ) ”1 。 在这一过程中，i c 特征尺寸不断减小，生产工艺已进入v d s m ( v e r yd e e p s u b - m i c r o n ) 阶段。线宽为0 1 8 0 1 3 t i n 的配产品已成为主流，0 1 删以下 电路的设计和制造正在兴起，这对集成电路的设计方法提出了新的挑战列。 另一方面，芯片工作频率也越来越高，目前主流芯片工作频率都在g h z 的 量级上，超高速芯片的设计已成为研究热点”1 。 回顾近3 0 年发展历程，e d a ( e l e c t r o n i cd e s i g na u t o m a t i o n ) 技术分可 为三个阶段。七十年代为c a d ( c o m p u t e ra i d e dd e s g i n ) 阶段，人们开始 用计算机辅助进行i c 版图编辑和p c b ( p r i n t e dc i r c u i tb o a r d ) 布局布线， 取代了手工操作。八十年代为c a e ( c o m p u t e ra i d e de n g i n e e r i n g ) 阶段， 在图形绘制功能的基础上，增加了电路功能设计和结构设计，并且通过电气 连接网络表将两者结合在一起，以实现工程设计。九十年代为e s d a ( e l e c t r o n i cs y s t e md e s i g na u t o m a t i o n ) 阶段。由于在整个电子设计过程中， 自动化和智能化程度还不高，各种e d a 软件界面千差万别，学习使用困难， 并且互不兼容，赢接影响到设计环节闻的衔接。于是人们开始追求贯彻整个 设计过程的自动化，这就是e s d a ，即电子系统设计自动化。其主要标志是 系统级设计工具的推出( 例如硬件描述语言) 和逻辑设计工具的广泛应用。 目前e d a 系统功能已覆盖了电子设计的全过程，且有开放的环境和标 准化的数据接口，具有相当高的水平。尽管如此，i c 设计技术仍然落后于 制造工艺的发展。i c 制造工艺的发展在模拟验证、延时分析、功耗和串扰 优化等方面为e d a 带来了更多的挑战。 在v d s m 电路中，互连线的延迟已超过门延迟。在0 1 8 a n 时，互连延 时已占电路延时的8 0 ，而到0 1 v n 左右时，互连延时则可占到9 5 以上。 哈尔滨工程大学博士学位论文 由于互连线寄生电容增大，已成为元件负载的主要决定因素，而线间距的减 小及电路中同时跳变数目的增加，使得串扰噪声、电源噪声等噪声问题的影 响相当突出，严重影响电路的功能和定时特性川。此外，功耗问题也日益突 出 这些挑战促使人们在e d a 基本理论和方法以及e d a 工具的研制等方 面进行更深入的探索。布尔代数作为数字逻辑的经典理论，成功地描述了数 字电路的逻辑行为。但随着i c 技术发展到当今的高复杂度和超高速阶段， 电路的定时问题越来越突出，而且随着串扰问题的日趋严重，布尔代数的理 论和模型已经不能胜任模拟验证和延时分析等方面的需要。国内外一些学者 已经认识到这是基础理论的缺欠。于是在1 9 9 4 年，我国闵应骅教授提出布 尔过程的概念”。与此同时，美国的l a m 和b r a y t o n 也提出时变布尔函数 概念”1 ，他们的目标都是为了处理用布尔代数无法处理的定时问题。1 9 9 6 年底，闵应骅等对布尔过程、波形函数、波形极限、波形多项式等概念给出 了明晰的定义”1 ，用数学分析的途径精确地描述逻辑电路的定时特性。虽然 这个理论正处在发展中，但已经显现出它在复杂高速i c 设计方面广泛的应 用前景。 目前，对布尔过程理论的扩展和应用研究尚有许多工作要做。本课题的 研究内容是将b o o l e 过程中波形表示和计算的方法作必要的扩展，使之应用 于互连效应下的逻辑模拟验证和测试、串扰优化布线、以及功耗优化布局等 方面。本课题得到如下基金的资助： 国家自然科学基金： b o o l e 过程论中高速a s i c 设计自动化新方法研究( 6 9 9 7 3 0 1 4 ) 黑龙江省自然科学基金： 复杂高速a s i c 芯片定时分析新模型新方法研究( f 0 2 0 9 ) 1 2 论文中涉及到的e d a 技术 1 2 1 逻辑模拟验证 逻辑模拟是在逻辑设计阶段，对自动综合或人工设计而生成的逻辑网 络的逻辑行为作验证。逻辑模拟的对象是由门和功能块等元件组成的逻辑电 2 第1 章绪论 路。为了对逻辑电路进行模拟，要对被模拟的电路建立模型，包括电路网表、 信号状态值、延迟模型和元件模型等。模拟模型反映实际电路的特性。越接 近于实际电路，模拟结果越精确，同时也增加了复杂度。选取什么样的模型， 取决于模拟的目的和对模拟的精度要求。 逻辑模拟算法的基本思想是将旋加在电路外部输入的激励信号通过各元 件向输出端传播，得到各节点的信号值。在实际处理过程中有许多不同的模 拟方法”，大体分为编译法和表驱动法两类。编译法的信号值采用二值模型， 元件只有基本逻辑门和一些特殊触发器，采用零延迟模型。每个逻辑门的信 号值计算直接采用逻辑运算指令来实现。这样，将电路的模拟过程直接编译 成计算机指令代码，通过运行生成的机器语言程序，实现电路的模拟。事件 表驱动法是目前逻辑模拟器采用的典型算法。该算法建立在内部表示电路结 构的静态数据结构的基础上，在外部激励信号的作用下，逐渐得到各级元件 的响应。节点信号的每一次变化为一个“事件”，由事件驱动该信号的负载元 件，根据元件的功能计算元件输出端的逻辑值，并得到新的事件，这样逐级 传播，直到不再存在新的事件，或者达到指定的结束时刻为止。 模拟结果包括输出波形文件和电路错误报告。波形文件随着模拟时钟的 前进不断添加新的模拟结果。电路错误报告保存模拟过程中得到的检查结果， 供设计者参考。 1 2 2 故障测试 i c 的测试问题就是用特定的一系列信号以一定的顺序加在被测电路的 输入端，观察其输出端的结果，如果与正常电路的输出结果相同，则认为被 测电路是合格的，否则认为电路有故障。 故障测试的主要问题是如何得到测试向量。a t p g ( a u t o m a t i ct e s t p a t t e r ng e n e r a t i o n ) 是根据逻辑电路本身的结构用算法自动生成测试向量。 测试生成算法，尤其是v d s m 互连效应下的测试生成，是目前研究的重要方面 【1 1 】 1 2 3 布局 布局问题就是要确定芯片版图设计中各模块在芯片上的精确位置，其目 标是在最小化芯片面积的同时满足其它约束，如线长、延时和功耗等。由于 一3 一 哈尔滨工程大学博士学位论文 i ；j i ii!,i i l l ；j ；# = 布局设计的复杂性通常将布局分为初始布局和迭代改善布局两个子过程。 首先通过一些构造性算法获得一个初始的布局构型，再通过一些优化算法进 行迭代改善，从丽获得最佳或满意的布局效果。 解决v l s i 的布局问题的最常采用策略是划分或结群。划分的思想是通过 对芯片进行连续的划分过程，使单元不断地限制在更小的区域内”1 。但是 它们于大规模电路易于陷入局部最优解，从而影响布局质量。结群的思想是 将连接紧密的单元结合在一起，作为一个整体参与布局，从而减小原始电路 的规模。从上世纪8 0 年代开始，出现了些基于非线性连续规划和二次规划 的算法，例如r i t u a l ”、g o d i a n ”圳及p r i m e l l 6 1 等。这类算法基于严格的数学 分析来证明它们的求解质量，可在较短的时间内得至0 全局最优解，而且可以 把时延、功耗因素等作为布局约束条件加入到问题描述中。将其与结群技术 相结合”“，有利于解决甚大规模集成电路的布局问题。 为了解决计算量爆炸的问题，模拟退火、遗传算法、人工神经网络等基于 随机优化的启发式算法被广泛应用于布局闯题”“1 ，得到很好的布局质量， 但它们的缺点是计算时间较长。 1 2 4 布线 布线过程分为总体布线和详细布线。总体布线确定线网的大致走线，它 将各线网合理地分配到各布线区域中，以确保尽可能高的布通率，详细布线 则最终产生线网在芯片上的实际走线。 1 2 4 1 通道布线问题 1 9 7 1 年a h a s h i m o t o 和s t e v e n s 首先提出了通道布线的概念“，把整个 布线区域划分成些彼此独立的予区域，即通道区，再对每个通道区单独布 线，使得问题得以简化。布线区域主要有两边通道、l 型通道和四边通道( 开 关盒) 等。已经证明两边通道布线是一个n p 完全问题，面对于四边通道这类 二维通道区布线问题，还没有令人满意的解决方法。 通道布线的优化目标主要有通道高度最小化、通孑l 数最小化、线长最小 化和串扰最小化等。例如文献【2 2 使用线网投影长度对通道内线网设置优先 级依次布线，减少了布线面积和通孔数：文献 2 3 提出种用神经网络模型 求解通道布线的算法，以总线长最短、轨道数最少为优化目标，通过均场退 d - 第1 章绪论 火方程迭代求解；而h z h o u 等通过调整平行线网间的距离和重叠长度来改 变耦合电容，实现了串扰优化。 1 2 4 2 通道布线算法 左边算法”在没有垂直约束的情况下能得到最小通道高度。由于它把一 个线网放在一个轨道上，自然会增加轨道的数目。为了减少轨道的数目 d e u t s c h 提出了狗腿算法“，通过引入狗腿减少了通道的高度。合并算法” 的基本思想是在通道布线时，对于具有水平约束的两个线网必不能布于一个 轨道上，而不具有水平约束的两个线网可能布于一个轨道。该算法引入了“带 区”的概念，在“带区”中新的待布线网与先前已布的线网结合起来，组成 合成线网。贪婪算法8 “允许同线网可以有几个干，分布在各个轨道上的同 一线网的轨道从左至右尽可能早的用狗腿连接起来。b u r s t e i n 和p e l a v i n l 2 s j 提 出的层次式通道布线的算法，运用“分而治之”的策略把一个i n n 的网格 布线问题化简为2 n 的网格布线问题。另外，r e e d 等提出的y a c r 2 算法” ”1 也是一个很好的通道布线算法，但它难以解决垂直约束关系比较复杂的问 题。在多层通道布线方面，c h e r t 和l i u ”首先提出了基于合并算法和左边算 法的三层通道布线算法。h a m b r u s h 在文献 3 2 】中提出了一种1 1 层通道布线 算法，对布线层数、通道宽度、线网重叠和通孔数目等因素之间的关系进行 了详细论述。而算法c h a m e l e o n 1 将多层通道布线分成划分和详细布线两 步，划分以整体通道面积最小为目标，把布线问题划分为两层或三层通道布 线子问题。 1 2 4 3 串扰优化问题 当版图特征尺寸不断减小而芯片面积和时钟频率不断增大时，噪声问题 变得相当严重。相邻电路和互连线之间的耦合以及电路同时跳变所产生的感 应噪声是最常见的。串扰是噪声的一种形式，它主要是由于相邻连线之间的 耦合电容引起的。耦合电容的大小取决于线间的距离和它们相邻一起走线的 长度。串扰会造成传播延迟和逻辑错误。于是人们开始在总体布线和详细布 线过程中进行串扰优化”刈，这无疑加大了布线问题的难度。 串扰优化既可以在物理设计布线过程中加以考虑，也可以在后处理步骤 中单独解决。目前大多数串扰优化算法在详细布线阶段才对串扰进行精确地 一5 哈尔滨工程大学博士学位论文 计算”1 。后处理算法虽然可以获得准确的布线数据，但在线网调整范围上欠 灵活。文献 3 6 3 9 都是讨论后处理中的串扰优化的。文献1 3 6 将串扰模型化 为平行网段问的斥力，然后再用参数迭代线性规划方法调整线网，该方法不 能直接处理垂直网段。文献 3 7 通过整数规划方法置换通道中线序来减小串 扰，能从全局规模上调整串扰。但它无法处理屏蔽效应，性能受网格的约束， 考虑串扰时出现的非线性目标函数使之难以开发有效的无网格优化算法。文 献 3 8 的结果是目前已知文献中最好的，它着眼于网段位置的微调，根据与 目标网段相邻的垂直段的变化将目标网段的撮动范围划分为一系列子区间， 使得在每个子区间内目标函数是单调或单峰的，以便保证不解非线性方程， 只需通过二分法或黄金搜索就能收敛到优化位置。文献 3 9 1 提出在总体布线 和详细布线过程之间，使用定量的方法进行线网排序和调整线间距，进而处 理串扰和定时约束问题。文献【4 0 】通过在局部布线区域进行串扰预测的同时 插入屏蔽的方法，实现了全芯片的布线串扰优化。 为了更加灵活地进行串扰优化，一些人提出了在总体布线阶段避免串扰 的方法。x u e 等提出了一种在总体布线之后对布线结果进行调整以减少串扰 的算法”“。该算法使用网格模型并假设只在相邻线网间存在串扰，通过界限 划分和线网排序来减少串扰。该方法完全基于区域，若一个区域经过界限划 分和线网排序仍需要额外的空白道，那么区域中的一些线网必须拆除并重布 到其它的区域中。z h o u 等提出了一种基于最小串扰s t e i n e r 树和拉格朗曰松 弛法”“的总体布线算法，首次在总体布线期间考虑如何避免串扰。算法采用 了更一般的串扰模型，为了能够精确地估计串扰，该算法将总体布线扩展瓢 包括层和道分配。文献 4 u 提出一种基于总体布线阻塞信息的早期( 详细布 线完成前) 互连线耦合电容噪声估计方法，在确定的走线位置之前，采用概 率估计的方法抽取耦合电容。另外，还有一些辅助减弱串扰噪声的方法。例 如，文献f 4 2 】通过优化互连线及驱动管脚的几何尺寸减小互连线延迟和串扰 噪声。文献 4 3 】通过在门的输出绑定负载电容来减少耦合噪声、减少信号跳 变的衰减。 1 2 5 低功耗设计 特征尺寸的缩小、器件密度和功耗密度的增加使得目前高性能集成电路 芯片的片上温度急剧升高。温度的升高严重影响电路的性能和可靠性洲。因 6 一 第1 章绪论 此在集成电路制造之前，需要对集成电路芯片表面的温度分布情况进行估计 及优化，热布局问题已经成为集成电路设计的一个热点。文献 4 5 】介绍了一 种综合考虑1 c 电学性能指标和热效应的布局优化方法，在保证面积、连线 长和延迟等不被恶化的基础上，通过降低或消耗芯片上的热点来优化芯片温 度分布情况。w a n g 等人”1 提出了采用基于a t p g 的方法估算电路最大功耗 下限的方法，通过从内部节点的信号翻转分配，得到一组输入测试向量，使 得电路在其驱动下产生的开关功耗最大。文献 4 7 】提出了一个考虑耦合效应 的互连线能量的解析模型，用一个时间参数表示在两个事件之间的相关时间 长度，从而得到更精确的互连线能量模型，为功耗估算提供依据。文献 4 8 用 线性规划法最小化动态功耗。而文献 4 9 ，5 0 讨论了在多芯片模块设计( m c m s ) 中的热布局问题。 准确的功耗估计是各类功耗优化算法的基础。c m o s 电路的功耗不仅 和它本身的一些属性有关，比如电压、负载电容等，另外还和整个电路的平 均翻转频率有关，因此精确的统计出电路的翻转频率是正确估计功耗的关 键。目前有许多研究机构、e d a 软件公司以及一些f o u n d r y 厂商都在致力 于研究快速准确的功耗估算模型，这些方法主要分为三类：统计估算、概率 估算和基于模拟的估算”“。 在统计方法中，电路模拟器在电路的输入端旌加较短的随机序列对电路 进行模拟，并同时估算当前电路的功耗，当功耗的平均值逼近一个固定的数 值时，模拟过程终止，并将这个数值作为电路的平均功耗。 概率分析方法是首先指定所有输入信号的维持在“0 ”或“i ”的概率， 然后根据电路的逻辑关系，按照布尔代数和概率论推算所有内部节点的概率 1 5 2 j 由这些数据就可以推算出电路的平均功耗。其优点是速度较快并且和输 入数据无关，但这种方法的可靠性完全由输入信号指定的几率确定的，而这 种几率本身就很难准确定义。同时在估算内部节点的概率时，各个节点在时 间和空间上的关联模型也影响这种方法的准确性。 基于模拟的功耗分析方法是目前绝大多数高层功耗分析软件采用的方 法，它利用高层次的模拟器对电路进行时序模拟，得到所模拟电路内各个节 点的翻转率，并通过这些翻转率计算出电路的功耗。因为它充分考虑了输入 向量的变化情况，所以比前两种方法都要准确，计算精度基本可以和电路级 模拟器得到的结果类似。虽然它的速度比前两种方法要慢一些，但要比电路 一7 一 哈尔滨工程大学博士学位论文 模拟器快5 7 个数量级。 2 6 底层相关的设计 在v l s i 系统设计、行为设计和逻辑设计过程中，未考虑到的与半导体 制造工艺有关的因素( 如延迟、功耗问题等) 严重影响设计结果的性能，以至 使物理设计结果的性能远离原来的设计目标。因此，只有将影响性能的底层 参数和信息引入高层次设计中，才能使高层次设计结果在进行物理实现之时 能满足性能要求。 超深亚微米工艺使芯片内互连线产生的寄生效应对时延、功耗等电路特 性起着至关重要的作用。当互连线延迟超过元件延迟时，在综合过程中被认 为是正确的设计结果，在物理设计之后却会发现其远不能满足原来的时延和 功耗要求。目前已经有许多关于时延驱动布图算法的研究”4 。1 ，但是仅仅靠 物理设计过程解决时延和功耗的问题有很大的局限性，必须在逻辑设计过程 中充分考虑时延和功耗约束，将逻辑设计和物理设计有机地结合起来，才能 最有效地解决互连线引起的问题。 1 3b o o ie 过程论 传统上布尔代数是数字系统自动设计的主要理论工具，但它无法处理数 字电路的定时问题；而延时分析又是独立于逻辑运算的。作为数字系统设计 的模型，它们都是不完整的，而且在处理电路延迟和异步性问题上并不令人 满意。为此，闵应骅等人提出了b o o l e 过程理论”j 。 b o o l e 过程论将电路的逻辑属性和时滞属性结合起来定义为波形，给出 了一种用数学分析途径精确地描述逻辑电路的定时特性的方法，有利于设计 中的定时验证和时滞测试9 1 。传统上，人们使用波形图对电路进行直观地分 析与综合。但是，这对于大型电路显然是不适宜的。b o o l e 过程将波形图抽 象为波形函数和波形多项式，利用数学方法进行分析和处理。波形函数可以 用数学工具形式地加以处理。电路的原始输出可以用关于输入的波形多项式 来表示，为电路表示提供了一种解析途径”。波形极限的概念精确地反跌了 电路中的通路敏化，在定时验证和测试方面具有广泛的应用性。b o o l e 过程 论中对通路敏化的概念进行了重新定义9 “，它与传统的敏化概念是相容的， 一8 第1 章绪论 但更接近实际，而且是对输入波形可以任意的电路敏化的推广。它对确定最 长和最短可敏化通路、假通路有重要作用。 目前b o o l e 过程理论正处于初始阶段，但却显示出它在超高速计算机设 计和高速i c 设计方面潜在的广泛应用前景。 1 3 1b o o l e 过程的基本理论 布尔过程论的基本理论包括布尔过程及波形的概念：波形运算的定义和 规则；波形多项式；波形差分、距离、极限的概念：波形敏化概念及其定理 等。这里给出本文用到的一些定义和定理。 定义1 - 1 布尔过程 z 0 ) j f 丁) 是与参数，有关的布尔变量族，其中t 在一个参数集t ( 一m ，+ 硝内变化。 定义1 - 2 如果实值函数x ( o 对任何t ，坝f ) = o 或1 ；而且坝f ) 是最多具 有可数多个不连续点一o 。 r l t 2 占，则称x ( o 为波形或波 形函数。 定义1 - 3 实值函数 f 0 ，t 0 ， c 0 0 ( t ) = ( 1 - 1 ) 【1 ，t 0 称为基本波形，简记为。，它表示只在t = - o 有一个上升沿的波形。 任何波形函数都可用基本波形来表示。例如，在t = f 处有一个上升沿 的波形为，( f ) = o f ) ，筒记为0 3 ，；只在t = f 处的下降沿波形可表示为 l 一国，；在t = r 处上升、脉宽占的正脉冲可表示为甜，- 0 ) ，而相应的负脉 冲为1 一国，+ 珊。 定理1 - 1 设以鼠c 是波形，则 m i n ( 4 占) ；彳x 置、 m d x ( a ，b ) = 爿+ 口爿尽| l n d , x ta 。8 ，c 、= a + 8 + e - 4 8 - a c b c a b c ， 口z ，2 “( ，) ，i ( 1 - 2 ) 甜，x 甜，+ d = 。，+ 如8 0 ，i 若盖只则，。， 一， 其中，x 和，是实数，十、一、指实数运算，式中的可以省略。 一9 - 哈尔滨工程大学博士学位论文 定理l - 2 设爿，占是波形，a n d , ，n a n d ，o r ，m 姐，：p 是延时为f 的 基本门，则 a n d ，o ，b ) = a ，坟、 n a n d ( a ，b ) = 1 4 ，毋i ，( 0 ，b ) = a ，+ 皿一a ，皿( 1 - 3 ) n o r 。( 一，b ) = 1 。爿，一或+ a ，b ，l n o t ( 一) = l 一一， 其中，和丑，分别表示将波形4 和b 延迟r 个时间单位。 定义1 - 4 对任何波形多项式x ( o ，x 在t 处的差分定义为 x ( f ) 2 x ( t + ) 一z ( r )( 1 4 ) 其中x ( t + ) = 鲰x ( t + j ) 表示鼻在t 的右极限。 ；万 定义1 - 5 若在区间t = ( t 1 ，