Home >

news ヘルプ

論文・著書情報


タイトル
和文:計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL 
英文: 
著者
和文: 安井 雄一郎, 藤澤 克樹, 佐藤 仁, 鈴村 豊太郎, 後藤 和茂.  
英文: 安井 雄一郎, Katsuki Fujisawa, 佐藤 仁, 鈴村 豊太郎, 後藤 和茂.  
言語 Japanese 
掲載誌/書名
和文:情報処理学会研究報告. [ハイパフォーマンスコンピューティング] 
英文: 
巻, 号, ページ Vol. 2011    No. 21    pp. 1-10
出版年月 2011年10月 
出版者
和文:一般社団法人情報処理学会 
英文: 
会議名称
和文: 
英文: 
開催地
和文: 
英文: 
アブストラクト 様々な分野においてネットワーク解析に対する期待は高まりを見せているものの,非常に大規模なネットワークを扱うための計算量が課題とされている.そこで我々は,一般的な計算機環境上での最短路問題と中心性指標に対する,計算機のメモリ階層構造を考慮した高速計算手法を提案し,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 倍の性能を示している.

©2007 Institute of Science Tokyo All rights reserved.