Verifiable early-reply with C++

Date

2007-09-17

Journal Title

Journal ISSN

Volume Title

Publisher

Texas A&M University

Abstract

Concurrent programming can improve performance. However, it comes with two drawbacks. First, concurrent programs can be more difficult to design and reason about than their sequential counterparts. Second, error conditions that do not exist in sequential programs, such as data race conditions and deadlock, can make concurrent programs more unreliable. To make concurrent programming simpler and more reliable, while still providing sufficient performance gains, we present a concurrency framework based on an existing concurrency initiation mechanism called ??????Early-Reply??????. Early-Reply is based on the idea that some functions can produce final return values long before they terminate. Concurrent execution begins when return value of a function is returned to the caller, allowing the rest of the work of the function to be done on an auxiliary thread. The simpler sequential programming model can be used by the caller, because the concurrency is initiated and hidden within the function body. Pike and Sridhar recognized Early-Reply as a way for sequential programs to get the benefits of concurrent execution. They also discussed using object-oriented programming to serialize access to data that needs synchronization. Our work expands on their approach and provides an actual C++ implementation of an Early-Reply based framework. Our framework simplifies concurrent programming for both users and implementers by allowing developers to use sequential reasoning, and by providing a minimal framework interface. Concurrent programming is made more reliable by combining the concurrency synchronization and initiation into one mechanism within the framework, which isolates where race conditions and deadlock can occur. Furthermore, this isolation facilitates the development of a simple set of coding guidelines that can be used by developers (through inspection) or static analysis tools (through verification) to eliminate race conditions and deadlocks. As a motivating example, we parallelize an instructional compiler that processes multiple input source files. For each input file; the parsing and semantic analysis execute on the calling thread, while the code optimization and object code generation execute on an auxiliary thread. Speedups of 1.5 to 1.7 were observed on a dual processor confirming that sufficient performance gains are possible.

Description

Citation