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