Optimal scan for pipelined testing: an asynchronous foundation

This paper addresses the problem of constructing a scan chain such that (1) the area overhead is minimal for latch-based designs, and (2) the number of pipeline scan shifts is minimal. We present an efficient heuristic algorithm to construct near-optimal scan chains. On the theoretical side, we show that part (1) of the problem can be solved in polynomial time, and that part (2) is NP-hard, thus precisely pinpointing the source of complexity and justifying our heuristic approach. Experimental results on three industrial asynchronous IC designs show (1) less than 0.1% extra scan latches for level-sensitive scan design, and (2) scan shift reductions up to 86% over traditional scan schemes