プレフィックスサムの使い道

Question

computershaderを勉強していたところ、プレフィックスサムとゆうアルゴリズムが出てきました。

内容はなんとなく理解できたのですが、私はcomputershaderをグラフィックに関する演算にしか使ってこなかったのでプレフィックスサムを使用してどういった処理を高速化するのか解りません。

Answer 1

一部のソートアルゴリズムの高速化に利用できます。

分布数え上げソート

https://www.codereading.com/algo_and_ds/algo/counting_sort.html
のサンプルコードのうち、累積度数分布を求めるところが、プレフィックスサムの計算になります。

ソート自体の並列化については
http://www.drdobbs.com/architecture-and-design/parallel-counting-sort/224700144（英語）
で解説されているようですが、ちゃんとは読んでいません。

クイックソート

http://courses.cs.washington.edu/courses/cse332/10sp/lectures/lecture20.pdf（英語）
のスライド11,12付近で解説されています。クイックソートの主要部分であるパーティショニングは、プレフィックスサムを使うと並列に実現できます。

Answer 2

興味ある分野なので答えをちゃんと知っているわけではないのですがコメントしてみます。

前提として並列計算が可能なハードウェアを用いた計算アルゴリズムであるというのがあるのではないでしょうか？prefix sumというのはreduce/scanのscanのことという記事を見ました。つまり多数の小さな計算を（レンダリングの際にはよく行う計算だと思います）並列して行う際に隣り合った要素の計算の結果を利用してまた別の並列計算を行うといった場合に並列に都合がよいといったことがポイントではないかと思いました。

外してたらスミマセン！

Comments

[seri]

回答ありがとうございます、なぜこのようなアルゴリズムが大々的に扱われているのか不思議でしたが、並列化との相性からきていたのですね、悩みが解決致しました。