Patent ID: 7949976

Claim:
A machine implemented method, comprising: accessing, by a computer processor, a set of information that defines a circuit, wherein the circuit comprises a signal source, a plurality of sinks, one or more cells, and a plurality of paths coupling the signal source to each of the sinks, and wherein at least a subset of the paths comprises one or more of the cells; constructing, by a computer processor, a tree structure based at least partially upon the circuit, wherein the tree structure has the signal source represented as a root, has each sink represented as a leaf node, has a branch connecting each leaf node to the root such that each branch represents a path, and has each cell in a path represented as an intervening node in a branch, wherein a plurality of the leaf nodes have a corresponding timing adjustment requirement (TAR) associated therewith; propagating, for at least a particular leaf node having a particular TAR associated therewith, the particular TAR from the particular leaf node towards the root along a particular branch connecting the particular leaf node to the root, assigning at least a portion of the particular TAR to one or more intervening nodes on the particular branch; and replacing, for at least a certain intervening node on the particular branch to which at least a portion of the particular TAR has been assigned, a certain cell in the circuit represented by the certain intervening node with a replacement cell having timing characteristics that satisfy all or part of the at least a portion of the particular TAR that was assigned to the certain intervening node, wherein the at least a portion of the particular TAR that was assigned to the certain intervening node is referred to as a particular TAR amount, and wherein replacing the certain cell further comprises: selecting a certain replacement cell, wherein the certain replacement cell has timing characteristics that satisfy only a portion of the particular TAR amount, leaving a remainder of the particular TAR amount to be satisfied; replacing the certain cell in the circuit with the certain replacement cell; and assigning the remainder of the particular TAR amount to a child intervening node as additional TAR to be satisfied by a cell represented by the child intervening node, wherein the child intervening node is an intervening node situated between the certain intervening node and the particular leaf node on the particular branch.