Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-04-11
2003-12-30
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06671867
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the fabrication and design of semiconductor chips and integrated circuits, and more particularly to a method of designing the physical layout (placement) of logic cells in an integrated circuit, and the wiring (routing) of those cells.
2. Description of the Related Art
Integrated circuits are used for a wide variety of electronic applications, from simple devices such as wristwatches, to the most complex computer systems. A microelectronic integrated circuit (IC) chip can generally be thought of as a collection of logic cells with electrical interconnections between the cells, formed on a semiconductor substrate (e.g., silicon). An IC may include a very large number of cells and require complicated connections between the cells. A cell is a group of one or more circuit elements such as transistors, capacitors, resistors, inductors, and other basic circuit elements grouped to perform a logic function. Cells types include, for example, core cells, scan cells and input/output (I/O) cells. Each of the cells of an IC may have one or more pins, each of which in turn may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip. For more complex designs, there are typically at least four distinct layers of conducting media available for routing, such as a polysilicon layer and three metal layers (metal-1, metal-2, and metal-3). The polysilicon layer, metal-1, metal-2, and metal-3 are all used for vertical and/or horizontal routing.
An IC chip is fabricated by first conceiving the logical circuit description, and then converting that logical description into a physical description, or geometric layout. This process is usually carried out using a “netlist,” which is a record of all of the nets, or interconnections, between the cell pins. A layout typically consists of a set of planar geometric shapes in several layers. The layout is then checked to ensure that it meets all of the design requirements, particularly timing requirements. The result is a set of design files known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator. During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design.
The present invention is directed to an improved method for designing the physical layout (placement) and wiring (routing) of cells. Cell placement in semiconductor fabrication involves a determination of where particular cells should optimally (or near-optimally) be located on the surface of a integrated circuit device. Due to the large number of components and the details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use computer aided design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
A few years ago, pure standard cell designs could be considered the norm, but today's “chunky” designs contain large blocks of reserved areas for memory arrays, proprietary (IP) blocks, etc. Consequently, placement now resembles the problem of arranging “dust” logic around these large blocks. Since the large blocks tend to dictate the design footprint, one can no longer assume that the placeable area in some way matches the total cell area of the design; indeed, there is a marked trend of increasing percentage of free space available on the chip. One might think increased free space, or “design sparsity”, would make placement easier. However, even though the dust logic is a small percentage of the chip area, there can still be millions of cells in the dust logic that have profound effects on timing and routability.
Placement algorithms are typically based on either a simulated annealing, top-down cut-based partitioning, or analytical paradigm (or some combination thereof). Recent years have seen the emergence of several new academic placement tools, especially in the top-down partitioning and analytical domains. The advent of multilevel partitioning as a fast and extremely effective algorithm for min-cut partitioning has helped spawn a new generation of top-down cut-based placers. A placer in this class partitions the cells into either two (bisection) or four (quadrisection) regions of the chip, then recursively partitions each region until a global coarse placement is achieved. Such recursive cut-based placement can perform quite well when designs are dense, but they perform rather poorly when the designs are sparse. Sparse designs tend to fool the partitioner since it does not know how to handle the large flexibility in the balance tolerance.
Analytical placers typically solve a relaxed placement formulation (such as minimizing total quadratic wirelength) optimally, allowing cells to temporarily overlap. Legalization is achieved by removing overlaps via either partitioning or by introducing additional forces and/or constraints to generate a new optimization problem. The classic analytical placers, PROUD and GORDIAN, both iteratively use bipartitioning techniques to remove overlaps. The PROUD placer is discussed in the article by R.-S. Tsay, E. S. Kuh, and C.-P. Hsu, “PROUD: A Fast Sea-of-Gates Placement Algorithm”, Proc. 25th IEEE/ACM Design Automation Conference, pp. 318-323 (1988). The GORDIAN placer is discussed in the article by J. Kleinhaus, G. Sigl, F. Johannes and K. Antreich, “GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization,” IEEE Trans. on Computer-Aided Design, 10(3), pp. 356-365 (1991).
Analytical placers can perform poorly when the data is naturally degenerate (which occurs when few objects are fixed to I/O ports) since it becomes difficult to legalize a placement where thousands of cells have virtually the same location. Also, analytic methods may have difficulties in dense designs where legalization is forced to significantly alter the analytic solution.
Finally, cut-based partitioners can suffer from their inability to see the global picture.
FIGS. 1A-1C
show a simplified example with three cells A, B and C, and one potential unit (chip) of free space. Using a conventional multilevel partitioning algorithm, the first partitioning assigns one cell A to one side, and two cells B and C to the other side. The minimum cut (min-cut) solution, i.e., minimizing the number of wires that cross, results in the placement shown in FIG.
1
A. This placement is adequate, but has more total wirelength than the preferred solution shown in
FIG. 1B
(which has a slightly higher net cut). An analytical solver does no better, and would place all three cells to the left of the cut-line, as shown in
FIG. 1C
(the overlap of the cells maybe adjusted by any one of several legalization methods).
In light of the foregoing, it would be desirable to devise an improved method of designing integrated circuits which could yield placements that are more efficient (compact), having reduced total wirelengths while maintaining relatively low net cuts. A more compact distribution leads to better timing and overall performance, and additionally reduces design time, and time to market. It would be further advantageous if the method could utilize the strength of analytical placers on sparse designs to improve the poor performance of cut-based placers.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved method of designing integrated circuits.
It is another object of the present i
Alpert Charles J.
Nam Gi-Joon
Villarrubia Paul G.
Musgrove Jack V.
Salys Casimer K.
Siek Vuthe
Tat Binh C.
LandOfFree
Analytical constraint generation for cut-based global placement does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Analytical constraint generation for cut-based global placement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analytical constraint generation for cut-based global placement will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3116940