Verschmelzungsliste mit Nachschlüssel in CUDA

Question

Angenommen, wir haben eine Liste von structs graph_node *:

struct graph_node{ 
    int from; 
    int to; 
    float prob; 
} 

Nun nehmen wir mehrere .ab und .to Elemente werden in der Liste wiederholt. Zum Beispiel: Wir können zwei Knoten mit denselben .from- und .to-Attributen (5,6, .6) und (5,6, .5) haben. Ich würde gerne wissen, ob es einen Weg in Schub oder Cuda gibt, um diese beiden Elemente zusammenzuführen und ihre Wahrscheinlichkeiten zu addieren (für das vorherige Beispiel haben sie 5,6 und 1,1) oder addieren einfach alle Wahrscheinlichkeiten der Objekte, die die gleichen .from und .to enthalten und ihnen die addierte Wahrscheinlichkeit zu allen Elementen mit diesem Schlüssel zuweisen (5,6,1,1 und 5,6,1,1).

Answer 1

Wie von @talonmies in den Kommentaren angezeigt, kann dies unter Verwendung thrust::reduce_by_key getan werden. Zuerst muss die Liste von graph_node sortiert werden, um gleiche Knoten zusammen zu bringen. Dann kann reduce_by_key verwendet werden, um wie Knoten zu summieren.

Es gibt wahrscheinlich viele Variationen davon, abhängig davon, wie Sie tatsächlich bereit sind, Ihre Daten zu speichern, und ob Sie eine Änderung der Eingabeliste usw. erlauben wollen. Ich gehe davon aus, dass die Daten in einem Vektor gespeichert werden müssen der Struktur, die Sie definieren, und die Ausgabeliste muss von der Eingabeliste getrennt sein.

In diesem Fall müssen wir einen Funktor für den Sortiervorgang bereitstellen, um anzugeben, wie graph_node in sortierter Reihenfolge angeordnet werden soll. Wir müssen auch einen Gleichheitstest und einen Summierungsoperator für die Operation reduce_by_key bereitstellen. Hier ist ein voll gearbeitet Beispiel einen möglichen Ansatz zeigt:

$ cat t13.cu 

#include <thrust/device_vector.h> 
#include <thrust/sort.h> 
#include <thrust/reduce.h> 
#include <iostream> 
#include <vector> 
#include <thrust/host_vector.h> 

struct graph_node{ 
    int from; 
    int to; 
    float prob; 
}; 

struct my_graph_node_sort 
{ 
    __host__ __device__ 
    bool operator()(graph_node &a, graph_node &b){ 
    if (a.from > b.from) return false; 
    if (a.from < b.from) return true; 
    return (a.to <= b.to); 
    } 
}; 

struct my_graph_node_equality 
{ 
    __host__ __device__ 
    bool operator()(const graph_node &a, const graph_node &b){ 
    return ((a.from == b.from) && (a.to == b.to)); 
    } 
}; 

struct my_graph_node_reduce 
{ 
    __host__ __device__ 
    graph_node operator()(const graph_node &a, const graph_node &b){ 
    graph_node t = a; 
    t.prob += b.prob; 
    return t; 
    } 
}; 


int main(){ 

    std::vector<graph_node> h_n = { {0,1,0.1f}, {0,2,0.1f},{5,6,0.6f},{1,2,0.1f},{2,5,0.1f},{5,6, 0.5f}}; 
    thrust::device_vector<graph_node> d_n = h_n; 
    thrust::device_vector<graph_node> d_kr(d_n.size()); 
    thrust::device_vector<graph_node> d_vr(d_n.size()); 
    thrust::sort(d_n.begin(), d_n.end(), my_graph_node_sort()); 
    int rs = (thrust::reduce_by_key(d_n.begin(), d_n.end(), d_n.begin(),d_kr.begin(), d_vr.begin(), my_graph_node_equality(), my_graph_node_reduce())).first - d_kr.begin(); 
    thrust::host_vector<graph_node> h_r = d_vr; 
    std::cout << "from,to,prob" << std::endl; 
    for (int i = 0; i < rs; i++) 
    std::cout << h_r[i].from << "," << h_r[i].to << "," << h_r[i].prob << std::endl; 
} 
$ nvcc -std=c++11 -arch=sm_35 -o t13 t13.cu 
$ ./t13 
from,to,prob 
0,1,0.1 
0,2,0.1 
1,2,0.1 
2,5,0.1 
5,6,1.1 
$ 

Wie wahr ist mit vielen Codes CUDA, die Anordnung der Daten in AOS-Format möglicherweise nicht optimal für die Effizienz der Verarbeitung. Die Umlagerung des Datenspeichers in einen separaten Satz von Vektoren für die Elemente .from, .to und .prob würde wahrscheinlich einen gewissen Effizienzgewinn und auch eine Vereinfachung des Codes ermöglichen.