命令レベル並列計算機上で並列実行する領域の選択を高速に行う方法

概要

論文の詳細を見る
プレディケート付き命令を許す命令レベル並列計算機においては, 条件分岐を削除して分岐先命令群に相補的なプレディケートを付けたり(IF変換), 制御依存やメモリ依存を超えた投機的な命令移動によってクリティカルパスを縮めたりすることで, プログラムの効率的な実行が実現できる.しかし, これらの最適化の適用領域(以降ハイパーブロックと呼ぶ)によっては, 分岐先命令のクリティカルパス長のバランスの悪さ, 実行可能性が低い命令の挿入などの原因で, 実行効率改善の程度が異なり, 実行効率の低下の可能性すらあるため, ハイパーブロックとする領域の適切な選択が必要である.従来の研究は, さまざまなハイパーブロックの選び方に対して実際にコードスケジュールして効率を比較するという, Generate&Test型の方法であり, Testされるハイパーブロックの場合の数は, 分岐命令の数に従って指数関数的に増大するため, 広範囲に高い実行効率を得ようとすると, コンパイル時間が多くなってしまう問題があった.本研究の基本アイデアは, プログラムのある領域全体(aとする)をハイパーブロックとしたときの実行効率を, その領域を構成する部分(b, cなど)の実行効率から再帰的に見積もれるとモデル化することにある.このモデルに動的計画法を適用することで, (a)の効率が(b), (c)を逐次に実行した場合より悪くなる場合を検出し, (b)と(c)を独立なハイパーブロックとする判断が高速に終了する.これらの仕組みは, 基本ブロックの数にほぼ比例する時間で終了し, なおかつ, コードスケジューラに直接依存しないため, 高速かつ広範囲に対し, 高い実行効率を実現する.
一般社団法人情報処理学会の論文
2002-01-15

命令レベル並列計算機上で並列実行する領域の選択を高速に行う方法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク