Wei-Yu Chen, Arvind Krishnamurthy and Katherine Yelick

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1272
September 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1272.pdf

The simplest semantics for parallel shared memory programs is sequential consistency in which memory operations appear to take place in the order specified by the program. But many compiler optimizations and hardware features explicitly reorder memory operations or make use of overlapping memory operations which may violate this constraint. To ensure sequential consistency while allowing for these optimizations, traditional data dependence analysis is augmented with a parallel analysis called cycle detection. In this paper, we present new algorithms to enforce sequential consistency for the special case of the Single Program Multiple Data (SPMD) model of parallelism. First, we present an algorithm for the basic cycle detection problem, which lowers the running time from O( n^3) to O( n^2). Next, we present three polynomial-time methods that more accurately support programs with array accesses. These results are a step toward making sequentially consistent shared memory programming a practical model across a wide range of languages and hardware platforms.

BibTeX citation:

@techreport{Chen:CSD-03-1272,
    Author = {Chen, Wei-Yu and Krishnamurthy, Arvind and Yelick, Katherine},
    Title = {Polynomial-time Algorithms for Enforcing Sequential Consistency for SPMD Programs with Arrays},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Sep},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6238.html},
    Number = {UCB/CSD-03-1272},
    Abstract = {The simplest semantics for parallel shared memory programs is sequential consistency in which memory operations appear to take place in the order specified by the program. But many compiler optimizations and hardware features explicitly reorder memory operations or make use of overlapping memory operations which may violate this constraint. To ensure sequential consistency while allowing for these optimizations, traditional data dependence analysis is augmented with a parallel analysis called cycle detection. In this paper, we present new algorithms to enforce sequential consistency for the special case of the Single Program Multiple Data (SPMD) model of parallelism. First, we present an algorithm for the basic cycle detection problem, which lowers the running time from <i>O</i>(<i>n</i>^3) to <i>O</i>(<i>n</i>^2). Next, we present three polynomial-time methods that more accurately support programs with array accesses. These results are a step toward making sequentially consistent shared memory programming a practical model across a wide range of languages and hardware platforms.}
}

EndNote citation:

%0 Report
%A Chen, Wei-Yu
%A Krishnamurthy, Arvind
%A Yelick, Katherine
%T Polynomial-time Algorithms for Enforcing Sequential Consistency for SPMD Programs with Arrays
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1272
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6238.html
%F Chen:CSD-03-1272