I am trying to parallelize a program with CUDA that has irregular memory access. To explain what I am talking about, I have attached two figures. In the first figure, I have plotted the indices of the output and input arrays that needs to be accessed during each loop iteration. Obviously I have plotted only a few iterations (the total number is actually in millions). For the loop iterations in between the black horizontal lines, I assign to the same element in the output array. It can be seen that the number of times this happens for different elements in the output array is varying.

Memory access patterns with iterations Memory access patters (zoomed)

In the next picture which is a zoom in of the first one, it can be seen that I need to access four elements of the input array for each iteration. These can be quite close together or quite far apart. I have only plotted the case when the number of elements in the input array are in the hundreds. This can be in tens of thousands.

As a first naiive approach for parallelising this, I can read all the elements in the input array into the shared memory. Then I can distribute the iterations over the threads. This way I only need to to reads/writes from the global memory and if I am careful in how I assign the work, these can be coalesced too.

Now, the problem comes when the input array don't fit into the shared memory. As you can see, for some of the iterations, I need to deal with elements quite far apart.

So, my question is this, for general, large sized (can't fit all into the shared memory) problems, what sort of algorithms or techniques can I apply to make this efficient? I have read around a bit regarding irregular programs but didn't find much that is directly applicable to my problem.

P.S. I already have this working very well with MPI. Doing this on CUDA is a bit of a curiosity thing.

  • 1
    $\begingroup$ Are your data stored with AoS or SoA ? This can have an impact. $\endgroup$ – Mauro Vanzetto Oct 26 '16 at 17:02
  • 1
    $\begingroup$ There is a good discussion of memory access patterns in the CUDA programming guide. It's worth noting that more recent CUDA versions have better caching for global memory reads, so since you don't write to it, it might not be a problem at all. Furthermore, your memory accesses actually look pretty regular: you access values that are close to the values that you accessed previously. Have you done any actual benchmarking to show there is indeed a problem, and can you post the results? $\endgroup$ – Kirill Oct 26 '16 at 17:27
  • 1
    $\begingroup$ How big is the input array, in bytes? In any case, it seems like you don't need to read the entire input array into shared memory, only small portions of it at a time, making sure that the reads are coalesced. $\endgroup$ – Kirill Oct 26 '16 at 17:36