Patent Document ID: 20070186200
Application ID: 11350667
Patent Status: 0

Claim One:
1. A method for determining a feasible cell placement for an integrated circuit design, the method comprising: receiving an input cell placement, which assigns a position to each cell instance in the integrated circuit design; receiving a set of regions within the integrated circuit design, wherein each region has a capacity constraint which can specify an upper limit on the total cell area that can be placed within the region; generating a bipartite graph which comprises instance vertices, region vertices, and edges, wherein an instance vertex is associated with a cell instance, a region vertex is associated with a region, and each edge is incident on an instance vertex and a region vertex, wherein each edge is assigned a cost that indicates the cost of placing the associated cell instance in the associated region; associating edges with shadow edges, wherein an edge and an associated shadow edge are incident to the same instance vertex; ranking the edges using the costs of the shadow edges; selecting a set of edges using the edge rankings; and determining the feasible cell placement using the set of edges.