7

X と Y の 2 つの 3D 行列でスライディング ウィンドウ計算を実装する Python コードを次に示します。

import numpy

def sliding_dot( X,Y ) :

    assert X.ndim == Y.ndim == 3
    iw,ih,id = X.shape
    fw,fh,fd = Y.shape

    assert id == fd
    assert fw < iw and fh < ih

    ow,oh = iw-fw+1,ih-fh+1
    out = numpy.zeros( [ow,oh] )

    for x in xrange(ow) :
        for y in xrange(oh) :
            window = X[x:x+fw,y:y+fh,:]
            out[x,y] = numpy.dot( window.flatten(),Y.flatten() )

    return out

#################    

A_dims = (640,480,32)
B_dims = (6,6,32)

A = numpy.random.rand(*A_dims)
B = numpy.random.rand(*B_dims)

sliding_dot(A,B)

一般に、Y は 1 次元と 2 次元では常に X よりもはるかに小さくなりますが、3 次元では等しくなります。

numpy.dot() を Y とウィンドウの任意の関数に置き換えることができることに注意してください。これは、Y が X の 1 番目と 2 番目の次元に沿ってのみスライドするという点で、畳み込みとは少し異なります。CUDA を使用して、この種のスライディング ウィンドウ計算を効率的に実装するための効果的な戦略を探しています。誰か私に方向性を教えてくれませんか?乾杯!

更新:以下の私の回答で、他のユーザーの助けを借りて最適化プロセスを進めているのを見ることができます。

4

4 に答える 4

4

必要なほぼすべての操作に対応できる「一般化された」実装を設計しようとすると、CUDA のようなアーキテクチャでは大きなトレードオフになります。典型的なリダクション操作である具体的な内積の例では、これは非常に便利な実装です。

__constant__ int ldaX[3];
__constant__ int ldaY[3];
__constant__ int dimX[3];
__constant__ int dimY[3];

template<typename real,int blocksize>
__global__ void sliding_k(const real *X, const real *Y, real *out)
{
    __shared__ volatile real buffer[blocksize];

    int tid = threadIdx.x;
    int gid = blockIdx.x * gridDim.y + blockIdx.y;

    real value = (real)0;
    int xpos = (blockIdx.y * ldaX[2]) + (blockIdx.x * ldaX[1]);
    int ypos = 0;
    for(int i=0; i<dimY[0]; i++) {
        for(int jk=tid; jk<ldaY[1]; jk+=blocksize) {
            value += X[xpos+jk] * Y[ypos+jk];
        }
        xpos += ldaX[1];
        ypos += ldaY[1];
    }

    buffer[tid] = value;
    __syncthreads();

# pragma unroll
    for(int i=(tid+32); ((tid<32)&&(i<blocksize)); i+=32)
        buffer[tid] += buffer[i];

    if (tid < 16) buffer[tid] += buffer[tid + 16];
    if (tid < 8)  buffer[tid] += buffer[tid + 8];
    if (tid < 4)  buffer[tid] += buffer[tid + 4];
    if (tid < 2)  buffer[tid] += buffer[tid + 2];
    if (tid == 0) out[gid] = buffer[0] + buffer[1];
}

内積が使用する浮動小数点の乗算加算/加算演算を任意の種類のリダクション演算子に置き換えることができ、コードは正常に動作するはずです。各ウィンドウ計算は、1 つのブロックによって実行されます。このウィンドウ サイズでウィンドウごとにブロックを正当化するのに十分な並列作業があります。これにより、結合されたグローバル メモリ アクセスが可能になり、Fermi カードでは大量の L1 キャッシュ ヒットが可能になります。

ここでは、ソース配列の 3 番目の次元とウィンドウ配列が等しいという仮定を 1 つだけコードに組み込みました。これにより、内側の 2 つのループを 1 つの操作に "融合" できます。これは、それらが共通のメモリ レイアウトを共有するためです。PyCUDA で記述されたホスト コードを使用して、参照コードの改善されたバージョンを使用して Python でテスト ハーネスを実行すると、次のようになります。

In [15]: %timeit -n3 -r3 out2=sliding_cuda(A,B)
3 loops, best of 3: 49.8 ms per loop

In [16]: %timeit -n3 -r3 out=sliding_dot(A,B)
3 loops, best of 3: 2.18 s per loop

In [17]: (numpy.abs(out2-out)/numpy.abs(out)).max()
Out[17]: 4.2921323635558404e-15

635x475 2D グリッドで 64 個のスレッド ブロックを使用して、GTX470 を搭載した 3GHz Phenom II で実行した場合。モジュールのロード、セットアップ、およびページング可能なホスト メモリ割り当てを使用したメモリ転送を含め、約 50 倍高速化します。カーネル自体は、メモリ転送とセットアップのオーバーヘッドを除いて、Python よりも約 100 倍高速です。これは倍精度バージョンであることに注意してください。Python はデフォルトで倍精度浮動小数点演算を使用します。

于 2011-10-11T10:25:25.577 に答える
1

さて、ここにいくつかの考えがあります:

の最大 640*480 反復を実行しnumpy.dot、それ自体が 6*6*32 要素を処理します。ドット積を並列化する価値はほとんどありません。192 個の並列スレッドは GPU には不十分であり、CUDA の削減は追加の問題です。したがって、IMO、タスクを並列化する最良の方法は、出力配列の 1 つの要素を各スレッドに割り当てることです。

メモリについて:出力配列はグローバルメモリになります。選択肢はあまりありません。入力データの場合、A隣接するスレッドが隣接する要素にアクセスするため、テクスチャ メモリには非常に適しているように見えます。別の方法として、共有メモリに手動で「キャッシュ」することもできますが、この場合、単純にテクスチャを使用するよりもあまり有利には見えません。の場合B、共有メモリは良くありません。ドット積を計算すると、ハーフワープのすべてのスレッドが同じ B の要素にアクセスするため、バンクの競合が発生するためです (異なるスレッドの異なる要素から合計を開始できますが、これも ( ) 有望に見えません)。したがって、選択はテクスチャまたは定数のいずれかです。(a) 定数メモリは、デバイス上のすべてのスレッドによってアクセスされるデータに適しているため、(b) テクスチャ キャッシュを汚染しないため、私は定数に投票します。

上記は単なる私の推測であり、実際に優れたパフォーマンスを達成するには、さまざまなバリアントを試してみてください...

単純な実装に関する更新

for (int Yi = 0; Yi < Ydims[0]; Yi++ )

ここでは、反復ごとにグローバル メモリにアクセスします。それは大きなパフォーマンスキラーです。3 つの次元があるため、int *Ydimsint3 Ydims( と についても同じXdims)に置き換えたほうがよいでしょうoutdims

out[out_indx] += X[X_indx]*Y[Y_indx];

繰り返しますが、非常に悪い考えです。レジスタ変数を作成し、それを使用してすべての操作を行います。カーネルの最後に 1 回だけグローバル配列に書き込みます。

これらの最適化は、最初に行うべきことです。2 つ目は、ユーザーXY3D テクスチャを作成することです。これにより、それらへのアクセスがキャッシュされます。この後、CUDAはCPUよりも優れていると思います。

さらなる最適化については、CUDA C Best Practices Guideをお読みください。読む必要があり、効率的な GPU コードを作成する方法についてより良いアイデアを得ることができます (現在、あなたの実装はあまりにも素朴です)。

于 2011-10-05T21:47:57.270 に答える
0

v0.1 - 素朴な実装

これを機能させるための私の最初の素朴な試みは次のとおりです。

__global__ void sliding_dot(float *out, int *outdims, float *X, int *Xdims, float *Y, int *Ydims )
{
    int i = threadIdx.x + blockDim.x * blockIdx.x;
    int j = threadIdx.y + blockDim.y * blockIdx.y;
    int Y_indx = 0;
    int X_indx = 0;
    if ( i < outdims[0] & j < outdims[1] )
    {
        int out_indx = j + i*outdims[1];
        for (int Yi = 0; Yi < Ydims[0]; Yi++ )
        {
            for (int Yj = 0; Yj < Ydims[1]; Yj++ )
            {
                for (int k = 0; k < Ydims[2]; k++ )
                {
                    Y_indx = k + Yj*    Ydims[2] + Yi*    Ydims[2]*Ydims[1];
                    X_indx = k + (j+Yj)*Xdims[2] + (i+Yi)*Xdims[2]*Xdims[1];
                    out[out_indx] += X[X_indx]*Y[Y_indx];
                }
            }
        }
    }
}

これまでのところ、結果は望ましくありません。ブロック サイズ (32,32,1) とグリッド ディメンション p,q が p*32 >= outdims[0] および q*32 >= outdims[1] となるように選択された場合:

method=[ sliding_dot ] gputime=[ 7013.280 ] cputime=[ 18.000 ] occupancy=[ 0.667 ] 
method=[ sliding_dot ] gputime=[ 6945.184 ] cputime=[ 7.000 ] occupancy=[ 0.667 ] 
method=[ sliding_dot ] gputime=[ 6990.816 ] cputime=[ 6.000 ] occupancy=[ 0.667 ] 
method=[ sliding_dot ] gputime=[ 6931.648 ] cputime=[ 6.000 ] occupancy=[ 0.667 ] 

v0.2 -texture<float,1>

私と同じように、みんながこれから多くのことを学んでくれることを願っています! 私は@alandの提案に従い、かなりのスピードアップを得ました:

texture<float,1> X;
texture<float,1> Y;

__global__ void dotconv(float *out, int2 outdims, int3 Xdims, int3 Ydims )
{
    int i = threadIdx.x + blockDim.x * blockIdx.x;
    int j = threadIdx.y + blockDim.y * blockIdx.y;

    if ( i < outdims.x & j < outdims.y )
    {
        int out_indx = j + i*outdims.y;
        float total = 0.0f;
        int X_indx = 0;
        int Y_indx = 0;
        for (int Yi=0; Yi<Ydims.x; Yi++ )
        {
            for (int Yj=0; Yj<Ydims.y; Yj++ )
            {
                for (int k=0; k<Ydims.z; k++ )
                {
                    Y_indx = k + Yj*    Ydims.z + Yi*    Ydims.z*Ydims.y;
                    X_indx = k + (j+Yj)*Xdims.z + (i+Yi)*Xdims.z*Xdims.y;
                    total += tex1Dfetch(X,X_indx)*tex1Dfetch(Y,Y_indx);
                }
            }
        }
        out[out_indx] = total;
    }
}

しかし、まだ CPU ほど速くは実行されていません。

method=[ dotconv ] gputime=[ 2224.928 ] cputime=[ 24.000 ] occupancy=[ 0.667 ] 
method=[ dotconv ] gputime=[ 2222.592 ] cputime=[ 7.000 ] occupancy=[ 0.667 ] 
method=[ dotconv ] gputime=[ 2225.216 ] cputime=[ 10.000 ] occupancy=[ 0.667 ] 
method=[ dotconv ] gputime=[ 2222.752 ] cputime=[ 10.000 ] occupancy=[ 0.667 ] 

v0.3 -texture<float,3>

texture<float,3,cudaReadModeElementType> X;
texture<float,3,cudaReadModeElementType> Y;

__global__ void dotconv(float *out, int2 outdims, int3 Xdims, int3 Ydims )
{
    int i = threadIdx.x + blockDim.x * blockIdx.x;
    int j = threadIdx.y + blockDim.y * blockIdx.y;
    if ( i < outdims.x & j < outdims.y )
    {
        int out_indx = j + i*outdims.y;
        float total = 0.0f;
        for (int Yi=0; Yi<Ydims.x; Yi++ )
        {
            for (int Yj=0; Yj<Ydims.y; Yj++ )
            {
                for (int k=0; k<Ydims.z; k++ )
                {
                    total += tex3D(X,k,j+Yj,i+Yi) * tex3D(Y,k,Yj,Yi);   
                }
            }
        }
        out[out_indx] = total;
    }
}

これは実際にはv0.2よりも少し遅いです

method=[ dotconv ] gputime=[ 2403.360 ] cputime=[ 35.000 ] occupancy=[ 0.667 ] 
method=[ dotconv ] gputime=[ 2392.160 ] cputime=[ 15.000 ] occupancy=[ 0.667 ] 
method=[ dotconv ] gputime=[ 2396.448 ] cputime=[ 15.000 ] occupancy=[ 0.667 ] 
method=[ dotconv ] gputime=[ 2398.880 ] cputime=[ 16.000 ] occupancy=[ 0.667 ] 

ご提案いただきありがとうございます。

于 2011-10-10T02:44:31.373 に答える
0

ストアの合計から読み取りを分離してみてください。

したがって、各カーネルには 3 つのセクションが必要です。

  1. テクスチャ メモリから読み取り、ブロック全体の共有メモリに保存

    __shared blockX[ Ydims.z ][ Ydims.y ][ Ydims.x ];
    __shared blockY[ Ydims.z ][ Ydims.y ][ Ydims.x ];
    // NOTE: MAKE EACH THREAD LOAD k ELEMENTs * 2 rather than each thread loading Ydims.X*Y*Z elements
    blockX[k][yj][yi] = ...
    blockY[k][yj][yi] = ...
    __syncthreads(); // <-- critical -- all threads in block must finish
    // reading from shared memory before any may use the values.
    
  2. #pragmaループを展開しますfor
    これにより、ILP が大幅に増加し、一定のループ サイズの分岐が大幅に少なくなります。

  3. 共有メモリ アクセスが適切にストライドされていることを確認してください。そうしないと、バンクの競合によってパフォーマンスが低下します。

于 2011-10-10T18:22:28.847 に答える