高层次综合与布图规划相结合的算法与方法学研究

论文摘要

进入超深亚微米工艺以后,工艺技术的持续发展,给集成电路设计提出了巨大的挑战。电路规模的不断增大、日益凸显的物理寄生效应,以及传统的综合与物理布图设计阶段的分离,导致设计过程的反复迭代,带来严重的设计不收敛问题。本论文从集成方法学和优化算法的角度,对“高层次综合与布图规划相结合”研究热点问题进行了深入地研究,旨在探讨有效地解决“设计不收敛”问题的方法和手段。论文的主要贡献点如下:本文针对高层次综合和布图规划在设计流程上的重要作用,以及两个设计过程的NP-难问题的特点,对基于性能优化的“高层次综合与布图规划相结合”的集成策略和方法进行了研究。提出了“二阶段法”集成优化方法,通过将设计全流程分为“快速解空间扫描”和“详细优化”两个阶段,改变了传统的依据功能对设计阶段进行划分的方法,实现了高层次综合与布图规划的更深层次的结合。论文中给出了解空间特点和求解过程收敛性的理论分析,实现了其软件原型设计和核心部分开发。论文中对fir滤波器和ellipf电路进行了全流程实验,实验结果表明方法可以达到21.1%的电路性能改进。针对传统的设计流程中通过后处理来进行电路性能优化的方法,提出一种布图规划后高层次再分配的优化算法,通过将布图规划结果中的互连线长度模拟成作用在电路行为操作上的虚拟的“力”,来对电路的互连延迟进行均匀的优化。对比逻辑再综合和物理设计优化方法,这一方法可以做到针对不同的控制步进行互连线优化,其优化手段更加细致有效。论文中通过fir滤波器和实际的IDCT解码器对算法进行了验证,实验证明算法可以对电路达到8%的电路性能改进。提出一种新的布图规划后高层次再调度算法。该算法的特点在于不改变电路的互连线长度,而是通过修改电路调度结果来放松对互连延迟的约束,从而达到对同步时序电路的优化作用。这一算法同时也可以和高层次再分配有效配合,对电路互连延迟进行更进一步的优化操作。实验结果表明再调度算法和再分配算法联合可以达到平均11.5%的电路性能改进。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 研究背景以及问题的提出
• 1.1.1 研究背景
• 1.1.2 问题的提出
• 1.2 相关工作
• 1.2.1 传统高层次综合的主要任务
• 1.2.1.1 经典的调度算法
• 1.2.1.2 经典的分配（含绑定）算法
• 1.2.1.3 经典的控制电路生成算法
• 1.2.2 高层次综合和布图规划相结合的典型方法
• 1.2.2.1 用确定性算法结合高层次综合和布图规划
• 1.2.2.2 用非确定性算法结合高层次综合和布图规划
• 1.2.3 新近进展以及研究趋势
• 1.3 论文的主要工作及结构
• 第2高 层次综合和布图规划结合后的解空间分析
• 2.1 本章引述
• 2.2 传统的解空间搜索过程分析
• 2.3 “高层次综合与布图规划相结合”的解空间分析
• 2.3.1 “高层次综合与布图规划相结合”的搜索过程分析
• 2.3.2 输入的形式化
• 2.3.3 构造表示法
• 2.3.4 构造表示法小结
• 2.3.5 模拟退火优化算法的收敛性
• 2.4 解空间分析的应用意义
• 2.5 本章小结
• 第3章 高层次综合和布图规划相结合的体系结构
• 3.1 本章引述
• 3.2 二阶段法
• 3.2.1 二阶段法的基本思路
• 3.2.2 二阶段法的输入与解的表示
• 3.2.3 “高层次综合和布图规划相结合”的快速的解空间定位
• 3.3 基于二阶段法的系统设计
• 3.3.1 解决方案原型
• 3.3.2 系统模块划分
• 3.3.3 核心数据结构设计
• 3.3.3.1 将电路的高层次综合和布图规划表示为电路属性的填充
• 3.3.3.2 电路参数化功能单元库的设计
• 3.3.3.3 电路行为节点的设计
• 3.4 一个完整流程的实验数据
• 3.5 本章小结
• 第4章 布图规划后高层次再分配
• 4.1 本章引述
• 4.2 针对链式操作的布图规划后高层次再分配
• 4.2.1 局部关键路径的概念
• 4.2.2 布图规划后再分配的目标形式化
• 4.2.3 基于模拟力平衡的布图规划后再分配算法：FIDER
• 4.2.4 试验结果及分析
• 4.3 本章小结
• 第5章 考虑寄存器的布图规划后高层次再分配与再调度
• 5.1 本章引述
• 5.2 考虑寄存器的布图规划后高层次再分配与再调度
• 5.2.1 局部关键路径集合的概念
• 5.2.2 通过“操作延展”优化约束
• 5.2.3 通过“调度扰动”加大优化空间
• 5.2.4 再分配和再调度的配合
• 5.2.5 试验结果及分析
• 5.3 本章小结
• 第6章 结论
• 6.1 结论
• 6.2 存在的不足以及未来的工作
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果