Optimistic Execution Techniques for Lightweight Threads

Event Sponsor: 
Mathematics and Computer Science Division Seminar
Start Date: 
Sep 29 2017 - 10:30am
Building 240/Room 4301
Argonne National Laboratory
Shintaro Iwasaki
Speaker(s) Title: 
The University of Tokyo
Halim Amer

User-level threads have been widely adopted by numerous parallel systems and libraries to efficiently parallelize irregular applications on today's multicore processors. Through requirements of threading features and capabilities are application-dependent, most previous lightweight parallel systems and libraries provide only two types of threads with opposing trade-offs. The first one is a fully-fledged user-level thread, with all capabilities expected from threads. The other is a run-to-completion thread, which is more lightweight but does not support suspend/resume capabilities. This trade-off between thread capabilities and their associated fundamental costs has still not been fully covered, however. In particular, the question on whether there are techniques that offer a better trade-off than the above opposing methods and how they relate to applications is still open.

In this talk, we will attempt to cover this gap by investigating the fundamental overheads of several threading methods that exist in the literature as well as new techniques we have developed. Some of these techniques are optimistic; that is, threads start as run-to-completion threads and then are dynamically promoted to fully-fledged threads when suspension is imminent. Thanks to this lazy promotion, thread management overheads are minimized when threads do not suspend. These methods, however, impose certain constraints on the programmer, which limits their applicability. We present the indispensable overheads and constraints of all of these techniques with their highly efficient implementations and integration to Argobots. These techniques have been evaluated with fine-grained parallel programs to get insight into their
practicality and performance characteristics.

*Speaker's Bio*:
Shintaro Iwasaki is a Ph.D. candidate at the University of Tokyo in Japan. He received his B.S. and M.S. degrees from the University of Tokyo in 2015 and 2017. His current research interests include parallel languages, compilers, runtime systems and scheduling techniques.