分布式环境下的图划分算法研究

摘要

自20世纪80年代开始,复杂系统的研究逐渐兴起,它被认为是解决各个领域研究面临的困难的一个重要突破点.而复杂网络是研究复杂系统的一个重要工具,如物流运输、道路规划、社交网络、生物研究等问题在研究的过程中,都可以抽象成由边和顶点组成的复杂网络,借助于复杂网络的相关技术对其进行研究.但系统中基本单元常常达到成千上万甚至是数以亿计,这就使得复杂网络的研究不得不借助于高效的计算工具来解决实时的、规模足够大的计算问题.分布式计算技术是现在最成熟、应用最广、最可行的计算加速技术之一.因此研究复杂网络的分布式计算技术具有十分重要的意义.在做分布式计算之前,需要将原始复杂网络划分成若干个子网络,保证各个子网络规模相对均衡和网络间的通信开销最小化是分布式计算性能好坏的关键.图划分技术就是解决这一问题的有效手段.　　图划分算法按照划分方式的不同,可以分为点划分算法和边划分算法.数据量的快速增长对图划分算法的划分质量和划分效率提出了新的要求.本文主要工作体现在以下方面:　　①针对当前点划分算法划分质量较低的问题,本文提出了基于滑动窗口的流式图划分模型(GraphWin),该模型通过引入滑动窗口机制,根据当前划分质量和划分时间,动态调整每次划分时参考的信息量(顶点度信息和邻接信息),以达到允许损失一定划分效率的前提下尽可能提高划分质量的目的.此外,GraphWin模型的评分函数在传统流式图划分算法的基础上做了改进,它包括自适应均衡评分函数、度评分函数、聚类评分函数,综合考虑了分区均衡性、顶点度、分区聚类系数在图划分中起到的作用.实验结果表明,相较于其他算法,GraphWin模型在一定程度上能够有效降低平均复制度.　　②针对当前边划分算法划分效率较低的问题,本文提出了基于GPU加速的图划分模型(GraphGPU),GraphGPU 模型分为初始划分阶段和优化划分阶段:在初始阶段,使用 Boruvka 算法对原始图数据做初始聚类,将亲和度较大的顶点尽可能被划分到同一分区;在优化划分阶段,使用桶交换算法对初始划分结果做进一步的优化.因为 Boruvka 算法和桶交换算法都具有并行性,所以 GraphGPU 模型建立在CPU+GPU异构并行计算框架基础之上.实验结果表明,GraphGPU模型相较于现有成熟的图划分算法在提高划分效率的同时,也能够降低割边率.

目录

1 绪 论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 当前图划分算法存在的问题

1.4 本文的研究内容

1.5 论文组织结构

1.6 本章小结

2 图划分算法的相关研究

2.1 图划分定义

2.2 经典图划分算法

2.2.1 离线图划分算法

2.2.2 在线图划分算法

2.3 分布式图计算平台

2.3.1 Pregel图计算平台

2.3.2 GraphLab图计算平台

2.4 本章小结

3 基于滑动窗口的流式图划分模型

3.1 经典流式图划分模型

3.2 基于滑动窗口的流式图划分模型

3.2.1 自适应滑动窗口

3.2.2 评分函数

3.2.3 复杂度分析

3.3.1 实验设置

3.3.2 实验结果及分析

3.4 本章小结

4 基于GPU加速的图划分模型

4.1 CPU+GPU异构并行计算框架与CUDA编程模型

4.1.1 CPU+GPU异构并行计算框架

4.1.2 CUDA编程模型

4.2.1 Boruvka算法

4.2.2 Boruvka算法在GPU上的实现

4.3 基于GPU加速的图划分模型

4.3.1 初始划分

4.3.2 优化阶段

4.3.3 复杂度分析

4.4.1 实验设置

4.4.2 实验结果及分析

4.5 本章小结

5 工作总结及展望

5.1 本文工作总结

5.2 未来工作展望

参考文献

附录

A 作者在攻读学位期间成果目录

B 作者在攻读学位期间参加的项目

C. 学位论文数据集

致谢