テスト容易化動作合成のための DFG のグループ化評価
日大生産工
(院
)○石井 英明 日大生産工 細川 利典
1.はじめに
近年，半導体技術の進歩による超大規模集積回路
（Very Large Scale Integrated circuit：VLSI）の 大規模化に伴い，回路が複雑化してきている．従来，
このような VLSI の設計にはハードウェア記述言語
（Hardware Description Language：HDL）でレ ジスタ転送レベル（Register Transfer Level：RTL） の記述をし，論理合成ツールを用いることでネット リストを生成してきた[1]．しかしながら，従来の手 順では設計生産性の面から設計が困難となってきて いる．そこでRTLよりさらに抽象度の高い動作レベ ルでの設計として動作合成ツールが着目されている [2]．
動作合成は前述のとおりRTLより抽象度が高いた め，RTLの記述に比べ記述量が少なく設計生産性に 優れる[3]．反面，どの演算操作をどの演算器に割当 てるか，どの変数をどのレジスタに割当てるかなど，
細かい設定は動作合成ツールが行うため，アルゴリ ズム次第で出力される回路の面積や性能に差が生じ てしまう．しかしながら，動作合成によって生成さ れる回路の面積や性能を最適化する方法がいくつも 提案され，動作合成による設計は実用的なレベルと なった[3]．
設計製造したLSIを出荷するにあたり，不良品を 市場に出さないためにLSIのテストをする必要があ る．通常，LSI のテストはフルスキャン設計を施し た回路に対し，自動テストパターン生成ツール（Au tomatic Test Pattern Generator：ATPG）を用い てテストパターンを生成しテストをする[5]．フルス キャン設計を施しているため高い故障検出効率を得 るテストパターンが生成できるが，スキャンチェイ ンを通じて，全てのレジスタに任意にアクセスでき てしまうためセキュリティの面で問題があり望まし くない．そのためなるべくスキャン設計を用いない でテスタビリティを向上させる必要があり，動作合 成内でもテスト容易化を考慮する必要がある．テス
ト容易化を考慮した動作合成として，レジスタの段 数（順序深度）を削減することでテスト容易化を実 現する手法が提案されている[6]．
本稿では，動作合成の序盤にあたるコントロール
／データフローグラフ（Control/Data-Flow Grap h：CDFG）生成フェーズにおいて生成されたデータ フローグラフ（Data Flow Graph：DFG）をグルー プ化することにより，以降の処理に与える影響を確 認し，順序深度を削減しやすいグループ化方法が存 在するか否かを評価する．
2.動作合成
動作合成はC 言語やSystemC[6]などで書かれた 動作記述を入力とし，Verilog-HDL[7]や VHDL[8]
などのHDLで書かれたRTL回路記述を生成する．
処理過程は大きく分けると，CDFG生成，スケジュ ーリング，バインディング，RTL回路記述生成の四 つのフェーズにわけられる（図1）[3]．
CDFG生成とは動作記述からコントロールフロー グラフ（Control Flow Graph：CFG）とDFGを生 成するフェーズである．本稿ではこのフェーズで生 成するDFGについてのグループ化をすることで，生 成される回路の違いについて評価する．スケジュー リングとは，各演算操作をどの時刻で実行するかを 決定するフェーズである．バインディングとは，各
動作記述
CDFG生成
スケジューリング バインディング
RTL回路記述生成
RTL回路記述
図1．動作合成
Evaluation of the grouping of DFG for Behavioral Test Synthesis
Hideaki ISHII and Toshinori HOSOKAWA
c = (a + 1) / 2; // B1の処理 switch(sel) {
case 1: // B2の処理
x = (a * b) * (c * d) – e – f * (g * h);
y = i * j + k;
z = (l + m) / n;
case 2: ・・・ // B3の処理 default: ・・・ // B4の処理 }
図2．動作記述
B2 B3 B4
1 2 E
１ ２ Ｅ B1
△＝制御開始
□＝演算ブロック
▽＝制御終了
図3．CFG
演算操作や変数に演算器やレジスタを割当てるフェ ーズである．ここでマルチプレクサやレジスタの制 御が決まるため，FSM（finite state machine）を 生成しコントローラを生成する．RTL回路記述生成 とは，バインディングで割当てた演算器やレジスタ 間の結線を実現するフェーズである．
3．CDFG 生成
動作合成の最初のフェーズとして CDFG 生成が ある．CDFG生成のフェーズでは動作記述（図 2）
からCFG（図3）とDFG（図4）を生成する．図3 は図2で示したswitch文をCFGにしたものである．
CFGとはif文などの条件分岐や，while文などのル ープ処理の情報や，演算処理のかたまりであるブロ ック情報が含まれたグラフである．if文や while文 は制御処理となるため，制御開始の三角形と制御終 了 の 逆 三 角 形 で 表 す ． 図 3 の 四 角
*
a b
*
c d
*
*
g h
- -
e
*
f
x
x = (a * b) * (c * d) – e – f * (g * h)
*
i j
y
+
k y = i * j + k
+
l m
z
/
n z = (l + m) / n
A
B
C 図4．DFG
形で表した部分が演算ブロックである．動作記述内 で演算処理が連続で出現する部分を一つの演算ブロ ックとして表現する．つまり制御文から制御文の間 の演算処理を一つのブロックとする．
各演算ブロックは複数の演算処理を含む．そのた め一つの演算ブロック内に複数の演算処理である式 を持つ．図4は図3で示したCFGのうち，演算ブロ ックB2内のDFGを示したものである．例えばx=(a
*b)*(c*d)-e-f*(g*h)という式をDFGにしたものが図 4のAである．DFGの上側が入力となり，下側が出 力となる．そのため複数の変数や定数を入力とし，
一つの変数に収束して出力となる．間にある演算操 作は左側の入力に対して右側の入力で演算操作を実 行することを意味する．例えばa*bの場合，図4の Aの左上部分のように表現し，変数aに対してbの 乗算操作を適用することを意味する．このようにDF G は変数と演算操作の関係をグラフにしたものであ る．
4．DFG グループ化
スケジューリングやバインディングは，利用でき るレジスタ数や演算器数，演算にかかる時刻などを 考慮したうえで割当てをする．そのため複数のDFG を一つのグループとし，グループ単位でスケジュー リングやバインディングを実行することで，複数の 割当てパターンを考慮することができる．よって性 能や面積などについて最適な結果を求めることがで きると考えられる．本稿ではグループ化するパター ンを複数考え，出力した回路の違いからテスト容易 化となりうるグループ化パターンについて評価する．
5．実験結果
条件分岐とループ処理を含む動作記述（図 5）を 入力としてDFG生成（図6）をし，生成されたDF Gに対してグループ化をする．
演算ブロックが四つとなるため，一つの演算ブロ ックを一つのグループとする場合，二つの演算ブロ ックを一つのグループとする場合，四つ全ての演算 ブロックを一つのグループとする場合について考え る．実際にグループ化したパターンを以下に示す．
一つの演算ブロックを一つのグループとする場合を パターンAとする．演算ブロック①と②を一つのグ ループ，③と④を一つのグループとする場合をパタ ーンBとする．演算ブロック①と③を一つのグルー プ，②と④を一つのグループとする場合をパター
do{
y = v * d; v = y + c;
}while(v < f);
if(c){
x = v + a; y = y – e;
}else{
x = v – a; y = y + e;
}
z = x / y; u = v + z;
図5．実験用動作記述
* +
<
v d c f
y v to
controller
+ -
v a y e
x y
- +
v a y e
x y
①
②
③
④
/
+
x y v
z u
図6．実験用DFG
ンCとする．全ての演算ブロックを一つのグルー プとする場合をパターンDとする．なお演算ブロッ ク①と④を一つのグループ，②と③を一つのグルー プとする場合については，処理の流れが①②④また は①③④となる関係上，入力から出力までの流れで データパスを往復する部分が出てくるため順序深度 が深くなることが分かるので省略する．具体的には 外部入力から与えられた信号が，演算ブロック①と
④をグループ化して生成されたデータパスへと進み，
次に演算ブロック②と③をグループ化して生成され たデータパスへと進み，もう一度演算ブロック①と
*1 +1
<1
v d c f
y(R1) v(R2) to controller
*1 +1
<1
v d c f
y(R1) v(R2) to controller
+1 -1
v(R2) a y(R1) e
x(R3) y(R1)
+1 -1
v(R2) a y(R1) e
x(R3) y(R1)
-1 +1
v(R2) a y(R1) e
x(R3) y(R1)
-1 +1
v(R2) a y(R1) e
x(R3) y(R1)
/1
+1 x(R3) y(R1) v(R2)
z u
/1
+1 x(R3) y(R1) v(R2)
z u
①
②
③
④
R1 R2 R3 R4
R2 R1
R100
R2 R5 R1 R6
R3 R1
R2 R5 R1 R6
R3 R1
R3 R1 R2
R4
R5
図7．レフトエッジアルゴリズム
バインディング
図8．レフトエッジアルゴリズム回路
④をグループ化して生成されたデータパスへと戻り，
外部出力へと出力されることとなる．そのため実験 するまでもなく傾向がわかるため今回の実験パター ンから除外した．
それぞれグループ化した DFG に対しスケジュー リングをするが，最短時刻でスケジュー
リングすると一つのパターンしか存在しないため，
その割当て時刻を利用する．
バインディングは二つの手法について考える．一 つ目はレフトエッジアルゴリズムと呼ばれる手法で，
DFG 上の左側から優先してレジスタや演算器を割 当てていく手法である[3]．二つ目は順序深度削減バ インディング手法で，外部入力や外部出力と繋がる レジスタに対して可能な限り内部変数を割当てる手 法である[3]．
パターンDについてレフトエッジアルゴリズムを 適用した場合のバインディング情報を図 7に示し，
回路にした情報を図8に示す．このバインディング アルゴリズムでは，例えば①のv*dの乗算操作を乗 算器1に割当てたことを示す．また①の入力vから 乗算操作までの値保持としてレジスタ1に割当てた ことを示す．同様に，パターンDについて順序深度 削減バインディングを適用した場合のバインディン グ情報を図9に示し，回路にした情報を図10に示す．
このバインディングアルゴリズムでは，例えば①のv
*dの乗算操作を乗算器1に割当てたことを示す．ま
*1 +1
<1
v d c f
y v to
controller
*1 +1
<1
v d c f
y v to
controller
+1 -1
v a y e
x y
+1 -1
v a y e
x y
-1 +1
v a y e
x y
-1 +1
v a y e
x y
/1
+1
x y v
z u
/1
+1
x y v
z u
①
②
③
④
R5 R2 R4 R6
R5 R2
R7
R5 R1 R2 R3
R1 R2
R5 R1 R2 R3
R1 R2
R1 R2 R5
R3
R4
図9．順序深度削減バインディング
図10．順序深度削減回路
た①の入力v から乗算操作までの値保持としてレジ スタ5に割当てたことを示す．
出力した回路から演算器やレジスタ数の違いや順 序深度の差を求める．例えばパターンDの場合，マ ルチプレクサの入力数が図8から15個，図10から 14個だとわかる．
実験結果を表1に示す．パターンの項目は前述し たパターン名を示す．加算器からレジスタまでの項 目は各演算器やレジスタの使用個数を示す．順序深 度の項目は生成された回路から求めた順序深度を示 す．
各パターンの上段がレフトエッジアルゴリズムで生 成された回路，下段が順序深度削減バインディング で生成された回路の結果である．
全ての演算ブロックを別々のグループとしたパタ ーンAよりも二つの演算ブロックを一つのグループ としたパターンBやCの方が加算器と減算器やレジ スタ数が少なくなっていることがわかる．また，全 ての演算ブロッ
クを一つのグループとした場合について比べ
てみると，さらに少なくなっていることがわかる．
順序深度に関してもパターンAよりパターンDの方 が少なくテスト容易であるといえる．パターンBと C は順序深度削減バインディングをすれば順序深度 が少なくなっている．以上のことより，グループ化 できる箇所はグループ化する方が面積やテスト容易 性について有利であることがわかる．
6．おわりに
本稿では DFG をグループ化することによる出力 回路の違いについて評価した．面積やテスト容易性 といった面から評価すると，全てのケースにおいて なるべくグループ化する方が有利という結果となっ た．しかし数値として表しにくい評価として回路の 再利用性があり，この場合グループ化しない方が有 利と考えられる．今後はそのような面からの評価も 必要となると考えられる．
「参考文献」
1) 堀 桂太郎，図解 Verilog HDL 実習 ゼロか らわかるハードウェア記述言語，森北出版株式会社，
2006
2) 藤原秀雄，ディジタルシステムの設計とテスト，
工学図書株式会社，2004
3) Daniel D. Gajski, Nikil D. Dutt, Allen C-H Wu, and Steve Y-L Lin, HIGH-LEVEL SYNT HESIS Introduction to Chip and System Desig n, Kluwer Academic Publisher, 1992
4) H.Fujiwara, Logic Testing and Design for Te stability, The MIT Press, 1985
5) H.Fujiwara, Logic Testing and Design for Te stability, The MIT Press, 1985
6) Tien-Chien Lee, Wayne H.Wolf, Niraj K.Jha, John M. Acken, Behavioral Synthesis for Easy Testability in Data Path Allocation, ICCD, 19 92
7) M.Abramovici, M.A.Breuer, and A.D.Frindma n, Digital Systems Testing and Testable Design, Computer Science Press, 1990
8) Mike Tien-Chien Lee, High-Level Test Syn thesis of Digital VLSI Circuits, Artech House, 1997
9) 並木秀明, 後閑哲也, 片岡忠士, SystemC による システムデザイン入門, 株式会社技術評論社, 2005 10) 並木秀明, 前田智美, 宮尾正大, ディジタル回路 とVerilog-HDL, 株式会社技術評論社, 1996 11) 中幸政, VHDLとCPLDによるロジック設計入 門, CQ出版株式会社, 2005
表1．実験結果
4 2 1 1 1 11 16 3
4 2 1 1 1 11 16 3
2 2 1 1 1 12 12 3
2 2 1 1 1 15 11 2
2 2 1 1 1 11 12 3
2 2 1 1 1 12 11 2
1 1 1 1 1 15 7
1 1 1 1 1 14 7
マルチ
2 2 プ
レクサの 入力数
レジスタ パターン
パターンB パターンC パターンD
順序深度 パターンA
加算器 減算器 乗算器 除算器 比較器
