Karri らの手法

この節では高位レベルにおけるfault-secure設計に関するKarriらの手法につい て説明する．

3.3.1 本手法の概要

前節で挙げたAntolaらの手法は入力CDFGに許容される時間オーバヘッドを 付加した上で，スケジューリングにより面積オーバヘッドを少なく抑えるといっ た手法であった．これに対し，Karriらは時間オーバヘッドを付加せずに面積オー バヘッドを少なくする方法を提案している．

この手法でもAntolaらの手法と同様にCDFGを入力として，そこに同一の CDFGを再計算用CDFGとして付加したものを考える．Antolaらの手法ではさ らに許容される範囲で時間オーバヘッドを付加した上で再計算用CDFGをスケ ジューリングしていった．しかし，Karriらの手法では時間オーバヘッドを付加し ないまま，面積オーバヘッドが小さくなるように再計算用CDFGをスケジューリ ングしていくのである．図2.1に示すCDFGを入力とする場合を考えると，そこ に再計算用CDFGを付加したものは図3.1となる．Karriらの手法ではこのCDFG の再計算部をこのまま演算器数が小さくなるようにスケジューリングしていくの であるが，このCDFGにはどのオペレーションにも可動性がないためこれ以上ス ケジューリングすることは不可能である．そこで，Karriらは，演算器数を減らす ために再計算用CDFGのエッジを選択的に分断し，いくつかの小さなサブCDFG に分けてスケジューリングを行っている．サブCDFGに分割することで，分割さ れたサブCDFGのオペレーションに可動性が生まれスケジューリングが可能とな る．分断されて新たにできたサブCDFGの入力データに関しては通常計算により 計算されたデータを流用することでその問題を解決している．しかし，この方法に は注意しなくてはならない点がある．それは，fault-secure設計においては入力と 出力の比較を行う必要が生じるということである．つまり，1つの再計算用CDFG をいくつかのサブCDFGに分割したことで増えた入力エッジと出力エッジ全てで，

対応する通常計算CDFG内のエッジのデータと比較しエラー検出のためのチェッ クを行わなくてならないということである．そのためにはそのようなエッジでそ

第3章 関連研究 れぞれ比較器が必要となり面積オーバヘッドが増加することにつながる．しかし，

設計対象となるようなVLSIでは加算器や乗算器にと比べ比較器の方が面積が小さ いために，この手法によりある程度比較器が増えたとしても全体的には面積オー バヘッド削減が実現できるのである．

3.3.2 実行例

実際に，図2.1に示す例を入力として，この手法を実行した例を示す．

まず，この入力CDFGに対して同一のCDFGを再計算用CDFGとして付加し，

図3.1としたものを考える．ここで，このCDFGの再計算部ついてサブCDFGに 分割を行うわけであるが，その分割アルゴリズムとしては，グラフ理論の観点か ら文献[19]に示されるmin-cut手法と，文献[24]に示されるアルゴリズムを適用 する．その分割結果を図3.5に示す．

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

R1

R2

normal comp.

図 3.5: Karriの設計過程CDFG1．

このように再計算用CDFGを2つのサブCDFG R1，R2に分割すると，サブ

CDFG R1に可動性が生まれ，スケジューリングが可能となる．また，サブCDFG

R2のオペレーション +3の入力エッジが切断されたため，あらたな入力エッジが

第3章 関連研究 にできた入力エッジの入力データをサブCDFG R1の出力から得ることができなく なってしまった．この問題を解決する方法として，Karriらは通常計算のデータを 再計算に流用する方法を提案した．図3.5に示す通常計算CDFGの印のついたエッ ジのデータを入力として用いるのである．同時に，このエッジのデータと，サブ CDFG R1の出力エッジを比較することで，サブCDFG R1のfault-secureを保障 し，かつ，サブCDFG R2の入力データの比較が行われるためにR2のfault-secure も同時に保障されるのである．

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. R1 recomputation R2

normal comp.

図 3.6: Karriの設計過程CDFG2．

この例ではサブCDFG R1のみに可動性が生まれたため，R1のみスケジューリ ングを行っているが，どのサブCDFGもスケジューリングを行うことができる．

最後にfault-secure設計に基づきアロケーションを行い終了する．Karriらの手 法による設計結果を図3.7に示す．

3.3.3 本手法のまとめ

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

Karriらの手法は，時間オーバヘッドを許さないとうい条件の下，できるだけ必

要となる演算器の数を減らすためにスケジューリングおこなうという手法であっ た．しかし，時間オーバヘッドがないとオペレーションに存在する可動性が非常 に小さく満足にスケジューリングが行えない場合や，例で示したように可動性が 全く存在せず，スケジューリングが行えないケースがある．そこで，Karriらは

第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. R1 recomputation R2

normal comp.

M5 M6

M5 M6 A3

A2 A3

図 3.7: Karriの手法の設計結果．

表 3.2: Karriらの手法の比較．

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

入力  4 2 0 – –

例1 8 4 1 7 0

例2 4 2 1 1 3

Karri 6 3 2 5 0

第3章 関連研究 CDFGのエッジを選択的に切断し，いくつかのサブCDFGに分けることで，その サブCDFGに可動性を生み出し，スケジューリング可能にした．その方法により 必要な演算器を減らすためのスケジューリングは行えるようになったが，それと 同時に，分割した全てのサブCDFGにおいてfault-secureを保障するために比較 器を付加する必要も生じた．表3.2を見るとわかるが，他の手法では入力データ がすでに１fault-secureであると仮定し，最終的な出力エッジの比較のみで済むた めに1つの比較器だけでよいが，Karriらの手法では比較器が2つ必要となってい る．だが，Karriらの手法と同じく時間オーバヘッドを許していない第2章で挙げ た例1の手法と比べても，演算器数のオーバヘッドでも勝っておりその有効性がわ かる．また，比較器は他の演算器と比べて面積は小さいため他の演算器数を減ら すために比較器数が増えてもデバイス自体の面積を小さくすることが可能となる．

第3章 関連研究