公开(公告)号：CN105590321B

公开(公告)日：2018-12-28

申请号：CN201510988695.3

申请日：2015-12-24

Applicant: 华中科技大学

Inventor： 王芳 ,  程永利 ,  冯丹 ,  汪修能 ,  张永选 ,  戎佳磊 ,  蒋子威

IPC: G06T11/20 ,  H04L29/08

Abstract: 本发明公开了一种基于块的子图构建及分布式图处理方法，其子图构建方法，包括图分割、对子图中的顶点重新贴标签、将区间与数据片关联、分块和构建子图的步骤；采用启发式的、轻量级的SGP方法进行图分割，采用用户定义的启发式函数把顶点按顺序指派到P个子图，具有性能高，边的切割率较低的特点，并且可以兼顾子图工作负载平衡问题；其分布式图处理系统，块分割之后，子图之间以整个内存块为单位进行通信；与现有技术的细粒度通讯方式相比，本发明的基于内存块的数据交换，可以充分利用网络带宽，提高网络的利用率，降低通讯时间。

公开(公告)号：CN105590321A

公开(公告)日：2016-05-18

申请号：CN201510988695.3

申请日：2015-12-24

Applicant: 华中科技大学

Inventor： 王芳 ,  程永利 ,  冯丹 ,  汪修能 ,  张永选 ,  戎佳磊 ,  蒋子威

IPC: G06T7/00 ,  H04L29/08

CPC classification number: H04L67/10

Abstract: 本发明公开了一种基于块的子图构建及分布式图处理方法，其子图构建方法，包括图分割、对子图中的顶点重新贴标签、将区间与数据片关联、分块和构建子图的步骤；采用启发式的、轻量级的SGP方法进行图分割，采用用户定义的启发式函数把顶点按顺序指派到P个子图，具有性能高，边的切割率较低的特点，并且可以兼顾子图工作负载平衡问题；其分布式图处理系统，块分割之后，子图之间以整个内存块为单位进行通信；与现有技术的细粒度通讯方式相比，本发明的基于内存块的数据交换，可以充分利用网络带宽，提高网络的利用率，降低通讯时间。

公开(公告)号：CN105653204B

公开(公告)日：2018-12-07

申请号：CN201510988839.5

申请日：2015-12-24

Applicant: 华中科技大学

Inventor： 王芳 ,  程永利 ,  冯丹 ,  汪修能 ,  张永选 ,  戎佳磊

IPC: G06F3/06

Abstract: 本发明公开了一种基于磁盘的分布式图计算方法，该方法采用基于磁盘的分布式计算模型，用图分割算法将原始图分割成P个子图，通过N次迭代完成一个图算法作业，子图的一次执行为一个任务，共包括(P×N)个任务；一个任务包括(1)子图加载和构建；(2)子图的计算；(3)结果存储、向其它子图发送相关数据的步骤；本方法以流水的方式调度任务，通过任务之间的重叠执行，可隐藏系统执行过程中磁盘读写与通讯的时延，这种执行过程使整个系统的运行时间几乎缩短到计算时间，大大提高了系统的性能，面对不同规模的图，系统可始终保持极小的系统规模，从而大大节省系统的硬件成本。

公开(公告)号：CN105653204A

公开(公告)日：2016-06-08

申请号：CN201510988839.5

申请日：2015-12-24

Applicant: 华中科技大学

Inventor： 王芳 ,  程永利 ,  冯丹 ,  汪修能 ,  张永选 ,  戎佳磊

IPC: G06F3/06

CPC classification number: G06F3/061 ,  G06F3/0659 ,  G06F3/0689

Abstract: 本发明公开了一种基于磁盘的分布式图计算方法，该方法采用基于磁盘的分布式计算模型，用图分割算法将原始图分割成P个子图，通过N次迭代完成一个图算法作业，子图的一次执行为一个任务，共包括(P×N)个任务；一个任务包括(1)子图加载和构建；(2)子图的计算；(3)结果存储、向其它子图发送相关数据的步骤；本方法以流水的方式调度任务，通过任务之间的重叠执行，可隐藏系统执行过程中磁盘读写与通讯的时延，这种执行过程使整个系统的运行时间几乎缩短到计算时间，大大提高了系统的性能，面对不同规模的图，系统可始终保持极小的系统规模，从而大大节省系统的硬件成本。