命令スケジューリングとリストスケジューリング

命令スケジューリングは特にUltraSPARCのようなイン・オーダー発行のプロセッサでは重要である。最適なスケジューリングを見つけるには、

1. 依存グラフを構築する
2. 依存関係を満たす全ての命令順に対してクロック数を計算する
3. 最小のクロック数を与える命令順を採用する

とすればよいのだが、当然ながら組み合わせ爆発するので現実的ではない、と思われる*1。

そこでリストスケジューリングでは、

1. 依存グラフを構築する。各エッジにはレイテンシを与える
2. グラフのリーフ（葉）ノードから上方のノードへレイテンシを積算し、それを各ノードの優先度とする。結果として、クリティカルパス上にある命令ほど優先度が高くなる。
3. 上方の依存関係が解消された命令から順に、レイテンシとstructural hazardを考慮しながらスケジューリングしていく。候補が複数ある場合は優先度の高い命令を先にスケジューリングする

というアルゴリズムとなる。リストスケジューリングが速い理由は、バックトラックをしないという点にある。structural hazardなどで実際にはスケジューリング中にクリティカルパスが変化するのだが、一度スケジューリングした命令を再検討したりはしないのだ。ここらへんを少し工夫すれば性能が上がったりするかもしれないが、いかにも既存研究がありそうだ。

*1:要、実験。