# US 10,769,345 B1 · Clock tree optimization by moving instances toward core route

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,769,345 B1
- Document ID: US10769345B1
- Status: Granted
- Kind: B1
- Application number: 16/228,451
- Filed: 2018-12-20
- Granted: 2020-09-08
- Earliest claimed: 2018-12-20
- Assignees: Cadence Design Systems, Inc.
- Applicants: Cadence Design Systems, Inc.
- Inventors: Andrew Mark Chapman; Zhuo Li
- Web page: https://patentgrep.com/patent/US10769345B1

## CPC

- G06F 30/396: Clock trees
- G06F 30/3312: Timing analysis
- G06F 30/392: Floor-planning or layout, e.g. partitioning or placement
- G06F 30/394: Routing (G06F30/396 takes precedence)
- G06F 30/3953: detailed
- G06F 30/398: Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36)
- G06F 30/30: Circuit design
- G06F 30/337: Design optimisation
- G06F 30/39: Circuit design at the physical level (physical level design for reconfigurable circuits G06F30/347)
- G06F 30/3947: global
- G06F 2111/04: Constraint-based CAD
- G06F 2119/12: Timing analysis or timing optimisation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Aspects of the present disclosure address improved systems and methods for core-route-based clock tree wirelength reduction. A method may include accessing an integrated circuit design comprising a clock tree comprising routes that interconnect terminals of a plurality of clock tree instances. The method further includes identifying a core route in the clock tree. The method further includes determining a first offset based on a distance between the first terminal and the core route and determining a second offset based on a distance from the second terminal to the core route. The method further includes determining a target offset based on a combination of the first and second offsets and moving the clock tree instance toward the core route by the target offset.

## Claims

### Claim 1

A system comprising:
one or more processors of a machine; and
a computer storage medium storing instructions, which when executed by the machine, cause the machine to perform operations comprising:
accessing an integrated circuit design in memory, the integrated circuit design comprising a clock tree comprising one or more routes that interconnect terminals of a plurality of clock tree instances, a clock tree instance of the plurality of clock tree instances comprising a first terminal and a second terminal;
identifying a portion of a route in the clock tree that has a maximum transitive fanout that is less than a transitive fanout threshold, the transitive fanout threshold corresponding to a threshold number of terminals connected to a branch in the route;
determining a first offset by measuring a distance between the first terminal of the clock tree instance and the identified portion of the route;
determining a second offset by measuring a distance between the second terminal of the clock tree instance and the identified portion of the route;
determining a target offset based on a combination of the first and second offsets;
moving the clock tree instance toward the identified portion of the route by the target offset; and
generating an updated clock tree for the integrated circuit design based on moving the clock tree instance toward the identified portion of the route.

### Claim 2 (depends on 1)

The system of claim 1, wherein the threshold number of terminals corresponds to a predetermined percentage of a total number of terminals in the clock tree.

### Claim 3 (depends on 1)

The system of claim 1, wherein the determining of the first offset comprises:
identifying a connected route of the first terminal;
accessing a binary tree equivalent of the connected route;
traversing the binary tree to identify a target node; and
determining a distance between the first terminal and the target node.

### Claim 4 (depends on 3)

The system of claim 3, wherein identifying of the target node is based on the target node having a transitive fanout that is less than the transitive fanout threshold.

### Claim 5 (depends on 3)

The system of claim 3, wherein identifying of the target node is based on the target node driving a wirelength that is less than a wirelength threshold.

### Claim 6 (depends on 3)

The system of claim 3, wherein:
the first terminal of the clock tree instance drives a connected clock net; and
the traversing of the binary tree comprises performing a top-down search of the binary tree from a root node to identify the target node, the root node corresponding to the first terminal.

### Claim 7 (depends on 3)

The system of claim 3, wherein:
the first terminal of the clock tree instance is driven by a connected clock net; and
the traversing of the binary tree comprises performing a bottom-up search of the binary tree from a leaf node to identify the target node, the leaf node corresponding to the first terminal.

### Claim 8 (depends on 1)

The system of claim 1, wherein:
the combination of the first and second offsets is a first combination of the first and second offsets;
the target offset is a first target offset; and
the operations further comprise:
determining a second target offset based on a second combination of the first and second offsets; and
moving the clock tree instance toward the identified portion of the route by the second target offset.

### Claim 9 (depends on 8)

The system of claim 8, wherein:
the first combination of the first and second offsets comprises a statistical mean of the first and second offsets; and
the second combination of the first and second offsets is a minimum of the first and second offsets.

### Claim 10 (depends on 8)

The system of claim 8, further comprising:
moving at least one additional clock tree instance in the clock tree, wherein the moving of the clock tree instance toward the identified portion of the route by the second target offset is performed subsequent to moving the at least one additional clock tree instance.

### Claim 11 (depends on 1)

The system of claim 1, wherein identifying the route in the clock tree is further based on a wirelength threshold.

### Claim 12 (depends on 1)

The system of claim 1, wherein the operations further comprise:
performing a validation to verify that moving the clock tree instance toward the identified portion of the route by the target offset results in a reduction to wirelength in the clock tree; and
moving the clock tree instance back to an initial location in response to an unsuccessful validation.

### Claim 13 (depends on 1)

The system of claim 1, wherein the operations further comprise:
generating a layout instance for the integrated circuit design based in part on the updated clock tree, the layout instance describing physical layout dimensions of the integrated circuit design.

### Claim 14

A method comprising:
accessing an integrated circuit design stored in memory, the integrated circuit design comprising a clock tree comprising one or more routes that interconnect terminals of a plurality of clock tree instances, a clock tree instance of the plurality of clock tree instances comprising a first terminal and a second terminal;
identifying a portion of a route in the clock tree that has a maximum transitive fanout that is less than a transitive fanout threshold, the transitive fanout threshold comprising a threshold number of terminals connected to a branch in the route;
determining, by at least one hardware processor, a first offset based on a distance between the first terminal of the clock tree instance and the identified portion of the route in the clock tree;
determining, by at least one hardware processor, a second offset based on a distance between the second terminal of the clock tree instance and the identified portion of the route;
determining, by at least one hardware processor, a target offset based on a combination of the first and second offsets;
moving, by the at least one hardware processor, the clock tree instance toward the identified portion of the route by the target offset; and
generating, by at least one hardware processor, an updated clock tree for the integrated circuit design based on moving the clock tree instance toward the identified portion of the route.

### Claim 15 (depends on 14)

The method of claim 14, wherein the determining of the second offset comprises:
identifying a connected route of the second terminal;
accessing a binary tree equivalent of the connected route;
traversing the binary tree to identify a target node, the target node having a transitive fanout that transgresses the transitive fanout threshold; and
determining a distance between the second terminal and the target node.

### Claim 16 (depends on 15)

The method of claim 15, wherein:
the first terminal of the clock tree instance drives a connected clock net; and
the traversing of the binary tree comprises performing a top-down search of the binary tree from a root node to identify the target node, the root node corresponding to the second terminal.

### Claim 17 (depends on 15)

The method of claim 15, wherein:
the first terminal of the clock tree instance is driven by a connected clock net; and
the traversing of the binary tree comprises performing a bottom-up search of the binary tree from a leaf node to identify the target node, the leaf node corresponding to the second terminal.

### Claim 18 (depends on 14)

The method of claim 14, wherein:
the combination of the first and second offsets is a first combination of the first and second offsets;
the target offset is a first target offset; and
the operations further comprise:
determining a second target offset based on a second combination of the first and second offsets; and
moving the clock tree instance toward the identified portion of the route by the second target offset.

### Claim 19 (depends on 18)

The method of claim 18, wherein:
the first combination of the first and second offsets comprises a statistical mean of the first and second offsets; and
the second combination of the first and second offsets is a minimum of the first and second offsets.

### Claim 20

A computer-storage medium storing instructions, which when executed by the machine, cause the machine to perform operations comprising:
accessing an integrated circuit design stored in memory, the integrated circuit design comprising a clock tree comprising one or more routes that interconnect terminals of a plurality of clock tree instances, a clock tree instance of the plurality of clock tree instances comprising a first terminal and a second terminal;
identifying a portion of a route in the clock tree based on a wirelength threshold;
determining a first offset based on a distance between the first terminal of the clock tree instance and a the route in the clock tree;
determining a second offset based on a distance between the second terminal of the clock tree instance and the identified portion of the route;
determining a target offset based on a combination of the first and second offsets;
moving the clock tree instance toward the identified portion of the route by the target offset;
generating an updated clock tree based on moving the clock tree instance toward the identified portion of the route; and
generating a layout instance for the integrated circuit design based in part on the updated clock tree, the layout instance describing physical layout dimensions of the integrated circuit design.