Implementing Sequentially Consistent Programs on Processor Consistent Platforms

Simple item page
dc.contributor.authorHigham, Lisaeng
dc.contributor.authorKawash, Jalaleng
dc.date.accessioned2008-02-27T22:13:14Z
dc.date.available2008-02-27T22:13:14Z
dc.date.computerscience2004-02-17eng
dc.date.issued2004-02-17eng
dc.description.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.eng
dc.description.notesWe 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.caeng
dc.identifier.department2004-738-03eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/30826
dc.identifier.urihttp://hdl.handle.net/1880/45980
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleImplementing Sequentially Consistent Programs on Processor Consistent Platformseng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
2004-738-03.pdf
Size:
159.52 KB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
2004-738-03.ps
Size:
151.4 KB
Format:
Postscript Files
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.86 KB
Format:
Plain Text
Description:
Download
Collections
Science Research & Publications