An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems
In this thesis, I present and analyze the novel stack-augmented split-tree data structure to support splitter hyperobjects for task-parallel systems. Splitters can mitigate races on shared, nonlocal state, where parallel nested tasks make independent local modifications without affecting shared hist...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/138981 |
| _version_ | 1826206047357894656 |
|---|---|
| author | Qi, Qi |
| author2 | Leiserson, Charles E. |
| author_facet | Leiserson, Charles E. Qi, Qi |
| author_sort | Qi, Qi |
| collection | MIT |
| description | In this thesis, I present and analyze the novel stack-augmented split-tree data structure to support splitter hyperobjects for task-parallel systems. Splitters can mitigate races on shared, nonlocal state, where parallel nested tasks make independent local modifications without affecting shared history. The data structure is inspired by “persistent” trees, but refined to achieve optimal performance in the common case. I prove that in a program with 𝑛 splitter variables using the mechanism based on the stack-augmented split-tree data structure, read and write accesses to a splitter variable cost Θ(1) except for the first access after a task migration, which costs 𝑂(log 𝑛 + log 𝐷) where 𝐷 is the maximum depth of task nesting. This splitter data structure will enable the parallelization of search algorithms for computationally expensive applications, such as SAT solvers, theorem provers, and game-playing programs. This thesis also contains theory and implementation work on other topics related to task-parallel programming and work stealing schedulers. Some parts of this thesis represent joint work with William Kuszmaul. |
| first_indexed | 2024-09-23T13:23:14Z |
| format | Thesis |
| id | mit-1721.1/138981 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:23:14Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1389812022-01-15T03:27:11Z An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems Qi, Qi Leiserson, Charles E. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science In this thesis, I present and analyze the novel stack-augmented split-tree data structure to support splitter hyperobjects for task-parallel systems. Splitters can mitigate races on shared, nonlocal state, where parallel nested tasks make independent local modifications without affecting shared history. The data structure is inspired by “persistent” trees, but refined to achieve optimal performance in the common case. I prove that in a program with 𝑛 splitter variables using the mechanism based on the stack-augmented split-tree data structure, read and write accesses to a splitter variable cost Θ(1) except for the first access after a task migration, which costs 𝑂(log 𝑛 + log 𝐷) where 𝐷 is the maximum depth of task nesting. This splitter data structure will enable the parallelization of search algorithms for computationally expensive applications, such as SAT solvers, theorem provers, and game-playing programs. This thesis also contains theory and implementation work on other topics related to task-parallel programming and work stealing schedulers. Some parts of this thesis represent joint work with William Kuszmaul. M.Eng. 2022-01-14T14:42:32Z 2022-01-14T14:42:32Z 2021-06 2021-06-17T20:14:05.909Z Thesis https://hdl.handle.net/1721.1/138981 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Qi, Qi An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems |
| title | An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems |
| title_full | An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems |
| title_fullStr | An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems |
| title_full_unstemmed | An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems |
| title_short | An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems |
| title_sort | efficient data structure for implementing splitter hyperobjects in task parallel systems |
| url | https://hdl.handle.net/1721.1/138981 |
| work_keys_str_mv | AT qiqi anefficientdatastructureforimplementingsplitterhyperobjectsintaskparallelsystems AT qiqi efficientdatastructureforimplementingsplitterhyperobjectsintaskparallelsystems |