Subgrid detailed routing

Details Subgrid detailed routing Subgrid detailed routing

1999-04-28

2003-01-14

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06507941

ABSTRACT:

FIELD OF THE ART
The present invention relates to a router for use in fabricating integrated circuit chips, and, more specifically, a subgrid detailed router
BACKGROUND OF THE RELATED ART
In the art of integrated chip layout, routing is the term used describe placing wires into locations on an integrated circuit chip. There are two conventional approaches to detailed routing, which are grid based routing systems, and gridless routing systems.
Prior to discussing detailed routing, it is helpful to put in context the overall design steps that are conventionally implemented when fabricating the physical design of an integrated circuit chip using a physical design system. As illustrated in
FIG. 1
, the overall design flow of the physical design includes receiving a cell level netlist, as shown in step
2
. Thereafter, this cell level netlist is used to determine the placement of modules that exist within the netlist into locations on the chip, shown as step
4
. Modules will contain information relating to a combination of logical functions, and will include the pin and obstacle information needed for routing purposes. The netlist will also contain information relating to the various different pins that need to be interconnected. Thereafter, in a global routing step
6
, a global routing grid (which may have been implemented in the placement step), is used to route various wires between pins of modules that traverse paths over several global routing grids. In a following detailed routing step
8
, a detailed routing grid (or simply routing grid hereafter) is implemented, typically at a higher resolution than the previously discussed global routing grid, and the detailed placement of wires is performed. The output of the detailed routing step
8
is an integrated circuit fabrication mask.
In a conventional grid based detailed routing system, each of the different layers of an integrated circuit chip is represented in the detailed routing grid. The detailed routing grid is a 3D representation, with each of the different layers of the integrated circuit needed for routing purposes having a uniform area that is subdivided into the routing grids previously discussed, thereby forming a grid pattern for each layer.
FIG. 2A
illustrates one layer of such a 3D routing grid, in which that layer is subdivided into a grid pattern
10
having separate grids
12
of uniform size. This uniform size of the grids
12
is typically determined by the minimum width of the wires that can be obtained plus the minimum spacing that must be maintained between adjacent wires and/or vias.
The 3D routing grid will have layers corresponding to the different routing layers. As shown in
FIG. 2B
, a typical integrated circuit will have at least a semiconductor layer, and three wiring layers, such as HVH wiring layers, which stands for horizontal, vertical and horizontal wiring. In HVH wiring, one wiring layer (H
1
) is generally used to make horizontal traversals, another wiring layer (V) is generally used to make vertical traversals, and another layer (H
2
) is generally used to make horizontal traversals. Using these different wiring layers, and vias that interconnect adjacent layers together, pins of modules that need to be interconnected can be connected together using the 3D routing grid.
When performing detailed routing, the detailed router receives chip technology description data and data that has been generated as a result of the global routing step, which describe data including the number of layers (levels) on which rectangles representing wires can be generated, the minimum allowed width of any part of the path of rectangles, and the minimum allowed separation between any non-electrically-connected rectangles, as is conventionally known.
In detailed routing, data associated with the various modules is received. For detailed routing purposes, the detailed router interprets this information either as a pin or an obstacle. For any set of pins being interconnected, those pins are not obstacles, but other pins, and other wires that have been previously generated, as well as other obstacles, must be avoided in order to avoid a short circuit. Each of these pins and obstacles is represented as a set of rectangular shapes and will have an associated position and associated layer that is maintained in the database.
Various conventions are used for the representation of pins, wires (or nets) and obstacles in a grid. A common convention—called the centerline convention—is that the grid describes the acceptable location for the centerline of the paths that is used during the expansion process to determine the path of a net. When a net is routed, the path must stay away from existing obstacles, such as other wires, vias, and pins of other nets that have been previously placed in the 3D routing grid. In order to stay away from these obstacles, they are modeled by marking certain grid points as invalid. Thus, every intersection of the horizontal and vertical equidistant gridlines is tracked as a position to which the center of a square of a net to be routed may be assigned when legal. Such an assignment is legal if the square centered on the grid point has legal separation with respect to all other rectangles not associated with the net currently being routed. It may require traversals over several proposed paths before a successful traversal results in a placement location being found
FIG.
3
. illustrates a representation of a portion of a routing grid and the obstacles and pins associated therewith. As can be seen, associated with one module are pins
12
A and
12
b
, and obstacles
14
A and
14
B. Associated with another module are Pins
12
C and
12
D; and obstacles
14
C and
14
D. Furthermore, the region marked
14
E shows the interconnection of the pins
12
B and
12
C. Thus, for interconnections of other nets, the region marked
14
E will also be an obstacle.
Using a list of the different pins that need to be connected, the detailed router will traverse a path from the initial pin location (such as pin
12
B in
FIG. 3
, to an endpoint pin location (such as pin
12
C In reply to FIG.
3
). It should be noted that in many cases, there exist many different possible connection locations to which the endpoint pin location can legally go, and once the detailed router finds a first such endpoint pin location, it has completed its task for that net, and will then move onto routing the next net. It should be noted that provision is also made for routing vias that connect conductors that exist at different adjacent levels and are used to form a single wire.
With that background description of grid based routing in mind, it will be appreciated that detailed routing grids are represented as a set of grid points and a set of edges between adjacent grid points. A so-called cost value is associated with every edge. Thus, detailed routing is a combinatorial optimization with the objective being to find a path of vertices between not yet connected features that are part of the net, including its pins. One manner in which to find the path between two points in a grid (such as two pins of different modules that need to be connected) can be found using a shortest path algorithm such as Dijkstra's shortest path algorithm. Routers that operate in the above-described manner are known as Lee-type routers.
In a detailed router, obstacle and wire congestion modeling analyses are also used in grid based routing systems to increase the likelihood that the particular wire placement determined during the global routing stage can actually be implemented at a finer level (i.e., within a portion of the grid in which it was placed). However, regardless of the effort put into these modeling techniques, they are either too optimistic at the expense of routing completion or too pessimistic at the expense of density. Thus, as integrated circuits become more complex and deep submicron designs proliferate, conventional grid based routing systems are not able to implement all of the design requirements. For example, in deep submicron des

Affiliated with

Also associated with

Rating

Subgrid detailed routing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Subgrid detailed routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subgrid detailed routing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3028133