文献

J-GLOBAL ID：201502261412008577   整理番号：15A0649498

QR分解に対する通信回避型アルゴリズムと自動チューニング

著者 (2件)： 深谷猛 (理研 計算科学研究機構) ,  深谷猛 (北大 情報基盤セ)
資料名： 計算工学  (Journal of the Japan Society for Computational Engineering and Science)
巻： 20  号： 2  ページ： 3247-3250  発行年： 2015年04月30日 
JST資料番号： L5669A  ISSN： 1341-7622  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： エクサスケールのスーパーコンピュータの開発がスタートし,大規模並列計算機での通信時間の削減が重要な課題となっている。本論文では,京コンピュータ上でMPI_Allreduceを実行した場合の性能を例に,超並列環境でボトルネックとなる通信時間を削減するために,通信回避によるレイテンシ削減が効果的なことを説明した。次に,最小二乗問題の求解を始めとする様々な場面で用いられる縦長行列のQR分解を題材とし,問題の難しさに依存せずに数値的に安定なハウスホルダーQR分解に対する通信回避型アルゴリズムを紹介した。TSQRアルゴリズムは各プロセスが部分行列のQR分解を独立に計算し,得られた上三角行列を隣のプロセスに1対1通信して,2つの上三角行列からなる小サイズの行列のQR分解によって1つの上三角行列にする操作を繰り返すことで,通信時間を大幅に削減できる。また,行列積が中心でTSQRアルゴリズムよりも高性能なコレスキーQR分解では行列の条件数が大きくなると,それに応じて計算精度が悪化するので,著者らは以前にコレスキーQR分解を2回繰り返すアルゴリズムCholeskyQR2を提案した。実際に10⁸程度の条件数までは安定であり,京コンピュータ上でTSQRアルゴリズムよりも高性能なことが確かめられており,異なる通信回避アルゴリズムの使い分けが課題であることを示した。

シソーラス用語： *スーパコンピュータ ,  時間 ,  *QR分解 ,  *超並列計算機 ,  最小二乗法 ,  *通信 ,  逐次近似 ,  計算機アルゴリズム ,  評価試験 ,  高速化
準シソーラス用語： Cholesky分解 ,  *京【スーパコンピュータ】 ,  通信時間 ,  反復法

分類 (3件)： ディジタル計算機方式一般  (JC02010O) ,  数値計算  (JE02000J) ,  電話・データ通信・交換一般  (ND11010T)

引用文献 (13件)：

• LAPACK Working Notes, http://www.netlib.org/lapack/lawns/downloads/
• BeBOP, http://bebop.cs.berkeley.edu/
• J. Demmel, http://www.cs.berkeley.edu/~demmel/
• G. Ballard, et al., Minimizing communication in linear algebra, SIAM J. Matrix Anal. Appl., Vol.32, No.3, pp.866-901 (2011).
• J. Demmel, et al., Communication-optimal parallel and sequential QR and LU factorizations, SIAM J. Sci. Comput., Vol.34, No.1, pp.206-239 (2012).

タイトルに関連する用語 (4件)： QR分解 ,  回避 ,  アルゴリズム ,  自動チューニング