Register clustering for clock network topology generation

• US 8,887,117 B1
• Filed: 10/07/2013
• Issued: 11/11/2014
• Est. Priority Date: 10/07/2013
• Status: Active Grant

• Current Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Original Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Inventors: Chuang, Yi-Lin
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US14/047,296
• Time in Patent Office: 400 Days
• Field of Search: 716/103, 716/105, 716/113, 716/124, 716/125
• US Class Current: 716/124
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/3312 Timing analysis
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G06F 30/396 Clock trees

Abstract

In some embodiments, in a method performed by at least one processor, a physical netlist of a placed integrated circuit (IC) chip design is received by the at least one processor. The physical netlist comprises a plurality of registers. Timing criticalities of register pairs in the registers are obtained by the at least one processor. Clusters of the registers are formed by the at least one processor. When forming cluster of the registers, candidate registers that are in physical vicinity of a first cluster are identified, and a first register is selected to be added to the first cluster by giving priority to a candidate register in a register pair across a boundary of the first cluster and with a higher timing criticality over a candidate register located closer to the first cluster. The registers in the same cluster have shorter non-common clock paths than the registers in different clusters.

Claims

1. A method performed by at least one processor, comprising:

receiving, by the at least one processor, a physical netlist of a placed integrated circuit (IC) chip design, the physical netlist comprising a plurality of registers;

obtaining, by the at least one processor, timing criticalities of register pairs in the registers;

assigning weights to the register pairs based on the timing criticalities of the register pairs; and

forming, by the at least one processor, clusters of the registers comprising;

identifying candidate registers that are in physical vicinity of a first cluster; and

selecting from the candidate registers a first register to be added to the first cluster by giving priority to a candidate register in a register pair across a boundary of the first cluster and with a higher timing criticality over a candidate register located closer to the first cluster, the registers in the same cluster having shorter non-common clock paths than the registers in different clusters, and the selecting comprising;

if a first candidate register in the candidate registers of the first cluster is unclustered, selecting the first candidate register as the first register to be added to the first cluster if sum of weights of other candidate registers in register pairs across the boundary of the first cluster is optimized.

2. The method according to claim 1, wherein the selecting further comprises:

if a first candidate register in the candidate registers of the first cluster is in a second cluster, selecting the first candidate register as the first register to be added to the first cluster if sum of weights of other candidate registers in register pairs across the boundary of the first cluster and the first candidate register in one or more register pairs across a boundary of the second cluster is optimized.

3. The method according to claim 1, wherein obtaining, by the at least one processor, timing criticalities of register pairs in the registers comprises:

performing timing analysis on the physical netlist to obtain the timing slacks of the register pairs in the registers.

4. The method according to claim 1, further comprising:

balancing loads in different clusters of the registers comprising;

identifying interfacing registers in a cluster with a higher load that interface with a cluster with a lower load; and

selecting a register in the interfacing registers to be reassigned to the cluster with the lower load that induces a smaller increase in sum of weights of register pairs across the cluster with the higher load and the cluster with the lower load than another register in the interfacing registers.

5. The method according to claim 1, further comprising:

updating the physical netlist to reflect connections of the clusters of registers to the corresponding clock paths.

6. A system, comprising:

at least one processor, configured to execute program instructions which configure the at least one processor as;

a timing analysis tool, configured to receive a physical netlist of a placed integrated circuit (IC) chip design comprising a plurality of registers and obtain timing criticalities of register pairs in the registers;

a weight-assigning module configured to assign weights to the register pairs based on the timing criticalities of the register pairs; and

a cluster-forming module, configured to receive the physical netlist and the timing criticalities of the register pairs and form clusters of the registers by performing operations comprising;

identifying candidate registers that are in physical vicinity of a first cluster; and

selecting from the candidate registers a first register to be added to the first cluster by giving priority to a candidate register in a register pair across a boundary of the first cluster and with a higher timing criticality over a candidate register located closer to the first cluster, the registers in the same cluster having shorter non-common clock paths than the registers in different clusters, and the selecting comprising;

if a first candidate register in the candidate registers of the first cluster is unclustered, selecting the first candidate register as the first register to be added to the first cluster if sum of weights of other candidate registers in register pairs across the boundary of the first cluster is optimized; and

at least one memory configured to store the program instructions.

7. The system according to claim 6, wherein the selecting of the cluster-forming module further comprises:

if a first candidate register in the candidate registers of the first cluster is in a second cluster, selecting the first candidate register as the first register to be added to the first cluster if sum of weights of other candidate registers in register pairs across the boundary of the first cluster and the first candidate register in one or more register pairs across a boundary of the second cluster is optimized.

8. The system according to claim 6, wherein the timing analysis tool obtains the timing criticalities of the register pairs in the registers by:

performing timing analysis on the physical netlist to obtain the timing slacks of the register pairs in the registers.

9. The system according to claim 6, further comprising:

the cluster-forming module further configured to balance loads in different clusters of the registers by performing operations comprising;

identifying interfacing registers in a cluster with a higher load that interface with a cluster with a lower load; and

selecting a register in the interfacing registers to be reassigned to the cluster with the lower load that induces a smaller increase in sum of weights of register pairs across the cluster with the higher load and the cluster with the lower load than another register in the interfacing registers.

10. The system according to claim 6, further comprising:

a physical netlist-updating module, configured to update the physical netlist to reflect connections of the clusters of registers to the corresponding clock paths.

11. A non-transitory computer-readable storage medium storing program instructions that when executed by a computer cause the computer to perform a method, the method comprising:

receiving, by the at least one processor, a physical netlist of a placed integrated circuit (IC) chip design, the physical netlist comprising a plurality of registers;

obtaining, by the at least one processor, timing criticalities of register pairs in the registers;

assigning weights to the register pairs based on the timing criticalities of the register pairs; and

forming, by the at least one processor, clusters of the registers comprising;

identifying candidate registers that are in physical vicinity of a first cluster; and

selecting from the candidate registers a first register to be added to the first cluster by giving priority to a candidate register in a register pair across a boundary of the first cluster and with a higher timing criticality over a candidate register located closer to the first cluster, the registers in the same cluster having shorter non-common clock paths than the registers in different clusters, and the selecting comprising;

if a first candidate register in the candidate registers of the first cluster is unclustered, selecting the first candidate register as the first register to be added to the first cluster if sum of weights of other candidate registers in register pairs across the boundary of the first cluster is optimized.

12. The computer-readable storage medium according to claim 11, wherein the selecting further comprises:

if a first candidate register in the candidate registers of the first cluster is in a second cluster, selecting the first candidate register as the first register to be added to the first cluster if sum of weights of other candidate registers in register pairs across the boundary of the first cluster and the first candidate register in one or more register pairs across a boundary of the second cluster is optimized.

13. The computer-readable storage medium according to claim 11, obtaining, by the at least one processor, timing criticalities of register pairs in the registers comprises:

performing timing analysis on the physical netlist to obtain the timing slacks of the register pairs in the registers.

14. The computer-readable storage medium according to claim 11, further comprising

balancing loads in different clusters of the registers comprising:

identifying interfacing registers in a cluster with a higher load that interface with a cluster with a lower load; and

selecting a register in the interfacing registers to be reassigned to the cluster with the lower load that induces a smaller increase in sum of weights of register pairs across the cluster with the higher load and the cluster with the lower load than another register in the interfacing registers.