文献

J-GLOBAL ID：201202280493307533   整理番号：12A0101854

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

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

著者 (10件)： 安井雄一郎 (中央大) ,  安井雄一郎 (JST-CREST) ,  藤澤克樹 (中央大) ,  藤澤克樹 (JST-CREST) ,  佐藤仁 (東京工大) ,  佐藤仁 (JST-CREST) ,  鈴村豊太郎 (東京工大) ,  鈴村豊太郎 (IBM 東京基礎研) ,  鈴村豊太郎 (JST-CREST) ,  後藤和茂 (マイクロソフト)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2011  号： 4  ページ： ROMBUNNO.ARC-197,NO.21  発行年： 2011年12月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 様々な分野においてネットワーク解析に対する期待は高まりを見せているものの,非常に大規模なネットワークを扱うための計算量が課題とされている。そこで我々は,一般的な計算機環境上での最短路問題と中心性指標に対する,計算機のメモリ階層構造を考慮した高速計算手法を提案し,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倍の性能を示している。(著者抄録)

シソーラス用語： *最短路問題 ,  指標 ,  数学的性質 ,  ネットワーク法 ,  *記憶階層 ,  計算機アーキテクチャ ,  衝突回避 ,  実験 ,  道路網 ,  *計算量 ,  性能評価 ,  グラフ ,  大規模系 ,  ライブラリ【計算機】 ,  解析 ,  数値実験 ,  ネットワーク解析
準シソーラス用語： 中心性指標 ,  中心性 ,  NUMAアーキテクチャ

分類 (3件)： ネットワーク法  (KA03040X) ,  オペレーティングシステム  (JD03020J) ,  計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 計算機 ,  階層構造 ,  高性能 ,  ネットワーク解析 ,  ライブラリ