基于M etis图划分算法的图平衡划分方法

摘要

随着集成电路技术的发展,具有低延迟、低功耗的片上网络(Network on Chip, No C)成为了SoC新的发展方向。FPGA原型验证成为了NoC研究的热点。大规模多核NoC无法在单个FPGA上实现验证,需要划分到多个FPGA。本论文主要针对多核NoC电路划分问题提出一种基于Metis图划分算法的多权值约束的划分方法,并完成算法的测试验证。
　　论文首先对划分的关键问题进行分析,将电路划分问题转化为图划分问题进行研究,分析比较了多种典型的划分算法,并总结了划分的基本设计方法。重点分析了Metis图划分算法的基本原理及工作流程,并提出了改进的多权值约束的划分算法。在划分前对多权值进行融合,并在划分后评估划分效果以改进融合参数,提高各个部分的平衡度。最后采用多个不同规模的多权值图对所提出算法进行了测试验证。仿真结果表明所提出算法能够有效地节省FPGA资源,降低成本。
　　本文提出了一种基于Metis算法的多权值图划分算法,在考虑到划分约束条件的情况下保证了一定的划分平衡度,对大规模NoC电路划分问题提供了一种新的解决方法。

目录

封面

声明

中文摘要

英文摘要

目录

第一章绪论

1 .1项目研究背景

1 .2国内外研宄现状

1 .3主要工作

1 .4文章结构

第二章划分关键问题分析

2 .1划分问题简介

2 .2划分算法分析

第三章算法分析及形式化描述

3.1 M e t i s划分算法

3 .2问题描述

3 .2问题形式化

第四章基于Met i s的多权值图划分算法

4 .1算法流程

4 .2将图又件转换成CSR格式

4 .3粗略估计限制条件

4 .3权值融合

4 .4约束验证

4 .5平衡度验证

第五章实验结果

5 .1实验平台

5 .2实验结果

第六章总结与展望

致谢

参考文献