Determination of most critical timing paths in digital circuits

A non-transitory computer-readable storage medium having program instructions that when executed by a computer implements a method for determining critical timing paths in an integrated circuit (IC), the method comprising:

• generating a most critical path to each node of a timing graph of nodes in the IC, wherein the generating does not include generating paths other than the most critical path;
• identifying the most critical path to a node of a destination register;
• invoking a next critical path function for the destination register to calculate a next critical path to the destination register, wherein the next critical path function recursively calls the next critical path function on one fan-in node of the node invoked in the next critical path function, the one fan-in node corresponding to a fan-in node which last contributed to the most critical path;
• selecting a next most critical path to the destination register from all paths to the destination register upon completion of invoking the next critical path function for the destination register;
• repeating the invoking and the selecting until a predetermined number of most critical paths have been selected for the destination register;
• and
• determining whether the IC is stable at a given clock frequency based on the selected most critical paths.

A method for determining critical rising timing paths in an integrated circuit (IC), the method comprising:

• computing a number K of most critical rising arrival paths for all destination registers in the IC based on a timing graph of nodes, wherein the computing does not include computing rising arrival paths other than the K most critical rising arrival paths, wherein computing the K most critical rising arrival paths for all destination registers includes creating a pseudo-node having all destination registers as children and invoking a recursive function at the pseudo-node to calculate each critical rising arrival path;
• computing K most critical falling arrival paths for all destination registers in the IC based on the timing graph of nodes, wherein paths other than the K most critical falling arrival paths are not computed;
• calculating K critical rising path slacks on each of the destination registers;
• calculating K critical falling path slacks on each of the destination registers;
• and
• selecting K most critical rising timing paths corresponding to most critical slacks from all the calculated critical rising path slacks on the destination registers, wherein at least one method operation is performed by a processor.