Method and integrated circuit adapted for partial scan testability

Description Submit all comments and votes

FIELD OF THE INVENTION

The invention relates to the testing of electric circuits in general, and more particularly, to methods and apparatus for testing integrated circuits with partial scan techniques.

BACKGROUND OF THE INVENTION

While the state of the art in semiconductor manufacturing enables the fabrication of integrated circuits with more than a million circuit elements, the process is imperfect and produces integrated circuits which may comprise unpredictable and dissimilar faults which prevent the circuits from functioning as designed. And since a disfunctional circuit can have catastrophic consequences, it proves prudent in many situations to ensure the integrity of each circuit before it is incorporated into other equipment.

Techniques for testing simple integrated circuits are well known to those skilled in the art. One method involves stimulating a circuit's inputs with one or more "test vectors" and retrieving from the circuit's outputs the "resultant vectors" which are the direct consequence of the test vectors. As long as the circuit is designed to produce a deterministic output which is based on its input, the resultant vectors can be predicted. A circuit comprising a fault is revealed when the circuit produces one or more resultant vectors which are inconsistent with those which were predicted.

While testing simple circuits is relatively straightforward, techniques for testing complex circuits comprising millions of transistors and thousands of memory elements is problematic. For the purposes of this disclosure a memory element is defined as a flip-flop, latch or any other circuit element which is capable of retaining a signal for some temporal period after the signal has been removed from the memory element's input. Memory elements complicate the testing of integrated circuits because (1) they can delay the propagation of fault effects through the circuit and (2) they can provide the keystone for feedback mechanisms which intermittently conceal faults.

In general, each manufactured circuit can be either exhaustively tested, which can guarantee that the circuit is totally free from manufacturing defects, or partially tested, which, when used in conjunction with statistical methods, provides some degree of confidence that the circuit is unblemished. Other things being equal, the exhaustive testing of complex integrated circuits is either technologically infeasible or disproportionately expensive when compared to the costs and benefits associated with partial testing.

Many techniques have been employed to screen out defective integrated circuits. At one time, integrated circuit testing was performed by machines comprising a large number of electrically conductive probes. These probes were put in physical contact with selected nodes in the circuit so that the test vectors could be introduced into the circuit and the resultant vectors retrieved. This technique lost favor, however, as inefficiencies associated with the method were compounded by the increasing complexity of integrated circuits.

Another technique for testing integrated circuits avoids conductive probes and instead uses a focused electron beam to charge selected circuit elements in the integrated circuit. While the electron beam technique overcomes some of the drawbacks associated with conductive probes it is slow and has the potential side effect that it can introduce faults into the circuit.

Historically, integrated circuits were not been designed to facilitate testing. Recently, however, one paradigm, known as design-for-testability, has been propounded which suggests that integrated circuit testing could be simplified if the integrated circuit was designed with after-manufacture testing in mind.

One design-for-testability technique is known as "scan testing." In scan testing, special-purpose test circuitry is advantageously incorporated into the integrated circuit so that it can be alternately switched between an "operation mode" and a "test mode" by an externally generated control signal.

When the integrated circuit is in operation mode, it is preferred that the combinational logic and memory elements are electrically connected so as to enable the circuit to operate in the manner for which it was designed and fabricated. In test mode, it is preferred that a subset of the memory elements (the "scan memory elements") are electrically insulated from the other memory elements (the "non-scan memory elements") and the combinational logic in the circuit and are configured in a manner so as to facilitate testing.

Testing is advantageously accomplished with external test equipment which supplies the test vectors and checks the resultant vectors. First, the scan memory elements are themselves tested by putting the circuit into test mode. A test vector is shifted into the scan memory elements and out again to test the ability of each scan element to be set and reset. It is well known to those skilled in the an how to generate the test vector and check the resultant vector.

Next, testing of the entire circuit begins by shifting a test vector into the scan memory elements while the circuit remains in test mode. After the test vector is loaded, the circuit is forced into function mode for a predetermined number of clock periods so that the states of the scan memory elements can be affected by the combinational logic and non-scan memory elements. After the predetermined number of clock periods, the circuit is again put into test mode so that the states of the affected scan memory elements can be retrieved from the circuit. The resultant vector is then compared with that which is expected. Because each test vector can typically only check a fraction of the potential faults in a circuit, the procedure is advantageously repeated with different test vectors until some desired level of fault coverage is achieved.

When all of the memory elements in an integrated circuit are reconfigurable into a test mode shift register, the testing technique is known as "full scan testing" and when fewer than all of the memory elements in the integrated circuit are reconfigurable it is known as "partial scan testing". Full scan testing is advantageous in that it enables an integrated circuit to be easily and thoroughly tested. It has one disadvantage, however, in that it typically causes the integrated circuit to consume more space on the integrated circuit than it would without the additional test circuitry. Partial scan testing consumes less space on the integrated circuit than full scan testing but requires that the memory elements which comprise the test mode shift register be judiciously chosen so that fault coverage is not compromised. Furthermore, techniques in the prior art often add circuitry to an integrated circuit in such a manner such that the added circuitry slows the maximum operation of the integrated circuit.

Empirically, the level of difficulty associated with testing an integrated circuit depends on the topology of that circuit. More specifically, on the existence and nature of a topological feature called a "cycle". For the purpose of this disclosure, a cycle is defined as a circuit path which feeds a signal from a memory element back into that memory element. Example cycles are shown in FIG. 1 within integrated circuit 150. Cycle 110 comprises memory elements 102 and 104 and NAND gates 101 and 103. Cycle 120 comprises memory element 106 and NAND gate 105.

Each cycle in a circuit can be characterized by a measure of its "length". For the purposes of this disclosure, a cycle's length is defined as the number of memory elements in a given cycle (including the memory element which serves as the "beginning" and "end" of the cycle. Cycle 110, in FIG. 1 for example, has a length of two while cycle 120 has a length of one.

V. D. Agrawal et al., U.S. Pat. No. 5,043,986, issued Aug. 27, 1991 teaches a method of partial scan testing in which memory elements are typically selected to be scan memory elements based on their respective ability to "break" a cycle--that is on their presence within a cycle.

D. H. Lee and S. M. Reddy in "On Determining Scan Flip-Flops in Partial-Scan Designs," Int'l Conf. on Computer-Aided Design, (ICCAD-90) (November 1990), teach a method for selecting which memory elements in a circuit should be selected to be scan memory elements.

SUMMARY OF THE INVENTION

One aspect of the present invention is a method and apparatus for designing integrated circuits for economical testing while avoiding many of the costs and restrictions associated with prior methods. The principal cost associated with the prior an is that the prior art added test circuitry to integrated circuits in such a way that it slowed the operation of the integrated circuit. Circuits designed with embodiments of the present invention are as easily testable as those in the prior art but usually avoid the performance degradation associated with the prior art.

These results are obtained in an illustrative embodiment of the present invention by chosing memory elements in the circuit to be scan memory elements based on the costs and benefits associated with (1) the scope of fault coverage provided by the scan memory elements, (2) the ease with which test vectors can be generated, (3) the ease with which the test vectors can be applied to the circuit and the resultant vectors retrieved, (4) the total area on the integrated circuit consumed by the scan memory elements, (5) the total area on the integrated circuit consumed by the conductors connecting the scan memory elements, and (6) the performance (timing) degradation caused by the scan memory elements. More specifically, scan memory elements are illustratively chosen based on their respective ability to both break cycles and to do so without affecting the performance characteristics of the circuit.

Another aspect of the present invention is a circuit which enables testing with partial scan techniques and does so with little or no impact on the circuit's performance when it is providing the functionality for which it was designed and fabricated. This accomplished by placing scan memory elements into the circuit in places where the performance degradation associated with scan memory elements does not affect the performance of the circuit as a whole.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 shows a schematic of a digital circuit comprising two cycles which in turn comprise combinational logic and memory elements.

FIG. 2 shows a block diagram of a digital circuit comprising combinational logic, non-scan memory elements and scan memory elements which may be configured into a test mode shift register for the reception of test vectors and outputting of test results.

FIG. 3 shows an illustrative digital circuit which does not incorporate partial scan test circuitry.

FIG. 4 shows a weighted directed graph which represents the digital circuit represented by FIG. 3.

FIG. 5 shows a flowchart for a technique which determines which memory elements in a circuit may be selected as scan memory elements.

FIG. 6 shows the weighted directed graph of FIG. 4 which has been pruned by the technique represented by the flowchart in FIG. 5.

FIG. 7 shows the weighted directed graph of FIG. 6 which has been pruned by the technique represented by the flowchart in FIG. 5.

FIG. 8 shows the weighted directed graph of FIG. 7 which has been pruned by the technique represented by the flowchart in FIG. 5.

FIG. 9 shows the weighted directed graph of FIG. 8 which has been pruned by the technique represented by the flowchart in FIG. 5.

FIG. 10 shows the weighted directed graph of FIG. 9 which has been pruned by the technique represented by the flowchart in FIG. 5.

FIG. 11 shows the weighted directed graph of FIG. 10 which has been pruned by the technique represented by the flowchart in FIG. 5.

FIG. 12 shows the weighted directed graph of FIG. 11 which has been pruned by the technique represented by the flowchart in FIG. 5.

FIG. 13 shows a schematic of the circuit in FIG. 3 as it has been modified according to the technique represented in FIG. 5 to incorporate partial scan test logic.

FIG. 14 shows a schematic of an illustrative design for a scan memory element.

FIG. 15 shows a diagram of a computer-aided design system which is capable of designing the circuits in FIGS. 2 and 13.

DETAILED DESCRIPTION

I. Overview of Detailed Description

The illustrative embodiment of the present invention is a post-processor in a computer-aided design system and advantageously converts a schematic of a circuit which does not provide partial scan testing into a schematic of a circuit which does provide partial scan testing. The detailed description comprises eight sections in addition to this overview. Circuits which enable partial scan testing advantageously conform to the partial scan architecture described in Section II. Section III describes an illustrative technique for testing circuits which conform to the partial scan architecture taught in Section II.

For pedagogical reasons, the illustrative embodiment is described twice. First, as it is applied to circuits in general and, second, as it is applied to an illustrative circuit. The illustrative circuit has been chosen for its ability to highlight aspects of the illustrative embodiment and to provide a specific example of its operation. Section IV describes the illustrative circuit, Section V describes the illustrative embodiment as it is applied to circuits in general, Section VI details the application of the illustrative embodiment to the illustrative circuit, and Section VII describes the illustrative circuit as it is modified in accordance with the illustrative embodiment to conform to the partial scan architecture taught in Section II.

Section VIII presents a description of an illustrative partial scan memory element as it may be used in the modified circuit of Section VII and Section IX describes an illustrative computer-aided design system which incorporates the illustrative embodiment.

II. An Architecture for Partial Scan Circuits

This section presents an illustrative circuit architecture which advantageously enables a circuit to be tested with partial scan techniques. The next section presents an illustrative methodology for testing circuits which conform to this architecture and Sections IV, V and VI teach a methodology for converting circuits which do not conform to this architecture into circuits which do.

FIG. 2 shows the layout of integrated circuit 200 which has been advantageously designed in accordance with the illustrative embodiment of the present invention. Integrated circuit 200 comprises combinational logic and memory elements and has two modes of operation: a "function" mode and a "test" mode. In function mode, the combinational logic and memory elements are electrically connected so as to enable the circuit to operate in the manner for which it was designed and fabricated. In test mode, a subset of the memory elements, the "scan memory elements," are electrically insulated from the other memory elements, the "non-scan memory elements," and the combinational logic in the circuit and are reconfigured in a manner so as to facilitate testing.

In integrated circuit 200, the combinational logic and non-scan memory elements are functionally grouped at 202. In accordance with an aspect of the invention, most of the memory elements are non-scan memory elements. The N scan memory elements in circuit 200 are labeled 250-1, 250-2 . . . 250-N.

Integrated circuit 200 comprises one or more leads 206 for providing functional data to the circuit and one or more leads 207 for retrieving functional data from the circuit when it is in function mode. Integrated circuit 200 also comprises lead 212 for providing externally generated test vectors to the scan memory elements 250-1, 250-2 . . . 250-N and lead 214 for retrieving resultant vectors from the scan memory elements when the circuit is in test mode.

To enable the scan memory elements to function independently of the non-scan memory elements, a pair of externally generated clock signals, CLOCK1 and CLOCK2, are provided to integrated circuit 200 on leads 208 and 209, respectively. The non-scan memory elements are clocked by CLOCK1 and the scan memory elements are clocked by CLOCK2. When integrated circuit 200 is in function mode, a single externally generated clock signal is provided through leads 208 and 209 to all of the memory elements in circuit 200 so that they all function and are clocked simultaneously. When integrated circuit 200 is in test mode, the externally generated clock signal is provided only to CLOCK2 on lead 209 while lead 208 is held inactive so that only the scan memory elements are clocked.

To control whether integrated circuit 200 is in function mode or in test mode, a MODE signal on lead 210 controls the mode of operation of the circuit. When such a MODE signal is asserted, integrated circuit 200 is put in function mode and thus scan memory elements 250-1, 250-2 . . . 250-N operate normally and are influenced by combinational logic and non-scan memory elements 202. When MODE is retracted and no clock is provided on lead 208, circuit 200 is put in test mode such that scan memory elements 250-1, 250-2 . . . 250-N are electrically isolated from the influence of the combinational logic and non-scan memory elements 202.

It is preferred that the electrical isolation of the scan memory elements be accomplished by incorporating into each scan memory element a two-to-one multiplexer. Each multiplexer has two data inputs: an "F" (functional) input, a "T" (test) input and a control input which receives the MODE signal on lead 210. When integrated circuit 200 is in function mode, each multiplexer feeds the signal on its F input to its associated memory element and ignores the signal on its T input. When circuit 200 is in test mode, every multiplexer feeds the signal on its T input to its associated memory element and ignores the signal on its F input. The scan memory elements 250-1, 250-2 . . . 250-N, may be fabricated as taught by D. K. Bhavsar, U.S. Pat. No. 4,669,061, issued May 26, 1987.

Lead 212, for carrying test vectors into circuit 200 is connected to the T input of scan memory element 250-1 and the output of scan memory element 250-N is connected to lead 214 for retrieving resultant vectors. The output of scan memory elements 250-1, 250-2 . . . 250-(N-1) are connected to the T input of scan memory elements 250-2, 250-3 . . . 250-N, respectively, so that when circuit 200 is in test mode, the scan memory elements form a shift register with its input on lead 212 and its output on lead 214.

III. A Methodology for Testing Partial Scan Circuits

Testing integrated circuit 200 proceeds as follows. First, scan memory elements 250-1, 250-2 . . . 250-N are themselves tested by retracting the MODE signal on lead 210--thus putting circuit 200 into test mode. A test vector is shifted into scan memory elements 250-1, 250-2 . . . 250-N via lead 212, and out, via lead 214, to test the ability of each scan memory element to be set and reset. It will be clear to those skilled in the art how to generate this test vector and how to check the resultant vector.

Next, the overall circuit, including combinational logic and non-scan memory elements, is tested by retracting the MODE signal. A test vector is shifted, via lead 212, into scan memory elements 250-1, 250-2 . . . 250-N. When the test vector is loaded into scan memory elements 250-1, 250-2 . . . 250-N, the MODE signal is asserted--thus putting circuit 200 into function mode. A clock signal is applied on leads 208 and 209 for a predetermined number of clock periods so that the states of the scan memory elements can be affected by combinational logic and non-scan memory elements 202. After the predetermined number of clock periods, the MODE signal on lead 210 is again retracted and with CLOCK2 the states of scan memory elements are shifted out on lead 214. The resultant vector is then compared with that which is expected. It will be clear to those skilled in the art how to generate the test vectors and how to check the corresponding resultant vectors to determine if faults exist in the circuit. This procedure of loading test vectors, operating the circuit in function mode and reading out resultant vectors is repeated with different test patterns until a desired level of fault coverage is achieved.

For the purposes of the illustrative embodiment, the propagation delay associated with scan memory elements is assumed to be greater than for non-scan memory elements based on the difference in the design of the respective circuits. It will be clear to those skilled in the art how to modify embodiments of the claimed invention when the propagation delay associated with scan memory elements is less than or equal to that for non-scan memory elements.

IV. An Illustrative Circuit

An illustrative circuit is presented in this section which provides some desired functionality but does not conform to the partial scan architecture taught in Section II. Techniques for designing circuits like the illustrative circuit are well known to those skilled in the art and form no part of the present invention. Section V presents the conversion methodology for turning non-partial scan circuits (e.g., the illustrative circuit) into partial circuits and Section VI teaches the conversion methodology as it applies to the illustrative circuit In Section VII, the illustrative circuit is shown as it has been modified according to the conversion methodology to conform to the architecture of Section II.

FIG. 3 shows the schematic of a typical circuit design which will be modified according to the conversion methodology. Circuit 350 comprises seven memory elements 301 through 307, combinational logic elements 311 through 316, and numerous signal paths from the functional output of a memory element, perhaps through a combinational logic element, and into the functional input of a memory element Lead 317 is an example of one signal path which does not go through a combination logic element and leads 318 and 319 are an example of a signal path which does go through a combinational logic element.

The circuit is synchronous and is designed to operate at some "performance metric," e.g., a target frequency. All memory elements are initially controlled by a clock signal (not shown) such as CLOCK1 208 in FIG. 2. Each memory element has associated with it a "performance characteristic," e.g., a quantity called "slack" which is defined as the difference between the circuit's target speed (in temporal units) and the time required for the signal to propagate to the memory element's data input from another memory element and perhaps through combinational logic. For example, when a circuit's target frequency is 100 MHz (i.e., one complete course of recurrent operations every 10 nanoseconds) and the worst-case signal propagation delay along a signal path into a memory element, as determined by a static timing analyzer, is 7 nanoseconds, then that memory element's slack is 3 nanoseconds. Techniques for determining the slack associated a memory element are well known in the an and forms no pan of the present invention. R. B. Hitchcock, Sr., in "Timing Verification and Timing Analysis Program," Proc. 19th Design Automation Conf. (1982), teaches a technique for static timing analysis of circuits.

Table 1 presents the illustrative slack values associated with each memory element in the circuit of FIG. 3.

TABLE 1 ______________________________________ Static Timing Analysis of Circuit in FIG. 3 (d.sub.max = 2 ns) Memory Graph Element Slack Vertex Weight ______________________________________ 301 3 ns 401 3 302 1 ns 402 1 303 5 ns 403 5 304 1 ns 404 1 305 5 ns 405 5 306 3 ns 406 3 307 3 ns 407 3 ______________________________________

V. A Methodology for Creating Partial Scan Circuits

One aspect of the present invention involves converting a non-scan circuit design into a partial scan circuit design such that the partial scan circuit, when fabricated, can be tested with partial scan techniques. Advantageously, the scan memory elements are chosen from among the memory elements in the circuit so as, to consider the costs and benefits associated with (1) the scope of fault coverage provided by the scan memory elements, (2) the ease with which test vectors can be generated, (3) the ease with which the test vectors can be applied to the circuit and the resultant vectors retrieved, (4) the total area on the integrated circuit consumed by the scan memory elements, (5) the total area on the integrated circuit consumed by the conductors connecting the scan memory elements, and (6) the performance (timing) degradation caused by the scan memory elements.

The selection of memory elements to be modified to be scan memory elements is facilitated when the circuit to be modified is represented as a weighted directed graph G=(V,E,W). In the graph G a vertex .upsilon..sub.i represents memory element i and an edge (.upsilon..sub.i,.upsilon..sub.j) exists when there is a signal path from memory element i to memory element j. Each vertex has associated with it a weight w.sub.i which is a unitless quantity which directly relates to the slack associated with the corresponding memory element i.

The circuit of FIG. 3 is illustratively represented by the weighted directed graph shown in FIG. 4. Vertex 40n in FIG. 4 represents memory element 30n from FIG. 3. Each memory element in the circuit is represented by a vertex in the graph and the direction of signal flow through the combinational logic elements and the interdependence of the memory elements is represented by the graph's edges. As a corollary, an edge between two vertices indicates that there exists a signal path between the memory elements associated with those vertices. Only the memory elements and the combinational logic dependencies between memory elements are represented in the graph of FIG. 4. As shown in FIG. 4, the number shown inside a vertex denotes the weight associated with that vertex. Table 1 shows the mapping of the memory elements of FIG. 3 to the vertices of FIG. 4 and the respective slacks associated with the circuit of FIG. 3 to the weights of the graph in FIG. 4. It will be clear to those skilled in the art how to construct a weighted directed graph, like that shown in FIG. 4, from a circuit schematic, like than shown in FIG. 3.

In an illustrative embodiment of the present invention, memory elements are advantageously chosen to be scan memory elements based on their ability to break some or all of the cycles in the circuit which have a length longer than some threshold. When a memory element .function. is selected to be convened into a scan memory element, extra circuitry is added to the memory element which causes extra propagation delay along the signal paths which end at memory element .function.. The amount of extra delay caused by the extra circuitry in a scan memory element is roughly fixed by the fabrication technology and is approximately equal to the delay of a two-to-one multiplexer. For the purposes of this specification, this delay is denoted as d.sub.mux. Techniques for determining d.sub.mux are well known to those skilled in the art and form no part of the present invention. The actual propagation delay incurred in converting a memory element into a scan memory element differs depending on the impedance of the specific signal path. In the illustrative embodiment, however, the delays due to variances in impedance are typically small and are neglected.

When a memory element is chosen in the course of design to be converted into a scan memory element and that memory element has slack equal to or greater than d.sub.mux, it is guaranteed that no performance degradation will be caused by this selection. When, however, a memory element is chosen to be converted into a scan memory element and that memory element has slack less than d.sub.max, in the absence of other performance optimization steps, the circuit's performance will be degraded because the signal coming into the memory element will not be stable before the memory element's set-up time. According to an embodiment of the present invention, memory elements are chosen to be scan memory elements based on the ability of the respective memory element to break a cycle and to do so with little or no performance degradation.

In practice, neither fault coverage nor ease of testing suffer when self-loops (i.e., cycles of length one) are not broken. And since the number of self-loops in a circuit is typically very high, it may be advantageous to break only cycles of length greater than one. In accordance with an illustrative embodiment of the invention, memory elements in the circuit of FIG. 3 will chosen based on the necessity of breaking circuit cycles of greater than length one and on the ability to do so with minimum impact on performance.

FIG. 5 shows a flowchart of a technique suitable for practice on a computer which selects those vertices in a weighted directed graph which represent those memory elements in a circuit which are advantageously made scan memory elements. It is to be understood, however, that neither the automation of this technique nor the use of this technique at all is essential to practice embodiments of the present invention. The technique involves iteratively examining, manipulating and pruning the graph until the graph is empty (i.e., void of vertices).

As shown in FIG. 5, the technique advantageously begins with a "preprocessing operation" (block 501) which processes the weighted directed graph (the "graph") representing the circuit to be modified by removing all of the edges from the graph which cause "self-loops". For the purpose of this specification, a self-loop is defined a vertex which has an edge which both begins and terminates on the vertex.

The preprocessing operation (block 501) implements the