arrays - 使用渲染脚本计算数组中的值总和

Question

嗨，我是新手，正在尝试使用 Renderscript 进行编码。我想知道如何使用渲染脚本对数组中的元素求和。有没有办法将输出传递回脚本以进行顺序添加？我的问题陈述是:
vector 总和

说明:计算数组中值的总和。

输入:整数数组

输出:整数

任何帮助将非常感激!

Answer 1

恐怕这比看起来要复杂一些，但是我将尽力在这里解释实现此目标的可能途径。

您所要求的是众所周知的并行约简算法，它可以根据您的情况实现数组求和，也可以是任何其他可交换+关联运算符，当对数组进行迭代应用时，这些运算符会将其“缩减”为单个数。其他示例是查找大型数组的最大值或最小值。在CUDA和OpenCL中，有一种众所周知的计算模式，能够最大程度地利用并行线程，例如，如果您搜索“CUDA reduction”，您将获得大量有关此算法的有用信息。

实现此方法的方法是一次又一次地重复将数组减半，直到最终得到单个元素。每次减少它时，每个新元素都是前两个元素的总和。这是一张更好地描述此算法的图片:

例如，从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，则可能会注意到一些奇怪的事情:

注意，RS内核中的“v_in”和“v_out”根本没有使用，因为它们仅限于读写与当前线程索引相对应的数据元素，而reduce算法则需要访问其他位置的数据元素。因此，有一个int数组指针“data”，它是从Java中以相同的名称绑定(bind)到绑定(bind)的，这就是内核直接在上面工作的。

从Java循环中多次调用内核，而不是在内核内部执行该循环。这是因为在每次迭代中，来自上一步的所有数据必须已经准备好在其预期位置，否则，“data [x + stride]”将不同步。在RS中，内核调用会锁定，这意味着在内核完成对所有数据的处理之前，不会执行任何其他操作。如果您对此熟悉，则类似于__syncthreads()在CUDA内核中执行的操作。

但是，我在上面提到这是一种低效的实现。但这应该为您指明正确的方向。为了提高效率，您可能需要将数据拆分为较小的块，以便分别计算，因为如此处所示，此算法将在每个迭代步骤中运行ints.length个线程，并在非常大的数组上运行，结果是很多步骤，每个步骤都有很多空闲线程。

此外，这假设数组的长度恰好是2的幂，因此，如果将一半减半，则将得到一个元素。对于其他大小的阵列，您可能需要对阵列进行0填充。同样，在处理非常大的阵列时，0填充将浪费大量内存。

因此，要解决这些问题，您可能需要将阵列分成多个块，每个块有64个元素。因此，如果没有确切的数组长度，则将“最后一个”块填充到64个将不需要那么多的内存。此外，您将需要更少的迭代步骤(和更少的空闲线程)来减少64个元素。当然，64是我刚刚制作的一个神奇数字。尝试使用其他2的幂来查看结果，对于其他块大小(例如16或32)，您可能会看到更好的结果。我怀疑性能与块大小的关系很大程度上取决于硬件。

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