Patent ID: 7571411

Claim:
A method of producing a flexible timing-driven routing tree, the method comprising the steps of: sorting two or more target nodes in accordance with data criticality; building a source-sink grid from one or more source nodes and the two or more target nodes; building an initial routing tree comprising the one or more source nodes; and executing a routing tree generation algorithm on the initial routing tree, utilizing the sorted two or more target nodes and the source-sink grid in accordance with a user-defined timing factor to construct a flexible timing-driven routing tree, wherein the user-defined timing factor specifies an extent of isolation between a first routing path and a second routing path, wherein the first routing path is between a given one of the one or more source nodes and a given one of the two or more target nodes, wherein there is no sharing between the first and second routing paths when the user-defined timing factor equals a first specific value, and wherein the amount of sharing between the first and second routing paths increases as the user-defined timing factor approaches a second specific value different from the first specific value; wherein the step of executing a routing tree generation algorithm comprises the steps of: initializing a current routing tree as the initial routing tree; determining if at least one of the two or more target nodes is unrouted; when at least one of the two or more target nodes is unrouted, executing a shortest path determination algorithm from a given node of the current routing tree to an unrouted target node in accordance with the timing factor and the source-sink grid to form a new current routing tree, and repeating the determining step; and defining the current routing tree as the flexible timing-driven routing tree when the two or more target nodes are routed; wherein, in the step of executing a shortest path determination algorithm, the given node of the current routing tree is selected from at least one of the one or more source nodes and one or more nodes on a routing path from a given one of the one or more source nodes to a given one of the two or more target nodes; wherein the step of executing a shortest path determination algorithm comprises the step of compiling a prioritized list of nodes in accordance with a shortest path that passes through a given node and extends from a certain one of the one or more source nodes to an unrouted target node of the two or more target nodes, and in accordance with the source-sink grid and the user-defined timing factor; wherein the step of compiling a prioritized list of nodes comprises the step of calculating a length of a shortest routing path from the given source node to the given node in accordance with the user-defined timing factor, wherein the above steps are performed on a computing system comprising a memory and a data processor coupled to the memory.