Name
Abstract | ||
|---|---|---|
Adequate coverage of small-delay defects in circuits affected by statistical process variations requires identification and sensitization of multiple paths through potential defect sites. Existing K longest path generation (KLPG) algorithms use a data structure called path store to prune the search space by restricting the number of sub-paths considered at the same time. While this restriction speeds up the KLPG process, the algorithms lose their optimality and do not guarantee that the K longest sensitizable paths are indeed found. We investigate, for the first time, the effects of missing some of the longest paths on the defect coverage. We systematically quantify how setting different limits on the path-store size affects the numbers and relative lengths of identified paths, as well as the run-times of the algorithm. We also introduce a new optimal KLPG algorithm that works iteratively and pinpointedly addresses defect locations for which the path-store size limit has been exceeded in previous iterations. We compare this algorithm with a naïve KLPG approach that achieves optimality by setting the path-store size limit to a very large value. Extensive experiments are reported for 45nm-technology data. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/DATE.2012.6176507 | DATE |
Keywords | Field | DocType |
klpg approach,longest path,k longest sensitizable path,memory constraint,pinpointedly addresses defect location,klpg process,k longest path generation,defect coverage,path-store size,path-store size limit,longest path generation,new optimal klpg algorithm,process variation,logic gates,network routing,search space,data structure,integrated circuit,testing,flowcharts,logic gate,data structures,statistical analysis,generic algorithm | Data structure,Logic gate,Network routing,Computer science,Algorithm,Statistical process control,Digital storage,Longest path problem,Flowchart,Statistical analysis | Conference |
ISSN | Citations | PageRank |
1530-1591 | 9 | 0.58 |
References | Authors | |
14 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jie Jiang | 1 | 19 | 1.76 |
| Matthias Sauer | 2 | 195 | 20.02 |
| Alexander Czutro | 3 | 56 | 4.53 |
| Bernd Becker | 4 | 855 | 73.74 |
| Ilia Polian | 5 | 889 | 78.66 |