1

C++ AMP を使用してフィボナッチを計算しようとしていますが、各数値は前の 2 つに依存します。したがって、コードは次のようになります。

for (int i = 0; i < size; i++){
    a[i] = 0;
    if (i == 0 || i == 1) a[i] = 1;
}
array_view<int, 1> A(size, a);
parallel_for_each(
    A.extent,
    [=](index<1> idx)restrict(amp){
        if( A[idx] == 0 ){
             while (A[idx - 2] == 0); 
             while (A[idx - 1] == 0);
             A[idx] = A[idx - 1] + A[idx - 2];
        }
 });

3 番目のスレッド ( idx[0] == 2 ) は、次の行で待機します。

A[idx] = A[idx - 1] + A[idx - 2];

ゼロ以外の数値には設定されないため、後続のすべてのスレッドは単純にループ内でスタックします。

抜け道はありますか？

4

1 に答える 1

2

上記のコメンテーターが指摘したように、フィボナッチは GPU での並列化の最悪の候補の 1 つです。ここで期待できる最善の方法は、同期プリミティブを使用して操作を次々に実行し、すべてのスレッドをシリアル化することです!

C++ AMP ランタイムは、GPU でスレッド タイルをスケジュールする順序について保証しません。シリーズの上半分を最初に計算するタイルをスケジュールすることを決定したとしますか? 下位のものは実行されず、カーネルがハングします。C++ AMPには に相当するものがないwait()ため、スレッドはブロックされず、ブロックされたスレッド/タイルを交換して他のスレッドを実行する必要があることをランタイムに示しません。基本的whileに の代わりに使用していwaitます。メモリの読み取りと書き込みが同時に行われるため、競合状態が発生するため、これは CPU または GPU のいずれかで悪い考えです。

ただし、あなたの質問は、一般的なスレッド同期のコンテキストでは有効です。C++ AMP には、基本的に 2 つのメカニズムがあります。バリアとアトミック操作。

theData次の例は、atomic を使用して、配列内の 0.999 より大きい乱数の数をカウントする方法を示しています。配列は 0.0 から 1.0 の間の乱数で初期化されるため、この数は非常に小さいです。つまり、アトミック操作でのブロックのコストが発生する頻度はごくわずかです。

array_view<float, 1> theDataView(int(theData.size()), theData);
int exceptionalOccurrences = 0;
array_view<int> count(1, &exceptionalOccurrences);
parallel_for_each(theDataView.extent, [=] (index<1> idx) restrict(amp)
{
    if (theDataView[idx] >= 0.999f) // Exceptional occurrence.
    {
        atomic_fetch_inc(&count(0));
    }
    theDataView[idx] = // Update the value...
});
count.synchronize();

これはアトミックの使用方法を示していますが、アトミックの使用を完全に回避するために (マップおよび) リダクション操作を使用して、この問題をより効率的に解決します。

次の例では、バリアを使用して、タイル内のスレッド間でメモリ アクセスを同期します。バリアの前のコードの前半では、すべてのスレッドを使用してデータを tile_static メモリにロードしてから、バリアを使用して、すべてのスレッドがデータにアクセスする前にすべてのデータがロードされるまで待機させます。

array<float, 2> inData(1000, 1000);
array<float, 2> outData(1000, 1000);

parallel_for_each(view, 
    inData.extent.tile<tileSize, tileSize>(), [=, &inData, &outData]
    (tiled_index<tileSize, tileSize> tidx) restrict(amp)
    { 
        tile_static float localData[tileSize][tileSize];
        localData[tidx.local[1]][tidx.local[0]] = inData[tidx.global];

        tidx.barrier.wait();
        index<2> outIdx(index<2>(tidx.tile_origin[1], 
                        tidx.tile_origin[0]) + tidx.local);
        outData[outIdx] = localData[tidx.local[0]][tidx.local[1]];
    });

したがって、アトミックを使用すると、すべてのスレッド間でメモリを安全に共有できますが、同期のオーバーヘッドが大きくなります。アトミックはノンブロッキングです。バリアを使用すると、ブロックしているタイル内のスレッド間で実行とメモリ アクセスを同期できます。この 2 つを組み合わせた C++AMP の機能はなく、GPU 上のすべてのスレッドでブロックすることはできません。

これは、プログラミング モデルの基本的な前提です。すべてのスレッドは最小限の同期の対象となり、スレッド間の依存関係がほとんどまたはまったくない状態で実行できます。このほとんどは、私のC++ AMP ブックの最適化とパフォーマンスに関する章で説明されています。

于 2013-11-03T22:04:18.680 に答える