Guy E. Blelloch
John Greiner
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.1 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.
- 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. Google Scholar
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. Google ScholarDigital 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. Google ScholarDigital Library
- 4.Guy Blelloch and Girija Narlikar. A comparison of two n-body algorithms. In Dimacs implementation challenge workshop, October 1994.Google Scholar
- 5.Guy E. Blelloch. Vector Models for Data-Parallel Computing. MIT Press, 1990. Google ScholarDigital Library
- 6.Guy E. Blelloch. NESL: A nested data-parallel language (version 3.1). Technical Report CMU-CS-95-170, Carnegie Mellon University, 1995.Google ScholarDigital Library
- 7.Guy E. Bleiloch. Programming parallel algorithms. Communications of the A CM, March 1996. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
- 11.F. Warren Burton. Storage management in virtual tree machines. IEEE Trans. on Computers, 37(3):321-328, 1988. Google ScholarDigital Library
- 12.F. Warren Burton and David J. Simpson. Space efficient execution of deterministic parallel programs. Manuscript, December 1994.Google Scholar
- 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
- 19.High Performance Fortran Forum. High Performance Fortran Language Specification, May 1993.Google Scholar
- 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. Google ScholarDigital 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. Google ScholarDigital Library
- 22.Joseph J~J~. An Introduction to Parallel Algorzthms. Addison-Wesley, Reading, Mass., 1992. Google ScholarDigital 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. Google ScholarDigital Library
- 24.Yossi Matias and Uzi Vishkin. On parallel hashing and integer sorting. Journal of Algorithms, 12(4):573-606, 1991. Google ScholarDigital 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. Google ScholarDigital Library
- 26.Abhiram G. Ranade. Fluent Parallel Computation. PhD thesis, Yale University, New Haven, CT, 1989. Google ScholarDigital Library
- 27.Paul Roe. Parallel Programming using Functional Languages. PhD thesis, Department of Computing Science, University of Glasgow, February 1991.Google Scholar
- 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.Google Scholar
- 29.Mads Rosendahl. Automatic complexity analysis. In Proceedings dth International Conference on Functional Programming Languages and Computer Architecture. Springer-Verlag, September 1989. Google ScholarDigital Library
- 30.David Sands. Calculi for Time Analysis of Functional Programs. PhD thesis, University of London, Imperial College, September 1990.Google Scholar
- 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. Google ScholarDigital 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. Google ScholarDigital 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.Google ScholarCross Ref
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. ...
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingWe 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 Nlog2 N (and like all ...
Comments