[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3385412.3386028acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
research-article

SCAF: a speculation-aware collaborative dependence analysis framework

Published: 11 June 2020 Publication History

Abstract

Program analysis determines the potential dataflow and control flow relationships among instructions so that compiler optimizations can respect these relationships to transform code correctly. Since many of these relationships rarely or never occur, speculative optimizations assert they do not exist while optimizing the code. To preserve correctness, speculative optimizations add validation checks to activate recovery code when these assertions prove untrue. This approach results in many missed opportunities because program analysis and thus other optimizations remain unaware of the full impact of these dynamically-enforced speculative assertions. To address this problem, this paper presents SCAF, a Speculation-aware Collaborative dependence Analysis Framework. SCAF learns of available speculative assertions via profiling, computes their full impact on memory dependence analysis, and makes this resulting information available for all code optimizations. SCAF is modular (adding new analysis modules is easy) and collaborative (modules cooperate to produce a result more precise than the confluence of all individual results). Relative to the best prior speculation-aware dependence analysis technique, by computing the full impact of speculation on memory dependence analysis, SCAF dramatically reduces the need for expensive-to-validate memory speculation in the hot loops of all 16 evaluated C/C++ SPEC benchmarks.

References

[1]
Lars Ole Andersen. 1994. Program Analysis and Specialization for the C Programming Language. Technical Report.
[2]
Utpal Banerjee. 1994. Loop Parallelization. Springer US. org/10.1007/978-1-4757-5676-0
[3]
Sam Blackshear, Bor-Yuh Evan Chang, and Manu Sridharan. 2013. Thresher: precise refutations for heap reachability. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’13). Association for Computing Machinery, Seattle, Washington, USA, 275–286.
[4]
[5]
Martin Bravenboer and Yannis Smaragdakis. 2009. Exception analysis and points-to analysis: better together. In Proceedings of the eighteenth international symposium on Software testing and analysis (ISSTA ’09). Association for Computing Machinery, Chicago, IL, USA, 1–12.
[6]
Martin Bravenboer and Yannis Smaragdakis. 2009. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications (OOPSLA ’09). Association for Computing Machinery, Orlando, Florida, USA, 243–262.
[7]
Calin Cascaval, Colin Blundell, Maged Michael, Harold W. Cain, Peng Wu, Stefanie Chiras, and Siddhartha Chatterjee. 2008. Software Transactional Memory: Why Is It Only a Research Toy? Queue 6, 5 (Sept. 2008), 46–58.
[8]
Tong Chen, Jin Lin, Xiaoru Dai, Wei-Chung Hsu, and Pen-Chung Yew. 2004. Data Dependence Profiling for Speculative Optimizations. In Compiler Construction (Lecture Notes in Computer Science), Evelyn Duesterwald (Ed.). Springer, Berlin, Heidelberg, 57–72. org/10.1007/978-3-540-24723-4_5
[9]
William Y. Chen, Scott A. Mahlke, and Wen-mei W. Hwu. 1992. Tolerating First Level Memory Access Latency in High-Performance Systems. In Proceedings of the 1992 International Conference on Parallel Processing. 37–43.
[10]
M. Cintra and J. Torrellas. 2002. Eliminating squashes through learning cross-thread violations in speculative parallelization for multiprocessors. In Proceedings Eighth International Symposium on High Performance Computer Architecture. 43–54. 2002.995697 ISSN: 1530-0897.
[11]
Patrick Cousot, Radhia Cousot, and Laurent Mauborgne. 2011. The Reduced Product of Abstract Domains and the Combination of Decision Procedures. In Foundations of Software Science and Computational Structures (Lecture Notes in Computer Science), Martin Hofmann (Ed.). Springer, Berlin, Heidelberg, 456–472. 642-19805-2_31
[12]
David Devecsery, Peter M. Chen, Jason Flinn, and Satish Narayanasamy. 2018.
[13]
Optimistic Hybrid Analysis: Accelerating Dynamic Analysis through Predicated Static Analysis. In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’18). Association for Computing Machinery, Williamsburg, VA, USA, 348–362.
[14]
Chen Ding, Xipeng Shen, Kirk Kelsey, Chris Tice, Ruke Huang, and Chengliang Zhang. 2007. Software behavior oriented parallelization. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’07). Association for Computing Machinery, San Diego, California, USA, 223–234.
[15]
Manel Fernández and Roger Espasa. 2002. Speculative Alias Analysis for Executable Code. In Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques (PACT ’02). IEEE Computer Society, Washington, DC, USA, 222–231.
[16]
Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. 1987. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems 9, 3 (July 1987), 319–349.
[17]
Jordan Fix, Nayana P. Nagendra, Sotiris Apostolakis, Hansen Zhang, Sophie Qiu, and David I. August. 2018. Hardware Multithreaded Transactions. In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’18). Association for Computing Machinery, Williamsburg, VA, USA, 15–29.
[18]
Flang Project. 2019. Flang: a Fortran Compiler Targeting LLVM. https: //github.com/flang-compiler/flang.
[19]
Freddy Gabbay and Avi Mendelson. 1997. Can program profiling support value prediction?. In Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture (MICRO 30). IEEE Computer Society, Research Triangle Park, North Carolina, USA, 270–280.
[20]
Rakesh Ghiya and Laurie J. Hendren. 1996. Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C. In Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’96). Association for Computing Machinery, St. Petersburg Beach, Florida, USA, 1–15.
[21]
Bolei Guo, Neil Vachharajani, and David I. August. 2007. Shape analysis with inductive recursion synthesis. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’07). Association for Computing Machinery, San Diego, California, USA, 256–265.
[22]
Michael Hind. 2001. Pointer analysis: haven’t we solved this problem yet?. In Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering (PASTE ’01). Association for Computing Machinery, Snowbird, Utah, USA, 54–61.
[23]
Jialu Huang, Prakash Prabhu, Thomas B. Jablin, Soumyadeep Ghosh, Sotiris Apostolakis, Jae W. Lee, and David I. August. 2016. Speculatively Exploiting Cross-Invocation Parallelism. In Proceedings of the 2016 International Conference on Parallel Architectures and Compilation (PACT ’16). Association for Computing Machinery, Haifa, Israel, 207–221.
[24]
Nick P Johnson. 2015. Static Dependence Analysis in an Infrastructure for Automatic Parallelization. PhD Thesis. Department of Computer Science, Princeton University, Princeton, NJ, United States.
[25]
Nick P. Johnson, Jordan Fix, Stephen R. Beard, Taewook Oh, Thomas B. Jablin, and David I. August. 2017. A collaborative dependence analysis framework. In Proceedings of the 2017 International Symposium on Code Generation and Optimization (CGO ’17). IEEE Press, Austin, USA, 148–159.
[26]
Nick P. Johnson, Hanjun Kim, Prakash Prabhu, Ayal Zaks, and David I. August. 2012. Speculative separation for privatization and reductions. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’12). Association for Computing Machinery, Beijing, China, 359–370.
[27]
Nick P. Johnson, Taewook Oh, Ayal Zaks, and David I. August. 2013. Fast condensation of the program dependence graph. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’13). Association for Computing Machinery, Seattle, Washington, USA, 39–50.
[28]
[29]
Kirk Kelsey, Tongxin Bai, Chen Ding, and Chengliang Zhang. 2009. Fast Track: A Software System for Speculative Program Optimization. In Proceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO ’09). IEEE Computer Society, USA, 157–168. PLDI ’20, June 15–20, 2020, London, UK S. Apostolakis, Z. Xu, Z. Tan, G. Chan, S. Campanoni, and D. I. August
[30]
Hanjun Kim, Nick P. Johnson, Jae W. Lee, Scott A. Mahlke, and David I. August. 2012. Automatic speculative DOALL for clusters. In Proceedings of the Tenth International Symposium on Code Generation and Optimization (CGO ’12). Association for Computing Machinery, San Jose, California, 94–103.
[31]
Hanjun Kim, Arun Raman, Feng Liu, Jae W. Lee, and David I. August. 2010. Scalable Speculative Parallelization on Commodity Clusters. In Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO ’43). IEEE Computer Society, USA, 3–14.
[32]
Monica S. Lam, John Whaley, V. Benjamin Livshits, Michael C. Martin, Dzintars Avots, Michael Carbin, and Christopher Unkel. 2005.
[33]
Context-sensitive program analysis as database queries. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS ’05). Association for Computing Machinery, Baltimore, Maryland, 1–12. 1065167.1065169
[34]
William Landi. 1992. Undecidability of static analysis. ACM Letters on Programming Languages and Systems 1, 4 (Dec. 1992), 323–337.
[35]
Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization (CGO ’04). IEEE Computer Society, Palo Alto, California, 75.
[36]
Chris Lattner, Andrew Lenharth, and Vikram Adve. 2007. Making context-sensitive points-to analysis with heap cloning practical for the real world. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’07). Association for Computing Machinery, San Diego, California, USA, 278–289.
[37]
Ondrej Lhotak. 2006. Program analysis using binary decision diagrams. phd. McGill University, CAN. ISBN-13: 9780494251959.
[38]
Ondřej Lhoták and Laurie Hendren. 2008. Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation. ACM Transactions on Software Engineering and Methodology 18, 1 (Oct. 2008), 3:1–3:53.
[39]
Jin Lin, Tong Chen, Wei-Chung Hsu, Pen-Chung Yew, Roy Dz-Ching Ju, Tin-Fook Ngai, and Sun Chan. 2003. A compiler framework for speculative analysis and optimizations. In Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation (PLDI ’03). Association for Computing Machinery, San Diego, California, USA, 289–299.
[40]
LLVM Project. 2019. LLVM Alias Analysis Infrastructure. http://llvm. org/docs/AliasAnalysis.html.
[41]
Maroua Maalej and Laure Gonnord. 2015. Do we still need new Alias Analyses? report. Université Lyon Claude Bernard / Laboratoire d’Informatique du ParallÃľlisme. https://hal.inria.fr/hal-01228581
[42]
Stanislav Manilov, Christos Vasiladiotis, and Björn Franke. 2018. Generalized profile-guided iterator recognition. In Proceedings of the 27th International Conference on Compiler Construction (CC 2018). Association for Computing Machinery, Vienna, Austria, 185–195.
[43]
Mojtaba Mehrara, Jeff Hao, Po-Chun Hsu, and Scott Mahlke. 2009. Parallelizing sequential applications on commodity hardware using a lowcost software transactional memory. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’09). Association for Computing Machinery, Dublin, Ireland, 166–176.
[44]
Naveen Neelakantam, Ravi Rajwar, Suresh Srinivas, Uma Srinivasan, and Craig Zilles. 2007. Hardware atomicity for reliable software speculation. In Proceedings of the 34th annual international symposium on Computer architecture (ISCA ’07). Association for Computing Machinery, San Diego, California, USA, 174–185. 1250662.1250684
[45]
Greg Nelson and Derek C. Oppen. 1979. Simplification by Cooperating Decision Procedures. ACM Transactions on Programming Languages and Systems 1, 2 (Oct. 1979), 245–257.
[46]
[47]
Taewook Oh, Stephen R. Beard, Nick P. Johnson, Sergiy Popovych, and David I. August. 2017. A Generalized Framework for Automatic Scripting Language Parallelization. In 2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT). 356–369.
[48]
Manohar K. Prabhu and Kunle Olukotun. 2003. Using thread-level speculation to simplify manual parallelization. In Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP ’03). Association for Computing Machinery, San Diego, California, USA, 1–12.
[49]
William Pugh. 1991. The Omega test: a fast and practical integer programming algorithm for dependence analysis. In Proceedings of the 1991 ACM/IEEE conference on Supercomputing (Supercomputing ’91). Association for Computing Machinery, Albuquerque, New Mexico, USA, 4–13.
[50]
Arun Raman, Hanjun Kim, Thomas R. Mason, Thomas B. Jablin, and David I. August. 2010. Speculative parallelization using software multi-threaded transactions. In Proceedings of the fifteenth International Conference on Architectural support for programming languages and operating systems (ASPLOS XV). Association for Computing Machinery, Pittsburgh, Pennsylvania, USA, 65–76.
[51]
Lawrence Rauchwerger and David Padua. 1995. The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization. ACM SIGPLAN Notices 30, 6 (June 1995), 218–232.
[52]
Silvius Rus, Maikel Pennings, and Lawrence Rauchwerger. 2007. Sensitivity analysis for automatic parallelization on multi-cores. In Proceedings of the 21st annual international conference on Supercomputing (ICS ’07). Association for Computing Machinery, Seattle, Washington, 263–273.
[53]
Silvius Rus, Lawrence Rauchwerger, and Jay Hoeflinger. 2003. Hybrid Analysis: Static & Dynamic Memory Reference Analysis. International Journal of Parallel Programming 31, 4 (Aug. 2003), 251–283.
[54]
Mooly Sagiv, Thomas Reps, and Reinhard Wilhelm. 1996. Solving shape-analysis problems in languages with destructive updating. In Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’96). Association for Computing Machinery, St. Petersburg Beach, Florida, USA, 16–31.
[55]
spec [n.d.]. Standard Performance Evaluation Corporation. http: //www.spec.org.
[56]
Bjarne Steensgaard. 1996. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’96). Association for Computing Machinery, St. Petersburg Beach, Florida, USA, 32–41.
[57]
J.G. Steffan, C.B. Colohan, A. Zhai, and T.C. Mowry. 2002. Improving value communication for thread-level speculation. In Proceedings Eighth International Symposium on High Performance Computer Architecture. 65–75. ISSN: 1530-0897.
[58]
Chen Tian, Min Feng, and Rajiv Gupta. 2010. Speculative parallelization using state separation and multiple value prediction. In Proceedings of the 2010 international symposium on Memory management (ISMM ’10). Association for Computing Machinery, Toronto, Ontario, Canada, 63–72. SCAF: A Speculation-Aware Collaborative Dependence Analysis Framework PLDI ’20, June 15–20, 2020, London, UK
[59]
Chen Tian, Min Feng, and Rajiv Gupta. 2010. Supporting speculative parallelization in the presence of dynamic data structures. In Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’10). Association for Computing Machinery, Toronto, Ontario, Canada, 62–73. 1806596.1806604
[60]
Chen Tian, Min Feng, Vijay Nagarajan, and Rajiv Gupta. 2008. Copy or Discard execution model for speculative parallelization on multicores. In Proceedings of the 41st annual IEEE/ACM International Symposium on Microarchitecture (MICRO 41). IEEE Computer Society, USA, 330– 341.
[61]
Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni, and David I. August. 2007. Speculative Decoupled Software Pipelining. In 16th International Conference on Parallel Architecture and Compilation Techniques (PACT 2007). 49–59. ISSN: 1089-795X.
[62]
Steven Wallace, Brad Calder, and Dean M. Tullsen. 1998. Threaded multiple path execution. In ISCA ’98: Proceedings of the 25th annual international symposium on Computer architecture. IEEE Computer Society, Washington, DC, USA, 238–249.
[63]
John Whaley and Monica S. Lam. 2004. Cloning-based contextsensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation (PLDI ’04). Association for Computing Machinery, Washington DC, USA, 131–144. 1145/996841.996859
[64]
Qiang Wu, Artem Pyatakov, Alexey Spiridonov, Easwaran Raman, Douglas W. Clark, and David I. August. 2004. Exposing Memory Access Regularities Using Object-Relative Memory Profiling. In Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization (CGO ’04). IEEE Computer Society, Palo Alto, California, 315.
[65]
Hongtao Zhong, Mojtaba Mehrara, Steve Lieberman, and Scott Mahlke. 2008. Uncovering hidden loop level parallelism in sequential applications. In 2008 IEEE 14th International Symposium on High Performance Computer Architecture. 290–301.

Cited By

View all
  • (2024)PROMPT: A Fast and Extensible Memory Profiling FrameworkProceedings of the ACM on Programming Languages10.1145/36498278:OOPSLA1(449-473)Online publication date: 29-Apr-2024
  • (2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
  • (2023)SPLENDID: Supporting Parallel LLVM-IR Enhanced Natural Decompilation for Interactive DevelopmentProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582058(679-693)Online publication date: 25-Mar-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2020
1174 pages
ISBN:9781450376136
DOI:10.1145/3385412
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2020

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. collaboration
  2. dependence analysis
  3. speculation

Qualifiers

  • Research-article

Conference

PLDI '20
Sponsor:

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)43
  • Downloads (Last 6 weeks)7
Reflects downloads up to 01 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)PROMPT: A Fast and Extensible Memory Profiling FrameworkProceedings of the ACM on Programming Languages10.1145/36498278:OOPSLA1(449-473)Online publication date: 29-Apr-2024
  • (2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
  • (2023)SPLENDID: Supporting Parallel LLVM-IR Enhanced Natural Decompilation for Interactive DevelopmentProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582058(679-693)Online publication date: 25-Mar-2023
  • (2023)Program State Element CharacterizationProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580011(199-211)Online publication date: 17-Feb-2023
  • (2022)WARio: efficient code generation for intermittent computingProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523454(777-791)Online publication date: 9-Jun-2022
  • (2022)CARAT CAKE: replacing paging via compiler/kernel cooperationProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507771(98-114)Online publication date: 28-Feb-2022
  • (2022)NOELLE offers empowering LLVM extensionsProceedings of the 20th IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO53902.2022.9741276(179-192)Online publication date: 2-Apr-2022
  • (2021)Paths to OpenMP in the kernelProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3458817.3476183(1-17)Online publication date: 14-Nov-2021
  • (2020)P2GO: P4 Profile-Guided OptimizationsProceedings of the 19th ACM Workshop on Hot Topics in Networks10.1145/3422604.3425941(146-152)Online publication date: 4-Nov-2020

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media