Modifying timing graph to avoid given set of paths

Details Modifying timing graph to avoid given set of paths Modifying timing graph to avoid given set of paths

1997-11-05

2001-09-18

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06292924

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuits. In particular, the present invention relates to the art of placing and connecting cells on integrated circuit chips.
2. Description of Related Art
An integrated circuit chip (hereafter referred to as an “IC” or a “chip”) comprises cells and connections between the cells formed on a surface of a semiconductor substrate. The IC may include a large number of cells and require complex connections between the cells.
A cell is a group of one or more circuit elements such as transistors, capacitors, and other basic circuit elements grouped to perform a function. 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 example,
FIG. 1A
shows a grossly simplified IC
10
having four cells
12
,
14
,
16
, and
18
and ten pins
22
,
24
,
26
,
28
,
30
,
22
,
34
,
36
,
38
, and
40
. For simplicity, the cells will be denoted C
nn
and the pins will be denoted p
nn
where nn is the reference number of the cell or the pin used in the figure.
A net is a set of two or more pins which must be connected. Because a typical chip has thousands, tens of thousands, or hundreds of thousands of pins, which must be connected in various combinations, the chip also includes definitions of thousands, tens of thousands, or hundreds of thousands of nets, or sets of pins. The number of the nets for a chip is typically in the same order as the order of the number of cells on that chip. Commonly, a majority of the nets include only two pins to be connected; however, many nets comprise three or more pins. Some nets may include hundreds of pins to be connected. The IC
10
of
FIG. 1A
has two nets. The first net is a two-pin net comprising pins p
34
and p
40
. The second net is a three pin net comprising pins p
32
, p
36
, and p
38
. A net can be denoted as a set of pins net (p
1
, p
2
, . . . p
n
)
A netlist is a list of nets for a chip.
Typically, an IC has a plurality of input pins and a plurality of output pins. The inputs are digital electrical signals being provided to the IC to be operated on. The outputs are digital electrical signals resulting from the operations of the IC. In between the input pins receiving the input signals to the IC and the output pins providing the output signals, the digital signals are operated on by a plurality of cells connected to each other. The connections of the cells are defined by the nets discussed hereinabove. The IC
10
of
FIG. 1A
has three input pins—p
22
, p
24
, and p
26
—and two output pins—p
28
and P
30
. For the purposes of describing the present invention, the pins of the IC which are neither input pins nor output pins will be referred to as intermediate pins.
One of the major constraints in design and fabrication of IC's is the time the IC requires to perform the specified function. This is often referred to as the performance of the IC. To determine the performance of an IC, various time measurements must to be considered. This is because, in addition to the input and output lines, the IC may include internal registers, or flip-flops, which may store certain output values and provide a portion of input values to the logic circuits. The performance of an IC may be defined as the period of time between the instant the last of the input signals are available to the logic circuit (whether the signals are from the input lines or from internal registers) to the instant the latest of the output signals are available from the logic circuit (whether the signals are for the output lines or for internal registers). The instant the input signal are applied is often denoted as t
0
. In any event, the performance of the IC is the period of time required for the logic circuits of the IC to performs its designed function irrespective of whether the inputs to the logic circuits are from the input pins or from the flip-flops or the outputs from the logic circuits are to the output pins or to the flip-flops. The performance of the IC is also referred to as the delay of the IC, or the IC delay.
For example, if the inputs to the IC
10
of
FIG. 1A
is applied at time t
0
and the last of the output signals of the IC is available at t
0
+3 ns (nano-seconds), then the delay of the IC
10
is 3 ns. This is true even if the other outputs signals of the IC are available at t
0
+1 ns or at t
0
+2 ns.
The performance of the IC depends on many factors such as the physical characteristics of the material, the layout of the cells, etc. Some of these factors, such as the physical characteristics of the material of the IC, cannot be changed during the cell placement and routing process. On the other hand, the placement of the cells and the routing of the nets can be modified during the placement process to improve the performance of the IC.
In order to increase the performance of the IC by modifying the placement of the cells and re-routing the nets, the paths of the IC must be analyzed and the critical paths identified. A path is an alternating sequence of nodes and edges connecting them. A critical path is the path or the paths among all possible paths of an IC which causes the highest delay of the IC.
An edge is the direction of signals flow through the cells and the wires. There are two types of edges in an IC. A cell edge is the direction of signals flow through the cells of an IC, and is obtained by “connecting” an input pin of a cell with an output pin of the same cell. If a cell takes an input signal at pin pi and produces and output signal at pin p
o
then the cell edge for that signal flow is denoted e
c
(p
i
, p
o
). Then, p
i
is called a parent of p
o
and p
o
a child of p
i
. For example, the IC
10
of
FIG. 1A
has several cell edges. The cell edges are e
c
(p
22
, p
32
), e
c
(p
24
, p
34
), e
c
(p
26
, p
34
), e
c
(p
36
, p
38
), e
c
(p
38
, p
30
), and e
c
(P
40
, p
30
) A pin may have none (for an input pin), one, or many parent(s), and none (for an output pin), one, or many children. If there is a path from node p
1
, to node p
2
, then p
1
is an ancestor of p
2
and p
2
is a descendant of p
1
.
A net edge is the direction of signal flow from an output pin of a cell to an input pin of another cell, and is obtained by connecting the driver pin of a net with sink pin of the same net. A driver pin is the pin of a net which provides the signal to the sink pins of the same net and is typically an output pin of a cell. If a net has a driver pin P
d
which is connected to a sink pin p
s
, then the net edge for that signal flow is denoted e
n
(p
d
, p
s
). A sink pin is a pin of a net which receives the signal from a driver pin, and is often an input pin of a cell. For example, the IC
10
of
FIG. 1A
has several net edges. The net edges are e
n
(p
32
, p
36
), e
n
(p
32
, p
38
), and e
n
(p
34
, p
40
).
All edges of an IC are directed edges having a driver pin from which the signal originates and a sink pin to which the signal flows. For the purposes of the present invention, the distinction between the cell edges and net edges is not critical. Therefore, an edge will mean a cell edge or a net edge, and will be denoted
e
(p
p
, p
c
) to indicate an edge between a parent pin p
p
and a child pin p
c
.
A path may be denoted as a set of pins and edges, for example, path(p
1
, e(p
1
, p
2
), p
2
, e(p
2
, p
3
), p
3
, . . . ). An alterative expression of the path is to merely list the nodes, for example, path(p
1
, p
2
, . . . ). Regardless of how it is denoted, a path comprises pins and edges connecting the pins.
The relationships of ancestor and descendent may exist between an edge and a node or between two edges. For example, if p
1
, is an ancestor of p
2
, then p
1
is also an ancestor of the edge e(p
2
, p
3
). Similarly, if p
7
is a descendent of p
4
, then e(p
7
, p
8
) is a descendent of p
4
.
FIG. 1B
illustrates a di

Affiliated with

Also associated with

Rating

Modifying timing graph to avoid given set of paths does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Modifying timing graph to avoid given set of paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modifying timing graph to avoid given set of paths will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2452540