Amir Ashraf Kamil and Katherine A. Yelick

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-41

April 18, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-41.pdf

A fundamental problem in the analysis of parallel programs is to determine when two statements in a program may run concurrently. This analysis is the parallel analog to control flow analysis on serial programs and is useful in detecting parallel programming errors and as a precursor to semantics-preserving code transformations. We consider the problem of analyzing parallel programs that access shared memory and use barrier synchronization, specifically those with textually aligned barriers and single-valued expressions. We present an intermediate graph representation for parallel programs and an efficient interprocedural analysis algorithm that conservatively computes the set of all concurrent statements.We improve the precision of this algorithm by using context-free language reachability to ignore infeasible program paths. We then apply the algorithms to static race detection and enforcing a sequentially consistent execution in the Titanium programming language and show that both can benefit from the concurrency information provided.

---

BibTeX citation:

@techreport{Kamil:EECS-2006-41,
    Author= {Kamil, Amir Ashraf and Yelick, Katherine A.},
    Title= {Concurrency Analysis for Parallel Programs with Textually Aligned Barriers},
    Year= {2006},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-41.html},
    Number= {UCB/EECS-2006-41},
    Abstract= {A fundamental problem in the analysis of parallel programs is to determine when two statements in a program may run concurrently. This analysis is the parallel analog to control flow analysis on serial programs and is useful in detecting parallel programming errors and as a precursor to semantics-preserving code transformations. We consider the problem of analyzing parallel programs that access shared memory and use barrier synchronization, specifically those with textually aligned barriers and single-valued expressions. We present an intermediate graph representation for parallel programs and an efficient interprocedural analysis algorithm that conservatively computes the set of all concurrent statements.We improve the precision of this algorithm by using context-free language reachability to ignore infeasible program paths. We then apply the algorithms to static race detection and enforcing a sequentially consistent execution in the Titanium programming language and show that both can benefit from the concurrency information provided.},
}

EndNote citation:

%0 Report
%A Kamil, Amir Ashraf 
%A Yelick, Katherine A. 
%T Concurrency Analysis for Parallel Programs with Textually Aligned Barriers
%I EECS Department, University of California, Berkeley
%D 2006
%8 April 18
%@ UCB/EECS-2006-41
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-41.html
%F Kamil:EECS-2006-41