命令スケジューリング
位相幾何学的ソートの結果を見つける最も単純なアルゴリズムで、しばしば用いられるのがリストスケジューリングである。概念的には依存グラフの入力を繰り返し選択し現在の命令を追加してグラフから削除する。これにより別の命令が入力となるが、それらもまたスケジューリングの対象となる。アルゴリズムは、グラフが空になると終了する。
よりよいスケジュール結果に到達するためにはストールを避けなければならない。これは、スケジュールする次の命令を選択することにより決定できる。多数の発見的な方法が一般的に使用されている。
既にスケジュールされた命令によって使用中のプロセッサの資源は記録する。候補となる命令が使用中の資源を使用する場合には、その優先順位が下げられる。
候補となる命令が、関連するレイテンシ以上に前の命令の近くにスケジュールされると、その優先順位が下げられる。
候補の命令がグラフのクリティカルパス上にある場合には、優先度を上昇させる。この方法はある種の先読みを必要とする。
候補を選択する事により多数の入力が作られる場合には、優先度を上昇させる。この方法はスケジューラに大きな自由度を与える傾向がある。