AccelerateHS/accelerate

Performance of highly skewed multidimensional reductions

Open

#140 opened on Dec 19, 2013

View on GitHub
 (7 comments) (0 reactions) (0 assignees)Haskell (830 stars) (112 forks)batch import
good first issuehelp wantedllvm-ptx

Description

Performance of multidimensional reductions is not good when the array is highly skewed. For example, a fold where the number of columns is (innermost dimension) is very small. See also this thread:

https://groups.google.com/forum/#!topic/accelerate-haskell/KAFYUz4Sjsk

Multidimensional reduction uses one thread block per reduction; so an (Z :. m :. n) sized matrix uses m thread blocks. If n is very small, then many threads in the block sit idle. We could change this to a warp-per-reduction style, which is actually the strategy segmented fold uses. This will likely have a negative impact if m is small and n large.

It would be possible to generate both variants and choose dynamically which to execute. That implies compiling four kernels per reduction (because fusion; initial vs. recursive step).

Contributor guide

Tech stack
None
Domain
performance
Issue type
performance
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
4
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
mostly clear
Prerequisites
HaskellGPU programmingparallel reduction algorithms
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
25
Research direction
The current implementation uses one thread block per reduction, which is inefficient for skewed matrices. The issue proposes a warp per reduction strategy, similar to segmented fold, and suggests compiling both variants for dynamic selection. Investigate the kernel generation code (e.g., in the Accelerate backend) and the linked discussion for additional context. Evaluate the trade offs and potential impact on performance for different array shapes.