Combining Task Parallelism and Multithreaded Concurrency
In this thesis, I present Multicilk, a threads library based on C11 threads and the OpenCilk runtime for enabling task parallelism within multiple concurrent threads. With Multicilk, a programmer can parallelize threads in a multithreaded application simply by using Cilk independently within each th...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143325 |
| _version_ | 1811069758751113216 |
|---|---|
| author | Pusapaty, Sai Sameer |
| author2 | Leiserson, Charles E. |
| author_facet | Leiserson, Charles E. Pusapaty, Sai Sameer |
| author_sort | Pusapaty, Sai Sameer |
| collection | MIT |
| description | In this thesis, I present Multicilk, a threads library based on C11 threads and the OpenCilk runtime for enabling task parallelism within multiple concurrent threads. With Multicilk, a programmer can parallelize threads in a multithreaded application simply by using Cilk independently within each thread. Without Multicilk, doing so violates the semantics that we expect in concurrent thread programming, leading to catastrophic failure of the application. No other existing combination of task-parallel system — including OpenMP, TBB, and TPL, and the various other implementations of Cilk — and threads library — including C11, C++11, Pthreads, and WinAPI threads — can parallelize multithreaded applications transparently and modularly.
The key insight behind Multicilk recognizes that integrating task-parallel systems with multithreaded concurrency requires two layers of thread abstraction that are conflated in previous systems. Service threads implement the workers in the Cilk runtime system. But the Cilk computation itself, called a cilk, though implemented by many service threads, itself provides the abstraction of a single application thread to other threads within the multithreaded application, regardless of whether they are cilks. Multicilk employs a technique called impersonation to individual workers to act on behalf of the entire cilk, providing the same interface to the outside world as it would it were an ordinary thread. This powerful “two-layer-cake” abstraction enables ordinary multithreaded applications to be ported to a Cilk environment and parallelized in a straightforward and modular fashion.
My Multicilk implementation for OpenCilk provides two thread libraries corresponding to the layers in the two-layer cake, as well as some modifications to the OpenCilk runtime system. The service-thread library is the standard glibc. The application-thread library was created by modifying eight glibc functions using 63 lines of source code and writing wrappers for four glibc functions using 115 lines of code, amounting to about half of the 25 functions in the C11 sublibrary of glibc. I wrote 180 lines of utility functions for threading and synchronization. The changes to OpenCilk amounted to 62 lines, also for threading and synchronization. In sum, I added or modified just over 400 lines of source code to implement Multicilk. |
| first_indexed | 2024-09-23T08:15:34Z |
| format | Thesis |
| id | mit-1721.1/143325 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:15:34Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1433252022-06-16T03:56:57Z Combining Task Parallelism and Multithreaded Concurrency Pusapaty, Sai Sameer Leiserson, Charles E. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science In this thesis, I present Multicilk, a threads library based on C11 threads and the OpenCilk runtime for enabling task parallelism within multiple concurrent threads. With Multicilk, a programmer can parallelize threads in a multithreaded application simply by using Cilk independently within each thread. Without Multicilk, doing so violates the semantics that we expect in concurrent thread programming, leading to catastrophic failure of the application. No other existing combination of task-parallel system — including OpenMP, TBB, and TPL, and the various other implementations of Cilk — and threads library — including C11, C++11, Pthreads, and WinAPI threads — can parallelize multithreaded applications transparently and modularly. The key insight behind Multicilk recognizes that integrating task-parallel systems with multithreaded concurrency requires two layers of thread abstraction that are conflated in previous systems. Service threads implement the workers in the Cilk runtime system. But the Cilk computation itself, called a cilk, though implemented by many service threads, itself provides the abstraction of a single application thread to other threads within the multithreaded application, regardless of whether they are cilks. Multicilk employs a technique called impersonation to individual workers to act on behalf of the entire cilk, providing the same interface to the outside world as it would it were an ordinary thread. This powerful “two-layer-cake” abstraction enables ordinary multithreaded applications to be ported to a Cilk environment and parallelized in a straightforward and modular fashion. My Multicilk implementation for OpenCilk provides two thread libraries corresponding to the layers in the two-layer cake, as well as some modifications to the OpenCilk runtime system. The service-thread library is the standard glibc. The application-thread library was created by modifying eight glibc functions using 63 lines of source code and writing wrappers for four glibc functions using 115 lines of code, amounting to about half of the 25 functions in the C11 sublibrary of glibc. I wrote 180 lines of utility functions for threading and synchronization. The changes to OpenCilk amounted to 62 lines, also for threading and synchronization. In sum, I added or modified just over 400 lines of source code to implement Multicilk. M.Eng. 2022-06-15T13:12:43Z 2022-06-15T13:12:43Z 2022-02 2022-02-22T18:31:51.862Z Thesis https://hdl.handle.net/1721.1/143325 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Pusapaty, Sai Sameer Combining Task Parallelism and Multithreaded Concurrency |
| title | Combining Task Parallelism and Multithreaded Concurrency |
| title_full | Combining Task Parallelism and Multithreaded Concurrency |
| title_fullStr | Combining Task Parallelism and Multithreaded Concurrency |
| title_full_unstemmed | Combining Task Parallelism and Multithreaded Concurrency |
| title_short | Combining Task Parallelism and Multithreaded Concurrency |
| title_sort | combining task parallelism and multithreaded concurrency |
| url | https://hdl.handle.net/1721.1/143325 |
| work_keys_str_mv | AT pusapatysaisameer combiningtaskparallelismandmultithreadedconcurrency |