Можно ли использовать CUDA для эффективного вычисления частоты элементов в отсортированном массиве?

Я очень новичок в Cuda, я прочитал несколько глав из книг и прочитал много уроков онлайн. Я сделал свои собственные реализации по сложению и умножению векторов.

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

Наша цель — найти частоты каждого целого числа в массиве.

Последовательно мы могли сканировать массив один раз, чтобы получить вывод. Время сложность будет O(n),

Так как группы разные, я думаю, должно быть возможно воспользоваться преимуществами CUDA.

Предположим, что это массив

   1
1
1
1
2
2
3
3
5
5
6
7

Чтобы достичь полного параллелизма, каждый поток должен точно знать, какую часть массива он должен сканировать, чтобы найти сумму. Это может быть достигнуто только если мы используем другой массив с именем int dataPosPerThread[] который для каждого потока идентифицирует dataPosPerThread[threadId] будет иметь в качестве значения начальную позицию в исходном массиве. Таким образом, это будет означать, что каждый поток будет знать, где начать и где закончить.

Однако таким образом мы ничего не получим, потому что это заняло бы у нас O(n) время для того, чтобы найти позиции. В конечном итоге общая стоимость будет O(n) + cost_to_transfer_the_data_to_the_gpu + O(c) + cost_to_transfer_the_results_to_the_gpu
где O(c) постоянное время, которое потребуется потокам, чтобы найти конечный результат, при условии, конечно, что у нас есть много различных целых чисел внутри исходного массива.

Я хотел бы избежать лишних O(n) Стоимость.

То, что я до сих пор думал, имеет массив размеров arraySize, мы указываем общее количество потоков, которые будут использоваться, скажем, totalAmountOfThreads это означает, что каждый поток должен будет сканировать totalAmountOfThreads/arraySize ценности.

Первый поток (id 0) начнет сканирование с позиции 0 до позиции totalAmountOfThreads/arraySize,

Второй поток начнется с totalAmountOfThreads/arraySize + 1 и так далее.

Проблема заключается в том, что какой-то поток может работать с разными целочисленными группами или с одной группой, у которой больше значений обрабатывается другими потоками. Например, в приведенном выше примере, если мы предположим, что у нас будет 6 потоков, каждый поток будет принимать 2 целых числа массива, поэтому у нас будет что-то вроде этого:

   1     <-------- thread 0
1
1     <-------- thread 1
1
2     <-------- thread 2
2
3     <-------- thread 3
3
5     <-------- thread 4
5
6     <-------- thread 5
7

Как вы можете видеть поток 0 имеет только 1 значения, однако есть и другие 1 значения, которые обрабатываются потоком 2. Однако для достижения параллелизма эти потоки должны работать с несвязанными данными. Предполагая, что мы будем использовать эту логику, каждый поток вычислит следующие результаты:

   thread 0 => {value=1, total=2}
thread 1 => {value=1, total=2}
thread 2 => {value=2, total=2}
thread 3 => {value=3, total=2}
thread 4 => {value=5, total=2}
thread 5 => {{value=6, total=1}, {value=7, total=1}}

Имея этот результат, что может быть достигнуто в дальнейшем? Кто-то может предложить использовать дополнительную hash_map, например unordered_map который может эффективно обновлять для каждого значения, вычисляемого одним потоком, общую переменную. тем не мение

1. Unordered_map не поддерживается компилятором cuda

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

3. Даже если вышеупомянутые два не были проблемой, мы все равно имели бы условия гонки между потоками при обновлении хэш-карты.

Что было бы хорошим способом для решения этой проблемы?

заранее спасибо