計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリ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--未来を開く高度なインテリジェンス)
- NAREGIグリッドミドルウェアによる大規模連携接続実証実験(OS-6:分散システム,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 1-A-5 大規模最短路問題に対する高速処理システム : メモリ階層構造の考慮とクラスタ&クラウド技術による高速化(つくばOR学生発表(5))
- 広域分散ファイルシステムにおけるアクセスパターンと性能を考慮したファイル配置(HPC-13:ファイルシステム,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 5K-4 情報爆発時代のグリッドファイルシステム上での大規模データ管理(情報爆発時代における分散システム技術,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 広域分散環境における大規模データ管理のためのノードグルーピング(HPC-7 : データ管理)
- NAREGIミドルウェアβ-gLite間における相互ジョブ起動実験(グリッド,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- ファイルへのアクセスの自動分散を行うグリッド用分散ファイルシステム(グリッド(1), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- ファイルへのアクセスの自動分散を行うグリッド用分散ファイルシステム
- レプリカ交換分子動力学シミュレータREMD Toolkitのグリッド上での実行(HPC-3 : 科学技術計算)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- グリッドチャレンジテストベッドの構築と運用 : グリチャレテストベッドの作り方(HPC-3 : 大規模運用システム(1))
- 8wt.%Y_2O_3-ZrO_2/CoNiCrAIY遮熱コーティングの界面酸化過程について
- 次世代グリッド基盤OGSAにおけるC言語動作環境提供システムの試作と評価(HPC-11 : グリッド(2))(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- アプリケーションのインストール、データの配布、更新をサポートするグリッドポータル構築ツールキット(PCT4G)の開発(HPC-11 : グリッド(2))(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- Gridポータル構築ツールキット Ninf-Portal
- 動的なアプリケーション開発実行を可能にするグリッドポータルアーキテクチャ
- 高性能広域計算基盤Gridへのポータルシステムの設計と実装
- 2000-HPC-81-11 Jiniを用いたComputing Portal Systemの開発
- クライアント・サーバ型のグローバルコンピューティングシステムの比較 : Ninf, NetSolve, CORBA, Ninf-on-Globusの性能評価
- データストリーム処理を用いた変化点検知アルゴリズムSSTのGPUによる性能最適化(ストリームマイニング,センサデータ処理,ストリームデータベース,及び一般)
- データストリーム処理とバッチ処理における動的負荷分散(ストリームデータ処理,センサデータ処理,ストリームデータベース,及び一般)
- GPUを考慮したMapReduceのタスクスケジューリング
- スーパーコンピュータTSUBAME上でのMapReduceの実現
- スーパーコンピュータTSUBAME上でのMapReduceの実現
- "Bare Metal" Cloud: 実マシンを提供するクラウドサービス
- e-サイエンス基盤としての計算機センターPOP(Point-of-Presence)連携
- ストリーム処理系System Sを基盤にしたウェブサーバーの実装と評価(インターネット一般,インターネットと環境・エコロジー,一般)
- 2-D-14 最適化問題用オンライン・ソルバーの構築と自動選択機能の開発(非線形計画(3))
- テンプレート・プログラミングモデルに基づく自動ウェブ・クライアント・サーバ分割
- PoP(Point of Presence)によるe-サイエンスリソース連携(研究発表,ネットワーク研究開発テストベッド運用・利用,一般)
- e-サイエンス基盤としての計算機センターPOP (Point-of-Presence) 連携
- GPUを考慮した MapReduce のタスクスケジューリング
- 大規模計算機システムの資源選択を支援するエキスパートシステム
- スーパーコンピュータ TSUBAME 上での MapReduce の実現
- スーパーコンピュータ TSUBAME 上での MapReduce の実現
- 庁舎建築の企画・設計におけるコストプランニングシステムに関する研究(建築経済・住宅問題)
- 2L-7 データストリーム処理を用いた変化点検知の実装とGPUによる性能最適化(並列システムソフトウェア,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- データストリーム処理におけるGPUタスク並列を用いたスケーラブルな異常検知機構の実現 (インターネットコンファレンス2010(IC2010)論文集)
- 大規模最短路問題に対するダイクストラ法の高速化 (最適化モデルとアルゴリズムの新展開)
- SDPA project and new features of SDPA 7.1.0 (計算科学の基盤技術としての高速アルゴリズムとその周辺--RIMS研究集会)
- 2-D-6 半正定値計画による分子の電子構造計算(数理計画(1))
- 最適化ソフトウェアSDPA
- 半正定値計画に対する行列補完型主双対内点法の並列化(錘計画問題と相補正問題)
- 半正定値計画問題を解くソフトウェアのPCクラスタ上における並列実装(最適化(2))
- 大規模最短路問題に対するダイクストラ法の高速化 (最適化モデルとアルゴリズムの新展開--RIMS研究集会報告集)
- 広域分散コンピューティング環境における数理計画ソフトウェアSDPA
- SOLVING LARGE SCALE OPTIMIZATION PROBLEMS VIA GRID AND CLUSTER COMPUTING(Network Design, Control and Optimization)
- ウェーブレット解析手法を用いた建築内部空間画像と知覚イメージの相関関係の分析
- High Performance Grid Computing for Optimization Problem (Mathematics and Algorithms of Optimization)
- 11022 ウェーブレット解析手法を用いた建築内部空間画像と知覚イメージの相関分析
- 繰り返し型建築工事におけるTOCを用いた工程計画に関する研究
- 建築プロジェクトにおける工事編成最適化 : 工事編成支援システムの提案
- 多面体ホモトピー法から生じる条件付き線形不等式系の全解列挙法
- ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD
- 建築工事編成最適化システムの構築
- 建築生産情報の確定過程に関する研究
- 建築画像の消失点検出手法の開発とそれに基づく3次元建築モデルの再構成手法
- 2-A-15 アルゴリズムサイエンス分野における最適化ソフトウエアの実装方式(計算と最適化(3))
- 1-A-7 計算と最適化の新展開に向けて(計算と最適化(1))
- NAREGIミドルウェアβ-gLite間における相互ジョブ起動実験(グリッド,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- ファイルへのアクセスの自動分散を行うグリッド用分散ファイルシステム(グリッド(1), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- 最適化分野におけるクラウド技術の利用 (特集 クラウドとアナリティクス)
- GPGPUを用いた高速大規模グラフ処理に向けて
- 大規模並列ファイルシステムに対するワークフローアプリケーションのI/O性能解析
- 広域分散環境を提供するHPCIシステムソフトウェア基盤の設計概要と共有ストレージ構築
- 細粒度I/Oを考慮したオンデマンド階層型データストアの実現にむけて
- ワークフローアプリケーションに対する計算資源割り当ての最適化
- TSUBAME2.0上でのHadoopの性能評価
- クラウドを利用したElasticなデータストリーム処理系の実装と評価
- データストリーム処理を利用した 複雑ネットワークグラフ処理
- データストリーム処理におけるGPU統合型CPUの予備的評価
- 最適化分野におけるクラウド技術の利用(クラウドとアナリティクス)
- Wikipediaの編集履歴を用いた大規模2部グラフのデータストリーム処理
- Wikipediaの編集履歴を用いた大規模2部グラフのデータストリーム処理
- 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
- 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
- Wikipediaの編集履歴を用いた大規模2部グラフのデータストリーム処理
- Wikipediaの編集履歴を用いた大規模2部グラフのデータストリーム処理
- 大規模グラフ処理ベンチマークGraph500への2次元分割の適用と性能評価
- 大規模グラフ処理ベンチマークGraph500への2次元分割の適用と性能評価
- 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
- 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
- 「持たざる国」の資源論 : 環境論との総合に向けて
- 環境問題と知のガバナンス : 経験の無力化と暗黙知の回復(環境ガバナンス時代の環境社会学)
- データストリーム処理によるインクリメンタルグラフ処理に向けて(テーマセッション,大規模マルチメディアデータを対象とした次世代検索およびマイニング)
- 汎用グラフ処理モデルGIM-Vの複数GPUによる大規模計算とデータ転送の最適化
- 大規模最短路問題に対するダイクストラ法の高速化
- 2-A-6 最適化と計算に関する最新の傾向について(計算と最適化の新展開)
- 2-F-10 最速フローを用いた避難所の評価(最適化(2))
- 1-E-4 大規模グラフに対する幅優先探索の高速化(探索理論)
- 2-E-1 緊急避難計画に対する普遍的最速流の実験的解析(防災・減災)