Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2007-11-13
2007-11-13
Whitmore, Stacy (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
10996293
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.
REFERENCES:
patent: 5847965 (1998-12-01), Cheng
patent: 6442743 (2002-08-01), Sarrafzadeh et al.
patent: 6480991 (2002-11-01), Cho et al.
patent: 6601226 (2003-07-01), Hill et al.
patent: 6851099 (2005-02-01), Sarrafzadeh et al.
patent: 7073144 (2006-07-01), Alpert et al.
patent: 2004/0158802 (2004-08-01), Wong et al.
patent: 2005/0015738 (2005-01-01), Alpert et al.
patent: 2005/0132306 (2005-06-01), Smith et al.
patent: 2005/0268267 (2005-12-01), Shang
patent: 2006/0031804 (2006-02-01), Alpert et al.
patent: 2006/0063156 (2006-03-01), Willman et al.
patent: 2006/0190899 (2006-08-01), Migatz et al.
Alpert et al., “Multilevel Circuit Partitioning,” IEEE Transactions on CADICS, vol. 17, No. 8, pp. 655-667, Aug. 1998.
Karypis et al., “Multilevel Hypergraph Partitioning: Applications in VLSI Domain,” IEEE Transactions on VLSI Systems, vol. 7, No. 1, pp. 69-79, Mar. 1999.
Alpert Charles Jay
Nam Gi-Joon
Reda Sherief Mohamed
Villarrubia Paul Gerard
International Business Machines - Corporation
Musgrove Jack V.
Rossoshek Helen
Salys Casimer K.
Whitmore Stacy
LandOfFree
Clustering techniques for faster and better placement of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Clustering techniques for faster and better placement of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clustering techniques for faster and better placement of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3878090