New techniques for compiling data-parallel languages

Data-parallel programming languages provide a portable, high level abstraction to support rapid parallel program development. Data-parallel languages are widely applicable, and considerable research has been devoted to compiling them for efficient execution. Much of this work has focused on implementing a shared address space on a distributed-memory machine, particularly for programs with regular communication patterns. Compiler support for non-regular applications has been limited to iterative irregular applications, with dynamic repetitive communication patterns.; This thesis describes three new compiler, language and run-time system techniques targeting data-parallel programs with adaptive and dynamic communication patterns. These techniques have been implemented in a compiler for the language C{dollar}sp{lcub}**{rcub}{dollar}, and include:; Implementing conflict-free data access. C{dollar}sp{lcub}**{rcub}{dollar}'s semantics avoid data access conflicts between parallel functions. We explore and compare two complementary implementations of conflict-free access. For parallel functions with regular data access patterns, the compiler inserts code in the program to maintain copies. When compiler data access analysis is imprecise, the compiler relies on a Loosely-Coherent Memory system to create transparent fine-grain copies.; User-defined reductions. Most data-parallel languages restrict reductions, which combine values from parallel operations, to a predefined set of reduction operators. User-defined reductions extend reductions in two ways, by allowing new combining operations, and by applying reductions to user-defined data types. This thesis motivates the need for user-defined reductions, and describes the design and efficient implementation of reductions in C{dollar}sp{lcub}**{rcub}{dollar} with only message-passing support.; Compiler-directed shared-memory communication. This thesis describes how a compiler and a predictive cache-coherence protocol can implement shared-memory communication efficiently for iterative adaptive applications. The compiler uses data-flow analysis to identify points in a program where potential repetitive communication patterns exist. An incremental predictive protocol builds a communication schedule for one iteration and utilizes a schedule to pre-send data in subsequent iterations. The protocol reduces the number of remote data requests, and the total remote access latency.