The theoretical foundations of parallel programs have historically been defined using unstructured parallel programming constructs such as threads and locks. While these constructs suffice to characterize fundamental properties of parallel program execution such as determinacy, data races, memory consistency, deadlock, and livelock, we argue that they are inappropriate foundations for programmability and performance of parallel software. One can see an analogy with the Turing Machine abstraction which suffices to establish theoretical properties of computable functions, but is an inappropriate foundation for sequential software.

The Habanero Multicore Software Research project at Rice University (http://habanero.rice.edu) has focused on identifying orthogonal sets of structured parallelism primitives that can provide a foundation for improved programmability and performance of parallel software. In this talk, we summarize key primitives for task creation, termination, synchronization and isolation, and show how they can provide rich semantic guarantees for different classes of programs while also being amenable to efficient and scalable implementations. The benefits of structured parallelism will be motivated by illustrating how these primitives can help improve the effectiveness of data race detectors, compilers, and runtime systems, relative to the use of unstructured parallelism.