CUDA/C++中的正整数范围查找表

Question

我目前正在为 CUDA 应用程序优化一段代码，该应用程序具有相对较大的代码部分，必须从无符号整数范围映射到数组索引，即范围 [0..~1000]：

if n >= 0 and n < 8 then index 0

if n >= 8 and n < 10 then index 1

等等

由于编译时的空间无关紧要，我考虑创建一个从范围映射到索引的编译时数组。我考虑将下限和上限范围的位打包成一个整数（因为

n

受~1000约束）并从该值映射到数组索引，所以像：

map[(unsigned int)(0 << 16 | 7 << 16)] = 0;
map[(unsigned int)(8 << 16 | 9 << 16)] = 1;
...

然后找到索引将需要以与设置相同的方式进行查找。

这有什么意义，或者有人有更好的主意吗？

Answer 1

由于您的范围是 [0..1000]，并且

max_index

<=

max_range

（我假设，索引是有序的），那么您可以将任何索引放入 2 字节

uint16_t

.

此后，您可以创建大小为 [max_range +1] 的“反向索引”数组，其中数组中的索引 - 您的值，数组的值是您的原始索引。

对于您的示例，数组的开头是：

uint16_t rev_map[] = { 0,0,0,0,0,0,0,0, 1, 1, .... }; 

要将您的值转换为索引，您可以只使用单一检索：

uint16_t index = rev_map[value];

你的 rev_map 的大小将只有 2K，所以我认为，可以适合你的 CUDA 卡。