NETAL : HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY(<Special Issue>SCOPE (Seminar on Computation and OPtimization for new Extensions))
-
- Yasui Yuichiro
- Chuo University
-
- Fujisawa Katsuki
- Chuo University
-
- Goto Kazushige
- Microsoft Corporation
-
- Kamiyama Naoyuki
- Kyushu University
-
- Takamatsu Mizuyo
- Chuo University
書誌事項
- タイトル別名
-
- NETAL : HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY
この論文をさがす
説明
The use of network analysis has increased in various fields. In particular, a lot of attention has been paid to centrality metrics using shortest paths, which require a comparatively smaller amount of computation, and the global characteristic features within the network. While theoretical and experimental progress has enabled greater control over networks, large amounts of computation required for dealing with large-scale networks is a major hurdle. This research is on high-performance network analysis considering the memory hierarchy in a computer; it targets extremely important kernel types called shortest paths and centrality. Our implementation, called NETAL (NETwork Analysis Library), can achieve high efficiency in parallel processing using many-core processors such as the AMD Opteron 6174, which has the NUMA architecture. We demonstrated through tests on real-world networks that NETAL is faster than previous implementations. In the all-pairs shortest paths for the weighted graph USA-road-d.NY.gr (n=264K, m=734K), our implementation solved the shortest path distance labels in 44.4 seconds and the shortest paths with multiple predecessors in 411.2 seconds. Compared with the 9th DIMACS benchmark solver, our implementation is, respectively, 302.7 times and 32.7 times faster. NETAL succeeded in solving the shortest path distance labels for the USA-road-d.USA.gr (n=24M, m=58M) without preprocessing in 7.75 days. Numerical results showed that our implementation performance was 432.4 times that of the Δ-stepping algorithm and 228.9 times that of the 9th DIMACS benchmark solver. Furthermore, while GraphCT took 18 hours to compute the betweenness of web-BerkStan, our implementation computed multiple centrality metrics (closeness, graph, stress, and betweenness) simultaneously within 1 hour. A performance increase of 2.4-3.7 times compared with R-MAT graph was confirmed for SSCA#2.
収録刊行物
-
- 日本オペレーションズ・リサーチ学会論文誌
-
日本オペレーションズ・リサーチ学会論文誌 54 (4), 259-280, 2011
公益社団法人 日本オペレーションズ・リサーチ学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282679086600832
-
- NII論文ID
- 110008682673
- 110008897245
-
- NII書誌ID
- AN10096105
-
- ISSN
- 21888299
- 04534514
-
- NDL書誌ID
- 023392154
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- NDLサーチ
- Crossref
- CiNii Articles
- OpenAIRE
-
- 抄録ライセンスフラグ
- 使用不可
