On Theoretical And Practical Considerations Of Path Selection For Delay Fault Testing

In current industrial practice, critical path selection is an indis-pensable step for AC delay test and timing validation. Tradition-ally, this step relies on the construction of a set of worse-case paths based upon discrete timing models. The assumption of discrete timing models can be invalidated by delay effects in the deep sub-micron domain, where timing defects and process variation are sta-tistical in nature. In this paper, we study the problem of optimizing critical path selection, under both fixed delay and statistical de-lay assumptions. With a novel problem formulation and new the-oretical results, we prove that the problem in both cases are com-putationally intractable. We then discuss practical heuristics and their theoretical performance bounds, and demonstrate that among all heuristics under consideration, only one is theoretically feasi-ble. Finally, we provide consistent experimental results based upon defect-injected simulation using an efficient statistical timing anal-ysis framework. 1