Method and apparatus for facilitating cell placement for an integrated circuit design

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform 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 bi-partite 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.

An apparatus for determining a feasible cell placement for an integrated circuit design, the apparatus comprising:

• a first receiving mechanism configured to receive an input cell placement, which assigns a position to each cell instance in the integrated circuit design;
• a second receiving mechanism configured to receive 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;
• a generating mechanism configured to generate a bi-partite 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;
• an associating mechanism configured to associate edges with shadow edges, wherein an edge and an associated shadow edge are incident to the same instance vertex;
• a ranking mechanism configured to rank the edges using the costs of the shadow edges;
• a selecting mechanism configured to select a set of edges using the edge rankings;
• and
• a determining mechanism configured to determine the feasible cell placement using the set of edges.