Realization-Independent Testing of IP-Based Systems

Hyungwon Kim and John P. Hayes

Introduction

Many recent system-on-a-chip (SOC) ICs incorporate pre-designed and reusable circuits, variously referred to as intellectual property (IP) circuits or cores. Such circuits are frequently supplied by third-party vendors and are extremely hard to test when embedded in an SOC because their functions are specified only in high-level terms. This is done either to protect the circuits' IP content or else to allow system designers to synthesize their own low-level (gate-level) implementations [2]. Conventional ATPG methods are realization-specific, so they cannot generate tests for unimplemented or incompletely specified IP-based systems. When the IP circuits are implemented by the vendor, the system designer must rely on test sets provided by the vendor [5]. These precomputed tests usually require high-cost boundary scan to apply them to the IP circuits in an SOC, they are difficult to modify for (re)synthesized IP circuits, and they can make at-speed testing impossible [1].

To address these problems, we are developing a new ATPG methodology for IP-based designs, which aims to generate tests that are realization-independent in the sense that, subject to some minor constraints, the tests are guaranteed to cover all specified faults in all implementations of the target designs. The tests are derived from high-level, functional specifications and cover high-level fault models that are more comprehensive than the standard single-stuck line (SSL) model; they also do not require boundary scan. Here we outline a realization-independent test generation algorithm of this kind called RIBTEC, which handles block-structured circuits and represents a step toward solving the SOC testing problem. We also present some preliminary experimental results using RIBTEC, which are quite promising.

Realization-Independent Tests

First we introduce a high-level fault model based on non-exhaustive "universal" tests, and describe a practical way to apply it to functional blocks embedded in large circuits. The universal test set (UTS) of a logic function z consists of all minimal true and maximal false expanded vectors of z [3]. For example, consider block2 of the three-block circuit in Fig. 1a. Input vector abcd = 0001 is false because z₁(0001) = 0; it is maximal because its expanded form abb'cc'd = 001011 is not less than any other expanded false vector, so the UTS_z1 includes 0001. The UTS for block2 consists of UTS_z1 and UTS_z2; see Fig. 1b. A block's UTS detects all multiple stuck-line (MSL) faults in what we call balanced inversion parity (BIP) realizations of the block [1]. A BIP realization such as that of Fig. 1c, is defined by the property that all paths from a unate variable to an output have the same inversion parity; this is an extension of the old unate-gate network concept [3, 4]. Almost all practical circuits automatically satisfy the BIP condition [1], or else can easily be modified to do so, hence the restrictions it imposes are negligible.

In the past, universal tests have been considered impractical and largely ignored for two reasons. First, although a UTS can be small for a unate function, it grows rapidly with the number of nonunate variables. In the worst case, a UTS includes all input vectors. For example, the UTS of an N-bit adder, which has no unate variables, contains all 2^(2N+1) input vectors. Second, if all tests in the UTS for an embedded block cannot be applied from the external inputs, full fault coverage may not be achieved. For example, the three boldface tests of UTS_z1 in Fig. 1b cannot be applied to block2, because block1 cannot generate bc = 01, and block3 prevents some responses to these tests from propagating to the external output z.

We have devised a technique called realization-independent block testing for cores (RIBTEC) that can resolve the preceding problems. Many circuits such as datapaths consist of blocks that are at least partially unate or are relatively small. RIBTEC constructs compact test sets from the UTSs for these blocks using only their functions and a block-level structural description of the overall circuit. The RIBTEC test set for an N-bit adder consisting of 3 blocks (propagate/generate, carry, and sum) given by Fig. 2 contains as few as 2N + 4 test vectors, but covers many adder styles such as ripple-carry, carry-lookahead (CLA), and carry-select (CS), in all their BIP implementations [1]. When its UTS cannot be applied to an embedded block, RIBTEC computes a modified UTS called a RIB test set (RTS), which detects all detectable MSL faults in that particular embedding. For UTS_z1 in Fig. 1b, RIBTEC computes the RTS given by Fig. 1d, in which the 3 inapplicable tests in UTS_z1 are replaced by the 2 new tests in boldface. Identifying all inapplicable vectors to compute the RTS is time-consuming, so RIBTEC incorporates a fast algorithm to compute replacements directly from the inapplicable tests in the UTS. We define a realization independent block (RIB) fault as any fault condition that causes a block to generate an erroneous output when a RIB test is applied. By detecting all RIB faults, we are guaranteed to cover all detectable MSL faults in each block of the circuit under test.

Experimental Results

We have implemented an ATPG program called RIBTEC that employs the forgoing RTS generation algorithm and RIB fault model. RIBTEC computes primary input vectors that apply an RTS to every (embedded) block and propagate the block's responses to the circuit's primary outputs. The program uses a circuit model specified in behavioral Verilog code.

So far, we have applied RIBTEC to a few combinational benchmark circuits of moderate size. For example, Fig. 3 shows a high-level specification of the ISCAS-85 benchmark c880. This is an 8-bit ALU with control logic, and is depicted here as a multi-block system consisting of an IP-style core (shaded) surrounded by user-defined logic. RIBTEC generates 196 tests for the c880 which provide 100% coverage of its RIB faults. We obtained similar results for a variant of the much larger c7552 benchmark (a 34-bit ALU), and several other datapath circuits including adders and magnitude comparators; see Fig. 4. These results are compared with test sets generated by a conventional ATPG tool represented by Atalanta, which was targeted at SSL faults in specific gate-level implementations of the same circuits. The RIB fault coverage listed in Fig. 4 shows that RIBTEC achieves a very high degree of realization independence (100% RIB fault coverage) with test sets slightly larger than Atalanta's. The conventional ATPG tool, on the other hand, while providing 100% coverage of SSL faults in the target implementations, has very poor realization independence.

In summary, RIBTEC represents a novel ATPG methodology that ensures exceptionally high realization independence with relatively small test sets, and appears well-suited to testing embedded IP circuits. Although we have only demonstrated RIBTEC for combinational datapath circuits, the approach can be extended to more complex IP-type testing problems. We are currently refining the functional fault model, developing block partitioning techniques for less structured circuits, and extending the test generation algorithm to sequential ATPG.

Acknowledgment: This research was supported by the National Science Foundation under Grant No. MIP-9503463.

References

1. H. Kim and J. P. Hayes, "High-Coverage ATPG for Datapath Circuits with Unimplemented Blocks," Submitted for publication, Feb. 1998.
2. B. T. Murray and J. P. Hayes, "Testing ICs: Getting to the Core of the Problem," IEEE Computer, vol. 29, pp. 32-38, Nov. 1996.
3. S. M. Reddy, "Complete Test Sets for Logic Functions," IEEE Trans. CAD, vol. C-22, pp. 1016-1020, Nov. 1973.
4. U. Sparmann et al., "Minimal Delay Test Set for Unate Gate Networks, " Proc. Asian Test Symp., pp. 155-163, 1996.
5. N. A. Touba and B. Pouya, "Testing Embedded Cores Using Partial Isolation Rings," Proc. VLSI Test Symp., pp. 10-16, 1997.