使用renderscript计算数组中的值的总和

Question

嗨,我是一个新手,并尝试在Renderscript中编码.我想知道如何使用渲染脚本在数组中执行元素的总和.有没有办法可以将输出传递回脚本以便顺序添加？我的问题陈述是:矢量和

描述:计算数组中值的总和.

输入:整数数组

输出:整数

任何帮助将非常感激!

Answer 1

我担心这比看起来要复杂一些,但我会尽力在这里解释一下你可以采取的实现这一目标的途径.

您要求的是更好地称为并行缩减算法,它可以实现像您的情况一样的数组求和,或任何其他可交换+关联运算符,当迭代地应用于数组时,它将"减少"为单个数.其他示例是查找大型数组的最大值或最小值.在CUDA和OpenCL中,有一个众所周知的计算模式,能够最好地使用并行线程,例如,如果你谷歌"CUDA减少",你将获得大量关于此算法的有用信息.

实现它的方法是反复将数组减半,一遍又一遍,直到最后得到一个元素.每次减少它时,每个新元素都是前两个元素的总和.这是一张更好地描绘此算法的图片:

例如,您从一个16元素数组开始.您运行该算法一次,最终得到一个8元素数组 - 其中这8个元素中的每一个都是原始数组中两个数字的总和.

再次运行它,最后得到4个元素 - 其中每个元素都是上一步中两个数字的总和.等等...

你一直这样做,直到你最终得到一个数字 - 你的总和.

一个低效的执行的renderScript这将是这样:

Java的:

int[] ints; // Your data is held here.

Allocation data = Allocation.createSized(rs, Element.I32(rs), ints.length, Allocation.USAGE_SCRIPT);
data.copy1DRangeFrom(0, ints.length, ints);

ScriptC_Reduce script = new ScriptC_Reduce(rs);
script.bind_data(data);

for (int stride = ints.length / 2; stride > 0; stride /= 2) {
    script.set_stride(stride);
    script.forEach_root(input, output);
}

data.copyTo(ints);
int totalsum = ints[0];

的renderScript:

#pragma version(1)
#pragma rs java_package_name(...[your package here]...)

int stride;
int * data;

void root(const int32_t *v_in, int32_t *v_out, uint32_t x) {
    if (x < stride) data[x] += data[x + stride];
}

如果您之前使用过RS,您可能会注意到一些奇怪的事情:

1. 注意,RS内核中的"v_in"和"v_out"根本不被使用,因为它们被限制为读取和写入对应于当前线程索引的数据元素,而reduce算法需要访问其他位置的数据元素.因此,有一个int数组指针"data",它是从具有相同名称的分配中从Java绑定的,这就是内核直接处理的内容.
2. 从Java中的循环中多次调用内核,而不是在内核中执行该循环.这是因为在每次迭代时,来自previuos步骤的所有数据必须已经准备好在其预期位置,否则,"data [x + stride]"将不同步.在RS中,内核调用锁定,这意味着在内核处理完整个数据之前不执行任何其他操作.这与__syncthreads()在CUDA内核中执行的操作类似,如果您熟悉它.

但是,我在上面提到过,这是一个效率低下的实现.但它应该指向正确的方向.为了提高效率,您可能需要将数据拆分为更小的块以便单独计算,因为这里给出的算法将在每个迭代步骤中运行ints.length线程数,并且在非常大的数组上运行将导致一个很大的步骤,和AA 很多在每一步的空闲线程.

此外,这假设您的数组的长度恰好是2的幂,因此多个减半将导致恰好一个元素.对于其他大小的数组,您可能需要对数组进行0填充.再次,当处理非常大的数组时,0填充将需要大量浪费的内存.

因此,要解决这些问题,您可能希望将阵列拆分为多个块,例如每个64个元素.因此,如果您没有精确的数组长度,将"最后"块填充到64将不需要那么多内存.此外,您将需要更少的迭代步骤(以及更少的空闲线程)来减少64个元素.当然,64是我刚刚组成的神奇数字.尝试其他2的幂来查看它们的结果,你可能会看到更好的结果与其他块大小,如16或32.我怀疑性能与块大小将是非常依赖于硬件.

编辑:这假设RenderScript可以为运行它的设备使用GPU驱动程序,以便它可以实际启动大量并行线程.否则,像这样的仅CPU执行内核可能比处理数组线性更慢.