c++ - [OpenCL] 使用欧氏距离的最近邻

Question

我正在使用 OpenCL 查找两组 3D 点之间的最近邻居。

最近邻:对于数据集中的每个点 (x,y,z)，我必须在模型中找到最近的一个。平方距离 = (Ax-Bx)^2 + (Ay-By)^2 + (Az-Bz)^2

这是我到目前为止所做的:

struct point {
int x;
int y;
int z;
};

__kernel void 
nearest_neighbour(__global struct point *model,
__global struct point *dataset,
__global int *nearest,
const unsigned int model_size)
{
    int g_dataset_id = get_global_id(0);

    int dmin = -1;
    int d, dx, dy, dz;

    for (int i=0; i<model_size; ++i) {
        dx = model[i].x - dataset[g_dataset_id].x;
        dx = dx * dx;

        dy = model[i].y - dataset[g_dataset_id].y;
        dy = dy * dy;

        dz = model[i].z - dataset[g_dataset_id].z;
        dz = dz * dz;

        d = dx + dy + dz;

        if(dmin == -1 || d < dmin)
        {
            nearest[g_dataset_id] = i;
            dmin = d;
        }
    }
}

代码似乎可以工作，但我确信它可以被优化。我想知道如何利用本地内存使其变得更好。

谢谢

附言我知道还有其他(更好的)方法可以找到最近的邻居，例如 kd-tree，但现在我想使用简单的方法。

Answer 1

编译器可能会为您提升这些循环不变量，但要确保它完成，请尝试将它们分配给名为 datum_x 等的临时变量的代码。此外，将 dmin 初始化为 MAX_INT 可以避免与 -1 进行多余的比较。另一种方法是展开第一个循环迭代(i=0)以初始化 dmin。

int dmin = MAX_INT;
int d, dx, dy, dz;
int datum_x, datum_y, datum_z;

datum_x = dataset[g_model_id].x;
datum_y = dataset[g_model_id].y;
datum_z = dataset[g_model_id].z;

for (int i=0; i<size_dataset; ++i) {
    dx = model[i].x - datum_x;
    dx = dx * dx;

    dy = model[i].y - datum_y;
    dy = dy * dy;

    dz = model[i].z - datum_z;
    dz = dz * dz;

    d = dx + dy + dz;

    if(d < dmin)
    {
        nearest[g_dataset_id] = i;
        dmin = d;
    }
}