AccelerateHS/accelerate

Performance of highly skewed multidimensional reductions

Open

#140 创建于 2013年12月19日

在 GitHub 查看
 (7 评论) (0 反应) (0 负责人)Haskell (830 star) (112 fork)batch import
good first issuehelp wantedllvm-ptx

描述

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).

贡献者指南

技术栈
无
领域
performance
议题类型
performance
难度面向新贡献者的预计实现难度，1 表示很小改动，5 表示专家级工作。
4
预计时间有经验贡献者完成调查、实现、测试并准备 pull request 的粗略时间范围。
over 1 week
活动状态议题当前的可参与程度：新鲜、活跃、陈旧、阻塞或等待维护者输入。
stale
清晰度议题是否清楚说明期望改动、验收标准和下一步。
mostly clear
前置要求
HaskellGPU programmingparallel reduction algorithms
新手友好度1-100 的估计分数，表示该议题对首次贡献者的友好程度。
25
研究方向
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.
Performance of highly skewed multidimensional reductions · AccelerateHS/accelerate#140 | Good First Issue