InvitedTalk@FTC2011ja 最近の更新履歴 Hideo Fujiwara InvitedTalk@FTC2011

(1)

第６４回 FTC 研究会（２０１１年１月２０日 ^２２日）

テスト生成アルゴリズムとベンチマークの歴史

半世紀の歩み

藤原秀雄

奈良先端科学技術大学院大学情報科学研究科〒630-0192 生駒市高山町 8916-5

E-mail: [email protected]

あらまし R.D.Eldred がテスト生成に関する世界で最初の論文を 1959 年の Journal

of ACM に発表してからちょうど半世紀が過ぎました。その間、数多くの優れたテスト

生成アルゴリズムが研究開発され、今日の半導体産業を支える多くの優れた ATPG ツー

ルに至っています。本講演では、テスト生成アルゴリズムの歴史を振り返り、個性豊

かなアルゴリズムが次々と研究開発されて来た半世紀の歩みを紹介します。また、そ

れらの活発な研究の起爆剤となった ISCAS85, ISCAS89, ITC99 のベンチマークがどのよ

うに作られ、多くの研究者に役立って来たか、その歴史についても紹介します。

History of Test Generation Algorithms and Benchmarks

– Half a Century of the Progress –

Hideo FUJIWARA

Graduate School of Information Science, Nara Institute of Science and Technology

8916-5 Takayama, Ikoma, Nara, 630-0192 Japan

E-mail: [email protected]

Abstract Half a century has passed since R. D. Eldred published the first paper on test

generation in Journal of ACM in 1959. Until now, many excellent algorithms for test generation

have been reported and they have come to many excellent ATPG tools supporting today’s

semiconductor industries. In this talk, looking back on the long history of test generation

algorithms, we introduce those excellent and unique ATPG algorithms that appeared and

contributed in the progress of half a century. We also introduce the history of benchmarks of

ISCAS85, ISCAS89, and ITC99 that became the trigger of those active and animated research

and development.

(2)

生成ンチ史

〜半世紀歩〜

良先端科学技術大学院大学

情報科学研究科

藤原雄

2011 ^年 1 20-22 ^日

第回FTC研究会

話内容

履書

生成史

余談 _(FAN, 非キャン ₎

ンチ史

(3)

話内容

履書

生成史

余談 _(FAN, 非キャン ₎

ンチ史

1974 ^年 4

阪大大学院工学研究科博士課程了

1985 ^年 4

阪大工学部電子工学科

1993 ^年 4

良先端大情報科学研究科

明治大理工学部情報科学科

2011 ^年 3

五十代四十代十代

(4)

1974 ^年 4

1985 ^年 4

阪大

1993 ^年 4

良先端大

明治大

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

自分気入い

研究成果

TC: Trans. on Computers

TCAD: Trans. on Computer-

Aided-Design

MIT Press

IEEE TC (Complexity+DFT)

2000

IEEE TCAD (ATPG)

2001

IEEE TCAD (DFT)

2008

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

2001

IEEE TCAD (DFT)

2008

阪大

良先端大

明治大

IEEE TCAD (ATPG)

H. Fujiwara, et al., "Easily testable sequential machines

with extra inputs," IEEE Trans. on Computers,1975.

キャン設計理論的研究

自分気入い

研究成果

(5)

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

2001

IEEE TCAD (DFT)

2008

阪大

良先端大

明治大

IEEE TCAD (ATPG)

H. Fujiwara, et al., "A design of programmable logic arrays

with universal tests," IEEE Trans. on Computers, 1981.

Edward McCluskey ^教授 ^気 ^入 ^論文

そ後 _Stanford 大 _PLA _DFT 研究行わ

自分気入い

研究成果

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

2001

IEEE TCAD (DFT)

2008

阪大

良先端大

明治大

IEEE TCAD (ATPG)

H. Fujiwara, et al., "The complexity of fault detection problems

for combinational circuits," IEEE Trans. on Computers, 1982.

当時最高速 _FAN 発明元理論的論文

自分気入い

研究成果

(6)

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

2001

IEEE TCAD (DFT)

2008

阪大

良先端大

明治大

IEEE TCAD (ATPG)

H. Fujiwara, et al., "On the acceleration of test generation

algorithms," IEEE Trans. on Computers, 1983.

FAN , ^{当時世界最高速} ^国内外 ^多 ^企業 ^採用

自分気入い

研究成果

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

2001

IEEE TCAD (DFT)

2008

阪大

良先端大

明治大

IEEE TCAD (ATPG)

Hideo Fujiwara, “Logic Testing and Design for Testability,”

The MIT Press, 1985

海外大学キ使わ

自分気入い

研究成果

(7)

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

2001

IEEE TCAD (DFT)

2008

阪大

良先端大

明治大

IEEE TCAD (ATPG)

H. Fujiwara, "A new class of sequential circuits with

combinational test generation complexity,"

IEEE Trans. on Computers, 2000.

^新 ^い概念(^タ ^等価性) ^入， ^高度 DFT ^応用

自分気入い

研究成果

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

2001

IEEE TCAD (DFT)

2008

阪大

良先端大

明治大

IEEE TCAD (ATPG)

Emil Gizdarski, Hideo Fujiwara, "SPIRIT: A Highly

Robust Combinational Test Generation Algorithm,"

IEEE Trans. on Computer Aided Design, 2002.

^{当時世界最高速} ATPG

自分気入い

研究成果

(8)

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

2001

IEEE TCAD (DFT)

2008

阪大

良先端大

明治大

IEEE TCAD (ATPG)

Hideo Fujiwara, et al.,

"A Non-Scan Design-for-Testability for Register-Transfer Level

Circuits to Guarantee Linear-Depth Time Expansion Models,"

IEEE Trans. on Computer-Aided Design, 2008.

^新 ^い非 ^{キャン方式} キャン設計方式効

自分気入い

研究成果

1974 ^年 4

1985 ^年 4

阪大

1993 ^年 4

良先端大

明治大

2011 ^年 3

単独研究

研究教育

国内学会

研究

国学会

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

MIT Press

IEEE TC (Complexity+DFT)

2000

IEEE TC (ATPG)

2001

IEEE TCAD (DFT)

2008

(9)

話内容

履書

生成史

余談 _(FAN, 非キャン ₎

ンチ史

生成史

組合せ回路順序回路

D (Roth, IBM)

1981 PODEM (Goel, IBM)

1983 FAN

(Fujiwara & Shimono, 阪大) 1985 ISCAS85 benchmarks 1987 CONT (Takamatsu & Kinoshita) 1988 SOCRATES

(Schulz & Auth, Munich Inst.)

1992 Recursive Learning (Kunz, U.Hannover) SAT (Larrabee, Stanford)

1999 ITC99 benchmarks

2001 SPIRIT (Gizdarski & Fujiwara, NAIST)

1968 ^拡張D (Kubo, NEC)

1984 HITEST (Bending, Cirrus)

1989 ISCAS89 benchmarks 1986 (Marlett, HHB)

1988 CONTEST (Agrawal, Bell Lab.)

1991 HITEC (Sunrise TestGen) (Niermann & Patel, Illinois)

1995 遺伝

(Rudnick & Patel, Illinois)

1971 拡張D (Putzolu & Roth, IBM) 1978 ^値法(Muth)

1992 Real-value Simulation (Hatayama, et al. ^日立) 19 R. D. Eldred

1966 ^{次元経路活性化法}(Armstrong)

2008 SAT-based ATPG (Drechsler, et al. Univ. of Bremen )

2001 Functional RTL ATPG (Ghosh & Fujita, 富士通₎

ベンチマークについては、後ほど、

詳しく紹介いたします。

(10)

生成史

組合せ回路順序回路

D (Roth, IBM)

1983 FAN

1995 遺伝

1966 ^年 D (Roth, IBM)

与え故冗長あ否を定冗長い故あそを

検出すタンを常求完全

D ^最初 ^あ

年発表後 _IBM 使わ，日本各ンュタカ採

用．比較的効率いあ年以わ

D ^そ ^役目を果 ^ン ^ュ ^タ ^大規

模化伴い高速必要

1959 ^年 R.E. Eldred, Datamatic

組合せ回路生成を扱最初論文

真空管ンュタ Datamatic-1000 ^診断 ^適用

生成史

組合せ回路順序回路

D (Roth, IBM)

1983 FAN

1995 遺伝

1981 ^年 PODEM (Goel, IBM)

D ^全 ^異 ^発想 ^桁高速 ^新 ^い

を考案

1983 ^年 FAN (Fujiwara & Shimono, ^阪大

PODEM ^効率 ^良いい ^{発見的手法} ^ュ

を考案大型計算機ン実使わ大規模回路を

使実験を行い PODEM 数倍一桁以効率良いを示

そ後 _FAN を自動生成日本複

数企業開発使わう

(11)

生成史

組合せ回路順序回路

D (Roth, IBM)

1983 FAN

1995 遺伝

1988 ^年 SOCRATES (Schulz & Auth,

^ュン ^ン工科大

ISCAS85 ^ンチ ^年後 ^そ ^個 ^ン

チす対％故検出効率を達

成す初成功

1987 ^年 CONT (Takamatsu & Kinoshita

1992 ^年 Recursive Learning

(Kunz, U. Hannover)

生成史

組合せ回路順序回路

D (Roth, IBM)

1983 FAN

1995 遺伝

1992 ^年 SAT (Larrabee, Stanford)

SAT ^基 ^最初

年 SPIRIT (Gizdarski & Fujiwara, NAIST)

ITC99 ^ンチ ^現 ^以前 ISCAS85, ISCAS89 ^ン

チ回路す対当時生成

％故検出効率を達成い _ITC99 大規模ンチ

出現市販生成え％故

検出効率を達成い回路現そ後年

E.Gizdarski ^筆者 ^発表 SPIRIT ITC9 ^ンチ

対％故検出効率を達成す成功い

2008 ^年 SAT (Drechsler , Univ. of Bremen)

強力 _{SAT solver} 出現注目

(12)

生成史

組合せ回路順序回路

D (Roth, IBM)

1983 FAN

1995 遺伝

1968 ^{年拡張} D (Kubo, NEC)

NEC H.Kubo ^氏 D ^を順序

回路用拡張拡張 _D 発表

い興味深い， _D 発明

者 _J.P.Roth 同様拡張 _D

を年遅発表い点あ

生成け日本研究

非常高を示す良い事例

あ

1976 ^年 ^値法 (Muth, Univ. of Karlsruhe)

拡張 _D 系列存在す故対

常そ系列を生成限いそ意味

組合せ回路対完全 _D 順序回路

対完全いを解消

1978 ^年 P. Muth ^発表 ^値法 ^あ

値法そ発生確率拡張 _D

い特長あ

生成史

組合せ回路順序回路

D (Roth, IBM)

1983 FAN

1995 遺伝

1988 ^年 CONTEST ( ^研

組合せ回路対多成功事例あ

対，順序回路対そ非

常少いそ中知

研究所開発 _CONTEST

1991 ^年 HITEC ( ^ノ ^大

ノ大学 _J.H.Patel 開発

HITEC ^あ HITEC ^後 Sunrise ^社

TestGen ^採用 ^現在 Synopsys ^社

TetraMAX ^発展 ^い

1992 ^年 Real-value Simulation

(Hatayama, et al. ^日立 )

(13)

生成史

組合せ回路順序回路

D (Roth, IBM)

1983 FAN

1995 遺伝

2001 ^年 Functional RTL ATPG

(Ghosh & Fujita, ^富士通 )

設計流生成特

機能記述RTL 自動生成

話内容

履書

生成史

余談 _(FAN, 非キャン ₎

ンチ史

(14)

The basis is necessary for development

発展基礎必要

•  For a tree to grow larger, its root must grow bigger and deeper

into the ground.

 

Similarly, for test technologies (leaves) to develop, substantial

results of the fundamental research (root) are necessary.

 

The more enriched the fundamental research results become,

the more enriched the practical research results become.

Fundamental problems of testing

基本

What are the fundamentals of testing?

Fundamentals of testing ???

I had the opportunity to ask myself

the same question 28 years ago

when I was requested to write a book

from MIT Press.

(15)

Test Generation

Design for Testability

Fundamental problems of testing

基本

So, I decided to write a book with the following title.

Hideo Fujiwara, Logic Testing and Design for Testability,

The MIT Press, 1985

Fundamental problems of testing

基本

So, I decided to write a book with the following title.

Hideo Fujiwara, Logic Testing and Design for Testability,

The MIT Press, 1985

(16)

経験

理論的基礎的研究実用的研究貢献す

Polynomial Time Class ???

テスト生成複雑度解析

FAN algorithm

高速のテスト生成アルゴリズム

生成い代 _@ 阪大 ₎

容易化設計い ₍ 代 _@ 良先端大 ₎

順序回路の分類最適なテスト容易化設計 Acyclic

testability???

Non-scan DFT

経験

理論的基礎的研究実用的研究貢献す

FAN algorithm

testability???

Non-scan DFT

生成い代 _@ 阪大 ₎

容易化設計い ₍ 代 _@ 良先端大 ₎

(17)

•  Fault detection (FD): Is a given single stuck-at fault detectable?

kM-FD: Fault detection problem for k-level monotone circuits

kU-FD: Fault detection problem for k-level unate circuits

 

Theorem 1 :

3M-FD is NP-complete.

Hence,

3U-FD and FD are NP-complete.

Complexity of test generation

生成複雑度 [Fujiwara, et al, IEEE Trans. Comp, 1982]

•  A combinational circuit C is said to be k-bounded if there exists a partition

Π={B

₁

, B

₂

_{, …, B}

_t

} such that

(1) the number of inputs of each block Bi is at most k, and

(2) graph G

Π

has no cycle.

B

₁

_B

4

B

₂

B

₅

B

₃

G

_Π

Complexity of test generation

生成複雑度 [Fujiwara, et al, IEEE Trans. Comp, 1982]

(18)

• Theorem ^２ : Let C be a k-bounded circuit. Then there is an algorithm

of time complexity O ( 16

^k

m ) to find a test for a single stuck-at fault in C,

where m is the number of lines in C.

3-bounded circuit 6-bounded circuit

Complexity of test generation

生成複雑度 [Fujiwara, et al, IEEE Trans. Comp, 1982]

•  k-FL-FD: Fault detection problem for k-fanout-limited circuits

•  k-FPB-FD: Fault detection problem for k-fanout-point-bounded

circuits

k-fanout-limited k-fanout-point-bounded

 

Theorem 3 :

k-FL-FD is NP-complete if k>2.

k-FPB-FD is solvable in O(4

^k

m) where m is the number of lines in C.

この定理の証明で、分岐点(fanout-

point) に0,1,D, D’の４値を割り当てる

テスト生成アルゴリズムを示した。

このアルゴリズムが、後のFANアルゴ

リズムの元になった。

Complexity of test generation

生成複雑度 [Fujiwara, et al, IEEE Trans. Comp, 1982]

(19)

•  Observation:

k-FL-FD is NP-complete even if k is a constant.

k-FPB-FD is solvable in O(m) if k is a constant.

k-fanout-limited k-fanout-point-bounded

 

The complexity of test generation is affected

not by the number of fanout branches from a fanout point

but by the number of fanout points.

Complexity of test generation

生成複雑度 [Fujiwara, et al, IEEE Trans. Comp, 1982]

定理の証明で示したアルゴリズムが，FANアルゴリズム

の元になった。

テスト生成複雑度解析

FAN algorithm

高速のテスト生成アルゴリズム

Complexity of test generation

生成複雑度 [Fujiwara, et al, IEEE Trans. Comp, 1982]

(20)

•  Strategy 1: In each step of the algorithm, determine as many signal values as

possible that can be uniquely implied.

Heuristics of the FAN algorithm

[Fujiwara, et al, IEEE Trans. Comp., 1983]

38 •  Strategy 1: In each step of the algorithm, determine as many signal values as

possible that can be uniquely implied.

 

Strategy 2: Assign a fault signal D or D’ that is uniquely determined or implied by the

fault in question.

 

Strategy 3: When the D-frontier consists of a single gate, apply a unique

sensitization.

D-frontier becomes empty and backtrack occurs later

Heuristics of the FAN algorithm

[Fujiwara, et al, IEEE Trans. Comp., 1983]

Unique assignment can reduce backtracks

(21)

39 •  Strategy 1: In each step of the algorithm, determine as many signal values as

possible that can be uniquely implied.

 

Strategy 2: Assign a fault signal D or D’ that is uniquely determined or implied by the

fault in question.

 

Strategy 3: When the D-frontier consists of a single gate, apply a unique

sensitization.

 

Strategy 4: Stop the backtrace at a head line, and postpone the line justification for

the head line to later.

This can reduce backtracks

Heuristics of the FAN algorithm

[Fujiwara, et al, IEEE Trans. Comp., 1983]

•  Strategy 1: In each step of the algorithm, determine as many signal values as

possible that can be uniquely implied.

 

Strategy 2: Assign a fault signal D or D’ that is uniquely determined or implied by the

fault in question.

 

Strategy 3: When the D-frontier consists of a single gate, apply a unique

sensitization.

 

Strategy 4: Stop the backtrace at a head line, and postpone the line justification for

the head line to later.

 

Strategy 5: Multiple backtracing (concurrent backtracing of more than one path) is

more efficient than backtracing along a single path.

Heuristics of the FAN algorithm

[Fujiwara, et al, IEEE Trans. Comp., 1983]

This can reduce computation of backtrace as well as backtracks

(22)

•  Strategy 1: In each step of the algorithm, determine as many signal values as

possible that can be uniquely implied.

 

Strategy 2: Assign a fault signal D or D’ that is uniquely determined or implied by the

fault in question.

 

Strategy 3: When the D-frontier consists of a single gate, apply a unique

sensitization.

 

Strategy 4: Stop the backtrace at a head line, and postpone the line justification for

the head line to later.

 

Strategy 5: Multiple backtracing (concurrent backtracing of more than one path) is

more efficient than backtracing along a single path.

 

Strategy 6: In the multiple backtrace, if an objective at a fanout point p has a

contradictory requirement, stop the backtrace so as to assign a binary value to the

fanout point.

PODEM assigns a binary value only to primary inputs. So, backtracks occur at primary inputs.

FAN assigns a binary value only to head lines and fanout points. So, backtracks occur at headlines and fanout points.

This is effective to reduce the number of backtracks.

Heuristics of the FAN algorithm

[Fujiwara, et al, IEEE Trans. Comp., 1983]

経験

理論的基礎的研究実用的研究貢献す

FAN algorithm

順序回路の分類最適なテスト容易化設計

Acyclic testability???

Non-scan DFT

生成い代 _@ 阪大 ₎

容易化設計い ₍ 代 _@ 良先端大 ₎

(23)

Theoretically,

CTG is NP-hard.

Empirically,

CTG = Combinational Test

Generation Problem

T ime (u s)

Circuit size, n

Classification of sequential circuits

Combinational test generation complexity

CTG seems to be solved in time O(n

^r

)

for some constant r.

[ Goel 1980], [Prasad 1999]

•  Introduced ^τ

^k

^notation to clarify the time complexity for the

test generation problem."

•  Classiﬁed sequential circuits based on ^τ

^k

^notation ^.

τ ^k -equivalent τ ^k -bounded

Classification of sequential circuits

^τ ^k notation [Fujiwara, IEEE Trans. Comp., 2000]

[Fujiwara, et al, IEEE Trans. CAD, 2008]

(24)

•  Let

–  P

C

: combinational test generation problem.

–  P

S

: sequential test generation problem.

–  P

α

: class α test generation problem.

 

Let T

_C

(n), T

_S

(n) and T

_α

(n) be the time complexity of P

_C

, P

_S

and

P

_α

respectively.

 

We assume that T

_C

(n) = Θ(n

^r

) for some constant r larger than 2.

 

Combinational test generation complexity: τ(n) = T

_C

(n)

Classification of sequential circuits

Test generation complexity [Fujiwara, IEEE TCAD, 2008]

 

A class α is τ

^k

-equivalent if T

_α

(n)= Θ ( τ

^k

(n))

and τ

^k

–bounded if T

_α

(n)=O( τ

^k

(n))

where k is a positive integer.

 

A class of circuits with combinational test generation complexity

is τ-equivalent

Classification of sequential circuits

^τ ^k -equivalent and ^τ ^k -bounded [Fujiwara, IEEE TCAD, 2008]

(25)

Classification of sequential circuits

Class of acyclic test generation complexity

Acyclically-testable sequential circuits

[Ooi & Fujiwara, 2006]

Acyclic sequential circuits

[Ooi & Fujiwara, 2004]

Internally balanced sequential circuits

[Fujiwara, 2000]

Balanced sequential circuits

[Gupta et al., 1990]

τ -equivalent

τ

²

_-bounded

τ

²

-bounded

Cyclic sequential circuits

Classification of sequential circuits

Design for acyclic testability

 

Introduced two classes of acyclically-testable circuits

 

Proposed Non-Scan type DFT for acyclic testability

 

Thru-testable circuits (at gate level)

[C.Y.Ooi, H.Fujiwara, ICCD 2006]

 

Linear-depth time-bounded circuits (at RTL)

[H.Iwata, T.Yoneda, H.Fujiwara, DAC 2007]

 

Non-scan

 

At-speed test

 

100% fault efficiency

 

Hardware overhead is lower than Full Scan

 

Test application time is much shorter than Full Scan

(26)

Design for acyclic testability

[Fujiwara, et al, IEEE Trans. CAD, 2008]

Circuit Characteristics

# of gates # of flip-flops

•  Linear-depth time-bounded RTL circuits

Hardware Overhead

[%]

•  Linear-depth time-bounded RTL circuits

Average overhead is

24.0%

Average overhead is

5.9%

Design for acyclic testability

[Fujiwara, et al, IEEE Trans. CAD, 2008]

(27)

•  Linear-depth time-bounded RTL circuits

51 Fault Efficiency

[%] For large original circuits,

high fault efficiency

cannot be obtained

Design for acyclic testability

[Fujiwara, et al, IEEE Trans. CAD, 2008]

Full scan & Proposed Non-Scan

can achieve

almost 100% fault efficiency

•  Linear-depth time-bounded RTL circuits

GCD Circuits

LWF JWF Paulin RISC MPEG

Test Generation Time [sec] Original Full Scan

3,070.07 85.45 2,873.34 4,290.51 156,808.67 195,260.82

1.72 1.01 5.91 8.07 166.88 1,208.90 0.27 0.17 0.88 0.53 98,870.71 55.72

Proposed Non Scan

Test Gneration Time [sec]

For original circuits,

test generation is

very time-consuming,

even for

low fault efficiency For full scan & proposed non-scan,

test generation is very fast

Design for acyclic testability

[Fujiwara, et al, IEEE Trans. CAD, 2008]

(28)

•  Linear-depth time-bounded RTL circuits

GCD Circuits

LWF JWF Paulin RISC MPEG

Original

Test Application Time [clock] Full Scan 421 392 412 201 6,928 148

588 108 675 798 4,345 8,515 4,232 2,904 20,975 6,147 1,233,859 462,942

Proposed Non Scan

Test Application Time [clock]

1000000

Design for acyclic testability

Test application time [Fujiwara, et al, IEEE Trans. CAD, 2008]

is very long

for full scan

Test application time

for full scan is

284 times longer than

proposed non-scan

for RISC,

and 54 times longer

for MPEG

FAN algorithm

生成い

容易化設計い

testability???

Non-scan DFT

経験

理論的 _• 基礎的研究実用的研究貢献す

実例を紹

(29)

話内容

履書

生成史

余談 _(FAN, 非キャン ₎

ンチ史

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

(30)

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

ンチけ

FAN ^発表

13

^th

International Symposium on Fault-Tolerant Computing

June 28-30, 1983 Palazzo Ex-Stelline, Milano, Italy

FTCS−

● H.Fujiwara, T. Shimono (Osaka Univ.)

● E. Fujiwara (NTT)

● T. Nanya, Y. Thoma (TIT)

● K. Yoshihara, Y.Koga, T. Ishihara (NDA)

● K.Furuya, Y. Akita, Y. Thoma (TIT)

(31)

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

McGill ^大学 ^{在外研究中} Franc Brglez ^当時 Bell Northern Research, ^現

在 North Carolina State University ^教授 ^会う

当時新い生成を提案，性能を比較す標準

的ンチ自分回路けを使性能を評価す

客観的性能評価．そ _Franc

Brglez ^年京都 ^開催 ^国 ^会議 ISCAS’ 85 ^い ^組合せ回

路を対象生成ンチ特ョンを企画

在外研究年 ₍₁₉₈₄ 年 Montreal ISCAS’84 ^開催 ^翌年 (1985 ^年 ^京都

ISCAS’85 ^{開催予定，} ^いう ^特 ^{ョンを提案}

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

Franc Brglez ^年京都 ^開催 ^国 ^会議 ISCAS’85 ^い

組合せ回路を対象生成ンチ特ョン

を企画日米企業大学協力を得個組合せ回路用ンチを

発表そンチを使協力いい企業大学保す

生成性能評価を行． _ISCAS85 ンチ起爆剤

そ後次々新い基性能い生成

発表続け

話 _…

(32)

1985 International Symposium on Circuits and Systems

June 5-7, 1985 Kyoto Hotel, Kyoto, Japan

ISCAS’85

Franc Brglez

ンチけ

FAN ^発表

1985 International Symposium on

Circuits and Systems

ISCAS’85

(33)

1985 International Symposium on Circuits and Systems

ISCAS’85

Co-Chairs: F. Brglez, H. Fujiwara

M. Kawai, et al. NEC Corp.

H. Fujiwara, Meiji Univ.

Y. Takamatsu, Saga Univ.,

K. Kinoshita, Hiroshima Univ.

M. Murakami, Oki Electric

1985 International Symposium on Circuits and Systems

ISCAS’85

(34)

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

ISCAS85 ^ンチ ^発表 ^年後 ^{，順序回路用} ^ンチ

必要性問わ

ITC’88@WashingtonDC ^記 ^ン ^集

Franc Brglez (MCNC, Microelectronics Center of North Carolina)

Vishwani Agrawal (AT&T Bell Labs)

Balaji Krishnamurthy (Tektronix Labs)

Hideo Fujiwara (Meiji Univ.)

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

再度国会議 _ISCAS’89 い順序回路を対象生成

ンチ特ョンを企画

ISCAS89 ^ンチ ^あ

回 Balaji Krishnamurthy (Tektronix Labs) ^中心

Organizer/Chair Balalji ^や

(35)

ンチ提供協力者

1989 International Symposium on Circuits and Systems

1989 Portland, Oregon

ISCAS’89

Chairs: B. Krishnamurthy, H. Fujiwara

T. Hayashi, Hitachi Research Laboratory

(36)

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

生成用ンチ _ISCAS85 ンチ

を第世代考え _ISCAS89 ンチ第世代

考えそ後，生成対象回路規模

増大一歩を大規模現実的新いンチ

必要性を問う H. Fujiwara ”Needed, Third-generation

ATPG benchmarks”, The Last Byte, IEEE Design & Test of

Computers, p.96, 1998.

(37)

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

The Last Byte ^編集者 Scott Davidson

を書う依頼

記事掲載後

年 Scott Davidson ^国 ^会議 ITC’99 (International

Test Conference 1999) ^い ^第 ^世代 ^呼 ^新 ^い ^ンチ

特ョン企画 _ITC99 ンチ

あ

(38)

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

1983 ^年 (37 ) FAN FTCS-13@Milano

ンチ史

1984 ^年 (38 ) ^在外研究 McGill Univ.@Montreal

1985 ^年 (39 ) ISCAS’85 ^ンチ ISCAS’85@ ^京都

1988 ^年 (42 ) Lunch Meeting ITC’88@Washington D.C.

1989 ^年 (43 ) ISCAS’89 ^ンチ ISCAS’89@Portland,Oregon

1998 ^年 (52 ) The Last Byte H.Fujiwara@IEEE_Design&Test

1999 ^年 (53 )

2010 ^年 (64 ) The Last Byte R.Aitken@IEEE_Design&Test

ITC’99 ^ンチ ITC’99@Atlantic City, NJ

ISCAS’85 ^ンチ ^発表

四半世紀年経過昨年 _IEEE

Design&Test The Last Byte

面白い記事掲載

(39)

On a June day 25 years ago, Franc Brglez and

Hideo Fujiwara forever changed the world of

design and test of computers. ……

……. The ISCAS85 benchmarks

Yet, despite their astounding and undeniable success,

as we approach the benchmarks’ silver anniversary,

I would like to suggest that it is time for them to retire.

How many students in 1985 would have wanted

a set of benchmark circuits from 1960?

(40)

So, I’m asking you to join me in a toast.

To the ISCAS85 benchmarks,

a wonderfully successful set of circuits:

may they pass quietly into history.

“Time to retire our benchmarks”

-- Rob Aitken, 2010

(41)

“Time to retire our benchmarks”

-- Rob Aitken, 2010

“Time to retire Fujiwara”

-- Hideo Fujiwara, 2011

最後

余談 _FAN, 非キャン

経験談を話う

実用研究理論的チすわ

理論を実用応用す研究タ

自由理論研究を楽

そ成果を世中役立実用研究応用

世中貢献す

大学そ研究タ

(42)

清聴

あうい

InvitedTalk@FTC2011ja 最近の更新履歴 Hideo Fujiwara InvitedTalk@FTC2011

第６４回 FTC 研究会（２０１１年１月２０日 ２２日）

テスト生成アルゴリズムとベンチマークの歴史

半世紀の歩み

藤原 秀雄

奈良先端科学技術大学院大学 情報科学研究科 〒630-0192 生駒市高山町 8916-5

E-mail: [email protected]

あ ら ま し R.D.Eldred がテスト生成に関する世界で最初の論文を 1959 年の Journal

of ACM に発表してからちょうど半世紀が過ぎました。 その間、数多くの優れたテスト

生成アルゴリズムが研究開発され、 今日の半導体産業を支える多くの優れた ATPG ツー

ルに至っています。 本講演では、テスト生成アルゴリズムの歴史を振り返り、個性豊

かなアルゴリズムが次々と研究開発されて来た半世紀の歩みを紹介します。 また、そ

れらの活発な研究の起爆剤となった ISCAS85, ISCAS89, ITC99 のベンチマークがどのよ

うに作られ、多くの研究者に役立って来たか、その歴史についても紹介します。

History of Test Generation Algorithms and Benchmarks

– Half a Century of the Progress –

Hideo FUJIWARA

Graduate School of Information Science, Nara Institute of Science and Technology

8916-5 Takayama, Ikoma, Nara, 630-0192 Japan

E-mail: [email protected]

Abstract Half a century has passed since R. D. Eldred published the first paper on test

generation in Journal of ACM in 1959. Until now, many excellent algorithms for test generation

have been reported and they have come to many excellent ATPG tools supporting today’s

semiconductor industries. In this talk, looking back on the long history of test generation

algorithms, we introduce those excellent and unique ATPG algorithms that appeared and

contributed in the progress of half a century. We also introduce the history of benchmarks of

ISCAS85, ISCAS89, and ITC99 that became the trigger of those active and animated research

and development.

生成 ンチ 史

〜 半世紀 歩 〜

良先端科学技術大学院大学

情報科学研究科

藤原 雄

2011 年 1 20-22 日

第 回FTC研究会

話 内容

履 書

生成 史

余談 (FAN, 非 キャン )

ンチ 史

話 内容

履 書

生成 史

余談 (FAN, 非 キャン )

ンチ 史

1974 年 4

阪大 大学院 工学研究科 博士課程了

1985 年 4

阪大 工学部 電子工学科

1993 年 4

良先端大 情報科学研究科

明治大 理工学部 情報科学科

2011 年 3

1974 年 4

1985 年 4

阪大

1993 年 4

良先端大

明治大

2011 年 3

IEEE TC (DFT)

1975

IEEE TC (DFT)

1981

IEEE TC (Complexity)

1982

IEEE TC (ATPG)

1983

自分 気 入 い

研究成果

TC: Trans. on Computers

TCAD: Trans. on Computer-

Aided-Design

MIT Press

IEEE TC (Complexity+DFT)

2000

IEEE TCAD (ATPG)

2001

IEEE TCAD (DFT)

2008

第６４回 FTC 研究会（２０１１年１月２０日 ^２２日）

藤原秀雄

奈良先端科学技術大学院大学情報科学研究科〒630-0192 生駒市高山町 8916-5

あらまし R.D.Eldred がテスト生成に関する世界で最初の論文を 1959 年の Journal

of ACM に発表してからちょうど半世紀が過ぎました。その間、数多くの優れたテスト

生成アルゴリズムが研究開発され、今日の半導体産業を支える多くの優れた ATPG ツー

ルに至っています。本講演では、テスト生成アルゴリズムの歴史を振り返り、個性豊

かなアルゴリズムが次々と研究開発されて来た半世紀の歩みを紹介します。また、そ

生成ンチ史

〜半世紀歩〜

藤原雄

2011 ^年 1 20-22 ^日

第回FTC研究会

話内容

履書

生成史

余談 _(FAN, 非キャン ₎

ンチ史

話内容

履書

生成史

余談 _(FAN, 非キャン ₎

ンチ史

1974 ^年 4

阪大大学院工学研究科博士課程了

1985 ^年 4

阪大工学部電子工学科

1993 ^年 4

良先端大情報科学研究科

明治大理工学部情報科学科

2011 ^年 3

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

自分気入い

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

キャン設計理論的研究

自分気入い

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3

Edward McCluskey ^教授 ^気 ^入 ^論文

そ後 _Stanford 大 _PLA _DFT 研究行わ

自分気入い

1974 ^年 4

1985 ^年 4

1993 ^年 4

2011 ^年 3