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
Bibliographic Information
- Other Title
-
- NETAL : HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY
Search this article
Abstract
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.
Journal
-
- Journal of the Operations Research Society of Japan
-
Journal of the Operations Research Society of Japan 54 (4), 259-280, 2011
The Operations Research Society of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390282679086600832
-
- NII Article ID
- 110008682673
- 110008897245
-
- NII Book ID
- AA00703935
-
- ISSN
- 21888299
- 04534514
-
- NDL BIB ID
- 023392154
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- NDL
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed