File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/2345156.2254090
- Scopus: eid_2-s2.0-84866403271
- WOS: WOS:000307582100019
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Sound and precise analysis of parallel programs through schedule specialization
Title | Sound and precise analysis of parallel programs through schedule specialization |
---|---|
Authors | |
Keywords | Parallel programs Specialization Multithreading Data-flow analysis Control-flow analysis Constraint solving |
Issue Date | 2012 |
Citation | ACM SIGPLAN Notices, 2012, v. 47, n. 6, p. 205-216 How to Cite? |
Abstract | Parallel programs are known to be difficult to analyze. A key reason is that they typically have an enormous number of execution interleavings, or schedules. Static analysis over all schedules requires over-approximations, resulting in poor precision; dynamic analysis rarely covers more than a tiny fraction of all schedules. We propose an approach called schedule specialization to analyze a parallel program over only a small set of schedules for precision, and then enforce these schedules at runtime for soundness of the static analysis results. We build a schedule specialization framework for C/C++ multithreaded programs that use Pthreads. Our framework avoids the need to modify every analysis to be schedule-aware by specializing a program into a simpler program based on a schedule, so that the resultant program can be analyzed with stock analyses for improved precision. Moreover, our framework provides a precise schedule-aware def-use analysis on memory locations, enabling us to build three highly precise analyses: an alias analyzer, a data-race detector, and a path slicer. Evaluation on 17 programs, including 2 real-world programs and 15 popular benchmarks, shows that analyses using our framework reduced may-aliases by 61.9%, false race reports by 69%, and path slices by 48.7%; and detected 7 unknown bugs in well-checked programs. © 2012 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/207916 |
ISSN | 2020 SCImago Journal Rankings: 0.310 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wu, J | - |
dc.contributor.author | Tang, Y | - |
dc.contributor.author | Hu, G | - |
dc.contributor.author | Cui, H | - |
dc.contributor.author | Yang, J | - |
dc.date.accessioned | 2015-01-26T11:46:42Z | - |
dc.date.available | 2015-01-26T11:46:42Z | - |
dc.date.issued | 2012 | - |
dc.identifier.citation | ACM SIGPLAN Notices, 2012, v. 47, n. 6, p. 205-216 | - |
dc.identifier.issn | 1523-2867 | - |
dc.identifier.uri | http://hdl.handle.net/10722/207916 | - |
dc.description.abstract | Parallel programs are known to be difficult to analyze. A key reason is that they typically have an enormous number of execution interleavings, or schedules. Static analysis over all schedules requires over-approximations, resulting in poor precision; dynamic analysis rarely covers more than a tiny fraction of all schedules. We propose an approach called schedule specialization to analyze a parallel program over only a small set of schedules for precision, and then enforce these schedules at runtime for soundness of the static analysis results. We build a schedule specialization framework for C/C++ multithreaded programs that use Pthreads. Our framework avoids the need to modify every analysis to be schedule-aware by specializing a program into a simpler program based on a schedule, so that the resultant program can be analyzed with stock analyses for improved precision. Moreover, our framework provides a precise schedule-aware def-use analysis on memory locations, enabling us to build three highly precise analyses: an alias analyzer, a data-race detector, and a path slicer. Evaluation on 17 programs, including 2 real-world programs and 15 popular benchmarks, shows that analyses using our framework reduced may-aliases by 61.9%, false race reports by 69%, and path slices by 48.7%; and detected 7 unknown bugs in well-checked programs. © 2012 ACM. | - |
dc.language | eng | - |
dc.relation.ispartof | ACM SIGPLAN Notices | - |
dc.subject | Parallel programs | - |
dc.subject | Specialization | - |
dc.subject | Multithreading | - |
dc.subject | Data-flow analysis | - |
dc.subject | Control-flow analysis | - |
dc.subject | Constraint solving | - |
dc.title | Sound and precise analysis of parallel programs through schedule specialization | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/2345156.2254090 | - |
dc.identifier.scopus | eid_2-s2.0-84866403271 | - |
dc.identifier.volume | 47 | - |
dc.identifier.issue | 6 | - |
dc.identifier.spage | 205 | - |
dc.identifier.epage | 216 | - |
dc.identifier.isi | WOS:000307582100019 | - |
dc.identifier.issnl | 1523-2867 | - |