Dimitrios Prountzos
Keshav Pingali
ABSTRACT
We describe a system that uses automated planning to synthesize correct and efficient parallel graph programs from high-level algorithmic specifications. Automated planning allows us to use constraints to declaratively encode program transformations such as scheduling, implementation selection, and insertion of synchronization. Each plan emitted by the planner satisfies all constraints simultaneously, and corresponds to a composition of these transformations. In this way, we obtain an integrated compilation approach for a very challenging problem domain. We have used this system to synthesize parallel programs for four graph problems: triangle counting, maximal independent set computation, preflow-push maxflow, and connected components. Experiments on a variety of inputs show that the synthesized implementations perform competitively with hand-written, highly-tuned code.
- A. Aho, R. Sethi, and J. Ullman. Compilers: principles, techniques, and tools. Addison Wesley, 1986. Google Scholar
Digital Library
- G. Barthe, J. M. Crespo, S. Gulwani, C. Kunz, and M. Marron. From relational verification to SIMD loop synthesis. PPoPP ’13, 2013. Google ScholarDigital Library
- A. J. C. Bik and H. A. G. Wijshoff. Compilation techniques for sparse matrix computations. In ICS, 1993. Google ScholarDigital Library
- G. E. Blelloch, J. T. Fineman, P. B. Gibbons, and J. Shun. Internally deterministic parallel algorithms can be fast. PPoPP ’12, 2012. Google ScholarDigital Library
- S. Cherem, T. Chilimbi, and S. Gulwani. Inferring locks for atomic sections. In PLDI. ACM, 2008. ISBN 978-1-59593-860-2. Google ScholarDigital Library
- G. Cong, G. Almasi, and V. Saraswat. Fast pgas connected components algorithms. PGAS ’09. ACM, 2009. Google ScholarDigital Library
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein, editors. Introduction to Algorithms. MIT Press, 2001. Google ScholarDigital Library
- M. Eriksson and C. Kessler. Integrated code generation for loops. ACM Trans. Embed. Comput. Syst., 11S(1), June 2012. Google ScholarDigital Library
- R. E. Fikes and N. J. Nilsson. Strips: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2, 1971.Google ScholarDigital Library
- S. Gulwani, S. Jha, A. Tiwari, and R. Venkatesan. Synthesis of loopfree programs. PLDI ’11, 2011. Google ScholarDigital Library
- P. Hawkins, A. Aiken, K. Fisher, M. Rinard, and M. Sagiv. Concurrent data representation synthesis. In PLDI, 2012. Google ScholarDigital Library
- M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP. ACM, 2008. Google ScholarDigital Library
- S. Itzhaky, S. Gulwani, N. Immerman, and M. Sagiv. A simple inductive synthesis methodology and its applications. In OOPSLA, 2010. Google ScholarDigital Library
- J. F. JaJa. An introduction to parallel algorithms. Addison Wesley, 1992. Google ScholarDigital Library
- T. A. Johnson and R. Eigenmann. Context-sensitive domainindependent algorithm composition and selection. PLDI ’06, 2006. Google ScholarDigital Library
- R. Joshi, G. Nelson, and K. Randall. Denali: A goal-directed superoptimizer. In PLDI, 2002. Google ScholarDigital Library
- R. Joshi, G. Nelson, and Y. Zhou. Denali: A practical algorithm for generating optimal code. ACM Trans. Program. Lang. Syst., 28(6), 2006. Google ScholarDigital Library
- H. A. Kautz, B. Selman, et al. Planning as satisfiability. ECAI, 1992. Google ScholarDigital Library
- H. Kwak, C. Lee, H. Park, and S. Moon. What is Twitter, a social network or a news media? WWW ’10, 2010. Google ScholarDigital Library
- Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Graphlab: A new parallel framework for machine learning. In UAI, 2010.Google ScholarDigital Library
- H. Massalin. Superoptimizer: A look at the smallest program. In ASPLOS, 1987. Google ScholarCross Ref
- B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL. ACM, 2006. Google ScholarDigital Library
- L. A. Meyerovich, M. E. Torok, E. Atkinson, and R. Bodik. Parallel schedule synthesis for attribute grammars. PPoPP ’13, 2013. Google ScholarDigital Library
- D. Nguyen, A. Lenharth, and K. Pingali. A lightweight infrastructure for graph analytics. In SOSP, 2013. Google ScholarDigital Library
- K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M. A. Hassaan, R. Kaleem, T. H. Lee, A. Lenharth, R. Manevich, M. Méndez-Lojo, D. Prountzos, and X. Sui. The TAO of parallelism in algorithms. In PLDI, 2011. Google ScholarDigital Library
- D. Prountzos, R. Manevich, and K. Pingali. Elixir: A system for synthesizing concurrent graph programs. OOPSLA, 2012. Google ScholarDigital Library
- T. Rompf, A. K. Sujeeth, N. Amin, K. J. Brown, V. Jovanovic, H. Lee, M. Jonnalagedda, K. Olukotun, and M. Odersky. Optimizing data structures in high-level programs: New directions for extensible compilers based on staging. In POPL, 2013. Google ScholarDigital Library
- N. Satish, N. Sundaram, M. M. A. Patwary, J. Seo, J. Park, M. A. Hassaan, S. Sengupta, Z. Yin, and P. Dubey. Navigating the maze of graph analytics frameworks using massive graph datasets. SIGMOD, 2014. Google ScholarDigital Library
- T. Schank. Algorithmic Aspects of Triangle-Based Network Analysis. PhD thesis, Universität Karlsruhe, 2007.Google Scholar
- E. Schkufza, R. Sharma, and A. Aiken. Stochastic superoptimization. ASPLOS ’13, 2013. Google ScholarDigital Library
- Y. Shiloach and U. Vishkin. An o(log n) parallel connectivity algorithm. J. Algorithms, 3(1):57–67, 1982.Google Scholar
- J. Shun and G. E. Blelloch. Ligra: A lightweight graph processing framework for shared memory. PPoPP ’13, 2013. Google ScholarDigital Library
- A. Solar-Lezama, C. Jones, and R. Bodik. Sketching concurrent data structures. In PLDI, 2008. Google ScholarDigital Library
- R. Tate, M. Stepp, Z. Tatlock, and S. Lerner. Equality saturation: A new approach to optimization. In POPL, 2009. Google ScholarDigital Library
- M. Vechev and E. Yahav. Deriving linearizable fine-grained concurrent objects. In PLDI, 2008. Google ScholarDigital Library
- M. Vechev, E. Yahav, and G. Yorsh. Abstraction-guided synthesis of synchronization. In POPL, 2010. Google ScholarDigital Library
Index Terms
- Synthesizing parallel graph programs via automated planning
Recommendations
A shape analysis for optimizing parallel graph programs
POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesComputations on unstructured graphs are challenging to parallelize because dependences in the underlying algorithms are usually complex functions of runtime data values, thwarting static parallelization. One promising general-purpose parallelization ...
Elixir: a system for synthesizing concurrent graph programs
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applicationsAlgorithms in new application areas like machine learning and network analysis use "irregular" data structures such as graphs, trees and sets. Writing efficient parallel code in these problem domains is very challenging because it requires the ...
Synthesizing parallel graph programs via automated planning
PLDI '15We describe a system that uses automated planning to synthesize correct and efficient parallel graph programs from high-level algorithmic specifications. Automated planning allows us to use constraints to declaratively encode program transformations ...
Comments