CUDAを使用したバイナリ検索の分岐の分岐を減らす方法

Question

アプリケーションは2つのソートされた整数リスト（交差点を設定）、たとえばlist1とlist2を交差させることです。

list1の各要素にはGPUスレッドが割り当てられ、リスト2に表示されているかどうかを確認するためにバイナリ検索が行われます。このアプリケーションでは、スレッドの発散が膨大になることは容易にわかります。私はスレッドの発散を減らすための良いアプローチがあるのだろうかと思います。私はこのアプリケーションを実装するためにCUDAを使用しています。

私はP-ary検索と呼ばれるアプローチがあることを知っていますが、私の仕事はバイナリ検索のスレッドの相違を減らすことです。また推力と呼ばれる図書館があることは知っていますが、発散を減らそうとする試みはないようです。

Answer 1

両方のリストがソートされている場合、バイナリ検索は実行可能な最良のアルゴリズムではありません。バイナリ検索ではO(n lg n)と表示されますが、交差点を取るだけでマージのようなアルゴリズムを実行すると、O(n)となります。

これは、GPUを使用するための愚かなアルゴリズムです。私が見る唯一のケースは、GPUでデータを生成したばかりです。その場合は、問題を小さな束の束に分割し、それぞれにスレッドを割り当てる必要があります。

これを実行するには、kの等間隔のlist1要素を選択し、list2でバイナリ検索を使用して検索します。同様に、リスト2の等間隔の要素をkと指定し、list1でそれらを見つけます。それぞれのリストには2kの範囲があり、各範囲には最大でN/kの要素があります。これらの範囲を並行して交差させます。 （あなたが欲しいスレッドの数の半分であることをkを設定してください。）

Answer 2

でとりうるコード：

bool end = false; 
    bool found = false; 

    while(!end && !found) 
    { 
      int diff  = max-min; 
      int middle  = min + (diff/2); 

      end    = diff < 1; 
      found   = element[middle] == element; 
      if (index < elements[middle]) 
        max = middle-1; 
      else //(index > elements[middle+1]) 
        min = middle + 2; 
    } 
    return found; 

警告：このコードは