Combinational Timing & Multi-Input Cell Arcs

STA fundamentals — cell delay, interconnect, setup/hold, MCMM, OCV, noise, IR-drop and sign-off

Chapter 15 — Combinational Timing & Multi-Input Cell Arcs

(Deep Dive)

Many engineers know one sentence. A path delay is the sum of cell delays and net delays. That sentence is true. But it hides the interesting part. The real action lives inside a single gate. How is a gate with two, three, or four inputs measured? How does the tool decide which input caused an output edge? How do many input arrival times become one number at a node? This chapter opens that box. By the end, you can reason about per-arc delay, unateness, and the optimism and pessimism in timing. You will also see how shared fanout quietly spoils results.

The cell as a collection of timing arcs, not a delay

A standard cell is not measured as "the cell delay." It is measured as a set of timing arcs. An arc is one (input pin, output pin) pair plus an output direction (does the output rise or fall). Think of an arc as one specific journey through the gate. A two-input NAND gate Y = !(A & B) has four delay arcs.

Each arc has its own delay table. Each arc also has its own output-slew table. (Slew means how fast an edge changes, its rise or fall time.) Each table is read using the arc's input slew and the output load. (Load is the capacitance the output must drive.) The library does not assume the A path and the B path are the same. Physically they often differ. The transistors for each input sit at different spots in the gate.

A table is usually a 2-D nonlinear delay model. (NLDM, a lookup table of delay versus slew and load.) Rows are input slew. Columns are output load. A small slice of the A → Y rising arc might look like this.

The tool reads between table points for the real slew and load. (This is bilinear interpolation, a smooth blend of nearby cells.) The B → Y rising arc has a different table. So even with the same slew and load, the A path and the B path can charge different delays.

Worst-arc selection per transition

The tool needs the arrival time of a rising edge at Y . (Arrival time means when the edge reaches that pin.) It must ask one thing. Which input caused Y to rise, and through which arc? For setup (max) analysis, the tool is pessimistic. It assumes the latest, slowest cause. The rule for output transition t at pin Y is below.

arrival(Y, t) = max over all input arcs i→Y that can produce t of
[ arrival(i, src_transition) + delay(i→Y, t) ]

This is worst-arc selection. Each arc gives one candidate arrival time. For setup, the largest wins. For hold (min) analysis, the same rule runs with min . It picks the earliest, fastest arc.

WORKED EXAMPLE 1 — ARC SELECTION AT A NAND2

Suppose the two NAND inputs see the following.

• Input A: rising edge arrives at 1.30 ns, input slew 0.10 ns
• Input B: rising edge arrives at 1.10 ns, input slew 0.30 ns
• Output load on Y: 20 fF For a NAND, both A↑ and B↑ pull Y low. So Y falls. Use these illustrative falling-arc delays.
• A → Y fall delay at (slew 0.10, load 20) = 0.075 ns
• B → Y fall delay at (slew 0.30, load 20) = 0.122 ns Candidate arrivals at Y for the falling edge.
• via A: 1.30 + 0.075 = 1.375 ns
• via B: 1.10 + 0.122 = 1.222 ns For setup, the tool charges max(1.375, 1.222) = 1.375 ns . The winning arc is A → Y fall. Notice the trick. B arrives earlier (1.10 vs 1.30) yet still loses. A's smaller slew does not change that here. The winner is decided by the sum, never by arrival or delay alone. The output slew sent downstream comes from the winning arc's slew table. So the choice also picks a slew, not just a number. This is why an interviewer asks "if input B arrives earlier, will the path go through B?" They want to know if you grasp that arc selection uses the per-arc sum. It is checked for each output direction on its own.

Unateness, in depth

Unateness describes how an output edge relates to an input edge along an arc. Think of it as the direction the gate keeps or flips.

• Positive-unate: an input rise gives an output rise, and an input fall gives an output fall. Examples are a buffer, an AND output, an OR output. The arc keeps direction.

• Negative-unate: an input rise gives an output fall, and the reverse. Examples are an inverter, and every input of a NAND or NOR. The arc flips direction.
• Non-unate: the output direction cannot be found from the input edge alone. It depends on the other inputs. Examples are XOR, XNOR, and a multiplexer select pin. (A multiplexer picks one of several data inputs.) Cell / arc Unateness Consequence for arcs Inverter A→Y negative-unate input rise → output fall AND A→Y positive-unate input rise → output rise NOR A→Y negative-unate input rise → output fall XOR2 A→Y non-unate both rise and fall arcs sensitive in both directions MUX select→Y non-unate select edge can drive Y either way For a unate arc, only two of the four direction pairs carry delay. For negative-unate, those are input- rise/output-fall and input-fall/output-rise. For a non-unate arc, the library must give delay for both output directions for each input edge. Either output direction is reachable, based on the side input. So an XOR's A → Y arc roughly doubles the delay cases. That is why non-unate cells cost a bit more to time. They also surprise you more often in critical-path picks.

A practical note. When you constrain a signal with set_case_analysis , you may turn a non-unate cell into a unate one. Tie a MUX select to a constant. Then the select arc disappears. One data arc becomes a simple pass-through. This speeds analysis and removes false sensitivities.

# standard (SDC)
set_case_analysis 0 u_mux/SEL
# With SEL=0, only the D0 -> Y data arc remains active;
# the SEL -> Y non-unate arc is pruned from analysis.

Static (topological) timing vs sensitization

Here is the core idea of the chapter. STA is topological. (Topological means it follows the wiring structure.) It times every structural arc on its own. It does not check whether the input pattern needed to fire that arc can ever happen. It does not run logic proof to show a path is real. (This proof is called sensitization.) This is a deliberate trade. Proving every path is exponential work. (This is the false-path problem, NP-hard in general.) So STA accepts that some timed paths can never happen. This trade cuts both ways.

• Pessimism: STA may flag a violating path that can never switch. The side-input conditions are logically impossible. This is a false path. You waive it with set_false_path or a multicycle rule.
• Optimism: more dangerous, by skipping sensitization STA may pick a side-input value that does not match reality. In rare corners this under-counts delay. So strong flows manage exceptions with care. They do not trust raw topological results blindly. # standard (SDC) # Tell the analyzer a topologically-timed path is not functionally real: set_false_path -from u_ctrl/state_reg[3]/Q -through u_dp/mux_byp/Y The interview summary is short. STA times arcs, not behaviors. If every timed arc meets its constraint, the circuit is safe. The cost is analyzing paths that may be logically dead.

Levelization and the order of delay calculation

To merge arrivals right, the tool cannot process cells in any order. It first does levelization. (This is a topological sort, ordering cells so drivers come before loads.) Every cell is processed only after all its drivers have final arrival times. Sequential elements split the graph into combinational stages. (Sequential elements are registers, which store state on a clock edge.) Register outputs are sources (launch points). Register data inputs are sinks (capture points). The logic between them is a directed acyclic graph. (A DAG, a graph with no loops.) The forward (arrival) pass then runs level by level.

1. 1. Seed primary inputs and register-Q pins with arrival times. These come from clock plus clk-to-Q, or

from input delay constraints.

1. 2. For each cell in order, compute output arrival per direction by worst-arc selection.
2. 3. At each node, merge. Use max of incoming arrivals for setup, min for hold.
3. 4. Send the winning arc's output slew to the next stage's input.

A separate backward pass computes required times from the endpoints. Slack at a node is required − arrival (setup) or arrival − required (hold). (Slack is the timing margin, positive is good.)

Arrival merging at a node

A node fed by many arcs holds a single arrival time per direction after merging. This happens at the output of any multi-input gate. It also happens at a net where reconvergent paths meet. For setup, keep the latest contributor. For hold, keep the earliest.

hold

WORKED EXAMPLE 2 — ARRIVAL MERGE AT A RECONVERGENT NODE

Consider a datapath. Signal S fans out to two branches. They meet again at an AND gate G .

+--> [buf chain P1] --> a -->|
S ----+                            AND (G) --> Z
+--> [buf chain P2] --> b -->|

Let the launch edge at S be 0 ns. Branch delays follow.

• Path P1 to pin a : 0.90 ns, arriving slew 0.12 ns
• Path P2 to pin b : 1.15 ns, arriving slew 0.20 ns AND gate G rising-output arcs at load 15 fF.
• a → Z rise delay (slew 0.12) = 0.064 ns
• b → Z rise delay (slew 0.20) = 0.088 ns Candidate arrivals at Z (rise), setup.
• via a: 0.90 + 0.064 = 0.964 ns
• via b: 1.15 + 0.088 = 1.238 ns ← wins The merged setup arrival at Z is 1.238 ns through the b arc. So far this is normal. The trap is in the next section.

Reconvergent fanout, correlated paths, and common-path effects

In Example 2, both branches start from the same source S . Their arrival times (0.90 and 1.15) share a common upstream segment up to the fanout point. Say S itself is late by 0.05 ns from upstream delay. Then both branches shift by 0.05 ns together. They are correlated, not independent. Picture two runners who share the same first mile.

Why this matters. STA may apply on-chip variation derates. (OCV models how delay varies across the chip.) Or it may compute statistical bounds. If it treats the two branches as independent, it derates the common segment twice. Once it is optimistic on one branch, once pessimistic on the other. This creates fake pessimism. The fix is common-path pessimism removal. (CPPR finds the shared part of the launch and capture paths.) It then credits back the double-counted variation on the shared part. This is classic on the clock network, but the same idea governs any reconvergent datapath.

The rule is simple. Correlated delays must not be derated as if independent. Reconvergent fanout is the reason correlation exists in pure datapath. It is the most common source of avoidable pessimism in tight timing closure.

Slew merging at multi-input nodes

When several arcs drive a node, each candidate brings an arrival time and an output slew. There are two approaches.

• Per-arc slew (accurate): the slew sent downstream comes from the arc that won the arrival merge. In Example 2, the winner was the b arc. So the downstream slew is the b → Z arc's slew.
• Worst-slew merge (pessimistic): the tool sends the worst (largest) slew across all arcs, no matter which arc won. Downstream delay grows with input slew, so this never under-counts. The cost is pessimism. Strategy Arrival uses Slew propagated Effect Per-arc (coupled) winning arc winning arc's slew most accurate, can be slightly optimistic Worst-slew (decoupled) winning arc max slew over arcs safe, can over-estimate downstream delay

The decoupling matters. The arc with the worst slew is not always the arc with the worst arrival. Suppose arc a arrives earlier but with a much larger slew than the winning arc b . Per-arc slew sends b 's tighter slew. Worst-slew merge sends a 's degraded slew. That inflates every downstream cell delay. Sign-off flows usually prefer the accurate per-arc behavior, with margin added elsewhere. But knowing both modes exist helps. It explains why a tool may report a downstream delay that differs from your hand calculation. That detail marks a senior STA engineer in an interview.

Pin-to-pin arcs on complex cells and internal pins

A complex cell may be an AOI (and-or-invert), a full adder, or a scan flop. It is measured with arcs between its boundary pins. But inside it may have internal pins. (These are nodes not on the cell's logical interface, needed only to model timing well.) The library may show multi-stage internal arcs. Input to internal pin, then internal pin to output. When the tool flattens the cell, it joins these internal arcs into effective boundary-to-boundary arcs. It sums internal delays and passes internal slews stage by stage. This is the same way it works across the netlist. Two practical points follow.

1. 1. The set of boundary arcs on a complex cell is not every input crossed with every output. The library

lists only arcs that physically exist. An AOI22 Y = !((A&B)|(C&D)) has arcs from A, B, C, and D to Y. The delay through A depends on the A→internal-node→Y chain, which the tool handles for you.

1. 2. State-dependent arcs exist. Some libraries give conditional (when-qualified) arcs. Here the delay

of A → Y changes with the static value of B . The tool picks the arc whose condition matches the side input. Without set_case_analysis , it takes the worst matching arc to be safe.

# illustrative — generic, not tool-specific:
# report a single cell's characterized arcs and their unateness
report_timing_arcs -cell u_alu/aoi22_7
#   A -> Y  negative_unate  (when "C")
#   A -> Y  negative_unate  (when "!C")
#   ...

Putting it together — a per-stage mental model

For any combinational stage, run this loop in your head.

1. 1. Enumerate arcs into the cell output. One per input pin per output direction.
2. 2. Evaluate each arc. Read delay and output slew from its NLDM table. Use that input's slew and the

real output load.

1. 3. Sum input arrival plus arc delay, per arc.
2. 4. Select the worst (setup) or best (hold) sum. That is the merged arrival and the winning arc.
3. 5. Propagate the slew. Use per-arc or worst-slew, per your flow.
4. 6. Account for correlation if the fan-in shares a common source (CPPR).

If you can narrate that loop for a NAND, a MUX, and a reconvergent AND, you understand combinational STA at the level interviews probe.

Interview Q&A

output direction) is a distinct journey through a different transistor stack. The A-input and B-input transistors sit at different spots in the network. So the same load and slew can give different delays. The library measures each arc on its own, with its own delay and slew tables.

A? No. Arc selection compares the sum of input arrival plus that arc's delay, per output direction. A later input through a faster arc can lose to an earlier input through a slower arc. You must add the arc delay before you compare. Arrival alone never decides the winner.

output direction cannot be found from the input direction alone. It depends on the other inputs' state. XOR, XNOR, and multiplexer select pins are the classic cases. They force the library to measure both output directions for each input edge. This doubles the delay cases and creates sensitivities in both directions.

path can fire (Boolean justification) is NP-hard. So STA times the netlist topologically. This is conservative and fast, but it can flag false paths. Engineers waive these with set_false_path or multicycle rules. The guarantee is this. If all timed arcs meet constraints, the design is safe.

per direction. Use max of contributors for setup (latest case) and min for hold (earliest case). The slew sent downstream is either the winning arc's slew (accurate) or the worst slew across arcs (pessimistic decoupled mode). This depends on flow setup.

share a common upstream segment, their delays are correlated. Derating them as independent (under OCV or statistical analysis) double-counts variation on the shared segment. That makes fake pessimism. Common-path pessimism removal (CPPR) finds the shared part and credits back the overcounted derate. This recovers realistic slack. It is most familiar on the clock tree, but it is just as valid for reconvergent datapath.

Key Takeaways

• A cell is a set of timing arcs. Each (input, output, direction) has its own delay and slew tables. There is no single "cell delay."
• Worst-arc selection compares input-arrival plus arc-delay sums per output direction. max wins for setup, min for hold. Neither arrival nor delay alone decides it.
• Unateness sorts arcs as positive-, negative-, or non-unate. Non-unate cells (XOR, MUX select) carry sensitivities in both output directions. They double the delay cases to consider.

• STA is topological. It times all structural arcs without proving sensitization. This trades exactness for speed. False paths are managed with exceptions, not Boolean proof.
• Levelization orders the DAG so arrivals merge right. At each node, arrivals merge by max (setup) or min (hold). Slew propagates per-arc or worst-case.
• Reconvergent fanout creates correlated paths. CPPR removes the double-counted variation on shared segments to avoid fake pessimism.
• Complex cells expose only physically real boundary arcs. They may use internal pins the tool flattens. They may carry state-dependent (when-qualified) arcs, resolved by side-input values or set_case_analysis .