# Measuring and interpreting performances of HPC applications with dependent tasks

Romain Pereira, Thierry Gautier, Adrien Roussel, Patrick Carribault

► To cite this version:

Romain Pereira, Thierry Gautier, Adrien Roussel, Patrick Carribault. Measuring and interpreting performances of HPC applications with dependent tasks. Future Generation Computer Systems, 2025, pp.107933. 10.1016/j.future.2025.107933. hal-05112187

HAL Id: hal-05112187

https://hal.science/hal-05112187v1

Submitted on 14 Jun 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Measuring and Interpreting Performances of HPC Applications with Dependent Tasks

Romain PEREIRA<sup>a,1,*</sup>, Thierry GAUTIER<sup>a,*</sup>, Adrien ROUSSEL<sup>b</sup>, Patrick CARRIBAULT<sup>b</sup>

<sup>a</sup>Avalon, LIP, ENS, Inria, Lyon, 69007, France

<sup>b</sup>LIHPC, CEA, DAM, DIF, Arpajon, F-91297, France

**Abstract**

Breaking down the parallel time into work, idleness, and overheads is crucial for assessing the performance of HPC applications but is challenging to measure in runtime systems with dependent tasks. No existing tools allow its measurement accurately. This paper introduces POT: a tool-suite for parallel applications performance analysis with support for dependent tasks. We focus on its low-disturbance methodology consisting of parallel object modeling, discrete-event tracing, and post-mortem simulation-based analysis. The POT tool-suite allows the tracing and analysis of OMPT (OpenMP), PMPI (MPI) and pthreads events. The paper evaluates the accuracy of POT's analysis on LLVM and MPC-OMP implementations. It shows that measurement bias may be neglected above 16µs workload per task, portably across two architectures and OpenMP runtime systems. We also illustrate the benefits unveiled by POT post-mortem simulation approach for analyzing mixed programming models with MPI+OpenMP.

**Keywords:** High Performance Computing, MPI, OpenMP, Tasks, Performance Tool

**1. Introduction**

Massively parallel and heterogeneous architectures are the core elements of supercomputers [1]. Each processing unit is capable of asynchronous execution: some logic may run on CPUs while computation is running on GPUs, and data are transiting on the network. Mixing programming models to exploit the underlying asynchronous hardware entirely became a necessity. The mixed-use through *dependent tasks* is a promising solution, allowing fine control of workload synchronizations. Since 2013, the OpenMP standard specifications include dependent tasks. However, its use remains niche with few applications using it: one of the main issues is the lack of a standard tool for comprehensive performance analysis, particularly when mixing programming models [2, 3].

The first step in performance profiling often consists of breaking down the time into the useful work provided by programmers with the *non-work* [4, 5, 6]. Without fine comprehension of the executing environment - including the operating system, compilers, runtimes, and libraries - it can be challenging to explain *non-work*. It is usually [7] separated into *overheads* and *idleness* as shown in Fig. 1. N.R. Tallent et al. defines overheads as the additional inherent work of the parallel system for

<table><caption>Table 1: N.R. Tallent et al. methodology on parallel execution effectiveness</caption><thead><tr><th></th><th>Idleness</th><th>Overheads</th><th>Interpretation</th></tr></thead><tbody><tr><td>LL</td><td>low</td><td>low</td><td>effectively parallel; focus on serial performance</td></tr><tr><td>LH</td><td>low</td><td>high</td><td>coarsen concurrency granularity</td></tr><tr><td>HL</td><td>high</td><td>low</td><td>refine concurrency granularity</td></tr><tr><td>HH</td><td>high</td><td>high</td><td>switch parallelization strategies</td></tr></tbody></table>

orchestrating tasks over processing units and idleness as a lack of work to feed each one of them. Breaking down non-work time is fundamental: authors proposed the Table 1 to determine whether an execution is effectively parallel, confronting idleness and overheads to work time.

N.R. Tallent et al. [7] (2008) focused on *independent* tasks with Cilk [8]. S.L. Olivier et al.[9] (2013) did such a time breakdown with HPCToolkit [10] to measure work-time inflation induced by Non-Uniform Memory Accesses (data) latencies for independent OpenMP tasks. Breaking down non-work time into idleness and overheads was the starting point for identifying the task dependence graph discovery as a performance-limiting factor [11] (2023) on a task-based version of LULESH. No tools existed for quantifying parallel idleness and overheads of HPC programs using *dependent* tasks, which led us to design our own measuring within the Multi-Processing Computing OpenMP runtime (MPC-OMP). One source of difficulties for attributing parallel idleness and overheads lies in dependent task-based programming models themselves: the available parallel work varies dynamically over time as tasks predecessors complete. Instrumenting such program can distort the scheduling itself leading to measurements bias [12] and having analysts to draw wrong conclusions.

This paper introduces a low-disturbance measuring methodology for attributing parallel idleness and overheads in pro-

<figure><img src="image_2.png" /><figcaption>Figure 1: Breakdown</figcaption></figure>

<footnote>*Corresponding author</footnote>

<footnote>Email addresses: romain.pereira@inria.fr (Romain PEREIRA), thierry.gautier@inrialpes.fr (Thierry GAUTIER), adrien.roussel@cea.fr (Adrien ROUSSEL), patrick.carribault@cea.fr (Patrick CARRIBAULT)</footnote>

<footnote n="1">¹Permanent address: romain.pereira@outlook.com</footnote>
programming models with dependent tasks. Our contributions are:

* a formal definition of parallel idleness and overhead metrics for programs with dependent tasks,

* the modeling of OpenMP 6.0 tasks to a transition system, to fall onto the formal metric definition,

* the introduction of POT: a tool-suite for mixed programming models analysis relying on discrete event tracing and post-mortem simulation for low-disturbance analysis with support for OMPT and PMPI<fnref n="2" />.

* an extension of POT to support MPI Requests from specifications 4.1, with analysis on the overlap and early-bird posting of communications [13].

POT should contribute to improving performance evaluations of applications using dependent tasks. This paper is organized as follows. Section 2 review related works. Section 3 defines parallel overhead and idleness for dependent task-based programs and the modeling of OpenMP tasks. Section 4 presents POT and Section 5 evaluates its measurement accuracy. Section 6 introduces mixed-programming models analysis illustrated on MPI+OpenMP. Eventually, we conclude in Section 7.

## 2. Related Works

HPX [5] is a parallel runtime system and includes counters for performance metrics. In particular, it provides Task Overheads as $\frac{\text{non-work time}}{\text{\#tasks}}$ and Thread Idle-rate as $\frac{\text{non-work time}}{\text{total time}}$. While the metrics name suggests they are related to the time breakdown understudy, they only consider non-work time without distinguishing idleness/overheads as per POT (see Fig. 1). It significantly transforms performance interpretation: users would observe high Task Overheads in both N. R. Tallent's LH and HL setup, while they suggest opposite directions for optimizing.

M. Roth et al. [6] proposed a breakdown of parallel performance factors that can be seen as a refinement of N.R. Tallent [7] breakdown of parallel time. As opposed to POT, their measurement requires a reference sequential execution and instrumentation of each entry point of the parallel runtime. In addition, it may produce negative values when scaling super-linearly; it corresponds to work time deflation between two execution instances with POT.

TAU [14] and HPCToolkit [10] are tool suites for HPC applications performance analysis. None of them performs a bookkeeping of ready-tasks with respect to their dependences to compute a time breakdown.

V. Garcia et al. introduced a performance analysis framework for distributed task-based programs [15] illustrated on StarPU. Their analysis also relies on discrete-event tracing through runtime system instrumentation. However, they do not breakdown non-work time, and idleness/overheads interpretation is mainly visual making it subjective to the analyst, in

particular with the presence of visual artifacts. POT metrics provide a quantification with a time breakdown.

Cilkview [16] is a scalability analyzer for Cilk++ programs via Intel Pin instrumentation. Authors report an average slowdown of 2x to 10x. Integrating the Cilkview analysis algorithm in POT simulator as a new pass would be straightforward, similarly allowing the detection of scalability issues.

Eztrace [17] is a tool-suite for instrumenting HPC parallel programs with support for several programming models (OpenMP, MPI, pthread, Cuda, StarPU...). It can generate OTF2 traces that can be analyzed post-mortem to compute metrics or synthesize Gantt to be visualized in ViTE. As its design is close to POT, we conducted a comparison on the execution distortion in Section 5.1 of this paper. Converting POT traces to OTF2 would also be straightforward.

LTTng [18] is a tracing framework for Linux. It aims to collect software traces on complex architectures without significantly changing the system behavior and performances; a concern that POT attempts to address too.

Tikki is a tracing tool built-in Kaapi [19] that was later externalized to trace OpenMP programs with OMPT. We include it in our later evaluations of execution's distortion.

Against all these tools, the main benefits of POT is its post-mortem analysis framework - later referenced as a *programming model simulator* - with re-usable analysis *passes* that can be ordered to create hybrid programming model analysis.

## 3. Definitions for Idleness and Overheads

In practice, parallel idleness and overhead metrics are whether not quantified explicitly [20, 21], not considering dependencies [5, 6, 9], or measured on a specific runtime system [11]. It causes issues with performance interpretation and comparison between programming models and implementations. This section defines the metrics using task graph scheduling formalism [22], with a case study on the OpenMP dependent tasks. The following sections introduce a measurement implementation, discuss its portability, and evaluate its accuracy.

### 3.1. Formal Definitions

Let $\mathcal{P} = \{1, 2, ..., n\}$ with $n \in \mathbb{N}^*$ a set of processing units, and $(V, E)$ an application represented as directed acyclic graph with $V$ representing tasks as nodes, and $E$ precedence constraints as edges: $(u, v) \in E$ means that task $u$ precedes $v$, for instance, due to dependency. An *observation* is a triplet $(\sigma, a, d)$

* $\sigma: V \mapsto \mathbb{R}^+$ mapping tasks to their starting time,

* $a: V \mapsto \mathcal{P}$ mapping tasks to processors,

* $d: V \mapsto \mathbb{R}$ mapping nodes to their work time,

<footnote n="2">²https://gitlab.inria.fr/ropereir/pot</footnote>
<figure><img src="image_3.png" /></figure>

<table><caption>Figure 2: Modeling of OpenMP Specifications 6.0 Tasks as a Transition System in POT</caption><thead><tr><th>Transition</th><th>Occurs</th><th>Related OpenMP events</th></tr></thead><tbody><tr><td>(1) → (2)</td><td>- during a <b>task</b> or a <b>target nowait</b> construct<br>- or after a <b>predecessor task</b> completed</td><td>- <b>task_create</b>, <b>implicit_task</b><br>- <b>dependences</b>, <b>task_schedule</b></td></tr><tr><td>(2) → (4)</td><td>- on a <b>cancel taskgroup</b> construct</td><td>- <b>cancel</b></td></tr><tr><td>(2) → (5)</td><td>- on a <b>scheduling point</b><br>- after a <b>taskwait completion</b><br>- or after an <b>undeferred child task</b> executed</td><td>- <b>task_schedule</b><br>- <b>sync_region</b><br>- <b>task_schedule</b></td></tr><tr><td>(4) → (8)</td><td>- the discarded task completed</td><td>- <b>none</b></td></tr><tr><td>(5) → (2)</td><td>- on any task <b>scheduling point</b><br>- on a <b>barrier</b> construct<br>- or on a <b>taskwait</b> construct<br>- or on an <b>undeferred child task</b> construct<br>- or on a <b>taskgroup ending</b></td><td>- <b>task_schedule</b><br>- <b>sync_region</b><br>- <b>task_create</b></td></tr><tr><td>(5) → (4)</td><td>- on a task cancellation point</td><td>- <b>cancel</b></td></tr><tr><td>(5) → (6)</td><td>- after the task structured block executed</td><td>- <b>none</b></td></tr><tr><td>(6) → (7)</td><td>- after executing a <b>detachable task</b> with an <b>unfulfilled event</b></td><td>- <b>task_schedule</b></td></tr><tr><td>(6) → (8)</td><td>- after executing an <b>undetachable task</b>, or a <b>detachable task</b> with a <b>fulfilled event</b>, or an <b>implicit task</b> ended</td><td>- <b>task_schedule</b><br>- <b>implicit_task</b></td></tr><tr><td>(7) → (8)</td><td>- after a detached task event is fulfilled</td><td>- <b>task_schedule</b></td></tr><tr><td>(8) → (1)</td><td>- on completion of a task with the <b>replayable</b> clause on its construct</td><td>- <b>none</b></td></tr><tr><td>(8) → (9)</td><td>- whenever the task is deleted</td><td>- <b>none</b></td></tr></tbody></table>

A correct observation verifies the precedence (1) and the processor (2) constraints:

$$ \forall e = (u, v) \in E, \sigma(u) + d(u) \le \sigma(v) \quad (1) $$

$$ \forall (u, v) \in V^2, a(u) = a(v) \Rightarrow \left\{ \begin{array}{ll} \sigma(u) + d(u) \le \sigma(v) & \text{or} \\ \sigma(v) + d(v) \le \sigma(u) & \text{or} \end{array} \right. \quad (2) $$

A task $v \in V$ is ready at time $t$ if $t < \sigma(v)$ and $\forall e = (u, v) \in E$, $\sigma(u) + d(u) \le t$. Let $\delta_r : \mathbb{R}^+ \mapsto \{0, 1\}$

$$ \delta_r(t) = \begin{cases} 1 & \text{if any task is ready at time } t \\ 0 & \text{otherwise} \end{cases} $$

A processing unit $p$ is working at time $t$ if $\exists v \in V$ so that $a(v) = p$ and $\sigma(v) \le t < \sigma(v) + d(v)$. Let $\delta_w : \mathcal{P} \times \mathbb{R}^+ \mapsto \{0, 1\}$ be

$$ \delta_w(p, t) = \begin{cases} 1 & \text{if } p \text{ is working at time } t \\ 0 & \text{otherwise} \end{cases} $$

Note that $\delta_r$ is an information global to all processing units while $\delta_w$ is local. Given a processing unit $p \in \mathcal{P}$ and a time interval $I = [t_0, t_f]$, we define overheads (3) as the non-working time while there are tasks ready. Symmetrically, we define idle-

ness (4) as the non-working time with no ready-tasks.

$$ \text{overheads}(p, I) = \int_{t_0}^{t_f} \delta_r(t) (1 - \delta_w(p, t)) \, dt \quad (3) $$

$$ \text{idleness}(p, I) = \int_{t_0}^{t_f} (1 - \delta_r(t)) (1 - \delta_w(p, t)) \, dt \quad (4) $$

Note that $\delta_r$, $\delta_w$, and their product are piecewise constant functions. Therefore, overheads/idleness can be computed as a discrete sum over constant intervals. Hence, measurement difficulties stand in defining $\delta_r$ and $\delta_w$ for a given execution using a task-based programming model.

## 3.2. Task-based Programming Model: OpenMP case of study

In order to define $\delta_r$ and $\delta_w$ for a task-based program, we propose to model tasks as a transition system [23]. We illustrate on OpenMP. Since the introduction of explicit tasks [24], the OpenMP standard kept evolving towards a general-purpose task-based programming model. Our reading of the standard specification and experience as implementers lead us to the modeling depicted Fig. 2. The table links OMPT callbacks to task transitions. For instance, (1) → (2) may occur whether (a) on a task construct if the task has no dependence or if its predecessors had already completed; or (b) after its last predecessor's completion. Note that the same event can cause different transitions depending on the values of its recorded parameters.
Additionally, the formal model Section 3.1 allows only a single schedule per task, while OpenMP tasks can have multiple schedules via the cycle (2) → (5) → (3). However, falling back to the formal model is straightforward, subdividing OpenMP tasks into logically sequential segments interpreting a task suspension as a task completion plus a new continuation task creation, as per H. S. Matar [25]. Using the transition system, $\delta_r$ and $\delta_w$ can be trivially defined for OpenMP tasks:

$$ \delta_r(t) = \begin{cases} 1 & \text{if there is any task in state (2) at time } t \\ 0 & \text{otherwise} \end{cases} $$

$$ \delta_w(p,t) = \begin{cases} 1 & \text{if there is any task in state (5) on } p \text{ at time } t \\ 0 & \text{otherwise} \end{cases} $$

Consequently, computing $\delta_r$ and $\delta_w$ is deferred to a problem of bookkeeping task states over the execution: this is the purpose of POT, that we introduce in the next section.

# 4. POT - A Tool-suite For Dependent Task-based Programming Model Performance Analysis

A source of motivation behind the POT tool-suite is to compute metrics from parallel programming models with low distortion on the execution. For that purpose, POT is a two-step process. First, the analyst must record an execution using available plugins to generate trace files. Then, it can run analysis alongside post-mortem simulation from the trace files. This workflow is summarized in Fig. 3. The following sections introduce each component and present the implementation of a time breakdown for OpenMP-dependent tasks.

## 4.1. Plugins, Kernel and Trace files

Plugins are shared libraries that may overload symbols for instrumenting using LD_PRELOAD, or be loaded by the programming model implementation itself for finer-grain instrumentation on specific events. The kernel is responsible for recording events and flushing them onto trace files on specific events or on the program termination. To limit distortions on the execution, POT plugins and kernel follow two principles:

* (1) Limit events callback to recording only

* (2) Perform only thread-local operations

Events are time-stamped by the kernel using `clock_gettime` with `CLOCK BOOTTIME`. Using the OSJitter<fnref n="3" /> benchmark, we measured 16ns overheads for `clock_gettime` time-stamping on Intel(R) Xeon(R) Gold 6130 CPU. Then, the kernel queues a record into memory to copy the event's information. Events are queued into records buffer: per-thread user-space virtual memory that is allocated and written on the thread creation so that the operating system pre-allocates memory pages, reducing page fault occurrences during the recording. Currently, supported events are sized from 8 to 64 bytes. Section 5.1 conducts evaluations to quantify distortions introduced by POT on a set of benchmarks.

## 4.2. Simulator and Analysis Passes

<caption>**Algorithm 1** Simulation following discrete event in-order</caption>

In: $\mathcal{E}$ a set of events
1: $E := \{\}$
2: **while** $E \neq \mathcal{E}$ **do**
3:     $e := \min \mathcal{E} \setminus E$
4:     $d_t := e.time - \max\{x.time \mid x \in E\}$
5:     **for each** pass ordered by constraints **do**
6:         | Call pass($e$, $d_t$)
7:         $E := E \cup \{e\}$

Once a process recorded events have been saved to trace files, POT simulator replays them sequentially following the timestamp ordering keeping. Analysis passes can be plugged to run along the events' replay as callbacks, as shown on Algorithm 1. Each pass may modify the simulator state, such as programming models object states (OpenMP tasks, MPI requests...). Their order of execution can be ordered in a graph, ensuring both correctness of analysis and a separation of concern: each pass does a simple job. POT simulator currently implements 15 passes with partial support for OpenMP, MPI, and pthreads, only a few of them are introduced in this paper. The following section zooms onto OpenMP support, focusing on the time-breakdown analysis in the presence of dependent tasks that motivated this work.

## 4.3. A Zoom on OpenMP

POT can compute a parallel time breakdown in presence of OpenMP dependent tasks. We introduce its OMPT plugin and the two analysis passes for that purpose.

### 4.3.1. OMPT Plugin

The POT OMPT plugin is loaded using the standard OpenMP interface OMP_tool_LIBRARIES environment variable. Respecting our second principle (2) to limit distortions, the tool identifies tasks with a primary key (thread-id, task-id) so that each thread generates them independently. OpenMP standard specifications provide 37 events out of which the 10 following are recorded by POT OMPT:

* `thread_{begin|end}` records available CPUs assuming no over-subscription.

* `task_create` and `implicit_task` records task initialization (1).

* `task_schedule` is used for several transitions and needed to track transition to state (5) and compute $\delta_w$.

* `dependences` controls whether a task became ready after a predecessor completion: a key transition (1) → (2) for computing $\delta_r$.

* `task_dependency` is used only to count task dependencies reported by the implementation runtime system. However, it may not report all edges as the runtime itself

<footnote n="3">³https://github.com/gsauthof/osjitter</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 3: POT Workflow</figcaption></figure>

may prune some, for instance, when predecessors are completed before the successor creation. Therefore, this callback is insufficient to reconstruct the task dependency graph and using the *dependence* callback is required for a time breakdown analysis.

* `sync_region_wait` reports the start and completion of a `task` construct, hence controls task suspension and readiness on the cycle: (③ → (② → ⑤): transitions needed to compute $δ_r$.

* `sync_region` and `cancel` can be used to detect a `taskgroup`, its cancellation, and discarded tasks for transitioning (②, ⑤ → ④).

### 4.3.2. OpenMP Passes

The `omp` pass reconstructs task states along the recorded execution so analysis can compute and integrate ($δ_r, δ_w$). It is illustrated on Algorithm 2 on a few OMPT events. For instance, on a `task_create` event, the simulator allocates a new task to state 1, and may transition it to (②) if its dependences are fulfilled.

**Algorithm 2 Simulator - OpenMP Pass**
1: **procedure** ANALYZE(event *e*, time *d*<sub>t</sub>)
2: &nbsp;&nbsp;&nbsp;&nbsp;**switch** *e* **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**case** task_create with task
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Transition *task* to (1)
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** *task* has no dependences or
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*task'* predecessors completed **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Transition *task* to (2)
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**case** dependences with (*task*, *dependences*)
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Insert in TDG with respect to *dependences*
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** *task'* predecessors completed **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Transition *task* to (2)
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**case** task_schedule with
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*prior_task*, *prior_task_status*, *next_task*)
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Transition *next_task* to (5)
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** *prev_status* is executed **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Transition *prior_task* to (6)
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;...
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**case** ...

A second pass named `time-breakdown` depends on the `omp` pass. It integrates $δ_r$ and $δ_w$ provided by the simulator as

a discrete sum, accounting for time steps between two events. Line 2, we consider OpenMP threads as the set of processing units $\mathcal{P}$ needed in the formal definitions Section 3. Lines 3-5, if there is any explicit task running (↔ $δ_w(p, t) = 1$) then the time step is accounted as *work*. Lines 6-9, the time step is accounted as idleness or overheads respectively, if there are explicit tasks ready in the simulator (↔ $δ_r(t) = 1$) or not (↔ $δ_r(t) = 0$)

<caption>**Algorithm 3 Simulator - OpenMP Dependent Tasks Time Breakdown**</caption>

1: **procedure** ANALYZE(event *e*, time *d*<sub>t</sub>)
2: &nbsp;&nbsp;&nbsp;&nbsp;**for each** Thread *p* ∈ $\mathcal{P}$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** there is an explicit task running on *p* **then**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*work* := *work* + *d*<sub>t</sub>
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** there is any explicit task ready **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*overheads* := *overheads* + *dt*
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*idleness* := *idleness* + *d*<sub>t</sub>

### 4.4. Discussion: Portability of the Time Breakdown

We primarily focused on bridging POT with OpenMP through OMPT. As shown by the transition system Fig. 2, the OpenMP standard task programming model had become very generic with many task states and transitions. Shared-memory task-based programming models such as Cilk [8], Kaapi [19], Kokkos [26], OmpSs-2 [21] or StarPU [27] could most likely be mapped to the presented transition system. Hence, a straightforward bridging to POT is through the support of the OMPT event callbacks listed on Fig. 2, differing the portability responsibility to OpenMP. StarPU, Kaapi or OmpSs have already provided support for OpenMP interfaces in the past.

However, any task-based programming model may not be mapped to the presented task transition system. For instance, it is the case for distributed task-based programming models [5, 28, 29, 30] where tasks migrate between processes. POT would need extensions to support new events and interpret them into states and transitions. In addition, time-stamping in a distributed environment using different hardware clock references (i.e. TSC registers) introduces a new measurement bias. D. Becker et al. mention that "the analysis of such traces may yield wrong quantitative results and confuse the user" [31], and proposed post-mortem timestamps correction, that POT simulator could implement.
<table><caption>Table 2: Slowdown using OMPT instrumentation per tool against a non-instrumented execution</caption><thead><tr><th>Benchmark</th><th>Parameter</th><th>Ref. time (s.)</th><th>no-op</th><th>POT</th><th>TiKKi</th><th>OMPTrace</th><th>OmpTracing</th><th>HPCToolkit</th><th>Eztrace</th></tr></thead><tbody><tr><td>(b) alignment</td><td>prot.100.aa</td><td>1.19</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.03</td><td>1.00</td><td>1.00</td></tr><tr><td>(b) fft(2<sup>26</sup>)</td><td>n = 2<sup>26</sup></td><td>2.09</td><td>1.01</td><td>1.08</td><td>1.90</td><td>3.18</td><td>45.1</td><td>1.07</td><td>1.21</td></tr><tr><td>(b) fib.manual</td><td>n = 36</td><td>0.007</td><td>1.02</td><td>1.03</td><td>1.23</td><td>1.06</td><td>3.37</td><td>1.03</td><td>1.03</td></tr><tr><td>(b) health</td><td>medium</td><td>0.72</td><td>1.00</td><td>1.03</td><td>1.09</td><td>1.08</td><td>7.67</td><td>1.00</td><td>1.07</td></tr><tr><td>(b) nqueens</td><td>n = 12</td><td>0.037</td><td>1.00</td><td>1.00</td><td>1.03</td><td>1.00</td><td>1.17</td><td>1.01</td><td>1.00</td></tr><tr><td>(b) sort</td><td>n = 2<sup>26</sup></td><td>0.62</td><td>1.00</td><td>1.02</td><td>1.31</td><td>1.22</td><td>11.3</td><td>1.02</td><td>1.07</td></tr><tr><td>(b) sparselu</td><td>(n,m) = (2<sup>5</sup>, 2<sup>8</sup>)</td><td>5.57</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.01</td><td>1.00</td><td>1.00</td></tr><tr><td>(b) strassen</td><td>n = 2<sup>12</sup></td><td>1.05</td><td>1.00</td><td>0.99</td><td>1.03</td><td>1.00</td><td>0.98</td><td>1.05</td><td>1.02</td></tr><tr><td>(b) uts</td><td>tiny</td><td>3.83</td><td>1.03</td><td><b>1.21</b></td><td>2.64</td><td><i>err</i></td><td><i>err</i></td><td><i>err</i></td><td>1.67</td></tr><tr><td>(k) jacobi</td><td>(n,b) = (2<sup>15</sup>, 2<sup>8</sup>)</td><td>4.69</td><td>1.00</td><td>0.97</td><td>1.01</td><td><i>err</i></td><td><i>err</i></td><td>1.01</td><td>1.01</td></tr><tr><td>(k) sparselu</td><td>(n,m) = (2<sup>7</sup>, 2<sup>6</sup>)</td><td>3.16</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>44.3</td><td>1.02</td><td>1.02</td></tr><tr><td>(k) strassen</td><td>n = 2<sup>13</sup></td><td>5.40</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.99</td><td>1.10</td><td>1.01</td><td>1.00</td></tr><tr><td>average of all</td><td>w/o uts, jacobi</td><td>N/A</td><td>1.00</td><td><b>1.02</b></td><td>1.16</td><td>1.25</td><td>11.7</td><td><b>1.02</b></td><td><b>1.04</b></td></tr><tr><td>average of all</td><td>with uts, jacobi</td><td>N/A</td><td>1.01</td><td>1.03</td><td>1.27</td><td><i>err</i></td><td><i>err</i></td><td><i>err</i></td><td>1.09</td></tr></tbody></table>

## 5. Evaluation

We conducted several experiments to assess the precision of POT measurements. In our evaluations, we are using Debian 11 installed via Kadeploy on Grid5000 [32], on compute nodes made of 2x Intel(R) Xeon(R) Gold 6130 16-Core processor (Dahu cluster), LLVM 19.x compiler and OpenMP runtime (commit c40146c) and compactly binding threads to cores.

### 5.1. Slowdown induced by tracing tools

Our first experiment evaluates the slowdown induced by OMPT tools against the non-instrumented execution. We use two complementary suites of benchmarks: the BOTS (b) [33] for independent tasking and the KaStORS (k) [34] for dependent tasking. We extended the BOTS benchmarks with a warm-up phase for the OpenMP runtime and OMPT tools. We measure the slowdown over non-instrumented executions of the following tools:

* no-op is an OMPT tool implementing all OpenMP events callback with a no-op function.

* HPCToolkit [10], Eztrace [17], TiKKi [35], OMPTrace<fnref n="4" /> and OmpTracing [36] are OMPT tools.

Results are presented on Table 2. The first and second columns are the benchmarks configuration, the third one is the execution time of the reference version in seconds, and the other columns are the average slowdown per-tool for 10 runs. A few measurements did not complete due to too important slowdown (>50) or error during the execution, which is reported with an err entry. The penultimate and last line, respectively, shows the average slowdown excluding and including them.

The no-op results show that enabling OMPT introduces little slowdown, with less than 3% over non-instrumented execution on fib.manual and uts.

On average, HPCToolkit, Eztrace and POT yield the least slowdown. It must be noted that HPCToolkit only records the

<table><caption>Table 3: Number of OMPT events raised per microbenchmarks. (b) and (k) respectively stands for BOTS and KASTORS benchmarks</caption><thead><tr><th></th><th>implicit_task</th><th>task_create</th><th>task_schedule</th><th>dependences</th></tr></thead><tbody><tr><td>(b) alignment</td><td>66</td><td>5,110</td><td>20,120</td><td>0</td></tr><tr><td>(b) fft</td><td>98</td><td>7,794,576</td><td>31,177,984</td><td>0</td></tr><tr><td>(b) fib.manual</td><td>66</td><td>2,206</td><td>8,504</td><td>0</td></tr><tr><td>(b) health</td><td>66</td><td>486,341</td><td>1,945,044</td><td>0</td></tr><tr><td>(b) nqueens</td><td>66</td><td>1,636</td><td>6,224</td><td>0</td></tr><tr><td>(b) sort</td><td>66</td><td>679,883</td><td>2,719,212</td><td>0</td></tr><tr><td>(b) sparselu</td><td>66</td><td>3,409</td><td>19,940</td><td>0</td></tr><tr><td>(b) strassen</td><td>66</td><td>217</td><td>548</td><td>0</td></tr><tr><td>(b) uts</td><td>66</td><td>30,399,277</td><td>121,596,788</td><td>0</td></tr><tr><td>(k) jacobi</td><td>226</td><td>327,840</td><td>655,680</td><td>262,144</td></tr><tr><td>(k) sparselu</td><td>162</td><td>399,136</td><td>798,272</td><td>798,272</td></tr><tr><td>(k) strassen</td><td>226</td><td>2,582</td><td>6,532</td><td>2,166</td></tr></tbody></table>

task_create and implicit_task tasking events and that Eztrace does not record the dependences events. It means a post-processing analysis would not be able to analyze dependencies and compute the presented time breakdown.

The total number of events raised by OpenMP is reported on Table 3 for each microbenchmark. Each benchmark has a different event throughput. For instance, while jacobi and uts both executes in about 4s, uts raises about 100x more events which explains the slowdown observed.

The task_schedule event represents from 40% to 80% of all events raised, so skipping it when possible could reduce the slowdown on the execution. However, POT must record all of them for its analysis.

Finally, some instrumented executions are faster than non-instrumented executions. For instance jacobi with POT yields a 0.97 slowdown on average. Modeling execution times with Gaussian distributions, the reference executions has $(\mu_r, \sigma_r) = (4.69s, 0.015s)$ and POT has $(\mu_p, \sigma_p) = (4.56s, 0.011s)$ with a t-test $p \ll 0.05$ showing that instrumenting consistently accelerates the execution: we do not have the exact reasons on these instances of execution. However, we have observed similar accelerations on AMD EPYC 7352 (Servan cluster). Analyzing with Linux's perf showed that instrumented executions improved cache re-use over non-instrumented execution on fft, most likely because it alters the task scheduling constructively.

<footnote n="4">⁴https://github.com/passlab/omptrace</footnote>
## 5.2. Measurements Precision

Instrumentation slowdown is not sufficient to determine whether its execution has been distorted. For instance, an execution could be uniformly distorted, and metrics could still be representative of uninstrumented execution.

**Load Imbalance.** The load-imbalance micro-benchmark aims to determine the accuracy of POT time breakdown measurement in an absolute manner, comparing measured metrics with theoretically known values on a micro-benchmark. It is defined as follows. Given a *g* granularity parameter, each thread *t* ∈ [1, *n*) repetitively (*I* times) creates one task running for *t.g* µs with *g* ∈ ℝ⁺ and waits for their completion. On an ideal execution of a single-iteration with no overheads (events recording, task creation, scheduling, synchronizations...), we expect:

$$ (\text{work, idleness, overhead}) = \left( g \frac{n(n+1)}{2}, g \frac{(n-1)n}{2}, 0 \right) $$

**Results.** Fig. 4 presents measurements for *I* = 10,000 iterations. X-axes represent the *g* parameter, which is the finest task grain. The left-side figure y-axis reports measured and ideal time accumulated on threads (in s.) for the entire execution. The right-side figure y-axis reports the divergence (in %), that is, the relative distance between measurement to ideal values for both work and idle times. Refining *g* below 2µs for idle time and 128ns for work time, both lead to more than 20% inflated measurement reported by POT.

For *g* > 16µs, measurements are accurate with less than 3% divergence on work and idleness reported. At finer grain, we find several explanations for the observed divergence inflation. First, each task actively polls its execution time using `clock_gettime` to stop after *g.t* seconds. Hence, each task may run a few more nanoseconds than ideal (reminder: `clock_gettime` takes 16ns). A second part stems in the POT-OMPT instrumentation. OpenMP runtime raises event call-backs, which are recorded by POT-OMPT adding a few function calls and from 16 to 64 bytes of memory written. For instance, a `task_schedule` event is recorded after executing the task structured block. Therefore, the event recording is counted as part of the task work, leading to slight work inflation.

Regarding idleness, the ideal value neglects that the thread may idle a bit until tasks are created. Using the EPCC microbenchmark [37] `PARALLEL_TASK`, we measured 250 ± 56ns for an MPC-OMP task creation. Additionally, the barrier delay on each iteration introduces idleness time, which can be observed on the Gantt chart.

**Extensibility.** In order to show the extensibility of POT, we reproduced the experiment on a different hardware and OpenMP implementation. Table 4 reports results on Intel and AMD EPYC 7352 24-Core Processor using both LLVM OpenMP implementation and the Multi-Processor Computing OpenMP (MPC-OMP) runtime with the LLVM compiler. Table 4 reports results on Intel and AMD CPUs. The first column is the runtime, the second and third columns are grain

<table><caption>Table 4: Load Imbalance benchmark results extensibility</caption><thead><tr><th colspan="4">Intel(R) Xeon(R) Gold 6130 16-Core</th></tr><tr><th>Runtime</th><th>Work Div(&lt;20%)</th><th>Idleness Div(&lt;20%)</th><th>Overhead average</th></tr></thead><tbody><tr><td>LLVM</td><td>g ≥ 128ns.</td><td>g ≥ 2µs</td><td>0.36s</td></tr><tr><td>MPC-OMP</td><td>g ≥ 128ns.</td><td>g ≥ 4µs</td><td>2.64s</td></tr></tbody></table><table><thead><tr><th colspan="4">AMD EPYC 7352 24-Core</th></tr><tr><th>Runtime</th><th>Work Div(&lt;20%)</th><th>Idleness Div(&lt;20%)</th><th>Overhead average</th></tr></thead><tbody><tr><td>LLVM</td><td>g ≥ 128ns.</td><td>g ≥ 2µs</td><td>1.80s</td></tr><tr><td>MPC-OMP</td><td>g ≥ 128ns.</td><td>g ≥ 4µs</td><td>6.69s</td></tr></tbody></table>

parameters *g* for which measurements diverge by more than 20%, and the last column is the average overhead reported for all grains. Both processors have similar grain thresholds for work and idleness divergence. Runtimes have similar results on the minimal grain, although MPC-OMP introduces more overheads than LLVM on average.

## 5.3. Case of Study: LULESH

The Livermore Unstructured Lagrangian Explicit Shock Hydrodynamics (LULESH) is a proxy-application from CORALs [38, 39]. We conducted a case of study using POT on a porting of LULESH using OpenMP tasks with dependencies<fnref n="5" />, results are reported on Fig. 5. In this experiment, we fixed parameters (*size*, *iterations*) to (80, 128) varying the number of threads from 1 to 32 (x-axis) and the number of tasks per loop from 1 to 256 with a step of 8. Heatmap cell values report metrics measured for an execution. The figures report the parallel time accumulated over threads (left) with its time breakdown (right). Note that this experiment exhaustively tests various threads and task grains. POT users would compute these metrics on a single point of interest to assess the application’s performance.

We observe the three LL, HL, and LH configurations respecting Table 1 interpretation. We observed a similar time breakdown using MPC-OMP, and the best performance with LLVM are reached for 21 threads and 88 tasks per loop with a LL configuration. Refining tasks grain further-more produces HH case-scenario that had been previously attributed to the task dependency graph discovery on LULESH and optimized with *persistent* tasks to reduce both idleness and overheads [11]. Regarding distortion, we measured an average of 1.3% and 0.8% slowdown with LLVM and MPC-OMP over non-instrumented execution. However, we observed peaks up to 49% slowdown and 42% speed-up in LH configurations where the average task grain varies from 25 to 45µs. In such configurations, POT distorts the execution and it would take additional experiments for analysts to draw conclusions.

Note that POT analysis conducted previously [11] lead to significant performance improvement on LULESH characterizing the task dependency graph overheads as a limiting factor for performance; and showed that fine-grain depth-first task scheduling improved overall performances through a better balance between work deflation and tasking overheads.

<footnote n="5">⁵https://github.com/rpereira-dev/LULESH</footnote>
<figure><img src="image_5.png" /><figcaption>Figure 4: POT accuracy on LLVM 19.x OpenMP and Intel Cores</figcaption></figure>

## 6. Extending POT with Support for MPI

To open POT towards HPC applications hybridizing programming models, we extended its support with MPI. Notably, the MPI specifications define an *MPI Request* object to manage message passing between processes, which we modeled and implemented in POT. We perform two cases of study that motivate its mixed-use with OpenMP tasks: fine-grain communications using partitioned requests and the early-bird posting using task scheduling.

### 6.1. A Modeling for MPI Requests

MPI requests can be modeled with a single 4-state transition system depicted in Fig. 6, similarly to transition systems depicted in figure 2.3 of the specifications 4.1 [40]. It includes most interfaces related to MPI requests; for instance, after a success on an *MPI Test*, a request instance may transition to the state (1) or (3) respectively if it is *persistent* or not. It must be kept in mind that the state of an MPI request may not be rigorously representative of the actual network activity. Instead, transitions primarily relate to the user memory buffer to be transferred. For instance, MPI specifies that the programmer should not modify the buffer of a *send* request in state (2).

### 6.2. Definition and Analysis of the Overlap of MPI Requests with OpenMP Tasks

The overlap of communication with computation is the capacity of CPUs to be active while data transfers occur

asynchronously onto the network. The lack of overlap is often a bottleneck at scale. Dependent task parallelism implicitly addresses the overlap issue, having cores switching to ready tasks during synchronizations. This approach was used with SmpSs in [41], but the overlap itself was not explicitly quantified. Garcia et al. [15] proposed multiple visualization panels for task-based applications to understand performances from a given task scheduler. This approach is mainly visual, which may include artifacts leading to different interpretations depending on analysts' subjectivity. Richard et al. [42] proposed to report a global ratio that quantifies the overlap in the special case where MPI operations are serialized on a single thread. Reynier et al. [43] proposed an overhead ratio metric and benchmarks to quantify computational/communication overheads when overlapping MPI collectives; as per Richard [42], they only consider the activity on a single thread. We propose a definition to *quantify* the overlap of MPI requests with OpenMP tasks when both execute concurrently on multiple threads.

#### 6.2.1. Definition

We define the overlap of an MPI request *r* on a set of processing unit *P*, as the amount of work processed concurrently to data transfers over a time window $[t_0, t_f] \in \mathbb{R}$:

$$ overlap(r, t_0, t_f) = \sum_{p \in P} \int_{t_0}^{t_f} \delta_w(p, t) \delta_c(r, t) dt $$
<figure><img src="image_6.png" /><figcaption>Figure 5: LULESH time breakdown varying threads and tasks on LLVM 19.x</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 6: MPI Requests as a transition system</figcaption></figure>

where

$$ \delta_c(r, t) = \begin{cases} 1 & \text{if the request is in state ② at time } t \\ 0 & \text{otherwise} \end{cases} $$

Such definition for $\delta_c(r, t)$ aims to select time where there may be data transferring onto the network. We define an overlap ratio per MPI request as the portion of time where processing units work concurrently while there may be data transfers as:

$$ \text{overlapable}(r, t_0, t_f) = \int_{t_0}^{t_f} \delta_c(r, t) dt $$

$$ r_{\text{overlap}}(p, r, t_0, t_f) = \frac{\text{overlap}(p, r, t_0, t_f)}{\text{overlapable}(r, t_0, t_f)} $$

Finally, we reduce the overlap ratio for all MPI request and processing unit to get a single metric over a time window

$$ r_{\text{overlap}}(t_0, t_f) = \frac{\sum_r \sum_{p \in \mathcal{P}} \text{overlap}(p, r, t_0, t_f)}{|\mathcal{P}| \cdot \sum_r \text{overlapable}(r, t_0, t_f)} $$

### 6.2.2. Implementation

We implemented an MPI plugin using PMPI interfaces, overloading the runtime entry points and recording events related to MPI requests. We also extended the simulator with a pass that keeps track of MPI requests and their state over time and a second pass that computes the $r_{\text{overlap}}$ metric.

### 6.2.3. Case of Study: MPI Partitioned Communications

R. E. Grant et al. [13, 44] introduced partitioned communications that were adopted in MPI 4.0. Their design has been motivated by the use of multi-threading or tasking in MPI communication, making it an appropriate case of study candidate for POT. Listing 1 is a minimal example on the sender side. Line 1, we declare a buffer of $S$ char. Lines 2-5 initializes an MPI partitioned request with $P$ partitions, where the partition $p \in [0..(P-1)]$ holds the $B_S = S/P$ characters from $p \times B_S$ to $(p+1) \times B_S$ in buffer. Lines 6-17, the OpenMP primary thread creates $P$ tasks, each one writing a partition and marking it ready, which may be executed by any OpenMP threads of the parallel region. Finally, line 18 waits for the request completion.

```
1 char buffer[S];
2 MPI_Request req;
3 const size_t P = 1024;
4 MPI_Psend_init(buffer, P, sizeof(buffer) / P, MPI_CHAR,
                  DEST, TAG, MPI_COMM WORLD, MPI_INFO_NULL, &req);
5 MPI_Start(&req);
6 # pragma omp parallel
7 {
8   # pragma omp masked
9   for (int p = 0 ; p < P ; ++p)
10    {
11     # pragma omp task
12     {
13       write(buffer, p);
14       MPI_Pready(p, req);
15     }
16    }
17 }
18 MPI_Wait(&req, MPI_STATUS_IGNORE);
```

<caption>Listing 1: MPI Partitioned Communication</caption>

As a case of study for POT, we made a micro-benchmark to evaluate MPI partitioned against non-partitioned requests. On the receiver side, a single thread posts receive-requests and waits for their completion. On the sender-side, threads compute a $S$ bytes buffer and send it with MPI requests, with the three following modes:

* Non-partitioned (P:1). $P$ tasks compute and write $B_S = S/P$ bytes preceding a single task performing an `MPI_Isend` with a `detach` clause.
*   **Non-partitioned (P:P).** P detachable tasks compute and write $B_S$ bytes and send using `MPI Send init` and `MPI Start`, manually partitioning the buffer with P requests.

*   **Partitioned.** A task starts a partitioned request with an `MPI_Psend_init` and `MPI_Start`, followed by a detachable task waiting for its completion, and P tasks compute and write $B_S$ bytes, then mark the partition ready using an `MPI_Pready`, similarly to Listing 1.

**Results.** We executed the micro-benchmark on two AMD EPYC 7642 CPUs interconnected with 100 Gbps InfiniBand with 1 MPI process bound on each CPU. We used LLVM 19.x and OpenMPI 5.0.6 with 32 OpenMP threads bound 1:1 onto physical cores and 1 additional progression thread polling pending MPI requests. We are using the default OpenMPI configuration. We run 10 times per point, and Fig. 7 reports median and extreme values for $P = 1,024$ on the sender side, exponentially increasing the buffer size $S$ from 1KB to 1GB.

The upper-most figure reports the computational (work) and communication workload to perform. The work accumulates time spent within the P OpenMP explicit tasks to compute and write the buffer - that is the same in three modes. The communication is the time from the `MPI_Isend` to the completion of its associated `MPI_Wait`. We observe a gap between 32KB and 64KB due to a switch of the point-to-point protocol used (eager against rendez-vous [40]). The work time dominates the overall execution below $S = 64MB$.

The middle figure reports the wall-clock time to receive data on the receiver side. Even though the implementation of the Non-partitioned (P:1) is much more synchronous, it provides the best performances below $S = 2MB$. It is most likely due to the cost of managing multiple requests, partitions, and tasks. Using multiple requests against a single partitioned request provides similar performances.

The bottom figure reports the overlap ratio reported by POT, which we interpret for each mode as follows.

**Non-partitioned (P:1).** We expected an overlap ratio close to 0 as the P tasks of work are not concurrent with the single send. However, for small transfers, we observed and measured some overlap. On these points, the communication is using an eager protocol and is much faster; so the observed overlap comes from the time spent offloading the request to the progression thread. It corresponds to lines 3-4 of Listing 1: when nested within a task, this time is accounted as work until the thread returns to the OpenMP runtime and raises a `task_schedule` event. Above the eager threshold, we reach the expected 0% overlap ratio.

```
1 # pragma omp task detach(hdl)
2 {
3     MPI_Start(req);
4     progress_thread detach(req);
5 }
```

<figure><img src="image_8.png" /><figcaption>Figure 7: Evaluating benefits of MPI partitioned communications</figcaption></figure>

**Non-partitioned (P:P).** The overlap ratio is about 90% for most sizes, but measurements faces important variation above 8KB per request. The communication time follows similar variations, that may be linked to contention in the queue of our progression thread.

**Partitioned.** We observe an overlap ratio above 50% for all points indicating that threads spend half their time executing OpenMP explicit tasks concurrently to MPI requests progressing. Surprisingly, the overlap ratio is lower than the Non-partitioned (P:P) at fine grain. One reason is that the metric is "inflated" in the Non-partitioned (P:P), due to the $P = 1,024$ eager send requests offloading, similarly to Non-partitioned (P:1); while the Partitioned version only offload a single partitioned request.
*Conclusions.* This case study shows that a reduced overlap ratio must be interpreted carefully, particularly with the presence of many fine-grain communications. However, it can still hint at an application's internal behavior and its capacity to overlap MPI communications with OpenMP explicit tasks.

## 6.3. Early-bird Posting of MPI Requests

The early-bird posting of communications is a common heuristic to increase the overlap of communications with computations. It consists of posting communications as early as possible reduce bulk-synchronous use of the hardware and potentially reduce waiting time on remote processes waiting for the communicated data. Our second case of study illustrates how POT can assess on the benefits of an early-bird heuristic for MPI requests within an OpenMP task dependency graph.

### 6.3.1. Case of Study: Cholesky

The MPC-OMP runtime implements several strategies for controlling the task scheduling. We evaluate two of them:

* default: this is the default MPC-OMP scheduling with a depth-first manner in the task dependency graph,

* early-bird (automatic): the MPI and MPC-OMP runtime interoperates to favor tasks leading to MPI sends.

<table><caption>Table 5 reports the time breakdown obtained with POT on a Cholesky matrix factorization.</caption><thead><tr><th>Scheduling</th><th>Makespan</th><th>Work</th><th>Idleness</th><th>Overhead</th></tr></thead><tbody><tr><td>default</td><td>28.05 ± 1.58</td><td>20.70 ± 0.82</td><td>7.67 ± 1.96</td><td>0.18 ± 0.01</td></tr><tr><td>early-bird</td><td>27.25 ± 1.71</td><td>20.74 ± 1.57</td><td>6.62 ± 2.35</td><td>0.38 ± 0.20</td></tr></tbody></table>

<caption>Table 5: Cholesky Factorization Performances with and without task priorities with MPC-OMP and OpenMPI 4.1.5. 32 MPI processes of 24 OpenMP threads each bound compactly onto Intel(R) Xeon(R) Platinum 8168 processors. Times are given in seconds (s.)</caption>

We observe that task scheduling provides more overheads, which is largely compensated by decreased idleness, improving performances (makespan) overall. We explain the decrease by the early-bird scheduling strategy: by posting MPI sends earlier, we reduce idle periods on the receiver side due to missing data. Therefore, we extended POT with a pass that detects such a scheduling pattern.

## 6.4. A Summary on POT Passes

Fig. 8 summarizes POT passes introduced in this paper. Nodes represent individual passes, and edges are precedence constraint during the simulation.

* `omp-time-breakdown` is the parallel time breakdown for OpenMP dependent tasks,

* `mpi-omp-task-overlap` is the overlap of MPI requests with OpenMP explicit tasks,

* `omp` is the simulation of the OpenMP runtime,

* `mpi` is the simulation of the MPI runtime,

<figure><img src="image_9.png" /><figcaption>Figure 8: POT simulator passes dependency graph</figcaption></figure>

* `mpi-omp-early-bird` is the analysis reporting late scheduling of OpenMP tasks performing MPI sends.

This graph allows a separation of concern and the re-use of per-programming models passes for hybrid analysis.

## 7. Conclusion

HPC applications are evolving towards more asynchrony, mixing programming models with dependent tasks. Profilers must take into consideration the presence of dependences.

This paper provides a formal definition of a common parallel time breakdown with support for dependent tasks. We proposed POT: a tool-suite for programming models performance profiling, with support for OpenMP-dependent tasks and MPI. POT has a low impact on the execution, providing accurate and meaningful measurement by modeling parallel objects as transition systems, tracing events discretely during the execution, and simulating programming models execution post-mortem. While experiments suggest low distortion above 16µs per task on two different CPUs and runtime systems, the analyst should always compare their measurement with non-instrumented execution to avoid misinterpreting due to the presented measurement bias. Finally, we conducted several cases of study showing the interest of POT analysis for measuring and interpreting HPC applications' performances.

In the future, we consider adding support for hardware counters, to measure variations between two programming model events: a technique we used in previous work to show the impact of depth-first scheduling on temporal locality in OpenMP dependent tasks [11]. As MPI requests are too high-level abstraction, we plan to add more precise events to the NIC activity. Additionally, we plan to support CUDA, HIP, and Level Zero for GPU performance analysis. Finally, we consider adding support for hardware topology as part of the simulator.

## Acknowledgment

Parts of this work was financed as part of a Ph.D. at the Commissariat à l'énergie atomique et aux énergies alternatives (CEA). Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).
## References

[1] J. L. Whitt, Frontier Overview - OLCF Annual User Meeting (2022).
URL https://www.olcf.ornl.gov/wp-content/uploads/2022-OLCF-User-Meetig-Overview-of-Frontier-Whitt.pdf

[2] L. Meadows, K.-i. Ishikawa, Openmp tasking and mpi in a lattice qcd benchmark, in: B. R. de Supinski, S. L. Olivier, C. Terboven, B. M. Chapman, M. S. Müller (Eds.), Scaling OpenMP for Exascale Performance and Portability, Springer International Publishing, Cham, 2017, pp. 77–91.

[3] V. Garcia Pinto, L. M. Schnorr, L. Stanisic, A. Legrand, S. Thibault, V. Danjean, A Visual Performance Analysis Framework for Task-based Parallel Applications running on Hybrid Clusters, Concurrency and Computation: Practice and Experience 30 (18) (2018) 1–31. doi:10.1002/cpe.4472.
URL https://inria.hal.science/hal-01616632

[4] J. Giménez, E. Mercadal, G. Llort, S. Mendez, Analyzing the efficiency of hybrid codes, in: 2020 19th International Symposium on Parallel and Distributed Computing (ISPDC), 2020, pp. 29–36. doi:10.1109/ISPDC51135.2020.00014.

[5] P. Grubel, H. Kaiser, J. Cook, A. Serio, The performance implication of task size for applications on the hpx runtime system, in: 2015 IEEE International Conference on Cluster Computing, 2015, pp. 682–689. doi:10.1109/CLUSTER.2015.119.

[6] M. Roth, M. Best, C. Mustard, A. Fedorova, Deconstructing the overhead in parallel applications, 2012, pp. 59–68. doi:10.1109/IISWC.2012.6402901.

[7] N. R. Tallent, J. M. Mellor-Crummey, Effective performance measurement and analysis of multithreaded applications, in: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '09, Association for Computing Machinery, New York, NY, USA, 2009, p. 229–240. doi:10.1145/1504176.1504210.
URL https://doi.org/10.1145/1504176.1504210

[8] M. Frigo, et al., The Implementation of the Cilk-5 Multithreaded Language, in: Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, PLDI '98, Association for Computing Machinery, New York, NY, USA, 1998, p. 212–223.

[9] S. Olivier, B. Supinski, M. Schulz, J. Prins, Characterizing and mitigating work time inflation in task parallel programs, Scientific Programming 21 (01 2013). doi:10.3233/SPR-130369.

[10] J. Anderson, et al., Preparing for Performance Analysis at Exascale, in: Proceedings of the 36th ACM International Conference on Supercomputing, ICS '22, Association for Computing Machinery, New York, NY, USA, 2022.

[11] R. Pereira, et al., Investigating Dependency Graph Discovery Impact on Task-based MPI+OpenMP Applications Performances, in: Proceedings of the 52nd International Conference on Parallel Processing, ICPP '23, Association for Computing Machinery, New York, NY, USA, 2023, p. 163–172.

[12] T. Mytkowicz, et al., Producing wrong data without doing anything obviously wrong!, SIGPLAN Not. 44 (3) (mar 2009).

[13] R. Grant, M. Dosanjh, M. Levenhagen, R. Brightwell, A. Skjellum, Finepoints: Partitioned multithreaded mpi communication, 2019, pp. 330–350. doi:10.1007/978-3-030-20656-7_17.

[14] S. S. Shende, A. D. Malony, The Tau Parallel Performance System, Int. J. High Perform. Comput. Appl. 20 (2) (2006) 287–311.

[15] V. Garcia Pinto, L. M. Schnorr, L. Stanisic, A. Legrand, S. Thibault, V. Danjean, A Visual Performance Analysis Framework for Task-based Parallel Applications running on Hybrid Clusters, Concurrency and Computation: Practice and Experience 30 (18) (2018) 1–31. doi:10.1002/cpe.4472.
URL https://hal.inria.fr/hal-01616632

[16] Y. He, C. E. Leiserson, W. M. Leiserson, The cilkview scalability analyzer, in: Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '10, Association for Computing Machinery, New York, NY, USA, 2010, p. 145–156. doi:10.1145/1810479.1810509.
URL https://doi.org/10.1145/1810479.1810509

[17] F. Trahay, F. Rue, M. Faverge, Y. Ishikawa, R. Namyst, J. Dongarra, Eztrace: A generic framework for performance analysis, in: 2011 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 2011, pp. 618–619. doi:10.1109/CCGrid.2011.83.

[18] M. Desnoyers, M. Dagenais, The Ittng tracer: A low impact performance and behavior monitor for gnu/linux, OLS (Ottawa Linux Symposium) (01 2006).

[19] T. Gautier, X. Besseron, L. Pigeon, Kaapi: A thread scheduling runtime system for data flow computations on cluster of multi-processors, in: Proceedings of the 2007 International Workshop on Parallel Symbolic Computation, PASCO '07, Association for Computing Machinery, New York, NY, USA, 2007, p. 15–23. doi:10.1145/1278177.1278182.
URL https://doi.org/10.1145/1278177.1278182

[20] M. Myllykoski, A Task-Based Algorithm for Reordering the Eigenvalues of a Matrix in Real Schur Form, in: Parallel Processing and Applied Mathematics, 2018.

[21] D. Álvarez, K. Sala, M. Maroñas, A. Roca, V. Beltran, Advanced synchronization techniques for task-based runtime systems, in: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '21, Association for Computing Machinery, New York, NY, USA, 2021, p. 334–347. doi:10.1145/3437801.3441601.
URL https://doi.org/10.1145/3437801.3441601

[22] Y. Robert, Task Graph Scheduling, Springer US, Boston, MA, 2011, pp. 2013–2025. doi:10.1007/978-0-387-09766-4_42.
URL https://doi.org/10.1007/978-0-387-09766-4_42

[23] R. Keller, A fundamental theorem of asynchronous parallel computation, LNCS 24 (1975).

[24] E. Ayguade, N. Copty, A. Duran, J. Hoeflinger, Y. Lin, F. Massaioli, X. Teruel, P. Unnikrishnan, G. Zhang, The design of openmp tasks, IEEE Transactions on Parallel and Distributed Systems 20 (3) (2009) 404–418. doi:10.1109/TPDS.2008.105.

[25] H. S. Matar, D. Unat, Runtime determinacy race detection for openmp tasks, in: Euro-Par, 2018.

[26] H. C. Edwards, D. A. Ibanez, Kokkos' Task DAG Capabilities., Tech. rep., Sandia National Lab.(SNL-NM), Albuquerque, NM (United States) (2017).

[27] C. Augonnet, S. Thibault, R. Namyst, P.-A. Wacrenier, StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures, CCPE - Concurrency and Computation: Practice and Experience, Special Issue: Euro-Par 2009 23 (2011) 187–198. doi:10.1002/cpe.1631.
URL http://hal.inria.fr/inria-00550877

[28] W. Wu, A. Bouteiller, G. Bosilca, M. Faverge, J. Dongarra, Hierarchical dag scheduling for hybrid distributed systems, in: Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS '15, IEEE Computer Society, USA, 2015, p. 156–165. doi:10.1109/IPDPS.2015.56.
URL https://doi.org/10.1109/IPDPS.2015.56

[29] D. Callahan, et al., The cascade high productivity language, in: Ninth International Workshop on High-Level Parallel Programming Models and Supportive Environments, 2004.

[30] J. Klinkenberg, et al., Reactive Task Migration for Hybrid MPI+OpenMP Applications, in: Parallel Processing and Applied Mathematics, 2020.

[31] D. Becker, et al., Replay-Based Synchronization of Timestamps in Event Traces of Massively Parallel Applications, in: International Conference on Parallel Processing - Workshops, 2008.

[32] F. Cappello, et al., Grid'5000: a large scale and highly reconfigurable grid experimental testbed, in: The 6th IEEE/ACM International Workshop on Grid Computing, 2005., 2005.

[33] A. Duran, X. Teruel, R. Ferrer, X. Martorell, E. Ayguade, Barcelona openmp tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp, in: 2009 International Conference on Parallel Processing, 2009, pp. 124–131. doi:10.1109/ICPP.2009.64.

[34] P. Virouleau, P. Brunet, F. Broquedis, N. Furmento, S. Thibault, O. Auimage, T. Gautier, Evaluation of openmp dependent tasks with the kastors benchmark suite, in: L. DeRose, B. R. de Supinski, S. L. Olivier, B. M. Chapman, M. S. Müller (Eds.), Using and Improving OpenMP for Devices, Tasks, and More, Springer International Publishing, Cham, 2014, pp. 16–29.

[35] I. Daoudi, et al., sOMP: Simulating OpenMP Task-Based Applications with NUMA Effects, in: OpenMP: Portable Multi-Level Parallelism on Modern Systems, Springer International Publishing, 2020.

[36] V. Pinho, et al., OmpTracing: Easy Profiling of OpenMP Programs, 2020.

[37] J. M. Bull, et al., A Microbenchmark Suite for OpenMP Tasks, in: OpenMP in a Heterogeneous World, Springer Berlin Heidelberg, 2012.
[38] I. Karlin, J. Keasler, N. Rob, Lulesh 2.0 updates and changes (technical report), 2013.
URL https://www.osti.gov/biblio/1090032

[39] S. S. Vazhkudai, B. R. de Supinski, A. S. Bland, A. Geist, J. Sexton, J. Kahle, C. J. Zimmer, S. Atchley, S. Oral, D. E. Maxwell, V. G. V. Larrea, A. Bertsch, R. Goldstone, W. Joubert, C. Chambreau, D. Ap-pelhans, R. Blackmore, B. Casses, G. Chochia, G. Davison, M. A. Ezell, T. Gooding, E. Gonsiorowski, L. Grinberg, B. Hanson, B. Hart-ner, I. Karlin, M. L. Leininger, D. Leverman, C. Marroquin, A. Moody, M. Ohmacht, R. Pankajakshan, F. Pizzano, J. H. Rogers, B. Rosen-burg, D. Schmidt, M. Shankar, F. Wang, P. Watson, B. Walkup, L. D. Weems, J. Yin, The design, deployment, and evaluation of the coral pre-exascale systems, in: SC18: International Conference for High Perfor-mance Computing, Networking, Storage and Analysis, 2018, pp. 661–672.
doi:10.1109/SC.2018.00055.

[40] M. P. I. Forum, Mpi: A message-passing interface standard version 4.1,
https://www.mpi-forum.org/docs/mpi-4.1/mpi41-report.
pdf.

[41] V. Marjanovic, J. Labarta, E. Ayguadé, M. Valero, Effective communication and computation overlap with hybrid mpi/smpss, in: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '10, Association for Computing Machinery, New York, NY, USA, 2010, p. 337–338.
doi:10.1145/1693453.1693502.
URL https://doi.org/10.1145/1693453.1693502

[42] J. Richard, G. Latu, J. Bigot, T. Gautier, Fine-grained mpi+openmp plasma simulations: Communication overlap with dependent tasks, in: R. Yahyapour (Ed.), Euro-Par 2019: Parallel Processing, Springer International Publishing, Cham, 2019, pp. 419–433.

[43] A. Denis, J. Jaeger, E. Jeannot, F. Reynier, A methodology for assessing computation/communication overlap of mpi non-blocking collectives, Concurrency and Computation: Practice and Experience 34 (22) (2022) e7168. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/cpe.7168, doi:https://doi.org/10.1002/cpe.7168.
URL https://onlinelibrary.wiley.com/doi/abs/10.1002/cpe.7168

[44] W. Schonbein, S. Levy, M. G. F. Dosanjh, W. P. Marts, E. Reid, R. E. Grant, Modeling and benchmarking the potential benefit of early-bird transmission in fine-grained communication, in: Proceedings of the 52nd International Conference on Parallel Processing, ICPP '23, Association for Computing Machinery, New York, NY, USA, 2023, p. 306–316.
doi:10.1145/3605573.3605618.
URL https://doi.org/10.1145/3605573.3605618