CCF: Medium: Routine Parallelism Enabled by Speculation

University Of Rochester, Rochester NY

Investigators

Abstract

Parallel programming is notoriously difficult, but essential to the future of computing. Much of the difficulty stems from the need to guarantee, in advance, that parallel computations will not conflict with one another. Speculation provides an attractive alternative. By monitoring behavior at run time, and retrying computations that conflict, speculation can expose significant amounts of otherwise unexploitable parallelism, while imposing little or no conceptual burden on the programmer. The sponsored research aims to make thread- and process-level speculation a fundamental feature of future programming systems, and to employ it in multiple forms and for multiple purposes: to automatically or semi-automatically parallelize sequential applications; to check, dynamically, the independence of explicitly parallel computations; to isolate the execution of semantically atomic functions; to enable optimizations that are not always safe; to parallelize scripting languages with one-thread-at-a-time semantics; and to profile applications in parallel, for feedback-driven optimization. The project adopts a tiered approach that isolates the users of simpler programming idioms from the need to understand more complex alternatives. At the implementation level, it stresses the seamless integration of shared memory and cluster-level distribution, compiler- and binary translator-based software instrumentation, virtual memory, and hardware speculation/transactions where available. Latter phases of the project place major emphasis on profiling tools to identify potentially independent program regions, which can then safely be executed in parallel (via speculation) in future runs.