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

Article

Free access

A provable time and space efficient implementation of NESL

Authors:

Guy E. Blelloch,

John GreinerAuthors Info & Claims

ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programming

Pages 213 - 225

https://doi.org/10.1145/232627.232650

Published: 15 June 1996 Publication History

Abstract

In this paper we prove time and space bounds for the implementation of the programming language NESL on various parallel machine models. NESL is a sugared typed λ-calculus with a set of array primitives and an explicit parallel map over arrays. Our results extend previous work on provable implementation bounds for functional languages by considering space and by including arrays. For modeling the cost of NESL we augment a standard call-by-value operational semantics to return two cost measures: a DAG representing the sequential dependence in the computation, and a measure of the space taken by a sequential implementation. We show that a NESL program with w work (nodes in the DAG), d depth (levels in the DAG), and s sequential space can be implemented on a p processor butterfly network, hypercube, or CRCW PRAM using O(w/p + d log p) time and O(s + dp log p) reachable space.¹ For programs with sufficient parallelism these bounds are optimal in that they give linear speedup and use space within a constant factor of the sequential space.

References

[1]

G. Blelloch, G. L. Miller, and D. Talmor. Developing a practical projection-based parallel Delaunay algorithm. In Proceedings A CM Symposium on Computational Geometry, May 1996.

Digital Library

[2]

Guy Blelloch, Phil Gibbons, and Yossi Matias. Provably efficient scheduling for languages with fine-grained parallelism. In A CM Symposium on Parallel Algorithms and Architectures, July 1995.

Digital Library

[3]

Guy Blelloch and John Greiner. Parallelism in sequential functional languages. In Proceedings 7th International Conference on Functional Programming Languages and Computer Architecture, pages 226-237, June 1995.

Digital Library

[4]

Guy Blelloch and Girija Narlikar. A comparison of two n-body algorithms. In Dimacs implementation challenge workshop, October 1994.

[5]

Guy E. Blelloch. Vector Models for Data-Parallel Computing. MIT Press, 1990.

Digital Library

[6]

Guy E. Blelloch. NESL: A nested data-parallel language (version 3.1). Technical Report CMU-CS-95-170, Carnegie Mellon University, 1995.

Digital Library

[7]

Guy E. Bleiloch. Programming parallel algorithms. Communications of the A CM, March 1996.

Digital Library

[8]

Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, jay Sipelstein, and Marco Zagha. Implementation of a portable nested data-parallel language. Journal of Parallel and Distributed Computing, 21(1):4-14, April 1994.

Digital Library

[9]

Guy E. Blelloch and Jonathan C. Hardwick. Class notes: Programming parallel algorithms. Technical Report CMU-CS-93-115, Carnegie Mellon University, February 1993.

Digital Library

[10]

R. D. Blumofe and C. E. Leiserson. Space-efficient scheduling of multithreaded computations. In Proc. 25th A CM Symp. on Theory of Computing, pages 362- 371, May 1993.

Digital Library

[11]

F. Warren Burton. Storage management in virtual tree machines. IEEE Trans. on Computers, 37(3):321-328, 1988.

Digital Library

[12]

F. Warren Burton and David J. Simpson. Space efficient execution of deterministic parallel programs. Manuscript, December 1994.

[13]

Matthias Felleisen and Daniel P. Friedman. A calculus for assignments in higher-order languages. In Proceedings 13th A CM Symposium on Principles of Programming Languages, pages 314-325, January 1987.

Digital Library

[14]

Cormac Flanagan and Mattias Felleisen. The semantics of future and its use in program optimization. In Proceedings 22nd A CM Symposium on Principles of Programming Languages, pages 209-220, 1995.

Digital Library

[15]

Joseph Gil and Yossi Matias. Fast and efficient simulations among CRCW PRAMs. Journal of Parallel and Distributed Computing, 23(2):135-148, November 1994.

Digital Library

[16]

Allan Gottlieb, B. D. Lubachevsky, and Larry Rudolph. Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. A CM Transactions on Programming Languages and Systems, 5(2), April 1983.

Digital Library

[17]

John Greiner. A comparison of parallel algorithms for connected components. In Proceedings 6th A CM Symposium on Parallel Algorithms and Architectures, pages 16-25, June 1994.

Digital Library

[18]

John Greiner and Guy E. BlelIoch. A provably timeefficient parallel implementation of full speculation. In Proceedings 23rd A CM Symposium on Principles of Programming Languages, pages 309-321, January 1996.

Digital Library

[19]

High Performance Fortran Forum. High Performance Fortran Language Specification, May 1993.

[20]

Paul Hudak. A semantic model of reference counting and its abstraction (detailed summary). In Proceedings A CM Conference on LISP and Functional Programmmg, pages 351-363, August 1986.

Digital Library

[21]

Paul Hudak and Steve Anderson. Pomset interpretations of parallel functional programs. In Proceedings 3rd International Conference on Functional Programming Languages and Computer Architecture, number 274 in Lecture Notes in Computer Science, pages 234- 256. Springer-Verlag, September 1987.

Digital Library

[22]

Joseph J~J~. An Introduction to Parallel Algorzthms. Addison-Wesley, Reading, Mass., 1992.

Digital Library

[23]

R. M. Karp and V. Ramachandran. Parallel algorithms for shared memory machines. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science ~ Volume A: Algorithms and Complexity. MIT Press, Cambridge, Mass., 1990.

Digital Library

[24]

Yossi Matias and Uzi Vishkin. On parallel hashing and integer sorting. Journal of Algorithms, 12(4):573-606, 1991.

Digital Library

[25]

Greg Morrisett, Matthias Felleisen, and Robert Harper. Abstract models of memory management. In Proceedings of the $ymposzum on Functional Programmzng and Computer Architecture, pages 66-77, June 1995.

Digital Library

[26]

Abhiram G. Ranade. Fluent Parallel Computation. PhD thesis, Yale University, New Haven, CT, 1989.

Digital Library

[27]

Paul Roe. Parallel Programming using Functional Languages. PhD thesis, Department of Computing Science, University of Glasgow, February 1991.

[28]

J. R. Rose and G. L. Steele Jr. C*: An extended C language for data parallel programming. In Proceedings Second International Uonference on Supercomputing, Vol. 2, pages 2-16, May 1987.

[29]

Mads Rosendahl. Automatic complexity analysis. In Proceedings dth International Conference on Functional Programming Languages and Computer Architecture. Springer-Verlag, September 1989.

Digital Library

[30]

David Sands. Calculi for Time Analysis of Functional Programs. PhD thesis, University of London, Imperial College, September 1990.

[31]

David B. Skillicorn and W. Cat. A cost calculus for parallel functional programming. Journal of Parallel and Distributed Computing, 28(1):65-83, July 1995.

Digital Library

[32]

Dan Suciu and Val Tannen. Efficient compilation of high-level data parallel algorithms, in Proceedings 6th A UM Symposium on Parallel Algorithms and Architectures, pages 57-66, June 1994.

Digital Library

[33]

Wolf Zimmermann. Complexity issues in the design of functional languages with explicit parallelism. In Proceedings International Conference on Computer Languages, pages 34-43, 1992.

Cited By

Rinaldi Fwunder jAzevedo de Amorim AMuller S(2024)Pipelines and Beyond: Graph Types for ADTs with FuturesProceedings of the ACM on Programming Languages10.1145/36328598:POPL(482-511)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632859
Muller SDhulipala LSun Y(2023)Static Prediction of Parallel Computation Graphs (Abstract)Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing10.1145/3597635.3598026(21-22)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3597635.3598026
Accattoli BDal Lago UVanoni G(2022)Reasonable Space for the λ-Calculus, LogarithmicallyProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533362(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533362
Show More Cited By

Index Terms

A provable time and space efficient implementation of NESL

Recommendations

A provable time and space efficient implementation of NESL

In this paper we prove time and space bounds for the implementation of the programming language NESL on various parallel machine models. NESL is a sugared typed λ-calculus with a set of array primitives and an explicit parallel map over arrays. ...
NESL: A Nested Data-Parallel Language
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size N that have Resolution refutations of space and size each roughly N^{log₂ N} (and like all ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programming

June 1996

273 pages

ISBN:0897917707

DOI:10.1145/232627

Chairman:
Robert Harper
Carnegie Mellon Univ., Pittsburgh, PA
,
Editor:
Richard L. Wexelblat

ACM SIGPLAN Notices Volume 31, Issue 6
June 15, 1996
273 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/232629
Chairmen:
Robert Harper
Carnegie Mellon Univ., Pittsburgh, PA
,
Richard L. Wexelblat
Issue’s Table of Contents

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICFP96

Sponsor:

SIGPLAN

ICFP96: International Conference on Functional Programming

May 24 - 26, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

ICFP '96 Paper Acceptance Rate 25 of 83 submissions, 30%;

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

136
Total Citations
View Citations
601
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)11

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rinaldi Fwunder jAzevedo de Amorim AMuller S(2024)Pipelines and Beyond: Graph Types for ADTs with FuturesProceedings of the ACM on Programming Languages10.1145/36328598:POPL(482-511)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632859
Muller SDhulipala LSun Y(2023)Static Prediction of Parallel Computation Graphs (Abstract)Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing10.1145/3597635.3598026(21-22)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3597635.3598026
Accattoli BDal Lago UVanoni G(2022)Reasonable Space for the λ-Calculus, LogarithmicallyProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533362(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533362
Muller S(2022)Static prediction of parallel computation graphsProceedings of the ACM on Programming Languages10.1145/34987086:POPL(1-31)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498708
Niu YSterling JGrodin HHarper R(2022)A cost-aware logical frameworkProceedings of the ACM on Programming Languages10.1145/34986706:POPL(1-31)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498670
Hoffmann JJost S(2022)Two decades of automatic amortized resource analysisMathematical Structures in Computer Science10.1017/S096012952100048732:6(729-759)Online publication date: 16-Mar-2022
https://doi.org/10.1017/S0960129521000487
Pawlak WHlava MMetaksov MOancea CLow TGibbons J(2021)Acceleration of lattice models for pricing portfolios of fixed-income derivativesProceedings of the 7th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming10.1145/3460944.3464309(27-38)Online publication date: 17-Jun-2021
https://dl.acm.org/doi/10.1145/3460944.3464309
Ghosh SCuevas MCampanoni SDinda PCuicchi CQualters IKramer W(2020)Compiler-based timing for extremely fine-grain preemptive parallelismProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3433701.3433771(1-15)Online publication date: 9-Nov-2020
https://dl.acm.org/doi/10.5555/3433701.3433771
Ghosh SCuevas MCampanoni SDinda P(2020)Compiler-Based Timing For Extremely Fine-Grain Preemptive ParallelismSC20: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41405.2020.00057(1-15)Online publication date: Nov-2020
https://doi.org/10.1109/SC41405.2020.00057
Larkins DSnyder JDinan J(2019)Accelerated Work StealingProceedings of the 48th International Conference on Parallel Processing10.1145/3337821.3337878(1-10)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3337821.3337878
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents