On the Optimality of K Longest Path Generation Algorithm Under Memory Constraints

Provided by: edaa
Topic: Hardware
Format: PDF
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.

Find By Topic