バイナリ検索を使用した並列マージソート

Question

Designing Efficient Sorting Algorithms for Manycore GPUsに記載されているCUDAでマージソートアルゴリズムを実装しようとしています。

中間レベルの場合と同様に、2つのソート済み配列（たとえばAとB）を1つの配列にマージするスレッドブロックを割り当てることを提案しました。また、配列Aのdata-a_iにスレッドを割り当て、バイナリ検索を使用してB配列上にそのスレッドの場所を見つけることを考えています。 B上のa_iの位置がjの場合、新しい配列上のa_iの位置は（i + j）

ですが、これを実装したとき（または試行したとき）には、上記の方法がうまくいかない。例えば、以下のようにマージされる必要がある2つの配列の場合、

と

（灰色一つに斜線）最初の配列に53見つけるなるように2番目の配列のそれぞれの位置は11であるため、最終配列の位置は（11 + 11 = 22）です。同様に青色で網掛けされた第1のアレイ上の53の位置は（11 + 12 = 23）である。

2番目の配列の53を取ると、その最終位置も（11 + 11 = 22）として与えられます。第1のアレイ上の灰色53と衝突する。

私の理解によれば、単純なバイナリ検索アルゴリズムを使用してこれら2つの配列をマージすることはできません。この競合を解決する既知の方法またはより簡単な方法はありますか？論文で

Answer 1

は、私が読んで：ソート順序AとBが与えられ

を、私たちはソート シーケンスC =マージ（A、B）を計算します。これらのシーケンスが十分に小さい場合、 のサイズはそれぞれt = 256個以下の要素のサイズであると言います。 を単一のt-スレッドブロックを使用してマージすることができます。要素ai∈Aの場合、 マージされたシーケンスCの要素aiの位置である 計算ランク（ai、C）のみが必要です。AとBの両方がソートされているので、 ランク（ai、C rank（ai、B）は、要素bj∈Bとbj < aiの単純に の数であり、バイナリ検索を使用して を効率的に計算する、i + rank（ai、B）です。 Bの要素は、明らかに同じ方法で で扱うことができます。

ランク（ai、B）を検索しているときは、バイナリ検索で重複を処理する必要があります。 BをBSTとすると、rank（ai、B）= j {bj < = ai} +1のmaxがうまくいくはずです。