File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Sound and precise analysis of parallel programs through schedule specialization

TitleSound and precise analysis of parallel programs through schedule specialization
Authors
KeywordsParallel programs
Specialization
Multithreading
Data-flow analysis
Control-flow analysis
Constraint solving
Issue Date2012
Citation
ACM SIGPLAN Notices, 2012, v. 47, n. 6, p. 205-216 How to Cite?
AbstractParallel 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 Identifierhttp://hdl.handle.net/10722/207916
ISSN
2015 SCImago Journal Rankings: 0.490

 

DC FieldValueLanguage
dc.contributor.authorWu, J-
dc.contributor.authorTang, Y-
dc.contributor.authorHu, G-
dc.contributor.authorCui, H-
dc.contributor.authorYang, J-
dc.date.accessioned2015-01-26T11:46:42Z-
dc.date.available2015-01-26T11:46:42Z-
dc.date.issued2012-
dc.identifier.citationACM SIGPLAN Notices, 2012, v. 47, n. 6, p. 205-216-
dc.identifier.issn1523-2867-
dc.identifier.urihttp://hdl.handle.net/10722/207916-
dc.description.abstractParallel 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.languageeng-
dc.relation.ispartofACM SIGPLAN Notices-
dc.subjectParallel programs-
dc.subjectSpecialization-
dc.subjectMultithreading-
dc.subjectData-flow analysis-
dc.subjectControl-flow analysis-
dc.subjectConstraint solving-
dc.titleSound and precise analysis of parallel programs through schedule specialization-
dc.typeConference_Paper-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/2345156.2254090-
dc.identifier.scopuseid_2-s2.0-84866403271-
dc.identifier.volume47-
dc.identifier.issue6-
dc.identifier.spage205-
dc.identifier.epage216-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats