計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL

The use of network analysis has increased in various fields. The large amounts of computation required for dealing with large-scale networks is a major hurdle. We propose an efficient multithreaded computation which considers computer memory hierarchy on general computing environments to solve the shortest paths and the centrality metrics. Our implementation, called NETAL (NETwork Analysis Library), configures the processor core and local memory allocation (affinity), to avoid computational resource request conflicts by considering the difference in distances between processor cores and the RAM within the NUMA architecture of the AMD Opteron 6174. We demonstrated through tests on real-world networks that NETAL is faster than previous implementations. NETAL succeeded in solving the exact shortest path distance table 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 reference solver. Furthermore, while it took GraphCT 21 days to compute the exact betweenness of USA-road-d.LKS.gr, 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.