Dynamic Threading Platforms

High-level abstractions for parallel programming simplify the development of efficient par-allel applications. In particular, composable abstractions allow programmers to construct a complex parallel application out of multiple components, where each component itself may be designed to exploit parallelism. This dissertation presents the design of three com-posable abstractions for synchronization in dynamic-threading platforms, based on ideas of task-graph execution, helper locks, and transactional memory. These designs demonstrate provably efficient runtime scheduling for programs with synchronization. For applications that use task-graph synchronization, I demonstrate provably efficient execution of task graphs with arbitrary dependencies as a library in a fork-join platform. Conventional wisdom suggests that a fork-join platform can execute an arbitrary task graph only with special runtime support or by converting the graph into a series-parallel compu-tation which has less parallelism. By implementing Nabbit, a Cilk++ library for arbi-trary task-graph execution, I show that one can in fact avoid introducing runtime modifi