HPGraph:高性能图形分析与生产力在GPU上

文摘

日益增长的使用图在许多领域引发了一场广泛的兴趣发展高级图像分析程序。现有GPU实现有限的性能与影响生产力。HPGraph,高性能bulk-synchronous图基于GPU的分析框架,提供一个抽象关注顶点程序映射到GPU上广义稀疏矩阵操作后台。HPGraph罢工之间的平衡性能和生产率提高了耦合高性能GPU计算原语和优化策略与高级编程模型为用户实现各种图形算法和相对较少的努力。我们评估的性能HPGraph四个图形原语(BFS SSSP, PageRank和TC)。我们的实验表明,HPGraph匹配甚至超过高性能GPU图形库的性能如MapGraph nvGraph, Gunrock。HPGraph也比先进的CPU运行速度显著提升图形库。

1。介绍

图计算已经成为分析关键数据在许多领域,如生物信息学、社交网络、网络分析、和交通工程。在过去的十年中,在处理大规模图,提出了各种并行图计算框架利用现代大规模并行处理器,尤其是图形处理单元(gpu)。gpu具有优秀的峰值吞吐量和能源效率(1)具有很强的计算性能和适当的优化。然而,不可预测的控制流和内存造成的分歧在gpu的不规则图形拓扑需要复杂的策略来确保效率,使一个有效的gpu上实现一个挑战。与图形查询越来越大,越来越复杂,必须为高级图像分析框架来帮助用户提取所需的信息以最少的编程工作。

为了消除高绩效和生产力之间的差距,我们建议HPGraph,高层在GPU并行图分析框架。关键抽象框架顶点程序映射到广义的稀疏矩阵向量乘法CUDA内核(SPMV)操作。与其他GPU图形计算模型,重点排序计算的步骤2),我们相反转换图遍历矩阵运算,这样我们可以专注于数据结构,提供高性能的操纵带来的优化的广义SPMV。此外,HPGraph封装复杂的编程和实现高生产率为用户通过隐藏底层的矩阵元素。用户提供有限的知识因此低级GPU的体系结构能够组装复杂的图形原语。

我们对这个领域的贡献如下:(1)我们提出一种有效的图形分析框架顶点程序映射到广义GPU上稀疏矩阵操作。这种抽象与抽象的透光GPU图形procecssing库,能够建立一个广泛的图形原语,同时提供高性能。(2)为用户HPGraph是富有成效的。我们隐藏的一些更令人讨厌的事实如何HPGraph真的完成工作,并提供了一套灵活的api来表达一些图形原语在较高的抽象层次。(3)HPGraph集成各种GPU-specific优化策略的数据结构,图遍历和内存访问到它的核心,进一步提高性能。在我们的实验中,我们的图形原语表现明显优于其他先进的CPU图表分析框架,实现相当甚至更高的性能和其他先进的GPU分析库。(4)我们提供一个详细的实验评估我们的图形原语包括比较几个先进的CPU和GPU实现的性能。

本文的其余部分组织如下:部分2介绍了现有图框架和我们工作的动机。部分3详细描述了我们的实现和优化。部分4论述了实现细节图的算法。部分5提供的结果测量框架的性能。节6,我们得出结论本文讨论潜在的未来的研究领域。

2。相关工作和动机

本节将讨论研究的大型景观图分析框架,既不同的编程模型以及支持平台。

并行图分析框架提出各种高级可编程模型,如顶点编程,矩阵运算任务模型和声明式编程。其中,顶点编程非常广泛的应用,为编写图形程序通常是富有成效的。然而,因为它侧重于排序计算的步骤和缺乏一个强有力的数学模型,很难分析由于其运行时长、内存消耗(高3]。相反,矩阵模型是建立一个坚实的数学背景,例如,图的遍历计算建模为操作在CombBLAS semi-ring [4]和nvGRAPH [5]。在推理和执行优化这是有益的,但它是很难计划(6]。

单节点CPU-based系统常用的图形计算。Giraph [7)使用一个迭代vertex-centric编程模型类似于谷歌的Pregel [8),它是基于Apache Hadoop MapReduce。PowerGraph [9),为实际设计图表有倾斜的幂律度分布,使用更加灵活Gather-Apply-Scatter抽象。这些方法分区边跨节点的vertex-cut暴露更多的并行性的自然图形。伽罗瓦(10- - - - - -12]是一种共享内存的最高性能图系统采用基于任务的抽象。CombBLAS [4]和GraphMat [3)是两种受欢迎的矩阵编程模型。CombBLAS是一个可扩展的分布式内存并行图形库提供一套小而强大的线性代数原语专门针对图形分析。GraphMat,英特尔开发的,是一个单节点多核图框架映射Pregel-like顶点程序高性能稀疏矩阵操作。最近的工作(3]和[13cpu上不同的图表框架相比)。这些文件表明,GraphMat显著优于许多其他框架在大多数情况下。此外,许多不同的映射图的功能操作一组小的矩阵运算提供了相当大的便利GraphMat后台的维护和扩展本身,例如,多个节点。

gpu是功耗小,能够开展high-memory-bandwidth处理。他们可以利用并行计算要求的应用程序。今天大多数高层GPU编程模型分析镜CPU的编程模型。例如,钟和他介绍了美杜莎14),一个高级基于gpu的并行图形系统计算使用Pregel的消息模型(8]。VertexAPI2 [15],MapGraph [16],CuSha [17,18)采用PowerGraph天然气编程模型(9]。Gunrock [2]是一个最近的库开发一个GPU图形算法。而不是设计一个抽象的计算,而是Gunrock使用GPU-specific以数据为中心的模型集中在操作顶点或边边界。王等人。2报告,相比硬GPU实现,Gunrock可比性能最快的GPU电路实现和达到更好的性能比其他任何GPU高级图形库。nvGRAPH (nvGRAPH可用https://developer.nvidia.com/nvgraph)是一种高性能的图书馆由NVIDIA GPU图形分析。它利用gpu的线性代数和矩阵计算来处理大规模图分析(5]。核心功能是使用semi-ring SPMV操作表达图计算(2]。目前支持三种算法:PageRank SSSP,单一宽的道路。

相比CPU图表框架,现有高级GPU图形框架通常获得改进的性能由于其优势在硬件方面,广义负载平衡策略和优化的GPU原语。然而,不可预测的控制流和记忆gpu的分歧引起的不规则图形拓扑需要复杂的策略来确保效率。这可能导致相对较低的生产率和高内存消耗。

某些基于矩阵框架cpu上,例如,CombBLAS [4],GraphMat [3],飞马(19),cpu上证明,基于顶点的编程模型可以用一个矩阵建立后端图形编程。同时,gpu有可能加速稀疏矩阵代数由于其内存受限的特性。各种各样的优化执行改善SPMV的性能(20.),最重要的一个在高性能计算(HPC)的业务,在gpu上。然而,据我们所知,现有的基于矩阵图分析在gpu实现远不及这些优化库(同样的性能21,22]。在这个工作中,我们的目标是实现高性能(优化的稀疏矩阵的后端)图分析以及顶点编程的效率(如顶点为用户编程)gpu。

3所示。HPGraph的抽象和优化

3.1。HPGraph的抽象

HPGraph基于遍历从一个顶点可以表示为一个操作类似于点积,SPMV例程图的邻接矩阵的元素(或其转置)。因此,HPGraph地图图形分析使用顶点编程广义SPMV的GPU提供高性能。它目标图操作,可以表示为迭代收敛过程。“迭代”,我们指的是操作可能需要反复运行的一系列步骤,和一个迭代的结果作为下一次迭代的起点。“收敛”,我们的意思是,正确答案可以获得具有足够精度的迭代终止过程之前。

HPGraph使用bulk-synchronous模型(BSP) [23]。在BSP并行程序执行在同步阶段,称为supersteps。这样操作是足够的gpu的可移植性和效率。每个迭代是一个superstep HPGraph。我们的抽象不同于其他框架,特别是其他基于gpu的框架。而不是集中在排序计算的步骤,我们关注的是顶点映射程序操作的数据结构。我们描述的图形原语本文主要包括三个步骤:进行预处理,SPMV,应用。

进行预处理:在进行预处理阶段,图转换为一个邻接矩阵存储在GPU内存。此外,根据图算法的具体要求,HPGraph为顶点生成不同的属性数据和框架配置参数。在数据结构方面,HPGraph代表所有每个节点数据作为structure-of-array (SOA)数据结构,它允许合并内存访问以最小的内存散度。

SPMV:类似于Giraph (7),HPGraph标志着一些顶点(或一个顶点)有一个“活跃的”状态。在每个迭代中,每个顶点只访问和与它的“活跃的”邻居。假设G是一个米——- - - - - -N稀疏矩阵存储图,x是一个向量存储用户定义的节点属性。在SPMV阶段,通过广义SPMV图遍历完成:(或 )。向量y存储每个节点的有前途的新属性,它将用于应用阶段。对稀疏矩阵对应的操作都是基于这个想法到相邻的顶点可以通过一个点进行产品描述如下:如果一个顶点r访问它的一个“活跃的”邻居,l沿着out-edges ( ),一个函数命名为“收集“将使用执行 , ,和这两个顶点的属性。相反,参观in-edges要求我们首先执行一个换位和获得矩阵 。因此,和可以直接使用。“减少”函数将一个新属性总结使用“收集”操作的结果,并将它存储在结果数组中y。上述过程可以被广义SPMV的点积。

图1显示了一个简单的例子,计算出度。本机SPMV操作,使用邻接矩阵转换图和一个向量的所有的作为输入,可以产生所有顶点的出度存储在一个向量。具体地说,一个沿着out-edges乘法(即顶点的访问。“收集”操作)和(即补充道。,“reduce” operation) together to obtain its out-degree.

我们抽象就足以表达大量多样的图形算法的效率。相对于其他SPMV-based GPU图形库,如nvGraph HPGraph提供方便表达像三角形计数算法SPMV访问顶点的属性。相反,这种方法可以删除一些原子操作的需要比其他graph-centric并行实现抽象Gunrock和MapGraph等。在其他GPU可编程图形框架,可能会有多个平行作家同样的顶点。这个过程需要原子操作,以确保互斥。在我们的抽象,写入数据输出数组的一个元素映射到减少连续使用一个线程或一段。有了这种映射,HPGraph移除大部分的争用,图的遍历和计算简单和直观的描述。一般来说,HPGraph可以实现高效的实现使用高性能SPMV的方法。

应用:一个基于programmer-specified标准应用步骤使用合成阵列y从广义SPMV更新顶点的状态。与此同时,它集这些顶点的状态改变了,“活跃的“顶点和顶点去除这些冗余。HPGraph并行执行,操作在所有元素。这种并行扫描正则和适合gpu。

HPGraph计算管道图所示2。HPGraph基元组装等多个迭代的序列SPMV和应用。他们主要是顺序执行:一步下一步开始前完成所有的操作。通常,HPGraph图形原语收敛,这通常相当于没有顶点状态更改或不”活跃的“顶点。此外,程序员也可以指定的最大数量的迭代。HPGraph将终止当迭代次数达到预定义的限制。

3.2。优化

由于我们关注操纵一些数据结构,如稀疏矩阵和向量,很容易允许将优化集成到我们的框架给程序员更多的选择。我们提供四个例子。

稀疏矩阵的格式:在进行预处理阶段,大量的图形转化为稀疏矩阵。与大多数其他图计算的框架,使用压缩稀疏行(CSR)或顶点操作的图形存储过程中,我们采用HYB (24]矩阵在整个论文格式存储图。

对于一个矩阵的最大K每一行,非零元素魔法(ELLPACK格式)(25)使用一个密集数组数据存储非零值,行不到K在非零。同样的,相应的列见方的块存储在索引数组,再次用零填充。它是适合一个矩阵的非零元素行之间均匀分布。首席运营官(坐标格式),特别是简单的存储方案,使用三个数组,行,坳,和数据,存储行指标,列索引,一个矩阵中的非零元素的值,分别。在我们的实现中,行数组排序,确保连续相同的行索引存储的条目。

l形的格式非常适合矢量架构。然而,当非零的数量每一行上有很大的不同,将会有更多的零元素应该填满。这会导致效率迅速下降。同时,所需的存储首席运营官格式总是非零的数量成正比。此外,这种特性(类似的属性)延伸到一个使用首席运营官SPMV的成本(26]。HYB,混合魔法/首席运营官存储格式,将一些离散矩阵的条目存储在首席运营官和绝大多数条目使用魔法。给定一个稀疏矩阵一个,N的行数在吗一个和非零值的数量吗一个。定义一个阈值K,超过的部分K非零连续提取和存储由首席运营官。其余部分是放在魔法为了减少补零。稀疏矩阵可以分为两部分。一个包含行不到K非零,另一个包含多行K非零。第一部分是放在魔法。第二部分,只K非零超过前面的那些行K非零元素放置到魔法。第二部分提取的剩余的条目存储首席运营官。假设 ,图3展示了一个例子的HYB表示矩阵。贝尔等人[中提到24),根据实证结果,它是有益的补充Kth列矩阵的魔法如果至少有三分之一行包含K(或更多)非零。我们采用这个想法实现最优阈值K。

对于许多(但不是全部)大的图,图的邻接矩阵的非零值(或它的转置)大多集中在小范围之内。这是适合HYB格式。目前,HYB一直在gpu上实现,如由NVIDIA CUDA稀疏矩阵的函数库(cuSPARSE) [27和尖端28SPMV的),但它并没有在GPU平台上实现了图形分析。基于尖端的SPMV函数HYB-formatted矩阵(28图书馆,我们提出两个内核,分别执行操作两个子矩阵。

自底向上遍历:斯科特et al。29日)描述了一种自底向上遍历BFS cpu上。而不是每个顶点在“活跃的“前沿试图成为所有邻国的父母,并且每个顶点试图找到任何父母在邻国,这可以减少边缘检测的总数。顶点的数量时,这种方法是有益的,并且低于访问顶点的大小。此外,HPGraph适应这和使用点积来找到这些节点的前辈。具体地说,在我排一个转置矩阵存储图,一个非零值表示一个边缘指向节点我。如果是有效的和节点j是一组的成员参观了,节点j可以成为父母的我,我们不需要检查其余的同一行中的元素。与此同时,任何操作进行处理我如果顶点th行可以跳过我已经访问了。目前,HPGraph,这种优化只是应用于石。在未来,它可以配合其他图算法。

内存访问优化:HPGraph active-status-lookup包含一个位掩码来减少我们的战略状态数据的大小从一个32位的标签一个每顶点,这可以减少检查一个给定的顶点的探视地位的开销(30.]。我们创建两个位掩码,命名和 ,分别。在进行预处理阶段,被初始化为0,而基于算法的初始化。在每个迭代中,SPMV内核访问数组通过纹理缓存来提高性能。SPMV使用指定的顶点。一旦任何顶点改变状态,数组自动更新,以确保正确性。然后,应用一步更新使用和重置下一个迭代之前。

此外,CUDA设备有几个类型的可寻址内存(即。,registers, shared memory, constant memory, texture memory, local memory, and global memory). As illustrated in [24),SPMV gpu上的操作是高度内存延迟绑定。间接的内存访问模式容易导致静态不可预知的内存访问行为依赖于输入图表。针对这一点,我们利用下面的方法来优化设备内存访问。

我们建议的只读数据加载HYB-formatted稀疏矩阵在开普勒通过只读缓存,可以受益内核的性能有限的带宽。的输入数组SPMV阶段,存储顶点状态和一些位掩码,它们是只读SPMV内核的整个生命周期。由于频繁和随机存取这些SPMV内核中的数组,我们决定将它们存储在纹理的记忆中,这可以提高性能和减少内存流量。

一般来说,相对于其他GPU computation-focused抽象,HPGraph一直是一个非常出色的适合这些选择和优化,特别是SPMV。

3.3。编程接口

为了方便的实现广泛的图形原语,HPGraph提供了一系列简单而灵活的应用程序编程接口(api)(图4)。一组配置参数,作为迭代的库调用控制等功能,是在初始化的进行预处理阶段。将被集成到用户定义的函数SPMV或应用内核调用。的隐瞒任何关于这些步骤在内部如何实现复杂性,我们建议的框架实现高可编程性和效率。用户只需要编写c++代码使用框架。

4所示。应用程序

的主要优势之一HPGraph抽象的SPMV和应用可以组合来构建不同的图形原语用最小的不必要的工作。下面我们描述我们如何表达HPGraph中的每个原始。

4.1。广度优先搜索(BFS)

BFS是最重要的一个图形算法和常用在传统搜索,如web爬行。它旨在探索所有的顶点连接从源。它从一个给定的源和迭代扩展找到所有可到达的顶点。在HPGraph,每个顶点的属性包括“深度”,显示了最小数量的边缘需要遍历从源到一个特定的顶点和“父”显示了前任顶点的ID。一个人可以认为该算法执行以下每个顶点每计算一次迭代:

BFS初始化所有深处到正无穷,除了从顶点开始,设置为0。我们实现更有效的“自下而上”的遍历模式(见部分3.2)减少并发发现子节点。石,因为边缘之间的任何竞争条件访问一个顶点是良性的,HPGraph只需要旗帜访问,既无顶点。当发现一个顶点的前任,我们设置其前任的IDSPMV阶段及其深度应用阶段。节点是永远不会在后面的迭代中重新审视。所以,通过记录顶点访问在每一个迭代,它是easi最终获得实际的路径。

4.2。单源最短路径(SSSP)

在导演和加权图顶点指定来源,SSSP计算源和目的地之间的最短路径长度及其顶点。这个问题已经提出了许多有效的解决方案,而我们使用的方法这是一个轻微的变化bellman最短路径算法用于LonestarGPU图形库(31日]。BFS相比,SSSP保持距离,代表所需的最小边的权值达到一个顶点从源,而不是深度。如果一个新的更新距离,这个顶点可能在后面的迭代中被重提。因此,SSSP需要录音边,所有节点的距离。算法1详细描述了它如何映射到HPGraph的抽象。在我们提出的抽象,初始化源顶点的距离为0,而所有其他的顶点都初始化为一个价值。HPGraph访问所有相关in-edges每个顶点和使用”活跃的”的(距离的改变在过去的迭代)连接到这些边放松距离的值(如果有必要)。我们使用一个原子操作保留位掩码与更新的顶点删除冗余顶点。重复相同的过程,直到收敛。

4.3。PageRank (PR)

PageRank算法是一种用于网页排名根据他们的受欢迎程度估算它们的重要性。这个应用程序迭代计算每个顶点在一个有向图的网页排名。的页面是递归地影响通过超链接和更新由以下方程在每一次迭代,直到达到收敛: 在哪里E在一个有向图的边集,网页排名的页面吗 , 网页排名的页面吗u链接页面 , 页链接的数量吗u,d是一套阻尼因子可在0和1之间。此外,我们每个顶点的初始等级设置为1.0。HPGraph计算每个顶点的出度在预处理阶段。所有顶点都初始化为”活跃的”图。的SPMV阶段计算加权之和在in-edges收到,其余部分完成应用阶段。我们用一个位掩码的顶点数组删除页面排名已经达到收敛。

4.4。三角形计数(TC)

三角形计算图表是一个统计算法中常用的在复杂网络分析中,随机图模型,和重要的现实世界的应用,如垃圾邮件检测,发现隐藏的主题结构在Web和链接推荐(32]。HPGraph,我们认为TC问题作为一组交叉问题的基础上,认为一个三角形顶点时存在有两个相邻的顶点,是相邻的3]。我们改变输入为TC有向无环图。对于一个给定的有向图,没有周期,十字路口的大小给图中三角形的数量。具体地说,让你的邻居列表之间的十字路口u和是 ,在哪里N十字路口的数量。然后,形成三角形的数量e是N,每个三角形的三条边 , ,和( )。一般来说,在HPGraph TC算法有两个阶段:首先,HPGraph形式邻居列表对所有顶点;其次,它计算的大小设置十字路口。

5。实验和结果

5.1。实验装置

实验平台:我们跑所有实验描述了在Linux工作站和两个英特尔(R)至强(R)的CPU e5 - 2620 CPU,每6芯2.40 GHZ。我们进行我们的GPU实验,符合CUDA工具包8.0,NVIDIA Tesla K40m GPU。K40m配备2880流核心,12 GB的内存,内存带宽288 GB /秒。使用英特尔ICPC 17.0.4 GraphMat编译编译器。所有测试都执行10倍的平均运行时使用的结果。我们报告的时间运行加载后的图算法图到GPU和CPU内存中(不包括时间分配资源或从磁盘读图)。同时,我们显示每秒百万遍历边石和SSSP (MTEPS)。

数据集:表1提供的基本特征数据集用于我们的实验。选择数据集包括真实的和生成的图表,以及这些数据集的拓扑结构跨度从常规到无标度。Pokec LiveJournal1数据,Youtube, Orkut社交网络收集;Kron_g500-logn21 R-MAT图生成。他们都是无尺度图的直径小于25,且节点度分布不均,而roadNet-CA相对较大的直径小而均匀分布的节点度(33]。MapGraph nvGRAPH,伽罗瓦没有TC的工作。尽管Gunrock提到其实验为TC (34),它的开源库中不包含这部分。所以,我们只是比较HPGraph TC GraphMat的的性能。边缘的重量值(用于SSSP)为每个数据集是随机1和64之间的值。

5.2。性能结果

5.2.1。HPGraph与GPU图形库

BFS, SSSP PageRank,我们比较HPGraph的性能的三个最先进的高级GPU图形分析框架:MapGraph Gunrock, nvGRAPH。比较结果如表所示2。

的几何平均值HPGraph的加速度MapGraph BFS, SSSP,和网页级别是2.4,2.8,和1.8,分别。Gunrock,他们是1.3、1.1和6.4,分别。从表2,很明显,HPGraph的性能相当,甚至优于MapGraph和Gunrock BFS和SSSP。roadNet-CA然而,我们注意到,HPGraph约1.7低于MapGraph和3.0 x比Gunrock慢。这种性能不一致的问题部分是由于BFS或SSSP小幅度大直径图需要花费大量的迭代来完成每个迭代仅仅更新一个有限数量的顶点。例如,我们需要在500年roadNet-CA迭代之前聚集。因此,HPGraph,一个相对较大的每个迭代的开销,表现不佳。PageRank, HPGraph显著优于MapGraph Gunrock。一般来说,PageRank HPGraph显示更大的加速度,密集计算和更多的常规边界结构(2)比traversal-based图形原语(BFS和SSSP)。

SSSP, nvGRAPH低于HPGraph在所有的数据集(4.3 x)的平均水平。PageRank, HPGraph达到类似的性能nvGRAPH (1.0 x)的平均水平。具体来说,nvGRAPH比HPGraph快四个数据集和慢上三(Youtube, Pokec, roadNet)。

5.2.2。HPGraph CPU和图形库

我们比较HPGraph两个先进的CPU的性能图库:伽罗瓦(10- - - - - -12),high-performance-task-based框架;GraphMat [3),一个高性能的矩阵编程框架。整个系统都使用(24芯)。如图5所示,HPGraph明显比伽罗瓦和GraphMat快。伽罗瓦相比,HPGraph的表现通常是更好的在大多数情况下,测试和它达到4.1 - -6.3 x加速算法和数据集的范围。虽然对GraphMat HPGraph提供4.6倍加速对所有原语(BFS平均3.4 x 5.4 x SSSP, 5.1 x PageRank, TC和3.2 x)。

5.3。优化的效果

图6显示我们的优化性能的影响(描述的部分3)石(LiveJournal上运行)和网页排名(Kron_g500-logn21上运行)。我们使用一个实现CSR-based广义SPMV基线天真的版本。第一栏显示基线天真实现规范化为1。位掩码数组添加到标记“活跃”顶点和内存访问优化提供了一些好处,第二栏所示。这使得更好的并行可扩展性。第三条表明HYB-formatted稀疏矩阵的结果进一步获得BFS和1.95 x 2.5 x的Pagerank。direction-optimal遍历策略(中提到的部分3.2)也为BFS效果更好。类似的结果以及数据集的其他算法。一般来说,我们的灵活GPU-specific编程模型,它允许为集成高效的优化,包括矩阵运算更快和更有效的图形遍历,可以使HPGraph生产不牺牲任何性能。

5.4。讨论的性能

这两个GPU BFS-based high-level-programming-model努力(MapGraph和Gunrock)用于比较采用负载均衡策略从美林等的石38]。没有其优化方法,我们仍预计HPGraph显示类似的性能在所有图形原语其他框架。与顶点程序映射到广义稀疏矩阵运算,HPGraph支持更好的稀疏矩阵格式,有效图遍历和内存访问优化。所有这些原因导致性能优越的平均变形效率HPGraph SPMV内核的所有算法和数据集(如表所示3)。平均变形效率意味着线程活动期间的分数计算,这是一个很好的负载平衡质量的措施。

相反,HPGraph nvGRAPH使用相似矩阵的后端,但HPGraph仍优于nvGRAPH尤其是SSSP。这样做的主要原因是我们大力优化广义SPMV端节中描述3。由于nvGRAPH是闭源,一个详细的比较是不可行的。此外,所示(6),一些图形计算,如三角形计数,很难有效地表示为一个纯粹的矩阵运算导致长期运行时和增加内存消耗。这可能是主要原因nvGraph尚未为三角形计数工作。与允许顶点的属性访问SPMV期间,HPGraph完成高效实现三角形计数并显示更好的生产力。

6。结论

图分析已经广泛应用于许多应用程序(39,40]。在本文中,我们提出了HPGraph, GPU图形分析框架,地图一个顶点编程优化矩阵的后端。这样一个模型提供了高绩效和生产力。主要的计算方法是基于SPMV以来,HPGraph使用改性高性能SPMV原语可以达到更好的性能。此外,HPGraph抽象允许我们将各种优化策略包括数据结构、direction-optimal遍历和内存访问。与此同时,高层抽象允许用户完成各种图形原语。实验结果对大规模图表明HPGraph显著快于先进的CPU运行库,可以匹配甚至超过其他先进的可编程GPU图形库的性能。由于可用的GPU内存仍然是瓶颈HPGraph更大的数据集,在未来的工作中,我们期望框架很好地伸缩从单个multi-GPU集群GPU版本。

努力使数字或许可的副本部分或所有的工作为个人或教室使用授予没有费用,提供副本不是获利或分布式或商业优势,承担此通知副本和完整的引文在第一页。版权为第三方组件的工作必须得到履行。对于所有其他用途,联系业主/作者(年代)。

的利益冲突

作者宣称没有利益冲突。

确认

作者欣然承认支持国家重点研究和发展项目的2016号yfb1000400和中国国家自然科学基金国家自然科学基金委号,61502509和61402504。

引用

1. s . w .闲扯,w . j .磨磨蹭蹭的,快b . Khailany m .花环和d . Glasco“gpu并行计算的未来,”IEEE微没有,卷。31日。5、7 - 17页,2011年。视图:出版商的网站|谷歌学术搜索
2. a . y . Wang戴维森,y, y, a . Riffel和j·d·欧文斯”Gunrock:高性能GPU图形处理库,”21 ACM SIGPLAN学报》研讨会上并行编程的原理和实践p。11日,巴塞罗那,西班牙,2016年3月。视图:谷歌学术搜索
3. s . Narayanan n . Satish m·m·a·Patwary et al .,“Graphmat:高性能图形分析了生产力,”美国养老,8卷,不。11日,第1225 - 1214页,2015年。视图:出版商的网站|谷歌学术搜索
4. 答:自由,a . Buluc和j·r·吉尔伯特组合布拉斯v1.6.1EECS,伯克利分校,美国,2018年,https://people.eecs.berkeley.edu/aydin/combblas/html/index.html。
5. j·凯普纳a .彼得·d·巴德et al .,“GraphBLAS的数学基础,”学报2016年IEEE极端高性能计算会议(HPEC)美国马,页1 - 9,沃尔瑟姆,2016年9月。视图:谷歌学术搜索
6. n . Satish s Narayanan m·m·a·Patwary et al .,“导航的迷宫图分析框架使用大规模图数据集”学报2014年ACM SIGMOD国际会议管理的数据芝加哥,页979 - 990,美国,2014年5月。视图:谷歌学术搜索
7. c·艾弗里,“Giraph:大规模图处理基础设施在hadoop,”学报Hadoop峰会。圣克拉拉,11卷,不。3,5 - 9,2011页。视图:谷歌学术搜索
8. g . Malewicz m . h . Austern j·c·b·阿尔特et al .,“Pregel:系统对大规模图处理”学报2010年ACM SIGMOD国际会议管理的数据印第安纳波利斯,页135 - 146年,2010年6月,美国。视图:谷歌学术搜索
9. j·e·冈萨雷斯,y低,h·顾d·比克森和c . Guestrin”PowerGraph:分布式计算graph-parallel自然图”,OSDI,12卷,不。2、2012。视图:谷歌学术搜索
10. d .阮、A . Lenharth和k . Pingali“轻量级基础设施图分析”《第二十四ACM研讨会上操作系统的原则法明顿,页456 - 471年,PA,美国,2013年11月。视图:谷歌学术搜索
11. 得克萨斯大学伽罗瓦v2.2.1德克萨斯大学奥斯汀,TX,美国,2014年,http://iss.ices.utexas.edu/?p=projects/galois/download。
12. k . Pingali d·阮m . Kulkarni et al .,“道并行的算法,ACM Sigplan通知,46卷,目前消费量,2011页。视图:出版商的网站|谷歌学术搜索
13. a . Iosup蒂姆•Hegeman w . l . Ngai et al .,“LDBC graphalytics:基准对大规模图分析并行和分布式平台上,“PVLDB,9卷,不。13,12页,2016。视图:谷歌学术搜索
14. j .钟和他的“美杜莎:简化图像处理在gpu,”IEEE并行和分布式系统,25卷,不。6,1543 - 1552年,2014页。视图:出版商的网站|谷歌学术搜索
15. 大肠Elsen诉Vaidyanathan,Vertex-Centric CUDA / c++ API对于大型图使用Gather-Apply-Scatter抽象对gpu的分析美国CA, Github,旧金山,2013年。
16. 傅z、m . Personick和b·汤普森“Mapgraph:高水平的API gpu的高性能图形分析的快速发展,”学报车间图数据管理经验和系统美国雪鸟,页1 - 6,UT, 2014年6月。视图:谷歌学术搜索
17. f . Khorasani r·古普塔和l . n . Bhuyan“gpu的可伸缩simd-efficient图处理,”学报2015年国际会议上并行体系结构和编译(协议)美国旧金山,页39-50 CA, 2015年10月。视图:谷歌学术搜索
18. f . Khorasani k . Vora r·古普塔和l . n . Bhuyan”gpu CuSha: vertex-centric图处理,”学报》第23届国际研讨会高性能并行计算和分布式计算温哥华,页239 - 252年,公元前,加拿大,2014年6月。视图:谷歌学术搜索
19. 美国康,c, e . Tsourakakis和c·凯利斯“飞马:peta-scale图矿业系统实现和观察”学报》第九IEEE国际会议数据挖掘ICDM ' 09,页229 - 238,迈阿密,佛罗里达,美国,2009年。视图:谷歌学术搜索
20. a . Ashari n . Sedaghati j . Eisenlohr美国高,p . Sadayappan”快速稀疏矩阵向量乘法对gpu图形应用程序,”学报为高性能计算国际会议,网络,存储和分析新奥尔良,页781 - 792年,洛杉矶,美国,2014年11月。视图:谷歌学术搜索
21. 诉Kalavri、诉Vlassov和s . Haridi“分布式图像处理的高级编程抽象”,IEEE知识&数据工程,30卷,不。2、305 - 324年,2018页。视图:出版商的网站|谷歌学术搜索
22. h, h·苏·m·温,c .张“HPGA:高性能图形分析框架在GPU,”学报2018年国际会议信息和计算机技术青岛,页584 - 588年,中国,2018年7月。视图:谷歌学术搜索
23. l . g .勇敢的“并行计算的桥接模式,”ACM的通信,33卷,不。8,103 - 111年,1990页。视图:出版商的网站|谷歌学术搜索
24. n·贝尔和m .花环,“有效的稀疏矩阵向量乘法CUDA上,”技术。代表,NVIDIA技术报告极- 2008 - 004,NVIDIA公司,圣克拉拉,CA,美国,2008年。视图:谷歌学术搜索
25. j . r .大米、“ELLPACK:进展和计划”椭圆问题解决者学术出版社,页135 - 162年,剑桥,妈,美国,1981年。视图:谷歌学术搜索
26. m . m . Baskaran和r . Bordawekar优化稀疏矩阵向量乘法在gpu使用编译时和运行时策略,“技术。代表,IBM Reserach报告RC24704, IBM,纽约,美国2008年约克镇。视图:谷歌学术搜索
27. 英伟达,NVIDIA Cuda稀疏矩阵库NIVIDIA圣克拉拉,CA,美国,2015年,https://developer.nvidia.com/cusparse。
28. 美国道尔顿:贝尔,l·奥尔森,m·加兰尖端:通用并行算法对稀疏矩阵和图计算美国CA, NVIDIA公司,圣克拉拉,2014年,http://cusplibrary.github.io/version0.5.0。
29. b·斯科特,k . Asanović和d·帕特森“Direction-optimizing广度优先搜索,”科学的规划,21卷,不。3 - 4、137 - 148年,2013页。视图:谷歌学术搜索
30. h, h·苏问:局域网,m·温和c,“高性能图形分析与生产力在混合CPU-GPU平台上,”第二届国际会议上高性能编译、计算和通信中国,香港,17 - 21页。区间,2018。视图:谷歌学术搜索
31. m . Burtscher r . Nasre, k . Pingali“定量研究不规则gpu上的程序,”学报2012年IEEE国际研讨会上负载特性(IISWC)拉霍亚,页141 - 151年,CA,美国,2012年11月。视图:谷歌学术搜索
32. m . n . Kolountzakis g·l·米勒,r·彭和c e . Tsourakakis”有效的三角形计数在大型图形通过mba顶点划分不同,“互联网上数学,8卷,不。1 - 2、161 - 185年,2012页。视图:出版商的网站|谷歌学术搜索
33. j . Leskovec k . j . Lang a·达斯古普塔和m·w·马奥尼,”大型网络社区结构:自然集群大小和缺乏大型定义良好的集群的情况下,“互联网上数学》第六卷,没有。1,29 - 123年,2009页。视图:出版商的网站|谷歌学术搜索
34. y, y, a·戴维森et al .,“Gunrock: GPU图形分析,”2017年,http://arxiv.org/abs/1701.01170。视图:谷歌学术搜索
35. t·a·戴维斯和y胡,”佛罗里达大学的稀疏矩阵集合,”ACM交易数学软件(汤姆斯),38卷,不。1、1 - 25,2011页。视图:出版商的网站|谷歌学术搜索
36. Leskovec和a . Krevl临时数据集:斯坦福大学大型网络数据集收集美国斯坦福大学,斯坦福大学,2014年,http://snap.stanford.edu/data。
37. r·a·罗西和n·k·艾哈迈德,”网络与互动图表分析和可视化数据存储库,”美国29日AAAI会议上人工智能美国奥斯汀,TX, 2015年1月,http://networkrepository.com。视图:谷歌学术搜索
38. 亚当和d . a . m .巴德”、可伸缩的和高性能的中间性中心GPU,”学报为高性能计算国际会议,网络,存储和分析新奥尔良,页572 - 583年,洛杉矶,美国,2014年11月。视图:谷歌学术搜索
39. 李x, p . j ., t . Tang z . Wang和c·杨,“高效、高质量的稀疏图着色在gpu上,“并发性和计算:实践和经验卷,29号10 p . e4064 2017。视图:谷歌学术搜索
40. h·张,陈x:肖et al .,“屏蔽stt - ram寄存器文件基于gpu对阅读障碍,”ACM杂志在新兴技术计算系统(JETC),13卷,不。2,p。2017。视图:出版商的网站|谷歌学术搜索

版权

版权©2018杨Haoduo et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。