Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-11-02
2004-02-17
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06694502
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to integrated circuit design, and more specifically to a data structure and method for routing interconnections between components of an integrated circuit.
An overview of a typical design process for integrated circuits is shown in the flow diagram of FIG.
1
. The process can be generally divided into a front-end design phase and a back-end development phase. During the front-end phase, from a set of specifications, the engineer designs and develops a logical representation of the integrated circuit of interest in the form of a schematic, at step
10
. The schematic is then entered on computer workstation from which a circuit netlist is generated, at step
12
. The netlist defines the entire integrated circuit, including all components and interconnections. Alternatively, the integrated circuit information may be developed using hardware description language (HDL) and synthesis. With the aid of circuit simulation tools available on the workstation, the designer then simulates the functionality of the circuit, at step
14
. The circuit simulation process may involve several iterations of design modifications and improvements until the circuit design is finalized.
The back-end development involves several steps during which a final circuit layout (physical description) is developed based on the schematic. During placement step
16
, various building blocks (or cells) as defined by the finalized circuit schematic are placed within a predefined floor plan. For integrated circuits designed based on array or standard cell technology, the various circuit building blocks are typically predefined and made available in a cell library. Placement is followed by a routing step
18
, during which interconnects between circuit elements are routed throughout the layout. Finally, the accuracy of the layout versus the schematic is verified at step
20
, and if no errors or design rule violations are found at step
22
, then the circuit layout information is used for the process of fabrication at step
24
.
During placement step
106
a plurality of cells are selected from one or more cell libraries and the cell interconnects are determined. For example, groups of cells may be interconnected to functions as flip-flops, shift registers and the like. The routing of wires to interconnect the cells and achieve the aforementioned functions is performed during the routing step
18
, typically referred to as conducting paths, wires or nets.
For more complex designs, often at least four distinct layers of conducting medium are made available for routing. These layers include 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 typically employed for vertical and/or horizontal routing. It is a common practice to route each net by using one or more of the distinct layers of conducting medium. One layer of an adjacent pair of layers of conducting medium is typically reserved for connections running along one direction, e.g., the “x” direction, referred to as a preferred wiring direction. The remaining layer of the pair has a preferred wiring direction, which is orthogonal to the “x” direction, i.e., the preferred wiring direction is in the “y” direction. Some of the layers, such as the metal layers, are exclusively used for interconnection of components. The polysilicon layer may have a dual role, such as forming the gates of transistors as well as for interconnection of components. Electrical connections between two nets on adjacent layers is implemented with a “via” which is an etched or drilled hole in the substrate for allowing a conductive path to extend from one layer to another layer.
Conventional design methodologies typically use a two-step process for determining the final size and location of each conducting path during the routing step
18
. The first step is the global routing step for roughly determining conducting paths. The “rough” wiring pattern generated in this step is known as a “global route.” Subsequently, a second detailed routing step for precisely determining a final routing pattern according to the global routes is used. This final routing pattern determined by the detailed routing step is known as a “detailed route.” It is important to entertain certain constraints when routing an integrated circuit. These constraints are arranged in two categories: electrical rules and design rules. Electrical rules concern electrical performance parameters that must be satisfied by the conducting paths, e.g., cross-talk, circuit parasitics and the like. Design rules concern physical parameters that must be satisfied by the conducting paths, e.g., minimum spacing between adjacent wires, minimum wire width and the like. Owing to ever decreasing size of the components on integrated circuits and the increasing complexity of the constraints, computer-aided design (CAD) has become indispensable.
As a result, several algorithms are currently employed to assist in routing nets employing CAD technology. Specifically, the integrated circuit of interest is mapped into a memory of the CAD system. The algorithm searches the information in the memory concerning the integrated circuit in order to define a conductive path between two or more points. The maze algorithm is one of the most widely used algorithms for routing nets due to its superior searching capability. The searching capability afforded by the maze algorithm enables determination of the shortest distance required for net routing. Specifically, the maze algorithm commences at a starting location and expands outwardly therefrom to neighboring locations until the destination is reached, in order to identify a preferring conducting path. However, the processing time of the maze algorithm is long, on the order of a few days to several weeks.
Other algorithms have been employed to reduce the search time for a conducting path between two points. To that end, algorithms such as a hierarchical algorithm, a line search algorithm and a channel router algorithm have been developed. While each of these algorithms reduces the time required to route wires. The drawbacks differ.
To assist in search of a conducting path, the integrated circuit may be mapped into locations of a memory of the CAD system as an imaginary grid of points, referred to as a gridded data structure. The points may be stored as a sparse matrix, i.e., as line intervals in a preferred direction. The grid, or sparse matrix, is employed by the CAD system to route and track the location of the various conducting paths and components that make up the integrated circuit. To that end, status information is stored at each of the data points. The status information includes various attributes, such as data point state information: information concerning the availability of data point to receive a wire, i.e., open, or open with high cost, invalid or blocked. Additional information concerns the data point location in x, y and z coordinates; the net identifier, i.e., which net the data point is associated, the shapedef, the geometric shape of the wire present, as well as the allowed shapeclass and current conducting path cost.
Another technique maps the wiring plane of an integrated circuit into locations of a CAD system memory as a plurality of longitudinal tiles, referred to as a tiled data structure. Electrical components present in the wiring plane, as well as other blockages, are represented as polygonal objects. The tiled data structure requires much less memory to map the integrated circuit, compared to the gridded data structure. However, conducting path searches of the tiled data structure by the various algorithms are slower than the conducting path searches of the gridded data structure.
What is need, therefore, is a technique for routing wires for integrated circuits that is memory efficient.
SUMMARY OF THE INVENTION
Provided is a data structure containing wiring information for an integrated circuit and a method for storing the same in a computer reada
Mehrotra Sharad
Patel Parsotam T.
Rossoshek Helen
Sun Microsystems Inc.
Zagorin O'Brien & Graham LLP
LandOfFree
Data structure for fine-grid multi-level VLSI routing and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data structure for fine-grid multi-level VLSI routing and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure for fine-grid multi-level VLSI routing and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301030