• Information Technology
  • Human Resources
  • Careers
  • Giving
  • Library
  • Bookstore
  • Active Living
  • Continuing Education
  • Go Dinos
  • UCalgary Maps
  • UCalgary Directory
  • Academic Calendar
My UCalgary
Webmail
D2L
ARCHIBUS
IRISS
  • Faculty of Arts
  • Cumming School of Medicine
  • Faculty of Environmental Design
  • Faculty of Graduate Studies
  • Haskayne School of Business
  • Faculty of Kinesiology
  • Faculty of Law
  • Faculty of Nursing
  • Faculty of Nursing (Qatar)
  • Schulich School of Engineering
  • Faculty of Science
  • Faculty of Social Work
  • Faculty of Veterinary Medicine
  • Werklund School of Education
  • Information TechnologiesIT
  • Human ResourcesHR
  • Careers
  • Giving
  • Library
  • Bookstore
  • Active Living
  • Continuing Education
  • Go Dinos
  • UCalgary Maps
  • UCalgary Directory
  • Academic Calendar
  • Libraries and Cultural Resources
View Item 
  •   PRISM Home
  • Science
  • Science Research & Publications
  • View Item
  •   PRISM Home
  • Science
  • Science Research & Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Implementing Sequentially Consistent Programs on Processor Consistent Platforms

Thumbnail
Download
2004-738-03.pdf (159.5Kb)
2004-738-03.ps (151.4Kb)
Download Record
Download to EndNote/RefMan (RIS)
Download to BibTex
Author
Higham, Lisa
Kawash, Jalal
Accessioned
2008-02-27T22:13:14Z
Available
2008-02-27T22:13:14Z
Computerscience
2004-02-17
Issued
2004-02-17
Subject
Computer Science
Type
unknown
Metadata
Show full item record

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
Corporate
University of Calgary
Faculty
Science
Doi
http://dx.doi.org/10.11575/PRISM/30826
Uri
http://hdl.handle.net/1880/45980
Collections
  • Science Research & Publications

Browse

All of PRISMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Download Results

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors

  • Email
  • SMS
  • 403.220.8895
  • Live Chat

Energize: The Campaign for Eyes High

Privacy Policy
Website feedback

University of Calgary
2500 University Drive NW
Calgary, AB T2N 1N4
CANADA

Copyright © 2017