命令レベル並列計算機のためのリカレンス演算の高速化手法とコンパイラへの実装

概要

論文の詳細を見る
VLIWやスーパスカラプロセッサなどの命令レベル並列計算機において, リカレンス演算部が性能のボトルネックのひとつとなっている. 本研究では, リカレンス演算に対する高速化手法として,高階型後退代入法と, ベクトル計算機のために導入した同次型後退代入法の2つを取りあげ, 実際のレジスタ割当てを含めたモジュロスケジューラを試作して評価を行った. その結果, 後者は前者に比べ, 絶対性能および最適な性能を与える展開数付近での性能感度が小さい点で優れていることが分かった. また, 現行の低いレベルの並列度を有するスーパスカラプロセッサにおいても有効であることが確認できた. 次に, 後者のアルゴリズムを最適化コンパイラで自動的に適用するため, パラメータであるループ展開数を求める経験則を見いだし, プロトタイプコンパイラに実装した. その結果, リバモアカーネル中のリカレンス演算を持つ3ループに対し, 理想的な性能の95%以上を得ることができた.
社団法人情報処理学会の論文
1996-09-15