0

アプリケーションは、list1 と list2 などの 2 つの整数の並べ替えられたリストを交差させます (交差を設定します)。

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

P-ary 探索と呼ばれるアプローチがあることは知っていますが、私の仕事は二分探索のスレッドの発散を減らすことです。また、スラストというライブラリがあることは知っていますが、発散を減らす試みはないようです。

4

2 に答える 2

2

両方のリストがソートされている場合、二分探索は最適なアルゴリズムではありません。二分探索では が得られますがO(n lg n)、マージのようなアルゴリズムを実行し、交点のみを取得すると、 になりますO(n)。

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

これを行うには、klist1 の等間隔の要素を選択し、二分探索を使用して list2 でそれらを見つけます。同様に、klist2 の等間隔の要素を選択し、list1 でそれらを見つけます。各リストには2k範囲があり、各範囲には最大でもN/k要素があります。これらの範囲を平行に交差させます。(必要なスレッド数の半分に設定kします。)

于 2012-05-01T05:11:43.673 に答える
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;

警告: このコードは、範囲外のメモリへのアクセスによって例外を生成する可能性があります

于 2012-09-29T17:48:19.800 に答える