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.