Parallelism in sequential functional languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallelism in sequential functional languages

Full text

Pdf (1.32 MB)

Source

Functional Programming Languages and Computer Architecture archive
Proceedings of the seventh international conference on Functional programming languages and computer architecture table of contents

La Jolla, California, United States

Pages: 226 - 237

Year of Publication: 1995

ISBN:0-89791-719-7

Authors

Guy Blelloch	School of Computer Science, Carnegie Mellon University
John Greiner	School of Computer Science, Carnegie Mellon University

Sponsors

IFIP WG 2.8 : IFIP WG 2.8
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 27, Citation Count: 10

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/224164.224210 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Abramsky , R. Sykes, Secd-m: a virtual machine for applicative programming, Proc. of a conference on Functional programming languages and computer architecture, p.81-98, January 1985, Nancy, France
	2	Amir M. Ben-Amram , Zvi Galil, On pointers versus addresses, Journal of the ACM (JACM), v.39 n.3, p.617-648, July 1992 [doi>10.1145/146637.146666]
	3	Bror Bjerner , S. Holmström, A composition approach to time analysis of first order lazy functional programs, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.157-165, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99382]
	4	Guy Blelloch. An L1 User's Manual (Verszon 1.2: Draft), November 1989.
	5	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	6	Guy E. Blelloch, NESL: A Nested Data-Parallel Language (Version 2.6), Carnegie Mellon University, Pittsburgh, PA, 1993
	7	Guy Blelloch , John Greiner, A Parallel Complexity Model for Functional Languages, Carnegie Mellon University, Pittsburgh, PA, 1994
	8	A. P. Willem Böhm , Robert E. Hiromoto, The dataflow time and space complexity of FFTs, Journal of Parallel and Distributed Computing, v.18 n.3, p.301-313, July 1993 [doi>10.1006/jpdc.1993.1066]
	9	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	10	I. Checkland and C. Runciman. Perfect hash functions made parallel--lazy functional programming on a distributed multiprocessor. In T. N. Mudge, V. Milutinovic, and L. Hunter, editors, Proceedings 26th Hawaii International Conference on System Sciences, volume 2, pages 397-406, January 1993.
	11	C. D. Clack and Simon Peyton Jones. Generating parallelism from strictness analysis. Technical Report Internal Note 1679, Dept. Comp. Sci., University College London, February 1985.
	12	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	13	Vincent Dornic , Pierre Jouvelot , David K. Gifford, Polymorphic time systems for estimating program complexity, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.33-45, March 1992 [doi>10.1145/130616.130620]
	14	John T. Feo , David C. Cann , Rodney R. Oldehoeft, A report on the Sisal language project, Journal of Parallel and Distributed Computing, v.10 n.4, p.349-366, Dec. 1990 [doi>10.1016/0743-7315(90)90035-N]
	15	Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
	16	Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
	17	T. Goldberg and U. gwick. Optimal deterministic processor allocation. In Proceedings Jth A CM-SIAM Syrup. on Discrete Algorithms, January 1995.
	18	Michael T. Goodrich and S. Rao Kosaraju. Sorting on a parallel pointer machine with applications to set expression evaluation. In 30th Annual Symposium on Foundations of Computer Science, pages 190-195, November 1989.
	19	Paul Hudak , Steve Anderson, Pomset interpretations of parallel function programs, Proc. of a conference on Functional programming languages and computer architecture, p.234-256, October 1987, Portland, Oregon, United States
	20	Paul Hudak , Eric Hohr, Graphinators and the duality of SIMD and MIMD, Proceedings of the 1988 ACM conference on LISP and functional programming, p.224-234, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62714]
	21	Neil D. Jones, Constant time factors do matter, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.602-611, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167244]
	22	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	23	Richard Kennaway, A Conflict Between Call-by-Need Computation and Parallelism, Proceedings of the 4th International Workshop on Conditional and Typed Rewriting Systems, p.247-261, July 13-15, 1994
	24	Donald E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley Publishing Company, Reading, MA, 1968.
	25	P. J. Landin. The mechanical evaluation of expressions. Computer Journal, 6:308-320, 1964.
	26	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
	27	Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
	28	Rishiyur S. Nikhil. ID Version 90.0 Reference Manual. Computation Structures Group Memo 284~1, Laboratory for Computer Science, Massachusetts Institute of Technology, July 1990.
	29	Robert Paige. Real-time simulation of a set machine on a RAM. In W. Koczkodaj, editor, Proceedings In~ ternational Conference on Computing and Information, volume 2, pages 68-73, 1989.
	30	S. L. Peyton Jones, Parallel implementations of functional programming languages, The Computer Journal, v.32 n.2, p.175-186, April 1989 [doi>10.1093/comjnl/32.2.175]
	31	Gordon D. Plotkin. Call-by-name, call-by-value and the lambda calculus. Theoretical Computer Science, 1:125- 159, 1975.
	32	Abhiram Gorakhanath Ranade, Fluent parallel computation, 1989
	33	Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
	34	R. Reischuk. Probabillstic parallel ~lgorithms for sorting and selection. SIAM Journal of Computing, 14(2):396-409, 1985.
	35	Brian Reistad , David K. Gifford, Static dependent costs for estimating execution time, Proceedings of the 1994 ACM conference on LISP and functional programming, p.65-78, June 27-29, 1994, Orlando, Florida, United States
	36	Paul Roe. Calculating lenient programs' performance. In Simon L Peyton Jones, Graham Hutton, and Carsten Kehler Holst, editors, Proceedings Functional Programming, Glasgow 1990, Workshops in computing. Springer-Verlag, August 1990.
	37	Paul Roe. Parallel Programming using Functional Languages. PhD thesis, Department of Computing Science, University of Glasgow, February 1991.
	38	Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
	39	David Sands. Calculi for Tzme Analysis of Functional Programs. PhD thesis, University of London, Imperial College, September 1990.
	40	Helmut Seidl and Reinhard Wilhelm. Probabilistic load balancing for parallel graph reduction. In Proceedings TENCON '89, Jth {EEE Region 10 International Uonference, pages 879-884, November 1989.
	41	Yossi Shiloach and Uzi Vishkin. Finding the maximum, merging and sorting in a parallel computation model. Journal of Algorithms, 2(1):88-102, 1981.
	42	Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
	43	D. B. Skillicorn , W. Cai, A cost calculus for parallel functional programming, Journal of Parallel and Distributed Computing, v.28 n.1, p.65-83, July 1995 [doi>10.1006/jpdc.1995.1089]
	44	Robert E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. System $ci., 18:110-127, 1979.
	45	P. Wadler, Strictness analysis aids time analysis, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-132, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73571]
	46	Wolf Zimmermann. Automatic worst case complexity analysis of parallel programs. Technical Report TR-90- 066, International Computer Science institute, December 1990.
	47	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 10

	Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, ACM SIGPLAN Notices, v.31 n.6, p.213-225, June 15, 1996
	John Greiner , Guy E. Blelloch, A provably time-efficient parallel implementation of full speculation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.309-321, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999
	Guy E. Blelloch, Programming parallel algorithms, Communications of the ACM, v.39 n.3, p.85-97, March 1996
	John Greiner , Guy E. Blelloch, A provably time-efficient parallel implementation of full speculation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.240-285, March 1999
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States
	Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Matthew Hammer , Umut A. Acar , Mohan Rajagopalan , Anwar Ghuloum, A proposal for parallel self-adjusting computation, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.3-9, January 16-16, 2007, Nice, France
	Daniel Spoonhower , Guy E. Blelloch , Robert Harper , Phillip B. Gibbons, Space profiling for parallel functional programs, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Ruy Ley-Wild , Umut A. Acar , Matthew Fluet, A cost semantics for self-adjusting computation, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA