Эффективное распараллеливание поиска для неупорядоченного набора данных

[andrey2185]

Привет, подскажите, куда копать, у меня естественно-научное образование, можно ли эффективно распараллелить следующую задачу?

Есть два плотных одномерных плотных массива целых чисел разной длины (от тысяч до миллионов интов), в одном значения не упорядочены и повторяются, второй отсортирован по возрастанию и значения не повторяются, надо найти для каждого элемента из первого вектора минимальное значение из второго вектора, которое больше или равно ему, но не больше чем на заданную величину, которая одинакова для всех.

Вот код на julia, просто для наглядности, но он выполняется в одном потоке, а вот с какой стороны подойти, чтобы выполнить за n тактов на GPU, я который день мучась

# for example
A = Int32[2, 3, 3, 15, 4, 4, 8, 32, 9, 9, 9, 13, 14]
B = Int32[1, 4, 5, 6, 7, 9, 10, 15, 23, 54]
limit = 10
sortA = sort(A)
inds = sortperm(sortperm(A))
sortR = zeros(Int32, 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]
# result:
R == [4, 4, 4, 15, 4, 4, 9, 0, 9, 9, 9, 15, 15]  # -> true

[BDA]

Не понял, зачем вы в коде-примере сортируете массив A и ищете перестановки индексов. Сразу ищите элементы из массива A в массиве B и попробуйте вместо линейного поиска использовать бинарный. Тогда, например, если массивы A и B будут оба длиной 1000000 (10^6), то вместо худшего случая линейного поиска с 1000000000000 (10^12) сравнений, будет всего лишь 20000000 (2 * 10 ^7) сравнений. А простейшее распараллеливание на ГПУ - искать каждый элемент массива A в массиве B в отдельном потоке.

[andrey2185]

BDA, да лучше получилось, и проще распараллелить, спасибо