NDLI: Functional parallel algorithms

Content Provider	ACM Digital Library
Author	Blelloch, Guy E.
Abstract	Functional programming presents several important advantages in the design, analysis and implementation of parallel algorithms: It discourages iteration and encourages decomposition. It supports persistence and hence easy speculation. It encourages higher-order aggregate operations. It is well suited for defining cost models tied to the programming language rather than the machine. Implementations can avoid false sharing. Implementations can use cheaper weak consistency models. And most importantly, it supports safe deterministic parallelism. In fact functional programming supports a level of abstraction in which parallel algorithms are often as easy to design and analyze as sequential algorithms. The recent widespread advent of parallel machines therefore presents a great opportunity for functional programming languages. However, any changes will require significant education at all levels and involvement of the functional programming community. In this talk I will discuss an approach to designing and analyzing parallel algorithms in a strict functional and fully deterministic setting. Key ideas include a cost model defined in term of analyzing work and span, the use of divide-and-conquer and contraction, the need for arrays (immutable) to achieve asymptotic efficiency, and the power of (deterministic) randomized algorithms. These are all ideas I believe can be taught at any level.
Starting Page	247
Ending Page	247
Page Count	1
File Format	QT / MOV
ISSN	03621340 15581160
DOI	10.1145/1932681.1863579
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	45
Issue Number	9
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Functional programming Parallel algorithms
Content Type	Video
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Seq no more:better strategies for parallel Haskell

Functional programming and hardware design: still interesting after all these years

Expressing graph algorithms using generalized active messages

Using functional programming within an industrial product group:perspectives and perceptions

F#: Taking Succinct, Efficient, Typed Functional Programming into the Mainstream

Adaptive functional programming

Typed functional programming

On programming parallel computers

Lifting sequential graph algorithms for distributed-memory parallel computation

Functional parallel algorithms

Similar Documents

Seq no more:better strategies for parallel Haskell

Functional programming and hardware design: still interesting after all these years

Expressing graph algorithms using generalized active messages

Using functional programming within an industrial product group:perspectives and perceptions

F#: Taking Succinct, Efficient, Typed Functional Programming into the Mainstream

Adaptive functional programming

Typed functional programming

On programming parallel computers

Lifting sequential graph algorithms for distributed-memory parallel computation

Functional parallel algorithms