gor match regenerated by bowen

pdf code

概述

grape-gundam 是一个在并行图计算系统grape上增加了gundam库的版本

Overview

Distributed graph algorithms library.

Install dependencies on Ubuntu

GCC version: 7.4.0 or above, support of c++17 standard required.

Install mpi:

sudo apt-get install openmpi-bin openmpi-doc libopenmpi-dev

Install glog:

sudo apt-get install libgoogle-glog-dev

Install gflags:

sudo apt-get install libgflags-dev

Install yaml:

sudo apt-get install libyaml-cpp-dev

Compile

mkdir build && cd ./build
cmake ../
make all -j

应用

gor_match

gor_match

图？？？规则（Graph Oracle Rule，GOR）匹配

• 分布式(MPI)
• 单线程
• 增量匹配
• 不支持分图

概述

本程序可对GOR逐条进行分布式匹配。各节点保存完整的数据图，程序运行之初将图中vertex分配到不同worker。各worker运行过程中暂不支持多线程。

编译

mkdir ./build/ && cd ./build/
cmake ../
make gor_match
cd ../

运行

单机运行

./build/gor_match --yaml_file ${yaml_file_name}

分布式运行

# 参数详见MPI文档
mpirun -N xxx -n yyy -c zzz ./build/gor_match --yaml_file ${yaml_file_name}

Slurm分布式运行

run_gor_match.sh:

#!/bin/sh 

mpirun ./build/gor_match --yaml_file ${1}

srun:

# 参数详见slurm文档
srun -N xxx -n yyy -c zzz ./shell/run_gor_match.sh ${yaml_file_name}

sbatch:

# 参数详见slurm文档
sbatch -N xxx -n yyy -c zzz ./shell/run_gor_match.sh ${yaml_file_name}

yaml 示例

gor_match yaml 示例。

yaml 文件格式:

单条 Gor 匹配

单条 gor 匹配的 yaml 文件格式如下所示：

DataGraphPath: 
  VFile : vertex file of the data graph
  EFile : edge file of the data graph
  
GorPath:
  VFile : vertex file of the gor
  EFile : edge file of the gor
  XFile : X (lhs) literal file of the gor
  YFile : Y (rhs) literal file of the gor
  PivotId : (optional) specify the pivot vertex id, needs to be contained in the Y literals of the gor

TimeLogFile: time log file

多条 Gor 匹配

多条 gor 匹配的 yaml 文件格式如下所示：

DataGraphPath: 
  VFile : ...
  EFile : ...
  
GorPath:
  # first gor
  - VFile : ...
    EFile : ...
    XFile : ...
    YFile : ...

  # second gor
  - VFile : ...
    EFile : ...
    XFile : ...
    YFile : ...
  ...

TimeLogFile: ...

Gor 增量匹配

如下所示，仅需在 yaml 文件中指定ΔG中包含的节点即可进行增量匹配：

DataGraphPath: 
  VFile : ...
  EFile : ...
  DeltaVFile : id of delta vertexes set in the given data graph
  
GorPath:
  VFile : ...
  EFile : ...
  XFile : ...
  YFile : ...
  PivotId : (optional) ...

TimeLogFile: ...

此时，本程序会将读取的数据图视作G + ΔG、将DeltaVFile中包含的节点ID视作数据图中新增的节点。

本程序同时支持多条 Gor 的增量匹配，yaml格式此处不再赘述。

向 Gor 匹配添加约束

可向Gor匹配过程中添加约束：

DataGraphPath: 
  VFile : ...
  EFile : ...
  
GarPath:
  VFile : ...
  EFile : ...
  XFile : ...
  YFile : ...
  PivotId : (optional) ...

# time limit of the entire gor matching
TimeLimit: (unit: second)

TimeLogFile: ...

分布式 Gor 匹配负载均衡

在coordinator的协调下，定期均衡各worker的负载：

DataGraphPath: 
  VFile : ...
  EFile : ...
  
GorPath:
  VFile : ...
  EFile : ...
  XFile : ...
  YFile : ...
  PivotId : (optional) ...

WorkloadBalance:
  # period for coordinator to balance the workload of each worker
  BalancePeriod:  (unit: ms)
  # size of pivot candidate in each worker for coordinator to add to each time
  PivotedCandidateBalanceSize: integer, pivot vertex number

TimeLogFile: ...