Exercises — Critical path identification

WHAT to do: critical path = the one with the largest summed delay, never the most gates. Sum each: $P=5$, $Q=4$, $R=6$ ns. Answer: Path R is critical, with 2 gates — it beats Path Q which has twice as many gates. Delay is about accumulated time, not node count.

Slack = required arrival − actual arrival. Negative slack means data arrives later than the deadline → the path FAILS (setup violation). Only slack $\ge 0$ passes.

$T_{\min }=t_{cq}+t_{logic}^{\max }+t_{su}=0.6+8+0.4=9\text{ ns}$ $f_{\max }=\frac{1}{9\text{ ns}}=\frac{1}{9\times 10^{-9}\text{ s}}\approx 111.1\text{ MHz}$ WHY: we add the fixed overheads ($t_{cq}$ before the logic, $t_{su}$ after it) to the worst logic delay, because all three must fit inside one period.

$\text{slack}=(T+t_{skew})-(t_{cq}+t_{logic}+t_{su})$ $=(12+0.5)-(0.8+9+0.7)=12.5-10.5=+2.0\text{ ns}$ Positive slack ⇒ PASSES with 2 ns to spare. The $+0.5$ ns of skew helped, because a later capture edge pushes the deadline out.

(a) Compare summed delays: $Y=7.2>X=6.5$ ns → Path Y is critical. (b) $T_{\min }=0.5+7.2+0.5=8.2$ ns → $f_{\max }=1/8.2\text{ ns}\approx 121.95$ MHz. (c) At $T=8.2$ ns, Path X slack $=8.2-(0.5+6.5+0.5)=8.2-7.5=+0.7$ ns. WHY it matters: the critical path (Y) has zero slack at $f_{\max }$; every other path has positive slack. That is literally what "critical" means — the tightest one.

WHAT rule: a gate's output cannot settle until its last input has settled. So ${\text{arrival}}_{\text{out}}=\max (3,5,4)+t_G=5+2=7\text{ ns}.$ Look at the red input in the figure — it is the last to arrive at $5$ ns, so it decides everything. This is exactly the max-of-inputs rule that makes a slowest path emerge inside Static Timing Analysis (STA).

Forward pass, taking max at every merge:

• $\text{AT}(A)=0$
• $\text{AT}(B)=\text{AT}(A)+2=2$
• $\text{AT}(C)=\text{AT}(A)+4=4$
• $\text{AT}(D)=\max (\text{AT}(B)+3,\text{AT}(C)+1)=\max (5,5)=5$
• $\text{AT}(E)=\max (\text{AT}(D)+3,\text{AT}(C)+4)=\max (8,8)=8$

Arrival at E = 8 ns. Two paths tie at 8: $A\to B\to D\to E$ ($2+3+3$) and $A\to C\to E$ ($4+4$). Both are co-critical — a real STA tool would report both. Trace back along the max-delay predecessor to reconstruct them (the yellow arrows in the figure).

(a) Required per path $=0.5+15+0.5=16$ ns $>9$ ns → FAILS. Slack $=9-16=-7$ ns. (b) Split into two halves of $15/2=7.5$ ns each. Per stage: $0.5+7.5+0.5=8.5$ ns $\le 9$ ns → each half PASSES (slack $+0.5$ ns). (c) With $n$ equal stages, each does $15/n$ ns of logic. We need $0.5+\frac{15}{n}+0.5\le 9\Rightarrow \frac{15}{n}\le 8\Rightarrow n\ge \frac{15}{8}=\mathrm{1.875.}$ So $n=2$ stages suffice. WHY: Pipelining converts one long path into several short ones; the fixed $t_{cq}+t_{su}$ overhead ($1$ ns) is paid once per stage, so you can't split forever for free.

First, the period: $T=1/f=1/(200\times 10^6)=5$ ns. From $t_{cq}+t_{logic}+t_{su}\le T+t_{skew}$: $t_{logic}^{\max }=T+t_{skew}-t_{cq}-t_{su}=5+0.2-0.4-0.3=4.5\text{ ns}.$ WHY: this is your logic budget — any path exceeding 4.5 ns of gate delay breaks the 200 MHz goal.

(a) By raw delay, Path N (8.5 ns) > Path M (8.0 ns). (b) Slack $=(T+t_{skew})-(t_{cq}+t_{logic}+t_{su})$:

• Path M: $(10-1.0)-(0.5+8.0+0.5)=9.0-9.0=0.0$ ns.
• Path N: $(10+0.5)-(0.5+8.5+0.5)=10.5-9.5=+1.0$ ns. (c) Worst slack = Path M ($0.0$ ns) — even though it has the smaller logic delay! (d) LESSON: the critical path is defined by minimum slack, not maximum delay. Negative/early skew stole 1 ns of budget from M, making the "shorter" path the real bottleneck. When skew differs per path, always rank by slack. (See Clock Skew and Jitter.)

Compare the new slacks: M $=+0.8$, N $=+1.0$, O $=+0.3$. The smallest is Path O ($+0.3$ ns) → Path O is now the critical path. WHY / lesson: fixing the old bottleneck promotes the next-slowest path to critical. Timing closure is iterative — you re-run Static Timing Analysis (STA) after every change until the worst slack is $\ge 0$ everywhere. This ties directly into the Synchronous Design Flow.

(a) $T=1/(250\times 10^6)=4$ ns. Current requirement $=0.5+6+0.5=7$ ns $>4$ ns → FAILS. Slack $=4-7=-3$ ns. (b) Logic budget $=T-t_{cq}-t_{su}=4-0.5-0.5=3$ ns, so you must cut $t_{logic}$ from 6 ns down to $\le 3$ ns — a reduction of $\ge 3$ ns. Two techniques:

1. Gate sizing / buffering — use faster (larger-drive) gates to cut per-gate delay (see Propagation Delay and Gate Sizing).
2. Pipelining — insert a register so each stage does $\le 3$ ns of logic (see Pipelining). Either way, re-run STA afterward to confirm no new path became critical.