Simulating a chip design at the register-transfer level before building it is essential but agonizingly slow, and splitting the work across CPU threads barely helps because within every simulated clock cycle the circuit's combinational logic creates fine-grained data dependencies between the pieces, forcing threads to stop and synchronize constantly; RepCut (UC Santa Cruz) breaks those dependencies by cutting the circuit into balanced partitions that share small overlaps and then REPLICATING the overlapping logic into each partition, so every thread can compute what it needs locally and the threads synchronize only once per cycle — and because each thread's now-smaller working set finally fits in cache, the speedup is SUPERLINEAR, hitting 27.1x on 24 threads for a big out-of-order-core SoC at just 3.81% extra replicated work.
The argument in one glance
-
Problem
Verifying a chip means simulating it for ages before it exists
Before a chip is fabricated, it is tested by RTL simulation — compiling the register-transfer-level design into a program that mimics the circuit cycle by cycle, so engineers can develop, debug, and verify it in software. The catch is speed: a large system-on-chip needs enormous numbers of test cycles for verification signoff, and the simulator is so slow that full coverage often cannot be reached within the development schedule. Making RTL simulation faster directly shortens how long it takes to build correct hardware, so the obvious lever is to run it across many CPU threads.
-
What people did
Split the circuit across threads and schedule around the dependencies
The natural plan is to partition the circuit into pieces, give each thread a piece, and run them in parallel. Verilator, the state-of-the-art open-source simulator, does a sophisticated version: it creates far MORE partitions than threads and uses dynamic scheduling to keep threads busy, trying to run each partition as soon as the data it depends on is ready. Cut the work up finely, schedule it cleverly, and in principle the threads stay busy and simulation scales.
-
Why it fell short
Intra-cycle dependencies force constant synchronization, and threads idle
It does not scale, because of INTRA-CYCLE data dependences. Within a single simulated cycle, combinational logic flows across the whole circuit, so a value computed in one partition is needed MID-CYCLE by another — and to hand it over safely, the threads must synchronize and signal when each dependence is ready. That synchronization is frequent and expensive, and profiling Verilator shows the consequence: many threads sit idle much of the time. Some partitions are too large (its partitioner puts no size limit), some too small to be worth the overhead, and inaccurate runtime predictions mean the scheduler cannot reliably have a dependence ready when a thread needs it. Partitioning only at registers, which communicate just once a cycle, would remove the mid-cycle sync — but then the partitions are wildly imbalanced. Scheduling around the dependences was the wrong fight.
-
This paper's idea
Replicate the overlap so the dependencies disappear
RepCut (UC Santa Cruz) stops scheduling around the intra-cycle dependences and instead ELIMINATES them. It cuts the circuit into balanced partitions that share small OVERLAPS, then REPLICATES the overlapping combinational logic into every partition that needs it. Once a partition holds a private copy of the boundary logic, it can compute every value it needs locally, without ever waiting on another thread mid-cycle — so the only synchronization left is once per simulated cycle, at the registers. Because shared memory means data need not be copied, only the computation (the logic cones) is duplicated, and the cost is tiny: 3.81% extra work on a large out-of-order SoC. The reward is not just linear scaling but SUPERLINEAR — 27.10x on 24 threads — because each thread's now-smaller working set finally fits in cache.
Why this problem is worth solving
RTL simulation is the workhorse of hardware verification, and
its slowness is a direct tax on how fast chips can be built. The
reason it is so hard to speed up with threads is a structural
feature of how circuits compute, the
the fact that within a
single simulated clock cycle, values ripple through the
circuit’s COMBINATIONAL logic (the gates between registers) in a
chain. A register holds a value at the start of the cycle; that
value feeds gates, whose outputs feed more gates, and so on until
the results land at the inputs of registers to be captured at the
cycle’s end. If you split the circuit across threads, these
combinational chains cross the partition boundaries: a gate in
one partition consumes a value produced by a gate in another,
DURING the same cycle. So the two threads cannot just run
independently — the consumer must wait until the producer has
computed the value and signaled that it is ready, which means
synchronizing mid-cycle, many times per cycle
Prior simulators accepted those dependences and tried to be
clever about them, which turns the whole problem into a
scheduling headache. Verilator cuts the circuit into many small
pieces and dynamically schedules them, hoping to run each piece
the moment its inputs are ready — but predicting readiness is
imperfect, so threads stall, and the
the cost, in both time and
lost parallelism, of coordinating threads so that a value
produced by one is safely visible to another before it is used.
Every mid-cycle dependence between partitions needs such a
handoff, and each handoff means a thread may block, wait at a
barrier, or spin — time spent coordinating instead of computing.
When dependences are frequent and fine-grained, as they are
inside one simulated cycle, this overhead dominates: threads
spend a large fraction of their time idle at synchronization
points rather than doing useful simulation work, so adding more
threads yields sharply diminishing returns
What people did before, and where it broke
- Verilator (threaded, dynamic scheduling). Cuts the circuit into many more partitions than threads and schedules them dynamically to keep threads busy. But its partitioner caps no sizes (so some pieces are far too big, some too small to be worth the overhead), and inaccurate execution-time predictions mean a dependence often is not ready when a thread wants it — so many threads sit idle. RepCut beats it by up to 3.09x.
- Partition-at-registers approaches. Cut only along register boundaries, which communicate once per cycle, removing mid-cycle synchronization entirely. But register boundaries do not divide the work evenly, so the partitions are wildly imbalanced and most threads finish early and wait.
- ESSENT and single-thread specialization. Push single-threaded RTL simulation to be very fast (activity-based evaluation, skipping unchanged logic). Excellent per-core, but leaves the parallel-scaling problem unsolved — one core can only go so fast, and the design’s code and data thrash the cache.
- Static partition-and-schedule. Pre-compute a partitioning and a thread schedule that respects the dependences. Still pays the mid-cycle synchronization the dependences demand, and is only as good as the schedule’s ability to have producers finish before consumers need them — which fine-grained circuits make hard.
- The gap. Every prior approach either tolerated frequent intra-cycle synchronization or accepted severe imbalance. None removed the dependences themselves. RepCut does, by replicating the overlapping logic so partitions become independent within a cycle — trading a few percent of extra computation for the elimination of nearly all synchronization.
How RepCut works
Split registers, find logic cones, cluster, partition to minimize replication, then duplicate
-
Split every register into a source and a sink new
Represent each register as TWO graph nodes: a read node (a source, the value available at cycle start) and a write node (a sink, the value to capture at cycle end). Because registers communicate only once per cycle, splitting them cuts the cross-cycle edges out of the graph, leaving a graph that reflects only the intra-cycle combinational flow that actually needs partitioning.
-
Find each sink's logic cone new
For every sink (a register-write or a primary output), crawl bottom-up through the combinational gates to the source inputs it depends on. That set of ancestors is the sink's CONE — the block of logic that must be evaluated to produce it. Cones from different sinks overlap wherever they share upstream gates.
-
Cluster the shared logic into a hypergraph new
Group gates that belong to the exact same set of cones into one cluster, then build an intersection HYPERGRAPH: vertices are sink clusters (the work), and hyperedges are the non-sink clusters (logic shared by several sinks). A hyperedge that would be split across partitions is precisely the logic that must be replicated.
-
Partition to minimize replication (KaHyPar) new
Hand the weighted hypergraph to a partitioner (KaHyPar), where each vertex's weight includes both its own simulation cost AND its proportional share of its ancestors' cost — so minimizing the cut weight minimizes the amount of logic that has to be duplicated. Balanced partitions with the smallest possible overlap fall out.
-
Replicate the overlaps, not the data new
For each cut hyperedge, copy its combinational logic into every partition that needs it, so each partition can compute all its inputs locally. Only COMPUTATION is replicated, never data — shared memory means the values live once, but the logic that derives boundary values is recomputed independently in each thread, breaking the cross-partition dependence.
-
Run: synchronize once per cycle, and fit the cache new
Each thread evaluates its now-independent partition with no mid-cycle waiting; threads meet at a single barrier per simulated cycle to exchange register values. With the per-thread working set shrunk, each core's code and data fit far better in cache, so instructions-per-cycle roughly doubles and the whole simulation runs SUPERLINEARLY faster.
The idea
Do not coordinate around the dependency — delete it by recomputing. Every prior parallel simulator treated the intra-cycle dependences as a fixed constraint and fought to schedule threads around them, which is a losing battle because the dependences are frequent and fine-grained. RepCut reframes the problem: a cross-partition dependence exists only because one partition needs a value another computes, so if BOTH partitions compute that value themselves, the dependence is gone. It replicates the small overlap of boundary logic into each partition, and the mid-cycle handoffs vanish. This is the recompute-instead-of-communicate trade the site keeps meeting — the pipeline-recomputation page throws activations away and recomputes them rather than storing and moving them — and here it is spent to buy independence: a few percent of duplicated gate evaluations in exchange for eliminating nearly all synchronization. When coordination is the bottleneck, redundant work can be the cheaper currency.
Change the graph so the cut you want becomes legal. The trick that makes the whole thing possible is splitting each register into a read-source and a write-sink node. A register is the one place a circuit naturally communicates only once per cycle, so by representing it as two separate nodes RepCut removes the cross-cycle edges from the dependency graph, leaving a clean combinational graph whose cones and overlaps can be reasoned about and partitioned. It is the same split-a-node-to-expose-the- structure move the heterogeneous-serving page uses when it splits each GPU into an in-vertex and an out-vertex so a capacity can live on the edge between them: a small change of representation turns an intractable tangle into a graph a standard partitioner (KaHyPar) can cut well. The representation is doing the work.
The real bottleneck was the cache, and parallelism was how to shrink the working set. The most surprising result is that 24 threads deliver 27x, not 24x — more than the thread count. The reason is not magic but a bottleneck hiding beneath the synchronization one: a single-threaded simulator’s code and data are too large for the last-level cache, so it thrashes, running at an instructions-per-cycle of just 0.41. Splitting the work across threads shrinks each thread’s working set until it crosses the threshold from frequent cache misses to frequent cache hits, and IPC doubles to 0.95. So the partitioning does double duty: it enables parallel execution AND it fits the cache, and the cache win is what lifts the speedup above linear. It is the measure-the-true-cost lesson again — the binding constraint was memory, not compute, so the technique that shrinks the memory footprint per core is the one that actually wins.
Why a little replication beats a lot of synchronization
One simulated cycle, cut two ways
A circuit partitioned across threads. Numbers from RepCut's evaluation on MegaBOOM SoCs.
Step 1 of 5
Inside one cycle, logic ripples across the whole chip
At the start of a simulated cycle, registers hold their values. Combinational logic then propagates those values through chains of gates until results arrive at register inputs, to be captured at the cycle's end. This ripple crosses the entire circuit — there is no natural seam mid-cycle, because the gates form one connected web of dependencies.
registers communicate once per cycle; the combinational logic between them is the fine-grained web verification needs enormous cycle counts, so per-cycle speed is what limits coverage
Why it works
- Intra-cycle dependences exist only because one partition needs a value another computes → replicating the boundary logic lets each partition compute that value itself → the cross-partition dependence disappears and mid-cycle synchronization is eliminated.
- With shared memory, data need not be copied, only computation → RepCut duplicates just the logic cones that straddle boundaries, not any data → the replication cost is tiny (3.81% on the largest design, under 25% everywhere).
- Splitting each register into a read-source and write-sink node removes cross-cycle edges → the remaining graph is purely the intra-cycle combinational flow → a standard hypergraph partitioner can find balanced cuts with minimal overlap.
- A single thread’s working set thrashes the last-level cache → partitioning shrinks each thread’s footprint below the cache-fit threshold → per-core IPC roughly doubles, pushing the speedup past linear to superlinear.
- Separate cores in a multi-core SoC are already nearly independent → so larger, more-core designs have little boundary logic to replicate → replication cost falls with scale and the method works best exactly where simulation is slowest.
What it costs
- Strong-scaling has a ceiling. A modestly-sized design can be split only so far before fixed per-cycle costs dominate; RepCut helps most on large designs (weak scaling), and small ones hit a wall — RocketChip-1C reaches only about 6-7x on 24 threads.
- Small designs amortize poorly. A small design’s simulated cycle is nearly an order of magnitude shorter, so there is far less work to hide the near-fixed synchronization and global- update costs behind, and speedup suffers.
- Partitions end up imbalanced despite balancing. Replication is distributed unevenly, so even when the hyperedge cut is nearly balanced the actual per-thread work is not; the weighting is a proxy that assumes even ancestor cost and introduces minor error.
- Very compiler-sensitive. The generated simulator’s speed depends heavily on the C++ compiler — Clang 14 versus Clang 10 nearly doubles MegaBOOM-4C performance — so results are entangled with toolchain choices in a way Verilator is less exposed to.
- Partitioning is NP-hard and heuristic. Finding the minimal- replication balanced cut is NP-hard, so RepCut relies on the KaHyPar heuristic, which need not find the optimal partition; the quality of the cut bounds the quality of the result.
The evaluation
Chipyard-generated SoCs from 70K to 1.2M FIRRTL nodes, spanning in-order Rocket and out-of-order BOOM cores in one-to-four-core configurations, on a 24-core dual-socket server, against Verilator with profile-guided optimization, measuring speedup, replication cost, and per-core performance counters.
Three ways to parallelize RTL simulation
| Property | Partition at registers only | Verilator (many partitions + dynamic scheduling) | RepCut (replication-aided) |
|---|---|---|---|
| Mid-cycle synchronization | |||
| Load balance | |||
| Thread utilization | Low — most threads finish early and wait | ||
| Extra cost | |||
| Speedup (24 threads, MegaBOOM-4C) | Poor (imbalance-bound) |
Check yourself
Check your understanding
1. Verilator fights intra-cycle dependences by cutting the circuit finely and dynamically scheduling partitions to run when their inputs are ready; RepCut instead REPLICATES the boundary logic. Predict why replication is the more effective response.
2. RepCut achieves 27.10x speedup on 24 threads — MORE than the thread count. Predict where the extra factor beyond 24x comes from.
3. A crucial early step is representing each register as TWO nodes — a read-source and a write-sink — rather than one. Predict why this seemingly minor change of representation is important.
4. RepCut reports that larger designs with MORE cores have LOWER replication cost (3.81% for a 4-core BOOM), and that it scales best on exactly these designs. Predict why bigger, more-core designs are the easy case.
Sources
- ACM DL: RepCut: Superlinear Parallel RTL Simulation with Replication-Aided Partitioning — ASPLOS 2023 (full text read via the ACM PDF; no arXiv preprint).
- Artifact (Zenodo, DOI 10.5281/zenodo.7707389) — open-source RepCut implementation and reproduction scripts.