Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-12-04
2003-12-16
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06665851
ABSTRACT:
FIELD OF THE INVENTION
Embodiments of the present invention relate to the field of electronic design automation (EDA). More particularly, embodiments of the present invention relate to techniques for cell placement and other optimizations used in the design and fabrication of integrated circuit devices.
BACKGROUND ART
The rapid growth of the complexity of modern electronic circuits has forced electronic circuit designers to rely upon computer programs to assist or automate most steps of the design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or “cells.” Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually.
One of the most difficult, complex and time-consuming tasks in the design process is known as placement. The placement problem is the assignment of a collection of connected cells to positions in a 2-dimensional arena, such that objective functions such as total wire length are minimized.
Conventionally, both the X and Y coordinates of the cells are determined simultaneously. There are many well known tools commercially available to accomplish this task, for example, the “Physical Compiler” by Synopsys of Mountain View, Calif.
Unfortunately, simultaneous two-dimensional placement is computationally intensive. Generally, such placement may take a period of time proportional to N (sqrt(N)) log(N), where N is the number of cells to be placed. Even on the fastest workstations, this task can take several hours for typical designs with several hundred thousand cells, and several days for designs with more than a million cells.
Although there are points in the design process at which the designer may be willing to trade long duration run times for increasing optimizations of the implementation of the design, there are many other circumstances when such time durations are very problematic.
For example, in the beginning stages of the physical design process, a “floor plan” is typically produced. A floor plan is a general guide as to the location that circuits, or groups of circuits, may be placed in the final design. In general, it is unacceptable to devote the time required for a full placement to this stage of the process. Further, the level of detailed optimization provided by full placement is generally not required at this stage.
As a result, floor planning is typically a very manual effort, involving much effort by the designers and their understanding of the overall design.
In addition, as chip designs continue to become more complex, and as the number of designers working on a chip continues to grow, it is becoming more and more difficult for a single person to understand the design well enough to produce an effective floor plan. Further, it is very difficult for a team, especially a large team to produce an effective floor plan working cooperatively. Consequently, an automated floor planning tool would be very appealing.
In other circumstances, reducing the time required to complete a design may be more important than achieving the optimal physical implementation of a design.
In addition, some simultaneous two-dimensional placers often benefit, in terms of run time and output quality, when given an initial placement to work from as a starting point. This seems to be especially the case when working on very large (several million cells) designs.
Therefore, for these reasons and more, a faster automatic method of placing electronic circuits in two dimensions is highly desirable. Such a method would have applications in floor planning, fast path designs and for seeding two dimensional placers, and potentially other areas of electronic design.
SUMMARY OF THE INVENTION
Embodiments of the present invention enable the fast placement of cells in an integrated circuit design. Further embodiments of the present invention enable a one-dimensional placement of cells in an integrated circuit design. Still further embodiments of the present invention enable the iterative improvement of an initial one-dimensional placement of cells in an integrated circuit design.
A method and system for the quick placement of electronic circuits using orthogonal one dimensional placements is disclosed. All circuits of a design are placed in a linear dimension to obtain a first placement. Next, those same circuits are placed in a second linear dimension, orthogonal to the first dimension, in order to obtain a second placement. Finally, a two dimensional placement for the circuits is created by selecting for each circuit element a first coordinate from the first placement and a second coordinate from the second placement.
Another embodiment of the present invention provides a method of placing electronic circuits in a linear dimension.
In one embodiment of the present invention, a first one-dimensional placement is iteratively improved.
REFERENCES:
patent: 5159682 (1992-10-01), Toyonaga et al.
patent: 5420800 (1995-05-01), Fukui
patent: 5579237 (1996-11-01), Shibuya
patent: 5627999 (1997-05-01), Cheng et al.
patent: 5638292 (1997-06-01), Ueda
Donelly Ross A.
Naylor William C.
Bever Hoffman & Harms LLP
Harms Jeanette S.
Lin Sun James
Siek Vuthe
Synopsys Inc.
LandOfFree
Quick placement of electronic circuits using orthogonal one... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quick placement of electronic circuits using orthogonal one..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quick placement of electronic circuits using orthogonal one... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3179710