Method for identifying test points to optimize the testing of integrated circuits using a genetic algorithm

Abstract

A method for identifying, by way of a genetic algorithm, test points to be inserted in an integrated circuit (IC) chip to improve the testability of the IC is described. The algorithm is particularly well suited for large circuit designs (several million gates) because it allows to simultaneous insert multiple additional test points at critical locations of the IC to gain supplemental controlability and/or observability and thereby eliminating the drawbacks associated with the single test point approach. To further improve performance, cost function gradient techniques are applied to guide the selection of potential test points for consideration by the algorithm. Fault simulation of random patterns is used to more accurately distinguish between random pattern testable and random resistant faults, and to provide a more accurate set of initial probabilities for the cost function calculations. The algorithm further identifies a reduced set of potential candidate test points according to a variety of criteria such as cluster roots, i.e., nodes in the IC having poor controlability at the outputs but good controlability at the inputs, by considering the inputs to the cluster roots as good test point candidates. The genetic algorithm makes it a prime candidate for implementation using parallel processing, wherein multiple computers are used to simultaneously evaluate potential solutions.