Lightweight Preemptive User-Level Threads@ PPoPP '21
Shumpei Shiina (The University of Tokyo), Shintaro Iwasaki (Argonne National Laboratory),Kenjiro Taura (The University of Tokyo), Pavan Balaji (Argonne National Laboratory)

More Threads than the Number of Cores
Nested Parallelism
ThreadExternal LibraryCore

Asynchronous Tasks

Threads are createddynamicallyThread schedulers should be able to handle many, fine-grained threads- Complicated software stacks where many parallel libraries are hierarchically composed- Coexisting various kinds of tasks (e.g., in situ analysis with simulation tasks and analysis tasks)--> Lightweight threads are needed1Customizable Thread Schedulers for High Performance
It is often beneficial to customize thread schedulers for specific workloads
The below example: work stealing scheduler for threads with priorities (e.g., for in situ analysis)
4. steal

Thread Queue

Low-Priority Threads
3. pop2. steal

High-Priority Threads
1. pop
CoreCoreCoreCore
2

How about M:N Threads (User-Level Threads)?
1:1 Threads

M:N Threads(Kernel-Level Threads; KLTs)(User-Level Threads; ULTs)

N threads

M threads

N KLTsN KLTsHeavyweight threading operations
e.g., thread creation, context switching

Lightweight threading operations
without the involvement of the kernel

Inflexible scheduling policies
controlled by the kernel

Flexible scheduling policies
which can be defined in user space
Many M:N thread-based parallel runtimes have been developed:
Language: Chapel, X10, Charm++, OmpSs, etc.
Library: Argobots, Qthreads, Massivethreads, etc.

3Lack of Preemption
in M:N Threads
Loss of Prioritization

High priority M:N threads remain idle for a long timeReady Threads

CoreA low-priority M:N thread is occupying the core for along time without voluntarily yielding the core

Deadlock
Many existing multithreaded programs assume thatthey can exclusively use all cores--> sometimes they have busy-loop-based barriers

M:N Thread

External
multithreaded
program
Nested Parallelism

Core

Ready Threads

CoreCore

Wait for other M:N threads for synchronization in a busy loop--> deadlock
4

Contributions of This Paper
Investigate preemption techniques for user-level M:N threads
They should be implemented as a pure library (that can be used from C/C++)
Two techniques:
Signal-Yield: an existing technique
KLT-Switching: our new proposal

Provide optimizations for preemptive M:N threads based on detailed analysis
Scalable periodic timer interruption for preemption
Efficient implementation of KLT-switching
Evaluate preemptive user-level threads implemented on Argobots [1]Preemptive M:N threads can be as fast as nonpreemptive M:N threads in practice[1] S. Seo, et al., "Argobots: A lightweight low-level threading and tasking framework," IEEE Transactions onParallel and Distributed Systems, vol. 29, no. 3, pp. 512-526, 2017.

5

Outline
1:1 Threads and M:N Threads
Design of Preemptive M:N Threads
Signal-Yield
KLT-Switching

Optimizations for Preemptive M:N Threads
Evaluation
Overhead of Preemption
Deadlock Prevention in Cholesky Decomposition
In Situ Analysis with LAMMPS
Conclusion

Outline
1:1 Threads and M:N Threads
Design of Preemptive M:N Threads
Signal-Yield
KLT-Switching

Optimizations for Preemptive M:N Threads
Evaluation
Overhead of Preemption
Deadlock Prevention in Cholesky Decomposition
In Situ Analysis with LAMMPS
Conclusion

1:1 Threads

M:N Threads
N threads

M threads

N KLTsN KLTs• Threads visible to the user are directly
mapped to kernel-level threads (KLTs)• Most implementations of Pthreads andOpenMP threads• Many user-visible threads are created
and dynamically mapped to KLTs
• As many KLTs as the number of cores
are usually created• Often called "user-level threads (ULTs)"6

1:1 Threads

M:N Threads
N threads

M threads

N KLTsN KLTsThe kernel can interrupt KLTs and scheduleothers on cores at any time (preemption)

KLTs can be preempted by the kernel,
but how to preempt M:N threads?

7Outline
1:1 Threads and M:N Threads
Design of Preemptive M:N Threads
Signal-Yield
KLT-Switching

Optimizations for Preemptive M:N Threads
Evaluation
Overhead of Preemption
Deadlock Prevention in Cholesky Decomposition
In Situ Analysis with LAMMPS
Conclusion

Signal-Yield[1] A. Anantaraman et al., "EDF-DVS scheduling on the IBM embedded PowerPC 405LP," Proceedings of the IBM
P= ac2 Conference, 2004.
[2] M. S. Mollison and J. H. Anderson, "Bringing theory into practice: A userspace library for multicore real-timescheduling," 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013.
[3] S. Boucher et al., "Lightweight preemptible functions," 2020 USENIX Annual Technical Conference, 2020.
[4] Go 1.14 release notes. Available: https://golang.org/doc/go1.14

Idea: Interrupt execution of threads by a signal and yield in a signal handler
This technique has already been proposed in [1, 2, 3] and integrated to Go from v1.14 [4]KLT1

Thread1
executiont8

Signal-Yield[1] A. Anantaraman et al., "EDF-DVS scheduling on the IBM embedded PowerPC 405LP," Proceedings of the IBM
P= ac2 Conference, 2004.
[2] M. S. Mollison and J. H. Anderson, "Bringing theory into practice: A userspace library for multicore real-timescheduling," 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013.
[3] S. Boucher et al., "Lightweight preemptible functions," 2020 USENIX Annual Technical Conference, 2020.
[4] Go 1.14 release notes. Available: https://golang.org/doc/go1.14

Idea: Interrupt execution of threads by a signal and yield in a signal handler
This technique has already been proposed in [1, 2, 3] and integrated to Go from v1.14 [4]KLT1

Thread1
Interruption

signal handler

executiont8

Signal-Yield[1] A. Anantaraman et al., "EDF-DVS scheduling on the IBM embedded PowerPC 405LP," Proceedings of the IBM
P= ac2 Conference, 2004.
[2] M. S. Mollison and J. H. Anderson, "Bringing theory into practice: A userspace library for multicore real-timescheduling," 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013.
[3] S. Boucher et al., "Lightweight preemptible functions," 2020 USENIX Annual Technical Conference, 2020.
[4] Go 1.14 release notes. Available: https://golang.org/doc/go1.14

Idea: Interrupt execution of threads by a signal and yield in a signal handler
This technique has already been proposed in [1, 2, 3] and integrated to Go from v1.14 [4]KLT1scheduler

Yield
Thread1
Interruption

signal handler

executiont8

Signal-Yield[1] A. Anantaraman et al., "EDF-DVS scheduling on the IBM embedded PowerPC 405LP," Proceedings of the IBM
P= ac2 Conference, 2004.
[2] M. S. Mollison and J. H. Anderson, "Bringing theory into practice: A userspace library for multicore real-timescheduling," 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013.
[3] S. Boucher et al., "Lightweight preemptible functions," 2020 USENIX Annual Technical Conference, 2020.
[4] Go 1.14 release notes. Available: https://golang.org/doc/go1.14

Idea: Interrupt execution of threads by a signal and yield in a signal handler
This technique has already been proposed in [1, 2, 3] and integrated to Go from v1.14 [4]KLT1

Thread2

Possibly scheduleother threads

Thread3

scheduler

Yield
Thread1
Interruption

signal handler

executiont8Signal-Yield[1] A. Anantaraman et al., "EDF-DVS scheduling on the IBM embedded PowerPC 405LP," Proceedings of the IBM
P= ac2 Conference, 2004.
[2] M. S. Mollison and J. H. Anderson, "Bringing theory into practice: A userspace library for multicore real-timescheduling," 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013.
[3] S. Boucher et al., "Lightweight preemptible functions," 2020 USENIX Annual Technical Conference, 2020.
[4] Go 1.14 release notes. Available: https://golang.org/doc/go1.14

Idea: Interrupt execution of threads by a signal and yield in a signal handler
This technique has already been proposed in [1, 2, 3] and integrated to Go from v1.14 [4]KLT1

Thread2

Possibly scheduleother threads

Thread3

scheduler

Yield
Thread1
Interruption

RescheduleThread1

signal handler

executiont8

Signal-Yield[1] A. Anantaraman et al., "EDF-DVS scheduling on the IBM embedded PowerPC 405LP," Proceedings of the IBM
P= ac2 Conference, 2004.
[2] M. S. Mollison and J. H. Anderson, "Bringing theory into practice: A userspace library for multicore real-timescheduling," 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013.
[3] S. Boucher et al., "Lightweight preemptible functions," 2020 USENIX Annual Technical Conference, 2020.
[4] Go 1.14 release notes. Available: https://golang.org/doc/go1.14

Idea: Interrupt execution of threads by a signal and yield in a signal handler
This technique has already been proposed in [1, 2, 3] and integrated to Go from v1.14 [4]KLT1

Thread2

Possibly scheduleother threads

Thread3

scheduler

Yield
Thread1
Interruption

signal handler

RescheduleThread1
Exit handler

executiont8

KLT-Dependence Issue in Signal-Yield
Some existing functions can access KLT-local data, not M:N thread-local datae.g., Glibc malloc() uses KLT-local data for KLT-local caching of memory blocks

KLT1

Thread1
Interruption

signal handler

malloct9

KLT-Dependence Issue in Signal-Yield
Some existing functions can access KLT-local data, not M:N thread-local datae.g., Glibc malloc() uses KLT-local data for KLT-local caching of memory blocks

KLT1
Thread2some function

Context SwitchingThread1
Interruption

signal handler

malloct9KLT-Dependence Issue in Signal-Yield
Some existing functions can access KLT-local data, not M:N thread-local datae.g., Glibc malloc() uses KLT-local data for KLT-local caching of memory blocks

KLT1
Thread2

Callmallocmalloc() is concurrently called in the same KLT--> race condition for KLT-local data(undefined behaviour)some function
KLT-local data

Context SwitchingThread1
Interruption

signal handler

malloct9

How to Support Safe Preemption?
KLT-Dependence Issue:
KLT-local data are assumed to be accessed sequentially, but signal-yield breaks thisassumption
Multiple thread contexts can run on the same KLT
By using signal-yield, threads can be interrupted while accessing KLT-local data
Some existing library functions are not M:N thread-awareand access KLT-local data directly(e.g., Glibc malloc uses KLT-local caching for memory blocks)

Solution:
Switch to another KLT when preemption happens so that KLT-local data are notmodified while being preempted
We call it KLT-switching(our new proposal)
10

KLT-Switching
Idea (our proposal): switching to another KLT only when preemption happens-> KLT-local data are not modified while being preempted

Suspended

KLT2

sleep

KLT1

Thread1
Interruption

signal handler
executiont 11

KLT-Switching
Idea (our proposal): switching to another KLT only when preemption happens-> KLT-local data are not modified while being preempted

KLT2

sleep

scheduler

Yield
KLT1

Thread1
Interruption

Suspend KLT

Suspendedsignal handler
executiont 11

KLT-Switching
Idea (our proposal): switching to another KLT only when preemption happens-> KLT-local data are not modified while being preemptedKLT2

Possibly scheduleother threads
sleepThread2

Thread3

scheduler

Yield
KLT1

Thread1
Interruption

Suspend KLT

Suspendedsignal handler
executiont 11

KLT-Switching
Idea (our proposal): switching to another KLT only when preemption happens-> KLT-local data are not modified while being preempted

KLT2

Possibly scheduleother threads
sleepThread2

Thread3

scheduler

Yield
KLT1

Thread1
Interruption

Suspend KLT

Suspendeddata of KLT1 is not modified
signalKLT-localhandler
while Thread1 is being suspended

executiont 11

KLT-Switching
Idea (our proposal): switching to another KLT only when preemption happens-> KLT-local data are not modified while being preemptedKLT2

Suspended
Possibly scheduleother threads
sleepThread2

Thread3

scheduler

Yield
KLT1

Thread1
Interruption

sleep

Reschedule Thread1
Suspend KLT

signal handler
Exit handler
executiont 11

Thread Mapping in Preemptive M:N Threads
Worker: virtualization of physical cores
M threads

M threads

N workers

N workers

N KLTsP KLTsNonpreemptive/signal-yield

KLT-switching
In KLT-switching,- There is no static mapping between workers and KLTs
- Only "N" KLTs are active at the same time--> Thread scheduling is customizable by the user12Outline
1:1 Threads and M:N Threads
Design of Preemptive M:N Threads
Signal-Yield
KLT-Switching

Optimizations for Preemptive M:N Threads
Evaluation
Overhead of Preemption
Deadlock Prevention in Cholesky Decomposition
In Situ Analysis with LAMMPS
Conclusion

Optimizations for Preemption Timer
Preemption Timer: periodic timer interruption for each worker (using timer_create() syscall)
Preemption intervalInterruption

Optimization of aligning timings of interruption

Core1Core2Core3Core4tt

Observation: When signals are delivered at the sametime across different cores, large amounts of time areconsumed because of lock contention in the kernel

Better Performance13

Optimizations for KLT-Switching
Use futex in Linux for suspending and resuming KLTs
The POSIX-compliant implementation use sigsuspend() and pthread_kill()
They can be called from signal handlers (async-signal-safe)
Heavyweight because of additional signal handling

Worker-local pools for suspended KLTs
Each worker has its own KLT pool for caching
Avoid resetting CPU affinity of KLTs
When a KLT is mapped to a worker, the CPU affinity of the KLT should be set to the worker's CPU14

Summary of Thread Implementations(*) Whether or not the KLT-dependence issue happens

Explicit Threading
Operations

Overhead ofPreemption

Scheduling
Policies

Safety ofPreemption (*)

1:1 Threads

Heavyweight

Low (2.8 us)

Not customizable

Safe

Nonpreemptive M:N Threads

Lightweight-

Customizable-

Preemptive M:N Threads(Signal-Yield)

Lightweight

Medium (3.5 us)

Customizable

UnsafePreemptive M:N Threads(KLT-Switching)LightweightHigh (9.9 us)

Customizable

Safe

High overhead of preemption is acceptable because
preemption is infrequent enough in practice(evaluated later)
15

Outline
1:1 Threads and M:N Threads
Design of Preemptive M:N Threads
Signal-Yield
KLT-Switching

Optimizations for Preemptive M:N Threads
Evaluation
Overhead of Preemption
Deadlock Prevention in Cholesky Decomposition
In Situ Analysis with LAMMPS
Conclusion

Evaluation
CPU: Intel Xeon Platinum 8180M (Skylake)# of sockets: 2# of cores: 56 (28 x 2)
Preemptive M:N threads are implemented on Argobots, an M:N threading library

Evaluation:
1. Overhead of Preemption (using a microbenchmark)2. Deadlock Prevention in Cholesky Decomposition
Preemptive M:N threads resolve a deadlock and outperforms 1:1 threads
3. In Situ Analysis with LAMMPS
Evaluation of the benefit of user-defined schedulers with preemption
16

Overhead of Preemption
Using a compute-intensive program
Baseline: nonpreemptive M:N threads

Optimizations forKLT-switching

KLT-switching costs higher than signal-yield
The overhead of KLT-switching is only ~ 1%with the timer interval of 1 ms
OS preemption interval is typically in the millisecond range

Note: Explicit threading operations (e.g.,context switching and thread creation) areas lightweight as nonpreemptive threads
17Cholesky Decomposition

Deadlockwithout
preemption

A closed-source library withbusy-loop-based barriers
Thread Thread

ThreadThread Thread

ThreadInner Parallelism
Intel MKLIntel MKL(OpenMP threads created within MKL)

Call BLAS subroutines(e.g., cblas_dgemm)
Thread Thread Thread Thread

ThreadOuter Parallelism

Cholesky Decomposition(OpenMP tasks with data dependencies)18Evaluation of Cholesky Decomposition
Nonpreemptive M:N threads with a hackfor replacing busy-loop-based barriers(BOLT: an OpenMP wrapper over Argobots)

Preemptive M:N threads(KLT-switching) without a hackIntel OpenMP based on
1:1 threads
Intel OpenMP with innerparallelism disabled

Higher is better
Larger Problem Size

19

Evaluation of Cholesky Decomposition
Outer parallelism is not enough-> Nested parallelism is beneficial

Preemption adds some overheads tononpreemptive M:N threads, but
performs better than 1:1 threads

Heavyweight threading operationsof 1:1 threads with nested parallelism

Higher is better
Larger Problem Size19

In Situ Analysis with LAMMPSLAMMPS: a widely-used molecular dynamics simulator
In situ analysis: a modern way to perform analysis and simulation at the same time
Lower priority

Higher priority

Analysis threads are created based on the progress of simulation threads
Thus, analysis threads should be evicted from cores in favor of simulation threads
Preemptive scheduling is effective for thread prioritization20

Evaluation of In Situ Analysis with LAMMPSLine Plot: relative overhead compared with the baseline
Baseline: simulation only (without analysis)

Priority of Pthreads is set
via "nice" values

1:1 Threads (Pthreads) add large overheads because ofheavyweight threading operations

Preemptive M:N threads perform better, thanks to...
Lightweight threading operations
Efficient prioritization of threads enabled by preemption
Lower is better
Preemptive M:N threads
21

Outline
1:1 Threads and M:N Threads
Design of Preemptive M:N Threads
Signal-Yield
KLT-Switching

Optimizations for Preemptive M:N Threads
Evaluation
Overhead of Preemption
Deadlock Prevention in Cholesky Decomposition
In Situ Analysis with LAMMPS
Conclusion

Artifact: https://doi.org/10.5281/zenodo.4420552

Conclusion
Investigated two techniques for preemptive M:N threads:
Signal-yield: lower cost, but unsafe
KLT-switching: Higher cost, but covers a wider range of programs

Implemented preemptive M:N threads on Argobots and evaluated them
They can avoid a deadlock and outperform runtimes based on 1:1 threads
They enable efficient user-level schedulers specialized for specific workloads
With nonpreemptive M:N threads, priority-based scheduling was hard to support

Preemption brings more freedom to M:N threads in implementing efficient user-definedschedulers with low overheads!
22