ACM Home Page
Please provide us with feedback. Feedback
Digital Library logoTake a look at the new version of this page: [ beta version ]. Tell us what you think.
Asserting and checking determinism for multithreaded programs
Full text PdfPdf (416 KB)
Source
Foundations of Software Engineering archive
Proceedings of the the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering table of contents
Amsterdam, The Netherlands
SESSION: Specifications and verification 1 table of contents
Pages: 3-12  
Year of Publication: 2009
ISBN:978-1-60558-001-2
Authors
Jacob Burnim  University of California, Berkeley, Berkeley, CA, USA
Koushik Sen  University of California, Berkeley, Berkeley, CA, USA
Sponsors
ACM: Association for Computing Machinery
SIGSOFT: ACM Special Interest Group on Software Engineering
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 33,   Downloads (12 Months): 160,   Citation Count: 0
Additional Information:

abstract   references   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/1595696.1595700
What is a DOI?

ABSTRACT

The trend towards processors with more and more parallel cores is increasing the need for software that can take advantage of parallelism. The most widespread method for writing parallel software is to use explicit threads. Writing correct multithreaded programs, however, has proven to be quite challenging in practice. The key difficulty is non-determinism. The threads of a parallel application may be interleaved non-deterministically during execution. In a buggy program, non-deterministic scheduling will lead to non-deterministic results - some interleavings will produce the correct result while others will not.

We propose an assertion framework for specifying that regions of a parallel program behave deterministically despite non-deterministic thread interleaving. Our framework allows programmers to write assertions involving pairs of program states arising from different parallel schedules. We describe an implementation of our deterministic assertions as a library for Java, and evaluate the utility of our specifications on a number of parallel Java benchmarks. We found specifying deterministic behavior to be quite simple using our assertions. Further, in experiments with our assertions, we were able to identify two races as true parallelism errors that lead to incorrect non-deterministic behavior. These races were distinguished from a number of benign races in the benchmarks.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
2
 
3
4
 
5
C. Artho, K. Havelund, and A. Biere. High-level data races. Software Testing Verification and Reliability, 13(4):207--227, 2003.
 
6
K. Asanovic, R. Bodik, J. Demmel, T. Keaveny, K. Keutzer, J. D. Kubiatowicz, E. A. Lee, N. Morgan, G. Necula, D. A. Patterson, K. Sen, J. Wawrzynek, D. Wessel, and K. A.Yelick. The parallel computing laboratory at U.C. berkeley: A research agenda based on the Berkeley view. Technical Report UCB/EECS-2008-23, EECS Department, University of California, Berkeley, Mar 2008.
7
8
 
9
R. Bocchino, V. Adve, S. Adve, and M. Snir. Parallel programming must be deterministic by default. In First USENIX Workship on Hot Topics in Parallelism (HOTPAR 2009), March 2009.
10
11
 
12
13
 
14
O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multithreaded Java program test generation. IBM Systems Journal, 41(1):111--125, 2002.
 
15
Edinburgh Parallel Computing Centre. Java Grande Forum benchmark suite. www2.epcc.ed.ac.uk/computing/research_activities/java_grande/index_1.html.
16
17
18
19
20
21
22
 
23
R. Floyd. Assigning meanings to programs. Mathematical aspects of computer science, 19(19--32):1, 1967.
24
25
 
26
IEEE. POSIX Part 1: System API- Amend. 1: Realtime Extension {C Language}. IEEE Std 1003.1b--1993, 1994.
 
27
Intel®. Threading Building Blocks for open source. http://threadingbuildingblocks.org/.
28
29
 
30
A. Kaminsky. Parallel Java: A Unified API for Shared Memory and Cluster Parallel Programming in 100% Java. In 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS 2007), March 2007.
 
31
 
32
 
33
34
35
36
37
38
39
 
40
41
42
43
44
 
45
N. Sterling. Warlock: A static data race analysis tool. In USENIX Winter Technical Conference, pages 97--106, 1993.
 
46
S. D. Stoller. Testing concurrent Java programs using randomized scheduling. In Workshop on Runtime Verification (RV'02), volume 70 of ENTCS, 2002.
 
47
W. Thies, M. Karczmarek, and S. Amarasinghe. StreamIt: A language for streaming applications. Lecture Notes in Computer Science, pages 179--196, 2002.
 
48
49

Collaborative Colleagues:
Jacob Burnim: colleagues
Koushik Sen: colleagues