整数線形計画法

整数線形計画法とは文字通り整数の値をとる変数を対象としており，目的関数 と制約条件が全て線形を示す問題に用いることができる最適解導出の方法となっ ている．

高位合成の分野でも時間制約のもとでのスケジューリングの最適解導出に用い られることのある方法である．一般的なスケジューリング問題においては

目的関数  資源の最小化 制約条件  ノードの依存関係 となっている．

目的関数となっている「資源の最小化」とは通常，その構成を実現するために必 要な演算器数を最小化することを指している．また，制約条件となっている「ノー ドの依存関係」はノードの計算順のことである．たとえば，DFG上でiステップ 目に演算jをスケジューリングすることを

x_i.j = 1 (5.1)

第5章 評価実験 それ以外のときを

x_i.j = 0 (5.2)

と表すとする．

すると，演算jが演算kよりも先に実行されなければいけないという依存関係は X

l

lx_l,j−X

m

kx_m,k≦−1 (5.3)

によって表される．ここでl，mはステップ数を意味している．

入力全体で考えれば，式(5.3)の形となる制約条件式がDFGにおける辺の数と 同じだけ存在するということになる．

5.2.2 本実験における変更点

今回，fault-secure設計におけるスケジューリングであることから，一般的な整 数線形計画法における依存関係の制約に加え，各種の演算器の演算器数も制約条 件として扱っている．本来は目的関数となるべき項目であるが，fault-secure設計 において既存手法，提案手法ともに演算に使用できる演算器数はあらかじめ与え られているためである．

目的関数としては再計算部のエッジ分断によるfault-secure保障のために必要 となる比較器数の最小化としている．これは，演算器数制約，時間制約のもとで

fault-secureな回路のスケジューリングを行う上で，資源を最小化するためである．

5.2.3 探索範囲の絞込み

前述の方法では，探索領域は単純に考えステップ数のノード数乗となり，膨大 なものとなってしまう．そのため探索領域を絞り込む方法として可動度による絞 込みを行っている．

可動度とはノードの依存関係を維持したままスケジューリング可能なステップ

第5章 評価実験

5.2.4 最適解導出の結果

まず，サンプルを入力とした場合の結果との比較についてである．図5.1に示す CDFGを入力とした場合の結果を表5.1に示す．また，出力として得られたCDFG の図を図5.2に示す．

+1

x1 +3 x2

x3 x4

+4 C1

C2

C3 A1

M2 A1 M1

M2 M1

C4 A1

+2 A2

図 5.1: サンプルCDFG．

図 5.2: 出力CDFG．

この入力はノード数が8と非常に小さな入力であるため探索範囲も狭く，探索 範囲の最大数は480000通りであり，266632通り目の探索で得られたため最適解 の導出も数秒で行われた．

結果は1ステップの時間オーバヘッドのもとで，演算器，比較器の付加なく

fault-secure設計を施すことができるという最適解が得られ，提案手法は既存手法より

第5章 評価実験

表 5.1: サンプルを入力とした結果．

乗算器数 加算器数 比較器数 ステップ数 面積OH 時間OH

入力  2 2 0 4 – –

最適解 2 2 0 5 0 1

Wuらの手法 2 2 3 5 3 1

提案手法 2 2 2 5 2 1

も有効ではあるが，最適解ではないことが示された．

次にFIRとEWFの入力に対する結果であるが，この2つの入力については最 適解を得ることはできなかった．この原因はFIR，EWFのノード数がそれぞれ

31，42であり，ステップ数も10，17と最適解を求めるには膨大な探索範囲となっ

てしまうためであると考えられる．

今回の最適解導出の手法における探索範囲の試算を行ってみる．制約条件であ るノードの依存関係，演算器制約により絞り込まれる範囲を考慮する計算は困難 であるため，可動度による絞込みを考慮した概算にとどめると，FIRで約169× 10²⁰通りであり，EWFではそれをはるかに越える探索範囲となった．現状ではお およそ10⁷通りの探索に1分ほどかかるため，FIRの最適解を求めるためには約3

×10⁹年という時間がかかってしまうこととなり，この規模の入力だとしても実 現可能な時間では最適解が求められないということになる．これはfault-secure設 計では再計算部はエッジの分断を許容するために可動度が必然的に大きくなって しまい，探索範囲の増大が避けられない問題であるため，通常のスケジューリン グよりも解決しがたい問題となっているためである．

これらの結果から，LSI設計の現状を踏まえたとき，fault-secure設計による最

第5章 評価実験

5.3 ヒューリスティックな手法との比較

前節において高位レベルにおけるfault-secure設計でのヒューリスティックな手 法の必要性が示された．この節では本提案手法のヒューリスティックな手法の中 での優位性を示すために，既存のヒューリスティックな手法との比較・考察を行 う．比較対象とするヒューリスティックな手法としてFDSをあげる．