超大规模集成电路详细布局算法研究

论文摘要

布局是超大规模集成电路物理设计中关键的一环。布局问题一般分为两个阶段：整体布局和详细布局,而合法化贯穿于整个布局问题之中。在过去的研究中,大多数仅仅关注于整体布局领域,并且出现了许多较为有效的优化算法,相较之下,对合法化和详细布局算法的研究则比较少。本文基于传统的布局算法流程,针对标准单元模式和混合模式电路的布局问题提出了一个完整的合法化和详细布局算法。在混合模式合法化算法中,本文针对约束图调整中出现的内存过大问题,采用深度优先搜索有效控制了初始图中边的数目。此外,我们采用了一种能产生最小移动的快速标准单元合法化算法。同时,我们提出了基于最优区域单元交换和基于Bin结构单元滑动两个阶段相结合的详细布局算法,它能通过对布图区域密度的调整来完善布局。最后,我们对ibm benchmark电路的数据进行了大量的仿真实验。实验结果表明,本文中的合法化算法能有效解决两种模式下模块的重叠问题,同时详细布局算法能进一步优化布局质量。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景与意义
• 1.2 研究现状与进展
• 1.3 论文的组织结构和本文的工作
• 第二章 超大规模集成电路布局问题
• 2.1 超大规模集成电路设计流程
• 2.1.1 设计流程概述
• 2.1.2 布局问题在集成电路物理设计中的意义
• 2.2 布局问题的基本概念和问题描述
• 2.2.1 布局问题描述
• 2.2.2 布局中的线长估计问题
• 2.2.3 解决布局问题的方法
• 2.3 布局问题的数学基础与数据结构
• 2.3.1 基本术语
• 2.3.2 解决布局问题的基本算法
• 2.3.3 布局问题中涉及的基本数据结构
• 2.4 本章小结
• 第三章 超大规模集成电路合法化和详细布局算法
• 3.1 合法化和详细布局算法概述
• 3.2 标准单元模式下的合法化算法
• 3.3 混合模式下的合法化算法
• 3.3.1 宏模块的合法化
• 3.3.2 标准单元的合法化
• 3.4 标准单元模式下的详细布局算法
• 3.4.1 单元交换算法
• 3.4.2 基于Bin结构的单元滑动
• 3.5 本章小结
• 第四章 仿真实验结果与分析
• 4.1 实验数据和运行环境
• 4.2 仿真实验结果与讨论
• 第五章 总结与展望
• 致谢
• 参考文献
• 研究成果