芯片级多层布线关键技术研究

论文摘要

布线系统分成两步:总体布线和详细布线。为了降低问题复杂度,传统布线通常采用基于均匀网格图的有网格布线。但本质上来讲,布线资源是一个连续区域,布线应该是可采用变线宽、变线间距的无网格布线。因此,随着计算机硬件计算能力的不断提高,国内外对无网格布线的研究越来越多。 本论文在对国内外有关无网格布线最新技术以及大规模布线问题中的各关键布线技术进行深入研究和深刻总结的基础上,针对性能驱动的芯片级多层布线流程,对总体布线、无网格详细布线等关键技术进行了深入研究,提出了时延和可制造性等多方面性能优化的一系列有效的布线算法。同时我们也对作为总体布线和详细布线桥梁的过点分配方法进行了初步研究。 针对现有无网格布线算法以布通率为主要目标,而很少考虑时延等性能优化的现状,本论文提出了一个时延驱动的多层总体布线算法。算法采用一种多层次的“V”字形工作流程,分粗化和细化两步完成布线。粗化阶段,采用Top—Down的方式逐级缩小问题规模,直到到达能够处理的层次;细化阶段,采用Down—Top的方式逐渐细化布线解,当重新到达最顶层,总体布线解确定。在粗化阶段的最粗层,针对大线网布线,专门提出了一个满足时延约束的多线网布线算法。该算法通过引入软边和移动斯坦纳点概念,来推迟精确走线的确定时机,以避免过早固定走线带来的盲目性,为布线提供更加全局化的考虑和极大的布线灵活性。 针对多层无网格区域布线的特性,需要一个新的过点分配算法CPA,以满足噪声约束,最小化通孔数。本论文对过点分配算法进行了初步研究:首先根据障碍物信息将小方块边界分解成多个区段,再分两步解CPA问题:粗略过点分配CCPA和精细过点分配RCPA。在CCPA阶段,根据噪声约束计算每个过点的安全线间距并将其分配到一个区段。CCPA算法采用有效的图布线算法,以最小化通孔数并确保没有区段溢出为目标;在RCPA阶段,为每个过点确定精确的位置,使其满足噪声约束,并使同一线网的过点对对齐数最大化。 详细布线阶段,本论文提出了一种基于非均匀网格图的多层无网格区域布线算法。算法首先通过一个考虑时延性能的最小化半径和费用的生成树算法MCSTMR将待布多端线网进行解耦,形成两端线网集合。然后通过一种自适应迭代策略,将多层布线转化为H-V布线层对序列来处理。当处理单个H-V布线层对时,根据当前处理的布线层对的障碍物集合,形成非均匀网格图,为迷宫布线建立基础图模型。在非均匀网格图上,利用改进的迷宫布线算法顺序处理两端线网集合,获得详细布线解。针对布线无网格特性,论文主要改进了迷宫算法的搜索策略,并通过二维区间树这一特殊的数据结构来管理障碍物,以加速迷宫算法。

论文目录

• 第一章 绪论
• 1.1 研究意义
• 1.2 研究背景
• 1.2.1 VLSI版图设计流程
• 1.2.2 布图模式
• 1.2.3 布线技术
• 1.3 论文的研究内容与组织形式
• 第二章 性能驱动的多层布线技术综述
• 2.1 引言
• 2.2 传统布线技术
• 2.2.1 总体布线
• 2.2.1.1 基于通道的总体布线
• 2.2.1.2 基于区域的总体布线
• 2.2.1.3 总体布线算法
• 2.2.2 详细布线
• 2.3 多层无网格布线技术
• 2.3.1 面向通道的无网格布线方法
• 2.3.2 面向区域的无网格布线方法
• 2.4 性能驱动的多层布线算法
• 2.5 考虑可制造性的多层布线算法
• 第三章 基于Non-Hanan点的时延驱动单线网布线算法
• 3.1 引言
• 3.2 Elmore时延模型
• 3.3 SERT算法简述
• 3.4 基于Non-Hanan点的时延驱动单线网布线算法
• 3.4.1 问题建模
• 3.4.2 基于Non-Hanan点的TDSRA算法
• 3.4.3 TDSRA算法的绕障碍方法
• 3.5 本章小结
• 第四章 时延驱动的多层总体布线算法
• 4.1 引言
• 4.2 算法总体框架
• 4.3 粗化阶段
• 4.3.1 布线资源估计
• 4.3.2 改进的资源估计方法
• 4.4 满足时延约束的多线网布线算法
• 4.4.1 软边
• 4.4.2 算法框架
• 4.4.3 基于网络流的软边分配算法
• 4.4.3.1 建立初始网络流图模型
• 4.4.3.2 完善网络流图模型
• 4.4.3.3 算法伪码描述
• 4.4.3.4 在网络流算法中考虑
• 4.4.4 时延约束的拆线重布
• 4.5 细化阶段
• 4.5.1 考虑时延的布线拓扑构造
• 4.5.2 细化过程
• 4.6 时延驱动的多层总体布线算法伪码描述
• 4.7 实验结果
• 4.8 本章小结
• 第五章 考虑噪声约束的过点分配方法初步研究
• 5.1 引言
• 5.2 串扰噪声估计方法
• 5.3 噪声驱动的层分配
• 5.3.1 层分配策略
• 5.3.2 过点分配策略
• 5.4 过点分配（C PA）算法
• 5.4.1 边界分解
• 5.4.2 CCPA算法
• 5.4.2.1 CCPA算法图模型
• 5.4.2.2 单线网CCPA算法
• 5.4.2.3 多线网CCPA算法
• 5.4.3 RCPA算法
• 5.4.3.1 过点顺序和间距确定算法
• 5.4.3.2 对齐算法
• 5.5 本章小结
• 第六章 基于非均匀网格图的多层无网格区域布线算法
• 6.1 引言
• 6.2 算法总体框架
• 6.3 MCSTMR拆线网策略
• 6.4 自适应迭代策略
• 6.5 改进的迷宫布线算法
• 6.5.1 非均匀网格图模型
• 6.5.2 基于非均匀网格图的搜索过程
• 6.5.3 基于非均匀网格图的加速策略
• 6.5.3.1 改进的二叉区间树
• 6.5.3.2 二维二叉区间树
• 6.6 算法伪码描述
• 6.7 考虑OPC的迷宫布线算法
• 6.7.1 OPC基本概念
• 6.7.2 OPC费用计算
• 6.7.2.1 光学系统模型
• 6.7.2.2 OPC费用计算
• 6.7.3 OPC费用优化的迷宫布线
• 6.8 实验结果
• 6.9 本章小结
• 第七章 总结和展望
• 7.1 论文的主要工作
• 7.2 进一步的研究工作和设想
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢