Clustering techniques for faster and better placement of VLSI circuits
US7296252B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 22, 2004 |
| Grant date | Nov 13, 2007 |
| Priority date | — |
| Expiry date | Jan 13, 2026 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/398
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A placement technique for designing a layout of an integrated circuit by calculating clustering scores for different pairs of objects in the layout based on connections of two objects in a given pair and the sizes of the two objects, then grouping at least one of the pairs of objects into a cluster based on the clustering scores, partitioning the objects as clustered and ungrouping the cluster after partitioning. The pair of objects having the highest clustering score are grouped into the cluster, and the clustering score is directly proportional to the total weight of connections between the two objects in the respective pair. The clustering scores are preferably inserted in a binary heap to identify the highest clustering score. After grouping, the clustering score for any neighboring object of a clustered object is marked to indicate that the clustering score is invalid and must be recalculated. The calculating and grouping are then repeated iteratively based on the previous clustered layout. Cluster growth can be controlled indirectly, or controlled directly by imposing an upper bound on cluster size.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.