SoC平面布图规划算法的若干研究

论文摘要

深亚微米下的SoC物理设计面临着比以往更多的电路可靠性,性能,功耗,成品率以及设计成本等新问题。传统的物理设计流程显然已经无法满足设计需求,必须结合新出现的问题而加以改进。作为物理设计的第一阶段,布图规划在整个设计流程中占有重要地位。因此,如何形成一个好的布局,考虑后序步骤的实际需求如减少RC延迟,降低布线拥塞度,减少前后端迭代的次数,加快设计收敛进程等成为设计的重中之重。本文在探讨平面布图规划几种表示方法的基础上,研究了传统的平面布图规划问题,新约束条件下的平面布图规划问题以及基于平面布图规划的电源布线。在传统的平面布图规划问题研究中,提出了模拟退火的加速策略。在考虑各种新约束条件下的平面布图规划算法中,提出SoC约束的平面布图规划算法以及考虑模块电压降的平面布图规划算法。在基于平面布图规划的电源布线研究中,提出了一种快速分析电源网络的计算方法,并基于模块功耗设计出不均匀的电源网络。在模拟退火的加速策略研究中,针对领域构造对模拟退火算法的影响进行研究分析,并在此基础上根据布图规划问题的特性提出在模块操作中增加导向性策略来加速算法收敛的方法。与原模拟退火算法相比,可以减少30%以上的搜索时间,提高布图规划的效率。在SoC约束的平面布图规划算法研究中,以偏移度P判断B*-tree约束操作的执行,确保了任何两种允许布局之间都可以经过少的基本操作而相互转化,并通过模块操作选择策略得以实现。实验表明这种算法不仅简单有效,并且与在模拟退火中增加惩罚项函数的传统做法相比,减少了1.6%以上的面积增加。在考虑模块电压降的平面布图规划算法研究中,通过对电压降物理模型的分析,以及模块噪声容限对布图结果的影响,提出模拟退火中的电压降约束函数,并结合SoC约束,实现了一种低电压降的SoC布局。最后在基于布局的电源网络设计中,提出了一种快速分析电源网络的方法。通过对移除电源条前后电流路径的变化,得到不均匀电源网络的数学分析模型。与传统的分析算法相比,计算量大大降低,从而节约了电源网络设计时间,加快设计收敛。同时,利用该模型在低电压降的布局基础上设计出满足芯片功耗的不均匀的电源网络。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 集成电路的发展
• 1.2 平面布图规划的发展和趋势
• 1.3 论文组织结构
• 第二章 平面布图的表示方法
• 2.1 可二分平面布图表示方法
• 2.1.1 NPE定义
• 2.1.2 基于NPE的布图规划
• 2.1.3 NPE表示法小结
• 2.2 非可二分平面布图的表示方法
• 2.2.1 序列对表示方法
• 2.2.1.1 序列对定义
• 2.2.1.2 基于序列对的布图规划
• 2.2.1.3 序列对表示法小结
• *-tree表示方法'>2.2.2 B^*-tree表示方法
• *-tree定义'>2.2.2.1 B^*-tree定义
• *-tree的布图规划'>2.2.2.2 基于B^*-tree的布图规划
• *-tree表示法小结'>2.2.2.3 B^*-tree表示法小结
• 2.3 马赛克布图表示方法
• 2.3.1 角模块序列定义
• 2.3.2 基于角膜块序列的布图规划
• 2.3.3 角模块序列小结
• 2.4 平面布图表示法小结
• 第三章 模拟退火加速策略
• 3.1 模拟退火算法
• 3.2 算法分析与加速策略
• 3.2.1 基于领域构造的算法分析
• 3.2.2 基于领域构造的算法加速策略
• 3.3 加速模拟退火算法及布图规划
• 3.4 实验结果
• 3.5 小结
• 第四章 SoC平面布图规划算法
• 4.1 SoC约束
• 4.2 SoC约束实现
• 4.2.1 SoC约束操作
• 4.2.2 操作选择策略
• 4.3 实验结果
• 4.4 小结
• 第五章 考虑电压降的布图规划
• 5.1 电压降问题的出现
• 5.2 电压降目标函数
• 5.2.1 电压降的物理模型
• 5.2.2 电压降目标函数
• 5.3 模拟退火中的选择策略
• 5.4 实验结果
• 5.5 小结
• 第六章 基于布局的快速设计电源网络算法
• 6.1 电源网络设计问题的出现
• 6.2 低电压降布局
• 6.3 电源网络优化
• 6.3.1 构建均匀的电源网络
• 6.3.2 基于电流路径的模型
• 6.3.3 电源网络的优化
• 6.4 实验结果
• 6.5 小结
• 第七章 总结和展望
• 7.1 总结
• 7.2 未来展望
• 参考文献
• 攻读硕士期间撰写的论文及申请的专利
• 致谢