Two algorithms are presented for minimizing the length of complete tests for VLSI systems subject to maximum power dissipation constraints. One is a general algorithm that applies to systems in which test lengths are unequal. The second is a simplified version, for the case in which all test lengths are equal. The paper’s main contribution is an abstract formalism for modeling the problem. The major steps are well-known graph algorithms, such as finding all cliques in a graph and finding a minimal-cost cover.
The two algorithms are interesting from a theoretical point of view, but the proposed application seems impractical. The maximum power dissipation for each test session must be known. The authors suggest using maximum peak power for all parallel tests. This is extremely pessimistic, since it is unlikely that the peak power for all tests will occur at the same instant. Even so, obtaining an estimate of the maximum peak power for a test session is virtually impossible. Such data are not available for existing VLSI devices, and obtaining such results, even when the internal circuit is known exactly, seems daunting. These algorithms are too complex, since two separate steps require solving NP-complete problems. The paper is also much too long, because the authors discuss numerous irrelevant side issues. The casual reader will find this paper difficult to digest.