解决OpenCL的经典地图减少问题?
-
23-09-2019 - |
题
我试图与OpenCL(即AMD实现)平行一个经典的MAP-REDUCE问题(可以与MPI平行)。但是结果使我感到困扰。
让我先介绍这个问题。有两种流入系统的数据类型:功能集(每个参数为30个)和示例集(每个参数为9000多个维度)。从某种意义上说,这是一个经典的地图减少问题,我需要计算每个样本(地图)上每个功能的分数。然后,总结每个功能的总分(减少)。大约有10K功能和30K样品。
我尝试了不同的方法来解决问题。首先,我试图通过功能分解问题。问题在于分数计算由随机内存访问(选择9000多个维度中的某些和do plus/sintraction计算)。由于我无法合并内存访问,因此成本。然后,我尝试通过样本分解问题。问题在于,要总结总分,所有线程都在争夺几个分数变量。它不断覆盖分数,这是不正确的。 (我不能先进行单个分数,然后再总结,因为它需要10k * 30k * 4字节)。
我尝试的第一种方法为我提供了具有8个线程的i7 860 CPU的相同性能。但是,我认为这个问题是无法解决的:它与射线追踪问题非常相似(为此,您进行了数百万射线对数以百万计的三角形的计算)。有任何想法吗?
此外,我正在发布一些我拥有的代码:
通过功能分解(工作,但慢):
__kernel void __ccv_cl_pos_error_rate(__global unsigned int* err_rate,
__constant int* feature, __constant int* data, int num, __constant
unsigned int* w, int s, int isiz0, int isiz01, int step0, int step1)
{
int igrid = get_global_id(0);
__constant int* of = feature + igrid * 30;
unsigned int e = 0;
int k, i;
int step[] = { step0, step1 };
for (k = 0; k < num; k++)
{
__constant int* kd = data + k * isiz01;
int pmin = kd[of[0] * isiz0 + of[1] + of[2] * step[of[0]]];
int nmax = kd[of[3] * isiz0 + of[4] + of[5] * step[of[3]]];
for (i = 0; i < 5; i++)
{
if (of[i * 6] >= 0)
pmin = min(pmin, kd[of[i * 6] * isiz0 + of[i * 6 + 1] + of[i * 6 + 2] * step[of[i * 6]]]);
if (of[i * 6 + 3] >= 0)
nmax = max(nmax, kd[of[i * 6 + 3] * isiz0 + of[i * 6 + 4] + of[i * 6 + 5] * step[of[i * 6 + 3]]]);
}
if (pmin <= nmax)
e += w[s + k];
}
err_rate[igrid] += e;
}
通过样本分解,无效:
__kernel void __ccv_cl_pos_error_rate(__global unsigned int* err_rate,
__constant int* feature, __constant int* data, int num, __constant
unsigned int* w, int s, int isiz0, int isiz01, int step0, int step1,
__local int* shared)
{
int igrid = get_global_id(0);
int lsize = get_local_size(0);
int lid = get_local_id(0);
unsigned int e = 0;
int k, i;
int ws = w[s + igrid];
int step[] = { step0, step1 };
for (k = 0; k < isiz01; k += lsize)
if (k + lid < isiz01)
shared[k + lid] = data[igrid * isiz01 + k + lid];
barrier(....);
for (k = 0; k < num; k++)
{
__constant int* of = feature + k * 30;
int pmin = shared[of[0] * isiz0 + of[1] + of[2] * step[of[0]]];
int nmax = shared[of[3] * isiz0 + of[4] + of[5] * step[of[3]]];
for (i = 0; i < 5; i++)
{
if (of[i * 6] >= 0)
pmin = min(pmin, shared[of[i * 6] * isiz0 + of[i * 6 + 1] + of[i * 6 + 2] * step[of[i * 6]]]);
if (of[i * 6 + 3] >= 0)
nmax = max(nmax, shared[of[i * 6 + 3] * isiz0 + of[i * 6 + 4] + of[i * 6 + 5] * step[of[i * 6 + 3]]]);
}
if (pmin <= nmax)
err_rate[k] += ws; // here is wrong.
}
barrier(....);
}
解决方案
来自HN的Andrew Cooke。从您的第一次尝试开始,我现在可以更好地理解问题,并且看到选择样本取决于功能的选择是杀死您的东西。
是按功能完全随机选择样品的选择,还是可以利用该样品(订购特征,以便将相同样品的人一起处理在一起)?这很明显,所以我想这是不可能的。
不幸的是,我不了解您的第二次尝试。
不隶属于 StackOverflow