loading...
Implementing Sequentially Consistent Programs on Processor Consistent Platforms
Hong Kong, SAR, China May 10-May 12
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2004.13005002004 International Symposium on Paral ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Lisa Higham, The University of Calgary, Canada
Jalal Kawash, The University of Calgary, Canada; American University of Sharjah, UAE
This paper investigates 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 the semantics of one variant of processor consistency, known as PC-G. We first provide a simple program transformation, and prove that it compiles any 2-process program with only single-writer variables. We show that this transformation is not a general compiler for 3 or more processes; however, it does correctly transform some specific n-process programs. In particular, for the special case of the (expected) wait-free 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.
Citation:
Lisa Higham, Jalal Kawash, "Implementing Sequentially Consistent Programs on Processor Consistent Platforms," ispan, pp.326, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.