私はGLSLシェーダを使用してGPUに大量の処理を移植することを検討しています。私が直面した直面する問題の1つは、ステップの1つで、アルゴリズムが要素のリストを保持し、それらをソートし、いくつかの最大のものを取る必要があることです（その数はデータに依存します）。 CPU上では、これは単にSTLベクトルとqsort（）を使って行われますが、GLSLではそのような機能はありません。この欠点に対処する方法はありますか？GLSLのクイックソート？
開示：GLSLは本当にわかりません - プログラミング言語の異なるAMD Stream SDKを使用してGPGPUプログラミングを行っています。
あなたからビョルンの答えにコメント、私はあなたが巨大なデータベースソートするGPUを使うことに興味ないであることを集める - 逆電話帳を作成するか、どんななどを、代わりに、あなたは小さなデータセットとそれぞれを持っていますフラグメントには、ソートするための独自のデータセットがあります。メジアンピクセルフィルタリングにもっと似ていますか？
私は、一般的に言うことができます：
小さなデータセットの場合は、ソートアルゴリズムは本当に重要ではありません。人々は、非常に大きなデータベースのための最良のソートアルゴリズムであることを心配していますが、小さなNでは、クイックソート、ヒープソート、基数ソート、シェルソート、最適化バブルソート、最適化されていないバブルソート、少なくともCPU上はそれほど重要ではありません。
GPUはSIMDデバイスであるため、各カーネルにロックステップで同じ操作を実行させたいと考えています。計算は安いですが、ブランチが高価で、データ依存のブランチでは、各カーネルが異なる方法で分岐するため、非常に、非常に、非常に高価です。
ソートするデータセットが各カーネルにあり、ソートするデータの数はデータに依存し、カーネルごとに異なる番号である可能性があります。それぞれのカーネルがまったく同じような並べ替えを実行するように、以下のようなものがあります：
擬似コード（私は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]);
}
}
とてもいいです。これはまさに私が探していたものです。データ依存のブランチの短所についての参考資料はありますか？ – shoosh
私は頭の上からの参照がありません。 BTWは、クイックソートがGPUで動作しない別の理由は、再帰をサポートしていないということです。 –
再帰は単なるループです。したがって、ほぼすべての再帰のケースをWhile/Forループとして書き直すことができます。 –
この記事を見たことがありますか？ https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html
クイックソートアルゴリズムやクイックソートアルゴリズムを探しているとは確信していませんでした。この記事のアルゴリズムは、マージソートを使用しています...
私はGPUのプログラミングについて知りませんでした。
クイックソートではなく、ヒープソートを使用したいと思うのは、上位のいくつかの値だけを調べる必要があるからです。ヒープはO(n)の時間に構築できますが、最も高い値を得るのはlog(n)です。したがって、必要な値の数が要素の合計数よりも大幅に少ない場合、パフォーマンスを得ることができます。
GPUがクイックソートでうまくいくのだろうか... –