# Parallel prefix sum with CUDA.jl

**URL:** <https://discourse.julialang.org/t/parallel-prefix-sum-with-cuda-jl/62316>\
**Category:** GPU\
**Created:** [June 3, 2021, 4:26am UTC](https://discourse.julialang.org/t/parallel-prefix-sum-with-cuda-jl/62316 "2021-06-03T04:26:12Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![adam246](https://avatars.discourse-cdn.com/v4/letter/a/c0e974/32.png) [@adam246](https://discourse.julialang.org/u/adam246)\
**Post date:** [June 3, 2021, 4:26am UTC](https://discourse.julialang.org/t/parallel-prefix-sum-with-cuda-jl/62316/1 "2021-06-03T04:26:12Z")

</div>

Is there a “parallel prefix sum” function implemented in CUDA.jl? If not, I’d offer to write one, but am relatively new to Julia and would need some examples/documentation on how to do that.

---

<div class="post-metadata">

**Author:** ![stillyslalom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stillyslalom/32/45687_2.png) [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)\
**Post date:** [June 3, 2021, 5:28am UTC](https://discourse.julialang.org/t/parallel-prefix-sum-with-cuda-jl/62316/2 "2021-06-03T05:28:58Z")

</div>

Take a look at `CUDA.scan!`, which is mentioned in the docs [only in passing](https://juliagpu.github.io/CUDA.jl/dev/usage/array/#Higher-order-abstractions), and is implemented [here](https://github.com/JuliaGPU/CUDA.jl/blob/800b7b89c4c19b9b98a7d150a813a0e3d0e18be5/src/accumulate.jl#L129). There are a few outstanding performance TODOs, and as it stands, its performance on my RTX 2060 GPU is roughly on par with single-threaded performance on my AMD Ryzen 2 CPU. The large number of allocations throws up a red flag, but I’m not sure where they’re coming from.

```julia
julia> cA = CUDA.rand(2^20); cB = similar(cA);

julia> @btime CUDA.@sync last(CUDA.scan!(+, $cB, $cA, dims=1))
  705.100 μs (312 allocations: 8.34 KiB)
524474.7f0

julia> @btime CUDA.@sync sum($cA);
  231.000 μs (100 allocations: 2.28 KiB)

julia> @btime sum(A) setup=(A = Array(cA))
  241.500 μs (1 allocation: 16 bytes)
524474.75f0

```

---

<div class="post-metadata">

**Author:** ![maleadt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/maleadt/32/10097_2.png) [@maleadt](https://discourse.julialang.org/u/maleadt)\
**Post date:** [June 3, 2021, 12:08pm UTC](https://discourse.julialang.org/t/parallel-prefix-sum-with-cuda-jl/62316/3 "2021-06-03T12:08:24Z")

</div>

Yeah, `scan!` hasn’t seen as much optimization as `mapreducedim!` has. That said, a 2060 isn’t that powerful, comparing a RTX 5000 with a 5950X I get 175/35/135us respectively. `scan!` also fares a little better when there’s more parallelism, e.g. reducing a 2^7x2^7^2^6 array takes 90us vs. 120us on the CPU. And 2^20 elements is only 4MB, ramping it up to 2^30/4GiB further shows that `scan!` needs some work, taking 150ms vs 135ms on the CPU (but only 15ms when using `sum`/`mapreducedim!`).