我正在尝试做的事情:
在 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 开始。话虽如此,我明白这意味着子元素可以被孤立,但我不会在这里解决这个问题的解决方案。
最佳答案
它看起来像是 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, ...
前提是
- 没有孤儿;
Parent_IDs
是无序且唯一的;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
。
关于c++ - 如何在 GPU(最好是 CUDA)上对两个数据容器执行关系连接?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37813436/