极大规模集成电路全局互连线设计与优化算法研究

摘要

伴随着集成电路工艺进入超深亚微米和纳米时代，不断增大的电路规模和日益凸显的互连线物理效应等问题，给集成电路设计自动化提出了巨大的挑战。集成电路设计自动化是一个发展变化快、学科交叉和算法密集型的领域，存在着大量的大规模数值方程求解和组合优化等问题，受到学术界和工业界的高度关注，互连线优化设计成为该领域研究的热点和前沿。本文以时钟网络、电源/地线网络和信号线网等三种全局互连线为背景，对互连线网分析和设计的方法和优化算法进行深入研究，旨在探讨以“互连线为中心”的集成电路设计优化方法和手段。 论文在广泛调研了现有的互连线优化算法的基础上，深入分析了时钟网络、电源／地线网络和信号线网等三种全局互连线优化问题及其理论基础，提出了相应的设计方法并实现了优化算法。研究了时钟网络可靠性设计问题，针对工艺变化对时钟线网性能带来的影响，以树型拓扑结构的时钟线网为例，探讨了抗工艺变化的时钟设计的优化算法；深入分析和研究了大规模供电网络的瞬态分析和优化问题，针对大规模网络带来的求解速度和精度问题，以链+网的拓扑结构为对象提出了快速的时域分析方法和高效的优化算法；对信号线网的串扰问题进行了研究，针对资源分配阶段解决串扰的多目标优化问题，提出在层分配、过点分配和轨道分配过程中减小串扰的综合资源分配算法，取得了以下创新性的成果： ●提出了抗工艺变化的带缓冲器插入的时钟网络设计和优化算法。针对时钟网络延迟和偏差易受工艺参数变化影响问题，论文从分析时钟树的特点入手，提出了时钟树对工艺参数变化的敏感性模型；在时钟树的构建过程中，采用偏差灵敏度指导下的时钟节点合并方法构造特殊的树型拓扑结构，有效地提高了时钟树抗工艺变化能力；通过对插入缓冲器数量和位置的规划进一步减小工艺参数变化对时钟偏差的影响，同时优化连线时延。实验结果表明，在时钟线长增加小于14％的情况下，违反偏差约束减小60～80％。 ●提出了层次式供电网络快速瞬态分析算法。针对大规模供电网络分析速度和精度问题，对标准单元布图模式中供电网络的链状(CHAIN)结构，采用无误差的等效电路方法将中间节点进行压缩，在求解压缩电路之后，恢复求解中间节点，从而大大提高了算法的分析速度；对供电网络的网状(MESH)结构，采用松弛策略进行电路划分，与已有的多网格方法不同，该方法不仅避免了稠密矩阵的引入，而且可以补偿由于电路划分引起的误差，同时避免了矩阵求逆运算，大大提高了求解速度并得到更为精确的结果。与商用软件SPICE相比，在精度不低于0.035％的情况下，速度提高两个数量级。 ●提出了基于电路划分和考虑漏电流的供电网络启发式优化算法。以大规模供电网络优化问题为背景，从降低供电网络优化问题复杂性入手，采用基于松弛策略和随机行走方法对电路进行划分，大大降低问题求解规模；采用启发式的算法求解去耦合电容的放置位置和大小，使优化效率大大提高。在建立了去耦合电容漏电流模型的基础上，采用线宽和添加去耦合电容结合的两步优化策略，有效地发挥了各自在消除供电网络噪声上的优势，使算法取得了比较好的综合优化效果。实验结果表明，与已发表的同类算法只能处理1K节点的网络相比，本算法可以处理11M节点的网络，且有更高的优化效率。 ●提出了减小串扰的启发式综合布线资源分配算法。针对互连线串扰带来的信号完整性问题，论文从布线资源分配的角度，探讨解决串扰影响的方法。算法将屏蔽插入与层分配、过点分配和轨道分配结合起来，使资源分配策略一致并提高分配质量；采取逐行(slice)处理的分解策略及屏蔽规划与详细分配的两阶段分而治之方法，有效地减小了问题的搜索空间；在详细分配中，采用动态优先队列策略，根据分配过程中资源占用情况和线段布线难度的变化，动态更新各线段的优先级，减小线段分配顺序对解的影响。提高了分配的成功率，并有效地减小串扰。实验结果表明，与已经发表的同类算法比较在分配成功率相当的情况下，减小串扰6～32倍。 本论文深入研究了集成电路设计中出现的工艺变化带来的可靠性设计问题、大规模电路分析建模、计算和优化问题以及串扰带来的信号完整性等新的问题，具有很强的针对性和代表性，可以作为其它以“互连线为中心”的集成电路设计优化算法的借鉴。

目录

文摘

英文文摘

中国科学技术大学学位论文相关声明

第一章引言

1.1 集成电路技术的发展和研究目标

1.1.1集成电路发展带来的挑战

1.1.2研究意义与研究目标

1.2 论文的贡献与组织

第二章基础知识

2.1 电源/地线网络模型

2.1.1线段的RLC模型

2.1.2电路功能模块的模型

2.1.3片上去耦合电容的模型

2.1.4供电网络的RLC模型

2.2 时钟网络模型

2.2.1 Elmore延迟模型

2.2.2缓冲器的RC网络模型

2.3 供电网络分析基础

2.4 供电网络噪声计算

2.5 电路灵敏度分析

第三章考虑工艺参数变化的时钟网络设计优化

3.1 引言

3.1.1优化目标

3.1.2前人工作

3.1.3研究动机与贡献

3.2 考虑工艺参数变化的时钟网络设计与优化算法

3.2.1安全时钟布线基本问题描述

3.2.2偏差灵敏度与分支敏感因子BSF

3.2.3抗工艺参数变化的时钟布线算法

3.3 实验结果

3.4 本章小结

第四章层次式电源/电线网络快速分析

4.1 引言

4.1.1研究目标

4.1.2前人工作

4.1.3研究动机与贡献

4.2 准确的电路功能模块吸纳电流模型

4.3 供电网络的约减

4.3.1电源/地线网络的链状模型

4.3.2链状电路的压缩

4.3.3算法复杂性分析

4.3.4实验结果

4.4 层次式的供电网络快速分析算法

4.4.1基于松弛补偿的电路划分

4.4.2层次式供电网络的分析算法

4.4.3实验结果

4.5 本章小结

第五章考虑漏电流的电源/地线网络优化

5.1 引言

5.1.1电源/地线网络优化基本问题描述

5.1.2优化目标

5.1.3前人工作

5.1.4研究动机与贡献

5.2 去耦合电容漏电流模型

5.3 考虑漏电流的电源/地线网络优化

5.3.1问题描述

5.3.2目标函数

5.3.3约束条件

5.3.4电路灵敏度分析

5.3.5优化算法

5.4 实验结果

5.5 本章小结

第六章考虑串扰的信号线网优化

6.1 引言

6.1.1优化目标

6.1.2前人工作

6.1.3研究动机与贡献

6.2 综合资源分配问题描述

6.2.1相关定义

6.2.2综合资源分配问题描述

6.2.3算法策略

6.3 综合资源分配中串扰的计算

6.3.1串扰的分类

6.3.2串扰的计算

6.4 考虑串扰的综合资源分配算法

6.4.1算法思路

6.4.2屏蔽规划和总体分配

6.4.3动态优先级队列和局部分配

6.5 实验结果

6.6本章小结

第七章总结与展望

7.1 全文总结

7.2 未来工作展望

参考文献

致谢

个人在学期间的研究成果及发表的论文