Patent ID: 7370305

Claim:
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, wherein ranking the edges involves assigning a rank r(e) to edge e using the expression r(e)=cost anchor (v)+[cost(e)−costs(e)]; wherein cost(e) is the cost of the edge e, costs(e) is the cost of the shadow edge associated with the edge e, and cost anchor (v) is the cost of the anchor edge associated with the instance vertex v; wherein the edge e is incident on the instance vertex v; and wherein the anchor edge is the costliest shadow edge out of all the shadow edges associated with the live edges which are incident on instance vertex v.