M Sato

H Murai

Keywords: Calcul Haute Performance, Modèle de Programmation, Tâche, MPI, OpenMP High-Performance Computing, Programming Model, Task, MPI, OpenMP

La simulation numérique est un outil puissant pour la recherche scientifique et l'industrie, il est considéré comme le troisième pilier de la science par les chercheurs. Le Calcul Haute-Performance (HPC) est la science visant à améliorer les performances des ordinateurs pour répondre aux besoins de la simulation numérique. Son objet d'étude est le supercalculateur : un ensemble de noeuds de calcul interconnectés en réseau, chacun composé de processeurs contribuant en parallèle à la simulation. Au fil des décennies, les superordinateurs ont connu une évolution rapide, avec une augmentation et une diversification des unités de calcul au sein des noeuds. En conséquence, la programmation de codes de simulation numérique portables et performants entre les différentes générations de machines devient un défi.

Pour y répondre, les vendeurs de matériel et les chercheurs conçoivent des modèles de programmation standards tels que « The Message Passing Interface (MPI) » ou « Open Multi-Processing (OpenMP) ». Ces modèles servent de pont entre l'expression d'un calcul scientifique par un code informatique et son exploitation par le matériel sous-jacent. La diversification du materiel pousse les programmeurs à utiliser conjointement (ou « composer ») de multiples modèles de programmation asynchrones afin d'utiliser toutes les unités de calcul du supercalculateur de façon concurrente. La composition de modèles asynchrones présente des difficultés pour le profilage des applications, leur programmation et leur niveau de performances.

Dans cette thèse, nous étudions la composition par tâche des modèles de programmation MPI et OpenMP, et apportons les contributions suivantes en réponse à ces difficultés. Tout d'abord, nous présentons un modèle de performance unifié par tâche pour l'hybridation MPI+OpenMP, en définissant des métriques et en implémentant un profileur pour analyser un programme après son exécution. Ensuite, nous concevons un ordonnanceur unifiant la progression et le recouvrement d'opérations asynchrones et hétérogènes, telles que les transferts de mémoire par le réseau, les tâches de calcul, ou les transferts mémoire/calcul depuis/vers un accélérateur. Enfin, nous évaluons et améliorons l'hybridation par tâche sur des proxy-applications modélisant des simulations scientifiques ; en caractérisant et atténuant des goulots d'étranglement aux performances, tels que l'ordonnancement des communications, la limitation du nombre de tâches en vol, ou la découverte du graphe des dépendances.

Motivations

Numerical simulation have become a powerful tool for scientific research and the industry. The use cases are wide: military defense, weather forecasting, chemistry, or vehicle security. In the scientific field, Numerical Simulation is considered the third pillar of science, complementing Theory and Experiment. It is, in particular, necessary for solving non-linear, multi-physics, and large-scale problems [START_REF] Boekholt | Multi-physics simulations in astronomy[END_REF]. In the industry, it improves the validation of systems; for instance, simulating thousands of car accidents by varying initial conditions helps to characterize material deformation. Their accuracy and speed are sometimes critical: in Japan, severe weather can occur in less than 20 minutes, which motivated the development of simulations to explore weather forecasts on a 100-m grid spacing over 30 minutes to evacuate citizens on time [START_REF] Miyoshi | big data assimilation" revolutionizing severe weather prediction[END_REF]. High Performance Computing (HPC) is the science of improving the computational performances to meet the accuracy and speed challenges of numerical simulations. The high-performance computing object of study is supercomputer: a set of interconnected machines (compute nodes) contributing in parallel to progressing a numerical application, such as simulations. The performance of supercomputers are measured by the number of numerical operations they perform per second (FLOPs/s). The TOP 500 list ranks worldwide supercomputers by their computational performances for resolving dense linear systems. It also provides hardware details of each ranked supercomputer. Over the last 20 years, the trend shows the evolution of compute nodes from single-core processors to multi-heterogeneous cores. In 2002, EARTH-SIMULATOR 1 supercomputer was ranked first using 5,120 single-homogeneous core compute nodes for a total of 40 TFlop/s. In 2010, Tianhe-1 2 was the first supercomputer with heterogenous cores (CPUs and GPUs) on the same compute nodes to perform above 1 PFlop/s. As of 2023 writing this thesis, Frontier is now the most powerful supercomputer with compute nodes embedding 64-core processors and 4 GPUs 3 for more than 1 EFlop/s in total.

A numerical application efficiency is its ability to fully exploit the underlying supercomputer to progress the computation. It can be quantified by comparing real execution performances over theoretical system performances, or peak performances provided by the TOP 500. The 1 https://www.top500.org/system/167148/ 2 https://www.top500.org/system/176929/ 3 https://www.top500.org/system/180047/ 1.1. MOTIVATIONS fast hardware architecture evolution faced over the last 20 years degraded the efficiency of existing simulation code that was originally conceived for single-core architectures: the problem of performance portability consists in keeping simulations efficient over past, new and future supercomputers architecture. In order to improve the performance portability of numerical simulation, programmers conceive simulation codes using programming models. It consists of an Application Programming Interface (API) providing the code building blocks and an Execution Model (EM) specifying how the executing environment must interpret the API. Therefore, Programming models serve as bridges between a calculation expression and its exploitation by the underlying architecture.

To ensure coherent bridging, programming models such as the Message Passing Interface (MPI) 4 or Open Multi-Processing (OpenMP) 5 are conceived by a large community of hardware vendors, research laboratories and programmers. Modifications are discussed, voted and eventually adopted in standard specifications. Such a collaborative approach to conceiving programming models provides guarantees to numerical simulation programmers on their code performance portability.

The diversity of processing units now imposes on programmers to use multiple programming models jointly, for instance:

• MPI requests to send messages by the interconnection network through the network interface controllers (NICs),

• pthreads or OpenMP to execute code on all available central processing units (CPUs),

• OpenMP for vectorized instructions (AVX, SVE...),

• CUDA/HIP/OpenCL/OpenMP to offload computation to accelerators (GPUs, FPGA),

• MPI-IO/Lustre to store data onto permanent storage (hard drive, magnetic tape).

Following historical hardware evolution, numerical simulation codes had been originally distributed on compute nodes using MPI only; and then parallelized with OpenMP to benefit intra-node parallelism introduced 20 years ago. Usually, computational loops are parallelized using OpenMP (CPUs/GPUs) followed by a local synchronization on the compute-node to wait for computation completion; and only then network communications (NICs) are initiated with MPI, followed again by synchronizations before pursuing computational loops 6 . Such distinct use of the two programming models simulation codes alternatively underload and overload each processing unit with bulk workloads On the other hand, all these processing units are capable of asynchronous execution: some iterations from computational loops could execute in parallel with independant network communications (NICs). Using each programming models distinctly, codes are not expressing such asynchrony leading to an inefficient use of the hardware.

The standard community primarily focused on using MPI with OpenMP before the introduction of dependent tasking in 2013. Dependent task-based programming is a promising approach to using multiple asynchronous programming models more tightly, which we refer to as programming model composition. It divides applications into tasks (as a sequence of instructions) and precedence constraints providing partial order of execution. Task-based execution models are rather simple: (1) a task can only execute once all its precedence constraints are met, and (2) only one task at a time can run per processing unit. This simplicity allows the representation of other programming models building blocks (MPI requests, CUDA streams) as a set of dependent tasks to be processed seamlessly by a shared execution model: the problem of performance portability is then partly differed to a question of task scheduling.

Problem Statement

Recent advances in the OpenMP dependent task model open new doors to compose programming models. Simulation codes can express a higher potential of asynchrony through smaller workload units (tasks). This approach allows a more performant exploitation of the hardware, staggering tasks on each processing unit over time instead of alternatively overwhelming them with bulk workloads as done historically. Yet, since 2013, few to no applications have migrated towards task-based programming due to three tied difficulties:

• Profiling. Distributed task-based applications execution is asynchronous and out-of-order, making it difficult to understand their behavior. Hybrid profiling and visualization tools (Gantt charts, graphs) are needed [START_REF] Vinicius | A Visual Performance Analysis Framework for Task-based Parallel Applications running on Hybrid Clusters[END_REF], but none supports standard MPI+(task-based OpenMP) composition: performance issues can hardly be understood, as reported in [START_REF] Meadows | Openmp tasking and mpi in a lattice qcd benchmark[END_REF].

• Programming. When modifying existing program, E. Aubanel [START_REF] Aubanel | Parallel program comprehension[END_REF] mentioned that "the data flow is not as obvious as the control flow, and the function of the program is the hardest to discover ". In our case, porting an existing program to use dependent tasks requires precise understanding of its data flow, so programmers express how communication and computation tasks are interleaved using tasks and dependencies. In particular, sideeffects (or 'interoperability issues') appear when mixing standard programming models implementations in production environments (GCC, LLVM, Open MPI): running MPI communications into OpenMP tasks most likely leads to deadlocks [START_REF] Sala | Integrating blocking and non-blocking mpi primitives with task-based programming models[END_REF]. Hence, the need for programming interfaces to ease programs porting and their maintenance in the future.

• Performances. Task-based application performances are a lot about finding a compromise between the parallelism expression (tasks granularity, dependencies) and induced runtime management costs [START_REF] Gautier | On the Impact of OpenMP Task Granularity: 14th International Workshop on OpenMP[END_REF]. They are also about task scheduling: misuse of the memory hierarchy [START_REF] Blelloch | Effectively sharing a cache among threads[END_REF][START_REF] Olivier | Characterizing and mitigating work time inflation in task parallel programs[END_REF] or the network [START_REF] Sinnen | Communication contention in task scheduling. Parallel and Distributed Systems[END_REF] can significantly degrade performances.

Objectives and Contributions

In this thesis, we investigate and propose solutions to the three difficulties of migrating applications to a task-based programming model composition to improve their performance portability. We use the Open Multi-Processing (OpenMP) tasking model and the Message Passing Interface (MPI), as their collaborative way of working will most likely make them survive in time. Most developments had been made as part of the existing Multi-Processor Computing (MPC) [START_REF] Perache | Mpc: A unified parallel runtime for clusters of numa machines[END_REF] OpenMP tasking runtime. We provide the following contributions to each difficulty:

• On profiling, we propose a unified task-based performance modeling of MPI+OpenMP applications. We define performance metrics implemented as part of a run-time profiler and post-mortem analysis. This toolchain allows precise assessment on the performances of an instance of execution. Ultimately, it leads us to show impacts on the interleaving between the OpenMP task dependency graph discovery and its parallel execution over performances.

• On programming, and to respond the lack of applications using task-based composition of MPI and OpenMP, we ported a benchmark (HPCG) and a proxy-applications (LULESH 7 ) to the task-based composition understudy. We provide porting experience feedback and a few extension proposals to OpenMP aiming to ease the porting of existing production simulation codes. We always consider our proposals by reflecting on their impacts on user simulation codes, runtimes and compilers. In particular, we propose the removal of some OpenMP restrictions which currently harden irregular dependencies expression; an extension for heterogeneous memory address space dependency expression; new mechanisms for tasks suspension/resumption; and an original OpenMP tasks priority management to favor the early-bird posting of tasks performing MPI communications.

• On performances, our developments in MPC have lead to a cutting-edge and open-source OpenMP tasking runtime implementing most recent standard interfaces 8 . Our cooperative task scheduling design shows improved performances on fine-grain tasks offloading to GPU over existing solutions. We also introduce and implement an original tasking extension that drastically reduces fine-grain tasking overheads: task persistence.

A significant contribution also lies in evaluations conducted as part of this thesis: it provides an idea on the level of performance to expect after porting existing simulation code to the task-based composition understudy under current MPI and OpenMP technology readiness. We organize the manuscript as follows. Part I presents the context of this thesis: Chapter 2 discusses general aspects of numerical simulations (what is / how to program a supercomputer); and Chapter 3 focuses on standard programming models and their hybridization. Part II presents our contributions we organized in three chapters: Chapter 4 presents the unified modeling and profiling tools we built; Chapter 5 presents standard and runtime extensions to improve scheduling capabilities; and Chapter 6 presents the porting of two mainstream HPC benchmarks (HPCCG, LULESH) with standard extensions to ease the porting of future irregular applications, and investigate issues related to the task dependency graph discovery. Finally, Part III concludes and provides research perspectives. In order to execute on supercomputers, numerical simulations rely on a vast stack built upon years of research and industrial uses. The iceberg Fig. 2.1 is an overview of the current HPC ecosystem, which we propose to divide into four layers. On the lowest layer, the Hardware represents electronic components provided by vendors, historically built through co-design to meet supercomputer application needs. Above, the Operating System corresponds to standard interfaces and the Linux kernel, which equip every supercomputer node to manage the Hardware and provide a primary bridging interface to programmers. Finally, the Software layer, built on top of the operating system, represents programming languages, compilers, libraries, tools, and programming models.

Chapter 2

Numerical Simulations on Supercomputers

Supercomputers Architecture

At the lowest layer of the HPC stack, hardware are the electronic components provided by vendors. We describe modern HPC hardware architecture with a zoom on the CEA-HF supercomputer compute nodes, which was recently in 2021-2022 and experimented as part of this thesis. The CEA-HF supercomputer 1 was installed between 2021-2022 as the successor of TERA-1000 in 2016-2017, ranked 22 on the top500 in June 2023. Fig. 2.2 provides an overview of its architecture 2 . The supercomputer is made of 200 Bull XH2000 42U Cabinet (1U ≃ 4.5cm). Each cabinet embeds a power management controller, a hydraulic cooler system; network switches for the interconnection network, and 32 standardized entries for compute blades. 1U compute blade installed in each cabinet is made of 2 AMD EPYC 7H12 General Purpose Processor (GPP) and 1 BullSequana eXascale Interconnect (BXI V2) network interface controller. For comparison, the exaflopian Frontier machine uses the same GPPs on AMD blades accelerated with 4 Instinct 250X GPUs, assembled into Cray cabinet/interconnection.

Zoom on Modern Compute Blades

Supercomputers' compute blades are the building blocks of a supercomputer, made of one or multiple compute nodes interconnected within a network. Each blade may contain multiple processors connected to a shared memory. [START_REF] Carribault | Compiler/Runtime Cooperation for High-Performance Multi-Paradigm Parallelism -Habilitation à Diriger des Recherches[END_REF] for TERA-1000

General Purpose Processor (GPP)

A General Purpose Processor (GPP) is the processing unit equipping every personal computers and supercomputers node. It is designed to perform any numerical operations (additions, multiplications, conditions testing, reading/writing to the memory, sending a signal on a bus...). It is built with multiple cores hierarchically connected to a shared memory.

Hierarchical Memory Fig. 2.3 shows the memory hierarchy of most GPPs (adapted from the lecture [START_REF] Shun | 6.172 performance engineering of software systems -caching and cache-efficient algorithms[END_REF]). Taking the AMD EPYC 7H12 64-core Processor as an example, each core has its own register set and L1/L2 caches; L3 caches are shared between 4 cores; NUMA domain is made of 16 cores that can access their local DRAM uniformly; and the processor is made of 4 NUMA domains. Each level of the hierarchy does not come with the same size and access latency: the table on the right depicts the core-to-core compare-and-swap latency benchmark 3on AMD EPYC 7H12 GPP (entire results in annex Fig. 8.1). As mentioned in [START_REF] Berg | Cache prefetching[END_REF], we observe an "inverse relationship between the size and access time of computer memories" that is inherent of the hardware. An interactive history of the memory accesses latency over the past 20 years has been made by C. Scott and is available online 4 .

Cache and Prefetching When a core reads from or writes to the DRAM, it first checks if the data is already in a lower cache level. In such case, the processor reads or writes to the cache instead of the DRAM accelerating its memory accesses latency: this is a cache-hit. Otherwise, a block of memory from the DRAM is copied cache lines (of fixed size, typically 32, 64, or 128 bytes5 ): this is a cache-miss. Cache prefetching [START_REF] Berg | Cache prefetching[END_REF] consists in bringing memory from the DRAM to caches before it is required by anticipating memory access pattern. Such techniques reduce memory accesses latency by overlapping independent instructions with DRAM fetching into caches. Prefetching can be implemented in the hardware and by software (done mainly by compilers currently). A prefetching decision may be accurate or inaccurate depending if the prefetched memory will actually be accessed by cores or not. Several research works have been conducted on reducing inaccurate prefetching predictions, as they may pollute caches erasing useful cache lines previously fetched, but there is none universal to any architecture and applications [START_REF] Vanderwiel | Data prefetch mechanisms[END_REF].

Instructions Pipelining As soon as a GPP is booted, its cores start processing instructions until they are physically shut down. An instruction is an opcode and a set of operands. Opcode and operands are integers coding an operation to be performed by the architecture: the opcode defines which operation, and operands are its parameters. The classic RISC instruction processing is a five-stage: fetch > decode > execute > memory access > write-back 6 . Pipelining performances are measured as the number of Instructions performed Per Cycle (IPC): in an ideal single RISC pipeline, the IPC is 1 (with one write-back stage performed per cycle). In practice, the IPC of a RISC pipeline is lower than 1 due to hazard : situations where it is necessary to prevent the processing of an instruction stage to ensure correctness of the operation (Chapter 2 of [START_REF] David A Patterson | Computer architecture : a quantitative approach[END_REF]). For instance, a data missing into cache memory may lead to an hazard, and sometimes a stall blocking entirely the core pipeline until the data arrives.

Cores Modes In addition, each core of a GPP can run multiple modes. For instance, the x86 architecture provides 4 modes (0 is kernel, 3 is user ). In the kernel mode, cores can perform any instructions implemented by the architecture: it may read/write every memory byte or even shut down hardware components. In the user mode, cores can only perform a subset of instructions with limitations on their operands, as restricted operations could lead to irreversible damage to the machine.

Network Interface Controller (NIC)

A Network Interface Controller (NIC) is a hardware component with its own memory and processing units, typically connected to the GPP memory through a PCI bus. A compute blade can embed multiple NIC per GPP, or multiple GPP per NIC: in any case, there is to interconnect the compute blade of the supercomputer. This interconnection network allows any compute nodes to communicate memory to one another, and the NIC manages transfer protocols. In particular, NICs are implementing Remote Direct Memory Accesses (RDMA) protocols [START_REF] Woodall | High performance rdma protocols in hpc[END_REF], allowing concurrent accesses to the memory with GPP cores. RDMA enables zero-copy (to/from GPP/NIC) communications from pinned memory regions, reducing transfer latency. In addition, NICs now also embed processing units, partly removing the need for GPP clock cycle to progress communications.

Graphic Processing Unit (GPU)

A Graphics Processing Unit (GPU) is a specialized processing unit used in HPC for its energy efficiency on dense linear algebra. On the Green500 ranking, every supercomputer on the top 10 rankings uses GPUs, and performs with about 40 to 60 Gflops/watts. On the other hand, the Chinese supercomputer Tianhe-2A ranked 10 on the Top500 is performing at 3 GFlops/Watt with a pure-GPP architecture, which is one order of magnitude less energy-efficient than GPU machines. This energy efficiency made it famous in the HPC industry and ultimately led to the Frontier exaflopian machine under 20MW consumption: a power restriction set by the US Department of Energy (DoE) in 2009 when power projection using existing technology where estimating 300MW to reach exaflopian performances then [START_REF] Whitt | Frontier overview -olcf annual user meeting[END_REF].

Summary

In order to reach high performances on supercomputers, the diversity and complexity of hardware must be taken into account. Our contributions in Chapters 4,5,6 primarily focus on GPP-only compute nodes interconnected in network from their NICs, such as the CEA-HF supercomputer. Results in Section 6.2 illustrate how an improved use of the memory hierarchy and caches can reduce pipeline stalls and double computational performances. While it is not presented in this document, preliminary results on accelerating the CEA-HF architecture with GPUs had been published in [START_REF] Ferat | Enhancing mpi+openmp task based applications for heterogeneous architectures with gpu support[END_REF].

Executing and Programming on a Supercomputer

Climbing up the scientific simulation iceberg Fig. 2.1, the Operating System (OS) is the lowest software layer of a computer. It is responsible of managing presented hardware by providing simpler and portable interfaces for upper-layer application software such as OpenMP. The Portable Operating System Interface (POSIX) [START_REF] Neth | Posix base specifications issue 7[END_REF] specifies standard interfaces for operating systems.

The Portable Operating System Interface (POSIX)

The Open Group is a worldwide consortium of 892 members at the time of writing this thesis 7 including banks, IT companies (Fujitsu, Intel, Huawei...) or even governmental institutions (Canadian Department of Defense, research institutes...) 8 . Its mission is to provide open and vendor-neutral technology standards and certifications, and in particular, it provides the POSIX specifications defining operating system concepts used in every implementation to some extent (MS-Windows, GNU/Linux, Mac OS, NetBSD, ...). For instance, the 2017 specifications provide the following definitions referenced in this thesis:

Program "A prepared sequence of instructions to the system to accomplish a defined task "

Thread "A single flow of control within a process. Each thread has its own thread ID, scheduling priority and policy, errno value, floating point environment, thread-specific key/value bindings, and the required system resources to support a flow of control. [...] " Live Process "An address space with one or more threads executing within that address space, and the required system resources of those threads."

Address Space "The memory locations that can be referenced by a process or the threads of a process."

The GNU/Linux operating system mostly complies with the POSIX standard, and above definitions, and is equipping every compute node of every supercomputer ranked on the Top 500 in the November 2022 list 9 . Therefore we introduce its Linux kernel briefly.

Operating System Kernels: a Fast Zoom on Linux

When booting a computer, the operating system kernel is one of the first programs executed. It remains in a protected memory region until the computer shutdowns and is a critical piece of software in terms of security and performance. Security-wide, cores process the kernel instructions in the kernel mode, giving it entire access to the system resources. In addition, the kernel is responsible for impactful mechanisms such as interrupts, multi-process scheduling, or memory management that can have a significant impact on performances. As the Linux kernel [START_REF] Love | Linux Kernel Development: Linux Kernel Development _p3[END_REF][START_REF] Tanenbaum | Modern Operating Systems[END_REF] runs on every supercomputer ranked on the Top 500, we briefly present a few of its components that we reference later in this thesis.

Interrupts

Interrupts are a means of communication between hardware components and the kernel. This mechanism was originally designed to ensure responsiveness between hardware interactions (pressing a key) and the operating system (writing the letter on the terminal). Each interrupt has an identifier that maps to an handler through an Interrupt Descriptor Table (IDT). When an interrupt occurs, the CPU suspends its execution flow and switches to its associated handler program. In the Linux Kernel Development guide [START_REF] Love | Linux Kernel Development: Linux Kernel Development _p3[END_REF], interrupts are presented as an alternative with less impact on performance than periodical execution flow suspension and polling, as an interrupt suspension is attached to an actual hardware event.

However, in the context of data centers, G. Regnier et al. [START_REF] Regnier | Tcp onloading for data center servers[END_REF] evaluated the operating system footprint (system call, interrupts, memory copies) to represent 50% of TPC/IP communications processing. This leads the HPC community to heavily optimize this part of the software stack, particularly with the implementation of Direct Memory Accesses (DMA) to reduce kernel involvement in communications. Using the Linux DMA driver API 10 , interrupts and memory copy costs can be removed, as hardware components (NICs, GPUs...) can directly write into Scheduler dispatches task to run: schedule() calls context_switch().

Task sleeps on wait queue for a specific event.

Task is preempted by higher priority task.

Event occurs and task is woken up and placed back on the run queue. [START_REF] Love | Linux Kernel Development: Linux Kernel Development _p3[END_REF] the user-space process memory. In parallel and asynchronously of a DMA, cores eventually poll the memory and may notice the completion of a request asynchronously without interrupting execution. Note that DMA sometimes requires memory to be pinned (i.e., virtual memory mapping to physical memory is constant); but not always: for instance, Bull BXI NICs can translate virtual to physical addresses [START_REF] Derradji | The bxi interconnect architecture[END_REF].

System Calls

System calls are interfaces provided by the operating system, so user-space programs can interact with the kernel. As user-space programs cannot execute kernel code directly, Linux implements system calls as an interruption with parameters passed using registers (instruction int x80, and registers ebx, ecx, edx, esi, edi, and ebp on x86). The kernel implements a handler that fall-backs to the associated kernel-space implementation of the system call. Note that the cost of a system call is significantly higher than a traditional function call. In [START_REF] Soares | Flexsc: Flexible system call scheduling with exceptionless system calls[END_REF], authors conducted several experiments on Intel Nehalem (Core i7) to quantify costs on (1) switching processor mode (∼ 150 cycles), (2) memory pollution (caches) and (3) impacts on IPC. Their results show that a system call is at least an order of magnitude higher than a conventional x86 user-space function call.

Thread/Process Management and Scheduling

Linux provides interfaces for managing POSIX threads and processes. Internally, the kernel represents both threads and processes using the struct task_struct data structure sizing about 1.7KB on a 32-bit machine 11 . Fig. 2.4 depicts the five states of a Linux task_struct: it can whether be not-ready, ready, running, waiting or completed. Each instance of a struct task_struct is forked through the clone system call and may share attributes (e.g. virtual memory mapping, file descriptors...). They embed multiple execution contexts (i.e. a stack and registers copy): a kernel-mode execution contexts for executing kernel code and interruptions; and a user-space execution context for executing user code. In this thesis, Kernel-Level Threads (KLT) refers to Linux task_struct and User-Level Threads refers to user-level execution contexts.

Linux task_struct instances can be created by threading libraries implementations such as the GNU POSIX threads (pthreads) 12 ; a POSIX thread is created as such:

clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0); Scheduling-wise, since 2007, Linux schedules its task_struct on CPUs using the Completely Fair Scheduling (CFS) scheduler implementation. In shorts:

• Tasks are sorted by their virtual run-time; a metric that is built upon their run-time on physical cores (time spent in the running state).

• When returning from the kernel code to user-space (after the completion of a system call or an interrupt handler), the kernel picks the ready task with the least virtual run-time executes it.

In addition, the Linux kernel is configured on boot with a time period at which a timer interrupt is raised, preempting the execution of the current task. The timer interrupt handler is defined in the kernel/time/tick-common.c file 13 . It updates various timers, and in particular: the current task virtual runtime. Hence, before returning, and just like any other interrupt handler, the kernel may decide to switch tasks.

Summary

The GNU/Linux operating system is mostly compliant with POSIX, providing portable interfaces on every supercomputer listed on the top500. As the lowest software layer of the HPC application stack, the OS manages the hardware, making it a critical component for performance. The operating system overheads on interruptions, system calls, and periodic preemption guided our research towards user-level thread scheduling: threads with no existence for the Linux kernel, running in the user-mode of CPUs. Section 5.1 presents OpenMP tasking extensions to enhance its scheduling flexibility with user-level threads.

In the next sections, we climb-up the HPC application stack towards the "Application Software" layer. We first provide a brief history on HPC programming languages and presents existing technologies.

Programming Languages and Compilers

Programming is the action of creating a program, that is, writing down a sequence of instructions to perform a specific task. Early in the 1950s, programming consisted in writing a sequence of CPU instructions opcode and operands. This is depicted on Listing 2.1 using x86 GNU Assembly (that could be directly converted to opcode/operands machine code), whose task is to compute 4 × 5 and output the result. Such a programming approach presented major drawbacks: programs are difficult to conceive, maintain and understand, and they needed to be more portable across processor architectures. J. Backus [START_REF] Backus | The history of fortran i, ii and iii[END_REF] mentions that back then, low-level programming was not economically sustainable as programmer costs were "at least as great as the cost of the computer itself [...] [and] as computers got cheaper, this situation would get worse".

This lead to the development of the FORTRAN programming language and compiler by J. Backus team at IBM in 1954. The programmer write a program in a language (FORTRAN) agnostic of the processor architecture, and the compiler is responsible of converting it to an [START_REF] Rudi | An extreme-scale implicit solver for complex pdes: Highly heterogeneous flow in earth's mantle[END_REF][START_REF] Joubert | Attacking the opioid epidemic: Determining the epistatic and pleiotropic genetic architectures for chronic pain and opioid addiction[END_REF], or a mix of C/C++/Python [START_REF] Jia | Pushing the limit of molecular dynamics with ab initio accuracy to 100 million atoms with machine learning[END_REF][START_REF] Fedeli | Pushing the frontier in the design of laser-based electron accelerators with groundbreaking meshrefined particle-in-cell simulations on exascale-class supercomputers[END_REF] using C/C++ as low-level programming languages for computations kernel, and Python as a higher-level programming language to orchestrate computational kernels.

C/C++ The C programming language was initially conceived at the Bell Laboratories by D. Ritchie, who presents the language development history in [START_REF] Ritchie | The Development of the C Programming Language[END_REF]. The language was motivated to create the Unix operating system commands and kernel. It showed to be portable across hardware, which led to the development of compiler support on most existing architectures at the same time, and its use was extended from operating system to application development. Listing 2.3 illustrates our minimal code example using the C programming language. The C++ programming language was initially developed at Bells Laboratories by B. Stroustrup to create a successor to C providing additional facilities 15 . Since then, the language has shown stable evolution and support by compilers. B. Stroustrup is no longer part of the language committee but is still influential. He recently (2021) expressed in an interview 16 that in the future, C++ could evolve toward better integration of heterogeneous processing units programming (CPUs, FPGA, GPU), in particular using hardware CPU/GPU uniform address spaces to relieve the burden of data movement from the programmer, as the hardware would embed implicit support. The Gnu Compiler Collection (GCC [START_REF] Stallman | Using The Gnu Compiler Collection: A Gnu Manual For Gcc Version 4[END_REF]) and LLVM's Clang [START_REF] Lattner | Llvm and clang: Next generation compiler technology[END_REF] currently are the two dominating C and C++ compilers. GCC first release was in 1987, and LLVM in 2007, whose motivations were primarily to provide more flexibility (with Just-In-Time compilation, or cross-file optimization, for instance) and faster compilation than the production compiler of that time. Both GCC and Clang are Free and Open-Source Software (FOSS) supporting most of the latest C/C++ language features. They are respectively distributed under the GNU GPL license and the Apache License 2.0. The Apache license allows a close-source and commercial redistribution of LLVM. When selling a machine, vendors would typically sell a compiler (ICC for Intel, AOCC for AMD) that is a patched clone of Clang, finely tuning the compiler for the targeted hardware.

Python As opposed to Fortran/C/C++ implementations, the Python programming language main implementation (CPython17 ) relies on an interpreter. It means that on each execution, a Python program is converted (or interpreted) to machine-code while this conversion is only done once for all at compilation-time with Fortran/C/C++ programs. Moreover, the Python language does not support concurrent multi-threading due to shared responsibility between standard definition and runtime implementation 18 . Hence, at first sight, Python sounds like a poor candidate for HPC programming. However, the language is excessively simple (as shown on Listing 2.4) and modular: it can be extended with high-performant C/C++ libraries doing the critical scientific simulation (parallel) computation to be called by the Python interpreter through (sequential) interfaces. According to the TIOBE index 19 , the language's popularity kept increasing over the last 20 years, making it the most popular language in 2022.

HPC-oriented Programming Languages

Many more programming languages have been created specifically for the development of scientific simulations but are, in practice, less represented than Fortran/C/C++/Python.

High Performance Fortran (HPF)

The High-Performance Fortran (HPF) [START_REF] Loveman | High performance fortran[END_REF] was proposed in 1992 as an extension to Fortran for distributed machine programming, but failed to become popular mainly due to immature technology and a lack of efficient implementations [START_REF] Kennedy | The rise and fall of high performance fortran: An historical object lesson[END_REF]. Nevertheless, HPF failure led to important research on Partitioned Global Address Space (PGAS) programming, with for instance: X11, Chapel, Fortress, SHMEM, Dash, XCalableMP (XMP). PGASs provide a global memory address space logically partitioned between processing units. Even though the memory is physically distributed, it can be accessed by the program as if it was shared. The execution parallelization and data transfers are managed implicitly from the partitioning.

Julia is a recent programming language released in 2012. V. Churavy et al. [START_REF] Churavy | Bridging hpc communities through the julia programming language[END_REF] describe the language as a bridging alternative between two communities: the scientific simulation programmers using low-level programming languages (C/C++/Fortran) and the data analysts using high-level programming languages (Python/Matlab). Julia uses the LLVM toolchain, and its implementation enables online interpretation and compilation to machine code, but also just-in-time compilation. Its syntax is close to scripting languages like Lua or Python, but as a compiled language, its performances can approach C/C++. As a recent programming language, its ecosystem is still immature and lacks stability. Only time will tell if its popularity in the HPC field will tackle these drawbacks. Domain Specific Programming Languages (DSL) are, as their name suggests, programming languages dedicated to a certain domain of problems. For instance, NabLab [START_REF] Benoit Lelandais | Fostering metamodels and grammars within a dedicated environment for hpc: The nablab environment (tool demo)[END_REF] and Devito [START_REF] Louboutin | Devito (v3.1.0): an embedded domain-specific language for finite differences and geophysical exploration[END_REF] target simulation over grids/meshes using finite-differential equation solvers, and PPML [START_REF] Karol | A domain-specific language and editor for parallel particle methods[END_REF] target hybrid particle-mesh simulations. As opposed to general-purpose programming languages (GPL) (C, C++, Python, ...), domain-specific programming languages can restrict the language. It provides a few specific interfaces tied to the domain so that simulation programmers can focus on the science and not on any architectural aspects. DSL programming is often close to mathematical notations familiar to scientific code programmers, as shown on Listing 2.5 which is a NabLab program.

1 ComputeLjr: ∀ c ∈ cells(), ∀ n ∈ nodesOfCell(c), res{c,n} = 4 * 5
Listing 2.5: NabLab program line of code, computing 4 x 5 on every mesh node

Programming Models in HPC

Programming Models (PMs) are programming language extensions defining an Application Programming Interface (API) and an Execution Model (EM). APIs provide the building blocks for calculation expressiveness to programmers, while the EM specifies how the executing environment must interpret the API. PMs adds an additional layer on top of programming languages, and serve as bridges between a calculation expression and its execution by the underlying hardware in a portable manner over hardware architectures. In the HPC application stack iceberg Fig. 2.1, a programming model is low-level if it is self-sufficient (i.e. not dependent on any others PMs), and high-level otherwise (i.e. built upon low-level PMs).

Low-level programming models include for instance OpenMP [START_REF] Dagum | Openmp: an industry standard api for shared-memory programming[END_REF], OpenCL [START_REF] Thompson | An introduction to the opencl programming model[END_REF], MPI [START_REF]MPI: A Message-Passing Interface Standard Version 4[END_REF], CUDA 20 and HIP 21 . OpenMP and OpenCL primarily focuses on portability at the compute-node level; that is, ensuring programs compatibility and performances for any hardware vendor, from a single CPU to a multi-GPP / multi-GPU compute node. CUDA is maintained by the Nvidia vendor to program their GPU hardware. HIP is maintained by the AMD vendor with a CUDA compatibility, so it can run on both Nvidia and AMD vendors hardware. MPI provides standardization for communications between compute nodes through the interconnexion network of supercomputers; it is the most widely adopted PM for distributed parallelism in HPC applications.

To improve the portability of codes and performances, higher-level programming models such as Raja [START_REF] Beckingsale | Raja: Portable performance for large-scale scientific applications[END_REF], Kokkos [START_REF] Trott | Kokkos 3: Programming Model Extensions for the Exascale Era[END_REF] or Arcane [START_REF]CEA/IFPEN and Contributors[END_REF] were developed. They provide higher abstracted interfaces which fallbacks to different lower-level programming models such as OpenMP, OpenCL, CUDA, HIP or MPI.

Task-based Programming Models

Many programming models falls under the category of Task-based Programming Models (TPMs) [START_REF] Dagum | Openmp: an industry standard api for shared-memory programming[END_REF][START_REF] Willhalm | Putting intel® threading building blocks to work[END_REF][START_REF] Bosilca | The template task graph (ttg) -an emerging practical dataflow programming paradigm for scientific simulation at extreme scale[END_REF][START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF][START_REF] Bauer | Legion: programming distributed heterogeneous architectures with logical regions[END_REF][START_REF] Kaiser | Hpx -a task based programming model in a global address space. 10[END_REF][START_REF] Arch | Composable parallel patterns with intel cilk plus[END_REF][START_REF] Chamberlain | Parallel programmability and the chapel language[END_REF][START_REF] Charles | X10: An object-oriented approach to non-uniform cluster computing[END_REF][START_REF] Gautier | Xkaapi: A runtime system for data-flow task programming on heterogeneous architectures[END_REF][START_REF] Galilée | Athapascan-1: On-line building data flow graph in a parallel language[END_REF][START_REF] Huang | Cpp-taskflow: Fast task-based parallel programming using modern c++[END_REF]. We introduce a common set of definitions for TPMs, and then we retrieve and extend the taxonomy on task-based programming model API from P. Thoman et al. [START_REF] Peter Thoman | A taxonomy of task-based parallel programming technologies for high-performance computing[END_REF].

A Definition for Task-based Programming Models

Transition Systems were introduced by R. M. Keller [START_REF] Keller | A fundamental theorem of asynchronous parallel computation[END_REF] (1975) for modeling asynchronous parallel computation. He defines transition system as a pair (S, →) where S is a set of state and → a binary relation on S, which can be represented as a directed graph with the nodes S and the edges (s, s ′ ) ∈ S 2 if and only if s → s ′ . Task-based Programming Models (TPM) are parallel and concurrent programming models which mostly comes with a single task transition system. Tasks are attached a program and precedence constraints, such as the completion of other tasks. In its simplest form, tasks can be represented as a three-state transition system: not-ready, ready and completed as shown on Fig. 2.5. It transitions from not-ready to ready state once all its precedence constraints are fulfilled and from ready to completed state after the sequential execution of its program instructions.

Ready Not-ready Completed

Once precedence constraints are fulfilled

After the sequential execution of the program Task-based programming models usually represent relationship between tasks using graphs, where nodes represents tasks and edges relation between one another. In particular, the Task Control Flow Graph (TCFG) and the Task Dependency Graph (TDG) are commonly used.

Task Control Flow Graph (TCFG) During its program execution, a task T 1 (the parent) may instantiate a new task T 2 (the child). The parent/child binary relation between tasks can be represented as a Direct Acyclic Graph (DAG): this is the Task Control Flow Graph. Fig. 2.6 illustrates a TCFG using OpenMP; for instance, C and D tasks are children of the task A , as they are created as part of its instruction flow.

Task Dependency Graph (TDG) If the completion of a task T 1 is a precedence constraint for the task T 2 , then T 1 is a predecessor of T 2 , and T 2 is a successor of T 1 . The predecessor/successor [START_REF] Peter Thoman | A taxonomy of task-based parallel programming technologies for high-performance computing[END_REF]. They considered an important set of TPMs and made a classification out of 13 multi-value parameters. The C++ Standard Library (STL) 22 is considered as a TPM through the std::async interface. The Threading Building Blocks (TBB) [START_REF] Willhalm | Putting intel® threading building blocks to work[END_REF] is a parallel library provided by Intel. OpenMP [START_REF] Dagum | Openmp: an industry standard api for shared-memory programming[END_REF] is a 25 year old general parallel programming language extension for Fortran/C/C++; originally targeting shared-memory architectures and providing a TPM since 2008. ParSEC [START_REF] Bosilca | The template task graph (ttg) -an emerging practical dataflow programming paradigm for scientific simulation at extreme scale[END_REF] and StarPU [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] are two libraries providing standard C interfaces for task-based programming. Legion [START_REF] Bauer | Legion: programming distributed heterogeneous architectures with logical regions[END_REF] or HPX [START_REF] Kaiser | Hpx -a task based programming model in a global address space. 10[END_REF] are TPM executing in a Global Address Space (GAS). Cilk Plus [START_REF] Arch | Composable parallel patterns with intel cilk plus[END_REF], Chapel [START_REF] Chamberlain | Parallel programmability and the chapel language[END_REF], or X10 [START_REF] Charles | X10: An object-oriented approach to non-uniform cluster computing[END_REF] are programming languages with their own compilers. However, the original taxonomy has a few issues:

• The "Graph Structure" parameter specifies "The type of task graph dependency structure supported by the given API " which could be a tree structure, an acyclic graph (dag), or an arbitrary graph. This parameter is probably not relevant, as a graph is simply the representation of a binary relation between tasks. For instance, a CFG is always a DAG, and TDGs are mostly DAGs as well even though D. Alvarez et al. [START_REF] Álvarez | Optimizing iterative data-flow scientific applications using directed cyclic graphs[END_REF] recently suggested cyclic TDGs in OmpSs.

• The AllScale project seems abandonned since its European Project ended in September 2018 23 and there is no clear documentation on its API accessible online anymore. • StarPU define itself as a "task programming library" and not a programming language extension24 (On "Implementation Type" parameter value).

• OpenMP does provide a distinct interface to execute a task on a specific hardware but was still classified as "implicit heterogeinity".

• OpenMP has both implicit (task construct) and explicit (device clause) work-mapping.

• OpenMP can support "Distributed Memory" to a certain extent; its lack of support is more of related to implementations than its API issue. For instance, A. Patel and J. Doerfert [START_REF] Patel | Remote openmp offloading[END_REF] proposed computation offloading from a source node to a target remote (distributed) nodes, without modifying OpenMP API.

• OpenMP does not prohibit implicit "Worker Management" to implementers; for instance, the LLVM implementation does have hidden helper threads [START_REF] Shilei Tian | Concurrent execution of deferred openmp target tasks with hidden helper threads[END_REF], that are workers capable of executing specific tasks even outside a parallel region.

Extending the Taxonomy

We fixed the P. Thoman et al. original taxonomy and extended it with NESL [START_REF] Blelloch | Nesl: A nested data-parallel language[END_REF], Athapascan-1 [START_REF] Galilée | Athapascan-1: On-line building data flow graph in a parallel language[END_REF], XKaapi [START_REF] Gautier | Xkaapi: A runtime system for data-flow task programming on heterogeneous architectures[END_REF], CPP-Taskflow [START_REF] Huang | Cpp-taskflow: Fast task-based parallel programming using modern c++[END_REF] and MPI. NESL is a programming language designed for parallel and vector supercomputers. Athapascan-1 is a C++ language extension and library for task-based programming with data-flow synchronizations. XKaapi is a C library for fine-grain data-flow synchronizations. It also comes with a C++ library interface and support for the Athapascan- traction 25 . We also removed the AllScale entry due to it lack of documentation; and we replaced the "Graph Structure" with a "Dependency Support" parameter. It characterizes whether the API support fine-grain synchronization between tasks using dependencies or not (i.e. whether the API support the expression of task dependency graphs). The complexity of the taxonomy shows the diversity of existing TPM and the difficulty of sorting them out. They all come with different features, often as a trade of between performances and automation for programmers

Conclusion

In this chapter, we briefly presented every layer that constitute the HPC applications stack. We introduced the diversity and levels of parallelism provided by hardware vendors building supercomputers. We presented the programming and execution of HPC applications over supercomputers: the operating system, programming languages, and programming models. They all provide a piece of the answer to the code and performance portability across hardware architectures. In particular, the task-based programming model is gaining traction, one argument being their composability with one another, which enables full exploitation of the underlying hardware. An important set of task-based programming models had been developed in the past, as shown by the discussed taxonomy. In the midst of these numerous existing programming models, standards such as the Message Passing Interface (MPI) and Open Multi-Processing (OpenMP) try to bring order.

In this thesis, we focus on the C/C++ programming language extended with MPI and OpenMP and compiled with GCC/Clang on a GNU/Linux operating system. This programming environment is reasonably common in the HPC community. We study the benefits of mixing the two standard to conceive programs taking advantages of both the shared and distributed memory parallelism. The next chapter presents furthermore each programming model individually and their mixed-used using tasks. In the midst of the numerous existing programming models, standard programming models such as the Message Passing Interface (MPI) and Open Multi-Processing (OpenMP) try to bring order. The standard designation means they are designed jointly by hardware vendors and research laboratory. Such a collaborative approach aims to ensure code portability over past, current and future architectures, often through co-design between hardware and software. It also aims to maintain a certain level of performances, referred in the literature as the problem of performances portability [START_REF] Thierry | Contribution à la définition des supports logiciels pour une programmation et une exécution portable et efficace en hpc[END_REF]. Over the last 20 years, programmers had been hybridizing (or "mixing" [START_REF] Smith | Development of mixed mode mpi/openmp applications[END_REF]) the two standards as they both provide complementary benefits to entirely exploit supercomputers. We present each programming models and hybridization attempts proposed in the literature.

Chapter 3

Hybridizing Standard Programming Models

The Message Passing Interface (MPI)

The Message Passing Interface (MPI) is an asynchronous, concurrent and parallel programming model. It provides interfaces for process communication over a supercomputer interconnection network. In [START_REF] Dagum | Openmp: an industry standard api for shared-memory programming[END_REF], L. Dagum mentions that "Message passing is the native model for these architectures, and developers can only build higher-level models on top of it.". The Request API The MPI specifications [START_REF]MPI: A Message-Passing Interface Standard Version 4[END_REF] define an MPI_Request transition system, depicted on Fig. 3.1. The colored node shows the left-side instance state after processing instructions line 5. An MPI_Request is a transition system instance representing a local handle for a communication that can be:

MPI

• synchronous if MPI_Request instances involved in the same communication must be started before any instance can be consumed, or asynchronous otherwise.

• point-to-point or collective respectively if only two MPI processes are involved in the communication (a receiver and a sender), or if it involves a group of MPI processes. In particular, many collective types had been developed to optimize specific communication pattern encountered in scientific simulation codes. For instance, the Allreduce collective defines a global reduction operation (such as a sum, an extremum...) whose result is returned to each member of the group.

• persistent or nonpersistent. An MPI request can be marked as persistent on initialization using the MPI_*_init family routines (* ∈ {Send, Recv, ..., Bcast}) as shown on Fig. 3.1.

Otherwise, the request is nonpersistent. The original motivations of persistent requests was to amortize communication initialization overheads by executing only once the transition 0 → 1 but multiple times 1 → 2 .

• partitionned if the message data may be cut into multiple partite, where each partite can be marked "ready" by the programmer using the MPI_Pready routine. As soon as a partite is ready, it may be sent/received independentely to one another. A nonpartitionned MPI request can be seen as a 1-partite MPI request (e.g. MPI_Send). MPI partitionned requests original motivations were two-fold [START_REF] Grant | Finepoints: Partitioned multithreaded mpi communication[END_REF]. The first motivation was similar to persistent requests: overhead reduction by executing 0 → 1 only once. The second motivation is early-bird posting, so network transfers can start as soon as the data is locally ready: using MPI partitioned requests, a partite may be sent as soon as its data was written to the send buffer without the need to fill the buffer entirely with every partite of the message. Note that in the current specifications, partitionned requests are necessarily point-to-point and persistent requests.

MPI Requests Progression

Transitioning MPI request instances requires some CPU cycles to ensure run the communication protocol logic. For instance, this is the case for routing hierarchical messages or simply emptying the network interface controller memory buffers. Progressing MPI requests consist in dedicating CPU cycles to run this logic. Even though it is not clearly defined in the standard specifications yet1 the community distinguishes two types of communication progression: strong and weak progressions.

Strong progression can be seen as mechanisms providing upper bounds on communications time. For instance, kernel threads preempting the execution dedicated to MPI communication progression had been studied by H. Taboada [START_REF] Taboada | Recouvrement des Collectives MPI Non-bloquantes sur Processeur Manycore[END_REF] and F. Reynier [START_REF] Reynier | A study on progression of MPI communications using dedicated resources[END_REF]; with a study on the impacts of dedicating or ovesubscribing (having multiple kernel threads competing CPU time) cores on computational performances [START_REF] Denis | Study on progress threads placement and dedicated cores for overlapping mpi nonblocking collectives on manycore processor[END_REF]. Other techniques, such as Direct Memory Accesses (DMA) by the NIC or offloading communication progression logic to computing units integrated into the NIC (known as "Smart NIC" [START_REF] Bayatpour | Bluesmpi: Efficient mpi non-blocking alltoall offloading designs on modern bluefield smart nics[END_REF]), can also be considered as strong progression mechanisms.

Weak progression does not provide bounds on communication time. It often refers to lazy and opportunistic progression mechanisms. Pioman [START_REF] Denis | pioman: A pthread-based multithreaded communication engine[END_REF] is a pthread-based multi-threaded communication engine whose design considered weak progression on idle periods or any explicit point raised by the program. MPC collaborative polling [START_REF] Didelot | Improving mpi communication overlap with collaborative polling[END_REF] is another form of weak progression: any thread may progress MPI requests during idle periods, which can improve latency and bandwidth in some cases by dynamically adjusting the number of cores contributing to communication progressions.

In this thesis, we extended MPC collaborative polling so MPI requests can be polled not only during idle periods, but also on specific OpenMP tasking events. This work is further presented in Section ??.

Implementations Currently, the two main implementations of MPI are Open MPI [START_REF] Gabriel | Open mpi: Goals, concept, and design of a next generation mpi implementation[END_REF] and MPICH [START_REF] Lusk | User's guide for mpich, a portable implementation of mpi[END_REF]; and their derivatives. Open MPI derivatives include for instance, Bull-MPI for BXI Interconnect, which relies on the Portals4 low-level network API2 . MPICH derivatives include, for instance, the Intel MPI Library, Cray MPT, or MVAPICH; which standardized their Application Binary Interface (ABI) so the MPI runtime implementation can be switched without the need to recompile the MPI program. Both implementations provide high-level standard specification support and performances on existing interconnection networks. Their working method by publications and open-source implementations lead to a friendly competition in which one can unlikely outperform the other for a long time 3 .

A few more MPI implementations non-derivative from Open MPI or MPICH exists, but at much less used in production environment and are mainly used for research purposes. MPC-MPI [START_REF] Perache | Mpc: A unified parallel runtime for clusters of numa machines[END_REF] implements MPI processes as threads. MAD-MPI is built on top of the New-Madeleine [START_REF] Olivier Aumage | New madeleine: a fast communication scheduling engine for high performance networks[END_REF] communication engine, and was originally motivated to improve non-continuous memory transfers. ExaMPI [START_REF] Schafer | Overview of ExaMPI[END_REF] is "an experimental MPI implementation designed to simplify learning, modifying and use for middleware research".

Conclusion

The MPI specifications include many more interfaces for managing inter-MPI process communications on supercomputers, such as: network topology, file I/O, one-sided operations, sessions... As part of this thesis, we primarily focus on the MPI request interface. In Chapter 5, we explore how it can be mixed with the Open Multi-Processing (OpenMP) standard programming model to improve data transfers with early-bird posting, and weak-progress not only on idle periods, but also opportunistically in the MPC-OMP runtime.

Open Multi-Processing (OpenMP)

OpenMP is a programming model initially designed for intra-node parallel programming. Its specification is a 600+ pages document defining C/C++/Fortran extensions with compiler directives, library interfaces, and environment variables. In addition, some members of the Architecture Review Board (ARB) in charge of maintaining the standard specifications also developed a document with a minimal example for each interface 4 . The two main implementations of the standard are currently LLVM OpenMP [START_REF]LLVM/OpenMP Documentation[END_REF] and GNU OpenMP [83] implementations, respectively with 587 and 228 commits merged in their production branches between February 01 2022 and March 30 2023. They both extend C/C++ compilers and provide a runtime system.

Other implementations exists but are mostly research projects with few uses in production environment. For instance, MPC-OMP [START_REF] Carribault | Enabling low-overhead hybrid mpi/openmp parallelism with mpc[END_REF], XKaapi [START_REF] Gautier | Xkaapi: A runtime system for data-flow task programming on heterogeneous architectures[END_REF] or Argobots [START_REF] Seo | Argobots: A lightweight low-level threading and tasking framework[END_REF] implements their own OpenMP runtime relying on GCC/LLVM Application Binary Interfaces (ABIs). OmpSs [START_REF] Fernández | Task-based programming with ompss and its application[END_REF] and its compiler Mercurium is a programming model extends the C programming language with directives similarly to OpenMP, and influences the standard specifications.

Before Tasking

The OpenMP 1.0 specifications were originally proposed as a portable programming interface for shared-memory multi-processor in 1997 [START_REF] Dagum | Openmp: an industry standard api for shared-memory programming[END_REF]. Back then, it was proposed as a simpler alternative to MPI, HPF and pthreads for shared memory parallelism, which we judged too low level for scientific applications. For instance, this very first version already included the parallel do (Fortran) and the parallel for (C) constructs to execute loops iterations in parallel, distributing iterations evenly and continuously between threads. This is also known as implicit tasking. Version 2.0 published in 2002 provided minor additions, for instance, with the addition of the num_threads clause onto the parallel construct, which could only be configured globally through OMP_NUM_THREADS variable previously.

After Tasking

Version 3.0 published in 2008 extended specifications with the concept of explicit tasks with the task construct heavily inspired by Cilk 5 [START_REF] Frigo | The implementation of the cilk-5 multithreaded language[END_REF]. This was the first step in moving OpenMP to a task-based programming model that led to significant work over the past 15 years.

The original tasking design was motivated to improve the expression of irregular parallelism [START_REF] Ayguade | The design of openmp tasks[END_REF] on compute-node with an increasing number of CPUs. This first version of the OpenMP task specification [START_REF] Ayguadé | A proposal for task parallelism in OpenMP[END_REF] only provided means to manage independent tasks in a control-flow graph. To ensure the correct order of execution, programmers were given barriers (taskwait construct, or implicit region barriers), which suspends the execution of the current task until every previously created children tasks completed. Interfaces for managing dependent tasks were only added in specifications 4.0 (2013) five years after the extension proposal [START_REF] Duran | Extending the openmp tasking model to allow dependent tasks[END_REF] to provide finer control on the order of execution through a dependency graph. For instance in 2014, the Kastors benchmark suite [START_REF] Virouleau | Evaluation of openmp dependent tasks with the kastors benchmark suite[END_REF] showed that dependent tasking could outperform independent tasking on SparseLU and Strassen benchmarks. Specifications 5.0 in 2018 introduced a few new tasking features, such as the taskloop construct, the detach clause to differ completion until an external event is fulfilled, and the capability to perform task-based reductions.

Tasks as a Transition System

Task Dependency Node states [START_REF] Carribault | Enabling low-overhead hybrid mpi/openmp parallelism with mpc[END_REF] runtime as a transition system, and refers to the simplified implementation depicted on Listing 3.1. Note that as a standard implementation, the LLVM, GCC and even Nanos6 [START_REF] Balart | Nanos mercurium: A research compiler for openmp[END_REF] implementations are very close to the MPC-OMP behavior.

MPC-OMP tasks are a 10-state transition system, with concurrency on some transitions such as 2 → 3 meaning that multiple threads may try to transition the same task instance in Listing 3.1: OpenMP Simplified Tasking Runtime parallel. The first column of the table is a transition; the second column provides events/interfaces that can lead to transitioning; the third column is the level of concurrency, that is the amount of thread that may concurrently try to transition a task instance; and the last column provides additional information on the transition.

On the simplified runtime implementation, the init and construct routines create a new task. The data parameter represents the task passed private variables, but could be more generally assimilated to a "task local storage". The dependency_insert routine inserts the task into the dependency graph. Any thread may run the schedule routine upon reaching a scheduling point; that is when a new task may be elected to run. After executing the task, the thread runs the finalize routine waiting for the associated event if the task had been detached, and then fulfill its dependencies. The process routine queue the passed task if its dependences are met, and waits for its execution if it is an undeferred task; that is, with respect to the if or final clauses, or if the runtime scheduler internally decides to serialize it through task throttling [START_REF] Duran | An adaptive cut-off for task parallelism[END_REF] to prevent excessive memory use if enough tasks had already been created. For instance by default, GCC and LLVM respectively limits the number of pending tasks to 64 × nthreads and 256 tasks.

Standard version Additions

Target Tasks

As accelerators (such as GPU) were appearing in supercomputers nodes, the OpenMP specifications provided the target interface in its specification 4.0 to enable portable computation offloading [START_REF] Ayguade | A proposal to extend the openmp tasking model for heterogeneous architectures[END_REF]. Programmers can define a target code region to be executed on a specific device connected to the host compute node. The memory model assumes that memory space between the host and the device are different: if memory spaces are unified, programmers must explicitly specify the requires(unified_shared_memory) clause. The execution model is host-centric:

the host decides explicitly which data to move when to move, and on which device. Initially, the target was separated from tasking in the specifications, but version 4.5 (2015) added the nowait and depend clause so target region are considered as dependent tasks, allowing fine synchronizations between the host and the device computation and memory transfers using the task dependency graph.

Conclusion

To follow intra-node evolutions, the OpenMP specifications had lived several extensions since its original specifications in 1999. Since the many-cores era in the mid 2000s, specifications had been moving towards a task-based programming model; which task-related evolution is summarized on Fig. 3.3. Still, the specifications original spirit of focusing on intra-node parallelism mostly remains. Therefore, stand-alone OpenMP is not a sufficient solution to efficiently exploit a supercomputer with distributed-memory. Another programming model, such as MPI, is required to perform memory movements over the inter-connexion network, which had lead the HPC community to mix both programming models.

Hybridizing MPI and OpenMP

Before the many-core era that started in the 2000s, supercomputer compute-node used to be single-core processors with a NIC interconnected in a network. Parallelizing applications using only MPI was sufficient to exploit the machine efficiently [START_REF] Smith | Development of mixed mode mpi/openmp applications[END_REF]. In particular, the Bulk-Synchronous Parallel (BSP) [START_REF] Valiant | A bridging model for parallel computation[END_REF] bridging model was widely implemented in application codes, where processors repetitively perform 3-stages super-steps: computation, communication, and synchronization. In the model, computation from super-step n + 1 cannot start until the synchronization of every processor of the super-step n is completed. Note that in the original model, each super-step has a fixed time duration; but hardware and software implementations were not rigorously providing such guarantees.

Historical Bulk-Synchronous Parallel Program Structure

As compute-node became themselves parallel architecture with the apparition of many cores, relying only on MPI was no longer sufficient [START_REF] Smith | Development of mixed mode mpi/openmp applications[END_REF]. A mixed-use of standard presents benefits to exploit this new intra-node parallelism using a shared memory programming model such as OpenMP; in particular for applications suffering from load imbalance between MPI processes, memory limitations due to data replication or a restriction on the number of MPI processes combinations. In 2009, M. Tsuji et al. [START_REF] Tsuji | Performance evaluation of openmp and mpi hybrid programs on a large scale multi-core multi-socket cluster, t2k open supercomputer[END_REF] conducted evaluations of the T2K supercomputer reporting results in that direction: mixed versions provide improved performances over MPI-only versions of the evaluated benchmarks on a multi-core multi-socket node cluster, and using one MPI process per socket running a multi-threaded OpenMP runtime. Since then, mixed-use of the standard became usual and found in a wide range of applications, but mostly consists in preserving existing BSP programs parallelizing the computation stage (and sometimes the communication stage) using # pragma omp parallel for loops. However, preserving original BSP program structure, communications may not start until its executing thread previously completed its computation stage, limiting the potential of network communication overlap with computation [START_REF] Sala | Integrating blocking and non-blocking mpi primitives with task-based programming models[END_REF]. In addition, the synchronization stage remains which limits load balancing and overlap furthermore.

Task-based Hybridization

On the other hand, mixed use of the standards using a task-based composition provides additional advantages over a BSP use. In particular, it allows the implicit overlap of communication with independent computation [START_REF] Marjanović | Overlapping communication and computation by using a hybrid mpi/smpss approach[END_REF] as the task dependency graph expressed by the programmer provides the degree of parallelism to the task scheduler. However, it requires porting applications from a BSP to a task-based model; and executing MPI communications within OpenMP tasks most likely leads to the loss of an OpenMP worker thread issue. Listing 3.2 presents a minimal and motivating example illustrating the loss of an OpenMP worker thread under a task-based hybridization. The objective of this code is to overlap the MPI synchronization line 6, switching the executing thread to any other ready tasks (such as the one line 10). However, such behavior is not granted by standards. In practice, the thread would block into the MPI runtime line 6, leading to the loss of worker thread [START_REF] Marjanovic | Effective communication and computation overlap with hybrid mpi/smpss[END_REF] on the OpenMP runtime; and ultimately to low performances or even deadlocks. This problem motivated the community to propose various solutions.

Solution (1) Test+Yield

In [START_REF] Meadows | Openmp tasking and mpi in a lattice qcd benchmark[END_REF], programmers replaced the MPI_Wait with a loop calling MPI_Test and the taskyield construct as shown on Listing 3.3. Authors initially assumed the executing thread would schedule any other ready tasks until the request is completed.

# pragma omp task { while (1) { int completed; MPI_Test(&req, &completed, &status); if (completed) break ; # pragma omp taskyield } } Listing 3.3: Suspending tasks using the taskyield construct However, the OpenMP standard does not guarantee such behavior, as it only specifies that: "The taskyield region includes an explicit task scheduling point in the current task region.". It means the executing thread may not necessarily switch to ready tasks. This motivated J. Schuchart et al. [START_REF] Schuchart | The impact of taskyield on the design of tasks communicating through mpi[END_REF] to explore various implementations on the taskyield construct for switching tasks. Their circular-yield algorithm suspend the current task until every other task executed at least once, enabling the expected behavior with MPI. Their stack-yield algorithm executes a new task on the current thread on top of the current one. Regarding OpenMP runtime implementations, GCC and MPC-OMP taskyield construct is a no-op. With LLVM, if the task is annotated untied, the compiler automatically privatizes variables from the outermost scope to a task local storage. It also rewrite its memory accesses accordingly. During the execution, as long as the instruction pointer remains in the task outermost scope, the task remains stack-less. In such case, the entire execution context fits into fixed-size task' local storage. Hence, whenever the executing thread reaches a scheduling point on the outermost scope, it can return to the LLVM OpenMP runtime leaving no footprint on the current thread stack and get re-queued. When the task is re-scheduled, the underlying thread jumps to the scheduling point where the task was suspended. As an explicit scheduling point, the taskyield construct follows this rule if appearing in the outermost scope of an untied task; else if the scheduling point appears in a nested function call, or if the task is tied, LLVM uses a stack-yield algorithm. Hence, LLVM mixes J. Schuchart and al. approaches but presents limitations:

• The stack-yield algorithm triggering by default can lead to the deadlock of valid OpenMP programs. Fig. 3.4 is a minimal example deadlock scenario: T 1 is scheduled, yields to T 2 , and T 2 yields until T 1 completed. T 1 will never be able to resume as it is blocked T 2 on the thread stack, leading to a deadlock. The OpenMP program of this scenario is provided in Annex 8.4.

• A circular-yield alike algorithm triggers only on untied tasks, and if scheduling points appear on the outermost scope of the task. However, programmers cannot use Variable Length Array (VLA) or the Linux alloca function, as the thread stack may be rewritten between scheduling points. Doing such currently causes the compiler to crash5 . MPICH+ULT [START_REF] Lu | Mpi+ult: Overlapping communication and computation with user-level threads[END_REF] (2015) proposed to automate threads suspension by using Argobots as a threading library for MPICH. In 2019, they implemented an OpenMP runtime (BOLT [START_REF] Iwasaki | Bolt: Optimizing openmp parallel regions with user-level threads[END_REF]) that also relies on the Argobots threading library. Their objectives were to automate interoperability between MPI and OpenMP through the common Argobots threading library. With such approach, as opposed to TAMPI, user code may remain unchanged. However, BOLT only provided Argobots support for threads on parallel region, and have not yet investigated explicit task suspension.

The Task-Aware MPI (TAMPI) [START_REF] Sala | Integrating blocking and non-blocking mpi primitives with task-based programming models[END_REF] library was proposed as an extra layer above MPI, to suspend tasks that would block in the MPI runtime otherwise. The authors provided an implementation for the Nanos6 tasking runtime of the OmpSs standard. Using this library, programmers must replace MPI blocking calls with their TAMPI equivalent (for instance, MPI_Wait by TAMPI_Wait).

Both approaches are summarized on Fig. 3.5. Nevertheless, no standard solutions have been adopted in the standard OpenMP or MPI specifications when executing blocking MPI operations in a task-based environment, so it remains implementers and programmers responsibility to ensure there is no loss of threads. Solution (3) Task Detach A third solution came with the task' detach clause introduced in OpenMP 5.0 specifications (Nov. 2018). Set on a task construct, the clause differs its completion until an external event is fulfilled. This would be used in codes as depicted in Listing 3.4 which we retrieved from [START_REF] Sala | Integrating blocking and non-blocking mpi primitives with task-based programming models[END_REF][START_REF] Protze | Mpi detach -asynchronous local completion[END_REF] Listing 3.4: MPI and OpenMP task-based using the detach clause programmers must express two dependent tasks for managing asynchronous operations: the launch (line 2) and its continuation after completion (line 8). MPIX_Detach (line 6) registers the omp_fulfill_event(ev_handle) callback on the MPI request completion, which raises an allow-completion event to the OpenMP runtime.

This new clause also impacted other asynchronous programming models. For instance, proposals were made to the MPI specifications to register a callback on request completion [START_REF] Protze | Mpi detach -asynchronous local completion[END_REF][START_REF] Schuchart | Callback-based completion notification using mpi continuations[END_REF] which are currently being standardized 67 . As opposed to the solution [START_REF] Boekholt | Multi-physics simulations in astronomy[END_REF], this clause provides a portable solution for synchronization overlapping with independent tasks. Nevertheless, as opposed to (2), it increases programming costs for users, moving interoperability responsibility from runtime systems to user codes. Still, this has become the standard way of hybridizing asynchronous programming models using task-based OpenMP.

What about Requests Progression ? All these solutions enable the suspension of tasks waiting on an MPI request completion. It can therefore overlap the MPI request completion time with other independent work through the OpenMP task scheduler. Yet remains questions on the responsibility of progressing communication (i.e. such as copying memory buffers, forwarding messages, computing collectives algorithm...) and raising the completion callback. In the MPI_Detach proposal [START_REF] Protze | Mpi detach -asynchronous local completion[END_REF], authors provided an implementation where a single kernel (p)thread progresses every MPI requests and raises the omp_fulfill_event callback on completion. This strong progress as the kernel preemption on cores ensures that the MPI requests will be granted CPU time to progress regularly, bounding communications during in time. Other approach relying on weak progress such as MPC collaborative polling [START_REF] Didelot | Improving mpi communication overlap with collaborative polling[END_REF] during idle periods is also a solution to progressing MPI requests and raising the OpenMP callback on completion. A Thread-based MPI Implementation MPC initial design in 2008 consisted in a unified implementation of POSIX Threads (pthreads) and MPI. pthreads and MPI processes are virtualized with user-level threads known as "MPC threads" [START_REF] Perache | Mpc: A unified parallel runtime for clusters of numa machines[END_REF]. The shared "Thread" layer of the MPC software architecture is responsible of scheduling each MPC threads on virtual processors (VPs) implemented as Linux kernel threads. While existing MPI runtimes used to implement MPI processes as Linux processes, MPC-MPI processes running on the same compute-node may run as MPC threads in the same virtual memory address space. This created issues for supporting existing codes, in which developers assumed that an MPI processes are always a POSIX process with their own virtual address space. For instance, global variables were assumed private per MPI processes unlike thread-based MPC-MPI processes. Therefore, compilers and linkers had been extended to support an extra layer of Thread Local Storage (TLS) which stores the MPI process data [START_REF] Carribault | Thread-local storage extension to support thread-based mpi/openmp applications[END_REF]. The MPC compiler privatizes global variables into this TLS so that each MPC-MPI process has its own copy, supporting previous code assumptions.

The MPC OpenMP Implementation In 2010, MPC was extended with an OpenMP runtime supporting both GCC and Clang ABIs [START_REF] Carribault | Enabling low-overhead hybrid mpi/openmp parallelism with mpc[END_REF]. OpenMP threads were implemented as MPC threads scheduled by the shared "Thread" layer like any other threads. In the "OpenMP" layer, A. Mahéo et al. [START_REF] Mahéo | Adaptive openmp for large numa nodes[END_REF] organized MPC-OMP threads in a tree based on hardware topology primarily motivated to accelerate thread synchronizations and activations. Fig. 3.7 illustrates such representation. In this example, the last level 2 represents cores (threads), level 1 represents the NUMA domain shared by cores, and level 0 is the compute node. In their conclusion, A. Mahéo et al. suggested reusing this data structure for a topology-aware task scheduling strategy; so that threads favor stealing on the closest threads queue in the hardware. They since then implemented into the MPC-OMP runtime and evaluated as part of his Ph.D. manuscript [START_REF] Maheo | Improving the Hybrid model MPI+Threads through Applications, Runtimes and Performance tools[END_REF].

N 2,2 N 2,1 N 2,2 N 2,1 Level 2 (cores) N 1,1 N 1,1 Level 1 (NUMA) N 0
Level 0 (socket)

Figure 3.7: Topological Representation of Threads

MPC in this thesis As part of this thesis, we mostly restricted our use of the MPC runtime to the OpenMP layer. Threads are always bound 1:1 onto virtual processors, themselves bound 1:1 to physical cores, mostly ignoring low-level MPC threads details to focus on OpenMP aspects. One source of motivation to that decision was to take advantage of previous work on the MPC-OMP work-stealing task scheduler by A. Mahéo, which we heavily re-used throughout this thesis.

Conclusion

Since the many-core era, mixing OpenMP and MPI showed to be crucial to efficiently exploit supercomputers. Original mixed-use were partly motivated by memory overheads of the MPI-only approach; on which OpenMP provide a response as a shared-memory programming model. Since the many-core era, OpenMP had been moving to a task-based programming model that could offers new benefits to the mixed-use with MPI. For instance, the overlap of MPI communications with OpenMP tasks through a task dependency graph scheduling was recently studied ( 2015-2019) [START_REF] Sala | Integrating blocking and non-blocking mpi primitives with task-based programming models[END_REF]. However, interoperability issues makes it hardly achievable in practice, with poor performance portability of existing solutions over environments of execution. In Section 5.1, we introduce mechanisms in the MPC-OMP runtime for suspending/resuming tasks in the presence of MPI synchronizations (implementing effective taskyield) towards the automation and portability of runtime interactions. Mixed-use of the programming models using tasks presents another important benefit: the early-bird of MPI communications by OpenMP dependent task scheduling. In Section 5.2, we present how we extended the MPC-OMP tasks with priorities to guide the scheduler to electing tasks performing communications at the earliest.

In order to evaluate these extensions on real-world applications, Chapter 6 presents our porting experience of two mainstream HPC applications. During our journey, we discuss the three profiling/programming/performances difficulties introduced earlier. For instance, we propose standard and MPC-OMP runtime extension on task in Chapter 5 for task suspension/resumption, and standard extensions in Section 6.1.1 to ease the expression of irregular dependencies. Evaluations suggested the task dependency graph creation can be a performance bottleneck in current OpenMP implementations, that lead us yet again to extend the standard and MPC-OMP task transition system with persistence in Section 6.2.3.2.

But first, the next Chapter 4 introduces the profiler we developed to overcome the current lack of tools for dependent task-based hybridization; that we extensively used in almost all of the experiments of this thesis.

Chapter 4

Measuring Performances of Task-based Applications This chapter present our contributions on the performance profiling difficulty of MPI and taskbased OpenMP applications. We respond to the lack of tool dedicated to dependent task-based programming proposing an hybrid profiler. First, we present a modeling of hybrid applications to a unified task graph scheduling problem, in order to formally define performance metrics in the context of dependent task-based programming. Then, we implement a profiler and analysis to synthesize metrics from actual executions.

Defining Metrics

Applications are often modelled through a graph where nodes represent sequential sets of instructions (tasks) and edge their precedence constraints [START_REF] Robert | Task Graph Scheduling[END_REF][START_REF] Haluk Topcuoglu | Performance-effective and low-complexity task scheduling for heterogeneous computing[END_REF][START_REF] Mixte | Static scheduling strategies for heterogeneous systems[END_REF]. Task Graph Scheduling is then studied as the assignation of tasks to their starting on a processing unit with solutions as couples (σ, a) mapping each node v to its starting time σ(v) on a processor a(v).

Task Graph Scheduling Problem and Observation

Classical modelings assume that each node and edge completion time is fixed and independent on the schedule itself. However multiple phenomena can cause tasks completion time to vary at execution. Hierarchical memory accesses [START_REF] Olivier | Characterizing and mitigating work time inflation in task parallel programs[END_REF], process stalls from cache misses [START_REF] Qureshi | A case for mlp-aware cache replacement[END_REF], memory contention [START_REF] Denis | Interferences between communications and computations in distributed hpc systems[END_REF], network contention [START_REF] Sinnen | Communication contention in task scheduling. Parallel and Distributed Systems[END_REF], or even Dynamic Voltage and Frequency Scaling (DVFS or CPU throttling) [START_REF] Merkel | Balancing power consumption in multiprocessor systems[END_REF] are examples of what can impact the duration of the exact same workload depending on the scheduling itself. Therefore in our modeling, nodes, and edges completion time are part of the scheduling solutions themselves, named below as observations to be constructed by profiling executions.

We define a Problem as a processor set P = {1, 2, ..., p} with p ∈ N * the number of processors and an application as a directed acyclic graph (V, E) with V the nodes representing tasks and E the edges representing tasks precedence constraints. An Observation is a triplet (σ, a, d) with

• σ : V ↦ → R + mapping tasks to their starting time,

• a : V ↦ → P mapping tasks to processors, Given a problem (P, V, E) and an observation S = (σ, a, d), we define multiple to assess the performances.

• d = (d t : V ↦ → R , d c : E ↦ → R)
∀e = (u, v) ∈ E, σ(u) + d t (u) + d c (e) ≤ σ(v) (4.1) a(u) = a(v) ⇒ { σ(u) + d t (u) ≤ σ(v) or σ(v) + d t (v) ≤ σ(u) (4.2)

Metrics Definition

Time Breakdown

In [START_REF] Tallent | Effective Performance Measurement and Analysis of Multithreaded Applications[END_REF], the authors proposed the time breakdown depicted in Fig. 4.1 to assess multithreaded application performances. It allows performance characterization of a multithreaded execution to balance the parallelism (idleness) with management costs (overheads). They illustrated this time breakdown on OpenMP before introducing dependent tasking [START_REF] Duran | A proposal to extend the openmp tasking model with dependent tasks[END_REF] in 2009. Hence, we adapted the time breakdown for dependent tasking while preserving the sense of these metrics. We define the total time as the duration from the first task schedule to completing the last task on any threads. The work is the time spent within an explicit task program, the overhead is the time spent outside of any explicit task program while there are tasks ready, and the idleness is the time spent outside of any task program while there are no tasks ready.

Work Time Inflation

The time breakdown provides an overview of the parallelism but lacks details on the work time performances. S. L. Oliver and al [START_REF] Olivier | Characterizing and mitigating work time inflation in task parallel programs[END_REF] introduced the work time inflation metric defined as "the additional time spent by threads in a multithreaded computation beyond the time required to perform the same work sequentially.". They illustrated that work time can significantly inflate in the presence of non-uniform memory accesses. However, work time inflation can be seen more generally as a matter of task scheduling, instead of a matter of the number of threads. For instance, depth-first scheduling can improve cache reuse [START_REF] Blelloch | Effectively sharing a cache among threads[END_REF] and reduce the work time, independently of the number of threads. Therefore, we propose a different definition of work time inflation: instead of an "additional time" (in seconds), we define the work time inflation i t as a ratio. (no units) between two observations

S ref = (_, _, d ref ) and S = (_, _, d). i t (u) = d t (u)
d ref t (u) and i t (V ) = ∑ u∈V d t (u) ∑ u∈V d ref t (u) i t (u)
is the work time inflation of the task u for the observation S, using the u work time on the observation S r ef as a reference. i t (V ) is the global work time inflation for the observation S using the observation S r ef as a reference. In practice, we usually choose S ref the observation with the least work time.

Communication Time and Inflation P. Swartvagher and al. [START_REF] Denis | Interferences between communications and computations in distributed hpc systems[END_REF] studied the impact of concurrent communication and computation on performances. In particular, they have shown that communication time can increase in case of memory contention where CPUs and NICs concurrently access the DRAM. In task-based applications, similarly to work time inflation, communication time degradation can be seen as a scheduling matter. We define communication time inflation metric to quantify degradation due to scheduling decisions, between two observations observation S ref and S as:

i t (e) = d c (e)

Communication Overlap with Computation

The overlap of communication with computation is the capacity of CPUs to perform computation while data transfers occur asynchronously onto the network. Dependent task parallelism enables automatic communication overlap with computation having cores switching to ready tasks during synchronizations. Such an approach was used with SmpSs in [START_REF] Marjanović | Overlapping communication and computation by using a hybrid mpi/smpss approach[END_REF][START_REF] Castillo | Optimizing computation-communication overlap in asynchronous task-based programs: Poster[END_REF], but the overlap itself was not explicitly quantified, making it hard to ensure that overlap is the reason for observed performance gain (and not other phenomena such as work/communication time inflation). Garcia et al. [START_REF] Vinicius | A Visual Performance Analysis Framework for Task-based Parallel Applications running on Hybrid Clusters[END_REF] proposed multiple visualization panels for task-based applications to understand performances from a given task scheduler. In particular, one panel is the network activity over time and another the cores activity over time. Placed on top of each other, this visualization gives hints on the communication overlap with computation. However, this approach is mainly visual, which depends on the analyst's subjectivity, in particular with the presence of visual artifacts.

Richard et al. [START_REF] Richard | Fine-grained mpi+openmp plasma simulations: Communication overlap with dependent tasks[END_REF] proposed to report a global ratio that quantifies the overlap. Their approach only assumes that MPI operations are serialized on a single thread and does not permit to report of any information on time sub-interval for finer analysis than ours. Reynier et al. [START_REF] Denis | A methodology for assessing computation/communication overlap of mpi nonblocking collectives[END_REF] proposed an overhead ratio metric and benchmarks to quantify computational/communication overheads when overlapping MPI collectives that are close to our communication inflation metric. Just like F. Richard, quantification only considers the activity on a single thread.

We propose a task-based definition of the overlap ratio from a given observation to quantify the amount of work processed on a set of processing units in parallel with communications on any time window, allowing fine analysis of multi-threaded and multi-phase applications. Let Run : P (P) × I(R) ↦ → P (V ) mapping the set of tasks running on a set of processors on a time interval. It is defined as:

∀Q ∈ P (P), ∀I ∈ I(R), Run(Q, I) = {u ∈ V | a(u) ∈ Q and I ∩ [σ(u) ; σ(u) + d t (u)] ̸ = ∅ }
The overlapped work on the set of processor Q and time interval [a, b] is:

o v : (Q, [a, b]) ↦ → ∑ u∈Run(Q,I) min(b, σ(u) + d t (u)) -max(a, σ(u)) P (P) × I ↦ → R
and inferred on edges execution time interval as

o v : (Q, e = (u, _)) ↦ → o v (Q, [σ(u) + d t (u) ; σ(u) + d t (u) + d c (e)]
)

P (P) × E ↦ → R
We define E ˆ(Q) the set of outgoing edges from a given processor partite Q ∈ P (P) as

E ˆ: Q ↦ → {e = (u, v) ∈ E | a(u) ∈ Q and a(v) / ∈ Q} P (P) ↦ → P (E)
The overlap ratio reduces the overlapped work on every outgoing edges of the processor partite Q

r overlap : Q ↦ → ∑ e∈E ˆ(Q) o v (Q, e) | Q | ∑ e∈E ˆ(Q) d c (e)
In practice with MPI, the overlap ratio. is measured using MPI processes as partites Q. Fig. 4.2 illustrates the overlap ratio. definition on the processor partite

Q = {p 1 , p 2 } for a graph G = (V, E) with V = {0, 1, 2, 3, 4, 5, 6}, E = E ˆ(Q) = {(0, 5)}.
This definition is the multi-threaded generalization of the usual single-thread overlap metrics found in the literature:

| Q | ∑ e∈E ˆ(Q) d c (e)

MPI+OpenMP(tasks): A Unified Modeling

In order to fall back to a task graph scheduling problem, observations, and defined metrics, we model distributed MPI+OpenMP(tasks) applications to a single unified graph: the Global Task Dependency Graph (GTDG). • (c) Adding intra-process edges between (b) sub-nodes to preserve both the parallelism expressed through MPI and the sequential order of execution,

• (d) Adding inter-process edges between MPI requests states transition nodes so that transitions to state (3) for collective, receive, and synchronous send operations depends on transitions to state (2) nodes of other processes involved in the communication. Note that step (d) must respect both the order of execution and the parallelism specified by MPI. For instance, it models the implicit barrier induced on each collective communication but also models that an MPI_Wait on an asynchronous send operation could return before the paired-receive is posted remotely. It also models the explicit overlap parallelism expressed between a started/completed transition state, as shown with independent nodes B and C.

Profiling MPI+OpenMP(tasks) Task-based Execution

Both OpenMP and MPI specifications come with profiling interfaces (OMPT and PMPI) which can allow to build such modelling, and ultimately the defined metrics. The two profiling interfaces are based on callbacks: PMPI overloads every MPI library call while OMPT raises callbacks on specific events. Tools like HPCToolkit [START_REF] Anderson | Preparing for performance analysis at exascale[END_REF] or TAU [START_REF] Sameer | The tau parallel performance system[END_REF] exists and take use of these interfaces to provide information on each programming model. However, they do not compute the time breakdown and the communication overlap we previously defined; as each programming model is profiled independently. Hence, we made a unified profiler using both interfaces. First, it records events during a program execution, and saves them to trace files on termination. After termination (or post-mortem), events are replayed sequentially to model the distributed execution to a single task graph scheduling problem (P, V, E) and an observation (σ, a, d), to synthesize previously defined metrics.

Hybrid Tracing: Recording PMPI and OMPT Events

For our concerns, we profile the states of MPI requests (see 3.1) and task-based OMPT events (implicit task launch/completion, task creation, task schedules, and task dependency completion).

MPC extensions In addition, MPC-OMP provides extra profiling capabilities. A label, a color, internal runtime flags, and up to 4 hardware counters are attached to records. Hardware counters are retrieved using the Performance Application Programming Interface (PAPI) [START_REF] Phhh | A portable programming interface for performance evaluation on modern processors[END_REF] per thread, and on each task schedule. Hence, hardware events can be counted at a task-level precision, in between two task schedule. It enables portable hardware event counters measurements on the task-level, as opposed to tools like perf or likwid which only provide hardware counters on overall execution. The task-level precision enables fine performance characterization on the work, removing idleness/overhead noise.

Moreover, an additional non-standard event has been added: the task deletion. The task deletion event is raised when the runtime releases a task that can occur asynchronously any time of the execution. This event helped runtime debugging to track the very asynchronous tasks' lifecycle and ensure no tasks were leaking into memory.

Timing Events Each event is timed using omp_get_wtime routine under a microsecond precision and sharing clock time reference between cores of the same compute node. It means that we only have a precisely timed observation per MPI process partite, with no clock synchronizations mechanisms between MPI processes.

From Events to Trace Files From raised events, our profiler generates machine-code records storing events information. During the execution, all records are enqueued per core to a preallocated memory region and flushed to disk on termination to limit the profiler impact onto the scheduling itself. Profiled execution presented in this manuscript has shown from 0% to 5% slowdown enabling the profiler.

From Events to an Observation

An observation is made of four functions (σ, a, d = (d t , d c )), which are to be defined for each graph node from a traced execution. Given a node u, its schedule time σ(u) is an OpenMP task schedule event or a PMPI callback on the transition state associated to the node. Its processor a(u) is set from its OpenMP thread and its MPI rank in the MPI_COMM_WORLD communicator. Its duration d t (u) corresponds to the time taken to execute instructions associated with the node but for MPI nodes d t (u) = 0. Instead, MPI nodes' weights are moved to edges: given an inter-process edge e, d c (e) is set to the duration of the associated MPI transition state. Intra-process edges duration is set to 0.

Analyzing Traces

In order to synthetize metrics previously defined, we made a framework to analyze execution traces that consists of a virtual scheduler and passes.

Virtual Scheduler

The virtual scheduler reads trace files and replay recorded events sequentially. It provides callbacks and data structures for tracking each OpenMP runtime scheduler event, such as a list of ready tasks, a list of blocked tasks, but also MPI communication state transitions.

Analysis Passes

Analysis passes implement the scheduler emulator callbacks; they are called sequentially on the event's callback they implement. Passes can depend on other passes, and the dependencies are automatically resolved by sorting their sequential order of execution (an error is raised in case of a dependency cycle). • the Global Task Dependency Graph (GTDG) builds the unified graph modeling. It provides a graph data structure and synthesizes the observation to be exploited by other passes.

• the GTDG -Critical compute the critical path from the GTDG. It implements the shortest path algorithm 24.5 DAG-SHORTEST-PATHS in [START_REF] Thomas | Introduction to Algorithms[END_REF], by setting edges (u, v) weight to -d t (u). This pass computes the critical path time, the average parallelism, and execution time bounds proposed by Cilk [START_REF] Frigo | The implementation of the cilk-5 multithreaded language[END_REF]. • the GTDG -Dot exports the TDG to a .dot file to be visualized with Graphviz for instance. Fig. 4.7 depicts the modeling for the Cholesky matrix decomposition presented in [START_REF] Schuchart | The impact of taskyield on the design of tasks communicating through mpi[END_REF] distributed on 4 MPI processes.

• the GTDG -Metrics exports general graph metrics: the number of nodes, edges, and minimum/average/median/maximum degrees.

• the Time Breakdown constructs the time breakdown metrics depicted on Fig. 4.1. Work time is the sum of each node duration. Non-work time is split into overheads and idleness by checking the scheduler emulator lists at each raised event.

• the Gantt pass export the scheduling observation to a Chrome Trace Event2 file format, to be imported by a viewer such as Catapult3 or Perfetto4 . The y-axis represents the MPI processes and the OpenMP threads, and the x-axis the time. Boxes represent work time (tasks), while the blank spaces represent non-work time. Fig. 4.5 depicts the visualization of a task-based nbody application, in which we can observe load imbalance between tasks leading to important idleness. Fig. 4.6 depicts the Gantt chart of a Cholesky factorization on two MPI processes, and arrows illustrate the tasks performing point-to-point MPI communications. Note that times are only coherent for cores using the same time reference.

• the Communication -Duration computes the duration of each MPI communications.

• the Communication -Overlap computes the overlap ratio.

• the PAPI aggregates hardware event counter per node for each schedule event. As opposed to tools like perf or likwid, which only provide hardware counters for the entire Linux process execution, this pass allows the extraction of hardware event counters occurring within explicit tasks for finer performance analysis.

Repos and Documentation

The profiler was built directly into the MPC-OMP runtime for historical reasons (the runtime was not supporting the OMPT interface at the start of the thesis). The MPI profiler is a dynamic library interacting with the MPC-OMP runtime profiler. Post-mortem analyses are built in Python and read from profilers' traces. Source are available online at https://mpc.hpcframework.com or https://github.com/cea-hpc/mpc as free-software under the CeCILL-C5 license.

Related Works

Amdahl's Law and Average Parallelism Amdahl's Law provides the theoretical maximum speedup obtainable by increasing the number of processors for a given work time w = w s + w p with w s the in-compressible sequential time, and p embarrassingly parallel time (i.e.that could be parallelized on any additional processing units). The law can hardly be applied in practical task-based programming, as there is rarely such thing as pure sequential or embarrassingly parallel time: instead, tasks are interdependent and the amount of parallelism available varies over the execution. Therefore, Cilk' average parallelism [START_REF] Blumofe | Space-efficient scheduling of multithreaded computations[END_REF] defined as p ˆ= Wt T∞ is more suitable to determine how the execution time is sensitive the number of processors. The work/idle/overhead time breakdown [START_REF] Tallent | Effective Performance Measurement and Analysis of Multithreaded Applications[END_REF] we adapted to task-based executions is also well-suited for determining execution time sensibility to the number of processors: important idleness may be linked to a lack of parallelism.

OpenMP Tools ScalOMP [START_REF] Daumen | Scalomp: Analyzing the scalability of openmp applications[END_REF] is an OMPT plugin that can provide hints on loop parallelization and scalability performances over the number of threads. However, it is restricted to loop constructs and does not consider dependent tasking as we do.

Tikki [START_REF] Daoudi | somp: Simulating openmp task-based applications with numa effects[END_REF] is an OMPT-based plugin that can profile task-based OpenMP applications. It attaches hardware event counters to tasks using PAPI, enabling performance characterization at the task level. Our profiler re-implemented the same capability.

OMPTracing [START_REF] Pinho | Omptracing: Easy profiling of openmp programs[END_REF] is another OMPT plugin that can profile OpenMP applications. From an execution, OMPTracing generates a Gantt chart and a task dependency graph from a single process OpenMP application. Our approach differs on two points. First, we not only consider task-based OpenMP information but also MPI distribution and build a global task dependency graph partitionned between MPI processes. OMPTracing does not provide such a global view and restricts its analysis to a single process. Secondly, OMPTracing generates its analysis at run-time, while our profiler only records execution information to be analyzed post-mortem. This gives us more flexibility for analysis; for instance, we could synthesize metrics such as the time breakdown or critical path that is hardly doable at run-time. Note that OMPTracing [START_REF] Pinho | Omptracing: Easy profiling of openmp programs[END_REF] was published in 2020, which is concurrent to my thesis and my work on the MPC-OMP profiler. Somehow funny, we both are using Chrome trace viewer 6 for visualizing Gantt charts and Graphviz7 for generating dependency graphs.

OmpSs/Extrae/Paraver and StarPU/Pajé/ViTE The Nanos runtime (OmpSs-2 programming model) implements a built-in tracer (Extrae), whose trace can be visualized in Paraver as a Gantt chart 8 . The OmpSs Mercurium compiler [START_REF] Ferrer | Mercurium: Design decisions for a s2s compiler[END_REF] (source to source) can compile standard OpenMP to target the Nanos runtime, so tools shall be working on standard OpenMP as well. The OmpSs-1 runtime implementation (Nanox) is capable of profiling hybrid MPI+OmpSs applications 9 .

Similarly to OmpSs/Extrae/Paraver chain, StarPU [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] can generate Pajé [START_REF] Chassin De Kergommeaux | Pajé, an interactive visualization tool for tuning multi-threaded parallel applications[END_REF] trace files to be visualized in the ViTE software [START_REF] Coulomb | An opensource tool-chain for performance analysis[END_REF]. StarVZ [START_REF] Lucas | StarVZ: Performance Analysis of Task-Based Parallel Applications[END_REF] is a R package and provide several visualization of task-based application executions using StarPU.

In our work, we built yet another minimal trace format optimized only for the MPC-OMP tasking runtime. We built a trace converter for visualization in Chrome Catapult viewer using an analysis pass of our framework. Additional analysis passes targetting Paraver or ViTE could be developed to benefit from their existing visualization, but was not explored as part of this thesis. In particular, the Catapult viewer for Chrome limits the visualization of traces up to 400Mo which showed to be limiting at some points. However, our tracing toolchain also comes with original analysis such as the time breakdown and communication overlap quantification as we defined in Section 4.1.2, which require virtualization of the execution post-mortem, that are not present in Paraver or ViTE.

Distributed Tools HPCToolkit [START_REF] Anderson | Preparing for performance analysis at exascale[END_REF] or TAU [START_REF] Sameer | The tau parallel performance system[END_REF] support hybrid profiling using both OMPT and PMPI, and provides fine information on each programming model independently. In our work, we provide a joint view of hybrid OpenMP-dependent tasks and MPI communications through unified modeling, metrics, profiler, and analysis. Our approach could be integrated into existing production tools that are also capable of more advanced profiling features such as event sampling, massive data processing, or even time coherency between distributed MPI processes.

Conclusion

The lack of performances profiling tools for the task-based hybridization of MPI and OpenMP understudy lead us to develop our own toolchain as part of the MPC-OMP runtime. We introduced a unified performance modelling of task-based hybridization of MPI and OpenMP, on which we formally defined metrics: the work/idle/overhead time breakdown, the work/communication time inflation, and the overlap ratio. These metrics are well-known and fundamental for assessing on multi-threaded execution performances, but were mainly conceived for the historical bulksynchronous parallel hybridization of MPI and OpenMP. In order to compute these metrics under the task-based hybridization understudy, we developed a new profiler into the MPC-OMP runtime. An instance of execution can be traced, and post-processed with analysis passes to compute mentioned metrics, but also to export visualizations (Gantt Charts, or the unified performance modelling graph). The profiler and its analysis passes had been widely used throughout this thesis in the results depicted in the upcoming chapters.

Chapter 5

Scheduling MPI communications as OpenMP tasks Executing MPI communications as OpenMP tasks could improve the overlap of communications with computations [START_REF] Marjanović | Overlapping communication and computation by using a hybrid mpi/smpss approach[END_REF]: The task dependency graph provides a sufficient description of the degree of parallelism so that ready-work is known to the runtime for overlapping data transfers. In addition, it could also lead to early-bird posting of MPI communications which "can help alleviate a major cost of bulk-synchronous parallelism" [START_REF] Grant | Finepoints: Partitioned multithreaded mpi communication[END_REF] by using tasks synchronizations over coarse threads barriers. Then, early-bird posting becomes the responsibility of the OpenMP runtime task scheduler, which may favor task paths leading to MPI communications in the TDG. However, executing MPI communications within OpenMP tasks with current production implementations (LLVM, GOMP, Open MPI, MPICH) most likely leads to poor performances [START_REF] Schuchart | The impact of taskyield on the design of tasks communicating through mpi[END_REF] or even deadlocks [START_REF] Meadows | Openmp tasking and mpi in a lattice qcd benchmark[END_REF]. Particularly, one issue happens when an OpenMP thread executes an MPI synchronization: the OpenMP thread ends up blocking within the MPI runtime without scheduling other OpenMP tasks: we refer to this problem as the loss of thread issue.

In this chapter, our contributions are two-fold. First, Section 5.1 presents extensions of the MPC-OMP runtime to tackle the loss of thread issue. Then, Section 5.2 presents improvements in the scheduler capabilities for the early-bird posting of communications, guiding decisions towards MPI communications with priorities. Most of this work had been published in the International Workshop on OpenMP (IWOMP) [START_REF] Pereira | Communication-Aware Task Scheduling Strategy in Hybrid MPI+OpenMP Applications[END_REF][START_REF] Pereira | Suspending OpenMP Tasks on Asynchronous Events: Extending the Taskwait Construc[END_REF].

Executing MPI Requests within MPC-OMP Tasks

In order to overlap blocking operations with useful work in a tasking environment, the idea consists of giving hand back to the task scheduler. Hence, it schedules any other independent ready tasks until the blocking operation asynchronous completion. However, such behavior is currently not granted by programming standards and depends on the implementation. In practice, running MPI blocking operations as part of OpenMP explicit tasks most likely leads to a loss of OpenMP worker thread [START_REF] Meadows | Openmp tasking and mpi in a lattice qcd benchmark[END_REF]. In Section 3.3.2, we presented the three solutions explored for blocking tasks suspension/resumption. We resume briefly each approach that ultimately motivated us to propose our design and implementation in the MPC-OMP runtime.

State of the art

The first solution consists of replacing blocking calls (such as MPI_Wait) with non-blocking test-for-completion calls (such as MPI_Test), and yielding to the OpenMP task scheduler (pragma omp taskyield) until the test passes. However, the OpenMP taskyield construct provides no guarantees that the scheduler will switch tasks, limiting the portability of such an approach. With existing implementations, it currently only works with the LLVM compiler, and its OpenMP runtime, and only if:

• The taskyield is placed on the outermost scope of the task so it is visible by the compiler when compiling the task.

• There are no dynamic stack allocations (C's variable length array, or alloca API)

Otherwise, in LLVM, the taskyield is implemented following the stack-yield algorithm executing a new task on top of the blocking one on the current thread stack, meaning the blocking task cannot resume until the stacked task completed, and cannot migrate between threads. In GCC, it is implemented as a "no-op" (GCC), meaning no other tasks are scheduled.

The second solution proposed by TAMPI [START_REF] Sala | Integrating blocking and non-blocking mpi primitives with task-based programming models[END_REF] consists of automating the first solution through an additional "interoperability" layer that overrides MPI blocking operations, ensuring task suspension/resumption if executing as part of a task-based environment, such as OpenMP. The authors only provided implementation for the Nanos6 (OmpSs-2) runtime. It consists in suspending/resuming the kernel (p)thread on which the task executes using conditions and signals, and forking a new one so there is no "thread lost". Their implementation tackles the stack-yield stacking/migration issues, but kernel threads management introduces new overheads such as system calls; moreover, the scheduling of the blocking task is delegated from the task-based environment (OpenMP) to the operating system scheduler.

The third solution comes with the detach(event) clause on the task construct [START_REF]Openmp application programming interface 5[END_REF] introduced in 2018. It differs the completion of a task (and its dependencies release) once the associated event is fulfilled through the omp_fulfill_event(event) callback API: the task is detachable. This approach delegates the problem to programmers by removing blocking operations from tasks and replacing them with their non-blocking counterparts in detachable tasks. Programmers also have to raise the callback to complete the task asynchronously and ensure the correct order of execution with dependencies. It ultimately leads to the MPI_Detach proposal [START_REF] Protze | MPI detach -Towards automatic asynchronous local completion[END_REF] (2022) that assists programmers in such a direction. However, back in 2020, at the beginning of this thesis, the detach clause was not well-supported in OpenMP runtimes: LLVM support was implemented in 2019 and merged in early 2020, GCC added support with release 12.1 in 2022), and MPC-OMP had no support.

Solutioning the loss of thread issue

While many solutions to the loss of thread issue had been proposed, they still needed to be implemented as part of the MPC-OMP environment. Inspiring ourselves from the state of the art, we designed and implemented interfaces to support the execution of MPI communications within MPC-OMP tasks.

Motivations

Stacking Tasks Using Nanos6's TAMPI implementation or the LLVM stack-yield algorithm, multiple tasks may be pushed onto the same thread's stack. Such an approach blocks the resumption of tasks previously stacked until the last stacked one is completed, which can raise issues. For instance, in single-producer/multi-consumer scenarios, the producer thread may end up scheduling tasks at some point. If it schedules a blocking task B on top of its original implicit task A, the task A may not resume until B is unblocked. In the best-case scenario, it only reduces the available parallelism (blocking A from producing further tasks until B is completed); but in the worst-case scenario, it can lead to a deadlock if unblocking B requires resuming A. Hence, detecting tasks that may block is essential to avoid such scenarios. However, this is not straightforward. A task may execute code from dynamic libraries that ends-up performing blocking operations at some point. Additionally, not every MPI blocking operation may retain the executing thread. For instance, this is the case when the sent data is small enough to be copied directly to the NIC or when the destination MPI process executes as part of the same POSIX process (MPC-MPI [START_REF] Perache | Mpc: A unified parallel runtime for clusters of numa machines[END_REF]) where a simple memcpy may be sufficient without requiring MPI processes synchronization. It is only with fine application knowledge or at execution time that the thread may decide whether it is worth suspending the current task in favor of another.

Oversubscribing Cores State-of-the-art solutions using MPI_Detach and Nanos6 implementation rely on kernel thread with periodic preemption. D. Tsafrir [START_REF] Tsafrir | The context-switch overhead inflicted by hardware interrupts (and the enigma of do-nothing loops)[END_REF] showed up to 22% slowdown on a computation thread sorting an array of integers, preempted by a thread periodically repetitively making a system call to trigger the kernel scheduler. In [START_REF] Bastoni | Cache-related preemption and migration delays: Empirical approximation and impact on schedulability[END_REF], authors also show computational slowdown due to cache-related delays induced by preemption. Therefore, state-of-the-art solutions may degrade the performances of other tasks, preempting them in the middle of their execution.

Design and Implementation

To tackle the task stacking and oversubscription problems of the state-of-the-art solutions, we implemented the following design in the MPC-OMP runtime.

First, we differ in the detection of blocking task detection to programmers. Programmers have to annotate any MPC-OMP task that may be suspended with a context(stack-size) clause, asking the MPC-OMP runtime to attach a fixed-size stack of stack-size bytes to the task. Whenever such annotated tasks are scheduled, the executing thread switches to the task' stack using the ucontext.h library. Once the task is completed, the thread switches back to its original stack pointer and resumes execution where it stopped.

Secondly, we extended the MPC-OMP runtime with an API to suspend the current task in the middle of its execution and prohibit its scheduling until an asynchronous event (such as MPI requests completion). Full details on the API standardization and implementation have been published in [START_REF] Pereira | Suspending OpenMP Tasks on Asynchronous Events: Extending the Taskwait Construc[END_REF].

Lastly, we added callbacks on the MPC-OMP runtime for progressing MPI requests and allowing the resumption of their associated OpenMP task. Right before suspending the current task, the executing thread registers the request and the task in a list. Then, on each OpenMP schedule event, threads progress requests using MPI_Test calls. If the test passes, then the task is unblocked so it may be scheduled once again. Our implementation allows progression on any thread, but only one at a time, and every request is tested once before pursuing execution. While this could have been implemented as an OpenMP Tool (OMPT), this progression callback mechanism was implemented as a built-in of the MPC-OMP runtime due to its lack of stable support for OMPT back in 2020.

The implementation is summarized in the Annex 8.1 as a one-header file TAMPI implementation for the MPC-OMP runtime, providing a portability layer across MPI runtimes for suspending MPC-OMP tasks on MPI_Wait synchronizations. It had also been re-used to support the execution of blocking GPU operations in the context of OpenMP target tasks, with preliminary results published in [START_REF] Ferat | Enhancing mpi+openmp task based applications for heterogeneous architectures with gpu support[END_REF].

Discussions

Our design and implementation come with the following benefits over existing solutions:

• A task may suspend at any time, resume on any thread, with full compatibility across codes assuming the existence of a linear stack (i.e. providing support to dynamic stack allocation, recursivity...).

• Suspension/resumption can be automated by simply executing blocking operations within tasks and having the MPI runtime give a hand back to the OpenMP runtime scheduler. This can be seen as an extension of the Argobots/BOLT [START_REF] Iwasaki | Bolt: Optimizing openmp parallel regions with user-level threads[END_REF] approach not only for parallel regions but also for tasking. Automation had been implemented as part of the MPC-MPI runtime, meaning that using MPC-OMP with MPC-MPI, programming can simply wrap blocking MPI operations into OpenMP tasks, and suspension/resumption occurs seamlessly. This is illustrated on the Listing 5.1 where the thread executing the MPI_Send line 2 may eventually yield to the task line 4 if blocking on an MPI synchronization.

• The MPI request progression on each OMPT schedule event ensures up-to-date knowledge of ready tasks before the OpenMP scheduler makes a new scheduling decision. In addition, it likely reduces interferences over state-of-the-art solutions with no preemption in the middle of their execution.

# pragma omp task context(stack-size) untied MPI_Send(...); // blocking operation # pragma omp task { // independent work } Listing 5.1: MPC-OMP and MPC-MPI program with automated task suspension/resumption However, our design and implementation also come with at least the following drawbacks:

• Programmers have to guess and annotate tasks that may block with a new context clause, so our runtime executes them using a dedicated stack (otherwise, they are executed on top of the thread original stack). Automatically managing OpenMP task stacks without the need of a new programmer annotation and evaluating induced performance overheads is yet to be evaluated more precisely.

• The use of a dedicated task' stack may have unnecessary overheads: (1) annotated tasks may never block (for instance, MPI eager protocol), meaning that stacking them onto the parent thread stack would have been acceptable, and (2) stack-less execution using LLVM detach implementation removes stack management costs (allocations, context switches).

• The context clause comes with a stack-size parameter raising the problem of optimizing it. Too small, execution may stack overflow; too big, we may consume unnecessary memory.

In [START_REF] Carbonneaux | End-to-End Verification of Stack-Space Bounds for C Programs[END_REF], authors propose an automated verification of stack size requirements for C programs at compile-time. Their approach is limited by Variable-Length Array (VLA) or alloca, which can hardly be predicted at compile-time. Outside these cases, their prediction is convincing and could lead to the automation of optimal stack-size parameters by the compiler.

• Our implementation relies on the <ucontext.h> library that is deprecated. It was introduced in POSIX.1-2001 as a portable interface for threads execution context at the user-space level. The POSIX.1-2008 made this interface deprecated, recommending applications to be rewritten using POSIX threads1 . Yet, practice showed the library to be portable across the recent Fugaku (2020) and CEA-HF (2022) supercomputers.

Summary

In this section, we have motivated and presented our design and implementation to tackle the loss of thread issue. It enables the execution of MPI requests as part of OpenMP tasks. In such a way, the overlap of MPI synchronization with independent OpenMP tasks may occur seamlessly, as the task dependency graph already provides the parallelism available to the task scheduler. This work enables the task-based hybridization of MPC-OMP with any MPI implementation, which leads us to explore the early-bird posting of communications by favoring tasks leading to MPI operations in the following section.

Early-bird Posting with Tasks Scheduling

In the previous section, we have introduced extensions towards automating the overlapping and progression of MPI communications through the OpenMP task scheduler. However, a second motivation of the task-based hybridization of MPI and OpenMP is the early-bird posting of MPI communication by scheduling OpenMP tasks leading to them in the TDGs. Let us motivate furthermore the benefits of early-bird communication posting with the following minimal example.

Motivations

The reference benchmark in the HPC tasking community is the matrix Cholesky decomposition. Given a matrix A, the benchmark computes the lower triangular matrix L so that A = L.L T ; which can also be used to resolve the A.x = b system. Implementations of the literature mostly rely on executing dense algebra kernels (from BLAS, LAPACK, CuBlas...) into tasks. It makes Cholesky a great example of tasking for such calculation that are sometimes on the core of scientific simulation. In 2018, J. Schuchart et al. [START_REF] Schuchart | The impact of taskyield on the design of tasks communicating through mpi[END_REF] implemented a tiled Cholesky factorization mixing MPI and OpenMP using tasks. We use it as a motivational example for early-bird communication posting using OpenMP task scheduling. Fig. 5.1 depicts a subgraph of the Cholesky factorization TDG, and its scheduling on 2 MPI processes of 2 OpenMP threads each from a real execution. Tasks are scheduled following MPC-OMP default "First-In, First-Out" (FIFO) scheduling policy: first-ready tasks are scheduled first. In this minimal example, such policy led to 61% idleness on cores. If task work and communication time are assumed constant, a portion of the idleness could be reduced by earlier posting of the MPI send requests, as shown on the alternative execution presented Fig. 5.2 (which is not a real execution). In this alternative scheduling, we favored the execution of tasks performing MPI send requests and their predecessors. Once yellow tasks L and H are completed, three tasks P , M , and J become ready. In the first-case scenario following a FIFO policy, J is favored over the communication task P on process 1. In parallel, the process 0 thread ends up idling: there are no more ready tasks, as local pending tasks depend on remote data sent by P . Delaying the communication P on process 0 lead process 1 to idle. In the second case scenario, P is favored over J : the send request is posted as soon as it is ready. Hence, process 0 spend less time idling for data to arrive and can schedule tasks F and C earlier. In the end, idleness is reduced to 36% thanks to the earlier send request posting.

It must be noted that favoring only tasks performing MPI communications is not sufficient: favoring their predecessors as well led to early posting of the task O for instance. Contributions In this section, we present how we enabled early-bird posting of MPI communication through the MPC-OMP tasking runtime scheduler. Section 5.2.2 presents a current limitations of existing OpenMP runtimes that limits the scheduler visions of the TDG, and therefore, early-bird communication scheduling. Section 5.2.3 presents MPC-OMP runtime extensions so tasks can be assigned priorities interpreted by the runtime scheduler, to favor tasks leading to communications. Finally Section 5.2.4 presents tasks priority heuristics with different level of automation for application programmers to guide the runtime scheduler towards the early-bird posting of MPI communications.

The Issue of Task Throttling

Task Throttling is a runtime mechanism originally motivated to reduce tasking operational and memory overheads [START_REF] Duran | An adaptive cut-off for task parallelism[END_REF]. Once a threshold is reached, producer threads stop producing and start consuming tasks instead. This mechanism limits the vision of the runtime scheduler of the future of the execution [START_REF] Richard | Fine-grained mpi+openmp plasma simulations: Communication overlap with dependent tasks[END_REF], making it impossible to perform early-bird communication task scheduling as tasks may not even be known by the runtime scheduler.

In [START_REF] Duran | An adaptive cut-off for task parallelism[END_REF], authors proposed to prune task creation and sequentialize their execution at run-time, using dynamic information such as the task depth in the control flow graph (CFG). Both GCC and LLVM runtimes implements a threshold bounding the number of ready-tasks that can co-exist which was developed in the context of OpenMP independent task model (version 3.0), as an efficient solution to bound the memory consumption. It is set to 64 × nthreads in GCC and 256 in LLVM. Though, it can be totally disabled in LLVM2 deferring the memory bounding responsibility to the application programmer.

In case of dependent tasks, ready-tasks throttling threshold not only limits the vision of the runtime scheduler; it is also insufficient to bound memory consumption overhead: as many successors tasks may be created but not marked as ready. Therefore, we extended the MPC-OMP runtime with a threshold on the total number of tasks that can co-exist (ready or not). This threshold can be configured through the MPCFRAMEWORK_OMP_TASK_MAXIMUM environment variable set to 10, 000, 000 by default. With a task descriptor of 512bytes and 16bytes per edge, this default values ensure at most 5Go of memory for task descriptors. This represents 4% of the available DRAM on AMD EPYC processors used in Exa or Titan supercomputers. A patch has also been submitted for adoption into LLVM3 .

Scheduling Tasks with Priorities

In order to control task scheduling, the OpenMP specifications provide a priority(p) clause on the task construct, taking an integer parameter h. This clause is a hint, and the standard recommends implementations to favor the scheduling of tasks with higher priority values. It also mentions that programs should not rely on this mechanism to ensure the correct order of execution as these are only recommendations, and implementers remain free to do as they please.

As we have shown in our minimal example on the Cholesky decomposition, not only tasks performing MPI communications should be favored, but also their predecessors in the task dependency graph. On this point, the standard provides no means or guidelines for propagating over the task dependency graph: under current specifications (and its production implementations GCC/LLVM), it is the programmer's responsibility to set priorities for every task of its application. Note that back-propagating priorities by the runtime to predecessors may increase furthermore task creation overheads.

A Design for Dependent Tasks Priority

In order to assist application programmers on favoring tasks leading to MPI communications, and limit induced overheads, we extended the interpretation of priority hint with three parameters: (VALUE, PROPAGATION, SYNCHRONY). Each parameter is defined with environment variables for the entire execution and they cannot be safely changed during the execution.

• VALUE ∈ {ZERO, INF, COPY} -controls the task priority. ZERO means the hint is ignored and the priority is set to 0, INF means tasks with non-zero hint will have an INT_MAX priority, and COPY means tasks priority will be set to the hint.

• PROPAGATION ∈ {NONE, EQUAL, DECREMENT} -controls how the priority should be propagated to predecessors. NONE means the priority will not be back-propagated, EQUALS means the priority will be copied to predecessors recursively, DECREMENT means the priority will be decremented and copied to predecessors recursively.

• SYNCHRONY ∈ {SYNCHRONOUS, ASYNCHRONOUS} -controls when the priority should be backpropagated (if PROPAGATION is not NONE). SYNCHRONOUS means it should be propagated on task creation by the producer thread that is between lines 16 and 17 of Listing 3.1.

ASYNCHRONOUS means it should be propagated opportunistically any time by the runtime.

Algorithm 1 summarizes this design and provides the priority P (T ) for a given task T of hint H(T ) depending on the parameters VALUE and PROPAGATION. The routine Successors returns the set of successors for the given task.

Remark Configuration (COPY, NONE, _) corresponds to GCC and LLVM interpretation of the priority clause. return max({P (S) -1 | S ∈ Successors(T )})

Implementation of Priority Support in the MPC-OMP Runtime

Back in 2019, the original MPC-OMP runtime used to ignore the priority hint at all. This lead us to propose an implementation following the design we just introduced. First, to sort-out tasks following their priorities, we implemented a red-black tree data structure following Chapter 13 of [START_REF] Cormen | Introduction to Algorithms[END_REF]. It is a binary search and self-balancing tree that can perform operations (search, insert, delete) with O(log 2 n) time and O(n) memory complexity, where each node of the tree is a list of tasks with the same priority. Fig. 5.3 depicts tree example where the root node contains the tasks T 3 and T 8 with priority 5. Whenever a task must be elected from a red-back tree, the runtime first selects the list with most priority (list 9 in the example), and then pops a task following a "First In, First Out" (FIFO) or "Last In, Last Out" (LIFO) strategy, that can be configured at launch with an environment variable.

We replaced MPC-OMP original task lists with red-black trees of 4 types that can be placed on different topological levels as shown in Fig. 5.4.

• NEW trees placement is configurable: in the example, they are placed per NUMA domain.

It stores ready tasks with no predecessors.

• SUCCESSORS trees are placed on the lowest topological level (one per core), storing ready tasks successors of previously completed tasks on that core to favor temporal locality as in [START_REF] Virouleau | Using data dependencies to improve task-based scheduling strategies on numa architectures[END_REF],

• TIED trees are also placed on the lowest topological level, storing suspended tied tasks,

• UNTIED trees placement is configurable: in the example, they are placed per socket. It stores suspended untied tasks.

Algorithm 2 summarizes which tree is elected whenever a task has to be queued. if T is tied then

3:
Queue in TIED tree of the current core Queue in UNTIED tree of the current core 6: else 7:

if T has no predecessors then 8:

Queue in NEW tree of the current core Queue in SUCCESSORS tree of the core on which T last predecessor completed Note that each couple (C, TYPE) with C a core and TYPE a red-black tree type identifies a unique red-black tree in the topology in the path from C to the root node: for instance on Fig. 5.4, (3, NEW) identifies the NEW tree of NUMA 2. Algorithm 3 presents the decision taken by a thread executing on core C whenever a new task is scheduled. The pop routine pops the task from the list with most priority of the red-black tree identified by the couple (C, TYPE). The steal routine steals work into trees of type TYPE from core C. Regarding the ASYNCHRONOUS propagation mode, we implemented it so that any thread can (2) computing and back-propagating priorities to parent tasks in the TDG. On line 20, we do not allow ready tasks to change priority. The reason is the work-first principle: the propagation only occurs when threads are idling. Updating a task priority would mean popping it off queues and reinserting it back, which would prevent another worker from scheduling the task during the priority update. Following the same principle, our implementation of this algorithm also embeds a stopping criterion: if enough tasks are ready, the propagating thread breaks.

Evaluation

In order to evaluate impacts on performance of our task priority management, we made the micro-benchmark in Annex 8.3. On this benchmark, each thread creates 1, 000, 000 empty tasks with a priority set using the system pseudo-random number generator. Note that this benchmark is among the worst case scenario, as (1) we are running empty tasks, hence emphasizing runtime structures contentions; and (2) setting a random priority p ∈ [0; 2 31 -1], so its very likely that every tasks has its own priority, hence a red-black tree with 16,000,000 nodes. We compile it with GCC 13.2.0 and executed it on 16 AMD EPYC 7H12 cores with 16 threads bound 1:1 to cores. We set the OMP_MAX_TASK_PRIORITY environement variable to INT_MAX (2 3 1 -1) and execute in two modes to compare against GCC 13.2.0 and LLVM 16.0.0 runtime implementations:

• no-priority with (VALUE, PROPAGATION, SYNCHRONY) = (ZERO, NONE, SYNCHRONOUS). This way, every tasks are assigned a 0 priority and scheduled using the default LIFO policy.

• with-priority with (VALUE, PROPAGATION, SYNCHRONY) = (COPY, NONE, SYNCHRONOUS). This way, task copy the passed priority value and are inserted into the thread red-black tree.

We performed 5 executions and for T in ROOTS do if T has successors then 12:

for S in Successors(T) do 13:

if S is not VISITED then 14:

Mark S as VISITED

15:

Push S to D tail

T = Pop U head 20:
if T is not queued then ▷ T is already queued, not updating its priority 21:

for P in P redecessors(T) do

22:

Update P priority ▷ Based on T priority

23:

Push P to U head much more overheads than LLVM and GCC respectively with a 3.18x and 1.78x slowdown in the no-priority mode. A second observation comparing the two modes:

• LLVM is whether deadlocking or very slow when enabling priorities, as we couldn't complete the execution.

• GCC has no overheads when enabling priorities. Our interpretation comes from its task throttling limiting only 64 tasks per threads to co-exist, which likely reduces priority management costs.

• MPC-OMP has a 2.6x slowdown when enabling priorities, as tasks requires sorting in red-black trees.

Communication-Aware Task Scheduling Strategies

As the Cholesky motivational example illustrated, favoring tasks performing MPI communications and their predecessors could improve performances. Using the new MPC-OMP priority-based scheduling infrastructure, we evaluated four priority heuristics with various intrusivity in usercode and runtimes in that direction. This work has been mostly published in [START_REF] Pereira | Communication-Aware Task Scheduling Strategy in Hybrid MPI+OpenMP Applications[END_REF] with a few more recent evaluations in the end of the section.

Guiding the Task Scheduler with Priorities

Manual 1 (MA-1) The runtime is configured with (COPY, NONE, _), and tasks performing MPI_Send communications are annotated with priority(1) on the user-code. It means ready tasks performing MPI_Send communications will always be chosen first against any other ready tasks.

Manual 2 (MA-2) The runtime is configured with (COPY, EQUAL, SYNCHRONOUS), and tasks performing MPI_Send communications are annotated with priority(1) on the user-code. It means ready tasks on a path from any roots to an MPI_Send communications will always be chosen first against other tasks.

Semi-Automatic (SA) The runtime is configured with (INF, DECREMENT, SYNCHRONOUS), and tasks performing MPI_Send communications are annotated with priority(1) on the user-code. It means that given a set of ready tasks, the closest task to any MPI_Send communications will be favoured over other tasks.

Fully-Automatic (FA) The runtime is configured with (ZERO, DECREMENT, ASYNCHRONOUS), and tasks performing MPI_Send communications are not annotated the priority clause. Instead, the MPI runtime notifies the OpenMP runtime whenever it performs an MPI_Send operation.

Then, the MPC-OMP runtime saves a task profile and automatically sets the priority to INT_MAX for future tasks with the same profile. The profile is made of tasks information such as its function pointer, its data size, its properties (tiedness, final-clause, undeferability, mergeability, if-clause), its parent task identifier, its number of predecessors, and its number of successors. As opposed to SA, FA does not require the programmer to annotate any tasks, but on the other hand, it has two limitations:

• The first tasks performing MPI_send communication (and their predecessors) will not be favored, as our OpenMP runtime has no clue about a task's content until it executes it once.

• The profile matching may lead to false-negative; for instance, the number of successors may not be fully known if tasks are being consumed as soon as they are produced.

Illustration Fig. 5.5 illustrates the task ordering on a Cholesky matrix decomposition, with the default scheduling heuristics (FIFO) with the third heuristic (SA): the redder the task, the earlier it is scheduled. Diamond tasks represent tasks performing MPI_send communication. As it can be seen on the SA ordering, the scheduler favors tasks leading to these communications, while the FIFO heuristic lead to a breadth-first scheduling. These figures illustrates that the SA heuristics manages to favor not only tasks performing MPI_Send but also their predecessors.

Evaluation

Fig. 5.6 shows the impact of cores spreading between MPI and OpenMP on the performance, varying scheduling heuristics, using the median over 20 executions. Note that the amount of computational tasks on each configuration remains constant: there is precisely 2,829,056 computational tasks distributed across MPI processes, while the number of communication increases with the number of MPI ranks. Table 5.2 shows the total number of point-to-point MPI requests in total (receive and send), with one request per OpenMP task. These results show that the scheduling heuristic used can have a significant impact on performance in the presence of MPI communications.

Overall Performances The MA-1 and MA-2 heuristics do not improve performances over the reference FIFO policy, but SA and FA do, respectively by 20% and 14%. It means that only favoring ready communication tasks is not sufficient, but their predecessors must be favoured as well. Note that the performance gain is directly reflected in idleness reduction, as MPI processes spend less time synchronizing due to earlier communication posting. Even though FA improves performances, it is never as good as SA for the two limitations mentioned previously.

Idleness As a general observation, increasing the number of MPI processes seems to increase the average idleness, likely due to the increase in the number of MPI synchronizations as heuristics SA and FA attenuate this phenomenon.

Work time On each spreading, threads are bound 1:1 compactly to the NUMA domain; which means on the 16-48 spreading, the 48 OpenMP threads are bound on 2 different 24-cores NUMA domain. Inter NUMA domain memory accesses likely is the source of the work time inflation observed [START_REF] Olivier | Characterizing and mitigating work time inflation in task parallel programs[END_REF], as work stealing may lead tasks' successors to migrate between NUMA domains. On the other spreadings, the work time remains about the same, independently of the heuristic used.

Overhead While overheads seem slightly higher on the FIFO, MA-1 and MA-2 heuristics, the actual reasons are not fully understood yet. A potential explanation could be the contention while accessing runtime internal data structures: the more idleness, the more concurrency on accesses. This behavior is specific to the MPC-OMP runtime, where threads almost never sleep at the kernel level and perform a lot of active waiting.

Another More Recent Evaluation

The previous experiment were conducted at the beginning of this thesis in 2021. We reproduced the experiment in 2023, but using an updated version of MPC-OpenMP, and switching from MPC-MPI to OpenMPI 4.1.5. We only reproduced the configuration with 32 MPI processes of 24 OpenMP threads each. Table 5.3 depicts the results: the first column is the scheduling parameters, the second and third column are the TDG execution (makespan) and discovery time; and the last three columns provide the time breakdown averaged on threads. We provide the median time for each value and its standard deviation over the 20 runs. These results validate previous results obtained in 2021, but gains on idleness and overall performances are smaller. A first reason is that we switched from MPC-MPI to OpenMPI, that ultimately lead us to detect a performance issue in the MPC-MPI runtime related to communications route creation. A second reason is that overheads also significantly reduced since 2021, likely due to the MPI runtime switch but also with MPC-OMP runtime improvements over the 2 years.

Mode

The SA configuration inflates the discovery time (about 36%) over the no priority configurations, explained by the synchronous priority propagation in the TDG by the producer thread. It also inflates the work time by about 5% which reasons remains to be investigated. The FA configuration slightly inflates the discovery time (about 14%) over the no priority configurations, likely because of runtime lock contention between the asynchronous priority propagation occurring in parallel of the discovery.

In both the SA and FA versions, performances gain (makespan) are explained by reducing idleness on cores, most likely because favoring tasks performing MPI_Send operations and their predecessors reduces idleness from remote data missing, as shown in the motivating example previously.

Related Works

OpenMP as a Low-Level Parallel Runtime OpenMP is used as a low-level back-end runtime for intra-node parallelization of higher-level programming models such as Kokkos [START_REF] Trott | Kokkos 3: Programming Model Extensions for the Exascale Era[END_REF] or Raja [START_REF] Beckingsale | Raja: Portable performance for large-scale scientific applications[END_REF], PGAS (XcalableMP [START_REF] Murai | XcalableMP programming model and language[END_REF]), or Domain Specific Languages/Abstraction (DSL/DSA) ( Devito [START_REF] Luporini | Architecture and Performance of Devito, a System for Automated Stencil Computation[END_REF], Nablab [START_REF] Benoit Lelandais | Fostering metamodels and grammars within a dedicated environment for hpc: The nablab environment (tool demo)[END_REF]). They provide a higher abstraction that allows programmers to write codes without low-level parallel considerations. In the specific case of DSL using MLIR [START_REF] Lattner | MLIR: Scaling compiler infrastructure for domain specific computation[END_REF] compilers, OpenMP is easily targetable, and merging/suspending tasks can be achieved. Our extensions on task context and suspensipn could be used in the code generated as a portable and low-overhead solution for suspending/resuming tasks until the completion of an external asynchronous event.

Scheduling Tasks in a Non-Uniform Memory Space Non-Uniform Memory Accesses (NUMA) architectures are now widely adopted by GPPs equipping supercomputers. This had lead to several works on the scheduling of tasks on such architectures [START_REF] Virouleau | Using data dependencies to improve task-based scheduling strategies on numa architectures[END_REF][START_REF] Stephen | Openmp task scheduling strategies for multicore numa systems[END_REF][START_REF] Drebes | Topology-Aware and Dependence-Aware Scheduling and Memory Allocation for Task-Parallel Languages[END_REF]. Olivier et al. [START_REF] Stephen | Openmp task scheduling strategies for multicore numa systems[END_REF] showed that hierarchical task scheduling with respect to the hardware topology can significantly impact performances. Debres et al. [START_REF] Drebes | Topology-Aware and Dependence-Aware Scheduling and Memory Allocation for Task-Parallel Languages[END_REF] proposed a joint scheduling and memory allocation algorithm, mixing a memory allocator with a work-stealing strategy, for task-parallel programs execution on NUMA systems. Virouleau et al. [START_REF] Virouleau | Using data dependencies to improve task-based scheduling strategies on numa architectures[END_REF] presented runtime strategies for scheduling dependent OpenMP tasks on NUMA architectures. In particular, they draw the conclusion that both the topology and the initial task data placement impact performances.

User-Level Threads Scheduling While GNU/Linux and its (kernel) pthread implementation is now equipping most supercomputers, other implementations were proposed. In particular, the SunOS [START_REF] Powell | SunOS Multi-Thread Architecture[END_REF]. (later known as "Solaris") provided a support of the PTHREAD_SCOPE_PROCESS pthread scope; said differently, it implemented a user-level threading pthread-compliant library with lightweight overheads.

The Parallel Multi-threaded Machine (PM24 ) is a distributed multi-threaded programming environment. Its original design (1995) consisted in Marcel (its threading library) and Madeleine (its communication library) [START_REF] Raymond | Contribution à la conception de supports exécutifs multithreads performants[END_REF]. Similarly to MPI, a PM2 program is replicated across a cluster of compute node, where each PM2 process can communicates to one another. Back in 1997, the PM2 environment already proposed the co-scheduling of user-level threads to reduce threading management overheads.

The Multi-Processor Computing runtime (MPC) [START_REF] Perache | Mpc: A unified parallel runtime for clusters of numa machines[END_REF] implements virtual processors (VPs) with kernel threads, which can schedule MPI processes, OpenMP threads or even pthreads as user-level threads (MPC threads) on top of it. MPC threads are slightly more rigid than OpenMP tasks, and re-using MPC threads for the tasks execution context management would have implied important modifications of MPC threading layer: for instance, load balancing of MPC threads on VPs is much more limited than OpenMP tasks work-stealing strategy between OpenMP threads [START_REF] Clet-Ortega | Evaluation of openmp task scheduling algorithms for large numa architectures[END_REF].

Argobots [START_REF] Seo | Argobots: A lightweight low-level threading and tasking framework[END_REF] is a low-level threading and tasking library. Authors conducted an important set of evaluations on user-space execution context management costs, and proposed several optimizations (such as « Not saving the context of terminating ULT ») that we could be integrated into MPC to reduce execution context management costs. The Bolt [START_REF] Iwasaki | Bolt: Optimizing openmp parallel regions with user-level threads[END_REF] OpenMP runtime implements its threads using Argobots. The task execution context extension we proposed could be implemented with Argobots fibers, but bridging the two worlds (OpenMP tasks, and Argobots fiber) would likely raise a few difficulties.

Conclusion

By nesting MPI communications into OpenMP tasks, programmers can differ the responsibility of overlapping, progression, and early-posting of MPI communication to the OpenMP task scheduler. However, current standard and implementations have limitations that makes it hard to achieve in practice. In this chapter, we have presented several extensions (in the OpenMP standard and runtimes) towards the automation of interactions between MPI and OpenMP to improve task-based hybridization.

In shorts:

• Tasks can be attached a user-level threads so they may suspend at any point of their execution without blocking the executing threads as per-before.

• A standard interface had been proposed for suspending/resuming tasks until the completion of an asynchronous operation. As opposed to existing interfaces, it goes towards standard OpenMP interface to be used by runtimes, hiding the suspension/resumption burden from applications developers.

• MPI progression callbacks can be registered into the runtime and raised at different execution point (such as scheduling points) of the runtime scheduler. This approach ensures weak progression of MPI communications in-between the task scheduler decisions, and the resumption of suspended tasks.

• We proposed a design and an implementation for task priorities in OpenMP, that not only favor annotated tasks (as currently) but also their predecessors. Performances results on the heuristics evaluations have shown that priority propagation to predecessors is necessary to ensure actual early-bird posting of MPI communications.

Ultimately, all these extensions lead us to show slight performance improvements on a Cholesky factorization, as we compared scheduling heuristics with various level of automation for programmers. Results show that early-bird posting slightly improve performances over naive breadth-first or depth-first scheduling, by reducing idleness that was mostly likely due to remote data being sent lately.

Chapter 6

Enabling Dependent Tasking in HPC Applications While state-of-the-art solutions enable working task-based hybridization, few applications migrated towards a task-based composition. At least one attempt led to convincing performances with the porting of the Cholesky factorization by J. Schuchart and al. [START_REF] Schuchart | The impact of taskyield on the design of tasks communicating through mpi[END_REF]. Other attempts whether failed to implement functional applications due to interoperability issues [START_REF] Meadows | Openmp tasking and mpi in a lattice qcd benchmark[END_REF], had to tinker application codes [START_REF] Richard | Fine-grained mpi+openmp plasma simulations: Communication overlap with dependent tasks[END_REF] to sequentialize communications or added coarse barriers losing potential communication overlap [START_REF] Massimo | A task programming implementation for the particle in cell code smilei[END_REF]. The lack of applications comes from the difficulties to reach functional and high-performance codes using a task-based composition of the current standards and their runtime implementation.

In the introduction of this manuscript, we declined these difficulties in three sources all tied together: Performances, Profiling, and Programming. Our work investigates these difficulties jointly and provides pieces of answers to each. Chapter 4 presented an hybrid profiler providing answers profiling and performances difficulties. Chapter 5 proposed an important set of extensions to improve both programming and performances aspects, that we evaluated on small benchmarks. In the Chapter 6, we pursue this work on applications more realistic of scientific simulation codes. Firstly, we present the porting of the HPCG benchmark and the LULESH proxy-application; with a few standard extension proposal during our journey that shall ease future applications porting. Then, preliminary evaluations of the ported applications guided us towards investigating impacts on the task dependency graph discovery on performances; and yet again to extend the standard and runtime.

Porting Irregular Applications with Task-based Programming

Production scientific codes are usually complex and closed-source codes. Therefore, computer scientist bases their research on benchmarks and proxy-applications. Benchmarks are usually small codes to assess raw computational power. Proxy-applications model production scientific simulations extracting their critical components to smaller and simpler open-source codes. Proxy applications aim to explicit scientific simulation needs to help design hardware, programming models, and end-codes.

The High-Performance Conjugate Gradient (HPCG [START_REF] Dongarra | High-performance conjugate-gradient benchmark: A new metric for ranking high-performance computing systems[END_REF]) benchmark and the Livermore Unstructured Lagrangian Explicit Shock Hydrodynamics (LULESH [START_REF] Karlin | Lulesh programming model and performance ports overview[END_REF]) proxy-application are two mainstream HPC use-cases Both original codes were parallelized with OpenMP workshare loops (# pragma omp parallel for) and MPI non-blocking and non-persistent communications. This section introduces in detail each application, and presents our porting experience towards the task-based composition of MPI and OpenMP, restricting our use of the standard as follows:

• The entire program runs into a parallel and a single region.

• The single thread discovers the application parallelism using the task and taskloop construct and the depend clause. Therefore, the task graph discovery occurs on a single producer thread concurrently and in parallel with its execution by every thread (including the producer). Note that using the depend clause on the taskloop construct is not allowed by the standard specifications, but our use follows the proposal made by M. Maroñas et al. [START_REF] Maroñas | Openmp taskloop dependences[END_REF].

• The computation is distributed through MPI, and communications are nested into task regions, inserted into the task dependency graph as any other tasks.

Remark At some point, we considered extending our use of the OpenMP standard to the teams construct, typically placing a single MPI process and OpenMP runtime per compute-node and one team per NUMA domain. This way, we could 1/ dampen the number of MPI processes furthermore and 2/ remove shared-memory messages. Yet, it implied important programming efforts; while 1/ the number of MPI processes has never shown to be limiting in the experiments of this thesis, and 2/ MPI implementations are already capable of automatically detecting and optimizing shared-memory message passing [START_REF] Hoefler | Mpi + mpi: A new hybrid approach to parallel programming with mpi plus shared memory[END_REF]. Therefore, we keep extra levels of partitioning as future optimization work, which could be, for instance, through the OpenMP team construct or new constructs such as hierarchical tasking [START_REF] Planas | Hierarchical task-based programming with starss[END_REF][START_REF] Mathieu Faverge | Programming Heterogeneous Architectures Using Hierarchical Tasks[END_REF].

Conjugate Gradient (HPCCG)

The High-Performance Linpack1 (HPL) [START_REF] Dongarra | The linpack benchmark: past, present and future[END_REF] and the High-Performance Conjugate Gradient2 (HPCG) [START_REF] Dongarra | High-performance conjugate-gradient benchmark: A new metric for ranking high-performance computing systems[END_REF] are two complementary benchmarks for assessing on a supercomputer performance. Both benchmarks resolve linear system A.x = b and provides a Flops/s metric corresponding to the number of floating point operations (additions, multiplications) performed per second. However, HPL performs dense algebra (few zeroes in matrices) algebra with regular memory accesses; while HPCG performs sparse algebra (elements are mostly zeroes) with irregular memory accesses. This makes the HPL compute-bound and HPCG memory-bound on most systems; respectively meaning respectively that HPL execution time is mostly determined by the CPU speed, while HPCG execution time is mostly determined by memory accesses speed. In term of raw performances, it results in HPL computing 85x (on Frontier) and 27x (on Fugaku) more Flops/s on HPL against HPCCG.

The HPCG benchmark implements the Conjugate Gradient method depicted on Algorithm 5. It consists of a sequence of dot products (dot), scaled vector addition (axpby), and sparse matrix-vector multiplication (SpMV). Each operation is implemented with element-wise loops and originally parallelized using the parallel for construct as shown on Listing 6.1.

r 0 ← b -A.x 0 3:
if r 0 is small-enough then ▷ for a given norm

α k ← r k •r k p T k .A.p k 9:
x k+1 ← x k + α k .p k 10:

r k+1 ← r k + α k .A.p k 11:
if r k+1 is small-enough then

β k ← r T k+1 •r T k+1 r T k •r T k 14: p k+1 ← r k+1 + β k .p k 15:
k ← k + 1

Task-based Porting of HPCCG

The task granularity is a critical parameter to reach high performances with task-based applications: finely tuning the granularity is necessary to balance tasking management costs with expressed parallelism [START_REF] Virouleau | Evaluation of openmp dependent tasks with the kastors benchmark suite[END_REF][START_REF] Gautier | On the impact of openmp task granularity[END_REF]. To do so, we cut each of the three algebraic operations into sub-operations over vector/matrix blocks (or "tiles"), and assigning one or more blocks to tasks. We cut operations using two parameters (T 1 , T 2 ) ∈ N while preserving the correct order of execution by inferring dependencies on block data accesses, as shown on the following equations. Let

(A i,j ) ∈ M n (R), (x i ) ∈ R n , (y i ) ∈ R n , (w i ) ∈ R n , T 1 ∈ 1 . . n and B 1 = ceil(n/T 1 ), T 2 ∈ 1 . . B 1 and B 2 = ceil(B 1 /T 2) (α, β) ∈ R 2 ,
then dot products are computed as .

n ∑ i=1 x i y i = T 1 -1 ∑ t 1 =0 min(n,(t 1 +1)B 1 ) ∑ i=t 1 B 1 +1 x i y i = α ⏞ ⏟⏟ ⏞ # pragma omp task depend(in: x[t 1 B 1 ], y[t 1 B 1 ]) depend(out:α) ( 6
# pragma omp task depend(in: x[0], x[0], x[4]) depend(inoutset: y[0]) { y[0] = A[0][2].x[2] y[1] = A[1][1].x[1] + A[1][5].x[5] }

Matrix/Vector Multiplication

∀t 1 ∈ 0 . . T 1 -1 , I 1 := t 1 B 1 + 1 and I 2 := min(n, (t 1 + 1)B 1 ) ∀i ∈ I 1 . . I 2 , w i = αx i + βy i ⏞ ⏟⏟ ⏞ # pragma omp task depend(in: x[t 1 B 1 ], y[t 1 B 1 ]) depend(out: w[t 1 B 1 ]) (6.2) SpMV with ∀i ∈ 1 . . n , z e (A, i) = {j ∈ 1 . . n | A i,j ̸ = 0} z b (A, i) = {t 1 B 1 | t 1 B 1 ≤ j < (t 1 + 1)B 1 | j ∈ z e (A, i)} as ∀t 1 ∈ 0 . . T 1 -1 , ∀t 2 ∈ 0 . . T 2 -1 , I 1 := t 1 B 1 + t 2 B 2 + 1 I 2 := min(n, min(t 1 B 1 + (t 2 + 1)B 2 , (t 1 + 1)B 1 )) ∀i ∈ I 1 . . I 2 , y i = ∑ j∈ze(A,i) A i,j x j ⏞ ⏟⏟ ⏞ # pragma omp task depend(in: x[k] so that k ∈ ⋃ i∈ I 1 . .I 2 z b (A, i) ⏞ ⏟⏟ ⏞ not real code ) depend(inoutset: y[t 1 B 1 ]) (6.3)
Remark Our implementation does not balance the number of non-zeroes element between tasks. Though, each line of the matrix has consecutive 27 non-zero elements per line in the reference version of HPCCG, meaning that

∀i ∈ 1..n , ≤ Card(z b (A, i)) ≤ 27 Sets z b (A, i) | 1.
.n are indices of the vector blocks for which the matrix has non-zero elements in an SpMV multiplication: they are computed only once on the initialization. Fig. 6.1 illustrates each task for n = 8 and T 1 = T 2 = 2, and depicts the first task of each operation, that is, for t 1 = t 2 = 0. In this example, computing the first block of y, z b (A, 0) ∪ z b (A, 1) = {0, 4} are the two x blocks for which A has columns with non-zero elements, hence the dependencies on x[0] and x [START_REF] Meadows | Openmp tasking and mpi in a lattice qcd benchmark[END_REF]. The main programming difficulty faced when porting the HPCCG application to task-based OpenMP was on expressing irregular dependencies. While expressing regular dependencies is rather straight-forward with OpenMP (dot 6.1 and waxpby 6.2), expressing tiled-irregular dependencies is more challenging. 3) must be computed and placed into a list, iterating on it using OpenMP iterator within a depend clause, as shown on Line 7 for Listing 6.2. Lines 1 to 4 are executed once on the matrix initialization, placing column block indices with non-zero elements consecutively into a C++ std::list, for the matrix lines k to k2. On the first SpMV block (k = 0) of the example Fig. 6.1, the list would be [0, 0, 4] as it depends on the x vector blocks starting at indices 0 and 4. The block 0 appearing twice in the list is said redundant. Redundant dependencies are not programming errors of the OpenMP standard, and the runtime is capable of filtering them out. However, it unnecessarily and repetitively stresses out the runtime on every iteration. On a second implementation, we simply replaced the C++ list with a std::set as shown on Listing 6.3; filtering-out redundancies once for all on matrix initialization in the 6.1. PORTING IRREGULAR APPLICATIONS WITH TASK-BASED PROGRAMMING 75 user-code, so there are no redundancies passed to the runtime on a task construct.

The Impact of Redundant Dependencies

Task dependencies management is a significant source of overheads for processing dependent tasks with OpenMP [START_REF] Gautier | On the impact of openmp task granularity[END_REF]. We experimented to evaluate its impact on performance. Table 6.2 presents results on 16 AMD EPYC 7H12 cores on a matrix of size n = 262, 144 with T 1 = 16 and T 2 = 1.

Columns present the number of dependencies passed to the runtime, the task graph creation time, and the task graph execution.

Row (a) presents measurements for the reference parallel-for HPCCG implementation (hence with no explicit tasks nor dependencies). Row (b) uses task with redundant and perscalar dependencies, meaning one distinct dependency is expressed for each memory address accessed by the task. Row (c) uses task with redundant and tiled dependencies, meaning there is one dependency expressed for each memory address accessed by the task, pointing to the vector/matrix block of that address (and so, likely many redundancies). It corresponds to the previous Listing 6.2. Row (d) uses tasks with no redundant and tiled dependencies, meaning one dependency is expressed for each vector/matrix block accessed by the task. It corresponds to the previous Listing 6. [START_REF] Vinicius | A Visual Performance Analysis Framework for Task-based Parallel Applications running on Hybrid Clusters[END_REF] Using per-scalar task dependencies leads to a 752x slowdown over the reference version due to higher task discovery costs. Tiling dependencies slightly improved performances reducing the slowdown to 157x ; but filtering redundancies was the key to reaching reasonable performances (1.09x slowdown). The runtime has several less order of magnitude dependencies to process, resulting in faster task creation.

Automating Filtering with an API Extension

As previous results suggest, removing redundancies and tiling irregular dependencies is crucial for performances. OpenMP provides the depobj interfaces for pre-allocating dependencies, that can then be passed several time to the same task through the depend clause. While it looks like a good candidate for such dependency scheme (for instance, filtering redundancies and tiling only once for all at matrix initialization), its current restrictions currently makes it impossible in practice. Therefore, we propose the following extensions and restriction relieves so that Listing 6.4 becomes standard-compliant.

• [START_REF] Boekholt | Multi-physics simulations in astronomy[END_REF] We remove the following constraint on the depobj construct: "A depend clause on a depobj construct can only specify one locator ". On the listing, writing x[col_idx[j]/B_1*B_1] (line 3) and y[k] (line 4) on the same depobj construct is illegal currently.

• (2) We extend the depobj construct so it can have multiple dependency types. On the listing, writing on the same depobj construct both in: (line 3) and out: (line 4) is illegal currently.

• (3) We remove the 'unique' property from the iterator modifier on a depend clause. On the listing, writing two iterator in the same depend clause (line 3) is illegal currently.

Implementation and evaluation of these extensions are kept as future work, and here are a few suggestions for implementers:

• Compiler: (1) redundant dependencies should be filtered-out at compile-time if possible; and (2) the compiler shall inform the runtime with the total number of dependencies n, and an upper-bound on the number of redundancies m ∈ [0, n].

• Runtime: filtering-out redundancies consists in building a set from a sequence of n integer with m redundancies at most. A high-quality implementation should adapt to special cases such as m = 0 and m = n (yet very common in regular applications). As a matter of fact, results presented Table 6.2, SpMV tasks had 70, 116, 861 redundancies for 2 or 3 unique dependencies. Refining tasks with T 1 = 512 and T 2 = 16 (optimal grain), we had 68, 758 redundancies for 1 or 2 unique dependencies.

(3) Tasks granularity can have a significant impact over performances. Too coarse, it may lead to a lack of parallelism and important idleness; too fine, management overheads may deteriorate performances [START_REF] Gautier | On the Impact of OpenMP Task Granularity: 14th International Workshop on OpenMP[END_REF]. Fig. 6.3 presents a task grain study on HPCCG, it shows the task graph execution (left) and its discovery (right) time. The discovery is the time from the first to the last task creation, occuring on a single producer thread concurrently of its execution by any threads (including the producer). The execution corresponds to wall-clock time from the first task schedule to the completion of the last task. Each point of the figure correspond to a single run on 16 AMD EPYC 7H12 cores. We set n = 41, 943, 040 occupying 62% of the NUMA domain memory capacity over 32 iterations, varying grain parameters T 1 ∈ [16; 1536] with a step of 16 and T 2 ∈ [1, 96] with a step of 1. It means there are few coarse tasks on the bottom-left points and many fine tasks on the top-right points. Colors indicate the time: the lighter, the shorter. We observe that both the graph execution and discovery time significantly vary with the number of tasks. More precisely, we observe 3 areas:

• (1) is the execution-bound area; tasks discovery is slower than their parallel execution, and the total time is bound by tasks execution.

• (2) is the execution/discovery frontier area; tasks discovery and their parallel execution time are close, and the total time may be slowed down due to tasks being discovered too slowly.

• ( 3) is the discovery-bound area; tasks discovery time and their parallel execution time are close, and the total time is mostly bound by task discovery, and threads end up idling waiting for work to be discovered.

For this HPCCG problem, the best performances are reached in area [START_REF] Boekholt | Multi-physics simulations in astronomy[END_REF], which gives a range of efficient task grains for this problem size. We observe a rebound effect between areas (2) and (3). Going through the frontier area (2), the tasks are getting consumed as soon as they are created. It makes the producer thread prune dependency edges since predecessors no longer exist on successors' discovery. Even though more tasks are discovered in the end, this accelerates the task graph discovery as there are fewer edges created. After the reddish region ((T 1 ; T 2 ) = (1, 200; 64)), there are almost no edges generated: a sign that we reached the discovery-bound area (3). Discovery is slightly faster than within the frontier area (2); until there are too many tasks (upper-right-most corner at (T 1 ; T 2 ) = (1, 536; 96)), and refining tasks furthermore would only slow down the execution time.

Simplified Hydrodynamic Simulation (LULESH)

While benchmarks primarily focus on performances, they are not representative of 1M+ lines production codes needs in term of programming. To respond to this limitation, the Collaboration of Oak Ridge, Argonne, and Livermore (CORAL) [START_REF] Sudharshan | The design, deployment, and evaluation of the coral pre-exascale systems[END_REF] laboratory from the United States Department of Energy (DOE) provided an important set of proxy applications, parallelized hybridizing MPI and OpenMP, which are more realistic of production application codes. The original purpose was co-designing machines, codes, and programming models towards exascale, that ultimately lead to the Frontier machine. As part of this thesis, we study the Livermore Unstructured Lagrangian Explicit Shock Hydrodynamics (LULESH [START_REF] Karlin | Lulesh programming model and performance ports overview[END_REF]) proxy application. This proxy application is modeling the core of ALE3D [START_REF] Noble | Ale3d: An arbitrary lagrangian-eulerian multi-physics code[END_REF], a 3D multi-physics simulation software capable of simulating multiple physical phenomena such as heat transfers or chemistry models.

A brief introduction on LULESH

LULESH models an hydrodynamic simulation of materials motion subject to forces over an unstructured mesh. The simulation duration and the mesh can be configured with command line arguments. We briefly introduce these concepts that guided our porting to the task-based model.

Unstructured Mesh An unstructured mesh is a set of nodes connected into elements. Each node is a multi-dimensional object embedding some properties such as a position vector (x, y, z), a velocity (v x , v y , v z ) or a mass m. The mesh represents a discrete three-dimensional spatial domain, with nodes being points and hexahedrons elements representing volumetric units. On LULESH, the mesh data structure is built-in for simplicity purposes: each element is made of 8 [START_REF] Blelloch | Effectively sharing a cache among threads[END_REF]; /* set of elements pointing to 8 nodes */ } mesh_t; Listing 6.5: Simplified LULESH mesh data structure nodes represented as an indirection array, as depicted on Listing 6.5. Internally, the LULESH benchmark uses a uniform cartesian grid, but its still represented as an unstructured mesh so researches on it are applicable to more complex irregular meshes used in production simulations. The mesh is a cube partitioned into sub-cubes distributed on MPI processes; therefore the application can only runs using a cubical number of MPI processes. On each MPI rank, local mesh nodes and elements lists are ordered along axes so that nodes and elements at position (x, y, z) in the cube are placed at index x.s 2 + y.s. + z in lists.

An Hydrodynamic Simulation Zooming into the code, it looks something similar to the code Listing 6.6. Line 3, the simulation iterates until a certain amount of iterations max_iter had been executed. Then each iteration starts with a global reduction (MPI_Allreduce) to compute a dynamic time step dt on line 5 to 7. Afterward from line 9 to 19, there is multiple mesh-wide computational loops iterating, so the simulation approximates hydrodynamics equations solutions discretely onto elements. In the original version provided by LLNL, each computational loop is parallelized using # pragma omp parallel for construct, and 9 out of the 38 loops also are annotated with the nowait clause. Then at some point of the iteration (line 22 to 30), frontier nodes are exchanged between MPI processes. Each MPI process can have up to 27 neighbors connected through faces, edges or nodes; and only one layer of ghost nodes is used. Finally after exchanging, there is a few more computational loops (line 32) before the next iteration starts.

Parameters The command line argument -i controls the number max_iter of simulation iterations, and -s the mesh size. For a given size s distributed on p MPI processes, the total number of elements is p × s 3 and the total number of nodes is p × (s + 1) 3 with each MPI process working on s 3 elements and (s + 1) 3 nodes.

Reference parallel-for version

The original LLNL version of the code relies on a fork-join programming model; the computation is parallelized through OpenMP parallel for (line 10 and 15 of Listing 6.6) and distributed with MPI communications outside of OpenMP constructs: the two programming models are used separately in the code. It also comes with two reports [START_REF] Karlin | Lulesh programming model and performance ports overview[END_REF][START_REF] Karlin | Lulesh 2.0 updates and changes[END_REF] presenting how the code must be used to remain representative of production user needs. For instance, constraints include the mesh data structure representation, the loop structure, and some extra computation. In [START_REF] Karlin | Tuning the LULESH Mini-app for Current and Future Hardware[END_REF], authors show that LULESH original code is poorly optimized but reports constraints limit the applicability of their optimizations. Though, their global allocation of temporary work arrays optimization is compatible. It consists of preallocating memory buffers instead of repetitively calling malloc and free within the inner-most loops. Hence, we backported it, which increased performances by about 24% on our configuration. In future evaluation, this optimized version is used as the parallel-for reference.

Task-based Porting

With a particular attention on the two reports constraints, we ported LULESH to the task-based model composition understudy. The porting follows lessons learned from the HPCCG porting: dependencies are tiled, and redundancies are filtered once and for all on the mesh initialization.

Computational Loops

We transformed the reference version parallel for computational loops (lines 10 and 15 of Listing 6.6) to dependent-tasks generating loops (lines 11 and 15 on Listing 6.7) with consecutive nodes or elements in the original loop computed in the same task. The number of tasks generated from node-wise and element-wise loops can be configured with a command line parameter, respectively -tnl and -tel, using a num_tasks clause on the taskloop construct. Dependencies are inferred from the loop breakdown into tasks with respect to the sequential data accesses (read/write) on the mesh, ensuring a correct order of execution while still exposing as much parallelism as possible. The annex Table 8.1 presents the average grain of each task (in µs.) measured on 24 Intel(R) Xeon(R) Platinum 8168 cores for s = 384, tel = tnl = 1024, and i = 16 compiled with GCC 12.2.0.

Communications We split frontier communications into multiple MPI persistent requests with balanced sizes. Similarly to loop parallelization, consecutive nodes in lists are communicated in the same MPI request. Each MPI request is placed into an OpenMP task with appropriate dependency to ensure its correct order of execution. The number of requests per frontier can be configured with the command line argument -rpf and -rpe respectively for the number of requests per face and per edge (nodes-frontier are always made of 1 request). Note that both parameters were fixed to 1 in the rest of this thesis to fall back to the reference application coarse-grain communication pattern (-rpf=1 and -rpe=1). Fine study on communication grain is kept as future work.

Minimal Example Fig. 6.4 illustrates the mesh partitioning into tasks on a minimal example. It shows a 2-dimensional slice of the domain along the x and y axes on 8 MPI ranks (only 4 shown). In this example, parameters value are -s 2, -tnl 2, -tel 2, -rpf 1 and -rpe 1. Listing 6.7 illustrates a minimal porting to dependent tasking of Listing 6.6. On line 14, the mesh.nodes[...] refers to irregular dependencies (to be understood as: "the elements' nodes on which the task is computing"). The num_tasks clause specifies the number of tasks on loops, and the grainsize is inferred from it similarly to the for schedule(dynamic) num_tasks() construct.

Studying the Impact of Task Granularity

As HPCG, we conducted an evaluation on the impact of task granularity on overall performances. Fig. 6.5 presents results as the execution time and the task dependency graph discovery time varying grain parameters on 16 AMD EPYC 7H12 cores. We set s = 256 occupying 72% of the NUMA domain memory capacity over 16 iterations, varying grain parameters tel = tnl varying in [START_REF] Shun | 6.172 performance engineering of software systems -caching and cache-efficient algorithms[END_REF]2048] with a step of 16, increasing and refining tasks from left to right. We make three following observations on this result:

• The same three areas as of HPCCG appears, annotated with (1), ( 2) and (3) on the figure

x-axis.

• There are some specific grains where the graph discovery appears to be very slow, for instance, on tel = 1, 168 or tel = 1, 520.

• On coarse grain, the execution time is inflated to 60s and reduces to about 30s when refining tasks grain.

Investigating The Task Dependency Graph Discovery Impacts on Performances

Our third observation on the LULESH task grain was that the execution time is almost half between coarse and fine grain. There may be multiple reasons on such gain, but in particular, fine grain-dependent tasking and depth-first scheduling following the data flow can improve the use of the hardware caches [START_REF] Blelloch | Effectively sharing a cache among threads[END_REF]. Using task-based OpenMP, task dependency graphs (TDGs) can be built following the actual application data flow. Therefore, if the data accessed by a task is fine-enough to fit into cache memory, scheduling its successors onto the same core can result in faster work execution, as cached memory is at least one order of magnitude faster to access than the DRAM. However, as the dependency graph creation (its discovery) is concurrent to its execution, the entire graph is never fully known by the task scheduler at run-time. In addition, refining tasks means more nodes to be processed by the runtime, and so it may slow down the discovery. Hence, refining tasks grain and accelerating the graph discovery are two critical concepts to balance: tasks must be fine-enough so that their accessed data fit into caches, but the discovery must be fast enough to provide an in-depth vision of the TDG to the runtime scheduler to benefit from predecessors cached-memory.

Motivations on the Dependency Graph Discovery

Fig. 6.7 presents our task-based version of LULESH performances using LLVM 16 and GCC 12.2.0 filling 78% of the DRAM (-s 384 -i 16), and with default throttling parameters. Each run is performed on a single process of 24 threads bound 1:1 onto Intel(R) Xeon(R) Platinum 8168 CPU @2.70GHz cores sharing a NUMA domain. The parallel for version takes about 86s to execute with 98% work time reported by Caliper [START_REF] Boehme | Caliper: Performance Introspection for HPC Software Stacks[END_REF]. From left to right on the task-based version, the number of tasks increases, and grains are refined. Figures report the time (in seconds) for the task dependency graph execution (blue filled curve) and its discovery (green dotted curve). The discovery is the time from the first to the last task creation, occurring on a single producer thread concurrently with its execution by any threads (including the producer). The execution corresponds to wall-clock time from the first task schedule to the completion of the last task. It only depends on the scheduler and the architecture: the performance increases while refining tasks, thanks to better data reuse enabled by the depth-first scheduler, until the task discovery becomes too slow and bounds the total execution time. Regardless of the number of tasks generated per loop, the performance is at most 12.8% better than the OpenMP parallel for version using LLVM (86s vs 75s) which is not enough relative to the effort of porting the application to the OpenMP dependent task model. GCC does not report any improvements using dependent tasks because throttling cannot be adjusted and does not allow depth-first scheduling, as too few tasks can co-exist.

Profiling LULESH with MPC

In order to provide finer analysis on the performances, we reproduced the previous experiment using the MPC-OMP runtime and our profiler to compute the time breakdown and collect hardware counters. Results are shown on Fig. 6.8

Overview of the results

On each graph of Fig. 6.8, the x-axis represents the number of Tasks per Loop (TPL), fixing tel = tnl = TPL. Fig. 6.8 (a) represents the overall number of tasks and edges discovered and breakdown averaged on threads. The bottom blue stack is the work time, the middle red stack is the idle time, and the top yellow stack is the overhead. The green dotted line represents the TDG discovery time on the single producer thread. Fig. 6.8 (d) shows the work time inflation of each TPL instance using the TPL instance with the shortest work time as a reference. Fig. 6.8 (e,f) respectively depicts the number of misses and stalled cycles per cache level occurring when cores execute task work.

Interpretation of the results

Coarse grain We observe that the left-most point is the less inflated. Our interpretation comes from LULESH being memory-bound by the DRAM bandwidth: having only 48 tasks per loop reduces the amount of parallelism, which increases idleness on cores, as it can be seen on the time breakdown Fig. 6.8 (c). It can also be seen on the gantt chart Fig. 6.9, which shows iterations 2 and 3 of the left-most point (for TPL=48). In average, cores spends more time idling reducing the contention on the DRAM as less cores are likely to access the DRAM in parallel, which ends up accelerating accesses of the few actual cores working.

Middle grain From 192 to 1,872 TPL, on Fig. 6.8 (d), the work time deflates significantly from 40% inflation to 10%. Fig. 6.8 (e,f) provide an explanation: on this TPL range, we observe a reduction of L3 cache misses (L3CM) and stalled cycles due to cache-miss. Whenever a data access causes an L1DCM or an L2DCM, the memory controller will more likely find the data in the L3 memory without having to retrieve it from the DRAM. It accelerates memory access with fewer process stalls, hence the observed work time deflation. This better use of the memory hierarchy is the result of two tasking mechanisms: (1) task refinement reduces average data size accessed per task, and (2) the depth-first scheduling heuristic favors the execution of tasks' successors, improving cached-data reusability.

Fine grain After 1,872 TPL, the application execution time is bound by the TDG discovery time. Many edges are pruned because tasks are getting consummed as soon as they are produced and no longer exists on their successors' discovery, as it can be seen on Fig. 6.8 (a) This is also reflected by an increase in the idle time on Fig. Overlapping TDG discovery with its execution has an impact on the task scheduler that promotes data reuse: if the TDG discovery is too slow, the data-producing task will never activate its successor as it has not been discovered yet. To measure the impact of the TDG discovery on its execution time, we run a complementary experiment blocking execution by threads until the TDG has been fully discovered so that the MPC-OMP scheduler has access to the description of all the dependencies before making decisions. Table 6.3 shows the cumulated work and idle time on threads, the number of L2 data cache misses, and L3 cache misses on different configurations. Instances with tag concurrent correspond to execution with TDG concurrent execution and discovery of the TDG. The Instance with tag non-concurrent means the graph is first fully discovered before starting its parallel execution. The two first rows present results from the best (1,872 TPL) and finest (4,608 TPL) grain execution shown on Fig. 6.8, under the concurrent configuration. The third row presents results with 4,608 TPL with the non-concurrent configuration. Comparing the two configurations with 4,608 TPL, in-depth knowledge of the TDG leads to significantly reducing the cache misses in L2 (-15%) and L3 (-42%) for a 32% work time reduction. We also observe almost no idleness, as threads do not have to wait for tasks to spawn. Work time and idleness gain lead to a 40% parallel execution time reduction. Though, the total execution time is still much slower in the non-overlapped configuration because the entire graph must be unrolled sequentially first: 357s with the non-overlapped experiment and 112s for the normal execution.

Summary

In this section, we presented an analysis of the gains from a task-based LULESH against the parallel for version. The task-based version executes in 69s with MPC-OMP against 86s for the parallel for version on LLVM 16. We measure a minimal time and work time at TPL=1,872, showing the importance of refining tasks until the TDG discovery speed becomes too limiting. Moreover, we also report that accelerating the TDG discovery on the task-based version would:

• allows reaching finer task grain so accessed data fits into the L2 cache level, which could reduce work time by 37% with effective depth-first scheduling.

• slightly reduces idleness as more parallelism is discovered.

Therefore, in the following section, we propose various techniques and evaluations for accelerating the TDG discovery.

Accelerating the Dependency Graph Discovery

As the TDG discovery speed is a limiting factor to reach high performances, we explored way to accelerating it. In this section, we present OpenMP TDG discovery optimizations on OpenMP on runtime and user codes. Some of them are standard, but we also propose an extension caching internal tasks data structure (or task persistence) with very lite intrusive cost in terms of user code modification. Altogether, optimizations accelerate the TDG discovery, and we report their individual impact on performances in the evaluation Table 6.4.

Reducing the number of edges

In the TDG, an edge corresponds to a precedence constraint between two tasks. Because of the sequential task submission and the very local view (per-procedure) of tasks, some unnecessary edges may appear between tasks which the correct order of execution is already guaranteed from other edges. Removing these edges can accelerate the TDG discovery: we present three optimizations in this direction. The optimization (a) is depicted in Fig. 6.10a. It consists in minimizing the number of dependencies expressed from the user code, preserving both the parallelism and the correct order of execution. In this example, task line 1 writes (x, y), which is only read by task line 8. This provides two data addresses to be processed by the runtime while only one is really needed. Such dependency pattern appeared in our original porting of LULESH in [START_REF] Ferat | Enhancing mpi+openmp task based applications for heterogeneous architectures with gpu support[END_REF]. It consists in suppressing multiple dependency edges between the two same tasks automatically by the runtime. The function link corresponds to the runtime procedure whenever an edge is created from the task pred to succ, by inserting succ to pred successors' list. Because of the sequential task flow semantic of OpenMP, multiple edges can be detected with a simple O(1) comparison, as if multiple edges are being generated, then succ is necessarily the last task inserted in pred successors' list. The highlighted code was added to the runtime, and perform such checking before inserting it. Note that optimization (a) differs from (b) in the sense that it not only merges multiple edges but also the cost of processing and detecting them in (b). This optimization is implemented into GCC 12.2.0 but not into LLVM 16: we implemented it in MPC-OMP. The optimization (c) is related to the inoutset dependency type. Tasks t i having a depend clause of type inoutset on the same data can run concurrently, but successor tasks with any other dependency type on the same data will depend on every t i task. This dependency type is also known as concurrent write in Athapascan [START_REF] Galilée | Athapascan-1: On-line building data flow graph in a parallel language[END_REF], Kaapi [START_REF] Gautier | Xkaapi: A runtime system for data-flow task programming on heterogeneous architectures[END_REF] or OmpSs [START_REF] Fernández | Task-based programming with ompss and its application[END_REF], and expresses that multiple tasks can write concurrently in a memory block. This knowledge can be used by the runtime for optimizations on the TDG edges. Fig. 6.11 depicts a minimal example of an inoutset dependency scheme where m tasks (X i ) i∈ [1,m] concurrently write onto the vector x which is read by the n tasks (Y j ) j∈ [1,n] . The optimization (c) consists in inserting an extra empty control-flow node R by the producer thread on the first inoutset for a given data, reducing the number of edges from m.n to m + n. This optimization had been implemented in LLVM 4but not into GCC: we implemented it in MPC-OMP. Scientific simulations often are iterative applications with similar existing parallelism over iterations. For instance, LULESH is a simulation on an unstructured mesh, and the task dependencies are built upon the mesh nodes and elements that do not change over iterations. To accelerate the TDG discovery furthermore, we propose an original interface and runtime implementation that adds persistence to tasks and edges. Looking back at OpenMP tasks transition system (see Fig. 3.2), persistence means adding a transition 8 → 1 .

m.n edges ... Y 1 Y 2 Y n ... X 1 X 2 X m m+n edges ... X 1 X m X 2 R Y 1 Y n Y 2 .
Implementation The optimization (p) is illustrated on Listing 6.10, and from a programmer's point of view, it only consists in annotating a loop generating dependent tasks in the same order and with the same dependency scheme on each iteration (line 1). Listing 6.11 shows the code generated by the pragma. Line 1, the mpc_omp_persistent_region_begin initializes a persistent region. Then on the first loop iteration, the application TDG is discovered just as before, but:

• Marking tasks as persistent, so they are not destroyed on completion,

• Putting tasks in a list L sorted by their discovery order.

• Creating every edge, as opposed to the non-persistent mode, which would prune edges from tasks already consumed: since no edges are created on the next iterations, generating every edge ensures the correct order of execution with no race conditions on the discovery. It also makes the first iteration of persistent TDG discovery slightly more costly than its non-persistent version.

In every iteration, the mpc_omp_persistent_region_iterate waits for the completion of every persistent task previously instantiated, and moves a pointer p to the beginning of L. On the next iterations, the producer thread executes the same execution flow, but on a task construct, it only:

• Retrieves the persistent task t pointed by p and increment p,

• Copies t firstprivate data (such as the loop iter variable),

• Transition t to a queuable state, Persistence relieves the runtime from other tasking overhead sources such as the internal task descriptor allocation, dependencies processing (depend clause), or Internal Control Variable (ICV) management. Therefore, a task initialization cost is reduced to a single memcpy on firstprivate data, representing 8 to 100 bytes in LULESH tasks. An implicit barrier at the beginning of each iteration ensures that every task is completed before re-instancing them.

Remark Coupling optimization (c) with (p) required a specific treatment by the runtime, as the control-flow tasks inserted by (c) are not only discovered by the producer thread once when processing dependencies on the first iteration. Instead, control-flow tasks are re-instantiated by the first consumer thread that executes one of its inoutset predecessors of the current iteration.

Applicability A persistent task graph assumes that dependencies between tasks remain constant over iterations. However, on simulation over unstructured meshes like LULESH, Adaptive Mesh Refinement (AMR) may occur at some point, slightly changing the mesh. Nevertheless, because of the inherent costs of mesh adaptation, simulations try to amortize it over a few iterations. The persistent task graph could be invalidated when AMR occurs so that the producer thread re-construct is entirely on the next iteration. Such an approach would allow fast integration of persistent task graphs into existing applications with this already existing strategy every few iterations. On the other hand, AMR only slightly changes the mesh, and it may be unnecessary to rebuild the entire graph, as only a small portion of the nodes and edges may have changed. Removing a persistent task from the TDG is rather straightforward: We even added an mpc_omp_persistent_region_pop_task API that deletes the task currently pointed by the producer thread and increments the pointer to the next task. However, inserting a new task is more complex and was not studied furthermore as part of this thesis.

Impact on user codes and runtimes

The impact of persistent TDG on user code is lite: from given task-based applications, a single line of code (LoC) annotation on a loop enabled persistence. Our implementation moderately impacted MPC-OMP runtime, adding only 175 LoC but changing critical and highly concurrent runtime code related to tasks' life-cycle.

Evaluation

Table 6.4 depicts the number of edges, the TDG discovery, the total execution time, and the work/idle/overhead time breakdown, crossing each optimization on the same problem as of Fig. 6.8 with T P L = 1, 872; for about 2.9 M. tasks of 365µs grain in average. We make the follow interpretations comparing pairs of lines: • (a) against (a)+(c) -about 800, 000 more tasks are generated, corresponding to the empty tasks of the optimization (c). However, they dampen the number of edges (n.m against n + m as shown on Fig. 6.11) for about 22, 000, 000 fewer edges. In this configuration, the execution is no longer discovery-bound, meaning that the scheduler likely manages to perform effective depth-first scheduling.

• none against (a)+(b)+(c) -enabling all optimization but (p) led to 2.04 fewer edges and 1.38 speedup on the discovery over the non-optimized version.

• (a)+(b)+(c) and (a)+(b)+(c)+(p) -enabling tasks' persistence optimization (p) drastically reduces the discovery time by an order of magnitude. Among the 5.97s of discovery, 4.11s corresponds to the first iteration discovery, and the remaining corresponds to the 15 other iterations taking 0.12s on average: the first iteration is about 34 times slower than the others, as it is the one responsible for building the dependency graph while the others simply update tasks private data. The first persistent iteration (4.11s) is more costly than non-persistent iterations (3.47s on average), and even though every edge is created (the runtime does not prune edges to tasks already consumed with persistent tasking enabled), we observe fewer edges enabling (p). This is a side effect of our runtime persistence implementation, which has an implicit barrier on each iteration, removing inter-iteration edges. Moreover, this barrier leads optimization (p) to increase the total execution time (69.17s to 70.80s): the work and idle times increase because the barrier prohibits successor tasks of iterations n + 1 from starting until every task of iteration n is completed. This is shown on the Gantt chart Fig. 6.14 where one color represents one iteration. Threads spend more time idling in this synchronization barrier, and the work time inflates as depth-first scheduling is constrained per iteration. However, as (p) accelerates the graph discovery, overheads are reduced, enabling effective depth-first scheduling at a much finer grain. Fig. 6.12 shows the same metrics as in Fig. 6.8 but enabling every optimization. The TDG execution is no longer bound by its discovery and enables effective depth-first scheduling. It leads to 1.56x speedup over the parallel for version and 1.27x speedup over the non-optimized task-based version. The 4,608 TPL configuration reaches a 1, 230s work time for 82B L2DCM and 54B L3CM.

METG report

The Minimum Effective Task Granularity metric was proposed [START_REF] Slaughter | Task bench: A parameterized benchmark for evaluating parallel runtime performance[END_REF] as a way to assess the overheads of tasking runtimes. For a given application and runtime system, (f)

Impacts on Distributed Execution

The TDG discovery speed also impacts distributed applications of applications using MPI. We evaluate three applications (LULESH, HPCG, Cholesky) with different parallel characteristics (computation, communication) that will lead to three conclusions. We performed evaluations Computational Performances Times were retrieved using our profiler for MPC-OMP and Caliper for LLVM (which only provides work/non-work times). We observe the same performance gain as on the previous architecture. The optimized task-based is 2.0x and 1.2x more performant than the parallel for and the non-optimized task-based version, for the exact same reason of hierarchical memory accesses. Note that we observe work time deflation on the non-optimized task-based version after 2,176 TPL. Above this threshold, the TDG discovery becomes too slow to feed every core (as shown by the important idleness), reducing the DRAM contention, which in turn, accelerates memory accesses of the few threads working in parallel.

Communication Overlap with Computation

The parallel for version exhibits no overlap potential on P2P send communications. All the requests are posted in non-blocking mode, and the execution flow waits for every completion before pursuing any computation. The collective is in blocking mode, posted at the beginning of a new iteration. The collective of iteration n + 1 depends on every task of iteration n. However, the Gantt chart of the task-based version on Fig. 6.14 shows that there are some independent computational tasks of iteration n + 1 such as CalcFBHourglassForceForElems ready for overlap. On the parallel for version, all this work would have been processed synchronously after the collective operation completion following the sequential instruction flow. On the task-based versions, the overlap ratio is improved when enabling optimizations and remains above 80% on any TPL against 50% on average without optimizations as shown Fig. 6.13: the application parallelism is discovered faster and more work is ready for overlap masking communication costs.

To estimate the gain from integrating MPI communications into OpenMP TDG following the data flow, we added explicit # pragma omp taskwait before and after communication sequences. This way, we reproduce the original application BSP communication pattern: every communications are posted once the entire domain is computing, meaning there is no computation/communication overlap nor early-bird posting. With the tracing disabled and on the most performant configuration (TPL=4,608), we measured 131.0s with taskwait against 121.9s with no taskwait, meaning that fine integration of MPI communications into OpenMP TDG reduced by 7% the total execution time.

On every iteration, with or without optimizations, we observe an idleness period on every thread on the Gantt chart Fig. 6.14. During this idle period, a single MPI_Irecv is blocking, and no more work is ready until its data are received. This behavior is similar to what we observed on the Cholesky factorization in Section 5.2. Therefore, we enabled our heuristic favoring send operations and evaluated for T P L = 1, 152, hoping that the MPI_Recv idleness observed on the Gantt chart may be removed due to earlier data posting remotely. Nevertheless, preliminary results have shown no improvement nor degradation on any of the work/idle/overhead metrics, likely because the default depth-first scheduling heuristic already lead to early-bird communication anyway.

Communication Time We made a breakdown of the communication time of each TPL, and on average, 94% of the communication time corresponds to the MPI_Iallreduce collective, and the remaining 6% are the 26 P2P send operations. The variation observed in the communication is, therefore, mostly related to this single collective.

Gantt charts Fig. 6.14 shows the execution of tasks from iterations 11 to 15 on the two task-based versions of T P L = 1, 152 of Fig. 6.13. Boxes represent task schedules, and each color identifies a different iteration. Time origins had been offset on each chart along the x-axis to align with the first task of iteration 12 (green). Because of the implicit task barrier on each iteration induced by our persistent TDG implementation, no tasks from iteration n + 1 can start until every task from iteration n is completed (bottom chart). Looking at the two charts, this behavior seems to inflate collective synchronization time globally. This phenomenon may explain why the (collective) communication time is faster on the non-optimized version on 128 < T P L < 1, 280. Though, it has really little impact on performances as it is getting overlapped with work anyway.

Refining from 128 to 1, 280, we also observe a reduction in communication time. We believe it comes from faster local execution (as shown on the time breakdown), allowing, on average earlier collective communication matching on every MPI process.

However, refining furthermore on the non-optimized version leads to important idleness, as the TDG discovery becomes too slow to feed every core with work. A possible explanation is that every MPI process must wait for the slowest local OpenMP TDG discovery, as results show that accelerating discovery lead to lower communication time at a fine grain.

Scaling to 65k cores

We performed a strong and weak scaling on LULESH for both the parallel for (GCC 11.2.0) and our optimized task-based version (MPC-OMP). We increased the number of simulation iterations from 64 to 1,024. Table 6.5 presents wall clock time results scaling from 8 MPI processes (= 1 node) to 4,096 processes on a single run. No performances could be recorded on the weak-scaling above 1,331 processes because all versions abort on a numerical error. The High-Performance Conjugate Gradient (HPCCG) is a benchmark used to rank supercomputers as a complement to the LINPACK (HPL) benchmarks [START_REF] Dongarra | High-performance conjugate-gradient benchmark: A new metric for ranking high-performance computing systems[END_REF]. The baseline implementation is parallelized using parallel for construct and barriers before communicating with MPI. Section 6.1.1 presented the porting of HPCG to OpenMP dependent task model with two grains parameters defining the number of block for vector-wise operations (TPL) and the number of sub-blocks for SpMV operations, that we fix to 32 in future experiments. Fig. 6.15 present our results on 32 MPI processes of 24 threads varying the TPL parameters on Intel Skylake processors.

On Communications Depending on the TPL, the communication time varies from 5 to 37 s. for an accumulated work time of around 700s. It means with perfect overlap, at most 5% of the work time would be overlapping communication. Moreover, even though TDG discovery is fast-enough, the overlap ratio remains low (≤ 23%), meaning little work is available in parallel of communications. Therefore, there is little no to gain to expect from overlapping communication with computational tasks on HPCG.

Time Breakdown Regarding work time, the best performances are reached for an average tasks grain of 80µs using the right-most 1,536 TPL. It allows 20% work time reduction compared to the baseline parallel for version. The reasons are the same as LULESH: memory accesses are faster due to better cache reuse. Even though TDG discovery optimizations were enabled, fine-grain tasks management overheads deteriorated total execution time more than the work time gain. Though, the minimal total time (30.6s) is obtained with TPL=144 (1ms/tasks) for 10% performances gain over the parallel for version with LLVM 16 (34.1s. with 95% work time). Above this grain, overheads, and idleness deteriorates more performances than the work time improvement. We explain this by the tasking runtime contention: as shown in Fig. 6.15, the number of edges per task grows linearly from 24 to 1,536 TPL while the workload per task decreases. Runtime-side, this is reflected by more threads accessing more often shared data structures, such as the task dependency graph.

Tile-based Cholesky Factorization

Tile-based Cholesky dense matrix factorization is a widely studied application of dependent task-based programming. We retrieved the version of [START_REF] Schuchart | The impact of taskyield on the design of tasks communicating through mpi[END_REF] with dependent task and MPI communications performed by tasks. Optimizations (a), (b), and (c) does not provide any performance improvement/degradation as they are not reflected in the application: its dense dependency scheme is simpler than sparse and indirection-based data structures found in HPCG and LULESH. The optimization (p) provides performance gain on TDG when iteratively decomposing matrices of the same dimensions and tile size. We evaluated the TDG discovery speed gain for a matrix of size n = 65, 536 with block sizes b = 512, distributed on 32 MPI processes of 24 cores over 16 Intel nodes. Our results showed 5x asymptotic 5 speedup on the discovery when increasing the number of iterations. It showed no significant impact on performances as the TDG discovery is already fast due to coarse tasks and regular dependencies (<2% of total time). On 16 Skylake nodes (768 cores), we measured 269s (with) and 274s (without) optimizations for matrix n=65,536 with block-size m=512.

Summary

In this section, we combined optimizations to hasten the TDG discovery. Optimization (a) is well-known, (b) is implemented in GCC, (c) is implemented concurrently to us in LLVM, and (p) is original. One contribution lies in combining them and evaluating their gain.

Then, through the LULESH case study, we analyzed the impact of the TDG discovery on performances. Our best result shows a 2.0x speedup on LULESH using OpenMP tasking over 5 the asymptotic speedup corresponds to tp tnp with tp and tnp respectively the discovery time of a persistent iteration, and a non-persistent iteration parallel for weak-scaled to 16,000 cores, thanks to task grain refinement and effective depthfirst scheduling, that were only possible by setting up a suitable task throttling and hastening the TDG discovery. Finely composing MPI and OpenMP by integrating communications into dependent tasks led to 7% execution time reduction. HPCG evaluations report moderate performances with a 1.1x speedup due to difficulties in balancing work time gains with runtime contention. Cholesky results do not provide either performance improvements or degradation.

Related Works

Persistent Task Graph In 2021, C. Yu et al. [START_REF] Yu | Enhancing OpenMP Tasking Model: Performance and Portability[END_REF] proposed an extension to the OpenMP specifications for taskgraph to capture the graph unrolled by a code section in order to re-execute it. Their proposal slightly differs from ours, as all the closures are only captured in the first iteration with their taskgraph: the producer thread execution flow is not re-executed on next iterations, so the firstprivate data may not be updated. Moreover, they only report provides a standard interface simulated results, while we also provide a runtime implementation and experimental results. In late 2022, the same authors uploaded complementary work on arVix [START_REF] Yu | Taskgraph: A low contention openmp tasking framework[END_REF] with a runtime implementation and speedup evaluations on shared-memory microbenchmarks. As opposed to their approach, our producer thread re-executes the instruction flow on every iteration. It can update task parameters (firstprivate data, if clause, ...) which preserves partially taskified programs conformity; authors conclude that it is a limit of their approach. Additionally, we evaluated an irregularly distributed proxy application (LULESH) reporting metrics; and showing impacts of/on the TDG discovery that are ignored on the arVix paper (cache re-use, communication overlap, throttling): they only report speedups on single-node Cholesky/Heat/Microbenchmark that may be inflated due to arbitrary fine-grained tasks. Nevertheless, their compile-time proposal nicely complements our runtime implementation.

In 2023, D. Alvarez et al. [START_REF] Alvarez | Optimizing iterative data-flow scientific applications using directed cyclic graphs[END_REF] proposed a cyclic data-flow task graph interface and implementation for iterative applications. Their approach is semantically identical to our persistent task graph: marking a loop generating the same TDG on every iteration, with the possibility to replay the producer task execution flow to update firstprivate data. However, as opposed to our runtime implementation, theirs does not have an implicit barrier on every iteration. Instead, the correct order of execution is guaranteed through a cyclic graph. To do so, their runtime stores multiple versions for each task and keep track of the TDG roots and leaves to insert cyclic edges. The detailed analysis and results we presented in this thesis on LULESH motivate the removal of our persistent task graph barrier on every iteration, as it limits scheduling possibilities and leads to work time inflation. Yet, remains to be evaluated if cyclic graph additional costs (multiple instances on-fly for the same task and leaves/roots tracking) will not deteriorate performances more than the gain obtained from the barrier removal. Likely, there is no fix answer on this, and an interface flexible-enough to have control on the iteration barrier could make sense.

Optimizations in Tasking Runtimes

The OpenMP dependent task model was adopted since the specifications 4.0 [START_REF] Duran | Extending the openmp tasking model to allow dependent tasks[END_REF] but implementations induces important overhead [START_REF] Gautier | On the Impact of OpenMP Task Granularity: 14th International Workshop on OpenMP[END_REF]. The history of optimization in task graph runtime starts at least twenty years before OpenMP 4.0. Cilk [START_REF] Frigo | The implementation of the cilk-5 multithreaded language[END_REF] was the precursor by considering end-to-end optimizations from the compilation a fast and slow versions of each task to the implementation of the stealing protocol without costly lock operation on the general case execution path. This was the starting point to several paper related to work stealing scheduler optimization which is outside the scope of our TDG optimization. Parsec [START_REF] Bosilca | DAGuE: A Generic Distributed DAG Engine for High Performance Computing[END_REF] based their graph model on the parametrized graph model [START_REF] Cosnard | Automatic Parallelization Techniques Based on Compact DAG Extraction and Symbolic Scheduling[END_REF] to implicitly represent tasks and their dependencies. It was a huge step in optimizing the memory space related to a task graph. Nevertheless, because this model does not fit well with irregular applications, the authors have also added a the classical task graph model proposed since the mid-90s [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF][START_REF] Gautier | Xkaapi: A runtime system for data-flow task programming on heterogeneous architectures[END_REF][START_REF] Galilée | Athapascan-1: On-line building data flow graph in a parallel language[END_REF][START_REF] Fernández | Task-based programming with ompss and its application[END_REF] built at run-time from description of tasks and their accesses (read,write) to the memory. Task graph optimizations presented in this chapter are almost present in all these runtime, but our runtime is the first OpenMP runtime that systematically integrates them.

Conclusion

The lack of applications using the task-based composition of MPI and OpenMP lead us to port a benchmark (HPCCG) and a proxy-application (LULESH) ourselves. During our porting journey, we faced the three programming/performances/profiling difficulties that motivated this thesis, and proposed solutions.

On programming aspects, both HPCCG and LULESH present irregular accesses which are hard to express under the current OpenMP specifications 5.2. Removing a few standard restrictions could ease future porting of applications. On profiling and performances aspects, our results on LULESH suggests that OpenMP TDGs discovery, which rely on a read-after-write (RaW) model, implies important runtime overheads with about 37% of the total discovery time on the LULESH producer thread. It makes it a critical component of task-based applications and runtimes to be profiled for assessing on performances; and optimized whenever bounding the execution time.

In our evaluation cases saturating the DRAM capacity, the TDGs discovery speed was an issue on both Intel Skylake and AMD EPYC nodes. It lead us to propose several performances optimizations: in applications code (reducing the number of dependencies expressed, and using the inoutset type); in the MPC-OMP runtime (redundancies filtering, inoutset efficient implementation, and task persistence); and in the OpenMP programming standard (task persistence). We evaluated the impact of each optimization on performances which lead us to the following conclusions:

• Fine-grain dependent tasking can improve performances of memory-bound applications whenever the domain computed does not fit into caches. Using a depth-first scheduling strategy, we showed 2x work time deflation thanks to temporal locality into caches.

• If an execution is discovery-bound, tasks may be consumed before an independent communication is discovered (and therefore, consumed), reducing the available work for overlapping.

• Whenever using task persistency (or cyclic graphs), a barrier at the end of each graph iteration may improve (by reducing overheads) or deteriorate performances (by inflating work time). If such persistence interface were to be standardized in OpenMP, programmers should probably be given a way to enable/disable this implicit barriers to match their usecases. Further evaluations should be conducted to assess more precisely on benefits/losses of such a barrier, for instance by comparing our approach (with a barrier) to D. Alvarez et al. [START_REF] Alvarez | Optimizing iterative data-flow scientific applications using directed cyclic graphs[END_REF] (with no barriers).

Chapter 7

Conclusion and Perspectives

Conclusion

Executing numerical simulations on supercomputers is a powerful tool for scientific research.

To assist scientific simulation programmers, the HPC community has been developing several programming models bridging codes with the ever-complexifying hardware. In particular, the Message Passing Interface (MPI) and Open Multi-Processing (OpenMP) are two standard programming models developed by large and diverse communities. They respectively target inter-node and intra-node parallelism, so their mixed-use appears as a well-suited solution to ensure both source code and performance portability across supercomputer architectures. OpenMP dependent task-based programming model opens the door to new ways and benefits of mixed-use, such as the implicit overlap of MPI communications with OpenMP tasks or the early-bird posting of MPI communications through the OpenMP task scheduler. However, porting existing scientific simulation codes to this new hybrid model raises the three Profiling/Programming/Performance difficulties we introduced in Chapter 1.

In this thesis, our contributions consisted of the investigation and solution proposals on these three difficulties:

• On profiling, we proposed a unified task-based performance modeling of MPI+OpenMP applications. We defined performance metrics and developed a run-time profiler and post-mortem analysis. For such mixed-use, the work/idle/overhead time breakdown and overlap metrics we profile are original, and their use throughout this thesis shows how necessary they are to assess performances. Additionally, task-based metrics (number of tasks, edges, granularity, per-task hardware counters) and visualizations (Gantt charts, dependency graphs) for such mixed-use were significantly helpful for interpreting presented results. Finally, our work on the task dependency graph showed the interleaving between its discovery and its execution (work time inflation, overlap potential reduction): it must be taken into account when profiling task-based applications.

• On programming, and to respond to the lack of applications currently taking benefits of the mixed-use using tasks, we ported two mainstream HPC applications: the High-Performance Conjugate Gradient (HPCG) and the Livermore Unstructured Lagrangian Explicit Shock Hydrodynamics (LULESH) providing experience feedback.

• On performances, our developments in the MPC-OMP runtime led to a cutting-edge and open-source OpenMP tasking runtime implementing the most recent features. In Chapter 6, we showed the criticality of the task dependency graph discovery and cross-evaluated several optimization techniques for its acceleration. Finally, preliminary results on our cooperative target task design suggests potential performances improvements over existing solutions at fine-grain GPU offloading.

Each of research axis contributed to propose extensions to the OpenMP specifications.

• Section 5.1 propose to differ the responsibility of tasks execution context to programmers and a new task suspension/resumption mechanism. They aim to automate the overlap and progression of external asynchronous operation through the OpenMP task scheduler.

• Section 5.2.3 extends the interpretation of the priority clause so it is back-propagated to predecessors. This way, programmers can guide the task scheduler towards critical tasks without the need to manually compute priorities of every tasks.

• Section 6.1.1 proposes an extension on existing the depobj construct and iterator to simplify the expression of irregular dependencies.

• Section 6.2.3.2 introduces task persistence to cache the task dependency graph of iterative applications, drastically reducing fine-grain tasking overheads.

This work lead to two publications in the International Workshop on OpenMP (IWOMP) [START_REF] Pereira | Communication-Aware Task Scheduling Strategy in Hybrid MPI+OpenMP Applications[END_REF][START_REF] Pereira | Suspending OpenMP Tasks on Asynchronous Events: Extending the Taskwait Construc[END_REF] and a publication in the International Conference on Parallel Processing (ICPP) [START_REF] Pereira | Investigating Dependency Graph Discovery Impact on Task-based MPI+OpenMP Applications Performances[END_REF]. Another publication in IWOMP [START_REF] Ferat | Enhancing mpi+openmp task based applications for heterogeneous architectures with gpu support[END_REF] presented preliminary experiments which was not presented as part of this document, adapting our work for GPU offloading using OpenMP target tasks. Finally, even though tasking comes with management overheads over traditional work-sharing loops, our contributions illustrates it may still be beneficial to overall performances:

• Early-bird posting using tasks reduced idleness and slightly improved overall performances (∼ 3%) on a Cholesky factorization.

• Application-wide load balancing and depth-first scheduling -significantly reduced idleness and work time on LULESH for a 2x speedup when saturating the DRAM capacity.

In the end, our contributions only provide partial responses on each of the three original difficulty, which lead us to present a few research directions to pursue our work.

Perspectives

Tools for Assisting Dependent Task-based Programming

We introduced a new profiler for the mixed-use of MPI and OpenMP using tasks. An important contribution was the post-mortem computation of the work/idle/overhead time breakdown heavily used for performance interpretation throughout this thesis. Still, mixed-use of the standard using tasks currently lacks such fundamental performance analysis tool accessible to a non-expert audience. We propose a few directions to explore to improve on debugging and profiling aspects.

Extending Our Profiler Firstly, our profiler would need to be ported toward standard OpenMP Tools (OMPT) interfaces; so it can run on any OpenMP runtime and reach a broader audience than MPC-OMP niche users. The porting had been initiated and would only require further engineering work.

Secondly, our analysis passes do not scale with the number of processing units and performances are rather poor. On scalability, computing the time breakdown (work/idle/overhead) is a rather sequential task anyway: each event must be treated sequentially, so the time frame in between can be classified as 'idleness' or 'overhead' depending on the virtual scheduler state. On performances, reading trace files with our analysis tools showed to be particularly slow. Even filtering-out traced events at run-time, converting the bytecode trace files to CPython PY_Object represents from 20% to 40% of the total analysis time. Removing memory conversion costs could be achieved improving the trace file format, or performing in-situ analysis (similarly to libyt1 ), dedicating cores to performance profiling; but it may increase interference with the execution over the current design (records are enqueued and flush to disk on program termination).

Finally, our profiler framework provides Python scripting interfaces to create new postmortem analysis passes. Such scripting approach had already been proposed by V. G. Pinto [START_REF] Vinicius | A Visual Performance Analysis Framework for Task-based Parallel Applications running on Hybrid Clusters[END_REF] in StarPU, a source of motivation being the flexibility by a scripting language that allows adapting visualizations and analysis. Our scripting framework could serve future research work on mixed-use of MPI and (MPC)-OMP using dependent tasks: for instance, an idea could be extending I. Daoudi work on task-based OpenMP application performance simulation [START_REF] Daoudi | Modélisation de performance et simulation d'applications OpenMP[END_REF] to simulate not only shared-memory but also distributed execution.

Finally, another direction to explore is static graph analysis to detect unoptimized pattern that could slow down the discovery speed, such as multiple edges or edges redundant by transitivity.

Ensuring the Correct Order of Execution As we ported LULESH and HPCG, most of the efforts were on setting up the correct dependencies between tasks. Ensuring the correct order of execution through dependencies (built upon data-flow) is significantly harder than fork-join parallelization (built upon control-flow). Any mistakes would lead to wrong calculations: debugging is painful and curretly mostly done by adding taskwait barriers to enforce execution order. This difficulty had already been characterized by S. Royuela et al. [START_REF] Royuela | Compiler analysis for openmp tasks correctness[END_REF] in 2015, which lead them to design compile-time analysis of dependencies to provide correctness tips to programmers. However, as a static analysis tool, their approach was limited to what the compiler can see. It lead them to extend this work in [START_REF] Economo | A toolchain to verify the parallelization of ompss-2 applications[END_REF] (2020) with Dynamic Binary Instrumentation (DBI) to detect any mistakes in dependencies expression at run-time by tracking tasks memory accesses. Standardizing such tool for OpenMP is necessary to reduce debugging efforts of dependent task-based programs. Following S. Royuela approach, additional run-time analysis on the task dependency graph could be conceived. For instance, we have shown in Section 6.2.3.1 that removing unnecessary dependencies (while preserving the correct order of execution) improves the task graph discovery speed and overall performances. It is not always trivial for programmers and mixed-use of static and dynamic analysis could help.

Compiler and Runtime Collaboration on Memory Prefetching

Performance gains on LULESH and HPCG of Section 6.2 were mostly from taking advantage of temporal locality using a depth-first scheduling heuristic. Applications are memory-bound, so accelerating memory access significantly improves performance. In order to accelerate memory accesses further-more, a way could be cache prefetching. For instance, attaching actual memory accesses performed to each task could lead to earlier and more accurate cache prefetching by the runtime; over traditional compiler/hardware prediction techniques.

In our porting of the application, we built task dependencies upon actual memory accesses; hence the OpenMP runtime even already has this information. Hence, it could perform explicit prefetching (__builtin_prefetch2 ) likely earlier than a compiler could detect by itself. Potential benefits would be improving the overlapping of data movements in the memory hierarchy with the execution of independent instructions with earlier prefetching. However, the co-existence of hardware/compiler/runtime memory prefetching could interfere and we believe collaboration of each layer may be needed to enhance performances.

Orchestrating Strong and Weak Progress of Asynchronous Operations

Supercomputers are getting massively parallel and heterogeneous: many-cores GPP, GPUs, FPGAs, NICs, someday Quantum Processing Units (QPUs). In order to fully use the hardware capability, programmers must use multiple programming models jointly, usually:

• one per device type,

• each requiring CPU time for transition system initialization and progression, which can overlap one another For instance, MPI requires CPU time to "to respond to control messages, post network read/write operations or poll the Host Channel Adapter (HCA), and orchestrate collective operations." [START_REF] Ruhela | Efficient asynchronous communication progress for mpi without dedicated resources[END_REF]; or Cuda requires CPU time to construct and schedule Cuda Graph, or perform memory transfers. Asynchronous operation progression mechanisms are often classified as

• strong -if it bounds the asynchronous operation duration,

• weak -else (if no such bound is guaranteed).

Strong progress is usually implemented through dedicated resources (physical cores, or kernel threads preempting the execution [START_REF] Sala | Integrating blocking and non-blocking mpi primitives with task-based programming models[END_REF][START_REF] Protze | Mpi detach -asynchronous local completion[END_REF]). It can lead to interferences degrading performances of each programming model [START_REF] Denis | Interferences between communications and computations in distributed hpc systems[END_REF][START_REF] Tseng | Demystifying asynchronous i/o interference in hpc applications[END_REF]: dedicating a physical core restricts the number of workers for each programming models, and ovesubscribing with kernel threads can deteriorate performances of each thread sharing the same core [START_REF] Tseng | Demystifying asynchronous i/o interference in hpc applications[END_REF][START_REF] Radojkovic | Measuring operating system overhead on cmt processors[END_REF]. In this manuscript, we have shown the importance of the task dependency graph discovery: sharing CPU time between producer threads and a progression thread would probably severely deteriorate performances of discovery-bound applications. On the other hand, weak progress is usually implemented with opportunistic polling, such as MPC collaborative polling on idle periods [START_REF] Didelot | Improving mpi communication overlap with collaborative polling[END_REF] or in-between OpenMP task scheduling decisions as we proposed in this thesis. Such approach can limit interferences removing kernel preemption with a 1:1 threads/core binding model; but it is not sufficient to bound asynchronous operation duration. Hence, a research direction to pursue is the orchestration of both strong and weak progress to provide both a duration time bound while limiting interferences at most.

Speculative Execution, and Distributed Task Graph Cancellation

Parallel iterative applications consists in re-iterating a computation scheme until a solution converged. The solution convergence test usually requires a global synchronization. Hence, it can be tested whether naively synchronizing on each iteration, or every few iteration as a tradeoff between the synchronization overheads and induced extra-computation [START_REF] Beaumont | Tradeoff to minimize extra-computations and stopping criterion tests for parallel iterative schemes[END_REF].

In Section 6.1, we presented our task-based porting of the LULESH and HPCG applications which are both iterative. LULESH and HPCCG criteria are the following:

• LULESH -the simulation finished (on the time-axis).

• HPCG -the residual r k+1 = r k -a k .A.p k is small-enough, providing an acceptable solution.

On the reference parallel-for versions, stopping the execution is straightforward due to the really-synchronous structure of the code, simply testing criteria after each iteration barrier. However, in the task-based versions, such barriers are removed, and criteria are only known after executing a specific task:

• LULESH -the task computing the time-step for the next iteration; line 4 on Listing 6.7.

• HPCG -the task computing the residual; represented in orange in the middle of Fig. 6.2.

When such "stopping criterion tasks" execute, tasks from many more iterations may already have been discovered by the producer thread. This in particular interesting to overlap (a) the task graph discovery with computation and (b) the completion of the iteration i with independent work from iterations j > i. (b) is also known as speculative computation: even though the execution of tasks from iteration i + 1 may not be needed, they are still executed speculatively, assuming the next iteration is actually needed. Speculative computation on LULESH is very-visible on the Gantt chart Fig. 6.14, where tasks of the same iteration are grouped per color.

However, once the stopping criterion is met, tasks from future iterations must be somehow canceled. As part of this thesis, we faced two difficulties to cancel a distributed task dependency graph with MPI and OpenMP under the current standard specifications. The first one is related to shared-memory cancellation with OpenMP, and the second one is related to on-going MPI communications cancellation.

Canceling OpenMP Tasks OpenMP provides a task cancellation interface. Using the OpenMP task transition system Fig. 3.2, the semantic of the cancel construct with specifications 5.2 is the following; after executing the construct:

• scheduled tasks finish execution; transition 4 → 6 .

• un-scheduled tasks does not execute; transition 4 → 7 , 8 . However, it remains the programmer responsibility to ensure the consistency of the computed solution, even if cancelled in the midsts of an interation.

Canceling MPI Requests Though, not only local tasks but also on-going communications and remote tasks must be cancelled. MPI specifications provide the MPI_Cancel interface to cancel a request. However, it only specifies its use on point-to-point receive requests 3 . Canceling point-to-point send requests used to be specified by MPI, but led to implementation issues 4 . Supporting cancellation on send requests implied overhead on every request, and there were no clear motivating use cases, leading the committee to remove it from the specification. In the context of speculative computation with task-based mixed use of MPI+OpenMP, canceling send operations and even collectives could be a motivating use case.

Nevertheless, canceling each request individually still implies unnecessary overheads on historical use cases (that would never cancel), and does not provide solutions to remote OpenMP tasks cancellation. That's why exploring cancellation on a coarser level (communicator or session) is probably a more suitable solution.

Going Forward In this thesis, we always ensured that stopping criteria were never met: in all our evaluations, the application always executes in a fixed amount of iterations, hence avoiding cancellation difficulties. Note that LULESH leap/frog solver (at most 2 different iterations on the fly), and the conjugate gradient (at most 1 iteration on the fly) remains inherently synchronous algorithm due to global reductions, limiting speculative computation possibilities. Asynchronous algorithm could benefit more from such speculative tasking approach. Providing solutions to mentionned difficulties and studying the impacts of distributed cancellation is a future work to be conducted to assess on benefits and drawbacks.

Co-Scheduling Task-based Programs to Maximize Resources Usage

As we discussed in our publication [START_REF] Taboada | Towards achieving transparent malleability thanks to mpi process virtualization[END_REF], executing multiple programs on the same compute node is a way to maximize compute resources use. The general idea is to overlap the idleness of a given application with useful work from another application. The first possibility is through cores over-subscription with kernel threads (e.g., pthreads), letting the operating system preemptively schedule threads. With n cores and m > n threads, this is the m : n co-scheduling approach.

Over-subscription had been widely adopted in parallel runtimes for overlapping synchronization idleness on cores, for instance, in AMPI [START_REF] Pei | Evaluation of programming models to address load imbalance on distributed multi-core cpus: A case study with block low-rank factorization[END_REF] or LLVM OpenMP [START_REF] Shilei Tian | Concurrent execution of deferred openmp target tasks with hidden helper threads[END_REF]. Yet, it can degrade performances when a high number of asynchronous operations concurrently progressed [START_REF] Radojkovic | Measuring operating system overhead on cmt processors[END_REF][START_REF] Bierbaum | Towards efficient oversubscription: On the cost and benefit of event-based communication in mpi[END_REF], one source of overhead being the operating system.

The second possibility is an n : n approach: each core is assigned a single kernel thread, and the scheduling decision is taken by a user-space scheduler cooperatively (such as MPC). A motivating result is Figure 8.2 of C. Barbossa Ph.D. thesis [START_REF] Barbosa | Sabo: Dynamic mpi+openmp resource balancer[END_REF]. Her objective was to reduce idleness induced by OpenMP synchronization from unbalanced work between threads of a parallel for loop. In her experiment, she compared the performances of three scenarios coscheduling two applications (MiniFE and Quicksilver), showing that letting the operating system manage scheduling is not sufficient to maximize resource usage in the HPC proxy-applications understudy. Precise reasons remain to be investigated but could include, for instance, preemption costs or CPU resource retention during synchronizations (spinlock).

A research direction we would like to conduct in the future is the co-scheduling of multiple task-based applications.

Task-based MPI and OpenMP Composition: Who is the Audience ?

Throughout this thesis, we have demonstrated that the mixed-use of MPI and OpenMP could respond to the problem of performance portability. We provided a few answers to the programming, profiling, and performance difficulties we introduced; however, hardware complexity remains: heterogeneity, hierarchical memory, interconnection network... As hardware becomes more complex, standard interface follows, and programming both performant and portable applications become almost impossible for a non-expert audience. In order to ease programming to a non-HPC expert audience and fully embrace the problem of performance portability, a promising long-term solution consists in designing higher-level and constrained interfaces such as Domain Specific Languages (DSL) on top of MPI and OpenMP: MPI and OpenMP would target HPC experts conceiving DSLs; while DSLs target scientific simulation programmers. In the literature, a few have initiated this approach, such as NabLab [START_REF] Benoit Lelandais | Fostering metamodels and grammars within a dedicated environment for hpc: The nablab environment (tool demo)[END_REF] for simulations over unstructured mesh. In the future, designing, optimizing, and maybe even unifying DSL are research directions to conduct for the performance portability of scientific simulations.

Annexes

8 1. 2

 82 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Objectives and Contributions . . . . . . . . . . . . . . . . . . . . . . . 10

Contents 2 . 1

 21 Supercomputers Architecture . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.1 Introducing the CEA-HF Supercomputer . . . . . . . . . . . . . . . . . 2.1.2 Zoom on Modern Compute Blades . . . . . . . . . . . . . . . . . . . . . 2.2 Executing and Programming on a Supercomputer . . . . . . . . . . 16 2.2.1 The Portable Operating System Interface (POSIX) . . . . . . . . . . . . 2.2.2 Operating System Kernels: a Fast Zoom on Linux . . . . . . . . . . . . 2.2.3 Programming Languages and Compilers . . . . . . . . . . . . . . . . . . 2.2.4 HPC-oriented Programming Languages . . . . . . . . . . . . . . . . . .2.2.5 Programming Models in HPC . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Task-based Programming Models . . . . . . . . . . . . . . . . . . . . . 23 2.3.1 A Definition for Task-based Programming Models . . . . . . . . . . . . 2.3.2 A Taxonomy of Task-based Programming Models . . . . . . . . . . . . . 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Figure 2 . 1 :Figure 2 . 2 :

 2122 Figure 2.1: Scientific Simulations Application Stack Overview. Top-most "Scientific Simulations" images from[START_REF] Fonseca | One-to-one direct modeling of experiments and astrophysical scenarios: Pushing the envelope on kinetic plasma simulations[END_REF][START_REF]SCM -HPC center[END_REF][START_REF]ETP4HPC -What is HPC ?[END_REF]

Figure 2 . 3 :

 23 Figure 2.3: General Purpose Processor -Hierarchical Memory

Figure 2 . 5 :

 25 Figure 2.5: A Task Transition System

Figure 2 . 7 :

 27 Figure 2.7: Task-Based Programming Models API Taxonomy from[START_REF] Peter Thoman | A taxonomy of task-based parallel programming technologies for high-performance computing[END_REF]

Contents

3. 1

 1 The Message Passing Interface (MPI) . . . . . . . . . . . . . . . . . . 28 3.2 Open Multi-Processing (OpenMP) . . . . . . . . . . . . . . . . . . . . 31 3.2.1 Before Tasking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.2 After Tasking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Hybridizing MPI and OpenMP . . . . . . . . . . . . . . . . . . . . . . 35 3.3.1 Historical Bulk-Synchronous Parallel Program Structure . . . . . . . . . 35 3.3.2 Task-based Hybridization . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4 Multi-Processor Computing (MPC) . . . . . . . . . . . . . . . . . . . 39 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Figure 3 . 1 :

 31 Figure 3.1: MPI Requests as a transition system

Figure 3 . 2 :

 32 Figure 3.2: OpenMP Task Transition System in the MPC-OMP runtime

Figure 3 . 3 :

 33 Figure 3.3: OpenMP Specifications evolutions on tasking concepts

Figure 3 . 4 :

 34 Figure 3.4: Deadlock of stack-yield algorithm

Figure 3 . 5 :

 35 Figure 3.5: MPI and OpenMP interoperability

3. 4 Figure 3 . 6 :

 436 Figure 3.6: MPC layers and source tree overview

Contents 4 . 1

 41 Defining Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.1.1 Task Graph Scheduling Problem and Observation . . . . . . . . . . . . . 42 4.1.2 Metrics Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.1.3 MPI+OpenMP(tasks): A Unified Modeling . . . . . . . . . . . . . . . . 45 4.2 Profiling MPI+OpenMP(tasks) Task-based Execution . . . . . . . . 47 4.2.1 Hybrid Tracing: Recording PMPI and OMPT Events . . . . . . . . . . 47 4.2.2 Analyzing Traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.3 Repos and Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

  mapping nodes and edges respectively to work and communication time, veryfing the precedence (4.1) and the processor (4.2) constraints:

Figure 4 . 1 :

 41 Figure 4.1: Time Breakdown

Figure 4 . 2 :

 42 Figure 4.2: Overlaped work on a communication edge

  is an ideal overlapable work time on the multi-threaded MPI process Q during time intervals progressing communications e, and ∑ e∈E ˆ(Q) o v (Q, e) is the work performed in parallel on any threads.

Figure 4 . 3 :

 43 Figure 4.3: From Hybrid Code to a Global Task Dependency Graph

Fig. 4 .

 4 Fig. 4.3 illustrates this algorithm. Bold elliptic nodes correspond to OpenMP tasks on step (a). Nodes {B, D, I, K} (MPI request state) and {A, C, E, F, G, H, J, L} (sequential instructions in-between) correspond to the OpenMP-task division on step (b). Paths {(A, B, D, E), (A, C, E), (H, I, K, L), (H, J, L)} correspond to step (c) intra-process edges. Dotted edges {(B, K), (I, D)} correspond to inter-process edges of step (d).Note that step (d) must respect both the order of execution and the parallelism specified by MPI. For instance, it models the implicit barrier induced on each collective communication but also models that an MPI_Wait on an asynchronous send operation could return before the paired-receive is posted remotely. It also models the explicit overlap parallelism expressed between a started/completed transition state, as shown with independent nodes B and C.

Figure 4 . 4 :

 44 Figure 4.4: MPI Collective Modeling

Fig. 4 .

 4 Fig. 4.4 illustrates another example of an MPI Broadcast collective, with nodes {S i , W i } corresponding to the initialization and completion state of the MPI request.

Figure 4 . 5 :

 45 Figure 4.5: Gantt chart of a nbody simulation, showing important load imbalance

Figure 4 . 6 :

 46 Figure 4.6: Gantt chart of a Cholesky factorization, arrows represent MPI point-to-point communications

Figure 4 . 7 :

 47 Figure 4.7: Unified Modeling generated by the GTDG analysis pass

Contents 5 . 1

 51 Executing MPI Requests within MPC-OMP Tasks . . . . . . . . . . 52 5.1.1 State of the art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.1.2 Solutioning the loss of thread issue . . . . . . . . . . . . . . . . . . . . . 53 5.1.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.2 Early-bird Posting with Tasks Scheduling . . . . . . . . . . . . . . . . 56 5.2.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.2.2 The Issue of Task Throttling . . . . . . . . . . . . . . . . . . . . . . . . 57 5.2.3 Scheduling Tasks with Priorities . . . . . . . . . . . . . . . . . . . . . . 58 5.2.4 Communication-Aware Task Scheduling Strategies . . . . . . . . . . . . 62 5.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Figure 5 . 1 :

 51 Figure 5.1: Top: sub-graph of a distributed blocked Cholesky factorization mapped onto 2 MPI Ranks (matrix size: 2048x2048 with tile of size 512). Bottom: Gantt chart with 2 threads per MPI process (real execution).

Figure 5 . 2 :

 52 Figure 5.2: Alternative scheduling for the graph in Fig. 5.1 (not real execution)

Algorithm 1 2 :PROPAGATION = EQUAL then 10 :

 1210 Task Priority Input: Task T Output: Integer P(T) the priority of T 1: function P(T) if PROPAGATION = NONE or Successors(T ) = Ø then return max({P (S) | S ∈ Successors(T )}) 11: else ▷ If PROPAGATION = DECREMENT 12:

10 Figure 5 . 3 :

 1053 Figure 5.3: Red/Black Tree with nodes as task list of the same priority

Figure 5 . 4 :

 54 Figure 5.4: Hierarchical Red/Black Tree Scheduling

Figure 5 . 5 :

 55 Figure 5.5: Task Ordering (the redder, the earlier schedule) depending on the heuristic used, on two MPI processes for n = 6, 144 and m = 512. The SA heuristic favors MPI_Send (diamond tasks) and their predecessors, while FIFO lead to breadth-first scheduling

Contents 6 . 1

 61 Porting Irregular Applications with Task-based Programming . . . 70 6.1.1 Conjugate Gradient (HPCCG) . . . . . . . . . . . . . . . . . . . . . . . 70 6.1.2 Simplified Hydrodynamic Simulation (LULESH) . . . . . . . . . . . . . 77 6.2 Investigating The TDG Discovery Impacts on Performances . . . . 86 6.2.1 Motivations on the Dependency Graph Discovery . . . . . . . . . . . . . 86 6.2.2 Profiling LULESH with MPC . . . . . . . . . . . . . . . . . . . . . . . . 86 6.2.3 Accelerating the Dependency Graph Discovery . . . . . . . . . . . . . . 89 6.2.4 Impacts on Distributed Execution . . . . . . . . . . . . . . . . . . . . . 94 6.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

#

  pragma omp parallel for for (Index_t i = 0; i < n; i++) local_result += x[i] * y[i]; Listing 6.1: HPCCG' dot product implementation Algorithm 5 Conjugate Gradient Algorithm Input: Matrix A, Vector b, Vector x 0 Output: Vector x -solution of A.x = b 1: function CG(A, b) 2:

. 1 ) 6 . 1 .

 161 PORTING IRREGULAR APPLICATIONS WITH TASK-BASED PROGRAMMING 72 # pragma omp task depend(in: α, β, x[0], y[0]) depend(out: w[0]) { for (int i = 0 ; i < B 1 ; ++i) w[i] = α.x[i] + β.y[i]

Figure 6 . 1 :

 61 Figure 6.1: HPCCG tasks for n = 8 and T 1 = T 2 = 2

Fig. 6 .Figure 6 . 2 :

 662 Figure 6.2: Conjugate Gradient Graph for the parallel-for and task version, on a 1 iteration

1

  std::list<int> indices; 2 int k2 = MIN(k+B2, (k/B1+1)*B1, n); 3 for (int i = k; i < k2; ++i) 4 for (int j = row[i]; j < row[i+1]; ++j) 5 indices.insert(inds.end(), col_idx[j]/B1*B1); 6 7 auto it = indices.begin(); 8 # pragma omp task depend(iterator(i=0:indices.size()), in: x[*it++]) depend(out: y[k/B1*B1]) 9 { for (int i = k; i < k2; ++i) { y[i] = 0; for (int j = row[i]; j < row[i+1]; ++j) y[i] += data[j] * x[col_idx[j]]; } } Listing 6.2: Matrix Vector Multiplication redundant and tiled dependencies 1 std::set<int> indices; 2 [...] Listing 6.3: Matrix Vector Multiplication tiled dependencies, filtering redundant dependency Listing 6.2 is our first implementation of the SpMV irregular dependencies using the Compressed Sparse Row (CSR) matrix format. With the current 5.2 specifications, indices from the union ⋃ z b (A, i) on SpMV (6.

  omp_depend_t obj; # pragma omp depobj(obj) depend(iterator(i=k:k+B2), iterator(j=row[i]:row[i+1]), in: x[col_idx[j]/B1*B1]) depend(out: y[k]) [...] # pragma omp task depend(obj) [...] Listing 6.4: Sparse Matrix / Vector Multiplication Task with no restrictions on depobj (deps. per block filtering redundancies) 6.1.1.5 Studying the Impact of Task Granularity

Figure 6 . 3 :

 63 Figure 6.3: HPCCG Task Graph Execution (left) and Discovery (right) time on 16 AMD EPYC 7H12 cores

6. 1 .Figure 6 . 4 :Figure 6 . 5 :

 16465 Figure 6.4: LULESH Slice View along the (x, y) axes

Fig. 6 .

 6 8 (b) depicts the average overheads and average work time per task (overhead and work time divided by the number of tasks). As shown on Fig. 6.8 (a,b), the right-most point reaches a total number of 7,5M OpenMP tasks with an average grain of 250µs. Fig. 6.8 (c) depicts the time

Figure 6 . 7 :

 67 Figure 6.7: LULESH performances on 24 Intel(R) Xeon(R) Platinum 8168 CPU @2.70GHz.

Figure 6 . 8 :iteration 3 Figure 6 . 9 :

 68369 Figure 6.8: LULESH performances on 24 Intel(R) Xeon(R) Platinum 8168 CPU @2.70GHz using MPC with -s 384 -i 16 -tel TPL -tnl TPL

Figure 6 . 10 :Fig. 6 .

 6106 Figure 6.10: Optimizations (a) and (b)

  .

  .

1Figure 6 . 11 :

 611 Figure 6.11: Optimization (c) -inoutset edges reduction

Figure 6 .

 6 Figure 6.13: LULESH -s 256 -i 64 on 125 MPI processes, 54 AMD EPYC 7763. Time breakdown (top) and communication performances (bottom) on a profiled MPI process (rank 82)

Figure 6 . 14 :

 614 Figure 6.14: Gantt chart of task-based execution for TPL=1,152

  tasks Average task grain (in μs.)

Figure 6 . 15 :

 615 Figure 6.15: HPCCG performances on 32 MPI processes on Intel processors for a matrix with n=41,943,040 on i=128 iterations

Figure 8 . 2 :

 82 Figure 8.2: Fugaku's A64FX Compute Node

  committee from the Association for Computing Machinery (ACM). It awards HPC applications (scientific simulation, engineering, or large-scale data analytics) showing notable performances and portability. Most Gordon Bell papers do not provide source code, and for some of them, too few implementation details to conclude on the programming languages used. Still, we observe the following trends. Between 1987 and 2000, we observe the domination of Fortran in the Gordon Bell Prize awards. After 2000, simulation programming languages start transitioning from Fortran to C/C++, with both languages being about equally represented. On the recent winners (2015 to 2022), simulations are whether using pure C/C++

	section .data
	num1 dd 4
	num2 dd 5
	format db "%d", 0
	result dd 0
	section .text
	global _start
	_start:
	mov eax, [num1] ; move '4' from the data segment to the 'eax' register
	mov ebx, [num2] ; move '5' from the data segment to the 'ebx' register
	imul ebx	; compute '4 x 5 = 20' to the 'eax' register
	mov [res], eax ; move '20' from the 'eax' register to the data segment
	; call printf to print the result
	push dword [res]
	push dword format
	call printf
	add esp, 8	; remove arguments from the stack
	; exit the program
	mov eax, 1	; 'sys_exit' system call
	xor ebx, ebx ; set the system call argument to 0
	int 0x80	; raise the system call
	1 program multiplication 2 implicit none 3 integer :: num1, num2, res 4 5 ! Multiply 4 x 5 6 num1 = 4 7 num2 = 5	1 int main(void) { 2 int num1 = 4; 3 int num2 = 5; 4 int res = num1 * num2; 5 printf("%d", res); 6 return 0; 7 }
	8 res = num1 * num2 9	Listing 2.3: C program
	10 ! Print the reuslt 11 write(*,*) res 12 13 end program multiplication	1 num1 = 4; 2 num2 = 5; 3 res = num1 * num2; 4 print("%d", res);
	Listing 2.2: Fortran program	Listing 2.4: Python program
	2.2.3.1 A Brief History on Programming Languages and Compilers in Scientific
	Simulations

Listing 2.1: X86 Assembly program architecture-specific low-level program (assembly, machine-code) so the hardware can execute it. Listing 2.2 illustrates a FORTRAN program that could be compiled to the Assembly code Listing 2.1. Abstracting programs from architecture through programming languages and compilers tackle machine-code programming drawbacks. It has led, since then, to significant development of programming languages and compilers.

FORTRAN (1954)

, C

[START_REF] Ritchie | The C Programming Language[END_REF]

(1970), C++

[31] (1985)

, Python

[START_REF] Michel | Python: a programming language for software integration and development[END_REF]

(1991) are the top 4 programming languages used by HPC programmers. The Gordon Bell Prize 14 has been awarded each year since 1987 by a

1 # pragma omp task depend(out: x) 2 { 3 # pragma omp task depend(out: y)

	4	y = 42;
	5
	6	# pragma omp task depend(in: y)
	7	func(y);
	8
	9	x = 1;
	10 }
	11
	12 #

pragma omp task depend(in: x) 13 { 14 # pragma omp task depend(out: z)

	15 16 17 18 19 20 21 }	z = 1; # pragma omp task depend(in: z) func(z); func(x);	} } } }	C E D F	} }	A B

Task Control Flow Graph (TCFG)

	A		B
	C	D	E	F
	Task Dependency Graphs
		(TDG)
	A	C	E
	B	D	F
	Figure 2.6: Task Control Flow and Dependency Graphs
	binary relation between tasks can also be represented as a direct acyclic graph: this is the Task
	Dependency Graph.
	2.3.2 A Taxonomy of Task-based Programming Models
	Many task-based programming models have been developed. The wide range of their features and
	applicability motivated P. Thoman et al. to propose a taxonomy of TPM APIs [63]. However, it
	has a few limitations which lead us to propose a slightly extended version.
	2.3.2.1 P. Thoman et al. Taxonomy
	Fig. 2.7 depicts P. Thoman et al. taxonomy from their original publication

  Processes, Program, Communications Within the MPI standard, an MPI process can be a POSIX process or thread depending on the implementation executing a (POSIX) program. An MPI program is a set of MPI processes executing the same POSIX program, that may communicate to one another through the MPI API such as requests.

	MPI Request states 0 -uninitialized (source)	2 -started	MPI_Send_init MPI_PSend_init	0
	1 -initialized	3 -consumed (sink)	MPI_Recv_init [...]
			1 MPI_Bcast_init	MPI_Ibcast [...] MPI_Irecv MPI_Isend
			if persistent and
			test success MPI_Test	MPI_Start
			MPI_Wait
				2
		Instruction Pointer is here	if test fails MPI_Test		MPI_Request_free
				if non persistent	3
				and test success
				MPI_Test
				MPI_Wait

  void init(task_t * task, int size, void * data, void (*f)(), int flags, int priority) {

	task->f = f;	/* Save outlined function pointer */
	task->data = data;	/* Copy shared/private data */
	task->omp_priority = priority;	/* Save task priority */
	setup(task, flags);	/* Convert passed flags (untied, final, ...) */
	Set 'task' not_queuable	/* 0 → 1 */
	}
	void construct(void * data, int size, void (*f)(), int flags, int priority, depends_t * deps)
	{
	task_t * task = (task_t *) malloc(size); /* Set state 0 */
	init(task, flags, priority);
	for (int i = 0 ; i < deps.size() ; ++i) /* Link dependences in the TDG */
	dependency_insert(task, deps[i]);
	Set 'task' queuable	/* 1 → 2 */
	process(task);
	}
	void finalize(task_t * task) {
	if (task->detach_event) {	/* If a 'detach(event)' clause is specified */
	Set 'task' detached	/* 4 , 6 → 7 */
	wait(task->detach_event);
	}
	Set 'task' completed	/* 4 , 6 , 7 → 8 */
	for (task_t succ : task->successors)
	process(succ);
	}
	void schedule(void) {
	task_t * task = next_ready_task();
	Set 'task' scheduled	/* 3 → 4 */
	if ('task' was not cancelled) {
	task->f(task->data);
	Set 'task' executed	/* 4 → 6 */
	}
	finalize(task);
	}
	void process(task_t * task) {
	if (each 'task' predecessor state ≥ completed) {
	queue(task);
	Set 'task' queued	/* 2 → 3 */
	}
	if (task is undeferred)
	while (state of 'task' is < executed)
	schedule();
	}
	void wait(void) {
	Set 'current_task' suspended	/* 4 → 5 */
	while ('current_task' has children tasks in state < executed)
	schedule()
	queue(task);
	Set 'current_task' queued	/* 5 → 3 */
	}

  Listing 3.2: MPI and OpenMP task-based hybridization

	3.3.2.1 Nesting MPI Communications into OpenMP Tasks
	# pragma omp task depend(out: x)
	{
	[...] /* some work on which depends on the request completion */
	MPI_Start(&req);
	[...] /* some independent work */
	MPI_Wait(&req, &status);
	[...] /* some work that depends on the request completion */
	}
	# pragma omp task
	{
	[...] /* some independent work */
	}

  as follows: Using the task detach(event) construct, application

	omp_event_handle_t ev_handle;
	# pragma omp task detach(ev_handle) depend(out: y)
	{
	[...] /* some work on which depends on the request completion */
	MPI_Start(&req);

MPIX_Detach(&req, omp_fulfill_event, ev_handle); [...] /* some independent work */ } # pragma omp task depend(in: y) depend(out: x) { [...] /* some work that depends on the request completion */ } # pragma omp task depend(out: x) { [...] /* some independent work */ }

Table 5

 5 Priority propagation (single-thread, during idle periods)

	1: Variables
	2:	List D, U

.1 reports minimum/median/maximum execution times. A first observation comparing runtimes, is that MPC-OMP tasking management seems to have Algorithm 4

Table 5 .

 5 1: Performance of the micro-benchmark Annex 8.3

Table 5 .

 5 Figure 5.6: Cholesky factorisation time varying heuristics, and the MPI/OMP cores spreading on 16 Skylakes nodes (e.g., 16-48 stands for 16 MPI ranks of 48 threads each) -with a matrix of size n = 131, 072, and blocks of size m = 512 -Using MPC-MPI and MPC-OMP 2: Number of point-to-point communication tasks in Fig. 5.6 runs

		in tasks
	Time average on threads (in s.)	idle overhead
		1	MA-2	SA	FA	FIFO	MA-1	MA-2	SA	FA	FIFO	MA-1	MA-2	SA	FA	FIFO	MA-1	MA-2	SA	FA
			16-48					32-24					64-12					128-6
								MPI-OMP cores spreading
		Cores spreading (MPI-OpenMP)			16-48	32-24		64-12		128-6
		P2P communication tasks (overall) 388.624 640.632 892.640 1.372.880

Table 5 .

 5 FIFO) 28.45 ± 1.63 0.44 ± 0.06 20.83 ± 0.76 7.96 ± 1.85 0.18 ± 0.01 no priority (+ LIFO) 28.05 ± 1.58 0.45 ± 0.05 20.70 ± 0.82 7.67 ± 1.96 0.18 ± 0.01 SA (+ LIFO) 27.04 ± 1.72 0.61 ± 0.05 21.72 ± 1.60 5.71 ± 3.03 0.18 ± 0.03 FA (+ LIFO) 27.25 ± 1.71 0.51 ± 0.05 20.74 ± 1.57 6.62 ± 2.35 0.38 ± 0.20 3: Cholesky Factorization Performances varying scheduling parameters with MPC-OMP 2023 and OpenMPI 4.1.5. Times are given in seconds (s.)

	Makespan	Discovery	Work	Idle	Overhead
	no priority (+

Table 6 .

 6 1: HPCCG: the number of FLOPs performed per task, and the median grain measured on 16 AMD EPYC 7H12 cores for n = 41, 943, 040, T 1 = 16 and T 2 = 1

	Task type FLOPs	Median grain (ms.) Performance (GFLOPs/s)
	dot waxpby SpMV	2. n T 1 3. n T 1 2 × 27. n T 1 .T 2	12.3 25.9 517.3	0.43 0.30 0.27
	6.1.1.2 Expressing Irregular Tiled Dependencies

Table 6 .

 6 .

	Dependencies passed Discovery Execution

2: HPCG Performances on Dependencies Expression

  6.1. PORTING IRREGULAR APPLICATIONS WITH TASK-BASED PROGRAMMING 78

	typedef struct {	/* a node data structure */
	double x, y, z;	/* position */
	double vx, vy, vz; /* velocity */
	double m;	/* mass */
	} node_t;
	typedef struct {	/* a mesh data structure */
	node_t nodes[n];	/* set of nodes */
	int elements[m]

Table 6 .

 6 6.8 (c) where threads ends up idling waiting for tasks to spawn. Being discovery-bound limits the vision of the TDG to the OpenMP scheduler: the depth-first scheduling heuristic cannot be effective because successors are not known by the scheduler on predecessors completion. Threads end up scheduling whatever is ready (in a breadth first manner) resulting in poor cache re-usability. 3: Impact of the task graph discovery on the work time 6.2.2.3 Impact of the task dependency graph discovery on the work time

	Instance	Idle (s.) Work (s.) L2DCM L3CM
	1,872 TPL (concurrent)	3.5	1,477	98B	73B
	4,608 TPL (concurrent)	766.6	1,589	98B	91B
	4,608 TPL (non-concurrent)	1.2	1,077	84B	53B

  -more edges are generated in the second case even though TDGs discovery are about the same. This rebound-effect phenomenon occurs because the TDG discovery is faster with optimization enabled, leading to more predecessors existing on successors' creation; therefore, less automatic pruning occurs. The same phenomenon occurs comparing none against (a).

	optimizations	n°of tasks n°of edges discovery execution work	idle	overhead
	none	2,802,400	56,320,296	76.67	77.48	1,612	3.49	229.50
	(a)	2,802,400	58,168,382	71.79	73.40	1,533	3.00	211.40
	(b)	2,802,400	21,926,084	67.53	71.83	1,546	2.85	131.70
	(c)	4,853,811	30,246,767	71.91	73.19	1,568	3.07	167.44
	(a)+(b)	2,802,400	31,144,779	66.60	69.39	1,503	3.23	144.26
	(a)+(c)	3,614,124	36,239,253	56.38	69.43	1,512	3.31	128.51
	(b)+(c)	4,858,307	24,837,165	71.73	72.95	1,568	2.85	163.29
	(a)+(b)+(c)	3,613,737	27,633,254	55.56	69.17	1,517	2.64	116.77
	(a)+(b)+(c)+(p)	3,557,840	19,177,294	5.97	70.80	1,655 12.22	27.30
	Table 6.4: Optimizations crossing on Intel Skylake nodes LULESH -s 384 -s 16 -TPL 1872. Times
	are given in seconds
	• (b) against (a)+(b)

  Figure 6.12: LULESH on Intel Skylake node with optimizations M ET G(X%) gives the minimum task grains for which an instance of execution reaches X% of the best performances measured on any runtime system. Their results on GCC/LLVM show a M ET G(95%) = 1ms for several applications. Running LULESH with GCC, LLVM, and MPC-OMP tasking runtime, we measured an M ET G(95%) of 65µs with 9,216 TPL using MPC-OMP, which is 1.5 order of magnitude less than the best OpenMP METG reported in[START_REF] Slaughter | Task bench: A parameterized benchmark for evaluating parallel runtime performance[END_REF] for such efficiency.

							Inflation	1.0 1.2 1.4 1.6	(d)									work time inflation
								4 8 3 3 6 6 2 4 9 1 2	1 2 0 0	1 4 8 8	1 7 7 6	2 0 6 4	2 3 5 2	2 6 4 0	2 9 2 8	3 2 1 6	3 5 0 4	3 7 9 2	4 0 8 0	4 3 6 8	4 6 0 8
											Number of tasks per loop (TPL)
						idle (s.)		overhead (s.)		work (s.)			graph discovery (s.)
						overlap ratio (%)			overlaped (s.)				communication (s.)
		parallel for			TDG optimizations disabled									TDG optimizations enabled
	Time average on threads (s.)	50 100 150 200 250 300			parallel for ~248 s. task-based non-optimized ~145 s. (TPL=1,664)						parallel for ~248 s. task-based non-optimized ~145 s. task-based optimized ~122 s. (TPL=4,608)	50 100 150 200 250 300
		0																					0
	Time cumulated on threads (s.)	500 1000 1500 2000 2500 0	1 2 8	6 4 0	1 1 5 2	1 6 6 4	2 1 7 6	2 6 8 8	3 2 0 0	3 7 1 2	4 2 2 4	4 7 3 6 Number of tasks per loop (TPL) 5 2 4 8 5 6 3 2 1 2 8 6 4 0 1 1 5 2	1 6 6 4	2 1 7 6	2 6 8 8	3 2 0 0	3 7 1 2	4 2 2 4	4 7 3 6	5 2 4 8	5 6 3 2	Overlap ratio (%) 100 17 33 50 67 83 0

Table 6 .

 6 5: LULESH -s 256 -i 1024 -Weak and Strong scaling from 8 to 1,000 MPI processes From 8 to 1,000 MPI processes with 2,048 TPL, task-based executions lasted about 2,000 s. with more than 95% weak-scaling efficiency and a 2.0x speedup compared to the parallel for version. The strong scaling from 8 to 4,096 MPI processes uses a dynamic TPL to balance parallelism and workload per task, ensuring at least 16 tasks per loop and, at most 8,192 mesh nodes per task, as shown in the last row. The task-based version improves performances over the parallel for version until 128 MPI processes for about 5% DRAM use.

	6.2.4.3 HPCCG

Table 8 .

 8 1: LULESH per-task: (1) average work, (2) instructions per cycle, and (2) double operation per load/store instructions ; for -s 384 -tel 1024 -tnl 1024 on 24 Intel(R) Xeon(R) Platinum 8168

	Task Label	Work (µs) TOT_INS/TOT_CYC DP_OPS/LST_INS
	AABCForNodes	4307	0.03	2E-05
	ApplyMaterialPropertiesForElems	68.18	1.97	1.98
	CalcAccelerationForNodes	726.41	0.27	0.33
	CalcCourantConstraintForElems	639.95	0.36	0.25
	CalcCourantConstraintForElems_reduce	3.14	0.42	0.01
	CalcEnergyForElems1	595.48	0.25	2.32
	CalcEnergyForElems2	1077.53	0.58	1.12
	CalcEnergyForElems3	209.08	0.55	1.99
	CalcEnergyForElems4	1274.39	0.61	1.12
	CalcEnergyForElems5	905.58	0.49	0.73
	CalcFBHourglassForceForElems1	18344.26	1.9	1.41
	CalcFBHourglassForceForElems2	5478.5	0.23	0.67
	CalcForceForNodes	246.13	0	0.01
	CalcHourglassControlForElems	22436.32	1.98	0.63
	CalcHydroConstraintForElems	210.4	0.72	0
	CalcHydroConstraintForElems_reduce	1.18	0.5	0.01
	CalcKinematicsForElems	7210.77	2.69	1.08
	CalcLagrangeElements	281.53	0.6	1.2
	CalcMonotonicQGradientsForElems	4256.46	2.15	0.87
	CalcMonotonicQRegionForElems	3089.27	1.15	1
	CalcPositionForNodes	440.9	0.57	0.67
	CalcPressureForElems1	315.06	0.22	1.32
	CalcPressureForElems2	548.12	0.53	0.33
	CalcSoundSpeedForElems	590.05	0.42	0.86
	CalcTimeConstraintsForElems_init	0.5	0.74	0.01
	CalcTimeConstraintsForElems_reduce_courant	1.5	0.23	0.01
	CalcTimeConstraintsForElems_reduce_hydro	1	0.36	0.01
	CalcVelocityForNodes	483.58	0.94	0.67
	EvalEOSForElems1	1988.75	0.15	0
	EvalEOSForElems2	676.42	0.46	1
	EvalEOSForElems3	249.7	0.39	0
	EvalEOSForElems4	124.25	0.92	0
	EvalEOSForElems5	80.25	0.01	0.01
	EvalEOSForElems6	961.96	0.2	0
	InitStressTermsForElems	1028.95	0.22	0.4
	IntegrateStressForElems1	14786.62	2.58	0.66
	IntegrateStressForElems2	5549.58	0.22	0.65
	TimeDump	174.5	0.13	0
	TimeIncrement	5.5	0.29	0.02
	UpdateVolumesForElems	143.54	1.18	0.5

https://www.mpi-forum.org/meetings/

https://www.openmp.org/about/members/

https://asc.llnl.gov/coral-2-benchmarks

https://github.com/rpereira-dev/LULESH1.3. OBJECTIVES AND CONTRIBUTIONS

https://github.com/nviennot/core-to-core-latency

https://colin-scott.github.io/personal_website/research/interactive_latency.html

http://www.nic.uoregon.edu/~khuck/ts/acumem-report/manual_html/ch03s02.html

https://en.wikipedia.org/wiki/Classic_RISC_pipeline

https://opengroup.org/aboutushttps://opengroup.org/aboutus

https://reports.opengroup.org/all.shtml

https://www.top500.org/

https://docs.kernel.org/driver-api/dmaengine/client.html

https://github.com/torvalds/linux/blob/a901a3568fd26ca9c4a82d8bc5ed5b3ed844d451/include/ linux/sched.h#L738-L1549

https://www.gnu.org/software/libc/manual/html_node/POSIX-Threads.html

https://github.com/torvalds/linux/blob/a901a3568fd26ca9c4a82d8bc5ed5b3ed844d451/kernel/time/ tick-common.c#L107-L147

https://awards.acm.org/bell

https://www.stroustrup.com/1st.html

https://www.youtube.com/watch?v=Bycec3UQxOc

https://github.com/python/cpython

In order to enable concurrent multi-threading, the Python Enhancement 703 (PEP703) proposes the removal of the global lock from the CPython runtime implementation, that restricts the interpretation of Python code to a single thread at a time. The Python community is (in 2023) still actively discussing.

https://docs.nvidia.com/cuda/cuda-runtime-api/

https://en.cppreference.com/w/cpp/thread/async

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

Over 8k stars on the public repository: https://github.com/taskflow/taskflow

https://github.com/mpi-forum/mpi-issues/issues/637

https://www.sandia.gov/portals/portals-4-0-specification-clone-2/

https://stackoverflow.com/questions/2427399/mpich-vs-openmpi -J. Hammond on differences between Open MPI and MPICH

https://github.com/OpenMP/Examples

https://github.com/llvm/llvm-project/issues/61499

https://github.com/mpiwg-hybrid/hybrid-issues/issues/6

https://github.com/devreal/ompi/tree/mpi-continue-master

https://github.com/cea-hpc/mpc

https://github.com/cea-hpc/mpc/tree/cea/2023/icpp-interop-tasks/src/MPC_OpenMP/tools/python

https://docs.google.com/document/d/1CvAClvFfyA5R-PhYUmn5OOQtYMH4h6I0nSsKchNAySU/preview

https://chromium.googlesource.com/catapult

https://ui.perfetto.dev

http://www.cecill.info/

https://www.chromium.org/developers/how-tos/trace-event-profiling-tool/

https://graphviz.org/

https://pm.bsc.es/ftp/ompss/doc/user-guide/faq-track-deps.html

https://www.olcf.ornl.gov/wp-content/uploads/2019/08/extrae_paraver_day_2.pdf

https://man.netbsd.org/NetBSD-8.0/i386/ucontext.2

https://reviews.llvm.org/D63196

https://reviews.llvm.org/D158416

https://pm2.gitlabpages.inria.fr/

https://netlib.org/benchmark/hpl/

https://hpcg-benchmark.org/

https://github.com/cea-hpc/mpc/blob/master/src/MPC_Common/include/uthash.h#L1120-L1125

https://reviews.llvm.org/D97085

https://github.com/yt-project/libyt

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

https://www.mpich.org/static/docs/v3.2/www3/MPI_Cancel.html

https://github.com/mpi-forum/mpi-forum-historic/issues/480

Acknowledgements

The first observation finds the same reasons as HPCCG: the runtime automatically prunes edges from already consumed predecessors. The second observation is explained in the following paragraph. The third observation is studied in Section 6.2.

The Impact of Dependency Hashing on the Graph Discovery

The MPC-OMP runtime relies on an hash table to build tasks precedence constraints. The runtime uses the uthash library [START_REF] Troy | uthash: A hash table for c structures[END_REF] that implements hash table methods summarized in [START_REF] Maurer | Hash table methods[END_REF]. The table hashes variables virtual memory addresses passed through the depend clause with tasks and infer precedence constraints following the standard specifications on dependency modifiers (in, out, inout, mutexinoutset, inoutset). Listing 6.8 is the data structure mapped by a dependency variable. The same dependency management relying on address hashing is used in GOMP, KMP, and Nanos6 (OmpSs-2); but GOMP/KMP implements their own hash tables, and Nanos6 uses the C++ std::unordered_map. We instrumented the MPC-OMP runtime and found out that get/put operations on this hash table were much slower on the low-performance peaks of the figure. Hence, we reproduced the same experiment varying the hashing function on Fig. 6.6. We compare the original MPC-OMP hash function also used in KMP (xor-6-2), GOMP (xor-0-32), Nanos6/MPC-OMP (div-8), and a Jenkins (lookup2) hash functions whose definition are provided in Listing 6.9.

Left-side figures report the parallel execution time (gray filled area), the single-thread discovery time (green dotted line), and the portion of the discovery time corresponding to hash map get/put accesses (blue dashed/dotted line). Right-side figures report the average number of collisions in the hash table for a single LULESH iteration.

The hash table was configured to resize automatically if more than 10 collisions for a given key occur, to preserve O(1) access costs. Nevertheless, the uthash implementation will not resize if it detects that the hash function is not a good fit for the key domain losing O(1) access time 3 . For some task grains, such as 1, 158 on xor-6-2, the number of collisions goes above 500 meaning that the function is not a good fit and that the runtime stopped resizing the hashmap; hence the peak number of collisions. This ends up slowing down hash map operations and therefore the graph discovery, which is ultimately bounding the execution time.

Another important result of these experiments is that in MPC-OMP, even for a "good fit" hash function (lookup2), the hash map accesses represent from 6% to 52% of the task graph discovery costs (37.17% on average), making it a critical component of the tasking runtime for dependency management overheads. Note that these costs is related to the number of expressed dependencies: reducing it while preserving the correct order of execution would reduce hash map accesses overheads. xor-6-2

Average number of collision Number of tasks per loop