WEKO3
-
RootNode
アイテム
k段飛ばし共役勾配法:通信を回避することで大規模並列計算で有効な対称正定値疎行列連立1次方程式の反復解法
https://ipsj.ixsq.nii.ac.jp/records/81365
https://ipsj.ixsq.nii.ac.jp/records/81365bd925308-2b10-492e-b48f-460c4ff2c6e3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-HPC12133030.pdf (546.4 kB)
|
Copyright (c) 2012 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-03-19 | |||||||
| タイトル | ||||||||
| タイトル | k段飛ばし共役勾配法:通信を回避することで大規模並列計算で有効な対称正定値疎行列連立1次方程式の反復解法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | k-skip Conjugate Gradient Methods: Communication Avoiding Iterative Symmetric Positive Definite Sparse Linear Solver For Large Scale Parallel Computings | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 共役勾配法 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東京大学情報理工学系研究科コンピュータ科学専攻 | ||||||||
| 著者所属 | ||||||||
| 東京大学情報理工学系研究科コンピュータ科学専攻 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo | ||||||||
| 著者名 |
本谷, 徹
× 本谷, 徹
|
|||||||
| 著者名(英) |
Toru, Motoya
× Toru, Motoya
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 連立一次方程式の反復解法として広く使われている共役勾配法を大規模に並列化した際に律速となるのは，頻繁に現われる内積計算の通信遅延である．内積計算は計算機全体の集団通信を必要とすることから，大規模なアーキテクチャでの通信遅延は大きくなる．また強スケーリングにおいては計算粒度が小さくなり，通信遅延は相対的が大きくなってしまう困難を抱えている．物理的制約を超えての通信遅延削減は不可能なため，アルゴリズム側のアプローチによる通信遅延の削減が必要とされている．本稿では，共役勾配法の k+1 反復分の内積計算に必要な通信を 1 回で済ませることで集団通信を回避し，通信遅延を削減するk段飛ばし共役勾配法を提案，実装した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | The rate limiting factor of the conjugate gradient method parallelized for supercomputers, which is widely used as a sparse linear solver, is the communication latencies of inner products that frequently occur. Because the inner product needs the collective communication of whole processors, the larger the architectures become, the bigger the communication latencies of inner products are. In addition, the communication latencies of the strong scaling will be relatively big because the granularity will be small. Therefore, reducing the communication latencies from the viewpoint of improving algorithms is necessary because they cannot be reduced beyond the physical limitations, In this paper,we propose and implement a new algorithm k-skip conjugate gradient method that avoids communication by skipping the collective communication of inner products of k times out of k+1 iterations. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10463942 | |||||||
| 書誌情報 |
研究報告ハイパフォーマンスコンピューティング（HPC） 巻 2012-HPC-133, 号 30, p. 1-8, 発行日 2012-03-19 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
