計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
スポンサーリンク
概要
- 論文の詳細を見る
様々な分野においてネットワーク解析に対する期待は高まりを見せているものの,非常に大規模なネットワークを扱うための計算量が課題とされている.そこで我々は,一般的な計算機環境上での最短路問題と中心性指標に対する,計算機のメモリ階層構造を考慮した高速計算手法を提案し,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-11-21
著者
-
藤澤 克樹
中央大学
-
安井 雄一郎
中央大学
-
安井 雄一郎
中央大学理工学研究科経営システム工学専攻
-
佐藤 仁
東京工業大学
-
鈴村 豊太郎
東京工業大学
-
藤澤 克樹
東京電機大学:産業技術総合研究所
-
佐藤 仁
東京工業大学学術国際情報センター
-
安井 雄一郎
中央大学|独立行政法人科学技術振興機構CREST
-
藤澤 克樹
中央大学|独立行政法人科学技術振興機構CREST
-
後藤 和茂
マイクロソフト株式会社
-
鈴村 豊太郎
東京工業大学|ibm東京基礎研究所|独立行政法人科学技術振興機構crest
-
藤澤 克樹
中央大学|jst Crest
-
後藤 和茂
マイクロソフト
関連論文
- 大規模最短路問題に対する高速処理システム : メモリ階層構造の考慮とクラスタ&クラウド技術による高速化 (21世紀の数理計画 : アルゴリズムとモデリング)
- 特集にあたって(半正定値計画に対するソルバーと応用例)
- 2-G-2 重み付き対数行列式を持つ半正定値計画問題を解くSDPA(連続最適化(1))
- データストリーム処理を用いた変化点検知アルゴリズムSSTのGPUによる性能最適化 (データ工学)
- データストリーム処理とバッチ処理における動的負荷分散 (データ工学)
- 大規模計算環境におけるユーザ満足度を考慮した資源管理へむけて(並列処理環境,2009年並列/分散/協調処理に関する『仙台』サマー・ワークショップ(SWoPP仙台2009))
- 2-F-14 大規模最短路問題に対するダイクストラ法の高速化(グラフ(2))
- 2-B-8 決定係数最大化ポートフォリオ選択に対する凸最適化アプローチ(連続最適化)
- 仮想クラスタを用いたData-Intensive Application実行環境の性能モデル構築と最適化(HPC-2:仮想クラスタ,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- ストリーム・コンピューティング時代を開く基盤ソフトウェアIBM InfoSphere Streams (特集 BAO--未来を開く高度なインテリジェンス)