CUDA brute force fun

Question

私はCUDA初心者ですが、この問題を解決するためにCUDAをプログラミングする方法を学び始めました。コードとGPUの使用率をどのように改善できるかについての意見が大好きです。 GTX 980 btwを走らせる。

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++; } 
    } 

次にforループネスト8の開始インデックス（前list.txtに生成）である8つのアレイを生成します。

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、行数= 266

あなたはどこフィニッシュに1つのスレッドの起動時にそれを実行する場合は完了するために周り286,853,510,505,870総ループがあります。私はちょっと騙され、入れ子にされたループで先に飛び降りるようなスマートを追加したので、データを並べ替えることで、価格>予算は次の位置にスキップして>予算にならないようにします。

次に、価格が<の場合、予算とavg>現在の最大平均ループインデックスが保存されているので、後で他のスレッドと比較するプレーヤー名と平均スコアを取得できます。

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各スレッド間のループ数です。

スレッド[]とmaxavg []をホストに戻し、maxavg [i]を使ってforループを実行して最高値を見つけ、スレッド[]を出力します。私はアトミックな機能がなければ、この行が

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

がどのように安全な興味

質問1

が、これは任意の衝突を見るのだろうか？私はそれを書きましたが、各スレッドがグローバルメモリとのソリューションを低速/衝突なしに共有できる優れた方法だと思っていました。他のスレッドから[0]をmaxavg [x]または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