Formulating SoC test scheduling as a network transportation problem. - Koranne, S.
A formulation of core-based system-on-chip (SoC) test scheduling as a network transportation problem is presented. Given a set of tests, with demands for transportation of test bits (either for test stimuli or test response) and unrelated parallel test resources (e.g., test access mechanisms or built-in self-test engines), the authors determine the start times and resource mappings of all the tests such that the finish time for the complete SoC test is minimized. The problem is NP-hard and they present an approximation algorithm using a result from the solution of the single source unsplittable flow problem. The proposed method uses the number of test bits that need to be transported for a test as the invariant and is hence relatively independent of the test application and execution model. Experimental results on benchmark SoCs demonstrate that their method outperforms the state-of-the-art integer linear programming formulations, not only in terms of schedule quality, but also significantly reduces the computation time. Index Terms
Keywords: NP-hard problem; VLSI test; Approximation algorithm; Automatic test equipment; Built-in self-test engines; Computation time; Core-based SoC test scheduling; Demands for transportation; Embedded core-based test scheduling; Execution model; Finish time minimization; Network transportation problem; Parallel test resources; Parallel unrelated multiprocessor scheduling; Resource mappings; Schedule quality; Single source unsplittable flow problem; Start times; Test access mechanisms; Test response; Test stimuli