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

research-article

Green-Marl: a DSL for easy and efficient graph analysis

Authors:

Kunle OlukotunAuthors Info & Claims

ASPLOS XVII: Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems

Pages 349 - 362

https://doi.org/10.1145/2150976.2151013

Published: 03 March 2012 Publication History

Abstract

The increasing importance of graph-data based applications is fueling the need for highly efficient and parallel implementations of graph analysis software. In this paper we describe Green-Marl, a domain-specific language (DSL) whose high level language constructs allow developers to describe their graph analysis algorithms intuitively, but expose the data-level parallelism inherent in the algorithms. We also present our Green-Marl compiler which translates high-level algorithmic description written in Green-Marl into an efficient C++ implementation by exploiting this exposed data-level parallelism. Furthermore, our Green-Marl compiler applies a set of optimizations that take advantage of the high-level semantic knowledge encoded in the Green-Marl DSL. We demonstrate that graph analysis algorithms can be written very intuitively with Green-Marl through some examples, and our experimental results show that the compiler-generated implementation out of such descriptions performs as well as or better than highly-tuned hand-coded implementations.

References

[1]

Green-marl lanaguage specification. http://ppl.stanford.edu/main/green_marl.html.

[2]

Pagerank c+ implementation. http://code.grnet.gr/projects/pagerank.

[3]

Strongly connected component (kosaraju) java implementation. http://www.keithschwarz.com/interesting/.

[4]

V. Agarwal, F. Petrini, D. Pasetto, and D. Bader. Scalable Graph Exploration on Multicore Processors. In ACM/IEEE SC 2010.

Digital Library

[5]

M. Anderson. Better benchmarking for supercomputers. Spectrum, IEEE, 48(1), 2011.

Digital Library

[6]

D. Bader and K. Madduri. Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. In ICPP 2006. IEEE.

Digital Library

[7]

D. Bader and K. Madduri. Parallel algorithms for evaluating centrality indices in real-world networks. In IEEE ICPP 2006.

Digital Library

[8]

D. Bader and K. Madduri. Snap, small-world network analysis and partitioning: An open-source parallel graph framework for the exploration of large-scale networks. In IEEE IPDPS, 2008.

[9]

D. A. Bader and K. Madduri. Snap: small-world network analysis and partitioning. http://snap-graph.sourceforge.net.

[10]

O. Bagge, K. Kalleberg, M. Haveraaen, and E. Visser. Design of the CodeBoost transformation system for domain-specific optimisation of C+ programs. In Source Code Analysis and Manipulation, 2003. Proceedings. Third IEEE International Workshop on.

[11]

O. Beckmann, A. Houghton, M. Mellor, and P. H. Kelly. Runtime code generation in c+ as a foundation for domain-specific optimisation. In Domain-Specific Program Generation, volume 3016 of Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2004.

[12]

B. Bollobás. Modern graph theory. Springer Verlag, 1998.

[13]

U. Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25(2):163--177, 2001.

[14]

H. Chafi, A. Sujeeth, K. Brown, H. Lee, A. Atreya, and K. Olukotun. A domain-specific approach to heterogeneous parallelism. In PPoPP. ACM, 2011.

Digital Library

[15]

D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-mat: A recursive model for graph mining. In SDM, 2004.

[16]

G. Cong and D. Bader. Lock-free parallel algorithms: An experimental study. High Performance Computing-HiPC 2004, 2005.

Digital Library

[17]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT press and McGraw-Hill, 2001.

Digital Library

[18]

G. Csardi and T. Nepusz. The igraph software package for complex network research. InterJournal Complex Systems, 1695, 2006.

[19]

D. Gregor and A. Lumsdaine. The parallel bgl: A generic library for distributed graph computations. Parallel Object-Oriented Scientific Computing (POOSC), 2005.

[20]

S. Z. Guyer and C. Lin. An annotation language for optimizing software libraries. In PLAN '99: Proceedings of the 2nd conference on Domain-specific languages.

Digital Library

[21]

S. Hong, S. Kim, T. Oguntebi, and K. Olukotun. Accelerating CUDA graph algorithms at maximum warp. In PPoPP, 2011.

Digital Library

[22]

S. Hong, T. Oguntebi, and K. Olukotun. Efficient parallel graph exploration for multi-core cpu and gpu. In IEEE PACT 2011.

Digital Library

[23]

P. Hudak. Building domain-specific embedded languages. ACM Computing Surveys, 28, 1996.

Digital Library

[24]

K. Kennedy, B. Broom, A. Chauhan, R. Fowler, J. Garvin, C. Koelbel, C. McCosh, and J. Mellor-Crummey. Telescoping languages: A system for automatic generation of domain languages. Proceedings of the IEEE, 93(3), 2005.

[25]

Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. Hellerstein. Graphlab: A new parallel framework for machine learning. In Conference on Uncertainty in Artificial Intelligence, 2010.

[26]

A. Lumsdaine, D. Gregor, B. Hendrickson, J. Berry, and J. Guest Editors. Challenges in parallel graph processing. Parallel Processing Letters, 17(1):5--20, 2007.

[27]

K. Madduri, D. Bader, J. Berry, and J. Crobak. Parallel shortest path algorithms for solving large-scale instances. 9th DIMACS Implementation Challenge-Shortest Paths, 2006.

[28]

K. Madduri, D. Ediger, K. Jiang, D. Bader, and D. Chavarria-Miranda. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets. In IEEE IPDPS 2009.

Digital Library

[29]

G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD '10. ACM.

Digital Library

[30]

NVIDIA. CUDA. http://developer.nvidia.com/object/cuda.html.

[31]

OpenMP ARB. Openmp. http://www.openmp.org.

[32]

L. Page. Method for node ranking in a linked database, Sept. 4 2001. US Patent 6,285,999.

[33]

J. Siek, L. Lee, A. Lumsdaine, L. Lee, L. Blackford, J. Demmel, J. Dongarra, I. Duff, S. Hammarling, M. Heroux, et al. The boost graph library: user guide and reference manual. 2002.

Digital Library

[34]

L. G. Valiant. A bridging model for parallel computation. Commun. ACM, 33, August 1990.

Digital Library

[35]

T. L. Veldhuizen. Expression templates, C+ gems. SIGS Publications, Inc., New York, NY, 1996.

Digital Library

[36]

T. L. Veldhuizen. Arrays in blitz+. In ISCOPE, pages 223--230, 1998.

Digital Library

[37]

T. L. Veldhuizen. Active Libraries and Universal Languages. PhD thesis, Indiana University Computer Science, May 2004.

Digital Library

[38]

A. Yoo, E. Chow, K. Henderson, W. McLendon, B. Hendrickson, and U. Catalyurek. A scalable distributed parallel breadth-first search algorithm on BlueGene/L. In SC 2005 ACM/IEEE.

Digital Library

Cited By

Behera NKumar ARajadurai T ENitish SM RNasre R(2024)StarPlat: A Versatile DSL for Graph AnalyticsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104967(104967)Online publication date: Aug-2024
https://doi.org/10.1016/j.jpdc.2024.104967
Firmli SChiadmi D(2023)A Scalable Data Structure for Efficient Graph Analytics and In-Place MutationsData10.3390/data81101668:11(166)Online publication date: 3-Nov-2023
https://doi.org/10.3390/data8110166
Lee ENoh SSeo J(2023)SageProceedings of the VLDB Endowment10.14778/3565838.356584415:13(3897-3910)Online publication date: 20-Jan-2023
https://dl.acm.org/doi/10.14778/3565838.3565844
Show More Cited By

Index Terms

Green-Marl: a DSL for easy and efficient graph analysis
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Green-Marl: a DSL for easy and efficient graph analysis
ASPLOS '12

The increasing importance of graph-data based applications is fueling the need for highly efficient and parallel implementations of graph analysis software. In this paper we describe Green-Marl, a domain-specific language (DSL) whose high level language ...
Green-Marl: a DSL for easy and efficient graph analysis
ASPLOS '12

The increasing importance of graph-data based applications is fueling the need for highly efficient and parallel implementations of graph analysis software. In this paper we describe Green-Marl, a domain-specific language (DSL) whose high level language ...
Pardis: a process calculus for parallel and distributed programming in Haskell

Parallel programming and distributed programming involve substantial amounts of boilerplate code for process management and data synchronisation. This leads to increased bug potential and often results in unintended non-deterministic program behaviour. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS XVII: Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems

March 2012

476 pages

ISBN:9781450307598

DOI:10.1145/2150976

General Chair:
Tim Harris
Microsoft Research
,
Program Chair:
Michael L. Scott
University of Rochester

ACM SIGARCH Computer Architecture News Volume 40, Issue 1
ASPLOS '12
March 2012
453 pages
ISSN:0163-5964
DOI:10.1145/2189750
Issue’s Table of Contents
ACM SIGPLAN Notices Volume 47, Issue 4
ASPLOS '12
April 2012
453 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2248487
Issue’s Table of Contents

Copyright © 2012 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: 03 March 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASPLOS'12

Sponsor:

ASPLOS'12: Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems

March 3 - 7, 2012

London, England, UK

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

242
Total Citations
View Citations
1,779
Total Downloads

Downloads (Last 12 months)92
Downloads (Last 6 weeks)10

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Behera NKumar ARajadurai T ENitish SM RNasre R(2024)StarPlat: A Versatile DSL for Graph AnalyticsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104967(104967)Online publication date: Aug-2024
https://doi.org/10.1016/j.jpdc.2024.104967
Firmli SChiadmi D(2023)A Scalable Data Structure for Efficient Graph Analytics and In-Place MutationsData10.3390/data81101668:11(166)Online publication date: 3-Nov-2023
https://doi.org/10.3390/data8110166
Lee ENoh SSeo J(2023)SageProceedings of the VLDB Endowment10.14778/3565838.356584415:13(3897-3910)Online publication date: 20-Jan-2023
https://dl.acm.org/doi/10.14778/3565838.3565844
Zhou YLeng JSong YLu SWang MLi CGuo MShen WLi YLin WLiu XWu HAamodt TJerger NSwift M(2023)uGrapher: High-Performance Graph Operator Computation via Unified Abstraction for Graph Neural NetworksProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575723(878-891)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575723
Chen YChung Y(2023)An Unequal Caching Strategy for Shared-Memory Graph AnalyticsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.321888534:3(955-967)Online publication date: 1-Mar-2023
https://doi.org/10.1109/TPDS.2022.3218885
Peng ZAshraf RGuo LTian RKestor G(2023)Automatic Code Generation for High-Performance Graph AlgorithmsProceedings of the 32nd International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT58117.2023.00010(14-26)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1109/PACT58117.2023.00010
Boukham HWachsmuth GDwars MChiadmi DFischer BBurgueño LCazzola W(2022)A Multi-target, Multi-paradigm DSL Compiler for Algorithmic Graph ProcessingProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3567512.3567513(2-15)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3567512.3567513
Kang SLee KShin K(2022)Personalized Graph Summarization: Formulation, Scalable Algorithms, and Applications2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00219(2319-2332)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00219
IWASAKI HEMOTO KMORIHATA AMATSUZAKI KHU Z(2022)Fregel: a functional domain-specific language for vertex-centric large-scale graph processingJournal of Functional Programming10.1017/S095679682100027732Online publication date: 20-Jan-2022
https://doi.org/10.1017/S0956796821000277
Eedi HKarra SPeri SRanabothu NUtkoor R(2022)An Improved/Optimized Practical Non-Blocking PageRank Algorithm for Massive Graphs*International Journal of Parallel Programming10.1007/s10766-022-00725-650:3-4(381-404)Online publication date: 26-Mar-2022
https://doi.org/10.1007/s10766-022-00725-6
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents