Article

Automatic inversion generates divide-and-conquer parallel programs

Authors:

Kazutaka Morita,

Akimasa Morihata,

Kiminori Matsuzaki,

Masato TakeichiAuthors Info & Claims

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 146 - 155

https://doi.org/10.1145/1250734.1250752

Published: 10 June 2007 Publication History

Abstract

Divide-and-conquer algorithms are suitable for modern parallel machines, tending to have large amounts of inherent parallelism and working well with caches and deep memory hierarchies. Among others, list homomorphisms are a class of recursive functions on lists, which match very well with the divide-and-conquer paradigm. However, direct programming with list homomorphisms is a challenge for many programmers. In this paper, we propose and implement a novel systemthat can automatically derive cost-optimal list homomorphisms from a pair of sequential programs, based on the third homomorphism theorem. Our idea is to reduce extraction of list homomorphisms to derivation of weak right inverses. We show that a weak right inverse always exists and can be automatically generated from a wide class of sequential programs. We demonstrate our system with several nontrivial examples, including the maximum prefix sum problem, the prefix sum computation, the maximum segment sum problem, and the line-of-sight problem. The experimental results show practical efficiency of our automatic parallelization algorithm and good speedups of the generated parallel programs.

References

[1]

J. Ahn and T. Han. An analytical method for parallelization of recursive functions. Parallel Processing Letters, 10(1):87--98, 2000.

[2]

Y. Ben-Asher and G. Haber. Parallel solutions of simple indexed recurrence equations. IEEE Transactions on Parallel and Distributed Systems, 12(1):22--40, 2001.

Digital Library

[3]

J. Bentley. Algorithm design techniques. In Programming Pearls, rm Column 7, pages 69--80. Addison-Wesley, 1986.

[4]

R. S. Bird. An introduction to the theory of lists. In Logic of Programming and Calculi of Discrete Design, NATO ASI Series F 36, pages 5--42. 1987.

Digital Library

[5]

R. S. Bird. Introduction to Functional Programming using Haskell. Prentice Hall, 1998.

Digital Library

[6]

G. E. Blelloch. Scans as primitive operations. IEEE Transactions on Computers, 38(11):1526--1538, 1989.

Digital Library

[7]

G. E. Blelloch. Prefix sums and their applications. Technical Report CMU-CS--90--190, School of Computer Science, Carnegie Mellon University, 1990.

[8]

M. Cole. Algorithmic skeletons: A structured approach to the management of parallel computation. Research Monographs in Parallel and Distributed Computing, 1989.

Digital Library

[9]

M. Cole. Parallel programming with list homomorphisms. Parallel Processing Letters, 5(2):191--203, 1995.

[10]

D. C. Cooper. Theorem proving in arithmetic without multiplication. Machine Intelligence, 7:91--99, 1972.

[11]

J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In 6th Symposium on Operating System Design and Implementation (OSDI 2004), pages 137--150, 2004.

Digital Library

[12]

E. W. Dijkstra. Program inversion. In Program Construction, LNCS 69, pages 54--57. 1978.

Digital Library

[13]

D. Eppstein. A heuristic approach to program inversion. In Proceedings of the 9th International Joint Conferences on Artificial Intelligence, pages 219--221, 1985.

Digital Library

[14]

A. L. Fisher and A. M. Ghuloum. Parallelizing complex scans and reductions. In Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation (PLDI '94), pages 135--146, 1994.

Digital Library

[15]

A. Geser and S. Gorlatch. Parallelizing functional programs by generalization. In Algebraic and Logic Programming (ALP'97), LNCS 1298, pages 46--60. 1997.

Digital Library

[16]

J. Gibbons. The third homomorphism theorem. Journal of Functional Programming, 6(4):657--665, 1996.

[17]

R. Glück and M. Kawabe. A program inverter for a functional language with equality and constructors. In Programming Languages and Systems. Proceedings, LNCS 2895, pages 246--264. 2003.

[18]

R. Glück and M. Kawabe. Derivation of deterministic inverse programs based on LR parsing. In Functional and Logic Programming, 7th International Symposium (FLOPS 2004), Proceedings, LNCS 2998, pages 291--306. 2004.

[19]

S. Gorlatch. Systematic extraction and implementation of divide-and-conquer parallelism. In Programming languages: Implementation, Logics and Programs. PLILP'96, LNCS 1140, pages 274--288. 1996.

Digital Library

[20]

D. Gries. Inverting programs. In The Science of Programming, chapter 21, pages 265--274. 1981.

[21]

Z. Hu, H. Iwasaki, and M. Takeichi. Formal derivation of efficient parallel programs by construction of. list homomorphisms. ACM Transactions on Programming Languages and Systems, 19(3):444--461, 1997.

Digital Library

[22]

Z. Hu, M. Takeichi, and W. N. Chin. Parallelization in calculational forms. In 25th ACM Symposium on Principles of Programming Languages (POPL '98), pages 316--328, 1998.

Digital Library

[23]

R. E. Korf. Inversion of applicative programs. In Proceedings of the 7th International Conferences on Artificial Intelligence (IC--AI '81), pages 1007--1009, 1981.

[24]

K. Matsuzaki, K. Emoto, H. Iwasaki, and Z. Hu. A library of constructive skeletons for sequential style of parallel programming (invited paper). In 1st International Conference on Scalable Information Systems (InfoScale 2006), 2006.

Digital Library

[25]

M. Presburger. Uber die vollstandigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervorstritt. Sprawozdanie z I Kongresu Matematikow Krajow Slowcanskich Warszawa, pages 92--101, 1929.

[26]

W. Pugh. The omega test: a fast and practical integer programming algorithm for dependence analysis. In Proceedings of the 1991 ACM/IEEE conference on Supercomputing, pages 4--13, 1991.

Digital Library

[27]

F. Rabhi and S. Gorlatch. Patterns and Skeletons for Parallel and Distributed Computing. 2002.

Digital Library

[28]

R. Rugina and M. C. Rinard. Automatic parallelization of divide and conquer algorithms. In Proceedings of the 7th ACM Symposium on Principles Practice of Parallel Programming (PPoPP '99), pages 72--83, 1999.

Digital Library

[29]

I. Sasano, Z. Hu, M. Takeichi, and M. Ogawa. Make it practical: A generic linear time algorithm for solving maximum--weightsum problems. In Proceedings of the 5th ACM SIGPLAN International Conference on Functional Programming (ICFP '00), pages 137--149. 2000.

Digital Library

[30]

G. Steele. Parallel programming and parallel abstractions in fortress. In Functional and Logic Programming, 8th International Symposium (FLOPS 2006), Proceedings, LNCS 3945, page 1. 2006.

Digital Library

[31]

D. N. Xu, S. C. Khoo, and Z. Hu. PType system: A featherweight parallelizability detector. In Proceedings of 2nd Asian Symposium on Programming Languages and Systems (APLAS 2004), LNCS 3302, pages 197--212. 2004.

Cited By

Ji RZhao YPolikarpova NXiong YHu Z(2024)Superfusion: Eliminating Intermediate Data Structures via Inductive SynthesisProceedings of the ACM on Programming Languages10.1145/36564158:PLDI(939-964)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656415
Ji RZhao YXiong YWang DZhang LHu Z(2024)Decomposition-based Synthesis for Applying Divide-and-Conquer-like Algorithmic ParadigmsACM Transactions on Programming Languages and Systems10.1145/364844046:2(1-59)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3648440
Teegen FPrott KBunkenburg NHage J(2021)Haskell⁻¹: automatic function inversion in HaskellProceedings of the 14th ACM SIGPLAN International Symposium on Haskell10.1145/3471874.3472982(41-55)Online publication date: 18-Aug-2021
https://dl.acm.org/doi/10.1145/3471874.3472982
Show More Cited By

Index Terms

Automatic inversion generates divide-and-conquer parallel programs
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

Automatic inversion generates divide-and-conquer parallel programs
Proceedings of the 2007 PLDI conference

Divide-and-conquer algorithms are suitable for modern parallel machines, tending to have large amounts of inherent parallelism and working well with caches and deep memory hierarchies. Among others, list homomorphisms are a class of recursive functions ...
Divide-and-conquer parallel programming with minimally synchronous parallel ML
PPAM'07: Proceedings of the 7th international conference on Parallel processing and applied mathematics

Minimally Synchronous Parallel ML (MSPML) is a functional parallel programming language. It is based on a small number of primitives on a parallel data structure. MSPML programs are written like usual sequential ML program and use this small set of ...
Grid-enabled parallel divide-and-conquer: theory and practice
SAC '02: Proceedings of the 2002 ACM symposium on Applied computing

This paper presents a general methodology for the communication-efficient parallelization of graph algorithms using the divide-and-conquer approach. The algorithm is communication-free in the conquer stage and uses only a small amount of messages while ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2007

508 pages

ISBN:9781595936332

DOI:10.1145/1250734

General Chair:
Jeanne Ferrante
University of California, San Diego, USA
,
Program Chair:
Kathryn S. McKinley
University of Texas at Austin, USA

ACM SIGPLAN Notices Volume 42, Issue 6
Proceedings of the 2007 PLDI conference
June 2007
491 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1273442
Issue’s Table of Contents

Copyright © 2007 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: 10 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI '07

Sponsor:

PLDI '07: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 10 - 13, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
732
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ji RZhao YPolikarpova NXiong YHu Z(2024)Superfusion: Eliminating Intermediate Data Structures via Inductive SynthesisProceedings of the ACM on Programming Languages10.1145/36564158:PLDI(939-964)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656415
Ji RZhao YXiong YWang DZhang LHu Z(2024)Decomposition-based Synthesis for Applying Divide-and-Conquer-like Algorithmic ParadigmsACM Transactions on Programming Languages and Systems10.1145/364844046:2(1-59)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3648440
Teegen FPrott KBunkenburg NHage J(2021)Haskell⁻¹: automatic function inversion in HaskellProceedings of the 14th ACM SIGPLAN International Symposium on Haskell10.1145/3471874.3472982(41-55)Online publication date: 18-Aug-2021
https://dl.acm.org/doi/10.1145/3471874.3472982
Morihata ASato SFreund SYahav E(2021)Reverse engineering for reduction parallelization via semiring polynomialsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454079(820-834)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454079
MORIHATA A(2021)Lambda calculus with algebraic simplification for reduction parallelisation: Extended studyJournal of Functional Programming10.1017/S095679682100005831Online publication date: 5-Apr-2021
https://doi.org/10.1017/S0956796821000058
Morihata A(2019)Lambda calculus with algebraic simplification for reduction parallelization by equational reasoningProceedings of the ACM on Programming Languages10.1145/33416443:ICFP(1-25)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341644
Farzan ANicolet VMcKinley KFisher K(2019)Modular divide-and-conquer parallelization of nested loopsProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314612(610-624)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314612
Jiang PChen LAgrawal GEvripidou SStenström PO'Boyle M(2018)Revealing parallel scans and reductions in recurrences through function reconstructionProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243204(1-13)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243204
(2018)Automatically deriving cost models for structured parallel processes using hylomorphismsFuture Generation Computer Systems10.1016/j.future.2017.04.03579:P2(653-668)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.future.2017.04.035
Suriana PAdams AKamil SReddi VSmith ATang L(2017)Parallel associative reductions in halideProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049863(281-291)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049863
Show More Cited By

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 Table of Contents