MULTITHREADED PARALLEL DATA STRUCTURES

Abstract

In this thesis we investigate the design and analysis of multithreaded parallel data structures that are both cost-scalable and composable. We introduce a high-level QRMW (queued read-modify-write) DMT (dynamic multithreading) model and a new easily-composable 'span'-type notion called delay. We then implement and prove work/span/delay bounds for many key building blocks within the QRMW DMT model, including higher synchronization primitives, basic batch operations and parallel entropy-sorting. Next we describe an extended implicit batching framework that when applied to any suitable batched data structure (including pipelined ones) yields an atomic data structure (supporting concurrent accesses) with low batching overhead. After that, we showcase novel multithreaded parallel data structures designed using these building blocks, including the batch-parallel 2-3 tree T, the simple parallel map M, the parallel priority queue PQ, and the distribution-sensitive parallel maps WM and FS. Finally, we present efficient schedulers for running QRMW DMT programs on real multi-processor machines.