Parallel Prefix Sum (Scan)

Несколько дней назад я тестировал сэмпл OIT11 из DirectX SDK и был неприятно поражён его производительностью: 12 fps в окне 320х240. Решив разобраться, в чём дело, я реализовал небольшую программу, приблизительно воспроизводящую алгоритм prefix sum из OIT11, а также проштудировал материал по теме.

Вот код программы: OIT prefix sum.
Во-первых, алгоритм сканирования реализован "в лоб". В процессе выполнения видно, что к концу сканирования он плохо параллелится - последний (единственный) тред суммирует половину фрагментов буфера кадра, что никак нельзя назвать параллельной работой. Во-вторых, асимптотическая оценка кол-ва операций этого алгоритма = O(N * log(N)), тогда как достаточно O(N) операций (более точно, этот алгоритм выполняет N * log(sqrt(N)) операций), т. е. для сколь-нибудь большого буфера кадра его производительность ниже оптимального на несколько (!) порядков.

Фактически, применённый алгоритм - это naive prefix scan, описание которого можно найти у NVIDIA. Для пробы я написал код и для него: Naive prefix sum. Асимптотическая оценка времени его выполнения тоже O(N * log(N)). Единственное отличие - для OIT11 не требуется промежуточный буфер, куда записываются результаты суммирования, а потом копируются обратно в основной буфер.

Наиболее оптимальный на сегодняшний день алгоритм был описан Guy E. Blelloch в 1990. Он состоит из двух фаз - reduce (up-sweep) и down-sweep. Алгоритм хорошо распараллеливается, т. к. каждый тред выполняет всего одно сложение (или сложение/обмен в down-sweep). Алгоритм выполняет ~(N * 2) операций, т. е. его асимптотическая оценка - O(N). Inclusive prefix sum.

P.S. Я не очень хорошо разбираюсь в CUDA и нюансах работы тредов, поэтому меня несколько смущают описанные проблемы конфликтов банков памяти при доступе из различных тредов. Я вот задумался: атомические операции в HLSL 11 призваны убрать именно эту проблему или они нужны для чего-то другого?