Title :
An optimal design for parallel test generation based on circuit partitioning
Author :
Xiang, Dong ; Wei, Dao-zheng
Author_Institution :
CAD Lab., Acad. Sinica, Beijing, China
Abstract :
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
Keywords :
VLSI; automatic testing; digital integrated circuits; graph colouring; integer programming; integrated circuit testing; linear programming; logic testing; parallel processing; scheduling; circuit partitioning; integer linear programming model; maximum parallelism; multiprocessor system; optimal design; optimal test generation scheme; parallel test generation; parallel testing graph; sequential test generation events; test scheduling problem; vertex chromatic number; vertex coloring; Circuit testing; Computers; Design automation; Integer linear programming; Laboratories; Multiprocessing systems; Parallel processing; Processor scheduling; Sequential analysis; System testing;
Conference_Titel :
VLSI Design, 1994., Proceedings of the Seventh International Conference on
Conference_Location :
Calcutta
Print_ISBN :
0-8186-4990-9
DOI :
10.1109/ICVD.1994.282706