分布式环境下的图划分算法研究
发布时间：2021-07-23 16:45
自20世纪80年代开始,复杂系统的研究逐渐兴起,它被认为是解决各个领域研究面临的困难的一个重要突破点。而复杂网络是研究复杂系统的一个重要工具,如物流运输、道路规划、社交网络、生物研究等问题在研究的过程中,都可以抽象成由边和顶点组成的复杂网络,借助于复杂网络的相关技术对其进行研究。但系统中基本单元常常达到成千上万甚至是数以亿计,这就使得复杂网络的研究不得不借助于高效的计算工具来解决实时的、规模足够大的计算问题。分布式计算技术是现在最成熟、应用最广、最可行的计算加速技术之一。因此研究复杂网络的分布式计算技术具有十分重要的意义。在做分布式计算之前,需要将原始复杂网络划分成若干个子网络,保证各个子网络规模相对均衡和网络间的通信开销最小化是分布式计算性能好坏的关键。图划分技术就是解决这一问题的有效手段。图划分算法按照划分方式的不同,可以分为点划分算法和边划分算法。数据量的快速增长对图划分算法的划分质量和划分效率提出了新的要求。本文主要工作体现在以下方面:（1）针对当前点划分算法划分质量较低的问题,本文提出了基于滑动窗口的流式图划分模型（Graph Win）,该模型通过引入滑动窗口机制,根据当前划...
【文章来源】：重庆大学重庆市 211工程院校 985工程院校 教育部直属院校
【文章页数】：58 页
【学位级别】：硕士
【部分图文】：
图1.1分布式环境下的图划分算法研究背景Fig.1.1Streamingpartitioningmodel
结果割边率比较大。Grid算法[17]、DBH算法[18]、HDRF算法[19]都属于此类算法。②当前边划分算法仍存在效率低的问题。边划分算法虽然使用到图数据的其他局部信息，能够获得较好的划分结果，但该类算法由于使用启发式算法在全局图数据上寻找较优划分方案，计算时间复杂度比较大。例如，使用Metis算法对超过14亿条边的Twitter数据集做划分时，划分后的结果割边率为35.96%，但划分时间却高达8.5小时[23]，这在许多要求实时响应的应用场景下是无法容忍的。所以如何提高边划分算法的划分效率是当前亟待解决的问题。图1.2各类算法在划分质量和分区划分上的对比Fig.1.2Comparisonofvariousalgorithmsinpartitionqualityandpartitiontime1.4本文的研究内容本文对复杂网络划分做了研究，首先调研了当前已有的图划分算法，并分析了这些算法的优缺点，其次针对现有算法存在的不足，提出了基于滑动窗口的流式图划分模型（GraphWin）和基于GPU加速的图划分模型（GraphGPU），并结合已有的图划分算法对两个模型分别做了对比试验。本文具体研究内容如下：①研究了图划分算法的发展历史，分析了图划分算法中的核心概念。之后研究了图划分的几种常用算法，包括传统的静态图划分算法和流式图划分算法。针对点划分算法和边划分算法存在的问题，本文分别提出了基于滑动窗口的流式图
重庆大学硕士学位论文2图划分算法的相关研究82图划分算法的相关研究图划分是图论中经典的问题之一，它在多个领域中有着广泛的应用，例如并行计算[24]、复杂网络[25-31]、道路规划[32-35]、图像分割[36-38]、超大规模集成电路设计[39-42]等。现实中的很多问题可以抽象为图划分问题，图划分可以将原始问题分解成多个小问题，再对每个小问题分别求解，从而能够进一步提高处理效率。本章首先给出了图划分的定义，之后详细介绍了经典的图划分算法和分布式计算平台。2.1图划分定义定义（割边）：给定两个分区Pi和Pj，其中i≠j。如果这两个分区中的任意两点u和v存在边，而称这条边为一条割边。{(,)|,,}ijedgeCuteuveEuPvP（2.1）定义（图划分）：给定图数据G=(V,E)和一个正整数k,V是图G的顶点集合，E是图G的边集合,k是分区个数。图划分问题就是将图数据G划分成k个互不相交的集合P={P1,…Pk}，每个集合称为一个分区，同时图划分还需要满足两个重要原则:①负载均衡。尽量使划分后各分区的顶点数目大致相同，避免因任务分配不均造成资源浪费，即使得：||1,...,iVVikk（2.2）②割边数尽可能校分区间的割边数量直接影响通信开销，因为分区与分区之间的通信开销完全取决于网络，而且比分区内的通信代价高，所以为了减少总体的通信开销，需要优化割边数量，关于割边数的优化目标如下：1,0((,))nijMininizeedgeCutij（2.3）图2.1基于edge-cut划分问题示例Fig.2.1Anexampleofpartitioningproblembasedonedge-cut
【参考文献】：
期刊论文
[1]BHP:面向BSP模型的负载均衡Hash图数据划分[J]. 周爽,鲍玉斌,王志刚,冷芳玲,于戈,邓超,郭磊涛. 计算机科学与探索. 2014(01)
本文编号：3299662
【文章来源】：重庆大学重庆市 211工程院校 985工程院校 教育部直属院校
【文章页数】：58 页
【学位级别】：硕士
【部分图文】：
图1.1分布式环境下的图划分算法研究背景Fig.1.1Streamingpartitioningmodel
结果割边率比较大。Grid算法[17]、DBH算法[18]、HDRF算法[19]都属于此类算法。②当前边划分算法仍存在效率低的问题。边划分算法虽然使用到图数据的其他局部信息，能够获得较好的划分结果，但该类算法由于使用启发式算法在全局图数据上寻找较优划分方案，计算时间复杂度比较大。例如，使用Metis算法对超过14亿条边的Twitter数据集做划分时，划分后的结果割边率为35.96%，但划分时间却高达8.5小时[23]，这在许多要求实时响应的应用场景下是无法容忍的。所以如何提高边划分算法的划分效率是当前亟待解决的问题。图1.2各类算法在划分质量和分区划分上的对比Fig.1.2Comparisonofvariousalgorithmsinpartitionqualityandpartitiontime1.4本文的研究内容本文对复杂网络划分做了研究，首先调研了当前已有的图划分算法，并分析了这些算法的优缺点，其次针对现有算法存在的不足，提出了基于滑动窗口的流式图划分模型（GraphWin）和基于GPU加速的图划分模型（GraphGPU），并结合已有的图划分算法对两个模型分别做了对比试验。本文具体研究内容如下：①研究了图划分算法的发展历史，分析了图划分算法中的核心概念。之后研究了图划分的几种常用算法，包括传统的静态图划分算法和流式图划分算法。针对点划分算法和边划分算法存在的问题，本文分别提出了基于滑动窗口的流式图
重庆大学硕士学位论文2图划分算法的相关研究82图划分算法的相关研究图划分是图论中经典的问题之一，它在多个领域中有着广泛的应用，例如并行计算[24]、复杂网络[25-31]、道路规划[32-35]、图像分割[36-38]、超大规模集成电路设计[39-42]等。现实中的很多问题可以抽象为图划分问题，图划分可以将原始问题分解成多个小问题，再对每个小问题分别求解，从而能够进一步提高处理效率。本章首先给出了图划分的定义，之后详细介绍了经典的图划分算法和分布式计算平台。2.1图划分定义定义（割边）：给定两个分区Pi和Pj，其中i≠j。如果这两个分区中的任意两点u和v存在边，而称这条边为一条割边。{(,)|,,}ijedgeCuteuveEuPvP（2.1）定义（图划分）：给定图数据G=(V,E)和一个正整数k,V是图G的顶点集合，E是图G的边集合,k是分区个数。图划分问题就是将图数据G划分成k个互不相交的集合P={P1,…Pk}，每个集合称为一个分区，同时图划分还需要满足两个重要原则:①负载均衡。尽量使划分后各分区的顶点数目大致相同，避免因任务分配不均造成资源浪费，即使得：||1,...,iVVikk（2.2）②割边数尽可能校分区间的割边数量直接影响通信开销，因为分区与分区之间的通信开销完全取决于网络，而且比分区内的通信代价高，所以为了减少总体的通信开销，需要优化割边数量，关于割边数的优化目标如下：1,0((,))nijMininizeedgeCutij（2.3）图2.1基于edge-cut划分问题示例Fig.2.1Anexampleofpartitioningproblembasedonedge-cut
【参考文献】：
期刊论文
[1]BHP:面向BSP模型的负载均衡Hash图数据划分[J]. 周爽,鲍玉斌,王志刚,冷芳玲,于戈,邓超,郭磊涛. 计算机科学与探索. 2014(01)
本文编号：3299662
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3299662.html
