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

書誌事項

タイトル別名
  • NETAL: High-Performance Implementation of NETwork Analysis Library Considering Computer Memory Hierarchy

この論文をさがす

抄録

様々な分野においてネットワーク解析に対する期待は高まりを見せているものの,非常に大規模なネットワークを扱うための計算量が課題とされている.そこで我々は,一般的な計算機環境上での最短路問題と中心性指標に対する,計算機のメモリ階層構造を考慮した高速計算手法を提案し,NETAL (NETwork Analysis Library) として実装した.NETAL は NUMA アーキテクチャを考慮して,計算機資源要求の衝突を回避する affinity 設定を行なっている.実ネットワークに対する数値実験に用いて,先行研究と比べ最も高速であることを示した.前処理を必要としない NETAL は,道路ネットワーク USA-road-d.USA.gr に対する全対全最短路長計算を 7.75 日で計算することに成功した.これは Δ-stepping algorithm の 432.4 倍,9th DIMACS 参照実装の 228.9 倍の性能に相当する.さらに,GraphCT を用いて 21 日間必要とする USA-road-d.LKS.gr に対する betweenness 計算は,我々の実装では複数の中心性指標 closeness,graph,stress,betweenness を同時に計算し 1 日で終了する.SSCA#2 を用いた R-MAT グラフに対する betweenness 計算に対しても我々の実装は 2.4-3.7 倍の性能を示している.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1571135652044839424
  • NII論文ID
    110008690463
  • NII書誌ID
    AN10463942
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ