chapter 6 最近の更新履歴 Hideo Fujiwara

(1)

第６章高位合成

2

6.1 _{高位合成の流れ}

(2)

3

6.1 _{高位合成の流れ}

与えられた動作記述をコントロール／データフローグラフ

（CDFG, Control/Data-Flow Graph^）で表現

CDFG(Control/Data-Flow Graph) _生成

(3)

5

スケジューリング

CDFGに現れる各演算操作を

どの時刻に実行するかのスケジュールを決める各時刻に演算操作を割り当てることを

スケジューリングという時刻: クロックサイクルコントロールステップ

制約と最適化の目標を決め与えられた制約のもとで最適なスケジュールを求める

制約や最適化の目標：時間（コントロールステップ数）

面積（演算器の個数）

6

スケジューリング

ALAPスケジューリングでは乗算器が２個に減るが加算器は２個必要 ASAPスケジューリングでは

乗算器が３個必要

(4)

7

バインディング

バインディングは

スケジューリングされた_CDFGに現れる各演算操作や変数に

具体的な演算器やレジスタ、メモリを割り当てる処理

バインディング

(5)

9

バインディング

３つのレジスタが必要レジスタR1, R2, R3

R_{１： h1, h5} R_{２： h2, h4} R_{３： h3}

10

バインディング

(6)

11

RTL _{回路記述生成}

マルチプレクサ方式かバス方式により割り当てられた演算器やレジスタ間の結線を実現

これによりデータパスが生成

生成されたデータパスで CDFGの動作を実現するために制御信号を生成するコントローラを生成

RTL _{回路記述生成}

マルチプレクサ方式により演算器やレジスタ間の結線を実現

これによりデータパスが生成

(7)

13

RTL _{回路記述生成}

生成されたデータパスで CDFGの動作を実現するために制御信号を生成するコントローラを生成

14

6.2 コントロール／データフローグラフ

(8)

15

6.2 コントロール／データフローグラフ

6.3 _{スケジューリング}

スケジューリングを行うにあたって CDFGに現れる演算を実現するためにどのような種類の演算器をどれだけ使うかを決める

加算については加算器か加減算器か_ALUか乗算については並列乗算器かパイプライン乗算器かまたそれらのビット幅、処理速度（遅延時間）、面積、等々を含み

演算器の種類とその個数を選ぶ

(9)

17

6.3 _{スケジューリング}

18

6.3 _{スケジューリング}

リソースライブラリから遅延時間が_{6 ns}で処理できる加算器と

16 nsの乗算器を選んだとする

演算器の遅延時間以外の遅延時間

（バス、マルチプレクサ、レジスタの遅延時間）を考慮して

１クロックサイクルで加算や乗算を完了するために１クロックサイクルを_{20 ns}に設定したとする

(10)

19

ASAP _ALAP

まず、加算器や乗算器の個数などの制約なしでスケジューリングすることを考える

考慮しないといけないのは

CDFGに示された演算の順序の依存関係だけ

できるものから先に処理する ASAP (As Soon As Possible)^{スケジューリング}

できるだけ後に処理する

ALAP(As Late As Possible)^{スケジューリング}

ASAP _{スケジューリング}

(11)

21

ALAP _{スケジューリング}

22

ASAP vs. ALAP

ALAPスケジューリングでは乗算器が２個に減るが加算器は２個必要

最小のクロックサイクル数３で実現１クロックサイクルが_{20 ns}なので全体で_{60 ns} ただ、演算器を多く使うため面積が大きくなる

ASAPスケジューリングでは乗算器が３個必要

(12)

23

面積制約（１乗算器、１加算器）

乗算器を１個、加算器を１個という制約を考え最小のクロックサイクル数の

スケジューリング

４クロックサイクルとなり１クロックサイクル増える

面積を最小にしているが全体の時間は 80 ns^{と長くなる}

面積制約（２乗算器、１加算器）

制約を変えて乗算器を₂個、加算器を１個

の制約のもとで時間最小のスケジュール

クロックサイクル数が３と減り ALAPより加算器が一つ減る

(13)

25

多サイクル演算、制約（１乗算器、１加算器）

複数のクロックサイクルにまたがって実行する演算を多サイクル(multi-cycle)^演算

１クロックサイクルを_{10 ns} とすると

乗算器１個，加算器１個という制約のもとで時間最小のスケジュール

乗算は２クロックサイクル

演算器数が最小

時間は８クロックサイクル 80 ns

26

多サイクル演算、制約（２乗算器、１加算器）

１クロックサイクル_{10 ns} 乗算器２個、加算器１個

の制約のもとで時間最小のスケジュール

５クロックサイクル全体の時間は_{50 ns}

これまで考えた中で時間最小の最もパフォーマンスが良い

スケジュール

(14)

27

比較、制約（２乗算器、１加算器）

制約（乗算器２個、加算器１個）１クロックサイクル：₂０_ns

クロックサイクル数：３全体の時間：_60ns

制約（乗算器２個、加算器１個）１クロックサイクル：₁０_ns

クロックサイクル数：₅ 全体の時間：_50ns 多サイクル演算を考えることで、同じ面積制約でもより短い時間のスケジュールを求めることができる

チェイニング

多サイクル演算ではクロックサイクル時間を短縮し一つの演算を複数のクロックに渡って実行するのに対して

反対に、クロックサイクル時間を延ばし１クロックサイクル内に複数の演算を連続して実行する

チェイニング_(chaining)

(15)

29

演習問題

つぎの動作記述のDFGに対して

y = ((a*b)+c)+(d*e)-(f+g)

つぎの各制約のもとでスケジューリングを行え (1) 乗算器１個、加減算器１個

すべての演算は１時刻で実行可能 (2) 乗算器1個、加算器2個、減算器１個

乗算器は実行に２時刻かかるマルチサイクル演算 (3) 乗算器２個、加算器１個、減算器１個

乗算器は実行に２時刻かかるマルチサイクル演算

30

演習問題１（(1)解答例）

y = ((a*b)+c)+(d*e)-(f+g)

(1) 乗算器１個、加減算器１個すべての演算は１時刻で実行可能

１クロックサイクル_{20 ns} ４サイクル _80ns

*

a b

+

−

+ c d e f g

y +

*

(16)

31

演習問題１（(2)解答例１）

y = ((a*b)+c)+(d*e)-(f+g)

(2) 乗算器1個、加算器2個、減算器１個

１クロックサイクル_{10 ns} 6^サイクル_60ns

*

a b

+

−

+

*

c d e f g

y +

演習問題１（(2)解答例２）

y = ((a*b)+c)+(d*e)-(f+g) = ((a*b)+(c+((d*e)-(f+g)))

a b

−

+

*

c d e f g

(17)

33

演習問題１（(2)解答例３）

y = ((a*b)+c)+(d*e)-(f+g) = ((a*b)+c)-(f+g)+(d*e)

*

a b

+

−

+

*

c f g d e

y

34

演習問題１（(3)解答例）

y = ((a*b)+c)+(d*e)-(f+g)

(3) 乗算器２個、加算器１個、減算器１個

*

a b

+

−

+

*

c d e f g

y

(18)

35

6.4 _{バインディング}

演算に必要な入力データはその演算が行われている間その値を保持し

その演算結果の値は

そのクロックサイクルの終了時まで保持する必要がある

これらの値の保持は

レジスタやメモリ（１ポートメモリか２ポートメモリ）などの記憶回路で行う

CDFG^において

演算に使われる入力や演算結果を変数で表しそのような変数の値を保持する記憶回路の

種類とその個数を決める処理をレジスタ（メモリ）アロケーションという

スケジュールされたDFG

(19)

37

レジスタのライフタイム

38

レジスタのバインディング

同じ時刻では

一つのレジスタには一つの内部変数しか割り当てることができない

少なくとも３つのレジスタが必要レジスタR1, R2, R3

R１： h1, h5 R２： h2, h4 R３： h3

(20)

39

演算器のバインディング

スケジュールされた各演算にリソースアロケーションで選択した

演算器を割り当てる

（バインディング１）乗算器１（＊１）： op1, op3 乗算器２（＊２）： op2, op4

（バインディング２）乗算器１（＊１）： op1, op4 乗算器２（＊２）： op2, op3

演算器のバインディング

(21)

41

データパスの構成

バインディングしたレジスタ_{R1, R2, R3}、および

乗算器１、乗算器２、加算器を配置

42

データパスの構成

レジスタ、演算器および入力a, b, c, d, e, f^、

出力_{x, y}の間の接続関係をスケジュールされた_DFG

とバインディング情報から求めるつづいて

まず乗算器１について接続関係を求める

(22)

43

R１： h1, h5

乗算器１の接続関係

乗算器１：左入力（_{a, e}）、右入力（_{b, f}）、出力（_R1）

スケジュールされたDFG

演算器バインディングレジスタバインディング

データパスの構成

乗算器１：左入力（_{a, e}）、右入力（_{b, f}）、出力（_R1）

(23)

45

データパスの構成

つづいて

乗算器２について接続関係を求める

46

R2： h2, h4

乗算器２の接続関係

乗算器２：左入力（_c）、右入力（_{d, h3}）、出力（_R2）

データパスの構成

演算器バインディングレジスタバインディング

(24)

47

乗算器２：左入力（c）、右入力（d, R3）、出力（R2）

データパスの構成

R2： h2, h4 R3: h3 h3 = R3

データパスの構成

つづいて

加算器について接続関係を求める

(25)

49

レジスタバインディング R1: h1, h5 R2: h2, h4 R3: h3

データパスの構成

左入力（a, h1, h5) = (a, R1) 右入力（b, h2, h4) = (b, R2) 出力（h4, h3) = (R2, R3)

左入力（a, h1, h4) = (a, R1, R2) 右入力（b, h2, h5) = (b, R2, R1)) 出力（h4, h3) = (R2, R3)

50

加算器：左入力（a, R1）右入力（b, R2）出力（R2, R3）

データパスの構成

(26)

51

したがって、

乗算器１：左入力（_{a, e}）、右入力（_{b, f}）、出力（_R1）乗算器２：左入力（c）、右入力（d, R3）、出力（R2）加算器：左入力（a, R1）、右入力（b, R2）、出力（R2, R3）

が求まる

次に各レジスタについて接続関係を求める

データパスの構成

R１：入力（乗算器１(op1,op3)）出力（加算器左入力(h1,h5)）

(27)

53

データパスの構成

R2：入力（乗算器２(op2), 加算器）出力（加算器右入力(h2,h4), y）

54

データパスの構成

R2：入力（乗算器２(op2), 加算器）出力（加算器右入力(h2,h4), y）

R3：入力（加算器）

出力（乗算器右入力(h3)、x）

(28)

55

データパスの構成

R１：入力（乗算器１）出力（加算器左入力）

R2：入力（乗算器２, 加算器）出力（加算器右入力, y）

R3：入力（加算器）

出力（乗算器右入力, x）

データパスの構成

(29)

57

コントローラの構成

コントローラはデータパス内のマルチプレクサやレジスタへの

制御信号を発生する_FSM として設計

マルチプレクサへの制御信号を m1, m2, m3, m4

レジスタに値を取り込む制御信号を r1, r2, r3

58

コントローラの構成

時刻１（状態S１）でのマルチプレクサへの制御信号は m1=0, m2=0とし、他はドントケアとなる

(30)

59

コントローラの構成

時刻１（状態S１）でのマルチプレクサへの制御信号は m1=0, m2=0とし、他はドントケアとなる

コントローラの構成

(31)

61

コントローラの構成

時刻２（状態S2）でのマルチプレクサへの制御信号は m1=0, m2=0^{を保持し、レジスタ}R1, R2^{に演算結果を} 取り込むために、r1=1, r2=1m4=0, r1=1, r2=1

62

コントローラの構成

時刻3（状態S3）でのマルチプレクサへの制御信号はレジスタ_{R1, R2}の値を保持するために、_{r1=0, r2=0}、乗算器の入力に_{e, f}を選ぶために、_m1=1,

加算器の入力に_a,bを選ぶために_m3=0, 加算結果を_R3に取り込むために、_r3=1

(32)

63

コントローラの構成

時刻3（状態S3）でのマルチプレクサへの制御信号はレジスタ_{R1, R2}の値を保持するために、_{r1=0, r2=0}、乗算器の入力に_{e, f}を選ぶために、_m1=1,

加算器の入力に_a,bを選ぶために_m3=0, 加算結果を_R3に取り込むために、_r3=1

コントローラの構成

(33)

65

演習問題２

つぎの動作記述のDFGに対して

y = ((a*b)+c)+(d*e)-(f+g)

つぎの制約のもとで得られたスケジュールに対して、バインディングを行い、データパスとコントローラを生成せよ。

(1) 乗算器１個、加減算器１個すべての演算は１時刻で実行可能

66

演習問題２

y = ((a*b)+c)+(d*e)-(f+g)

スケジュール結果（乗算器１個、加減算器１個）

バインディングを行い、データパスとコントローラを生成せよ。

(34)

67

演習問題２（(1)解答）

(35)

69

演習問題２（(1)解答）

70

演習問題２（(1)解答）

(36)

71

演習問題２（(1)解答）

(37)

73

GCD _{の高位合成}

74

GCD _{の高位合成例１}

(38)

75

chapter 6 最近の更新履歴 Hideo Fujiwara

第６章 高位合成

6.1 高位合成の流れ

6.1 高位合成の流れ

CDFG(Control/Data-Flow Graph) 生成

スケジューリング

スケジューリング

バインディング

バインディング

バインディング

バインディング

RTL 回路記述生成

RTL 回路記述生成

RTL 回路記述生成

6.2 コントロール／データフローグラフ

6.2 コントロール／データフローグラフ

6.3 スケジューリング

6.3 スケジューリング

6.3 スケジューリング

ASAP ALAP

ASAP スケジューリング

ALAP スケジューリング

ASAP vs. ALAP

面積制約（１乗算器、１加算器）

面積制約（２乗算器、１加算器）

多サイクル演算、制約（１乗算器、１加算器）

多サイクル演算、制約（２乗算器、１加算器）

比較、制約（２乗算器、１加算器）

チェイニング

演習問題

演習問題１（(1)解答例）

*

−

*

演習問題１（(2)解答例１）

*

−

*

演習問題１（(2)解答例２）

−

*

演習問題１（(2)解答例３）

*

−

*

演習問題１（(3)解答例）

*

−

*

6.4 バインディング

スケジュールされたDFG

レジスタのライフタイム

レジスタのバインディング

演算器のバインディング

演算器のバインディング

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

データパスの構成

コントローラの構成

コントローラの構成

コントローラの構成

コントローラの構成

コントローラの構成

コントローラの構成

コントローラの構成

コントローラの構成

演習問題２

第６章高位合成

6.1 _{高位合成の流れ}

6.1 _{高位合成の流れ}

CDFG(Control/Data-Flow Graph) _生成

RTL _{回路記述生成}

RTL _{回路記述生成}

RTL _{回路記述生成}

6.3 _{スケジューリング}

6.3 _{スケジューリング}

6.3 _{スケジューリング}

ASAP _ALAP

ASAP _{スケジューリング}

ALAP _{スケジューリング}

6.4 _{バインディング}

GCD _{の高位合成}

GCD _{の高位合成例１}

GCD _{の高位合成例２}