Exploiting nested task-parallelism in the H-LU factorization

Rocío Carratalá-Sáez, Sven Christophersen, José Ignacio Aliaga, Vicenç Beltran, Steffen Börm, Enrique S. Quintana-Ortí

Introduction

Hierarchical matrices ($\mathcal{H}$-matrices) are a powerful mathematical tool for representing large, dense matrices common in Boundary Element Methods (BEM). By organizing data into a hierarchy of dense blocks and low-rank approximations, they reduce computational complexity from $O(n^2)$ to nearly $O(n)$. However, parallelizing the LU factorization of these matrices is notoriously difficult due to recursive dependencies and non-contiguous memory layouts. This paper presents a high-performance approach using the OmpSs-2 programming model to unlock nested task-parallelism, achieving significant speedups on modern multicore processors.

The Challenge of Hierarchical Parallelism

Standard parallel models often struggle with the recursive nature of $\mathcal{H}$-matrices. Traditional implementations rely on "barriers" (like taskwait) at each level of the hierarchy, which prevent a processor from starting a sub-task until the entire parent task is complete. This creates significant bottlenecks where cores remain idle despite data being ready. Furthermore, the fragmented memory layout of $\mathcal{H}$-matrices makes it difficult for runtimes to track data dependencies using standard memory addresses, especially when low-rank arithmetic causes data to shift.

Hierarchical partitioning of a matrix into dense and low-rank blocks

Innovations in Task-Parallelism

To address these hurdles, the authors propose two primary innovations integrated into the OmpSs-2 runtime:

  • The Skeleton Array: This auxiliary data structure provides a unique "representant" memory address for every leaf block in the matrix. By using this fixed skeleton to track dependencies instead of the actual data blocks, the runtime can accurately manage task synchronization regardless of the underlying memory layout.
  • Weak Dependencies & Early Release (WD+ER): This mechanism allows for fine-grained synchronization. Weak dependencies enable a parent task to become "ready" while its data is still being processed by children. Early release allows a task to signal completion of specific data segments as soon as relevant sub-tasks finish, rather than waiting for the entire block to complete.
Sequence of operations for the H-LU factorization, illustrating the dependencies between sub-blocks

As shown in the operation sequence above, WD+ER allows tasks to "cross the boundaries" of the hierarchy. For instance, sub-operations within the factorization of $A_{1,1}$ (O1.1 to O1.5) can release dependencies for subsequent operations like O2 or O3 before the entire top-level block is technically finished. This overlap is critical for maintaining high processor utilization.

Results and Performance

The proposed method was evaluated using BEM-generated matrices, such as those from Laplace equation problems. Results demonstrate superior scalability compared to standard task-parallel versions and multi-threaded BLAS libraries like Intel MKL. On a 24-core system, the WD+ER implementation achieved speedups of up to 19.04x compared to the sequential version. The approach consistently maintained higher GFLOPS/core, particularly as the number of cores increased or block sizes became smaller, where traditional methods typically stall.

Conclusion

By decoupling logical dependency tracking from physical storage and utilizing advanced task-parallel features like Weak Dependencies and Early Release, this approach effectively breaks the "recursive trap" of $\mathcal{H}$-LU factorization. Future work will explore hybrid parallelism—combining high-level task scheduling with low-level loop parallelism—and extending these concepts to distributed memory environments.

Summary updated

BibTeX
@article{carratalasaez2019exploiting,
  author = {Rocío Carratalá-Sáez and Sven Christophersen and José Ignacio Aliaga and Vicenç Beltran and Steffen Börm and Enrique S. Quintana-Ortí},
  title = {{Exploiting nested task-parallelism in the H-LU factorization}},
  journal = {J. Comput. Sci.},
  year = {2019},
  doi = {10.1016/j.jocs.2019.02.004},
}
Figure