An optimal design for parallel test generation based on circuit partitioning

A parallel testing graph (PTG) is offered to deal with the test scheduling problem; test scheduling in this paper refers to finding an optimal test generation scheme that allocates subcircuits or part of each subcircuit to the processors in a multiprocessor system. Test generation of subcircuits that can be run simultaneously should not share the same multiplexer in the process of test generation. The test scheduling problem is reduced to the vertex coloring of the PTG; and then the test scheduling problem is found to be solvable in quadratic time. Certainly, the number of sequential test generation events is equal to the vertex chromatic number of the PTG. The problem is how to minimize the vertex chromatic number of the PTG. On the basis of these results, an integer linear programming model is offered to design for maximum parallelism of the test generation problem, which minimizes the vertex chromatic number of the PTG, and thereby, maximizes the parallelism of the problem