NETAL: High-Performance Implementation of NETwork Analysis Library Considering Computer Memory Hierarchy

Bibliographic Information

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

Search this article

Abstract

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.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 2011 (21), 1-10, 2011-11-21

    Information Processing Society of Japan (IPSJ)

Keywords

Details

  • CRID
    1571135652044839424
  • NII Article ID
    110008690463
  • NII Book ID
    AN10463942
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top