Patent ID: 8261223

Claim:
A computer-implemented method for specifying positions of a plurality of instances and the orientation for each rotatable instance thereof 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 or rotatable instances residing at current level of the hierarchy; and 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 in Cartesian coordinate for representing the position of each instance and in Polar coordinate for representing the orientation of a rotatable instance relative to the center of the rotatable instance; b3. determining the positions of instances and the orientations of rotatable instances by iteratively executing the following sub-steps until the cost of the objective function ceases to decrease, wherein the sub-steps comprise: b31. determining new position for each of the plurality of instances according to current position of the instance and the direction taken by the gradient of the objective function with respect to the Cartesian coordinate; and b32. determining new orientation for each rotatable instance according to current orientation of the rotatable instance and the rotating direction taken by the gradient of the objective function with respect to the Polar coordinate; 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.