Wie man relationalen Join auf zwei Datencontainern auf GPU (vorzugsweise CUDA) durchführen?

Question

Was ich versuche zu tun:

Auf der GPU, ich versuche die Konventionen von SQL in der relationalen Algebra verwendet nachzuahmen schließt sich auf Tabellen auszuführen (z Inner Join, Outer Join, Kreuz verbinden). Im folgenden Code möchte ich einen Inner Join ausführen. Stellen Sie sich zwei Tabellen (Container) vor, in denen eine Tabelle die Eltern/Master-Tabelle und die andere die Child-Tabelle ist. Die Join-Beziehung Parent zu Child ist 1 zu viele (oder 1 zu keine), falls in Child_ParentIDs kein Element vorhanden ist, das mit einem Element in Parent_IDs übereinstimmt.

Beispiel Eingabedaten:

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 

Betrieb als SQL-Abfrage:

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

Betriebsbeschreibung:

Join Child_ParentIDs zu Parent_IDs die entsprechenden Parent_Values ​​zuzugreifen. Verwenden Sie die entsprechenden Parent_Values, um sie mit den entsprechenden Child_Permanances zu multiplizieren, und platzieren Sie das Ergebnis jeder Operation in Child_Values.

Erwarteter Ausgang (Child_Values ​​ist das einzige geänderte Vektor während des Betriebs):

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 

Erläuterung (falls es nicht sinnvoll, DID): abgeleitet ist

Der Wert von 2226 mit 106 multipliziert wird und 21. 10439 ergibt sich aus Multiplikation von 143 und 73. Beachten Sie auch, dass ALLE Einträge auf den untergeordneten Vektoren erhalten bleiben (alle 7 Elemente existieren noch in der Ausgabe, wenn auch einzelne Elemente von Child_Values ​​aktualisiert werden). Die übergeordnete Vektoren werden in der Ausgabe nicht beibehalten (Notice ParentID 4 fehlt in der Liste der Vektoren und es gibt keinen "Dummy" -Platzhalter dafür). Dies ist das Verhalten eines "Inner Join".

Ideen von eleganten Lösungen, die ich nicht zur Arbeit bekommen habe:

-Utilizing CUDA Dynamic Parallelism. Vielleicht ist die einzige Lösung im gesamten Internet, die ich gefunden habe, genau das, was ich versuche zu tun ist here-part 1 und here-part 2.

-Verwendung der Hash-Operationen von CUDPP;

-Alenka DB.

Und schließlich meine Frage wiederholte:

Gibt es eine Arbeitslösung aus einer rein GPU Perspektive (vorzugsweise mit CUDA, aber OpenCL funktionieren würde) zur Durchführung Relational schließt sich auf zwei getrennte Behälter von Daten, so dass die Daten können über diese Joins gesucht und Elemente parallel aktualisiert werden?

EDIT
Parent_IDs wird nicht immer eine Folge sein. Während der Laufzeit können Elemente aus den übergeordneten Vektoren entfernt werden. Neu eingefügten Elternelementen wird immer eine ID angehängt, die von der ID des letzten Elements aus gesetzt wird. Wenn ich das gesagt habe, verstehe ich, dass Child-Elemente verwaist sein können, aber ich gehe hier nicht auf die Lösung ein.

Answer 1

Es sieht wie eine einfache elementweise Multiplikation zwischen Elementen von Child_Permanences und ausgewählten Elementen aus Parent_Values aus. Mit ein paar Retraktionen kann dies mit einer einzigen thrust::transform durchgeführt werden.

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); 

Sie können feststellen, dass Parent_IDs nicht verwendet wird. Es ist die Einschränkung des obigen Codes. Der Code geht davon aus, dass Parent_IDs nichts als eine 1-Basen-Sequenz sein kann. Sie werden feststellen, dass thrust::make_transform_iterator nicht erforderlich ist, wenn Parent_IDs eine 0-Basen-Sequenz ist, oder Child_ParentIDs ist nur ein Elternwert-Index wie folgt in Ihrem Beispiel.

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

EDIT

Der obige Code wird davon ausgegangen, dass 1) kein Waisenkind ist; und 2) Parent_IDs ist eine feste Basis 1 Sequenz wie 1, 2, 3, ...

---

Unter der Bedingung, dass

1. gibt es kein verwaistes Kind;
2. Parent_IDs ist ungeordnet und einzigartig;
3. Child_ParentIDs ist nicht gerollt, aber nicht eindeutig;

und die Tatsache, dass Ihre Parent_IDs vom Typ int16, könnten Sie eine übergeordneten Wert Indextabelle erstellen für Element Kind, wenn der Bereich der Parent_IDs ist relativ klein zu suchen.

den Bereich der Parent_IDs Unter der Annahme, [1, 32767], könnte die Lösung Code

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); 

Hinweis sein, dass Parent_index neu erstellt wird der Elternvektor jedes Mal geändert werden müssen.