係数行列のビット表現による疎行列反復解法の高速化

摘要

ぁるアーキテクチャ上でのアルゴリズムの性能予測にRooflineモデルが提案され，性能の傾向を説明する簡便な方法として利用されている．Rooflineモデルでは，Operational Intensityが大きければそのアーキテクチャの性能を十分に引き出せ，理論性能に近い演算性能となる．言い換えると，プログラムのループ中の演算数と必要な変数のロードの比とアーキテクチャの演算処理性能とメモリバンド幅の比によって性能が予測できる．このモデルは疎行列計算の場合には，メモリからコアへのデータ転送がボトルネックとなり，演算性能が律速となることをうまく説明している．また，性能を改善するためには，Operational Intensityを大きくすることが必要であること述べている．このためには，演算数を多くする（高コストであるが高収束の反復アルゴリズムを用いる）か，メモリからのデータ転送量を削減する指針が得られる．本論文は，後者のアプローチにより反復計算の性能を改善する方法を提案する．