Using memory mapping to support cactus stacks in work-stealing runtime systems
Many multithreaded concurrency platforms that use a work-stealing runtime system incorporate a "cactus stack," wherein a function's accesses to stack variables properly respect the function's calling ancestry, even when many of the functions operate in parallel. Unfortunately, su...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2011
|
| Online Access: | http://hdl.handle.net/1721.1/64623 |
| _version_ | 1826188670933139456 |
|---|---|
| author | Lee, I-Ting Angelina Boyd-Wickizer, Silas Huang, Zhiyi Leiserson, Charles E. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Lee, I-Ting Angelina Boyd-Wickizer, Silas Huang, Zhiyi Leiserson, Charles E. |
| author_sort | Lee, I-Ting Angelina |
| collection | MIT |
| description | Many multithreaded concurrency platforms that use a work-stealing runtime system incorporate a "cactus stack," wherein a function's accesses to stack variables properly respect the function's calling ancestry, even when many of the functions operate in parallel. Unfortunately, such existing concurrency platforms fail to satisfy at least one of the following three desirable criteria:
full interoperability with legacy or third-party serial binaries that have been compiled to use an ordinary linear stack,
a scheduler that provides near-perfect linear speedup on applications with sufficient parallelism, and
bounded and efficient use of memory for the cactus stack.
We have addressed this cactus-stack problem by modifying the Linux operating system kernel to provide support for thread-local memory mapping (TLMM). We have used TLMM to reimplement the cactus stack in the open-source Cilk-5 runtime system. The Cilk-M runtime system removes the linguistic distinction imposed by Cilk-5 between serial code and parallel code, erases Cilk-5's limitation that serial code cannot call parallel code, and provides full compatibility with existing serial calling conventions. The Cilk-M runtime system provides strong guarantees on scheduler performance and stack space. Benchmark results indicate that the performance of the prototype Cilk-M 1.0 is comparable to the Cilk 5.4.6 system, and the consumption of stack space is modest. |
| first_indexed | 2024-09-23T08:02:54Z |
| format | Article |
| id | mit-1721.1/64623 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:02:54Z |
| publishDate | 2011 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/646232022-09-30T07:07:41Z Using memory mapping to support cactus stacks in work-stealing runtime systems Lee, I-Ting Angelina Boyd-Wickizer, Silas Huang, Zhiyi Leiserson, Charles E. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Leiserson, Charles E. Leiserson, Charles E. Lee, I-Ting Angelina Boyd-Wickizer, Silas Huang, Zhiyi Many multithreaded concurrency platforms that use a work-stealing runtime system incorporate a "cactus stack," wherein a function's accesses to stack variables properly respect the function's calling ancestry, even when many of the functions operate in parallel. Unfortunately, such existing concurrency platforms fail to satisfy at least one of the following three desirable criteria: full interoperability with legacy or third-party serial binaries that have been compiled to use an ordinary linear stack, a scheduler that provides near-perfect linear speedup on applications with sufficient parallelism, and bounded and efficient use of memory for the cactus stack. We have addressed this cactus-stack problem by modifying the Linux operating system kernel to provide support for thread-local memory mapping (TLMM). We have used TLMM to reimplement the cactus stack in the open-source Cilk-5 runtime system. The Cilk-M runtime system removes the linguistic distinction imposed by Cilk-5 between serial code and parallel code, erases Cilk-5's limitation that serial code cannot call parallel code, and provides full compatibility with existing serial calling conventions. The Cilk-M runtime system provides strong guarantees on scheduler performance and stack space. Benchmark results indicate that the performance of the prototype Cilk-M 1.0 is comparable to the Cilk 5.4.6 system, and the consumption of stack space is modest. National Science Foundation (U.S.) (Grant 0540248) National Science Foundation (U.S.) (Grant 0615215) 2011-06-21T14:30:17Z 2011-06-21T14:30:17Z 2010-09 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0178-7 http://hdl.handle.net/1721.1/64623 Lee, I-Ting Angelina et al. "Using Memory Mapping to Support Cactus Stacks in Work-Stealing Runtime Systems." in Proceedings of the 19th international conference on Parallel architectures and compilation techniques, PACT '10, Sept. 11-15, 2010, Vienna, Austria. en_US http://dx.doi.org/10.1145/1854273.1854324 Proceedings of the 19th international conference on Parallel architectures and compilation techniques, PACT '10 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Lee, I-Ting Angelina Boyd-Wickizer, Silas Huang, Zhiyi Leiserson, Charles E. Using memory mapping to support cactus stacks in work-stealing runtime systems |
| title | Using memory mapping to support cactus stacks in work-stealing runtime systems |
| title_full | Using memory mapping to support cactus stacks in work-stealing runtime systems |
| title_fullStr | Using memory mapping to support cactus stacks in work-stealing runtime systems |
| title_full_unstemmed | Using memory mapping to support cactus stacks in work-stealing runtime systems |
| title_short | Using memory mapping to support cactus stacks in work-stealing runtime systems |
| title_sort | using memory mapping to support cactus stacks in work stealing runtime systems |
| url | http://hdl.handle.net/1721.1/64623 |
| work_keys_str_mv | AT leeitingangelina usingmemorymappingtosupportcactusstacksinworkstealingruntimesystems AT boydwickizersilas usingmemorymappingtosupportcactusstacksinworkstealingruntimesystems AT huangzhiyi usingmemorymappingtosupportcactusstacksinworkstealingruntimesystems AT leisersoncharlese usingmemorymappingtosupportcactusstacksinworkstealingruntimesystems |