[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A DSL for graph parallel programming with vertex subsets

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

The vertex-centric (VC) computation model has emerged as a promising approach for easy parallel programming and massive parallel execution for big graph processing. A simple graph computation can easily be implemented in the VC model, but some algorithms cannot easily be implemented in the VC model. Examples of the latter algorithms are those that use vertex subsets or subgraphs as a manipulation unit. Such a “global view style” is natural for programmers to design graph algorithms, but the VC model requires us to redesign algorithms in the “local view style” focusing on a vertex. The gap between these styles prevents us from writing parallel programs for useful graph computations. In this paper, we propose a novel DSL for graph processing that can be used to write parallel programs for big graph processing in the “global view style”. It is compiled into the VC model so that it can enjoy massive parallelism in various parallel computing environments including commercial cloud services like Amazon EC2. We show non-trivial examples in our DSL, and our experimental results show that the compiled program achieves good scalability.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Notes

  1. The threshold \(\theta\) is a factor of 2 because an edge is counted twice in the sum of degrees \(\text{ deg }_S(i)\).

References

  1. The Apache Software Foundation. Apache giraph: the giraph website. http://giraph.apache.org/. Accessed 20 June 2018

  2. Bahmani B, Kumar R, Vassilvitskii S (2012) Densest subgraph in streaming and mapreduce. Proc VLDB Endow 5(5):454–465

    Article  Google Scholar 

  3. Emoto K, Matsuzaki K, Hu Z, Morihata A, Iwasaki H (2016) Think like a vertex, behave like a function! A functional DSL for vertex-centric big graph processing. In: Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, ICFP 2016, pp 200–213. ACM

  4. Hong S, Chafi H, Sedlar E, Olukotun K (2012) Green-Marl: a DSL for easy and efficient graph analysis. In: Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVII, pp 349–362. ACM

  5. Hong S, Salihoglu S, Widom J, Olukotun K (2014) Simplifying scalable graph processing with a domain-specific language. In: Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’14, pp 208–218. ACM

  6. Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, pp 135–146. ACM

  7. Morihata A, Emoto K, Matsuzaki K, Hu Z, Iwasaki H (2018) Optimizing declarative parallel distributed graph processing by using constraint solvers. In: Proceedings on functional and Logic Programming—14th International Symposium, FLOPS 2018, Lecture Notes in Computer Science, vol 10818. Springer, pp 166–181

  8. Quamar A, Deshpande A, Lin JJ (2016) Nscale: neighborhood-centric large-scale graph analytics in the cloud. J VLDB 25(2):125–150

    Article  Google Scholar 

  9. Salihoglu S, Widom J (2013) GPS: a graph processing system. In: Proceedings of the 25th International Conference on Scientific and Statistical Database Management, SSDBM, pp 22:1–22:12. ACM

  10. Tian Y, Balmin A, Corsten SA, Tatikonda S, McPherson J (2013) From think like a vertex to think like a graph. Proc VLDB Endow 7(3):193–204

    Article  Google Scholar 

  11. Tsourakakis C, Bonchi F, Gionis A, Gullo F, Tsiarli M (2013) Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’13, pp 104–112. ACM

  12. Tung LD, Hu Z (2015) Towards systematic parallelization of graph transformations over Pregel. In: Proceedings of the 8th International Symposium on High-level Parallel Programming and Applications, HLPP ’15

  13. Verma S, Leslie LM, Shin Y, Gupta I (2017) An experimental comparison of partitioning strategies in distributed graph processing. Proc VLDB Endow 10(5):493–504

    Article  Google Scholar 

  14. Watts DJ, Strogatz SH (1998) Collective dynamics of small-world networks. Nature 393(6684):440–442

    Article  Google Scholar 

  15. Yan D, Cheng J, Xing K, Lu Y, Ng W, Bu Y (2014) Pregel algorithms for graph connectivity problems with performance guarantees. Proc VLDB Endow 7(14):1821–1832

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by JSPS KAKENHI Grant Nos JP15K15974 and JP26280020.

Author information

Authors and Affiliations

  1. Kyushu Institute of Technology, Kitakyushu, Japan

    Kento Emoto & Fumihisa Sadahira

Authors
  1. Kento Emoto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fumihisa Sadahira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kento Emoto.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Emoto, K., Sadahira, F. A DSL for graph parallel programming with vertex subsets. J Supercomput 76, 4998–5015 (2020). https://doi.org/10.1007/s11227-019-02821-w

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-019-02821-w

Keywords

Search

Navigation