RTL
演算器に対するパス遅延故障検出条件の評価日大生産工
(
院)
○井上諒一
日大生産工
細川
利典 奈良先端大
藤原
秀雄
1
はじめに近年，半導体微細化技術の進歩に伴い，回路の 大規模化，高速化，複雑化が急速に進み，回路の タイミングに関する欠陥が問題になっている．そ のため，遅延故障テストが重要になっている．遅 延故障は，ゲートのスイッチング時間や配線の信 号伝搬時間が増大し，本来起きるはずのフリップ フロップ値の変化が規定の時間内に起こらない故 障である．遅延故障にはパス遅延故障
[1]
や遷移 故障[1]
などの故障モデルが存在する．中 で も パ ス 遅 延 故 障 は ， フ リ ッ プ フ ロ ッ プ
（
Flip-Flop: FF
）からFF
までのパスを一つの故 障として扱い，そのパス上にある欠陥により累積 された遅延を考慮した遅延故障モデルである．パ ス遅延故障は微小な遅延を扱うことができ，パス に遅延を定義できるのでパス上の複数の信号線の 遅延もモデル化できる．しかしながら，パス数が ゲート数に対して指数関数的に増加する場合があ り，全故障を対象とするテストは現実的に不可能 である．そのため，回路中のクリティカルパスの みを対象にテスト生成をおこなうのが一般的であ る．したがって，回路全体のパス遅延故障を網羅 的にテストしているといえない．また，近年
VLSI
の設計生産性向上のために，ハードウェア記述言語を用いた
VLSI
設計法が，設計者に広く普及している．具体的には，レジス タ ト ラ ン ス フ ァ ー レ ベ ル （
Register Transfer Level: RTL
）で回路を設計している．RTL
の回路 情報を用いてテスト不能パスを同定する手法が提 案されている[2]
．この手法では，RTL
パス情報を 用いることにより，ゲートレベル情報を用いた判 定法よりも高速で効率的な判定ができている．また，サイクル精度な動作を記述する機能記述
RTL
を対象に，縮退故障のテスト生成を行う手法が提案されている
[3][4]
．これらの手法は，機能記 述RTL
回路を割当決定図（Assignment Decision Diagram: ADD
）[5]
で表現したものを対象にテス ト系列を生成している．具体的には，各機能要素 のテスト環境[6]
を生成し，各機能要素のゲートレ ベル回路に対する縮退故障テストパターンをテス ト環境に代入することでテスト系列を生成してい る．これらの手法は，従来のゲートレベルテスト 生成と比較し高速にテスト生成ができ，高い故障 検出率を得ることができている．一方，近年
SAT-solver
の処理速度の高速化に伴 い，テスト生成技術などの論理関数を処理する分 野で，充足可能性問題（Satisfiability Problem:
SAT
）を利用した手法が提案されている[7][8]
． 本稿ではADD
の機能要素ごとにクリティカル パスを定義し，このパスの組合せに対してSAT
を 用いてパス遅延故障のテスト生成法を提案する．これにより，回路全体のパス遅延故障を網羅的に テストできるようなテストパターンを高速に生成 することを目指す．
2 ADD
（Assignment Decision Diagram
） 本論文の対象である割当決定図（Assignment Decision Diagram: ADD
）にていて説明する．ADD
は，図1
のように4
つの要素から構成され ている：割当値，割当条件，割当決定，割当対象．さらにこれらは，
4
つのノードで構成されてい る：演算ノード，読込みノード，書込みノード，割 当 決 定 ノ ー ド （
Assignment Decision Node:
ADN
）．ADD
の動作は以下の通りである．論理演 算で計算される割当条件により，ADN
の条件入 力の一つが真になる．条件入力に対応する値入力 が選択され，論理演算で計算された割当値が割当 対象に入力される．Evaluation of Detection Conditions for Path Delay Faults in RTL Operation Units
Ryoichi INOUE, Toshinori HOSOKAWA, and Hideo FUJIWARA
=
!
<
Q P
R ST0
割当条件 割当値
割当決定 a 7 State Register
&
+ -
&
CC
V V
割当対象
-読込みノード -書込みノード -演算ノード -割当決定
ノード（AND）
-値入力 -条件入力 V
C
図
1
：ADD
表
1:
論理ゲートのCNF
変換規則ゲートタイプ 入力 出力
CNF
AND
X YZ
(￢Z+X)・(￢Z+Y)・(￢X+￢Y+ Z)OR
X YZ
(Z+￢X)・(Z+￢Y)・(X+Y+￢Z)NAND
X YZ
(Z+X)・(Z+Y)・(￢X+￢Y+￢Z)NOR
X YZ
(￢Z+￢X)・(￢Z+￢Y)・(X+Y+Z)NOT X
Y(X+Y)・(￢X+￢Y)
ADD
は本来，動作合成に用いるために導入され たものであるが，機能記述RTL
回路を表現する データ構造として用いることもできる．コントロ ーラとデータパスを一様に表現できるため，コン トローラとデータパスを分離せずにテスト生成を 行うモデルとして適している．3
パス遅延テストライブラリパス遅延テストライブラリは，
ADD
のノードご とに仮論理合成を行う．生成した論理回路のクリ ティカルパスに対するパス遅延故障の検出条件を 保存する．検出条件は和積標準形論理式（
Conjunctive Normal Form: CNF
）で表現する．3.1
でSAT
について述べ，3.2
で論理回路のCNF
変換について述べ，3.3
でADD
の演算ノードの一 つである加算ノードを例にパス遅延故障テストラ イブラリを示す．3.1 SAT
（Satisfiability Problem
）SAT
とはCNF
が与えられたときに，それに含 まれる全ての変数の値に1
（真）または0
（偽）を定めることで，全体の値を真にできる割り当て が存在するか否かを判定する問題である．
SAT
はCNF
を入力として問題を解決するため，問題をCNF
に置き換える必要がある．3.2
論理回路のCNF
変換表
1
に各論理ゲートのCNF
変換規則を示す．各論理ゲートは表
1
の規則に従いCNF
に変換さ れる．それぞれの括弧でくくられた論理和式を節b
1a
0b
0a
1z
2z
0z
1G1 G2
G3 G4 G5
G6 d
e
f g i
h k
j c
図
2
：2bit
加算器のゲートレベル回路信号名 1パターン目 2パターン目
b
10 1
c 1 1
d 1 0
e 0 1
f X 1
g 1 0
h X 1
i 0 1
j 1 1
k 1 0
z
10 1
CNF
￢b1・c・d・￢e・g・￢i・j・k・￢z1
b
1・c・￢d・e・f・￢g・h・i・j・￢k・￢z1 表
2
：パス遅延故障の検出条件例といい，節を論理積した式が各ゲートの
CNF
で ある．例として2
入力（X , Y
）1
出力（Z
）のAND
ゲートを考える．全体の値が真になるのは(X
，Y
，Z) = (0
，0
，0)
，(0
，1
，0)
，(1
，0
，0)
，(1
，1
，1)
の４通りだけである．これにより，CNF
が実際 の論理ゲートの動作を表現していることがわかる．回路全体の
CNF
は各論理ゲートのCNF
を論理積 することで表現できる．3.3
パス遅延テストライブラリ作成手順 クリティカルパスに対する立ち上り遅延故障と 立ち下がり遅延故障の検出条件を抽出し．その条 件をCNF
で表現したものをパス遅延テストライ ブラリとする．クリティカルパスの本数はパラメ ータで設定する．2bit
加算ノードの例を用いて説明する．本稿で はロバスト[1]
条件で検出可能なパス遅延故障を 対象にする． 図2
に2bit
加算ノードを論理合成 した例を示す．a = {a
0, a
1}, b = {b
0, b
1}
は外部入 力，z = {z
0, z
1, z
2}
は外部出力を表している．1
本のパス(b
1, G1, d, G2, e, G3, g, G4, i, G5, k,
G6, z
1)
をクリティカルパスであると仮定する．G1
，G2
，G3
，G4
，G5
，G6
はクリティカルパス 上の論理ゲートを表している．c
，d
，e
，f
，g
，h
，i
，j, k
はクリティカルパス上の論理ゲートの入出 力信号線を表している．クリティカルパスに対す る，立ち上り遅延故障を検出するための1
パター ン目と2
パターン目の条件と，その条件をCNF
で 表現したものを表2
に示す．表2
において，X
は ドントケアを表している．4 RTL
情報を用いたパス遅延故障テスト生 成本テスト生成法のねらいについて
4.1
で述べ，4.2
で本テスト生成方法の戦略について述べる．4.1
ねらい回路全体を論理合成しパス遅延テストを行う場 合，パス数が膨大なためクリティカルパスに限定 してテスト生成をする必要がある．この場合，回 路全体のパスを網羅的にテストできているとはい えない．
ADD
のノードは論理合成される際に，演 算器バインディングにより複数のノードが一つの 演算器に割り当てられる可能性がある．ADD
のノ ードを仮論理合成した論理回路に対するパス遅延 障テストパターンは，論理合成し演算器バインデ ィングされた回路全体のパス遅延故障にも有効で あると考える．加えて，回路全体のパス遅延故障 を網羅的に検出できると考える．そこで，本手法 では，パス遅延テストライブラリで指定されたパ スの範囲内でパスを組み合わせてSAT
を用いて テスト生成をおこなう．これにより，高速に回路 全体のゲートレベル回路のクリティカルパスを含 むパスを網羅的にテストできるテストパターンが 得られると予測する．生成したテストパターンで ゲートレベルのクリティカルパスが全て検出でき なかった場合，検出できなかったクリティカルパ スに対してテスト生成を行う．この場合，対象と するパスが大幅に減少するため，短い時間でテス ト生成ができると考えられる．4.2
テスト生成戦略テスト生成戦略について説明する．全体テスト 生成フローを図
3
に示す．全体テストフロー中の パス遅延テストライブラリの作成フローを図4
に 示す．(STEP1)
ADD
を入力とし，回路全体をCNF
で表現する．(STEP2)
ADD
の読込みノードから書込みノードまでのパ スを抽出しパスの集合を生成する．(STEP3)
ADD
のノードごとにパス遅延テストライブラリ を作成する．STEP4
～STEP8
で詳細に記述する．(STEP4)
ADD
のノードを種類ごとに仮に論理合成し論理 回路生成する．(STEP5)
生成した論理回路のパスの集合を生成する．
(STEP6)
論理回路の回路情報を
CNF
として生成する．(STEP7)
論理回路のパスの集合からクリティカルパスを選 択してクリティカルパスの集合を生成する．クリ ティカルパスの本数はパラメータで設定する．
(STEP8)
パス遅延故障の検出条件を
CNF
として生成し，パス遅延テストライブラリに格納する．
(STEP9)
回路全体の
CNF
とパス遅延テストライブラリを 入力とし，SAT-solver
を実行することでテスト生 成をおこなう．STEP2
で作成したパスの集合とパ ス遅延テストライブラリの組合せ分実行する．5
おわりに本稿では，
RTL
の情報を用いて回路全体のパス 遅延故障を網羅的にテストするための，高速テス ト生成法を提案した．今後の課題として，本手法を実装し，生成され たパターンでどれだけ回路全体のパス遅延故障を 検出できるかを検証する必要がある．
「参考文献」
[1] A. Krstic, and K. T. Cheng, "Delay Fault
Testing for VLSI Circuits," Kluwer Academic Publishers, 1998.
[2] Yuki Yoshikawa, Satoshi Ohtake and
Hideo Fujiwara, "RTL don’t care path
identification and synthesis for
transforming don’t care paths into false
paths," Digest of Papers IEEE 8th
CNF作成（回路全体）
パス遅延テストライブリ 作成（各RTLプリミティブ）
テストパターン CNF
（プリミティブ回 路）
RTL-ADD CNF
（回路全体）
CNF
（パス遅延故障 検出条件）
パスの集合
（RTL）
読込みノードから書込みノード のパス抽出
START
END パス遅延故障テスト生成
STEP1
STEP2
STEP9 STEP3
ゲートレベル回 路
パスの集合
（GL）
CNF
（プリミティブ回 路）
クリティカルパ スの集合
CNF
（パス遅延故障 検出条件）
パスの集合生成
クリティカルパス抽出
CNF生成（回路情報）
論理合成 START
END CNF生成
（パス遅延故障検出条件）
STEP4
STEP5 STEP6
STEP7 STEP8
図
