ch14.5.htm

来自「介绍asci设计的一本书」· HTM 代码 · 共 1,043 行 · 第 1/3 页

 </A>
Iteration</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=118094">
 </A>
	Objective</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=79951">
 </A>
	Backtrace<SUP CLASS="Superscript">
1</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=79953">
 </A>
	Implication</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=79955">
 </A>
D-frontier</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79957">
 </A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=118091">
 </A>
	U3.A2 = 0</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79961">
 </A>
	J = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79963">
 </A>
	</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79965">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79967">
 </A>
2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79969">
 </A>
	U3.A2 = 0</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79971">
 </A>
	K = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79973">
 </A>
	U7.ZN = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79975">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79977">
 </A>
3</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79979">
 </A>
	U3.A1 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79981">
 </A>
	M = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79983">
 </A>
	U3.ZN = D</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79985">
 </A>
U4, U6</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79987">
 </A>
4</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79989">
 </A>
	U6.A2 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79991">
 </A>
	N = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79993">
 </A>
	U6.ZN = D</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79995">
 </A>
U4, U8</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79997">
 </A>
5a</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=79999">
 </A>
	U8.A1 = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=80001">
 </A>
	L = 0</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=80003">
 </A>
	U8.ZN = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=80005">
 </A>
U4, U8</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=80007">
 </A>
5b</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=80009">
 </A>
	Retry</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=80011">
 </A>
	L = 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=80013">
 </A>
	U8.ZN = D</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=80015">
 </A>
A</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="5">
<P CLASS="TableLeft">
<A NAME="pgfId=118066">
 </A>
<SUP CLASS="Superscript">
1</SUP>
Backtrace is not the same as retry or backtrack.</P>
<P CLASS="TableLeft">
<A NAME="pgfId=135188">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="5">
<P CLASS="TableFigTitleSide">
<A NAME="pgfId=118056">
 </A>
FIGURE&nbsp;14.20&nbsp;<A NAME="15623">
 </A>
The PODEM (path-oriented decision making) algorithm.</P>
</TD>
</TR>
</TABLE>
</OL>
<P CLASS="Body">
<A NAME="pgfId=79857">
 </A>
We can see that the PODEM algorithm proceeds in two phases. In the first phase, iterations 1 and 2 in <A HREF="CH14.5.htm#15623" CLASS="XRef">
Figure&nbsp;14.20</A>
, the objective is fixed in order to activate the fault. In the second phase, iterations 3&#8211;5, the objective changes in order to propagate the fault. In step 3 of the PODEM algorithm there must be at least one path containing unknown values between the gates of the D-frontier and a PO in order to be able to complete a sensitized path to a PO. This is called the <SPAN CLASS="Definition">
X-path check</SPAN>
<A NAME="marker=95622">
 </A>
.</P>
<P CLASS="Body">
<A NAME="pgfId=80869">
 </A>
You may wonder why there has been no explanation of the backtrace mechanism or how to decide a value for a PI in step 2 of the PODEM algorithm. The decision tree shown in <A HREF="CH14.5.htm#15623" CLASS="XRef">
Figure&nbsp;14.20</A>
 shows that it does not matter. PODEM conducts an implicit binary search over all the PIs. If we make an incorrect decision and assign the wrong value to a PI at some step, we will simply need to retry that step. Texts, programs, and articles use the term <SPAN CLASS="Emphasis">
backtrace</SPAN>
 as we have described it, but then most use the term <SPAN CLASS="Definition">
backtrack</SPAN>
<A NAME="marker=80788">
 </A>
 to describe what we have called a retry, which can be confusing. I also did not explain how to choose the objective in step 1 of the PODEM algorithm. The initial objective is to activate the fault. Subsequently we select a logic gate from the D-frontier and set one of its inputs to the enabling value in an attempt to propagate the fault. </P>
<P CLASS="Body">
<A NAME="pgfId=81704">
 </A>
We can use intelligent procedures, based on <SPAN CLASS="Emphasis">
controllability</SPAN>
 and <SPAN CLASS="Emphasis">
observability</SPAN>
, to guide PODEM and reduce the number of incorrect decisions. PODEM is a development of the D-algorithm, and there are several other ATPG algorithms that are developments of PODEM. One of these is <SPAN CLASS="Definition">
FAN</SPAN>
<A NAME="marker=80757">
 </A>
<A NAME="marker=80758">
 </A>
 (<SPAN CLASS="Definition">
fanout-oriented test generation</SPAN>
<A NAME="marker=80756">
 </A>
) that removes the need to backtrace all the way to a PI, reducing the search time [<A NAME="Fujiwara and Shimono, 1983">
 </A>
Fujiwara and Shimono, 1983; <A NAME="[Schulz,   Trischler, and Sarfert, 1988]">
 </A>
Schulz, Trischler, and Sarfert, 1988]. Algorithms based on the D-algorithm, PODEM, and FAN are the basis of many commercial ATPG systems.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=53440">
 </A>
14.5.4&nbsp;<A NAME="17491">
 </A>
Controllability and Observability</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=53441">
 </A>
In order for an ATPG system to provide a test for a fault on a node it must be possible to both control and observe the behavior of the node. There are both theoretical and practical issues involved in making sure that a design does not contain buried circuits that are impossible to observe and control. A software program that measures the <A NAME="marker=53442">
 </A>
<SPAN CLASS="Definition">
controllability</SPAN>
 (with three<SPAN CLASS="Emphasis">
 l&#8217;</SPAN>
s) and <A NAME="marker=81537">
 </A>
<SPAN CLASS="Definition">
observability</SPAN>
 of nodes in a circuit is useful in conjunction with ATPG software. </P>
<P CLASS="Body">
<A NAME="pgfId=81753">
 </A>
There are several different measures for controllability and observability [<A NAME="Butler and Mercer, 1992">
 </A>
Butler and Mercer, 1992]. We shall describe one of the first such systems called <SPAN CLASS="Definition">
SCOAP</SPAN>
<A NAME="marker=81615">
 </A>
<A NAME="marker=81617">
 </A>
 (<SPAN CLASS="Definition">
Sandia Controllability/Observability Analysis Program</SPAN>
<A NAME="marker=81616">
 </A>
) [<A NAME="Goldstein, 1979">
 </A>
Goldstein, 1979]. These measures are also used by ATPG algorithms.</P>
<P CLASS="Body">
<A NAME="pgfId=81277">
 </A>
<SPAN CLASS="Definition">
Combinational controllability</SPAN>
<A NAME="marker=81278">
 </A>
 is defined separately from <SPAN CLASS="Definition">
sequential controllability</SPAN>
<A NAME="marker=81279">
 </A>
. We also separate <SPAN CLASS="Definition">
zero-controllability</SPAN>
<A NAME="marker=81280">
 </A>
 and <SPAN CLASS="Definition">