research-article

Parallel functional arrays

Authors:

Guy E. Blelloch,

Robert HarperAuthors Info & Claims

POPL '17: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages

Pages 706 - 718

https://doi.org/10.1145/3009837.3009869

Published: 01 January 2017 Publication History

Abstract

The goal of this paper is to develop a form of functional arrays (sequences) that are as efficient as imperative arrays, can be used in parallel, and have well defined cost-semantics. The key idea is to consider sequences with functional value semantics but non-functional cost semantics. Because the value semantics is functional, "updating" a sequence returns a new sequence. We allow operations on "older" sequences (called interior sequences) to be more expensive than operations on the "most recent" sequences (called leaf sequences).

We embed sequences in a language supporting fork-join parallelism. Due to the parallelism, operations can be interleaved non-deterministically, and, in conjunction with the different cost for interior and leaf sequences, this can lead to non-deterministic costs for a program. Consequently the costs of programs can be difficult to analyze. The main result is the derivation of a deterministic cost dynamics which makes analyzing the costs easier. The theorems are not specific to sequences and can be applied to other data types with different costs for operating on interior and leaf versions.

We present a wait-free concurrent implementation of sequences that requires constant work for accessing and updating leaf sequences, and logarithmic work for accessing and linear work for updating interior sequences. We sketch a proof of correctness for the sequence implementation. The key advantages of the present approach compared to current approaches is that our implementation requires no changes to existing programming languages, supports nested parallelism, and has well defined cost semantics. At the same time, it allows for functional implementations of algorithms such as depth-first search with the same asymptotic complexity as imperative implementations.

References

[1]

A. Aasa, S. Holmström, and C. Nilsson. An efficiency comparison of some representations of purely functional arrays. BIT, 28(3):490–503, 1988.

Digital Library

[2]

Z. M. Ariola, J. Maraist, M. Odersky, M. Felleisen, and P. Wadler. A call-byneed lambda calculus. In Proc. ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 233–246, 1995.

Digital Library

[3]

L. Birkedal, F. Sieczkowski, and J. Thamsborg. A concurrent logical relation. In Computer Science Logic (CSL’12) - 26th International Workshop/21st Annual Conference of the EACSL, CSL 2012, September 3-6, 2012, Fontainebleau, France, pages 107–121, 2012.

[4]

G. Blelloch and J. Greiner. Parallelism in sequential functional languages. In Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture, FPCA ’95, pages 226–237, 1995.

Digital Library

[5]

G. E. Blelloch and J. Greiner. A provable time and space efficient implementation of nesl. In Proceedings of the First ACM SIGPLAN International Conference on Functional Programming, ICFP ’96, 1996.

Digital Library

[6]

G. E. Blelloch and R. Harper. Cache and i/o efficent functional algorithms. In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’13, pages 39–50, 2013.

Digital Library

[7]

A. Bloss. Update analysis and the efficient implementation of functional aggregates. In Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture, FPCA ’89, pages 26–38, New York, NY, USA, 1989. ACM.

Digital Library

[8]

R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. J. ACM, 46(5):720–748, Sept. 1999.

Digital Library

[9]

R. P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201–206, Apr. 1974.

Digital Library

[10]

T.-R. Chuang. Fully persistent arrays for efficient incremental updates and voluminous reads. In Symposium Proceedings on 4th European Symposium on Programming, ESOP’92, pages 110–129, London, UK, UK, 1992. Springer-Verlag.

Digital Library

[11]

J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan. Making data structures persistent. J. Comput. Syst. Sci., 38(1), 1989.

Digital Library

[12]

J. Girard. Linear logic. Theor. Comput. Sci., 50:1–102, 1987.

Digital Library

[13]

J. Greiner and G. E. Blelloch. A provably time-efficient parallel implementation of full speculation. ACM Trans. Program. Lang. Syst., 21(2): 240–285, Mar. 1999.

Digital Library

[14]

J. C. Guzmán and P. Hudak. Single-threaded polymorphic lambda calculus. In Proc. Symposium on Logic in Computer Science (LICS), pages 333– 343, 1990.

[15]

P. R. Harper. Practical Foundations for Programming Languages. Cambridge University Press, New York, NY, USA, 2012.

Digital Library

[16]

R. Harper. Practical Foundations for Programming Languages, 2nd edition. Cambridge University Press, 2016.

[17]

M. P. Herlihy. Impossibility and universality results for wait-free synchronization. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC ’88, pages 276–290, 1988.

Digital Library

[18]

M. P. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463–492, July 1990.

Digital Library

[19]

P. Hudak. A semantic model of reference counting and its abstraction (detailed summary). In Proceedings of the 1986 ACM Conference on LISP and Functional Programming, LFP ’86, pages 351–363, New York, NY, USA, 1986. ACM.

Digital Library

[20]

P. Hudak and A. G. Bloss. The aggregate update problem in functional programming systems. In ACM Symposium on Principles of Programming Languages (POPL), pages 300–314, 1985.

Digital Library

[21]

G. F. Italiano and N. Sarnak. Fully persistent data structures for disjoint set union problems, pages 449–460. Springer Berlin Heidelberg, 1991.

[22]

C. B. Jones. Tentative steps toward a development method for interfering programs. ACM Trans. Program. Lang. Syst., 5(4):596–619, Oct. 1983.

Digital Library

[23]

E. Moggi. Computational lambda-calculus and monads. In Proc. Symposium on Logic in Computer Science (LICS), pages 14–23, 1989.

Digital Library

[24]

A. J. Turon, J. Thamsborg, A. Ahmed, L. Birkedal, and D. Dreyer. Logical relations for fine-grained concurrency. In The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’13, Rome, Italy - January 23 - 25, 2013, pages 343–356, 2013.

Digital Library

[25]

P. Wadler. Linear types can change the world! In PROGRAMMING CONCEPTS AND METHODS. North, 1990.

[26]

P. Wadler. Monads for functional programming. In Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, pages 24–52, London, UK, UK, 1995. Springer-Verlag.

Digital Library

Cited By

Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Henriksen TSerup NElsman MHenglein FOancea C(2017)Futhark: purely functional GPU-programming with nested parallelism and in-place array updatesACM SIGPLAN Notices10.1145/3140587.306235452:6(556-571)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062354
Biermann FSestoft PElsman MGrelck CKloeckner APadua DSolomonik E(2017)Quad Ropes: immutable, declarative arrays with parallelizable operationsProceedings of the 4th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/3091966.3091971(1-8)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3091966.3091971
Show More Cited By

Index Terms

Parallel functional arrays
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
2. Theory of computation
  1. Formal languages and automata theory
  2. Semantics and reasoning
    1. Program semantics

Recommendations

Parallel functional arrays
POPL '17

The goal of this paper is to develop a form of functional arrays (sequences) that are as efficient as imperative arrays, can be used in parallel, and have well defined cost-semantics. The key idea is to consider sequences with functional value ...
Formally based profiling for higher-order functional languages

We present the first source-level profiler for a compiled, nonstrict, higher-order, purely functional language capable of measuring time as well as space usage. Our profiler is implemented in a production-quality optimizing compiler for Haskell and can ...
Parallel Computation in Biological Sequence Analysis

A massive volume of biological sequence data is available in over 36 different databases worldwide, including the sequence data generated by the Human Genome project. These databases, which also contain biological and bibliographical information, are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '17: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages

January 2017

901 pages

ISBN:9781450346603

DOI:10.1145/3009837

General Chair:
Giuseppe Castagna
Paris Diderot University, France / CNRS, France
,
Program Chair:
Andrew D. Gordon
Microsoft Research, UK / University of Edinburgh, UK

ACM SIGPLAN Notices Volume 52, Issue 1
POPL '17
January 2017
901 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3093333
Editor:
Matthew Fluet
Issue’s Table of Contents

Copyright © 2017 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

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '17

Sponsor:

SIGPLAN

POPL '17: The 44th Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 15 - 21, 2017

Paris, France

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
386
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)4

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Henriksen TSerup NElsman MHenglein FOancea C(2017)Futhark: purely functional GPU-programming with nested parallelism and in-place array updatesACM SIGPLAN Notices10.1145/3140587.306235452:6(556-571)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062354
Biermann FSestoft PElsman MGrelck CKloeckner APadua DSolomonik E(2017)Quad Ropes: immutable, declarative arrays with parallelizable operationsProceedings of the 4th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/3091966.3091971(1-8)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3091966.3091971
Henriksen TSerup NElsman MHenglein FOancea CCohen AVechev M(2017)Futhark: purely functional GPU-programming with nested parallelism and in-place array updatesProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062354(556-571)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062354

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