J149 j IEICE 2009 10

部分スルー可検査性に基づく順序回路のテスト生成法

岡 伸也

Chia Yee OOI

^{市原 英行}

^{井上 智生}

藤原 秀雄

Test Generation for Sequential Circuits with Partial Thru Testability

Nobuya OKA^†a), Chia Yee OOI^††, Hideyuki ICHIHARA^†, Tomoo INOUE^†, and Hideo FUJIWARA^†††

あらまし 無閉路可検査順序回路[11] は実用的にテスト容易な順序回路であり，その一つのクラスとして完全 スルー可検査順序回路[12] がある．完全スルー可検査性に基づくテスト容易化設計では，完全スキャン設計に比 べて小さい面積オーバヘッドでテスト実行時間の小さいテスト系列を生成できる．本論文では，無閉路可検査性 を満たす新たな順序回路のクラスとして，部分スルー可検査順序回路を提案し，部分スルー可検査順序回路に対 するテスト生成法，並びに，部分スルー可検査性に基づくテスト容易化設計法を示す．部分スルー可検査性は， 完全スルー可検査性のスルー機能に関する十分条件を緩和することで定義され，よって，部分スルー可検査順序 回路のクラスは完全スルー可検査順序回路のクラスを真に包含する．実験により，部分スルー可検査性に基づく テスト容易化設計は，完全スルー可検査性に基づくそれに比べて実用的に更なる面積オーバヘッドの削減が可能 なだけでなく，テスト実行時間も削減可能であることを示す．

キーワード スルー可検査性，無閉路可検査性，テスト容易化設計，時間展開モデル，組合せテスト生成アル ゴリズム

1.

組合せ回路に対するテスト生成問題は_NP完全であ ることが示されているが，実用的には回路規模の多項 式オーダで計算可能と考えられている_{[1], [2]}．一方で， 順序回路に対するテスト生成問題は実用的な時間で解 くことが難しく，多くの場合，回路内のすべてのフリッ プフロップをスキャンフリップフロップに置き換える 完全スキャン設計によって，組合せ回路のテスト生成 問題として取り扱われる．しかし，順序回路でありな がら，組合せ回路用のテスト生成アルゴリズムを用い てテスト系列を得ることが可能な回路が存在する．無

†広島市立大学大学院情報科学研究科，広島市

Guraduate School of Information Sciences, Hiroshima City University, 3–4–1 Ozuka-higashi, Asaminami-ku, Hiroshima- shi, 731–3194 Japan

††マレーシア工科大学，マレーシア

Faculty of Electrical Engineering, University of Technology Malaysia, Malaysia 81310 UTM Skudai Johor Malaysia

†††

奈良先端科学技術大学院大学情報科学研究科，生駒市

Graduate School of Information Science Nara Institute, Ikoma-shi, 630–0192 Japan

a) E-mail: [email protected]

閉路順序回路は，組合せ回路モデルである時間展開モ デルを用いることで，組合せ回路用のテスト生成アル ゴリズムを用いてテスト系列を得ることが可能である ことが示されている_{[3], [4]}．無閉路順序回路のテスト 生成複雑度は組合せ回路と比べて高いが，一般の順序 回路と比べると十分に低く，実用的である_{[5], [6]}．更 に，無閉路順序回路のうち，文献_[7]∼_[10]で示された 平衡構造や切換平衡構造は，組合せ回路と同等のテス ト生成複雑度をもつことが知られている．

藤 原 ら は ，回 路 中 に 閉 路 を も つ 順 序 回 路 で あ り な が ら ，無 閉 路 順 序 回 路 と 同 様 に テ ス ト 生 成 が 可 能 と な る 順 序 回 路 の ク ラ ス を 無 閉 路 可 検 査 性（_acyclical testability）として定義し，無閉路可検査性を満たす 順序回路のクラスを提案している_[11]．文献_[12]では， 回路内の外部入力から外部出力までのスルー機能だけ で構成される経路（スルー木と呼ばれる）に基づいて， 無閉路可検査性を満たす順序回路であるための十分条 件が示されている．

本論文では，文献_[12]で提案されたクラスを真に包 含する，テスト容易な順序回路の新しいクラスを提案 し，更に，提案したクラスに対するテスト生成法，及

び，テスト容易化設計法も提案する．新しいクラスは， 文献_[12]で示されたスルー木に代わって導入する，正 当化スルー木と伝搬スルー木に基づくクラスである． ここでは，正当化スルー木と伝搬スルー木の性質と文 献_[12]で定義されたスルー木の性質の違いから，本論 文で提案するクラスを部分スルー可検査性，文献_[12] で提案されたクラスを完全スルー可検査性と呼ぶ．部 分スルー可検査順序回路は，無閉路順序回路や完全ス ルー可検査順序回路と同様に，時間展開モデルを用い て組合せテスト生成アルゴリズムによりテスト生成が 可能である．また，部分スルー可検査順序回路は，完 全スルー可検査順序回路のクラスを真に包含する．こ れは，一般の順序回路に対して，部分スルー可検査性 に基づくテスト容易化設計によるハードウェアオーバ ヘッドが完全スルー可検査性に基づくそれに比べて小 さくなることを意味する．本論文では，部分スルー可 検査性に基づくテスト容易化設計として，ハードウェ アオーバヘッド最小を目指したスルー木集合生成のた めのヒューリスティックアルゴリズムを示す．実験に より，テスト容易化設計による面積オーバヘッドが削 減できるだけでなく，テスト実行時間も削減可能であ ることを示す．

本論文では，紙面の都合上，一部の定義や証明を省 略，若しくは概略のみを示している．詳細は文献_[13] にまとめた．

2.

図₁の順序回路_S1について考える．順序回路は，組 合せ論理部（combinational logic block^：CLB^）とレ ジスタからなり，それらの接続関係で表される．_CLB には，図₂に示すようなスルー機能を有するものもあ る．スルー機能には，一つの入力の値をそのまま出力 に伝搬する単純スルー（図 _{2 (a)}）と，複数の入力を まとめて一つの出力に伝搬する併合スルー（図_{2 (b)}） がある．

順序回路_S1は完全スルー可検査順序回路であるた めの十分条件を満たす．十分条件の中に，外部入力か ら外部出力までをスルー機能のみで構成する経路とし て定義したスルー木に関する条件がある．_S1は，回 路内に二つのスルー木をもつことでその条件を満たし ている．一つは外部入力_{P I2}からスルー機能_t1，_t7， t8^，t2^{を通る外部出力}P O1への経路，もう一つは外 部入力_{P I4}からスルー機能_t3，_t4，_t9，_t5，_t6を通 る外部出力_{P O2}への経路である．図₃に_S1におけ

図1 順序回路S1

Fig. 1 Sequential circuit S1.

図2 スルー機能 Fig. 2 Thru function.

図3 S1のC13 のための時間展開モデル Fig. 3 Time expansion model with respect to C13 of

S1.

る_{CLB C13}のための時間展開モデルを示す．時間展

開モデルは，回路内のレジスタへの値のロードやホー ルドを行う時刻を考慮した，_CLBの接続関係を表す組 合せ回路モデルである．時間展開モデルは組合せ回路 である．下部に示した数は，各_CLBや入出力が，も との順序回路_Sで動作する時刻の相対値を表す．順序 回路S₁では，上述のスルー木の存在により，回路の 閉路上にあるレジスタの値の正当化と伝搬を無閉路順 序回路のように行うことができる．そのため，時間展 開モデルを用いたテスト生成が可能となる．

3.

本章では，提案する部分スルー可検査順序回路につ いて説明する．

3. 1 回路モデル

順序回路は，次に示す_Rグラフによって表される．

［ 定 義₁］（_Rグ ラ フ ） 順 序 回 路 _S を 表 す_Rグ ラ フ GR = (V, A, w, r, t) は以下に示すような有向グラフ である．

図4 順序回路S2

Fig. 4 Sequential circuit S2.

1. ^{頂 点}v (∈ V )は ，レ ジ ス タ，外 部 入 力 ，外 部 出 力 の い ず れ か を 表 す．レ ジ ス タ 集 合 ，外 部 入 力 集 合，外部出力集合をそれぞれ，_{VR, VI, VO} とすると， V = VR∪ VI∪ VO ^である．

2. ^辺(u, v) (∈ A)は，レジスタまたは外部入出力 の間の接続を表す．信号線で直接接続されるものと組 合せ論理を通るものとがある．

3. 外部入出力，またはレジスタ_{v ∈ V} のビット 幅は w(v) (w : V → Z⁺) ^{で表される（}Z^{+ は正の} 整数）．

4. ^{関 数}r^はr : V → {h, φ}で あ り，レ ジ ス タ v ∈ VRがホールド機能を有するとき，_{r(v) = h}とす る．また，_vがホールド機能を有しないレジスタ，ま たは外部入出力のときは，_{r(v) = φ}とする．

5. ^{二つのレジスタ（または外部入出力）間}(u, v) (∈ A) に ス ル ー 機 能 _ti が あ る と き ，t(u, v) = ti ^と

示 す．ス ル ー 機 能 が な い 場 合 は t(u, v) = φ ^{と 示 す}

（_{t: V}²→ F ∪ {φ}, F = {t1, t2, . . . , tm}^{はスルー機}

能の集合）． _✷

（例₁） 順序回路_S2（図₄）の_Rグラフ_GR2を図₅ に示す．図₄の順序回路_S2ではレジスタのビット幅 及びホールド機能の有無は定義していないため，_GR2 では関数wとrは示していない． _✷

スルー機能_tiによる値の伝達は，回路中のレジスタ の値と外部入力の値に依存する．例えば，あるいくつか のスルー機能ti(∈ F )^{がレジスタ}v₁, v₂(∈ V )^の値に よって有効となるとき，_tiは_{{v1, v2}}によって活性化 されるといい，_{α(ti) = {v1, v2}}と表す_{(α : F → 2}

V₎

． なお，_{α(ti) = φ}のとき，_ti は常に活性化されている ことを表す．

3. 2 部分スルー可検査順序回路

順序回路のテスト生成を考えるとき，回路内の各レ ジスタに対する外部入力からの値の正当化と，外部出

図5 順序回路S2のR グラフ G_R2 Fig. 5 R-grah G_R2 of S2.

力への値の伝搬を行う方法が重要となる．そこで，ス ルー機能を使った値の正当化と伝搬について考える． 外部入力からレジスタへ任意の値を正当化するための 正当化スルー木_T

J

と，レジスタから外部出力へ任意 の値を伝搬するための伝搬スルー木_T

P

を以下に示す．

［定義₂］（正当化スルー木，伝搬スルー木） _Rグラ フ を _GR = (V, A, w, h, t)と す る ．正 当 化 ス ル ー 木 T^J = (V^J, A^J), V^J ⊆ V, A^J ⊆ A^{は，以下の条件を} 満たす_Rグラフ_GRの部分グラフである．

1. ^{任 意 の 葉}v (∈ V^J)^{は 外 部 入 力}(VP I)^{に 対 応} する．

2. ^任意の辺(u, v) (∈ A^J)^{はスルー機能を有する} (∀(u, v) ∈ A^J, t(u, v) = φ)^．

3. 併 合 ス ル ー の 入 力 は ，す べ て_T

J

に 含 ま れ る か ，全 く 含 ま れ な い か の い ず れ か で あ る_{(∀ti ⊆ F,} t⁻¹(ti) ∩ A^J= t⁻¹(ti) ∨ t⁻¹(ti) ∩ A^J = φ)^．

伝 搬 ス ル ー 木_T^P _{= (V}^P_{, A}^P_{), V}^P _{⊆ V, A}^P _{⊆ A} は，以下の条件を満たす_RグラフGR^{の部分グラフ}

である．

1. ^根v(∈ V^P)^{は外部出力}(VP O)^{に対応する．} 2. ^任意の辺(u, v) (∈ A^P)^{はスルー機能を有する} (∀(u, v) ∈ A^P, t(u, v) = φ)^． ✷

（例₂） 図₅に示した順序回路_S2の_Rグラフ_GR2で は，正当化スルー木と伝搬スルー木が二つずつ存在す る．正当化スルー木は，_T1^J_{= (V1}^J= {P I2, R1}, A^J₁ = {(P I2, R1)})^と，T₂^J = (V₂^J = {P I4, R9, R10}, A^J₂

= {(P I4, R9), (R9, R10)})である．伝搬スルー木は， T₁^P = (V₁^P = {R3, P O1}, A^P₁ = {(R3, P O1)})^と， T₂^P = (V2^P = {R11, R12, P O2}, A^P2 = {(R11, R12),

(R12, P O2)})^である． _✷

R^{グラフ中のスルー木}Ti^とTi^{に含まれるスルー機}

能を活性化する頂点との関係と，この関係に基づくス

ルー木の関係を以下に示す．

［ 定 義₃］（ ス ル ー 木 の 依 存 関 係 ） _Rグ ラ フGR = (V, A, w, r, t)に お け る ス ル ー 木_{Ti = (Vi, Ai)}を 考 え る ．こ こ で ，ス ル ー 木_{Ti = (Vi, Ai)} に つ い て ， Tiに 含 ま れ る ス ル ー 機 能 を 活 性 化 す る レ ジ ス タ の 集 合 を_D(Ti)と 表 す．す な わ ち ，ス ル ー 木 の 辺 集 合 Ai に 含 ま れ る 辺 をak (1 ≤ k ≤ |Ai|)^{と す る と ，} D(Ti) = ∪^|A_k=1^i|α(t(ak))である．あるレジスタ，若し くは外部入力_{v∈ V} が，_Tiのいずれかの辺のスルー 機能を活性化するとき，すなわち，_{v∈ D(Ti)}のとき， Ti^はvに依存するという．また，二つのスルー木_Ti， Tj= (Vj, Aj)^{について，}D(Ti) ∩ Vj= φ^のとき，Ti

は_Tjに依存するといい，_{Ti≺ Tj}と表す． _✷

（例₃） 図₅において，正当化スルー木T₂^Jの辺集合 A^J₂ ^{に含まれるスルー機能}t3^{はレジスタ}R1^によって 活性化される，つまり，_{α(t3) = {R1}}であると仮定 する．このとき，_GR2におけるスルー木同士の依存関 係は，_T2^J_{≺ T1}^Jと表すことができる． _✷

レジスタの値の正当化においては，上記のようなス ルー木の依存関係を考慮すると同時に，特定の回路構 造も考慮する必要がある．特定の回路構造とは，一つ の レ ジ ス タ に 収 れ ん す る 二 つ の 経 路 が ，そ れ ぞ れ ス ルー機能の出力と，そのスルー機能を活性化するレジ スタをもつ場合や，始点が同じ場合（分岐再収れん） である．これらの構造は以下のようにまとめられる．

［定義₄］（経路の依存性） _Rグラフにおける二つの経 路p= (u1^{, u}2, . . . , un_p)^，q= (v1^{, v}2, . . . , vn_q) ^を考 える．各経路_{p, q}は，単純路であるか，または，始点 と終点を経路_p（または_q）の終点_unp（または_vnq） とするサイクルをたかだか一つ含む．このとき，以下 の条件をすべて満たすならば，経路_pは経路_qに依存 するという．

1. p^とq^{の長さが等しい}(np= nq(= n))^． 2. p^とqの終点が同一の頂点である_{(unp= vnq)}． 3. p ^{の 最 初 の 辺} (u1,u2) が ス ル ー 機 能 を も つ (t(u1^{, u}2) = φ)^．

4. ^経路p, qの始点が同一の頂点である_{(u1= v1)}， または，_pの最初の辺_{(u1, u2)}が頂点_v1によって活 性化される_{(v1 ∈ α(t(u1, u2)))}． _✷

（例₄）図₅に示す_Rグラフにおいて，二つの経路 p1= (P I4, R9, R10, R11, R12)^，q1= (P I4, R6, R7, R8, R12)の依存性について考える．経路_{p1, q1} の経

路長は₅で等しく，経路の終点の頂点も_R12で同じ であり，経路p₁の最初の辺_{(P I4, R9)}は，スルー機 能_t3をもつ．更に，各経路の始点が同一の頂点_{P I4} である．これは，条件₄の前者の条件を満たす．よっ て，_p1は_q1に依存するといえる． _✷

ここまでの定義をもとに，部分スルー可検査順序回 路の定義を以下に示す．

［定義₅］（部分スルー可検査順序回路） 順序回路_S に 対 す る_Rグ ラ フGR = (V, A, w, r, t) ^{が ，以 下 の} 条 件 を 満 た す 正 当 化 ス ル ー 木 の 集 合_T

J _{= {T}J i = (V_i^J, A^J_i), i = 1, 2, . . . , n^J} と 伝 搬 ス ル ー 木 の 集 合 T^{P = {T}i^{P = (V}

P i ^{, A}

P

i), i = 1, 2, . . . , n^P} ^{を も つ} とき，順序回路_Sは部分スルー可検査順序回路であ る と い う．こ こ で ，_{T = T}

J ∪ T^{P, V}T^J = ∪ⁿ_i=1^J V_i^J, V_T^P = ∪ⁿ_i=1^PVi^{P とする．}

（正当化スルー木と伝搬スルー木が満たすべき条件） 1. 正 当 化 ス ル ー 木 の 集 合 _T

J

は 以 下 の 条 件 を 満 たす．

(a) 正当化スルー木は互いに素である． (b) 正当化スルー木を構成する頂点の集合_V

J T ^はR

グラフのフィードバック頂点集合_FVS

（注 1）

を被覆する． (c) スルー機能を活性化するために必要なレジス タはホールド機能をもつ_{(∀v ∈ α(ti})(∈ F ), r(v) = h)^．

2. ^{伝搬スルー木の集合}_T^P は以下の条件を満たす． (a) 伝搬スルー木は互いに素である．

(b) 伝搬スルー木を構成する頂点の集合_V

P T ^はR

グラフの_FVSを被覆する．

（スルー木の依存関係に関する条件）

3. ス ル ー 木 集 合_T に 含 ま れ る 任 意 の ス ル ー 木 T = (VT, AT)は以下の条件を満たす．

(a) ス ル ー 木 の 依 存 関 係_≺に お け る 推 移 閉 包_≺^′ を 考 え た と き ，関 係_≺^′は 自 分 自 身 と 関 係 を も た な い

（すなわち，∀T ∈ T , T ≺^′T）．

(b) ^スルー木Tが依存する任意の頂点vは，正当 化スルー木に含まれる頂点であるか，外部入力である

（すなわち，∀v ∈ D(T ), v ∈ (V_T^J− VT) ∪ VP I^）．

(c) ^スルー木T ^{は他の正当化スルー木}T^′と同じ 頂点に依存しない（すなわち，D(T ) ∩ D(T^′) = φ^）．

（依存関係をもつ経路対に関する条件）

4. ^{以下に示す条件}(a)^から条件(d)^{を満たす任意} の経路対_{p= (u1, u2}, . . . , un_p), q = (v1, v2, . . . , vn_q)

（注₁）：FVS: Feedback Vertex Set.取り除くと閉路がなくなる頂点 の集合．

において，_p若しくは_q上に，条件_(i)，_(ii)をどちら も満たすような頂点u_ˆkが存在する．なお，条件_(i)， (ii)^の経路pˆ= ( ˆu1,uˆ2, . . . ,uˆn)^は，経路p^若しくは q^を表す．

(a) ^経路p^，q上に存在する任意の閉路は，基本閉 路

（注 2）

である．

(b) ^経路pはqに依存する．

(c) ^{経 路}p^{上 の 頂 点}ui_p(1 < ip < np)^{に お い} て，経路_(u1, . . . , uip⁾は正当化スルー木に含まれる， か つ ，辺 _{(uip, uip+1)}は 正 当 化 ス ル ー 木 に 含 ま れ な い ．経 路_pは ，正 当 化 ス ル ー 木 に 含 ま れ る 頂 点_uj

p

か ら 伝 搬 ス ル ー 木 に 含 ま れ る 頂 点uk_pへ の 部 分 経 路 (uj_p, . . . , uk_p)(ip< jp≤ kp< np)^{を含まない経路で} ある（すなわち，_{ujp∈ V}

J

T^{，かつ，u}kp^{∈ V} P T ^）．

(d) ^経路qは，正当化スルー木に含まれる頂点_vjq か ら 伝 搬 ス ル ー 木 に 含 ま れ る 頂 点_vk

q へ の 部 分 経 路 (vj_q, . . . , vk_q)(iq< jq≤ kq< nq)^{を含まない（すなわ} ち，_{vjq∈ V}

J

T^{，かつ，vk}q ^{∈ V} P T^）．

(i) ^経路pˆ^{の部分経路}p^′= ( ˆuk,uk+1ˆ , . . . ,uˆn)^に おいて，経路の長さ_|p^′_|が，_Rグラフ上の異なる経路 p^′′= ( ˆuk, . . . ,uˆn)^の経路長|p^′′|と比べて等しいか長い．

(ii) ^{頂 点}uˆk が ホ ー ル ド 機 能 を も つ（ す な わ ち ，

r( ˆuk) = h^）． _✷

（ 例₅） 図 ₄ に 示 す 順 序 回 路S₂ と 図 ₅ に 示 すS₂ の_Rグ ラ フ_GR2 に お い て ，部 分 ス ル ー 可 検 査 性 を 考 え る ．_GR2 で は ，頂 点_{R1, R2, R3}の い ず れ か と ， R10, R11のいずれかの頂点を含む頂点集合が_FVSと なる．_GR2の正当化スルー木を例₂で示した_T1^J_{, T2}^J と す る と ，そ れ ら の 頂 点 集 合 は_FVSと な る 頂 点 集 合_{{R1, R10}}を 被 覆 し て い る ．_GR2 の 伝 搬 ス ル ー 木 を 例₂で 示 し た_T

P

1 ^{, T}2^P と す る と ，そ れ ら の 頂 点 集 合 は_FVSと な る 頂 点 集 合_{{R3, R11}}を 被 覆 し て いる．_GR2において，例₄で示した依存関係をもつ 経路対p₁ = (P I4, R9, R10, R11, R12)^，q₁ = (P I4, R6, R7, R8, R12)について考える．経路対_p1，_q1は， 定義₄条件₄の対象となる経路_pと_qに合致する．こ の経路対において，頂点_R8がホールドレジスタであ ることで条件₄の_(i)と_(ii)を満たす．よって，_R8の ホールド機能を用いることで，p₁がq₁に依存しても R12に値の正当化を行うことができる（詳細は例₆に 示 す ）．他 の 経 路 対 に つ い て も 同 様 に 考 え る と ，_R2， R4^，R6^，R8がホールドレジスタであればすべての経

路対に対して条件を満たす． _✷

こ こ で 示 し た 部 分 ス ル ー 可 検 査 順 序 回 路 と 完 全 ス ルー可検査順序回路_[12]の関係について考える．部分 スルー可検査順序回路の定義から，正当化スルー木集 合_T

J

と伝搬スルー木集合_T

P

において_T

J_{= T}P

で ある場合，完全スルー可検査順序回路であるといえる． よって，次の定理が成り立つ．

［定理₁］ 部分スルー可検査順序回路のクラスは，完全 スルー可検査順序回路のクラスを真に包含する．_✷

3. 3 部分スルー可検査順序回路のテスト生成法 部分スルー可検査順序回路に対するテスト生成は， 完全スルー可検査順序回路と同様に，時間展開モデル に対して行う．基本的には，回路内の一つの_CLBに 対 し て 一 つ の 時 間 展 開 モ デ ル を 考 え る ．部 分 ス ル ー 可検査順序回路_Sにおける_{CLB Ci}のための時間展 開モデル_{C(GA(S, Ci))}は，対応する時間展開グラフ GA(S, Ci) = (VA, AA, l, c)^{で表される．ここで，}VA

は頂点集合，AA^{は辺集合，}lは時間展開グラフの頂点 集合_VAから_Rグラフの頂点集合_V への写像を表す． 写像_cは順序回路_Sにおける回路の動作時刻を表し， 頂点集合_VAから整数集合_Zへの写像である．時間展 開グラフの基本的な定義は，文献_[3]等で示されたも のと同じであり，Sの_RグラフGR^{に基づいて作ら}

れる．

時間展開モデルに対して入力パターン_ICを与えた ときの各外部入力，信号線の値は，時間展開グラフの 写像_l，_cの情報により，_S中の外部入力やレジスタに おける値と対応づけることが可能である．また，順序 回路_Sに入力系列_ISとホールドレジスタ，スルー機 能の制御系列_IH，_ITを与えたときに得られる外部入 力やレジスタの値は，系列_IH，_IT をもとに得られる 時間展開モデルの信号線の値と対応づけることが可能 である．そのため，時間展開モデルにIC^{を与えるこ}

とで得られる出力_OCは，もとの順序回路_Sの_ICに 対応する入力系列_IS から得られる出力系列_OSに変 換可能であり，またその逆も可能である．

順 序 回 路 _S に お け る 故 障 と 時 間 展 開 モ デ ル C(GA(S, Ci))に お け る 故 障 の 対 応 に つ い て 考 え る ． S^におけるCLB Ci^は，C(GA(S, Ci))^{で複数存在す} る場合がある．そのため，_Sの_{CLB Ci}における単一 故障は，_{C(GA(S, Ci))}におけるすべての_{CLB Ci}に おける多重故障に対応する．

（注₂）：長さが₁以上で終点が始点に一致する以外には同じ頂点を₂度 通らない閉路．

図6 S2におけるCLBC8 のための時間展開モデル C(GA(S2, C8)) Fig. 6 Time expansion model C(GA(S2, C8)) with respect to C8 of S2.

以上のことから，以下の定理を導くことができる．

［定理₂］部分スルー可検査順序回路_Sの_Rグラフ を_GR= (V, A, w, r, t)^，GR^におけるCLB Ci^に関す

る時間展開グラフを_{GA(S, Ci) = (VA, AA}, w, t, l, c)^， GA(S, Ci)に基づく時間展開モデルを_{C(GA(S, Ci))} とする．回路_Sにおける故障集合を_F，_{C(GA(S, Ci))} における故障集合を_FAとする．回路_Sにおける_CLB Ci^{に対応する}CLB^の故障をf ∈ F^，C(GA(S, Ci)) における_{CLB Ci}に対応する_CLBの故障を_{fA∈ FA} と す る ．故 障fA が テ ス ト 可 能 な ，時 間 展 開 グ ラ フ GA(S, Ci)に基づいた時間展開モデル_{C(GA(S, Ci))} が存在するならば，かつそのときに限り，順序回路_S における故障_fはテスト可能である． _✷

（例₆） 図₄の順序回路_S2の_{CLB C8}に故障_fを仮 定し，時間展開モデル_{C(GA(S2, C8))}において_fに 対応する故障_fAを検出するテスト系列について考え る．_{C(GA(S2, C8))}を図₆に示す．時間展開モデル の下部の数字は時間展開グラフにおける写像cを表す． I20^やO1^は，C(GA(S2, C8))^{に対して組合せ回路用} のテスト生成アルゴリズムを適用することで得られた， CLB C8の 故 障 を 検 出 す る た め の テ ス ト パ タ ー ン で ある．図₆に示すように，レジスタ_R2（_{CLB C2}の 出力レジスタ），_R4（_C5の出力レジスタ），_R6（_C7 の出力レジスタ），_R8（_C9の出力レジスタ）の値が， 数時刻ホールドされる．これにより，_S2内に依存関係 をもつ経路対がある場合にもスルー機能を活性化し， 任意の値を正当化可能となる．例えば，例₄，例₅で 示した経路対p₁，q₁について考える．図₆において， p1^は時刻6^のP I4^から時刻10^のCLB C10^の出力に 対応し，_q1は時刻₈の_{P I4}から時刻₁₀の_{CLB C10} の 出 力 に 対 応 す る ．定 義₅条 件_(i)，_(ii)を 満 た す レ

ジスタ_R8（_{CLB C9}の出力レジスタ）のホールド機

表 1 S2 に お け るCLB C8 のための時間展開モデル C(GA(S2, C8)) から得られる入出力系列 Table 1 Input and outout sequences for S2 with

C(GA(S2, C8).

系列 頂点 時刻

名 名 0 1 2 3 4 5 6 7 8

I_S P I2 I20 I21 X I22 X X X I24 I25

P I3 X X I30 X X X X X X P I4 X X I40 I41 X X I42 I43 I44

IH R2 X L H H H X X X X

R4 X X X X X L H H H

R6 X X L H X X L H X

IT t1 a X X X X X X X X

t3 X X X a X X X X X

OS P O1 X X X X X X O1 X X

能によって，経路の始点である_{P I4}の値は，異なる 時刻₆と₈で異なる値_I42と_I44を入力可能となる． C(GA(S2, C8))^{の外部出力}P O1^{への出力パターンを} 得るために必要となる_S2に対する入出力系列を表 ₁ に示す．ここでは，紙面の都合上時刻₉からの系列は

示さない． _✷

定理₂より，部分スルー可検査順序回路は，回路内 のすべての_CLBのための時間展開モデルに対してテ スト生成を行うことで，回路内のすべての対象故障に 対するテスト系列を得ることが可能である．時間展開 モデルの生成は，部分スルー可検査順序回路の_Rグラ フから得られる時間展開グラフを変換することで得ら れる．時間展開グラフを得ることでホールドレジスタ， スルー機能の制御系列を得ることができる．そのため， 対象とする_CLBのすべての故障をテスト可能である ような時間展開モデルが生成可能である．

3. 4 部 分 ス ル ー 可 検 査 順 序 回 路 の テ ス ト 生 成 手 続き

上述した一つの_CLBのための時間展開モデルを利 用した，順序回路_S全体に対するテスト生成の手続き

について考える．

順序回路Sにおける_CLBの集合をCS^，Sの故障 集合を_Fとする．まず，集合_CSに含まれるテスト対 象_{CLB Ci}を選択する．故障集合_F に_Ciの故障が 含まれる場合，以下の手順を実行する．_{CLB Ci}のた めの時間展開モデルにおいて，スルー機能を活性化し ていない_{CLB Ci}の故障リストFC ∈ F ^{を得る．得} られた故障リスト_FCをもとに多重故障を対象とする 組合せ回路用テスト生成アルゴリズムを適用し，時間 展開モデルに対するテストパターンを得る．得られた テストパターンからもとの順序回路のためのテスト系 列を得る．故障リストFCと，得られたテスト系列を 使って検出可能となる故障を_F から削除する．もし， F = φであるならば上記の手順を繰り返し実行し，残 りの故障のためのテスト系列を得る．

3. 5 テスト容易化設計

与えられた順序回路を部分スルー可検査順序回路へ 変換するためのテスト容易化設計法（_DFT法）につい て考える．_DFTとしての回路への追加要素は，_CLB におけるスルー機能とレジスタにおけるホールド機能 となる．ここでは，ハードウェアオーバヘッド最小を 指向したスルー木集合探索のためのヒューリスティッ クアルゴリズムを示す．提案するアルゴリズムは_Rグ ラフを入力とし，部分スルー可検査性を満たすために 必要となる正当化スルー木集合と伝搬スルー木集合を もつ_Rグラフを出力とする．アルゴリズムによって 得られた_Rグラフにおけるスルー木集合に対応する CLBにスルー機能を付加する．ここでは正当化スルー 木の探索について説明する．以下の操作の繰返しを正 当化スルー木を探索するために実行する．

1. ^{ヒューリスティック尺度として，}R^{グラフの各} 頂点に対してその頂点を正当化スルー木に含むために 必要なスルー機能の最小数を計算．

2. Rグラフに含まれる辺を一つ以上もつような強 連結成分の要素に含まれる頂点集合から，スルー木に 含まれる頂点を選択．選択は，自己ループをもつ頂点， 重みが小さい頂点，頂点数の多い強連結成分に含まれ る頂点という優先順序に従って行う．選択する頂点が なくなったとき，ステップ₅へ進む．

3. 選択した頂点へ隣接する頂点の中で重みが最も 小さい頂点を選択し，その頂点に接続している辺を選 択．新たに選択した頂点に対してステップ₃を繰り返 すことで，外部入力に到達するまで辺の選択と頂点の 選択を行い，それを正当化スルー木とする．

図7 R グラフ G_R3 Fig. 7 R-graph G_R3.

図8 スルー木探索結果 Fig. 8 DFT result.

4. 生成されたスルー木に関する情報をもとにグラ フの情報を更新しステップ₁へ戻る．

5. ^ステップ1^から4で得られた回路において，定 義₄条件₄の_(a)から_(d)を満たす経路対を探索し， その経路対において，定義₄条件₄の_(i)，_(ii)を満た す頂点_uˆkがホールドレジスタでない場合，ホールド レジスタとする．

（ 例₇）図₇ に 示 す_Rグ ラ フ_GR3に 対 し て 上 述 の DFTアルゴリズムを適用する．このとき，正当化ス ルー木の探索後，伝搬スルー木の探索を実行する．こ の_GR3のどの辺も，スルー機能をもっていない．図₈ に 示 す よ う に ，六 つ の ス ル ー 機 能 を 付 加 す る こ と で 頂点_{P I1, R1}とP I2, R2, R4^{をそれぞれ含む二つの} 正当化スルー木と頂点_{R5, P O0}とR4, R6, P O1^をそ れ ぞ れ 含 む 二 つ の 伝 搬 ス ル ー 木 が 構 成 さ れ る ．こ の とき，完全スルー可検査順序回路とするためには，辺 (R1, R3)^，(R3, R5)にスルー機能を付加する必要があ る．この例において，依存関係をもつ経路が存在しな いため，ホールド機能を付加する必要はない． _✷

4.

部分スルー可検査性の有効性を調べるため，実験を 行った．テスト生成ツールはTetraMAX(synopsys)^， 論理合成ツールはDesign Compiler(synopsys)^，計算 機 は ，Dell PowerEdge 2950^（Red Hat Linux v.5^，

表2 実 験 結 果 Table 2 Experimental results.

回路， DFT 面積 テスト 故障 テスト テスト

FF 数，法 オーバ パターン 検出 実行時間 生成

面積 ヘッド 数 効率 （サイクル） 時間[s]

org. — 42 70.55 200 9875.04 ex1 FS 280 56 100.00 2336 0.01

40 FT 73 56 100.00 336 0.05

2664 PT 49 58 100.00 348 0.13

org. — 61 99.97 238 62.55

ex2 FS 672 41 100.00 4073 0.02

96 FT 96 56 100.00 280 0.04

3989 PT 48 48 100.00 288 0.35

org. — 18 88.97 210 15267.39 lwf FS 336 71 100.00 3527 0.11 48 FT 145 82 100.00 492 0.30

4782 PT 97 71 100.00 426 1.05

org. — 27 96.38 199 3551.20 trap FS 616 74 100.00 6674 0.04

88 FT 75 90 100.00 720 0.11

4489 PT 50 89 100.00 712 0.26

org. — 29 98.02 185 1960.27 diff FS 672 84 100.00 8244 111.32 96 FT 194 88 100.00 880 136.63 5727 PT 48 59 100.00 531 798.92

CPU 2.33 GHz Quad^，メモリ4 GByte^{）を用いた．} 実験では，_DFTを行っていない（すべての_CLBが スルー機能をもっておらず，すべてのレジスタがホー ルド機能をもつ）順序回路（_org.），完全スキャン設計

（_FS）を行った順序回路，完全スルー可検査設計_[12]

（_FT）を行った順序回路，そして部分スルー可検査設 計（_PT）を 行った 順 序 回 路 の 四 つ を 面 積 オ ー バ ヘッ ドとテスト生成の観点から比較した．スルー可検査設 計（_{FT, PT}）は ，3.4で 示 し た 方 法 に 基 づ い て 行っ た ．実 験 回 路 に お い て ，ス テップ₅の ホ ー ル ド レ ジ ス タ の 付 加 は な かった ．表 ₂に ，実 験 で 用 い た 回 路 情報（_FF数と回路面積）に加えて，三つの設計に対 する面積オーバヘッド，テストパターン数，テスト実 行 時 間 ，テ ス ト 生 成 時 間 を 示 す．回 路 面 積 は ，_NOT ゲートの面積を₁としたときの組合せ論理部のみの面 積 を 表 す．完 全 ス キャン に お け る テ ス ト 実 行 時 間 は ， (^{テストパターン数}) × ((FF^数) + 1) + (FF^数)^とした． 各回路の対象故障は，回路内の各_CLBと外部入出力 に対する故障とした．各回路において，_org.では順序 回路用のテスト生成アルゴリズム，それ以外について は組合せ回路用のテスト生成アルゴリズムを適用した． 時間展開モデルにおける多重故障は，文献_[14]の手法 を用いて単一故障としてテスト生成を行った．テスト 生成におけるバックトラックリミットは_10,000,000回 とした．

表₂において，完全スキャン設計（_FS）と，テスト 容易化設計としてスルー機能を用いるスルー可検査設 計（_FT，_PT）の結果について比較する．_FSに比べ て，スルー可検査設計では面積オーバヘッドを大きく 削減できた．これは，すべてのレジスタをスキャンレ ジスタに置き換える_FSに比べて，スルー可検査設計 は回路の必要な部分にのみスルー機能を付加するため である．テスト実行時間について，_PTは最大で_1/16 に短縮した_(diff)．これは，フルスキャン設計におけ るテスト実行で必要となるスキャンシフト操作が，ス ルー可検査順序回路では必要ないためである．

次に，完全スルー可検査設計（_FT）と部分スルー 可検査設計（_PT）を比較する．_FTと比べて，_PTは 面積オーバヘッドが小さくなり，最大で_1/4となった

(diff)．これは，部分スルー可検査順序回路のクラス

が完全スルー可検査順序回路のクラスを真に包含する ため，必要なテスト容易化設計のオーバヘッドが小さ くなることを示すものである．また，_ex1を除く回路 において，_FTと比べて_PTのテストパターン数も小 さくなった．これは，_PTの時間展開モデルでは，ス ルー機能を用いないで値の正当化と伝搬を行うことが 多くなるため，₁パターン当りの検出故障数が増加し たためと考えられる．テスト生成時間は，_PTは_FT に比べて大きくなった．これは，_PTではスルー機能 を利用せずに値の正当化と伝搬を行う場合が増えるた め，テストパターンの探索が多少困難になるためであ る．しかしながら，テスト生成時間が最も大きい場合 (diff)^でもorg.に比べて半分以下であり，_{FS, FT}と 同様に完全故障検出効率を達成していることから，十 分実用的であるといえる．

5.

本論文では，組合せ回路用のテスト生成アルゴリズ ムを用いてテスト系列を生成可能な順序回路のクラス として部分スルー可検査順序回路を提案し，それに基 づくテスト生成法，テスト容易化設計法を提案した． 実験により，完全スルー可検査設計に比べテスト容易 化設計における面積オーバヘッドを削減でき，かつ， 完全スルー可検査順序回路と同様に完全故障検出効率 が得られることを示した．今後の課題として，テスト 容易な順序回路のクラスの更なる拡張が挙げられる． 具体的には，本論文で提案した部分スルー可検査性の 条件の緩和，スルー機能以外の回路の機能に着目した 新たなテスト容易性の提案が挙げられる．

謝辞 本研究に関し，多くの貴重な御意見を頂いた 本学の吉川祐樹助教，並びに，コンピュータデザイン 研究室の諸氏に感謝します．本研究は一部，日本学術 振興会科学技術研究費補助金基盤研究（_B）（課題番号 20300018^{），基盤研究（}C^{）（課題番号}19500048^）の 研究助成による．

文 献

[1] H. Fujiwara, Logic Testing and Design for Testability, MIT Press, 1985.

[2] M.R. Prasad, P. Chong, and K. Keutzer, “Why is ATPG easy?,” Proc. 36th DAC, pp.22–28, June 1999. [3] T. Inoue, T. Hosokawa, T. Mihara, and H. Fujiwara,

“An optimal time expansion model based on com- binational ATPG for RT level circuits,” IEEE 7th Asian Test Symposium, pp.190–197, Dec. 1998. [4] T. Inoue, D.K. Das, C. Sano, T. Mihara, and H.

Fujiwara, “Test generation for acyclic sequential cir- cuits with hold registers,” Proc. International Conf. on Computer Aided Design, pp.550–556, Nov. 2000. [5] C.Y. Ooi and H. Fujiwara, “Classification of sequen-

tial circuits based on τ^knotation,” IEEE Proc. 13th Asian Test Symp., pp.348–353, Nov. 2004.

[6] C.Y. Ooi, T. Clouqueur, and H. Fujiwara, “Classifi- cation of sequential circuits based on τ^knotation and its applications,” IEICE Trans. Inf. & Syst., vol.E88- D, no.12, pp.2738–2747, Dec. 2005.

[7] R. Gupta and M.A. Breuer, “The BALLAST method- ology for structured partial scan design,” IEEE Trans. Comput., vol.39, no.4, pp.538–544, April 1990.

[8] A. Balakrishnan and S.T. Chakradhar, “Sequential circuits with combinational test generation complex- ity,” Proc. IEEE International Conference VLSI De- sign, pp.111–117, Jan. 1996.

[9] H. Fujiwara, “A new class of sequential circuits with combinational test generation complexity,” IEEE Trans. Comput., vol.49, no.9, pp.895–905, Sept. 2000. [10] M. Inoue, C. Jinno, and H. Fujiwara, “An extended class of sequential circuits with combinational test generation complexity,” IEEE Proc. International Conference on Computer Design, pp.200–205, Sept. 2002.

[11] H. Fujiwara, H. Iwata, T. Yoneda, and C.Y. Ooi, “A non-scan design-for-testability for register-transfer level circuits to guarantee linear-depth time expan- sion models,” IEEE Trans. Comput.-Aided Des. In- tegr. Circuits Syst., vol.27, no.9, pp.1535–1544, Sept. 2008.

[12] C.Y. Ooi and H. Fujiwara, “A new class of sequen- tial circuits with acyclic test generation complexity,” IEEE Proc. International Conference on Computer Design, pp.425–431, Oct. 2006.

[13] 岡 伸也，C.Y. Ooi，市原英行，井上智生，藤原秀雄，“組

合せテスト生成可能な順序回路の新しいクラスの提案とそ れに基づくテスト生成法・テスト容易化設計法について，” http://harp.lib.hiroshima-u.ac.jp/handle/harp/3985 [14] H. Ichihara and T. Inoue, “A method of test genera-

tion for acyclic sequential circuits using single stuck- at fault combinational ATPG,” IEICE Trans. Funda- mentals, vol.E86-A, no.12, pp.3072–3078, Dec. 2003.

（平成21 年 5 月 11 日受付，7 月 22 日再受付）

岡 伸也 （学生員）

平16 広島市立大・情報科学・情報機械 システム工卒．同大大学院修士課程了．現 在，同大大学院情報科学研究科博士後期課 程在学中．テスト生成，テスト容易化設計 に関する研究に従事．

Chia Yee Ooi

received the B.E. and M.E. degrees in Electrical Engineering from Univer- siti Teknologi Malaysia, Malaysia in 2001 and 2003, respectively, and the Ph.D. degree in information science from Nara Insitute of Science and Tech- nology, Japan in 2006. She is currently a lecturer in Uni- versiti Teknologi Malaysia, Malaysia. Her research inter- ests include VLSI design and testing. She is a member of the IEEE.

市原 英行 （正員）

平7 阪大・工・応用物理卒．平 9 同大 大学院工学研究科応用物理学専攻博士前期 課程了．平11 年 2 月から 7 月まで米アイ オア大学のResearch Scholar．平 11 大阪 大学大学院工学研究科応用物理学専攻博士

後期課程了，博士（工学）．同年広島市立

大学情報科学部情報機械システム工学科助手．平16 同大助教 授．平19 より准教授．VLSI のテスト及びテスト容易化設計， フォールトトレラントシステムの研究に従事．平17 本会論文 賞及びWRTLT 2004 Best Paper Award 受賞．

井上 智生 （正員）

昭63 明大・工・電子通信卒．平 2 同大 大学院博士前期課程了．同年より平4 まで 松下電器産業（株）半導体研究センターに てマイクロプロセッサの開発に従事．明大 大学院博士後期課程を経て，平5 奈良先端 大情報科学研究科助手．平11 広島市立大 学情報科学部助教授，平16 より同大同学部教授．テスト生成， テスト容易化高位合成，再構成可能デバイス，耐故障設計に関 する研究に従事．博士（工学）．平17 WRTLT’04 Best Paper Award 受賞．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 Society Golden Core Member，IEEE Fellow．