テストパターンの静的圧縮における厳密解と貪欲解の比較

摘要

本稿ではドントケアに基づく静的テストパターン圧縮をクリーク被覆問題や頂点彩色問題として定式化し，厳密解法と貪欲解法による解法実験を行った．その結果，今回実験を行ったほとんどのテストパターンについて圧縮されたテストパターン数の上界と下界が厳密解と一致することがわかった．また，この性質はテストパターンの生成方法を変えても保たれていた．このことから，貪欲法の解は厳密解に非常に近いことがわかり，多数の回路に対して長時間かけて厳密解を求める効果が少ないことがわかった．さらに圧縮の妨げになっているテストパターンを示し，圧縮効果を高める方法を考察する．%In this paper, we formulate static test compaction using don't cares as a minimum clique cover problem and a vertex coloring problem. We made experiments on exact solution methods and greedy solution methods. For most test patterns used in this experiment, the upper and lower bounds are close to the exact solution. This holds for wide variety of test generation methods. We coclude that greedy solutions are very close to exact solutions and there is small advantage in computing exact solutions for many circuits. Moreover, we indicate the subset of test patterns which is a bottleneck of test compaction, and consider the way to improve the compaction efficiency.