超大规模集成电路中标准单元的布局优化方法

论文摘要

布局是超大规模集成电路物理设计中最重要的环节之一。随着集成电路设计复杂性的日益增加和深亚微米技术的迅速发展，布局问题已经引起了研究人员的广泛关注。由于布局问题是一个NP完全问题，许多现代的布局算法通常可以分为三个步骤：（1）全局布局，尽可能均匀地将芯片上的单元分开，这样会产生少许的重叠；（2）合法化，将芯片上的单元按行对齐，并且没有任何重叠；（3）详细布局，根据某些标准优化合法化后的布局，进一步改善布局的质量。通常，大量的电路上由几百万个标准单元组成，这些标准单元具有相同的高度、不同的宽度（反之亦然）。这些标准单元应该按行排列并且对齐，可以方便地提供电源供应。由于IP核和预置宏模块（如模拟电路、嵌入式内存）固定在芯片上不能与其他单元重叠，随着它们的复用，布局问题变得越来越难以解决。本文提出了一种基于线密度的布线驱动全局布局方法。高密度的拥塞区域可能导致布线的迂回和更差的布线线长，甚至降低布线工具的性能，产生不可布通的电路。为了解决上述问题，获得一个均匀可布通的全局布局，提出了一种布线驱动布局方法。它是基于两层框架的解析方法，采用LSE线长模型和贝尔型密度函数，集解析布局和两层框架为一体，通过一种线长估计策略影响整个全局布局流程，进而达到优化的目的。首先，通过一个有效的全局布局方法将结群安置在芯片区域上，使得结群移动到一个新的位置，待布局的单元位于相应的结群中心。然后，将单元安置在芯片区域上，进一步减少其中的重叠。在线长估计策略中，定义了一个线网的线密度为该线网中线面积和线网面积的比率与一个参数的积，这个参数与该线网中引脚的位置有关。此外，还分析了线网和方格之间重叠的几种情况，进而提出了重叠函数并对其进行平滑估计处理。经过大量的实验结果验证，该方法是可行、有效的。本文还提出了一种有效的标准单元电路布局合法化方法。在全局布局中，冗余的单元重叠对于布线的好坏具有直接的影响。为了解决上述问题，将提出的合法化方法分为了两个主要的阶段：根据某种标准对待布局的单元进行排序；逐个对单元进行合法化。在合法化中，我们引入了一个新的术语“碰撞”，用来移除单元之间的重叠，并且深入分析了“碰撞”如何实现一个更好的布局。此外，通过改进的Dijkstra算法将单元重新安置到合适的行上。大量的实验结果表明，该方法可以获得一个更好的布局质量。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
• 1.1 研究课题的学术背景及意义
• 1.2 国内外研究现状
• 1.2.1 全局布局
• 1.2.2 合法化
• 1.2.3 详细布局
• 1.3 研究课题的来源及目的
• 1.4 本文的主要研究工作及创新
• 第二章 布局理论基础
• 2.1 全局布局
• 2.1.1 线长模型
• 2.1.1.1 二次模型
• 2.1.1.2 Bound2Bound 模型
• 2.1.1.3 Lp-norm 模型
• 2.1.1.4 LSE 模型
• 2.1.1.5 CHKS 模型
• 2.1.2 布局算法分类
• 2.1.2.1 随机布局
• 2.1.2.2 最小割布局
• 2.1.2.3 解析布局
• 2.2 合法化
• 2.3 本章小结
• 第三章 一种基于线密度的布线驱动全局布局方法
• 3.1 引言
• 3.2 布局模型
• 3.2.1 线长模型
• 3.2.2 单元密度描述
• 3.2.3 问题描述
• 3.3 线长估计策略
• 3.3.1 线网的线密度
• 3.3.2 线网与方格之间的重叠
• 3.3.1.1 几个基本函数的平滑估计
• 3.3.1.2 重叠函数的平滑处理
• 3.3.3 线长估计函数的平滑估计
• 3.4 算法实现
• 3.5 实验结果与分析
• 3.6 本章小结
• 第四章 一种有效的标准单元电路布局合法化方法
• 4.1 引言
• 4.2 合法化方法
• 4.3 单元碰撞
• 4.3.1. 结群的定义
• 4.3.2. 结群碰撞
• 4.3.3. 边界处理方法
• 4.4 改进的 Dijkstra 算法实现
• 4.5 实验结果与分析
• 4.6 本章小结
• 结论
• 参考文献
• 致谢
• 个人简历
• 在学期间的研究成果及发表的学术论文