# Efficient CuArray shift/rotation

**URL:** <https://discourse.julialang.org/t/efficient-cuarray-shift-rotation/86845>\
**Category:** GPU\
**Created:** [September 6, 2022, 3:44pm UTC](https://discourse.julialang.org/t/efficient-cuarray-shift-rotation/86845 "2022-09-06T15:44:08Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![swibe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swibe/32/42493_2.png) [@swibe](https://discourse.julialang.org/u/swibe)\
**Post date:** [September 6, 2022, 3:44pm UTC](https://discourse.julialang.org/t/efficient-cuarray-shift-rotation/86845/1 "2022-09-06T15:44:08Z")

</div>

Hi all,

I have a workload which regularly needs to perform operations on adjacent elements in an array and accumulate the result. I would sometimes like to be able to run this parallelised across the whole GPU, sometimes have many copies, each running sequentially within a single GPU thread, and sometimes run it sequentially on the CPU.

For the parallel option, `circshift` does the job (though at the cost of copying the whole array). This copy requires a memory allocation, so doesn’t work in the sequential case.

```julia
julia> a = CuArray([1,2,3]);

julia> sum(a + circshift(a, -1))
12

```

For the sequential case, I can use array indices, but `getindex` isn’t allowed in the parallel case.

```julia
sum(a[i] + a[mod1(i+1, length(a))] for i in eachindex(a))

```

It looks like [ShiftedArrays](https://juliaarrays.github.io/ShiftedArrays.jl/latest/) would be ideal for this. It offers a lazy version of `circshift` which doesn’t need to allocate any memory. On the CPU, this is by far the quickest option I’ve found, but it’s not compatible with the GPU.

```julia
julia> sum(a + ShiftedArrays.circshift(a, -1))
ERROR: GPU compilation of kernel #broadcast_kernel#17(CUDA.CuKernelContext, CuDeviceVector{Int64, 1}, Base.Broadcast.Broadcasted{CUDA.CuArrayStyle{1}, Tuple{Base.OneTo{Int64}}, typeof(+), Tuple{Base.Broadcast.Extruded{CuDeviceVector{Int64, 1}, Tuple{Bool}, Tuple{Int64}}, Base.Broadcast.Extruded{CircShiftedVector{Int64, CuArray{Int64, 1, CUDA.Mem.DeviceBuffer}}, Tuple{Bool}, Tuple{Int64}}}}, Int64) failed
KernelError: passing and using non-bitstype argument

```

Obviously I can have multiple options and use whichever one is appropriate, but I’d like to have a single implementation if possible. Is there an obvious way to do this?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 6, 2022, 4:59pm UTC](https://discourse.julialang.org/t/efficient-cuarray-shift-rotation/86845/2 "2022-09-06T16:59:28Z")

</div>

> [@swibe](#):
>
> I have a workload which regularly needs to perform operations on adjacent elements in an array and accumulate the result. I would sometimes like to be able to run this parallelised across the whole GPU, sometimes have many copies, each running sequentially within a single GPU thread, and sometimes run it sequentially on the CPU.

The most common way to do this in parallel computing is not by shifting the array, but rather by using “ghost cells” — make redundant copies of boundary data in a communication step, after which point the operations on each “chunk” of the array can occur in parallel. See e.g. _Principles of Parallel Programming_ by Lin and Snyder, quoted here: [Seemingly unnecessary allocation within for loop - #9 by ptoche](https://discourse.julialang.org/t/seemingly-unnecessary-allocation-within-for-loop/72556/9) and the [GitHub - fverdugo/PartitionedArrays.jl: Vectors and sparse matrices partitioned into pieces for parallel distributed-memory computations.](https://github.com/fverdugo/PartitionedArrays.jl) package (though this is not GPU-based).

---

<div class="post-metadata">

**Author:** ![RainerHeintzmann](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rainerheintzmann/32/19726_2.png) [@RainerHeintzmann](https://discourse.julialang.org/u/RainerHeintzmann)\
**Post date:** [April 20, 2023, 7:55pm UTC](https://discourse.julialang.org/t/efficient-cuarray-shift-rotation/86845/3 "2023-04-20T19:55:53Z")

</div>

Please feel free to try out this fork:

> **[GitHub - RainerHeintzmann/ShiftedArrays.jl: Lazy shifted arrays for data...](https://github.com/RainerHeintzmann/ShiftedArrays.jl)**
>
> Lazy shifted arrays for data analysis in Julia. Contribute to RainerHeintzmann/ShiftedArrays.jl development by creating an account on GitHub.

It should hopefully do the trick.  
Please let me know if you find any problems.