行列積を用いた古典Gram-Schmidt直交化法の並列化

IPSJ Web Site

Bibliographic Information

Other Title
  • ギョウレツ セキ オ モチイタ コテン Gram-Schmidt チョッコウカホウ ノ ヘイレツカ
  • Efficient Parallel Implementation of Classical Gram-Schmidt Orthogonalization Using Matrix Multiplication

Search this article

Description

本論文では，直交化アルゴリズムの1つである古典Gram-Schmidt法（CGS 法）の効率的な実装を行い，並列化して評価した結果について述べる．CGS法においては，内積計算とベクトル変換を行列積に変更することで高速化できることが知られている．本論文では，CGS法を行列積で行う手法を拡張し，行列積を適用できる範囲の比率を高めることで性能を改善することができることを示す．また，行列積の実装上の特徴から，最適な分割手法が存在することを示す．提案する手法をPCクラスタに実装し，性能評価を行った．その結果，32ノードのXeon 3 GHz PCクラスタにおいて，naiveな実装に対し約5.36倍の高速化となり，約122.9GFLOPSの性能を得ることができた．

In this paper, we propose an efficient parallel implementation of classical Gram-Schmidt (CGS) orthogonalization. It is known that the CGS orthogonalization of a matrix can be altered into a matrix multiplication. We show that the CGS orthogonalization with matrix multiplication improves performance effectively and blocking method using square matrix multiplication improve performance because of matrix's row-column ratio affects DGEMM routine performance. We succeeded in obtaining performance of approximately 122.9GFLOPS on a 32-node Xeon 3 GHz PC cluster.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top