超大规模集成电路的平面布图规划算法研究

论文摘要

随着超大规模集成电路的飞速发展，越来越多的模块被集成到同一块芯片上，基于分级的设计流程已成为必然趋势，因此平面布图规划越来越重要。基于这样的原因，本文深入探讨了平面布图规划的各种表示方法，主要研究了传统的平面布图规划问题和新约束条件下的平面布图规划问题。在传统的平面布图规划领域的研究中，提出基于权重的平面布图规划算法和基于线性规划的软模块调整方法。在考虑各种新约束的平面布图规划算法中，提出多时钟系统的平面布图规划算法和考虑电压降的平面布图规划算法。在基于权重的平面布图规划算法研究中，针对各个模块的面积以及长边长度的不同提出权重的概念，并在此基础上提出基于权重的布图规划算法，该算法根据各个模块权重的不同在优化过程中以不同概率选择相应的模块，克服了原有算法以相同的概率选择各个模块的缺点，达到了更好的布图规划效果。针对软模块的调整问题，本文分析了基于最优化求解超大规模集成电路平面布图规划的方法，对目标函数中的芯片面积本文提出通过估计芯片的长宽比对目标函数进行线性化。此外本文提出利用分段线性的方法对模块面积约束条件线性化，保证了解空间的可行性。实验结果表明使用本文提出的线性规划模型在保证了解空间可行性的同时达到了良好的布图规划效果。针对多时钟系统的平面布图规划，本文给出了容许的多时钟系统平面布图的定义以及相应的定理和证明，并基于序列对表示法和模拟退火算法提出了多时钟系统平面布图规划算法，对软模块的优化采用了线性规划的方法。本文提出算法在不增加时间复杂度的前提下，根据多时钟系统的特点大大减小了解空间。实验结果表明本文提出的算法对多时钟域平面布图规划有良好效果。随着集成电路工艺发展，工作电压降低，功耗密度增大，电源网络电压降的问题将越发突出。本文提出在平面布图规划阶段考虑电压降约束，在物理设计初期解决电压降问题，从而加快了物理设计收敛。首先提出了一个快速而满足一定精度的量化电压降的模型，然后基于模拟退火算法和序列对表示法提出考虑电压降的平面布图算法。对软模块的优化采用了线性规划的方法。实验结果表明，本算法在达到良好的平面布图规划效果的同时，有效地降低芯片的平均电压降以及最大电压降。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 超大规模集成电路平面布图规划研究的意义及现状
• 1.2 研究动机
• 1.3 主要工作及创新
• 1.4 论文的组织结构
• 第二章 超大规模集成电路平面布图的分类及表示方法
• 2.1 可二分平面布图的表示方法[Wong86]
• 2.1.1 NPE（Normalized Polish Expression）的定义
• 2.1.2 基于NPE的平面布图规划算法
• 2.1.3 对NPE表示法的综合评价
• 1]'>2.2 GPE（Generalized Polish Expression）表示法[Lin02₁]
• 2.2.1 GPE的定义
• 2.2.2 基于GPE表示的平面布图规划算法
• 2.2.3 GPE表示法的综合评价
• 2.3 序列对（Sequence Pair）表示法[Murata95][Murata96]
• 2.3.1 从平面布图到序列对
• 2.3.2 从序列对到平面布图
• 2.3.3 基于序列对的平面布图规划算法
• 2.3.4 序列对的综合评价
• 1]'>2.4 BSG（Bounded-Sliceline-Grid）表示法[Nakatake96][Xu05₁]
• 2.5 TCG（Transitive Closure Graph）表示法[Lin01]
• 2.5.1 平面布图的TCG表示
• 2.5.2 从TCG到平面布图
• 2.5.3 基于TCG的平面布图规划算法
• 2.5.4 TCG的综合评价
• 2.6 改进的TCG表示法——TCG-S[Lin04]
• 2.6.1 从平面布图到TCG-S
• 2.6.2 从TCG-S到平面布图
• 2.6.3 基于TCG-S平面布图规划算法
• 2.6.4 TCG-S的综合评价
• 2.7 O-tree表示法[Guo99][Guo01]
• 2.7.1 O-tree的定义
• 2.7.2 O-tree的编码
• 2.7.3 基于O-tree的平面布图算法
• 2.7.4 O-tree的综合分析
• *-tree表示法[Chang00][Lee03]'>2.8 B^*-tree表示法[Chang00][Lee03]
• *-tree的定义'>2.8.1 B^*-tree的定义
• *-tree的平面布图算法'>2.8.2 基于B^*-tree的平面布图算法
• *-tree的综合分析'>2.8.3 B^*-tree的综合分析
• 2.9 角模块序列（Corner Block List）表示法[Hong00]][Hong02]
• 2.9.1 角模块序列的相关定义
• 2.9.2 从平面布图到角模块序列
• 2.9.3 从角模块序列到平面布图
• 2.9.4 角模块序列（Corner Block List）表示法的综合分析
• 2.10 TBT（Twin Binary Tree）表示法[Yao01]
• 2.10.1 从马赛克平面布图到TBT
• 2.10.2 从Twin Binary Tree到马赛克平面布图
• 2.10.3 基于Twin Binary Tree的平面布图规划算法
• 2.10.4 Twin Binary Tree的综合评价
• 2.11 对各种表示方法的比较
• 第三章 基于权重的超大规模集成电路平面布图规划方法
• 3.1 基于最小自由度的平面布图规划方法[Dong01]
• 3.2 基于权重的布图规划算法
• 3.2.1 单个模块权重的定义
• 3.2.2 基于权重的平面布图规划算法
• 3.2.3 复杂度分析
• 3.2.4 基于权重的平面布图算法的实验结果
• 第四章 对软模块的优化
• 4.1 使用构造法对软模块进行优化
• 4.1.1 确定性算法
• 4.1.2 随机优化算法
• 4.2 基于最优化方法的软模块调整方法建模
• 4.3 基于凸规划的软模块调整方法
• 4.4 基于线性规划的软模块调整方法
• 4.4.2 约束不等式的线性化
• 4.4.3 近似后的的线性规划模型
• 4.4.4 基于线性规划的平面布图实验结果
• 4.4.5 减少线性规划的变量个数
• 4.5 总结
• 第五章 多时钟域系统的平面布图规划
• 5.1 多时钟系统的特点
• 5.2 多时钟系统平面布图规划的问题描述
• 5.3 多时钟系统平面布图规划算法
• 5.4 软模块的调整
• 5.5 解空间分析
• 5.6 实验结果
• 5.7 结论
• 第六章 考虑电压降的平面布图规划
• 6.1 电压降问题的出现
• 6.2 电压降与距离的关系
• 6.3 各模块电压降的权重
• 6.4 退火过程中的选择策略
• 6.5 目标函数
• 6.6 对软模块的调整
• 6.7 实验结果
• 6.8 本章小结
• 第七章 平面布图规划的总结与展望
• 7.1 本文工作的总结
• 7.2 对未来工作的展望
• 攻读博士期间撰写的论文及申请的专利
• 致谢