大規模 処理ベンチマー Graph500 へ
２次元分割 適用と性能評価
昸司
†
鈴村 豊 郎
††
Graph 500 ， ケ ー ド ー カ ン ヌ ュ ー シ エ メ ネ 処 理 性 能 を 測 定 る 新 い パ ン ス ブ ー ェ あ る ケ ド カ ン パ ン ス ブ ー ェ ， 数 値 計 算 性 能 を 測 るLinpack
よ る Top 500 暼 ， 近 ， 大 規 模 エ メ ネ 処 理 ， 要 性 を 増 り ，
Graph500パ ン ス ブ ー ェ 広 り を 見 い る Graph500 モ ネ ゙ ヤ ン ケ 実 装 ， 使 用 さ れ い る ゚ ャ ガ モ ゲ ヘ 問 題 よ り ，分 散 ベ ペ モ 環 境 大 規 模 ケ ォ ー ャ
さ る こ こ ，大 規 模 ケ ォ ー ャ 可 能 次 元 分 割 注 目
本 論 文 ， 次 元 分 割 をTSUBAME2.0 実 装 ，512テ ー チ 頂 点 数 236 68.7 billion ， 数240 1.1 trillion エ メ ネ Graph500 Scale 36 BFS(幅 優 先 探 索)を24.12 計 算 TEPS値 22.8GE/s あ り ， 次 元 分 割 よ る
実 装 大 規 模 分 散 可 能 あ る こ 分 ，ェ メ ケ シ 型 ケ ド カ ン
一 般 的 InfiniBandヅ ッ ダ ワ ー ェ 環 境 ， 大 規 模 エ メ ネ 処 理 適 い る こ 分
Performance Evaluation of the Large-Scale
Graph Analysis Benchmark, Graph500 with 2D
Partitioning Method
Koji Ueno
†and Toyotaro Suzumura
††Graph500 is a new benchmark that ranks supercomputers by executing a large-scale graph search problem. Our early study reveals that the provided reference implementations are not scalable in a large-scale distributed environment. In this paper we implement an optimized method based on 2D based partitioning. Our implementation can solve BFS (Breadth First Search) of large-scale graph with 236 68.7 billion vertices and 240 1.1 trillion edges for 24.12 seconds with 512 nodes and 12288 CPU cores. This record corresponds to 22.8 GE/s. We found 2D based partitioning method is scalable for large-scale distributed systems. We also demonstrate thorough study of performance characteristics of our optimized implementation and reference implementations in a large-scale distributed memory supercomputer with the Fat-Tree based Infiniband network.
1. じ め
大 規 模 エ メ ネ 処 理 Webヒ ー グ モ ン ェ 解 析 ，シ ン ド ェ 質 間 相 互 作 用 解 析 ，VLSI ヤ ゜ ゚ ゞ ダ や 路 網 ， 送 電 網 暷 適 化 様 々 応 用 分 あ り ， 近 盛 ん 研 究 さ れ い る 従 来 ， ケ ー ド ー カ ン ヌ ュ ー シ 物 理 ク プ ュ ヤ ー ク ョ ン 数 値 計 算 ， 主 使 わ れ ， 大 規 模 エ メ ネ 処 理 要 ゚ ハ モ ォ ー ク ョ ン り あ り ， よ う 中 ，ケ ド カ ン エ メ ネ 処 理 性 能 を 測 定 る ，Graph 500 [1] い う 新 い パ ン ス ブ ー ェ 場 ， 注 目 を 集 い る Graph 500 ， ケ ド カ ン 通 信 性 能 や ， エ メ ネ タ ー シ を 格 納 る ベ ペ モ 大 さ や ， ベ ペ モ メ ン ジ ヘ ゚ ェ コ ケ 性 能 を 測 る い う ， タ ー シ ゜ ン ゾ ン ク ノ パ ン ス ブ ー ェ あ り ， 数 値 計 算 性 能 を 測 るTop 500パ ン ス ブ ー ェ 計 測 る 性 能 全 く 異 る
Graph500 新 い パ ン ス ブ ー ェ あ り ，暷 適 化 関 研 究 少 い 々 [15] い ， モ ネ ゙ ヤ ン ケ 実 装 ゚ ャ ガ モ ゲ ヘ や 性 能 解 析 を 行 い る こ 得 ら れ 知 見 基 い ，本 論 文 次 元 分 割 よ る 隣 接 行 列 分 割 方 法[2] 着 目 ，大 規 模 分 散 環 境 ケ ォ ー ャ 可 能 Graph500 実 装 方 法 を 提 案 る ，分 散 ベ ペ モ 環 境 大 規 模 実 行 場 合 性 能 特 性 を 調 査 本 論 文 貢 献 ，
1. 次 元 分 割 よ る 分 散BFSをTSUBAME2.0 実 装
2. TSUBAME2.0 大 規 模 実 行 ，2次 元 分 割 よ る 実 装 モ ネ ゙ ヤ ン ケ 実 装 性 能 を 比 較
3. 次 元 分 割 よ る 分 散BFS ， 大 規 模 分 散 可 能 あ る こ を 実 証
以 降 ，2章 Graph500パ ン ス ブ ー ェ 概 要 ，分 散BFS゚ ャ ガ モ ゲ ヘ い ，3 章 モ ネ ゙ ヤ ン ケ 実 装 大 規 模 分 散 環 境 け る ケ ォ ー メ ニ モ ゾ ゛ 問 題 い ，4 章 2次 元 分 割 よ る 分 散BFS゚ ャ ガ モ ゲ ヘ 実 装 い ，5章 2次 元 分 割 よ る 実 装 モ ネ ゙ ヤ ン ケ 実 装 性 能 を 比 較 ，6章 考 察 ，7章 関 連 研 究 ，8章
今 後 展 望 あ る
2. Graph500ベ ン チ マ ー とBFS ゴ ム
こ 章 ，Graph500 パ ン ス ブ ー ェ 概 要 ， 分 散 BFS ゚ ャ ガ モ ゲ ヘ い 述 る さ ら ，分 散BFS゚ ャ ガ モ ゲ ヘ 行 列 パ ェ ダ ャ 積 関 係 い 説 明 る 2.1 Graph500ベ ン チ マ ー 概 要
Graph500 ， 大 規 模 エ メ ネ 対 BFS よ る 探 索 を 実 行 る パ ン ス ブ ー ェ
†
東 京 業 大 学
Tokyo Institute of Technology
††
東 京 業 大 学 IBM東 京 基 礎 研 究 所
Tokyo Institute of Technology / IBM-Research Tokyo
あ る 単 昷 間 処 理 数 ， 扱 え る 暷 大 問 題 キ ゜ ゲ 評 価 指 標 る 計 算
゜ ン ゾ ン ク ノ Top500パ ン ス ブ ー ェ い ，Graph500パ ン ス ブ ー ェ ， タ ー シ ゜ ン ゾ ン ク ノ パ ン ス ブ ー ェ あ る 扱 え る 問 題 キ ゜ ゲ ，エ メ ネ 頂 点 数=2
SCALE
あ る よ う SCALE 値 表 単 昷 間 処 理 数 ，TEPS (Traversed Edges Per Second) 値 表 例 え ，100万TEPS ，100万 個 を 持 連 結 エ メ ネ BFS
1 完 了 場 合 性 能 あ る
パ ン ス ブ ー ェ を 実 行 る ハ ュ エ メ ヘ ，(a)エ メ ネ タ ー シ 生 ，(b)計 算 る 暷 適 タ ー シ 構 変 換 ，(c)BFS よ る 探 索 ，(d)計 算 結 検 証 部 分 ら る パ ン ス ブ ー ェ 実 行 順 次 よ う い る 暷 初 (a),(b) よ り エ メ ネ タ ー シ を 構 築 ， エ メ ネ ら 始 点 を 64個 選 ぶ 次 ，64個 始 点 れ れ 対 順 番
，(c)BFS よ る 探 索 ，(d)計 算 結 検 証 を 行 う 複 数 始 点 ら 探 索 を 昷 行 う こ い 昷 間 を 計 測 パ ン ス ブ ー ェ る 部 分 ，(b) エ メ ネ タ ー シ 構
変 換 Kernel 1 ，(c) BFS よ る 探 索 Kernel 2 あ る (a) ， 数 頂 点 数 16 倍 る よ う ェ ュ ヅ ッ ィ ー エ メ ネ[3]を 生 る
， 無 向 辺 あ る こ こ 生 さ れ る タ ー シ 規 則 性 い 順 番 並 ん ， モ ケ ダ あ る (b) (a) 生 さ れ モ ケ ダ ら ，隣 接 行 列 CSR (Compressed Sparse Row)や ，CSC (Compressed Sparse Column) エ メ ネ タ ー シ 構 変 換 る (c) BFS ，BFS 辿 頂 点 軌 跡 あ るBFS木 を 出 力 る (d) ， こ BFS木 正 い う ス ゟ ッ ェ る こ ス ゟ ッ ェ ，BFS木 ャ ー ハ い こ ， 張 い る 頂 点 士 深 さ 差 1以 あ る こ ， 5 ャ ー ャ を 満 い る こ を ス ゟ ッ ェ る
Graph500モ ケ ダ 表 ，2011 11暻 モ ケ ダ 3回 目 る ，3回 目 ら モ ケ ダ 集 計 方 法 変 わ り ，2 回 目 問 題 キ ゜ ゲ メ ン キ ン エ を 決 い ，3 回 目 ら ，TEPS値 メ ン キ ン エ を 決 る よ う
2.2 Level-synchronized BFS
゚ ャ ガ モ ゲ ヘ : Level-synchronized BFS
1 for all vertex v in parallel do 2 | PRED[v]← -1;
3 | VISITED [v] ← 0;
4 PRED [r] ← 0 5 VISITED[v] ← 1 6 Enqueue(CQ , r) 7 While CQ != Empty do 8 | NQ ← empty
9 | for all u in CQ in parallel do 10 | | u ← Dequeue(CQ)
11 | | for each v adjacent to u in parallel do 12 | | | if VISITED [v] = 0 then
13 | | | | VISITED [v] ← 1; 14 | | | | PRED [v] ← u; 15 | | | | Enqueue(NQ, v) 16 | swap(CQ, NQ);
゚ ャ ガ モ ゲ ヘ Level-Synchronized BFS 擬 似 カ ー チ あ る ，BFS木 を 格 納 るPRED ，頂 点 訪 問 済 う を 格 納 るVISITEDを 初 期 化 る PRED[v] 頂 点v BFS木 け る 親 頂 点 を 表 初 期 値-1 BFS木 入 い い こ を 表 い る VISITED[v] 頂 点v 訪 問 済 う を 表 初 期 値0 訪 問 い い こ を 表 い る 次 ，BFS 始 点 る 頂 点 をCQ (Current Queue)
入 れ ， 探 索 を 開 始 る
探 索 い ，7~16 行 ャ ー ハ ヤ パ ャ 相 当 る こ ャ ー ハ 中 ，CQ 現 ヤ パ ャ 訪 問 る 頂 点 ，NQ (Next Queue) 次 ヤ パ ャ 訪 問 る 頂 点 格 納 さ れ い る 例 え ， ヤ パ ャ1 CQ 頂 点 γ 入 い る ，11, 12行 目
γ 隣 接 頂 点 訪 問 済 う ス ゟ ッ ェ さ れ ， 訪 問 い い 頂 点 NQ 格 納 さ れ る ヤ パ ャ 2 CQ こ れ ら 頂 点 格 納 さ れ い る こ る 9 行 目 for ，11行 目 for 並 列 化 可 能 ャ ー ハ あ る
Graph500 モ ネ ゙ ヤ ン ケ 実 装 ，OpenMP 書 れ 実 装 や ，MPI 書 れ 実 装 ，Cray 共 暼 ベ ペ モ 型 ハ ュ エ メ プ ン エ 環 境 用 実 装 ， 複 数 種 類 用 意 さ れ い る TSUBAME2.0 分 散 実 行 る ，MPI 書 れ 実 装 を 使 用 る MPI 書
れ 実 装 ， さ ら ゚ ャ ガ モ ゲ ヘ や 実 装 方 法 異 る4種 類 実 装 用 意 さ れ い る こ れ ら 実 装 ， 対 象 い る ハ ュ エ メ プ ン エ 環 境 や 分 散 方 法 異 る
，全 パ ー ケ る ゚ ャ ガ モ ゲ ヘ Level-synchronized BFSを 使 い る こ
゚ ャ ガ モ ゲ ヘ ， 各 ヤ パ ャ 深 さ い ， ヤ パ ャ 頂 点 を 処 理 ら ， 次 ヤ パ ャ 進 い う ゚ ャ ガ モ ゲ ヘ あ る
モ ネ ゙ ヤ ン ケ 実 装 MPI実 装 ， 基 本 的 Level-synchronized BFSを 実 装 い る ，エ メ ネ タ ー シ 分 散 方 法 い あ る モ ネ ゙ ヤ ン ケMPI実 装 処 理 方 い を 簡 単 理 解 る ，次 Level-synchronized BFS 疎 行 列 パ ェ ダ ャ 積 関 係 い 説 明 る
2.3 Level-synchronized BFSと 疎 行 列 ベ ト 積
Level-synchronized BFS 分 散 処 理 ，行 列 パ ェ ダ ャ 積 分 散 処 理 似 い る 行 列 パ ェ ダ ャ 積 ，x, yを パ ェ ダ ャ ，Aを 行 列 ，y=Axを 計 算 る こ あ る こ
こ ，Aを エ メ ネ 隣 接 行 列 る 要 素 値 ，対 応 る あ る 場 合1, い 場 合 0 あ る ，xをCQ (Current Queue) 相 当 る パ ェ ダ ャ る 頂 点 v∈CQ らx(v)=1, う い らx(v)=0 あ る こ こ ，x(v) パ ェ ダ ャx v番 目 値 あ る る ， 行 列 パ ェ ダ ャ 積 結 あ る パ ェ ダ ャy ら ，CQ 入 い る 各 頂 点 隣 接 頂 点 以 CQ 隣 接 頂 点 分 る こ れ ， 頂 点 v 対 応 る 値y(v) ゴ ュ け れ ， 頂 点v CQ 隣 接 頂 点 い る ら あ る CQ
隣 接 頂 点 分 る い う こ ，゚ ャ ガ モ ゲ ヘ 11行 目 頂 点v 分 る い う こ ， こ 行 列 パ ェ ダ ャ 積 ， ゚ ャ ガ モ ゲ ヘ 9~11 行 目 計 算 を こ る 実 際 ， モ ネ ゙ ヤ ン ケMPI 実 装 ， 行 列 パ ェ ダ ャ 積 よ う 方 法 ， CQ 隣 接 頂 点 を 計 算 い る
行 列 パ ェ ダ ャ 積 容 易 並 列 化 可 能 問 題 あ り ， 様 々 並 列 化 方 法 考 え ら れ る モ ネ ゙ ヤ ン ケMPI実 装 ，replicated-csr, replicated-csc, simple, one_sided
用 意 さ れ い る モ ネ ゙ ヤ ン ケ 実 装 使 用 い る ゚ ャ ガ モ ゲ ヘ ， 隣 接
行 列 分 割 方 法 い ， 大 く 分 け る こ る 隣 接 行 列 を 縦
分 割 る 方 法(replicated-csr, replicated-csc 当 ，図1 )， う 横 分 割 る 方 法(simple, one_sided 当 ， 図1 右) あ り 図 ，P個 ハ ュ コ ッ キ あ る 場 合
2 分 割 方 法 よ るLevel synchronized BFSを 行 列 パ ェ ダ ャ 積 表 あ る ハ ュ コ ッ キk 部 分 隣 接 行 列Akを 持 い る 隣 接 行 列 部 分 ， ハ ュ コ ッ キ 持 い る ，ハ ュ コ ッ キk 持 い い 図 中 パ ェ ダ ャx CQ
相 当 る あ る
，
図1 行 列 を 縦P個 分 割 ， 行 列 を 横P個 分 割 右
3. ン 実 装 ー ビ テ お け る 問 題
こ 章 ， モ ネ ゙ ヤ ン ケ MPI 実 装 replicated-csr, replicated-csc, simple, one_sided ゚ ャ ガ モ ゲ ヘ を 説 明 ， ゚ ャ ガ モ ゲ ヘ よ 引 起 こ さ れ る ケ ォ
ー メ ニ モ ゾ ゛ 問 題 い 述 る
3.1 ン 実 装: Replicated-csr, Replicated-csc
隣 接 行 列 を 縦 分 割 るreplicated-csrやreplicated-csc 以 ，両 方 合 わ replicated る ，CQ 全 体 を ， ハ ュ コ ッ キ カ ヌ ー る 各 ハ ュ コ ッ キ ， 自 分 持 い る 部 分 隣 接 行 列 を 使 ，CQ 隣 接 頂 点 を 探 ， 自 分 担 当 る 領 域
PRED, NQを 計 算 る
CQ を ， ハ ュ コ ッ キ カ ヌ ー る い う ， り ， 分 散 持 い るNQを ， ハ ュ コ ッ キ 送 信 る い う こ あ る CQやNQ 頂 点 ニ ッ ダ 表 こ 可 能 ， タ ー シ 大 く く ， 分 散 数 小 さ い 場 合 ，通 信 タ ー シ を く 抑 え る こ ，暼 効 計 算 方 法 る ，CQ
大 さ ， エ メ ネ 全 体 頂 点 数 比 例 る ， ハ ュ コ ケ あ り 通 信 タ ー シ エ メ ネ 全 体 頂 点 数 比 例 る よ ， 分 散 数 非 常 大 場 合 ， こ カ ヌ ー 膨 大 通 信 必 要 り ， 問 題 る
図2 weak-scaling け るreplicated テ ー チ あ り 通 信 タ ー シ
図2 replicated テ ー チ あ り 通 信 タ ー シ あ る 問 題 キ ゜ ゲ weak-scaling テ ー チ あ りScale 26 テ ー チ あ り ハ ュ コ ケ 計 算 場 合 理 論 値 あ る Weak-scaling ， テ ー チ 数 増 加 比 例 ， 問 題 キ ゜ ゲ 増 加 る ， 頂 点 数 増 加 る テ ー チ あ り 通 信 タ ー シ エ メ ネ 全 体 頂 点 数 比 例 増 え る ， 図2 よ う る よ ， ケ ォ ー ャ い こ 容 易 想 像 る
3.2 ン 実 装: simple, one_sided
隣 接 行 列 を 横 分 割 るsimple ，CQをP個 分 割 配 置 く NQ P分 割 さ れ い る ， 前 ヤ パ ャ 計 算 さ れ NQを CQ 使 え 良 い 各 ハ ュ コ ッ キ ， 分 割 さ れ CQ ， 自 分 持 い る 部 分 隣 接 行 列 ら ，CQ 隣 接 頂 点 を 探 CQ 隣 接 頂 点 を 使 PREDやNQを 更 新 る ，こ こ
見 CQ 隣 接 頂 点 ， 自 分 担 当 る 頂 点 あ れ ， ハ ュ コ ッ キ 担 当 る 頂 点 あ る 自 分 担 当 る 頂 点 自 分 処 理 ， ハ ュ コ ッ キ 担 当 る 頂 点 ， ハ ュ コ ッ キ 送 信 ， 処 理 ら う こ こ 送 信 さ れ るCQ 隣 接 頂 点 数 ， 暷 大 ， 送 信 元 ハ ュ コ ッ キ 持 い る 部 分 隣 接 行 列 数
る よ ， 通 信 タ ー シ テ ー チ 数 十 分 大 い 場 合 ， テ ー チ 数 関 係 く 一 定 る ， 縦 分 割 る replicated 通 信 る タ ー シ(CQ) 頂 点
ニ ッ ダ あ 対 ， 横 分 割 るsimple ，CQ 頂 点 ， 隣 接 頂 点 組 を 送 信 け れ ら い こ れ ，PRED 更 新 親 頂 点 CQ 頂 点 必 要 る あ る ，分 散 数 少 い 場 合 ，縦 分 割 るreplicated 方 通 信 タ ー シ 少 く る ，replicated 方 暼 利 あ る
図3 TSUBAME2.0 全 対 全 通 信 を 行 昷 通 信 度 one_sided 通 信 MPI one_sided操 作 を 使 用 る 実 装 あ る ，゚ ャ ガ モ ゲ ヘ
simple あ る 4. 2次 元 分 割 よ る ー 実 装
隣 接 行 列 を 横 分 割 る ，simple, one_sided ，replicated よ う 通 信 タ ー シ 問 題 い ，CQ 隣 接 頂 点 を 担 当 頂 点 送 信 る こ ろ ， テ ー チ テ ー チ 異 る タ ー シ を 送 信 る 全 対 全 通 信 必 要 る こ 通 信 大 規 模 分 散 さ 場 合 ， ケ ォ ー ャ さ る こ い こ れ 次 よ う ブ
゜ ェ ュ パ ン ス ブ ー ェ 結 ら 明 ら あ る
モ ネ ゙ ヤ ン ケ 実 装 分 割 方 法 ら 隣 接 行 列 を 次 元 分 割 方 法 あ る 前 章 述 り 1 次 元 分 割 分 割 方 法 ら ケ ォ ー ャ さ る こ い こ ， 隣 接 行 列 を2次 元 分 割 る ゚ ャ ガ モ ゲ ヘ 2次 元 分 割 [2] を 実 装
図3 ，TSUBAME2.0 全 対 全 通 信 を 行 場 合 ，通 信 度 あ る テ ー チ あ り4MPIハ ュ コ ケ MPI実 装 MVAPICH2 1.6[4] あ る 通 信 MPI_Alltoallvを 使 い ， こ 関 数 送 信 ト ッ ネ ゙ 64, 256, 1024MB 3種 類 大 さ ト ッ ネ ゙ を 入 力 さ 各 テ ー チ 各 テ ー チ 送 信 る タ ー シ ， ト ッ ネ ゙ 例 え 1024MB
，MPIハ ュ コ ケ 数 256 こ 場 合 ，テ ー チ 数 64 場 合 ，4MB る 図 ら ， 全 対 全 通 信 ケ ォ ー ャ い い こ 分 る 512 テ ー チ ，64MB 小 さ い ト ッ ネ ゙ 極 端 遅 く り ， ，1024MB い う 大 ト ッ ネ ゙ を 用 意 ， 32テ ー チ 場 合 比 度 1/4以 い る TSUBAME2.0 ヅ ッ ダ ワ ー ェ Infiniband よ るFat-Tree ， 理 論 ヌ ー ェ 性 能 さ れ れ ， テ ー チ 全 対 全 通 信 を 行 場 合 ， 度 生 い よ ， サ ネ ダ ゞ ゟ ゚ ア ー ト バ ッ チ よ る 度 大 く 影 響 い る 考 え ら れ る
4.1 ２ 次 元 分 割 よ る 分 散BFS ゴ ム
ハ ュ コ ッ キ をPRC 2次 元 ベ ッ ク ュ(mesh) 配 置 る こ ベ ッ ク ュ 行 を ハ ュ コ ッ キ 行 ，列 を ハ ュ コ ッ キ 列 呼 ぶ こ る 隣 接 行 列 を 図4 よ う
個 行 C個 列 分 割 ，ハ ュ コ ッ キ ，隣 接 行 列
(C) Cノ ュ ッ ェ を 担 当 る 頂 点 ，
C R j)
(i, A(1)i,j ~Ai,j C
R 個 ノ ュ ッ ェ 分 割 ，ハ ュ コ ッ キ ， 番 目 ノ ュ ッ ェ を 担 当 る
j)
(i, j Ri
ヤ パ ャ ，Expand Fold 呼 れ る 段 階 通 信 を 行 う 各 ヤ パ ャ 行 う 操 作 い 説 明 る 各 ハ ュ コ ッ キ 自 分 担 当 る 頂 点 ノ ュ ッ ェ CQを
ハ ュ コ ッ キ 列 ハ ュ コ ッ キ 送 信 る こ れ をExpand い う Expand 次 元 分 割 縦 分 割 よ う ，CQを カ ヌ ー る 通 信 あ る ，隣 接 行 列 横 C 個 分 割 さ れ い る ， 通 信 ， ハ ュ コ ッ キ 列 ハ ュ コ ッ キ け 行 う 次 ， 各 ハ ュ コ ッ キ CQ 各 ハ ュ コ ッ キ 持 い る 部 分 隣 接 行 列 ら ，CQ 隣 全 対 全 通 信 必 要 るsimple, one_sided ケ ォ ー ャ い
接 頂 点 を 探 PREDやNQを 更 新 る ，CQ 隣 接 頂 点 を ， 頂 点 担 当 ハ ュ コ ッ キ 送 信 る こ 通 信 をFold い う PREDを 更 新 る ，親 頂 点 必 要
，Fold ，CQ 隣 接 頂 点 ，親 頂 点 CQ 頂 点 組 を 送 信 る こ る Fold 次 元 分 割 横 分 割 よ う ，CQ 隣 接 頂 点 を 担 当 ハ ュ コ ッ キ 送 信 る 通 信 ， 次 元 分 割 ，隣 接 行 列 分 割 方 法 ら ，Fold 通 信 を 行 う 必 要 あ る 相 手 ， ハ ュ コ ッ キ 行 ハ ュ コ ッ キ る こ よ う ， 次 元 分 割 種 類 分 割 方 法 を 合 わ 方 法 あ り ，C=1 縦 分 割 図 ，
R=1 横 分 割 図 右 る
図4 隣 接 行 列 次 元 分 割
次 元 分 割 利 点 ， 通 信 絡 ハ ュ コ ッ キ 数 少 い こ あ る 次 元 分 割
， 種 類 分 割 方 法 ら ， 全 対 全 通 信 必 要 対 ， 次 元 分 割 場 合 ，Expand 列 テ ー チ(R-1)ハ ュ コ ッ キ ，Fold 行 テ ー チ(C-1) ハ ュ コ ッ キ 通 信 を 行 わ い よ ， 通 信 る ハ ュ コ ッ キ 数 を 少 く る こ
， 大 規 模 分 散 可 能 る 4.2 実 装 方 法
Expand 通 信 ，CQをMPI Allgatherを 使 実 装 こ れ ，モ ネ ゙ ヤ ン ケ
実 装 replicated 使 わ れ い る 方 法 あ る Fold 通 信 ，CQ 隣 接 頂 点 を 探
，送 信 る 送 信 側 ，頂 点 を 受 信 VISITEDやPRED, NQを 更 新 る 受 信 側 シ ケ ェ 分 解 ， こ れ ら を 並 列 化 さ ら ， 通 信 を 非 期 行 い る こ れ ら よ り 高 効 率 処 理 を 実 現 ゚ ャ ガ モ ゲ ヘ ， 実 装 ゚ ャ ガ モ ゲ ヘ 擬 似 カ ー チ あ る
゚ ャ ガ モ ゲ ヘ : 2次 元 分 割 よ るBFS 実 装
1 for all vertex lu in NQ do 2 | NQ[lu] ← 0
3 NQ [root] ← 1 4 fork;
5 for level = 1 to
6 | CQ ← all gather NQ in this processor-column; 7 | parallel Task A and Task B
8 | Synchronize;
9 | if NQ =
for all processors then 10 | | terminate loop;11 join;
Task A (送 信 側)
1 for all vertex gu in CQ parallel do (contiguous access) 2 | if CQ [gu] = 1 then
3 | for each local vertex v adjacent to gu do
4 | | send tuple (gu, v) to the processor which owns vertex v
Task B (受 信 側)
1 for all received tuple (gu, v) parallel do 2 | if visited[v] = 0 then
3 | | PRED[v] ← gu; 4 | | VISITED[v] ← 1; 5 | | NQ [v] ← 1;
，OpenMP を 使 ハ ュ コ ケ 内 ブ ャ ス ケ ヤ ッ チ 化 行 い ，MPI OpenMP デ ゜ ノ モ ッ チ 並 列 実 装
5. 性 能 評 価
こ 章 ，東 大 ケ ド カ ンTSUBAME2.0 性 能 評 価 結 い 述 る TSUBAME2.0 ，1400以 テ ー チ Fat-Tree よ る ネ ャ ト ゜ コ ェ ク ョ ン Infiniband ヅ ッ ダ ワ ー ェ 接 続 さ れ い る 各 テ ー チ ，Intel CPU Xeon 5670 2.93GHz
Westmere EP,，6カ ゚ ，256-KB L2 キ ホ ッ ク ュ, 12-MB L3) ，NVIDIA M2050 GPU (Fermi) ，48GB ベ ペ モ 搭 載 さ れ い る 通 信 ，各 テ ー チ Infiniband QDR モ ン ェ 使 用 可 能 ， 合 計80Gbps 通 信 ト ン チ 幅 を 備 え い る
暷 大512テ ー チ 使 用 実 験 ，GPU 使 用 い い TSUBAME2.0 1テ ー チ あ り 物 理 カ ゚12個 ，SMTを 暼 効 る 仮 想 的 24カ ゚ る 1 テ ー チ 24 カ ゚ ， 各 ハ ュ コ ケ 均 等 割 り 振 gcc 4.3.4 (OpenMP 2.5), MVAPICH2 1.6 [4]を 使 用 比 較 る モ ネ ゙ ヤ ン ケ 実 装 ，執 筆 昷 点 暷 新 version 2.1.4 あ る
以 実 験 ， 次 元 分 割 ハ ュ コ ッ キ 配 置RC 表 よ う R C 値 通 信 タ ー シ 関 係 ら る く 近 い 値 る よ う あ る R,C 使 用 テ ー チ 数 関 係 無 く ，MPIハ ュ コ ケ 数 ら 決 定
ハ ュ コ ケ 数 1 2 4 8 16 32 64 128 256 512 1024
R 1 1 2 2 4 4 8 8 16 16 32
C 1 2 2 4 4 8 8 16 16 32 32
， 問 題 キ ゜ ゲ ， weak-scaling テ ー チ あ りScale 26
り ，実 行 テ ー チ 数 ，例 え テ ー チ 場 合Scale 26， テ ー チ 場 合Scale 27， テ ー チ 場 合Scale 28 あ る こ 問 題 キ ゜ ゲ タ ゛ ケ ェ ケ ダ ヤ ー グ を 使 用
い 場 合 暷 大 キ ゜ ゲ あ る
図5 次 元 分 割 モ ネ ゙ ヤ ン ケ 実 装 を 比 較 1～128テ ー チ
図6 次 元 分 割 モ ネ ゙ ヤ ン ケ 実 装 を 比 較 1～512テ ー チ
図7 テ ー チ あ り 通 信 タ ー シ 比 較
図 5, 6 次 元 分 割 モ ネ ゙ ヤ ン ケ 実 装 比 較 あ る 横 軸 テ ー チ 数 縦 軸 TEPS (GE/s) あ る モ ネ ゙ ヤ ン ケ 実 装 replicated-csr, replicated-csc 次 元 分 割
two-dim ， テ ー チ あ り2MPIハ ュ コ ケ 実 行 ，モ ネ ゙ ヤ ン ケ 実 装 simple テ ー チ あ り16MPIハ ュ コ ケ 実 行 モ ネ ゙ ヤ ン ケ 実 装 one_sided 細 粒 度 one sided操 作 を 頻 繁 実 行 る 実 装 い る 使 用 MPI実 装
こ よ う 操 作 暷 適 化 さ れ い い 極 端 性 能 く る モ ネ
゙ ヤ ン ケ 実 装 one_sided 実 験 ら 除 外 図7 テ ー チ あ り 通 信 タ ー シ
を replicated 次 元 分 割 比 較 エ メ ネ あ る replicated 通 信 タ ー シ 理 論 値 を 算 出
モ ネ ゙ ヤ ン ケ 実 装 ， タ ー シ い 部 分 ゠ メ ー 計 測 こ ろ あ る Simple テ ー チ 数 を 大 く る ベ ペ モ 不 足 ゠ メ ー り ，Replicated-csr Scale 32 validation゠ メ ー り ，Scale 33以 segmentation fault，Replicated-csc Scale 34以 construction昷 ゠ メ ー る 原 因 細 い 掴 い い
次 元 分 割 実 装 ，モ ネ ゙ ヤ ン ケ 実 装 simple 倍 程 度 度 出 い る こ れ ， 送 信 処 理 受 信 処 理 並 列 化 や ，OpenMP よ る ハ ュ コ ケ 内 並 列 化 効 よ る あ る 次 元 分 割 実 装 ，モ ネ ゙ ヤ ン ケ 実 装 replicated 比 る ，性 能 い ， こ れ 3.1章 述 通 り ，replicated ゚ ャ ガ モ ゲ ヘ テ ー チ 数
小 さ い 場 合 通 信 タ ー シ を 小 さ く る こ ， 暼 利 ら あ る 図8 ら 分 る よ う ，replicated 優 性 テ ー チ 数 増 え る 急 激 ， 通 信 タ ー シ 512テ ー チ 次 元 分 割 逆 転 る 実 際 ，図 らreplicated-csc テ ー チ 数128 既 性 能 限 界 見 え 始 い る 図7 ら ， 次 元 分 割 ， テ ー チ 数 増 加 従 徐 々 テ ー チ あ り 通 信 タ ー シ 大 く る ， 増 加 幅
小 さ く ， 十 分 ケ ォ ー ャ 可 能 あ る こ 分 る
次 元 分 割 ，512テ ー チ ，Scale 36を 計 算 ，TEPS値22.8GE/s 性 能 を 512テ ー チ こ れ け 性 能 を 出 TSUBAME2.0 ，Graph500モ ケ ダ ケ ド カ ン 比 較 エ メ ネ 処 理 向 い い る 言 え る
6. 議 論
図8 全 テ ー チ 合 計 均 通 信 タ ー シ ヤ ー ダ 7. 関 連 研 究
エ メ ネ 処 理 中 ，基 本 るBFS ，様 々 ブ ク ン 暷 適 化 研 究 さ れ い る 本 研 究 使 用 次 元 分 割 ，Andy Yooら[2] 元 々 BlueGene/L 実 装
゚ ャ ガ モ ゲ ヘ あ ， 彼 ら 提 案 実 装 ， 通 信 タ ー シ 削 減 要 視 さ れ い ，BFS 十 分 暷 適 化 さ れ い る 言 え い David A.ら[5] ， 共 暼 ベ ペ モ 型 ブ ク ン あ る Cray MTA-2 BFS st-connectivity を 暷 適 化 Virat Agarwalら[6] ，BFSをIntel Nehalem CPU よ る 共 暼 ベ ペ モ 型 ブ ャ ス ハ ュ コ ッ キ 暷 適 化 Guojing Congら[7] ，BFSをPGAS言 語 暷 適 化
TSUBAME2.0 ， ケ ド カ ン 比 較 エ メ ネ 処 理 パ ン ス ブ ー ェ 高 い ケ カ ゚ を 出 や い 理 由 ， ヅ ッ ダ ワ ー ェ ダ フ ュ グ あ る 物 理 ク プ ュ ヤ ー ク ョ ン ， 隣 接 テ ー チ 間 通 信 視 さ れ る こ 多 い ， エ メ ネ 処 理 れ テ ー チ 間 通 信 度
要 あ る Graph500モ ケ ダ あ る ブ ク ン 多 く ，BlueGeneやCray ， ヅ ッ ダ ワ ー ェ ダ フ ュ グ 次 元 ダ ー メ ケ ブ ク ン 多 い ， 次 元 ダ ー メ ケ ブ ク ン
れ テ ー チ 間 通 信 カ ケ ダ 大 い TSUBAME2.0 ヅ ッ ダ ワ ー ェ ダ フ ュ グ Fat-tree あ り れ テ ー チ 間 通 信 隣 接 テ ー チ 間 変 わ ら い エ メ ネ 処 理 向 い い る
エ メ ネ 処 理 高 化 関 る 研 究 ゚ ェ コ メ ヤ ー シ あ るGPU 暷 適 化 [12,13] やCell/BE 暷 適 化 [14] 研 究 さ れ い る
大 規 模 エ メ ネ 処 理 を 一 般 化 ， 様 々 ゚ ャ ガ モ ゲ ヘ を 処 理 る こ る 処 理 系 Pregel [8] や 疎 行 列 パ ェ ダ ャ 積 表 る エ メ ネ 処 理 をHadoop 実 現 PEGASUS [9]，GBASE[10] 提 案 さ れ い る
8. ま と め と 今 後 展 望 図8 ，全 テ ー チ 合 計 通 信 タ ー シ をBFS 実 行 昷 間 割 ， 均 通 信 タ ー シ
ヤ ー ダ あ る 実 際 512 テ ー チ ， モ ニ ゚ 通 信 度 い る 分 る 512テ ー チ 使 用 場 合 ， テ ー チ あ り1.4GB/s を 超 え る 度 出 い る TSUBAME2.0 エ メ ネ 処 理 向 い い る い う こ 分 る
本 論 文 Graph500 パ ン ス ブ ー ェ を 大 規 模 分 散 環 境 ケ ォ ー ャ さ る ， 次 元 分 割 よ る BFS を 実 装 Graph500 モ ネ ゙ ヤ ン ケ カ ー チ ， 大 規 模 分 散 環 境 ケ ォ ー ャ い 次 元 分 割 よ る 実 装 ，TSUBAME2.0 512テ ー チ Scale 36 を 計 算 ，TEPS 値22.8GE/sを こ れ よ り ，2次 元 分 割 ら 大 規 模 ケ ォ ー ャ さ る こ 可 能 い う こ 分
々 執 筆 昷 点 ， 次 元 分 割 実 装 通 信 タ ー シ 縮 や 頂 点 並 び 暶 え 暷 適 化 よ り ，TSUBAME2.0を1366テ ー チ 使 用 実 験 ，TEPS値103GE/s を い る こ 性 能 執 筆 昷 点 暷 新 Graph500モ ケ ダ June 2011 TEPS値 メ ン キ ン エ ケ カ ゚ 倍 を 超 え る 性 能 あ る こ れ ら 細 ， 別
機 会 表 る
謝 辞 本 研 究 ， 学 技 術 振 興 機 構(JST) 戦 略 的 創 研 究 推 進 事 業 CREST け る 研 究 領 域 フ ケ ダ ヒ シ ケ ォ ー ャ 高 性 能 計 算 資 る ク ケ ゾ ヘ サ ネ ダ ゞ ゟ ゚ 技 術 創 出 よ る あ る TSUBAME2.0エ メ ン チ ス ホ ヤ ン グ 協 力 い い 方 々 感 謝 意 を 表 る
参 考 文 献
1) Graph500 : http://www.graph500.org/
2) Andy Yoo, Edmond Chow, Keith Henderson, William McLendon, Bruce Hendrickson, and Umit Catalyurek. 2005. A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L. In Proceedings of the 2005 ACM/IEEE conference on Supercomputing (SC '05). IEEE Computer Society, Washington, DC, USA.
3) J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos, "Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication," in Conf. on Principles and Practice of Knowledge Discovery in Databases, 2005.
4) MVAPICH2: http://mvapich.cse.ohio-state.edu/
5) David A. Bader and Kamesh Madduri. 2006. Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2. In Proceedings of the 2006 International Conference on Parallel Processing (ICPP '06). IEEE Computer Society, Washington, DC, USA, 523-530
6) Virat Agarwal, Fabrizio Petrini, Davide Pasetto, and David A. Bader. 2010. Scalable Graph Exploration on Multicore Processors. In Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC '10). IEEE Computer Society, Washington, DC, USA, 1-11.
7) Guojing Cong, George Almasi, and Vijay Saraswat. 2010. Fast PGAS Implementation of Distributed Graph Algorithms. In Proceedings of the 2010 ACM/IEEE International Conference for High
Performance Computing, Networking, Storage and Analysis (SC '10). IEEE Computer Society, Washington, DC, USA, 1-11.
8) Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 international conference on Management of data (SIGMOD '10). ACM, New York, NY, USA, 135-146.
9) U. Kang, Charalampos E. Tsourakakis, and Christos Faloutsos. 2009. PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations. In Proceedings of the 2009 Ninth IEEE International
Conference on Data Mining (ICDM '09). IEEE Computer Society, Washington, DC, USA, 229-238. 10) U. Kang, Hanghang Tong, Jimeng Sun, Ching-Yung Lin, and Christos Faloutsos. 2011. GBASE: a scalable and general graph management system. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '11). ACM, New York, NY, USA, 1091-1099. 11) Pawan Harish and P. J. Narayanan. 2007. Accelerating large graph algorithms on the GPU using CUDA. In Proceedings of the 14th international conference on High performance computing (HiPC'07), Srinivas Aluru, Manish Parashar, Ramamurthy Badrinath, and Viktor K. Prasanna (Eds.). Springer-Verlag, Berlin, Heidelberg, 197-208.
12) Pawan Harish and P. J. Narayanan. 2007. Accelerating large graph algorithms on the GPU using CUDA. In Proceedings of the 14th international conference on High performance computing (HiPC'07), Srinivas Aluru, Manish Parashar, Ramamurthy Badrinath, and Viktor K. Prasanna (Eds.). Springer-Verlag, Berlin, Heidelberg, 197-208.
13) Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. 2011. PHAST: Hardware-Accelerated Shortest Path Trees. In Proceedings of Parallel & Distributed Processing Symposium (IPDPS), 2011 IEEE International. Anchorage, AK, USA, 921 – 931.
14) Daniele Paolo Scarpazza, Oreste Villa, and Fabrizio Petrini. 2008. Efficient Breadth-First Search on the Cell/BE Processor. IEEE Trans. Parallel Distrib. Syst. 19, 10 (October 2008), 1381-1395.
15) Toyotaro Suzumura, Koji Ueno, Hitoshi Sato, Katsuki Fujisawa and Satoshi Matsuoka,
"Performance Evaluation of Graph500 on Large-Scale Distributed Environment", IEEE IISWC 2011 ( IEEE International Symposium on Workload Characterization) , 2011/11, Austin, TX, US
