計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリ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 倍の性能を示している.
収録刊行物
-
- 情報処理学会研究報告. [ハイパフォーマンスコンピューティング]
-
情報処理学会研究報告. [ハイパフォーマンスコンピューティング] 2011 (21), 1-10, 2011-11-21
一般社団法人情報処理学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1571135652044839424
-
- NII論文ID
- 110008690463
-
- NII書誌ID
- AN10463942
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles