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