(12) United States Patent
`Boubezari et ai.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006363520Bl
`US 6,363,520 BI
`Mar. 26,2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) METHOD FOR TESTABILITY ANALYSIS
`AND TEST POINT INSERTION AT THE
`RT-LEVEL OF A HARDWARE
`DEVELOPMENT LANGUAGE (HDL)
`SPECIFICATION
`
`(75)
`
`Inventors: Samir Boubezari, Mountain View, CA
`(US); Eduard Cerny; Bozena
`Kaminska, both of Montreal (CA);
`Benoit Nadeau-Dostie, Aylmer (CA)
`
`(73) Assignee: LogicVision, Inc., San Jose, CA (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.c. 154(b) by 0 days.
`
`(21) AppI. No.: 09/098,555
`
`(22) Filed:
`
`Jun. 16, 1998
`
`C.H. Chen et aI., An Approach to Functional Level Test(cid:173)
`ability Analysis, 1989 International Test Conference, pp.
`373-380, Aug. 1989.*
`C.H. Chen et aI., Behavioral Synthesis for Testability, 1992
`IEEE/ACM International Conference on Computer-Aided
`Design, pp. 612-615, Nov. 1992. *
`c.P. Ravikumar et aI., HISCOAP: A Hierarchical Testability
`Analysis Tool, 8th International Conference on VLSI
`Design, pp. 272-277, Jan. 1995. *
`Y. Fang et aI., Efficient Testability Enhancement for Com(cid:173)
`binational Circuit, 1995 International Conference on Com(cid:173)
`puter Design, pp. 168-172, Oct. 1995.*
`S. Boubezari et aI., Testability Analysis and Test-Point
`Insertion in RTL VHDL Specifications for Scan-Based
`BIST, IEEE Transactions on Computer-Aided Design of
`Integrated Circuits and Systems, pp. 1327-1340, Sep.
`1999.*
`
`(List continued on next page.)
`
`(51)
`
`Int. CI? ......................... G06F 17/50; G06F 17/10;
`G06F 7/60
`(52) U.S. CI. .................................. 716/18; 716/2; 716/4
`(58) Field of Search ........................................ 716/18, 4
`
`Primary Examiner-Matthew Smith
`Assistant Examiner-A. M. Thompson
`(74) Attorney, Agent, or Firm-Sheridan Ross P.c.
`
`(57)
`
`ABSTRACT
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,791,578 A * 12/1988 Fazio et al. ................. 364/488
`5,043,986 A
`8/1991 Agrawal et al. ........... 371/25.1
`5,329,533 A
`7/1994 Lin ........................... 371/22.3
`5,379,303 A * 1/1995 Levitt .......................... 371/27
`5,450,414 A
`9/1995 Lin ........................... 371/22.3
`5,513,123 A * 4/1996 Dey et al. ................... 364/489
`5,828,828 A * 10/1998 Lin et al. ............... 395/183.06
`6,038,691 A * 3/2000 Nakao et al. ............... 714/733
`
`OlliER PUBLICATIONS
`
`H. Fujiwara, Computational Complexity of Controllability/
`Observability Problems for Combinational Circuits, 18th
`International Symposium on Fault-Tolerant Computing, pp.
`64-69, Jun. 1988.*
`
`A method is provided for producing a synthesizable
`RT-Level specification, having a testability enhancement
`from a starting RT-Level specification representative of a
`circuit to be designed, for input to a synthesis tool to
`generate a gate-level circuit. The method includes the steps
`of performing a testability analysis on a Directed Acyclic
`Graph by computing and propagating Testability Measures
`forward and backward through VHDL statements, identify(cid:173)
`ing the bits of each signal and/or variable, and adding test
`point statements into the specification at the RT-Level to
`improve testability of the circuit to be designed. The com(cid:173)
`putation of Controllability and Observability method is
`purely functional, and does not subsume the knowledge of
`a gate-level implementation of the circuit being analyzed.
`
`36 Claims, 7 Drawing Sheets
`
`14
`
`~-.----,.('
`
`(
`I\~~ciflcatlon
`
`~_,,/""'2
`~DL analyzer
`VHDL Intermediate F~rmat (V~
`
`)
`" - -__ . - - - - / 18
`
`16 ,
`
`( Construction of DAG
`
`28
`
`)
`
`I
`
`2o~-T
`(
`Computation of TMs
`" - - r
`...LL
`24~_ '
`SufficlentTMs? ~mt insertion]
`t es
`Ge,ner~te modified '\
`(
`~HDLmodel
`
`26
`
`1
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`US 6,363,520 BI
`Page 2
`
`OlliER PUBLICATIONS
`
`M.H. Gentil et aI., A New High Level Testability Measure:
`Description and Evaluation, 12th IEEE VLSI Test Sympo(cid:173)
`sium 1994, pp. 421-426, Apr. 1994.*
`T.e. Lee et aI., Behavioral Synthesis for Easy Testability in
`Data Path Allocation, IEEE 1992 International Conference
`on Computer Design, pp. 29-32, Oct. 1992.*
`P. Vishakantaiah et aI., "AMBIANT': Automatic Generation
`of Behavioral Modifications for Testability", IEEE ICCD,
`pp. 63-66, Oct. 1993.
`S. Bhattacharya et aI., "Transformations and Resynthesis for
`Testability of RT -Level Control-Data Path Specifications",
`IEEE Trans. on (VLSI) Systems, vol. 1, No.3, Sep. 1993, 15
`pp.
`H. Chen et aI., "Structural and Behavioral Synthesis for
`Testability Techniques", IEEE Trans. on Cad, vol. 13, No.6,
`Jun. 1994.
`W. Mao et aI., "Improving Gate-Level Fault Coverage by
`RTL Fault Grading", IEEE ITC pp. 150-159, 1996.
`
`e. Papachristou et aI., "Test Synthesis in the Behavioral
`Domain", IEEE International Test Conference, 1995, pp.
`693-702.
`B.H. Seiss et aI., "Test Point Insertion for Scan-Based
`BIST", Proc. of European Test Conference, pp. 253-262,
`1991.
`e.H. Cho et aI., "B-algorithm: A Behavior Test Generation
`Algorithm", IEEE International Test Conference, 1994, pp.
`968-979.
`X. Gu et aI., "Testability Analysis and Improvement from
`VHDL Behavioral Specifications", Proc. EURO-DAC, pp.
`644-649, 1994.
`L.J. Avra et aI., "High Level Synthesis of Testable Designs:
`An Overview of University Systems", IEEE TC Test Syn(cid:173)
`thesis Seminar, 1994, pp. 1.1.1.-1.1.8.
`S. Dey et aI., "Transforming Behavioral Specifications to
`Facilitate Synthesis of Testable Designs" IEEE ITC pp.
`184-193, 1994.
`
`* cited by examiner
`
`2
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`u.s. Patent
`
`Mar. 26,2002
`
`Sheet 1 of 7
`
`US 6,363,520 BI
`
`16
`
`"
`
`VHDL Intermediate Format (VIF)
`
`VHDL specification
`
`~~L analyzer
`
`14
`
`12
`
`18
`
`28
`
`( Construction of DAG
`~-----.--~------~
`
`Add a new node
`in the DAG
`
`20 ~.~ ______ ~
`(
`Computation of TMs
`
`26
`
`Test point insertion
`
`Fig. 1
`
`Yes
`
`Generate modified
`VHDL model
`
`RTL synthesis
`
`3
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`u.s. Patent
`
`Mar. 26,2002
`
`Sheet 2 of 7
`
`US 6,363,520 BI
`
`-- Moore machine
`
`entity MOORE is
`port(X, CLOCK in BIT;
`Z: out BIT);
`end;
`architecture BEHAV of MOORE is
`type STATE_TYPE is (SO, S1, S2, S3);
`signal CURRENT_STATE, NEXT_STATE
`S TAT E_ TYPE;
`begin
`-- Process to hold combinational logic
`COMBIN: process(CURRENT_STATE, X)
`begin
`case CURRENT_STATE is
`when SO =>
`Z <= '0';
`if X = '0' then
`NEXT_STATE <= SO;
`else
`NEXT_STATE <= S2;
`end if;
`when S1 =>
`Z <= '1';
`if X = '0' then
`NEXT_STATE <= SO;
`else
`NEXT_STATE <= S2;
`
`when S2 =>
`Z <= '1';
`if X = '0' then
`NEXT_STATE <= S2;
`else
`NEXT_STATE <= S3;
`end if;
`when S3 =>
`Z <= '0';
`if X = '0' then
`NEXT_STATE <= S3;
`else
`NEXT_STATE <= S1;
`end if;
`end case;
`end process COMBIN;
`
`-- Process to hold synchronous elements (flip-
`
`flops)
`
`SYNCH: process
`
`begin
`
`wait until CLOCK = '1';
`
`CURRENT_STATE <= NEXT_STATE;
`
`end process SYNCH;
`
`end BEHAV;
`
`Fig. 2
`
`4
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`u.s. Patent
`
`Mar. 26,2002
`
`Sheet 3 of 7
`
`US 6,363,520 BI
`
`"11"
`
`"01" Present state register
`
`'0'
`
`'1'
`
`'1'
`
`'0'
`
`22
`
`hanout stem
`
`~ Data transfer operation
`
`o
`D Pseudo primary input/output
`
`Primary input/output
`
`Fig. 3
`
`5
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`u.s. Patent
`
`Mar. 26, 2002
`
`Sheet 4 of 7
`
`US 6,363,520 BI
`
`aO
`
`bO
`
`\--1
`co-CT)~
`
`an-1
`
`bn-1
`
`ai
`
`bi
`
`/
`~+~ ...
`
`ci+1
`
`ci
`
`cn-1
`
`sa
`
`si
`
`Fig. 4
`(Prior Art)
`
`sn-1
`
`sn
`
`A-
`
`Fig. 5
`(Prior Art)
`
`Fig. 6(a)
`
`Fig.6(b)
`
`~L-f '
`
`D lc ,-
`
`','
`
`Fig. 6(c)
`
`6
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`u.s. Patent
`
`Mar. 26,2002
`
`Sheet 5 of 7
`
`US 6,363,520 BI
`
`Signal A, B, C, Z: bit;
`P1: Process
`Variable V: bit;
`Begin
`V= A and B;
`V:= Vor c;
`Z <= V;
`end Process P1;
`
`Fig. 7(a)
`
`A
`
`DAG representation
`
`Fig. 7(b)
`
`DAG modification
`
`Function Insert AND OR
`(V: bit; Cirp: boolean; T _In: bit; TM boolean) return bit IS
`Variable VAR: bit,
`Begin
`VAR =V
`if (TM) then
`if (Ctrp) then
`VAR := VAR and Tin:
`Return VAR;
`-
`
`else
`VAR := VAR or Tin;
`Return VAR;
`_.
`end if;
`else
`Return VAR;
`end if;
`end Insert_AND_OR:
`
`Signal A, B, C, Z: bit;
`P1' Process
`Variable V: bit;
`Begin
`V:= A and B:
`V:= Vor C;
`V:= Insert_AND_OR(V, 1, TesUn, Test_Mode);
`Z <=V;
`end Process P1,
`
`Fig.7(d)
`
`VHDL modification
`
`:V
`
`Fig.7(c)
`
`7
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`u.s. Patent
`
`Mar. 26,2002
`
`Sheet 6 of 7
`
`US 6,363,520 BI
`
`Signal A, B, C, 0,2: integer range 0 to 7;
`P1: Process
`variable V: integer range 0 to 7;
`Begin
`if (0 >= 2) Then
`V:= A + B;
`
`else
`
`V:= C + 0;
`end if;
`2 <= V;
`end Process P1;
`
`Function Insert Test POint(VAR: integer 0 to 3; size: integer;
`position: integer; Ctrp: boolean TJ bit ;TM:boolean) is
`variable V int: integer range 0 to 7;
`Variable V- vect: bit vector(size-1 downto 0),
`begin
`-
`-
`If(TM) then
`V vect = con v bit vector(VAR, size);
`if(Ctrp) then - ,-
`V_vect(positlon)= T_I AND V _vect(posltion);
`V_int = conv_integer(V_vect);
`return (V_int);
`
`else
`V vect(position) := T_I OR V_vect(position);
`V-int := conv integer(V vect);
`-
`return (V jnt);
`end if;
`else
`return (VAR);
`end if;
`end Insert_ Test_POint;
`
`Signal A, B, C, D, 2: Integer range 0 to 7
`P1: Process
`variable V: integer range 0 to 7;
`Begin
`If (0 >= 2) Then
`V:= A+ B;
`
`else
`
`V :=C + 0;
`end if;
`V=lnsert_ Test_Point(V, 4, 0, 0, TesUn, Test_Mode);
`2 <= V;
`end Process P1;
`
`Fig. 8( d)
`
`Fig. 8(a)
`
`A[02J
`
`8[02J C[0:2J 0[02J
`
`DAG representation
`
`Fig.8(b)
`
`~02]
`
`T Z[02]
`
`DAG modification
`
`A[02]
`
`8[0:2] C[0:2] 0[0:2]
`
`VHDL modification
`
`Fig. 8(c)
`
`8
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`u.s. Patent
`
`Mar. 26,2002
`
`Sheet 7 of 7
`
`US 6,363,520 BI
`
`Fig. 9(a)
`
`A
`
`DAG representation
`
`Fig.9(b)
`
`, Z ,
`
`DAG modification
`
`A
`
`VHDL modification
`
`Signal A, B, C, Z: bit;
`
`P1: Process
`
`Variable V: bit;
`
`Begin
`V:= A and B;
`
`V:= Vor C:
`
`Z <=V;
`
`end Process P1;
`
`-- S1
`
`-- 52
`
`-- 53
`
`Signal A, S, C, Z,Reg: bit;
`
`P1: Process
`
`Variable V: bit;
`
`Begin
`
`V:= A and 8;
`
`V:=VorC;
`
`Z <=V;
`
`end Process P'l;
`
`P _Obs: Process
`
`Begin
`
`wait until Clk = '1';
`
`If (Test_Mode) Then
`
`Reg <= Z;
`
`end if;
`
`end Process P._obs;
`
`Fig. 9(d)
`
`Fig.9(c)
`
`9
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`US 6,363,520 Bl
`
`1
`METHOD FOR TESTABILITY ANALYSIS
`AND TEST POINT INSERTION AT THE
`RT-LEVEL OF A HARDWARE
`DEVELOPMENT LANGUAGE (HDL)
`SPECIFICATION
`
`2
`Analysis and Improvement from VHDL behavior
`Specification", Proc. EURO-DAC, pp. 644-649, 1994.
`However, the paper analyzes only very simple VHDL con(cid:173)
`structs to perform test point insertion at the RT-Level. In
`5 addition, the TM computations based on Controllability and
`Observability transfer functions are very complex for large
`primitive functional modules and involve more hardware for
`test point insertion.
`Other methods (see S. Dey and M. Potkonjak, "Trans-
`10 forming Behavioural Specifications to Facilitate Synthesis
`of Testable Designs", ITC pp. 184-193, 1994; P. Vishakan(cid:173)
`taiah et aI, "AMBIANT: Automatic Generation of Behavo(cid:173)
`rial Modifications for Testability", IEEE ICCD, pp. 63-66,
`October 1993; A. Debreil, P. Oddo, "Synchronous Designs
`15 in VHDL', Euro-VHDL 93, pp. 486-491) work by modify(cid:173)
`ing a behavioral description before high level synthesis
`begins, however they concentrate on the testability of the
`synthesized datapath, without outlining a test scheme for
`testing the datapath and the controller as a whole.
`Finally, recently an RT-Level testability analysis method
`has been proposed in W. Mao and R. K. Gulati, "Improving
`Gate-Level Fault coverage by RTL Fault Grading", ITC pp.
`463-472, 1996. The authors use verilog RT-Level models
`and functional verification patterns to evaluate the fault
`coverage of the resulting circuit. However, the paper does
`not propose test point insertion at the RT-Level to improve
`the testability of the resulting circuit.
`
`The present invention relates to method of producing a
`synthesizable Register Transfer (RT) Level VHDL specifi(cid:173)
`cation for input to a synthesis tool to generate a gate-level
`circuit having testability enhancement.
`BACKGROUND OF THE INVENTION
`VLSI circuit complexity has made testing difficult and
`more expensive. Increasing the testability of a design
`becomes one of the important issues in the design cycle of
`VLSI circuits. It helps to achieve the high test quality and to
`reduce test development and test application costs. In the
`past, it was possible to add Design-for-Testability (DFT)
`circuits manually after logic synthesis. But current needs for
`a shorter time to market makes this approach an un affordable
`design bottleneck. Ignoring DFT during the design cycle 20
`affects product quality and introduces schedule delays. Most
`industrial digital designs use automated synthesis and DFT
`can be achieved by incorporating test and synthesis into a
`single methodology that is as automated as possible. Indeed,
`considering testability during the design synthesis, as 25
`opposed to traditional approaches of making back-end modi(cid:173)
`fication after an implementation has been generated, can
`reduce design time. Even more important, the testability
`enhancement at the entry level to a synthesis tool makes it
`independent of the tool and the implementation technology. 30
`It becomes part of the design specification.
`As indicated below, several methods have been proposed
`in the literature to address the problem of testability analysis
`at higher levels of abstraction. Most of them concentrate on
`improving the testability of datapaths, assuming that the 35
`controller can be tested independently and that its outgoing
`control signals to the datapath are fully controllable in test
`mode. However, even when both the controller and the
`datapath are individually testable, the composite circuit may
`not be. A method based on testability analysis at the behav- 40
`iourallevel was presented in C. Papachristou and 1. Carletta,
`"Test Synthesis in the Behavioural Domain", IEEE Interna(cid:173)
`tional Test Conference, 1995, pp. 693, 702. While the
`authors perform the test insertion of the datapath at the
`behavioural level, test point insertion for the controller and 45
`the interface between the datapath and the controller, is
`performed at the structural level. Moreover, even if the
`authors use two metrics for testability analysis at the behav(cid:173)
`ioural level, test overhead can be very large for practical
`circuits. In contradistinction, the present invention considers 50
`the Controllability and the Observability of each bit of each
`signal and/or variable declared in the VHDL specification
`after data type conversion. In addition, test point insertion is
`also performed at the bits of each signal and/or variable
`identified as hard to detect areas instead of all bits, as used 55
`in previous methods (see for example P. Vishakantaiah et aI.,
`"Automatic Test Knowledge Extraction from VHDL
`(ATKET)", IEEE Design Automation conference, pp.
`273-278); X. Gu, et aI., "Testability Analysis and Improve(cid:173)
`ment from VHDL behavior Specification", Proc. EURO- 60
`DAC, pp. 644-649, 1994; A. Debreil, P. Oddo, "Synchro(cid:173)
`nous Designs in VHDL', Euro-VHDL 93, pp. 486-491, and
`this can reduce the test overhead for practical circuits and
`makes test point insertion more oriented to the hardware
`represented by the VHDL specification.
`Another method which considers testability features at the
`behavioral level was presented in X. Gu, et aI., "Testability
`
`65
`
`SUMMARY OF THE INVENTION
`
`The primary objective of the method of the present
`invention is to raise the level of abstraction at which
`testability analysis and test point insertion is performed. The
`present invention proposes a new testability analysis and test
`point insertion method at the RT-level assuming full scan
`and a Built In Self Test (BIST) design environment. The
`method uses as the starting point a specification given at the
`synthesizable RT-Level VHDL. The specification is ana(cid:173)
`lyzed to produce an intermediate representation, called the
`VHDL Intermediate Format (VIF), and transformed into a
`Directed Acyclic Graph (DAG) on which testability analysis
`is performed by computing and propagating Testability
`Measures (TMs) forward and backward through the VHDL
`statements. These measures are then used to identify the bits
`of each signal and/or variable on which faults are hard to
`detect. Finally, test point insertion is performed to improve
`testability, again at the RT-Level, by adding new VHDL test
`statements.
`The computation of Controllability and Observability
`method is purely functional, that is, it does not subsume the
`knowledge of a gate-level implementation of the circuit
`being analyzed. Therefore, it enables the computation of
`testability estimations with a high degree of accuracy for
`circuits on which existing tools fail due to the enormous
`amount of information which must be handled when con(cid:173)
`sidering the structural implementation of the circuit.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These and other features of the invention will become
`more apparent from the following description in which
`reference is made to the appended drawings in which:
`FIG. 1 illustrates the overall structure of the testability
`analysis environment of the present invention;
`FIG. 2 is a VHDL specification which represents a Moore
`finite state machine with 4 states (SO, S1, S2, S3) and one
`output Z;
`
`10
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`US 6,363,520 Bl
`
`3
`FIG. 3 illustrates a Direct Acrylic Graph for Testability
`Measures computation of the Moore State machine illus(cid:173)
`trated in FIG. 2;
`FIG. 4 illustrates a ripple-carry adder composed of n full
`adders;
`FIG. 5 illustrates a binary representation and notation for
`input A of a comparator;
`FIGS. 6(a)-(e) illustrate test point implementation at gate
`level in which FIG. 6(a) shows a circuit before test point
`insertion; FIG. 6(b) shows insertion of an observation point
`at signal S and FIG. 6(e) shows insertion of an AND-gate as
`a control point at signal S;
`FIGS. 7(a)-(e) show control point insertion of a single
`assignment statement where FIG. 7(a) shows the original
`VHDL specification, FIG. 7(b) shows the DAG before test
`insertion and FIG. 7(e) shows the VHDL specification after
`test statement insertion;
`FIGS. 8(a)-(d) illustrate control point insertion for a
`conditional statement in which FIG. 8(a) is the original
`VHDL specification; FIG. 8(b) is the DAG before test
`insertion; FIG. 8(e) is the DAG after test insertion and FIG.
`8(d) is the VHDL specification after test statement insertion;
`FIGS. 9(a)-(d) illustrate observability point insertion in
`which FIG. 9(a) is the original VHDL specification; FIG.
`9(b) is the DAG before test insertion; FIG. 9(e) is the DAG
`after test insertion and FIG. 9(d) is the VHDL specification
`after test statement insertion.
`
`5
`
`4
`input to a synthesis tool to generate a gate-level circuit that
`includes a testability enhancement. The algorithm illustrated
`in FIG. 1 may implemented using the C language.
`Construction of the Direct Acyclic Graph
`As shown in FIG. 1 and indicated above, the VHDL
`specification is compiled into a VIF representation and then
`a DAG is constructed that represents the flow of information
`and data dependencies from primary and pseudo-primary
`inputs (DAG's inputs) to primary and pseudo-primary out-
`10 puts (DAG's outputs). Each internal node of the DAG
`corresponds to an operation in the VHDL specification.
`Source and sink nodes represent present and next,
`respectively, state and primary inputs and outputs.
`VHDL operations generally consist of arithmetic opera-
`15 tions (addition, subtraction, multiplication), relational
`operations (various comparators), data transfer operations
`and logical operations (AND, OR, NAND, ... etc.). The
`present and the next states are given by synthesized registers
`in the VHDL specification. Edges represent the flow of
`20 information from the present states and primary inputs
`through the operators to the next states and primary outputs.
`These edges are signals and/or variables declared in the
`VHDL specification and virtual signals and/or variables.
`A virtual signal and/or variable is defined as an unnamed
`25 signal and/or variable formed by an expression which is not
`a simple signal and/or variable name. For example, from the
`following VHDL specification, two virtual signals (S_vl,
`S_v2) and two virtual variables (V_vI and V _v2) are
`defined:
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT OF THE INVENTION
`While the method of the present invention is described
`herein with reference to VHDL specifications, it is to be
`understood that the invention is not limited thereto and that
`the principles of the invention are equally applicable to other 35
`known specifications, such as Verilog, for example.
`FIG. 1 illustrates the overall structure 10 of the testability
`analysis environment of the present invention which can
`operate as a front-end to RT-Level synthesis tools such as
`Synopsys. In the first step, a VHDL analyzer 12 from LEDA 40
`as disclosed in C. H. Chen and P. R. Menon, "An Approach
`to Functional Level Testability Analysis", International Test
`Conference, pp. 373-379, 1989, is used to process a starting
`VHDL specification 14 to produce a VHDL Intermediate
`Format representation 16 and to identify all registers (full 45
`scan is assumed) and sequential VHDL statements. A
`Directed Acyclic Graph (DAG) 18 is used to store this
`information by linking the present states of registers with the
`next states through the VHDL statements. Testability Mea(cid:173)
`sures (TMs) are then computed at 20 using DAG 18 by 50
`initializing the Controllability of primary and pseudo pri(cid:173)
`mary inputs to 0.5 (both 0 and 1), and the Observability of
`primary and pseudo-primary outputs to 1, and by propagat(cid:173)
`ing them forward and backward through the VHDL state(cid:173)
`ments. The VHDL statements are converted to operate at the 55
`bit level and modeled by their Boolean functional models.
`These models are described by VHDL operations using
`signals and variables as operands.
`The present invention proposes an efficient method for
`propagating TMs through such VHDL operators. The 60
`method allows the identification of hard-to-detect bits in the
`signals and variables of the VHDL specification. This infor(cid:173)
`mation is used to insert VHDL test statements in the VHDL
`specification by locally converting the affected signal!
`variable to the bit-level and back.
`As a result, the method of the present invention produces
`a synthesizable RT-Level VHDL specification which can be
`
`30
`
`65
`
`Signal A, B, C, D, E: integer;
`Process (A, B, C, D, E)
`Variable V: integer;
`begin
`
`V:~(A+B)+C;
`
`S<~(V+D)+E;
`
`End Process;
`
`S_v1: (V+D)
`S_v2:(V+D)+E
`V _v 1: (A+B)
`V _v2:(A+B)+C
`While the entire language is supported by the VHDL
`analyzer; the method of the present invention supports only
`synchronous synthesizable VHDL constructs which are
`accepted by commercial synthesis tools (Snyopsys, Mentor,
`Cadence, ... etc.)
`The construction of the Directed Acyclic Graph involves
`the following five steps:
`1. Generation of a Control and Data Flow Graph (CDFG)
`for each process of the VHDL specification.
`2. Unrolling all For-Loops and expansion of procedures
`and functions by adding new nodes to the CDFG.
`3. Conversion of data types to bits.
`4. Translation of the CDFG into a DAG.
`5. Connection of DAG graphs of individual processes to
`produce a global DAG.
`Each of these steps is described below.
`
`Generation of CDFG
`Each VHDL process can be transformed into a Control
`Flow Graph (CFG) to represent the control flow of opera(cid:173)
`tions. The CFG is a directed graph defined as:
`
`11
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`US 6,363,520 Bl
`
`CFG~(V,E), where
`
`5
`
`V is a set of nodes corresponding to the different VHDL
`sequential statements:
`
`S
`
`6
`Identification of Multiplexers
`The following description provides a suited translation for
`the VHDL conditional statements if and case, A new node
`type is added to the DAG representing a multiplexer opera-
`tion, In fact, each conditional statement if and case is
`translated into a set of multiplexers having one output for
`each signal/variable assigned within the conditional state(cid:173)
`ment The condition expression translates into a set of nodes
`which feeds the control input of each multiplexer, The data
`10 inputs to each multiplexer are fed from the nodes of the
`corresponding expression being assigned, Thus, to translate
`each conditional statement to a multiplexer operation, it is
`necessary to find its scope, i,e"
`its corresponding end(cid:173)
`statement
`Connection of Processes
`A VHDL specification consists of a set of interacting
`processes (clocked and unclocked), Entity ports and internal
`signals, declared in the VHDL architecture, are used to
`communicate between the processes, The connection
`between processes is represented as a Directed Graph,
`20 However, as indicated earlier, each VHDL process can be
`transformed into a CDFG which is represented as a DAG,
`Hence, the global VHDL specification is also represented as
`a DAG, The following description, which refers to FIG, 2,
`illustrates the overall construction,
`FIG, 2 is a VHDL specification which represents a Moore
`finite state machine with four states SO, S1, S2, S3 and one
`output Z, The specification consists of two processes:
`COMBIN which is clocked and SYNCH which is
`unclocked, Its DAG is shown in FIG, 3, which also shows
`the primary and pseudo-primary inputs/outputs, The signal
`CURENT_STATE is synthesized as a register and thus
`becomes a pseudo-primary two bit-wide input/output since
`it is declared as an enumerated data type of four possible
`values, The states or constants SO, S1, S2, and S3 are
`35 encoded as 00, 01, 10, and 11, respectively, Each multiplexer
`operation corresponds to a conditional statement Fan-out
`stems are also identified by the method of the present
`invention, as shown at 22 in FIG, 3,
`Testability Computation in the DAG of a VHDL Specifica(cid:173)
`tion
`Most previous methods in testability analysis are
`restricted to circuits consisting of logic gates only, This
`implies that circuits containing complex functional modules
`must be expanded to a gate-level modeL In contrast, the
`method of the present invention handles all VHDL opera(cid:173)
`tions at the functional level in addition to logical operations,
`The present invention supports the following operators: n-bit
`adders, n-bit comparators «, <=, =,
`, , , etc,), n-bit
`multipliers, n-bit sub tractors, and multiplexers inferred by
`50 conditional statements, All of these are represented func(cid:173)
`tionally which means that Controllability and Observability
`propagation through them is exact This is not the case with
`gate-level models because reconvergent fanout in such mod-
`els introduces errors in the calculations, The present method
`computes a Controllability of zero (Co) and of one (Cl), and
`Observability (0) values for each bit of each signal and
`variable after data type conversion, The following descrip(cid:173)
`tion describes the propagation of Co, Cl and 0 through
`typical VHDL operators,
`Combinational Controllability is defined as the probabil(cid:173)
`ity that a signal s has a specific value (see C, H, Chen and
`P, R, Menon, "An Approach to Functional Level Testability
`Analysis", International Test Conference, pp, 373-379,
`1989), There are two measures: 1-Controllability (Cl(s)) and
`O-Controllability (Co(s)) such that Co(s)=1-Cl(s),
`Combinational Observability 0(1, s) of a line I is defined
`as the probability that a signal change on I will result in a
`
`v w is the set of synchronization nodes (wait statements),
`Vb is the set of conditional statement nodes (if, case),
`VI is the set of for , , , loop statement nodes,
`Ve is the set of other nodes (signal/variable assignments,
`procedure calls, , , , ), and
`E is the set of edges representing the flow of controL
`Each node of a CFG is associated with a Data Flow
`Graph, The DFG consists of a set of nodes and edges where 15
`each node represents one operation in the VHDL specifica(cid:173)
`tion and each edge represents signals and variables con(cid:173)
`nected the nodes, There is an edge from node 0i to node OJ
`if the result of the operation at node 0i is input to node OJ'
`A CFG in which each node is a DFG is called a Control and
`Data Flow Graph or CDFG,
`Loop Unrolling and Expansion of Procedures/Functions
`For-Loop statements are used to repeat a sequence of
`operations for a constant number of times, Thus, the result
`of synthesis would be a replication of the hardware corre- 25
`sponding to the statements inside the loop, one for each
`iteration, Each procedure call is expanded in-line, The
`contents of the procedure are first copied into the process in
`place of the calL Then, the actual parameters are substituted
`for the formal parameters of the procedure, Functions are 30
`expanded in a similar fashion except that a function is
`expanded immediately before the expression that calls it As
`a result of loop unrolling and expansion of procedure/
`functions, the CDFG is augmented by new nodes,
`Data Type Conversion
`All synthesized VHDL data types are converted into bits,
`An enumerated type is defined by listing all its possible
`values, The main issue with enumerated types is their
`encoding, Enumerated values are encoded by default into
`bit-vectors whose length is determined by the minimum 40
`number of bits required to code the number of enumerated
`values and the actual code assigned to each value corre(cid:173)
`sponds to the binary representation of the position in the type
`declaration (starting from zero), Or subtypes are defined
`using subranges that impose bounds on the possible values, 45
`They are encoded using bit-vectors whose length is the
`minimum necessary number of bits to hold the defined
`range, If the range includes negative numbers, it is encoded
`as a 2's-complement bit-vector,
`Translation of the CDFG into Directed Acyclic Graph
`The next step is to translate the resulting CDFG into a
`DAG, As stated, each node corresponds to a VHDL opera(cid:173)
`tion and edges correspond to signals/variables and virtual
`signals/variables connecting the nodes, Synchronous regis(cid:173)
`ters are inferred on signals and some variables are assigned 55
`in a clocked process, However, a DAG is obtained when the
`present and the next states of registers are separated into
`separate nodes, The source nodes are the primary inputs and
`present state values of registers and the sink nodes are the
`primary outputs and the next-state values, The primary 60
`inputs (outputs) of the DAG are all the input (output) signals
`of the entity port declaration and they correspond to all
`signals that are only read (assigned) and not assigned (read)
`in the VHDL specification, Pseudo-primary inputs (outputs)
`correspond to synthesized register outputs (inputs), The 65
`algorithm to identify the synthesized registers in the VHDL
`specification is the same as used by most synthesis tools,
`
`12
`
`SYNOPSYS 1012, Synopsys v. Mentor, IPR-2012-00042
`
`

`
`US 6,363,520 Bl
`
`7
`signal change on an output s. For multiple output modules,
`the Observability of a line must be computed relative to each
`output and the overall Observability 0(1) of I is given by
`max, [0(1, s)]. Thus max, [0(1, s)] simply refers to the
`maximum one of the observabilities computed for all of the
`outputs of the multiple output module.
`Controllability Calculations
`The following description outlines the formulas for deter(cid:173)
`mining the Controllability on an output of a VDHL operator
`given the Controllability on the inputs. The Controllability
`formulas for logical operators can be found in P. H. Bardel
`et aI., "Built-In Test for VLSI; Pseudorandom Techniques",
`Wiley Inter-Science, 1987.
`Controllability of the Outputs of an N-Bit Adder
`It is necessary to compute the Controllability on the
`outputs of an n-bit adder, given the Controllability on its
`inputs and assuming that the inputs are independent. When
`two n-bit binary numbers a and b are added, each bit of the
`sum s is a functio