Implementing Sequentially Consistent Programs on Processor Consistent Platforms
Date
2004-02-17
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
<p>Designers of distributed algorithms typically assume strong
memory consistency guarantees, but system implementations provide weaker
guarantees for better performance and scalability. This motivates the study of
how to implement programs designed for sequential consistency on platforms
with weaker consistency models. Typically, such implementations are
impossible using only read and write operations to shared variables. For
example, Sparc's Total Store Order machines (and their even weaker Partial
Store Order and Relaxed Memory Order machines), the PowerPC, Alpha, Java and
most variants of processor consistency all require the use of strong and
expensive built in hardware synchronization primitives to implement mutual
exclusion. One variant of processor consistency originally proposed by
Goodman and called here PC-G is an exception. It is known that PC-G provides
just enough consistency to implement mutual exclusion using only reads and
writes. This paper extends the study of Goodman's version of processor
consistency from specific problems (such as mutual exclusion) to arbitrary
ones. That is, we investigate the existence of compilers to convert programs
that use shared read/write variables with sequentially consistent memory
semantics, to programs that use read/write variables with PC-G consistency
semantics.<p>We first provide a simple program transformation, and prove
that it compiles any 2-process program with only single-writer variables from
sequentially consistency to PC-G consistency. We next prove that no similar
simple compiler exists for even a very restricted class of 2-process
programs.<p>Even though our program transformation is not a general
compiler for 3 or more processes, it does correctly transform some specific
<i>n</i>-process programs from sequentially consistency to PC-G consistency.
In particular, for the special case of the (necessarily randomized) Test&Set
algorithm of Tromp and Vitanyi, our transformation extends to any number of
processes. Thus, one notable outcome is an implementation of Test&Set on PC-G
that uses only reads and writes of shared variables. This is the first
expected, wait-free implementation of Test&Set on any weak memory model, and
illustrates the use of randomization with a weak memory model.
Description
Keywords
Computer Science