MainPage:abstract

Rethinking Parallel Execution for Multicore Processors

Guri Sohi, University of Wisconsin

Parallel processing has finally come into the mainstream of computing as almost every processing chip going forward will have multiple processing cores. Software which is typically written as a sequential program, with the intention of running on a uniprocessor, now has to be written to run correctly and efficiently on multiple processor cores. This is a decades old problem, and several decades of research have been invested in trying to find solutions but success has been very limited. New ways about achieving parallel execution are needed in order to easily make use of multicore processors.

The prevailing wisdom, based upon many decades of experience, says that a parallel program representation is required to achieve a parallel execution on multiple processors. This talk will challenge that decades-old wisdom and present a new paradigm for achieving parallel execution. This paradigm, which we call Dynamic Serialization, achieves parallel execution with a sequential program representation using an ordinary object-oriented programming language (C++) on stock commercial hardware using an ordinary stock compiler. Unlike other approaches that are being explored, such as thread-level speculation and transactional memory, dynamic serialialization currently employs no speculation in either hardware or software. This talk will present experimental results gathered on real machines (AMD Barcelona, Intel Nehalem, Sun Niagara) showing that the new paradigm can achieve parallel execution speedups comparable to traditional parallel execution techniques, but can do so with a sequential program representation that does not suffer from the challenges and drawbacks of a parallel representation.

TBD

Martin Rinard, MIT

Simple Read/Write Effect Typing in C#

Joe Duffy, Microsoft

This talk presents a simple imperative type system extension that make effects known to the Common Language Runtime (CLR)'s type system. The motivation for this work is enabling deterministic and provably race-free concurrent programming statically, by construction, with a model that spans data parallel and message passing programming styles. By fusing "effects" and "regions" using simple and natural object oriented concepts, it has been possible to seamlessly add this support to an existing programming language and framework: namely, C# and the .NET Framework. And what's better, it allows parallelism to be extracted often without the programmer knowing it, in constructs like data comprehensions and library routines.

'BIO': Joe Duffy is an architect in the technical strategy group at Microsoft, where his main focus is on concurrent languages, runtimes, and operating systems. Previously he led the creation of Parallel Language Integrated Query (PLINQ), Parallel Extensions to the .NET Framework, and software transactional memory on the Common Language Runtime (CLR) team. His latest book, Concurrent Programming on Windows (Addison-Wesley), was published in November 2008, and his next, Notation & Thought: A Brief History of Programming Languages, is well underway. When not working, Joe enjoys studying the history of mathematics, dabbling in various branches of abstract algebra, and, most of all, spending time and traveling with his fiancée Kim.

Disciplined Support for Deterministic and Non-deterministic Parallelism

VIkram Adve, University of Illinois

Simple Architectural Support for Determinism

Josep Torrellas, University of Illinois"

Machine architecture will play a role in the push for determinism. It may take the more expensive approach of enforcing determinism, or may follow the cheaper approach of encouraging or even just checking for determinism. This talk will explore some alternatives, focusing on the latter approaches.

Grace: Safe Multithreaded Programming for C/C++

Emery Berger, University of Massachusetts"

The shift from single to multiple core architectures means that programmers must write concurrent, multithreaded programs in order to increase application performance. Unfortunately, multithreaded applications are susceptible to numerous errors, including deadlocks, race conditions, atomicity violations, and order violations. These errors are notoriously difficult for programmers to debug.

This talk presents Grace, a software-only runtime system designed to enforce the correctness of a class of multithreaded programs: those based on fork-join parallelism. By turning threads into processes, leveraging virtual memory protection, and imposing a sequential commit protocol, Grace provides programmers with the appearance of deterministic, sequential execution, while taking advantage of available processing cores to run code concurrently and efficiently. Experimental results demonstrate Grace's effectiveness: with modest code changes (1-16 lines) across a suite of computationally-intensive benchmarks, Grace can achieve high scalability and performance while enforcing correct execution.

Deterministic Shared Memory Multiprocessing

Joseph Devietti, University of Washington

urrent shared memory multicore and multiprocessor systems are nondeterministic. This frustrates debugging and limits the ability to properly test multithreaded code, becoming a major stumbling block to the much-needed widespread adoption of parallel programming. In this paper we make the case for fully deterministic shared memory multiprocessing (DMP). Previous approaches to coping with nondeterminism in multithreaded programs have focused on replay, a technique useful only for debugging. In contrast, while DMP systems are directly useful for debugging by offering repeatability by default, we argue that parallel programs should execute deterministically in the field as well. We show that determinism can be provided with little performance cost on future hardware.