Agilent Technologies, Inc.

Xilinx, Inc.

Kang Wu

Susan L Stirrat

Neil G Jacobson

A cycle basis is efficiently determined for a directed graph. A first depth-first search of the directed graph classifies each of the edges of the directed graph to have a type that is one of a within-tree type for an edge within a tree of the first depth first search, a forward type for an edge skipping forward along the tree, a back type for an edge directed back along the tree, or a cross type for an edge between two subtrees of the tree. A second depth-first search of the directed graph determines a respective cycle for each of the edges of the back type. A third depth-first search of the directed graph determines a respective cycle for each of the edges of the cross type that is included a cycle. The basis is output the basis that specifies each of the respective cycles.

Determining a cycle basis of a directed graph

An Nalgorithm for optimizing correlated events, applicable to the optimization of the detection of redundant tests and inefficient tests (RIT's), is disclosed. This algorithm represents a set of N tests with L defects as N L-dimensional correlation vectors. The Nalgorithm optimizes in terms of the minimum set of vectors, and the set of vectors that take the minimum time to detect the L defects. The minimum set optimization determines a set of vectors (tests) that contains the minimum number of vectors (tests) by analyzing the correlation among the N vectors. This minimum set optimization provides the minimum test set containing all defects in an algorithm that takes O(N) operations. The minimum time optimization determines a sequence of vectors (tests) that will detect the defects in a minimum amount of time. Taking into the account of the different execution time of each vector (test), the algorithm analyzes the complicated correlation among the vectors (tests) and gives an optimized sequence of vectors (tests) within O(N) operations. The optimized sequence of vectors (tests) takes a minimum amount of time to find all the defects.

N-squared algorithm for optimizing correlated events

A test method for the detection of redundant tests and inefficient tests (RITs) used for testing integrated circuits (ICs) and a subsequent optimization of test complexity and test time duration. Empirical data from an execution of all tests of interest in a test plan, flow or suite of tests is collected. The empirical data is collected without stopping at errors. This empirical data is then used to determine the identity of one or more redundant and/or inefficient tests in the test plan. In order to reduce testing time and optimize the test flow, one of more of the following occurs. Redundant tests may be selectively removed, inefficient tests may be re-ordered to allow more efficient tests to be executed earlier in the test flow of the ICs, or some combination of this. RIT information is thus used to optimize the test flow, resulting in a reduction in test complexity and in test duration.

Growing community of inventors

Fort Collins, CO, United States of America

Kang Wu