Back to Search
Start Over
Generic functional parallel algorithms: scan and FFT
- Source :
- Proceedings of the ACM on Programming Languages. 1:1-25
- Publication Year :
- 2017
- Publisher :
- Association for Computing Machinery (ACM), 2017.
-
Abstract
- Parallel programming, whether imperative or functional, has long focused on arrays as the central data type. Meanwhile, typed functional programming has explored a variety of data types, including lists and various forms of trees. Generic functional programming decomposes these data types into a small set of fundamental building blocks: sum, product, composition, and their associated identities. Definitions over these few fundamental type constructions then automatically assemble into algorithms for an infinite variety of data types—some familiar and some new. This paper presents generic functional formulations for two important and well-known classes of parallel algorithms: parallel scan (generalized prefix sum) and fast Fourier transform (FFT). Notably, arrays play no role in these formulations. Consequent benefits include a simpler and more compositional style, much use of common algebraic patterns and freedom from possibility of run-time indexing errors. The functional generic style also clearly reveals deep commonality among what otherwise appear to be quite different algorithms. Instantiating the generic formulations, two well-known algorithms for each of parallel scan and FFT naturally emerge, as well as two possibly new algorithms.
- Subjects :
- 020203 distributed computing
Functional programming
Theoretical computer science
Generic programming
Fast Fourier transform
Search engine indexing
Parallel algorithm
02 engineering and technology
Data type
Product (mathematics)
0202 electrical engineering, electronic engineering, information engineering
Prefix sum
Safety, Risk, Reliability and Quality
Software
Mathematics
Subjects
Details
- ISSN :
- 24751421
- Volume :
- 1
- Database :
- OpenAIRE
- Journal :
- Proceedings of the ACM on Programming Languages
- Accession number :
- edsair.doi...........d3f7a5b101f40bfedc09d99bf5f30b9f