如何构建这个OpenCL暴力破解代码

Question

我刚开始接触OpenCL，遇到了一些问题，不知道怎么把程序结构设计得更高效一些（主要是想避免频繁地把数据传输到GPU或者其他处理地方）。

我想做的是，给定：

v = r*i + b*j + g*k

..我知道不同的r、g和b值对应的v，但是i、j和k的值我还不知道。我想通过穷举法来计算出合理的i/j/k值。

换句话说，我有一堆“原始”的RGB像素值，还有这些颜色的去饱和版本。我不知道用来计算去饱和值的权重（i/j/k）。

我最初的计划是：

1. 把数据加载到CL缓冲区中（也就是输入的r/g/b值和输出值）。

2. 有一个内核函数，它接收三个可能的矩阵值和各种像素数据缓冲区。

   然后它执行v = r*i + b*j + g*k，并把计算出的v值与已知值相减，结果存储在一个“分数”缓冲区中。

3. 另一个内核计算这个值的均方根误差（如果所有输入值的差异为零，那么i/j/k的值就是“正确”的）。

我已经实现了这个功能（使用Python和PyCL编写，代码在这里），但我在想怎么能让这部分工作并行化更多一些（一次尝试多个i/j/k值）。

一个问题是，我有4个只读缓冲区（3个用于输入值，1个用于期望值），但我需要为每种i/j/k组合准备一个单独的“分数”缓冲区。

另一个问题是均方根计算是最慢的部分，因为它实际上是单线程的（要把“分数”中的所有值加起来，然后开平方）。

基本上，我在想有没有合理的方法来构建这样的程序。

这似乎是一个非常适合OpenCL的任务——希望我描述的目标没有太复杂！如前所述，我当前的代码在这里，为了更清楚，这就是我想做的Python版本：

import sys
import math
import random


def make_test_data(w = 128, h = 128):
    in_r, in_g, in_b = [], [], []

    print "Make raw data"
    for x in range(w):
        for y in range(h):
            in_r.append(random.random())
            in_g.append(random.random())
            in_b.append(random.random())

    # the unknown values
    mtx = [random.random(), random.random(), random.random()]

    print "Secret numbers were: %s" % mtx

    out_r = [(r*mtx[0] + g*mtx[1] + b*mtx[2]) for (r, g, b) in zip(in_r, in_g, in_b)]

    return {'in_r': in_r, 'in_g': in_g, 'in_b': in_b,
            'expected_r': out_r}


def score_matrix(ir, ig, ib, expected_r, mtx):
    ms = 0
    for i in range(len(ir)):
        val = ir[i] * mtx[0] + ig[i] * mtx[1] + ib[i] * mtx[2]
        ms += abs(val - expected_r[i]) ** 2
    rms = math.sqrt(ms / float(len(ir)))
    return rms


# Make random test data
test_data = make_test_data(16, 16)


lowest_rms = sys.maxint
closest = []

divisions = 10
for possible_r in range(divisions):
    for possible_g in range(divisions):
        for possible_b in range(divisions):

            pr, pg, pb = [x / float(divisions-1) for x in (possible_r, possible_g, possible_b)]

            rms = score_matrix(
                test_data['in_r'], test_data['in_g'], test_data['in_b'], 
                test_data['expected_r'],
                mtx = [pr, pg, pb])

            if rms < lowest_rms:
                closest = [pr, pg, pb]
                lowest_rms = rms

print closest

Answer 1

这里有两个可能的问题：

1. 如果处理每张图片所需的工作量很小，那么启动内核的开销可能会很大。为了解决这个问题，你可以把多个 i,j,k 值的计算放在一个内核中一起处理。
2. 计算均方根误差（RMSE）时的求和过程可能会出现串行化问题。这可能是目前更大的问题。

针对第二个问题，注意到求和可以并行进行，但这并不像对每个像素单独应用一个函数那么简单。因为求和需要在相邻的元素之间传递值，而不是把所有元素都当作独立的。这种处理方式通常被称为 归约。

PyOpenCL 提供了对 常见归约操作 的高级支持。在这里你需要的是求和归约： pyopencl.array.sum(array)。

如果想更深入了解在原始 OpenCL 中是如何实现的，苹果的 OpenCL 文档中有一个关于求和的 并行归约示例。与您想做的最相关的部分是 内核代码 以及 main 和 create_reduction_pass_counts 函数，这些都是 运行归约的主机 C 程序 的一部分。

Answer 2

i、j、k 这几个集合是独立的吗？我原本以为是的。不过，有几个因素会影响你的性能：

1. 运行太多小的计算任务
2. 在 score_matrix 和 rm_to_rms 之间使用全局内存进行通信

你可以把这两个计算任务合并成一个，做以下几个改动：

1. 让一个 OpenCL 工作组处理不同的 i、j、k - 你可以在 CPU 上提前生成这些数据

2. 为了实现第一点，你需要让一个线程处理数组中的多个元素，可以这样做：

   int i = get_thread_id(0);
   float my_sum = 0;
   
   for (; i < array_size; i += get_local_size(0)){
       float val = in_r[i] * mtx_r + in_g[i] * mtx_g + in_b[i] * mtx_b;
       my_sum += pow(fabs(expect_r[i] - val), 2);
   }
   

3. 接下来，你需要把每个线程的 my_sum 写入本地内存，然后用归约（O(log(n)) 算法）把它们加起来。

4. 最后，把结果保存到全局内存中

另外，如果你需要顺序计算 i、j、k，可以查一下 OpenCL 规范中的屏障和内存屏障函数，这样你就可以用这些函数代替运行两个计算任务。记得在第一步把所有结果加起来，写入全局内存，然后再加一次。