Abstract
In this paper, we consider the problem of distributing the tiles of a dense matrix onto a set of homogeneous nodes. We consider both the case of non-symmetric (LU) and symmetric (Cholesky) factorizations. The efficiency of the well-known 2D Block-Cyclic (2DBC) distribution degrades significantly if the number of nodes $P$ cannot be written as the product of two close numbers. Similarly, the recently introduced Symmetric Block Cyclic (SBC) distribution is only valid for specific values of $P$. In both contexts, we propose generalizations of these distributions to adapt them to any number of nodes. We show that this provides improvements to existing schemes (2DBC and SBC) both in theory and in practice, using the flexibility and ease of programming induced by task-based runtime systems like Chameleon and StarPU.
Introduction
In high-performance computing (HPC), dense linear algebra factorizations such as LU and Cholesky are fundamental building blocks. The standard approach for distributing matrix tiles across a cluster is the 2D Block-Cyclic (2DBC) distribution. While highly effective when the number of nodes $P$ allows for a balanced $r \times c$ grid (ideally a square), its performance suffers significantly when $P$ is prime or does not factor into two nearly equal integers. This paper addresses the practical challenge of maintaining high efficiency on "weird" numbers of nodes, ensuring that researchers can utilize their full hardware allocation without performance penalties.
The Challenge of Non-Square Node Counts
The primary limitation of 2DBC is its rigidity. If a user is allocated 23 nodes, a standard 2DBC mapping would likely result in a $23 \times 1$ or $1 \times 23$ grid. Such lopsided configurations create massive communication bottlenecks because the "fan-out" of data broadcasts is maximized along one dimension. Alternatively, a user might choose to leave nodes idle (e.g., using only 16 nodes in a $4 \times 4$ grid), which wastes expensive computational resources.
As shown in the experimental data, the throughput (TFlop/s) per node and total system performance drop sharply as the grid becomes less square. The $23 \times 1$ mapping performs significantly worse than configurations that allow for more balanced communication, such as $4 \times 4$ or $5 \times 4$.
Methodology: Generalized Distribution Schemes
To overcome these limitations, we leverage modern task-based runtime systems like StarPU and the Chameleon library. These systems decouple the algorithm from the data distribution, allowing for complex, irregular mapping patterns that would be prohibitively difficult to implement manually using MPI.
Generalized 2DBC (G-2DBC) for LU Factorization
G-2DBC relaxes the requirement for a simple rectangular grid. Instead, it constructs a larger virtual pattern where nodes can appear multiple times in a way that approximates a square layout. This approach keeps the communication cost bounded by $2\sqrt{P} + \frac{2}{\sqrt{P}}$, which is near-optimal for any $P$.
Greedy ColRow & Matching (GCR&M) for Cholesky Factorization
Symmetric factorizations like Cholesky are more complex because only half the matrix is stored. We propose a two-phase heuristic:
- Greedy Phase: Assigns "colrows" (the union of a row and a column) to nodes to ensure perfect workload balance.
- Matching Phase: Uses a bipartite graph matching algorithm to assign specific tiles to nodes, minimizing data movement and network congestion.
Experimental Evaluation
The proposed schemes were evaluated on the PlaFRIM cluster using up to 44 nodes (36 Intel Xeon Skylake Gold cores per node). We tested matrix sizes ranging from 50,000 to 300,000.
Key Results
- LU Factorization ($P=23$): G-2DBC significantly outperformed standard 2DBC. By avoiding the $23 \times 1$ bottleneck, it achieved performance levels comparable to those seen with perfect square node counts.
- Cholesky Factorization ($P=31$): The GCR&M scheme achieved 11% higher throughput than the best possible SBC distribution, which was limited to using only 28 nodes.
- Strong Scaling: Unlike traditional methods that show "staircase" performance improvements only at square numbers, our schemes enable consistent performance gains with every additional node.
Conclusion and Future Work
By embracing irregular data distributions enabled by task-based runtimes, we can achieve near-optimal performance on any number of nodes. This flexibility is crucial for maximizing the utility of modern HPC clusters. Future work will focus on extending these distributions to heterogeneous environments (mixing CPUs and GPUs) and optimizing the memory overhead associated with managing large, complex distribution patterns.
Summary updated