JuliaGPU / JuliaGPU/AcceleratedKernels.jl
`accumulate!` with `inclusive=false` gives wrong answer
- Dominant language
- Julia
- Stars
- 204
- Forks
- 15
- Avg merge
- 10d 5h
- Merged PRs (30d)
- 6
Description
On AcceleratedKernels v0.4.3, CUDA.jl v6.4.0 and Julia 1.13.0:
```julia
import AcceleratedKernels as AK
using CUDA
# Exclusive prefix sum: out[i] = v[1] + ... + v[i-1]
exclusive_cumsum(v) = cumsum(v) .- v
# 1024 elements = 2 GPU blocks at the default block_size=256 (512 elements per block)
v = zeros(Int32, 1024)
v[512] = 1 # last element of the first block
v[600] = 1 # an element in the second block
expected = exclusive_cumsum(v)
cpu = AK.accumulate!(+, copy(v); init=Int32(0), inclusive=false)
println("CPU matches: ", cpu == expected)
for alg in (AK.ScanPrefixes(), AK.DecoupledLookback())
gpu = Array(AK.accumulate!(+, CuArray(v); init=Int32(0), inclusive=false, alg=alg))
println(nameof(typeof(alg)), " GPU matches: ", gpu == expected)
println(" index ", [511, 512, 513, 600, 601])
println(" expected ", expected[[511, 512, 513, 600, 601]])
println(" got ", gpu[[511, 512, 513, 600, 601]])
end
```
```
CPU matches: true
ScanPrefixes GPU matches: false
index [511, 512, 513, 600, 601]
expected [0, 0, 1, 1, 2]
got Int32[0, 0, 0, 1, 1]
DecoupledLookback GPU matches: false
index [511, 512, 513, 600, 601]
expected [0, 0, 1, 1, 2]
got Int32[0, 0, 0, 1, 1]
```
There appear to be two issues: the running total carried out of the first block leaves out that block's last element, and every element after the first block includes its own value. The two cancel when the input is all ones.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by running the provided Julia reproducer and trace AK.accumulate! for inclusive=false with both ScanPrefixes() and DecoupledLookback(). Compare the block-boundary carry and post-boundary values against expected; done means both GPU algorithms match the exclusive prefix-sum result while the existing CPU result remains correct.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 68/100