Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-12-04
2004-09-28
Whitmore, Stacy A. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06799309
ABSTRACT:
FIELD OF THE INVENTION
This invention is related to the field of design automation of VLSI chips, and more particularly, to a method of reducing the complexity of a floorplanner by solving the mix of large blocks and cell placement while preserving the accuracy of the floorplanner.
BACKGROUND OF THE INVENTION
With the increasing size and complexity of VLSI (Very Large Scale Integrated) circuit designs, the physical design task of floorplanning is gaining more relevance in today's design methodologies. These designs consist of a mix of large cells (the height of the object spanning over several circuit rows) and smaller ones. A VLSI design is represented by a netlist consisting of a set of blocks, large and small, interconnected by nets. (Nets can be viewed as wires or interconnections that link the various blocks in the design). A block may be a hard block, whose area and shape are already fixed, or a soft block consisting of smaller cells, and whose area and shape are flexible. Examples of large hard blocks are register arrays, memories, and the like. The blocks may also be small leaf level gates within the design, commonly referred to as leaf level cells. Floorplanning determines the best placement of the large blocks. Blocks that are to be placed on the layout by the floorplanner are termed “floorplan objects of interest” or simply large blocks
A typical approach to determine the best location of large blocks in a netlist consisting of a mixture of large blocks and small leaf level cells is to first group the smaller leaf level cells into large blocks. By way of example, the original netlist (consisting of large blocks and small leaf cells) is transformed, by performing some sort of clustering/partitioning, into a netlist consisting of large blocks.
Given a flat VLSI netlist, the step of creating flexible blocks from small leaf cells in the design amounts to creating a level of hierarchy therein. This step is achieved by grouping a set of cells into a separate flexible block. Grouping introduces extra floorplan objects of interest into the design. This type of explicit hierarchy creation has its own drawbacks since it introduces extra steps in the design process, potentially increasing the turnaround time (TAT) of the design.
When a transformed netlist is made of large blocks or floorplan objects of interest, the task of determining their locations on the layout can be done manually based on the design's architectural constraints or automatically. In the latter case, algorithmic techniques for global optimization are used, such as simulated annealing driven by a cost function that minimizes objectives like the total wire length between the large blocks. The term simulated annealing is derived from an analogous physical process of heating and then slowly cooling a substance to obtain a strong crystalline structure. In simulated annealing, the minimum cost function corresponds to the ground state of the substance. The simulated annealing process lowers the temperature in slow stages until the system “freezes”, after which no further changes occur. To apply simulated annealing, the system is initialized with a particular configuration. A new configuration is constructed by imposing a random displacement. If the energy of the new state is lower than the previous one, the change is accepted unconditionally and the system is updated. If the energy is greater, the new configuration is accepted probabilistically. More details regarding this technique are found in the article “Optimization by Simulated Annealing” by Kirkpatrick, Gellatt and Vecchi, published in the 1983 edition of Science. Subsequent placement of the leaf level cells is sensitive to the quality of the floorplan (location of large blocks in the design). Thus, achieving a good initial floorplan is critical for obtaining high quality final placement solutions.
Conventional floorplanning uses a representation wherein intermediate leaf levels cells are clustered to form the nodes of the netlist amounting to the previously stated creation of a hierarchical level. However, these do not describe a methodology wherein the abstracted cells are represented as abstract interconnections with constraint annotations (that helps to preserve the potential signal path behavior of the design), and which efficiently drives the optimization floorplanning algorithm with a path based abstract interconnection representation. (Abstract interconnections are referred as such because they do not exist in the given netlist, but are introduced in the present invention in order to account for intermediate leaf cells and related nets that were removed from the original netlist. Abstract interconnections will also be referred to hereinafter as abstract hyper-edges or abstract nets. A hyper-edge is a known term used in graph theory to indicate a connection between multiple nodes in a graph).
Simulated annealing has been used in the art as an effective floorplanning algorithm because of its ability to handle various constraints, such as block shapes, I/O constraints, etc. This technique belongs to a class of algorithms called “hill-climbing algorithms” that have the ability of finding near-optimal solutions to the problem on hand. However, the algorithm requires vast amounts of computational resources and is inherently slow. The algorithm is an iterative improvement algorithm. In each iteration, several solutions are generated by perturbing the initial solution. Then, the quality of the solutions is evaluated, the measure of quality forming the basis for their acceptance or rejection. A cost function is finally used to compute this measurement.
Some reasons for the inherent slowness of the annealer arise from the near-exhaustive nature of the solution space being contemplated, and from the time taken for evaluating the quality of the solution. The floorplanner that is used in the abstraction based flow is based on simulated annealing. In this context, novel techniques to reduce the complexity of an annealing based floorplanner working within a path based abstraction flow will also be described in the present invention hereinafter.
Referring to
FIG. 1
, the outline of a conventional physical design methodology is shown. The chip physical design step starts with floorplanning. The task of floor-planning results in associating coordinate locations to floorplan objects of interest on the two-dimensional region representing the chip layout.
Upon completion of the floorplanned design, the next step of placement results in associating specific coordinate locations for all remaining design objects in the netlist (other than the floorplan objects of interest). The objective is to arrive at valid locations for the floorplan objects of interest, in order that subsequent steps of the chip physical design may be successfully completed. Present techniques are known to be ineffective in optimizing a floorplan design.
OBJECTS OF THE INVENTION
Thus, it is an object of the invention to provide a method to optimize the floorplan of a VLSI chip using a path based hyper-edge representation.
It is another object to provide a framework consisting of a path oriented abstract representation of detailed VLSI design netlists alongside with mechanisms for generating them efficiently, and appropriate techniques for interfacing with, and for driving optimization based floorplanning algorithms
It is still another object to improve the efficiency of the floorplanner by reducing the complexity of an annealing based floorplanner working within a path based abstraction flow.
It is a further object to execute the abstraction phase by abstracting the leaf level logic (to reduce the solution space of the floorplanner) and reintroduce them in the form of floorplan constraints (to account for the presence of the leaf level logic while determining the location of large blocks).
It is yet another object to achieve by way of abstraction a significant improvement in the performance of a simulated annealing based floorplanner.
SUMMARY OF THE INVENTION
In a first aspect of the invent
Dhanwada Nagashyamala R.
Holmes Glenn E.
Morrell Joseph K.
Neves Jose Luis P. Correia
Venkateswaran Natesan
International Business Machines - Corporation
Lin Sun James
Schnurmann H. Daniel
Whitmore Stacy A.
LandOfFree
Method for optimizing a VLSI floor planner using a path... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for optimizing a VLSI floor planner using a path..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimizing a VLSI floor planner using a path... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3259628