MEMORY, MICROPROCESSOR, and ASIC phần 6 pot

Timing and Signal Integrity Analysis 8-3

Because of the importance of static techniques in verifying the timing behavior of microprocessors, we

will restrict the discussion below to the salient points of static TA.

8.2.1 DCC Partitioning

The first step in transistor-level static TA is to partition the

circuit into dc connected components (DCCs), also called

channel-connected components. A DCC is a set of nodes which

are connected to each other through the source and drain

terminals of transistors. The transistor-level representation

and the DCC partitioning of a simple circuit is shown in

Fig. 8.1. As seen in the diagram, a DCC is the same as the

gate for typical cells such as inverters, NAND and NOR

gates. For more complex structures such as latches, a single

cell corresponds to multiple DCCs. The inputs of a DCC

are the primary inputs of the circuit or the gate nodes of

the devices that are part of the DCC. The outputs of a

DCC are either primary outputs of the circuit or nodes that are connected to the gate nodes of

devices in other DCCs. Since the gate current is zero and currents flow between source and drain

terminals of MOS devices, a MOS circuit can be partitioned at the gates of transistors into components

which can then be analyzed independently. This makes the analysis computationally feasible since

instead of analyzing the entire circuit, we can analyze the DCCs one at a time. By partitioning a circuit

into DCCs, we are ignoring the current conducted by the MOS parasitic capacitances that couple the

source/drain and gate terminals. Since this current is typically small, the error is small. As mentioned

above, DCC partitioning is required for transistor-level static TA. For higher levels of abstraction, such

as gate-level static TA, the circuit has already been partitioned into gates, and their inputs are known. In

such cases, one starts by constructing the timing graph as described in the next section.

8.2.2 Timing Graph

The fundamental data structure in static TA is the timing graph. The timing graph is a graphical

representation of the circuit, where each vertex in the graph corresponds to an input or an output

node of the DCCs or gates of the circuit. Each edge or timing arc in the graph corresponds to a signal

propagation from the input to the output of the DCC or gate. Each timing arc has a polarity defined

by the type of transition at the input and output nodes. For example, there are two timing arcs from

the input to the output of an inverter: one corresponds to the input rising and the output falling, and

the other to the input falling and the output rising. Each timing arc in the graph is annotated with the

propagation delay of the signal from the input to the output. The gate-level representation of a simple

circuit is shown in Fig. 8.2(a) and the corresponding timing graph is shown in Fig. 8.2(b). The solid-line

timing arcs correspond to falling input transitions and rising output transitions, whereas the dotted-line

arcs represent rising input transitions and falling output transitions.

FIGURE 8.1 Transistor-level circuit parti￾tioned into DCCs

FIGURE 8.2 A simple digital circuit: (a) gate-level representation, and (b) timing graph.

8-4 Memory, Microprocessor, and ASIC

Note that the timing graph may have cycles which correspond to feedback loops in the circuit.

Combinational feedback loops are broken and there are several strategies to handle sequential loops

(or cycles of latches).5

In any event, the timing graph becomes acyclic and the vertices of the graph can

be arranged in topological order.

8.2.3 Arrival Times

Given the times at which the signals at the primary inputs or source nodes of the circuit are stable, the

minimum (earliest) and maximum (latest) arrival times of signals at all the nodes in the circuit can be

calculated with a single breadth-first pass through the circuit in topological order. The early arrival time

a(v) is the smallest time by which signals arrive at node v and is given by

(8.1)

Similarly, the late arrival time A(v) is the latest time by which signals arrive at node v and is given by

(8.2)

In the above equations, FI(v) is the set of all fan-in nodes of v, i.e., all nodes that have an edge to v and

duv is the delay of an edge from u to v. Equations 8.1 and 8.2 will compute the arrival times at a node

v from the arrival times of its fan-in nodes and the delays of the timing arcs from the fan-in nodes to

v. Since the timing graph is acyclic (or has been made acyclic), the vertices in the graph can be arranged

in topological order (i.e., the DCCs and gates in the circuit can be levelized). A breadth-first pass

through the timing graph using Eqs. 8.1 and 8.2 will yield the arrival times at all nodes in the circuit.

Considering the example of Fig. 8.2, let us assume that the arrival times at the primary inputs a and

b are 0. From Eq. 8.2, the maximum arrival time for a rising signal at node a1 is 1, and the maximum

arrival time for a falling signal is also 1. In other words, Aa1,r= Aa1,f=1, where the subscripts r and f

denote the polarity of the signal. Similarly, we can compute the maximum arrival times at node b1 as

Ab1,r=Ab1,f=1, and at node d as Ad,r=2 and Ad,f=3.

In addition to the arrival times, we also need to compute the signal transition times (or slopes) at the

output nodes of the gates or DCCs. These transition times are required so that we can compute the

delay across the fan-out gates. Note that there are many timing arcs that are incident at the output

node and each gives rise to a different transition time. The transition time of the node is picked to be

the transition time corresponding to the arc that causes the latest (earliest) arrival time at the node.

8.2.4 Required Times and Slacks

Constraints are placed on the arrival times of signals at the primary output nodes of a circuit based on

performance or speed requirements. In addition to primary output nodes, timing constraints are

automatically placed on the clocked elements inside the circuit (e.g., latches, gated clocks, domino

logic gates, etc.). These timing constraints check that the circuit functions correctly and at-speed.

Nodes in the circuit where timing checks are imposed are called sink nodes.

Timing checks at the sink nodes inject required times on the earliest and latest signal arrival times

at these nodes. Given the required times at these nodes, the required times at all other nodes in the

circuit can be calculated by processing the circuit in reverse topological order considering each node

only once. The late required time R(v) at a node v is the required time on the late arriving signal. In

other words, it is the time by which signals are required to arrive at that node and is given by

(8.3)

Timing and Signal Integrity Analysis 8-5

Similarly, the early required time r(v) is the required time on the early arriving signal. In other words, it

is the time after which signals are required to arrive at node v and is given by

(8.4)

In these equations, FO(v) is the set of fan-out nodes of v (i.e., the nodes to which there is a timing arc

from node v) and duv is the delay of the timing arc from node u to node v. Note that R(v) is the time

before which a signal must arrive at a node, whereas r(v) is the time after which the signal must arrive.

The difference between the late arrival time and the late required time at a node v is defined as the

late slack at that node and is given by

(8.5)

Similarly, the early slack at node v is defined by

(8.6)

Note that the late and early slacks have been defined in such a way that a negative value denotes a

constraint violation. The overall slack at a node is the smaller of the early and late slacks; that is,

(8.7)

Slacks can be calculated in the backward traversal along with the required times. If the slacks at all

nodes in the circuit are positive, then the circuit does not violate any timing constraint. The nodes with

the smallest slack value are called critical nodes. The most critical path is the sequence of critical nodes that

connect the source and sink nodes.

Continuing with the example of Fig. 8.2, let the maximum required time at the output node d be

1. Then, the late required time for a rising signal at node a1 is Ra1,r=-0.5 since the delay of the rising-to￾falling timing arc from a1 to d is 1.5. Similarly, the late required time for a falling signal at node a1 is

Ra1,f=Rd,r 1=0. The required times at the other nodes in the circuit can be calculated to be: Rb1,r = -1,

Rb1,f=0, Ra,r=-1, Ra,f=-1.5, Rb,r=-1, and Rb,f=-2. The slack at each node is the difference between the

required time and the arrival time and are as follows: Sd,r=-1.5, Sd,f=-2, Sal,r=-1.5, Sa1,f=-1, Sb1,r = -2,

Sb1,f=–1,Sa,r=-1, Sa,f=-1.5, Sb,r=-1, and Sb,f=-2. Thus, the critical path in this circuit is b falling—b1

rising—d falling, and the circuit slack is -2.

8.2.5 Clocked Circuits

As mentioned earlier, combinational circuits have timing checks imposed only at the circuit primary

outputs. However, for circuits containing clocked elements such as latches, flip-flops, gated clocks,

domino/precharge logic, etc., timing checks must also be enforced at various internal nodes in the

circuit to ensure that the circuit operates correctly and at-speed. In circuits containing clocked elements,

a separate recognition step is required to detect the clocked elements and to insert constraints. There

are two main techniques for detecting clocked elements: pattern recognition and clock propagation.

In pattern recognition-based approaches, commonly used sequential elements are recognized using

simple topological rules. For example. back-to-back inverters in the netlist are often an indication of a

latch. For more complex topologies, the detection is accomplished using templates supplied by the

user. Portions of a circuit are typically recognized in the graph of the original circuit by employing

subgraph isomorphism algorithms.9

Once a subcircuit has been recognized, timing constraints are

automatically inserted. Another application of pattern-based subcircuit recognition is to determine

logical relationships between signals. For example, in pass-gate multiplexors, the data select lines are

typically one-hot. This relationship cannot be obtained from the transistor-level circuit representation

without recognizing the subcircuit and imposing the logical relationships for that subcircuit. The

logical relationship can then be used by timing analysis tools. However, purely pattern recognition-

8-6 Memory, Microprocessor, and ASIC

based approaches can be restrictive and may necessitate a large number of templates from the user for

proper functioning.

In clock propagation-based approaches, the recognition is performed automatically by propagating

clock signals along the timing graph and determining how these clock signals interact with data signals

at various nodes in the circuit. The primary input clocks are identified by the user and are marked as

(simple) clock nodes. Starting from the primary clock inputs and traversing the timing arcs in the

timing graph, the type of the nodes is determined based on simple rules. These rules are illustrated in

Fig. 8.3, where we show the transistor-level subcircuits and the corresponding timing subgraphs for

some common sequential elements.

FIGURE 8.3 Sequential element detection: (a) simple clock, (b) gated clock, (c) merged clock, (d) latch node, and

(e) footed and footless domino gates. Broken arcs are shown as dotted lines. Each arc is marked with the type of

output transition(s) it can cause (e.g., R/F: rise and fall, R: rise only, and F: fall only).