DOI: https://doi.org/10.26089/NumMet.v18r208

Application of the CHARM++ software model as a target platform for a domain-specific language compiler for the analysis of static graphs

Authors

  • A.S. Frolov

Keywords:

domain-specific programming languages
parallel graph processing
asynchronous computation models

Abstract

The implementation of a code generation mechanism in the domain-specific language (DSL) Green-Marl compiler targeted in the Charm++ framework is presented. Green-Marl is used for the parallel static graph analysis and adopts an imperative shared memory programming model, whereas Charm++ implements a message-driven execution model. The graph representation in the generated Charm++ code and the translation of the basic Green-Marl constructs to Charm++ are described. The evaluation of the typical graph algorithms: Single-Source Shortest Path (SSSP), Connected Components (CC), and PageRank shows that the performance of Green-Marl programs translated to Charm++ is the same as for native Charm++ implementations.

New computational technologies

Downloads

Published

2017-03-13

Issue

Vol. 18 (2017): Issue 2.

Section

Section 1. Numerical methods and applications

Author Biography

A.S. Frolov

Research Center for Electronic Computing
• Head of Department

References

  1. A. Lumsdaine, D. Gregor, B. Hendrickson, and J. Berry, “Challenges in Parallel Graph Processing,” Parallel Process. Lett. 17 (1), 5-20 (2007).
  2. L. V. Kale and S. Krishnan, “CHARM++: A Portable Concurrent Object Oriented System Based on C++,” ACM SIGPLAN Not. 28 (10), 91-108 (1993).
  3. G. Zheng, E. Meneses, A. Bhatele, and L. V. Kale, “Hierarchical Load Balancing for Charm++ Applications on Large Supercomputers,” in Proc. 39th Int. Conf. on Parallel Processing Workshops, San Diego, USA, September 13-16, 2010 (IEEE Press, Washington, DC, 2010), pp. 436-444.
  4. J. J. Willcock, T. Hoefler, N. G. Edmonds, and A. Lumsdaine, “Active Pebbles: Parallel Programming for Data-Driven Applications,” in Proc. Int. Conference on Supercomputing, Tucson, USA, May 31-June 4, 2011 (ACM Press, New York, 2011), pp. 235-244.
  5. J. J. Willcock, T. Hoefler, N. G. Edmonds, and A. Lumsdaine, “Active Pebbles: A Programming Model for Highly Parallel Fine-Grained Data-Driven Computations,” ACM SIGPLAN Not. 46 (8), 305-306 (2011).
  6. D. Callahan, B. L. Chamberlain, and H. P. Zima, “The Cascade High Productivity Language,” in Proc. 9th Int. Workshop on High-Level Parallel Programming Models and Supportive Environments, Santa Fe, USA, April 26-26, 2004 (IEEE Press, Washington, DC, 2004), pp. 52-60.
  7. B. L. Chamberlain, D. Callahan, and H. P. Zima, “Parallel Programmability and the Chapel Language,” Int. J. High Perform. Comput. Appl. 21 (3), 291-312 (2007).
  8. R. Haque and D. Richards, “Optimizing PGAS Overhead in a Multi-Locale Chapel Implementation of CoMD,” in Proc. First Workshop on PGAS Applications, Salt Lake City, USA, November 13-18, 2016 (IEEE Press, Piscataway, 2016), pp. 25-32.
  9. P. Charles, C. Grothoff, V. Saraswat, et al., “X10: An Object-Oriented Approach to Non-Uniform Cluster Computing,” ACM SIGPLAN Not. 40 (10), 519-538 (2005).
  10. O. Tardieu, B. Herta, D. Cunningham, et al., “X10 and APGAS at Petascale,” ACM Trans. Parallel Comput. 2 (4) (2016).
    doi 10.1145/2894746
  11. S. Hong, H. Chafi, E. Sedlar, and K. Olukotun, “Green-Marl: A DSL for Easy and Efficient Graph Analysis,” ACM SIGARCH Comput. Archit. News 40 (1), 349-362 (2012).
  12. S. Hong, J. Van Der Lugt, A. Welc, et al., “Early Experiences in Using a Domain-Specific Language for Large-Scale Graph Analysis,” in Proc. First Int. Workshop on Graph Data Management Experiences and Systems, New York, USA, June 23-23, 2013 (ACM Press, New York, 2013).
    doi 10.1145/2484425.2484430
  13. S. Hong, S. Salihoglu, J. Widom, and K. Olukotun, “Simplifying Scalable Graph Processing with a Domain-Specific Language,” in Proc. Annual IEEE/ACM Int. Symp. on Code Generation and Optimization, Orlando, USA, February 15-19, 2014 (ACM Press, New York, 2014).
    doi 10.1145/2544137.2544162
  14. D. Prountzos, R. Manevich, and K. Pingali, “Elixir: A System for Synthesizing Concurrent Graph Programs,” ACM SIGPLAN Not. 47 (10), 375-394 (2012).
  15. U. Cheramangalath, R. Nasre, and Y. N. Srikant, “Falcon: A Graph Manipulation Language for Heterogeneous Systems,” ACM Trans. Archit. Code Optim. 12 (4) (2016).
    doi 10.1145/2842618
  16. A. S. Frolov and A. S. Semenov, “A Survey of Object-Oriented Programming Languages for Parallel Analysis of Static Graphs,” Vychisl. Nanotekhnol. No. 1, 2017 (in press).
  17. S. Salihoglu and J. Widom, “GPS: A Graph Processing System,” in Proc. 25th Int. Conf. on Scientific and Statistical Database Management, Baltimore, USA, July 29-31, 2013 (ACM Press, New York, 2013).
    doi 10.1145/2484838.2484843
  18. S. Schelter, Large Scale Graph Processing with Apache Giraph , invited talk at GameDuell, Berlin, 29th May 2012.
  19. S. Hong, S. Depner, T. Manhardt, et al., “PGX.D: A Fast Distributed Graph Processing Engine,” in Proc. Int. Conf. for High Performance Computing, Networking, Storage and Analysis, Austin, USA, November 15-20, 2015 (ACM Press, New York, 2015).
    doi 10.1145/2807591.2807620
  20. G. Malewicz, M. H. Austern, A. J. C. Bik, et al., “Pregel: A System for Large-Scale Graph Processing,” in Proc. ACM SIGMOD Int. Conf. on Management of Data, Indianapolis, USA, June 06-10, 2010 (ACM Press, New York, 2010), pp. 135-146.
  21. T. Cheatham, A. Fahmy, D. Stefanescu, and L. Valiant, “Bulk Synchronous Parallel Computing - A Paradigm for Transportable Software,” in Tools and Environments for Parallel and Distributed Systems (Springer, New York, 1996), pp. 61-76.
  22. D. Chakrabarti, Y. Zhan, and C. Faloutsos, “R-MAT: A Recursive Model for Graph Mining,” in Proc. SIAM Int. Conf. on Data Mining, Lake Buena Vista, USA, April 22-24, 2004 (SIAM Press, Philadelphia, 2004), pp. 442-446.
  23. I. A. Zhabin, D. V. Makagon, D. A. Polyakov, et al., “First Generation of Angara High-Speed Interconnection Network,” Naukoemkie Tekhnol., No. 1, 21-27 (2014).
  24. A. A. Agarkov, T. F. Ismagilov, D. V. Makagon, et al., “Performance Evaluation of the Angara Interconnect,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 26-27, 2016 (Mosk. Gos. Univ., Moscow, 2016), pp. 626-639.
  25. L. Wesolowski, R. Venkataraman, A. Gupta, et al., “TRAM: Optimizing Fine-Grained Communication with Topological Routing and Aggregation of Messages,” in Proc. 43rd Int. Conf. on Parallel Processing, Minneapolis, USA, September 9-12, 2014 (IEEE Press, Piscataway, 2014), pp. 211-220.

License

Copyright (c) 2017 Вычислительные методы и программирование

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.