k段飛ばし共役勾配法:通信を回避することで大規模並列計算で有効な対称正定値疎行列連立1次方程式の反復解法
スポンサーリンク
概要
- 論文の詳細を見る
連立一次方程式の反復解法として広く使われている共役勾配法を大規模に並列化した際に律速となるのは,頻繁に現われる内積計算の通信遅延である.内積計算は計算機全体の集団通信を必要とすることから,大規模なアーキテクチャでの通信遅延は大きくなる.また強スケーリングにおいては計算粒度が小さくなり,通信遅延は相対的が大きくなってしまう困難を抱えている.物理的制約を超えての通信遅延削減は不可能なため,アルゴリズム側のアプローチによる通信遅延の削減が必要とされている.本稿では,共役勾配法の k+1 反復分の内積計算に必要な通信を 1 回で済ませることで集団通信を回避し,通信遅延を削減するk段飛ばし共役勾配法を提案,実装した.
- 2012-03-19
著者
関連論文
- Scilab : 数値計算のためのフリーソフトウェア
- 自動チューニングのための数理基盤技術 (特集 数値計算のための自動チューニング)
- 自動チューニングのための数理基盤技術(数値計算のための自動チューニング)
- Dutt-Rokhlinの不等間隔高速順フーリエ変換の数値的研究
- 二重フーリエ級数展開を用いた球面上の浅水方程式の高速解法
- 自然勾配学習法の有効性
- Multi-Master Divisible Loadスケジューリングの最適化と漸近性能(最適化・高速化)
- 高速球面調和関数変換法の誤差の解析と制御
- 行列計算ライブラリインタフェースSILCの分散並列環境への実装(HPC-14 : 分散環境(2))
- 計算環境に依存しない行列計算ライブラリインタフェースSILC(一般講演2)
- オフライン自動チューニングの数理手法
- 並列ソフトウェアのオンライン自動チューニングのためのBayes的手法
- 6K-3 並列実験による疎行列格納法のオンライン自動チューニング(情報爆発時代における並列分散処理技術,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 線形方程式求解アルゴリズムの実行データに対するクラスタリング技術の一適用
- とびらの言葉
- 3.ソフトウェア自動チューニングの数理(ソフトウェア自動チューニングを支える基盤,科学技術計算におけるソフトウェア自動チューニング)
- 頑健で効率的なオンライン自動チューニングのための統計モデル(HPC-7:自動チューニングII,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 統計的パターン認識手法によるソフトウェア自動チューニングのための実験計画(HPC-3:自動チューニングI,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- ヘテロ並列計算環境における性能指標(並列化と高速化)
- オンライン自動チューニングのためのBayes逐次実験計画の解析モデルによる性能評価(性能評価,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- オンライン自動チューニングのためのBayes逐次実験計画の解析モデルによる性能評価(性能評価,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 自動チューニングにおける実験計画的手法を考慮した性能評価データ収集器の設計と実装(HPC-12 : 自動チューニングII)
- 並列・分散処理のためのスケジューリング理論(超ロバスト計算原理とモデリング・シミュレーション)
- Multi-master divisible loadの漸近最適スケジューリングの実機への実装(HPC-3: 科学技術計算)
- Multi-master divisible loadモデルに対する漸近最適スケジューリングの評価(ヘテロ型クラスタ)
- マルチクラスタ環境でのMMDL漸近最適スケジューリング(HPC-5 : 科学技術計算)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- 高速球面調和関数変換ルーチン FLTSS(高性能計算及び一般)
- 実行時自動チューニングのための逐次実験計画 : 分散が共通な2つの正規分布の場合(Session 2:最適化)
- GPGPUにおけるデータ転送とカーネル実行のヒューリスティックスケジューリング
- 自動チューニング数理基盤ライブラリATMathCoreLib
- ヘテロ並列計算環境のためのタスクスケジューリング手法のサーベイ(サーベイ)
- 汎用的なソフトウェア自動チューニング機構のための実験計画法の応用の検討(HPC-11 : 自動チューニング)
- 知恵と勇気と自動チューニング
- 有限サイズのmulti-master divisible load問題に対する再分散スケジューリングアルゴリズム(負荷分散,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- 有限サイズのmulti-master divisible load問題に対する再分散スケジューリングアルゴリズム(負荷分散, 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- ヘテロ型クラスタのための2次元列ベース分割における通信スケジューリングと分割の最適化(ヘテロ型クラスタ)
- Multi-master divisible load modelにおける漸近最適スケジューリング(スケジューリング)
- 高速直交関数変換ルーチンFXTPACKの球面調和関数変換における高性能実装と性能評価(数値計算)
- 2次元列ベース分割によるヘテロ型クラスタのためのLU分解(HPC-7: 並列数値計算ライブラリ)
- ERXPP-数値ライブラリにより並列計算性能を簡易かつ適応的に引き出す方式の提案(科学技術計算)
- 高速球面調和関数変換法の安定性制御
- k段飛ばし共役勾配法:通信を回避することで大規模並列計算で有効な対称正定値疎行列連立1次方程式の反復解法
- GPUにおけるダイバージェンス削減による高速化手法
- 相関を利用した自動チューニング数理手法
- GPUとGPGPUの概要
- 1. GPUとGPGPUの概要(GPUとその応用)
- 自動チューニング : 数理的手法によるソフトウェア高性能化 (次世代計算科学の基盤技術とその展開)