More Web Proxy on the site http://driver.im/

research-article

Open access

Reasoning about recursive tree traversals

Authors:

Xiaokang QiuAuthors Info & Claims

PPoPP '21: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Pages 47 - 61

https://doi.org/10.1145/3437801.3441617

Published: 17 February 2021 Publication History

Abstract

Traversals are commonly seen in tree data structures, and performance-enhancing transformations between tree traversals are critical for many applications. Existing approaches to reasoning about tree traversals and their transformations are ad hoc, with various limitations on the classes of traversals they can handle, the granularity of dependence analysis, and the types of possible transformations. We propose Retreet, a framework in which one can describe general recursive tree traversals, precisely represent iterations, schedules and dependences, and automatically check data-race-freeness and transformation correctness. The crux of the framework is a stack-based representation for iterations and an encoding to Monadic Second-Order (MSO) logic over trees. Experiments show that Retreet can automatically verify optimizations for complex traversals on real-world data structures, such as CSS and cycletrees, which are not possible before. Our framework is also integrated with other MSO-based analysis techniques to verify even more challenging program transformations.

References

[1]

Pierre Amiranoff, Albert Cohen, and Paul Feautrier. 2006. Beyond Iteration Vectors: Instancewise Relational Abstract Domains. In Static Analysis, Kwangkeun Yi (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 161--180.

[2]

Johan Bleuzen. 2015. cssmin. https://www.npmjs.com/package/cssmin

[3]

Ben Briggs. 2015. cssnano. https://cssnano.co/

[4]

Steve Clay. 2007. minify. https://github.com/mrclay/minify

[5]

Loris D'Antoni, Margus Veanes, Benjamin Livshits, and David Molnar. 2014. Fast: A Transducer-based Language for Tree Manipulation. SIGPLAN Not. 49, 6 (jun 2014), 384--394.

[6]

Roman Dvornov. 2011. csso. https://github.com/css/csso

[7]

Jacob Elgaard, Nils Klarlund, and Anders Møller. 1998. MONA 1.x: New techniques for WS1S and WS2S. In Computer Aided Verification, Alan J. Hu and Moshe Y. Vardi (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 516--520.

[8]

Rakesh Ghiya, Laurie J. Hendren, and Yingchun Zhu. 1998. Detecting Parallelism in C Programs with Recursive Darta Structures. In Proceedings of the 7th International Conference on Compiler Construction (CC '98). Springer-Verlag, London, UK, UK, 159--173. http://dl.acm.org/citation.cfm?id=647474.727598

Digital Library

[9]

Andrew Gill, John Launchbury, and Simon L. Peyton Jones. 1993. A Short Cut to Deforestation. In Proceedings of the Conference on Functional Programming Languages and Computer Architecture (Copenhagen, Denmark) (FPCA '93). ACM, New York, NY, USA, 223--232.

Digital Library

[10]

Matthew Hague, Anthony W. Lin, and Chih-Duo Hong. 2019. CSS Minification via Constraint Solving. ACM Trans. Program. Lang. Syst. 41, 2, Article 12 (June 2019), 76 pages.

Digital Library

[11]

Youngjoon Jo and Milind Kulkarni. 2011. Enhancing locality for recursive traversals of recursive structures. In Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications (Portland, Oregon, USA) (OOPSLA '11). ACM, New York, NY, USA, 463--482.

Digital Library

[12]

Youngjoon Jo and Milind Kulkarni. 2012. Automatically Enhancing Locality for Tree Traversals with Traversal Splicing. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (Tucson, Arizona, USA) (OOPSLA '12). Association for Computing Machinery, New York, NY, USA, 355--374.

Digital Library

[13]

Neil D. Jones and Steven S. Muchnick. 1982. A Flexible Approach to Interprocedural Data Flow Analysis and Programs with Recursive Data Structures. In Proceedings of the 9th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Albuquerque, New Mexico) (POPL '82). ACM, New York, NY, USA, 66--74.

Digital Library

[14]

MóNica MartíNez and Alberto Pardo. 2013. A Shortcut Fusion Approach to Accumulations. Sci. Comput. Program. 78, 8 (Aug. 2013), 1121--1136.

Digital Library

[15]

Leo A. Meyerovich and Rastislav Bodik. 2010. Fast and Parallel Web-page Layout. In Proceedings of the 19th International Conference on World Wide Web (Raleigh, North Carolina, USA) (WWW '10). Association for Computing Machinery, New York, NY, USA, 711--720.

Digital Library

[16]

Leo A. Meyerovich, Matthew E. Torok, Eric Atkinson, and Rastislav Bodik. 2013. Parallel Schedule Synthesis for Attribute Grammars. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Shenzhen, China) (PPoPP '13). ACM, New York, NY, USA, 187--196.

Digital Library

[17]

Marvin L. Minsky. 1967. Computation: Finite and Infinite Machines. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.

Digital Library

[18]

Jakub Pawlowicz. 2011. clean-css. https://github.com/jakubpawlowicz/clean-css

[19]

Dmitry Petrashko, Ondřej Lhoták, and Martin Odersky. 2017. Miniphases: Compilation Using Modular and Efficient Tree Transformations. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (Barcelona, Spain) (PLDI 2017). ACM, New York, NY, USA, 201--216.

Digital Library

[20]

Xiaokang Qiu. 2020. Streaming Transformations of Infinite Ordered-Data Words. arXiv:2001.06952 [cs.FL] https://arxiv.org/abs/2001.06952

[21]

S. Rajbhandari, J. Kim, S. Krishnamoorthy, L. Pouchet, F. Rastello, R. J. Harrison, and P. Sadayappan. 2016. A Domain-Specific Compiler for a Parallel Multiresolution Adaptive Numerical Simulation Environment. In SC '16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, Piscataway, NJ, 468--479.

[22]

Samyam Rajbhandari, Jinsung Kim, Sriram Krishnamoorthy, Louis-Noël Pouchet, Fabrice Rastello, Robert J. Harrison, and P. Sadayappan. 2016. On Fusing Recursive Traversals of K-d Trees. In Proceedings of the 25th International Conference on Compiler Construction (Barcelona, Spain) (CC 2016). Association for Computing Machinery, New York, NY, USA, 152--162.

Digital Library

[23]

Tiark Rompf, Arvind K. Sujeeth, Nada Amin, Kevin J. Brown, Vojin Jovanovic, HyoukJoong Lee, Manohar Jonnalagedda, Kunle Olukotun, and Martin Odersky. 2013. Optimizing Data Structures in High-level Programs: New Directions for Extensible Compilers Based on Staging. In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Rome, Italy) (POPL '13). ACM, New York, NY, USA, 497--510.

Digital Library

[24]

Radu Rugina and Martin Rinard. 2000. Symbolic Bounds Analysis of Pointers, Array Indices, and Accessed Memory Regions. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (Vancouver, British Columbia, Canada) (PLDI '00). ACM, New York, NY, USA, 182--195.

Digital Library

[25]

Laith Sakka. 2020. Techniques for Automatic Fusion of General Tree Traversals. Ph.D. Dissertation. Purdue University.

[26]

Laith Sakka, Kirshanthan Sundararajah, and Milind Kulkarni. 2017. TreeFuser: A Framework for Analyzing and Fusing General Recursive Tree Traversals. Proc. ACM Program. Lang. 1, OOPSLA, Article 76 (Oct. 2017), 30 pages.

Digital Library

[27]

Kirshanthan Sundararajah and Milind Kulkarni. 2019. Composable, Sound Transformations of Nested Recursion and Loops. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA) (PLDI 2019). ACM, New York, NY, USA, 902--917.

Digital Library

[28]

Margus Veanes and Jonas Barklund. 1996. Construction of Natural Cycletrees. Inf. Process. Lett. 60, 6 (1996), 313--318.

Digital Library

[29]

Margus Veanes and Jonas Barklund. 1996. Natural Cycletrees: Flexible Interconnection Graphs. J. Parallel Distrib. Comput. 33 (02 1996), 44--54.

Digital Library

[30]

Margus Veanes and Jonas Barklund. 1996. On the Number of Edges in Cycletrees. Inf. Process. Lett. 57, 4 (1996), 225--229.

Digital Library

[31]

Philip Wadler. 1990. Deforestation: transforming programs to eliminate trees. Theoretical Computer Science 73, 2 (1990), 231 -- 248.

Digital Library

[32]

Yusheng Weijiang, Shruthi Balakrishna, Jianqiao Liu, and Milind Kulkarni. 2015. Tree Dependence Analysis. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (Portland, OR, USA) (PLDI '15). ACM, New York, NY, USA, 314--325.

Digital Library

Cited By

Ji RZhao YPolikarpova NXiong YHu Z(2024)Superfusion: Eliminating Intermediate Data Structures via Inductive SynthesisProceedings of the ACM on Programming Languages10.1145/36564158:PLDI(939-964)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656415
G SM VGuruprasad N(2023)Comparative Study of Recursive and Non-Recursive Approach in TREE Traversal2023 International Conference on IoT, Communication and Automation Technology (ICICAT)10.1109/ICICAT57735.2023.10263714(1-3)Online publication date: 23-Jun-2023
https://doi.org/10.1109/ICICAT57735.2023.10263714

Index Terms

Reasoning about recursive tree traversals

Recommendations

Automatic vectorization of tree traversals
PACT '13: Proceedings of the 22nd international conference on Parallel architectures and compilation techniques

Repeated tree traversals are ubiquitous in many domains such as scientific simulation, data mining and graphics. Modern commodity processors support SIMD instructions, and using these instructions to process multiple traversals at once has the potential ...
TreeFuser: a framework for analyzing and fusing general recursive tree traversals

Series of traversals of tree structures arise in numerous contexts: abstract syntax tree traversals in compiler passes, rendering traversals of the DOM in web browsers, kd-tree traversals in computational simulation codes. In each of these settings, a ...
Automatically enhancing locality for tree traversals with traversal splicing
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

Generally applicable techniques for improving temporal locality in irregular programs, which operate over pointer-based data structures such as trees and graphs, are scarce. Focusing on a subset of irregular programs, namely, tree traversal algorithms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '21: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 2021

507 pages

ISBN:9781450382946

DOI:10.1145/3437801

General Chair:
Jaejin Lee
Seoul National University, South Korea
,
Program Chair:
Erez Petrank
Technion, Israel

Copyright © 2021 ACM.

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: 17 February 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

PPoPP '21

Sponsor:

PPoPP '21: 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 27, 2021

Virtual Event, Republic of Korea

Acceptance Rates

PPoPP '21 Paper Acceptance Rate 31 of 150 submissions, 21%;

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
674
Total Downloads

Downloads (Last 12 months)196
Downloads (Last 6 weeks)25

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ji RZhao YPolikarpova NXiong YHu Z(2024)Superfusion: Eliminating Intermediate Data Structures via Inductive SynthesisProceedings of the ACM on Programming Languages10.1145/36564158:PLDI(939-964)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656415
G SM VGuruprasad N(2023)Comparative Study of Recursive and Non-Recursive Approach in TREE Traversal2023 International Conference on IoT, Communication and Automation Technology (ICICAT)10.1109/ICICAT57735.2023.10263714(1-3)Online publication date: 23-Jun-2023
https://doi.org/10.1109/ICICAT57735.2023.10263714

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents