グラフデータの探索処理をcuGraphで高速化できるか検証した

グラフデータはSNSのネットワークや化学の分野でよく使われるぞ

このデータも高速に解析するためのツールがあるぞ

環境情報

GPUでグラフデータを高速に解析できるcuGraphを発見しました。

https://github.com/rapidsai/cugraph

NGCからdockerコンテナを取得して動作確認をしました。NGCの設定方法は下記をご覧ください。

構築環境は下記です。

ハードウェア

  • CPU: Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz
  • Memory: 64GB
  • GPU: Geforce 2080 Ti

ソフトウェア

  • OS: Ubuntu 18.04
  • cuda: バージョン11.0
  • Graphics Driver: バージョン450.51.06
  • docker: 19.03.12

下記のNotebookを参考に幅優先探索を実行して、パフォーマンス比較を行います。

https://github.com/rapidsai/cugraph/blob/branch-0.16/notebooks/cugraph_benchmarks/bfs_benchmark.ipynb

幅優先探索はグラフ内の探索したいノードを見つけるための手法の1種です。グラフの浅い位置に探索したいノードがある場合は有効な手法になります。ただ今回の幅優先探索の関数は開始ノードから全ノードを探索して、頂点情報、距離情報、各頂点に繋がっている前の頂点の情報を取得する関数になっています。

詳細は下記をご覧ください。

https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

コードの取得

docker コンテナにアクセスします。

docker run --gpus all --rm -it -p 8889:8889 -p 8787:8787 -p 8786:8786          rapidsai/rapidsai:cuda10.1-runtime-ubuntu18.04

“cugraph”のディレクトリがすでにあって名前が重なるので名前変更してダウンロードします。

git clone https://github.com/rapidsai/cugraph.git cugraph_test

データの準備

cd cugraph_test//notebooks/cugraph_benchmarks/
sh ./dataPrep.sh

コードの実行確認

“bfs_benchmark.ipynb”を開きます。

まず使用しているGPUを確認します。

!nvidia-smi
Wed Aug 26 06:42:40 2020       
+-----------------------------------------------------------------------------+
| NVIDIA-SMI 450.51.06    Driver Version: 450.51.06    CUDA Version: 11.0     |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|                               |                      |               MIG M. |
|===============================+======================+======================|
|   0  GeForce RTX 208...  On   | 00000000:01:00.0  On |                  N/A |
| 25%   35C    P5    38W / 250W |   2268MiB / 11014MiB |     26%      Default |
|                               |                      |                  N/A |
+-------------------------------+----------------------+----------------------+
                                                                               
+-----------------------------------------------------------------------------+
| Processes:                                                                  |
|  GPU   GI   CI        PID   Type   Process name                  GPU Memory |
|        ID   ID                                                   Usage      |
|=============================================================================|
+-----------------------------------------------------------------------------+

Jupyter-labを起動します。

jupyter-lab --allow-root --ip=0.0.0.0 --NotebookApp.token=""

使用するGPUを設定します。

import os
os.environ["CUDA_VISIBLE_DEVICES"]="0"

必要なライブラリをインポートします。

import gc
import time
import rmm
import cugraph
import cudf

比較を行うためCPUでグラフ処理を行うライブラリをインポートします。


# NetworkX libraries
import networkx as nx
from scipy.io import mmread

結果を描画するためのライブラリをインポートします。

try: 
    import matplotlib
except ModuleNotFoundError:
    os.system('pip install matplotlib')

import matplotlib.pyplot as plt; plt.rcdefaults()
import numpy as np

使用するGPUデバイス名を取得します。

cudf._cuda.gpu.deviceGetName(0)

パフォーマンスを確認するためのデータをリスト化しておきます。これらのデータは先程のスクリプトで取得したデータです。

# Test File
data = {
    'preferentialAttachment' : './data/preferentialAttachment.mtx',
    'caidaRouterLevel'       : './data/caidaRouterLevel.mtx',
    'coAuthorsDBLP'          : './data/coAuthorsDBLP.mtx',
    'dblp'                   : './data/dblp-2010.mtx',
    'citationCiteseer'       : './data/citationCiteseer.mtx',
    'coPapersDBLP'           : './data/coPapersDBLP.mtx',
    'coPapersCiteseer'       : './data/coPapersCiteseer.mtx',
    'as-Skitter'             : './data/as-Skitter.mtx'
}

mtxフォーマットのデータを読み込むための関数です。scipyにmmread関数があるため、こちらを使用します。行列フォーマットのデータを読み込む際に使う関数です。

# Data reader - the file format is MTX, so we will use the reader from SciPy
def read_mtx_file(mm_file):
    print('Reading ' + str(mm_file) + '...')
    M = mmread(mm_file).asfptype()
     
    return M

cugraph“にデータを読み込み、幅優先探索を行い時間を測る関数です。まずcudfで行、列要素にデータを読み込みます。

幅優先探索で返すグラフ情報は頂点情報、距離情報、各頂点に繋がっている前の頂点の情報です。

  • gdf[‘src’] = M.row : 列に出発地点の情報があるので、それを設定します。
  • gdf[‘dst’] = M.col: 行に目的地の情報があるので、それを設定します。
  • G = cugraph.DiGraph(): グラフを作成用のインスタンスです。DiGraph に定義されています。このクラスはもとのGraphクラスを継承しています。
  • G.from_cudf_edgelist(gdf, source=’src’, destination=’dst’, renumber=False): 先程作成したインスタンスから”from_cudf_edgelist”を呼んでcudf上で定義した出発地点と目的地のインデックス情報を渡してグラフ作成を行います。
  • cugraph.bfs(G, 1): グラフとスタート頂点を設定してbfs(幅優先探索の関数)をコールします。
def cugraph_call(M):

    gdf = cudf.DataFrame()
    gdf['src'] = M.row
    gdf['dst'] = M.col
    
    print('\tcuGraph Solving... ')
    
    t1 = time.time()
        
    # cugraph Pagerank Call
    G = cugraph.DiGraph()
    G.from_cudf_edgelist(gdf, source='src', destination='dst', renumber=False)
    
    df = cugraph.bfs(G, 1)
    t2 = time.time() - t1
    
    return t2

CPUでの処理性能を比較するためにnetworkxを使用して、同様にグラフ作成からbfs処理の時間を計測する関数を作成します。

def networkx_call(M):
    nnz_per_row = {r: 0 for r in range(M.get_shape()[0])}
    for nnz in range(M.getnnz()):
        nnz_per_row[M.row[nnz]] = 1 + nnz_per_row[M.row[nnz]]
    for nnz in range(M.getnnz()):
        M.data[nnz] = 1.0/float(nnz_per_row[M.row[nnz]])

    M = M.tocsr()
    if M is None:
        raise TypeError('Could not read the input graph')
    if M.shape[0] != M.shape[1]:
        raise TypeError('Shape is not square')

    # should be autosorted, but check just to make sure
    if not M.has_sorted_indices:
        print('sort_indices ... ')
        M.sort_indices()

    z = {k: 1.0/M.shape[0] for k in range(M.shape[0])}
        
    print('\tNetworkX Solving... ')
        
    # start timer
    t1 = time.time()
    
    Gnx = nx.DiGraph(M)

    pr = nx.bfs_edges(Gnx, 1)
    
    t2 = time.time() - t1

    return t2

下記のコードでGPUの速度がCPUに比べてどの程度、早くなるか確認します。

用意したデータが複数あるので各データセットに対して、どの程度、高速になったか確認できるようにlistに結果を収納しています。データ・セットは下記があります。

  • preferentialAttachment.mtx
  • caidaRouterLevel.mtx
  • coAuthorsDBLP.mtx
  • dblp-2010.mtx
  • citationCiteseer.mtx
  • coPapersDBLP.mtx
  • coPapersCiteseer.mtx
  • as-Skitter.mtx
# arrays to capture performance gains
perf_nx = []
names = []
time_cu = []
time_nx = []

# do a simple pass just to get all the libraries initiallized
v = './data/preferentialAttachment.mtx'
M = read_mtx_file(v)
trapids = cugraph_call(M)
del M

for k,v in data.items():
    gc.collect()

    # Saved the file Name
    names.append(k)
    
    # read the data
    M = read_mtx_file(v)
    
    
    # call cuGraph - this will be the baseline
    trapids = cugraph_call(M)
    
    # Now call NetworkX
    tn = networkx_call(M)
    speedUp = (tn / trapids)
    perf_nx.append(speedUp)
    time_cu.append(trapids)
    time_nx.append(tn)
    del M
    
    print("\tcuGraph (" + str(trapids) + ")  Nx (" + str(tn) + ")" )

下記のコードで結果を可視化します。

%matplotlib inline

plt.figure(figsize=(11,9))

bar_width = 0.5
index = np.arange(len(names))

_ = plt.bar(index, perf_nx, bar_width, color='g', label='vs NetworkX')



plt.xlabel('Datasets')
plt.ylabel('Speedup')
plt.title('BFS Performance Speedup')
plt.xticks(index + (bar_width/4), names)
plt.xticks(rotation=90) 

# Text on the top of each barplot
for i in range(len(perf_nx)):
    plt.text(x = (i - .5) + bar_width, y = perf_nx[i] + 25, s = round(perf_nx[i], 1), size = 12)

plt.legend()
plt.show()

下記のような結果になります。

300〜1800倍とかなり速度が向上するぞ

Close Bitnami banner
Bitnami