2016-10-02 7 views
0

サイズ2^Lの未ソート1D配列の特定の値を検索するためにGPUを使用したいとします(Lは正の偶数です)。配列内のすべての値はユニークです。 パラレルリダクション(ピンポン技術)を使用して検索結果を1つの番号に減らすことはできますか?ピンポン​​手法を使用して1D配列の値を検索しますか?

私の直感はそれが可能であると言いますが、私はどのように起動するのか分かりません。誰か助けてくれますか?私は数日間それに固執しています!どんな提案も歓迎です、ありがとう!

+0

なぜ還元を使用しますか?あなたは何か、または最初のもの、またはそれらのすべてを見つける必要がありますか? – Dimaleks

+0

@Dimaleks:1st one –

+0

多くの出現が予想されますか?つまり、通常のシナリオでは、10要素ごとに1回、つまり10,000になるようになります。 – Dimaleks

答えて

1

検索された値が見つかったかどうかによって、スレッドごとに0または1Dインデックス+ 1を出力バッファに書き込む場合は、prefix sumを実行して、(1Dインデックス+1 O(n)の代わりにO(log n)の出力バッファに検索された値に対応します。これは単純に全体を反復処理する代わりの方法です。

関連する問題