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 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.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Qi, Qi

Advisor dc:contributor.advisor

• Leiserson, Charles E.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/138981

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/138981