# Batching the tasks of the LU factorization with partial pivoting on top of runtime systems

Alycia Lisito, Mathieu Faverge, Matthieu Kuhn, Florent Pruvost, Pierre Ramet

► To cite this version:

Alycia Lisito, Mathieu Faverge, Matthieu Kuhn, Florent Pruvost, Pierre Ramet. Batching the tasks of the LU factorization with partial pivoting on top of runtime systems. COMPAS 2025 - Conférence francophone d'informatique en Parallélisme, Architecture et Système, Jun 2025, Bordeaux, France. hal-05148627

HAL Id: hal-05148627

https://inria.hal.science/hal-05148627v1

Submitted on 7 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Batching the tasks of the LU factorization with partial pivoting on top of runtime systems

A. Lisito, M. Faverge, M. Kuhn, F. Pruvost, P. Ramet

Compas 2025

Eviden, Centre Inria de l'université de Bordeaux
# The LU factorization with partial pivoting

## Where is it used?

* Numerical simulation

* Maxwell equations in the frequency domain via the Boundary Element Method

* Evaluate supercomputers

* The TOP500 based on the HPL Benchmark performance (solves $Ax = b$ with $A = PLU$)

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>
# LU factorization with Partial Pivoting (GETRF)

## Problems

* Few implementations, most are private and implement HPL not just LU factorization with partial pivoting

* Supercomputers have thousands of nodes, million cores and are heterogeneous
  → need to be able to exploit efficiently all the resources

* Many constructors (Intel, Nvidia, AMD, ...) = many architectures
  → need to be portable
# LU factorization with Partial Pivoting (GETRF)

## Problems

* Few implementations, most are private and implement HPL not just LU factorization with partial pivoting

* Supercomputers have thousands of nodes, million cores and are heterogeneous
  → need to be able to exploit efficiently all the resources

* Many constructors (Intel, Nvidia, AMD, ...) = many architectures
  → need to be portable

## Our goal:

Implement an efficient scalable and portable (and heterogeneous) task based LU factorization with partial pivoting on top of runtime systems
# LU factorization with Partial Pivoting (GETRF)

## Problems

* Few implementations, most are private and implement HPL not just LU factorization with partial pivoting

* Supercomputers have thousands of nodes, million cores and are heterogeneous
  → need to be able to exploit efficiently all the resources

* Many constructors (Intel, Nvidia, AMD, ...) = many architectures
  → need to be portable

## Our goal:

Implement an efficient scalable and portable (and heterogeneous) task based LU factorization with partial pivoting on top of runtime systems

## STARPU and CHAMELEON

* Parallel task based runtime system

* Task based parallel dense linear algebra library

* Tested and validated on large heterogeneous scale

* Efficient on all types of architecture
# Task based algorithm

## How does it work ?

* The matrix is split into blocks to reduce the size of the problem

* The algorithms are adapted

<figure><img src="image_4.png" /></figure>
# Task based algorithm

## How does it work ?

* The matrix is split into blocks to reduce the size of the problem

* The algorithms are adapted

* Each operation on a block corresponds to one task

* Dependencies between the tasks (block in read and / or write mode)

<figure><img src="image_5.png" /><figcaption>LU factorisation without partial pivoting</figcaption></figure>
# The LU factorization algorithm

## The panel operations
No piv

<figure><img src="image_6.png" /></figure>

Without partial pivoting

<figure><img src="image_7.png" /></figure>

Not numerically stable

With partial pivoting

<figure><img src="image_8.png" /></figure>

Numerically stable
# The LU factorization algorithm

## The panel operations
No piv

<figure><img src="image_9.png" /></figure>

Without partial pivoting

* Not numerically stable

With partial pivoting

* Numerically stable

* High number of tasks → can overflow the runtime
# The LU factorization algorithm

## The panel operations
No piv

<figure><img src="image_10.png" /></figure>

Without partial pivoting

With partial pivoting

Not numerically stable

Numerically stable

High number of tasks → can overflow the runtime

Very small tasks → more than 80% of the time in the runtime overhead
# The LU factorization algorithm

## The panel operations
No piv

<figure><img src="image_11.png" /></figure>

Partial piv

Without partial pivoting

* Not numerically stable

With partial pivoting

* Numerically stable

* High number of tasks → can overflow the runtime

* Very small tasks → more than 80% of the time in the runtime overhead

* Low granularity tasks → update operation with Level 1 BLAS and Level 2 BLAS

* Many reductions → lots of synchronisation in the critical path
# The LU factorization algorithm

## The panel operations
No piv

<figure><img src="image_12.png" /></figure>

Partial piv

Without partial pivoting

With partial pivoting

* Not numerically stable

* Numerically stable

* High number of tasks → can overflow the runtime

* Very small tasks → more than 80% of the time in the runtime overhead

* Low granularity tasks → update operation with Level 1 BLAS and Level 2 BLAS

* Many reductions → lots of synchronisation in the critical path
No batch / batch = 1

<figure><img src="image_13.png" /></figure>

12 small tasks

80% of the time in the
runtime overhead

batch = 3

<figure><img src="image_14.png" /></figure>

4 tasks 3 times bigger

less runtime overhead

batch = 5

<figure><img src="image_15.png" /></figure>

3 tasks 4 times bigger

almost no runtime overhead
# Batching the tasks
## Distributed memory case

<figure><img src="image_16.png" /><figcaption>Blocks distributed on 0 and 1</figcaption></figure>

2 blocks distributed on 2 processes

<figure><img src="image_17.png" /><figcaption>Batch 3 on 0</figcaption></figure>

2 tasks on process 0

<figure><img src="image_18.png" /><figcaption>Batch 3 on 1</figcaption></figure>

2 tasks on process 1
# Batching the tasks

## Adaptative batch size

<table><caption>Batch 12</caption><tr><td>h = 0</td></tr></table>

<table><caption>Batch 4</caption><tr><td>h = 1</td></tr></table>

<table><caption>Batch 1</caption><tr><td>h = 2</td></tr></table>

<table><caption>Batch 4</caption><tr><td>h = 3</td></tr></table>

<table><caption>Batch 2</caption><tr><td>h = 4</td></tr></table>

<table><caption>Batch 4</caption><tr><td>h = 5</td></tr></table>

<table><caption>Batch 6</caption><tr><td>h = 6</td></tr></table>

<figure><img src="image_19.png" /></figure>

*Computes the size of the batch at each column $h$ iteration

*The minimum of flops per task $flops_{min}$

*The number of blocks in the factorisation $nb_{left}$

*The number of flops of the factorisation $flops$

*The maximum size of batch possible $b_{max} = min(MAX, nb_{left})$

$$batch_{size} = \min\left( \left[ \frac{nb_{left}}{\min\left(\max\left(\frac{flops_{min}}{flops}, 1\right), b_{max}\right)} \right], b_{max} \right)$$
# Blocking and batching

Matrix size 115200 × 115200 with `blocksize = 576`

<table><thead><tr><th></th><th>batch 1</th><th>batch 12</th><th>batch adaptive</th></tr></thead><tbody><tr><td>Tasks nbr</td><td>11 601 100</td><td>1 023 536</td><td>461 996</td></tr><tr><td>flops/task mean</td><td>330 003</td><td>3 740 363</td><td>8 286 644</td></tr><tr><td>flops/task median</td><td>19 008</td><td>214 272</td><td>1 339 642</td></tr></tbody></table>

<figure><img src="image_20.png" /></figure>
# Blocking and batching

## AMD Genoa - 24 cores / Intel Cascade Lake - 18 cores

<figure><img src="image_21.png" /></figure>

* **GETRF_NOPIV**: reaches a peak at 1200 GFlops/s and 940 GFlops/s

* **DPLASMA**: same as batch 1

* batch 1: AMD 95% and Intel 87% of GETRF_NOPIV

* batch 12: AMD 97% and Intel 90% of GETRF_NOPIV

* batch adaptive: AMD 99% and Intel 97% of GETRF_NOPIV
# All Reduce

## 8 AMD Genoa - 24 cores / 8 Intel Cascade Lake - 18 cores - 2 MPI processes per node

<figure><img src="image_22.png" /></figure>

* **GETRF_NOPIV**: speedup of 15.5 on AMD and 14 on Intel out of 16

* **DPLASMA**: similar to batch 1

* **batch 12**: AMD 96% and Intel 97% of GETRF_NOPIV

* **batch adaptative**: AMD 97% and Intel 99% of GETRF_NOPIV

* **batch adaptative**: speedup of 15 on AMD and 14 on Intel out of 16
# Conclusion

## Contributions

Scalable and portable adaptive batching mechanism

## Future work

* Batch at the runtime level

* Manage batching with recursive tasks of STARPU

* Manage batching in heterogeneous context