4.3.6. Shortest and longest path algorithms
Given a combinational circuit in which each gate has its own delay value, suppose we want to find the critical path—that is, the path with the longest delay—from an input to an output. A trivial solution is to explicitly evaluate all paths from the input to the output. However, the number of paths can grow exponentially with respect to the number of gates. A more efficient solution exists: we can model the circuit as a directed graph whose edge weights are the delays of the gates. The longest path algorithm can then give us the answer more efficiently.
In this subsection, we present various shortest and longest path algorithms. Not only can they calculate the delays of critical paths, but they also ...
Get Electronic Design Automation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
