An Interrupt-Driven Work-Sharing For-Loop Scheduler

In this paper we present a parallel for-loop scheduler which is based on work-stealing principles but runs under a completely cooperative scheme. POSIX signals are used by idle threads to interrupt left-behind workers, which in turn decide what portion of their workload can be given to the requester. We call this scheme Interrupt-Driven Work-Sharing (IDWS). This article describes how IDWS works, how it can be integrated into any POSIX-compliant OpenMP implementation and how a user can manually replace OpenMP parallel for-loops with IDWS in existing POSIX-compliant C++ applications. Additionally, we measure its performance using both a synthetic benchmark with varying distributions of workload across the iteration space and a real-life application on Sandy Bridge and Xeon Phi systems. Regardless the workload distribution and the underlying hardware, IDWS is always the best or among the best-performing strategies, providing a good all-around solution to the scheduling-choice dilemma.


INTRODUCTION
Most parallelism in shared-memory parallel programming comes from loops of independent iterations, i.e. iterations which can be safely executed in parallel. However, distributing the iteration space over the available computational resources of a system is not always a simple thing. Finegrained control of distribution is often associated with high overhead whereas static partitioning of the iteration space can lead to significant load imbalance. In both cases, the impact on performance is serious.
Research on an advanced for-loop scheduler was motivated by our work on PRAgMaTIc [12], a hybrid OpenMP/MPI mesh adaptivity framework. Profiling data revealed that many of PRAgMaTIc's parallel loops are highly diverse, involving irregular computations which introduce high levels of iteration-to-iteration load imbalance. Existing scheduling strategies provided by OpenMP fail to achieve good balance with low scheduling overhead, whereas adaptive mesh algorithms which constantly modify mesh topology make it impossible to balance workload a priori.
We wanted the new scheduler to be portable and easily plug-able into the widely-adopted OpenMP API, so that it can target an as wide as possible range of systems, like Fujitsu's FX-10, a SPARC64-based supercomputer [6]. Those portability requirements prohibit the use of platform-or vendor-specific threading mechanisms and parallel libraries, like Intel R Cilk TM Plus [11,5,3]. On the contrary, they call for a POSIX-compliant implementation, based on the fact that most operating systems used in scientific computing are POSIX-compliant and most compilers (e.g. Linux versions of gcc, icc, xlc, etc.) implement OpenMP threads as POSIX threads (we have found it out by experimenting with those compilers). Of course, since every OS has threading and signalling mechanisms, the new scheduler can be implemented into any compiler on any OS.
The main contributions of this article are the following: • Present an new interrupt-driven work-sharing scheduler (IDWS) which can easily be used with existing POSIX-compliant OpenMP applications • Demonstrate how OpenMP loops can be converted to IDWS loops • Describe how a compiler vendor can incorporate the new scheduler into their product • Show using a variety of benchmarks that IDWS is a good all around solution to the scheduling-choice dilemma, always being among the best-performing strategies in all benchmarks The rest of this paper is organized as follows: Section 2 provides an overview of loop scheduling options currently available, listing their advantages and weaknesses. In Section 3 we describe the new scheduler, the way it works and explain why it offers a better tradeoff between load balance and scheduling overhead compared with other alternatives. Section 4 goes into details about the current implementation in C++ and explains how it can be used to replace OpenMP for-loops in existing codes. We demonstrate the scheduler's performance in Section 5 using both a synthetic benchmark and real for-loops from PRAgMaTIc. Finally, we conclude the paper in Section 6.

BACKGROUND
OpenMP offers three different scheduling strategies for parallel loops: static, dynamic and guided [7]. There is also a more advanced scheduling technique, known as "workstealing", which is implemented by libraries such as Intel Cilk Plus, though it is not part of the OpenMP specification, nor is it supported (to the best of our knowledge) by any OpenMP implementation. In this section we will present these four options and compare them in terms of load balance, scheduling overhead and overall efficiency.

OpenMP static
Under the static scheduling scheme, the iteration space is divided into equally large chunks which are then assigned to threads. This can be seen in the first example in Figure 1.
Partitioning of iteration space is done statically at the beginning of the for-loop, so there is zero scheduling overhead.
On the other hand, this scheme can lead to significant load imbalance, especially in a highly diverse loop.

OpenMP dynamic
Dynamic scheduling is a first approach to the problem of load imbalance. Instead of a static partitioning of the iteration space, chunks of work are assigned to threads dynamically. Once a thread finishes a chunk, it takes the next available from the iteration space. This is shown in the middle example in Figure 1. Access to chunks is done via atomic updates of the loop counter; a thread acquiring a chunk reads the current value of the loop counter and increments it atomically by the chunk size.
Dynamic scheduling solves imbalance problems as threads proceed to the next iterations of the for-loop in a fine-grained way. As an immediate consequence, good load balance comes at a cost. The loop counter is updated atomically and this constitutes a 2-way source of overhead. The two components of overhead are related to instruction latency and thread competition. The time it takes to execute an atomic instruction can vary anywhere between a standard update in L1 (if the thread performing the update is running on the same physical core as the thread which last updated the shared variable) and an update in RAM (if the last thread to update the shared variable is running on another socket in case of NUMA systems). This may not be a problem in short for-loops, but becomes easily a hotspot in loops with millions of iterations and little work per iteration (i.e. when atomic instruction latency is comparable to the loop body itself). Secondly, as the number of threads increases, so does the competition for the shared variable, leading to either (depending on the architecture) increased locking or increased number of failed update attempts, thus making atomic instruction latency even longer.
It could be argued that this overhead can be mitigated by increasing the chunk size, therefore lowering the number of times a thread will need to access the loop counter. On the other hand, increasing the chunk size can introduce load imbalance once again. Additionally, it is usually impossible to know the optimal chunk size at compile time and/or it can vary greatly between successive executions of an algorithm. Besides, relying on the chunk size for performance optimization puts an extra burden on the programmer.
We have found that using dynamic scheduling over guided in PRAgMaTIc can increase the execution time of specific algorithms by up to three times, as will be shown in Section 5. Following that, dynamic scheduling was rejected as an option for that framework.

OpenMP guided
The guided scheme is an attempt to reduce dynamic scheduling overhead while retaining good load balance. The key difference between the two strategies is how chunks of work are allocated. Whereas in dynamic scheduling the chunk size is constant, the guided scheme starts with large chunks and the size is reduced exponentially as threads proceed to subsequent iterations of the for-loop. This can be seen in the last example of Figure 1. Initial large chunks account for reduced atomic accesses to the loop counter while the more fine-grained control towards the end of the loop tries to maintain good load balance.
For the most part, guided scheduling works well in PRAg-MaTIc, yet there are cases where we have observed significant load imbalance. This can happen if, for instance, most of the work in an irregular loop is accumulated in a few of the initial big chunks. In a case like that, threads processing the "loaded" chunks are busy for long while others go through the remaining "light" iterations relatively quickly and reach the end of the for-loop early, waiting for the busy workers to finish as well.

Work-stealing
Work-stealing ( [4,13]) is a more sophisticated technique aiming at balancing workload among threads while keeping scheduling overhead as low as possible. The generic workstealing algorithm for a set of tasks [4] can be summarized as follows. Each thread keeps a deque (double-ended queue) of tasks to execute. While the deque is full, the thread pops workitems from the front. Once the deque is empty, the thread becomes a thief, i.e. it chooses a victim thread randomly and steals a chunk of workitems from the back of the victim's deque.
For a parallel for-loop with a predefined number of iterations N the deques can simply be replaced with pairs of indices < istart, i end > corresponding to the range in the iteration space [istart, i end ) which has been assigned to each thread, 0 ≤ istart, i end < N . In this case, every thread executes iterations by using istart as the loop counter whereas thieves steal work by decrementing a victim's i end .
Accesses to those pairs of indices can lead to race conditions, so they need to be accessed with atomics. Following that, work-stealing for for-loops comes close to OpenMP's dynamic scheduling with some chunk size > 1, with a major difference being that in work-stealing threads do not compete all together for atomic access to the same shared vari-static dynamic guided Thread 0 Thread 1 Thread 2 Thread 3 Figure 1: Example with four threads of the three scheduling strategies offered by OpenMP: static, dynamic (chunk=2) and guided. Note that under the guided scheme chuck size is reduced exponentially.
able (the common loop counter); instead, congestion is rare and happens only if two thieves try to steal from the same victim.
Performance can still suffer from load imbalance and scheduling overhead when using work-stealing. The main drawback of the classic work-stealing algorithm is that thieves choose victims randomly. There is no heuristic method to indicate which threads are more suitable victims (i.e. have more remaining workload) than others. Stealing comes at a cost and picking victims with too little or no remaining work is inefficient, as it leads to the need for frequent stealing which induces some overhead. Additionally, failed attempts do not help balance the workload. As an example of an extreme case, a single thread becomes the sole remaining worker while the rest waste time trying to steal from each other in vain.
Mitigating the effects of random choice was our main concern when designing the new for-loop scheduler. We devised a low-overhead heuristic method for finding appropriate victims. At the same time, we tried to reduce scheduling overhead by eliminating the need to use atomics when accessing each thread's < istart, i end > pair. The following section describes in detail how the scheduler is implemented.

INTERRUPT-DRIVEN WORK SHARING
Our new scheduler differs from existing work-stealing approaches in two major ways. First of all, as was mentioned in Section 2.4, every worker constantly "advertises" its progress so that thieves can find suitable victims which have been left behind. Secondly, a thief does not actually steal work from the victim in the classic sense; instead, it interrupts the chosen victim by sending a POSIX signal. The signal handler executed by the victim encapsulates the code with which the victim decides what portion of its remaining workload can be given away. As it becomes apparent, the new scheduling algorithm is much closer to work-sharing than work-stealing, therefore we call it Interrupt-Driven Work-Sharing (IDWS). Nonetheless, we will use work-stealing terminology throughout this article.
The abstract description of this scheme can be split into three parts: Algorithm 1 Parallel loop executed by each thread for i = istart; i < i end ; i ← i + 1 do flush i ⊲ from register file to memory, so that ⊲ thieves can see this thread's progress execute i th iteration flush i end ⊲ from memory to register file, as it may ⊲ have been modified by the signal handler end for Algorithm 2 Work-stealing for all threads tn do remainingt n ← i end,tn − istart,t n − it n end for let T ← tn for which remainingt n = max send signal to victim T wait for answer update own istart, i end execute loop chunk Loop execution (Algorithm 1). Every thread executes the iterations of the chunk it has acquired in the same way as it would using OpenMP's static scheduling scheme. Initially, the iteration space is divided statically into chunks of equal size and every thread tn is assigned one chunk. The chunk's boundaries for thread tn, referred to as istart,t n and i end,tn , are globally visible variables accessible by all threads. Compared to static scheduling, the important addition here is some necessary flushing of the loop counter it n and the loop boundary i end,tn . More precisely, the value of it n has to be written back to memory (instead of being cached in some register) at the beginning of every iteration so that potential thieves can monitor tn's progress, calculate how much work is left for tn and decide whether it is worth stealing from it. Similarly, the end boundary i end,tn has to read by tn from memory (instead of caching it in some register) before proceeding to the next iteration because i end,tn might have been modified by the signal handler if a thief interrupted tn while the latter was executing an iteration of the for-loop.
Choosing suitable victims (Algorithm 2). By flushing their loop counters, threads advertise their progress so potential thieves can find where to steal from. When a thread becomes a thief, it calculates the remaining workload for all other threads by reading the associated values it n , istart,t n and i end,tn . This way, we have a heuristic method for finding which thread has the most remaining work, thus being a more suitable victim than others. This heuristic may not be optimal, but is an improvement over random choice. Once the thief has spotted its victim, it sends a signal and waits for an answer. The victim executes the signal handler and replies with the boundaries (a pair of < istart, i end >) of the chunk it wants to give away. Finally, the thief becomes a worker once again and moves on to process the newly acquired chunk.

Signal handler (Algorithm 3). When a victim is inter-
rupted by the signal, control is transferred by the operating system to the associated handler. Inside that code, the thread calculates how much work it can give away (if any), replies to the thief with the boundaries of the donated chunk, re-adjusts the boundaries of its own chunk and finally returns from the signal handler.
It is clear that there are no races and no need for atomic access to any loop variables during the stealing process, as the donor is the one who decides what will be donated. Of course, switching from user to kernel mode to execute the signalling system call and busy-waiting for a reply from the victim involves some overhead; however, as will be shown in the results section, this method seems to be more efficient than classic work stealing.

C++ IMPLEMENTATION AND USAGE
This section describes how the IDWS scheduler is implemented and how it can replace existing OpenMP for-loops.

IDWS namespace
IDWS is a namespace encapsulating all necessary data structures and functions used by the new scheduler. Its declaration can be seen in Code Snippet 1. struct IDWS::thread_state_t. The heart of IDWS is a struct named thread_state_t, which encapsulates all variables involved in parallel loop execution and work-stealing. Each participating thread has its own instance of this struct, which is accessible by all other threads. The struct can be seen in Code Snippet 2. • processed: Is used by a thread to advertise its progress through the loop • current_ctx: IDWS loops are nowait loops, which means that a thread can proceed to the rest of the program without synchronising with other threads. In order to know whether two threads work inside the same loop, so stealing work from one another is valid, a counter current_ctx is used, which is incremented each time a thread finishes a loop. Here we assume that all threads will go through all loops of the program.
• active: Indicates whether the thread is inside the loop; this variable is used by thieves to skip immediately threads which have also become thieves.
• signal_arg: POSIX signals can only have two arguments, what signal is to sent and to whom. The victim needs to know, however, who the thief is, so sig-nal_arg is used by the thief to send its ID to the victim.
• comm_lock: In order to avoid needless busy-waiting by other thieves while one thief has already sent a signal to its victim, we use a lock (in form of a mutex); while this lock is held by a thief, other thieves will choose other victims to steal from.
• ptid: POSIX ID of the thread; it is used by the thief to raise the signal.
• request_mutex and wait_for_answer: POSIX mutex and condition variables which assist the process of sending the signal and waiting for a reply.
Note that we need two separate mutexes and cannot use re-quest_mutex in place of comm_lock. The former is implicitly released by the thief in order to enable the victim to signal the condition variable; in the meantime, before the victim locks request_mutex, another thief might acquire the lock and destroy the process.

Signal handler. A victim decided what portion of its chunk
can be donated by executing the signal handler. The way it is done is described in Code Snippet 3. The victim first checks that the thief works in the same context. Then, it calculates how much work it can give away using start, end and processed, also leaving a safety margin due to an uncertainty regarding the true value of processed. In case of success, the victim updates both the thief's and its own start and end and sets sig_arg=1 to indicate successful donation (otherwise, sig_arg is set to another value). Finally, the victim signals the condition variable to let the thief know that the signal handler is over.

Prologue and epilogue macros
The new scheduler is defined in two parts, using macros IDWS_prologue and IDWS_epilogue. These macros must surround the loop body.
IDWS_prologue macro. Before entering a loop, the iteration space is split into equal chunks which are assigned to threads. After that, each thread begins the execution of its chunk. Compared to a standard for-loop, a IDWS for-loop is defined slightly differently. Apart from checking for the end of the loop and incrementing the counter after every iteration, in IDWS we must also enforce the compiler to flush the counter back to memory and load the updated value of i end from memory (which might have been modified by the signal handler), as indicated by Algorithm 1. Flushing is done selectively for those two variables by casting them to volatile datatypes. Using #pragma omp flush would flush the entire shared program state, which is not efficient. A pseudo-code of how the macro expands is given in Code Snippet 4. Parameters TYPE, NAME and SIZE correspond to the datatype of the loop counter, its name and the size of the iteration space, respectively. In the current implementation of the new scheduler we assume that loops run from 0 to SIZE with increments of 1 and that the loop counter is of an unsigned integral datatype.
IDWS_epilogue macro. After a thread finished its chunk, it becomes a thief. That means it has to enter the stealing process, as described in Algorithm 2. The IDWS_epilogue macro serves this purpose. The way the macro expands can be seen in Code Snippet 4. The thief calculated for all active workers the amount of remaining work. Then, starting from the worker with the highest remaining workload, it tries to acquire the worker's comm_lock. If no suitable worker is found, then the thief exits the IDWS loop and proceeds to the rest of the code. Otherwise, the thief locks the victim's mutex, sends the signal and waits on the victim's condition variable for an answer. The answer comes via sig_arg.
If sig_arg==-1, then the victim has set the thief's start and end variables, so the thief becomes a worker again.
If any other answer has been sent back, then the thief exits the IDWS loop. It is important to note that a memory fence is necessary on the thief's side between setting the victim's signal argument sig_arg and raising the signal, so that we make sure that the victim will see the correct value of sig_arg. Locking the victim's mutex before sending the signal works as an implicit memory fence. The new scheduler can be used directly with virtually any C++ OpenMP application written for any POSIX-compliant operating system (provided that the compiler used implements OpenMP upon pthreads). A prerequisite for converting an OpenMP loop to a IDWS one is that the former is written as shown in Code Snippet 5, i.e. the loop must be inside an omp parallel region. Conversion to IDWS loops is shown in Code Snippet 6. The user needs to include header file "IDWS.h" which can be downloaded from PRAg-MaTIc's page on Launchpad 1 . This header file defines the IDWS namespace and the prologue and epilogue macros. Compared to the initial version, we need to define:

OpenMP to IDWS
• int nthreads=omp_get_max_threads(): shared variable outside the parallel region • int tid=omp_get_thread_num(): thread-private variable inside the parallel region , remove the #pragma omp for directive and the for-loop declaration and, finally, surround the loop-body with the IDWS_prologue and IDWS_epilogue macros.  In order to measure the performance of our new scheduler, we ran a series of tests using both synthetic benchmarks and real kernels from the PRAgMaTIc framework. We used three systems: a dual-socket Intel Xeon E5-2650 (Sandy Bridge, 2.00GHz, 8 physical cores per socket, 2 hyperthreads per core, 32 threads in total), a dual-socket Intel Xeon E5-2643 (Sandy Bridge, 3.30GHz, 4 physical cores per socket, 2 hyperthreads per core, 16 threads in total) and an Intel Xeon Phi 0b/01 board (1.2GHz, 61 physical cores, 4 hyperthreads per core, 244 threads in total). The two Xeon systems run Red Hat Enterprise Linux Server release 6.4 (Santiago). Both versions of the code (intel64 and mic) were compiled with Intel Composer XE 2013 SP1 using the -O3 optimisation flag. The benchmarks were run using Intel's thread-core affinity support with the maximum number of available threads on each platform. Additionally, we ran a second series of benchmarks on Xeon Phi using half the available number of threads and more specifically using all 61 cores with 2 hyperthreads per core. We did so because we have observed that for some codes Xeon Phi performs best when using this threading configuration.

EXPERIMENTAL RESULTS
The synthetic benchmark was designed to be compute-bound with minimal memory traffic and no thread synchronization. Our purpose is to show how the different scheduling strategies compare to each other in terms of achievable load balance and incurred scheduling overhead without being affected by other factors (such as memory bandwidth, data locality etc.  butions of workload and total amount of work. Each population has been given a name: • Regular: All elements of states are set equal to 2. This is a distribution corresponding to a regular loop which does the exact same thing in every iteration.
• Random: states is populated with random values following a uniform distribution. This sub-benchmark corresponds to real-life distributions in problems like graph coloring or the swap and smooth kernels in PRAg-MaTIc.
• Dense End: Most of the workload is accumulated towards the end of the iteration space, where states[i]=3, while the beginning is populated with a uniform mixture of values [0..3). The rest of the iteration space is set to 0, i.e. no work. This is a distribution closely related to the refinement kernel in PRAgMaTIc.
• Dense Start: Mirrored distribution of Dense End. Closely related to the PRAgMaTIc's coarsening kernel. This is an example of workload distribution for which OpenMP guided scheduling is a bad choice.
• Periodic: There is a repeating pattern of states throughout the iteration space. It is particularly bad for static scheduling with interleaved allocations of iterations (i.e. with some chunk size).
Apart from the synthetic benchmark, we also ran PRAg-MaTIc using the various scheduling options in order to see how each strategy performs in a real-life scenario, where compute capacity is not the only performance-limiting factor. It should be noted that PRAgMaTIc is build upon OpenMP, so there are no results for Cilk+ in this case. Table 1, Table 2 and Tables 3 & 4 show the execution time on the three platforms, respectively, using six scheduling strategies for each distribution of the synthetic benchmark and the four PRAgMaTIc kernels. The strategy named "OMP static,1" is static scheduling with chunk size equal to 1. As can be seen, IDWS is either the fastest scheduling option or very close to the fastest for each benchmarkplatform combination. Additionally, it clearly outperforms Cilk Plus, with the performance gap becoming wider as the number of threads increases and Cilk's design to pick victims in a random fashion becomes inefficient. Those results are a good indication that IDWS is future-proof and ready for the thousand-core era.
Regarding PRAgMaTIc, IDWS's major competitor seems to be OpenMP's guided scheduling. Despite not being very suitable for certain kernels (coarsening) theoretically, in practice it performs just as well as IDWS. A notable exception is the 244-thread case on Xeon Phi, where guided scheduling is the worst choice among the available options.
A comparison of relative performance between the three major competitors (IDWS, OpenMP guided and Cilk Plus) is shown in Figure 2 (Intel Xeon E5-2650 system), Figure 3 (Intel Xeon E5-2643 system), Figure 4 (Intel Xeon Phi with 122 threads) and Figure 5 (Intel Xeon Phi with 244 threads).
For each benchmark, we compare the relative execution time between IDWS, OpenMP guided and Cilk Plus (for PRAg-MaTIc kernels there is only IDWS vs OpenMP guided comparison). Reference execution time per benchmark, i.e. the one which corresponds to 1.0 on the y-axis, is execution time of the fastest scheduler.

CONCLUSIONS AND FUTURE WORK
We have presented an Interrupt-Driven Work-Sharing forloop scheduler which is based on work-stealing principles and tries to address major problem of the original work-stealing algorithm: random choice of victims. The first implementation of IDWS works very efficiently, outperforming Intel Cilk Plus, while being from slightly slower to considerably faster than the best (per kernel) OpenMP scheduling strategy. These results indicate that IDWS could become the universal default scheduler for OpenMP for-loops, freeing the programmer from tricky and disruptive management of load balance.
Two main points of focus for further work should be data locality and efficiency of work-sharing. Work on locality issues has been published by several groups ([9, 8, 10, 1]), whereas Adnan and Sato have presented interesting ideas on efficient work-stealing strategies [2], some of which could be applicable to our work-sharing scheduler.