research-article

Declarative coordination of graph-based parallel programs

Authors:

Seth Copen GoldsteinAuthors Info & Claims

ACM SIGPLAN Notices, Volume 51, Issue 8

Article No.: 4, Pages 1 - 12

https://doi.org/10.1145/3016078.2851153

Published: 27 February 2016 Publication History

Abstract

Declarative programming has been hailed as a promising approach to parallel programming since it makes it easier to reason about programs while hiding the implementation details of parallelism from the programmer. However, its advantage is also its disadvantage as it leaves the programmer with no straightforward way to optimize programs for performance. In this paper, we introduce Coordinated Linear Meld (CLM), a concurrent forward-chaining linear logic programming language, with a declarative way to coordinate the execution of parallel programs allowing the programmer to specify arbitrary scheduling and data partitioning policies. Our approach allows the programmer to write graph-based declarative programs and then optionally to use coordination to fine-tune parallel performance. In this paper we specify the set of coordination facts, discuss their implementation in a parallel virtual machine, and show---through example---how they can be used to optimize parallel execution. We compare the performance of CLM programs against the original uncoordinated Linear Meld and several other frameworks.

Supplementary Material

ZIP File (a4-cruz.zip)

Supplemental material.

Download
73.65 KB

References

[1]

S. Ahuja, N. Carriero, and D. Gelernter. Linda and friends. Computer, pages 26--34, 1986.

Digital Library

[2]

F. ARBAB. Reo: a channel-based coordination model for component composition. Mathematical Structures in Computer Science, pages 329--366, 2004.

Digital Library

[3]

M. P. Ashley-Rollman, P. Lee, S. C. Goldstein, P. Pillai, and J. D. Campbell. A language for large ensembles of independently executing nodes. In International Conference on Logic Programming, pages 265--280, 2009.

Digital Library

[4]

M. Bauer, J. Clark, E. Schkufza, and A. Aiken. Programming the memory hierarchy revisited: Supporting irregular parallelism in sequoia. In ACM Symposium on Principles and Practice of Parallel Programming, pages 13--24, 2011.

Digital Library

[5]

M. Bauer, S. Treichler, E. Slaughter, and A. Aiken. Legion: Expressing locality and independence with logical regions. In International Conference on High Performance Computing, Networking, Storage and Analysis, page 66, 2012.

Digital Library

[6]

G. E. Blelloch. Programming parallel algorithms. Communications of the ACM, pages 85--97, 1996.

Digital Library

[7]

M. Chakravarty, G. Keller, R. Lechtchinsky, and W. Pfannenstiel. Nepal: Nested data parallelism in Haskell. In Euro-Par 2001 Parallel Processing, pages 524--534. 2001.

Digital Library

[8]

P. Charles, C. Grothoff, V. Saraswat, C. Donawa, A. Kielstra, K. Ebcioglu, C. von Praun, and V. Sarkar. X10: An object-oriented approach to non-uniform cluster computing. In ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, pages 519--538, 2005.

Digital Library

[9]

D. Clarke. Coordination: Reo, nets, and logic. In Formal Methods for Components and Objects, pages 226--256. 2008.

Digital Library

[10]

F. Cruz. Linear Logic and Coordination for Parallel Programming. PhD thesis, Carnegie Mellon University, University of Porto, 2016.

[11]

F. Cruz, R. Rocha, S. Goldstein, and F. Pfenning. A linear logic programming language for concurrent programming over graph structures. Journal of Theory and Practice of Logic Programming, Special Issue, pages 493--507, July 2014.

[12]

F. Cruz, R. Rocha, and S. C. Goldstein. Design and implementation of a multithreaded virtual machine for executing linear logic programs. In O. Danvy, editor, International Symposium on Principles and Practice of Declarative Programming, pages 43--53, September 2014.

Digital Library

[13]

J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. Communications of the ACM, pages 107--113, 2008.

Digital Library

[14]

E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, pages 269--271, 1959.

Digital Library

[15]

K. Fatahalian, D. R. Horn, T. J. Knight, L. Leem, M. Houston, J. Y. Park, M. Erez, M. Ren, A. Aiken, W. J. Dally, and P. Hanrahan. Sequoia: Programming the memory hierarchy. In ACM/IEEE Conference on Supercomputing, page 83, 2006.

Digital Library

[16]

J.-Y. Girard. Linear logic. Theoretical Computer Science, pages 1--102, 1987.

Digital Library

[17]

J. Gonzalez, Y. Low, and C. Guestrin. Residual splash for optimally parallelizing belief propagation. In Artificial Intelligence and Statistics, pages 177--184, 2009.

[18]

J. S. Hodas and D. Miller. Logic programming in a fragment of intuitionistic linear logic. Information and Computation, pages 32--42, 1994.

Digital Library

[19]

E. J. Hoffman, J. C. Loessi, and R. C. Moore. Construction for the solutions of the M Queens problem. Mathematics Magazine, pages 66--72, 1969.

[20]

M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In European Conference on Computer Systems, pages 59--72, 2007.

Digital Library

[21]

R. Jagadeesan, G. Nadathur, and V. Saraswat. Testing concurrent systems: An interpretation of intuitionistic logic. In Foundations of Software Technology and Theoretical Computer Science, pages 517--528. 2005.

Digital Library

[22]

B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, and J. M. Hellerstein. Declarative networking: Language, execution and optimization. In International Conference on Management of Data, pages 97--108, 2006.

Digital Library

[23]

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

[24]

G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In International Conference on Management of Data, pages 135--146, 2010.

Digital Library

[25]

D. Miller. An overview of linear logic programming. In Computational Logic, pages 1--5, 1985.

[26]

K. P. Murphy, Y. Weiss, and M. I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Conference on Uncertainty in Artificial Intelligence, pages 467--475, 1999.

Digital Library

[27]

D. Nguyen and K. Pingali. Synthesizing concurrent schedulers for irregular algorithms. In International Conference on Architectural Support for Programming Languages and Operating Systems, pages 333--344, 2011.

Digital Library

[28]

R. S. Nikhil. An overview of the parallel language Id (a foundation for pH, a parallel dialect of Haskell). Technical report, Digital Equipment Corporation, Cambridge Research Laboratory, 1993.

[29]

C. Olston, B. Reed, U. Srivastava, R. Kumar, and A. Tomkins. PigLatin: A not-so-foreign language for data processing. In ACM SIGMOD International Conference on Management of Data, pages 1099--1110, 2008.

Digital Library

[30]

C. Palamidessi, V. Saraswat, B. Victor, and F. Valencia. On the expressiveness of linearity vs persistence in the asychronous pi-calculus. In IEEE Computer Society, pages 59--68, 2006.

Digital Library

[31]

G. A. Papadopoulos and F. Arbab. Coordination models and languages. In Advances in Computers, pages 329--400, 1998.

[32]

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 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 12--25, 2011.

Digital Library

[33]

D. Prountzos, R. Manevich, and K. Pingali. Elixir: A system for synthesizing concurrent graph programs. In ACM International Conference on Object Oriented Programming Systems Languages and Applications, pages 375--394, 2012.

Digital Library

[34]

J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Durand, and S. Amarasinghe. Halide: A language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 519--530, 2013.

Digital Library

[35]

V. A. Saraswat, R. Jagadeesan, and V. Gupta. Default timed concurrent constraint programming. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 272--285, 1995.

Digital Library

[36]

J. Shun and G. E. Blelloch. Ligra: A lightweight graph processing framework for shared memory. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 135--146, 2013.

Digital Library

Cited By

Ciccozzi FAddazi LAsadollah SLisper BMasud AMubeen S(2022)A Comprehensive Exploration of Languages for Parallel ComputingACM Computing Surveys10.1145/348500855:2(1-39)Online publication date: 18-Jan-2022
https://dl.acm.org/doi/10.1145/3485008
Houshmand FLesani MVora K(2021)Grafs: declarative graph analyticsProceedings of the ACM on Programming Languages10.1145/34735885:ICFP(1-32)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473588
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
Show More Cited By

Index Terms

Declarative coordination of graph-based parallel programs
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
    2. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Declarative coordination of graph-based parallel programs
PPoPP '16: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Declarative programming has been hailed as a promising approach to parallel programming since it makes it easier to reason about programs while hiding the implementation details of parallelism from the programmer. However, its advantage is also its ...
Machine Independent AND and OR Parallel Execution of Logic Programs: Part II-Compiled Execution

In pt.I, we presented a binding environment for the ANDand OR parallel execution of logic programs. This environment was instrumental inrendering a compiler for the AND and OR parallel execution of logic programs machineindependent. In this paper, we ...
Compiling data-parallel programs for clusters of SMPs: Research Articles
Compilers for Parallel Computers

Clusters of shared-memory multiprocessors (SMPs) have become the most promising parallel computing platforms for scientific computing. However, SMP clusters significantly increase the complexity of user application development when using the low-level ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 51, Issue 8

PPoPP '16

August 2016

405 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/3016078

Editor:
Matthew Fluet

Issue’s Table of Contents

PPoPP '16: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
February 2016
420 pages
ISBN:9781450340922
DOI:10.1145/2851141
General Chair:
Rafael Asenjo
University of Málaga, Spain
,
Program Chair:
Tim Harris
Oracle Labs, Cambridge, UK

Copyright © 2016 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 February 2016

Published in SIGPLAN Volume 51, Issue 8

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Regional Development Fund (ERDF) through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme
National Funds through the Portuguese funding agency - Fundao para a Ciencia e a Tecnologia (FCT)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
433
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ciccozzi FAddazi LAsadollah SLisper BMasud AMubeen S(2022)A Comprehensive Exploration of Languages for Parallel ComputingACM Computing Surveys10.1145/348500855:2(1-39)Online publication date: 18-Jan-2022
https://dl.acm.org/doi/10.1145/3485008
Houshmand FLesani MVora K(2021)Grafs: declarative graph analyticsProceedings of the ACM on Programming Languages10.1145/34735885:ICFP(1-32)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473588
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
Houshmand FLesani MVora K(2021)Grafs: declarative graph analyticsProceedings of the ACM on Programming Languages10.1145/34735885:ICFP(1-32)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473588
Morihata AEmoto KMatsuzaki KHu ZIwasaki H(2018)Optimizing Declarative Parallel Distributed Graph Processing by Using Constraint SolversFunctional and Logic Programming10.1007/978-3-319-90686-7_11(166-181)Online publication date: 24-Apr-2018
https://doi.org/10.1007/978-3-319-90686-7_11

View Options

Get Access

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 Issue’s Table of Contents