GPU beschleunigt rekursive Funktion in C++

Question

Ich bin ziemlich neu in C++ (zwei Tage tatsächlich) und ich würde gerne wissen, ob es möglich ist, einige Parallelisierung mit diesem Code zu tun. Ich brauche das viel schneller, da es Millionen von Iterationen gibt. Von dem, was ich bisher verstanden habe, ist es nicht möglich zu parallelisieren, da die einzige von mir verwendete Schleife von der Iteration vorher abhängt, die keine Parallelisierung erlaubt. Recht? Und wenn Parallelisierung nicht möglich ist, wie kann man es sonst optimieren, damit es schneller wird. Ich war ziemlich überrascht, da dies nur 3x schneller läuft als mein ursprünglicher Python-Code. (Einige der C++ ist bis zu 100 schneller 400x als Python)

Wenn die Visual Studio 2015-Projektdateien benötigt werden, erklären Sie mir bitte ..

Wenn Sie die Anwendung ausführen: Sie benötigen ein SHA1-Hash eingeben und dann das Programm sagen, wie viele Zeichen das Grundwort hatte, so zum Beispiel das Wort Test: hash: a94a8fe5ccb19ba61c4c0873d391e987982fbbd3 Länge: 4

vielen Dank im Rat

#include "stdafx.h" 
#include <stdio.h> 
#include <string> 
#include <iostream> 
#include <cstring> 
#include "..\crytoPP\sha.h" 
#include "..\crytoPP\filters.h" 
#include "..\crytoPP\hex.h" 
#include "..\crytoPP\channels.h" 

using namespace CryptoPP; 
using namespace std; 

int found = 0; 
int iteration = 0; 
int length; 
char source[] = "abcdefghijklmnopqrstuvwxyz"; 
string solution = " didn't match"; 
string base_hash; 

string CHECK(string hash, int argc, char** argv); 
void COMBINATIONS(string b, int length, int source_length, int argc, char** argv); 

int main(int argc, char** argv) 
{ 
    char *arr_ptr = &source[0]; 
    int source_length = strlen(arr_ptr); 
    cout << "Please enter hash:"; 
    cin >> base_hash; 
    cout << "Please enter length:"; 
    cin >> length; 
    transform(base_hash.begin(), base_hash.end(), base_hash.begin(), ::toupper); 
    COMBINATIONS("", ::length, source_length, argc - 1, argv + 1); 
    system("PAUSE"); 
    return 0; 
} 

string CHECK(string hash, int argc, char** argv) { 
    if (::found == 0) { 
     iteration++; 
     cout << iteration << endl; 
     if (argc == 2 && argv[1] != NULL) 
      hash = string(argv[1]); 
     string s1; 
     SHA1 sha1; SHA224 sha224; SHA256 sha256; SHA512 sha512; 
     HashFilter f1(sha1, new HexEncoder(new StringSink(s1))); 
     ChannelSwitch cs; 
     cs.AddDefaultRoute(f1); 
     StringSource ss(hash, true /*pumpAll*/, new Redirector(cs)); 
     cout << s1 << endl; 
     if (s1 == ::base_hash) { 
      ::found = 1; 
      cout << " =" << hash << endl; 
     } 
     return s1; 
    } 
} 

void COMBINATIONS(string b, int length, int source_length, int argc, char** argv) { 
    if (::found == 0) { 
     if (length == 0) { 
      CHECK(b, argc, argv); 
     } 
     else { 
      for (int i = 0; i < source_length; i++) { 
       COMBINATIONS(b + ::source[i], length -1, source_length, argc -1, argv + 1); 
      CHECK(b, argc - 1, argv + 1); 
      } 
     } 
    } 
} 

Answer 1

Das erste, was Sie versuchen sollten, ist, Ihre Ausgabe in jeder Iteration zu entfernen, da dies die Leistung Ihres Programms erheblich reduziert.

Gerade jetzt Sie sie berufen COMBINATIONS nur einmal mit einem leeren String b, aber wenn Sie einen Thread für jeden Ausgang Zeichenfolge b der Größe 1 in main schaffen würden, kann man zum Beispiel 26 Threads lösen jeweils einen gleich großen Teil des Problems. Am besten wäre es jedoch, die COMBINATIONS-Funktion neu zu schreiben, um besser für die Parallelität geeignet zu sein.

Darüber hinaus sind Sie derzeit Leck Speicher jedes Mal, wenn Sie CHECK anrufen, die im Moment möglicherweise nicht so viel wie ein Problem scheint, aber je länger das Wort, das Sie suchen, desto mehr Speicher benötigt Ihr Programm. C++ erfordert, dass Sie den Speicher selbst verwalten, also sollten Sie mindestens den gesamten Speicher freigeben, den Sie mit new zugewiesen haben, indem Sie delete verwenden (um sicherzustellen, dass es wiederverwendet werden kann). Noch besser, wenn Sie versuchen würden, die von Ihnen erstellten Objekte wiederzuverwenden, da die Speicherzuweisungen ebenfalls etwas langsam sind.

Last but not least überdenken Sie bitte den Zweck der Erhöhung/Dekrementierung argc und argv. Ehrlich gesagt verstehe ich deine Absicht dort nicht ganz und es scheint böse.