NETAL : HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY(<Special Issue>SCOPE (Seminar on Computation and OPtimization for new Extensions))

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

著者

• Fujisawa Katsuki

  Chuo University

• Yasui Yuichiro

  Chuo University

• Goto Kazushige

  Microsoft Corporation

• Kamiyama Naoyuki

  Kyushu University

• Takamatsu Mizuyo

  Chuo University

• Fujisawa Katsuki

  Chuo Univ. Tokyo Jpn

関連論文

• SDPA PROJECT : SOLVING LARGE-SCALE SEMIDEFINITE PROGRAMS(the 50th Anniversary of the Operations Research Society of Japan)
• NETAL : HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY(SCOPE (Seminar on Computation and OPtimization for new Extensions))
• MATROID INTERSECTION WITH PRIORITY CONSTRAINTS

スポンサーリンク