Abstract
We introduce a data distribution scheme for $\mathcal{H}$-matrices and a distributed-memory algorithm for $\mathcal{H}$-matrix-vector multiplication. Our data distribution scheme avoids an expensive $\Omega(P^2)$ scheduling procedure used in previous work, where $P$ is the number of processes, while data balancing is well-preserved. Based on the data distribution, our distributed-memory algorithm evenly distributes all computations among $P$ processes and adopts a novel tree-communication algorithm to reduce the latency cost. The overall complexity of our algorithm is $O\Big(\frac{N \log N}{P} + \alpha \log P + \beta \log^2 P \Big)$ for $\mathcal{H}$-matrices under weak admissibility condition, where $N$ is the matrix size, $\alpha$ denotes the latency, and $\beta$ denotes the inverse bandwidth. Numerically, our algorithm is applied to address both two- and three-dimensional problems of various sizes among various numbers of processes. On thousands of processes, good parallel efficiency is still observed.
Introduction
In scientific computing, solving partial differential equations (PDEs) or integral equations often results in massive, dense matrices. Hierarchical matrices ($\mathcal{H}$-matrices) are a clever mathematical trick to compress these dense matrices into a "data-sparse" hierarchical form, reducing the memory and computational cost from $O(N^2)$ to a highly efficient $O(N \log N)$.
However, to solve truly massive problems, we need to distribute these $\mathcal{H}$-matrices across supercomputers with distributed memory. Previous attempts at parallelizing $\mathcal{H}$-matrices relied on dynamic, task-based scheduling. The problem? The scheduling algorithm itself required $O(P^2)$ operations, where $P$ is the number of processors. If you have 16 processors, that's fine. If you have 10,000 processors, the system spends more time figuring out who should do the work than actually doing the work, killing parallel efficiency. This paper seeks to eliminate that scheduling bottleneck entirely.
Methodology
The authors ditch dynamic scheduling in favor of a static, geometry-aware approach that aligns the computational hierarchy with the physical problem domain.
Hierarchical Process Organization and Data Distribution
The physical domain of the problem is recursively partitioned into a "domain tree." The authors organize the MPI processes into a matching "process tree." Instead of assigning random blocks of the matrix to random processors, data is distributed based on this process tree. If a processor is assigned to a specific geometric sub-domain, it owns the matrix data corresponding to that sub-domain. This naturally balances the memory and computational load.
H-Matrix Structure and Admissibility
By tying the hierarchy of the computer processors directly to the physical geometry of the simulated domain, load balancing happens almost automatically. The algorithm successfully handles both "weak" admissibility (simpler, blocks only interact with direct neighbors) and "standard" admissibility (more complex, blocks interact with a wider buffer zone). While standard admissibility requires more communication, the tree-based approach keeps it manageable.
Tree-Communication Algorithm
Matrix-vector multiplication requires adding up results from different processors. Instead of naive, expensive all-to-all communications, the authors introduce "tree-reduction" and "tree-broadcast." Processors pass partial sums up the process tree to "group leaders," who then broadcast the final results back down. This drops the communication latency to a highly scalable $O(\log P)$.
Experimental Evaluation
The authors evaluated their algorithm using synthetic $\mathcal{H}$-matrices based on ideal 2D and 3D geometric grids. The 2D grids scaled up to $65536^2$ (over 4 billion degrees of freedom), and the 3D grids scaled up to $1024^3$ (over 1 billion degrees of freedom).
Key Results
- Massive Scalability: The algorithm was tested on the TACC Stampede2 supercomputer using up to 16,384 MPI processes. Previous methods struggled to scale past 16 processes.
- High Parallel Efficiency: For large problems (e.g., an $8192^2$ grid), the algorithm maintained over 90% parallel efficiency on thousands of cores under standard admissibility conditions.
- Blazing Fast Compute: Matrix-vector multiplications for problems with hundreds of millions of degrees of freedom were completed in just a few seconds.
- Theoretical Complexity Achieved: The authors proved, and empirically demonstrated, that their overall algorithmic complexity is $O(\frac{N \log N}{P} + \alpha \log P + \beta \log^2 P)$, where $\alpha$ is latency and $\beta$ is inverse bandwidth.
Discussion and Future Work
While this work provides a scalable foundation for $\mathcal{H}$-matrix-vector multiplication, several avenues for improvement remain. The current code relies entirely on MPI; combining it with OpenMP for shared-memory multi-threading within compute nodes could further reduce local communication costs. Additionally, this paper only addresses matrix-vector multiplication. A full algebraic suite requires matrix-matrix multiplication, matrix inversion, and LU factorization, which the authors plan to address in future work. Finally, while load balancing is generally excellent, slight imbalances persist at domain corners under standard admissibility conditions, though these are bounded by a constant factor.
Summary updated