誤差の補償能力をもつ並列計算向きの総和計算アルゴリズム

小澤 一文  宮崎 正俊  

誌名
電子情報通信学会論文誌 D   Vol.J75-D1   No.8   pp.765-770
発行日: 1992/08/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 特集論文 (並列/分散処理論文特集)
専門分野: 応用
キーワード: 
丸め誤差解析,  リカーシヴダブリング法,  総和計算,  並列計算,  精度保証,  

本文: PDF(365.3KB)>>
論文を購入




あらまし: 
並列計算機上で浮動小数点数の総和を効率的に,しかも精度良く計算するアルゴリズムを提案し,その誤差解析,計算効率を理論と実験の両面から考察する.このアルゴリズムは,並列計算機上でn個のデータの総和をlog2nステップで計算するリカーシヴダブリング法の一つの拡張でもあり,やはり,時間計算量はO(logn)である.このアルゴリズムを用いて総和を計算することによって,より精度の高い値が得られるだけではなく,精度の保証も与えられる.実際に並列計算機を用いて数値実験を行った結果,本アルゴリズムの実行速度は,使用可能なプロセッサ数が2以上であれば,seriesアルゴリズムの中では最も高速な誤差補償アルゴリズムであるKahanの方法よりも高速であることが判明した.また,本アルゴリズムの計算速度を誤差の補償を全くしない通常のアルゴリズムと比較した場合,seriesに計算した場合,約1/8の速度であり,使用可能なプロセッサ数が5のとき,約半分の速度になる.このことから,プロセッサ数が10から20になれば,通常のアルゴリズムよりも高速になることが予想される.精度に関しては,Kahanの方法とほぼ同等な結果が得られている.