3

私がやろうとしていること:

GPU では、リレーショナル代数の SQL でテーブルの結合 (内部結合、外部結合、クロス結合など) を実行するために使用される規則を模倣しようとしています。以下のコードでは、内部結合を実行したいと考えています。一方のテーブルが親/マスター テーブルで、もう一方が子テーブルである 2 つのテーブル (コンテナー) を想像してください。親と子の結合関係は 1 対多 (または、Parent_IDs の要素と一致する Child_ParentIDs に要素がない場合は 1 対なし) です。

入力データの例:

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_ParentID を Parent_ID に結合して、対応する Parent_Value にアクセスします。対応する 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 を乗算した結果です。また、すべてのエントリが子ベクトルに保持されていることに注意してください (Child_Values の個々の要素が更新されているにもかかわらず、7 つの要素はすべて出力に存在します)。親ベクトルは出力に保持されません (ベクトルのリストに ParentID 4 がなく、そのための「ダミー」プレースホルダーがないことに注意してください)。これが「内部結合」の動作です。

私がうまくいかなかったエレガントなソリューションのアイデア:

-CUDA の動的並列処理の利用。おそらく、インターネット全体で私が見つけた唯一の解決策は、私がやろうとしていることを正確に実行するのはhere-part 1とhere-part 2です。

-CUDPP のハッシュ操作を使用する。

-アレンカDB。

最後に、私の質問は次のように繰り返されます。

純粋に GPU の観点から (できれば CUDA を使用しますが、OpenCL も機能します)、データの 2 つの別個のコンテナーでリレーショナル結合を実行して、データを検索し、要素を並列に更新できるようにするための有効なソリューションはありますか?

EDIT
Parent_IDs は常にシーケンスになるとは限りません。実行時に、親ベクトルの要素が削除される可能性があります。新しく挿入された親要素には、最後の要素の ID からシードされた ID が常に追加されます。そうは言っても、これは子要素が孤立する可能性があることを意味すると理解していますが、ここではその解決策には触れていません。

4

1 に答える 1

1

Child_Permanencesの要素とから選択された要素の間の単純な要素単位の乗算のように見えますParent_Values。いくつかの制限を加えれば、これは 1 つの で実行できます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あなたがタイプであるという事実は、範囲がかなり小さい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 に答える