A polynomial-time algorithm for power constrained testing of core based systems

We address the problem of scheduling test sessions for core based systems-on-chip (SOC). We assume the built-in self-test methodology for testing individual cores and permit sharing of test resources (pattern generators and signature registers) among cores. Our objective is to minimize the test application time and the test area overhead, treating the total power dissipation as a constraint. A vast solution space exists for the problem of test scheduling. At one end of the spectrum is an entirely sequential test schedule which will consume the least test power, and at the other end of the spectrum is a fully concurrent test schedule which will consume the largest test power. Each of these solutions will differ in terms of the test area overhead and the test application time. We show a polynomial-time algorithm for finding an optimum power-constrained schedule which minimizes the test time. In our formulation, we implicitly address the problem of minimizing the test area overhead by introducing the notion of area penalty for merging the test sessions for two different cores. We argue that the merger of two test sessions for two different cores must address such issues as similarity of the cores being tested as well as layout-related issues. We capture these area penalties in the form of a desirability matrix which is the essential data structure for our scheduling algorithm. We report the results of our implementation of the scheduling algorithm on two circuits