Abstract
To construct a parallel preconditioner to solve the linearized problem $JX = B$, we identify the parallelizable operations involved. By utilizing $m$ processing elements, this research proposes a hierarchical preconditioning strategy that decomposes large, densely coupled nonlinear equations into a tree-like structure of independent sub-problems, achieving significant simulation speedups and improved numerical robustness compared to standard industry methods.
Introduction
Harmonic Balance (HB) is the standard method for simulating the steady-state behavior of nonlinear circuits, such as mixers and power amplifiers, in the frequency domain. However, as circuits grow in complexity and nonlinearity, HB faces a "curse of dimensionality." The primary bottleneck is solving the massive system of linear equations—the Jacobian matrix—generated during Newton iterations.
Standard iterative solvers like GMRES require a preconditioner to converge efficiently. The industry-standard Block-Diagonal (BD) preconditioner often fails or becomes excessively slow for strongly nonlinear circuits because it ignores frequency coupling. Furthermore, traditional HB algorithms are difficult to parallelize due to dense data dependencies. This paper addresses these challenges through a hierarchical, divide-and-conquer approach.
Hierarchical Preconditioning Strategy
The core of the proposed method is the Hierarchical Harmonic Balance Preconditioner. This strategy decomposes the top-level linearized HB problem into a series of smaller, independent matrix problems across multiple levels, creating a tree-like data dependency structure.
The Jacobian is partitioned along frequency boundaries, where each "super block" in the hierarchy corresponds to a specific set of frequency components. Lower-level preconditioners are created recursively until the sub-problems are small enough to be solved directly. For larger sub-blocks, the authors utilize Flexible GMRES (FGMRES). To optimize memory usage, the sub-problems employ an implicit, matrix-free representation, using time-varying linearizations that are low-pass filtered to create time-domain waveforms with decreasing resolution further down the hierarchy.
Parallel Implementation
The tree structure naturally facilitates coarse-grained parallelization. Unlike standard methods where parallelization is often an afterthought, this hierarchical structure provides independent tasks at each level of the tree by construction.
The implementation utilizes both MPI for distributed clusters and pThreads for multi-core shared memory systems. By employing non-blocking communication, the solver can overlap computation with data transfer. The granularity of the simulation can be tuned by adjusting the number of levels and sub-problems to match the specific hardware architecture, such as matching the tree width to the number of available processing elements.
Experimental Results
The method was evaluated on a diverse suite of benchmark circuits, including driven circuits (mixers, LNAs), autonomous circuits (oscillators), and envelope-following analysis for power amplifiers.
Key performance metrics include:
- Parallel Speedup: On a 9-CPU platform, the parallel implementation achieved speedups of approximately 3.5x to 4.0x compared to the serial version.
- Algorithmic Efficiency: In serial tests, the hierarchical preconditioner was 2x to 8x faster than the standard Block-Diagonal (BD) approach. This is largely because the hierarchical method captures more nonlinear coupling, requiring significantly fewer iterations to converge.
- Oscillator and Envelope Analysis: For a 15-stage ring oscillator, simulation time dropped from 83 seconds (BD) to 44 seconds (Hierarchical). In envelope-following analysis for a power amplifier, the hierarchical approach was 32x faster than traditional transient simulation.
Conclusion and Future Work
While the hierarchical approach offers significant gains in speed and robustness, communication overhead remains a bottleneck as the CPU count increases, particularly for smaller circuits. Future work will focus on optimizing the framework for heterogeneous computing environments by dynamically adjusting sub-problem sizes to match varying processor speeds. Additionally, managing memory resources on shared-memory systems remains a priority for very large-scale simulations to prevent performance degradation due to memory thrashing.
Summary updated