5 スケジューリング

5
スケジューリング
最近のコンピュータは，多くの異なった命令の一部を同時に実行することが
できる．これは，命令レベル並列性（ILP）と呼ばれ，20 世紀最後の 10 年で，
プロセッサを驚異的に高速化させた大きな要因である．
パイプライン化されたマシン ：ある命令の書戻しを，次の命令の算術「実行」
（execute）や，1 つ前のオペランド読込みなどと同じサイクルで行う．
超長命令ワード（very-long-instruction-word，VLIW）：同じプロセッ
ササイクルで，幾つかの命令を発行する．コンパイラは，それらが，互
いにデータ依存しないことを保証しなければならない．
スーパースケーラ（superscalar）マシン ：2 つ以上の命令が，データ依存
によって関連していないなら（命令デコードハードウェアの中で素早
く検査される），それらを並列に発行する．さもなければ，逐次的に命
令を発行する．
命令の実行には，幾種類かの制約が存在する．プログラムは，命令レベ
ル並列性を得るために，これらの制約に従う最良のスケジュール（schedule）
を見付けることによって最適化することができる．
データ依存： 命令 A が，命令 B のオペランドとして使用される結果を計算
するなら，B は，A が終了する前に実行されることができない．
機能ユニット： チップ上に，kfu 乗算器（加算器など）が存在するなら，せ
いぜい kfu の乗算（加算など）命令を一斉に実行することができる．
命令発行： 命令発行ユニットは，せいぜい kii 命令を一度に発行できる．
レジスタ： せいぜい kr レジスタは，1 度に使用できる．さらに明確に言うと，
いずれのスケジュールも，適切なレジスタ割付けが必要になる．
機能ユニット，命令発行，及びレジスタ制約は，よく資源制約（resource constraints）あるいは資源ハザードとして，一緒に扱われる．
パイプライン化されたマシン上で，たとえ「B が A の前に実行すること
ができない」としても，B の実行には，A と並行に進めることができる（取
出しのような）部分が存在する可能性がある．図 26 や 27 は，その詳細を示
している．
変数の名前付替えによって，無くなる仮想的な制約も存在する．
47
Cycle 0 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9
Shift
Round Round
ADD
I-Fetch Read
Unpack
Write
Add
Add
Shift
MultB
MULT I-Fetch Read
Unpack MultA MultA MultA MultB
Round Write
Add
CONV I-Fetch
Read
Unpack Add
Round
Shift
Shift
Add
Round
Write
Figure 25: （MIPS R4000 プロセッサ上の）命令の機能ユニット要求．このマシンの浮動
少数点 ADD 命令は，1 サイクルで命令取出しユニットを使用し，1 サイクルでレジスタを
読込み，指数部と仮数部を取り出し，それから，次のサイクルで，シフタと加算器を使用す
る．その後，加算器と丸めユニットの両方を使用し，結果をレジスタファイルに書き戻す．
MULT と CONV 命令は，異なる順序で，機能ユニットを使用する．
ADD
I-Fetch Read
Unpack
Shift
Add
Round
Add
Round
Shift
Write
MultB
Add
MULT I-Fetch Read
Unpack MultA
MultA
MultA
MultB
ADD
I-Fetch
Read
Unpack
Shift
Add
Round
Add
MULT I-Fetch
Read
Unpack
MultA
MultA
MultA
Round
Write
Shift
MultB
MultB
Add
I-Fetch
Read
Unpack
Shift
Add
Unpack
MultA
MultA
MultA
I-Fetch
Read
Unpack
MultA
MultA
MultA
I-Fetch
Read
Unpack
MultA
MultA
MultB
I-Fetch
Read
Unpack
Shift
Add
MultA
MultB
MultB
Add
Round Write
ADD
MULT I-Fetch
Read
ADD
MULT I-Fetch
Read
Unpack
ADD
MULT Read
Unpack MultA
ADD
MULT Unpack
MultA
MultA
Round Round
Add
Shift
MultB
MultB
Add
Shift
Add
Round
Add
MultB
MultB
Add
X
Round
Write
Round
Write
OK
Write
OK
Round
Round
Write
Shift
X
Round Write
Shift
Round Round
Add
Add
Shift
MultB
Round Write
Add
Round
Add
Write
Round
Shift
Write
X
Write
OK
Figure 26: もし，各種類の機能ユニットが 1 つだけしかないなら，ADD は，
（太文字で示
した多くの資源ハザードのために）MULT と同時に開始できない．
（Add，Round，及び
Write ハザードのために）MULT の 3 サイクル後では開始できないし，
（Add と Round ハ
ザードのために）4 サイクル後でも開始できない．しかし，2 つの加算器と 2 つの丸めユニッ
トが存在したとすると，ADD は，MULT の後 4 サイクルで開始できる．あるいは，2 重取
出しユニットや，多重アクセスレジスタファイル，そして 2 重展開器があれば，MULT と
ADD は同時に開始できるようになる．
48
書込み後書込み： 命令 A が，レジスタやメモリ位置に書き込み，B が，同
じ場所に書き込むなら，A と B の順序を変更してはならない．しかし，
A と B が異なる場所に書き込むように，プログラムを変更できる場合
がある．
読込み後書込み： A のある場所からの読込みが，B の同じ場所への書込みの
前でなければならない場合，名前を付替えて異なる場所を使用するよう
にできないのであれば，A と B の実行順序は，交換されてはならない．
5.1
5.1.1
命令に対する制約
命令による資源の使用．
図 25 は，ある仮想マシンの 3 命令について，そのような観点で記述したも
のを示している．
命令 A の i 番目のサイクルが特定の資源を使用し，命令 B の j 番目のサイ
クルが同じ資源を使用するなら，B は，正確に，A の後の i − j にスケジュー
ルされることができる．
5.1.2
命令のデータ依存
データ依存の制約にも，同等の配慮が必要である．ある命令 A の結果は，そ
の実行の書込みステージの間に，レジスタファイルに書き戻される（図 25 を
参照）．もし，命令 B がこのレジスタを使用するなら，B の読込みステージ
は，A の書込みステージの後でなければならない．マシンの中には，バイパ
スを用いて，B の算術演算ステージが，A の算術演算ステージのすぐ後に続
くようにできるものもある．例えば，ADD 命令のシフト/加算ステージは，
MULT の丸めステージのすぐ後に続くことができる．これらの状況を，図 27
に示す．
5.2
資源束縛のないループスケジューリング
データ依存制約や資源ハザードに関して，最適のスケジュールを選択するこ
とは，困難（NP 完全）なので，資源束縛のあるループスケジューリングを
実践的に行うのが難しい場合がある．
最初に，資源制約を無視して，データ依存制約に関してだけ最適スケジュー
ルを見付けるアルゴリズムを述べる．このアルゴリズムは，実践的には有用
でないが，命令レベル並列性に存在する機会の種類を示す．
49
MultA MultA MultA MultB
MultB
Round
Add
Write↓
I-Fetch ↑Read
MultB
Round↓ Write
Add
Shift
I-Fetch Read Unpack ↑
Add
Unpack
Shift
Add
Round Round
Write
Add
Shift
MultA MultA MultA MultB
Round Round
Add
Shift
Write
Figure 27: データ依存．上側の図で，もし，MULT が，ADD のオペランドになる結果を
生成するなら，MULT は，その結果を，ADD が読出し可能になる前に，レジスタファイル
に書き込まなければならない．下側の図で，特殊なバイパスは，MULT の結果を，直接シ
フトや加算ユニットに振り向けて，書込み，読込み，及び取出しステージを飛び越えること
ができる．
Aiken-Nicolau ループパイプライニング（Aiken-Nicolau loop pipelining）
アルゴリズムには，幾つかのステップが存在する．
1. ループを展開する．
2. 各繰返しの各命令を，最も初期の可能な時間にスケジュールする．
3. 繰返し番号と時間を対にしたタブローに，命令を記入する．
4. 指定されたスロープで，分割された命令のグループを見付ける．
5. スロープを合併する．
6. ループの形に戻す．
タブロー（tableau），スロープ（slope），合併（coalesce）の概念を説明
するために，プログラム 28a を例として用いる．すべての命令は，1 サイク
ルで終了でき，多くの命令を，同じサイクルで任意に発行できると仮定する．
5.2.1
メモリを介したデータ依存
格納と取出しの最適なスケジューリングについて，値は，メモリに格納され，
その後，読み戻されるので，データ依存を追跡する必要がある．
スカラ置換 プログラム 28a では，本格的な依存解析う代わりに，V [i − 1]
への参照を等価な b で置き換えるスカラ置換（scalar replacement）を用いる
ことができる．配列 U ，V ，W ，X に重なりがないと仮定すると，プログラ
ム 28b で，すべてのメモリ参照が独立になる．
50
for i ← 1
a
b
c
d
e
f
g : V [i]
h : W [i]
j
for i ← 1 to N
to N
← j ⊕ V [i − 1]
← a⊕f
← e⊕j
← f ⊕c
← b⊕d
← U [i]
← b
← d
← X[i]
ai
bi
ci
di
ei
fi
g : V [i]
h : W [i]
ji
(a)
←
←
←
←
←
←
←
←
←
ji−1 ⊕ bi−1
ai ⊕ fi−1
ei−1 ⊕ ji−1
fi−1 ⊕ ci
bi ⊕ di
U [i]
bi
di
X[i]
(b)
Figure 28: (a) ソフトウェアパイプライン化できる for ループ．(b) （a の定義における）
スカラ置換（scalar-replacement）最適化，及び，繰返し番号でラベル付けしたスカラ変数．
データ依存グラフ 現在の繰返しの値と，以前の繰返しの値を区別するため
に，ループ本体の各変数に印を付け（プログラム 28b），データ依存（datadependence）グラフを作成することができる．
グラフ 29a で，実線辺は，ある繰返し内のデータ依存であり，点線辺は，
ループが運ぶ依存である．
タブロー 次に，ループを展開する．は，グラフ 29b のように，DAG で表
現されるデータ依存グラフをスケジューリングするのは，
（資源制約がなけれ
ば）容易である．先行節をもたない操作から始めて，各操作は，その先行節
がすべて処理し終えた後に処理する．
Cycle
1
2
3
4
5
..
.
Instructions
a1 c1 f1 j1 f2 j2 f3 j3 . . .
b1 d1
e1 g1 h1 a2
b2 c2
d2 g2 a3
..
.
このスケジュールを，タブロー（tableau）に記述すると便利である．表 30a
が示すように，タブローでは，行が連続するサイクルであり，列が，元のルー
プにおいて連続する繰返しである
51
a
c
g1
j
c1
a1
b1
j1
a2
f1
d
f
j2
g2
a3
h
g
h1
c2
d2
b2
b
d1
e1
f2
e2
h2
c3
b3
e
(a)
(b)
Figure 29: プログラム 28b のデータ依存グラフ：(a) 元のグラフ．ここで，実線辺は，同
じ繰返しの依存であり，点線辺は，ループが運ぶ依存である．(b) 展開したループの非循環
依存．
C
y
c
l
e
s
1
2
1 acf j f j
2 bd
3 egh a
4
cb
5
dg
6
eh
7
8
9
10
11
12
13
14
15
Iterations
3
4
fj
fj
a
b
cg
d
eh
a
b
g
c
d
eh
5
fj
6
fj
1
2
acf j
bd
fj
Pro- egh a
logue
bc
dg
eh
Iterations
3
4
fj
a
b
cg
d
eh
Loop
body
a
b
g
a
b
g
c
d
eh
Epilogue
(b)
(a)
Figure 30: (a) ソフトウェアパイプライン化したループスケジュールのタブロー．スロー
プ 0 をもつ命令 f j のグループが存在し，スロープ 2 をもつ別のグループ abg や，スロープ
3 をもつ 3 番目のグループ cdeh も存在する．(b) より小さいスロープのグループは，スロー
プ 3 に押し込まれ，パイプライン化したループを構成する（箱型の）パターンが見付かる．
52
fj
a
b
g
c
d
eh
5
fj
a
b
g
c
d
eh
2，3 の繰返しをスケジュールした後，タブロー内のパターンに気づく．1
繰返し当たり 3 サイクルのスロープで，右下の角に滑べり降りている命令
cdeh のグループ，1 繰返し当たり 2 サイクルの緩いスロープの別のグループ
abg ，及び，0 スロープの 3 番目のグループ f j が存在する．見て分かるよう
に，スケジュールには，一致するグループを分けるギャップ（gaps）が存在
し，一定の割合で大きくなる．この場合，繰返し i ≥ 4 にある命令のグルー
プは，繰返し i + 1 のグループに一致する．一般に，繰返し i のグループは，
i + c のグループに一致する．
5.2.2
理論
• ループ内に K 命令存在するなら，ギャップで分割されたグループのパ
ターンは，常に K 2 繰返し内に（そして，通常ずっと早く）現れる
• データ依存制約に違反しないように，ギャップを取り除くか，少なくと
も小さくして増えないようにすることで，傾斜が緩いグループのスロー
プを増加させることができる．
• 結果として生ずるタブローは，一致した m サイクルの繰返し集合をも
つ．そして，その集合は，パイプライン化したループの本体を構成する．
• 結果として生じるループは，最適にスケジュールされている（可能な
最も少ない時間で動作する）．
ループが最適かどうかを知るためには，展開したループのデータ依存 DAG
に，最後に実行される命令に到る長さ P のパスが存在して，スケジュールし
たループがその命令を時間 P で実行することを考慮しなければならない．
例の結果を，表 30b に示す．ここで，3 サイクルの繰返しパターンを見付
けることができる（3 は，最も急なグループのスロープに当たる）．この場合，
パターンは，四角で示してあるように，サイクル 8 まで始まらない．これは，
スケジュールしたループの本体（body）を構成することになる．ループ本体
の前の不規則にスケジュールされた命令は，プロローグ（prologue）を構成
し，その後の命令は，エピローグ（epilogue）を構成する．
ここで，このループのために，図 31 に示すような，多重命令発行のプロ
グラムを生成することができる．しかしながら，変数には，依然として，こ
のプログラム中に添字がある．すなわち，変数 ji+1 は，ji と同時に生存して
いる．このプログラムを命令にコード化するためには，図 32 に示すように，
異なる変数の間 move命令の中に配置する必要がある．
4 つの同時ロードと格納を含めて，マシンが 1 度に 8 命令実行できると仮
定すると，このループは，最適な状態にスケジュールされる．
53
L:
a1
b1
e1
b2
d2
e2
c3
di
ei
ci+1
dN −1
eN −1
cN
dN
eN
←
←
←
←
←
←
←
←
←
←
←
←
←
←
←
j0 ⊕ b0
a1 ⊕ f0
b1 ⊕ d1
a2 ⊕ f1
f1 ⊕ c2
b2 ⊕ d2
e2 ⊕ j2
fi−1 ⊕ ci
bi ⊕ di
ei ⊕ ji
fN −2 ⊕ cN −1
bN −1 ⊕ dN −1
eN −1 ⊕ jN −1
fN −1 ⊕ cN
bN ⊕ dN
c1
← e0 ⊕ j 0
d1
← f0 ⊕ c1
V [1] ← b1
c2
← e1 ⊕ j 1
V [2] ← b2
W [2] ← d2
V [3] ← b3
bi+1 ← ai ⊕ fi
W [i] ← di
ai+2 ← ji+1 ⊕ bi+1
bN
← aN ⊕ fN −1
W [N − 1] ← dN −1
f1 ← U [1]
f2 ← U [2]
W [1] ← d1
f3 ← U [3]
a3 ← j2 ⊕ b2
b3 ← a3 ⊕ f2
a4 ← j3 ⊕ b3
j1
j2
a2
j3
←
←
←
←
X[1]
X[2]
j1 ⊕ b1
X[3]
f4
←
U [4]
V [i + 1] ← bi+1
i
← i+1
fi+2 ← U [i + 2] ji+2
if i < N − 2 goto L
j4
i
V [N ] ← bN
W [N ] ← dN
Figure 31: パイプライン化したスケジュール．各行の代入は，同時に生じる．各右辺は，
代入前の値を参照している．ループの出口検査 i < N + 1 は，i が 3 増加する分「過去へ移
動」しているので，i < N − 2 として現れている．
L:
a1
b1
e1
b2
d
e2
c
d
e
c
d
e
c
d
e
←
←
←
←
←
←
←
←
←
←
←
←
←
←
←
j0 ⊕ b0
a1 ⊕ f0
b 1 ⊕ d1
a2 ⊕ f1
f1 ⊕ c2
b 2 ⊕ d2
e2 ⊕ j 2
f ′′ ⊕ c
b′ ⊕ d
e ⊕ j ′′
f ′′ ⊕ c
b′ ⊕ d
e ⊕ j′
f′ ⊕ c
b⊕d
c1 ← e0 ⊕ j0
d1 ← f0 ⊕ c1
V [1] ← b1
c2 ← e1 ⊕ j1
V [2] ← b2
W [2] ← d2
V [3] ← b
b
← a′ ⊕ f ′
W [i] ← d
a
← j′ ⊕ b
b
← a ⊕ f′
W [N − 1] ← d
f1
← U [1]
f ′′ ← U [2]
W [1] ← d1
f′
← U [3]
a
← j2 ⊕ b2
b
← a ⊕ f ′′
a
← j′ ⊕ b
b′ ← b; a′ ← a; f ′′
V [i + 1] ← b
i
← i+1
b′
← b
V [N ] ← b
j1
j2
a2
j′
←
←
←
←
X[1]
X[2]
j1 ⊕ b1
X[3]
f
←
U [4]
j
i
← f ′ ; f ′ ← f ; j ′′ ← j ′ ;
f
← U [i + 2]
j
if i < N − 2 goto L
W [N ] ← d
Figure 32: 転送命令を付加したパイプライン化したスケジュール
54
← X[4]
← 3
j′ ← j
← X[i + 2]
←
←
X[4]
3
←
X[i + 2]
5.3
資源束縛のあるループパイプライニング
実際のマシンは，1 度に制限された数の命令しか発行することができないし，
制限された数のロード/格納ユニット，加算器，及び，乗算器しか存在しない．
実践的に有用なものにするためには，資源制約を考慮しなければならない．
スケジューリングアルゴリズムへの入力は，3 つの部分からなる．
1. スケジュールするプログラム
2. 各命令が，その各パイプラインステージで，どの資源を使用するする
かという記述．
3. マシン上で利用可能な資源の記述（各種の機能ユニットが 1 度に幾つ
発行できるのか，幾つの命令が 1 度に発行できるのか，どの種類の命
令が同時に発行できるかの制限など）．
資源束縛スケジューリングは，NP 完全なので，
「典型的な」場合にうまく
いく近似アルゴリズムを用いる．
5.3.1
モジュロスケジューリング
繰返しモジュロスケジューリングは，資源束縛ループスケジューリングに対
する，実践的なアルゴリズムである．アイデアは，機能ユニット及びデータ
依存の制約に従うよいスケジュールを見付け，その後，レジスタ割付けを実
行するために，繰返しバックトラックを用いることである．
アルゴリズムは，ループ本体のすべての命令を ∆ サイクルのスケジュー
ルに配置しようとする．アルゴリズムは，スケジュールを作成できるような
値に到達するまで，∆ の値を増加させることを試みる．
モジュロスケジューリング（modulo scheduling）のアイデアの鍵は，命
令が，時間 t で機能ユニット制約に違反したら，時間 t + ∆ に適合しないか，
あるいは，t ≡ t′ mod ∆ である任意の時間 t′ に適合しない点である．
例えば，1 度に 1 つのロード命令だけしか実行できないマシン上で，プロ
グラム 28b を ∆ = 3 でスケジュールしようとしていると仮定する．
0
1
2
fi ← U [i]
ji ← X[i]
fi は，ループのサイクル 1 からサイクル 0 あるいはサイクル 2 に移動させ
ることができる．
55
0
1
2
fi ← U [i]
0
1
3
ji ← X[i]
fi ← U [i]
ji ← X[i]
いずれか一方は，資源競合を避けられる．fi は，ずっと初期のサイクル
−1 に移動することができる．ここでは，fi+1 を計算することになる．また，
ずっと後のサイクル 3 に移動することもできる．ここでは，fi−1 を計算する
ことになる．
0
1
2 fi+1 ← U [i + 1]
0 fi−1 ← U [i − 1]
1
3
ji ← X[i]
ji ← X[i]
しかし，1 ≡ 4 mod 3 なので，∆ = 3 では，fi をサイクル 1 からサイクル
4 へ移動することによって，資源競合を避けることはできない．
0
1 fi−1 ← U [i − 1]
2
5.3.2
ji ← X[i]
レジスタ割り付けの影響
図 31 において，スケジュールのサイクル 0 に現れる d ← f ⊕ c の計算を
考える．もし，d の計算を，後のサイクルに配置すると，f と c の定義から
W [i] ← d における d の使用へのデータ依存辺は，縮退することになる．も
し，データ依存辺が 0 サイクルより小さく縮退すると，データ依存制約に違
反してしまう．これは，d を使用する計算を後のサイクルに移動することに
よっても解決できる．
逆に，もし，データ依存辺が多くのサイクルを示すために長くなると，ルー
プの周辺に，複数の値の「バージョン」
（versions）を運ばなければならない
（図 32 のループ周辺で，f ，f ′ ，f ′′ を運ぶように ）．そして，これは，より
多くのテンポラリを使用しており，その結果，レジスタ割付けに失敗する可
能性があることを意味する．実際，最適な（optimal）ループスケジューリ
ングアルゴリズムは，スケジューリングと同時にレジスタ割付けを考慮する
べきである．しかし，最適なアルゴリズムが実践的かどうかは明らかではな
いので，この節で述べた繰返しモジュロスケジューリング（iterated modulo
scheduling）によって最初にスケジュールし，その後，レジスタ割付けを行っ
て，うまく行くこと期待することになる．
56
5.3.3
最小開始間隔の発見
モジュロスケジューリングは，パイプライン化したループ本体のサイクル数
について下限を発見することから始まる．
資源評価値： 乗算器やメモリ取出しユニットのような，いずれの種類の機能
ユニットについても，ループ本体内の一致する命令（それぞれ，乗算
やロード）によって，そのようなユニットに何サイクル使用されるか
確認することが可能である．これは，ハードウェアによって与えられ
る機能ユニットの数で割ると，∆ の下限が得られる．例えば，各乗算
器を 3 サイクルで使用する 6 つの乗算命令が存在し，2 つの乗算器が存
在するなら，∆ ≥ 6 · 3/2 である．
データ依存評価値： 値 xi−1 に依存した他の計算のチェインに依存する値 xi
が存在するとして，データ依存グラフのいずれのデータ依存サイクル
についても，チェインの遅延の合計は，∆ の下限を与える．
∆min をこれらの評価値の最大値であるとする．
プログラム 28b の ∆min を計算してみる．簡単にするために，1 つの ⊕ 算
術命令と，1 つのロード/格納は，1 度に発行でき，すべての命令は 1 サイク
ルで終了すると仮定する．また，i ← i + 1 あるいは，条件分岐のスケジュー
リングは考慮しないことにする．
それから，算術資源評価値（arithmetic resource estimator）は，ループ
本体内の 5⊕ 命令を，1 サイクル当りに発行可能な命令数 1 によって割ったも
の，あるいは，∆ ≥ 5 である．ロード/格納資源評価値（load/store resource
estimator）は，ループ本体内の 4 つのロード/格納命令を，1 サイクル当りの
発行可能なメモリ操作数 1 で割ったもの，あるいは，∆ ≥ 4 である．データ依
存評価値は，∆ ≥ 3 の長さをもつグラフ 29a のサイクル ci → di → ei → ci+1
から得られる．
次に，どの命令を最初に考慮すべきか決定する幾つかの発見的手法によっ
て，ループの本体の命令に優先順位を付ける．例えば，クリティカルデータ
依存サイクルにある命令や，乏しい資源を多く使用する命令は，スケジュー
リングにおいて，最初に配置されるべきであり，それから，それらの周辺を
他の命令で埋めるとよい．H1 , . . . , Hn は，
（発見的な）優先順序で並んだルー
プ本体の命令である．
例では，H = [c, d, e, a, b, f, j, g, h] を用いて，クリティカル資源サイクル
に存在したり，あるいは，算術関数ユニットを使用したりする命令を初期の
方へ配置する（このループの資源評価値は，算術命令の方が，ロード/格納
より多くの要求をもつことを示している）．
57
for ∆ ← ∆min to ∞
Budget ← n · 3
for i ← 1 to n
LastTime[i] ← 0
SchedTime[i] ← none
while Budget > 0 and there are any unscheduled instructions
Budget ← Budget − 1
let h be the highest-priority unscheduled instruction
tmin ← 0
for each predecessor p of h
if SchedTime[p] ̸= none
tmin ← max(tmin , SchedTime[p] + Delay(p, h))
for t ← tmin to tmin + ∆ − 1
if SchedTime[h] = none
if h can be scheduled without resource conflicts
SchedTime[h] ← t
if SchedTime[h] = none
SchedTime[h] ← max(tmin , 1 + LastTime[h])
LastTime[h] ← SchedTime[h]
for each successor s of h
if SchedTime[s] ̸= none
if SchedTime[h] + Delay(h, s) > SchedTime[s]
SchedTime[s] ← none
while the current schedule has resource conflicts
let s be some instruction (other than h) involved in a resource conflict
SchedTime[s] ← none
if all instructions are scheduled
RegisterAllocate()
if register allocation succeeded without spilling
return and report a successfully scheduled loop.
Delay(h, s) =
Given a dependence edge hi → si+k , so that h uses the value of s from the kth previous iteration
(where k = 0 means that h uses the current iteration’s value of s);
Given that the latency of the instruction that computes s is l cycles;
return
l − k∆
Figure 33:
繰返しモジュロスケジューリング．
58
SchedTime
Resource
a 3
Table
b
⊕ M
c
0
0 c
d 1
e 2
1 d
f
2 e
g
3 a
h
4
j
Placing c, d, e, a.
SchedTime
Resource
a 3
Table
b
4
⊕ M
c ̸05
0 c
d ̸1
1
e ̸27
f
2 e
g
3 a
h
4 b
j
Placing e violates
e → c; remove c;
placing c violates
c → d; remove d.
SchedTime
Resource
a 3
Table
b
4
⊕ M
c
0
0 c
d 1
e ̸2
1 d
f
2
g
3 a
h
4 b
j
Placing b violates
b → e; remove e.
SchedTime
Resource
a 3
Table
b
4
⊕ M
c ̸05
0 c f
d ̸16
1 d
j
e ̸27
f
0
2 e
g
7
g
3 a h
h 8
4 b
j
1
Placing d, f, j, g, h.
Figure 34: プログラム 28b に適用される繰返しモジュロスケジューリング．
グラフ 29a は，データ依存グラフであり，∆min = 5（57 ページを参照）であり，H =
[c, d, e, a, b, f, j, g, h] である．
スケジューリングアルゴリズムは，特定の時間 t にそれぞれスケジュールさ
れる命令の集合を管理している．もし，h ̸∈ S なら，値 SchedTime[h] = none
であり，さもないと，SchedTime[h] は，現在スケジュールされる h の時間で
ある．S の要素は，すべての資源とデータ依存制約に従う．
アルゴリズム 33 の各繰返しは，スケジュールされていない最も高い優先
順位の命令 h を，次のように S に配置する．
1. h の既に配置された先行節に関するすべてのデータ依存制約に従い，す
べての資源制約に配慮した最も初期の時間スロット（もしあるなら）に
配置する．
2. しかし，資源制約に従う ∆ 分の連続サイクルにスロットが存在しない
なら，そのようなスロットはまったく存在する可能性がない．なぜな
ら，時間 t に利用可能な機能ユニットは，t + c · ∆ のものと同じだから
である．この場合，h は，資源制約に関係なく，依存制約に従い，以前
の h を配置する試みよりも後の時間で，最も初期の時間スロットに配
置する．
一旦，h が配置されると，再度，部分スケジュール S を正当なものにするた
めに，他の命令は取り除かれる．すなわち，今ではデータ依存制約に従わな
くなった h の任意の後続節や，h と競合する資源をもつ任意の命令である．
この配置と除去は，永遠に繰り返される可能性があるが，ほとんどの場
合，指定した ∆ に，解がすぐ見付かるか，解が存在しないかのいずれかであ
る．もし，すぐに解が見付からない場合，アルゴリズムを停止させるために，
c · n スケジュール配置の予測値（c = 3 あるいは近い数字）を可能にする．そ
して，その後，この ∆ の値を放棄し，次のものを試みる．
59
変数 j に関連した定義使用辺が，∆ サイクルより長くなるとき，バケツ
リレー形式で異なる繰返しバージョンをコピーする move命令をもつ j の 2
個以上のコピーが必要になるこれについては，変数 a, b, f, j の例を，図 32 に
示す．しかし，転送命令を挿入する明示的なアルゴリズムは示さない．
資源競合の検査は，長さ ∆. の配列である資源予約表（resource reservation
table）を用いて行われる．時間 t に命令によって使用される資源は，配列の
t mod ∆ の位置に置くことができる．資源の使用法を加えたり，表から取り
除いたり，競合を検査したりすることは，定数時間で実行できる．
このアルゴリズムは，いずれの意味においても，最適なスケジュールを見
付けることができると保証されるわけではない．開始間隔 ∆ をもつ最適で，
レジスタ割付け可能なスケジュールは存在するかもしれないが，アルゴリズ
ムは，時間 ∆ をもつスケジュールをまったく見付けることができないかもし
れなし，あるいは，レジスタ割付けが失敗するスケジュールしか見付けられ
ないかもしれない．唯一の慰めは，実践的に非常にうまく動作することが報
告されていることである．
この例におけるアルゴリズムの操作を，図 34 に示す．
60