c++ - 如何在 GPU(最好是 CUDA)上对两个数据容器执行关系连接？

Question

我正在尝试做的事情:

在 GPU 上，我试图模仿 SQL 在关系代数中使用的约定来对表执行连接(例如内连接、外连接、交叉连接)。在下面的代码中，我想执行一个内部连接。想象一下有两个表(容器)，其中一个表是 Parent/Master 表，另一个是 Child 表。父子连接关系是 1 对多(或 1 对无，如果 Child_ParentIDs 中没有元素与 Parent_IDs 中的元素匹配)。

示例输入数据:

Parent_IDs:    [1, 2,  3,  4, 5]  ... 5 elements
Parent_Values: [0, 21, 73, 0, 91] ... 5 elements
Child_ParentIDs:   [1,   1,   1,  2,   3,   5,  5]  ... 7 elements
Child_Permanences: [120, 477, 42, 106, 143, 53, 83] ... 7 elements
Child_Values:      [0,   0,   0,  0,   0,   0,  0]  ... 7 elements

作为 SQL 查询操作:

SELECT child.permanence * parent.value FROM child, parent WHERE child.parent_id = parent.id;

操作说明:

将 Child_ParentIDs 连接到 Parent_IDs 以访问相应的 Parent_Values。使用对应的Parent_Values与对应的Child_Permanences相乘，并将每个运算的结果放入Child_Values。

预期输出(Child_Values 是操作期间唯一更改的 vector ):

Child_ParentIDs:   [1,   1,   1,  2,    3,     5,    5]     ... 7 elements
Child_Permanences: [120, 477, 42, 106,  143,   53,   83]    ... 7 elements
Child_Values:      [0,   0,   0,  2226, 10439, 4823, 7553]  ... 7 elements

解释(以防万一):

2226 的值是通过将 106 和 21 相乘得出的。10439 是通过将 143 和 73 相乘得出的。还要注意，所有条目都保留在子 vector 上(所有 7 个元素仍然存在于输出中，尽管 Child_Values 个别元素已更新).父 vector 未保留在输出中(注意 vector 列表中缺少 ParentID 4，并且那里没有“虚拟”占位符)。这是“内部联接”的行为。

我还没有开始工作的优雅解决方案的想法:

-利用 CUDA 的动态并行性。也许我在整个互联网上找到的唯一解决方案正是我想做的事情是 here-part 1和 here-part 2 .

-使用CUDPP的散列操作；

-Alenka 数据库。

最后，重申一下我的问题:

从纯 GPU 的角度来看(最好使用 CUDA，但 OpenCL 也可以)是否有任何可行的解决方案来完成两个独立数据容器的关系连接，以便可以通过所述连接并行搜索数据和更新元素？

编辑
Parent_IDs 并不总是一个序列。在运行时，可以删除父 vector 中的元素。新插入的父元素将始终附加一个 ID，该 ID 从最后一个元素的 ID 开始。话虽如此，我明白这意味着子元素可以被孤立，但我不会在这里解决这个问题的解决方案。

Answer 1

它看起来像是 Child_Permanences 的元素与 Parent_Values 的选定元素之间的简单元素乘法。通过一些限制，这可以通过单个 thrust::transform 完成。

thrust::transform(
    Child_Permanences.begin(),
    Child_Permanences.end(),
    thrust::make_permutation_iterator(
        Parent_Values.begin(),
        thrust::make_transform_iterator(Child_ParentIDs.begin(),
                                        _1 - 1)),
    Child_Values.begin(),
    _1 * _2);

您可能会注意到未使用 Parent_IDs。就是上面代码的限制。该代码假定 Parent_IDs 只能是一个 1 碱基序列。如果 Parent_IDs 是一个 0 基序列，或者 Child_ParentIDs 只是一个父值索引，你会发现 thrust::make_transform_iterator 不是必需的按照你的例子。

Child_ParentIDs:   [0, 0, 0, 1, 2, 4, 4]

编辑

以上代码假定 1) 没有孤儿；和 2) Parent_IDs 是一个从 1 开始的固定序列，如 1, 2, 3, ...

---

前提是

1. 没有孤儿；
2. Parent_IDs 是无序且唯一的；
3. Child_ParentIDs 未被编码但不是唯一的；

并且您的 Parent_IDs 是 int16 类型的事实，当 的范围时，您可以创建一个父值索引表供子元素查找>Parent_IDs 相当小。

假设Parent_IDs的范围是[1, 32767]，解法代码可以是

thrust::device_vector<int> Parent_index(32768, -1);
thrust::scatter(thrust::make_counting_iterator(0),
                thrust::make_counting_iterator(0) + Parent_IDs.size(),
                Parent_IDs.begin(),
                Parent_index.begin());
thrust::transform(
    Child_Permanences.begin(),
    Child_Permanences.end(),
    thrust::make_permutation_iterator(
        Parent_Values.begin(),
        thrust::make_permutation_iterator(
            Parent_index.begin(),
            Child_ParentIDs.begin())),
    Child_Values.begin(), _1 * _2);

请注意，每次修改父 vector 时，都需要重新创建Parent_index。