Order statistics for correlated random variables and its application to at-speed testing

Abstract

Although order statistics have been studied for several decades, most of the results are based on the assumption of independent and identically distributed (i.i.d.) random variables. In the literature, how to compute the mth order statistics of n correlated random variables is still a problem. This article proposes a recursive algorithm based on statistical min/max operations to compute order statistics for general correlated and not necessarily identically distributed random variables. The algorithm has an O(mn) time complexity and O(m+ n) space complexity. A binary tree-based data structure is further developed to allow selective update of the order statistics with O(nm2) time. As a vehicle to demonstrate the algorithm, we apply it to the path selection algorithm in at-speed testing. A novel metric multilayer process space coverage metric is proposed to quantitatively gauge the quality of path selection. We then show that such a metric is directly linked to the order statistics, and our recursive algorithm can thus be applied. By employing a branch-and-bound path selection algorithm with these techniques, this article shows that selecting an optimal set of paths for a multimillion-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. © 2013 ACM.