CUDA Brute Force Spaß

Question

Ich bin ein CUDA Neuling begann erst lernen, wie man CUDA programmiert, um dieses Problem zu lösen. Ich würde gerne einige Meinungen darüber hören, wie ich den Code und die GPU-Nutzung verbessern kann. Lauf GTX 980 BTW.

Ich schuf ein Problem zum Spaß, die jede Gruppe von 8 Spielern aus 266 benötigt, um ein Team zu bilden. Ziel ist es, die höchste Gesamtpunktzahl (jeder Spieler hat einen bestimmten Punktdurchschnitt) für das Team zu erreichen, während die Budgetbeschränkungen eingehalten werden (jeder Spieler kostet einen bestimmten Geldbetrag). So ähnlich wie ein Fantasy Sport Team Problem.

Ich möchte sehen, wie schnell ich die große Anzahl von Kombinationen brutal erzwingen kann (nicht wirklich an Optimierungsalgorithmen in diesem Stadium interessiert).

Ich erstelle derzeit Arrays für Spielerdetails.

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

erzeugen Dann 8-Arrays, die den Startindex für einen 8-for-Schleife verschachtelt sind (vor dem list.txt generiert).

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

Dann alles an den Kernal übergeben. Jeder Thread liest seinen Startpunkt zuerst von diesem Array.

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

Wo x = threadIdx.x, rowcount = 266.

Es gibt um 286.853.510.505.870 insgesamt Schleifen abzuschließen, wenn Sie, wo es bis zum Ende auf einem Gewindeanfang zu tun. Ich habe ein wenig geschummelt und ein paar Tricks hinzugefügt, um in den verschachtelten Loops vorzuspringen, indem ich die Daten sortiere, wenn Preis> Budget an irgendeiner Position zur nächsten Position springt, die nicht> Budget ist.

Dann bewerten Sie die Schleife und wenn Preis < Budget und Durchschnitt> aktuelle maximale Durchschnitt speichern Schleife Index, so kann ich Spieler Namen und avg Ergebnis zu den anderen Themen später vergleichen.

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

zählen = 16936750, die die Anzahl der Schleifen zwischen jedem Thread ist.

Führen Sie thread [] und maxavg [] zurück zum Host und dann eine for-Schleife durch maxavg [i], um den höchsten Wert zu finden und den Thread [] auszudrucken.

Frage 1

Ich bin gespannt, wie sicher diese Linie

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

Ohne Atomfunktionen wird dies keine Auseinandersetzungen sehen? Als ich es schrieb, dachte ich, es sei eine hervorragende Möglichkeit, jedem Thread zu erlauben, seine Lösung mit dem globalen Speicher zu teilen, ohne dass es zu Verzögerungen/Konflikten kommt. Könnte es sein, dass [0] aus einem anderen Thread in maxavg [x] oder loopcounter geschrieben wird?

Frage 2

Wie kann ich das beschleunigen? Um dies zu vervollständigen, müssten 33002854 Threads benötigt werden.

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

Ich lief gestern Abend mit 1024 Blöcken und Themen

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

und ich hielt es nach nicht in 13 Stunden beendet.Da ich 2048 CUDA-Kerne habe, bedeutet das, wenn 100% ausgelastet ist, dass ich 2048 Threads gleichzeitig addKernel <<<2048, 1>>> ausführen kann? Oder mehr wie addKernel <<<2048, 1024>>>? Ich kann dann die Größe der for-Schleife Lücken anpassen, um diese Form anzupassen.

Gerne, den Code bei Bedarf zu posten (es ist lang so wollte nicht mehr zu diesem großen Beitrag hinzufügen).

Answer 1

Vor allem, da es ein Budget gibt, ist dies ein Rucksackproblem. Brute Force ist unnötig. Die CPU könnte dies fast sofort mit einem geeigneten Algorithmus berechnen.

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