文档介绍：中国科学技术大学
博士学位论文
极大规模集成电路全局互连线设计与优化算法研究
姓名:蔡懿慈
申请学位级别:博士
专业:计算机应用
指导教师:熊焰
20070301
摘要伴随着集成电路工艺进入超深靶微米和纳米时代,不断增大的电路规模和日益凸显的互连线物理效应等问题,给集成电路设计自动化提出了巨大的挑战。集成电路设计自动化是一个发展变化快、学科交叉和算法密集型的领域,存在着大量的大规模数值方程求解和组合优化等问题,受到学术界和工业界的高度关注,互连线优化设计成为该领域研究的热点和前沿。本文以时钟网络、电源/地线网络和信号线网等三种全局互连线为背景,对互连线网分析和设计的方法和优化算法进行深入研究,旨在探讨以“互连线为中心”的集成电路设计优化方法和手段。论文在广泛调研了现有的互连线优化算法的基础上,深入分析了时钟网络、电源,地线网络和信号线网等三种全局互连线优化问题及其理论基础,提出了相应的设计方法并实现了优化算法。研究了时钟网络可靠性设计问题,针对工艺变化对时钟线网位能带来的影晌,以树型拓扑结构的时钟线网为铡,探讨了抗工艺变化的时钟设计的优化算法;深入分析和研究了大规模供电网络的瞬态分析和优化问题,针对大规模网络带来的求解速度和精度问题,以链耐仄私构为对象提出了快速的时域分析方法和高效的优化算法;对信号线网的串扰问题进行了研究,针对资源分配阶段解决串扰的多目标优化问题,提出在层分配、过点分配和轨道分配过程中减小串扰的综合资源分配算法,取得了以下创新性的成果:提出了抗工艺变化的带缓冲器插入的时钟网络设计和优化算法。针对时钟网络延迟和偏差易受工艺参数变化影响问题,论文从分析时钟树的特点入手,提出了时钟树对工艺参数变化的敏感性模型;在时钟树的构建过程中,采用偏差灵敏度指导下的时钟节点合并方法构造特殊的树型拓扑结构,有效地提高了时钟树抗工艺变化能力;通过对插入缓冲器数量和位置的规划进一步减小工艺参数变化对时钟偏差的影响,同时优化连线时延。实验结果表明,在时钟线长增加小于%的情况下,违反偏差约束减小~%。提出了层次式供电网络快速瞬态分析算法。针对大规模供电网络分析速度和精度问题,对标准单元布图模式中供电网络的链状峁梗捎梦尬差的等效电路方法将中间节点进行压缩,在求解压缩电路之后,恢复求解中间节点,从而大大提高了算法的分析速度;对供电网络的网状结构,采摘要·
的情况下,减小串扰以倍。用松弛策略进行电路划分,与已有的多网格方法不同,该方法不仅避免了稠密矩阵的引入,而且可以补偿由于电路划分引起的误差,同时避免了矩阵求逆运算,大大提高了求解速度并得到更为精确的结果。与商用软件啾龋精度不低于%的情况下,速度提高两个数量级。提出了基于电路划分和考虑漏电流的供电网络启发式优化算法。以大规模供电网络优化问题为背景,从降低供电网络优化问题复杂性入手,采用基于松弛策略和随机行走方法对电路进行划分,大大降低问题求解规模;采用启发式的算法求解去耦合电容的放置位置和大小,使优化效率大大提高。在建立了去耦合电容漏电流模型的基础上,,使算法取得了比较好的综合优化效果。实验结果表明,与已发表的同类算法只能处理节点的网络相比,本算法可以处理踅诘愕耐纾矣懈叩挠呕省提出了减小串扰的启发式综合布线资源分配算法。针对互连线串扰带来的信号完整性问题,论文从布线资源分配的角度,探讨解决串扰影响的方法。算法将屏蔽插入与层分配、过点分配和轨道分配结合起来,使资源分配策略一致并提商分配质量;采取逐行淼姆纸獠呗约捌帘喂婊胂晗阜峙涞牧浇段分而治之方法,有效地减小了问题的搜索空间;在详细分配中,采用动态优先队列策略,根据分配过程中资源占用情况和线段布线难度的变化,动态更新各线段的优先级,减小线段分配顺序对解的影响。提高了分配的成功率,并有效地减小串扰。实验结果表明,与已经发表的同类算法比较在分配成功率相当本论文深入研究了集成电路设计中出现的工艺变化带来的可靠性设计问题、大规模电路分析建模、计算和优化问题以及串扰带来的信号完整性等新的问题,具有很强的针对性和代表性,可以作为其它以“互连线为中心”的集成电路设计优化算法的借鉴。关键词:超大规模集成电路;全局互连线;时钟网络;电源/地线网络;信号线网;分析和优化摘要Ⅱ·
鸼豰鞠琺文珧醥鰋躺...膚矗∞—甌.,...琧
.%一%,瓺瑃,瓼Ⅳ.,.●.瓵阤篿瓺瓼.,
瞐慨甌懿商玳删餬鑑鷕.%.痝甌协伊砒,﹛琣甌..甇甌甀琤●..·痝/豻琩瑃瑃鏛鍿:
.珿..珻,甌篤,
一怕年丝匙巷囊中国科学技术大学学位论文相关声明本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果