研究日誌。

大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。

Fast & Energy-Efficient Breadth-First Search on a Single NUMA System

2014-04-15 10:37:19 | Weblog
こちらでも紹介いただいていますが、ISC14 (International Supercomputing Conference) に投稿していた論文が採択されました。ISC14 プログラムも公開されています。

内容は Graph500 (Nov. 2013) と Green Graph500 (Nov. 2013) での成果をまとました。
・我々の既存研究 Hybrid BFS + NUMA を更に改善 (2.68 倍)
・実行時間の大部分を占めている Bottom-up での探索枝削減と、CSR グラフに対する in-direct アクセスの削減
・実ネットワークに対する計算機実験
・SGI Altix UV1000 上での性能解析
・Intel Xeon サーバや、Android device 上での電力性能解析

Title:
Fast & Energy-Efficient Breadth-First Search on a Single NUMA System

Authors:
Yuichiro Yasui, Chuo University & JST CREST
Katsuki Fujisawa, Chuo University & JST CREST
Yukinori Sato, JAIST & JST CREST

Abstract:
Breadth-first search (BFS) is an important graph analysis kernel. The Graph500 benchmark measures a computer's BFS performance using the traversed edges per second (TEPS) ratio. Our previous nonuniform memory access (NUMA)-optimized BFS reduced memory accesses to remote RAM on a NUMA architecture system; its performance was 11 GTEPS (giga TEPS) on a 4-way Intel Xeon E5-4640 system. Herein, we investigated the computational complexity of the bottom-up, a major bottleneck in NUMA-optimized BFS. We clarify the relationship between vertex out-degree and bottom-up performance. In November 2013, our new implementation achieved a Graph500 benchmark performance of 37.66 GTEPS (fastest for a single node) on an SGI Altix UV1000 (one-rack) and 31.65 GTEPS (fastest for a single server) on a 4-way Intel Xeon E5-4650 system. Furthermore, we achieved the highest Green Graph500 performance of 153.17 MTEPS/W (mega TEPS per watt) on an Xperia-A SO-04E with a Qualcomm Snapdragon S4 Pro APQ8064.


最新の画像もっと見る

コメントを投稿