完全故障検出効率を 保証するデ ータパ スの非スキャン テ スト 容易化
設計法
和田 弘樹
†増澤 利光
†Kewal K. Saluja
††藤原 秀雄
†A Non-Scan DFT Method for Data Paths to Provide Complete Fault Efficiency
Hiroki WADA†, Toshimitsu MASUZAWA†, Kewal K. SALUJA††, and Hideo FUJIWARA†
あらまし 本論文では ，レジ スタ転送レ ベルデ ータパスを対象とし た完全故障検出効率を保証するテスト 容易 化設計法，及び ，対応するテストプ ラン 生成法を提案する．提案するテ スト 容易化設計法は ，階層テスト 生成法 に 基づいて おり，組合せ回路用テ スト 生成ツールによるテスト 生成を可能とし ている．組合せ回路用テ スト 生成 を利用する従来法の完全スキャン 設計法に 比べ，提案手法は ，ハード ウェアオーバヘッド が 小さく，テ スト 生成 時間，テ スト 実行時間が 短い．提案するテスト 容易化設計法の時間計算量はO(n)（ n はデータパス中の回路要 素数 ）であり，テストプ ラン 生成法は 各回路要素のテ ストプ ランをO(n2) 時間で生成する．
キーワード テ スト 容易化設計，デ ータパス，階層テ スト，完全故障検出効率
1. ま え がき
近年におけ る論理回路の大規模化に 伴い，論理回路 の故障の有無を調べるテストが 重要となり，故障の有 無で 論理回路の 出力が 異な る入力系列（ テ スト 系列 ） を印加するテストの要求も高まっている．特に単一縮 退故障集合に 対し て 完全故障検出効率
（ 注1）
をもつテ ス ト 系列でのテストは ，回路の信頼性を保証する観点か らも極めて有用だが ，一般の順序回路に 対し て故障検 出効率が 高いテ スト 系列は 生成困難で ある ．そこで ， 単一縮退故障集合に 対し て高い故障検出効率をもつテ スト 系列が 容易に（ 組合せ回路に 対するテ スト 生成と 同程度の計算量で ）生成できるように 論理回路の設計 を 変更するテ スト 容易化設計（ 以下DFT）が 実用化 され ている．
完全スキャン 設計[1]は 現在一般的なDFTであり， ゲ ートレベル回路中の全フリップ フロップ（ 以下FF） をスキャンフリップ フロップに置き換えることで ，FF
†
奈良先端科学技術大学院大学情報科学研究科 ，生駒市
Graduate School of Information Science, Nara Institute of Science and Technology, 8916–5 Takayama-cho, Ikoma-shi, 630–0101 Japan
††ウ ィスコン シン 大学，米国
Department of Electrical & Computer Engineering, Univer- sity of Wisconsin-Madison 1415 Engineering Drive, Madison, WI 53706–1691 USA
の 値を 外部から 制御/観測可能とし て いる ．し たが っ て ，FFを 外部入出力端子で 置き換えて 得られ る組合 せ回路（ 以下，核回路 ）に対し てテスト 生成を行えば ， 完全故障検出率をもつテ スト 系列が 容易に得られるが ， 以下の問題点がある．
1. 論理合成後の回路を変更するので ，タ イミング 等の合成時の制約を損な う．
2. ハード ウェアオーバヘッド が 大きい． 3. テ スト 系列長が 大きい．
4. at-speedテストができない．
上記の問題点を解消するために ，ゲ ートレ ベル 回路 に 変換され る前の設計を 対象とし たDFTが 提案され ている[3], [7]．ゲ ートレ ベルに 変換され る前の回路は デ ータを 処理するデ ータパ スとデ ータパスの動作を制 御するコント ローラという二つの部分回路で構成され ， デ ータパスはレジ スタ転送レベル（ 以下RTL）回路と し て 設計され る．ここでRTL回路とはレジ スタや マ ルチプレ クサ，演算器など の回路要素を相互に 接続し たものを 指す．一般に 回路のほとんど はデ ータパスな ので ，RTLデータパスを対象とし たDFTは上記の問
（ 注1）：テ スト 生成アルゴ リズ ムは 故障に 対し て テスト 系列の生成を試 みること で ，故障の冗 長/非 冗長を 判定するが 計算時間の問 題から 実用 上は 判定を打ち切ることが ある．ここで 全故障数をN，判定を打ち切っ た故 障数をN a，と すると 故障検出効率F EはN −N a
N で 与えられ ， F E= 100%の場合を 完全故障検出効率という．
D– Vol. J82–D– No. 7 pp. 843–851 1999 7 843
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
題点の 解 消に 大き く貢献することが 期待され て おり， これ までにいくつかの提案が 行われている[3], [7]．本 論文で もRTLデ ータパ スに 対するDFT手法を 提案 する．以下にRTLデ ータパスに対する既知のDFT手 法について述べる．
まずRTL回路に 対し てDFTを 行 うことで ，論理 合成後の 回路へのDFTが 不用とな るため ，問題点1 は 解消され る．問題点2.∼4.を解消する目的で ，デ ー タパスが 通常使用するデ ータ転送経路を通じ てレジ ス タの値の制御/観測を行うDFTとし て直交スキャン設 計法[3], [4]やGenesis [5]∼[7]が 提案され ている．一 般に 完全スキャン 設計の回路をテスト する場合，通常 動作時とは 別系統のクロック系に 通常動作時よりも周 波数の低いクロックを与え る必要がある．つまり，通 常動作時に 用いられ るクロック系に 通常動作時と同じ 周波数のクロックを与え るテ スト（at-speedテ スト ） ができない．直交スキャンやGenesisではテスト 実行 時のテ スト パターン や応答の伝達にデ ータパ スの通常 動作時のデ ータ転送経路を利用するので ，通常動作時 のクロック系に 通常動作時と同じ 周波数のクロックを 与えるテストが 可能である．よって問題点4.を解消し ている．
直交スキャン 設計では ，デ ータパス上の各レジ スタ の値を外部入出力端子から一度に制御/観測できるよう に ，レジ スタに 対するホールド 機能と演算器に対する マスク素子を追加する．マスク素子は 演算器の入出力 間での 値の伝達に 必要な 定数を発生する．直交スキャ ンでは ，DFTとレジ スタの制御/観測のためのデ ータ 転送経路発見にかか る時間計算量がO(n2)（ ただし n はデ ータパス上の 回路要素数 ）となり，ハード ウェア オーバヘッド も完全スキャンより小さい．し かし 核回 路全体に対し て一括し てテスト 生成を行う必要があり， デ ータパ スの大規模化に 伴うテスト 生成時間の増加は 避けられない．
またテ スト 生成時間を短縮する手法とし て階層テス ト 生成法[2]が あ る．階層テ スト 生成法ではデ ータパ ス上の故障fに対し て2段階のテスト 生成を行う．第 1段階ではfが 発生する回路要素M のゲ ートレベル
回路を用いてテストベクタvを生成する．第2段階で は M に 対し てRTL回路を 用いたテ ストプ ラン 生成 を 行 う．テ ストプ ラン とは 外部入力から M の 入力へ 値を伝達し ，またM の出力の 値を外部出力まで 伝達 するためのデ ータパ スへの 制 御入力の 時 系列であ る ． 第2段階でvのためのテストプ ラン 生成に失敗し た場
合，第1段階にバックトラックし てfに対する新たな テ スト ベクタv
′
を 生成し ，最終的にテ ストプ ラン 生 成が 失敗し た場合はf を冗長とみなす．
また 階層テ スト 生成を 志向し たRTLデ ータパ スの DFTとし てGenesis [5]∼[7]がある．Genesisでは 第 1段階とし て回路要素ご とにゲ ートレ ベル 回路を 用い
たテ スト 生成を行う．次に 第2段階とし て各回路要素 に 対し て ，外部入力から 回路要素の入力へ任意の値を 伝達し ，また回路要素の任意の値を外部出力まで 伝達 できるテ ストプ ラン の生成を試みる．テ ストプ ランが 存在し ない場合にはDFTとし て 外部入力から 直接値 を代入し たり，外部出力で 直接値を観測するためのマ ルチプレ クサ（ テスト マルチプレ クサ ）と配線をRTL デ ータパ ス上の適切な回路要素の前後に 挿入する．こ のよ うな 手法に よって 従来手法[2]で 生じ る第2段階 から第1段階へのバックト ラックがなくなる．しかし ， テストプ ラン 探索時のバックトラックは発生するので ， デ ータパ スの大規模化とともにテストプ ラン 生成時間 が 急速に 増大する．また ，テスト マルチプレ クサと 外 部入出力への 配 線は 大域的で 配線長が 増加し やす く， 回路面積も増大し やすい．
そこで 本論文では 完全故障検出効率を保証するテ ス トが 実行可能であり，かつ完全スキャン 設計の問題点 1.∼4.を 解決するRTLデ ータパ スに 対するDFT手
法とテ ストプ ラン 生成法を提案する．提案する手法で はRTLデ ータパ ス上のすべての 回路要素に 対し てテ ストプ ランが 高速に（ バックト ラックせずに ）求めら れ るようにマスク素子とレジ スタのホールド 機能を追 加する．また生成され るテ ストプ ランはGenesisのテ ストプ ランと同様にデ ータパスの外部入力から回路要 素への任意の値の伝達と ，回路要素が 出力し 得る任意 の値のデ ータパスの外部出力への伝達を保証する．提 案するDFT手法を 適用し たRTLデ ータパ ス上の各 回路要素に 対し てテ スト 生成の第1段階で 完全故障検 出効率をもつテ ストベクタを求め ，第2段階で 求める テ ストプ ランを用いてテ ストベクタの 入力と応答の観 測を行えばデ ータパス全体に対し て完全故障検出効率 を達成できる．
直交スキャン 設計では ，デ ータパス上のすべてのレ ジ スタの値を同時に制御/観測することを要求する．一 方 ，提案手法では すべてのレジ スタを 同時に 制御/観 測する必要はなく，一つの 回路要素に 接続する入力信 号線に ，外部入力から 任意の値の組を設定し ，出力信 号線の値を外部出力で 観測できれば 十分である．し た
がって提案方式は，直交スキャン設計よりもDFTで実 現する回路の能力が 真に 小さいため ，直交スキャン 設 計よりハード ウェアオーバヘッド が 小さい ．また，マ スク素子，ホールド 機能の追加は 局所的な設計変更で あり，Genesisのテ スト マルチプレ クサに 比べても提 案手法は ハード ウェアオーバヘッド が 小さい ．よって 提案手法は従来のRTLデ ータパスを対象とし たDFT に 比べてハード ウェアオーバヘッド が 小さい ．
2. 対象とす るデ ータパ ス
本論文で 扱うRTLデ ータパスについて 述べる． 2. 1 データパス
デ ータパ スは信号線と回路要素で 構成され る．信号 線は 制御信号線，状態信号線，デ ータ信号線に分類さ れ る．制御信号線はコント ローラからデ ータパスの回 路要素へ制御信号を伝達し ，状態信号線はデ ータパス の 回 路要素から コント ローラへ 状態信号を 伝達す る ． 本論文では ，テスト 実行時にすべての制御信号線に 対 し て任意の時点で 任意の値が 回路外部から 設定可能で あり，かつ，すべての状態信号線に 対し て任意の時点 で任意の値が 回路外部から観測可能であると仮定する．
デ ータ信号線（ 以下，信号線 ）はデ ータ出力端子と デ ータ入力端子を接続する．デ ータ出力端子には 複数 の信号線が 接続できる（ ファンアウト 可能 ）が ，デ ー タ入力端子に接続できる信号線は 一つとする．
回路要素は 外部入力，外部出力，レジ スタ，マルチ プレ クサ，演算モジ ュール ，観測モジ ュールに 分類さ れ ，各種信号線が 接続され る端子をもつ．デ ータ信号 線が 接続され る端子をデ ータ端子，制御信号線が 接続 され る端子を制御端子，状態信号線が 接続され る端子 を状態端子と呼ぶ．デ ータ端子は 回路要素の入力であ るデ ータ入力端子（ 以下，入力端子 ）と ，出力である デ ータ出力端子（ 以下，出力端子 ）に 分類され る．す べて のデ ータ 端 子のビ ット 幅は 等し いと す る ．また ， 各入力端子は少なくとも一つの外部入力から 到達可能 であり，各出力端子からは 少なくとも一つの 外部出力 へ到達可能とする．
便宜上，外部入力は 一つの出力端子のみを ，外部出 力は 一つの 入 力端 子の みを もつ 回 路要素とし て 扱 う． マルチプレ クサは二つの入力端子と一つの出力端子，1 ビ ット の制御端子をもち，制御端子の値によって，い ずれかの入力端子の値を出力する．
演算モジュールは 一つ又は二つの入力端子，一つの 出力端子，たかだか 一つの 制御端子，たかだか一つの
状態端子をもつ．演算モジュールは，制御端子と（2入 力演算モジュールの場合は ）他方の入力端子に対し て 適切な定数を与え ることで ，各入力端子と出力端子の 間が全単射になると仮定する．つまり，演算モジュール Mが実現する関数族FMに対し て，Mが1入力（ 入
力端子をx，出力端子をzとする ）ならば ，z= f (x) が 全単射となる関数f ∈ FM の存在を仮定する．また Mが2入力（ 入力端子をx, y，出力端子をzとする ） ならば ，z = f (x, a)，z = g(b, y)が それぞ れ 全単射 となる関数f, g ∈ FM と定数a, bの存在を仮定する． 以降，f(x, a)をfy=a(x)と表し ，g(b, y)をgx=b(y) と表す．
観測モジュールは 一つ又は二つの入力端子，一つの 状 態 端 子 ，た か だ か 一つの 制 御 端 子を も ち ，出 力 端 子をもたない．観測モジュールは 比較器等のモデ ルで ある．
デー タ パ ス 上 の 回 路 要 素 e1, ek に 対 して e1 を 始 点 ，ek を 終 点 と す る 経 路 p を p = (e1, l1, e2, l2, · · · , lk−1, ek) と 表し ，e1– ek 経 路と 呼
ぶ ．ここでliは信号線で ，回路要素eiの出力端子と 回路要素ei+1の 入力端子の一つを 接続する．特に す べてのeiが 相異なる場合，pを単純経路と呼ぶ．経路 pの始点と終点が 同じ 回路要素eであり，eが 始点と 終点以外に 現れず，e以外の回路要素がpにたかだか 1回だけ 現れ る場合，pをサ イクルと 呼ぶ ．また ，経 路pに現れるレジ スタ数をpの順序深度と呼ぶ．任意 の 相 異な る回路要素e1, e2 に 対し て ，e1 を 始点，e2 を終点とする任意の相異なる単純経路の組を再収束経 路の組と呼ぶ．
本 論 文で 提 案 す るDFT手 法が 適 用で き るた め に デ ータパ ス上の任意の経路が 満たすべき条件は次のと おり．
P1: 任意の 演算/観測モジ ュールe1, e2に 対し て ，
任意のe1– e2 経路はレジ スタを 含む．
P2: 任意の 再収束経路の 組に 対し て ，一方の経路 にのみ含まれ るレジ スタが 存在する．
P3: 任意のサイクルにレジ スタが 存在する． 2. 2 端子グ ラフ
以下では ，デ ータパ スを端子グ ラフG= (V, E)と して表す．頂点集合Vはデータパス上のすべてのデ ー タ端子からなる．また，有向辺集合E= E1∪E2は信
号線に 対応する有向辺集合E1と ，回路要素でのデ ー タ端子間の入出力関係を表す有向辺集合E2からなる． つまり，入力端子v1と出力端子v2が 同じ 回路要素に
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
(a) データパス (b) 端子グラフ
図1 データパスと端子グラフ
Fig. 1 Data Path and corresponding port graph.
属する場合のみ，有向辺(v1, v2)がE2の要素となる． 図1にデ ータパ スと 対応す る端 子グ ラフの 例を 示 す．以下では特に 混乱のない限り，Vの要素を入出力 端子とし て扱い，E1 の要素を信号線とし て扱う．
3. テスト 容易化設計アルゴ リズ ム
3. 1 基 本方 針
本 論 文で はデ ー タ パ スに 対し て 階 層テ スト 生 成を 行った場合に完全故障検出効率が 得られ るための十分 条件とし てデ ータパスの強可検査性を考え る．すべて の回路要素に対し て ，1)外部入力から任意の値を入力 端子に 伝達可能（ 強可制御性 ）かつ，2)出力端子のと り得る任意の値が 外部出力まで伝達可能（ 強可観測性 ） ならば ，デ ータパスが 強可検査であるとい う．デ ータ パスが 強可検査ならば ，全回路要素に 対し てテストプ ランが 存在することから ，回路要素ご とに 完全故障検 出効率をもつテストベクタ集合を用いることで完全故 障検出効率を実現する階層テ ストが 可能となる．
提案するテスト 容易化設計法はデ ータパ スを強可検 査とする．まず 強可制御性を確保するために ，入力端 子aご とに 外部入力からaへ 任意の 値を 伝達する経 路（ 制御経路 ）を決定する．次に 強可観測性を確保す るために ，出力端子bご とにbから 外部出力まで 任 意の値を伝達する経路（ 観測経路 ）を決定する．そし て ，これらの 経路上で 値が 伝達できるよ うにDFT要 素を 追加する．DFT要素は2入力演算モジ ュールで の全単射の実現に 必要な定数を発生するマスク素子と 経路間のタ イミングに 関する問題を解決するレジ スタ のホールド 機能からなる．
3. 2 制御林の生成
各入力端子に 対し ，制御経路を求める．一般に ，外
(a) 制御林 (b) 観測林 (c) データパス
（DFT 後）
図2 制御/観測林と DFT 後のデータパス Fig. 2 Control/observe forest and datapath.
(after DFT)
部入力から あ る 入力端子への 経路は 複数存在するが ， テ スト 実行時間を短縮するために ，順序深度が 最小の 経路を制御経路とする．また ，追加され るDFT要素 を削減する目的で ，制御経路の集合が 外部入力を根と する 林を 構成するよ うに 制御経路を 選ぶ ．制御林は ， デ ータパ ス上で 外部入力を始点とし て順序深度に 基づ いた 最短経路林を構成することでO(n)時間で 求めら れ る．図2 (a)に 制御林の例を示す．
3. 3 観測林の生成
各出力端子に 対し ，観測経路を求める．一般に ，出 力端子から 外部出力への経路は 複数存在するが ，観測 経路と制御経路の共有でDFT要素が 削減され るので ， 観測経路と制御経路の共有部分の極大化を目的とし て， 制御林に 含まれない観測経路上の辺が 最小となるよう に 選ぶ（ 制御林に 含まれ ない観測林上の辺を合流辺と 呼ぶ ）．観測林は ，デ ータパ ス上で 外部出力を 始点と し て制御林に含まれない辺の数に 基づいた 最短経路林 を 構成することで O(n)時間で 求められ る．図2 (b) に 観測林の例を示す．
3. 4 DFT要素の追加
任意の 制御/観測経路上を 任意の値が 伝達で きるよ うに ，以下のよ うにDFT要素を追加する．
［ マスク素子の挿入 ］ 回路要素に 関する条件から ，す べての回路要素で 入出力間に全単射が 実現できる．し たが って ，制御林上の任意の経路pにおいて，p上の すべての 辺l ∈ E2を 全単射とする制御入力を 回路要 素に 与えれば pの始点–終点間で 任意の値が 伝達で き る．ただし ，2入力演算モジュール M（ 入力をx, y，
出力をzとする ）に含まれ るp上の辺e（ 注2）を全単射 とする場合，M が 全単射z= fx=a(y)を実現するよ うに ，M の制御入力に 対し てM の関数f ∈ FM を 実現するための 定数を与え ，xに対し て定数aを与え る必要が あ る ．そこで 定数a を 発生するこ とが 可能 なマスク素子をxの直前に追加する．マスク素子は1 ビ ット の制 御入力をもつ1入力1出力の 回路要素で ， 制御入力に 従って定数又は 入力値を出力する．マスク 素子で定数aを発生し ，Mに 制御信号とし てfを与 えればy– z間が 全単射になる．以下では マスク素子 と M を 併せて 一つの 演算モジュールM⋆とみなし ， マスク素子とM の制御信号線を併せてM
⋆
の制御信 号線とみな す（M
⋆
の 入力端子をx
′, y′，出力端子を z′ と すると ，y′ はyと ，x′は マ スク素子の 入力と ， z′はz と同一である ）．また以下では M⋆の 関数で ， y′– z′間を全単射とするものをT HRUと呼び ，x′– z′間で 全単射が 実現できる関数を T HRU
⋆
と呼ぶ ． 観測林上の合流辺を含まない部分経路qは制御林に 含まれ るので ，q上でも値の 伝達が 可能である．また 任意の 合流辺d（dを含む回路要素の入力端子を x, y とし ，dの始点をxとする ）に 対し ，dを全単射とす るためには ，yへある定数を入力し なければ ならない が ，この定数はyへの制御経路（ 以下では ，dの補助 経路と呼ぶ ）から 設定できる．よって制御林上の経路 において 任意の値の伝達が 可能であれば ，任意の観測 経路においても任意の値が 伝達され る．
各経路上で値を伝達する方法を以下に まとめる．制 御経路上ではレジ スタに 値をロード し ，マルチプレ ク サには 経路上の入力端子の値を出力する制御信号を与 え る．また演算モジュールには 関数T HRUを実現す るために 必要な定数を制御入力に 与え る．観測経路上 ではレジ スタに 値ををロード し ，マルチプレ クサには 経路上の 入力端子の 値を 出力する制御信号を 与え る ． また合流辺でない辺を経路上にもつ演算モジュールに はその 関数T HRUを実現するために 必要な定数を制 御入力に 与える．一方で 合流辺を経路上にもつ演算モ ジュールには 関数T HRU
⋆
を 実現するために 必要な 定数を制御入力と他方の（ 経路上にない ）デ ータ入力 に 与え る．このときデ ータ入力に 与え る定数は合流辺 の補助経路を用いて 外部入力から 供給する．
［ ホールド 機能の追加 ］テ ストベクタを 印加する際や テ ストベクタに 対する回路要素の応答を伝達する際に タ イミング 衝突が 発生する場合がある．ここでタ イミ ング 衝突とは ，ある時点で 同一の頂点に 異なる値を与
えようとすることを指し ，テストに 必要な経路の集合 が ，順序深度の等し い経路からなる再収束経路の組を 含む場合に 再収束経路の始点で 発生する．経路に 関す る条件（P2）から再収束経路の組にはど ちらか一方に し か 含まれ ないレジ スタが 存在する．このレジ スタに ホールド 機能を与え ることで再収束経路の組を構成す る経路間でテスト 実行時の順序深度が 実質的に異なる ようにする．タ イミング 衝突が 発生するのは 次のよ う な場合である．
［ 場合1］2入力の回路要素M（ 入力をx, yとする ） のテスト 時に ，xの制御経路とyの制御経路が 同一の 始点と順序深度をもつ場合（ 図3 (a)）．
［ 場合2］2入力の回路要素M（ 入力をu, v，出力を wとし (v, w)を合流辺とする ）の合流辺(v, w)を含 む観測経路sを用いてテストベクタに 対する応答を観 測する場合を考え る．制御経路（ 又は 補助経路 ）の終 点に vを 終点とする s上の部 分経路を 接続し て 得ら れ る経路の うち ，始点と 順序深度が (v, w)の 補 助経 路と等し いものが 存在する場合（ 図3 (b)）．
回路要素M の入力端子xに 対し てdepth(x)はx への制御経路の順序深度を，ctrlP I(x)はxへの制御 経路の始点となる外部入力を表すこととする．また合 流辺(v, w)の うちdepth(v)とdepth(w)が 異なるも のを 観測林から 除いてできた林をT
′
とする．以下の いずれかの条件を満たすレジ スタにホールド 機能を与 え る．
• 任意の2入力の回路要素M（ 入力端子をx, y， 出 力 端 子 を z と し ，(x, z) が 制 御 林 に 含 まれ な い
(a) (b)
図3 ホールド 機能の追加 Fig. 3 Templates for hold-addition.
（ 注2）：2入力モジ ュール 上の2本の辺の うち1本のみが 制御林に 含ま れ るので ，一般性を 失うことなくe= (y, z)と 仮定する．
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
もの と す る ）に お い て ，depth(x) = depth(y)か つ ctrlP I(x) = ctrlP I(y)である場合，制御林上でxに
最も近い先祖のレ ジ スタRにホールド 機能を 与え る
（ 図3 (a)）．
• 任意のレ ジ スタ R（ 入力を x，出力を yと す る ）に対し て以下の条件を満たす回路要素M（ 入力を u, v，出力をwとし ，(v, w)を合流辺とする ）が 存在 する場合，Rにホールド 機能を与える（ 図3 (b)）．
– depth(u) = depth(v)
– T′ 上で 順序深度が0のy– v経路が 存在 – ctrlP I(u) = ctrlP I(x)
このテ スト 容易化設計に より，図1 (a)のデ ータパ スから図2 (c)のデ ータパスが 得られ る．図2 (c)の斜 線部にホールド 機能又は マスク素子が 挿入され る．
4. テスト プ ラン 生成アルゴ リズ ム
本章では 前章のテ スト 容易化設計で 得られたデ ータ パス上の任意の回路要素Mに 対し ，そのテ ストプ ラ ンを生成するアルゴ リズムを 示す．ただし ，アルゴ リ ズムの入力とし て ，制御林，観測林も与え る．
Mが2入力の回路要素で ，M を通るサ イクルが 存
在する場合，M の入力端子に 対する制御経路（cpと する ）の中間にMが 現れ ることがある．M が 故障し ている場合，cpを用いてテストベクタが 正し く伝達で きず，M の 故 障が 検出され ない可 能性が あ る．そこ で ，このよ うなcpが 存在する場合，テ スト ベ クタご とに 副テストを行ってから 主テスト を行う．ここで 副 テ ストとは 外部入力からcpを通し て外部出力までテ スト ベ クタを 伝達することでcp上をテ スト ベ クタが 正し く伝達され るかを確認するテ ストであり，主テ ス ト とは cpを用いた M のテ スト を 指す．副テ スト の ためのテ ストプ ランは 主テ ストのためのテ ストプ ラン と同様に 生成できるので ，以下では 主テ スト のための テ ストプ ラン 生成についてのみ述べる．
（1）主 経路集 合の 生成 まず，M の 入 力 端子ご とに 制御林から 制御経路を 求め ，（ もし あれば ）M の 出力端子に 対し て観測林から観測経路を求める．更に 観測経路上の合流辺ご とに 制御林から 補助経路を求め る．これらの経路集合を主経路集合と呼ぶ ．
図1 (a)の 加 算 器に 対す る 主 経 路 集 合を 図4に 示 す．Cpath1，Cpath2が 制 御 経 路 ，Opathが 観 測 経 路，Spath1が 補助経路を表す．
（2）経路集合のタ イミング 調整 3.4で 示し たよ うに ，回路要素M にテ ストベ クタを 外部入力から 伝
図4 加算器(3) の主経路集合 Fig. 4 Main path set for adder (3).
達するとき，あるいは ，その応答を外部出力まで 伝達 するときに ，タ イミング 衝突が 発生する可能性がある
（ 例えば 図4においてCpath1とSpath1が 同じ タ イ ミングで同じ 外部入力を利用し ようとしている ）．この ようなタイミング 衝突を解消する手続きを以下に示す．
1.制御経路の調整 Mが2入力の回路要素（ 入力
をx, y，出力をz とし ，一般性を失うことなく(x, z) が 制御林に含まれないものと仮定する ）である場合，x の制御経路をcpx，yの制御経路をcpyとする．cpx と cpy の 順序深度と 始点が と もに 等し い場 合タ イミ ング 衝突が 生じ る．この場合，cpx 上の終点に 最も近 いレ ジ スタrにホールド 機能が 追加され ているので ， rを1回ホールド することでタ イミング 衝突を解消す
る．以降，追加され たホールド の回数を経路のレジ ス タ数に 加えたものをその 経路の順序深度とする．
2. 補助経路の 調 整 制御経路の 調整が 終了し た
後に 行う．観測経路上の 合流辺を始点に 近いものから 順にj1, · · · , jkとし ，各jiの補助経路を spiとする．
また ，j0 を制御経路と観測経路を結ぶM 上の辺で 制 御林に 含まれ るものと する．sp1, · · · , spk を順に 次の
方法で 調整する ．これ までに 調整が 終了し た 制御/補 助経路lご とに ，観測経路の 始点からjiの 始点まで の観測経路上の部分経路をlの終点に 連結し て得られ る経路の集合をLとし ，Lの 要素の うちspiと 始点 が 等し い経路の 集合を L
⋆
とする．L
⋆
の 中に spiと 順序深度が 等し い経路が 存在する場合，jiの始点から 観測経路を 逆にたど って 最初に 現れ るレジ スタriを 探す．1) riはji−1–ji 間に 存在すること ，2)テ スト 容易化設計でホールド 機能がriに追加され ること，3) 制御経路は順序深度が 最小であることより，riを1回 ホ ールド する（ これ に よって Lに 含まれ るすべ ての
図5 加算器(3) の主経路集合（ タイミング調整済み） Fig. 5 Main path set for adder (3). (after timing
regulation)
経路の順序深度が1増え る ）ことでspiとタイミング 調整済である経路間のタ イミング 衝突が 解消され る． ただし sp1の調整時に観測経路の先頭まで 探索し て もレジ スタが 存在し ないことがある．この場合，経路 集合に 含まれ る制御経路が1本であれば ，制御経路を 終点から 逆方向に 探索し て 最初に 現れ るレジ スタをr とする．経路集合に含まれ る制御経路が2本であれば ， 制御林に 含まれないM 上の 辺の始点を終点にもつ制 御経路clが 存在するので ，そちらを 終点から 逆方向 に探索し ，最初に 現れ るレジ スタを rとする．この場 合，rのホールド で順序深度が 増える経路はclのみで あるので ，clの順序深度がL
⋆
に含まれ るど の経路と も異なるよ うな最小の回数だけホールド する．
タ イ ミ ン グ 調 整 手 続 き は 経 路 集 合 上 の 辺 集 合 J = (j0, · · · , ji) の 各 要 素ご と に ，対 応 す る 補 助 経 路と 既に タ イミング 調 整 済みの 経 路と の 間で タ イミ ング 衝突が 起きるかど うかを判定し ，もし 衝突が 起こ るのであれば ，それ を解消する．Jの要素数はたかだ かnであり，各要素について衝突判定の時間計算量は O(n)である ．し たが ってタ イミング 調整手続きの 時
間計算量はO(n2)となる．図5に 図4をタ イミング 調整し た もの を 示す．Spath1とCpath1に よって 生 じ るタ イミング 衝突がOpath上のレ ジ スタ4をホ ー ルド することによって解消されている．
（3）テ ストプ ラン の生成 タ イミング 調整済みの 主経路集合と（ もし あれば ）副経路集合からテストプ ラン を作成する．経路集合において ，観測経路の終点
（M が 観測モジュールの場合はM）から経路を逆にた ど った際のレジ スタ数を各回路要素に 与え る．与えら れた順序深度が 大きいものから 順に3.4で 述べた 制御 信号を与え ることでテ ストプ ランが 生成できる．表1 に 図5に対応するテ ストプ ラン を示す．
表1 テストプラン Table 1 Testplan.
時刻 1
回路要素 1 3 4
制御入力 （ ベクタ入力 ） T HRU ロード
時刻 2
回路要素 1 3 4
制御入力 （ ベクタ入力 ） （ テスト ベクタ ） ロード
時刻 3
回路要素 1 2 4
制御入力 （ ベクタ入力 ） ロード ホールド
時刻 4
回路要素 5 6
制御入力 T HRU⋆ （ ベクタ観測 ）
表2 データパスの特性 Table 2 Character of circuits.
GCD 4thIIR Paulin
入力数 2 1 2
出力数 1 1 2
レジ スタ数 3 12 7
MUX 数 3 3 8
演算モジュール 数 2 5 7
観測モジュール 数 3 0 0
5. 実 験 結 果
完全故障検出効率を保証するテスト 容易化設計法と して，提案方式と完全スキャンを，実験によって比較し た．3種類のデ ータパス「GCD」「，4thIIR」「，Paulin」 に 対し て ，テスト 生成時間，テスト 容易化設計に 基づ くオーバヘッド ，テ スト 系列長の3項目をデ ータパス のビ ット 幅を8，16，32ビット と変化させて評価した． 表2に 各デ ータパスの特性を示す．
［ テスト 生成時間 ］完全スキャン（ 以下FS）でははじ めにデ ータパス上の全レジ スタを外部入出力で置き換 えた組合せ回路から 論理合成ツールを用いてゲートレ ベル 回路を得た．次にゲ ートレ ベル 回路に 対し てテ ス ト 生成ツールを用いて 組合せテ スト 生成を行いテ スト ベクタを 得た．テスト 生成に 要し た時間を完全スキャ ンのテ スト 生成時間(TF S)とし た．
提案方式（ 以下ST）では ，はじ めにレジ スタ転 送 レ ベル 回路に対し てテ スト 容易化設計とテ ストプ ラン の生成を行い，要し た時間を T1とし た ．ここで マル チプレ クサ（ 以下MUX）と演算/観測モジュールをテ ストプ ラン 生成の対象とし た．次に 論理合成ツールを 用いてMUXと演算モジュール（ テスト 容易化設計済 みの もの ），観測モジ ュールご とにゲ ートレ ベル 回路 を得た後，個々のゲ ートレ ベル 回路に 対し てテスト 生 成ツールを用いて 組合せテ スト 生成を行いテ ストベク
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
タを 得た ．各ゲ ートレ ベル 回路のテ スト 生成に要し た 時間をT2 とし ，提案方式のテ スト 生成時間TST を T1+T2 とし た ．
な お ，論 理 合 成 ツ ー ル と して Autologic II
（Mentor Graphics），テ ス ト 生 成 ツ ー ル と し て TestGen（Sunrise）を用い，SUN SPARCstation 20
（SuperSPARC 75 MHz）相当の 計算機上で 実行し た
（ 以下の実験も同じ ）．結果を表3に 示す．
大規模な回路において 提案方式のテ スト 生成時間は 完全スキャンよりも小さい ．これはテ スト 生成を回路 全体に 対し てではなく回路要素ご とに 行うことで ，テ スト 生成ツールが 取り扱 う回路の規模が 小さくなるこ とが 原因であると思われ る．よってこの傾向はデ ータ パスの大規模化とともに より顕著になると思われ る．
［ テスト 系列長 ］ テ スト 生成で 得られ るテ ストベクタ と テ ストプ ラン か ら 以 下の 方 法で テ スト 系 列 長を 求 めた ．ここでテスト 系列長とは 全テ ストベクタの入力 と ，その応答の観測に 必要なクロック数である．結果 を表4に示す．
• 提案方式（ST）
（ 回路要素のテ スト ベクタ数× 回路要素のテ ストプ ラ ン 長 ）の全テスト 対象回路要素に 対する和
• 完全スキャン（FS）
（ テ スト ベ ク タ数 ）×（ スキャン パ ス長 + 1）+（ ス キャン パス長 ）
ただし ，（ スキャンパス長 ）=（ フリップ フロップ 数 ） 完全スキャン 方式と提案方式のテ スト 系列長の差は デ ータパ スのビ ット 幅の増加に 伴って急速に 広が って いる．よって，提案方式が 大規模なデ ータパ スでのテ スト 実行時間を大幅に 削減することがわか る．
表3 テスト生成時間（ 単位：秒） Table 3 Test generation time. (sec.)
GCD 4thIIR Paulin T1= 0.2 T1= 0.2 T1= 0.2 bit TST TF S TST TF S TST TF S
8 1.1 0.5 0.8 0.7 1.2 1.4 16 1.6 1.7 1.3 2.2 2.8 4.5 32 5.8 7.5 14.2 33.7 11.3 18.2
表4 テスト系列長（ 単位：クロック） Table 4 Test sequence length. (clocks)
GCD 4thIIR Paulin
bit ST FS ST FS ST FS
8 254 1299 852 2715 1137 2792 16 470 5732 1392 8105 1503 8587 32 760 22794 2600 71224 2512 24524
［ ハ ード ウェア オ ーバ ヘッド ］ テ スト 容 易 化 設 計 前
（org.），完全スキャン 設計（FS）後，提案方式による テスト 容易化設計（ST）後の回路を論理合成し ，ゲー ト 数を比較し た．ここで ，レジ スタにホールド 機能を 与え るために1 bit当り3ゲ ート，スキャン 機能を 与 え るために3ゲ ート，ホールド 機能と スキャン 機能を 同時に与えるために4ゲート を要し た ．結果を表5に 示す．ただし ，表中の%OHの項は 次のとおり．
DFT後のゲ ート 数−DFT前のゲ ート 数
DFT前のゲ ート 数 ×100(%)
提 案 方 式は 完 全 スキャン 方 式に 比べて 小さい ハ ード ウェアオーバヘッド で 完全故障検出効率を保証し てい る．4thIIRに対する提案方式でのオーバヘッド が他の 回路に 対する提案手法のそれに 比べて大きい．これは 4thIIRに含まれ る定数乗算器（1入力1出力の演算モ
ジュール ）の入出力間において マスク素子と制御入力 の制御だけでは 全単射が 実現できないために ，乗ず る 定数とし て設計値のほかに定数1を選択できるように し て入出力間で 全単射が 実現できるように機能を拡張 し たためである．
提案方式では 演算モジュールの入出力間で 全単射が 実現できることを前提とし ているが ，実際の回路では 定数乗算器やシフタなど がこの前提を満たさない．こ の場合入出力間で 全単射が 成り立つよ うに回路要素の 機能を拡張することで提案手法が 適用できる．4thIIR では5個の演算モジュールの うち3個が 定数演算器で あり，すべての定数乗算器に 対し て全単射が 実現でき るように機能の 拡張を 行った ．実験結果は 完全スキャ
表5 ハード ウェアオーバヘッド Table 5 Hardware overheads.
GCD
org. ST FS
bit #FF #gate #gate %OH #gate %OH 8 24 259 267 3.1 283 9.3 16 48 529 545 3.0 677 28.0 32 96 873 905 3.7 1161 33.0
4thIIR
org. ST FS
bit #FF #gate #gate %OH #gate %OH 8 96 350 510 45.7 636 81.7 16 192 1192 1512 26.8 1768 48.3 32 384 4316 4641 7.5 5468 26.7
Paulin
org. ST FS
bit #FF #gate #gate %OH #gate %OH 8 56 1152 1184 2.8 1240 7.6 16 112 3848 3912 1.7 4042 5.0 32 224 13848 13976 0.9 14200 2.5
ン と 比 較し た 場 合 ，提 案 方 式の ハ ード ウェア オ ーバ ヘッド はこのよ うな機能の拡張を行っても十分小さい ことを示唆し ている．
6. む す び
本論文では ，与えられたレジ スタ転送レ ベルデ ータ パ スに 対し て ，完全 故 障 検 出 効 率を 保 証す るテ スト 容易化設計法，及び ，テ スト 容易化設計法を適用し た デ ータパ ス上の回路要素に 対するテ ストプ ラン 生成法 を示し た ．また，完全故障検出効率を保証するテスト 容易化設計法とし て完全スキャンと提案方式の比較実 験を3種類の回路に 対し て行うことで ，ハード ウェア オーバヘッド ，テ スト 生成時間，テスト 系列長の3点 で ，特に 大規模な回路において提案方式が 完全スキャ ン 方式より優れていることを示し た ．
今後の課題とし ては ，デ ータパスに対する条件の緩 和が 挙げ られ る ．具体的には ，1）異な るビ ット 幅を もつデ ータ信号線の混在する場合，2）3個以上のデ ー タ入力端子や2個以上のデ ータ出力端子をもつ回路要 素が 存在する場合，にも適用できるようにアルゴ リズ ムを拡張することを考えている．
謝辞 本研究に 際し ，多くの貴重な意見をいただ い た本学の情報論理学講座の諸氏に深く感謝し ます．本研 究は一部，（ 株 ）半導体理工学研究センター（STARC） との共同研究，及び ，文部省科学技術研究費補助金・基 盤研究B(2)（ 課題番号09480054）の研究助成による．
文 献
[1] H. Fujiwara, “Logic testing and design for testabil- ity,” The MIT press, Cambridge, 1985.
[2] J. Lee and J.H. Patel, “Hierarchical test genera- tion under architectural level functional constraints,” IEEE Trans. on CAD, vol.15, no.9, pp.1144–1151, Sept. 1996.
[3] R.B. Norwood and E.J. McCluskey, “Orthogonal scan: Low overhead scan for data paths,” Proc. 1996 Int. Test Conf., pp.659–668, 1996.
[4] R.B. Norwood and E.J. McCluskey, “High-level syn- thesis for orthogonal scan,” Proc. 15th VLSI Test Symp., pp.370–375, 1997.
[5] S. Bhatia and N.K. Jha, “Genesis: A behavioral synthesis system for hierarchical testability,” Proc. European Design and Test Conference, pp.272–276, 1994.
[6] I. Ghosh, A. Raghunath, and N.K. Jha, “Design for hierarchical testability of RTL circuits obtained by behavioral synthesis,” Proc. 1995 IEEE Int. Conf. on Computer Design, pp.173–179, 1995.
[7] I. Ghosh, A. Raghunath, and N.K. Jha, “A design
for testability techinique for RTL circuits using con- trol/dataflow extraction,” Proc. 1996 IEEE/ACM Int. Conf. on CAD, pp.329–336, 1996.
（ 平成10 年 10 月 14 日受付，11 年 2 月 5 日再受付）
和田 弘樹 （ 学生員 ）
平8 阪大・工・通信卒．平 10 奈良先端 科学技術大学院大学博士前期課程了．現在 奈良先端科学技術大学院大学博士後期課程 に 在学中．現在テスト 容易化設計の研究に 従事．
増澤 利光 （ 正員 ）
昭57 阪大・基礎工・情報卒．昭 62 同大 大学院博士後期課程了．同年同大情報処理 教育セン ター助手．同大基礎工助教授を経 て ，平6 奈良先端科学技術大学院大学情報 科学研究科助教授，現在に 至る．平5 コー ネル大客員準教授（ 文部省在外研究員 ）．分 散アルゴ リズム，並列アルゴ リズム，テスト 容易化設計，テス ト 容易化高位合成に 関する研究に 従事．工博．ACM，IEEE， EATCS，情報処理学会各会員．
Kewal K. Saluja
ル ーキ ー 大 学（ インド ）電気 工学 科卒 ． 1973 ア イオワ大電気計算機工学科博士後 期課程了．現在，ウィスコンシン大（ マデ ィ ソン ）電気計算機工学科教授．南カリフォ ル ニア 大 ，ア イオ ワ 大 ，ル ーキ ー 大 ，広 大，奈良先端大など で客員教授．テスト 生 成，テスト 容易化設計，フォールトトレ ラント 計算，VLSI 設 計，計算機アーキ テクチャなど の研究に 従事．工博．Journal of Electronic Testing: Theory and Applications (JETTA) Associate Editor.
藤原 秀雄 （ 正員 ）
昭44 阪大・工・電子卒．昭 46 同大大学 院博士後期課程了．阪大工学部助手，明治 大理工学部教授を経て，現在奈良先端科学 技術大学院大学情報科学研究科教授．昭56 ウォータール ー 大 客員助教授．昭59 マッ ギル大客員準教授．論理設計，高信頼設計， 設計自動化，テスト 容易化設計，テスト 生成，並列処理，計算 複雑度に 関する研究に 従事．著書“Logic Testing and Design for Testability”（ The MIT Press）など ．大川出版賞．工博． IEEE，情報処理学会各会員，IEEE Fellow，IEEE Golden Core Member.
