Patent ID: 7984410

Claim:
A computer-implemented method for specifying positions of a plurality of instances within an integrated circuit (IC) by converging total overflow ratio (TOFR), wherein TOFR indicates the degree of instance overlap and is based on the parameters comprising at least one of the area occupied by moveable instances and the area not occupied by pre-placed instances that is available for accommodating moveable instances, the method comprising using a computer to perform the steps of: a. defining a hierarchy of blocks, wherein a parent block residing at the next higher level of the hierarchy comprises a plurality of component block instances or cell instances residing at current level of the hierarchy; b. for each hierarchy level from the highest level to the lowest level one by one, generating a placement within the hierarchy level, further comprising the steps of: b1. assigning the initial position of each instance residing at the hierarchy level according to the position of its respective parent block, or by assigning the initial position of each instance to a pre-determined position if the hierarchy level is the highest level; b2. providing an initial objective function; b3. iteratively determining the new positions for a plurality of moveable instances according to the current positions of the instances and the directions taken by the gradient of the objective function until the cost of the objective function ceases to decrease; b4. modifying the objective function according to TOFR if TOFR is not converged to a pre-defined range for the hierarchy level; and b5. repeating step b3 and step b4 until TOFR is converged to the pre-defined range for the hierarchy level.