Name
Title | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2491477.2491486 | ACM Trans. Design Autom. Electr. Syst. |
Keywords | Field | DocType |
path selection algorithm,at-speed testing,recursive algorithm,random variable,order statistic,n correlated random variable,path selection,space coverage metric,mth order statistic,novel metric multilayer process,branch-and-bound path selection algorithm,order statistics | Data structure,Random variable,Mathematical optimization,Recursion (computer science),Parallel computing,Selection algorithm,Binary tree,Algorithm,Independent and identically distributed random variables,Time complexity,Order statistic,Mathematics | Journal |
Volume | Issue | ISSN |
18 | 3 | 1084-4309 |
Citations | PageRank | References |
3 | 0.39 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yiyu Shi | 1 | 553 | 83.22 |
| Xiong Jinjun | 2 | 801 | 86.79 |
| Vladimir Zolotov | 3 | 1367 | 109.07 |
| Chandu Visweswariah | 4 | 615 | 60.90 |