从1D数组表示计算3D索引的有效方法

Question

我有一个3D数据,存储在一维数组中.我像这样计算1D索引:

index = i + j * WIDTH + k * WIDTH * HEIGHT

比我需要从原来的i,j,k索引回来index.显而易见的方法是这样的:

k = index / (WIDTH * HEIGHT) 
j = (index % (WIDTH * HEIGHT)) / WIDTH
i = index - j * WIDTH - k * WIDTH * HEIGHT

但我想知道,有没有更有效的方法来做到这一点？至少没有模数......

这个问题的上下文 - 我在CUDA中有一个内核,我访问数据和计算i, j, k索引(index对应于唯一的线程ID).那么也许有一些特定于CUDA的方法可以做到这一点？我想这是很常见的问题,但我找不到更好的方法来做到这一点......

谢谢你的想法!

Answer 1

尝试将您的尺寸四舍五入到下一个2的幂.然后你可以使用位移和掩码代替乘法,除法和模数.

index = i | (j | k << HEIGHT_BITS) << WIDTH_BITS;

k = index >> (WIDTH_BITS + HEIGHT_BITS);
j = (index >> WIDTH_BITS) & ((1 << HEIGHT_BITS) - 1);
i = index & ((1 << WIDTH_BITS) - 1);

Answer 2

你得到的很好; 如果你想避免使用模数(因为这在gpus上非常昂贵)你可以使用j你所做的事情i:

j = (index - (k*WIDTH*HEIGHT))/WIDTH

如果你想让逻辑更清晰一些,并且不需要原版index,你就可以做到

k = index/(WIDTH*HEIGHT); 
index -= k*WIDTH*HEIGHT; 

j = index/WIDTH; 
index -= j*WIDTH; 

i = index/1;

然后,它非常直接地扩展到任意维度.您可以尝试通过执行预先计算之类的方法来调整上述内容WIDTH*HEIGHT,但是我只需要进行优化并信任编译器为您执行此操作.

关于向上舍入到2的幂的建议是正确的,因为它会加速指数计算,但是需要相当高的成本.在这个(不太糟糕)的情况下,WIDTH=HEIGHT=100它会增加你的3d阵列的内存需求60%(WIDTH=HEIGHT=128)和GPU上的内存通常已经很紧张; 根据您的访问模式,使您的阵列具有两个大小的权限可能会引发银行冲突问题.