基于多水平方法的无向图剖分及其在VLSI设计中的应用研究

论文摘要

本文在多水平方法的基础上,研究了无向图剖分优化问题,并将其研究成果应用在VLSI设计中,提出并实现了“基于多水平方法的电路剖分系统”。本文主要的工作和创新点有以下四个方面:1.在多水平粗化阶段提出了一种基于核排序的重边匹配算法,给出了基于图压缩存储格式的算法实现细节。该算法借助图核的全局信息,改进以往仅利用结点度等局部信息进行匹配的粗化算法,在对原始图粗化过程中发挥结点核值导向性作用,克服以往只能选择随机匹配算法作为导向匹配算法的缺陷。本文还提出了基于核排序和基于度排序重边匹配的组合粗化策略,在发挥结点核值导向性作用的同时,又不致于过份强调而使粗化图违背结点核值大小均匀分布的原则。在基于ISPD98电路测试基准的评估中,相比无向图剖分软件MeTiS采用的随机匹配和基于度排序重边匹配的组合粗化策略,取得了一定性能的改进。2.在多水平初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法,给出了基于Lanczos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。该算法借助Laplacian矩阵的次小特征值对应的特征向量刻画了结点间相对距离基本思想,将基于非赋权无向图的Laplacian谱图论在图的剖分应用扩展到无向赋权图上,实现对最小图进行初始剖分。在基于ISPD98电路测试基准的评估中,该算法配合基于核排序和基于度排序的重边匹配的组合粗化策略,取得了进一步性能的改进。同时实验数据也反映了在最小图上的全局近似最优剖分可能是初始图的局部最优剖分,需要加强多水平优化阶段的迁移优化算法逃离局部最优的能力。3.在多水平优化阶段引入智能优化技术,分别提出了基于禁忌搜索的多水平迁移优化算法和基于群智能的多水平迁移优化算法。它们从不同的角度,采取各自的方式增强算法的逃离局部最优能力,从而在优化阶段找到初始图更优的剖分。在基于ISPD98电路测试基准的评估中,它们配合第2章和第3章提出的算法,更进一步地改进了多水平方法的性能。实验数据反映出,针对最小图上的全局最优剖分可能是初始图的局部最优剖分、粗化图上的全局最优剖分可能是细化图的局部最优剖分的情况,基于群智能的多水平迁移优化算法相比基于禁忌搜索的多水平迁移优化算具备更强的逃离局部最优的能力;基于蚁群的多水平迁移优化算法相比基于微粒群的多水平迁移优化算法,对收益值的启发信息更为有效地利用,取得最佳的性能改进。4.将基于多水平方法的无向图剖分研究成果应用在VLSI设计中,提出并实现了“基于多水平方法的电路剖分系统”。本文还给出了该系统的结构框架和流程,组成模块以及各个模块实现过程中的难点。该系统用于软硬件协同模拟验证系统的配置阶段,实现对大规模集成电路的剖分,保证剖分前后的电路功能等价、剖分后的电路子集所包含的元件数目大致相等以及电路子集之间的连线数据达到近似最小,最终得到以Verilog语言描述的电路剖分结果,可用于后续的软硬件协同模拟验证流程。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 无向图剖分优化问题的定义
• 1.1.1 无向图二剖分优化问题的定义
• 1.1.2 基于递归二分法的多路图剖分
• 1.2 无向图剖分优化问题的应用
• 1.2.1 在高性能科学模拟的应用
• 1.2.2 在数据挖掘中数据聚类的应用
• 1.2.3 在图像处理中图像分割的应用
• 1.3 无向图剖分优化问题的研究现状
• 1.3.1 迁移方法
• 1.3.2 几何方法
• 1.3.3 组合方法
• 1.4 基于多水平方法的无向图剖分研究现状
• 1.4.1 多水平粗化阶段
• 1.4.2 多水平初始剖分阶段
• 1.4.3 多水平优化阶段
• 1.4.4 多水平方法的可行性分析
• 1.5 本文研究工作概况
• 1.5.1 研究思路
• 1.5.2 内容安排
• 第二章 多水平粗化阶段基于核排序的重边匹配算法
• 2.1 图的核值的定义与扩展
• 2.2 基于核排序的重边匹配算法及实现
• 2.2.1 基于核排序的重边匹配算法的框架
• 2.2.2 基于核排序的重边匹配算法的实现
• 2.2.3 基于核排序的重边匹配算法的复杂度分析
• 2.3 实验对比
• 2.3.1 无向图剖分软件MeTiS介绍
• 2.3.2 电路测试基准ISPD98介绍及格式转换
• 2.3.3 实验设计
• 2.3.4 实验结果讨论
• 2.4 小结
• 第三章 多水平初始剖分阶段基于谱方法的无向赋权图剖分算法
• 3.1 谱图论及其在无向图剖分中的应用
• 3.2 基于谱方法的无向赋权图剖分算法及实现
• 3.2.1 基于谱方法的无向赋权图剖分算法的框架
• 3.2.2 基于谱方法的无向赋权图剖分算法的实现
• 3.2.3 基于谱方法的无向赋权图剖分算法的复杂度分析
• 3.3 实验对比
• 3.3.1 实验设计
• 3.3.2 实验结果讨论
• 3.4 小结
• 第四章 多水平优化阶段基于禁忌搜索的迁移优化算法
• 4.1 禁忌搜索
• 4.1.1 禁忌搜索的基本概念
• 4.1.2 简单禁忌搜索的算法流程
• 4.2 基于禁忌搜索的多水平迁移优化算法及实现
• 4.2.1 基于禁忌搜索的多水平迁移优化算法的框架
• 4.2.2 基于禁忌搜索的多水平迁移优化算法的实现
• 4.2.3 基于禁忌搜索的多水平迁移优化算法的复杂度分析
• 4.3 实验对比
• 4.3.1 实验一设计及结果讨论
• 4.3.2 实验二设计及结果讨论
• 4.4 小结
• 第五章 多水平优化阶段基于群智能的迁移优化算法
• 5.1 群智能
• 5.1.1 基本蚁群算法及其模型特征
• 5.1.2 基本微粒群算法及其模型特征
• 5.2 基于群智能的多水平迁移优化算法
• 5.2.1 基于蚁群的多水平迁移优化算法及实现
• 5.2.2 基于蚁群的多水平迁移优化算法的复杂度分析
• 5.2.3 基于微粒群的多水平迁移优化算法及实现
• 5.2.4 基于微粒群的多水平迁移优化算法的复杂度分析
• 5.3 实验对比
• 5.3.1 实验一设计及结果讨论
• 5.3.2 实验二设计及结果讨论
• 5.4 小结
• 第六章 基于多水平方法的电路剖分系统
• 6.1 MCP系统的结构框架和流程
• 6.1.1 MCP系统的结构框架
• 6.1.2 MCP系统的流程
• 6.2 MCP系统的实现
• 6.3 电路剖分问题的数学模型
• 6.4 电路剖分实验
• 6.4.1 八位串行加法电路剖分实验
• 6.4.2 CPU电路剖分实验
• 6.5 小结
• 第七章 总结与展望
• 7.1 总结
• 7.2 进一步的工作
• 参考文献
• 作者在攻读博士学位期间完成的学术论文
• 作者在攻读博士学位期间获得的研究成果
• 作者在攻读博士学位期间参与的项目
• 致谢