我正在尝试使用具有不规则内存访问的 CUDA 并行化程序。为了解释我在说什么，我附上了两个数字。在第一个图中，我绘制了在每次循环迭代期间需要访问的输出和输入数组的索引。显然我只绘制了几次迭代（总数实际上以百万为单位）。对于黑色水平线之间的循环迭代，我分配给输出数组中的相同元素。可以看出，对于输出数组中的不同元素，这种情况发生的次数是不同的。

在下一张放大了第一张的图片中，可以看出我需要为每次迭代访问输入数组的四个元素。这些可以非常接近或相距很远。我只绘制了输入数组中的元素数量为数百个的情况。这可能是数以万计。

作为并行化的第一种简单方法，我可以将输入数组中的所有元素读入共享内存。然后我可以将迭代分布在线程上。这样我只需要从全局内存中读取/写入，如果我在分配工作时小心，这些也可以合并。

现在，当输入数组不适合共享内存时，问题就来了。如您所见，对于某些迭代，我需要处理相距很远的元素。

所以，我的问题是，对于一般的大型（不能全部放入共享内存）问题，我可以应用什么样的算法或技术来提高效率？我已经阅读了一些关于不规则程序的信息，但没有找到很多直接适用于我的问题的内容。

PS我已经很好地使用了MPI。在 CUDA 上做这件事有点奇怪。