Parallel Programming Must Be Deterministic By Default
The general-purpose computing industry is at a major crossroads. Power constraints and design complexity have pushed microprocessor designers to use multiple execution cores on a single die, with 4-16 cores being commonplace today, many tens of cores expected in the next 3-5 years, and some projections claiming hundreds of cores on a chip within a decade. Increases in application performance will depend on their ability to harness this parallelism. In the past, new software capabilities and technologies have been strongly driven by increases in processor performance (keeping up with increasing memory capacity and network bandwidth). In the future, such advances in mainstream applications will only occur if software developers are able to harness parallelism for higher performance. Mainstream applications today primarily use threads programming for parallelism, whether through libraries like pthreads and Intel’s Threading Building Blocks (TBB), or multithreaded languages like Java and C#. There is broad consensus, however, that programs written in current threads-based programming models can be extremely diffi- cult to understand and debug. A root cause of the problem is that the execution of a shared-memory program can follow one of a large number of interleavings of dependent memory accesses, and some of these interleavings can potentially produce different results. In contrast, a large class of computations is inherently deterministic; i.e., a given input for such a (correct) computation always produces the same output. Specifically, concurrency is used for broadly two purposes. For “reactive” computations like servers, interactive games, and embedded systems, concurrency is part of the problem specification; e.g., serving multiple external requests. This concurrency is usually necessary for correctness; e.g., to ensure bounded response times. On the other hand, for “transformative” computations, concurrency is not part of the problem specification and is not required for correctness. Here, concurrency is used solely for performance – to produce the output faster. Reactive computations may internally include transformative computations; e.g., a physics simulation in a game. Many, though not all, transformative algorithms are deterministic (a given input always produces the same output), and programming them with a fundamentally non-deterministic model unnecessarily introduces extraordinary complexity. There is a rich literature discussing the merits of determinism and proposing deterministic models and languages. In a recent article [10], Lee eloquently argues that if we are to have any hope of simplifying parallel programming for the vast majority of mainstream programmers and applications, then parallel programming models must greatly constrain the possible interleavings of program executions. In particular, deterministic algorithms must be expressible in a style that guarantees determinism, and non-deterministic behaviors, where desired, must be requested explicitly. Much of the prior work on determinism, however, has been in a context that is not general enough (e.g., regular data parallel operators [14]) and/or requires significant departure from mainstream programming styles (e.g., pure functional [12], dataflow [7], and actor [10] styles). In contrast, a large fraction of modern applications are developed in an object-oriented style with expressive use of features such as aliasing through references, imperative updates, dynamic method dispatch, and extensive reuse of sophisticated libraries and frameworks. Programmers are already familiar with this style, and there is a large existing code base written in languages such as Java, C++ and C#. Much of this code will need to be ported to multicore, as it is simply not feasible to rewrite it all from scratch in a new language. Thus, we believe it is crucial for parallel languages to support an object-oriented style, including the use of O-O libraries and frameworks. In this paper, we argue that to simplify parallel programming, determinism must be brought to mainstream object-oriented programming languages. A broad research agenda will be required to achieve this goal
Free download research paper
CSE PROJECTS