Generating and selecting bit-stack candidates from a graph using dynamic programming
View Patent ↗Bit stacks of an integrated circuit design are identified in a netlist by analyzing cell clusters. Candidate bit stacks are generated for each cluster using cone tracing, and wirelength costs are calculated for the candidate bit stacks based on the cells' locations from a previous (e.g., global) placement. The bit stack partition having a minimum total wirelength cost is selected for the final bit stacks. The invention can find K bit stacks in a cell cluster having N input cells and M output cells, where K, N and M are all different. The method is advantageously made timing aware by weighting connections between cells using weights based on timing information. Once the final bit stacks have been identified, the information can be included in the netlist and passed to a datapath placer for optimized placement.
1. A method of identifying bit stacks in an integrated circuit design comprising:
receiving a circuit description for the integrated circuit design which includes a plurality of cells interconnected to form a plurality of nets, the cells having locations from a previous placement, by executing first instructions in a computer system;
identifying at least one cluster of the cells from the design, by executing second instructions in the computer system;
generating candidate bit stacks from groups of interconnected cells in the cluster, by executing third instructions in the computer system;
calculating wirelength costs for the candidate bit stacks based on the cell locations, by executing fourth instructions in the computer system; and
selecting a partition from a plurality of different partitions of the candidate bit stacks as final bit stacks wherein said selecting is based on a minimum total wirelength cost for the partition equal to the sum of the wirelength costs of all candidate bit stacks in the partition, by executing fifth instructions in the computer system.
2. The method of claim 1 , wherein said generating includes cone tracing from output cells of the cluster to input cells of the cluster.
3. The method of claim 1 , wherein the previous placement is derived from multiple iterations of a global placement routine.
4. The method of claim 1 , wherein the circuit description further includes timing information, and said calculating includes weighting connections between cells using weights based on the timing information.
5. The method of claim 1 , wherein said selecting includes dynamic programming whereby a group of cells which have been identified as a possible bit stack for a candidate partition are used to exclude other possible bit stacks for that candidate partition when the other possible bit stacks include any of the cells in that group.
6. The method of claim 1 , wherein the cluster is identified as a datapath structure.
7. The method of claim 1 , wherein the cluster has a number N of input cells and a number M of output cells where M≠N, and the partition has a number K of bit stacks where K≠N, K≠M, and K, M, and N are integers greater than zero.
8. A computer system for identifying bit stacks in an integrated circuit design comprising:
one or more processors which process program instructions;
a memory device connected to said one or more processors; and
program instructions residing in said memory device for receiving a circuit description for the integrated circuit design which includes a plurality of cells interconnected to form a plurality of nets wherein the cells having locations from a previous placement, identifying at least one cluster of the cells from the design, generating candidate bit stacks from groups of interconnected cells in the cluster, calculating wirelength costs for the candidate bit stacks based on the cell locations, and selecting a partition from a plurality of different partitions of the candidate bit stacks as final bit stacks wherein the selecting is based on a minimum total wirelength cost for the partition equal to the sum of the wirelength costs of all candidate bit stacks in the partition.
9. The computer system of claim 8 , wherein the generating includes cone tracing from output cells of the cluster to input cells of the cluster.
10. The computer system of claim 8 , wherein the previous placement is derived from multiple iterations of a global placement routine.
11. The computer system of claim 8 , wherein the circuit description further includes timing information, and the calculating includes weighting connections between cells using weights based on the timing information.
12. The computer system of claim 8 , wherein the selecting includes dynamic programming whereby a group of cells which have been identified as a possible bit stack for a candidate partition are used to exclude other possible bit stacks for that candidate partition when the other possible bit stacks include any of the cells in that group.
13. The computer system of claim 8 , wherein the cluster is identified as a datapath structure.
14. The computer system of claim 8 , wherein the cluster has a number N of input cells and a number M of output cells where M≠N, and the partition has a number K of bit stacks where K≠N, K≠M, and K, M, and N are integers greater than zero.
15. A computer program product for identifying bit stacks in an integrated circuit design comprising:
a computer-readable storage medium; and
program instructions residing in said storage medium for receiving a circuit description for the integrated circuit design which includes a plurality of cells interconnected to form a plurality of nets wherein the cells having locations from a previous placement, identifying at least one cluster of the cells from the design, generating candidate bit stacks from groups of interconnected cells in the cluster, calculating wirelength costs for the candidate bit stacks based on the cell locations, and selecting a partition from a plurality of different partitions of the candidate bit stacks as final bit stacks wherein the selecting is based on a minimum total wirelength cost for the partition equal to the sum of the wirelength costs of all candidate bit stacks in the partition.
16. The computer program product of claim 15 , wherein the generating includes cone tracing from output cells of the cluster to input cells of the cluster.
17. The computer program product of claim 15 , wherein the previous placement is derived from multiple iterations of a global placement routine.
18. The computer program product of claim 15 , wherein the circuit description further includes timing information, and the calculating includes weighting connections between cells using weights based on the timing information.
19. The computer program product of claim 15 , wherein the selecting includes dynamic programming whereby a group of cells which have been identified as a possible bit stack for a candidate partition are used to exclude other possible bit stacks for that candidate partition when the other possible bit stacks include any of the cells in that group.
20. The computer program product of claim 15 , wherein the cluster is identified as a datapath structure.
21. The computer program product of claim 15 , wherein the cluster has a number N of input cells and a number M of output cells where M≠N, and the partition has a number K of bit stacks where K≠N, K≠M, and K, M, and N are integers greater than zero.