Patent ID: 7509611

Claim:
A method of clustering circuit elements in a circuit design, the method comprising: grouping a plurality of circuit elements in a circuit design into a plurality of size balanced clusters; heuristically optimizing a spatial locality metric for the plurality of circuit elements by iteratively: performing a swap of circuit elements between clusters among the plurality of clusters; calculating the spatial locality metric after performing the swap; and selectively discarding the swap based upon the calculated spatial locality metric; and terminating iteration of the heuristic optimization after reaching an endpoint; wherein each cluster is associated with a desired centroid, wherein the spatial locality metric is based at least in part upon a distance from a circuit element to the desired centroid of a cluster, wherein the desired centroid for each cluster defines a position along an axis defined in a layout of the circuit design, and wherein the spatial locality metric is based at least in part upon a distance from a circuit element to the desired centroid of a cluster along the axis.