Statistical multilayer process space coverage for at-speed test

Increasingly large process variations make selection of a set of critical paths for at-speed testing essential yet challenging. This paper proposes a novel multilayer process space coverage metric to quantitatively gauge the quality of path selection. To overcome the exponential complexity in computing such a metric, this paper reveals its relationship to a concept called order statistics for a set of correlated random variables, efficient computation of which is a hitherto open problem in the literature. This paper then develops an elegant recursive algorithm to compute the order statistics (or the metric) in provable linear time and space. With a novel data structure, the order statistics can also be incrementally updated. By employing a branch-and-bound path selection algorithm with above techniques, this paper shows that selecting an optimal set of paths for a multi-million-gate design can be performed efficiently. Compared to the state-of-the-art, experimental results show both the efficiency of our algorithms and better quality of our path selection. Copyright 2009 ACM.