並列数値計算アルゴリズムとその性能について Parallel numerical algorithms and their performances a 筑波大学大学院システム情報工学研究科，b 筑波大学計算科学研究センター 高橋大介 a, b D. Takahashia, b Graduate School of Systems and Information Engineering, University of Tsukuba a Center for Computational Sciences, University of Tsukuba b 本稿では，並列数値計算アルゴリズムとして，大規模電子状態計算で使われることが多い， 高速フーリエ変換（FFT）およびグラム・シュミットの直交化アルゴリズムを取り上げ，並 列化および高速化の手法およびその性能にについて述べる． 大規模な FFT やグラム・シュミットの直交化においては，大量のデータを高速に処理する ために，並列化が必須となる．本稿では，PC クラスタのような分散メモリ型並列計算機をタ ーゲットとすることにする．多くの数値計算アルゴリズムは処理するデータがキャッシュメ モリに載っている場合には高い性能を示す．しかし，問題サイズがキャッシュメモリのサイ ズより大きくなった場合においては著しく性能が低下することも多い．したがって，並列数 値計算アルゴリズムにおける一つの目標は，いかにしてキャッシュミスの回数を減らすかと いうことが挙げられる．近年のプロセッサの演算速度に対する主記憶のアクセス速度は相対 的に遅くなってきており，主記憶のアクセス回数を減らすことは，より重要になっている． そこで，本稿ではキャッシュブロッキングという手法を三次元 FFT アルゴリズムおよびグ ラム・シュミットの直交化アルゴリズムに適用することで，従来提案されている手法に比べ て高速化を図ることができることを示す． 具体的な高速化手法であるが，三次元 FFT においてはキャッシュ内のデータを有効に再利 用し，キャッシュミスの回数を減らすために，従来の三次元 FFT では分離されていた multicolumn FFT と行列の転置を統合する手法を用いた． 一方，グラム・シュミットの直交化としては，古典的な計算順序に従う方法（古典グラム・ シュミット法，以下 CGS 法）および，計算誤差の蓄積を考慮した計算順序に従う方法（修正 グラム・シュミット法，以下 MGS 法）があるが，MGS 法は並列化に適していない． CGS 法においては，精度が問題になるが，要求精度を満たすまで CGS 法を繰り返す Daniel-Gragg-Kaufman-Stewart 型グラム・シュミット法（DGKS 法）を用いることで，精 度を改善することが可能である．さらに，複数のベクトルに対して行う CGS 法においては， 複数のベクトルに対する内積および複数のベクトルに対するベクトル変換を BLAS 3 アルゴ リズムである行列積に変換することでさらに高速化できる． これらの計算を実際に PC クラスタ上で実行し，性能を評価した結果について述べる．
© Copyright 2024 ExpyDoc
