Test generation and evaluation for large sequential circuits

Computer Engineering Research Center
The University of Texas at Austin

Generating tests for sequential circuits is known to be a difficult problem, and existing automatic test pattern generation (ATPG) packages, both from university research and industry, can only deal with relatively small circuits. Several directions to solve this problem are explored.

We have developed new techniques of hierarchical fault simulation to evaluate the quality of generated tests. These approaches greatly reduce the simulation time for large designs. Techniques applicable to hardware accelerators as well as distributed workstations have been developed. The latter approach has been applied to the Pentium Pro (TM) processor.

In collaboration with Professor Daniel Saab, Case Western Reserve University, we pioneered the use of genetic algorithms for sequential circuit test generation. The test generation system using these ideas, CRIS, generates tests with high fault coverages on large sequential circuits.

Our extensive research in hierarchical test generation recently resulted in a novel technique of functional test generation for embedded modules. This allows a commercial gate level sequential automatic test pattern generation (ATPG) package to generate tests for faults in the module, in times which are orders of magnitude lower, with coverages which are significantly higher, when compared with test generation on the flat chip. We abstract the behavior of the logic surrounding the module under consideration by deriving constraints for the embedded module described in a hardware description language and synthesized to gates using commercial synthesis tools. Then, the commercial sequential ATPG tool is used to generate module level vectors for a transformed circuit which includes the synthesized constraints and the original embedded module. Since this transformed circuit is much smaller (it only has logic relevant to the embedded module), commercial tools can develop high quality tests for this circuit in times which are significantly lower than when considering the entire circuit.

Selected Papers

C.-H. Chen and J. A. Abraham, "Generation and Evaluation of Current and Logic Tests for Switch-Level Sequential Circuits," Journal of Electronic Testing: Theory and Applications, vol. 3, December 1992, pp. 359-366.

M. E. Levitt, K. Roy and J. A. Abraham, "BiCMOS Logic Testing," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 2, June 1994, pp. 241-248.

G. Ganapathy and J. A. Abraham, "Hardware Acceleration Alone will not make Fault Grading ULSI a Reality," Proceedings IEEE International Test Conference, Nashville, TN, October 28-30, 1991, pp. 848-857.

R. B. Mueller-Thuns, J. T. Rahmeh, J. A. Abraham, J. A. Wehbeh and D. G. Saab, "Concurrent Hierarchical and Multilevel Simulation of VLSI Circuits," Simulation, vol. 60:2, February 1993, pp. 79-91.

S. Karthik and J. A. Abraham, "A Framework for Distributed VLSI Simulation on a Network of Workstations," Simulation, vol. 60:2, February 1993, pp. 95-104.

Abstract

A distributed framework for logic simulation is presented. Switch-level simulation has been mapped to a distributed platform using a network of workstations on an Ethernet bus. Model parallelism is used with preprocessing to partition the circuit to be simulated among the processors. The simulation algorithm is decoupled from the communication layers to ensure easy portability. We have proposed a high level pipeling scheme with multiple buffers to overcome the effects of a low bandwidth network. Speedups of up to 4.1 with 5 processors have been obtained for medium sized ISCAS benchmark circuits. The speedups achieved using distributed simulation are very close to that obtained by the same switch-level simulator implemented on a shared memory parallel machine. Novel techniques to improve the performance of distributed simulation have also been implemented on a shared memory parallel machine.

R. B. Mueller-Thuns, D. G. Saab, R. F. Damiano and J. A. Abraham, "VLSI Logic and Fault Simulation on General Purpose Parallel Computers," IEEE Transactions on Computer Aided-Design, vol. 12, March 1993, pp. 446-460.

S. Karthik, M. Aitken, G. Martin, S. Pappula, B. Settler, P. Vishakantaiah, M. d'Abreu and J. A. Abraham, "Distributed Mixed Level Logic and Fault Simulation on the Pentium Pro Microprocessor," Proceedings IEEE Int'l Test Conference, October 1996, pp. 160-166.

Abstract

Logic and fault simulation are crucial steps in the design process for verifying the correctness of a circuit and generating high quality manufacturing tests. Traditionally, Intel has been relying on dedicated hardware accelerators to meet its fault grading needs. The unprecendented size and complexity of the Pentium Pro microprocessor were forseen to severely stretch the existing compute resources at Intel. Exploiting the design hierarchy and using the processing power of distributed computers were identified to be key areas which could alleviate the simulation problem. This paper describes a distributed mixed level logic and fault simulator that has been developed using an RTL simulation engine as the core, in conjunction with a gate level logic/fault simulator. The techniques and algorithms developed have been successfully applied on the Pentium Pro microprocessor.

D. G. Saab, Y. G. Saab and J. A. Abraham, "Automatic Test Vector Cultivation for Sequential VLSI Circuits Using Genetic Algorithms," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, October 1996, pp. 1278 - 1285.

Abstract

This paper discusses a new approach for generating test vectors, using test cultivation, for both combinational and sequential VLSI circuits described hierarchically at the transistor, gate, and higher levels. The approach is based on continuous mutation of a given input sequence and on analyzing the mutated vectors for selecting the test set. The hierarchical technique used in the analysis drastically reduces the memory requirements, allowing test generation for large circuits. The test cultivation algorithms are simulation-based and a test set can be cultivated for any circuit that can be simulated logically. In particular, general MOS digital designs can be handled, and both stuck-at and transistor faults can be accurately modeled. Using the approach, tests were generated with very high fault coverage for gate-level circuits as well as for transistor level circuits.

R. S. Tupuri and J. A. Abraham, "A Novel Functional Test Generation Method for Processors using Commercial ATPG," Proceedings Int'l Test Conference, November 1997, pp. 743-752.

Abstract

As the sizes of general and special purpose processors increase rapidly, generating high quality manufacturing tests for them is becoming a serious problem in industry. This paper describes a novel method for hierarchical functional test generation for processors which targets one embedded module at a time and uses commercial ATPG tools to derive tests for faults within the module. Applying the technique to benchmark processor designs, we were able to obtain test efficiencies for the embedded modules of the procesors which were extremely close to what the commercial ATPG could do with complete access to the module. The hierarchical approach used produced this result, using the same commercial tool, but required a CPU time several orders of magnitude less than when using a conventional, flat view of the circuit.

Back to: