CUDA蛮力乐趣

Question

我是CUDA新手，刚开始学习如何编程CUDA来解决这个问题。我喜欢一些关于我可以如何提高代码和GPU利用率的意见。运行GTX 980btw。

我创造了一个有趣的问题，需要266个玩家中的任何8个人组成一个团队。目标是在预算限制下(每个球员花费特定金额的钱)为球队获得最高的总平均分数(每个球员都有一个特定的平均分数)。有点像梦幻运动队的问题。

我想看看我能以多快的速度破解大量的组合(在这个阶段对优化算法并不真正感兴趣)。

我目前为玩家详细信息创建了数组。

    ifstream file("D:\\Players.txt");
    string content;
    while (file >> content){
        if (j == 0){
           name[i] = content;
        }
        else if (j == 1){
           price[i] = stoi(content);
        }
        else if (j == 2){
           avg[i] = stoi(content);
        }
        else if (j == 3){
           tot[i] = stoi(content);
        }
        j++;
        if (j == 4){ j = 0; i++; }
     }

然后生成8个数组，它们是嵌套的8个for循环的起始索引(之前生成了list.txt )。

    while (output >> content){ //33002854 number of rows row ind
      if (j == 0) pos[ind] = stoi(content);
      else if (j == 1) pos1[ind] = stoi(content);
      else if (j == 2) pos2[ind] = stoi(content);
      else if (j == 3) pos3[ind] = stoi(content);
      else if (j == 4) pos4[ind] = stoi(content);
      else if (j == 5) pos5[ind] = stoi(content);
      else if (j == 6) pos6[ind] = stoi(content);
      else if (j == 7) pos7[ind] = stoi(content);
      j++;
      if (j == 8){ j = 0; ind++; }
    }

然后将所有这些都传递给内核。每个线程首先从该数组读取它的起始点。

    for (q = 0; q < rowcount - 7; q++){
        if (stopper == 0) q = pos[x];
        for (w = q + 1; w < rowcount - 6; w++){
            if (stopper == 0) w = pos1[x];
            for (e = w + 1; e < rowcount - 5; e++){
               if (stopper == 0) e = pos2[x];
               for (r = e + 1; r < rowcount - 4; r++){
                  if (stopper == 0) r = pos3[x];
                  for (t = r + 1; t < rowcount - 3; t++){
                     if (stopper == 0) t = pos4[x];
                     for (y = t + 1; y < rowcount - 2; y++){
                        if (stopper == 0) y = pos5[x];
                           for (u = y + 1; u < rowcount - 1; u++){
                             if (stopper == 0) u = pos6[x];
                                for (i = u + 1; i < rowcount; i++){
                                if (stopper == 0) {
                                    i = pos7[x]; stopper = 1;
                                }

其中x= threadIdx.x，rowcount = 266。

如果你从一个线程开始到结束，总共大约有286,853,510,505,870个循环要完成。我通过对数据进行排序，在嵌套循环中增加了一些小技巧，以便在价格>预算时跳到下一个位置，而不是>预算。

然后评估循环和如果价格<预算和平均>当前最大平均保存循环索引，以便我可以获得球员姓名和平均得分，以便稍后与其他线程进行比较。

    for (i = u + 1; i < rowcount; i++){
        if (stopper == 0) {
            i = pos7[x]; stopper = 1;
        }

        p[0] = price[q] + price[w] + price[e] + price[r] + price[t] + price[y] + price[u] + price[i];
        if (p[0] < budget){
            a[0] = avg[q] + avg[w] + avg[e] + avg[r] + avg[t] + avg[y] + avg[u] + avg[i];
            if (a[0] > maxavg[x]){
                thread[x] = loopcounter;
                maxavg[x] = a[0];
            }
            loopcounter++;
        }
        else {
           loopcounter = loopcounter + rowcount - i;
           i = rowcount;
        }
        if (loopcounter >= count){return;}
    }

count = 16936750，这是每个线程之间的循环数。

将thread[]和maxavg[]传回主机，然后通过maxavgi执行一个for循环，以找到最高值并打印thread[]。

问题1

我很好奇这条线路有多安全

    thread[x] = loopcounter;
    maxavg[x] = a[0];

如果没有原子函数，这会出现任何冲突吗？当我写它的时候，我认为这是一个很好的方式，允许每个线程与全局内存共享其解决方案，而不会出现任何减速/冲突。会不会是将来自另一个线程的写入maxavgx或loopcounter？

问题2

我怎么才能加快速度呢？要完成此任务，需要33002854个线程。

   addKernel <<<32230, 1024>>>(dprice, davg, dpos, dpos1, dpos2, dpos3, dpos4, dpos5, dpos6, dpos7, dthread, dmaxavg);

我昨晚运行了1024个代码块和线程

    addKernel <<<1024, 1024>>>(dprice, davg, dpos, dpos1, dpos2, dpos3, dpos4, dpos5, dpos6, dpos7, dthread, dmaxavg);

在13个小时内没有完成之后我停止了它。因为我有2048个CUDA核心，这是否意味着如果100%被利用，我应该能够同时运行2048个线程addKernel <<<2048, 1>>>？或者更像是addKernel <<<2048, 1024>>>？然后，我可以调整for循环间隙的大小以适合此形状。

如果需要，我很乐意发布代码(它很长，所以不想在这篇大文章中添加更多内容)。

Answer 1

首先，由于有预算，这是一个背包问题。暴力是不必要的。CPU可以使用适当的算法几乎立即计算出这一点。

https://en.m.wikipedia.org/wiki/Knapsack_problem