Структуры данных в ядре CUDA

Question

Я пытаюсь реализовать случайный лес в CUDA, причем каждый поток является отдельным деревом решений, для которого требуется рекурсия. Однако мой компьютер не поддерживает рекурсию в CUDA. Поэтому я пытаюсь использовать структуры данных, такие как очередь, для выполнения рекурсивной части. Я искал googled, но я не могу найти много информации об этом, и я попытался использовать Thrust внутри ядра CUDA, но он не будет компилироваться .. Так есть способ использовать очередь внутри ядра CUDA? Спасибо заранее!

Answer 1

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

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

Это то, для чего было оптимизировано оборудование. Деревья принятия решений (и, следовательно, случайные леса) не являются подобными. Вы будете использовать разные ветви if/else в каждом дереве. Так что это не подходит для графических процессоров. Вы получите ужасную эффективность ветвей. Ваша производительность снизится до менее 1/32 (т. Е. 3%) теоретических возможностей вашего оборудования.

Из Википедии CUDA ограничений:

Филиалов в программном коде существенно не влияют на производительность, при условии, что каждый из 32 нитей имеет тот же выполнение путь

же путь выполнения = все 32 потоков сделайте ветку «if true», или все 32 сделайте ветку «else».

(«Обход» вокруг этого, но это довольно дорого ИМХО, и я не думаю, что он будет полностью конкурирующим с подходами, которые предназначены для графических процессоров, например, с помощью матричных умножений сразу. ленивый, чтобы набрать его - вы наверняка найдете его в литературе GPU. Это довольно часто, чтобы ускорить работу . Если это возможно для нескольких уровней if, это будет намного менее эффективно, поскольку стоимость растущий экспоненциально с глубиной. Иногда либо компилятор CUDA, либо процессор могут оптимизировать это автоматически для простых/неглубоких случаев.)