階層 BIST ：低いオーバヘッド を 実現する Test-per-clock 方式 BIST
山口 賢一
†∗井上美智子
†藤原 秀雄
†Hierarchical BIST: Test-Per-Clock Scheme BIST with Low Overhead
Kenichi YAMAGUCHI†∗, Michiko INOUE†, and Hideo FUJIWARA†あらまし レジ スタ転送レベル（RTL）回路に対する階層組込み自己テスト（ BIST）のためのテスト容易化設 計法を提案する．階層BIST とは，RTL 回路に対する BIST を RTL とゲートレベルの二つの階層で行う BIST を総称する概念である．RTL においては，テスト対象モジュールに対して，テストパターン発生器で発生したパ ターンを印加し ，応答解析器で観測するための経路を生成する．ゲ ートレ ベルでは ，テ スト 対象モジュールに 対 し て故障シ ミュレ ーションによる故障検出率の評価を行う．階層BIST に基づく手法の利点は，高い故障検出率， 小さいハード ウェアオーバヘッド を達成できることである．本論文では ，階層BIST のための可検査性として新 たに 時分割単一制御可検査性を提案し ，テ スト 実行時間とハード ウェアオーバヘッド の削減を行い，実験により 提案手法の有効性を示す．
キーワード テスト 容易化設計，レジ スタ転送レ ベル ，組込み自己テスト，単一制御並行可検査性
1. ま え が き
VLSIの 大規模複雑化に 伴い，テ ストデ ータ量やテ スト 時間の増大化が 問題となっている．これらの問題 を解決する方法として，組込み自己テスト法（Built-In Self-Test：BIST）が 重要視され ている．
BISTは ，test-per-scan方式とtest-per-clock方式 に 分類で きる．test-per-scan方式[1]は ，ハード ウェ アオーバヘッド が 小さいが ，スキャン 操作を行うため， 連 続し た シ ステ ム ク ロックで テ スト 系 列を 印 加で き ず，テ スト 実行時間も長 くな る ．test-per-clock方式 は ，テ スト 実行時間が 短く，テ スト パターンの連続印 加を必要とする遅延故障など のテ ストにも適用可能で ある．この方式では ，Wunderlichら[2]が ，回路中の すべ ての 閉 路が 少な くと も 二つのBILBO [3]か 一つ のCBILBO [4]を含むようにするテスト 容易化設計法
（Desing for Testability. DFT）を 提 案し て い るが ， ハード ウェアオーバヘッド が 大きくなる．
筆 者ら はレ ジ ス タ 転 送レ ベル（Register Transfer Level：RTL）デ ータパ スに 対し て 単一制御可検査性
†奈良先端科学技術大学院大学情報科学研究科，生駒市
Graduate School of Information of Science, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma-shi, 630–0192 Japan
∗現在，奈良工業高等専門学校情報工学科
（Single-Control testability）に基づく手法（SC法 ）[5] や単一制御並行可検査性（Concurrent Single-Control testability）に 基づ く手法（CSC法 ）[6]を 提案し た ． SC法 ，CSC法 及び 本 論 文で 提 案 す る 手 法は ，階 層 BISTを 実 現す る 具 体 的な 方 法で あ る ．RTL回 路の テ スト 生成に おいては ，RTLとゲ ートレ ベル の 二つ の階層を利用する階層テスト 生成[7]がある．同様に ， BIST方式においてもRTLとゲートレベルの二つの階 層を利用し た階層BISTが 考えられ る．階層BISTで はテ スト パターン 発生器（Test Pattern Generator： TPG）で 発 生し たパ タ ーン を テ スト 対 象モジュール に 対し て 印 加し ，その 応答を 応答 解析 器（Response Analyzer：RA）で観測するための経路の生成をRTL で 行う．ゲ ートレ ベルでは ，テスト 対象モジュールに 対し て故障シ ミュレ ーションを行い故障検出率を評価 する．SC法やCSC法は ，故障検出率が 高く，Wun- derlichらの手法[2]に 比べハード ウェアオーバヘッド は 小さい ．SC法では 組合せ 回路要素を 一つず つテ ス ト するためにテスト 実行時間が 大きくなるため ，CSC 法では ，同時に 複数の組合せ回路要素をテスト 可能に し た ．し かし ，CSC法で は テ スト スケジ ュー リング をハード ウェアオーバヘッド に 基づいて 行うため ，テ スト 実行時間がSC法と 比較し て 改善され ない場合も あった．
D– Vol. J86–D– No. 7 pp. 469–479 2003 7 469
本論文では，SC法やCSC法と同等の故障検出率で， ハード ウェアオーバヘッド とテ スト 実行時間を削減す るた めにデ ータ パ スに 対し て 時 分 割 単 一 制 御 並 行 可 検 査 性（Time Division Concurrent Single-Control Testability）を提案する．この可検査性では ，テ スト パターンの印加と応答の解析のために 用いる経路の条 件を緩和し ，ハード ウェアオーバヘッド の削減を行う． この可検査性に基づくテスト容易化設計法（TCSC法） では ，各組合せ回路要素単体でのテ スト 実行時間に 基 づきテスト スケジ ューリング を行い，テスト 実行時間 を短縮する．デ ータパスの時分割単一制御並行可検査 性を実現するためのアーキテクチャを提案し ，RTL全 体のBIST法も提案する．
2. レジ スタ転送レ ベル回路
本論文で 対象とするRTL回路は ，コント ローラと デ ータパ スから 構成され る（ 図1）
（ 注 1 ）
．コント ローラ は 有限状態機械，デ ータパスは回路要素と回路要素を 接続する信号線で 記述され る．回路要素は ，PI，PO， ラッチ，レジ スタ，マルチプレ クサ，演算モジ ュール ， 観測モジ ュールに 分類され る．この うち，マルチプレ クサ，演算モジ ュール ，観測モジ ュールを組合せ回路 要素と呼ぶ．各回路要素は 端子をもち，それぞれデ ー タ端子，制御端子，観測端子に 分類され る．デ ータ端 子には ，回路要素にデ ータを 入力する入力端子と回路 要素からデ ータを 出力する出力端子がある．制御端子 は ，コント ロー ラか ら 制 御 信 号を 入 力す る 端 子で あ る．観測端子は ，コント ローラへ ステータス信号を出 力する端子である．信号線は ，デ ータ信号線，制御信 号線，ステータス信号線に 分類され る．デ ータ信号線 は ，二つの回路要素のデ ータ端子を接続する．制御信 号線は ，コント ローラと 制御端子を接続する．ステー タ ス信号線は ，観測端子とコント ローラを 接続する ．
図1 レジスタ転送レベル回路 Fig. 1 Resister transfer level circuit.
本論文で 扱うデ ータパスは ，各回路要素のデ ータ端子 のビ ット 幅が すべて等し く，観測モジ ュール 以外のす べての回路要素は1または2個の入力端子，1個の出 力端子 ，たかだか1個の制 御端子と 観測端子をもち ， 観測モジ ュールは1または2個の入力端子，たかだか 1個の制御端子と観測端子をもつ ．また ，すべての 入 力端子は ，少なくとも一つのPIから 到達可能であり， すべての出力端子は 少なくとも一つのPOに 到達可能 である．
3. 階層 BIST
階層BISTは ，RTLとゲ ート レ ベル の 二つの 階層 を利用するBIST方式である．RTLではテスト 対象と な るモジ ュールに 対し て ，TPGから 発生し たテ スト パターン を組合せ回路要素に 印加し ，その応答をRA で 観測するための経路を生成する．このとき，対象と する故障はゲ ートレ ベルなので ，テ スト 対象モジ ュー ルに対し てゲ ートレ ベルで 故障シ ミュレ ーシ ョンを行 い故障検出率を評価する．
本論文では，RTLにおけるテスト 容易化設計法を提 案する．ゲ ートレ ベルに 対し ては ，テストポ イント 挿 入[10]など の既存の手法を用いて ，組合せ回路要素単 体に対し ては十分な故障検出率が 得られ るものとする． これらの手法では ，デ ータパスに対し てはテ ストプ ラ ンを生成する．テ ストプ ラン とは ，ゲートレ ベルの故 障シミュレ ーシ ョンで与えたパターンと同じ パターン を与え るために ，デ ータパス中の各組合せ回路要素に 対し て ，TPGからのテスト パターン の 伝搬とRAで の応答の観測のために与え る制御信号線上の信号の時 系列である．また ，コント ローラに 対し ては ，本論文 では 状態レジ スタをCBILBOに 置き換え ることに よ り階層BISTを実現する．
4. 提案手法のア イデア
TCSC法では ，SC法やCSC法と 異な る新し いア イデアを導入する．
4. 1 制御経路と観測経路
TCSC法で は ，SC法やCSC法と 同 様 ，TPGと RAをPI，PO及び 制御入力（CI）に のみ 付加する ． テ スト 対象組合せ 回路Mに 対し て ，TPGからMの
（ 注1）：RTLを人手で 設計する場合，デ ータパスとコント ローラに 分離 できな い場合が ある ．し かし 通常のRTL回路は ，デ ータパ スとコント ローラに 分離し て 構成する[8]．例えば ，高位合成では ，デ ータパスとコ ント ローラを 分離し たRTL回路を出力する．
図2 制御経路と観測経路のタ イプ Fig. 2 Type of control and observation paths.
入力端子への制御経路とMの 出力端子からRAまで の観測経路を単一の制御信号からなるテストプ ランで 実現する経路とし て，type1に加え ，type2，type3の 経路も新たに 考え る（ 図2）．三つの タ イプ の 経路に よって ，各組合せ 回路要素の異な る入力端子にTPG で 発生し た異なるテ スト パターン を印加することが 可 能となる．TCSC法では ，三つのタ イプ の経路を利用 し て，type1のみ利用するSC法，CSC法に 比べ付加 するDFT要素を削減する．
• type1：Mの 制御経路と観測経路は 互いに 共通 部分をもたない．
• type2：Mの 異な る入力端子は 同じTPGを始 点とする異な る順序深度（ 制御経路上のレジ スタ数 ） の 制御経路をも ち，か つMの 観測経路は 制御経路と 共通部分をもたない．
• type3：Mの 一方の 入力端子i1 の 制御経路は ，
Mの他方の 入力端子i2 への制御経路とi2 からMの 出力端子への経路を通り，i2は スルー機能を有する． type1，type2，type3の経路を用いて 実用時間内でテ ストが 可能かを確かめるために 各タ イプでの故障検出 率，パターン 数を調べた ．表1に 示す組合せ回路要素 に対し て，デ ータ入力（DIN）には32 bitのLFSRを 利用し てパターンを与え ，制御入力（CIN）には8 bit のLFSRの 上 位bitから パタ ーン を 与え た ．異な る LFSRの特性多項式は異なるように設定し ，各LFSR に対し て任意に選んだ五つのseed，特性多項式を用い て故障シ ミュレ ーシ ョンを行い，検出可能故障に 対し て 故障検出率100%を 達成する平均パターン 数とその 標準偏差を 求め た（ 表2）．ただし ，すべ ての 入力端 子に ，TPGで 生成され たパ ターンが 印加され た 時点 より計測を行った ．表2より，必要となるパターン 数
（#P）は ，type1，type2，type3の順に小さいが ，ど のタ イプ でも実用時間内でテ ストが 可能である．また 標準偏差（SD）も必要となるパターン 数に比べて小さ
表1 組合せ回路特性
Table 1 Characteristics of combinational ciruits.
DIN DOUT CIN
組合せ回路 #DIN #DOUT #CIN bit 幅
MUX 2 1 1 1
加算器 2 1 1 2
減算器 2 1 1 2
乗算器 2 1 1 2
AND 2 1 1 2
OR 2 1 1 2
表2 パターン数と標準偏差 Table 2 Number of patterns and standard
deviations.
type1 type2 type3
組合せ回路 #P SD #P SD # P SD
MUX 27 3.24 32 2.73 74 1.41 加算器 123 4.85 185 10.15 215 16.64 減算器 167 8.25 298 5.52 325 11.68 乗算器 680 14.20 902 12.63 1870 12.86 AND 100 1.22 158 5.10 198 7.52 OR 102 1.58 162 4.70 201 5.48
表3 テストスケジューリング例 Table 3 Example of test scheduling.
TCSC 法 CSC 法 [6]
セッション 要素1 要素2 #P 要素1 要素2 #P
1 MULT M1 27 MULT M1 680
2 MULT M2 32 M2 M3 27
3 MULT M3 74 ADD — 123
4 MULT ADD 123
5 MULT — 424
合計 680 826
いため ，TPGのseedや特性多項式が 異なっても必要 となるパターン 数が 大幅に 増加し ない．
4. 2 テスト スケジ ューリング
TCSC法で は ，複数の 組 合せ 回 路 要 素を 同 時に テ スト する．そのため ，同時にテ スト する組合せ回路要 素の集合（ テ ストセッション ）を決定するテ スト スケ ジューリングが 必要となる．TCSC法では ，一つの組 合せ回路要素を複数のセッションでテスト することに よってテスト 実行時間を削減する．
[例1] 表1に示す平均パターン 数で各組合せ回路要素 が テ スト で き ，一つの 乗算器MULTと 加算器ADD, 三つのMUX M1，M2，M3をたかだか 二つず つテ ス ト する場 合のテ スト スケジ ュー リング を 表3に 示す． TCSC法において ，各セッションはそのセッション 中 の少なくとも一つの 回路要素に 十分なテスト パターン 数が 与えられれば 終了する ．セッション1では ，M1 に十分なテストパターン 数が 与えられ ，MULTはセッ ション2以降でもテスト 対象となっている．CSC法で
は ，各セッション 中のすべての組合せ回路要素に 十分
なパターンを必要とする． ✷
5. 時分割単一制御並行可検査性
5. 1 データパ スグ ラフ
デ ータパ スに 対し てデ ータパ スグ ラフ G= (V, A) を次の有向グ ラフとし て定義する．
• V = V1∪ V2
ここでV1はすべての回路要素の集合，V2はすべて のデ ータ端子の集合とする．
• 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の出力端子}とする． 図3 (a)のデ ータパ スに 対するデ ータパ スグ ラフを 図 3 (b)に示す．また，デ ータパスグラフはその対応する デ ータパスと同一視する．
デ ータパ スグ ラフ G= (V, A)に対し ，スルー制約 付デ ータパス部分グ ラフG′= (V, A′(⊂
=A))を定義す る．ここで ，A′= A1∪ A′2∪ A3 であり，A′2 は ，ス ルー機能を有する組合せ回路要素の入力端子と回路要 素，若し くはレジ スタ及び ラッチの入力端子と回路要 素への対応を表す．スルー機能は ，演算モジュールに おいて入力端子と出力端子の間での任意の値の伝搬を 保証する機能である．
5. 2 時分割単一制御並行可検査性
階層BISTとし てtype1，type2，type3を考慮し た
(a) Data path (b) Data path digraph 図3 データパスとデータパスグラフ Fig. 3 A data path and its data path digraph.
時分割単一制御並行可検査性を以下のように定義する． [定義1] スルー制約付デ ータパス部分グ ラフG′にお いて，テ ストセッションMが ，以下の条件を満たす とき，Mは 時分割単一制御並行可検査であるという．
• 以下の条件を満たす互いに 共通部分をもたない 木T1, T2,. . . , Ti,. . . , Tmが 存在．
– 各木の根はPIである．
– Mに 属する各組合せ 回路要素の 各入力端子は いずれかの木に 属する．
– Mに 属する各組合せ 回路要素の 異な る入力端 子は ，異なる木に 属する，または 根からの順序深度が 異なる．
• T1, T2,. . . , Ti,. . . , Tmに 現れ るG′の入次数2 以上の端子に対し ，Tiに現れ る入力辺以外の入力辺及 び その入力辺にのみ到達可能な辺をG′から 消去し た グ ラフに おいて ，以下の条件を満たす互いに 共通部分 をもたない経路P1, P2,. . . , Pnが 存在．
– 各Piの 始点は Mに 含まれ る各組合せ 回路要 素の出力端子であり，終点はPOである． ✷
テストセッション Mが 時分割単一制御並行可検査 なら ，TPG，RAをPI，PO，CIに 配置し ，type1， type2，type3の制御経路，観測経路を用いることによ り，Mに 属するすべての組合せ 回路要素を 同時にテ ストできる．このテ ストの間，制御経路及び 観測経路 に 現れ る制御信号（ テストプ ラン ）を固定し ておくこ とができる．つまり，一つのテ スト セッション Mに 対し て ，一つの 制御パターン を 与えれば ，連続クロッ クでテ スト 系列の 印加/応答の観 測が 可能とな る．次 に ，同時に テ スト す る組 合せ 回路要素の 数を k 個と し たときのデ ータパ スの可検査性を以下のよ うに定義 する．
[定義2]（ デ ータパ スの時分割単一制御k-並行可検査 性 ）以下の 条件を 満た す場合 ，デ ータパ スは 時分割 単一制御k-並行可検査であると定義する．
• 各テ ストセッションが 時分割単一制御並行可検 査である．
• 各テ スト セッション の 要素 数は たか だ か kで ある．
• 各組合せ回路要素は，少なくとも一つのセッショ
ンに含まれ る． ✷
時分割単一制御k-並行可検査性では ，各組合せ回路 要素は 複数のテ スト セッションに 属することが 可能で ある．以下では ，kの値を特に 指定し ないときは ，時 分割単一制御k-並行可検査性のことを時分割単一制御
並行可検査性と呼ぶ ．
6. 時分割単一制御並行可検査性を実現する
ためのテスト 容易化設計法
与えられたデ ータパスを時分割単一制御並行可検査 デ ータパスに設計変更するためDFTを示す．
6. 1 問題の定式化
時 分 割 単 一 制 御 並 行 可 検 査 性を 実 現す るの た めの DFTを ，次の最適化問題とし て定式化する． [定義3]（ 時分割単一制御並行可検査DFT）
• 入力：データパス，並行度k，テストライブ ラリ
• 出力：時分割単一制御k-並行可検査なデ ータパ ス，各テストセッション 及び セッション 長，テ ストプ ラン
• 最 適 化 目 標：ハード ウェア オー バ ヘッド 最 小 ，
テ スト 実行時間最小 ✷
デ ータパスのDFT要素は ，新し い経路を 付加する ためのMUX（TMUXと呼ぶ ），スルー機能を考える． また ，テスト ラ イブ ラリは各組合せ回路要素に 対する 目標故障検出率を達成するために 必要となる各タ イプ の経路に対する平均テストパターン 数の見積りである． セッション 長は ，各テストセッションに要するテ スト 実行時間である．
6. 2 DFTアルゴ リズ ムの概要
単一制御並行可検査DFTのための発見的アルゴ リ ズ ムを 示す．本アルゴ リズ ムは ，以 下の3段 階か ら なる．
ステージ1 カット エッジ 除去：テ スト スケジ ューリ ングにかかわらず 時分割単一制御並行可検査性を満た さない組合せ回路要素に 対し てDFTを行う． ステージ2 テストセッションごとのテストスケジュー リング，観測経 路及び 制 御経路のた めのDFT：以下 の ，（1）から（4）を各組合せ回路要素に 十分な個数 のパターンが 印加され るまで 繰り返す．
（1）テ スト スケジューリング ：テ ストセッション Mを決定する．
（2）観測DFT：Mに 対する観測経路を求める．
（3）制御DFT：Mに 対する制御経路を求める．
（4）セッション 長決 定：Mの セッション 長を 求 める．
ステージ3 制御経路とセッション 長の再決定 6. 3 カット エッジ 除去
必要性の 高いDFT要素を早い段階で 付加するため に ，スケジ ューリングにかかわらず 時分割単一制御並
行 可 検 査 性を 満た さな いよ うな 組 合せ 回 路 要 素に 対 し て，以下に 定義するカット エッジに基づいた 処理を
行う．
[定義4] デ ータパスグ ラフGに 対し て ，回路要素と 出力端子を接続する辺eを取り除いて得られ るグ ラフ をG′(e)と 表す．G′(e)に おいてど のPIから も到達 不能であり，かつど のPOへも到達不能である組合せ 回路要素M が 存在する場合，eを カット エッジ と 呼 び ，M はeによって支配され るとい う． ✷
eによって支配され る組合せ回路要素はテスト スケ ジューリングにかかわらず，時分割単一制御並行可検 査性を満たすことができない．eを除去するために ，e によって支配され る組合せ回路要素の入力に 任意の順 序でTMUXを 付加し ，eに 到達不能なPIが 存在す る場合はそのPIから ，なければ 任意のPIとTMUX を接続する．これをeが カット エッジでなくなるまで 繰り返す．一つのTMUXを 加え ることにより，複数 の カット エッジ を 除去で き る可能 性が あ る ．そこ で ， カットエッジに 対し て次の半順序関係を定義し ，その 半順序に 従ってカットエッジを処理する．
[定義5] データパスグラフGにおけるカットエッジe に対して，eによって支配され るすべての組合せ回路要 素をD(e)と表す．e及び e′において，D(e)⊂
=D(e′) のとき，またそのときに 限り，e <= e′とする． ✷
もし ，二つの カット エッジ e1 とe2が e1 <= e2 を 満たすなら ，e1 のために 加えられ るMUXに よって ， e2が カット エッジでなくなることがある．
[例2] 図4 (a)では，e1とe2が カットエッジであり， D(e1) = {M3}，D(e2) = {M1, M 3}であ る．し た が って ，e1 <= e2とな り，まず，e1 に 対し て カット
(a) Before adding TMUX (b) After adding TMUX for e1
図4 カットエッジ 処理例
Fig. 4 Example of adding TMUX for cut edge.
エッジ 除 去を 行 う．M3 ∈ D(e1)の 左 入 力の 直 前に TMUX M 4を付加し ，M4の他方の入力をPI2に 接 続する．付加し た後のグ ラフ（ 図4 (b)）において ，e1 だ け で な く e2も カット エッジ で は な くなって い る ．
✷ 6. 4 テスト スケジ ューリング 及び 観測DFT 一 つの テ スト セッション Mの 決 定（ テ スト ス ケ ジューリング ），Mに対する観測経路を同時に求める． 観測経路を制御経路より先に 求めるのは ，制御経路は 異なる組合せ回路要素で 共有可能だが ，観測経路は 共 有不能であり，可観測性のためのDFTハード ウェア オーバヘッド が 支配的になるためである．
組合せ回路要素に 対し て ，既に 目標となる故障検出 率を達成するパターン 数が 印加され ているものを スケ ジューリング 済み，そうでないものを未スケジ ューリ ングであるという（ 詳細は6.6）．
PO，観測端子，または スケジューリング 済みの組合 せ回路要素に 隣接するすべての未スケジューリング 組 合せ回路要素を候補とし て ，テストセッションM及 びMに含まれ る組合せ回路要素の観測経路を求める．
観測経路は ，デ ータパス中の経路，または 組合せ回路 要素Mの 出 力をTMUXを 用いて 直接POに 接続す る経路を 用いて 構成する．ただし ，MUXの観測経路 のためにはTMUXに よる経路は 付加し ない
（ 注 2 ）
．そ れぞれの経路に 要するハード ウェアオーバヘッド をコ スト とし て与え ，流量k（ ただし ，候補数がm(< k) 個なら流量m）の最小費用流問題を用いて観測経路を 求め る．デ ータパ スグ ラフGから 以下の よ うに 最小 費用流問題の入力となるグ ラフを構成する．
• 各候補組合せ回路要素への辺をもつダ ミー頂点 を付加し 始点とし ，各PO及び 観測端子からの辺をも つダ ミー頂点を付加し 終点とする．
• MUX以外の 各候補組合せ 回路要素Mに 対し ， Mの 出 力端子か ら 各POへ 辺を 付加す る ．この 辺は TMUXの付加を 表す．ただし ，直接接続するPO若 し くは観測端子が 存在する場合，そのPOや観測端子 への辺の付加は 行わない．
• 得られ たグ ラフに おけ る各辺(u, v)に 対し て ， 容量を1とする．コ スト p(u, v)を 以下のよ うに 定義 する．
p(u, v) = cost thru(u) uがvの入力端子．
= cost M U X (u, v)はTMUXに 対応．
= 0 上記以外の場合．
図5 テスト スケジ ューリング 例（ k= 2） Fig. 5 Example of test scheduling (k = 2).
（cost thru(u)は uから vの出 力端子への スル ー機 能を付加するための ハード ウェアコ スト．付加済みの 場合は，cost thru(u) = 0．cost M U XはTMUXを 付加するためのハード ウェアコ スト ）
最 小 費 用 流で 求 ま る 経 路は ，最 小の ハード ウェア オーバヘッド で 実現できる観測経路を表す．観測経路 のために ，スルー機能とTMUXが 付加され る． [例3] 図5で ，k= 2でありM1, M 2, M 3, M 4が ス ケジューリング 済みの場合を示す（ 簡単のためにレジ スタを 省略する ）．M5, M 6, M 7が 候補組合せ回路要 素である．MUXでないM5の出力端子から，PO1と PO2へTMUXに対する辺をコストcost M U X(= 6) とし て 付加する ．M2, M 3, M 4の入 力端子と 回路要 素を結ぶ辺の うち，スルー機能をもたない辺がコ スト 3とな る．それ 以外の辺のコ ストは0である．このグ ラフ上で 流量2の最小費用流問題を解くと，図中太線 の経路がコ スト6で 決定され る．このセッションでは M5とM7が 選択され ，経路上の スル ー機能に 対応 する辺であるM1の左入力と M4の左入力に スルー 機能が 付加され ることを意味する． ✷
6. 5 制御DFT
一つのテ スト セッション Mに 対し て ，Mに 含ま れ るすべての 組合せ 回路要素の 制 御経路を 決定する ． この 手続きは ，Mに 含まれ る組合せ 回路要素を 一つ ずつ順に 処理する．また，各回路要素に 対し ては 入力 端子への経路は 一つずつ決める．各回路要素に 対する
（ 注2）：MUXのテ スト にTMUXを付 加すれば ，付加し たTMUXの テストも必要となり，テスト 実行時間を削減させることなく，ハード ウェ アオーバヘッド が 増加し てし まう．
最初のステップ では ，ハード ウェアコ スト 最小となる 制御経路を一つ（ 第1制御経路と呼ぶ ）決定する．次 に ，他方の制御経路（ 第2制御経路と呼ぶ ）を順序深 度を考慮し て決定する．
第1制御経路は ，デ ータパスグ ラフから 次に示すよ うなグ ラフを構成し ，流量1の最小費用流問題を解く ことで求まる．
• 各PIへの 辺をもつダ ミー頂点を 付加し 始点と し ，対象となる組合せ回路要素Mを終点とする．
• Mに 属する組合せ回 路要素の 決定済みの 制御 経路及び 観測経路上の組合せ回路要素から ，制御経路 と観測経路に属さない辺を削除する．（ 既に 選ばれてい る経路と異なる制御信号を要する経路を選ば ない ）
• 対象要素MがMUX以外の場合，各PIから対 象要素の 入力端 子へTMUXに 対応する 辺を 加え る ． ただし ，Mに 直接接続するPIが 存在する場合，その PIからの辺は 付加し ない．
• 各辺に 対し ，観測経路を求めるときと 同様のコ スト，容量を与え る．
[例4] 図6 (a)で ，M4 の 第1制 御 経 路 の 決 定 例 を 示 す．各 PIか ら 演 算 モ ジュー ル M4 の 各 入 力 端 子へ のTMUXに 対 応 す る 辺を 付 加し ，コ スト を cost M U X(= 6)とする．また，M1, M 3の各入力端 子から 回路要素の辺のコ スト をcost thru(= 3)とす る．このグ ラフ上で流量1の最小費用流問題を解くと， 始点からPI2, M 2, M 3, R2とM4の左入力を通って 終点に至る経路が 選択され る． ✷
第2制御経路も流量1の最小費用流問題を解いて 求 める．ここで 用いるグ ラフは ，第1制御経路のためグ ラフと下記の点を除き同様である．
• 始点，終点以外の端子は ，その端子を通り始点 から 終点に 至る経路の順序深度の種類分複製し ，各端 子に 順序深度を対応づけ る．各経路は ，順序深度に 対 応し た頂点を通るよ うに 接続する．例えば ，始点から 終点までの順序深度がdの経路は ，dに 対応する頂点 を 通る．TMUXに 対応する辺は 順序深度0の 経路と し て考え る．
• TMUXに 対応する辺の うち，第1制御経路で 決定し た入力端子への辺を削除する．
• 終点へ接続する辺のうち，第1制御経路で 利用 し た辺を削除する．
• 始点から，複製されたPI端子への辺の うち，第 1制御経路と 同じPIで 同じ 順序深度の ものを 削除す る．始点から ，PI端子への 辺のコ スト は ，第1制御
(a) DFT for control path of first port
(b) DFT for control path od second port
図6 制御経路の決定 Fig. 6 DFT for control paths.
経路と同じPIであればtype2cost，そうでなければ0 とする．type2costはtype2を用いる場合の時間のコ ストである．
• type3を 表すための辺とし て ，始点から 対象要 素の出力への辺を付加する．この辺は ，始点から 対象 要素までは 第1制御経路を 利用することを 意味する ． この辺のコ ストは ，テスト 対象回路への スルー機能の 付加に対応するcost thruとtype3を用いる場合の時 間のコ ストであるtype3costの和である．
[例5] 図6 (b)は ，M4の第2制御経路の決定例を示 す．始点からM4までの順序深度を考慮し て端子を複 製する．例えば ，PI3に対し ては ，TMUXによる経路
（ 順序深度0）と 順序深度が1の経路が 存在するので ， 二つの端子を用意する．既に 同じ セッションに 対し て 決定し ている制御経路上の組合せ回路要素の制御経路 に 含まれ な い辺で ある M2の右 入力から の辺と M3
の左入力からの辺を削除する．始点からPI2に 対応す る端子へ順序深度1に 対応する端子以外に 接続し ，コ スト をtype2cost(= 1)とする．また ，始点から M4 の 出力への 辺を付加し ，コ スト をtype3cost(= 2)と する．M4の右入力へTMUXに対応する辺を付加し ， コ ストはcost M U X(= 6)とする．このグ ラフ 上で ， 流量1の 最小費用流問題を 解くと ，始点から M4の 出力端子とR3を 通り終 点に 至る経 路が 決定され る ． 結果とし て，M4はtype3の経路を利用し てテストす
る． ✷
最 小 費 用 流 問 題 を 解 く 際 に 与 え る コ スト で あ る type2cost，type3cost，cost thru及びcost M U Xを 調節することで ，得られ るデ ータパ スに対し て時間優 先及び 面積優先を選択することができる．
対象要素がMUXである場合，制御経路を生成する ためにTMUXを付加し ないため制御経路を決定でき ない場合がある．この場合は，MUXをテストセッショ ンMから 削除し ，未スケジ ューリング とする．デ ー タパ ス中のすべての組合せ回路要素は カット エッジ 処 理によってあるテ ストセッションでは 時分割単一制御 並行可検査性を満たすことが 保証できるので ，このよ うなMUXもいずれ スケジ ューリング 済みとなる．
6. 6 セッシ ョン 長決定
セッション 長をテストライブ ラリに基づき決定する． テ ストセッションM∞,M∈,. . . , M∫ −∞が 既に 決定 し ，M∫ のセッション 長を 決定すると す る ．lj (j = 1, 2, . . . , s)をセッション M| のセッション 長とする． M|,∞,M|,∈,M|,∋ を それぞ れ M| に おいてtype1， type2，type3の経路をもつ組合せ回路要素の集合とす る．組合せ回路要素Miに対し ，Ni,1，Ni,2，Ni,3 を それぞれtype1，type2，type3でのMiに要するテス ト パターン 数とする．組合せ 回路要素Mi, p= 1, 2, 3 に 対し ，M,∫√ = {||M ∈ M|.√,∞ <= | <= ∫ }と す る．このとき，
CLi,s=
j∈Mi,s1
lj
Ni,1
+
j∈Mi,s2
lj
Ni,2
+
j∈Mi,s3
lj
Ni,3
を M1,. . . , Ms に おけ る Mi のテ スト パターン 充足 率と呼ぶ ．Miのテ ストパターン 充足率が1になれば ， Miには 十分なパターン 数が 印加され ，スケジューリ ング 済みと 考え る．Ms のセッション 長は ，Msに 属 するある組合せ回路要素が スケジ ューリング 済みとな る最小パターン 数とする．すなわち，Msへのテ スト パターンの印加は 少なくとも一つの 組合せ回路要素が
スケジ ューリング 済みとなる時点までとする． 6. 7 制御経路の再決定とセッシ ョン 長決定 ステージ2では ，テ ストセッションご とに制御経路 及び 観測経路の決定を行った ．し かし 例えば ，あるテ ストセッションでtype2の制御経路をもつ組合せ回路 要素が ，後のテ スト セッションで 付加され たDFT要 素を用いてtype1の制御経路をもつというように ，よ りテ スト 実行時間の 小さい 経路を もつ 可能性が あ る． そこで ，DFT要素が 付加され たデ ータパ スに 対し て 6.5で 示し た 手法を 用いて 再 度制御 経路を 決定す る ． ただし ，この際に 新たにDFT要素に 対応する辺の付 加は行わない．最後に ，各セッションに 対し て故障シ ミュレ ーション を 行い ，各セッション 長を 決 定す る ． ここで ，ある組合せ回路要素の検出率が 所望の値に 達 し ない 場合は ，リシ ーデ ィング[9]やテ スト ポ イント 挿入[10]など を行い所望の検出率を達成できるよ うに するか ，若し くは 与えるパターン 数に上限を与えてテ ストセッション 長を決定する．
7. BISTアーキテクチャ
図7にレジ スタ転送レ ベル 全体に 対する階層BIST アーキテクチャの一例を示す．データパスに対し ては ， 提案した時分割単一制御並行可検査DFTを行う．コン ト ローラを 組合せ回路部と状態レジ スタに 分離し ，状 態レジ スタをCBILBOに置き換える．入力にはTPG の値が 印加できるよ うにMUX M5を ，出力にはRA で 応答を観測できるようにMUX M6を付加する．
このア ーキテ クチャはTESTピン とbresetピ ン の 二つの 外部ピ ン を もつ ．TESTピ ン が1の と きに 回路に 対し てテ ストが 実行され る．破線部のBISTコ
図7 BIST アーキテクチャ Fig. 7 BIST architecture.
ント ローラは ，デ ータパスに 付加し たDFT要素の制 御 信 号 ，及び コント ロー ラとデ ー タ パ ス 間に 加え ら れたMUXを制御する信号を出力する．BISTコント ローラは 二つの カウン タと 組合せ 回路から 構成する ． SIDカウン タは テ スト セッション ，SLカウン タは 現 在のテ ストセッションのテ スト 実行時間を示す．コン ト ローラのテ ストは ，一つのテ ストセッションと考え る．TPG，RA及びM1，M2，M3は 提案するBIST 回路の外部で 実現可能であるため ，提案するアーキテ クチャは 二つの外部ピンと三つのMUX及びデ ータパ ス部とコント ローラ部のDFTで 実現可能である．
8. 実験 結 果
提 案 手 法（TCSC 法 ）と Wunderlich ら の 手 法 [2] 及 び CSC 法[6] を 比 較 す る ．使 用 し た RTL 回 路 は ，LWF，Paulin及びTseng（ 表4）で あ る ．
#PI,#PO,#Reg,#MUX,#OPは そ れ ぞ れ PI 数 ， PO数 ，レ ジ ス タ 数 ，MUX数 ，演 算 モ ジュー ル 数 を 表す．回路面積の 単 位はgate equivalentで ，論理 合成ツールとし てDesign Compiler（Synopsys）を用 いた ．
表5，表6に検出可能故障に対して100%の故障検出 率を達成する場合の，ハード ウェアオーバヘッド とテス
表4 回路特性 Table 4 Circuit characteristics.
コント ローラ デ ータパス
回路 面積（gate）
#PI #PO #State #Status #Control 面積（ gate ）#PI #PO |bit| #Reg. #Mod. 面積（ gate）
LWF 6835 1 0 4 0 8 67 64 64 32 5 3 6588
Paulin 36203 1 0 6 0 16 67 64 64 32 7 4 35333
Tseng 23000 3 2 5 0 13 102 96 64 32 6 7 22842
表5 ハード ウェアオーバヘッド 及び テスト 実行時間（ k= 1） Table 5 Hardware overhead and test application time (k = 1).
ハード ウェアオーバヘッド（%） テスト 実行時間（#clock）
回路 CSC 法 [6] TCSC 法（ 面積優先） TCSC 法（ 時間優先） CSC 法 TCSC 法
C DP BIST-C MUX C DP BIST-C MUX C DP BIST-C MUX [6] 面積優先 時間優先 LWF 38.43 1.20 19.50 13.14 4.59 25.51 1.20 7.33 12.38 4.59 25.51 1.20 7.33 12.38 4.59 540 626 626 Paulin 17.39 0.36 9.65 5.01 1.17 9.36 0.36 3.12 4.71 1.17 10.91 0.36 4.67 4.71 1.17 2247 3136 1955 Tseng 26.65 0.55 17.18 7.23 1.69 21.13 0.55 11.66 7.23 1.69 21.41 0.55 11.94 7.23 1.69 1868 3411 1783
表6 ハード ウェアオーバヘッド 及び テスト 実行時間（ k= 2） Table 6 Hardware overhead and test application time (k = 2).
ハード ウェアオーバヘッド（%） テスト 実行時間（#clock）
回路 CSC 法 [6] TCSC 法（ 面積優先） TCSC 法（ 時間優先） CSC 法 TCSC 法
C DP BIST-C MUX C DP BIST-C MUX C DP BIST-C MUX [6] 面積優先 時間優先 LWF 43.59 1.20 26.76 12.12 4.59 26.73 1.20 8.56 12.38 4.59 26.73 1.20 8.56 12.38 4.59 509 387 387 Paulin 17.55 0.36 10.97 4.63 1.59 10.14 0.36 3.90 4.71 1.17 12.46 0.36 5.45 4.71 1.17 2108 2705 1201 Tseng 30.53 0.55 20.03 7.44 2.51 22.05 0.55 12.85 6.96 1.69 25.13 0.55 17.62 6.96 1.69 1593 1592 1050 ト 実行時間を示す．TCSC法，CSC法にBISTアーキ テクチャを適用した回路を対象とした．C，DP，BIST- C，MUXはそれぞれコント ローラ部，デ ータパス部， BISTコントローラ部，MUX M4，M5，M6のハード ウェアオーバヘッド である．面積優先時は ，コ ストを type2cost < type3cost < cost thru < cost M U X と 与え ，時 間 優 先 時は ，演 算モジ ュール のコ スト を cost thru < cost M U X < type2cost < type3cost と与えた．提案手法では ，並行度k= 1の場合（ 表5） 及び 並行度k= 2の場合（ 表6）ともに ハード ウェア オーバヘッド を削減し た．これは ，type1だけでなく type2，type3の 経路を 利用し てテ ストし たためで あ る．k= 1の場合，時間優先時でもハード ウェアオー バヘッド が 減少し た ．これはMUXのテ ストに 対し て TMUXを 付加し ないためにテ スト 対象の組合せ回路 要 素数が 減 少し た た めで あ る ．k = 2 の 場 合 ，時 間 優先時では ，すべての場合においてテスト 実行時間を 削減し た ．これは ，提案し たテ スト スケジ ューリング が 有効に 働いたためであ る．面積優先時でも，LWF， Tsengにおいてはテ スト 実行時間が 減少し ている．こ れは ，ハード ウェアオーバヘッド を最小にするために ， 付加するDFT要素がが 減少し ，同時にテ スト 実行時 間を減少させたためである．
表7 データパス部のハード ウェアオーバヘッド Table 7 Hardware overhead of data paths.
Wunderlich CSC 法 TCSC 法
らの手法[2] [6] 面積優先 時間優先
k= 1 k = 2 k = 1 k = 2 k = 1 k = 2 HW/OH（ %） 38.43 21.71 34.66 7.41 8.66 7.41 8.66
LWF クロック数 106 530 499 616 367 616 367
FC（ %） 100 100 100 100 100 100 100 HW/OH（ %） 22.49 8.66 14.88 3.14 3.92 4.69 5.47 Paulin クロック数 701 2222 2093 3121 2680 1930 1176 FC（ %） 99.99 99.99 99.99 99.99 99.99 99.99 99.99 HW/OH（ %） 17.58 17.01 20.00 11.73 12.92 12.01 17.72 Tseng クロック数 657 1843 1568 3386 1567 1758 1025 FC（ %） 99.25 99.99 99.99 99.99 99.99 99.99 99.99
Wunderlichらの 手法はデ ータパ スに 対する手法で あるため ，その 比較のためにデ ータパ ス部のみに 対し て評価を行った（ 表7）．提案手法は ，Wunderlichの 手法に 比べてハード ウェアオーバヘッド が 小さく，故 障検出率（FC）が 高いが テスト 実行時間が 長くなる． これは ，提案手法ではTPGとRAを回路のPIとPO にのみ置き，組合せ回路要素ご とにテ ストを行うのに 対し ，Wunderlichらの手 法が 回路内部のレジ スタを BILBOやCBILBOに 変更し 閉路を 含まな い回 路に 対し てテストを行うからである．
9. む す び
本論文では ，階層BISTのためのデ ータパ スの時分 割単一制御並行可検査性とそのDFT及びRTL全体 に 対する階層BISTアーキテクチャを提案し た ．提案 手法はtest-per-clock方式に基づき，高い故障検出率， 低いハード ウェアオーバヘッド ，短いテ スト 実行時間 を実現する．今後の課題とし て提案手法の有効性を明 らかにするため ，より大規模な回路への提案手法の適 用や消費電力を考慮する手法の提案など がある．
謝辞 本研究に 際し ，多くの貴重な意見を頂いた 大 阪大学の増澤利光教授，本学の大竹哲史助手，並び に コンピュータ設計学講座の皆様方に深く感謝致し ます． 本 研 究は 一 部 ，奈 良 先 端 科 学 技 術 大 学 院 大 学 支 援 財 団教育研究活動支援による研究助成，及び ，新エネル ギ ー・産業技術総合開発機構（NEDO）から 半導体理 工学研究セン ター（STARC）に 委託され た「SoC先 端設計技術の研究開発 」の一部とし て奈良先端科学技 術大学院大学に 再委託され 実施され て い ます．また ， 21世紀COEプ ログ ラム「 ユビ キタス統合 メデ ィアコ ンピ ューテ ィング 」の支援を受けている．
文 献
[1] P. Bardell and W.H. McAnney, “Self-testing of mul- tichip logic modules,” Proc. 1982 IEEE Test Conf., pp.200–204, 1979.
[2] A.P. Stoele and H.J. Wunderlich, “Hardware-optimal test register insertion,” IEEE Trans. Comput.-Aided Des. Intergr. Circuits Syst., vol.17, no.6, pp.531–539, 1998.
[3] B. Koenemann, J. Mucha, and G. Zwiehoff, “Built-in logic block observation techniques,” Proc. 1979 IEEE Test Conf., pp.37–41, 1979.
[4] L.T. Wang and E.J. McCluskey, “Concurrent built-in logic block observer (CBILBO),” Proc. Int. Symp. on Circuits and Systems, pp.1054–1057, 1986.
[5] 井筒 稔，和田弘樹，増澤利光，藤原秀雄，“単一制御可検 査性に基づくレジ スタ転送レ ベルデ ータパスの組込み自己 テスト 容易化設計法，” 信学論（ D-I），vol.J84-D-I, no.1, pp.69–77, Jan. 2001.
[6] 山口賢一，和田弘樹，増澤利光，藤原秀雄，“レジスタ転 送レ ベルデ ータパ スの単 一制御並行可検査性に 基づ く 組 込み 自 己テ スト 法 ，” 信学論（ D-I），vol.J85-D-I, no.6, pp.527–537, June 2002.
[7] B.T. Murray and J.H. Hayes, “Hierarchical test gen- eration using pre computed tests for modules,” IEEE Trans. Comput.-Aided Des. Integr. Circuts Syst., vol.16, no.9, pp.1001–1014, 1990.
[8] D.D. Gajski, N.D. Dutt, A.C-H Wu, and S.Y-L Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic, 1992.
[9] B. Koenemann, “LFSR-coded test patterns for scan design,” Proc. European Test Conference (ETC), pp.237–242, 1980.
[10] B. Krishnanmurthy, “A dynamic programming ap- proach to the test point insertion problem,” Proc. ACM/IEEE DAC, pp.695–705, 1987.
（ 平成14 年 10 月 4 日受付，15 年 2 月 14 日再受付）
山口 賢一 （ 正員 ）
平11 奈良高専専攻科・電子情報工学専 攻了．平13 奈良先端科学技術大学院大学 博士前期課程了．平15 同大博士後期課程 了．博士（ 工学 ）．現在テ スト 容易化設計 の研究に 従事．平15 より奈良高専情報工 学科助手．IEEE 会員．
井上美智子 （ 正員 ）
昭62 阪大・基礎工・情報卒．平元同大 大学院博士前期課程了．同年（ 株 ）富士通 研究所入社．平7 阪大大学院博士後期課程 了．奈良先端大助手を経て ，現在同大助教 授．分散アルゴ リズム，グ ラフ理論，テ ス ト 容易化設計，高位合成の研究に 従事．工 博．IEEE，情報処理学会，人工知能学会各会員．
藤原 秀雄 （ 正員：フェロー ） 昭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．
