Efficient Algorithms for Computing the Longest Viable Path in a Combinational Network

摘要

We consider the elimination of false paths in combinational circuits. We give the single generic algorithm that is used to solve this problem, and demonstrate that it is parameterized by a boolean function called the sensitization condition. We give two criteria which we argue that a valid sensitization condition must meet, and introduce four conditions that have appeared in the recent literature, of which two meet the criteria and two do not. We then introduce a dynamic programming procedure for the tightest of these conditions, the viability condition, and discuss the integration of all four sensitization conditions in the LLLAMA timing environment. We give results on the IWLS and ISCAS benchmark examples and on carry-bypass adders.