VLSI的高层次综合方法研究

论文摘要

芯片设计的高速化和复杂化对VLSI基础理论和设计方法提出了新的挑战。以超深亚微米和纳米工艺及IP核重用为基础的系统芯片是VLSI的发展趋势。传统的设计方法已经难以应付，出现了许多新的设计技术，如有效的高层次综合技术、验证技术及纳米工艺带来的一系列关键技术等。高层次综合是连接系统行为和结构之间的纽带，它能够缩短设计、布局和验证的时间。高层次综合阶段对电路功耗有巨大的优化空间，而物理设计阶段的功耗优化空间则急剧减少。本文就高层次综合中的调度、分配和多电压低功耗设计等问题展开研究，主要工作如下：1)提出了基于遗传算法与蚂蚁算法相融合的时间约束和资源约束下的高层次调度方法。在充分研究遗传算法和蚂蚁算法独立解决约束条件下的高层次调度问题的基础上，提出了遗传算法的编码方案、交叉算子、变异算子和评估函数及蚂蚁算法的信息素更新规则，并讨论了两个算法之间的动态切换条件。当遗传算法的子代进化率低于事先设定的最小子代进化率或超过最大迭代次数时，结束遗传算法，切换到蚂蚁算法，并由遗传算法得到的优化解产生蚂蚁算法的初始信息素分布。这样避免了蚂蚁算法在初期由于信息素匮乏而做的大量盲目搜索，提高了算法的效率。实验结果表明，与遗传算法和蚂蚁算法相比，本文资源约束的调度方法能明显减少调度长度，本文时间约束的调度方法能明显减少所用资源总数目。2)在充分研究复杂高层次数据流特性的基础上，提出一种适合高层次复杂数据流分解和设计空间搜索的多项式新模型K~*TDG。首先根据复杂数据流多项式中各参数之间的关系，对TDG中的边权值重新进行定义。然后讨论了K~*TDG模型的两种基本运算：加法和乘法。K~*TDG模型充分利用了TDG模型的思想，克服了TDG模型的缺点。在此基础上，借助于Maple中的Simplify函数和Factor函数，提出复杂数据流分解匹配算法。在此过程中定义关于面积和关键路径时延的代价函数，使上述过程始终向代价函数更优的方向进行。为了进一步降低算法复杂度，还提出了根据复杂元件多项式次数进行分组的策略，使每次搜索时的空间由整个设计空间变成与K~*TDG中分支次数相等的元件组成的局部空间。实验结果表明，在保持面积和延迟近优的前提下，本文方法能明显缩小设计空间。3)提出了基于网络流的多电压高层次低功耗设计方法。定义了一种新的系统功耗模型，同时考虑了功能单元功耗、互连功耗和电压转换功耗。首先进行单电压高层次综合，然后迭代地对单电压高层次综合结果进行局部多电压调度和分配调整。只有当某个操作与其前驱节点或后继节点有分配到同一电压簇器件的可能时，才执行该调整。提取每次迭代时需要调整的网络流子图，对该子图运行最小费用最大流增量算法。该方法充分利用前面迭代中得到的优化解，避免了对整个网络流的重复计算，节省了大量时间。最后，在讨论电路拓扑结构的基础上提出了一种门控填充值算法，能进一步减少电路设计中的伪开关跳变功耗。实验结果表明，本文方法对电路的互连功耗，电平转换功耗和总功耗均有明显的优化。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题的研究背景和意义
• 1.2 VLSI的发展
• 1.3 高层次综合概述
• 1.3.1 高层次综合的发展
• 1.3.2 高层次综合的作用
• 1.3.3 高层次综合的主要研究任务
• 1.3.4 高层次综合的准备工作
• 1.4 本文的研究内容
• 1.5 本文的组织结构
• 第2章 高层次综合综述
• 2.1 基本的调度和分配研究
• 2.1.1 调度方法研究
• 2.1.2 分配方法研究
• 2.1.3 国内的相关研究
• 2.2 基于遗传算法的调度和分配研究
• 2.3 高层次综合低功耗研究
• 2.3.1 高层次综合中动态功耗的优化
• 2.3.2 高层次综合中互连功耗的优化
• 2.3.3 其他相关的高层次低功耗研究
• 2.4 高层次综合中存在的问题和本文的研究方向
• 2.4.1 基于蚂蚁算法与遗传算法相融合的调度方法研究
• 2.4.2 提出多项式新模型和新分配搜索算法
• 2.4.3 高层次综合中的多电压低功耗研究
• 2.5 本文解决的关键问题
• 第3章 遗传算法与蚂蚁算法动态融合的高层次调度方法
• 3.1 引言
• 3.2 遗传算法与蚂蚁算法动态融合的基本思想
• 3.3 资源约束的调度算法
• 3.3.1 遗传算法设计
• 3.3.2 最大最小蚂蚁系统设计
• 3.4 时间约束调度算法
• 3.4.1 遗传算法设计
• 3.4.2 最大最小蚂蚁系统设计
• 3.5 遗传算法与蚂蚁算法的动态切换
• 3.5.1 遗传算法的结束条件
• 3.5.2 MMAS初始信息素的产生
• 3.6 实验结果与分析
• 3.7 本章小结
• 第4章 高层次分配模型及方法
• 4.1 引言
• 4.2 问题的提出
• 4.3 K*TDG模型
• 4.3.1 K*TDG模型的基本概念
• 4.3.2 K*TDG模型的基本运算
• 4.4 复杂数据流的分配算法
• 4.4.1 算法策略
• 4.4.2 分配算法
• 4.4.3 算法应用
• 4.5 表达式的相关操作技术
• 4.6 实验结果与分析
• 4.7 本章小结
• 第5章 多电压低功耗高层次综合方法
• 5.1 引言
• 5.2 相关知识
• 5.3 系统功耗模型
• 5.4 高层次低功耗网络流算法
• 5.4.1 网络流图的建立
• 5.4.2 最小费用最大流增量算法
• 5.4.3 基于网络流的高层次低功耗算法
• 5.5 SSA的缩减方法
• 5.5.1 输出网络拓扑结构
• 5.5.2 门控信号的填充值
• 5.6 实验结果与分析
• 5.7 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表的论文和取得的科研成果
• 致谢