Включенное сканирование на основе графического процессора на неуравновешенном дереве

Question

У меня есть следующая проблема: мне нужно вычислить включенные проверки (например, prefix sums) значений на основе древовидной структуры на графическом процессоре. Эти проверки выполняются либо из корневого узла (сверху вниз), либо из листовых узлов (снизу вверх). Случай простой цепи - easily handled, но древовидная структура делает распараллеливание довольно сложным для эффективной реализации.

Например, после того, как сверху вниз включительно сканирования, (12) проведет (0)[op](6)[op](7)[op](8)[op](11)[op](12), и снизу вверх включительно сканирования, (8) проведет (8)[op](9)[op](10)[op](11)[op](12), где [op] является данный бинарный оператор (матрица сложения, умножение и т. д.).

Кроме того, нужно учитывать следующие моменты:

• Для типичного сценария, длина различных ветвей не должна быть слишком длинной (~ 10), с чем-то вроде 5 до 10 ветвей, так что это то, что будет выполняться внутри блока, и работа будет разделена между потоками. Различные блоки будут просто обрабатывать разные значения узлов. Это, очевидно, не является оптимальным в отношении занятости, но это ограничение проблемы, которая будет решена через некоторое время. На данный момент я буду полагаться на Instruction-level parallelism.
• Структура диаграммы не может быть изменена (она описывает реальную систему), поэтому она не может быть сбалансирована (или только путем изменения корня дерева, например, с использованием (6) в качестве нового корня). Тем не менее, типичное дерево не должно быть слишком неуравновешенным.
• В настоящее время я использую CUDA для GPGPU, поэтому я открыт для любой библиотеки шаблонов с поддержкой CUDA, которая может решить эту проблему.
• Узел данных уже находится в глобальной памяти, и результат будет использоваться другими ядрами CUDA, поэтому цель заключается в достижении этого, не делая этого огромным узким местом.
• Не существует «цикла», то есть ветви не могут сливаться с деревом.
• Структура дерева фиксирована и задана в фазе инициализации.
• Одна бинарная операция может быть довольно высокой (например, умножение полиномиальных матриц, т.е. каждый элемент является многочленом заданного порядка).

В этом случае, какая была бы «лучшая» структура данных (для древовидной структуры) и лучшие алгоритмы (для включенных сканирований/префиксов) для решения этой проблемы?

Answer 1

Наверное, загадочная идея, но представьте, что вы вставляете узлы значения 0 в дерево, чтобы получить двумерную матрицу. Например, в вашем примере будет 3 узла нулевого значения ниже узла . Затем используйте один поток для перемещения каждого уровня матрицы по горизонтали. Для суммы префикса сверху вниз смещайте потоки таким образом, чтобы каждый нижний поток задерживался на максимальное количество ветвей, которые дерево может иметь в этом месте. Итак, вы получаете «волну» с наклонным краем, проходящим по матрице. Верхние потоки, находящиеся далее, вычисляют эти узлы во времени, чтобы они могли обрабатываться далее потоками, идущими дальше вниз. Вам понадобится то же количество потоков, что и дерево.

Answer 2

Я думаю, что параллельно Приставка сканирование может не подходит для вашего случая, потому что:

алгоритм сканирования параллельно Приставка увеличит общее количество [op] в вашем звене prefix sum, 16 входов параллельно Приставка сканирование требует 26 [op], в то время как для последовательной версии требуется только 15. Оптимальный параллельный алгоритм основан на предположении, что существует достаточно аппаратных ресурсов для параллельного запуска нескольких [op].

Вы можете оценить стоимость вашего [op] перед тем, как попробовать параллельное префиксное сканирование.

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

0-1-2-3 
0-4-5 
0-6-7-8-9-10 
0-6-7-8-11-12 

Answer 3

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

Answer 4

Мое первое впечатление заключается в том, что вы могли бы организовать узлы дерева в одномерном массиве, аналогично тому, что предложил Эрик. А затем вы можете выполнить Segmented Prefix Sum Scan (http://en.wikipedia.org/wiki/Segmented_scan) над этим массивом.

Использование дерева узлов в качестве примера, 1-тусклый массив будет выглядеть следующим образом:

0-1-2-3-0-4-5-0-6-7-8-9-10-0-6-7-8-11-12 

И тогда вы бы параллельный массив флагов, указывающий, где начинается новый список (по списку, я имею в виду последовательность, начиная с корня и заканчивая листовым узлом):

1-0-0-0-1-0-0-1-0-0-0-0- 0-1-0-0-0- 0- 0 

Для восходящем случае, вы можете создать отдельный массив сегмента флаг следующим образом:

0-0-0-1-0-0-1-0-0-0-0-0- 1-0-0-0-0- 0- 1 

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

А как реализовать сегментированный Prefix Scan, я не выполнил один я, но я нашел несколько ссылок, которые могут быть информативными о том, как это сделать: http://www.cs.cmu.edu/afs/cs/academic/class/15418-s12/www/lectures/24_algorithms.pdf и http://www.cs.ucdavis.edu/research/tech-reports/2011/CSE-2011-4.pdf (стр.23)