Statistical multilayer process space coverage for at-speed test

ABSTRACT

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.

REFERENCES

• 1: V. Iyengar, T. Yokota, K. Yamada, T. Anemikos, R. Bassett, M. Degregorio, R. Farmer, G. Grise, M. Johnson, D. Milton, M. Taylor, and F. Woytowich. At-speed structural test for high-performance ASICs. Proc. International Test Conference, pages 2.4:1--10, October 2006. Santa Clara, CA.
• 2: L-C. Wang, J-J. Liou, and K-T. Cheng. Critical path selection for delay fault testing based upon a statistical timing model. IEEE Transactions on Computer-Aided Design of ICs and Systems, 23(11):1550--1565, November 2004.
• 3: V. Iyengar, J. Xiong, S. Venkatesan, V. Zolotov, D. Lackey, P. A. Habitz, and C. Visweswariah. Variation-aware performance verification using at-speed structural test and statistical timing. IEEE International Conference on Computer-Aided Design, November 2007. San Jose, CA.
• 4: M. L. Bushnell and V. D. Agrawal. Essentials of electronic testing for digital, memory and mixed-signal VLSI circuits. Kluwer Academic Publishers, 2000.
• 5: M. Sharma and J. H. Patel. Finding a small set of longest testable paths that cover every gate. International Test Conference, pages 974--982, October 2002. Baltimore, MD.
• 6: J-J. Liou, A. Krstic, L-C. Wang, and K-T. Cheng. False-path-aware statistical timing analysis and efficient path selection for delay testing and timing validation. Proc. 2002 Design Automation Conference, pages 566--569, June 2002. New Orleans, LA.
• 7: W. Qiu and D. M. H. Walker. An efficient algorithm for finding k longest testable paths through each gate in a combinational circuit. International Test Conference, pages 592--601, Setpember 2003. Charlotte, NC.
• 8: V. Zolotov, J. Xiong, H. Fatemi, and C. Visweswariah. Statistical path selection for at-speed test. IEEE International Conference on Computer-Aided Design, November 2008. San Jose, CA.
• 9: C. Visweswariah, K. Ravindran, K. Kalafala, S. G. Walker, and S. Narayan. First-order incremental block-based statistical timing analysis. Proc. 2004 Design Automation Conference, pages 331--336, June 2004. San Diego, CA.
• 10: L. Zhang, W. Chen, Y. Hu, J. A. Gubner, and C. C. Chen. Correlation-preserved non-gaussian statistical timing analysis with quadratic timing model. In Proc. Design Automation Conf, pages 83--88, June 2005.
• 11: R. M. Dudley. Real Analysis and Probability. Cambridge University Press, 2002.
• 12: H. A. David and H. N. Nagaraja. Order Statistics. John Wiley and Sons, 2003.
• 13: H. M. Barakat and Y. H. Abdelkader. Computing the moments of order statistics from nonidentical random variables. Statistical Methods and Applications, 13:13--24, 2004.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Theory

Keywords:
order statistics, path selection, process space coverage