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.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca