# Vector operations, tiled operations, distributed execution, task graphs, ... What next ?

Samuel Thibault

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

## To cite this version:

Samuel Thibault. Vector operations, tiled operations, distributed execution, task graphs, ... What next?. JLESC 15 - 15th Joint Laboratory for Extreme Scale Computing Workshop, Mar 2023, Talence, France. hal-04115280

HAL Id: hal-04115280

https://inria.hal.science/hal-04115280

Submitted on 2 Jun 2023

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

INVENTEURS DU MONDE NUMÉRIQUE

Vector operations, tiled operations,
distributed execution, task graphs, ...

What next ?

Samuel Thibault, University of Bordeaux
Inria STORM Team
# High-Performance Computing

* Frontier supercomputer

* #1 on top500.org LINPACK benchmark

* 1.102 EFlop/s

* 9472 nodes

* 1 AMD Epyc CPU

* 4 AMD Instinct 250X GPUs

* 4TB flash memory

* Infinity Fabric interconnect

* Slingshot 100GB/s network

* 21.1 MW

* Also #1 Green 500

<figure><img src="image_4.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

<figure><img src="image_5.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

<figure><img src="image_6.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

* MPI+threads+GPU

<figure><img src="image_7.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

* MPI+threads+GPU

* Data transfers

<figure><img src="image_8.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

* MPI+threads+GPU

* Data transfers

<figure><img src="image_9.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

* MPI+threads+GPU

* Data transfers

* Disk storage

<figure><img src="image_10.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

* MPI+threads+GPU

* Data transfers

* Disk storage

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

<figure><img src="image_12.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

* MPI+threads+GPU

* Data transfers

* Disk storage

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

<figure><img src="image_14.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

* MPI+threads+GPU

* Data transfers

* Disk storage

## Manage it all by hand?!

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

<figure><img src="image_16.png" /></figure>
# High-Performance Computing

## Classical parallel programming

* threads

* MPI+threads

* MPI+threads+GPU

* Data transfers

* Disk storage

## Manage it all by hand?!

## Need high-level abstractions

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

<figure><img src="image_18.png" /></figure>
Cholesky (A = L.L^T)

<figure><img src="image_19.png" /></figure>
Cholesky (A = L.L^T)

■

☐☐

☐☐☐

☐☐☐☐

☐☐☐☐☐

☐☐☐☐☐☐

☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐☐☐☐☐☐☐

☐☐☐☐☐☐☐☐☐☐☐☐☐☐☐
Cholesky (A = L.L^T)

<figure><img src="image_20.png" /></figure>
Cholesky (A = L.L^T)

<figure><img src="image_21.png" /></figure>
Cholesky (A = L.L^T)

<figure><img src="image_22.png" /></figure>
Cholesky (A = L.L^T)

<figure><img src="image_23.png" /></figure>
Cholesky (A = L.L^T)

<figure><img src="image_24.png" /></figure>
# Cholesky, LINPACK

## Vector computers (end ‘70s, ‘80s)

<figure><img src="image_25.png" /></figure>
# Cholesky, LINPACK

## Vector computers (end ‘70s, ‘80s)

<figure><img src="image_26.png" /></figure>
# Cholesky, LINPACK

## Vector computers (end ‘70s, ‘80s)

<figure><img src="image_27.png" /></figure>
# Cholesky, LINPACK

## Vector computers (end ‘70s, ‘80s)

<figure><img src="image_28.png" /></figure>
# Cholesky, LAPACK

Computers with cache (early ‘90s-today), blocked operations : BLAS

<figure><img src="image_29.png" /></figure>
# Cholesky, LAPACK

Computers with cache (early ‘90s-today), blocked operations : BLAS

<figure><img src="image_30.png" /></figure>
# Cholesky, LAPACK

Computers with cache (early ‘90s-today), blocked operations : BLAS

<figure><img src="image_31.png" /></figure>
# Cholesky, LAPACK

Computers with cache (early ‘90s-today), blocked operations : BLAS

<figure><img src="image_32.png" /></figure>
# Cholesky, ScaLAPACK

## Distributed Computers (late ‘90s-today), 2D-block-cyclic distribution

<figure><img src="image_33.png" /></figure>
# Cholesky, ScaLAPACK

## Distributed Computers (late ‘90s-today), 2D-block-cyclic distribution

<figure><img src="image_34.png" /></figure>
# Cholesky, ScaLAPACK

## Distributed Computers (late ‘90s-today), 2D-block-cyclic distribution

<figure><img src="image_35.png" /></figure>
# Cholesky, ScaLAPACK

## Distributed Computers (late ‘90s-today), 2D-block-cyclic distribution

<figure><img src="image_36.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today)

<figure><img src="image_37.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today)

<figure><img src="image_38.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today)

<figure><img src="image_39.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today)

<figure><img src="image_40.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today)

<figure><img src="image_41.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today)

<figure><img src="image_42.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today)

<figure><img src="image_43.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today)

<figure><img src="image_44.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today), priorities

<figure><img src="image_45.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today), priorities

<figure><img src="image_46.png" /></figure>
# Cholesky, PLASMA

## Task graph (~'08-today), priorities

<figure><img src="image_47.png" /></figure>
# Task graphs in HPC

## Runtime systems

* OmpSs, PARSEC, StarPU, SuperGlue/DuctTeip, XKaapi...

## Standards

* OpenMP4.0 introduced task dependencies

## Applications

* Chameleon, DPLASMA, SLATE for dense linear algebra

* qr_mumps, PaStiX for sparse linear algebra

* ScaIFMM for FMM

* ...
# Task-based support

* Task/data scheduling

* Load balancing

* Data prefetching

* Pipelining

* GPU memory limitation management

* Distributed execution through MPI

* Out-of-core: optimized swapping to disk

* High-level performance analysis

* Performance bounds

* Debugging sequential execution

* Reproducible performance simulation

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

<figure><img src="image_49.png" /></figure>
How big should a task be?

* Small enough to get parallelism to **feed** all processing units

* Large enough to **efficiently** use the processing units
How big should a task be?

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

From PARSEC : « Hierarchical DAG Scheduling for Hybrid Distributed Systems », Wu, Bouteiller, Bosilca, Faverge, Dongarra
# How big should a task be?

## GPUs

* Efficient only with large tile sizes

## CPUs

* Need many tasks

→ **Hybrid** task size

More generally, **hierarchical** task graphs

* Seen in CEA, OmpSs, PaRSEC, StarPU
# Outline

* How big should a task be?

* Hierarchical task graphs

* Opportunities

<figure><img src="image_51.png" /></figure>
How big should a task be?

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

<figure><img src="image_53.png" /></figure>
# How big should a task be?

* Lower bound due to runtime overhead

* Proposed by Martin Tillenius for DuctTeip (U. Uppsala)

<figure><img src="image_54.png" /></figure>
How big should a task be?

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

From PARSEC : « Hierarchical DAG Scheduling for Hybrid Distributed Systems », Wu, Bouteiller, Bosilca, Faverge, Dongarra
# How big should a task be?

## GPUs

* Have **thousands** for cores to feed

* Newer generations require yet larger sizes

* Can run several kernels at the same time

* Still limited
How big should a task be?

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

From PARSEC : « Hierarchical DAG Scheduling for Hybrid Distributed Systems », Wu, Bouteiller, Bosilca, Faverge, Dongarra
# How big should a task be?

## CPUs

* Have many independent cores

→ Need many tasks

* Can use parallel implementations (e.g. from MKL)

* But better have subtasks to interleave them
# How big should a task be?

How size does not fit all

Gwenolé Lucas experimented with Chameleon

* Cholesky inversion

* 2 NVIDIA V100

* 2 Xeon Gold 6142

* Different matrix tile sizes : 2880 / 960 / 320
Hybrid tile sizes

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

Version: Tile sizes

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

Non-Hierarchical: 2880

Non-Hierarchical: 960

Non-Hierarchical: 320

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

Hierarchical: 2880 / 960

Hierarchical: 2880 / 960 / 320
# How big should a task be?

## Tuning the tile size?

* B = “big” tile size, for GPUs

* Large enough for GPUs

* Not too large for parallelism

* b = “small” tile size, for CPUs

* Large enough for CPUs

* Not too large for parallelism

With Parsec, Wu, Bouteiller, Bosilca, Faverge and Dongarra experimented tuning
How big should a task be?

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

From PARSEC : « Hierarchical DAG Scheduling for Hybrid Distributed Systems », Wu, Bouteiller, Bosilca, Faverge, Dongarra
How big should a task be?

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

From PARSEC : « Hierarchical DAG Scheduling for Hybrid Distributed Systems », Wu, Bouteiller, Bosilca, Faverge, Dongarra
How big should a task be?

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

From CEA : « A hierarchical fast direct solver for distributed memory machines with manycore nodes », Augonnet, Goudin, Kuhn, Lacoste, Namyst, Ramet
# How big should a task be?

Multiple answers

* Depends on available platform parallelism

* Depends on available application parallelism

* Depends on application phases

Automatically adapt?
Hierarchical task graphs

<figure><img src="image_63.png" /></figure>
# Hierarchical task graphs

Applications themselves are recursive

* e.g. h-matrices

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

From Airbus Group
# Hierarchical task graphs

Applications themselves are recursive

* e.g. h-matrices

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

From Airbus Group
# Hierarchical task graphs

Applications themselves are recursive

* e.g. h-matrices

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

From Airbus Group
# Hierarchical task graphs

Ideally, should just start with one huge task, and split

<figure><img src="image_67.png" /></figure>
# Hierarchical task graphs

Ideally, should just start with one huge task, and split

<figure><img src="image_68.png" /></figure>
# Hierarchical task graphs

Ideally, should just start with one huge task, and split

<figure><img src="image_69.png" /></figure>
# Hierarchical task graphs

Ideally, should just start with one huge task, and split

<figure><img src="image_70.png" /></figure>
# Hierarchical task graphs

Ideally, should just start with one huge task, and split

<figure><img src="image_71.png" /></figure>
# Hierarchical task graphs

Ideally, should just start with one huge task, and split

<figure><img src="image_72.png" /></figure>
Hierarchical task graphs

* In OpenMP?

```c
TRSM(A, B) {
    #pragma omp task depend(in:A, inout:B) wait
    {
```

```c
        #pragma omp task \
        depend(in:A[0][0], inout:B[0][0])
        TRSM(A[0][0], B[0][0])
```

```c
        #pragma omp task \
        depend(in:A[0][0], inout:B[1][0])
        TRSM(A[0][0], B[1][0])
```

```c
        #pragma omp task \
        depend(in:A[1][0], in:B[0][0], inout:B[0][1])
        GEMM(A[1][0], B[0][0], B[0][1])
```

...

<figure><img src="image_73.png" /></figure>
# Hierarchical task graphs

## Synchronization concerns

* Fork-join parallelism

* Hindered by synchronization induced by task graph

<figure><img src="image_74.png" /></figure>
Hierarchical task graphs

• OmpSs introduced weak dependencies

```
TRSM(A, B) {
    #pragma omp task depend(weakin:A, weakinout:B) \
        weakwait
{
```

```
#pragma omp task \
    depend(in:A[0][0], inout:B[0][0])
    TRSM(A[0][0], B[0][0])
```

```
#pragma omp task \
    depend(in:A[0][0], inout:B[1][0])
    TRSM(A[0][0], B[1][0])
```

```
#pragma omp task \
    depend(in:A[1][0], in:B[0][0], inout:B[0][1])
    GEMM(A[1][0], B[0][0], B[0][1])
```

...

<figure><img src="image_75.png" /></figure>
# Hierarchical task graphs

In StarPU

* Explicit data registration

* Recursive partitioning

<figure><img src="image_76.png" /></figure>
# Hierarchical task graphs

In StarPU

* Explicit data registration

* Recursive partitioning

<figure><img src="image_77.png" /></figure>
# Hierarchical task graphs

In StarPU

* Explicit data registration

* Recursive partitioning

<figure><img src="image_78.png" /></figure>
# Hierarchical task graphs

In StarPU

* Explicit data registration

* Recursive partitioning

<figure><img src="image_79.png" /></figure>
# Hierarchical task graphs

## In StarPU

* Explicit data registration

* Recursive partitioning

<figure><img src="image_80.png" /></figure>
# Hierarchical task graphs

## In StarPU

* Multi-level data coherency, among CPUs-GPUs-disk

* Enables seamless recursive tasks

* More details in Gwenolé Lucas' talk Thursday 14:40

<figure><img src="image_81.png" /></figure>
# Hierarchical task graphs

## Multi-level data coherency

* Synchronization pseudo-tasks

* Only when needed

* Result is exactly as appropriate

→ Just split at will!

<figure><img src="image_82.png" /></figure>
# Hierarchical task graphs

## Multi-level data coherency

* Synchronization pseudo-tasks

* Only when needed

* Result is exactly as appropriate

→ Just split at will!

<figure><img src="image_83.png" /></figure>
# Dividing tasks

No extra synchronization

→ Can consider task graph subdivision as a tree

POTRF

Recursion
# Dividing tasks

No extra synchronization

→ Can consider task graph subdivision as a tree

<figure><img src="image_84.png" /></figure>
# Dividing tasks

No extra synchronization

→ Can consider task graph subdivision as a tree

<figure><img src="image_85.png" /></figure>
# Dividing tasks

No extra synchronization

→ Can consider task graph subdivision as a tree

→ Decide at will where and when to stop recursing

<figure><img src="image_86.png" /></figure>
Opportunities

<figure><img src="image_87.png" /></figure>
# Opportunities

GPU / CPU efficiency management

* Stop recursing at desired tile size

* Care for latency of the task graph critical path

<figure><img src="image_88.png" /></figure>
# Opportunities

## Parallel submission

* Unroll the graph in parallel

* While one PU is computing the first task

<figure><img src="image_89.png" /></figure>
# Opportunities

## Delay unrolling

* Observe behavior before unrolling the rest accordingly

* Decorrelate submission and execution

<figure><img src="image_90.png" /></figure>
# Opportunities

## Delay unrolling

* Observe behavior before unrolling the rest accordingly

* Decorrelate submission and execution

<figure><img src="image_91.png" /></figure>
# Opportunities

## Scaling at large

* Master unrolls higher recursion levels, schedules result

* Slaves unroll the rest

* Master still contention point

<figure><img src="image_92.png" /></figure>
# Opportunities

## Scaling at large

* All nodes unroll higher recursion levels, determine task mapping

* Nodes unroll their own remaining recursion

* Network communication quite coarse

→ Spurious synchronizations

<figure><img src="image_93.png" /></figure>
# Opportunities

## Scaling at large

* All nodes unroll higher recursion levels, determine task mapping

* Nodes unroll their own remaining recursion

* Network communication at **finer grain**

* Fine-grain enough vs overhead?

<figure><img src="image_94.png" /></figure>
# Opportunities

## Scheduling at large

* High-level global task graph scheduling, e.g. mapping, critical path

* High-level local task graph scheduling, e.g. memory-based ordering

* $O(N^2)$ or even $O(N^3)$ not that costly

<figure><img src="image_95.png" /></figure>
Opportunities

- Computation efficiency

- Scaling at large

- Scheduling at large

NumPEx PEPR project
# NumPEx project

## Building a national ecosystem for the future exaflops machine hosted in France

* Facilitate conception, deployment, and monitoring of composite applications at large scale

* Efficiently exploit a heterogeneous architecture with many accelerators

* Control the energy envelope

80 teams in France

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

● Maths/computation/data

★ Applications/demonstrators

▲ NumPEx contributors
# NumPEx project

## PC1-ExaMA

Methods/Algorithms
for the Exascale

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

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

## PC2-ExaSoft

HPC softwares/tools
for the Exascale

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

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

## PC5-ExaDIP

Application co-design
Integration and
productivity

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

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

## PC3-ExaDost

Data-oriented
softwares/tools
for the Exascale

## PC4-ExaAToW

Architectures/tools for
large-scale workflows

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

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

## A Software Forge

Integration and
productivity

<figure><img src="image_105.png" /></figure>
# NumPEx project

## PC2-ExaSoft

* Holistic approach

* Contribute to a sound, consistent software stack

* Most components should fit together!

* Bridge the gap between existing languages/software/tools

* Integrate state-of-the-art research results

* Demonstrate relevance on representative applications

* WP3 : Runtime Systems at Exascale

## Application

Simulation Core

Data Analytics, Visualization, AI

Numerical/
AI
Libraries

Decomposition,
mapping tools

IO, storage,
data

## Parallel Compilers

Runtime
Systems

Just-In-Time
compilers

Communication
Libraries

## Resource Arbitration

<figure><img src="image_106.png" /></figure>
# Conclusion

* Programming large systems requires abstraction

* Recursive applications are there

* Hierarchical task graphs seem an opportunity for

* Controlling task size

* Controlling task submission

* High-level task graph scheduling

<figure><img src="image_107.png" /></figure>
# The StarPU runtime system

## Development context

* History

* Started in 2008

- PhD Thesis of Cédric Augonnet

* StarPU main core ≈ 70k lines of code

* Written in C

* Open Source

* Released under LGPL

* Sources freely available

- git repository and nightly tarballs

- See https://starpu.gitlabpages.inria.fr/

* Open to external contributors

* [HPPC'08]

* [Europar'09] – [CCPE'11],... >1500 citations
# Features

* C, OpenMP, OpenCL APIs

* CPUs, GPUs, Phi

* Advanced task mapping & scheduling

* Optimized data transfers

* Cluster Support through MPI

* Out-Of-Core support

* Simulation support

* Performance analysis tools
# The StarPU runtime system

## Success stories

Task-based programming actually makes things easier!

* QR-Mumps (sparse linear algebra)

* Non-task version: only 1D decomposition

* Task version: 2D decomposition, flurry of parallelism

- With seamless memory control

* H-Matrices (compressed linear algebra, AirBus)

* Out-of-core support

- Could run cases unachievable before

- e.g. 1600 GB matrix with 256 GB memory

* Shipped to AirBus customers

* Implemented CFD, FMM, CG, stencils, ...

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

<figure><img src="image_109.png" /></figure>
# The StarPU runtime system

## Supported platforms

* Supported architectures

* Multicore CPUs (x86, PPC, ...)

* NVIDIA GPUs

* OpenCL devices (eg. AMD cards)

* HIP

* FPGA (ongoing)

* Old Intel Xeon Phi (MIC), SCC, Kalray MPPA, Cell (decommissioned)

* Supported Operating Systems

* Linux

* Mac OS

* Windows
# Applications on top of StarPU

Using CPUs, GPUs, distributed, out of core, ...

* Dense linear algebra

* Cholesky, QR, LU, ... : Chameleon (based on Plasma/Magma)

* Sparse linear algebra

* QR_MUMPS

* PaStiX

* Compressed linear algebra

* BLR, h-matrices

* Fast Multipole Method

* ScalFMM

* Conjugate Gradient

* Other programming models : Data flow, skeletons

* SignalPU, SkePU

* ...