When sequential programs are extended with parallel code, shared memory multithreading is the common programming model. The transition from a sequential to a correct parallel program is however a difficult task. Race conditions are a common source of error, which can introduce (undesired) nondeterminism. We show how language support can alleviate the task of parallelization: Parallel programs are by default determinate, nondeterminism can be introduced selectively. The key idea is to define an implicit order among parallel tasks and resolve race conditions among tasks accordingly.

The ideas are illustrated as extensions of the X10 programming language. The approach leads quickly to a correct parallelization of an application with irregular memory access and unstructured data dependencies (umt2k). We also show the importance of task scheduling and data access locality and demonstrate how such performance critical aspects can be addressed at an algorithmic level.