Advanced synchronization techniques for task-based runtime systems

Advanced Synchronization Techniques for Task-based Runtime Systems David Álvarez Barcelona Supercomputing Center Barcelona, Spain [email protected] Kevin Sala Barcelona Supercomputing Center Barcelona, Spain [email protected] Marcos Maroñas Barcelona Supercomputing Center Barcelona, Spain marcos.maronasbrav[email protected] Aleix Roca Barcelona Supercomputing Center Barcelona, Spain [email protected] Vicenç Beltran Barcelona Supercomputing Center Barcelona, Spain [email protected] Abstract Task-based programming models like OmpSs-2 and OpenMP provide a flexible data-flow execution model to exploit dynamic, irregular and nested parallelism. Providing an efficient implementation that scales well with small granularity tasks remains a challenge, and bottlenecks can manifest in several runtime components. In this paper, we analyze the limiting factors in the scalability of a task-based runtime system and propose individual solutions for each of the challenges, including a wait-free dependency system and a novel scalable scheduler design based on delegation. We evaluate how the optimizations impact the overall performance of the runtime, both individually and in combination. We also compare the resulting runtime against state of the art OpenMP implementations, showing equivalent or better performance, especially for fine-grained tasks. CCS Concepts: •Computing methodologies →Parallel programming languages. Keywords: parallel programming models, OmpSs-2, OpenMP, task-based runtimes, data dependencies, lock-free, waitfree 1 Introduction Due to diminishing returns on modern CPUs’ single-thread performance, the industry has shifted towards many-core and heterogeneous architectures [ 3 , 11 , 36 ]. The recent focus on energy efficiency has increased the interest in systems with numerous processing elements with lower frequencies. Those parallel systems can achieve huge performance figures, but their limiting factor is the scalability of the software. PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea ©2021 Association for Computing Machinery. This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’21), February 27-March 3, 2021, Virtual Event, Republic of Korea,https://doi.org/10.1145/3437801.3441601. One of the most widely used standards for programming shared-memory systems in both industry and academy is OpenMP[ 6 ]. OpenMP initially had only a fork-join execution model, where programmers explicitly define parallel regions. The fork-join model is an efficient way to exploit well-structured parallelism, but it is not well suited to exploit irregular, dynamic, or nested parallelism. In recent years, task-based parallelism has been introduced in OpenMP to overcome these limitations. The task-based paradigm can exploit more fine-grained, dynamic, and irregular parallelism than the fork-join model. Additionally, it minimizes the need for global synchronization points, and it naturally copes with load-imbalance. These features make the paradigm especially promising to exploit modern many-core architectures [10, 22]. Moreover, the introduction of task data dependencies was the critical element to truly move forward to a data-flow execution model that relies on fine-grained synchronizations between tasks. This model reduces further the need for global synchronization points and allows the runtime to exploit data-locality between tasks. However, task management inside the runtime might incur some non-negligible overhead, especially for fine-grained tasks on large many-core systems. This paper presents optimized designs for the main components of a task-based runtime system. We also present a lightweight and integrated instrumentation system, which we used to analyze in detail how the scalability of each component affects the global scalability of the runtime. A task-based runtime system has three main components: the dependency system, the task scheduler, and the memory allocator, which tightly interact with each other. The first stage of a task’s life cycle is its creation, which involves the memory allocator. The runtime then checks its data dependencies to determine if the task is ready or blocked based on the previous tasks’ dependencies. Once all its dependencies are satisfied, the task becomes ready and is added to the scheduler, which will eventually schedule it on an available core. Once the task has executed, it releases its dependencies so that its successor tasks may become ready. Note that PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea David Álvarez, Kevin Sala, Marcos Maroñas, Aleix Roca, and Vicenç Beltran Main thread #pragma oss task in(A) #pragma oss task in(A) #pragma oss task in(A) #pragma oss task in(A) A A A A Successor Child Child { { } } Figure 1. The graph of task dependency accesses on an OmpSs-2 program. The program (left) results in the dependency graph (right) between the accesses to location A. the three components require a synchronization mechanism as they have to deal with multiple requests simultaneously. Thus, the application developer has to strike a balance in task granularity: it has to be small enough to provide sufficient work for all available cores while being coarse enough to evade runtime system overheads [ 15 ]. However, as applications scale out to more cores (or nodes) and the problem size remains constant, task granularities naturally decrease. At some point in the scaling process, tasks can become so small that the application is overhead-bound, and the scalability depends on the ability of the parallel runtime to handle small tasks. Our contributions are to (1) present a novel wait-free data structure and algorithm to support complex dependency models in a task-based runtime; (2) provide a scalable task scheduler that works well under high contention and uses delegation instead of work-stealing; and (3) analyze and create a detailed performance profile of the task-based runtime with a lightweight instrumentation framework. 2 Data dependency system The data dependency system is one of the limiting factors in the scalability of task-based runtimes, especially when running programs with very fine-grained tasks. Such programs register large amounts of small tasks with dependencies that take a short time to execute. Thus the overhead in the dependency system can significantly impact the overall application performance. In this paper, we apply our optimizations to the Nanos6 runtime [ 4 ] for the OmpSs-2 programming model. Compared to OpenMP, the model for data dependencies in OmpSs-2 is more complex [ 5 , 13 , 28 ]. The main complexity increase is because the dependency domains of tasks on different nesting levels can share dependencies, which complicates the locking scheme used to implement the model. Reductions also are treated as data dependencies on OmpSs-2 tasks, unlike OpenMP where they are defined at a task group level. 2.1 Dependencies in Nanos6 In Nanos6, a task is a sibling of another when they are at the same nesting level. Tasks declared inside another one (nested) are considered child tasks. The dependencies of a task in Nanos6 are represented as accesses, which are composed of a memory address and an access type, e.g., read or write. Two accesses have a successor relation when they share the same memory address and their tasks have a sibling link. Similarly, two accesses have a child relation if they share the same memory address and their tasks have a child link. Task access relations on OmpSs-2 programs form binary trees between the linked tasks, as shown in Figure 1. Note that on OpenMP users cannot express dependencies crossing nesting levels, and the child relationship is not considered to determine the dependencies between tasks. During an OmpSs-2 program, several tasks can be created and finished concurrently. They have to propagate dependency information through the data structures to determine if the added tasks are ready and if the recently finished tasks allow any successor to become ready. 2.2 Wait-free data dependencies The previous implementation of dependencies inside Nanos6 was based on fine-grained locking, but it was very complex to avoid possible deadlocks. Instead of protecting the data structures that hold the information about the dependencies through mutual exclusion, our alternative is to adapt some wait-free programming concepts to create a data structure capable of supporting the concurrency we need. Otherwise, if we had decided to build a data structure based on mutual exclusion, we would have to compromise either with the complexity of fine-grained locking or the performance degradation of coarse-grained locking. The main goal is not to have wait-freedom as a requirement but to provide fast and scalable dependency registration. In this section, we describe the concept behind the dependency implementation we propose for the Nanos6 runtime. In the following section, we will formalize the approach and prove its wait-freedom property. When a program creates a task, all the dependencies are registered inside the Nanos6 runtime using the DataAccess structure, shown in Listing 1. The Task structure stores all task-related information, including a pointer to the array of its accesses. Each access has an atomic flags field that stores its current state, indicating if the dependency is currently satisfied (not preventing the task execution) and whether the satisfiability information has propagated to its successor and child accesses. The access also stores a pointer to its successor, which is the next access (belonging to a successor task) to the same address in the current nesting level, and a pointer to the child, which points to the first access to the same address that belongs to a child task. Advanced Synchronization Techniques for Task-based Runtime Systems PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea The flags field represents a Finite State Machine in which the state diagram has no cycles, so there are starting and final states. Since we only modify this data structure with atomic operations, we have named it Atomic State Machine or ASM. Note that there is one instance of this state machine for each access. 1struct Task { 2... 3DataAccess * dataAccesses ; 4}; 5 6struct DataAccess { 7void * address ; 8std :: atomic < access_flags_t > flags ; 9Da taA cce ssT ype type ; 10 DataAccess * successor , * child ; 11 }; Listing 1. Relevant fields in the Task and DataAccess structures The only way for an ASM to transition from one state to another is through receiving a data access message. The structure of a message, shown in Listing 2, contains two flags fields. One field contains the flags to set in the target access. The other has flags that have to be set on the message’s originator as a delivery notification. The ASM’s transitions have to be done as a single atomic operation, optimally through a fetch&or. Based on the values before and after the transition, the ASM may generate additional messages to deliver to its child or successor accesses. All the messages that are still pending to deliver are stored in a simple per-thread queue called MailBox. We illustrate this process in Figure 2. 1struct DataAccessMessage { 2access_flags_t flagsForNext , flagsAfterPropagation ; 3DataAccess *from , *to; 4}; Listing 2. DataAccessMessage structure Figure 2 represents the basic structure of the algorithm. While the MailBox has undelivered messages, we pop one from the container and deliver it to the destination access. Upon receiving the message, the access atomically updates its flags field. The atomic update provides us with the flags’ exact values before and after the message was received. As flags cannot be unset, we know each transition happens only once in the access lifetime. With this information, we decide if it is needed to generate more messages (to propagate information about satisfied accesses, for example). Finally, we atomically update the flags field of the originator access of the message to notify the delivery of the information. We use this last atomic update to determine we can safely delete an access. 2.3 Formalization In this section, we introduce several relevant definitions and finally prove wait-freedom. #1 00000101 00001111 #2 Pop Push While MailBox is not empty Message #1 ... Message #2 MailBox Deliver Delivery creates new messages Figure 2. Atomic state machine dependency propagation Definition 2.1. Access Flags. We can define the set of all possible flags an access can have as set 𝐹 . Then, the set 𝐹𝑎 of flags that an access 𝑎 has is defined as 𝐹𝑎⊆𝐹 . When 𝑎 is created, flags are initialized as 𝐹𝑎=∅. Definition 2.2. Delivery. The only operation that can be done on the flags 𝐹𝑎 of an access 𝑎 is the delivery of a message 𝑀⊆𝐹. A delivery operation is defined as: 𝐹𝑎,𝑖+1=𝑀∪𝐹𝑎,𝑖 Assuming the message M follows the two restrictions: 𝑀∩𝐹𝑎,𝑖 =∅ 𝑀≠∅ The restrictions on the content of the messages are part of what provides the wait-freedom assurance. Informally, bits in the flag field can only be set, and the field size is limited. Additionally, each message that an access receives has to contain at least one flag, and none of the flags can be already set in the access. By those properties, we can deduce that each access can receive only a limited number of messages, which in the worst case is |𝐹|. Lemma 2.3. The delivery of a message 𝑀 to an access 𝑎 is non-blocking and wait-free. Proof. To establish wait-freedom, we need to prove that there is a bound on the time a delivery operation can take regardless of any other threads. Assuming that the operation is performed using a CAS primitive, we can assume constant time for the CAS, but it can fail in case of conflict with another thread. Hence, to prove wait-freedom, we need to bound the number of failures due to conflict a delivery operation can suffer. ACAS can fail if and only if another thread modified the memory location during the delivery operation. However, in our system, the only way to change the flags 𝐹𝑎 of an access 𝑎 is to deliver another message. As we established our restriction that a message cannot be empty, the maximum number of messages an access 𝑎 can receive if each message PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea David Álvarez, Kevin Sala, Marcos Maroñas, Aleix Roca, and Vicenç Beltran only contained one flag would be: 𝑀𝑚𝑎𝑥 ={{𝑥} | 𝑥∈𝐹} Then, the maximum number of CAS operations that have to be done until one succeeds, assuming a worst case scenario, is |𝑀𝑚𝑎𝑥 | , which trivially |𝑀𝑚𝑎𝑥 |=|𝐹| .We can establish that the maximum number of tries to deliver a message 𝑀 is 𝑇𝑚≤ |𝐹| . It is possible to get a closer bound on the retries if we consider the number of flags in the message to be delivered, but this is sufficient for us to prove Lemma 2.3. The time needed to deliver a message is clearly bounded to a constant number of CAS operations. □ Definition 2.4. Unregister. For a Task 𝑡 that has a set of accesses 𝐴𝑡 , the unregister operation on a Task is defined as delivering a specific message 𝑀 to each access 𝑎 so that 𝑎∈𝐴𝑡. A task is unregistered once it finishes its execution, and the message delivered to the access indicates this condition. An unregister operation will thus do |𝐴𝑡| delivery operations. As we have proved that a delivery is wait-free, the unregister operation will be wait-free because it does a finite and known number of delivery operations. 3 Task Scheduling System The scheduling system orchestrates the execution of ready tasks on worker threads. Throughout this section, we assume that exactly one worker thread is bound to each CPU for simplicity but without loss of generality. When a task becomes ready, it is forwarded to the scheduling system. Then, when a core becomes idle, it calls the scheduler to ask for more work. If there are ready tasks, the scheduling system will determine the best task that can be executed on this specific core. It is worth noting that multiple ready tasks can be added to the scheduler concurrently and that several worker threads can simultaneously call the scheduler. Thus, it becomes mandatory to add some kind of synchronization on the scheduler to prevent data-races. Most task-based runtime systems rely on multiple ready task queues combined with work-stealing to mitigate the above-mentioned problems. However, on the typical application design pattern in which a single thread creates all tasks, work-stealing behaves similarly to the global lock approach because most threads need to steal work from a single creator queue. In contrast, the approach described in this section adapts the global lock concept to handle both single creator and multiple creator cases efficiently. Usi a global lock is the most straightforward approach to synchronize the scheduler. In this case, the lock is acquired to add ready tasks to the scheduler and to schedule tasks to worker threads. When task granularity is coarse enough, this approach works well and keeps the scheduling system’s design simple and the scheduling policies accurate. However, when task granularity is fine-grained and the system has many cores, the core that is creating new tasks might not be fast enough to feed all other cores. In this scenario, many worker threads will busy-wait on the global lock. This has two adverse effects. Firstly, it increases contention on the cache subsystem due to the additional cache coherence traffic. Secondly, it prevents ready tasks from entering the scheduler fast enough because the task creator has to fight with all of the worker threads to get the global lock. A well-known technique to mitigate lock contention on the scheduler is to let the worker threads spin for a while, and if they do not get any ready task, block its thread using a mutex until a ready task becomes available. We avoid using this approach because it adds extra work to the thread that is creating tasks. When ready tasks are added to the scheduler, it has to check if there are blocked threads and wake them up with an expensive system call. 3.1 Optimizing task insertion To avoid the stagnation of ready tasks in the scheduler, we have decoupled the actions of adding and scheduling ready tasks. When a task becomes ready, we do not directly add it to the scheduler but a bounded wait-free single-consumer single-producer (SPSC) queue working as a buffer. The number of SPSC queues can be configured from a single one to one per core. In the first case, we would need a lock to synchronize all task additions, while in the latter, no locking is needed at all. We use the lock to synchronize between producers, but the synchronization between producer and consumers remains wait-free. In our experiments, we use one SPSC queue and lock per NUMA node. When a worker threads enters the scheduler, it first drains all SPSC queues and inserts the ready tasks into the global ready queue. With this approach, we ensure that any contention generated by many worker threads calling the scheduler does not affect the performance of cores that are creating tasks. We can implement this optimization because the actual addition of tasks can be safely delayed until a core becomes idle and calls the scheduler. Notice that this delegation technique is compatible with any lock implementation. 3.2 Scalable lock designs The scheduler system has to be extensible, and adding new scheduling policies should be easy. We have discarded a wait-free or lock-free scheduler because of its complexity and difficulty to maintain, as each scheduling policy would require a new ad-hoc design and implementation. Our scheduling system relies on a global lock to protect its internal data structures, making it easy to develop new scheduling policies. Ticket Locks [ 31 ] are fair and provide strict FIFO ordering, but they have contention problems under high-load conditions, so they are not suitable for our centralized scheduler. Partitioned Ticket Locks [ 8 ] (PTLocks) Advanced Synchronization Techniques for Task-based Runtime Systems PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea extend Ticket Locks with a padded array used to do busywaiting by idle threads. If the size of this array is equal to the number of CPUs, then each core will busy-wait in a different array slot, reducing the cache coherence traffic to the minimum. We use PTLocks as a building block of our optimized lock design presented in the next section. 1struct PTLock { 2// Can be a constructor parameter 3const static int Size = 64; 4std :: atomic < uint64_t > _head = { Size }; 5uint6 4_t _ tail = { Size + 1}; 6std :: atomic < uint64_t > _waitq [ Size ] = {{ Size }}; 7 8uint64_t _getTicket () { 9return _head . fetch_add (1) ; 10 } 11 void _waitTurn ( uint64_ t ticket ) { 12 while ( _waitq [ ticket % Size ] < ticket ) { spin () ; } 13 } 14 void lock () { 15 _waitTurn ( _getTicket ()); 16 } 17 void unlock () { 18 uint6 4_t idx = _tail % Size ; 19 _waitq [ idx ] = _tail ++; 20 } 21 }; Listing 3. Implementation of a PartitionedTicketLock Listing 3 shows the implementation of a Partitioned Ticket Lock. For the sake of clarity, we have omitted the padding of the fields to prevent false sharing, and the memory order constraints of all atomic operations. The _waitq (line 6) is an array of unsigned 64-bit integers used to implement a circular buffer representing an infinite virtual waiting queue. The _head and _tail fields (lines 4 and 5) are used to index the _waitq array. The _head represents the index of the latest slot in the virtual waiting queue and the _tail is the index of the next slot that will be able to acquire the lock. When the lock is free and no thread is waiting to acquire it, _tail == _head+1. We initialize the lock such that _waitq[_head%Size] == _head, guaranteeing that the first thread that arrives will be able to acquire it. The lock() operation (line 14) consists of just two calls. The first one is _getTicket() (line 8), which performs an atomic fetch and increment of the _head field to obtain the last ticket (line 9). The second call is _waitTurn (line 11) that receives the ticket as a parameter. The current thread busy-waits on the _waitq[ticket % Size] position until it matches (or exceeds) the ticket value. The unlock operation (line 17) calculates the next slot index that will be able to acquire the lock. Then it increments _tail and writes _tail-1 in the computed slot to release the lock. PTLocks perform as well as more complex designs such as MCS [ 25 ] or Ticket Locks Augmented with a Waiting Array (TWA) [9], however it requires more memory space. 3.3 Delegation Ticket Lock (DTLock) Another well-known technique to improve the performance of data structures that are not amenable to fine-grained locking is delegation [ 32 ]. The main idea behind this method is that protected data structures are accessed only by one privileged thread, which executes all the operations on behalf of the other threads. Delegation relies on a lightweight and optimized communication protocol between the privileged thread and the rest of the threads to be able to delegate operations and forward results back. A drawback of this approach is that it requires a dedicated core for each independent set of data structures that has to be protected, making it unpractical in many situations. There are variants of the delegation technique that use queues to delegate work to the threads currently inside the lock [ 21 ]. These are better suited to use in centralized schedulers as they do not require dedicated cores for each lock. In order to build our scalable centralized scheduler, we have developed a novel Delegation Ticket Lock (DTLock) that builds on state of the art delegation techniques and extends our implementation of the PTLock with support for finegrained and dynamic delegation of operations. The DTLock supports the standard lock,unlock and trylock operations, as well as lockOrDelegate,empty,front,popFront and setItem. The lockOrDelegate operation either acquires the lock if it is free or delegates the operation to the current lock’s owner. However, it is the current owner that will decide if it executes or not the delegated operations. Suppose the current owner releases the lock without performing a pending delegated operation. In that case, the thread that originally delegated that operation will eventually acquire the lock and execute it by itself. The empty,front,popFront and setItem operations can only be called by the thread that owns the lock and are used to manage the threads that are waiting outside the lock. The main advantages of the DTLock are that it does not require a dedicated core and its additional operations can be freely combined with traditional lock,unlock and trylock operations. Additionally, the DTLock allows for threads to remain inside the critical section of the lock executing delegated operations. This can be leveraged to minimize operation latency when there is not enough work to keep all cores busy. Listing 4 shows the implementation of a DTLock in C++, which inherits the PTLock’s _head,_tail and _waitq[] members, as well as, lock,unlock and tryLock operations. The DTLock extends the PTLock with two additional arrays. The _logq array (line 3) is used to register waiting threads while the _readyq array (line 4) is used to store the result of delegated operations, i.e. ready tasks in our case. The first parameter of the lockOrDelegate operation is a unique id that identifies the thread that is calling this function. This id should be in the range 0..Size-1 as it is used to index the _readyq array. Thus, we need to know in advance PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea David Álvarez, Kevin Sala, Marcos Maroñas, Aleix Roca, and Vicenç Beltran 1template <typename T> 2struct DTLock : public PTLock { 3std :: atomic < uint64_t > _logq [ Size ] = {}; 4struct { uint 64_t ti cket ; T item ; } _re adyq [ Size ]; 5 6bool lock OrDelegate ( uint64_t const id , T & item ) { 7uint64_t const ticket = _getTicket (); 8_logq [ ticket % Size ] = ticket + id ; 9_waitTurn ( ticket ) ; 10 if ( _ready q [id ]. ticket != ticket ) { 11 _tail ++; 12 return true ; 13 } 14 item = _readyq [ id ]. item ; 15 return false ; 16 } 17 bool empty () const { 18 return _logq [ _tail % Size ] < _tail ; 19 } 20 uint64_t front () { 21 return _logq [ _tail % Size ] - _tail ; 22 } 23 void popFront() { 24 unlock () ; 25 } 26 void setItem ( uint64_t const id , T item ) { 27 _re ad yq [ id ]. item = item ; 28 _re adyq [ id ]. t icket = _tail ; 29 } 30 }; Listing 4. Implementation of a Delegation Ticket Lock the maximum number of threads that can call the DTLock. If the lockOrDelegate operation is finally delegated, the second parameter is used to store the result. The first thing done in lockOrDelegate is to obtain a ticket (line 7). Then, the thread is registered on the _logq (line 8) array with just one store operation that combines the ticket and calling thread’s id. The values written on the _logq array cannot be overrun because it is guaranteed that there will be at most Size threads calling the lockOrDelegate operation, so that each thread will have their own position. Once the thread has been registered, it just busy-waits (line 9) until it acquires the lock (lines 11-12), or the operation has been delegated and the result is stored in the &item parameter (line 14). The empty operation (line 17) returns true if there is no thread registered in the _logq array and false otherwise. We check the first position of the _logq array, and if the value is smaller than _tail, we know there is no thread waiting yet. Otherwise we would see the value written in line 8. Notice that this operation is intrinsically racy but harmless. If a call to empty returns false, then the owner of the lock can call front (line 20) to obtain the id of the thread that is waiting. To that end, we only need to do the inverse of the operation done on line 8, subtracting the _tail’s value to obtain the thread id (line 21). Then, the setItem operation assigns a result Tto a registered thread using its id to index the _readyq array. First, it sets the item field (line 27) and then the ticket to the _tail value, marking the entry as valid. We use the ticket field in line 10 to determine if an operation was delegated or not. Finally, the popFront operation wakes up the first thread busy-waiting on the _waitq by executing the unlock operation. 3.4 Synchronized Scheduler This section presents a synchronized scheduler that leverages the SPSC queues and the DTLock described in sections 3.1 and 3.3, respectively. 1struct SyncScheduler { 2DTLock < Task *> _loc k ; 3Un sy nc Sch ed ul er _sched ; 4PTLock _addQueueLock; 5boost :: lockfree :: spsc_queue < Task *> _addQueue = {100}; 6 7void processReadyTasks () { 8_addQueue . consume_all ( 9[&]( Task *t) { _sched . addReadyTask (t) ; }) ; 10 } 11 void ad dR ead yT ask ( Task * task ) { 12 while (1) { 13 _a dd Que ueL oc k . lock () ; 14 bool added = _ad dQ ue ue . push ( task ); 15 _add Qu eu eL ock . unlock () ; 16 if ( added ) break; 17 if ( _lock . t ryLock () ) { 18 processReadyTasks () ; 19 _lock . unlock () ; 20 } 21 } 22 } 23 Task * getReadyTask ( uint64_t const id ) { 24 Task *task; 25 if (! _lock . lockOrDelegate (id , task )) 26 return task; 27 processReadyTasks () ; 28 while (! _lock . empty ()) { 29 uint6 4_t w ai tingId = _lock . front () ; 30 task = _sched . getReadyTask ( waitingId ); 31 if ( task == nullptr ) break; 32 _lock . se tItem ( waitingId , task ) ; 33 _lock . popFron t () ; 34 } 35 task = _sched . getReadyTask ( id ); 36 _lock . unlock () ; 37 return task; 38 } 39 }; Listing 5. Implementation of the Synchronized Scheduler using a Delegation Ticket Lock Listing 5 shows the implementation of a synchronized scheduler using a DTLock (line 2) and a SPSC wait-free queue (line 5) to synchronize the getReadyTask and addReadyTask operations, respectively. The SyncScheduler is a wrapper of the unsynchronized scheduler (line 3), which implements the actual scheduling policy. The PTLock (line 4) protects the producer side of the SPSC queue in the addReadyTask function (line 14), while the DTLock protects the consumer side in the processReadyTasks function. In the addReadyTask function, if there is no free space on the SPSC queue, the thread will try to acquire the Advanced Synchronization Techniques for Task-based Runtime Systems PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea Figure 3. Timeline of five threads using a DelegationLock to add and get ready task into the scheduler. DTLock with a tryLock operation (line 17). If it succeeds, it will call the processReadyTasks function (line 18), which removes all tasks from the SPSC queue and inserts them to the unsynchronized scheduler (line 8). We use the lockOrDelegate operation (line 25) of the DTLock to synchronize getReadyTask operations. If the operation is delegated because another thread owns the DTLock, the calling thread will busy-wait until it gets a task (lines 2526). Otherwise, it will eventually acquire the lock and call the processReadyTasks (line 27) to add the tasks that are waiting on the SPSC queue into the unsynchronized scheduler. Then, it will try to schedule a task for each of the threads that are waiting on the DTLock (lines 28-33) until there are no more waiting threads (line 28) or no ready tasks are left (line 31). At that point, it will try to get a task for him (line 35) and then release the DTLock (line 36). In our simplified design, the thread inside the scheduler leaves as soon as there are no more tasks to schedule. However, it is easy to extend our design in a way that processReadyTasks is called when no tasks are left inside the scheduler. Figure 3 shows a timeline of five threads creating and scheduling tasks using the SyncScheduler and a simple FIFO scheduling policy. 𝑇ℎ0 has already created and inserted three tasks ( 𝑇0 - 𝑇3 ) that are inside the SPSC queue before creating and inserting four additional tasks ( 𝑇4 - 𝑇7 ). 𝑇ℎ1 to 𝑇ℎ4 call the getReadyTask function, one after the other, to obtain a ready task. The call to lockOrDelegate of 𝑇ℎ1 acquires the lock, while the other threads delegate and busy-wait. Once 𝑇ℎ1 is inside the lock, it calls processReadyTasks and inserts tasks 𝑇0 to 𝑇3 into the actual scheduler. Then, 𝑇ℎ1 schedules one ready task for each of the waiting threads, and finally, it gets a ready task for itself. When 𝑇ℎ3 finishes the execution of 𝑇1 , it calls again to getReadyTask, and just after that, 𝑇ℎ2 does the same. 𝑇ℎ3 acquires the lock and calls processReadyTasks, moving the tasks from the SPSC queue ( 𝑇4 and 𝑇5 ) to the actual scheduler. Finally, 𝑇ℎ3 schedules 𝑇4 for 𝑇ℎ2 , and then, it executes 𝑇5. In microbenchmarks, we found a fourfold speedup on task scheduling using a DTLock compared to a PTLock, and a twelvefold speedup compared to serial task insertion thanks to the SPSC queues. 4 Memory management When optimizing a runtime to achieve the lowest overhead, every operation that requires synchronization between threads quickly becomes a bottleneck. This is the case for memory allocation. Some general-purpose allocators are not well suited to handle a high volume of memory requests in manycore systems. Many implementations require the serialization of every allocation in the system. Additionally, the operating system may introduce even more overhead when allocators request more memory areas through system calls. In the Nanos6 runtime case, removing contention from the scheduler and dependencies caused an even more significant bottleneck on memory allocation. However, the current state of the art techniques for scalable memory allocation can be applied to any software [ 2 , 12 ], solving most of the contention problems. To solve this bottleneck and achieve the performance presented in this article, we had to substitute the default allocator in Nanos6 for Jemalloc, a widely used scalable memory allocator. 5 Instrumentation Analyzing runtime performance and finding problems or bottlenecks in the different component requires a mechanism to collect fine-grained instrumentation data. This instrumentation must have a very low overhead, which is difficult to achieve on a very optimized runtime. Additionally, runtime systems are sensitive to OS noise (such as thread preemptions), making exploiting kernel internals particularly useful when evaluating latency-critical features, such as those presented in this article. For this reason, we have developed a new tracing backend aiming at minimum overhead and with both runtime and kernel tracing capabilities. The backend generates traces in the Common Trace Format (CTF) [ 7 ], which strives for fast data writes. Instrumentation overhead is minimized by storing events on lock-free NUMA-aware per-core circular buffers. Each buffer is divided into page-aligned sub-buffers that, when full, are periodically flushed to a tmpfs backed file by Nanos6 threads between tasks execution. Each file contains a time-ordered event subset of the final trace, with either kernel or user events. Nanos6 threads write events on the lock-free per-core buffer they are pinned to. User-selected Kernel events are obtained from a per-core memory-mapped circular buffer exported by the Linux Kernel through the perf_event_open() system call. Between task executions, Nanos6 threads read and format the kernel events according to the CTF specification and move them to an exclusive kernel-events Nanos6 per-core circular buffer. PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea David Álvarez, Kevin Sala, Marcos Maroñas, Aleix Roca, and Vicenç Beltran 6 Evaluation In this section, we evaluate the effects of the different optimizations that we present in this paper. To evaluate their impact, we have prepared different versions of the Nanos6 runtime system, where each one removes one of the three optimizations. This methodology allows for a better understanding of which optimizations have the most significant impact on runtime performance. To prove that these optimizations make Nanos6 one of the lowest-overhead task runtimes, we also compare our most optimized version with the most relevant OpenMP implementations. We conduct our experiments on three HPC machines. 6.1 Methodology To evaluate the task-based runtimes and check the capability of scaling to more finely partitioned work, we will use the following benchmarks, running constant problem sizes and varying the task granularity. These are (1) a Dot product between two arrays that uses a task reduction to aggregate the results from each block, (2) an iterative Gauss-Seidel method solving the heat equation of a 2-D matrix in blocks and task reductions to calculate the residual of each time step, (3) a taskified HPCCG with with several kernels using task reductions and multi-dependencies, (4) a taskified version of Lulesh 2.0 [ 20 ], (5) a taskified miniAMR that mimics the different patterns of Adaptive Mesh Refinement applications [ 33 , 34 ], (6) a classic parallel blocked Matmul , (7) an NBody benchmark that mimics dynamic particle system simulations, and (8) a blocked Cholesky decomposition that is generally compute bound. We ran our experiments on various HPC platforms featuring very different architectures: (1) the Intel Xeon with 2x Intel Xeon Platinum 8160 (Sky-lake) for a total of 48 cores, (2) the ARM Graviton2 with 64 ARM Neoverse N1 cores, and (3) the AMD Rome with 2x AMD EPYC 7H12 processors for a total of 128 cores and 256 hardware threads. For all benchmarks, the parallelization is implemented using tasks with OpenMP and OmpSs-2 versions that feature the same amount of parallelism. However, the kernels used inside each task are sourced from the best available vendor library for each machine, to guarantee competitive performance. In the AMD and Intel machines this library was Intel MKL, and on the ARM Graviton2 we used the ARM Performance Libraries. We ran each benchmark a minimum of five times to extract each measurement. Following this evaluation, we will compare our optimized Nanos6 runtime with the most relevant OpenMP implementations for each machine, including GOMP 9.2.0 [ 17 ], LLVM 10 [ 23 ], Intel OpenMP and the AMD AOCC depending on availability for each platform. It is worth noting that both the LLVM, AMD AOCC and Intel OpenMP runtime are based optim ized w/o jem alloc w/o wait-free dependencies w/o DTLock Efficiency 226 227 228 229 230 0 25 50 75 100 Lulesh 213 215 217 219 221 223 0 25 50 75 100 Dot Product Task 219 220 221 222 0 25 50 75 100 miniAMR 217 219 221 223 225 0 25 50 75 100 Cholesky granularity Figure 4. Efficiency vs task granularity of the Nanos6 runtime with and without the described optimizations on Intel Xeon (higher is better) on a work-stealing scheduler, which will allow us to determine if our centralized delegation-based implementation can outperform work-stealing runtimes. Note that some combinations might not be available depending on the platform because of incompatibilities, nonimplemented OpenMP features or compiler bugs. For brevity, we only show the four most relevant benchmarks for each machine. 6.2 Results The best way we found to evaluate objectively how each component of the runtime affects the overall performance is to remove the optimizations we have described selectively. To present the results, we use a metric [ 35 ] we will refer to as efficiency. It is calculated by dividing the performance of a specific run of a benchmark by the peak performance obtained across all executions. This efficiency provides a view of how close to peak performance is a specific run while being agnostic to benchmark specific units. Combining this metric with varying task granularity [ 15 , 24 ] gives a good view of each runtime version’s scalability. The granularity is expressed in instructions executed per task, which gives an approximation of the task’s size. We chose this unit instead of using time or cycles because the scheduling policies used by each of the runtimes can affect the execution time of a task, and thus it could result in unfair comparisons. The runtime version without the wait-free dependencies uses the previous dependency implementation based on finegrained locking. The variant without the DTLock has a simple mutual exclusion mechanism (based on the PTLock) protecting the scheduler. Finally, the version without jemalloc uses the standard system allocator for each of the machines. Figure 4 displays our benchmarks running in the Intel Xeon platform. The different versions allow us to explore precisely how each optimization affects the scalability for Advanced Synchronization Techniques for Task-based Runtime Systems PPoPP ’21, February 27-March 3, 2021, Virtual Event, Republic of Korea optim ized w/o jem alloc w/o wait-free dependencies w/o DTLock Efficiency 218 220 222 224 226 0 25 50 75 100 NBody 216 218 220 222 0 25 50 75 100 HPCCG Task 219 220 221 222 0 25 50 75 100 miniAMR 217 220 223 226 229 0 25 50 75 100 Matmul granularity Figure 5. Efficiency vs task granularity of the Nanos6 runtime with and without the described optimizations on AMD Rome (higher is better) optim ized w/o jem alloc w/o wait-free dependencies w/o DTLock Efficiency 217 219 221 223 0 25 50 75 100 Heat 216 218 220 222 0 25 50 75 100 HPCCG Task 219 220 221 222 0 25 50 75 100 miniAMR 217 220 223 226 229 0 25 50 75 100 Matmul granularity Figure 6. Efficiency vs task granularity of the Nanos6 runtime with and without the described optimizations on ARM Graviton2 (higher is better) different benchmarks. The results also confirm that for every benchmark at least one optimization greatly increases the performance for fine-grained tasks. Figure 5 shows a similar picture on the AMD Rome system. This system has a much larger number of CPUs, which can increase the performance degradation caused by heavily contended locks. Illustrating this point, we see that the scheduler optimization is much more relevant than in the Intel Xeon. The clearest example is seen on the miniAMR benchmark, which we analyze with detailed traces in subsection 6.4. Finally, Figure 6 shows the same benchmarks running on an ARM Graviton2 system. Results are similar to our Intel Xeon evaluation, although some benchmarks have different behaviors due to the lack of NUMA effects on this platform. Overall, we have seen that our optimizations achieve significant performance gains, especially on small task granularities. Depending on the benchmark, the wait-free dependencies or the scheduler are the most important optimizations. Nanos6 GCC Intel LLVM Efficiency 217 219 221 223 0 25 50 75 100 Heat 213 215 217 219 221 223 0 25 50 75 100 Dot Product Task 219 220 221 222 0 25 50 75 100 miniAMR 217 219 221 223 225 0 25 50 75 100 Cholesky granularity Figure 7. Comparison of performance between the current Nanos6 version and the main OpenMP runtimes on Intel Xeon (higher is better) However, the scalable memory allocator also delivers some notable performance improvements, especially on the Intel Xeon and AMD Rome machines. 6.3 Comparison versus OpenMP To give context to the results, we compare the optimized Nanos6 runtime to current state-of-the-art OpenMP runtimes on the same three systems. Our baseline for every benchmark will be the GOMP runtime, distributed with the GCC Compiler, and the LLVM OpenMP Runtime. However, on Intel Xeon we use the Intel OpenMP runtime, and on AMD Rome the runtime provided by the AMD AOCC, as long as they implement all the features needed by the benchmark. To ensure a fair comparison, we expressed the same parallelism in the OmpSs-2 and OpenMP versions of the benchmarks. We also used available kernels in Intel MKL or the ARM Performace Libraries, to prevent noise introduced by the compilers to alter the results. Figures 7, 8 and 9 feature the results of comparing the current OpenMP implementation versus the optimized variant of the Nanos6 runtime. The results are really positive, as in all of the machines, and all of the benchmarks, the best performance in small granularity tasks is provided by the Nanos6 runtime. In some cases, a higher peak performance is also achieved. This happens when the ideal block size for a specific benchmark is small enough that performs better in one runtime than another. As for the other runtimes, the LLVM OpenMP implementation comes second in most benchmarks in terms of scalability, and ties on AMD Rome with the runtime provided with the AOCC compiler. However, this is expected because the AOCC compiler is based on LLVM 10.