Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping

Modern embedded platforms (e.g., NVIDIA Jetson series) implement complex processor architectures combining multicore systems with accelerator devices to provide high-performance capabilities to critical applications (e.g., automotive industry) [17]. Parallel programming models can be used in these systems to effectively exploit the parallel nature of applications, efficiently orchestrating parallel tasks while meeting the timing requirements of the system. One such parallel model is OpenMP. Although originally targeting shared-memory systems for the high-performance computing domain, this language has been increasingly used in real-time systems by virtue of its programmability and flexibility, combined with the quality to allow predictable execution.

From the large number of mechanisms provided in OpenMP, the tasking model is of particular interest for real-time systems because it abstracts computation in tasks, i.e., concurrent units of work that can express structured data parallelism and unstructured task parallelism. Furthermore, the execution of OpenMP tasks is organized as a task dependency graph (TDG), a form of direct acyclic graph (DAG), where nodes represent task instances and edges represent data dependencies between tasks.

OpenMP threads are abstractions of user-level threads that act as proxies of the actual physical processors. Accordingly, runtime implementations of the model, first, map tasks to OpenMP threads, which are in turn mapped to operating system (OS) threads (typically, pthreads), and these are mapped to actual cores. Based on this structure, there are several levels of freedom to provide OpenMP compliant implementations. To simplify the system and enhance the schedulability of OpenMP applications, this work considers that OpenMP threads are mapped one-to-one with OS threads, and these are equally mapped one-to-one to cores, and bind to these for the entire execution of an application (i.e., cannot migrate).

During the scheduling of an OpenMP task-based application, tasks are mapped to threads. This process can be carried out through a single queue, in which all threads access the same queue to insert (allocation phase) and pick (dispatching phase) tasks, or a multi-queue system, in which each thread has its own queue where to insert and pick tasks. In both cases, tasks are allocated to a queue only when their input dependencies are met, if any. Mainstream implementations of OpenMP use both methods, e.g., GCC uses a single-queue system while LLVM uses a multi-queue one, showing that the former typically introduces much more contention due to concurrent accesses to shared resources.

Schedulability is one of the main requirements in critical systems. When these systems are implemented using parallel programming models (e.g., OpenMP), the task-to-thread mapping process, whether employing global scheduling with online mapping decisions or partitioned scheduling with offline static mapping, can be efficiently adjusted to reduce worst-case response time (WCRT) and improve system schedulability. Schedulability is a property of a real-time task set that denotes whether tasks complete within their required deadlines under a scheduling algorithm, even under worst-case conditions. This process is necessary to avoid system failure. Although not strictly needed, application response time (and especially WCRT) should be reduced by selecting an appropriate scheduler to improve schedulability [4, 18, 10, 20]. In this way, the schedulability analysis of any mapping approach can be evaluated using schedulability tools based on random graphs or benchmarks.

The main issues with current evaluations of static task-to-thread mapping and their impact on OpenMP applications are that (i) they do not consider recently presented task-to-thread mappings, which may improve the schedulability of the system compared to previous methods, and (ii) analyses do not consider large and different configurations, like diverse applications with respect to their complexity, the number of threads used, and different possible deadlines. Accordingly, in this paper, the schedulability of OpenMP applications using recent task-to-thread mapping methods [16] are evaluated based on static scheduling, and compared to the literature. Overall, the main contributions of the paper can be represented as following:

1. 1.

   Applying a methodology for evaluating static task-to-thread mappings in OpenMP using an integration of our simulator and an existing schedulability analysis toolset.

2. 2.

   Analyzing schedulability of the recent heuristic task-to-thread mapping, compared to other relevant mappings, under different aspects, including small and large random graphs, based on partitioned mapping with the limited preemptive policy.

3. 3.

   Evaluating all the heuristic algorithms through analysis to identify their behavior in achieving acceptable schedulability.

The structure of the paper is organized as follows. Section 2 addresses a background on the main characteristics of OpenMP. Section 3 studies the related works by describing some of the existing task-to-thread mapping methods. Section 4 explains the system model and the proposed methodology for the analysis. Section 5 evaluates the schedulability of the mapping methods under simulations through different configurations. Finally, Section 6 concludes the paper.

OpenMP is a shared-memory parallel programming framework for high-performance computing (HPC), which has been increasingly used in heterogeneous embedded platforms. From the earlier versions of the specification, it supports a thread model that allows boosting loop-intensive and data-parallel applications. Later versions introduced first a task model to create irregular and highly dynamic parallelism and then a host-centric accelerator model built on top of the tasking one for offloading tasks to acceleration devices. The main metrics of interest for the tasking model are simplicity of use, compatibility with existing specifications for a “legacy” execution model, and performance [17]. Given these characteristics and the suitability of OpenMP tasks to represent real-time situations, this work focuses on the tasking model.

An OpenMP task-based program starts sequentially (initial thread) until a parallel construct is found. At this point, a team of threads is created, one implicit task is created for each thread with the code contained in the associated region, and all threads start executing their corresponding tasks. A single construct is typically used to allow only one thread to execute the structured block associated with the single region. That region can include multiple explicit tasks defined, for example, with the task directive. In this structure, the implicit task executed by the single thread is the parent of the nested explicit tasks, which are the child tasks of the former. Accordingly, the explicit tasks of the single region are siblings among them. Data dependencies can be defined between tasks through the depend clause and the in, out and inout modifiers, which define the directionality of the dependency. Tasks are ready to execute if they do not have any input dependency or these have been already satisfied, i.e., previous tasks without output dependencies on the same data objects have already completed their execution. The data-flow relation between tasks generated by the dependencies can be represented as a TDG. Besides the point-to-point synchronizations defined by dependencies, OpenMP allows defining memory fences through the taskwait directive, which forces the encountering thread to wait until all its child tasks finish. In the case of the barrier directive, child tasks, and any task generated inside those are waited for.

Regarding the binding of tasks to threads, OpenMP tasks can be categorized into tied, i.e., they can only be executed by the thread that started executing them, and untied, i.e., once suspended, any thread can continue their execution. Tasks are untied by default, unless a tied clause is attached to the task directive. The main feature of an untied task is that it favors a work-conserving strategy to map tasks to threads, enabling any idle thread in the system to execute a pending task.

This section presents the main features of the task-to-thread mapping methods in OpenMP used in the evaluations of this paper.

Serrano et al. [17] have addressed the predictability of OpenMP applications through the study of two schedulers: (i) a generic scheduler without using any concrete scheduling policy, and (ii) a breadth-first scheduler (BFS) [15], in which a thread that creates a task places it in the system and continues the execution of the encountering task, and work-first scheduler (WFS) [7], in which a thread that creates a task immediately executes it, both based on the first-in, first-out (FIFO) algorithm.

Melani et al. [14] have introduced two mapping policies for an OpenMP framework using a single queue for orchestrating tasks: optimal and sub-optimal allocations. The former policy uses a non-trivial integer linear programming (ILP), while the latter one uses several heuristic techniques. The optimal allocation is computationally expensive, but minimizes the makespan of tasks and also provides a reference point to evaluate other static and dynamic algorithms. In contrast, the sub-optimal allocation is not computationally expensive and, therefore, is more suitable for large task sets. In the sub-optimal policy, a ready task-part, i.e., the sequential task region between two TSPs, is selected from the queue using one of the heuristic algorithms, and the first idle thread is selected to execute the task-part. Note that TSPs are task scheduling points that dynamically divide task regions into multiple parts, where each part can be executed with an idle thread based on the order in the same task region. Among the heuristics provided, we have used the longest processing time (LPT), which selects the task with the longest worst-case execution time (WCET), the shortest processing time (SPT), which selects the task with the shortest WCET, and the largest number of successors in the next level (LNSNL), which selects the task with the largest number of immediate successors.

In a recent work [16], we have proposed a heuristic task-to-thread mapping, an extended version of the method presented in [9], to perform the mapping process in a multi-queue OpenMP system using different heuristic algorithms. This technique consists of two phases, allocation and dispatching. During allocation, one of the allocation queues is selected for each OpenMP task using one of the following heuristics: minimum number of task-parts (MNTP), next thread (NT), most recent idle time (MRIT), minimum total execution time (MTET), maximum total response time (MTRT), and total multi-criteria decision (TMCD). During dispatching, when a thread is idle, it selects one of the ready tasks from its queue, if any, using one of the heuristics: minimum execution time (MET), maximum response time (MRT), and multi-criteria decision (MCD). Task stealing is disabled in this technique to enhance the predictability of the system. This paper focuses on the schedulability analysis of OpenMP applications using these proposed heuristics, in comparison with that obtained using the other mapping approaches.

This section describes the system model used to generate random graphs (DAGs) and the tools used to evaluate the schedulability of the generated graphs.

This section describes the schedulability analysis results for the mapping approaches under different configurations obtained through simulation-based offline mapping. Specifically, it evaluates the efficiency of the heuristic task-to-thread mapping methods [16], compared to BFS [15], LPT [14], SPT [14], LNSNL [14], and WFPA [1, 19] (i.e., an algorithm to allocate tasks to threads based on having the least used utilization). The goal is to analyze the impact of the different mappings on the schedulability and WCRT of random graphs; therefore, an existing schedulability analysis tool [1] is used to compare the different algorithms under the same conditions. Note that the results for the NT-X heuristics in the heuristic mapping are not included here, as they do not perform as efficiently as the other algorithms in most cases.

This paper evaluates the recent heuristic task-to-thread mapping method, against other mapping methods, in terms of schedulability and WCRT. The evaluation is conducted based on various types of DAGs (including small and large graphs) under both implicit and constrained deadline policies. The results for single DAGs show that the efficiency of the heuristic mapping, in terms of improving schedulability and minimizing WCRT, are better than those of other methods in most cases.

In particular, the schedulability analysis results show that, when the utilization of task sets is 1, the efficiency of the proposed heuristics is better than the previous mapping methods in Case 2 (i.e., large graphs with implicit deadline) with 4 threads and Case 4 (i.e., large graphs with constrained deadline) with 8 threads. The reason is that when there are many tasks in the system (i.e., large graphs), the heuristic algorithms can select the most appropriate tasks from the queues. Therefore, the mapping’s work-conserving nature is improved, the program completes sooner (i.e., WCRT is reduced), and schedulability is improved.

Furthermore, these heuristics are more efficient than or equal to the other methods in Case 4 with 4 threads. The reason is that when the number of threads is low, the heuristic algorithms cannot select the most suitable queues for tasks, leading to a slight increase in WCRT and a reduction in schedulability, compared to the case with many threads. Their efficiency is comparable to that of the previous methods in Case 1 (i.e., small graphs with implicit deadlines) with 4 threads and Case 2 with 8 threads. The reason is that when the number of tasks is low (i.e., small graphs), the heuristics fail to select the most proper tasks during the allocation and dispatching phases.

Besides, the WCRT obtained using the heuristic algorithms is lower than that of previous mapping methods in most cases, especially in cases 2 and 4. The reason is that the most appropriate tasks can be selected using these algorithms, especially during the dispatching phase, based on their characteristics (e.g., execution time), when there are many tasks in the system. This flexibility improves the work-conserving nature of the mapping and considerably reduces the WCRT. All these evaluations indicate that the schedulability and quality of critical systems can be improved by utilizing the heuristic task-to-thread mapping.

As future work, schedulability analysis of real-world programs, especially those used in artificial intelligence applications with enormous workloads, will be conducted under different application and system configurations. Furthermore, schedulability analysis will be performed based on other policies, such as global or semi-partitioned approaches.