The Algorithm That Could Shrink Chip Design Time by Half

The Slowest Part of Designing a Chip

Imagine waiting three hours for your laptop to boot up. Now imagine waiting three hours for a single simulation of whether your chip design will actually work. That's the reality facing engineers who design the integrated circuits found in everything from smartphones to satellites.

The bottleneck isn't the clever logic that makes computations happen. It's something more mundane: the parasitic electrical effects that zip through the copper wires and insulation layers when billions of transistors switch on and off. These effects create vast networks of resistors and capacitors—RC networks—that must be simulated to verify that a chip will function correctly before anyone spends billions of dollars manufacturing it.

A team of researchers from Fudan University and the company Empyrean has developed a new method called FlexRC that can simulate these RC networks up to 50 times faster than existing approaches, while maintaining accuracy that engineers can trust. Their work, published on arXiv, tackles one of the most stubborn computational bottlenecks in modern chip design.

The Problem with Parasitics

When engineers design a chip, they spend enormous effort optimizing the transistors themselves—the tiny switches that flip between on and off states. But once the chip is laid out physically, a new challenge emerges: the connections between components behave like resistors and capacitors.

Modern chips contain miles of copper wiring per square centimeter. Adjacent wires, separated by insulating material, form capacitors. The wires themselves have resistance. These parasitic elements—unwanted but unavoidable electrical effects—can cause signals to arrive late, buffers to switch incorrectly, and entire systems to fail.

"In modern IC design, interconnect effects have become a dominant factor in determining whole-chip performance," the researchers note, citing decades of accumulated evidence from the semiconductor industry. The RC networks created by these parasitic effects can contain hundreds of thousands of individual nodes, each representing a point where electrical behavior might matter.

The challenge is that these massive RC networks must be connected to nonlinear devices—transistors, memory cells, and other active components—for simulation. "The large numbers of nodes and ports in RC parasitic networks make direct nonlinear simulation computationally prohibitive and time-consuming," the researchers explain. A port, in this context, is simply a connection point between the RC network and the nonlinear devices it feeds into. Modern chips can have thousands of such ports.

Model Order Reduction: Compressing the Essentials

When a system has too many components to simulate directly, engineers use a technique called model order reduction (MOR). The idea is to create a much smaller system—one with far fewer nodes—that behaves essentially the same way as the original.

Think of it like approximating a complex curve with a simpler one. A jagged mountain profile might require thousands of data points to describe accurately, but a smooth polynomial with just a dozen coefficients might capture everything that matters for, say, calculating airflow over an aircraft wing. The reduction is valid because the full complexity wasn't necessary for the question being asked.

For RC networks, the goal is to compress a system with perhaps 500,000 nodes down to one with just a few thousand, while preserving the input-output behavior that matters when the RC network connects to transistors and other components.

The standard approach to ensuring this preservation is called moment matching. The transfer function of an electrical system—essentially a mathematical description of how inputs transform into outputs—can be expressed as an infinite series. Each term in this series is a "moment." If the reduced model matches the same moments as the original, it will behave identically across a range of frequencies.

The key expansion point is the frequency at which the system is being analyzed. Traditional methods often fixed this at zero, corresponding to direct current conditions. But circuits operate across many frequencies simultaneously, and matching moments at just one frequency can produce inaccurate results elsewhere.

The Limitations of Existing Approaches

Researchers have developed numerous reduction techniques over the past three decades, but each comes with significant trade-offs.

Projection-based methods like PRIMA (Passive Reduced-Order Integrator Macro-modeling Algorithm) construct explicit mathematical subspaces to project the large system onto a smaller one. The resulting reduced models are accurate and passive—meaning they don't generate energy, which is physically required for RC networks. However, the projection matrices become dense, meaning most entries are nonzero. This dense structure makes subsequent simulations slow because every node affects every other node.

Port-compression methods attempt to identify and eliminate redundant ports, but "these methods rely on port correlations that are often weak in practical networks," the researchers note. Without strong correlations, compression fails to achieve meaningful reduction.

Elimination-based methods like PACT, TICER, and SIP take a different approach. Rather than constructing projection matrices explicitly, they use sparse Gaussian elimination—the same algorithm taught in introductory linear algebra—to generate reduced models that naturally preserve sparsity. A sparse matrix has mostly zero entries, which makes matrix operations dramatically faster.

SIP (Single-point Implicit PTL) generates passive reduced models that match the first two DC moments, but this may be insufficient for high-accuracy applications. TurboMOR-RC extends SIP to higher-order moment matching while maintaining sparse banded structure, but its frequency point is fixed at zero.

SMP-RCR introduced multi-point moment matching with freely chosen frequency sequences, plus sparsity-control techniques. But "SMP-RCR must explicitly generate the intermediate discarded blocks that are not retained in the final reduced-order model," the researchers explain. "Since these blocks can be very large and dense, the reduction time and memory cost can become prohibitive for large-scale cases."

The core tension: methods that offer flexibility (multiple frequency points, sparsity control) incur heavy computational costs during the reduction itself. Methods that are fast to apply (elimination-based approaches) sacrifice that flexibility.

FlexRC: Combining Flexibility with Efficiency

FlexRC threads this needle by combining elimination-based methods with a carefully designed projection step. The result is a method that preserves the sparsity advantages of elimination while enabling multi-point matching and port reduction.

The algorithm proceeds in stages. First, standard elimination as in prior methods removes the conductance coupling between port variables and internal variables. This step eliminates the block that would otherwise connect ports directly to internal nodes, producing the structure shown in equation (4) of the paper.

The innovation comes next. Rather than performing full QR decomposition as in TurboMOR-RC or SMP-RCR, FlexRC computes an economic QR decomposition—one that produces only the columns actually needed for computation. This is significantly cheaper for large systems.

The researchers then apply a tolerance-controlled port reduction technique. After decomposing the capacitive coupling matrix, they examine the row norms—essentially measuring how much each row contributes to the overall matrix. Rows with small norms contribute little and can be discarded with minimal impact on accuracy.

"Given a prescribed port-reduction tolerance tol, we choose the largest integer m such that the cumulative discarded energy doesn't exceed tol," the researchers explain. This provides a principled way to trade accuracy for reduced model size: setting a tighter tolerance preserves more information, while a looser tolerance enables greater compression.

The retained rows form a reduced coupling matrix that preserves the sparsity structure inherited from the triangular R matrix. This is crucial because sparsity translates directly to computational speed during simulation.

The Three Adjustable Levers

What makes FlexRC genuinely new is not a single technique but a framework with three independently tunable components.

The first lever is frequency point selection. Unlike TurboMOR-RC, which is locked to s₀ = 0 (the DC point), FlexRC allows engineers to specify arbitrary frequency points for moment matching. "The frequency points can be specified by the user to improve accuracy for the target transient response," the researchers note. For circuits where high-frequency behavior dominates—fast switching transients, for example—matching at a nonzero frequency can dramatically improve accuracy without increasing model complexity.

The second lever is port-reduction tolerance. The tolerance parameter controls how aggressively the algorithm discards port connections in the internal subsystem. The researchers provide a rigorous error bound: the relative truncation error is guaranteed to be no larger than the specified tolerance. This gives engineers a quantitative guarantee about the accuracy they're sacrificing for speed.

With the conservative setting tol = 0 (no port reduction), "the resulting reduced models have simulation efficiency comparable to that of TurboMOR-RC." But with moderate tolerance settings, FlexRC can achieve significantly greater reduction—up to the reported 50× speedup—while maintaining acceptable accuracy.

The third lever is optional sparsity control. By retaining more nodes during elimination, the sparsity-control variant produces even sparser reduced models, trading some additional fill-in for faster simulation times. Fill-in refers to nonzero entries that appear in previously sparse regions during the elimination process.

Preserving Passivity and Proving Correctness

For RC networks, passivity is non-negotiable. A passive system cannot generate energy—it can only store and dissipate it. This reflects physical reality: resistors convert electrical energy to heat, capacitors store energy in electric fields. Any reduced model that violates passivity could predict impossible behaviors like signal amplification without input.

The researchers analyze passivity carefully. For the exact reduction (no port reduction), passivity follows from the congruence structure of the construction—mathematical transformations that preserve the passive property. When port reduction is applied, the reduced capacitance matrix receives a symmetric perturbation. The researchers show that passivity is preserved as long as this perturbation remains sufficiently small.

They also extend moment-matching analysis to RC networks with singular conductance matrices—a mathematically challenging case that prior work avoided. "To the best of our knowledge, this is the first treatment of this case for elimination-based RC reduction methods." The result is a Laurent moment matching theorem that covers a broader class of networks than previous work.

Industrial Validation

Theory is essential, but engineers need evidence that methods work on real-world problems. The researchers tested FlexRC on industrial RC examples from analog circuit designs and the IBM Power Grid benchmark suite—a standard collection of test cases representing genuine challenges in chip analysis.

The results demonstrate the method's effectiveness across multiple dimensions.

For the IBM power grid benchmark ibmpg2t with 1,200 ports, the researchers compared FlexRC directly against TurboMOR-RC, the current state-of-the-art for sparse RC reduction. Using frequency points [0, 0, 0]—essentially matching at DC only—both methods produced reduced models of the same order. The transient responses matched almost perfectly, with signed errors staying within acceptable bounds.

But the critical advantage emerges when port reduction is enabled. With a tolerance setting of tol = 0.01, FlexRC reduced the model order significantly while maintaining accuracy well within engineering tolerances. The flexibility to adjust this tolerance provides a dial that engineers can tune based on their accuracy requirements.

The sparsity results tell an equally compelling story. For AAADC_net64, the default FlexRC model contained 30,068,235 nonzero entries. With sparsity control enabled (FlexRC-SC), this dropped to 24,769,262—a reduction of about 18%. For AAADC_net76, the default model had 29,731,297 nonzeros, while the sparsity-controlled variant had just 4,860,346—an 84% reduction.

These sparsity differences translate directly to simulation speed. Solving sparse systems is dramatically faster than solving dense ones because algorithms can skip the zero entries entirely. A model with 84% fewer nonzeros might simulate 5 to 10 times faster, depending on the solver and problem structure.

The researchers also measured reduction time and transient simulation time. Their experiments "demonstrate the effectiveness of FlexRC in terms of reduction time and transient simulation time," though specific speedup numbers vary by problem size and parameter settings. The key insight is that the economic QR decomposition avoids explicitly forming large dense intermediate blocks, which was the computational bottleneck in SMP-RCR.

Why This Matters for Chip Design

The semiconductor industry is at an inflection point. Advanced process nodes—the latest generation of manufacturing technology—are becoming simultaneously more powerful and more difficult to simulate. Transistors are smaller, wires are closer together, and parasitic effects are more pronounced. Every design verification run costs millions of dollars in compute time.

Current engineering practice often involves approximations and compromises. Engineers might use coarse simulations during early design phases, reserving detailed simulations for critical paths. They might accept less accurate models to keep simulation times manageable. They might reduce RC networks aggressively, risking undetected timing violations in production.

FlexRC doesn't eliminate these trade-offs, but it shifts the Pareto frontier. Engineers can achieve a given accuracy with smaller models and faster simulations, or maintain model size while targeting multiple frequency points for better coverage. The tolerance parameter provides a quantitative, physically meaningful way to control the accuracy-versus-speed trade-off.

The method is particularly relevant for analog and mixed-signal circuits, where multiple frequency bands matter simultaneously. A wireless transmitter, for instance, operates at radio frequencies during transmission but contains baseband circuitry operating at much lower frequencies. Multi-point moment matching can capture behavior across both bands without requiring separate reduced models.

Limitations and Open Questions

No method solves every problem, and the researchers are transparent about FlexRC's constraints.

Port reduction introduces approximation errors, and while the researchers provide theoretical bounds, these bounds may be conservative. In practice, the actual error could be larger or smaller than predicted. Engineering judgment remains necessary when setting tolerances.

The multi-point extension to more than two frequency points requires additional algorithmic steps similar to TurboMOR-RC's multi-stage process. While the paper extends to q ≥ 3 points in principle, the computational complexity grows with each additional point. For most practical applications, two or three points likely suffice.

The method assumes RC networks without inductive elements. Adding inductors would require different mathematical treatment, as the resulting systems would no longer be positive real in the same sense.

Numerical stability remains a concern for very large problems. The economic QR decomposition and subsequent manipulations involve matrix operations that can accumulate roundoff errors. For problems with hundreds of thousands of nodes, the condition numbers of intermediate matrices could become problematic.

Finally, the researchers note that implementation efficiency depends heavily on software details—memory layout, cache utilization, parallelization—that go beyond the algorithmic description. Production implementations would require careful engineering to realize the theoretical advantages.

Looking Forward

The researchers identify several directions for future work. Extending the framework to RLC networks—adding inductors to the resistive and capacitive elements—would broaden applicability to power distribution networks and high-speed links. Developing adaptive tolerance selection, where the algorithm automatically chooses tolerances based on error indicators, would reduce the tuning burden on engineers. Hardware acceleration using GPUs or specialized matrix engines could further improve performance for the largest problems.

There's also potential for integration with machine learning approaches. Reduced-order models are essential for training neural network approximations of circuit behavior, and faster reduction methods could enable more extensive exploration of the design space.

The broader context is important to appreciate. Model order reduction is one thread in a larger tapestry of simulation speedups that have made modern chip design possible. Without decades of algorithmic advances, the complexity of today's processors would be unmanageable. Every improvement in simulation speed translates to faster design cycles, lower costs, and ultimately more capable electronic systems.

FlexRC represents incremental but meaningful progress on a problem that never fully resolves. As chips continue to grow in complexity, methods like this become increasingly critical—not because they solve everything, but because they extend the horizon of what's tractable, one order-of-magnitude improvement at a time.