NUMAを考慮した並列幅優先探索

全文

(1)情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2014-AL-147 No.8 2014/3/3. NUMA を考慮した並列幅優先探索安井雄一郎中央大学 & JST CREST [email protected]. Abstract—本発表では, NUMA アーキテクチャを有する計算機上で高い性能を示す幅優先探索について説明する. 提案手法は汎用的なグラフ分割手法を用いて, プロセッサソケットと対となるローカルメモリを考慮し, 局所性を高めることに成功している. 本研究で開発した実装は, HPC 分野において注目されている幅優先探索の性能を用いたベンチマーク Graph500 の 1 ノード最高性能を, 幅優先探索の省電力性能を用いたベンチマーク Green Graph500 では世界 1 位をそれぞれ獲得している.. I. BFS と G RAPH 500, G REEN G RAPH 500 近年, グラフを用いた解析手法は様々な分野で盛んに研究されており, 中でも幅優先探索 (Breath-first search; BFS) は基本的かつ重要なグラフ処理である. Graph500 ベンチマーク1 は BFS の探索性能指標を用いて計算機の不連続なメモリアクセス性能の評価を目的として設計が行われ, 2010 年 11 月から開始され半年毎に更新される. このベンチマークでは 2 種類のパラメータ SCALE と edgefactor (=m/n, デフォルトでは 16) を入力として手順 (a), (b), (c) から構成される. a) 点数 n=2SCALE , 枝数 m=n · edgefactor となる無向グラフ Kronecker graph の枝リストを生成する. b) 生成した枝リストからグラフ表現を構築する. c) 次の手順を 64 回繰り返す; 構築したグラフ表現に対する BFS を行い, 1 秒辺りの探索枝数 (traversed edges per second; TEPS) を算出する. リストの順位は (c) で得られる 64 個の TEPS 値の中央値により決定される. また Green Graph500 ベンチマーク2 では, 消費電力あたりの Graph500 における TEPS 値となる電力性能指標 TEPS/W によりリストの順位を決定する.. II. NUMA を考慮した幅優先探索の高速化近年, BFS に対する並列計算を考慮した高速なアルゴリズムとして, 直径の小さいグラフに対して効率的に動作する Direction-optimized BFS [1] が注目されている. このアルゴリズムでは, 探索済みの点集合から未探索の隣接点集合を発見するという従来手法である Top-down 探索と, 未探索の隣接点集合から探索済みの点集合を発見する Bottom-up 探索を組み合わせて, 点数 228 , 枝数 232 からなる Kroncker graph に対し 4-way Intel Xeon E7-8870 を用いて 5.1 GTEPS を達成している. 我々は Direction-optimized BFS 上での主要なボトルネック箇所となる隣接枝の探索に対し, NUMA アーキテク 1 Graph500: 2 Green. http://www.graph500.org. Graph500: http://green.graph500.org.. ⓒ 2014 Information Processing Society of Japan. 藤澤克樹中央大学 & JST CREST [email protected]. チャを考慮した効率的なアルゴリズム NUMA-optimized BFS を開発した [2]. 提案手法では, NUMA (Non-uniform memory access) アーキテクチャのプロセッサを有する計算機上の実行を想定し, プロセッサと対となるローカルメモリと, 他のプロセッサと対となるリモートメモリへのデータアクセスを制御し, コストの大きなリモートメモリへのアクセスを大きく削減している. なお, 我々の実装は点数 226 , 枝数 230 からなる Kroncker graph に対して先行研究と同等の計算機上 4-way Intel Xeon E5-4640 で 11.2 GTEPS を達成し, 2.2 倍の高速化を達成した (Table I). Table I 先行研究の BFS 性能 Authors Reference Beamer et al. [1] Yasui et al. [2]. Base architecture (p) Xeon E5-4640 (16×4) Xeon E7-8870 (20×4) Xeon E5-4640 (16×4). SCALE 26 28 26. GTEPS 0.1 5.1 11.2. 加えて我々は NUMA-optimized BFS に対して更なる高速化手法を適用し, Graph500 list (Nov. 2013) において, SGI Altix UV1000 (one-rack) 上で 1 ノード最速となる 37.66 GTEPS を, 4-way Xeon E5-4650 2.7GHz 上で 1 サーバ最速となる 31.65 GTEPS を, それぞれ達成した. また SONY 製スマートフォン Xperia-A-SO-04E を用いて, Green Graph500 list (Nov. 2013) 上で最高の電力性能値 153.17 MTEPS/W を達成した (Table II). G RAPH 500. LIST. Table II (N OV. 2013) と G REEN G RAPH 500 における BFS 性能. Machine spec. SONY Xperia-A-SO-04E ASUS NEXUS7 (2013) 4-way Xeon E5-4640 2.4GHz 4-way Xeon E5-4650 2.7GHz SGI Altix UV1000 (one-rack). SCALE 20 20 27 27 30. LIST. GTEPS 0.478 0.534 29.034 31.648 37.659. (N OV. 2013). MTEPS/W 153.17 129.63 45.43 41.01 1.89. R EFERENCES [1] S. Beamer, K. Asanovi´c, and D. A. Patterson: Directionoptimizing breadth-first search, Proc. ACM/IEEE Int. Conf. High Performance Computing, Networking, Storage and Analysis (SC12), IEEE Computer Society, 2012. [2] Y. Yasui, K. Fujisawa, and K. Goto: “NUMA-optimized Parallel Breadth-first Search on Multicore Single-node System,” Proc. ACM/IEEE Int. Conf. BigData 2013, IEEE Computer Society, 2013.. 1.

(2)