Clock tree synthesis

Until CTS, the clock exists only as a line in the timing constraints (the SDC file): a period and some estimated delays. CTS turns it into the largest and busiest net on the die. The tool works through each clock network in two phases. First it builds: it groups the sinks, buffers each group, and connects the groups to the root, aiming at targets for skew, latency and maximum transition set per skew group (a set of sinks that must be balanced against each other). Then it optimizes with the real, propagated clock delays: it deliberately shifts some clock arrivals to rescue slow paths (useful skew, or concurrent clock and data optimization, CCD), inserts delay cells to fix hold failures, and resizes cells to fix slow edges and save power.

One consequence is easy to miss. Timing signoff assumes that any two clock paths may differ slightly because of manufacturing variation (OCV), but it gives credit back for the stretch of tree that two flip-flops share, since a shared wire can’t be both fast and slow at once (CPPR). So the shape of the tree, specifically where each critical pair of flip-flops splits apart, decides how much margin signoff takes away.

Power is the other half of the objective. Every clock node switches on every cycle, while a data node switches only when its value changes. Clock networks have taken well over a quarter of total power in some designs, and 40–44% across several generations of the DEC Alpha processor.¹ Tools: Cadence Innovus, Synopsys IC Compiler II and Fusion Compiler, and the open-source OpenROAD TritonCTS, which first clusters sinks with a capacity-limited k-means method and then connects the clusters with a generalized H-tree.⁷

Beyond the basic files, three kinds of input shape the result. Scenarios. A chip is checked in several modes (normal operation, test) at several corners (slow, hot, low-voltage silicon; fast, cold silicon; and so on), a setup called multi-mode multi-corner. Which corner the tree is balanced in matters, because a tree balanced in one can be skewed in another. Balancing rules. Skew-group definitions say which sinks must align, and exclude or ignore pins say which needn’t. Macro latencies. A memory block or other macro may contain its own internal clock tree. Liberty can describe that internal delay with min/max_clock_tree_path timing groups, and OpenSTA includes it in latency and skew reports when asked to.⁴

TritonCTS uses that information to balance the macro tree against the register tree by inserting delay buffers, and adds dummy loads (cells that exist only to add capacitance) to even out the leaves. Its inserted instances carry the name prefixes clkbuf_regs, delaybuf and clkload, which makes them easy to find in the netlist.⁵ Clock nets often leave CTS with routing guides or pre-routed wires and special wiring rules attached, and are routed before ordinary signal nets so they get the best tracks.

What the targets really mean

Global skew is only a proxy. Whether the chip works depends on local skew between flip-flops joined by a timing path, which is why useful-skew methods work only on those pairwise constraints.² Tools still keep skew tight within each skew group, because a balanced tree is predictable and leaves room for later optimization to add deliberate offsets. What matters at signoff is slack after variation margins, and that depends on three properties of the tree: its latency, how much of each critical pair’s two clock paths is unshared, and its edge rates.

Variation, derates and CPPR

Static timing analysis allows for on-chip variation by scaling delays: for a setup check it multiplies the launch-side delays by a “late” factor (say 1.05) and the capture clock’s delays by an “early” factor (say 0.95), and does the reverse for hold. Clock paths are derated too (set_timing_derate -clock -early / -late).⁴ One flat factor everywhere turned out to be excessively pessimistic, because random variations partly cancel along a path of many cells. Advanced OCV (AOCV) therefore looks the factor up by path depth and distance; parametric OCV (POCV) goes further and gives each cell its own variation (a standard deviation, sigma) as a function of its delay and load, stored in the library in the Liberty Variation Format (LVF).¹³

Now the catch. In a setup check the launch clock is treated as late and the capture clock as early. But if the two flip-flops’ clock paths share their first few buffers, those shared buffers would have to be late and early at the same instant, which is impossible. CPPR credits back the late-minus-early difference on the shared segment.¹² A worked illustration: if two flip-flops split at the last buffer, nearly their whole clock path is shared, and they lose almost nothing to clock derates. If they split at the root, every buffer of both paths is derated against them. A 400 ps unshared path at ±5% costs about 20 ps on each side, around 40 ps in all. Shallow, low-latency trees, and clustering tightly connected flip-flops under one branch, both buy real slack.

Uncertainty before and after CTS

Clock uncertainty is a margin for jitter, the cycle-to-cycle wobble of the clock edge.⁴ Before CTS it usually also covers the skew the tree will add. The two are different things: jitter varies from one cycle to the next, while skew is a difference between locations.³ The ideal-mode set_clock_latency and set_clock_transition describe the tree only when the design is analyzed with ideal clocks.⁴ A typical flow deletes them after CTS and cuts setup uncertainty to jitter plus margin. Leaving the pre-CTS numbers in place counts skew twice, once as computed and once as margin, and sends the optimizer chasing violations that aren’t real.

Topology trade-offs in practice

An H-tree buys balance with capacitance: its total wirelength, and so its power, exceeds that of a buffered tree shaped around the actual sinks, and symmetric structures add latency.¹ A mesh puts branch resistances in parallel, and everything above the mesh is shared by all loads, so only the short stubs below it are exposed to uncorrelated variation.¹¹⁰ Multisource CTS drives a mesh that Toyama describes as one to two orders of magnitude sparser than a full clock mesh, fed by H-trees, with ordinary subtrees hanging off tap points.¹⁰ The Alpha 21264 shows the hybrid style at processor scale: a trunk and X- and H-trees fed 16 drivers of a gridded global clock, every grid wire was shielded by power or ground, locally gated clocks sat below, and 65 ps of skew was measured on silicon.¹

Clock gating inside the tree

An ICG’s clock pin sits upstream of the flip-flops it gates, so its clock arrives earlier than theirs. Its enable signal, though, is launched by ordinary flip-flops at full latency and must arrive before that earlier ICG clock, so the enable path gets less time than a normal path. Moving ICGs toward the root gates more of the tree and saves more power, but tightens enable timing; cloning an ICG so each copy sits near its flip-flops does the opposite. TritonCTS’s -balance_levels option tries to keep a similar number of levels across non-register cells such as clock gates and inverters.⁵

Generated clocks, macros and skew groups

A divided clock inherits the main clock’s latency up to the divider flip-flop, plus the divider’s clock-to-Q delay, plus its own tree. So when a divide-by-2 domain exchanges data with its parent clock, the two trees must be balanced at the flip-flops where they meet. Skew groups say exactly which sinks must align: include the divider’s fanout and the main-clock flip-flops it talks to, and exclude scan-only or asynchronous sinks. Macros bring their own internal latency; TritonCTS inserts delay buffers to balance macro and register trees, with a derate option to insert only part of the delay needed.⁵

Hold repair and the useful-skew budget

Post-CTS hold repair is where a bad tree shows. By default OpenROAD caps hold buffers at 20% of the design’s instance count and refuses buffers that would create setup violations unless told otherwise.⁶ Every picosecond of useful skew given to a setup path is a picosecond taken from hold on that pair and from setup on the next stage, so CCD methods look for clock-arrival changes that improve the worst negative slack (WNS) and total negative slack (TNS) together.¹⁴

Power and electromigration

Clock nets are long, heavily loaded and switch every cycle.¹ Switching also wears out wires. Electromigration (EM) is metal atoms being pushed along a wire by current until it thins and fails; one form of it is driven by the heating from alternating (RMS) current, and its expected time to failure falls as the switching rate rises.¹⁵ Clock nets have the highest switching rate on the die, so clock drivers and trunk wires need EM checks at their true rate. The usual fixes are wider wires, extra vias (vertical connections between layers) on trunk connections, and splitting large loads across several drivers.

Use the sim to reason about margins the sliders don’t show directly. Fold uncertainty and variation derates into the sliders by hand, and watch how fast the window that useful skew opens closes again.

1. Add uncertainty. Take period 1000 ps, launch 300, capture 360, data 950: setup slack +30 ps. Model 50 ps of setup uncertainty by raising setup from 80 to 130 ps: slack −20 ps. The skew that fixed the ideal-mode path is not enough with post-CTS margins.
2. Add OCV. Derate the data path late by 5% (950 → 998 ps) and the part of the capture clock path not shared with the launch clock early by 5% (if 200 of its 360 ps is unshared, capture becomes 350 ps). Setup slack falls by about 58 ps, before even counting the launch clock’s own late derate. The CPPR credit applies only to the shared segment.
3. Borrowing from the next stage. Suppose the downstream path from the capture flop has data 900 ps and launches at 300 ps into a flop clocked at 300 ps: setup slack +20 ps. After you moved this flop’s clock to 360 ps, that stage launches at 360 ps and its slack is −40 ps. Around any loop of stages the skews cancel, which is the core of Fishburn’s formulation (see Under the hood).

Two artifacts tell you whether the tree is good. The first is the CTS summary plus a skew report: how many sinks and buffers, how deep the tree is, and the worst skew between two connected flip-flops. The second is the worst timing path, printed with the clock network expanded so you can see the clock delays on both sides. Both are illustrative, in OpenROAD/OpenSTA format, with times in ns.

[INFO CTS-0098] Clock net "core_clk"
[INFO CTS-0099]  Sinks 18432
[INFO CTS-0100]  Leaf buffers 912
[INFO CTS-0101]  Average sink wire length 41.27 um
[INFO CTS-0102]  Path depth 6 - 8
[INFO CTS-0207]  Dummy loads inserted 37
Total number of Clock Roots: 1.
Total number of Buffers Inserted: 1206.
Total number of Clock Subnets: 1206.
Total number of Sinks: 18432.

> report_clock_skew -setup -digits 3
Clock core_clk
  0.461 source latency u_lsu/addr_reg[3]/CK ^
 -0.389 target latency u_lsu/tag_reg[3]/CK ^
  0.050 clock uncertainty
 -0.018 CRPR
--------------
  0.104 setup skew

A timing path report reads top to bottom in two halves. The first half builds the arrival time: the clock edge at 0, the launch clock’s travel through the tree, then each cell on the data path with its delay and the running total. The second half builds the required time: the next clock edge one period later, the capture clock’s travel through the tree, the CPPR credit, and then the margins taken away (uncertainty and the flip-flop’s setup time). Slack is required minus arrival. The arrows ^ and v mark rising and falling edges.

Startpoint: u_alu/acc_reg[12] (rising edge-triggered flip-flop clocked by core_clk)
Endpoint: u_alu/res_reg[31] (rising edge-triggered flip-flop clocked by core_clk)
Path Group: core_clk
Path Type: max

  Delay    Time   Description
---------------------------------------------------------
  0.000   0.000   clock core_clk (rise edge)
  0.458   0.458   clock network delay (propagated)
  0.000   0.458 ^ u_alu/acc_reg[12]/CK (DFF_X1)
  0.121   0.579 ^ u_alu/acc_reg[12]/Q (DFF_X1)
  0.143   0.722 v u_alu/U812/ZN (NAND2_X2)
  0.208   0.930 ^ u_alu/U1033/ZN (AOI22_X1)
  0.236   1.166 v u_alu/U1207/ZN (OAI21_X2)
  0.198   1.364 ^ u_alu/U1301/ZN (XNOR2_X1)
  0.028   1.392 ^ u_alu/res_reg[31]/D (DFF_X1)
          1.392   data arrival time

  1.000   1.000   clock core_clk (rise edge)
  0.443   1.443   clock network delay (propagated)
  0.011   1.454   clock reconvergence pessimism
  0.000   1.454 ^ u_alu/res_reg[31]/CK (DFF_X1)
 -0.050   1.404   clock uncertainty
 -0.042   1.362   library setup time
          1.362   data required time
---------------------------------------------------------
          1.362   data required time
         -1.392   data arrival time
---------------------------------------------------------
         -0.030   slack (VIOLATED)

• Balanced in the wrong corner. A tree balanced at one corner can be skewed at another, because buffer delay and wire delay change by different amounts with voltage and temperature: a tree whose branches mix buffer-heavy and wire-heavy paths drifts apart. Teams choose the balancing corner deliberately and check skew in every signoff scenario.
• Long unshared clock paths. Critical pairs that split near the root pay the clock derate on almost the whole tree and get little CPPR credit back. Caught by sorting critical paths by their unshared clock latency; fixed by clustering the pair under one branch or with skew-group constraints.
• Clock-gate enable timing. ICGs placed near the root save the most power, but their enable paths are checked against an early clock and fail. Look for clock-gating check violations, then clone the ICG or move copies toward their loads.
• Duty-cycle drift. Long chains of buffers with mismatched rise and fall delays move the duty cycle at every stage.⁸ The minimum-pulse-width check catches a high or low phase that has become too short; run it on the routed clock rather than waiting for signoff.⁴ Use clock cells with matched edges, or pairs of inverters.
• Scan mode surprises. For manufacturing test, scan chains link the flip-flops into long shift registers, with little or no logic between neighbors. Skew that is harmless in normal operation can then make data race through in test mode (a hold failure).¹ Time the scan shift mode as its own scenario.
• Electromigration on clock drivers. Wear-out from RMS current rises with switching activity, and clock nets switch every cycle.¹⁵ Run EM checks on clock nets with their true switching rate, not the default assumed for data nets.

The problem

Given where the sinks are and how much load each presents, find a tree of wires from the source to all of them that meets a skew target with the least wire (and so the least capacitance and power). There are three formulations: a zero-skew tree (ZST), where every sink gets the clock at exactly the same time; a bounded-skew tree (BST), where skew only has to stay under a bound because signoff tolerates that much; and useful skew, which constrains only the local skew between sinks that exchange data.² Most algorithms split the work into topology generation (which sinks merge with which) and geometric embedding (where each branch point goes on the chip).

H-trees and the method of means and medians

An H-tree is exactly zero-skew by symmetry but only for regular sink arrays, so it serves top-level distribution.² The method of means and medians (Jackson, Srinivasan and Kuh, 1990) handles arbitrary sink positions top-down: split the sinks at the median into two equal halves, connect the center of mass of the whole set to the centers of mass of each half, and recurse with the split direction alternating.¹⁷²¹⁸ It balances sink counts and is fast, with no skew guarantee. Bottom-up recursive geometric matching (Kahng, Cong and Robins) pairs nearby subtrees and achieves near-zero pathlength skew in practice, still without a guarantee.¹⁷

Tsay’s exact zero skew

Tsay (1991) was the first to guarantee exact zero skew, under the Elmore model. It merges two zero-skew subtrees bottom-up at a tapping point on the wire joining their roots.¹⁷ With subtree delays $t_1$, $t_2$, downstream capacitances $C_1$, $C_2$, a connecting wire of length $L$, and per-unit resistance $r$ and capacitance $c$, equalizing the Elmore delay from the tapping point to both sides gives the fraction $z$ of the wire on subtree 1’s side:

If $0 \le z \le 1$ the tap lies on the wire. Otherwise one subtree is too slow, and the algorithm elongates (snakes) the wire on the faster side until delays match.¹⁸ Buffered trees apply the same merge per stage, since a buffer hides its subtree’s capacitance from upstream.¹⁸

Deferred-merge embedding (DME)

Earlier methods fixed each branch point’s location as soon as it was computed. DME, found independently by three groups around 1991–92, defers that choice. Given a topology, a bottom-up pass computes for each internal node a merging segment: the locus of all points where the two child subtrees can join with minimum added wire and zero skew. Chip wires run only horizontally and vertically, so distance is measured as $\Delta x + \Delta y$ (Manhattan distance). Under that measure these loci are Manhattan arcs, line segments tilted at 45°, and merging two arcs yields another arc. A top-down pass then picks the root anywhere on its segment and places each child at the point of its segment nearest the parent.¹⁷¹⁸ Kahng and Tsao summarize DME as a linear-time algorithm that optimally embeds any given topology with exact zero skew and minimum total wirelength. Its limitation is that it needs the topology as input, so it is paired with topology generators such as matching or greedy merging.¹⁷²

Bounded-skew trees (BST/DME)

Zero skew wastes wire when signoff tolerates some skew. BST/DME replaces merging segments with merging regions, the loci of feasible embedding points that keep skew within a bound $B$, then embeds top-down as before. It works under both pathlength and Elmore delay, and sweeping $B$ gives a smooth trade-off between skew and wirelength; at $B = 0$ it reduces to DME, and with no bound at all it approaches a Steiner tree, the shortest possible tree connecting the points.¹⁹

Elmore delay and its limits

For an RC tree, the Elmore delay to a node sums, over each resistor on the path from the source, that resistance times all capacitance downstream of it. It is the first moment of the impulse response, which makes it additive along a path and cheap enough to evaluate inside merge loops.¹⁶ Gupta, Tutuianu and Pileggi showed that it acts as a delay bound for RC trees, even with general input signals.¹⁶ It is often inaccurate but faithful: reducing Elmore delay almost always reduces true delay, so it ranks choices well.¹⁶ It knows nothing about input slew, nonlinear driver behavior or inductance, and skew is a small difference of two large delays, so computing it needs far more accuracy than computing either delay alone.¹ Modern CTS therefore builds with characterized lookup tables. TritonCTS characterizes buffered wire segments on the fly from Liberty data and selects segments from that table.⁵

Buffer insertion: van Ginneken’s dynamic program

Van Ginneken (1990) finds optimal buffer positions on a fixed tree under Elmore wire delay and a linear buffer model. Working from sinks to source, each candidate solution at a node is a pair $(Q, C)$: $Q$ is the slack (how late the signal may still arrive at that node) and $C$ is the capacitance the node’s driver will see downstream. At each legal buffer position the algorithm also considers a buffered option, merges candidate lists at branch points, and discards dominated candidates, those with more load and less required time than another. Run time is $O(n^2)$ in $n$ candidate positions. Lillis, Cheng and Lin extended it to $b$ buffer types in $O(b^2 n^2)$, and Li and Shi reduced that to $O(b n^2)$ by showing the useful candidates lie on a convex hull in the $(Q, C)$ plane.²⁰ For clocks the objective changes from maximum slack to balance and power, but the candidate-and-prune structure carries over. TritonCTS uses dynamic programming over its generalized H-tree to choose the minimum-power topology that meets latency and skew targets, with capacitated k-means for sink clustering.⁷

Clock mesh analysis

STA delay calculation assumes each net has one driver feeding a tree of wires. A mesh breaks that: many drivers are shorted together, paths split and rejoin, and the skew between mesh-buffer inputs feeds into the output. SPICE handles this accurately but slowly, and simplified models miss slew and input-skew effects, which is why research on fast mesh timing (including learned models trained on SPICE) continues.¹¹

Useful-skew scheduling as an LP

Fishburn (1990) posed skew scheduling as a linear program. Assign each register $i$ a latency $x_i$. For every path $i \to j$ with delays $d_{\mathrm{min}}$ and $d_{\mathrm{max}}$:

Minimize $T$, or for a fixed $T$ maximize the smallest margin across all constraints. Fishburn named the two hazards zero-clocking (setup) and double-clocking (hold), and on a 4-bit ripple-carry adder with accumulator cut the minimum period from 9.5 ns with zero skew to 7.5 ns with scheduled skew.¹ Every constraint bounds a difference $x_j - x_i$, so for a fixed $T$ the whole problem is a set of difference constraints. Draw each register as a node and each constraint $x_j - x_i \le b$ as an edge from $i$ to $j$ with weight $b$. A valid set of latencies exists exactly when no cycle of edges has a negative total weight, which the Bellman–Ford shortest-path algorithm checks. Summing the setup constraints around any cycle of $k$ registers cancels every $x$, leaving $T \ge \bigl(\sum (d_{\mathrm{max}} + t_{\mathrm{setup}})\bigr) / k$. For example, two registers that feed each other through 900 ps and 1100 ps paths (ignoring setup time) can never run faster than a 1000 ps period, whatever the skew. Skew can move time around a loop but cannot shrink the loop’s average. Practical CCD methods solve incremental, physically constrained versions of this problem after CTS, because each latency change must be built from real buffers on a real tree.¹⁴