Semantic Language Extensions for Implicit Parallel Programming

Abstract:

Several emerging fields of science and engineering are increasingly
characterized by computationally intensive programs. Without parallelization,
such programs do not benefit from the increasing core counts available in todays
chip multiprocessors. However, writing correct and well-performing parallel
programs is widely perceived to be an extremely hard problem. In order to
understand the challenges faced by scientific programmers in effectively
leveraging parallel computation, this dissertation first presents an in-depth
field study of the practice of computational science.

Based on the results of the field study, this dissertation proposes two new
implicit parallel programming (IPP) solutions. With IPP, artificial constraints
imposed by sequential models for automatic parallelization are overcome by use
of semantic programming extensions. These preserve the ease of sequential
programming and enable multiple parallelism forms without additional
parallelism constructs, achieving the best of both automatic and explicit
parallelization.

The first IPP solution, Commutative Set, generalizes existing notions of
semantic commutativity. It allows a programmer to relax execution orders
prohibited under a sequential programming model with a high degree of
expressiveness. The second IPP solution, WeakC, provides language extensions to
relax strict consistency requirements of sequential data structures, and
dynamically optimizes a parallel configuration of these data structures via a
combined compiler-runtime system.

This dissertation evaluates both Commutative Set and WeakC on real-world
applications running on real hardware, including some that are actively used by
some scientists in their day-to-day research. The detailed experimental
evaluation results demonstrate the effectiveness of the proposed techniques.