著者

遠藤 敏夫 田浦 健次朗

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.81, pp.121-126, 2005-08-05

---

密に通信を必要とする並列計算をグリッド環境において行なう上での障害は、広域ネットワークの高い通信遅延である。本稿は、そのような計算の一つとして密行列のガウス消去法を取り上げ、高遅延環境でも高性能な並列アルゴリズムを述べる。その主要な技術はbatched pivotingと呼ばれるピボット選択手法である。本手法は、複数ステップのピボット選択処理をまとめて行なうことにより、同期コストを大幅に削減する。遅延をエミュレートした実験により、高遅延環境において本手法がpartial pivotingよりもはるかに高速に動作することを示す。一方、本手法ではpartial pivotingよりも計算精度が低下する可能性があるが、比較的良好なピボットを選択することにより、その低下を抑えるよう設計されている。乱数行列を用いた数値実験を通して、本手法がpartial pivotingに匹敵する計算精度を達成することを示す。Large latencies over WAN will remain to be an obstacle to running tightly coupled parallel applications on Grid environments. This paper takes one of such applications, Gaussian elimination of dence matrices and describes a parallel algorithm that is highly tolerant to latencies. The key technique is a pivoting strategy called batched pivoting, which largely reduces synchronization costs by batching pivot selections of several steps. Through experiments with large latencies emulated by software, we show our method works much faster than partial pivoting with large latencies. On the other hand, numerical accuracy of our method may be inferior to that of partial pivoting. However, our method is designed to suppress the degradation by selecting `better' pivots. Through experiments with random matrices, the batched pivoting achieves comparable accuracy to that of partial pivoting.