EDA电子设计论文提纲
论文题目：基于斯坦纳树的VLSI避障布线算法研究
摘要：最小斯坦纳树（SMT,Steiner Minimum Tree）问题是超大规模集成电路（VLSI,Very Large-Scale Integration）物理设计中的一个基础研究问题。VLSI布线中的许多问题都可以转换为斯坦纳树构建问题。目前传统后端布线中的走线是水平或者竖直的,因此直角最小斯坦纳树（RSMT,Rectilinear Steiner Minimum Tree）问题是SMT子问题中的一个重要的研究问题。随着集成电路产业技术的发展,芯片后端设计的布局布线阶段需要考虑越来越多的障碍,例如IP块、电源网络、预布线网以及保障可制造性的一些障碍等等,这些障碍在构建RSMT时会阻碍一些边的形成。因此,研究在考虑障碍的情况下快速高效构建绕障直角最小斯坦纳树（OARSMT,Obstacle Avoiding Rectilinear Steiner Minimum Tree）的问题就尤为重要。确定性的算法可以保证构建的RSMT具有最小线长,但是其时间复杂度往往是指数级的,不适用于实际工程应用,近似算法无法保证解的最优性,但通常具有较高的计算效率,因此,近似算法是目前的研究热点。目前学术界已经有许多高效的不考虑障碍的RSMT算法,本文基于不考虑障碍的RSMT算法在考虑障碍的情况下借鉴当前主流方法研究了OARSMT的近似算法。本文首先分析了在不考虑障碍的斯坦纳树上实现绕障斯坦纳树的基本方案的优缺点,直接合法化的方案虽然简单快速但是解的质量差,分割法的方案在障碍数量较少的情况下解的质量较好,障碍过多的情况下运行求解效率和解的质量都会恶化。本文结合分割和合法化研究了单层绕障直角最小斯坦纳树（SL-OARSMT,Single-Layer OARSMT）构建算法,SL-OARSMT问题中障碍和线网的所有端点都在一个布线平面。为了划分原始线网,首先构造绕障生成图（OASG,Obstacle-Avoiding Spanning Graph）,再从绕障生成图中提取绕障生成树,接着将绕障生成树转换为Pin生成树,依据Pin生成树将原始线网分割为若干子线网;然后,对各子线网使用无障碍RSMT算法构建RSMT并合法化生成合法初始解;最后,本文提出了基于“边链”的粗粒度和细粒度两阶段优化方法,在粗粒度优化阶段,从全局角度进行优化,细粒度优化阶段,从局部角度进行优化,两阶段的优化会在初始解的基础上进一步引入斯坦纳点减小总线长。在SL-OARSMT的研究基础上,本文研究了多层绕障直角最小斯坦纳树（ML-OARSMT,Multi-Layer OARSMT）构建算法,ML-OARSMT问题中障碍和线网的端点可以分布在不同的布线层。首先通过层内中继点和层间通孔插入构建多层绕障生成图（ML-OASG,Multi-Layer-OASG）,然后在ML-OASG中提取多层绕障最小斯坦纳树（ML-OASMT,Multi-Layer Obstacle-Avoiding Steiner Minimum Tree）,最后对ML-OASMT直角化得到ML-OARSMT。本文使用IND1～IND5,RT01～RT05和RC01～RC12三组测例测试了本文的SL-OARSMT构建算法,结果显示本文的SL-OARSMT算法较基于连接图的方法、基于迷宫布线的方法、基于斯坦纳点的方法等总线长有约1%～5%的减小,且所有测例都能在1s内完成。同时,本文自建测例ML01～ML03测试了本文的ML-OARSMT算法,结果显示本文的ML-OARSMT算法是有效的。
关键词：斯坦纳树;绕障;布线;超大规模集成电路（VLSI）;电子设计自动化（EDA）
学科专业：集成电路系统设计
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
1.1 研究背景及意义
1.2 国内外研究现状
1.2.1 VLSI布线算法研究现状
1.2.2 最小斯坦纳树(SMT)问题研究现状
1.2.3 绕障斯坦纳树(OASMT)问题研究现状
1.3 本文内容及结构安排
第二章 斯坦纳树在VLSI布线中的应用及FLUTE基本原理
2.1 斯坦纳树在VLSI布线中的应用
2.2 基于查找表的无障碍直角最小斯坦纳树构建算法FLUTE
2.2.1 Hanan网格和线网的拓扑序列
2.2.2 FLUTE对9 pin及以下线网的处理
2.2.3 FLUTE对9 pin以上线网的处理
2.3 绕障斯坦纳树问题中应用无障碍斯坦纳树的难点分析
2.4 本章小结
第三章 单层绕障直角最小斯坦纳树(SL-OARSMT)研究
3.1 SL-OARSMT问题中的基本概念定义
3.2 SL-OARSMT构建算法
3.2.1 SL-OARSMT设计思路和流程框架
3.2.2 绕障生成图(OASG)构建
3.2.3 多端生成树(MTST)构建
3.2.4 pin生成树(PST)构建
3.2.5 单层绕障直角最小斯坦纳树(SL-OARSMT)构建
3.2.6 基于“边链”的粗粒度优化
3.2.7 基于“边链”的细粒度优化
3.3 SL-OARSMT时间复杂度分析
3.4 本章小结
第四章 多层绕障直角最小斯坦纳树(ML-OARSMT)研究
4.1 ML-OARSMT问题中的基本概念定义
4.2 ML-OARSMT构建算法
4.2.1 ML-OARSMT设计思路和流程框架
4.2.2 多层绕障生成图(ML-OASG)构建
4.2.3 多层多端生成树(ML-MTST)构建
4.2.4 多层绕障直角最小斯坦纳树(ML-OARSMT)构建
4.3 ML-OARSMT时间复杂度分析
4.4 本章小结
第五章 SL-OARSMT和 ML-OARSMT算法实现和验证
5.1 软件架构设计
5.2 结构体定义
5.3 数据结构的设计实现
5.3.1 障碍树(Obstacle-Tree)
5.3.2 线段推移树(Move Seg-Tree)
5.3.3 绕障生成图引擎(OASG-Engine)数据结构设计
5.3.4 图的存储
5.4 基于Python的结果验证和可视化
5.5 实验环境
5.6 SL-OARSMT结果分析
5.7 ML-OARSMT结果分析
5.8 本章小节
第六章 总结与展望
6.1 论文总结
6.2 工作展望
参考文献
致谢