本手法の概要

第3章 関連研究

第3章 関連研究 CDFGの他に表3.3に示す演算器数，時間オーバヘッドを入力とした．

表 3.3: Wuの手法の入力．

乗算器数 加算器数 許容される時間OH

4 2 1

まずはじめに，入力CDFGの下に同一のCDFGを再計算用CDFGとして付加 した図3.8を考える．

C1

C2

C3

C4

M1 M2 M3 M4

A1 A2

A1

x1 x2 x3 x4

+1 +2

+3

C5

C6

x1 x2 x3 x4

+1 +2

+3 normal comp.

recomputation

図 3.8: Wuの手法の設計過程CDFG1．

次にこのCDFGの再計算部をいくつかのサブCDFGに分割していく．その分

割方法はKarriらの手法と異なる．ここではCDFGを分割する際にスケジューリ

ング後のアロケーションのしやすさを意識した独自の分割手法を用いている．Wu

第3章 関連研究 らの手法では，まず，再計算用CDFGの入力エッジに続くオペレーションを示す 入力ノード，つまり，この例ではｘ1，ｘ2，ｘ3，ｘ4のいずれかを選ぶ．この 例ではｘ1を選ぶことにする．選んだこのノードがこれから作るサブCDFGの第 1ノードとなる．そして，選んだノードと出力エッジでつながるノードと，選ん だノードに入力データを与えているノードである隣接ノードをそのサブCDFGに 加える．さらに，サブCDFGに加えられたノードの隣接ノードを加えていく．こ の操作を繰り返し，サブCDFGに含まれていない隣接ノードがなくなれば1つの サブCDFGができあがるのである．その際に，注意すべき点が1つある．Wuら の手法では，その後のアロケーションであらかじめ入力として与えられた演算器 数を越えるようなアロケーションを行うことをしないために，この分割後のスケ ジューリング結果が最悪，分割後のあるサブCDFGとその通常計算サブCDFGと 同一クロックサイクルにスケジューリングされるような結果であった場合に，そ のクロックで演算器が不足するということが起こりうる．そのようなケースを回 避するために，分割段階からサブCDFG内の同一クロックサイクルに含まれる同 種オペレーション数を与えられた演算器数の半分以下とする．ｘ1から始まるサ ブCDFGが完成すると，次に，まだサブCDFGに含まれていない入力ノードを 選択し，同様の操作を行う．全てのノードがサブCDFGに分割されればこの操作 の終わりとなる．その結果を図3.9に示す．

分割後はスケジューリングを行っていく．このスケジューリングは大きなサブ CDFGから順に行っていくこととする．この例ではサブCDFG R1，R2の順に スケジューリングしていくことになる．サブCDFG内のエッジが切断されない範 囲で演算器が空いており，かつ，可能な限り早いクロックサイクルにスケジュー リングを行う．全てのサブCDFGのスケジューリング終了後にその結果が入力と なっている許容される時間オーバヘッドを満たしていればスケジューリング終了 となる．もし，許容される時間オーバヘッドを満たしていなければ，サブCDFG のエッジを切断してもよいとして演算器があいているなるべく早いクロックサイ

第3章 関連研究

C1

C2

C3

C4

M1 M2 M3 M4

A1 A2

A1

x1 x2 x3 x4

+1 +2

+3

C5

C6

x1 x2 x3 x4

+1 +2

+3 normal comp.

recomputation R1

R2

図 3.9: Wuの手法の設計過程CDFG2．

第3章 関連研究 この例でのスケジューリング結果を図3.10に示す．この例では最初に分割した サブCDFGをさらに分割することなく時間オーバヘッドを満たすことができた．

C1

C2

C3

M1 M2 M3 M4

A1 A2

A1

x1 x2 x3 x4

+1 +2

+3

x1 x2 x3 x4

+1

+2 +3

normal comp.

recomputation C4

normal comp.

R1 R2

図 3.10: Wuの手法の設計過程CDFG3．

ここにfault-secure設計を満たすようにアロケーションを行い終了する．ここ

で，この例では再計算用サブCDFGのfault-secureを保証するためにサブCDFG

R1，R2の出力にそれぞれ比較器が必要となるため，2つの比較器を加えることに

なる．Wuらの手法による設計結果を図3.11に示す．

3.4.3 本手法のまとめ

この手法による出力結果と前節，図2.2，2.3に示したfault-secure設計の例との 比較結果を表3.4に示す．

Wuらの手法ではあらかじめ使用する演算器数を決めて入力とするために面積 オーバヘッドはその入力に関係する．この例では，乗算器，加算器の付加を許さ

2 CDFG

第3章 関連研究

C1

C2

C3

M1 M2 M3 M4

A1 A2

A1

x1 x2 x3 x4

+1 +2

+3

x1 x2 x3 x4

+1

+2 +3

normal comp.

recomputation C4

normal comp.

R1 R2

M3 M4 M1 M2

A2

A2 A1

図 3.11: Wuの手法の設計結果CDFG．

表 3.4: Wuらの手法の比較．

乗算器数 加算器数 比較器数 面積OH 時間OH

入力  4 2 0 – –

例1 8 4 1 7 0

例2 4 2 1 1 3

Wuの手法 4 2 2 2 1

第3章 関連研究 用CDFGを分割しスケジューリングするという方法をとっていたが，Wuらは，あ らかじめ演算器数を決めておき，その中で時間オーバヘッドを満たすべく再計算 用CDFGを分割していくという違いがあった．

この例ではスケジューリング中にさらにサブCDFGを分割する必要はなかった が，大規模なCDFGや，演算器数を抑えた設計要求の場合には必然的に再分割の 必要があり，比較器の数が増え，面積オーバヘッドが増えるケースがあることも 考えられる．しかし，この手法では演算器数を設計者があらかじめ入力できるこ とを利用し，あまりにも分割が進むようなケースではある程度の演算器数の増加 を許すことで比較器を減らすといった方法もとれる．同様に，入力する演算器数 を変えられることで，面積オーバヘッドと時間オーバヘッドのトレードオフのバ ランスをとりうることが可能となる．このような柔軟性の高さにもこの手法の特 長があると言える．