Route-based cell merging
Methods and systems for performing route-based cell merging for a clock tree. The methods and systems access, from memory, a circuit design comprising a clock tree that interconnects a clock source to a plurality of clock sinks through a plurality of components. The methods and systems generate a Steiner tree that represents at least a portion of the clock tree including a portion of the plurality of components and identify two or more components of the portion of the plurality of components in the Steiner tree that are part of a direct fanout of a common node representing a set of components of the plurality of components. The methods and systems determine that the identified two or more components satisfy a mergeability function and, in response, modify at least a portion of the clock tree by merging the set of components into a single component.
1 . A method comprising:
accessing, from memory, a circuit design comprising a clock tree that interconnects a clock source to a plurality of clock sinks through a plurality of components;
generating a routing tree that represents at least a portion of the clock tree including a portion of the plurality of components;
identifying two or more components of the portion of the plurality of components in the routing tree that are part of a direct fanout of a common node representing a set of components of the plurality of components;
determining that the identified two or more components satisfy a mergeability function that defines whether or not components can be merged; and
in response to determining that the identified two or more components satisfy the mergeability function, modifying at least a portion of the clock tree by merging the set of components into a single component.
2 . The method of claim 1 , wherein the routing tree comprises a Steiner tree, and wherein the two or more components comprise a pair of inverters, and wherein the set of components comprise a pair of inverters.
3 . The method of claim 1 , wherein the two or more components comprise a pair of logic cells with identical functions, and wherein the set of components comprise a pair of logic cells with identical functions.
4 . The method of claim 1 , wherein the common node is coupled to the clock source, a buffer, or an inverter.
5 . The method of claim 1 , wherein a wirelength of the circuit design is increased by a negligible amount in response to merging the set of components into the single component.
6 . The method of claim 1 , wherein merging the set of components into the single component comprises merging the set of components without increasing a wirelength of the circuit design.
7 . The method of claim 1 , comprising in response to determining that the identified two or more components satisfy the mergeability function:
accessing user constraints, transition constraints, and timing constraints associated with the circuit design; and
conditionally merging the two or more components into the single component in response to determining that merging the set of components continue to satisfy the user constraints, transition constraints, and timing constraints associated with the circuit design.
8 . The method of claim 1 , wherein generating the routing tree comprises:
selecting a net driver from the clock tree;
identifying a group of components of the plurality of components that are part of a direct fanout of the net driver;
within the group of components, identifying a first set of components that are mergeable and a second set of components that are not mergeable;
excluding the first set of components from the routing tree while including a third set of components in a fanout path from the first set of components and including the second set of components, each of the third set of components and the second set of components being associated with a respective initial point in the routing tree.
9 . The method of claim 8 , wherein the routing tree is constructed with locations of inputs to the direct fanout of the net driver which is not mergeable and locations of the inputs to a fanout of the direct fanout which is mergeable.
10 . The method of claim 8 , comprising:
generating horizontal and vertical line segments from the net driver to each component of the third set of components and the second set of components, the routing tree comprising a set of routing points at junctions and corners where perpendicular line segments of the horizontal and vertical line segments meet.
11 . The method of claim 10 , comprising:
searching the horizontal and vertical line segments to find a set of initial points having multiple edges; and
replacing the set of initial points with merge points.
12 . The method of claim 11 , comprising:
removing any routing point of the set of routing points from the routing tree having only two edges; and
marking a remaining set of the routing points as merge points.
13 . The method of claim 12 , comprising:
traversing the merge points of the routing tree in a bottom up or top down manner to identify merge candidates for which respective components directly connected to the respective merge point satisfy the mergeability function.
14 . The method of claim 13 , comprising:
determining whether the merge candidates satisfy additional constraints associated with the circuit design to conditionally merge the merge candidates.
15 . The method of claim 1 , comprising:
generating a merge tree based on the routing tree, wherein the mergeability function is evaluated using the merge tree.
16 . A non-transitory computer readable medium comprising instructions that, when executed by at least one processor, configure the at least one processor to perform operations comprising:
accessing, from memory, a circuit design comprising a clock tree that interconnects a clock source to a plurality of clock sinks through a plurality of components;
generating a routing tree that represents at least a portion of the clock tree including a portion of the plurality of components;
identifying two or more components of the portion of the plurality of components in the routing tree that are part of a direct fanout of a common node representing a set of components of the plurality of components;
determining that the identified two or more components satisfy a mergeability function that defines whether or not components can be merged; and
in response to determining that the identified two or more components satisfy the mergeability function, modifying at least a portion of the clock tree by merging the set of components into a single component.
17 . The non-transitory computer readable medium of claim 16 , wherein the two or more components comprise a pair of inverters.
18 . The non-transitory computer readable medium of claim 16 , wherein the two or more components comprise a pair of buffers.
19 . The non-transitory computer readable medium of claim 16 , wherein a wirelength of the circuit design is increased by a negligible amount in response to merging the set of components into the single component.
20 . A system comprising:
one or more processors; and
a memory storing instructions that, when executed by the one or more processors, cause the system to perform operations comprising:
accessing, from memory, a circuit design comprising a clock tree that interconnects a clock source to a plurality of clock sinks through a plurality of components;
generating a routing tree that represents at least a portion of the clock tree including a portion of the plurality of components;
identifying two or more components of the portion of the plurality of components in the routing tree that are part of a direct fanout of a common node representing a set of components of the plurality of components;
determining that the identified two or more components satisfy a mergeability function that defines whether or not components can be merged; and
in response to determining that the identified two or more components satisfy the mergeability function, modifying at least a portion of the clock tree by merging the set of components into a single component.