Optimistic parallelization of communicating sequential processes

Abstract

We present a transparent program transformation which converts a sequential execution of S1; SZ by a procesl; in a multiprocess environment into an optimistic parallel execution of SI and S2. Such a transformation is valuable in the case where S1 and SZ cannot be para.llelized by static analysis either because S2 reads a value from S1 or because S1 and S2 each interact with an external process. The optimistic transformation works under a weaker set of conditions: (1) if the value Sz reads from S1 can usually, but not always, be correctly guessed ahead of time, and (2) if S1 and S2 interact with an external process, conflicts which violate the ordering of S1 and % are possible but rare. Practical applications of this approach include executing the likely outcome of a test in pwdlel with making the test, and converting sequences of calls into streams of asynchronous sends. We analyze the problem using the framework of guarded cornputatiow, in which each computation is tagged with the set of guesses on which it depends. We present an algorithm for managing communications, thread creation, committing, and aborting in the transformed program. We contrast our approach with related work.