無閉路部分スキャン 設計に 基づ くデ ータパ スのテ スト 容易化
高位合成に おけ るバ インデ ィング 手法
高崎 智也
†井上 智生
††藤原 秀雄
†A Binding Method in High-Level Synthesis for Testable Data Paths
Based on Acyclic Partial Scan Design
Tomoya TAKASAKI†, Tomoo INOUE††, and Hideo FUJIWARA†
あらまし 本論文では ，無閉路構造に 基づ く部分スキャン 設計のための，デ ータパスのテ スト 容易化高位合成 手法を提案する．スケジュールされ た動作記述（ デ ータフローグ ラフ ）に 対し て ，面積（ リソー ス数 ）の最小性 を満たし ながら ，無閉路化のためのスキャンレジ スタ数を最小にする演算器とレジ スタのバ インデ ィング 法を提 案する．本手法は ，テスト 容易性を考慮し ない従来手法と比較し て ，リソース数を増やすことなく，無閉路化の ためのスキャンレジ スタ数の小さいレ ジ スタ転送レ ベルデ ータパスを合成することができる．
キーワード 高位合成，部分スキャン 設計，無閉路構造，最小クリーク分割，デ ータパス
1. ま え がき
近年のVLSIの高集積化，大規模化に 伴い，回路の テ スト は ます ま す 重 要で か つ 困 難な 問 題と なって い る[1]．テストの費用を削減するために ，設計の初期の 段階からテ スト 容易性を考慮することが 必要とされ て いる．抽象度の高い動作記述からレジ スタ転送レ ベル
（RTL）の 回路を 合成する高位合成の 段階でテ スト 容 易性を考慮することにより，回路の面積・性能ととも にテ スト 容易性も含めた最適化及び 設計費用の削減が できるものと期待され ている．本論文では ，テスト 容 易性を考慮し た高位合成（ テスト 容易化高位合成 ）の 一手法とし て，無閉路構造に基づ く部分スキャン 設計 のためのデ ータパスのテ スト 容易化高位合成法を考察 する．
一部のフ リップ フロップ をスキャン 可能なフリップ フロップ（ スキャンフ リップ フロップ ）に 置き換え る 部分スキャン 設計は ，小さい ハード ウェアオーバヘッ ド でテ スト 容易な回路を実現するための重要な技術の
†奈良先端科学技術大学院大学情報科学研究科 ，生駒市
Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma-shi, 630–0101 Japan
††広島市立大学情報科学部，広島市
Faculty of Information Sciences, Hiroshima City University, Hiroshima-shi, 731–3194 Japan
一つである．用いるテスト 生成アルゴ リズムによって， 部分スキャン 設計法は大きく二つの手法に分けられ る． 一つは 順序回路用テ スト 生成アルゴ リズムを用いるこ とを前提とし た部分スキャン 設計法で ，文献[4], [5]で は スキャンフリップ フロップによってセルフループ を 除いたフ ィード バックループ を切断する手法が 提案さ れている．もう一つは 組合せ回路用テ スト 生成アルゴ リズムを用いることを前提とし た部分スキャン 設計法 である[6]∼[9]．この部分スキャン 設計法において共通 することは ，RTL回路の一部のレジ スタ（ フリップ フ ロップの組 ）をスキャンレジ スタに置き換え，スキャン レジ スタに よってセルフループ を含むすべてのフ ィー ド バックループ を切断することにより，無閉路構造を 実現する無閉路部分スキャン 設計である．本論文での 高位合成法は ，無閉路部分スキャン 設計の スキャンレ ジ スタ数が 最小にな るRTLデ ータパ スを合成し ，組 合せ回路用のテ スト 生成アルゴ リズムを適用すること を目的とする．
部分スキャン 設計を指向し たデ ータパスのテスト 容 易化高位合成法とし て ，これ までに 多くの手法が 提案 され ている．文献[10]では 一部のレジ スタを スキャン レジ スタに 割り当て，レジ スタの可制御性/可観測性を 向上させ るためのデ ータパ スの合成法が 提案され てい る．文献[11]では 小さい数のスキャンレジ スタを 用い
282 D– Vol. J83–D– No. 2 pp. 282–292 2000 2
てセルフループ 以外のすべてのフ ィード バックループ を切断するデ ータパスの合成法が 提案され ている．文 献[13]ではセルフル ープ 以外のすべてのフ ィード バッ クループ を切断するスキャンレジ スタ数を小さくする ためのレジ スタのバ インデ ィング 法が 提案されている． また，文献[12]では部分スキャン 設計を想定し ないが ， フ ィード バックループ 数の小さいデ ータパ スの合成法 が 提案され ている．これらの手法はいずれ も順序回路 用テ スト 生成アルゴ リズムを用いることを前提にし て おり，必ずし もすべてのフ ィード バックループ を切断 する手法ではない．よって ，組合せ回路用テ スト 生成 アルゴ リズムのための無閉路部分スキャン 設計を指向 し た合成法にそのまま適用することができない．
本論文では，高位合成の部分問題として，スケジュー ル され た 動作記述（ デ ータフ ローグ ラフ ）に 対し て ， リソース数（ 演算器数，レジ スタ数 ）の最小性を満た しながら，生成され るRTLデータパスで無閉路化（ セ ルフループ を含むすべてのフィード バックループ を切 断 ）のためのスキャンレジ スタ数を最小にする演算器 とレジ スタのバ インデ ィング 法を提案する．提案する バ インデ ィング 法は ，(1)動作レ ベルでセル フループ を 構成す る変 数は ，RTLデ ータパ スで スキャンレ ジ スタに 割り当てなければ ならない，(2)動作レ ベルで フ ィード バックループ が 発生し ても，レジ スタを効率 良く共有できれば ，RTLデ ータパスで スキャンレジ ス タ数を減らすことができる，という二つの 事実に 着目 し ，(1)演算器・レジ スタの共有に よってセルフル ー プ の 発生をで きるだけ 回避する，(2)で きるだけ 多く のフ ィード バックループ が 同じレジ スタを 通るように 演算器・レジ スタを 割り当てるものである．
以下，2.で提案するバ インデ ィング 法の全体の流れ を示し ，3.で演算器とレジ スタバ インデ ィングの発見 的手法について詳細を説明する．4.で最小クリーク分 割を 用いたバ インデ ィング のヒューリステ ィックアル ゴ リズムについて示し ，5.で動作記述のベンチマーク に 対する実験結果より提案手法の有効性を示す．
2. 全体の流れ
提案するバ インデ ィング 法は ，リソース数（ 演算器 数，レジ スタ数 ）を最小にする一般的なアルゴ リズム を ，無閉路部分スキャン 設計のための スキャンレジ ス タ数が 最小になるように変更し たものである．もとと なるスキャンレジ スタ数最小化を指向し ない一般のバ インデ ィング アルゴ リズムとし て ，文献[2], [3]にある
ような，両立グ ラフを用いた手法を採用し た ．ここで はまず，そのアルゴ リズムについて説明する．なお，ス ケジ ューリング とアロケーションは 既に 行われている ものと する．入力とな るデ ータフローグ ラフ（DFG） は 以下のよ うに 定義され る．
［ 定義1］ スケジュール 済みDFG（SDFG）は有向グ ラフGsD= (VD, ED, t, s)である．ここで ，VDは 外 部入出力を含む演算を頂点とする集合，ED⊂ VD×VD は変数を辺とする集合，t: VD→ {op1, op2,. . . , opn} は 演算の型，s: VD→ Z+∪ {0}（ 非負整数 ）は 演算 が 実行され る制御ステップ を表す．
ここでは 簡単のため ，各演算の実行遅延は1制御ス テップ と仮定する．
バ インデ ィング の主要な手続きは ，SDFG中の演算 を演算器に 割り当てる演算器バ インデ ィング と変数を レジ スタに 割り当てるレジ スタバ インデ ィングからな る．一般には演算器バ インデ ィング とレジ スタバ イン デ ィングに 分けて問題を解く．ここでは 演算器バ イン デ ィング，レジ スタバ インデ ィング の 順に 行う手法を 考える．各バ インデ ィングついて，最小個の演算器・レ ジ スタの 割当てを行うため ，両立グ ラフに 対し て最小 クリーク分割（ クリーク数最小のクリーク分割 ）を解 く．ここで 各クリークは 共有され た演算器またはレジ スタに 対応し ている．本論文で扱う両立グ ラフとし て， 以下で 定義する演算/レジ スタ両立グ ラフを用いる．
SDFG中の二つの演算が 同じ 制御ステップで実行さ れず，同じ 型の演算器で 実現できるとき，これらの演 算は 両立可能であるという．
［ 定義2］SDFG GsD に 対 す る 演 算 両 立 グ ラ フ
（OCG）は ，無 向グ ラ フ GO = (VO, EO) で あ る ． こ こ で ，頂 点 v ∈ VO はSDFG GsD の 演 算 ，辺 (u, v) ∈ EO⊂ VO× VOは 頂点u, vに 対応する演算 が 両立可能であることを表す．
［ 例1］ 図1のSDFGの加 算に 対する演算両立グ ラ フは 図2のようになる．例えば ，+1と+2はそれぞ れ ステップ1, 3で スケジュールされているので ，両立 可能な 辺をもつ．+2と+3は 同じ 制御ステップ で ス ケジュールされているので ，その間に辺は存在し ない．
SDFG中の二つの変数のライフタイム（ 変数が 使用 され ている時間 ）に 重複がないとき，これらの変数は 両立可能であるという．
［ 定義3］SDFG GsD に 対 す るレ ジ ス タ 両 立グ ラ フ（RCG）は ，無向グ ラフGR = (VR, ER)である ． こ こ で ，頂 点 v ∈ VR はSDFG GsD の 変 数 ，辺
図1 スケジ ュール済みDFG GsD
Fig. 1 Scheduled DFG GsD.
図2 GsDに 対する演算両立グ ラフGO
Fig. 2 Operation compatibility graph GOfor GsD.
(u, v) ∈ ER⊂ VR× VRは 頂点u, vに 対応する変数 が 両立可能であることを表す．
［ 例2］ 図1のSDFGに 対するレ ジ スタ両立グ ラフ は 図3のようになる．例えば ，変数uとvはラ イフ タ イムが 異なるので ，両立可能な辺をもつ．一方，変 数d2は すべての 制御ステップ にわたって 利用され て いるので ，それ と両立可能な辺は 存在し ない．
以上で 定義し た演算/レジ スタ両立グ ラフを用いて ， 最小クリーク分割により最適なバ インデ ィングを求め る．最小クリーク分割を求めるとき，演算器数または レジ スタ数に関し て等価なバ インデ ィングは 複数存在 することが 考えられ る．し かし ，それらは 無閉路化の ための スキャンレジ スタ数について 必ずし も等価であ るとは 限らない．複数の最小クリーク分割の解の中か ら スキャンレジ スタ数を最小にする解を選択するため に ，スキャンレジ スタの 必要性をクリークの重みで 表 す．求めたいバ インデ ィング をすべての最小クリーク 分割の中で 重みが 最小になる最小クリーク分割を求め る問題とし て扱うことにする．次の章では 演算器とレ
図3 GsDに 対するレジ スタ両立グ ラフGR
Fig. 3 Register compatibility graph GRfor GsD.
ジ スタバ インデ ィング のための両立グ ラフのクリーク の重みとその重みを 利用し た最小クリーク分割につい て述べる．
3. 無閉路部分スキャン 設計を指向し たバイ
ンデ ィング
3. 1 演算器バ インデ ィング
ここでは 演算の共有によってできるループ を少なく し ，それらのル ープ がこの後のレジ スタバ インデ ィン グで 互いに スキャンレジ スタを共有し やすくすること を考え る．
SDFGで 両立可能な 二つの 演算間に 経路が 存在し ， それらの演算を一つの 演算器とし て共有すれば ，もと の演算間の経路は共有し た演算器を通るループ となる． よって ，その演算間の経路上にあるいずれかの変数は ループ を切断するための スキャンレジ スタに 割り当て なければ なら ない ．両立可能な 演算間の 経 路の 長さ ， すなわちその経路上にある変数の数が 大きければ ，そ の うちいずれか 一つを スキャンレジ スタに 割り当てれ ば よいので ，スキャンレジ スタを選択する自由度は 大 きくなる．一般に 両立可能な二つの演算間には複数の 経路が 存在する．簡単のため，ここでは 最短経路を複 数の経路の代表とし て扱うことにする．複数ある経路 の中で 最短経路上の変数は 最もスキャンレジ スタの共 有が 行いに くいと 考えられ る．また ，スキャンレジ ス タに 割り当てられ る変数の ラ イフタ イムが 長ければ ， スキャンレジ スタは 共有し にくい．ラ イフタ イムの正 確な見積もりはレジ スタバ インデ ィングで行うとし て， ここではラ イフタ イムの代わりに 経路をもつ両立可能 な二つの演算間の時刻差を単純に評価することにする．
以上のことを 考慮し て ，演算両立グ ラフ の 各辺に ， 以下の重みを付け る．
3. 1. 1 演算両立グ ラフで 付け る重み
［ 演算両立グ ラフの辺(u, v)の重み ］
（1）SDFGで 対応する演算uとvの 間に 経路が 存在し ない（u→ v, v → uのいずれの 方向に も経路 が 存在し ない ）とき
wo(u, v) = 0
（2）SDFGで 対応する演算uとvの 間に 経路が 存在するとき
uとvの 最短経路を p（u → v, v → uの 両 方向 で 経路が 存在するとき，それらすべての経路の中で 最 短 ），pの長さと 時間（ 時刻差 ）をそれぞれ l(p), t(p) とすると ，
wo(u, v) = t(p) × Kl(p)
ここで ，Kl(p) はKl(p) > Kl(p)+1を 満たす十分大 きな 数とする．
上の式を用いると ，経路が 短いほど 大きな重みが 与 えられ る．特に ，最短経路長が1のときにできるセル フループ は ，演算の共有によってできる限り作りた く ないことを表し ている．また，重みにかけている最短 経路の時間は ，同じ 長さの 最短経路の中だけで差が つ くようにし たものである．同じ 最短経路長の共有の組 合せがあれば ，時間の短いものが 優先され ることを表 し ている．
この重みにおいて ，演算間の経路が 長い共有につい ては ，経路が 短い共有と比べて ，小さい値の重みが 与 えられ る．し たが って実際には ，ある程度の長さの経 路の 短 い 共 有だ け で 評 価に 差が 十 分 現れ るも の と 考 え られ る ．実験で は 長さ5のも の まで 評 価し た（5. 参照 ）．
［ 例3］ 図1のSDFGの加 算に ついての 演算両立グ ラフ 図2に 対し て ，各辺に 対応す る 演算間の 最短経 路長とその 時間を図4の括弧の中に示す．ここで ，現 在の ステップ5と 次の ステップ 0が 同じ 制 御 ステッ プ 内で 行われ るものと 仮定する ．K3 = 1, K2 = 10, K1= 100とするとき，各辺の重みは 図4の数値のよ うにな る．例えば ，+3と+4を一つの 演算器とし て 共有すると，共有し た演算器はセルフループ を構成し ， 変数wは スキャンレジ スタに 割り当てなければ なら ない．同様に +1と+2を共有すると d2は スキャン レジ スタとな るが ，これは wよりも 利用され てい る 時間が 長い ．一方，+1と+3を 共有すると ，セル フ ル ープ で な いル ープ が で き ，uか vの いずれ かが ス キャンレジ スタに 割り当てられ る．スキャンのための 共有に 関し ては ，(+3, +4)は(+1, +2) よりもよ く，
図4 演算両立グ ラフGOの重み付け Fig. 4 Weighted operation compatibility graph for
GO.
(+1, +3)は(+3, +4)よりもよい ．図 4の 両 立グ ラ フの各辺の重みはこの順位を表したものになっている．
3. 1. 2 クリークの重み
一つの 演算器の共有に 関するスキャンレジ スタの必 要性を表す尺度とし てクリークの重みを 考え る．ここ で ク リークは 共有され た 一つの 演算器を 表し ている ． 演算両立グ ラフで クリーク（ 演算器 ）を構成するとき， 重みの大きい辺（ 共有 ）が少ないことが 望まし い．よっ て ，クリークCi= (Vi, Ei)の重みWo(Ci)を以下の ように定義する．
Wo(Ci) =
e∈Ei
wo(e)
3. 1. 3 重み和最小クリーク分割問題
演算器バ インデ ィングに 関するスキャンレジ スタの 必要性を表す尺度とし てクリーク分割の重みを考える． クリーク分割では 重みの大きいク リークが 少ないこと が 望まし いことから ，クリーク分割の重みをその中に 含まれているクリークの重みの 総和で 表す．演算器数 最小のもとで ，スキャンレジ スタ数を最小にする演算 器バ インデ ィング とし て ，以下の問題を考え ることが できる．
［ 重み和最小クリーク分割問題 ］ 入力： 演算両立グ ラフGO= (VO, EO) 出力： クリークの重みの総和
n
i=1Wo(Ci)が 最小と
なるクリーク分割 π= {C1, C2,. . . , Cn}
（ ク リークCi= (Vi, Ei)とすると ，VO = V1∪ V2∪ . . . ∪ VnかつVi∩ Vj= ∅, ∀i |= j）
条件： クリーク数nが 最小
以上のよ うに 演算両立グ ラフに 対し てクリーク分割
図5 GOに 対する重み和最小クリーク分割 Fig. 5Weighted minimum clique partitioning for
GO.
図6 演算共有グ ラフGoD
Fig. 6 Operation bound graph GoD.
を 行った 結果 ，演算器の 共 有を 表し たグ ラフとし て ， 同じ 演 算 器に 割り 当てられ る 複 数の 演 算に 対 応す る SDFGの頂点を一つの頂点とし て併合し たグ ラフをつ くる．このグ ラフを演算共有グ ラフという．
［ 例4］ 図4の 演 算 両 立グ ラフ に 対し て ，最 小と な るク リーク 数2の 分割は ，{{ + 1, +2}, { + 3, +4}}, {{ + 1, +3}, { + 2, +4}}, {{ + 1, +2, +4}, { + 3}}, {{ + 1, +3, +4}, { + 2}}の4通り存在する．この う ち図5に示す{{ + 1, +3}, { + 2, +4}}が クリークの 重みの 和が 20 + 60 = 80で 最小とな る分 割で あ る ． このときの演算共有グ ラフは図6のようになる．結果 とし て，この解はセルフループ を含んでいない．一方， ほかの最小クリーク分割の解はすべてセルフループが 発生する辺(+1, +2)または(+3, +4)を含んでいる．
3. 2 レジ スタバ インデ ィング
ここでは 先に 得られた演算共有グ ラフで 変数の共有 によってできるループ を少なくし ，それらのループが スキャンレジ スタをできる限り共有することを考える．
演算共有グ ラフで 両立可能な二つの 変数間に経路が 存在し ，それらの変数を一つのレジ スタとし て共有す れば ，もとの変数間の経路は共有し たレジ スタを通る ループ となる．よって ，その変数自身も含める経路上 にあるいずれかの変数は スキャンレジ スタに 割り当て
なければ ならない．特に ，演算共有グ ラフで 隣接し て いる 二つの 変 数を 一つのレ ジ スタとし て 共有すれば ， もとの経路は共有し たレジ スタを通るセルフループ と なるので ，そのレジ スタは 必ず スキャンレジ スタにし なければ ならない．演算共有グ ラフで 共有する二つの 変数間に 隣接以外の経路がある場合は ，共有し たレジ スタが スキャンレジ スタになるかど うかは ，経路中の ほかの変数が スキャンレジ スタに 割り当てられ るかど うかに 影響する．両立可能な二つの変数を一つのレジ スタとし て共有し たとき，そのレジ スタが スキャンレ ジ スタになるかど うかをレジ スタ両立グ ラフの辺の重 みで 表現する．
また ，ほかのど の変数との共有に 関係なく，演算共 有グ ラフでセルフループ を構成し ている変数は必ず ス キャンレジ スタに 割り当てなければ ならない．これを レジ スタ両立グ ラフの頂点の重みで 表現する．
3. 2. 1 レジ スタ両立グ ラフで 付け る重み
レジ スタ両立グ ラフの各辺に 以下の重みを付け る．
［レジ スタ両立グ ラフの辺(u, v)の重み ］
（1）演算共有グ ラフで 対応する変数uとvの 間 に 経路が 存在し ない（u→ v, v → uのいずれ の方向 にも経路が 存在し ない ）とき：wer(u, v) = 0
（2）演算共有グ ラフで 対応する変数uとvの 間 に 経路が 存在する（u→ v, v → uのいずれかの方向 で 経路が 存在する ）とき：
（2-1） 変数u, vが 隣接し ているとき：wer(u, v) = 1
（2-1） 変数u, vが隣接し ていないとき：wer(u, v) = ω（ ただし ，0 < ω < 1）
レジ スタ両立グ ラフの各頂点（ 変数 ）に 以下の重み を付け る．
［レジ スタ両立グ ラフの頂点vの重み ］
（1）演 算共有グ ラフで 対応する 変 数vが セル フ ループ を構成し ているとき：wvr(v) = 1
（2） （1）以外のとき：wvr(v) = 0
［ 例5］ 図3のレジ スタ両立グラフに対して，図6の 演算共有グ ラフにある演算器バ インデ ィングが 行われ たときの各辺と各頂点に 重みを 付けたレジ スタ両立グ ラフは 図7のよ うにな る．ここで ，ω= 0.5とする． 図6の演算共有グ ラフでは ，それ 自身がセルフル ープ を構成し ている変数が 存在し ないので ，レジ スタ両立 グ ラフの各頂点の重みは すべて0となる．各辺の重み に ついて 考え ると ，例えば ，wとxは 一つのレジ ス タとし て共有するとセルフループができ，共有し たレ ジ スタは スキャンレジ スタにな る．d1とxは 共有し
図7 レジスタ両立グラフ GRの重み付け Fig. 7 Weighted register compatibility graph for GR.
てもル ープができることはなく，スキャンレジ スタの 必要がない．スキャン のための共有に 関し ては ，(d1, x)は(w, x)よりは るかによい．このように ，レジ ス タ両立グ ラフの各辺の重みは変数を共有することによ るスキャンレジ スタの 必要性を表し ている．
3. 2. 2 クリークの重み
一つのレジ スタの 共有に 関するスキャンレジ スタの 必要性を表す尺度とし てクリークの重みを考える．こ こで クリークは共有され た一つのレジ スタを 表し てい る ．レ ジ スタ両立グ ラフで ク リークを 構成す ると き ， 共有し たレジ スタ（ クリーク ）がセルフループができ る変数の共有（ 重み1の辺 ）やセルフループ を構成す る変数（ 重み1の頂点 ）を一つでも含んでいれば ，そ のレ ジ スタは スキャンレ ジ スタで なければ なら な い ． クリークCi= (Vi, Ei)の重みWr(Ci)を以下のよう に 定義する．
Wr(Ci) = max{max
e∈Ei
wer(e), max
v∈Vi
wvr(v)}
クリークの重みは その 中に含まれているすべての変 数を一つのレジ スタとし て共有し たとき，そのレジ ス タが スキャンレジ スタになるかど うかを表し ている．
3. 2. 3 重み和最小クリーク分割問題
レジ スタバ インデ ィングに関し て スキャンレジ スタ の必要性を表す尺度とし てクリーク分割の重みを 考え る．クリーク分割では 重みの大きい クリーク，特に ス キャンレジ スタに 割り当てなければ ならない重み1の クリークが 少ないことが 望まし い．よって ，クリーク 分割の重みをその中に 含まれているクリークの重みの 総和で 表す．この重みが 小さくなるよ うにクリーク分 割を行えば ，必要な スキャンレジ スタ数を小さくする ことができると考えられ る．実際，この重みは結果と し てRTLデ ータパ スで 必要なおおよその スキャンレ ジ スタ数を表し ている．レジ スタ数最小のもとで ，ス
図8 GRに 対する重み和最小クリーク分割 Fig. 8 Weighted minimum clique partitioning for
GR.
図9 合成され たRTL データパス（ 本手法） Fig. 9 A synthesized RTL data path. (our method)
キャンレジ スタ数を最小にするレジ スタバ インデ ィン グ とし て ，以下の問題を考えることができる．
［ 重み和最小クリーク分割問題 ］
入力： レジ スタ両立グ ラフGR= (VR, ER) 出力： クリークの重みの 総和
n
i=1Wr(Ci)が 最小と
なるクリーク分割 π= {C1, C2,. . . , Cn}
（ ク リーク Ci = (Vi, Ei)とすると ，VR = V1∪ V2∪ . . . ∪ VnかつVi∩ Vj= ∅, ∀i |= j）
条件： クリーク数nが 最小
［ 例6］ 図 7 の レ ジ ス タ 両 立グ ラ フ に 対し て ，最 小 と な る ク リ ー ク 数3の 分 割は ，{{d2}, {u, v, w}, {d1, x, y}}, {{d2}, {u, v, w, y}, {d1, x}}, {{d2}, {u, v, d1}, {w, x, y}}, {{d2}, {u, v, y, d1}, {w, x}} の 4通 り 存 在 す る ．こ の う ち 図 8 に 示 す{{d2}, {u, v, w, y}, {d1, x}} が ク リ ー ク の 重 み の 和 が 0 + 1 + 0 = 1で 最 小と な る 分 割で あ る ．こ の と き ， セルフル ープ を 構成するクリーク {u, v, w, y}に よっ て，少なくとも一つの スキャンレジ スタが 必要である． これに 対し ，ほかの最小クリーク分割の解ではセルフ
図10 合成され たRTL データパス（ クリークの重みの和 が 最小でない場合 ）
Fig. 10 A synthesized RTL data path. (sum of weights of cliques is not minimum)
ループ を構成するクリーク（ この例では 重み1の辺を 含んでいるクリーク ）が 二つできるため ，少なくとも 二つの スキャンレジ スタが 必要となる．
［ 例7］ 例4，例6（ 図5，図8）の演算器・レジ スタ バ インデ ィング の結果 ，合成され たRTLデ ータパ ス は 図9のようになり，無閉路部分スキャン 設計のため の最小のスキャンレジ スタ数は1となる．これは 図1 のSDFGから合成され るRTLデ ータパスの中で ，最 小の スキャンレジ スタ数である．一方，例6のレジ ス タバ インデ ィング で ク リー クの 重 みの 和が 最 小に な らない クリーク 分割 {{d2}, {u, v, w}, {d1, x, y}}で は ，RTLデ ータパスは図10のようになり，{u, v, w}, {d1, x, y}に 対応するレ ジ スタが セル フル ープ を 構成 することから ，少なくとも二つの スキャンレジ スタが 必要となる．
4. ヒ ューリステ ィックアルゴ リズ ム
ここでは 前章で 述べた重み和最小クリーク分割を解 くヒューリ ステ ィックアルゴ リズムを 示す．これは 重 みなし の最小ク リーク分割を 求め るヒューリステ ィッ クアルゴ リズ ム[3]をもとにし て ，クリーク数最小を 求めながら スキャンレジ スタ数が 最小となるように 重 みを 組み込んだものである．クリークの重みの計算を 変え ることで ，演算器とレジ スタのバ インデ ィング の 両方に 同じ アルゴ リズムを適用することができる．ア ルゴ リズムweighted min cliqueを図11に 示す．
演 算/レジス タ 両 立 グラ フ Gc に対 して， weighted min cliqueは ク リーク 数最 小に 関し て 等 価な複数の解の中から スキャンレジ スタ数を最小にす るクリーク分割C bestを選択する．このアルゴ リズ ムでははじ めに 各頂点に クリークを割り当てる．両立
図11 重み和最小クリーク分割のヒューリスティックアル ゴ リズム
Fig. 11 Heuristic algorithm for weighted minimum clique partitioning.
グ ラフの辺は共有できるクリークの組を表し ている． 最 適 な ク リ ー ク 分 割 を よ り 広 く 探 索 す る た め に ， select start pair(C)でクリーク分割を複数回繰り 返し て求め ，それらの分割の中から クリーク数が 最小 で ク リー クの 重 みの 和が 最 小に な るもの を 最 適 解と し て出力する．select start pair(C)では評価関数 H1 ではじ めに 同じ ク リークにで きる組を選択し ，そ れらのクリークを共有する．この評価関数は 両立グ ラ フの辺の重みが 小さいものを優先する．クリーク分割 を求める繰返し は 前よりもクリーク数が 小さいか また は クリーク数が 同じ で クリークの重みの 和が 小さい分 割が 求められ る限り，続けられ る．クリーク分割の解 を求める全体の繰返し の数Lmaxについては ，実験的 に 評価する．
クリーク分割を求める各繰返し については ，評価関
数H2(hc, hw)で 同じ ク リークにで き る組を 選 択し ， それらのクリークを共有する．これを同じ クリークに で きる 組が な くな るまで 行 う．ここで の 評価関数は ， クリーク数を最小にし ながらクリークの重みの和が 小 さいクリーク分割を求めるのに 利用され る．具体的に は ，以下のように 考え る．
評価尺度hcは クリーク数最小の分割を 求め るため に 適用され る[3]もので ，(α, β)の2項組から な る ． 選択し た共有するクリークの組によって，αはほかに 共有できる可能性のあるクリーク数，βは 共有できな くなるクリーク数を表し ている．同じ クリークにでき る組を選択するとき，αは大きい方が 望まし く，βは 小さい方が 望まし い ．評価尺度hcは α, βの優 先順 位に 従って評価を行う．
評価尺度hwは クリークの重みの和を小さくするた めのもので ，評価尺度hcに 関し て複数の 等価な候補 の中から 一つを選択するために 適用され る．共有し て もクリークの重みが 増えないものを 優先する．演算器 バ インデ ィングでは（ 選択する両立グ ラフの辺の重み ）
−（ 選択し た 辺によって 共有で きな くなる両立グ ラフ の辺の重みの和 ）を計算し ，この値が 最も小さいもの を選択する．選択し た辺によって共有できなくなる両 立グ ラフの辺は ，結果とし てできるクリーク分割の中 に 含まれ ない辺である．この辺の重みを 足し た値が 大 きい方が ，辺の重みの 総和をクリークの重みとすると き ，ク リークの重みの 和を 小さくすることが で きる ． レジ スタバ インデ ィングでは（ 共有する2頂点の重み の和 ）−（ 選択する両立グ ラフの辺の重みと 共有する 2頂点の重みの 最大値 ）を 計算し ，この 値が 最も小さ いものを 選択する．この評価式の第1項，第2項はそ れぞれ 共有前と後のクリークの重みの和を表し ている． この値が0以下であれば ，クリークの重みが 増えるこ とはない．共有前後のクリークの重み和の差が 小さい ものを 優先し て選択することにより，辺と頂点の重み の最大値をクリークの重みとするとき，クリークの重 みの 和を小さくすることを指向し ている．
5. 実 験 結 果
提案手法の有効性を示すために，前章で述べたヒュー リスティックアルゴ リズムを 実装し ，いくつか の 動作 記述のベンチマークに 対し て演算器とレジ スタのバ イ ンデ ィング を求める実験を行った．実験に 利用し たベ ンチマークは3rd Lattice Wave Filter（LWF，図1）， Tseng [10]，Paulin [10]，4th Jaumann Wave Filter
（JWF），4th IIR Cascade Filter (IIR)，5th Elliptic Wave Filer（EWF）の6種類のDFGに対し て何通り かのスケジューリングを試みた スケジュール済みDFG
（SDFG）である．回路名に付いている‘.1’など は同じ DFGで スケジ ューリング を 適当に 変化させ たもの を 示し ている．表1に使用し たベンチマークのレ イテン シ（l），外部入力数（#PI），外部出力数（#PO），外 部入出力以外の演算数（#Op），変数の個数（#Var） を示し ている．
ここで 演算器バ インデ ィングにおいて ，演算両立グ ラフの重みは 長さ5の最短経路まで 評価し た．よって， l(p)を最短経路pの長さとするとき，時間にかける定 数はKl(p)= 325−l(p)とし た．レジ スタバ インデ ィン グ に おいて ，重みに 付け る0と1の間の 定数ωに つ いては ，0.5とおいて 評価し た ．また ，各バ インデ ィ ングで クリーク分割を求める繰返し 数Lmaxについて は ，繰返し の中で 最良の解が 得られ る回数の適切な値 を 調べ るために ，特定の値を 設定せずに 演算/レ ジ ス タ両立グ ラフの辺数とし た ．
バ インデ ィングの結果得られたRTL回路に 対し て ， 文献[14]のアルゴ リズムを用いて 無閉路化に必要な最 小個の スキャンレジ スタを求めた ．その結果を表2に STとして示す．表2において ，#OU, #Mux, #Reg,
#Scanはそれぞれ 合成され たRTLの演算器数，2入 力マルチプレ クサ数，レジ スタ数，スキャンレジ スタ 数を表し ている．CPUはSUN Ultra30で 演算器・レ ジ スタのバ インデ ィングに 対し てLmax回の繰返し で
表1 ベンチマーク特性 Table 1 Benchmark characteristics. Bench. l #PI #PO #Op #Var LWF
LWF.1 5 2 1 5 7
Tseng 5
Tseng.1 3 1 8 11
Tseng.2 6 Paulin
Paulin.1 5 4 3 10 11
JWF JWF.1
JWF.2 9 1 1 17 20
JWF.3 IIR IIR.1 7
IIR.2 1 1 17 22
IIR.3 8 EWF
EWF.1 16 1 1 34 38
EWF.2
表2 ヒューリスティックアルゴ リズムによる実験結果 Table 2 Experimental results with heuristic
algorithms.
RTL Characteristics CPU Bench. M #OU #Mux #Reg #Scan [s]
LWF NT 3 6 3 3 <0.1
ST 3 3 3 1 <0.1
LWF.1 NT 3 5 4 3 <0.1
ST 3 3 4 1 <0.1
Tseng NT 7 6 6 4 <0.1
ST 7 8 5 2 <0.1
Tseng.1 NT 6 8 6 4 <0.1
ST 6 7 6 3 <0.1
Tseng.2 NT 6 7 6 5 <0.1
ST 6 10 5 3 <0.1
Paulin NT 4 17 6 6 <0.1
ST 4 12 6 4 <0.1
Paulin.1 NT 5 16 7 7 <0.1
ST 5 13 7 5 <0.1
JWF NT 3 15 7 7 <0.1
ST 3 14 7 5 <0.1
JWF.1 NT 3 16 7 7 <0.1
ST 3 17 7 5 <0.1
JWF.2 NT 3 17 7 7 <0.1
ST 3 17 7 6 <0.1
JWF.3 NT 4 17 8 8 <0.1
ST 4 17 8 4 <0.1
IIR NT 5 21 7 7 <0.1
ST 5 16 7 4 <0.1
IIR.1 NT 5 23 7 7 1.0
ST 5 20 7 4 1.0
IIR.2 NT 4 22 7 7 1.0
ST 4 20 7 4 1.0
IIR.3 NT 4 21 7 7 1.0
ST 4 13 7 4 1.0
EWF NT 4 39 11 11 56.0
ST 4 33 11 7 53.0
EWF.1 NT 4 35 11 11 56.0
ST 4 37 11 7 53.0
EWF.2 NT 4 35 11 11 56.0
ST 4 34 11 7 53.0
ク リーク分割の 解を 求め るのにかかったCPU時間を 示し ている．CPUにおけ る‘<0.1’はCPU時間が0.1 秒未満であったことを示し ている．
演算/レ ジ スタ両 立グ ラフ の重みの 効果を 調べ るた めに ，スキャンレジ スタ数最大化を 指向する手法 NT も実験した．その結果も併せて表2に示してある．NT は クリーク分割の重み（ クリークの重みの和 ）が 最大 にな るよ うにヒューリステ ィックアルゴ リズムに 変更 を加えて求めたものである．表2の結果より，すべて のベンチマークに対し て，本手法STは手法NTより も少ないスキャンレジ スタ数が 得られた ．これらから わか るよ うに ，提案し た 演算器・レジ スタバ インデ ィ ングにおけ る重みは 無閉路化のスキャンレジ スタ数に
図12 手法NT による合成結果（ LWF） Fig. 12 Result of synthesized RTL data path by
method NT. (LWF)
相関が あるといえ る．参考のため ，図12にLWFの 手法NTのときのRTLデ ータパスを示す．本手法ST のときのRTLデ ータパスは図9に 対応し ている．こ れらの結果のRTLデ ータパ スを見てもわか るよ うに ， セルフループ 数が 減り，複数のループ が 共通のレジ ス タを 通るよ うに スキャンレジ スタが 効率良く共有され て ，スキャンレジ スタ数が 小さくなっている．
クリーク分割の繰返し の中で 最良の解が 得られ る回 数に関し ては ，ほとんどが10以下の少ない回数で ，規 模の大きいEWTでも両立グ ラフの辺数330の約半分 程度の回数でよいことがわかった ．
次に ，本バ インデ ィング 法の有効性を調べるために ， 演算/レ ジ スタ両立グ ラフで 重みを 付けずにヒュー リ スティックアルゴ リズムを適用し た手法NWも実験し た ．その結果を 表 3に 示す．表2と 表3の結果を比 較し てみると ，ほとんど すべてのベンチマークに対し て，NWのスキャンレジ スタ数はSTとNTの間の値 をとった ．STはNWよりも同じ か 小さいスキャンレ ジ スタ数が 得られていることがわか る．提案し た演算 器・レジ スタバ インデ ィング 法は有効であるといえ る．
更に ，ヒューリ ステ ィックアルゴ リズムの 精度を 調 べるために ，表2の実験とは 別に ，EWF以外の例に 対し て ，起こり得るすべてのク リーク分割の中から 時 間をかけて重みが 最小の解を求めることを試みた ．そ の う ち文 献[14]のア ルゴ リズ ムで 求めた 最 小 数の ス キャンレ ジ スタが 表2のST の 結果より 更に 小さく なったものを表4に示す．それ以外のものについては， ヒューリスティックで も演算器数，レジ スタ数 ，及び スキャンレジ スタ数は 等し く小さい解を得ることがで
表3 重みなし の実験結果
Table 3 Experimental results with no weights. RTL Characteristics CPU Bench. #OU #Mux #Reg #Scan [s]
LWF 3 4 3 3 <0.1
LWF.1 3 5 4 3 <0.1
Tseng 7 7 5 2 <0.1
Tseng.1 6 6 6 3 <0.1
Tseng.2 6 8 5 4 <0.1
Paulin 4 12 6 5 <0.1
Paulin.1 5 16 7 5 <0.1
JWF 3 15 7 6 <0.1
JWF.1 3 17 7 7 <0.1
JWF.2 3 13 7 7 <0.1
JWF.3 4 16 8 6 <0.1
IIR 5 17 7 5 <0.1
IIR.1 5 20 7 5 1.0
IIR.2 4 20 7 5 1.0
IIR.3 4 17 7 6 1.0
EWF 4 32 12 10 56.0
EWF.1 4 34 12 10 56.0
EWF.2 4 34 11 10 56.0
表4 全探索による実験結果
Table 4 Experimental results with all search. RTL Characteristics CPU Bench. #OU #Mux #Reg #Scan [s]
Tseng.1 6 7 5 2 <0.1
Tseng.2 6 10 5 2 <0.1
IIR 5 20 7 3 3394.0
IIR.1 5 17 7 3 24059.0
IIR.2 4 10 7 3 16199.0
きた ．この結果からわか るように ，Tseng.1に 対する ST（ 表2）は ，スキャンレジ スタ数だけでなく，レジ スタ数も最小の解を得られていなか った（レジ スタ数 6）．し かし ，スキャンレジ スタに 関する重みを 付けず に 求めた結果NW（ 表3）でもレジ スタ数は6になっ ていることから ，レジ スタ数並び に スキャンレジ スタ 数の増加は ，提案するアルゴ リズムのもととし た最小 クリーク分割のヒューリスティック[3]によるものと思 われ る．また ，IIR, IIR.1, IIR.2では ，STの解となっ たレジ スタ両立グ ラフに対するクリーク分割の重みが ， 表4に 示す解の重みよりわずかに 大きい ，すなわ ち， STのヒュー リ スティックが 最小の重みの ク リーク 分 割を得ていないことがわか った．し たが って ，重みの わずかな差も表現で きるよ うにヒューリステ ィックを 改良することが 課題といえ るが ，これらの スキャンレ ジ スタ数はSTにおいていずれも4で ，最小の3に近 い解を選択し ていることがわか った ．Tseng.2につい ては ，ω= 0.5のもとで ，表4で 示し た スキャンレジ スタ数が2とな るク リーク分割の重みは ，STで 求め
た スキャンレジ スタ数が3となるクリーク分割の重み と等し いことがわか った ．すなわち，Tseng.2につい ては ，今回の実験で設定し たω= 0.5のもとで得られ る重み和最小クリーク分割の解は ，必ずし もスキャン レジ スタ数最小に 対応し ていなか ったといえ る．この 例ではωを0.5よりも小さい値にし て重みを計算する と ，スキャンレジ スタ数が2のときのみが クリークの 重み和が 最小となり，STに よってその 解が 得られ る ことがわか った ．ωの適切な値については若干の調整 が 求められ るが ，多くの 場合，0.5に 設定するだけで よい結果が 得られ ることがわか った ．
以上のように ，提案する重み付けとヒューリスティッ クアルゴ リズムによって ，無閉路化のための スキャン レジ スタ数は最小か 若し くはそれに 近い値を得ること ができるといえ る．
6. む す び
本 論 文で は ，ス ケジュー リング 処 理 後の 動 作 記 述
（ デ ータフ ローグ ラフ ）に 対し て ，テ スト 容易性を 考 慮し ない従来手法と比較し て，演算器数，レジ スタ数 のリソース数を増やすことなく，無閉路化のための ス キャンレジ スタ数の小さいレジ スタ転送レ ベルのデ ー タパ スを 合 成す るテ スト 容 易 化 高 位 合 成 手 法を 提 案 し た ．更に ，提案手法を小規模ではあるが 動作記述の ベンチマークに適用し ，その有効性を示し た ．提案手 法は リソース数の最小性を満たし ながら ，生成され る RTLデ ータパスで無閉路部分スキャン 設計に必要とな るスキャンレジ スタ数を最小にする演算器とレジ スタ のバ インデ ィングが 得られ る．
今後はバ インデ ィング 手法だけでなく，スキャンレ ジ スタ数最小化のための スケジ ューリング 手法につい ても提案する必要がある．更に ，デ ータパ スだけでな くコント ローラも含めた合成手法についても検討し て いきたい．
謝辞 本研究に 関し ，多くの貴重な意見を頂いた 本 学の増澤利光助教授，井上美智子助手はじ め情報論理 学講座の諸氏に 感謝する．本研究は一部，（ 株 ）半導体 理工学研究セン ター（STARC）との共 同研究，及び 文部省科学技術研究費補助金・基盤研究B(2)（ 課題番 号09480054）の研究助成による．
文 献
[1] H. Fujiwara, Logic Testing and Design for Testability, The MIT Press, 1985.
[2] G. De Micheli, Synthesis and Optimization of Digital
Circuits, McGraw-Hill, Inc., 1995.
[3] P. Michiel, U. Lauther, and P. Duzy, The Synthe- sis Approach to Digital System Design, Kluwer Ace- demic Publishers, 1992.
[4] K. Cheng and V.D. Agrawal, “A partial scan method for sequential circuits with feedback,” IEEE Trans. Comput., vol.39, no.4, pp.544–548, April 1990. [5] D.H. Lee and S.M. Reddy, “On determining scan
flip-flops in partial-scan design approach,” Proc. Int. Conf. Computer-Aided Design, pp.322–325, 1990. [6] R. Gupta, R. Gupta, and M.A. Breuer, “The BAL-
LAST methodology for structured partial scan de- sign,” IEEE Trans. Comput., vol.39, no.4, pp.538– 544, April 1990.
[7] 藤原秀雄，大竹哲史，高崎智也，“組合せテスト生成複雑
度で テスト 生成可能な 順序回路構造とその 応用，” 信学論
（D-I），vol.J80-D-I, no.2, pp.155–163, Feb. 1997.
[8] 高崎智也，井上智生，藤原秀雄，“内部平衡構造に基づく
部分スキャン設計法の考察，” 信学論（ D-I），vol.J81-D-I, no.3, pp.318–327, March 1998.
[9] T. Inoue, T. Hosokawa, and H. Fujiwara, “An optimal time expansion model based on combinational ATPG for RT level circuits,” Proc. IEEE the 7th Asian Test Symposium, pp.190–197, Dec. 1998.
[10] T.C. Lee, N.K. Jha, and W.H. Wolf, “Behavioral syn- thesis of highly testable data paths under the non- scan and partial scan environments,” Proc. Design Automation Conf., pp.292–297, 1993.
[11] M. Potkonjak, S. Dey, and R.K. Roy, “Behav- ioral synthesis of area-efficient testable designs us- ing interaction between hardware sharing and par- tial scan,” IEEE Trans. Comput.-Aided Des. Inte- grated Circuits & Syst., vol.14, no.9, pp.1141–1154, 1995.
[12] A. Mujumdar, R. Jain, and K. Saluja, “Behavioral synthesis of testable designs,” Proc. IEEE Int. Symp. on Fault-Torelant Computing, pp.436–445, 1994. [13] V. Fernandez and P. Sanchez, “Partial scan high-level
synthesis,” Proc. European Design and Test Conf., pp.481–485, 1996.
[14] S.T. Chakradhar, A. Balakrishman, and V.D. Agrawal, “An exact algorithm for selecting par- tial scan design,” Proc. Design Automation Conf., pp.81–86, 1994.
（ 平成11 年 4 月 26 日受付，9 月 6 日再受付）
高崎 智也 （ 学生員 ）
平7 創価大・工・情報システム卒．平 9 奈良先端大博士前期課程了．現在奈良先端 大博士後期課程に 在学中．テスト 容易化設 計，テスト 容易化高位合成に 関する研究に 従事．
井上 智生 （ 正員 ）
昭63 明大・工・電子通信卒．平 2 同大 大学院博士前期課程了．同年松下電器産業
（ 株 ）入 社．明大大学院博士後期課程を 経 て ，平5 奈良先端大情報科学研究科助手． 平11 より広島市立大学情報科学部助教授． 松下電気電器産業（ 株 ）に おいて マイクロ プ ロセッサの研究開発に 従事．明治大，奈良先端大，広島市大 に おいて ，テスト 生成，並列処理，テスト 容易化設計に 関する 研究に 従事．博士（ 工学 ）．IEEE，情報処理学会各会員．
藤原 秀雄 （ 正員 ）
昭44 阪大・工・電子卒．昭 49 同大大 学院博士後期課程了．阪大工学部助手，明 治 大 理 工 学 部 教 授を 経て ，現 在 奈 良 先 端 大情報科学研究科教授．昭56 ウォーター ルー大客員助教授．昭59 マッギル大客員 準教授．論理設計，高信頼設計，設計自動 化 ，テ スト 容易 化 設 計 ，テ スト 生成 ，並 列 処理 ，計 算 複雑 度 に 関する研究に 従事．著書に“Logic Testing and Design for Testability”（ The MIT Press）など ．工博．情報処理学会会 員．IEEE Fellow，IEEE Golden Core Member.
