3

我正在尝试做的事情：

在 GPU 上，我试图模仿 SQL 在关系代数中使用的约定来对表执行连接（例如内连接、外连接、交叉连接）。在下面的代码中，我想要执行内部联接。想象两张表（容器），其中一张是父/主表，另一张是子表。父子连接关系是一对多（或一对无，如果 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 是操作期间唯一更改的向量）：

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 相乘得出的。还要注意，所有条目都保留在子向量上（所有 7 个元素仍然存在于输出中，尽管 Child_Values 单个元素已更新）。父向量不会保留在输出中（请注意，向量列表中缺少 ParentID 4，并且那里没有“虚拟”占位符）。这是“内部联接”的行为。

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

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

- 使用 CUDPP 的哈希运算；

-Alenka DB。

最后，我的问题再次重申：

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

编辑
Parent_IDs 并不总是一个序列。在运行时，可能会删除父向量中的元素。新插入的父元素将始终附加一个从最后一个元素的 ID 播种的 ID。话虽如此，我理解这意味着子元素可能是孤立的，但我没有在这里解决解决方案。

4

1 回答 1

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 碱基序列。您会发现如果是 0 碱基序列，或者只是父值索引，thrust::make_transform_iterator则不需要，如下所示。Parent_IDsChild_ParentIDs

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并且您属于 type的事实，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);

注意Parent_index每次修改父向量时都需要重新创建。

于 2016-06-14T14:19:58.933 回答