отсортированный список пересечений на GPU - PullRequest
Новая
       57

отсортированный список пересечений на GPU

0 голосов
/ 17 октября 2011

я знаю, как пересечь два отсортированных списка на ЦП, используя алгоритм O (n + m), где n и m - длина двух списков.Тем не менее, есть ли хороший алгоритм для пересечения двух списков на GPU, который позволяет избежать конфликтов записи.Я боюсь, что при пересечении два потока могут попытаться записать в один и тот же буфер вывода, что приведет к конфликту.Я не ищу библиотеку.Я хочу знать основную идею + некоторый код, если это возможно

Ответы [ 3 ]

1 голос
/ 17 октября 2011

Я понимаю, что вы не хотите, чтобы ваш код был привязан к библиотеке. Тем не менее, я думаю, что Thrust имеет алгоритм, который делает именно то, что вы хотите, при условии, что вы обрабатываете свой список в традиционном C-массиве.

Взгляните на thrust::merge здесь http://wiki.thrust.googlecode.com/hg/html/group__merging.html

- редактировать -

Подумав немного больше о вашем вопросе, пересечение двух списков непосредственно на GPU кажется очень сложным для написания с помощью CUDA.

Следующий фрагмент кода является альтернативным решением (объединение моего предыдущего решения и @ jmsu's). Это пример того, как пересекать два списка целых чисел, хранящихся в порядке убывания. Списки хранятся в памяти устройства, но вычисления не могут быть выполнены в ядре. Таким образом, вам нужно использовать его между вызовами ядра, если это возможно: 

#include <thrust/set_operations.h>
#include <ostream>

int main() {

    int A_host[] = {11, 9, 5, 3};
    int B_host[] = {14, 12, 10, 5, 1};
    int sizeA = 4;
    int sizeB = 5;
    int sizeC = (sizeA < sizeB) ? sizeA : sizeB;

    int C_host[sizeC];

    int* A_device;
    int* B_device;
    int* C_device;

    cudaMalloc( (void**) &A_device, sizeof(int) * sizeA);
    cudaMalloc( (void**) &B_device, sizeof(int) * sizeB);
    cudaMalloc( (void**) &C_device, sizeof(int) * sizeC);

    cudaMemcpy( A_device, A_host, sizeof(int) * sizeA, cudaMemcpyHostToDevice);
    cudaMemcpy( B_device, B_host, sizeof(int) * sizeB, cudaMemcpyHostToDevice);
    cudaMemset( C_device, 0, sizeof(int) * sizeC);

    // add an alias to thrust::device_ptr<int> to be more readable
    typedef thrust::device_ptr<int> ptrI;

    thrust::set_intersection(ptrI(A_device), ptrI(A_device + sizeA), ptrI(B_device), ptrI(B_device + sizeB), ptrI(C_device), thrust::greater<int>() );
    cudaMemcpy( C_host, C_device, sizeof(int) * sizeC, cudaMemcpyDeviceToHost);


    std::copy(C_host, C_host + sizeC, std::ostream_iterator<int> (std::cout, " ") );
}
0 голосов
/ 17 октября 2011

Следуя идее Thrust, @jHackTheRipper сказал, что вам не нужен весь Thrust, вы можете использовать только то, что вам нужно.

Чтобы сделать это с помощью Thrust, вы можете использовать thrust :: set_intersection

http://wiki.thrust.googlecode.com/hg/html/group_set_operations.html#ga17277fec1491c8a916c9908a5ae40807

Пример кода из документации по Thrust: 

#include <thrust/set_operations.h>
...
int A1[6] = {1, 3, 5, 7, 9, 11};
int A2[7] = {1, 1, 2, 3, 5,  8, 13};

int result[7];

int *result_end = thrust::set_intersection(A1, A1 + 6, A2, A2 + 7, result);
// result is now {1, 3, 5}

Чтобы выполнить его в графическом процессоре, вы можете скопировать массивы в память устройства и использовать thrust :: device_ptr, или лучше использовать thrust :: device_vector. Они совместимы с векторами STL. 

thrust::host_vector<int> h_list1;
thrust::host_vector<int> h_list2;
// insert code to populate the lists...

thrust::device_vector<int> d_list1 = h_list1; // copy list1 from host to device
thrust::device_vector<int> d_list2 = h_list2; // copy list2 from host to device

thrust::device_vector<int> d_result;

thrust::set_intersection(d_list1.begin(), d_list1.end(), d_list2.begin(), d_list2.end(), d_result.begin());

thrust::host_vector<int> h_result = d_result; // copy result from device to host

Я не проверял код, но он должен быть чем-то близким к этому. У этого сайта есть отличные примеры, с которых можно начать.

0 голосов
/ 17 октября 2011

Как насчет того, чтобы сделать что-то вроде этого: Если значение A [i] существует в массиве B, сохраните его в C [i], в противном случае C [i]: = DUMMY.

И затем выполните параллельный массивуплотнительная?Для этого есть инструменты - например, отметьте здесь - библиотеку и документ с описанием используемого алгоритма.

...