Распараллелить поиск на CUDA

подскажите пожалуйста, какой алгоритм должен быть на CUDA для распараллеливания этой задачи:

Есть два вектора A и B целочисленных значений, они имеют разное количество элементов от тысяч до миллионов штук.

В векторе А может значения могут повторяться и неупорядоченные. В векторе B значения упорядочены и не повторяются.

Для каждого значения (v) из вектора A надо найти в пределах [v; v + 10] следующее по величине значение, но из вектора B. (Если значение не найдено, оставляем 0 в векторе с ответами)

Подскажите какой-то подход, алгоритм, помогите псевдокодом, ибо ничего на ум не приходит.

На CPU я сортирую А, запоминая старые индексы, потом перебираю значения А в одном потоке в цикле for с использованием дополнительного счетчика для В. После найденные индексы В для А выстраиваю в изначальном порядке значений А, и готово, но хотелось бы ускориться.

Примерно так:

// для примера
A = [2, 3, 3, 15, 4, 4, 8, 32, 9, 9, 9, 13, 14]
B = [1, 4, 5, 6, 7, 9, 10, 15, 23, 54]

limit = 10

sortA, inds = sort(A)
sortR = zeros(length(A))

b = 1
for i = 1 : length(sortA)
    while B[b] < sortA[i]
        b += 1
        if b == length(B)
            break
        end
    end
    if B[b] <= (sortA[i] + limit)
        sortR[i] = B[b]
    end
end
R = sortR[inds]

// результат:
R = [4, 4, 4, 15, 4, 4, 9, 0, 9, 9, 9, 15, 15]  

Ответы (0 шт):