Name
Abstract | ||
|---|---|---|
Most multithreaded programming languages prohibit or discourage data races. By avoiding data races, we are guaranteed that variables accessed within a synchronization-free code region cannot be modified by other threads, allowing us to reason about such code regions as though they were single-threaded. However, such single-threaded reasoning is not limited to synchronization-free regions. We present a simple characterization of extended interference-free regions in which variables cannot be modified by other threads. This characterization shows that, in the absence of data races, important code analysis problems often have surprisingly easy answers. For instance, we can use local analysis to determine when lock and unlock calls refer to the same mutex. Our characterization can be derived from prior work on safe compiler transformations, but it can also be simply derived from first principles, and justified in a very broad context. In addition, systematic reasoning about overlapping interference-free regions yields insight about optimization opportunities that were not previously apparent. We give preliminary results for a prototype implementation of interference-free regions in the LLVM compiler infrastructure. We also discuss other potential applications for interference-free regions. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1988915.1988922 | MSPC |
Keywords | Field | DocType |
data-race-free program,extended sequential reasoning,local analysis,code region,simple characterization,interference-free region,overlapping interference-free regions yield,important code analysis problem,extended interference-free region,synchronization-free code region,llvm compiler infrastructure,data race,concurrency,programming language,first principle,compiler optimization | Static program analysis,Programming language,Semaphore,Computer science,Lock (computer science),Concurrency,Optimizing compiler,Theoretical computer science,Compiler,Thread (computing),Local analysis | Conference |
Citations | PageRank | References |
12 | 0.55 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laura Effinger-Dean | 1 | 62 | 2.60 |
| Hans Boehm | 2 | 632 | 38.83 |
| Dhruva R. Chakrabarti | 3 | 188 | 13.69 |
| Pramod Joisha | 4 | 18 | 1.31 |