論 文
レジ スタ転送レ ベルデ ータパスの単一制御並行可検査性に 基づ く
組込み自己テ スト 法
山口 賢一
†和田 弘樹
††増澤 利光
†††藤原 秀雄
†A BIST Based on Concurrent Single-Control Testability of RTL Data Paths
Ken-ichi YAMAGUCHI†, Hiroki WADA††, Toshimitsu MASUZAWA†††, and Hideo FUJIWARA†
あらまし レジ スタ転送レ ベルデ ータパスの組込み自己テ スト 法とし て ，単一制御可検査性に 基づ く方法が 提 案され ている[2]．この手法では，小さいハード ウェアオーバヘッド で 100%近い故障検出率が得られるが，組合 せ回路要素を一つず つテ スト するためテ スト 実行時間が 大きい．そこで本論文では ，複数の組合せ回路要素を同 時にテ スト（ 並行テ スト ）できるように ，単一制御可検査性を拡張し た単一制御並行可検査性を提案し ，この可 検査性に 基づ く組込み自己テスト 方式を提案する．ベンチマーク回路を用いた 実験の結果により，提案手法は 単 一制御可検査性に 基づ く手法に 比べて ，ハード ウェアオーバヘッド がほとんど 増加することなく，テ スト 実行時 間を縮小できることを示す．
キーワード テスト 容易化設計，レジ スタ転送レ ベルデ ータパ ス，組込み自己テスト，単一制御可検査性，階 層テ スト
1. ま え がき
VLSIの大規模化，複雑化に 伴い，論理回路のテ ス トとし て組込み自己テスト 法（Built-In Self-Test．以 下 ，BIST）が 重 要 視され て い る ．BISTを 実 現す る ために ，テスト 対象回路の外部入力（Primary Input. PI），外部出力（Primary Output. PO）に ，それぞ れ ，テストパターン 生成器（Test Pattern Generator. TPG），応答解析器（Response Analyzer. RA）を付 加する．し かし ，テ スト 対象回路に 閉路が 含まれてい る場合には ，PIとPOにTPG，RAを付加するだけ では高い故障検出率を得ることができない．そのため， 高い故障検出率を得るために ，回路内部にテ ストのた めのハード ウェアを付加する方法が 数多く提案され て いる[1]．このように ，回路の設計をテスト 容易となる
†
奈良先端科学技術大学院大学情報科学研究科 ，生駒市
Graduate School of Information of Science, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma-shi, 630–0101 Japan
††株式会社日立製作所中央研究所シ ステムLSI研究部 ，国分寺市
Central Research Laboratory, Hitachi, Ltd, 1-280 Higashi- Koinokubo, Kokubunji-shi, 185–8601 Japan
†††大阪大学大学院基礎工学研究科 ，豊中市
Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka-shi, 560–8531 Japan
ように変更することをテスト 容易化設計（Design For Testability. 以下，DFT）と呼ぶ．
BISTは ，test per scan方式とtest per clock方式 に分類できる．test per scan方式では ，回路中の（ 一 部の ）レジ スタを スキャンレジ スタに 変更し ，スキャ ン 操作に より，TPGで 生成し たテ スト 系列を スキャ ンレジ スタにシフト インし ，スキャンレジ スタに 格納 された応答をRAにシフトアウト する．test per scan 方式では ，スキャン 操作によりテスト 系列を1ビ ット ずつシフト イン するので ，連続し たシ ステムクロック でテ スト 系列を印加できず，テ スト 実行時間も長い． 一方，test per clock方式では ，回路中の（ 一部の ） レ ジ スタをTPG，RAに 変更する ．このよ うなテ ス トレジ スタとし ては ，BILBO（Built-In Logic Block Observer）[3]，CBILBO（Concurrent BILBO）が用 いられ る．test per clock方式のBISTとし て，Wun- derlichら[4]は ，回 路 中の すべ て の 閉 路が 少な くと も二つのBILBOか 一つのCBILBOを 含むよ うにす るテ スト 容 易 化 設 計 法を 提 案し て い る ．こ の 手 法で は ，内部レジ スタを 含む多くのレジ スタをBILBOや CBILBOに設計変更する必要があるため，ハード ウェ アオーバヘッド が 大きくなる．
D– Vol. J85–D– No. 6 pp. 527–537 2002 6 527
そこで ，井筒ら[2]は，単一制御可検査性というテス ト 容易性を 提案し ，test per clock方式のBISTとし て ，単一制御可検査性に 基づく方法とそのテ スト 容易 化設計法を提案し ている．この手法では ，内部レジ ス タをBILBOやCBILBOに変更せず，TPG，RAは ， それぞ れ テ スト 対象回路のPI，POのみに 付加する． そし て ，階層テストに 基づいてデ ータパス中の組合せ 回路要素（ 演算器，マルチプレ クサなど ）ご とにテス ト を 行 う．つまり，テ スト 系列をTPGから 各組合せ 回路要素までデ ータパ ス 内の 経 路を 通って 伝搬させ ， 応答をその組合せ回路要素からRAまでデ ータパス内 の経路を通って伝搬させ る．また，連続クロックでテ スト 系列の生成/印加，応答の解析を可能にするため ， これらの経路が 共通部分をもたないよ うにする．その ため ，単一制御可検査性は（ 単一縮退故障に 対し て ） 高い故障検出率が 保証され ，更にシ ステムクロックで のテ ストが 必要となる他の故障モデル（ト ランジショ ン 故障，遅延故障など ）も検出することが 可能である． 井 筒ら の 手 法[2]で は ，内 部レ ジ スタをTPGやRA に 変更せず，応答の 伝搬はデ ータパス中の経路を利用 するため ，Wunderlichら[4]の手法と同等の故障検出 率を得るために 必要な ，ハード ウェアオーバヘッド は 小さい．し かし ，組合せ回路要素を一つず つテスト す るために ，テストセッション 数がテ スト 対象回路要素 分だけ 必要になるためテ スト 実行時間が 大きくなる． そこで ，本論文では ，井筒ら の手 法[2]の 長 所で あ る高い故障検出率と低いハード ウェアオーバヘッド を 実現し ，欠点であったテ スト 実行時間を短縮するため に ，単一制御並行可検査性を提案する．単一制御並行 可検査性は ，複数の組合せ回路要素を同時にテスト す ることによりテ スト 実行時間を短縮するように単一制 御可検査性を一般化し たものである．単一制御並行可 検査性は 単一制御可検査性と同様にデ ータパ ス内のレ ジ スタをTPGやRAに変更せず，PIのみに付加し た TPGから の 値を 伝搬し ，POのみに 付加し たRAへ の応答の伝搬を 行 うため ，井筒らの 手法[2]と 同様に 低いハード ウェアオーバヘッド で 高い故障検出率を得 ることができる．また，低いハード ウェアオーバヘッ ド で 与えられたデ ータパスを単一制御並行可検査にな るように設計変更するテスト 容易化設計法を提案する．
本 論 文で 提 案す るBISTの 特 徴は 以 下の と お りで ある．
• 高い故障検出率：提案手法は階層テスト[5]に基 づき，テ ストはデ ータパス中の回路要素ご とに行われ
る．実際のデ ータパスで使用され るほとんど の組合せ 回路要素（ 加算器，減算器，乗算器，マルチプレ クサ など ）は ，ランダ ムパターンを用いることにより，高 い故障検出率を得られることが 知られており[6]，提案 手法で 高い故障検出率が 得ることが 期待できる．
• 低いハード ウェアオーバヘッド ：提案手法は 井 筒らの手法[2]と同様にTPG，RAをPI，POのみに 付加するので ，Wunderlichら[4]の手法に 比べ，ハー ド ウェアオーバヘッド が 低いことが 期待できる．
• 短いテスト 実行時間：提案手法はデ ータパス中 の複数の組合せ回路要素を同時にテ スト する．そのた め，一つずつテストする井筒らの手法[2]に比べて ，テ スト 実行時間が 短くなることが 期待できる．
• test per clock方式：井筒ら の 手法[2]と 同様 ， 連続クロックで ，テ スト パターンの生成，応答の解析 が 可能であり，シ ステムクロックでのテ ストが 可能で ある．ただし ，シ ステムクロックは ，通常動作時の最 大遅延だけから 決定するのではなく，テ スト 動作時の 最大遅延も考慮し て決定するものとする．
以下，2.ではデ ータパスを定義し ，デ ータパスグ ラ フについて述べる．3.では単一制御並行可検査性を定 義する．4.では単一制御並行可検査性に基づ くテスト 容易化設計法を述べる．5.ではベン チマーク回路を用 いた実験により，提案手法を評価し ，6.にてまとめる．
2. データパ ス
2. 1 データパ ス
レジ スタ転送レ ベル 回路はデ ータパスとコント ロー ラから 構成され るが ，本論文ではデ ータパ スのみを 対 象と考え る．デ ータパスは以下の構成要素からなる．
⊲ 回路要素
⊲ デ ータ信号線：回路要素を相互に 接続
⊲ 制御信号線：コント ローラから 回路要素へ制御 信号を伝達
⊲ 状態信号線：回路要素からコント ローラへ状態 信号を伝達
以下に 各構成要素について説明する．
• 回路要素：回路要素はPI，PO，ラッチ ，レジ スタ，マルチプレ クサ，演算モジュールに分類され る． この うちマルチプ レ クサ，演算モジュールを組合せ 回 路要素と呼ぶ．
回路要素に対し てデ ータ信号線が 接続され る端子を デ ータ端子，制御信号線が 接続される端子を制御端子， 状態信号線が 接続され る端子を状態端子と呼ぶ．デ ー
タ端子は 回路要素に 信号を入力するためのデ ータ入力 端子と回路要素からデ ータを出力するためのデ ータ出 力端子に 分類され る（ 以下，デ ータ入力端子を入力端 子 ，デ ータ 出力端子を 出力端子と 呼ぶ ）．デ ータパ ス 上のすべての回路要素のデ ータ端子は 等し いビ ット 幅 をもつものとする．
PI，PO： PIは デ ー タ パ ス 外 部か ら デ ー タ パ スに デ ータを 入力するための回路要素，POはデ ータパ ス から 外部にデ ータを 出力するための回 路要素であ る ． 便宜上，PIは 一つの出力端子のみをもち，POは 一つ の入力端子のみをもつものとする．
マルチプレ クサ： マル チプ レ クサは 二つの 入 力端子 と 一つの 出力端子，1ビ ット の 制御端子をもつ ．制御 端子の値に 従って ，対応する入力端子の値をそのまま 出力端子に 出力する．
演算モジュール： 演算モジ ュールは 一つまたは 二つ の入力端子，一つの 出力端子，たかだか 一つの制御端 子，たかだか一つの 状態端子をもつ．入力端子に 与え られた値に 対し て演算を行い，その結果を出力端子に 出力する．
ラッチ，レジ スタ： ラッチ，レジ スタはいずれも記憶 素子である．ラッチは 一つの入力端子と一つの出力端 子をもつ．入力端子に 与えられた値を記憶し ，その値 を次のクロックサイクルで 出力端子に 出力する．レジ スタは 一つの 入力端子と 一つの 出力端子，1ビ ット の 制御端子をもつ．制御端子の値によって ，入力端子の 値を 新たに 記憶するか（ ロード ），既に 記憶し てい る 値を 保持する（ ホ ールド ）．記憶し て いる値は 次の ク ロックサ イクルで 出力端子に 出力する．
• デ ータ信号線：デ ータ信号線（ 以降，単に 信号 線と呼ぶ ）は相異なる回路要素の出力端子と入力端子 を接続する．複数の信号線を同一の出力端子に接続で きる（ ファンアウト 可能 ）が ，入力端子に 接続する信 号線は1本のみとする．
• 制御信号線，状態信号線：制御信号線はコント ローラからデ ータパス上の回路要素に 対し て制御信号 を伝達し ，状態信号線は 回路要素からコント ローラに 対し て状態信号を伝達する．
2. 2 データパスグ ラフ
デ ータパ スに 対し てデ ータパ スグ ラフG = (V, A) を次の有向グ ラフとし て定義する．
• V = V1∪ V2
ここで V1はデ ータパス中のすべての回路要素の 集 合 ，V2 はデ ータパ ス中のすべ てのデ ータ端 子の 集合
(a) Data path (b) Data path digraph
図1 データパスとデータパスグラフ Fig. 1 Data path and data path digraph.
とする．以下では ，デ ータパ スグ ラフ Gの 頂点集合 V1, V2 をそれぞれG.V1, G.V2,と表す．また，すべて の組合せ回路要素の頂点集合をVC(⊂
=V1)とし て表す．
• A = A1∪ A2∪ A3
ここで A1 はデ ータ信号線を 表し ，A1= {(x, y) ∈ V2 × V2|出 力 端 子 xと 入 力 端 子 y が デ ー タ 信 号 線 で 接 続 } と す る ．ま た ，A2，A3 は そ れ ぞ れ ， 入 力 端 子 と 回 路 要 素 を 接 続 す る 信 号 線 ，回 路 要 素 と 出 力 端 子 を 接 続 す る 信 号 線 を 表 す．す な わ ち ， A2 = {(x, u) ∈ V2 × V1|xは u の 入 力 端 子 }， A3 = {(u, x) ∈ V1× V2|xはuの 出 力 端 子}と す る．以下では ，デ ータパスグラフGの辺集合A1, A2, A3 をそれぞれG.A1, G.A2, G.A3とし て表す．
図1 (a)のデ ータパ スに 対するデ ータパ スグ ラフを 図1 (b)に示す．本論文で対象とするデ ータパスは，そ のデ ータパ スグ ラフにおいてすべての入力端子は ，少 な くとも一つのPIから 到達可能であり，すべての 出 力端子は 少なくとも一つのPOに 到達可能であるもの とする．また，デ ータパ スグ ラフはその 対応するデ ー タパスと同一視する．
またデ ータ パ スグ ラフ の 拡 張とし て ，演 算 器に ス ルー機能が 実現され ている場合のデ ータパ スグ ラフに ついても考える．スルー機能は ，演算モジュールにお いて 入力端子と出力端子の間での任意の値の伝搬を保 証する機能である．
そ こ で ，デ ー タ パ ス グ ラ フ G = (V, A) の 部 分
(a) Data path with thru (b) Data path digraph with thru
図2 スルー機能付デ ータパスとスルー制約付デ ータパス 部分グ ラフ
Fig. 2 A data path and data path diagraph with thru function.
グ ラフ とし て ，スル ー 制 約 付デ ータ パ ス 部分グ ラフ G′= (V, A′(⊂=A))を 定義する ．A′ = A1∪ A′2∪ A3
のよ うに 定義され ，A′2は ，スルー機能を 有する組合 せ回路要素の入力端子と回路要素，若し くはレジ スタ 及び ラッチの入力端子と回路要素への対応を表す．
図2に スル ー機 能を 有す るデ ータパ スに 対す る ス ルー制約付デ ータパスグ ラフを示す．デ ータパスの制 御信号線に 適切な制御ベクトルを与え ることで スルー 制 約 付デ ー タ パ ス部 分グ ラフ 上の 任 意の 単 純 経 路に 沿って任意の値を連続し て伝搬することができる．
図2 (a)のデ ータパ スに 対するデ ータパ スグ ラフを 図2 (b)に 示す．
3. 単一制御並行可検査性
3. 1 単一制御可検査性
井筒らの手法[2]は，BISTのためにレジ スタ転送レ ベルデ ータパスの単一制御可検査性を提案し ，与えら れ たデ ータパ スを単一制御可検査に するため のDFT 手法を提案し た．デ ータパ スの単一制御可検査性を次 のよ うに定義し ている．
[定義1] デ ータパス中の任意の組合せ回路要素M に おいて ，以下の条件を満たす三つの共通部分をもたな い経路P1, P2, P3が 存在するなら ，デ ータパスは単一 制御可検査であるという．
• 任 意の 値が それぞ れ P1, P2, P3 を 通って 伝 搬 可能．
• P1, P2はTPGを始点とし ，M（ 注1）の入力端子 を終点とする．
• P3は ，M の出力端子を始点とし ，RAを終点
とする． ✷
P1, P2 をM の 制 御経路，P3 をM の 観 測経路と 呼ぶ ．
単一制御可検査デ ータパスにおいてTPGとRAを それぞれPIとPOに 置くことに より，組合せ 回路要 素M に 対し て ，制御経路を 用いてPIから 連続し た テ スト 系列を印加し ，観測経路を用いて M の応答を 連続し てPOで 観測できる．ほとんど の組合せ回路要 素（ 加算器，減算器，乗算器，シフタ，マルチプレ ク サなど ）はランダ ムパターンでテスト 可能である．ま た ，比較器など ランダ ムパターンでテ スト 可能でない 組合せ回路要素に 関し ては ，テストポ イント 挿入手法 に よってランダ ムパターン でテ スト 可能にで きる[6]． し たが って ，単一制御可検 査デ ータパ スに 対し ては ， BISTによって高い故障検出率を得ることができる．
制御経路，観測経路上の ，演算モジ ュールやマルチ プレ クサは ，この経路上の入力端子の値が 出力端子に 伝搬するよ うに制御する
（ 注2）
．これらを 制御する信号 は ，M のテ スト の間 固定し て おけば よい ．この よ う に ，各組合せ回路要素に 対し て ，一つの 制御パターン で 十分なので ，この性質のことを単一制御可検査性と 呼ぶ ．
3. 2 単一制御並行可検査性
ここでは ，複数の組合せ回路要素を同時にテスト 可 能なように単一制御可検査性を拡張し た単一制御並行 可検査性を定義する．
[定義2] Mをデ ータパス中の組合せ回路要素の集合 とする．スルー制約付デ ータパ ス部分グ ラフ G′にお いて 組合せ回路要素の集合Mが 以下の条件を満たす とき，Mは 単一制御並行可検査であるという．
• 以下の条件を満たす，互いに 共通部分をもたな い木T1, T2, . . . , Tmが 存在．（ 各Tiを制御木と呼ぶ．）
– それぞれの木はPIを根とする．
– 各組合せ回路要素Mi(∈ M)の各入力端子は木
（ 注1）：P1とP2はそれぞれ 異な るTPGを 始点とする．
（ 注2）：演算モジ ュールが 入力端子の値を出 力端子に 伝搬する機能（ ス ルー機能 ）をもたな い場合は ，テスト 容易化設計で スルー機能を 付加し ， それ を 利用する．
の葉である．
– 各組合せ回路要素Mi(∈ M)の二つの 入力端子 は 異なる木に属する．
• G′−(T1∪T2∪. . .∪Tm)において，以下の条件を 満たす，互いに共通部分をもたない経路P1, P2, . . . , Pn
が 存在．（ 各Piを観測経路と呼ぶ．）
– 各組合せ回路要素Mi(∈ M)の出力端子が 始点 である．
– 各経路の終点はPOである． ✷ Mが 単一制御並行可検査なら ，TPG，RAをそれ ぞ れPI，POに 配置し ，テ スト 系列 ，応答を 制御木， 観測経路を 用いて 伝搬することに より，Mに 属する すべての組合せ回路要素を同時にテストできる．更に ， このテ スト の間，制御木及び 観測経路に 現れ る演算モ ジュール 及び マルチプレ クサの制御信号を固定し てお けば よい ．つまり，Mに 対し て ，一つの 制 御パター ンで 十分である．
デ ータパ スのすべての組合せ回路要素を ，単一制御 並行可検査な組合せ回路要素の集合M1, M2, . . . , Ml
に分割できるとする．このとき，各Miに属する組合 せ回路要素を同時にテ スト すれば ，デ ータパ ス全体の テスト 実行時間は ，全体の組合せ回路要素数ではなく， lに比例すると考えられ る．このとき，各Miに 属す る組合せ回路要素のテストをテストセッションと呼ぶ．
デ ータパ ス全体のテ スト 実行時間を 短縮す るには ， テ ストセッション 数が 小さくなるように ，すべての組 合せ回路要素を単一制御並行可検査な集合に 分割すれ ば よい．一方，同時にテ スト され る組合せ回路は ，相 異なる応答解析器を利用するので ，応答解析器がk個 し か なければ ，たかだか k 個の 組合せ 回路要素が 単 一並行可検査となり得 る ．これ ら のことを 考慮し て ， デ ータパ スの並行可検査性を以下のよ うに定義する． [定義3]（データパスの単一制御k–並行可検査性 ） ス ルー制約付デ ータパス部分グ ラフ G
′
において ，以下 の 条 件を 満た す組合せ 回路要素 VC 上の分 割P (VC) が 存在するなら ，デ ータパ スDPが 単一制御 k–並行 可検査であると定義する．
• ∀S ∈ P (VC)に 対し て ，S（ 組合せ 回路要素の 集合 ）が 単一制御並行可検査
• ∀S ∈ P (VC)に 対し て，|S| <= k
• |P (VC)| = ⌈|VC|/k⌉ ✷ 単一制御k–並行可検査デ ータパ スでは ，組合せ回 路要素集合VC を ，⌈|VC|/k⌉個の部分集合（ ただし ， 各部分集合はたかだかk個の組合せ回路要素を 含む ）
に 分割し ，各部分集合に 属する組合せ回路要素を同時 にテ ストできる．し たが って，テストセッション 数が 単一制御可検査デ ータパスの場合に比べてほぼ1/kに 減少する ．単一制御k–並 行可検査性は ，単一制御可 検査性の一般化であり，k = 1の場合，単一制御k–並 行可検査性は 単一制御可検査性とな る．以下では ，k の 値を 特に 指定し な いと きは ，単一制御 k–並行可検 査性のことを単一制御並行可検査性と呼ぶ ．
4. 単一制御並行可検査テスト 容易化設計法
本 章で は ，与え られ たデ ー タ パ スを 単 一 制 御 並 行 可検査デ ータパスに 設計変更するためのDFT手法を 示す．
4. 1 問題の定式化
与えられたデ ータパスにおいて ，同時にテ スト する 組合せ回路要素に 対し て ，共通部分をもたない制御木 及び 観測経路が 存在し ない場合，単一制御並行可検査 にするためには ，デ ータパ スに新し い経路を付加し な ければ ならない．提案するDFTでは ，この 経路付加 は ，マルチプレ クサ（ テストMUXと呼ぶ ）を用いて 実現する．また，制御経路，観測経路に 演算モジ ュー ルが 現れ る場 合，任意の 値を 伝搬可能と す るために ， この演算モジュールに スルー機能を付加する．そこで ， 単一制御並行可検査のためのDFTを ，次の最適化問 題とし て定式化する．
[定義4]（ 単一制御並行可検査DFT）単一制御並行可 検査のためのDFTを次の最適化問題とし て定義する．
• 入力：デ ータパス，並行度k
• 出力：単一制御k–並行可検査なデ ータパ ス
• 最適化目標：付加するDFT要素（ スルー機能， テ ストMUX）のハード ウェア量最小化 ✷
4. 2 DFTアルゴ リズムの概要
単一制御並行可検査DFTのための 発見的アルゴ リ ズ ムを 示す．本アルゴ リズ ムは ，以 下の2段 階か ら なる．
ステージ1： 与えられたデ ータパスを単一制御可検査 に 設計変更する ．この設 計変更には ，井筒ら[2]の 手 法を改良し たものを 用いる．詳細は4. 3に 示す． ステージ2： ステージ1で 得られたデ ータパスを単一 制御k–並 行可検査なデ ータパ スに 設計変更する ．こ こでは ，すべての組合せ回路要素に 対し て制御経路と 観測経路を決定するまで ，以下の三つの ステップ を繰 り返す．
（1）スケジ ューリング ：同時にテ スト する組合せ
回路要素とし て ，未スケジ ューリング 組合せ回路要素 からk個選択する．1.で 詳細を示す．
（2）観測経路に 関するDFT：( 1 )で 選ば れ た k 個の組合せ回路要素に 対し て，それぞれ 観測経路を決 定する．ここで ，テストMUXを付加し た場合，付加 し たテストMUXは 未スケジューリング 組合せ回路要 素となり，後の スケジューリング の対象となる．1.で 詳細を示す．
（3）制御経路に関するDFT：( 1 )で選ばれたk個 の組合せ回路要素に 対し て ，それぞれ 制御経路を決定 する．( 2 )と同様に ，付加し たテストMUXは 未スケ ジューリング 組合せ回路要素であり，後に スケジ ュー リング 対象となる．4. 5で 詳細を示す．
4. 3 単一制御可検査DFT（ ステージ1） この ステージの目的は ，与えられたデ ータパスを最 小のハード ウェアオーバヘッド で 単一制御可検査にす ることで あり，井筒ら[2]の手 法を 改良し た 手法を 用 いる ．文献[2]の 手法は ，組合せ回 路要素一つず つを 順に 処理し ，互いに 共通部分をもたない二つの制御経 路と 一つの 観測経路をもつよ うにDFT要素を 付加す る．先に 加えたDFT要素は 後の 組合せ回路要素で 再 利用できるので ，全体のハード ウェアオーバヘッド を 削減するには ，必要性の高いDFT要素を 早い段階で 付加することが 重要である．そこで ，本論文の手法で は ，文献[2]の 手法を 適用する前に ，以下に 定義する カット エッジに 基づいた 処理を行う．
[定義5] デ ータパ スグ ラフ Gに 対し て ，e ∈ G.A3 を取り除いて得られるグラフをG
′(e)
と表す．つまり， G′(e).V = G.V か つG′(e).A = G.A − {e}である ． G′(e)に おいてど のPIから も到 達不能な 組合せ 回路 要素M が 存在する場合，e(∈ G.A3)をカットエッジ と呼び ，M はeによって支配され るという． ✷
デ ータパ スグ ラフが カット エッジ eをもつなら ，e に よって 支 配され る 組 合せ 回 路 要 素は 共 通 部 分を も たない二つの 制御経路をもつことがで きず，MUXを 付加することにより，新たな経路を追加する．一つの MUXを 加え ることに より，複数の カット エッジ を解 消できる可能性がある．そこで ，カット エッジに 対し て次の 半順序関係を定義し ，その 半順序に 従ってカッ ト エッジを処理する．
[定義6] デ ータパスグ ラフGにおけ るカットエッジ eに対して，eによって支配され るすべての組合せ回路 要素をD(e)と表す．ここで ，Gにおけ るカットエッ ジの半順序を次のよ うに定義する．
while (there exists a cut edge in G){ e:=minimal cut edge in G;
V(e) :=the set of all vertices unreachable from any PI in G(e);
M(e) :=the maximal subgraph of G(e) with vertex set V(e);
construct a spanning tree T of M(e) with the root u (u is the end vertex of e); V′:= {v ∈ V (e) | v has an outgoing edge in M(e).E − T.E};
choose any v from V′and insert a test MUX M in front of the v’s input port;
if (there exists a PI i unreachable to e) connect i to the other input port of M; else
choose any PI i and connect i to the other input port of M;
update G by adding M and the lines; }
apply the DFT method in [2];
図3 単一制御可検査DFT Fig. 3 DFT for single-control testability.
カットエッジe及び e
′
において ，D(e) ⊂ D(e
′)
の とき，またそのときに 限り，e < e
′
とする． ✷ もし ，二つの カット エッジ e1と e2 がe1< e2 を 満たすなら ，e1 のために 加えられ るMUXに よって ， e2 が カット エッジ で な くな るこ とが あ る ．こ のよ う に 提案手法では ，最初に e1 に 対し てテ ストMUXを 付 加し て お き ，必 要で あれば e2 に 対し て も テ スト MUXを 付加する．カット エッジが なくなるまでテ ス トMUXを 付加し ，その 後は[2]で 提案し た 手法を 適 用してDFTを行う．ただし ，提案手法は最初のステー ジでは 制御経路及び 観測経路の決定は 行わない．図3 に 我々のDFT手法の最初の ステージ を示す．
4. 4 スケジューリング 及び観測経路に関するDFT
（ ステージ2）
スケジ ューリングは 同時にテスト する組合せ回路要 素の集 合Mを 決定することで あ る．提案するDFT アルゴ リズムは ，最小のハード ウェアオーバヘッド で 観測経路を実現できるようにMを決定する．観測経 路を制御経路より先に 決定するのは ，制御経路は 異な る組合せ回路要素で 共有可能だが ，観測経路は共有不 能であり，可観測性のためのDFTハード ウェアオー バヘッド が 支 配的（ 並 行度 kが 大きいと き ，特に 顕 著 ）になるためである．
スケジ ューリングにおいて，組合せ回路要素が 既に 決定され た集合Mに 含まれ るなら スケジ ューリング 済み，そ うでないなら 未スケジ ューリング 組合せ回路
要素とい う．ただし ，すべてのPOは スケジ ューリン グ 済みとする．未スケジ ューリング 組合せ回路要素か ら 同 時に テ スト す る 組 合せ 回 路 要 素を 決 定す る2ス テップ を以下に 示す．
（1）候補組合せ回路要素の選択
• k個以上未スケジ ューリング 組合せ回路要素が 存在する場合：スケジ ューリング 済み組合せ回路要素 に 隣接するすべての未スケジューリング 組合せ回路要 素を候補とする．候補数ℓがk未満ならば ，候補がk 個になるよ うに ，未スケジ ューリング 組合せ回路要素 を適当に 候補に 加え る
• m(< k)し か 未スケジ ューリング 組合せ 回路要 素が 存在し ない場合：すべての未スケジ ューリング 組 合せ回路要素を候補とする．
（2）組合せ回路要素集合M及び Mに 含まれ る 組合せ回路要素の観測経路の決定
次に 示すよ うにデ ータパスグ ラフを構築し ，流量k
（ ただし ，候補数が m(< k)個なら流量m）の最小費 用流問題を解く．図4にk = 3の例を示す．
• 各候補組合せ回路要素に 対する辺をもつダ ミー 頂点を付加し 始点とする．
• すべてのPOからの辺をもつダ ミー頂点を付加 し 終点とする．
• 各候補組合せ回路要素からPOへテ ストMUX に 対応する辺を加え る．
• 得られ たグ ラフに おけ る各辺(u, v)に 対し て ， 容量をc(u, v) = 1と 定義し ，コ スト p(u, v)を 以下 のよ うに定義する．
p(u, v) = cost thru(u) uがvの入力端子
= cost M U X (u, v)が 付加され たMUX
= 0 上記以外の場合
（cost thru(u)はuからvの出力端子への スルー機能 のハード ウェアコ スト．スルー機能が 既に 付加され て いる場合は ，cost thru(u) = 0．cost M U XはMUX のハード ウェアコ スト ）
グ ラフの最小費用流はMを構成する組合せ回路要 素数であり，最小費用流で 用いる経路は ，最小のハー ド ウェア オーバ ヘッド で 実現で きる 観 測 経路を 表す．
観測経路のために ，スルー機能とテストMUXが 付加 され る．
4. 5 制御経路に関するDFT（ ステージ2） 与えられ た 組合せ 回路要素集 合Mに 対し て ，M に 含まれ るすべての組合せ回路要素の 制御経路を図5
図4 (k = 3) スケジューリング例 Fig. 4 Example of scheduling (k = 3).
G′:= a digraph obtained from G by removing the observation paths of all modules in M while (M |= ∅){
choose any module v ∈ M;
determine control paths P1and P2of v (by finding the minimum cost flow of two); add DFT elements for P1and P2; for each module u on Pi(i = 1, 2)
update G′by removing the outgoing edge from the input port of u that is not on Pi; M:=M-{v}
}
図5 制御経路に 関するDFT Fig. 5 DFT for control paths.
の手続きに よって 決定する ．この手 続きでは ，Mの 要素は 一つずつ考慮する．組合せ回路要素の制御経路 は観測経路と同様に決定され る：GからMに含まれ る組合せ回路要素のすべての観測経路を除去し て構成 され るグ ラフG
′
において ，流量2の最小費用流問題 を解く．Gの代わりに G′において 扱うのは ，決定す る制御経路が 既に 決定され ている観測経路と共通部分 をもたないようにするためである．すべての制御経路 が 手続きによって互いに 共通部分をもたない木を決定 するので ，各繰返し ステップの最後にG
′
を更新する． 図5において，組合せ回路要素に二つの共通部分を もたな い制御経路が 見つからない場合，テストMUX M を 制 御 経 路 を 構 成 す る た め に 付 加 す る ．テ スト MUX Mは ，付加されたときには未スケジューリング 組合せ 回路要素とみな され ，M の 制御経路と 観測経 路は 後で 決定する．デ ータパスの構造によっては ，M の入力端子に 新たにも う一つのテストMUXが 制御経 路を決定するために 加えられ る可能性があり，更にテ ストMUXのためのテストMUXが 付加され 続ける可 能性もあ る．連続し たテストMUXの付加を避け るた
めに ，必要に 応じ て 図5の 手続きに 例外処理を 行 う． この 場合 ，グ ラフ Gに おいて M の 制 御経路の 決定 を 妨げ る観測経路を 有する組合せ 回路要素 M
′ ∈ M
を 検出し ，M′ から（ テ ストMUXを 加え ることで ） POに 直接観測経路を生成することによってM′の観 測経路を変更する．
4. 6 テストMUX挿入に関する考察
提案し たDFT手法では ，あ る組 合せ 回路要 素M の制御経路若し くは観測経路を新たに生成するために ， テストMUX（M′とする ）を付加することがある．こ のテ ストMUX M′もテ ストの対象であり，追加時に は ，M
′
は 未スケジュー リング 組合せ 回路要素とみな され る．つまり，M の スケジ ュール のためにM
′
を 加え ることは ，未スケジ ューリング 組合せ回路要素数 を減らすことには 寄与し ない．
そこで ，テストMUX M′ を付加する代わりに ，M を以降のテ ストセッションに移すことによって，全体 とし て同じ テストセッション 数を小さいハード ウェア オーバヘッド で実現できる可能性がある．ただし ，M のテ ストのためにM′を追加すると ，M′を他の組合 せ回路要素の制御経路及び 観測経路のために 利用可能 で あ り，他のテ ストMUXの 追 加を 防ぐ ことが あ る ． このため ，M
′
を 付加し ないことで ，同じ テ スト セッ ション 数を小さいハード ウェアオーバヘッド で実現で きるとは 限らない．そこで ，上記の手法の有効性を実
図7 DFT 適用後 (k = 2) Fig. 7 Paulin DFT circuit(k = 2).
験的に 調査する．そのために ，図5に おいて ，M が 前 節で 述べた 例 外 処 理を 必 要と す る 組 合せ 回 路 要 素 であ る場合，M (∈ M)をMから 取り除き ，未スケ ジューリング 組合せ回路要素とするように変更し た場 合についても，実験結果を次節に 示す．
ただし ，上記の変更によって得られ るデ ータパスは， 変更し ない場合と同じ テ ストセッション 数をより小さ
図6 Paulin 元回路 Fig. 6 Paulin original circuit.
いハード ウェアオーバヘッド で 実現する場合であって も，k 並行可検査の定義を満たすとは 限らない．これ は ，得られたデ ータパスの組合せ回路要素が 少なくな るために，テストセッション 数が⌈|Vc|/k⌉となること を保証できないからである．
4. 7 適 用 例
提 案し た 手 法をレ ジ スタ 転 送レ ベル ベン チ マ ー ク 回路Paulin（ 図 6）に 適用し たデ ータパ スを 図7に 示す．図7は ，並行度kを2とし て 得られ た単 一制 御2並行可 検査なデ ータパ スで あ る ．図 7に おけ る m12, m13, m14, m15, m16, m17, m18は，ステージ1 の処理に より 加えられ たDFT要素であ る．m13は ， 図6のsub1とm2を接続する信号線が ，4.3で 示し たカット エッジであるために加えられたMUXであり， m12もカットエッジ 処理によって加えられたMUXで ある．また，m14, m15, m16, m17, m18は井筒らの手 法[2]に基づいて挿入されたMUXである．表1では ，
表1 Paulin に対するステージ 2 の適用過程 (k = 2) Table 1 Application process of the stage2 in
Paulin(k = 2).
ID test module DFTelements 1 m15 m18 add.1-r,mult.1-r
2 m14 m17
3 m1 m16 sub.1-r
4 m4 m2 mult.1-l
5 add.1 sub.1
6 m6 m9 mult.2-r
7 m12 m11 mult.2-l
8 m5 m13
9 m3 mult.1
10 m8 m10 MUX(m19)
11 m7 mult.2 add.1-l 12 m19
表2 回路特性 Table 2 Circuit characteristics.
#PI #PO #Reg #MUX #OP Area(8 bit) Area(16 bit) Area(32 bit)
Tseng 3 2 6 7 7 858.6 2499.4 8085.0
Paulin 2 2 7 11 4 1142.9 3818.9 13778.9
LWF 2 2 5 5 3 355.8 735.0 1493.4
表3 付加テストMUX 及び スルー機能 Table 3 Added MUX and thru function. our previous method
[2]
Our methods
(k = 1) k= 1 k= 2 k= 3 Modification
(k = 3)
Circuit #MUX #THRU #MUX #THRU #MUX #THRU #MUX #THRU #MUX #THRU
Tseng 8 8 10 11 15 8 14 8
Paulin 8 5 7 6 8 7 14 7 12 7
LWF 4 3 2 4 4 4 11 3 7 2
ステージ2の適用過程を示す：IDはテストセッション のIDを 示し ，test moduleは ，セッションで テ スト され る組合せ回路要素を表す．DFTelementsは，セッ ション を 行うために 付加され たDFT要素を 示す．例 えば ，add.1-rは ，加算器add.1の 右入力から 出力へ のスルー機能の付加を表す．
5. 実 験 結 果
この章では ，提案手法の実験結果を示し ，提案手法 と井筒らの手法[2]を比較する．
実験に 使用し たレジ スタ転送レ ベルベンチマーク回 路は ，Tseng及びPaulinと3rd Lattice Wave Filter
（LWF）である．なお，井筒らの手法ではTsengでの 適用結果について 示され ていないため ，比較について はPaulinとLWFで行う．表2にそれらのベンチマー ク回路の特性を示す：#PI,#PO,#Reg,#MUX,#OP は それ ぞ れPI数 ，PO数 ，レ ジ ス タ 数 ，マル チプ レ クサ数，演算モジ ュール 数を表す．回路面積の単位 はgate equivalentで ，論理合成ツール とし てAuto- LogicII（Mentor Graphics）を用い，ALTERA社の 論理合成ラ イブ ラリを使用し て ，計算機上で 論理合成 を行うことによって得た ．
表3は，DFTによって付加され るテストMUXとス ルー機能数を示し ，表4では ハード ウェアオーバヘッ ド （HW/OH）を 示す．これらの 表において ，Modi- ficationについては4. 6で 示し た変更によって得られ た結果である．一般にBISTを実現する場合，PI及び POにはTPG及びRAを付加するので ，表4にそれ らは 含まな いものとし た ．ただし ，k = 3の 場合は ， 新たに 応答を 観測するためのLFSRを 付加し たため ，
表4 ハード ウェアオーバヘッド Table 4 Hardware overhead.
our previous method [2] Our methods
(k = 1) k= 1 k= 2 k= 3 Modification (k = 3)
Circuit bit width HW/OH(%) HW/OH(%) HW/OH(%) HW/OH(%) HW/OH(%)
8 33.47 41.25 64.07 61.19
Tseng 16 22.61 27.83 42.43 40.48
32 13.68 17.01 25.74 24.54
8 22.50 19.15 26.17 46.38 41.98
Paulin 16 13.23 12.39 15.38 26.66 24.11
32 7.27 6.80 8.66 14.48 11.00
8 35.10 23.66 37.55 109.13 78.92
LWF 16 33.32 22.34 35.59 100.83 72.05
32 32.47 21.71 34.66 96.87 68.78
表5 テストセッション Table 5 Test session.
our previous method [2] Our methods
(k = 1) k= 1 k= 2 k= 3 Modification (k = 3)
Circuit session session session session session
Tseng 21 12 10 10
Paulin 23 22 12 10 10
LWF 12 10 6 7 6
その ハード ウェアオーバヘッド を加えたものを示し て いる ．表4より，提案手法のk = 1の場 合 ，井筒ら の 手 法[2]と 比較し て ハード ウェア オーバ ヘッド が 改 善され ていることがわか った．これは ，今回追加し た カット エッジに 基づ く処理が 効果的に 働いたためであ る．表5にテストセッション 数を示す．表4及び 表5 から ，ハード ウェアオーバヘッド とテ スト 実行時間の トレ ード オフがわか る．提案手法のk = 2の場合，以 前に 提案し た 手法[2]よりもテ スト セッション 数が 削 減できており，提案手法はテ スト 実行時間を改善し て いる．し かし ながら ，テストMUXのテ ストによって テ ストセッション 数が 増加し たため ，k = 3におけ る テ ストセッション 数は 我々が 予期し ていたよりも（ 組 合せ回路要素数の約1/3）より悪くなった ．4. 6で 示 し た 修正DFTが 今回実験し た回路に 関し ては 有効に 働いたことが ，表4，表5から 示され る．故障検出率 については 示さないが ，テ スト 対象組合せ回路要素に 対し てTPGからの値を伝搬し ，その応答をRAへ伝 搬する手法は 井筒ら の手法[2]と同じ であ るため ，井 筒らの手法と同じ 高い故障検出率が 達成され る．
6. む す び
本論文では，BISTのためのRTLデ ータパスの単一 制御並行可検査性とそのDFTに ついて 提案し た ．提 案手法のBISTの利点は 高い故障検出率，低いハード ウェアオーバヘッド ，短いテ スト 実行時間，シ ステム
クロックでテスト 可能である．
提案手法は ，test per clock方式に 基づ き，テスト 対象組合せ回路要素に 対し て，連続クロックでテスト パターン の生成，応答の解析が 可能であるのでシ ステ ムクロックでテスト 可能であると考えている．ただし ， シ ステムクロックは ，通常動作時の最大遅延だけから 決定するのではなく，テ スト 動作時の最大遅延も考慮 し て決定するものとする．し たが って ，テ スト 動作時 の最大遅延が 通常動作時の最大遅延よりも大きい場合， 通常動作時の回路性能を犠牲にし ていると考えられ る． この点を改良するには ，テ スト 動作時の最大遅延が 通 常動作時の最 大遅延より大き くならな いよ うにDFT 要素を付加することが 考えられ るが ，これは 今後の課 題である．
また，提案手法では ，MUXと 演算モジュールを 等 価と扱っている．し かし ，MUXのテスト 系列長は 演 算モジュール のものより短い場合が 多く，MUXと演 算モジ ュールのテ ストセッションを分け ることに よっ てテ スト 実行時間を短くすることができると 考えられ る．し たが って ，MUXと 演算モジュール を別のテ ス ト セッションでテ スト するような スケジ ューリング の 考案が 必要である．更に ，提案手法の有効性を明らか にするため ，より大規模な回路への提案手法の適用も 必要である．
提案手法は ，RTL回路のデ ータパスに対するBIST 手法である．し たが って，コント ローラも含めたRTL
回路全体のBIST手法の考案が 今後の課題である． 謝辞 本研究に 際し ，多くの貴重な意見を頂いた 本 学の井上美智子助教授，大竹哲史助手，情報論理学講 座の皆様方に 深く感謝致し ます．本研究は 一部，日本 学術振興会・科学研究費補助金・基盤研究B(2)（ 課題 番号09480054）の 研究助成 ，及び（ 株 ）半導体理工 学研究セン ター（STARC）との共同研究による．
文 献
[1] M. Abramovici, M.A. Breuer, and A.D. Friedman, Digital System Testing and Testable Design, Com- puter Science Press, 1990.
[2] 井筒 稔，和田弘樹，増澤利光，藤原秀雄，“単一制御可検 査性に 基づ くレジ スタ転送レベルデータパスの組込み自己 テ スト 容易化設計法 ，” 信学論 (D-I), vol.J84-D-I, no.1, pp.69–77, Jan. 2001.
[3] B. Koenemann, J. Mucha, and G. Zwiehoff, “Built-in logic block observation techniques,” Proc. 1979 IEEE Test Conf., pp.37–41, 1979.
[4] A.P. Stoele and H.J. Wunderlich, “Hardware-optimal test register insertion,” IEEE Trans. Comput. Aided Des. Intergrated Circuits & Syst., vol.17, no.6, pp.531-539, 1998.
[5] I. Ghosh, A. Raghunathan, and N.K. Jha, “Design for hierarchical testability of RTL circuits obtained by behavioral synthesis,” Proc. 1995 IEEE Int. Conf, on Computer Desing, pp.173–179, 1995.
[6] I. Ghosh, N.K. Jha, and S. Bhawmik, “A BIST scheme for RTL circuits based on symbolic testabil- ity analysis,” IEEE Trans. Comput. Aided Des. In- tergrated Circuits & Syst., vol.19, no.1, pp.111–128, 2000.
（ 平成13 年 7 月 11 日受付，10 月 18 日再受付）
山口 賢一 （ 学生員 ）
平11 奈良高専専攻科・電子情報工学専攻 了．平13 奈良先端科学技術大学院大学博 士前期課程了．現在同大博士後期課程に 在 学中．現在テスト容易化設計の研究に従事．
和田 弘樹 （ 正員 ）
平8 阪大・工・通信卒．平 10 奈良先端 大情報科学博士前期課程了．平13 同大博 士後期課程了．現在（ 株 ）日立製作所中央 研究所に 勤務．現在テ スト 容易化設計の研 究に 従事．博士（ 工学 ）．
増澤 利光 （ 正員 ）
昭57 阪大・基礎工・情報卒．昭 62 同大 大学院博士後期課程了．同年同大情報処理 教育セン ター助手．同大基礎工助教授を経 て ，平6 奈良先端科学技術大学院大学情報 科学研究科助教授．平12 阪大基礎工学研 究科教授，現在に 至る．平5 コーネル大客 員準教授（ 文部省在外研究員 ）．分散アルゴ リズ ム，並列アル ゴ リズム，テスト 容易化設計，テスト 容易化高位合成に 関する 研究に 従事．工博．ACM，IEEE，EATCS，情報処理学会各 会員．
藤原 秀雄 （ 正員：フェロー ） 昭44 阪大・工・電子卒．昭 49 同大大学 院博士課程了．同大・工・電子助手，明治 大・工・電子通信助教授，情報科学教授を経 て，現在奈良先端大・情報科学教授．昭56 年ウォータール ー大客員助教授．昭59 年 マッギル大客員準教授．論理設計論，フォー ルト ト レ ラン ス ，設 計 自動 化 ，テ スト 容 易 化設 計 ，テ スト 生 成，並列処理，計算複雑度に 関する研究に 従事．著書「Logic Testing and Design for Testability」（MIT Press）など ．大 川出版賞，IEEE Computer Society Outstanding Contribu- tion Award，IEEE Computer Society Meritorious Service Award など 受賞．情報処理学会会員，IEEE Computer Soci- ety Golden Core Member，IEEE Fellow．
