GLSLでクイックソート？

Question

私は、GLSLシェーダを使用してGPUへの処理の大きな塊を移植検討しています。私は全体つまずい当面の問題の一つは、ステップの一つでアルゴリズムが（データに依存する数）、要素のリストを維持し、それらを並べ替えると、いくつかの最大のものを取る必要があることです。 CPUでは、これは単にSTLのベクトルとのqsort（）を使用して行われますが、GLSLで、私はこのような施設を持っていません。この欠陥に対処する方法はありますか？

Answer 1

情報開示：私は本当にGLSLを知らない - 私は別のプログラミング言語を持っているAMDのストリームSDK、とGPGPUプログラミングを行ってきた。

。

あなたからビョルンの答えにコメント、私はあなたがのありませんの巨大なデータベースをソートするためにGPUを使用することに興味を持っていることを集める - 逆電話帳を作成するか、何のように、代わりに、あなたが持っています小さなデータセットと、各フラグメントは、ソートするためのそれ自身のデータセットを持っています。その他の中央値ピクセルフィルタリングをやろうような？

私は、一般的に言うことができます：

小さなデータセットの場合は、ソートアルゴリズムは本当に重要ではありません。人々は非常に大規模なデータベースのための最高のソートアルゴリズムであるの心配のキャリアを費やしてきたが、小さなNのために、それは本当にあなたがクイックソートを使用するかどうかは関係ありません、ヒープはソート、基数ソート、シェルソート、最適化されたバブルソート、最適化されていないバブルソート、など少なくともそれは、CPUにあまり重要ではありません。

GPUはSIMDデバイスなので、ロックステップにおいて同一の動作を実行する各カーネルを持ちたいです。計算は安いですが、枝は、各カーネルは別の方法は非常に、非常に、非常に高価であり、branchs高価で、データ依存枝です。

各カーネルはそれをソートする独自の小さなデータセットだし、ソートするデータの＃はデータ依存であり、それは各カーネルごとに異なる数の可能性があるのであれば、

は、あなたはおそらく、あなたができれば（最大サイズを選ぶ方がいいでしょう）、無限またはいくつかの多数、有する配列をパディングと、各カーネルが最適化されていない無店舗バブルソートであろう全く同じ並べ替えを行う。このようなものを有する：

擬似コード（私はGLSLを知っていないので）、9ポイントの一種。

#define TwoSort(a,b) { tmp = min (a, b); b = a + b - tmp; a = tmp; }
for (size_t n = 8; n ; --n) {
  for (size_t i = 0; i < n; ++i) {
    TwoSort (A[i], A[i+1]);
  }
}

Answer 2

あなたはこの記事を見たことがありますか？ https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html

私はあなたがクイックソートアルゴリズムやクイックソートのアルゴリズムを探していた確認されませんでした。記事のアルゴリズムはマージソート使用しています...

Answer 3

は、私はGPUプログラミングについての知識を持っていない。の

あなたが唯一の上位のいくつかの値を見てする必要がありますと言ったので

私は、クイックソートではなくヒープソートを使用すると思います。ヒープはO(n)時間内に構築さが、トップ値を取得することはlog(n)であることができます。したがって、もしあれば、あなたが必要とする値の数はあなたには、いくつかのパフォーマンスを得ることができエレメントの総数よりも著しく小さいます。