优化字节操作CUDA

Question

优化字节操作CUDA

use*_*912 1 c++ optimization byte cuda absolute-value

我对Cuda相对较新,我正在尝试编写一个内核,用于计算查询向量和大型向量数据库之间的绝对差值之和.两者的元素必须是8位无符号整数.我已经将我的内核基于nvidias示例并行缩减内核,我也读过这个帖子.

我只得到大约5GB/s,这比快速CPU好多了,甚至没有接近我的DDR5 GT640的理论带宽大约80GB/s.

我的数据集包含1024字节的查询向量,100,000 x 1024字节的数据库

我有100,000个128个线程的块,如果每个块访问相同的1024字节query_vector,那会导致更糟糕的性能吗？由于每个块都访问相同的内存位置.

blockSize和共享内存都设置为128和128*sizeof(int),128是#define'd为THREADS_PER_BLOCK

template<UINT blockSize> __global__ void reduction_sum_abs( BYTE* query_vector, BYTE* db_vector, uint32_t* result )
{
    extern __shared__ UINT sum[]; 
    UINT db_linear_index = (blockIdx.y*gridDim.x) + blockIdx.x ; 
    UINT i = threadIdx.x; 

    sum[threadIdx.x] = 0; 

    int* p_q_int = reinterpret_cast<int*>(query_vector); 
    int* p_db_int = reinterpret_cast<int*>(db_vector); 

    while( i < VECTOR_SIZE/4 ) {

        /* memory transaction */
        int q_int = p_q_int[i]; 
        int db_int = p_db_int[db_linear_index*VECTOR_SIZE/4 + i]; 

        uchar4 a0 = *reinterpret_cast<uchar4*>(&q_int); 
        uchar4 b0 = *reinterpret_cast<uchar4*>(&db_int); 

        /* sum of absolute difference */ 
        sum[threadIdx.x] += abs( (int)a0.x - b0.x ); 
        sum[threadIdx.x] += abs( (int)a0.y - b0.y ); 
        sum[threadIdx.x] += abs( (int)a0.z - b0.z ); 
        sum[threadIdx.x] += abs( (int)a0.w - b0.w ); 

        i += THREADS_PER_BLOCK; 

    }

    __syncthreads(); 

    if ( blockSize >= 128 ) {
        if ( threadIdx.x < 64 ) { 
            sum[threadIdx.x] += sum[threadIdx.x + 64]; 
        }
    }

    /* reduce the final warp */
    if ( threadIdx.x < 32 ) {        
        if ( blockSize >= 64 ) { sum[threadIdx.x] += sum[threadIdx.x + 32]; } __syncthreads(); 

        if ( blockSize >= 32 ) { sum[threadIdx.x] += sum[threadIdx.x + 16]; } __syncthreads(); 

        if ( blockSize >= 16 ) { sum[threadIdx.x] += sum[threadIdx.x + 8 ]; } __syncthreads(); 

        if ( blockSize >= 8  ) { sum[threadIdx.x] += sum[threadIdx.x + 4 ]; } __syncthreads(); 

        if ( blockSize >= 4  ) { sum[threadIdx.x] += sum[threadIdx.x + 2 ]; } __syncthreads(); 

        if ( blockSize >= 2  ) { sum[threadIdx.x] += sum[threadIdx.x + 1 ]; } __syncthreads(); 

    }


    /* copy the sum back to global */
    if ( threadIdx.x == 0 ) {
        result[db_linear_index] = sum[0]; 
    }
}

Run Code Online (Sandbox Code Playgroud)

如果我使用4行代码运行内核并将实际的绝对差值计算注释掉,我可以得到大约4倍的带宽增加,显然它会导致错误的答案,但我相信至少很大一部分时间是在那里度过.

是否有可能以我访问字节的方式创建银行冲突？如果可以,我可以避免冲突？

我的用法reinterpret_cast是否正确？

有没有更好的方法进行8位无符号计算？

还有什么(我会假设很多,因为我是一个完整的新手)我可以做出优化吗？

谢谢

编辑:

我的机器规格如下:

Windows XP 2002 SP3

英特尔6600 2.40GHz

2GB内存

GT640 GDDR5 1gb

visual c ++ 2010 express

Answer 1

Rob*_*lla 7

对于像这样的问题,提供一个可以编译和运行的完整代码是很好的做法,而无需添加任何内容或更改任何内容.一般来说,SO期待这一点.由于您的问题也与性能有关,因此您还应在完整的代码中包含实际的时序测量方法.

固定错误:

您的代码中至少有2个错误,其中一个错误是@Jez已经指出的.在这个"部分减少"步骤之后:

if ( blockSize >= 128 ) {
    if ( threadIdx.x < 64 ) { 
        sum[threadIdx.x] += sum[threadIdx.x + 64]; 
    }
}

Run Code Online (Sandbox Code Playgroud)

__syncthreads();在继续进行其余工作之前我们需要一个.通过上述更改,我能够让您的内核生成与我的天真主机实现相匹配的可重复结果.此外,由于你有这样的条件代码,它不会在threadblock中评估相同的代码:

if ( threadIdx.x < 32 ) {

Run Code Online (Sandbox Code Playgroud)

__syncthreads()在条件代码块中包含一个语句是 违法的:

  if ( blockSize >= 64 ) { sum[threadIdx.x] += sum[threadIdx.x + 32]; } __syncthreads();

Run Code Online (Sandbox Code Playgroud)

(同样对于后续行做同样的事情).所以建议修复它.有几种方法可以解决这个问题,其中一种方法是切换到使用volatile类型指针来引用共享数据.由于我们现在在warp中运行,因此volatile限定符会强制编译器执行我们想要的操作:

volatile UINT *vsum = sum;
if ( threadIdx.x < 32 ) {        
    if ( blockSize >= 64 ) vsum[threadIdx.x] += vsum[threadIdx.x + 32];
    if ( blockSize >= 32 ) vsum[threadIdx.x] += vsum[threadIdx.x + 16]; 
    if ( blockSize >= 16 ) vsum[threadIdx.x] += vsum[threadIdx.x + 8 ];
    if ( blockSize >= 8  ) vsum[threadIdx.x] += vsum[threadIdx.x + 4 ];
    if ( blockSize >= 4  ) vsum[threadIdx.x] += vsum[threadIdx.x + 2 ]; 
    if ( blockSize >= 2  ) vsum[threadIdx.x] += vsum[threadIdx.x + 1 ];
}

Run Code Online (Sandbox Code Playgroud)

CUDA 并行缩减示例代码和相关的pdf可能是一个很好的审查.

时间/完整分析:

我碰巧有一台GT 640,cc3.5设备.当我运行bandwidthTest它时,我观察到大约32GB/s的设备到设备传输.当设备内核访问设备存储器时,该数字代表可实现带宽的合理近似上限.此外,当我添加cudaEvent基于时序并围绕您显示的示例代码构建示例代码时,使用模拟数据,我观察到吞吐量约为16GB/s,而不是5GB/s.因此,您的实际测量技术在这里将是有用的信息(实际上,可能需要一个完整的代码来分析我的内核时序和时间之间的差异).

问题仍然存在,是否可以改进？(假设~32GB/s是近似上限).

你的问题:

是否有可能以我访问字节的方式创建银行冲突？如果可以,我可以避免冲突？

由于您的内核实际上将字节有效地作为32位数量(uchar4)加载,并且每个线程正在加载相邻的连续32位数量,因此我不认为您的内核存在任何存储库冲突访问问题.

我对reinterpret_cast的使用是否正确？

是的,它似乎是正确的(下面的示例代码,使用上面提到的修复,验证您的内核生成的结果与一个朴素的主机函数实现相匹配.)

有没有更好的方法进行8位无符号计算？

在这种情况下,正如@njuffa所指出的那样,SIMD内在函数可以用一条指令来处理这个问题(__vsadu4()参见下面的示例代码).

还有什么(我会假设很多,因为我是一个完整的新手)我可以做出优化吗？

使用@MichalHosala提出的cc3.0 warp-shuffle约简方法
利用SIMD instrinsic __vsadu4()来简化和改进@njuffa提出的字节数量的处理.
将数据库矢量数据重新组织为列主存储.这允许我们省去普通的并行缩减方法(即使如第1项中所述)并切换到直接的for循环读取内核,一个线程计算整个矢量比较.这允许我们的内核在这种情况下达到设备的大约内存带宽(cc3.5 GT640).

下面是代码和示例运行,显示了3个实现:您的原始实现(加上上面命名的"修复"以使其产生正确的结果),一个opt1内核修改您的内容,包括上面列表中的项目1和2,和opt2内核用上面列表中的2和3替换你的内核.根据我的测量,你的内核达到了16GB/s,大约是GT640带宽的一半,opt1内核以大约24GB/s的速度运行(增加的内容大致相当于上面的第1和第2项),以及opt2内核通过数据重组,以大约全带宽(36GB/s)运行.

$ cat t574.cu
#include <stdio.h>
#include <stdlib.h>
#define THREADS_PER_BLOCK 128
#define VECTOR_SIZE 1024
#define NUM_DB_VEC 100000

typedef unsigned char BYTE;
typedef unsigned int UINT;
typedef unsigned int uint32_t;


template<UINT blockSize> __global__ void reduction_sum_abs( BYTE* query_vector, BYTE* db_vector, uint32_t* result )
{
    extern __shared__ UINT sum[];
    UINT db_linear_index = (blockIdx.y*gridDim.x) + blockIdx.x ;
    UINT i = threadIdx.x;

    sum[threadIdx.x] = 0;

    int* p_q_int = reinterpret_cast<int*>(query_vector);
    int* p_db_int = reinterpret_cast<int*>(db_vector);

    while( i < VECTOR_SIZE/4 ) {

        /* memory transaction */
        int q_int = p_q_int[i];
        int db_int = p_db_int[db_linear_index*VECTOR_SIZE/4 + i];

        uchar4 a0 = *reinterpret_cast<uchar4*>(&q_int);
        uchar4 b0 = *reinterpret_cast<uchar4*>(&db_int);

        /* sum of absolute difference */
        sum[threadIdx.x] += abs( (int)a0.x - b0.x );
        sum[threadIdx.x] += abs( (int)a0.y - b0.y );
        sum[threadIdx.x] += abs( (int)a0.z - b0.z );
        sum[threadIdx.x] += abs( (int)a0.w - b0.w );

        i += THREADS_PER_BLOCK;

    }

    __syncthreads();

    if ( blockSize >= 128 ) {
        if ( threadIdx.x < 64 ) {
            sum[threadIdx.x] += sum[threadIdx.x + 64];
        }
    }
    __syncthreads(); // **
    /* reduce the final warp */
    if ( threadIdx.x < 32 ) {
        if ( blockSize >= 64 ) { sum[threadIdx.x] += sum[threadIdx.x + 32]; } __syncthreads();

        if ( blockSize >= 32 ) { sum[threadIdx.x] += sum[threadIdx.x + 16]; } __syncthreads();

        if ( blockSize >= 16 ) { sum[threadIdx.x] += sum[threadIdx.x + 8 ]; } __syncthreads();

        if ( blockSize >= 8  ) { sum[threadIdx.x] += sum[threadIdx.x + 4 ]; } __syncthreads();

        if ( blockSize >= 4  ) { sum[threadIdx.x] += sum[threadIdx.x + 2 ]; } __syncthreads();

        if ( blockSize >= 2  ) { sum[threadIdx.x] += sum[threadIdx.x + 1 ]; } __syncthreads();

    }


    /* copy the sum back to global */
    if ( threadIdx.x == 0 ) {
        result[db_linear_index] = sum[0];
    }
}

__global__ void reduction_sum_abs_opt1( BYTE* query_vector, BYTE* db_vector, uint32_t* result )
{
  __shared__ UINT sum[THREADS_PER_BLOCK];
  UINT db_linear_index = (blockIdx.y*gridDim.x) + blockIdx.x ;
  UINT i = threadIdx.x;

  sum[threadIdx.x] = 0;

  UINT* p_q_int = reinterpret_cast<UINT*>(query_vector);
  UINT* p_db_int = reinterpret_cast<UINT*>(db_vector);

  while( i < VECTOR_SIZE/4 ) {

    /* memory transaction */
    UINT q_int = p_q_int[i];
    UINT db_int = p_db_int[db_linear_index*VECTOR_SIZE/4 + i];
    sum[threadIdx.x] += __vsadu4(q_int, db_int);

    i += THREADS_PER_BLOCK;

    }
  __syncthreads();
  // this reduction assumes THREADS_PER_BLOCK = 128
  if (threadIdx.x < 64) sum[threadIdx.x] += sum[threadIdx.x+64];
  __syncthreads();

  if ( threadIdx.x < 32 ) {
    unsigned localSum = sum[threadIdx.x] + sum[threadIdx.x + 32];
    for (int i = 16; i >= 1; i /= 2)
      localSum = localSum + __shfl_xor(localSum, i);
    if (threadIdx.x == 0) result[db_linear_index] = localSum;
    }
}

__global__ void reduction_sum_abs_opt2( BYTE* query_vector, UINT* db_vector_cm, uint32_t* result)
{
  __shared__ UINT qv[VECTOR_SIZE/4];
  if (threadIdx.x < VECTOR_SIZE/4) qv[threadIdx.x] = *(reinterpret_cast<UINT *>(query_vector) + threadIdx.x);
  __syncthreads();
  int idx = threadIdx.x + blockDim.x*blockIdx.x;
  while (idx < NUM_DB_VEC){
    UINT sum = 0;
    for (int i = 0; i < VECTOR_SIZE/4; i++)
      sum += __vsadu4(qv[i], db_vector_cm[(i*NUM_DB_VEC)+idx]);
    result[idx] = sum;
    idx += gridDim.x*blockDim.x;}
}

unsigned long compute_host_result(BYTE *qvec, BYTE *db_vec){

  unsigned long temp = 0;
  for (int i =0; i < NUM_DB_VEC; i++)
    for (int j = 0; j < VECTOR_SIZE; j++)
      temp += (unsigned long) abs((int)qvec[j] - (int)db_vec[(i*VECTOR_SIZE)+j]);
  return temp;
}

int main(){

  float et;
  cudaEvent_t start, stop;
  BYTE *h_qvec, *d_qvec, *h_db_vec, *d_db_vec;
  uint32_t *h_res, *d_res;
  h_qvec =   (BYTE *)malloc(VECTOR_SIZE*sizeof(BYTE));
  h_db_vec = (BYTE *)malloc(VECTOR_SIZE*NUM_DB_VEC*sizeof(BYTE));
  h_res = (uint32_t *)malloc(NUM_DB_VEC*sizeof(uint32_t));
  for (int i = 0; i < VECTOR_SIZE; i++){
    h_qvec[i] = rand()%256;
    for (int j = 0; j < NUM_DB_VEC; j++) h_db_vec[(j*VECTOR_SIZE)+i] = rand()%256;}
  cudaMalloc(&d_qvec, VECTOR_SIZE*sizeof(BYTE));
  cudaMalloc(&d_db_vec, VECTOR_SIZE*NUM_DB_VEC*sizeof(BYTE));
  cudaMalloc(&d_res, NUM_DB_VEC*sizeof(uint32_t));
  cudaMemcpy(d_qvec, h_qvec, VECTOR_SIZE*sizeof(BYTE), cudaMemcpyHostToDevice);
  cudaMemcpy(d_db_vec, h_db_vec, VECTOR_SIZE*NUM_DB_VEC*sizeof(BYTE), cudaMemcpyHostToDevice);
  cudaEventCreate(&start); cudaEventCreate(&stop);

// initial run

  cudaMemset(d_res, 0, NUM_DB_VEC*sizeof(uint32_t));
  cudaEventRecord(start);
  reduction_sum_abs<THREADS_PER_BLOCK><<<NUM_DB_VEC, THREADS_PER_BLOCK, THREADS_PER_BLOCK*sizeof(int)>>>(d_qvec, d_db_vec, d_res);
  cudaEventRecord(stop);
  cudaDeviceSynchronize();
  cudaEventSynchronize(stop);
  cudaEventElapsedTime(&et, start, stop);
  cudaMemcpy(h_res, d_res, NUM_DB_VEC*sizeof(uint32_t), cudaMemcpyDeviceToHost);
  unsigned long h_result = 0;
  for (int i = 0; i < NUM_DB_VEC; i++) h_result += h_res[i];
  printf("1: et: %.2fms, bw: %.2fGB/s\n", et, (NUM_DB_VEC*VECTOR_SIZE)/(et*1000000));
  if (h_result == compute_host_result(h_qvec, h_db_vec)) printf("Success!\n");
  else printf("1: mismatch!\n");

// optimized kernel 1
  cudaMemset(d_res, 0, NUM_DB_VEC*sizeof(uint32_t));
  cudaEventRecord(start);
  reduction_sum_abs_opt1<<<NUM_DB_VEC, THREADS_PER_BLOCK>>>(d_qvec, d_db_vec, d_res);
  cudaEventRecord(stop);
  cudaDeviceSynchronize();
  cudaEventSynchronize(stop);
  cudaEventElapsedTime(&et, start, stop);
  cudaMemcpy(h_res, d_res, NUM_DB_VEC*sizeof(uint32_t), cudaMemcpyDeviceToHost);
  h_result = 0;
  for (int i = 0; i < NUM_DB_VEC; i++) h_result += h_res[i];
  printf("2: et: %.2fms, bw: %.2fGB/s\n", et, (NUM_DB_VEC*VECTOR_SIZE)/(et*1000000));
  if(h_result == compute_host_result(h_qvec, h_db_vec)) printf("Success!\n");
  else printf("2: mismatch!\n");

// convert db_vec to column-major storage for optimized kernel 2

  UINT *h_db_vec_cm, *d_db_vec_cm;
  h_db_vec_cm = (UINT *)malloc(NUM_DB_VEC*(VECTOR_SIZE/4)*sizeof(UINT));
  cudaMalloc(&d_db_vec_cm, NUM_DB_VEC*(VECTOR_SIZE/4)*sizeof(UINT));
  for (int i = 0; i < NUM_DB_VEC; i++)
    for (int j = 0; j < VECTOR_SIZE/4; j++)
      h_db_vec_cm[(j*NUM_DB_VEC)+i] = *(reinterpret_cast<UINT *>(h_db_vec + (i*VECTOR_SIZE))+j);
  cudaMemcpy(d_db_vec_cm, h_db_vec_cm, NUM_DB_VEC*(VECTOR_SIZE/4)*sizeof(UINT), cudaMemcpyHostToDevice);
  cudaMemset(d_res, 0, NUM_DB_VEC*sizeof(uint32_t));
  cudaEventRecord(start);
  reduction_sum_abs_opt2<<<64, 512>>>(d_qvec, d_db_vec_cm, d_res);
  cudaEventRecord(stop);
  cudaDeviceSynchronize();
  cudaEventSynchronize(stop);
  cudaEventElapsedTime(&et, start, stop);
  cudaMemcpy(h_res, d_res, NUM_DB_VEC*sizeof(uint32_t), cudaMemcpyDeviceToHost);
  h_result = 0;
  for (int i = 0; i < NUM_DB_VEC; i++) h_result += h_res[i];
  printf("3: et: %.2fms, bw: %.2fGB/s\n", et, (NUM_DB_VEC*VECTOR_SIZE)/(et*1000000));
  if(h_result == compute_host_result(h_qvec, h_db_vec)) printf("Success!\n");
  else printf("3: mismatch!\n");

  return 0;
}

$ nvcc -O3 -arch=sm_35 -o t574 t574.cu
$ ./run35 t574
1: et: 6.34ms, bw: 16.14GB/s
Success!
2: et: 4.16ms, bw: 24.61GB/s
Success!
3: et: 2.83ms, bw: 36.19GB/s
Success!
$

Run Code Online (Sandbox Code Playgroud)

几点说明:

上面的代码,特别是你的内核,必须编译为cc3.0或更高版本,就像我设置测试用例一样.这是因为我在单个1D网格中创建了100,000个块,因此我们无法在cc2.0设备上按原样运行它.
对于opt2内核,通过修改网格和块参数,可能会进行一些额外的轻微调整,特别是如果在不同的设备上运行.我将这些设置为64和512,并且这些值不应该是关键的(尽管块应该是VECTOR_SIZE/4个线程或更大),因为算法使用网格跨越循环来覆盖整个向量集.GT640只有2个SM,因此在这种情况下,64个线程块足以让设备保持忙碌状态(可能甚至32个就可以).您可能希望修改这些以在较大的设备上获得最大性能.

归档时间：	11 年，11 月前
查看次数：	1722 次
最近记录：	11 年，11 月前