Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-03-27
2002-04-23
Smith, Matthew (Department: 2763)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06378121
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an automatic global routing device, in a CAD system which designs and develops a large-scale integrated circuit (LSI) and a logic circuit by means of a computer, for automatically placement and routing component cells on LSI chips or printed boards so as to minimize the entire size or minimize a routing length and a global routing method therefor.
2. Description of the Related Art
Automatic placement and routing processing of this kind for placement and routing integrated circuit chips by an automatic routing device using a CAD system is executed in four steps, floor plan processing, placement processing, global routing processing and detailed routing processing.
In the following, conventional automatic placement and routing methods will be described with reference to
FIGS. 7 and 8
. First, at the floor plan processing, one places macro cells on an integrated circuit to be processed, and determines a region in which basic cells are to be placed as shown in FIG.
8
(A) (Step
701
of FIG.
7
). This floor plan processing is conducted semi-automatically. Next, determination is made whether routing processing is possible for the integrated circuit subjected to the floor plan processing (Step
702
). When the determination is made that routing is impossible, the routine returns to Step
701
to execute the floor plan processing over again.
When the determination is made at Step
702
that routing is possible, one places desired basic cells at the basic cell placement region as shown in FIG.
8
(B) (Step
703
). Then, determination is made whether routing processing is possible for the integrated circuit subjected to the basic cell placement processing (Step
704
). When the determination is made that routing is impossible, the routine returns to Step
703
to conduct the placement processing over again. When the determination is still made at Step
704
that routing is impossible even after further trials of the placement processing a preset number of times, the routine returns to Step
701
to start over with the floor plan processing.
When the determination is made at Step
704
that routing is possible, one divides the integrated circuit chip to be processed into rectangles (global routing cells) and determines a routing route of each net on a divisional unit basis as shown in FIG.
8
(C) (Step
705
). “Net” here represents a route from an output terminal of an arbitrary gate circuit to an input terminal of other gate circuit. For each net, net information indicating which terminals are to be connected is defined. Global routing processing at Step
705
is conducted based only on a wire capacitance of a global routing cell boundary (degree of wire congestion) as will be described later. Next, determination is made whether routing processing is possible for the integrated circuit subjected to the global routing processing (Step
706
). When the determination is made that routing is impossible, the routine returns to Step
705
to conduct the global routing processing over again. When the determination is still made at Step
706
that routing is impossible even after further trials of the global routing processing a preset number of times, the routine returns to Step
703
to conduct the placement processing over again. Furthermore, when the determination is still made at Step
706
that routing is impossible even after further trial of the placement processing a preset number of times, the routine returns to Step
701
to start over with the floor plan processing.
When the determination is made at Step
706
that routing is possible, one determines a detailed routing route within each global routing cell as shown in FIG.
8
(D) (Step
707
). Then, one determines if there is a shorted net or an unrouted net (Step
708
). When there is a shorted net or an unrouted net, the routine returns to Step
707
to conduct the detailed routing processing over again. If a shorted net or an unrouted net is still detected at Step
708
even after further trials of the detailed routing processing preset times, the routine returns to Step
705
to conduct the global routing processing over again. Further, when a shorted place or a place yet to be wired is still detected at Step
708
even after further executions of the global routing processing preset times, the routine returns to Step
703
to start over with the placement processing. Further, if a shorted place or a place yet to be wired is still detected at Step
708
even after further executions of the placement processing preset times, the routine returns to Step
701
to start over with the floor plan processing. Then, when there remains neither a shorted place nor a place yet to be wired (yes at Step
708
), the automatic placement and routing processing is completed.
Next, with reference to
FIG. 9
, detailed description will be made of the global routing processing (
FIG. 7
, Step
705
) and the following routing possibility/impossibility determination processing (
FIG. 7
, Step
706
) at the conventional automatic placement and routing processing. Conventional global routing processing of this kind is disclosed, for example, in Japanese Patent Laying-open (Kokai) No. Heisei 3-278446, entitled “Automatic Routing Method for Semiconductor Device”.
First, as shown in FIG.
10
(A), divide a chip into rectangles (global routing cells) (Step
901
). In FIG.
10
(A), a black square represents a terminal, while a region denoted by slant lines represents a global route for the connection of terminals. “Global routing cell” is also called a unit routing region. In the figure, a boundary between adjacent global routing cells is called a “global routing cell boundary”. More specifically, each global routing cell has four global routing boundaries in the upper, lower, right and left directions.
Next, calculate a wire capacitance which indicates how many wires can pass through each global routing cell boundary (Step
902
). With reference to
FIG. 11
, a method of calculating a wire capacitance will be described. In
FIG. 11
, one specific global routing cell is denoted by solid lines and a routing track is denoted by a dotted line. Here, “routing track” represents a passage on which routing can be made. “Wire capacitance” is therefore equal to the number of routing tracks passing through a global routing cell boundary. In addition, a routing inhibited region is denoted as a block of slant lines. In practice, routing is made over a plurality of layers. In other words, routing tracks and routing inhibited regions exist individually on each layer in practice. In this example, description will be made of one-layer routing for the purpose of simplicity. In the example illustrated in
FIG. 11
, five routing tracks exist in the right-and-left direction and five routing tracks also exist in the up-and-down direction. In this case, if there exists no routing inhibited region within the global routing cell and on the global routing cell boundaries, a wire capacitance of each global routing cell boundary will be 5.
However, since a routing inhibited region exists in practice as illustrated in
FIG. 11
, a wire capacity of each global routing cell boundary will be 5 or less than 5 which is a value derived from the number of routing tacks. In the example shown in
FIG. 11
, the symbol “∘” on a global routing cell boundary denotes a passable track, and a wire capacity of the upper global routing cell boundary is 3, that of the lower global routing cell boundary is 4, that of the left-side global routing cell boundary is 5 and that of the right-side global routing cell boundary is 3. Here, according to the above literature, a wire capacity is obtained as the number of routing tracks allowing routing which is estimated based on a distribution of obstructions within the global routing cell (routing inhibited region). In the global routing processing, therefore, a routing route is selected such that a wire capacity will not exceed an estimated value at each global routin
Foley & Lardner
NEC Corporation
Speight Jibreel
LandOfFree
Automatic global routing device for efficiently determining... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic global routing device for efficiently determining..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic global routing device for efficiently determining... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2847244