Tue 16 Jun 2015 15:15 - 15:40 at PLDI Main BLUE (Portland 254-255) - Analysis Chair(s): Yannis Smaragdakis

We develop a new framework for analyzing recursive methods that perform traversals over trees, called tree dependence analysis. This analysis translates dependence analysis techniques for regular programs to the irregular space, identifying the structure of dependences within a recursive method that traverses trees. We develop a dependence test that exploits the dependence structure of such programs, and can prove that several locality- and parallelism-enhancing transformations are legal. In addition, we extend our analysis with a novel path-dependent, conditional analysis to refine the dependence test and prove the legality of transformations for a wider range of algorithms. We then use these analyses to show that several common algorithms that manipulate trees recursively are amenable to several locality- and parallelism enhancing transformations. This work shows that classical dependence analysis techniques, which have largely been confined to nested loops over array data structures, can be extended and translated to work for complex, recursive programs that operate over pointer-based data structures.

PLDI 2015 Artifact Evaluated Badge

Tue 16 Jun
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

14:00 - 15:40: Research Papers - Analysis at PLDI Main BLUE (Portland 254-255)
Chair(s): Yannis SmaragdakisUniversity of Athens
pldi2015-papers14:00 - 14:25
Akash LalMicrosoft Research India, Shaz QadeerMicrosoft Research
Media Attached File Attached
pldi2015-papers14:25 - 14:50
Andrew JohnsonHarvard University, Lucas WayeHarvard University, Scott MooreHarvard University, Stephen ChongHarvard University
Media Attached
pldi2015-papers14:50 - 15:15
Gagandeep SinghETH Zurich, Switzerland, Markus PüschelETH Zurich, Martin VechevETH Zurich
Media Attached
pldi2015-papers15:15 - 15:40
Yusheng WeijiangPurdue University, Shruthi BalakrishnaPurdue University, Jianqiao LiuPurdue University, Milind KulkarniPurdue University
Media Attached