社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

高位合成における可変スケジューリングの近似手法
曽根 康介†

石浦菜岐佐†† 関西学院大学 理工学部
〒 669-1337 兵庫県三田市学園 2-1
あらまし

本稿では, 高位合成における可変スケジューリングの近似手法を提案する. オペランドの値に依存して実行サイクル数が変動する演算がある場合, 従来の固定的なスケジューリングでは無駄な待ちが生じる. これに対し, 可変スケジューリングは, 演算器の完了信号を基に各演算の実行タイミングを動的に変更することにより, 効率的なスケ
ジューリングを可能とする. しかし, 可変スケジューリングの結果は, 起こり得る全ての制御ステップから成る状態遷移グラフとして表現され, その状態数が膨大なものとなることがあるため, 合成される回路の規模や性能が損なわれる恐れがあった. 本稿では, 可変スケジューリングにおいて平均サイクル数を犠牲にして回路規模および遅延の増加を抑制する近似手法として, 平均サイクル数の短縮効果に着目した方法と, 状態独立なバインディングに基づく方法を提案する. 評価実験を行った結果, 従来の可変スケジューリングと比較して平均サイクル数は増加するが, 回路規模の指標となる LUT 数と遅延を削減することができた.
キーワード

高位合成, 不定サイクル演算, 可変スケジューリング, 近似計算法

Approximated Variable Scheduling for High-Level Synthesis
Kousuke SONE† and Nagisa ISHIURA†† School of Science and Technology, Kwansei Gakuin University
2-1 Gakuen, Sanda, Hyogo, 669-1337, Japan
Abstract This article presents approximated variable scheduling methods for high-level synthesis. In the presence of indeﬁnite cycle operations, which complete their tasks in diﬀerent cycles depending on the values of theiroperands, conventional static scheduling often results in ineﬃcient execution. Variable scheduling enables eﬃcientcomputation by adjusting the execution steps of each operation dynamically based on the completion signal fromthe functional unit. However, the size of the state transition graphs, which are the results of variable scheduling,
often grow so large that the area and the delay of the synthesized circuits may not be acceptable. For the purpose ofrelaxing this problem, we propose two approximate methods which curve the area and the delay of the synthesizedcircuits at the cost of the average execution cycles in variable scheduling. The ﬁrst method is based on deletionof the states that do not contribute to the reduction of the execution cycles. The second one is based on state
independent binding of operations to functional units, which reduces both the state transition graph size and thedatapath complexity. Experimental results show that the size and the delay of the circuits are reduced as comparedwith the conventional variable scheduling, although the average number of execution cycles is increased.
Key words high-level synthesis, indeﬁnite cycle operation, variable scheduling, approximate method

1. は じ め にを大きく左右するのがスケジューリングとバインディングである. スケジューリングでは, 各演算を実行する制御ステップを演

近年, VLSI の設計効率化のため, C 言語などによるハード

算間の依存関係に基づき決定し, バインディングでは, 演算と演

ウェアの動作記述からレジスタ転送レベルの回路を自動合成す算の入出力の値に対してそれぞれ演算器とレジスタの割り当て

る高位合成技術 [1] に関する研究が多くなされ, 実用化が進めらを行う. スケジューリングとバインディングよって, 実行に必れている.

要なサイクル数や生成回路の規模, 遅延は大きく異なってくる.

高位合成の処理過程の中で, 生成されるハードウェアの品質

従来のスケジューリングでは, 各演算の実行に要するサイク—1—

ル数は一定であると仮定して演算を制御ステップに割り当てて

図 1 (a) の DFG において, f2 , f3 , f4 は実行サイクル数がいた. しかし, 演算のサイクル数は必ずしも一定ではなく, メモ< 1, 2 > の不定サイクル演算であり, f1 , f5 はサイクル数 1 のリアクセス演算や乗除算等では, オペランドの値に依存して実固定サイクル演算であるとする. この DFG に対し, 従来の静的行に必要なサイクル数が変動する場合がある. このような演算なスケジューリングを行った結果を (b) と (c) に示す. (b) はがある場合, 仮定したサイクル数よりも早く演算が完了すれば実行サイクル数を最大としてスケジューリングしたもので, 演

無駄な待ち時間が生じ, 仮定したサイクル数以下で演算が完了

算が早く終わった場合には無駄な待ちが生じる. f3 が 1 サイ

しなければ回路全体を停止 (ストール) させる必要がある. これクルで完了するとわかっていれば, f4 , f5 を 1 サイクル繰り上に対し, 可変スケジューリング [2] は, 演算器からの完了信号をげることができ, 全体の実行サイクル数を 4 サイクルに減らせ基に各演算の実行タイミングを動的に変更することによって効る. (c) は不定サイクル演算の実行サイクル数を最小としてス

率的な実行を可能にする.

ケジューリングを行ったものである. ただし, f2 には 2 サイク

可変スケジューリングの結果は 1 つの制御ステップを 1 つのル要した場合には, 図のようにハードウェア全体をストールさ状態とする状態遷移グラフで表現されるが, 起こり得る全てのせる必要がある. f2 にだけ 2 サイクル要することがわかってい制御ステップを網羅するため状態数が著しく増加することがあれば, f1 と f3 に依存する f4 , f5 を繰り上げ, 全体の実行サイる. これに伴い, 合成されるハードウェアの回路規模や遅延がクル数を 3 サイクルに短縮できる.

許容できないほど大きくなる恐れがあった.
この問題を解決するため, 本稿では, 可変スケジューリングに

従来のスケジューリングでは, このように不定サイクル演算を含む場合に必ずしも効率的な実行を行うことができなかった.

おける近似手法を提案する. これは, 平均サイクル数を犠牲に

2. 2 可変スケジューリング

して状態数を削減することにより, 回路規模と遅延の増加を抑可変スケジューリングは, 演算器からの完了信号を基に各演制するものである. 本稿では, 具体的な近似手法として, 平均サ

算の実行タイミングを動的に変更することによって効率的なス

イクル数の短縮効果に基づく方法と, 状態独立なバインディン

ケジューリングを行い, 全体の実行サイクル数を減少させる. こグに基づく方法の 2 つを提案する. 前者は, 各状態から終了状

れは, 予め状態遷移グラフを構築することにより実現する.

態までの平均サイクル数の短縮効果が小さい場合に完了信号に

図 1 (a) の DFG に対する可変スケジューリングの例を図 2よる分岐を行わないことにより状態数増加を抑えるものである.

(a) に示す. cj は不定サイクル演算 fj を実行する演算器から後者は, 演算を実行する演算器を状態に依存せず一意に決定すの fj の完了信号を表す. fjt は演算 fj の t サイクル目の実行る演算器バインディングを行って, 状態遷移グラフの状態数増を表す. 有向枝は状態 (制御ステップ) 間の遷移を表し, 枝のラ

加を抑制するものである. これらの手法により, 状態数の増加

ベルは遷移が起こる条件を表す. 状態 s1 において, f2 が 1 サに伴う制御回路の面積増加を抑制すると同時に, データパスのイクルで完了し f3 が 1 サイクルで完了しない場合, c2 c̄3 の枝

複雑度を抑制し回路の遅延の短縮を図る.

をたどって状態 s7 に遷移する.

上記の近似可変スケジューリング・バインディングを実装し,この可変スケジューリングにより DFG の実行に必要な平均生成された Verilog HDL 記述を Xilinx ISE 12.3 で論理合成

サイクル数は減少する. しかし, DFG によっては状態数が大した. 評価実験の結果, 従来の可変スケジューリングと比較し幅に増大する可能性がある. これによって合成後のデータパスて平均サイクル数は増加するが, 回路規模の指標となる LUTのマルチプレクサ (MUX) や制御回路の面積も増加する恐れが数と遅延を削減することができた.

ある.

2. 従来法の可変スケジューリングとバインディング
2. 1 不定サイクル演算

2. 3 可変スケジューリングに対応したバインディング
バインディングでは, 演算と演算の入出力値に対してそれぞれ演算器とレジスタの割り当てを行う. 可変スケジューリング
に対応したバインディングでは, 状態に依存して各演算に演算実行サイクル数がアドレスやオペランドの値に依存して変化器を割り当てる必要がある. 図 2 (a) の状態遷移グラフに対すする不定サイクル演算の例として, メモリアクセス演算や乗除る演算器バインディングの例を (b) に示す. 例えば, s1 では算などが挙げられる. メモリアクセス演算では, メモリセルア

f2 , f3 にそれぞれ M1 (乗算器 1), M2 (乗算器 2) を割り当て, s6

レイの同じ行に続けてアクセスする場合は高速であるが, そうでは, f4 に利用可能な M2 を割り当てる. また, s3 では, f4 にでない場合にはアクセスに多くのサイクル数を要することがあM1 を割り当てる. このとき, s6 で f4 に M2 を割り当てた場

る. 乗除算では, オペランドの値によっては少ないサイクル数合, s6 の遷移先である s4 (f4 の 2 サイクル目を行う制御ステッで計算を完了するものがある. また, エラー検出・回復方式によプ) では, f4 を M1 に既に割り当てている. このように, s4 でる演算回路 [3] でもクロックサイクルやオペランドの値に依存

f4 を M1 , M2 で実行するという衝突が生じる. この場合, s4 でして演算のサイクル数が変動する.

f4 の 2 サイクル目を M1 , M2 のどちらでも行えるように状態

本稿では, 演算の実行サイクル数はリストで与えられるものを複製し f4 を M2 で実行する状態 s′4 を作る必要がある. ことする. 例えば, < 1, 2, 3 > は演算に 1, 2, または 3 サイクルの結果, 状態数はさらに増加すると同時に, 同じ演算を異なる演要することを表す. (固定サイクル演算は要素数 1 のリストで算器に割り当てることに伴ってマルチプレクサや遅延が増加す

表す.)る恐れがある.

—2—

f3

f1

×f2 s1 f1 ＋

f2

＋ × ×

<1>

s2

< 1, 2 > < 1 , 2 >f4f4

イクル数を増加させることなく状態数を削減することができる.

,
1

図 4 (a) において, s8 (σ(s8 ) = 8.2) から c の有無により s9 と

s

s3

×f4

s10 に分岐するが, どちらの場合をたどっても, σ(s9 ), σ(s10 )f5 ＋

は 7.2 で等しいので分岐を c̄ に統合する. s10 が初期状態から

f5 ＋

s5

<1>

s1 f1 ＋ ×f3 ×f2
s2

×

s4

f5 ＋

×

1,2 >

s3

×

< 1, 2 >

f3 f

× ×2

到達できなければ s10 を削除する.
,

s4(着眼点 3) 平均サイクル数の短縮効果が小さい場合(b) サイクル数最大 (c) サイクル数最小(a) DFG

さらに, (着眼点 2) の考え方を進め, 分岐の遷移先にある 2 状態

図 1: スケジューリングの結果

sx と sy の平均サイクル数 σ(sx ), σ(sy ) の差が小さければ平均

s1

1
1

f

c2 c3

c 2 c3s2 f 23

M2M1
c2c3 s1 f 1 1 1
f3 f2
1

1
3

f f21 c 2c 3
c2 c3

s
f22 7

f32

s6

f22 ff411

c4

s3

cc4

4

4

f41 c
4
s4

c4

f

2
4

s5

f

1
5

ssFF

c2 c3

サイクルの短縮効果が小さいと判断して分岐をせず遷移を統合

c2c3

c2c3

M M
s
s
f32 f22 7 f32M2 f f 1 6
4,
M2 M 1c 4 s4
s3
2
M1
f4 M2
c4
f41 c
4
c
s4 4 2M1s5 1
sF
f4
f5

s2

(a) スケジューリング

1
2
2

2

(b) バインディング

図 2: 可変スケジューリング・バインディングの結果する. 即ち, 0 <=β<= 1 なる定数 β に対して, σ(sy ) >= β · σ(sx )であれば分岐を無くし遷移を統合する. 例えば, 図 5 (a) のs1 から s2 , s6 への分岐に注目する. s2 , s6 から終了までのσ(s2 ), σ(s6 ) はそれぞれ 3.5, 2.5 サイクルで, それらの比は 0.7となる. β = 0.7 とすれば, 図 5 (b) のように s6 への遷移を無くし s6 を削除することができる. これにより, σ(s1 ) は 4.0 サ
イクルから 4.5 サイクルに増加するが, 状態数をさらに削減することができる.

s

4.0 1

3. 実行サイクル数の短縮効果を考慮した
可変スケジューリングの近似手法

s2

本稿では, 近似可変スケジューリングの一手法として, 状態遷s3移グラフにおいて総サイクル数の改善に貢献しない場合に遷移

2.5の分岐を削除することにより, できるだけ性能を低下させずに

s

4.0 1

f11 f31 f 1 c2 c3

c 2c 3c 2 c3c 2c 32
2 s7
3.5 f 3 f 2 3.5

2.5

s6

f32

f22 f41

c4

f

1
4

s4

f

2.0

状態数を削減する手法を提案する.

s5

2
4

c4

s2

c4

s3

f

f

1
4

s4 c4 2 s5
f4 1.0

sF

1
5

2.5

f22 f41
c4

c4

2.0

(a) 分岐削除前

3. 1 スケジューリングにおける状態数削減の着眼点

s6

f32 f22

3.5

c4

1.0

c3

c3

2.5

c4

f11 f31 f 1
2

2

sF

f51

(b) 分岐削除後

図 3: 遷移先が一致する場合の状態削除例

状態 s からの平均サイクル数 σ(s) を s から最終状態までのサイクル数の平均値と定義する. 例えば, 図 3 (a) において,σ(s5 ) = 1.0, σ(s4 ) = 2.0 であり, σ(s3 ) は両状態 s4 , s5 への

s8
8 .2

c

c

s9

遷移確率が等しいと仮定すると 2.5 となる. 初期状態 s1 から

s8
8 .2

7.2

s10

s9

7.2

7 .2

の平均サイクル数 σ(s1 ) が全演算の実行に要する平均サイクル数となる. 本近似手法の着眼点は次の通りである.

(a) 分岐削除前(着眼点 1) 2 状態の遷移先が一致する場合(b) 分岐削除後

図 4: 平均サイクル数が等しい場合の状態削除例

可変スケジューリングにより得られる状態遷移グラフにおいて,

s

4.0 1

ある状態から完了信号 c により分岐した 2 状態に注目する. こ

維持したまま状態数を削減できる. 例えば, 図 3 (a) において,
状態 s1 から (c¯3 の条件下で) c2 により分岐する s2 , s7 に着目する. 両者の遷移先は同じ s3 なので, この分岐 (完了信号 c2 )による平均サイクル数の短縮効果は得られない. そこで, s1 から s7 への遷移を無くし s2 への遷移に統合する. s7 は初期状
態から到達できない状態になるので削除する. 同様に, s1 から(c3 の条件下で) c2 により分岐する s3 , s6 に着目すると, 遷移を c¯2 c3 に統合できる. 以上の結果, 実行サイクル数を増加させることなく (b) のように状態数を削減できる.

(着眼点 2) 2 状態からの平均サイクル数が等しい場合

s2
3.5

4.5 1

c3

2

の 2 状態からの遷移先が全て一致していれば, c による分岐を
削除 (遷移を c̄ 側に統合) することにより, 平均サイクル数をs

f11 f31 f 1

c3

s6

f32 f222

2.5

f22 f41

c4

s

3
2.5

f41
s4

2.0

c4

f42

s5
1.0

f11 f31 f 1

c4

f(a) 分岐削除前

3.5

f32 f22

s

3
2.5

c4
1
5

s2

sF

f41
s4 c4 2 s5
f4 1.0

c4

2.0

f51

sF

(b) 分岐削除後 (β = 0.70)

図 5: 平均サイクル数の短縮効果に注目した状態削除例

3. 2 実行サイクル数の短縮効果を考慮した近似アルゴリズム3.1 節の考え方に基づく可変スケジューリングの近似アルゴ
リズムを図 6 に示す.

次に (着眼点 1) を一般化し, 分岐の遷移先にある 2 状態 sx , sy

01 〜 05 行目の main では再帰関数 var scheduling を呼が σ(sx ) = σ(sy ) を満たすとき, 両状態からの遷移先が一致しび出して, 与えられた DFG の可変スケジューリングを行う.

ていなくても分岐をせずに遷移を統合する. これにより, 平均サ

var scheduling は, 未スケジューリングの演算の集合 O と, 実
—3—

行が完了した演算の集合 OF を受け取って, 可変スケジューリ

4. 状態独立なバインディングによる可変スケジューリングの近似手法

ングを行い, 得られる状態遷移グラフの先頭状態を返す. (ここでは, s1 が初期状態となる.)

4. 1 バインディングにおける状態数削減の着眼点

07 〜 12 行 目 の var scheduling で は, 08 行 目 で 新 た な状態 s を作り, 09 行目で状態 s に実行可能な演算をスケ

2.3 節で述べた通り, 演算の演算器へのバインディングは状態

ジュー ル し, 10 行 目 で s 以 降 の ス ケ ジュー リ ン グ を 行 う.

に依存して変化するが, これが状態数の増加だけでなく, デー

SCHEDULE(s, O, OF ) は, OF の実行が完了しているとタパスの複雑化を引き起こす. 可変スケジューリングに対応し

きに O のうち実行可能なものを s にスケジューリングする.

たバインディングの結果を図 7 (a) に示す. s4 では f4 を M1 ,OS は s でスケジューリングした演算の集合, OI は s で実行

M2 の両方で実行する可能性があるので (f4 を s3 では M1 に,が完了する可能性と完了しない可能性の両方がある演算の集合,

s6 では M2 に割り当てるため), s4 , s′4 のように状態分割が生じ

OF′ は s で実行が完了する演算の集合である. 関数 next は,

状態数が増加する. 図 7 (a) から生成されるデータパスは図 8

OI , 未スケジューリングの演算の集合 O − OS , s までで完了し(a) のようになる. レジスタ R1 と R3 の値を使う f4 は状態に′た演算の集合 OF ∪ OF

依存して M1 , M2 の両方で行うので, これを切り換えるためのを受け取り, s の次のスケジューリング

を行って, s の次状態を返す.

マルチプレクサが必要になり, 回路面積および遅延が増加する.

14 〜 29 行目が関数 next の処理過程である. 15 〜 17 行目

そこで, 第 2 の近似手法では, 状態に依存せずに各演算を一は, 分岐の可能性がない場合の処理であり, var scheduling を意に演算器にバインディングし, 矛盾が生じる状態を削除する.

呼び出して次状態以降のスケジューリングを行う. 18 行目以

これにより, 制御回路の縮小化および演算器への入力部のマル降が, 遷移の分岐を作成する処理である. 19 〜 21 行目で, OI

チプレクサの削減による生成回路の面積の削減や遅延の短縮をの 1 つの要素 f1 に対して, next を再帰的に呼び出して遷移狙う. 例えば, 図 7 (a) において, f2 , f4 を M1 に, f3 を M2の分岐を作成する. 20 行目は f1 が完了しなかった場合の遷移に一意 (状態に依存せず) に割り当てるとする. すると, s6 では

先を, 21 行目は f1 が完了した場合の遷移先をそれぞれ返す.

f2 , f4 を同一演算器 M1 で実行するという矛盾が生じるので s6

22 〜 27 行目では, 分岐の統合判定を行う. 22 行目において,σ(x1 ) >= β · σ(x0 ) を満たせば, 分岐を作らず, f1 が完了しなを削除する. ここで, s6 は s1 から (c¯2 の条件下で) c3 によりかった場合の遷移 x0 を返す. そうでなければ, 24 〜 26 行目に合する. これによって, f4 は状態に依存せず M1 で実行される

おいて分岐節点 x を作ってこれを返す. 24 行目の BRANCH

ので, MUX3, MUX4 が不要になり, 回路面積と遅延が削減では, f1 の完了信号 c(f1 ) が得られないときには x0 に, 得られ

きる. ただし, これによって平均サイクル数は増加する可能性

るときには x1 に分岐する分岐節点 x を作る. 25 行目では, xがある.

分岐する状態の 1 つなので, 図 7 (b) のように遷移を c¯3 に統の平均サイクル数 σ(x) を計算する. p(c(f1 )) は c(f1 ) が得ら

c2c3 s1 f 1
1

れない確率, p(c(f1 )) は c(f1 ) が得られる確率を表す.
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

main() {O = { 全演算 };OF = ϕ;s1 = var scheduling(O, OF );}State var scheduling(O, OF ) {s = new State;′(OS , OI , OF
) = SCHEDULE(s, O, OF );′s.next = next(OI , O − OS , OF ∪ OF)
return s;}State next(OI , O, OF ){if (OI == ϕ) {return var scheduling(O, OF );}else {
f1 ∈ OI ;x0 = next(OI − {f1 }, O, OF );x1 = next(OI − {f1 }, O, OF ∪ {f1 });if (σ(x1 ) >= β · σ(x0 )) { return x0 ; }else {
x = new BRANCH(c(f1 ), x0 , x1);
σ(x) = p(c(f1 )) · σ(x0 ) + p(c(f1 )) · σ(x1 );return x;}}}

図 6: 可変スケジューリングの近似アルゴリズム

f41
c4

sF

s2

c2 c3

M 12 M 1f3 f21s
f32 f22 7
M2 M 1
s3
M1
f41 c
4
c
s4 4 2M1s5
f4

c 2c3 s1

c2c3

2

c2c3

M1 M2
s
f32M2 f 22 f 1 6 f 1
44,

c 4 s4 c 4

c4

f

M2M1
f11 f31 f 1

f42M2
sF

1
5

(a) 可変バインディング

sF

c2

s
f22 7
M M1
s3
M1
f 41 cs2 f 2

3
2

s4

c4

c 2 c3f32M2

4

s
f M1 5
2
4

sF

f51

(b) 状態に依存しないバインディング

図 7: バインディングの結果

4. 2 状態独立なバインディングによる可変スケジューリングの近似アルゴリズムの流れ
状態独立なバインディングによる可変スケジューリングの状
態遷移グラフのサイズの削減は, 次の手順により行える.

(Step 1): 可変スケジューリングを行う.
(Step 2): 可変スケジューリングの初期状態から終了状態へ至る最長のパス (遷移の条件が全て完了信号の否定リテラルの積である状態の系列) に対してバインディングを行う.

(Step 3): (Step 2) のバインディングで矛盾が生じる状態 (矛盾状態) を全て削除する. 矛盾状態とは, その状態にスケジューリングされた複数の演算に同一の演算器がバインディングされているような状態である.

(Step 4): 削除された状態に, ある状態 s から完了信号 c をラベ

—4—

δ(s)
δ(s)

制
御
回
路

s1

MUX5
R1

R2

δ(s)
δ(s)

θ(c)

R3

R5

R4

MUX1

MUX2

MUX3

M1
f2 f 4ALU

f1 f 5f11 f31 f 1 c 2c 3
2

c2 c3

R6

c 2 c3

MUX4

s2 f 2

M 2
f3 f4

3

演算を実行する演算器は状態に依存
MUX が増加 ? 遅延が増加

s
f22 7

s6

f32

f
s4

1
4

s2

f

s5

2
4

c4

f

c2 c3

s4

sF

1
5

c2c3

s
f32 f22 7
M2 M 1
s3
M1
f41 c

c4

c4

c 2c3

2

f22 f41c4s3(a) 可変バインディングによる生成データパス

c2 c3

M2M1
f11 f31 f 1

c2c3 s1

c4

f32
c4

s
f 22 f41 6
c4

4s
f M1 5
2
4

sF

f51

δ(s)
MUX5

δ(s)

制
御
回
路

R1

R2

δ(s)
δ(s)

θ(c)

R3

R5

R4

MUX1

(a) 可変スケジューリングの結果 (b) 最長パスのバインディングの結果

R6

M 2 M1
f11 f31 f 1

c 2c3 s1

MUX2

M1
f2 f 4ALU

f1 f 5

M 2
f3

s2

演算を実行する演算器は状態に依存
MUX が増加 ? 遅延が増加(b) 状態に依存しないバインディングによる生成データパス
図 8: データパス

c2 c3

s
f32 f22 7
M2 M 1
s3
M1
f41 c
s4

ルに持つ遷移があった場合には, それを s から c̄ をラベルに持つ遷移に統合する. 逆に, 削除された状態に, ある状態 s から完了信号 c̄ をラベルに持つ遷移があった場合には, s を削除する.

(Step 5): (Step 3), (Step 4) によって, 初期状態から到達できなくなる状態を全て削除する.

4

c4

f

2
4

M1s5

c2c3 s1c 2c 32M 2 M1
f11 f31 f 1
2

c

c2 c3

2
1 1
M1 MM
ss s 2 2s
f32
f22 f41f416 6 2 f3 f 2 7, ,M2 M 1c4
s4 s4 s3
1M 1

f4

c4

f51

sFsF

s4

(c) 矛盾状態の発生 (s6 )

c4

c2c3

f32

c4

s
f M1 5
2
4

f51

sF

(d) 遷移の統合

図 10: 状態に依存しないバインディングの流れ

dows 上の Cygwin 環境で動作する.
合成結果を表 1 (a) 〜 (c) に示す. 論理合成で使用した ISE

上記 (Step 4) の例を図 9 に示す. s1 は c により分岐を持ち,のオプションは表 2 の通りである. matrix41.c は 4 次正方行

s2 または s3 に遷移するものとする. (a) は矛盾状態 s3 を持つ

列と 4 次元ベクトルの積計算, matrix3 g1.c は 3 次正方行列同とする. (a) においては, s3 は削除されているので (b) のよう

士の乗算, det3.c は 3 次元の行列式計算をそれぞれ行う C プに c̄ の遷移に統合する. また, (c) は矛盾状態 s2 を持つとする.

ログラムである. (a) において, 演算器には ALU 3 個, MUL(c) においては, s2 は削除されているので遷移を c の遷移に統(乗算器) 2 個, LDST (メモリアクセスユニット) 1 個を用いた.

合することができない. ゆえに, (d) のように s1 , s3 も矛盾状

乗算のサイクル数は, 等確率で 1 または 2 になるものとし, 加態として削除する.

算とメモリアクセス演算は 1 サイクル固定とした. 従来法を含(Step 1) 〜 (Step 5) によって, 図 7 (b) の状態遷移グラフをむ 8 種類の手法について, 平均サイクル数, 状態数, LUT 数,得る過程を図 10 に示す. スケジューリング結果 (a) に対して,遅延を示している. 「max」は演算の実行サイクル数を最大とまず, パス s1 s2 s3 s4 s5 にバインディングを行う. その結果, (b)仮定としてスケジューリングを行ったものである. 「min」はのように, f2 , f4 は M1 に, f3 は M2 に割り当てたとする. (c)演算の実行サイクル数を最小と仮定してスケジューリングを行

では, s6 において, f2 と f4 の両方を同時に M1 を割り当てる

い, そのサイクルで終了しなかったら回路全体をストールさせことになるので, s6 は矛盾状態とし削除する. (d) では, s1 かるものである. 「可変」は従来の可変スケジューリングとバイら (c¯2 の条件下で) c¯3 に遷移を統合する. 結果, 図 7 (b) と同

ンディングの結果である. 「近似 (1) 」は平均サイクル数を考じ状態遷移グラフを得る.

慮した可変スケジューリングを行ったものであり, β は遷移の

s1

s2

c

s1
c

s3

統合の基準値を示す. 「近似 (2)」は状態独立なバインディングs 3 s2s3による可変スケジューリングの結果である. 「可変」は「max」
より約 7% の平均サイクル数を減少させたが, 状態数, LUT 数(a) c 側に矛盾状態がある場合
s1
s1

s2

c

(b)s (a) の削除後がそれぞれ約 5.3 倍, 約 2.5 倍増加し, 遅延も約 9.6% も増加

1

s1
c

s3

s 3 s2(c) c̄ 側に矛盾状態がある場合

c

した. 近似 (1) において基準値 β = 1.00 のとき, 「可変」と
cs3

比較すると LUT 数を 約 6.7% 削減した. β の値を徐々に下げることにより, 回路規模の抑制と遅延を短縮することができた.

(d) (c) の削除後

β = 0.88 では, 「可変」と比較すると, LUT 数は約 39.5% 削減した. β をある程度まで下げると, 「max」の回路と等価に

図 9: 状態遷移グラフの矛盾状態の削除例

5. 評 価 実 験
本稿で提案する可変スケジューリングの近似アルゴリズムをなる. β の設定方法は, LUT 数を許容範囲まで減少させ, 平均
サイクル数の短縮効果を維持できる値まで下げることが必要となる. 「近似 (2)」は,「可変」よりも LUT 数を約 29.5% 削減
し遅延を約 7.8% 短縮した.

高位合成システム ACAP [4] 上に実装し, FPGA Xilinx Spar-(b), (c) においても, 状態数や LUT 数の減少傾向は (a) とtan3E 上に Xilinx ISE 12.3 で論理合成を行った. ACAP は同様である. 特に, (b) では, 「近似 (1)」は,「可変」よりも平

Perl (5.10.1) で実装されており, Linux, Mac OSX 及び Win-

均サイクル数が約 6.6% 増加したが LUT 数を約 52.5% 削減で—5—

表 1: 論理合成結果(a) matrix41.c
max

min 可変 [2]近似 (1)

近似 (2)

β = 1.00 β = 0.96 β = 0.92 β = 0.88
平均サイクル数

39.00 40.53

36.14

36.14

36.69

37.08

38.00

37.11

状態数

39

34

206

154

131

78

45

81

LUT 数

2367

2589

6008

5605

5455

5292

3633

4236

遅延 (ns)11.88 11.77

13.02

13.15

12.85

12.89

12.52

12.01

演算器数: ALU:3, MUL:2, LDST:1
実行サイクル数: + < 1 >, ∗ < 1, 2 >, M< 1 > 確率: + < 1 >, ∗ < 0.5, 0.5 >, M< 1 >(b) matrix3 g1.c
max

min

可変 [2]

近似 (1)

近似 (2)

β = 1.00 β = 0.98 β = 0.96
平均サイクル数

44.00

45.56

39.39

39.39

39.41

41.98

41.11

44

35

804

410

408

110

222

状態数

LUT 数

3633

3649

13318

7925

8009

6326

6662

遅延 (ns)

12.10

12.07

13.69

13.74

14.50

12.95

13.97

演算器数: ALU:3, MUL:2, LDST:1
実行サイクル数: + < 1 >, ∗ < 1, 2 >, M< 1 > 確率: + < 1 >, ∗ < 0.5, 0.5 >, M< 1 >(c) det3.c
max

min

可変 [2]

近似 (1)

近似 (2)

25.00

21.66

19.08

19.08

19.24

20.4

状態数

25

16

114

81

69

47

76

LUT 数

1031

911

2319

2045

1925

1641

2025

遅延 (ns)

11.76

11.48

14.87

12.95

15.66

12.12

11.81

β = 1.00 β = 0.95 β = 0.90
平均サイクル数

20.38

演算器数: ALU:1, MUL:2, LDST:1
実行サイクル数:+ < 1 >, ∗ < 1, 2 >, M< 1, 4 > 確率:+ < 1 >, ∗ < 0.5, 0.5 >, M< 0.8, 0.2 >きた. 「近似 (2)」は,「可変」よりも平均サイクル数が約 4.4%

法を 2 つ提案した. 本手法により, 平均サイクル数を維持した

増加したが LUT 数を約 50.0% 削減できた. (c) は,「近似 (2)」まま, あるいは犠牲にして, 状態数増加を抑制し, 合成される回の効果があるもので, 遅延が「可変」よりも約 20.6% 短縮した.

路のサイズや遅延を削減できる可能性があることを確認した.

しかし, 遅延に関しては β を小さくしても, 「近似 (2)」でも改今後の課題として, 可変スケジューリングにおいて生成回路善されない (むしろ悪化する) 場合がある. この原因は判明しての規模の削減や性能を向上させるための状態符号化について検いないが, 一因としては, 状態数の変化に伴う状態割り当ての変討する必要がある. また, マルチプレクサによる遅延を削減す化が考えられる.

るための手法を考案する必要がある.

状態数と平均サイクル数は概ねトレードオフの関係にある.
生成回路の面積の指標となる LUT 数の増減は, 回路制御部分となる状態数とデータパス上のマルチプレクサ数, 配線数の影響が大きいと考えられる.

謝辞

本研究を進めるにあたり, 御助言・御討論を頂きました

京都高度技術研究所の神原弘之氏, 立命館大学の冨山宏之教授,
元立命館大学の中谷嵩之氏, 元関西学院大学の戸田勇希氏, および関西学院大学石浦研究室の諸氏に感謝します.
文

表 2: ISE のオプション

献

FSM Style

LUT[1] D. D. Gajski, N. D. Dutt, A. C-H Wu, and S. Y-L Lin: High-RAM Extraction

NO

Level Synthesis: Introduction to Chip and System Design,

ROM Extraction

NO

Kluwer Academic Publishers (1992).

Mux Style

MUXCY

Mux Extraction

YESof Dynamic Execution for High-Level Synthesis,” in Proc.

Multiplier Style

AUTO

SASIMI 2009, pp. 107–112 (Mar. 2009).

Automatic Register Balancing YES
Optimization Goal

Speed[2] Y. Toda, N. Ishiura, and K. Sone:“Static Scheduling[3] 右近, 井上, 高橋, 谷口: “エラー検出回復方式における加算器の性能評価,” 信学技報, VLD2009-121, pp. 133–137 (Mar. 2010).

[4] 池上, 石浦: “MIPS アセンブリを中間表現とする高位合成,” 情

6. む す び処関西支部大会 2008, A-03 (Dec. 2008).

本稿では, 高位合成における可変スケジューリングの近似手—6—