Automatically Deriving Cost Models for Structured Parallel Processes(...)
summary
Uses hylomorphisms and a dependent-type-driven rewrite to derive operational and cost semantics for algorithmic skeletons and proves both semantics sound against an existing denotational account. Automatically generates amortised cost equations from queue-based implementations, then statically selects a provably optimal parallel structure for a target architecture. Empirical results show predicted speedups closely match measurements (about 17× on ~22 cores for matrix multiply, image convolution scaling to ~56× on 64 cores) and predictions tend to slightly underestimate observed performance.
AI-written summary · about
chapters (20)
- 0:00Intro
- 1:12Motivation
- 2:20Example Skeleton: Parallel Task Farms
- 3:03Example Skeleton: Parallel Pipeline
- 4:07Example: Parallel Image Merge
- 5:58So, why types?
- 7:31Selecting an Implementation
- 9:17Introducing/Transforming Parallel Patterns
- 10:14How do we decide semantic equivalences?
- 11:16Hylomorphism Example
- 12:03Introducing Parallelism
- 13:17Base Semantics
- 14:56Deciding Semantic Equivalences
- 15:33Recursion Schemes are Hylomorphisms!
- 16:19Inferring Parallel Structures
- 17:33Example: Cost Model for Task Farms
- 18:48Predicting Parallel Execution Costs
- 20:15Alternative Parallel Structures
- 21:21Conclusions
- 23:53Bringing Functional Ideas to the Masses!
related talks
28mCost Models for Locality and Parallelism
15mCAMP: Cost-Aware Multiparty Session Protocols
23mA Haskell Auto-Parallelizer for Distributed Computing
01h 07mThe Asynchronous C++ Parallel Programming Model
28mCommunication Avoiding Algorithms for Linear Algebra and Beyond
31mSome Novel Computational Models to Think About
03h 42mFull workshop
21mEfficient Parallel Functional Programming with Effects