Optimizing iterative data-flow scientific applications using directed cyclic graphs

Received 6 March 2023, accepted 14 April 2023, date of publication 24 April 2023, date of current version 1 June 2023. Digital Object Identifier 10.1109/ACCESS.2023.3269902 Optimizing Iterative Data-Flow Scientific Applications Using Directed Cyclic Graphs DAVID ÁLVAREZ AND VICENÇ BELTRAN Barcelona Supercomputing Center, 08034 Barcelona, Spain Corresponding author: David Álvarez (david.alv[email protected]) This work was supported in part by the European Union’s Horizon 2020/EuroHPC Research and Innovation Programme (DEEP-SEA) under Grant 955606; in part by the Spanish State Research Agency—Ministry of Science and Innovation, Generalitat de Catalunya, under Project PCI2021121958 and Project 2021-SGR-01007; in part by the Spanish Ministry of Science and Technology under Contract PID2019-107255GB; and in part by Severo Ochoa under Grant CEX2021-001148-S/MCIN/AEI/10.13039/501100011033. ABSTRACT Data-flow programming models have become a popular choice for writing parallel applications as an alternative to traditional work-sharing parallelism. They are better suited to write applications with irregular parallelism that can present load imbalance. However, these programming models suffer from overheads related to task creation, scheduling and dependency management, limiting performance and scalability when tasks become too small. At the same time, many HPC applications implement iterative methods or multi-step simulations that create the same directed acyclic graphs of tasks on each iteration. By giving application programmers a way to express that a specific loop is creating the same task pattern on each iteration, we can create a single task directed acyclic graph (DAG) once and transform it into a cyclic graph. This cyclic graph is then reused for successive iterations, minimizing task creation and dependency management overhead. This paper presents the taskiter, a new construct we propose for the OmpSs-2 and OpenMP programming models, allowing the use of directed cyclic task graphs (DCTG) to minimize runtime overheads. Moreover, we present a simple immediate successor locality-aware heuristic that minimizes task scheduling overhead by bypassing the runtime task scheduler. We evaluate the implementation of the taskiter and the immediate successor heuristic in 8 iterative benchmarks. Using small task granularities, we obtain a geometric mean speedup of 2.56x over the reference OmpSs-2 implementation, and a 3.77x and 5.2x speedup over the LLVM and GCC OpenMP runtimes, respectively. INDEX TERMS Taskiter, data-flow programming, ompss-2, openmp, iterative applications. I. INTRODUCTION Task-based programming models, pioneered by Cilk [1], have become popular for writing parallel applications since they are better suited than work-sharing models (such as OpenMP’s parallel for) to uncover parallelism from dynamic and irregular applications. Generally, these models allow programmers to express parallelism in a tree-like manner, recursively creating tasks. Under this nested-parallel structure, the The associate editor coordinating the review of this manuscript and approving it for publication was Claudio Zunino. cost of spawning each task is small, and scheduling can be done optimally through work-stealing. However, not all parallel applications can be easily written in a tree-like or recursive structure. To give programmers greater flexibility when writing parallel programs, data-flow programming models appeared as a subset of taskbased programming. In data-flow programming, parallelism is expressed as a directed acyclic graph (DAG) of tasks, where edges represent dependence relations needed to preserve sequential consistency. Some examples of these programming models include OpenMP Tasks [2], OmpSs-2 [3], PaRSEC [4], StarPU [5], Xkaapi [6] and TBB Graphs [7]. VOLUME 11, 2023 This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License. For more information, see https://creativecommons.org/licenses/by-nc-nd/4.0/ 51971 D. Álvarez, V. Beltran: Optimizing Iterative Data-Flow Scientific Applications Amongst data-flow programming models, some rely on users building the task DAG manually through a special syntax, and then scheduling these DAGs. This paradigm often comes at the cost of having to substantially alter a program to adapt it to the data-flow model. Other data-flow programming models such as OpenMP and OmpSs-2 tasking rely instead on implicit DAG creation. In this paradigm, users annotate their source code with tasks, and specify their data dependencies. Then, a runtime will build the DAG online, defining dependency relations based on the specified data dependencies. This model provides more productivity than manually defining the task DAG. Furthermore, the runtime can use the provided data dependencies to infer data-locality information, which can then be leveraged during scheduling. However, the cost of the extra productivity of implicit dataflow programming models is a larger tasking overhead. Creating tasks becomes more complexas data dependencies must be registered and tracked. Moreover, data-flow programs usually have a single thread creating tasks, which can become a bottleneck. Finally, scheduling becomes more challenging as well: as data-flow programming does not necessarily exhibit a recursive task creation pattern, and dependencies can have one-to-many relations, work-stealing scheduling algorithms can suffer from high contention. In this scenario, data-flow programs must regulate the size of the created tasks to minimize the relative impact of tasking overheads. This forces data-flow programmers to strike a balance in task granularity. We define task granularity as the duration of each task in an application [8]. The effects of task granularity on performance have been widely described in literature [9], [10], [11], [12]. Adverse effects are found both when task granularities are too small and when they are too coarse. When the granularity is too small, task creation, scheduling and dependency management become a bottleneck, and tasks cannot be created fast enough to feed all cores. This situation produces two adverse effects that hinder performance: First, some cores remain idle, as not enough work is being created. Second, as the number of tasks ready to execute is very low, there is little chance of applying locality-aware scheduling policies. However, when tasks are too coarse, there may not be enough tasks to feed all cores, the program can suffer from load imbalance, and locality-aware scheduling policies may lose effectiveness as task working sets grow and stop fitting in cache. Thus, we want to create tasks in a balanced region, where granularity is not too fine nor too coarse. This is normally achieved through granularity tuning, but there are relevant situations where tuning is impossible. For example, when the problem size is too small or when scaling out an application. In these cases, it is critical that the runtime efficiently supports small task granularities. To overcome this issue, data-flow programming models have been optimized over time to minimize these task management overheads [13], [14], [15]. Task creation is generally optimized using scalable memory allocators [16], [17]. Task scheduling is optimized with scalable scheduling techniques, such as work-stealing variants [18] or delegation-based schedulers [13]. Finally, task dependency management requires fine-grained locking or waitfree implementations to achieve good performance. However, these optimizations may not be enough to achieve competitive performance when very fine-grained tasks are needed. At the same time, many HPC applications present an iterative pattern, creating the same tasks with the same dependencies for each iteration. This results in identical tasks and dependency graphs concatenated one after the other. For example, this happens in iterative methods and solvers, machine learning training phases and multi-step simulations. As such, iterative programs can spend a significant amount of time creating, scheduling and managing tasks and dependencies that are the same for each iteration. This paper presents and implements two techniques that drastically reduce the main sources of runtime overhead in iterative data-flow applications. First, we propose a new taskiter construct for the OmpSs2 [3] and OpenMP [2] programming models. The taskiter construct annotates loops where each iteration generates the same directed acyclic graph (DAG) of tasks and dependencies. The runtime system then leverages this information to construct a directed cyclic task graph (DCTG) based on the DAG of the first iteration. Dependencies between different iterations are considered and linked in this new directed cyclic graph. In the DCTG, task descriptors and dependency structures are reused for each iteration, drastically reducing task creation and dependency management overheads for any iterations after the first one. The taskiter construct does not create any implicit barriers between iterations or after the construct, allowing it to be transparently mixed with successor or predecessor tasks or taskiter constructs. Secondly, we present a new immediate successor scheduling technique that preserves data locality while drastically reducing scheduling overheads by bypassing the scheduler. Unlike the taskiter, this technique is not restricted to iterative applications. We note that both proposals can be implemented in other data-flow programming models [4], [5], [6], [19], since the ideas are generally applicable. However, we focus on OpenMP and OmpSs-2 in order to provide a working implementation that can be compared to the current state-of-the-art. Finally, we will show in the evaluation how both contributions present a particular synergy that results in significant performance improvements for small granularities. Specifically, our contributions are as follows: 1) We propose the taskiter construct for OmpSs-2 and OpenMP to reduce runtime overheads in iterative dataflow applications. 2) We present the immediate successor scheduling technique designed to forego most of the scheduling overhead and maximize data locality. 51972 VOLUME 11, 2023 D. Álvarez, V. Beltran: Optimizing Iterative Data-Flow Scientific Applications 3) We implement both the taskiter construct and the scheduling policy on the state-of-the-art Nanos6 OmpSs-2 implementation, which is competitive with mainstream OpenMP implementations [13]. 4) We evaluate the taskiter construct on 8 iterative benchmarks and find an average speedup of 3x with a geometric mean of 2.56x for small task granularities. The rest of this document is structured as follows: Section II reviews the current state of the art, Section III introduces the taskiter construct and Section IV introduces the immediate successor technique. Then, we evaluate our contributions in Section V, and present the conclusions in Section VI. II. RELATED WORK The effects of task granularity on application performance have been thoroughly studied in literature [9], [10], [11], [12]. Moreover, several proposals to reduce task management and scheduling overhead have been proposed. A. TASK MANAGEMENT OVERHEAD Tasking overhead can be tackled through granularity tuning, runtime optimizations and model-oriented solutions. Automatic granularity tuning has been actively researched for task-based programming models. Multiversioning [20] can generate compiler transformations with different task granularities and choose the most appropriate at runtime. Another work explored using cut-off mechanisms [12], where the runtime decides the optimal cut-off point based on a userprovided cost function. Finally, in [21] authors propose an automatic oracle-guided granularity control mechanism for Cilk in which users may elide providing cost functions in some cases. Some works have focused on optimizations that can be applied to task-based runtimes to reduce synchronization overheads and scale better [13], [15]. Both granularity tuning and runtime optimizations are complementary approaches, which can be combined with model-oriented solutions such as the taskiter. Other approaches have focused on reducing task overheads by decreasing the total number of tasks that have to be created. Worksharing tasks [22] and Chapel’s coforall construct [23] can parallelize all iterations from a loop using a single task, reducing their overhead. Similarly, Index Launches [24] can automatically compact several task launches in a loop without need for explicit annotation. Polytasks [25] also merge several similar tasks when they are created at the same time, provided tasks are managed through queues. These approaches reduce the total number of tasks created by an application. In contrast, the proposed taskiter focuses on task reuse, and both approaches can be freely combined, as they are complementary. In [14], the authors propose the dep_pattern clause to cache data dependency patterns reducing dependency management overhead. Our proposal goes further, not only caching dependency structures but preventing task creation altogether. Moreover, the dep_pattern clause must be placed on a parent task, which in OpenMP would prevent placing dependencies between iterations to overlap their execution. Another approach is task DAG caching, provided by the CUDA Graph API [26], which allows GPU programmers to record a graph of kernel invocations and memory copy operations and re-invoke them, removing a significant amount of overhead. The graph API was also motivated by applications with an iterative structure, like machine learning training. However, CUDA Graphs require a barrier between iterations, which prevents the overlap of kernels from multiple iterations and limits the applicability of policies like the immediate successor. Similarly, OpenCL’s Command-buffer [27] allows programmers to record a DAG of OpenCL commands and then submit it multiple times in iterative applications. TBB Graphs [28] also allow task graphs that contain cycles, but the programmer must explicitly instantiate all nodes and edges of a task graph manually. A task DAG caching proposal for OpenMP is the taskgraph clause for the target and task constructs [29]. Similar to CUDA Graphs, authors present a way to record and re-play task DAGs for OpenMP tasks. However, the approach requires task DAGs to be defined inside their own dependency domain with an implicit barrier at the end. This barrier limits the applicability of policies like the immediate successor. Moreover, dependencies between tasks inside the construct and tasks outside it or in other replays are not allowed, breaking the data-flow execution model. The taskgraph model is a caching strategy and not a task DAG transformation like the one proposed in this paper. These task caching proposals can potentially improve the performance of iterative applications. However, as we will show in the experimental evaluation, the taskiter construct outperforms task caching approaches. B. SCHEDULING Many works have tackled overhead reduction in task scheduling. Scalable schedulers have been traditionally implemented through work-stealing [18], in which each creator thread has a local task queue and can steal from other creators if they run out of work, distributing the scheduling load. Delegationbased techniques [13] are also a suitable implementation, especially on data-flow models where there is often a single creator thread, and thus work-stealing does not offer significant benefits. Moreover, there have been proposals for locality-aware scheduling, mainly focused on preventing remote accesses on NUMA systems. For example in [30] authors develop a mechanism to accept data distribution hints on malloc calls and then leverage data dependency information to determine the best NUMA nodes to schedule a task. These approaches usually improve data locality at the cost of adding some overhead during task submission or scheduling. However, our focus is not on optimal locality but on improving VOLUME 11, 2023 51973 D. Álvarez, V. Beltran: Optimizing Iterative Data-Flow Scientific Applications locality while simultaneously eliminating most of the scheduling overhead. The philosophy for our scheduling work is similar to Cilk’s work-first principle [1]: to remove scheduling overheads from worker threads. However, the heuristic we propose in Section IV is adapted for data-flow applications, works well under any amount of available parallelism, and provides additional locality improvements. III. THE TASKITER CONSTRUCT Iterative applications often generate the same dependency graph on each iteration. Dependencies always form a directed acyclic graph of tasks, enforcing restrictions on execution order to maintain serial consistency. Additionally, some task instances from an iteration iwill depend on task instances from previous iterations, as we avoid using global barriers. An example of this pattern is shown in the left part of Figure 1, showing two iterations of an iterative application, which models a Gauss-Seidel method with a 4-block matrix. Dependencies between task instances of the same iteration are shown in solid lines, and dashed lines indicate dependencies between iterations. The taskiter construct is designed to prevent creating and executing the same DAG for each iteration. Instead, the programmer can express that a loop generates the same DAG N times. The programming model runtime will instead generate a directed cyclic task graph (DCTG), as shown in the right part of Figure 1. To build the DCTG the runtime executes the first iteration of the loop and generates a regular task DAG. When the first iteration ends, the left and right sides of the DAG are connected, as shown in Figure 1. This representation is then used to execute the remaining N−1 iterations, skipping task creation and significantly minimizing dependency management overheads. Specifically, dependency management consists of two main components. First, when tasks are created, the runtime must track which tasks are declaring a dependency on each memory location and then apply some logic to transform this information into dependencies between tasks. The second component is dependency release, which tracks the outstanding dependencies for each task, and schedules them when all predecessors have finished. While we cannot remove the overhead of dependency release, as it has to be done for every iteration, we can skip the first dependency management component and calculate the dependencies only in the first iteration. In essence, we create the task instances and their related data structures once and then reuse the same data structures for all following iterations. Moreover, the proposed DCTG representation is much more compact in memory than creating the task instances for every iteration. This leads to lower memory usage, which may otherwise be a problem for data-flow programming models when the number of task instances is very large. This model makes it possible to execute task instances from different iterations simultaneously in a pipelining effect, as the DCTG has no implicit barrier between iterations. This pipelining effect is shown on Figure 2, where thanks to iteration pipelining, the available parallelism is improved. Note that many previous approaches described in Section II did not allow pipelining. Additionally, dependencies from task instances on the first and last iterations can be matched to tasks outside the taskiter construct, maintaining the data-flow model. Note that the task instances of the first iteration can be executed while building the DCTG, not introducing any performance penalty. LISTING 1. Taskiter applied to a sample Gauss-Seidel Heat Equation application. reps is a matrix of representatives (one per matrix block). The syntax of the taskiter construct for OpenMP and OmpSs-2 is defined as the following: #pragma omp taskiter [clause [...]] new-line loop #pragma oss taskiter [clause [...]] new-line loop The loop can be any loop statement, provided it fulfills the following conditions: 1) The dependency graph generated by the tasks inside the construct must remain constant for each iteration. However, nested tasks do not have this restriction. 2) The program must remain valid if the code inside the loop body but outside any task is executed only once. This condition can be ignored if the update clause is specified, which we explain later on. The first condition is what the user is actually annotating with the taskiter construct: that the dependency graph for the loop repeats itself and thus can be optimized to a cyclic graph. However, this only needs to be true for first-level tasks (created directly in the loop body), but not for tasks created in deeper nesting levels, allowing irregularity between iterations. The second condition allows the implementation to execute the loop body only once. Programs can generally be adapted to fulfill this condition by taskifying any code inside the loop body. For example, we can apply the taskiter construct to an example Gauss-Seidel solver, which iterates through all blocks of a matrix in a wave-front pattern. This results in the code displayed in Listing 1. This code would fulfill the 51974 VOLUME 11, 2023 D. Álvarez, V. Beltran: Optimizing Iterative Data-Flow Scientific Applications FIGURE 1. Example iterative application, pictured on the left without using the taskiter construct, and on the right when using the taskiter construct. FIGURE 2. Possible execution trace of the application pictured in Figure 1, with and without inserting barriers between iterations. Task ijrefers to task ifrom the previous figure in iteration j. requirements of the taskiter, and it only requires the addition of Line 1 from the plain tasks version of this solver. In the current implementation, users must find suitable loops to apply the construct manually, similar to other OmpSs-2 and OpenMP constructs. The complexity of determining suitable loops to apply the taskiter on varies depending on the specific application. Generally, tracking usages of the induction variable in a loop is a straightforward way to determine if the task DAG changes, and does not require a full analysis of the target application. Moreover, this proposal could be combined with existing static and dynamic analysis tools [31] to facilitate the usage of the taskiter construct. Two new clauses can be combined with the proposed construct: •All clauses accepted in the task construct, since the taskiter is a task on itself. •The unroll(n) clause performs loop unrolling, executing the initial niterations instead of one. This clause can be used for loops with a regular dependency graph each niterations. For example, a loop that behaves differently for even and odd iterations can be unrolled two times to generate the cyclic dependency graph. Moreover, with the unroll clause it is possible to have interiteration dependencies of distance up to n. LISTING 2. Using dependencies between sibling tasks and tasks inside a taskiter region. •A taskiter with the update clause will generate a cyclic dependency graph for its tasks only once, but the loop body will be executed for each iteration. Each time the loop body is executed, the parameters used to create each task instance will be recorded, allowing tasks in the generated DCTG to have different parameters for each iteration. Use of the taskloop construct inside a taskiter is allowed, including taskloops with dependencies [32]. The taskiter construct itself can also have dependencies, which can be used to express a dependency from the first VOLUME 11, 2023 51975 D. Álvarez, V. Beltran: Optimizing Iterative Data-Flow Scientific Applications and last iterations of the taskiter to its sibling tasks. This is demonstrated in Listing 2, where using dependencies is convenient because the task in Line 13 can be created before the full DAG of the taskiter in Line 5 is registered. Task reductions are also supported inside a taskiter region. Nevertheless, OpenMP task reductions imply barriers between iterations, precisely what we try to avoid. To efficiently support reductions inside a taskiter region, in OmpSs-2 we synchronize the combination of reductions with dependencies instead of barriers [33]. The loop transformed by the taskiter does not need to perform a constant number of iterations; thus, executing the next iteration can depend on an arbitrary condition. However, when the loop does not have a run-time constant amount of iterations, the implementation must guarantee that the condition is checked between iterations and the taskiter is stopped when the condition becomes false. Otherwise, when the number of iterations is a run-time constant, the runtime is free to overlap execution of tasks instances from as many different iterations as the dependencies permit. A. IMPLEMENTATION When an OmpSs-2 or OpenMP compiler encounters a taskiter construct, it encapsulates one iteration of the following loop as a task. That task is instantiated and passed to the runtime with the number of iterations to execute and a flag indicating it is a taskiter. This special task is queued for execution and will execute the loop’s body once, creating any child tasks and registering the initial DAG. However, every child task instance will inherit an iteration counter from the taskiter to track how many times the task instance has to be executed. FIGURE 3. Implementation of the taskiter with top and bottom maps. Squares represent entries in the maps, and point to the first/last task to declare a dependency on a specific address. The snapshot of the data structures is taken before the transformation to a cyclic graph. When the runtime has finished executing the first body of the loop, it will access the bottom map, which is a data structure containing the last task that has declared a dependency on each memory location. It will match those tasks to the top map, which contains the first task that depends on each memory location. If locations match, there is a dependency from one iteration to the next, and we create an edge between the last and first tasks depending on that location. This edge is marked as crossing the iteration boundary. An example of the top and bottom map structures is shown in Figure 3. The pictured dependency graph corresponds to the attached code fragment. In this example, for memory location A, the top map points to task instance T1, which is the first to declare a dependency on A. Likewise, T2 is the last task instance to declare a dependency on A. Therefore, there is a cross-iteration dependency where T1 depends on the previous iteration’s T2. With these data structures, finding the cross-iteration dependencies is reduced to matching all entries from the bottom map to the ones on the top map. Whenever a child task finishes, it decreases its iteration counter, and unless it reaches zero, it will try to execute again if its dependencies are satisfied. Each task instance has two data structures that track outstanding dependencies: for even and odd iterations. This way, we do not have to reinitialize the data structures after each iteration. We can track dependencies simultaneously for the current and next iterations without inserting implicit barriers. Moreover, this technique allows us to maintain the wait-freedom of Nanos6’s dependency system. For applications where the transformed loop does not have a run-time constant number of iterations, a special task is inserted in the DCTG, which we call a control task. This control task depends on every leaf task, and every root task has a cross-iteration dependency on the previous iteration’s control task. Inside the body of this inserted task, we check the loop’s condition. If the condition is false, the taskiter is canceled and finishes. By default, taskiters with control tasks cannot pipeline tasks from different iterations, since the control task serializes iteration execution. However, these control tasks are strided when the taskiter is unrolled, providing means to overlap execution from different iterations. For example, on a taskiter with unroll(2), the control task executed after iteration i does not control the execution of iteration i+1, but instead controls the execution of i+2. This would allow a rolling window of two iterations being pipelined, and can be increased with larger unroll values. IV. IMMEDIATE SUCCESSOR Using the taskiter, we can minimize the overhead of task creation and dependency management. However, reducing those overheads shifts the contention to the remaining source of overhead: task scheduling. After introducing the taskiter in our benchmarks, we observed that the scheduler could become the bottleneck, limiting application performance. Specifically, the speed at which tasks are inserted and requested from the scheduler grows significantly, and so does contention on the locking system of the scheduler. The reference OmpSs-2 implementation currently features a delegation-based centralized scheduler based on [13], but the same contention can be observed in work-stealing implementations when there are few creators. 51976 VOLUME 11, 2023 D. Álvarez, V. Beltran: Optimizing Iterative Data-Flow Scientific Applications This section presents a scheduling policy that maximizes data locality for data-flow applications and can be applied without acquiring any scheduler lock. This way, we minimize the number of times any thread has to access the scheduler, reducing contention. This heuristic is based on a straightforward successor locality principle. When one task has a dependency relation with another task, defined by the list of memory locations in their dependency clauses, they probably share a part of their working set. The reasoning behind this principle is straightforward. Data dependencies specify which memory locations a task will access. If two tasks declare a dependency on the same location, both tasks will contain a memory reference to the same location, sharing a part of their working set. Formally, we define the working set of a task ti∈Tas W(ti), representing the set of all memory locations that ti accesses during its execution. Then, we can define a dependency relation, on which a task t1depends on a task t0as t1≻t0. This denotes constraints in execution order and means that t1and t0share at least one memory location on the declared data dependencies. Then, we propose the successor locality principle: ∀t0,t1∈T,t1≻t0→W(t0)∩W(t1)= ∅ Hence, for any pair of tasks t0and t1, if t1depends on t0, the intersection of their working sets is not empty. While it is possible to create a program on which the above statement is not valid, it matches the patterns observable on most HPC applications written using a data-flow model. Data locality is paramount when scheduling tasks because it allows applications to exploit the memory hierarchy when the working sets fit in any cache level. We can leverage this successor locality principle to bypass the task scheduler while simultaneously preserving data locality. We do this through the immediate successor mechanism, which works as follows: 1) Whenever a task finishes its execution, the worker thread executing it releases its dependencies and can mark one or more successor tasks as ready. 2) The first task with the highest priority marked as ready is kept into a local per-worker variable, becoming the immediate successor. The priority of a task is calculated from the priority clause, which the user specifies. 3) The remaining ready tasks (if any) are placed into the scheduler for other workers to grab. 4) If the worker has an immediate successor task, the scheduler is bypassed, and the task is executed next. This mechanism is illustrated in Figure 4, where a task DAG is introduced, followed by execution traces with and without the immediate successor. The sample task DAG is a subset of a matrix multiplication application. When executing without the immediate successor, each core will execute a ready task, free its dependencies, and then enter the scheduler to find the next ready task in the queue. No priority is given to newly released tasks. FIGURE 4. Sample task DAG and execution following the immediate successor heuristic. In contrast, when the immediate successor is enabled, cores will execute the newly ready tasks immediately. For example, when Task 1 ends, Task 6 is marked as ready. As Task 6 is the only task marked as ready, it will be assigned as the immediate successor, and executed immediately without entering the scheduler. Moreover, in the execution shown in Figure 4, the execution time of Task 6 will be reduced due to the presence of part of its working set in cache. Both the removal of scheduling overhead and the increased locality reduce the overall execution time when using the immediate successor mechanism. Note that we choose the first ready task amongst the ones with the highest priority as the immediate successor. However, choosing the first one is arbitrary, as every ready task follows the successor locality principle. While this policy is simple, it minimizes the number of times the scheduler is invoked, preventing contention. Moreover, as we show during experimentation, it achieves significant speedups for some applications thanks to its locality-preserving property. There is a trade-off when applying the immediate successor mechanism. Bypassing the scheduler can be problematic when executing applications that rely on specific scheduling policies (for example, task priorities). We can solve this issue by modifying step 2of the immediate successor algorithm, VOLUME 11, 2023 51977 D. Álvarez, V. Beltran: Optimizing Iterative Data-Flow Scientific Applications and adding a tunable probability that ready tasks are not marked as immediate successors, allowing threads to enter the scheduler every once in a while. V. EXPERIMENTAL EVALUATION To evaluate both the taskiter and the immediate successor (IS) policy, we implemented both features on top of the reference implementation for OmpSs-2. Most changes were located in the Nanos6 runtime, although we added compiler support for the construct in clang. Our changes in the Nanos6 runtime only add a small constant overhead to dependency management for tasks inside a taskiter, which does not depend on the number of iterations. The version of Nanos6 with support for the taskiter construct is available at https://github.com/bsc-pm/ nodes, and complementary material such as benchmarks and scripts are located at https://github.com/ dave96/taskiter-ieee-access-2023. A. METHODOLOGY We conducted the evaluation for the taskiter on a node equipped with an AMD EPYC 7742 (Rome) processor with 64 cores clocked at 2.25 GHz and SMT disabled. The system has 1TiB of main memory at 3200MHz. The software stack comprised a CentOS Linux 8.1 distribution with a Linux 4.17 kernel. We measured the performance when varying task granularity on a set of data-flow benchmarks. We used a combination of smaller benchmarks and larger established HPC applications. The goal is to gather a wide variety of computational patterns representing many scientific applications. Following, we include a brief description of each benchmark and explain their relevance for this experiment: •The Multisaxpy benchmark performs a loop of nSingle A·X+Ykernels over two arrays. Each iteration is embarrassingly parallel, stressing mainly task creation and scheduling. Dependent tasks share the totality of their working set, but this working set only fits in cache when task granularity is small. Thus, this application can clearly show the effect of low-overhead locality-aware scheduling policies. •The acoustic Full-Waveform Inversion is a proxy application for exploration geophysics. It implements an iterative method to generate high-resolution subsoil velocity models through collected seismic data. The FWI is divided into a forward propagation and a backward propagation phase, both acting on the modeled three-dimensional soil. Each created task has a large number of many-to-many dependencies, placing stress on dependency management performance. •The N-Body simulation performs several timesteps of the interaction of forces in a particle system. This benchmark is strongly compute-bound, thus data locality is generally not impactful. It places uniform stress on the components of data-flow runtimes, thus providing a reasonable estimate of the amount of overhead introduced. •The Heat Gauss-Seidel equation solver that was showcased in Listing 1. This application is a parallel stencil that displays a wave-front pattern. This implies that the amount of available parallelism varies throughout its execution. As such, this benchmark is sensitive to the introduction of barriers between iterations, as it prevents overlapping the execution of several iterations to hide the parallelism variations. It is strongly memory-bound. •The Heat (while), is the same application with a variable iteration count instead of a fixed number of iterations. It checks the solution’s convergence by computing a residual for each iteration. •The HPCCG is a proxy application for the Conjugate Gradients algorithm, which finds the solution to a sparse system of partial differential equations. It uniformly stresses the components of data-flow runtimes (like the N-Body), is memory-bound, and has 14 different task regions. •The HPCG [34] (High Performance Conjugate Gradients) benchmark, with a fixed iteration count, is an industry-standard benchmark for supercomputers. It features 41 different taskified parallel kernels, together with some wave-front phases. It is designed to reproduce computational and data access patterns representing a wide scientific application set. Moreover, task granularity varies during HPCG’s execution, making granularity tuning challenging. This benchmark is sensitive to both data locality and runtime overheads. •The HPCG (while) variant is the HPCG benchmark with a variable iteration count, checking for convergence on each iteration. We run two experiments to evaluate the proposed extensions. In the first experiment, we evaluate the performance of our taskiter and immediate successor policy using two task granularities: one where tasks are small, simulating a strong scaling scenario, and another where granularity is optimal. The main goal is to find out if the proposed extensions deliver performance improvements in two scenarios: an optimal case, where granularity tuning has already been manually done for each application, and a case where task granularity is constrained by the problem size or the number of total cores, and thus is inevitably small. We evaluate each proposal in isolation and then combine it with the rest. In the second experiment, we do a granularity study for each benchmark comparing the optimized Nanos6 against the reference implementation, other OpenMP runtimes and work-sharing versions of the benchmarks. Both experiments were repeated ten times. In every figure we plot average performance and standard error lines. Finally, after presenting the results, analyze the HPCG benchmark using execution traces. B. EXPERIMENT 1: EVALUATION OF PROPOSED EXTENSIONS In the first experiment, we measure the normalized performance, which is the performance of a specific execution 51978 VOLUME 11, 2023 D. Álvarez, V. Beltran: Optimizing Iterative Data-Flow Scientific Applications FIGURE 5. Performance comparison of different variants when executed with optimal and small granularities. relative to the maximum performance of all executions. This normalized performance is obtained based on the figure of merit provided by each application, and absolute performance figures for all granularities are presented later in Section V-C. We run the experiment on two different configurations to observe the most relevant task granularities: First, at the optimal granularity, where performance is in the optimal region. Second, when tasks are too small but still more than 50% peak performance is achieved. This second scenario simulates a strong scaling situation, thus evaluating the scalability of each solution. These granularities were obtained by running a granularity study for each benchmark and selecting: the task size which delivers the maximum performance, and the smallest task size that results in more than 50% of the maximum performance. The complete granularity study is available in Section V-C. In this experiment, we test seven variants of the Nanos6 runtime to verify the effect of both the taskiter and the immediate successor policy: 1) Tasks is the base OmpSs-2 version of the application, using tasks with dependencies, and no immediate successor. 2) Tasks +Immediate Successor (IS) is the same as the Tasks version but applies the immediate successor policy. However, this immediate successor is only applied inside the synchronization mechanism for the task scheduler. 3) Tasks +IS Outside Scheduler is the Tasks version using the immediate successor policy and bypassing the scheduler when possible. 4) Task Caching is the application adapted to simulate a task caching approach. We implemented the semantics of the taskgraph construct [29], where all data structures are cached between iterations, but without transformation or matching. In other words, it is a taskiter with a barrier between iterations. of dependencies between one iteration and the next. 5) Taskiter is the application adapted to use a taskiter to transform the main loop into a cyclic graph. 6) Taskiter +Immediate Successor (IS) is the same as the Taskiter version but applies the immediate successor policy inside the scheduler’s synchronization mechanism. 7) Taskiter +IS Outside Scheduler is the Taskiter version using the immediate successor policy and bypassing the scheduler when possible. Note that we split the evaluation for the IS policy into two parts. First, we apply the logic behind the immediate successor policy, but every task still has to go through the existing scheduler queues (the Immediate Successor version). This way, we can measure when performance increases thanks to better data locality instead of just the reduction of scheduling overhead. In the second part, we also use the immediate successor to bypass the scheduler altogether when an appropriate candidate is found, reducing the contention in the scheduler (the IS Outside Scheduler version). Additionally, we compare every result with two different OpenMP runtimes: the GOMP runtime provided by GCC 10.2.0 and the LLVM OpenMP Runtime on its 13.0.0-rc1 version. We chose to compare against the GCC runtime as a reference implementation for OpenMP, and against the LLVM runtime because it is based on the Intel OpenMP runtime, which is known to have very competitive performance. Figure 5a shows the performance of each evaluated version versus the maximum figure of merit for each benchmark. Note that we stack the improvements of the immediate successor policies. For instance, the solid orange color bar refers to the Tasks version, while lighter orange bars show VOLUME 11, 2023 51979