村田法のスレッド並列化によるマルチコアＣＰＵ上での実対称帯行列帯幅縮小操作の高速化

摘要

本論文は固有値計算における帯幅縮小操作において、高いデータ再利用効率を持つ村田法を複数の同期方式を用いて並列化した際の性能を比較し、特性についてまとめたものである。固有値計算は基礎的な数値計算であり多くの分野で使用されている。反復計算の内部で用いられることもあり、高速化は重要な課題である。一般的に固有値計算は三重対角行列を経由することで高速に計算を行う。Bischofらは三重対角化操作を帯行列化と帯幅縮小の二段階に分けることでデータ再利用性が高い行列-行列積を用いて実行する手法を提案し、現在主流の方法となりつつある。村田法はHouseholderを用いた帯幅縮小操作である。反復計算により変換を行い、反復の一部過程において計算範囲が重複しないため、並列に実行することが可能である。しかしながら、村田法の並列実行は頻繁にデータの同期処理が発生する。同期処理はコストが高く、性能に影響を与える可能性がある。そのため同期回数が異なる３種類の同期方式に基づき並列実装を行い、性能の比較を行った。また性能差が発生した場合の原因として考えられるキャッシュミス回数と同期処理回数、全体に占める同期処理の割合を測定することで原因の考察を行った。Intel Core i7 2600Kプロセッサ(4コア)上で性能を測定したところ、論文中で典型的なベンチマーク行列として扱っている行列サイズ10240、帯幅96において、村田法による縮小操作はLAPACKによる帯幅縮小操作より1.89倍高速化した。さらに村田法のスレッド並列実行を行うことで、8スレッド並列実行を行った場合は1スレッド逐次実行の場合より3.93倍高速化を行うことができた。また同期方式の違いにより4スレッド並列実行の時実行速度に1.12倍の差が発生し、8スレッド並列実行の時2.15倍差が発生した。一部同期方式では特定のスレッド数で同期処理が頻発し、低速化する事態が発生し、これらの結果から同期方式と実行時間の間に明確な相関があることが確認された。主な要因としてキャッシュミスによるペナルティが考えられ、性能分析からも関係が裏付けられている。また同期回数と同期処理の割合から、同期回数よりも、同期処理単体のオーバヘッドが性能に影響を与えることがわかった。今後の課題として本研究を反映させ、並列性を最大に高めた調歩方式による同期の実装、より大きな行列に対する計算を行うため並列化方法を変更したMPIによるプロセス並列化の適用が考えられる。