Critical Paths

The idea of critical paths in a CMOS circuit can be derived, intuitively, from the idea of path between the the output and the input: a critical path is a conducting path between a node (the ``output'' node, i.e. the final node of the path) and the ground, or between this node and the power supply, such that a change in the state of an input gate of a MOSFET comprised in the path causes directly a change in that node. Naturally each MOSFET included in the path must be on, or switch to, conduction, in order to create a conducting path.
This concept must be extended, however, since a change of the so called output node can cause itself a change of another critical path (i.e. the output node is itself connected to a gate of another critical path), so that a change in a gate node in the very beginning of the circuit may propagate through a lot of conducting paths.

Definition 6.1 (Critical path)   A critical path is a set of conducting paths such that:

i)

each conducting path is between a generic node and a ground node, or between a generic node and a power supply node, and is composed by MOSFETs; and

ii)

each final node of a conducting path is either connected to a gate of a MOSFET comprising another critical path, or is an output of the circuit; and

iii)

a change in the state of any MOSFET gates in the first conducting path propagates till the last conducting path, causing a change in the critical path output node.

Definition 6.2 (Critical path delay)   The delay of a critical path is the delay between the output node of the critical path and the gate node causing the state change of the output node.

From the definition 5.1 it is clear that even a simple circuit has more than one critical path in it ¹².

In order to develop a rigorous definition of critical paths, let's introduce the following sets, characterizing a typical CMOS circuit:

$$\mathcal{G} =\left\{\text{set of all the {\sc mosfet} gate nodes in the circuit}\right\} =\left\{g_1,\, g_2,\dots,\, g_j,\, \dots\, \right\}$$

$$\mathcal{N} =\left\{\text{set of all the nodes in the circuit}\right\} =\left\{n_1,\, n_2,\dots,\, n_j,\, \dots\, \right\}$$

$$\mathcal{O} =\left\{\text{set of all the output nodes of the circuit}\right\} =\left\{o_1,\, o_2,\dots,\, o_j,\, \dots\, \right\}$$

$$\mathcal{I} =\left\{\text{set of all the input nodes of the circuit}\right\} =\left\{i_1,\, i_2,\dots,\, i_j,\, \dots\, \right\}$$

$$\mathcal{M} =\left\{\text{set of all {\sc mosfet}s in the circuit}\right\} =\left\{m_1,\, m_2,\dots,\, m_j,\, \dots\, \right\}$$

$$\mathcal{V} =\left\{\text{gnd=ground node},\text{vdd=power supply node}\right\};$$

let's define also the set $\mathcal{N}_{m_j}$ as the set of all the nodes pertaining to the MOSFET $m_j$, and the gate of the $j$-th MOSFET with $g_{m_j}$.
All these sets are in such relations: $\mathcal{I}\subseteq\mathcal{G}\subset\mathcal{N}\,$, $\mathcal{V}\subset\mathcal{N}\,$, $\mathcal{O}\subseteq\mathcal{N}\setminus{G}$.

The generic $n$-th critical path of a circuit, denoted by $\mathsf{C}_n$, equation (5.1a) (page ), is the collection of conducting paths, denoted by $\gamma_{ni}$, such that each $\gamma_{ni}$, equation (5.1b), is defined as the union of two ordered node sets, the set $\mathcal{G}_{\gamma_{ni}}$, equation (5.1c), of all gates of all the $k$ MOSFETs pertaining to the conducting path, and the set $\mathcal{D}_{\gamma_{ni}}$, equation (5.1d), of all drain and source nodes (in number of¹³ $k+1$) of the same $k$ MOSFETs,  (5.1e)
The nodes in $\mathcal{D}_{\gamma_{ni}}$ set have a peculiar property: the first and last one may be or may be not¹⁴ in common among two or more MOSFETs, while the other ones must be in common among two or more MOSFETs.
In other words, the set $\mathcal{D}_{\gamma_{ni}}$ is an ordered collection of nodes such that among these nodes there are $k$ MOSFETs, constituting a continuous (and conducting) path from the output node to a power supply (or ground) node.

Finally, collecting all the definitions, respectively, of critical path, conducting path, conducting path gate nodes set and conducting path drain nodes set:

Figure 5.3: Example of critical paths

The figure 5.3 shows an example of critical paths in a dynamic circuit (actually the carry part of a full-adder in a TSPC logic). In this figure are represented the six critical paths, each one with the list of MOSFET numbers. For example, the first critical path ( $\mathbf{C}_1$) is composed by the conducting path $\gamma_{11}$, made up of n-MOSFETs $1,2,4,5$ and the p-MOSFET $11$: that means that the set $\mathcal{G}_{11}$ is composed by the gates node of transistors 1, 2, 4, 5, and 11, while $\mathcal{D}_{11}$ is made up of drain and source nodes of the same transistors; if one gate of n-MOSFETs $1,2,4,5$ switch from the low state to the high state (and the others are all at the high state), then the gate of p-MOSFET $11$ is discharged, and this p-MOSFET conducts, charging the output node. Another critical path for example is the one composed only by the p-MOSFET $6$: if its gate switch from high to low, then the gate of n-MOSFET $9$ switch form low to high, but this can not produce the discharging of the output node, since the gate of n-MOSFET $6$ is driven by the same signal of the original p-MOSFET.

Note 1   The definition of critical path can be viewed as a tree rooted at the transistor that is driving the change in the critical path. One leaf of the tree is the transistor which drain (or source) is the critical path output node. So it is possible to traverse the tree between the root (the input) and a leaf (the output): if one is able to model all the lateral subtree encountered during the traversing of the tree as static load, then the tree becomes a transistor chain (figure 5.4). This is the base of the use of several delay models that are able to evaluate a chain delay.

Figure 5.4: Critical path tree that becomes a chain.

After the definition of critical paths, the problem of associating a delay (one and only one) to a circuit is still unresolved, since there is surely more than one critical path in a circuit: the solution is to find the max of all the critical path delays, and regard this delay as the delay of the whole circuit. In this manner, we are sure that a change in the state of a node caused directly by an input, can never occurs after the max delay fixed. Also this definition is consistent with the optimization purposes, since the optimization objective is always (usually!) the minimization of the delay. So the strategy to be applied is a min-max scheme of optimization (minimization of the maximum).

Definition 6.3 (Circuit delay)   ¹⁵ The delay of a circuit $t_d$ is:

$$t_d = \max_{n}\left\{ d(\mathsf{C}_n) \right\}$$

where $d(\mathsf{C}_n)$ is the delay of the $n$-th critical path comprising in the circuit.

So, finally, in order to known the delay of a circuit, one must search all the critical paths in the circuit, calculate (or measure) the delay of each critical path, and calculate the max of these delays.

The delay of each critical path can be calculated by means of some model (maybe after the transformation of figure 5.4), or measured by means of simulations.

This delay, obtained in some way, must be analyzed in order to know its coherence with the mathematical results of chapter 4 (page ), and the validity of these results.