Patent ID: 8359565

Claim:
A method for use by a general purpose computing device that is configured to generate a set of test patterns with which to test an integrated circuit chip, the method comprising: generating, by a processor of the general purpose computing device, the set of test patterns; and selecting, by the processor of the general purpose computing device, a set of paths on which to test the set of test patterns, wherein the generating and the selecting are performed simultaneously, and wherein the selecting comprises: sensitizing one or more potential paths for inclusion in the set of paths, wherein the sensitization is performed as the one or more potential paths are traversed, wherein the sensitizing comprises, for each given path in the one or more potential paths: traversing the given path through a combined graph in order to assess an impact of the given path on the set of test patterns, wherein the combined graph merges a logical representation of the integrated circuit chip with a timing graph for the integrated circuit chip, wherein the traversing comprises: setting, at each node of the given path, a required transition; justifying values of the required transition by propagating the values forward and backward along circuits of the integrated circuit chip; and when the justifying is successful, computing a pair of input vectors corresponding to the required transition, and adding the pair of input vectors to the set of test patterns; and wherein the setting comprises computing a pair comprising: a signal that produces the required transition along at least one of the one or more potential paths; and a distance between a current node of the given path and an output of the given path.