Data-Parallel Flattening by Expansion
summary
Claims a single higher-order Futhark function expand compiles many irregular data-parallel patterns to GPU code with work-efficiency comparable to sequential work and polylogarithmic depth. Implementation composes segmented scan and replicated iota primitives to turn variable-length inputs (lines, triangles, sparse matrices) into flat arrays; line rasterization and triangle-to-lines examples produce correct point lists and a demo scene renders at ~15 frames per second. Paper gives benchmarks and shows generated CUDA kernels perform well in practice.
AI-written summary · about
chapters (9)
- 0:00Data-parallel flattening intro
- 2:17Expand function concept
- 9:25Line drawing with expand
- 13:47Work-efficient expand
- 16:20Segmented scan for expand
- 20:46Expand in Futhark
- 23:34Irregular parallel problems
- 25:51Triangle expansion perf
- 27:37Future directions
related talks
02h 50mFunctional Array Funhouse Intensive - Part 3 of 5
18m(De/Re)-Composition of Data-Parallel Computations via Multi-Dimensional(…)
30mGenerating High Performance Code for Irregular Data Structures using Dependent Types
01h 00mThe Shape of Things to Come
58mFunctional Array Funhouse Intensive - Part 2 of 5
23mDeep Fusion for Efficient Nested Recursive Computations
01h 07mParallel-by-construction Tree Manipulation with APL (Part 2)
19mFuthark: A High-Performance Purely Functional Array Language