Hallo,
ich möchte einen recht komplizierten Algorithmus gerne optimieren.
Es sind jedoch kaum zu parallelisierende Codeabschnitte forhanden (nur etwa 1%). Der größte Teil des Algorithmus ist leider nicht zu parallelisieren. Es enthält auch kaum noch FOR iterationen, sodas auch ein parallelisieren einzelner Interationen nicht möglich ist.
Der Algorithmus hat jedoch die Eigenschaft, dass er mit verschiedenen Startwerten unterschiedlich schnell zum Ziel führt. Wenn ich die Startwerte zufällig gut wähle, dann ist die Lösung nach wenigen Sekunden vorhanden.
Wenn ich die Startwerte zufällig schlecht wähle, dann dauert das lösen mehrer Stunden.
Leider ist es nicht möglich gute "Startwerte" zu berechnen oder vorherzusagen.
Daher habe ich folgende Idee:
Wenn ein Beutzer z.B. ein 4-Core-Prozessor hat, dann wird der Algorithmus einfach 4 mal parallel ausgeführt.
Der Tread, welcher als erstes die Lösung findet gibt diese Lösung weiter. Die anderen Threads werden gelöscht.
Ich habe zwar gelesen, dass mit "terminate" ein thread gelöscht werden kann, ich habe aber auch gelesen, dass es so nicht gemacht werden soll, weil der Arbeitsspeicher wohl nicht korrect freigegeben wird.
Wer kann mir an einem Minimalbeispiel erklären, wie ich es korrekt umsetzen sollte? (Bitte nicht zu kurz, da ich mit threads nicht so viel Erfahrung habe. Ich habe zwar schon versucht mit concurrent einiges es parallelisieren, aber dadurch nicht einmal 1% performance gewinnen können (weil der Rest leider nicht parallelisierbar ist.)
Danke
Volker
Multithreading
Man kann schon auf mehrere Prozessoren verteilen.
vgl. assitent "QtConcurrent"
Von der Idee her müsste ich QtConcurrent aufach auf den ganzen Algorithmus anwenden (und nicht nur auf Teile davon.). Aber wie beende ich dann die anderen Threads korrekt?
vgl. assitent "QtConcurrent"
Wie gesagt, damit habe ich auch schon Dinge parallelisiert. Ist recht einfach, aber in meinem Fall nicht möglich.Programs written with QtConcurrent automaticallly adjust the number of threads used according to the number of processor cores available.
Von der Idee her müsste ich QtConcurrent aufach auf den ganzen Algorithmus anwenden (und nicht nur auf Teile davon.). Aber wie beende ich dann die anderen Threads korrekt?
Noe noe, unterschiedliche Threads vom gleichen Prozess koennen schon auf unterschiedliche cores laufen. Die frage ist ob es das BS automatisch tut, oder ob man nachhelfen muss ....Soweit ich weiß funktioniert das mit Multithreading nicht. Du kannst zwar mehreren Thread starten, aber die laufen alle auf dem gleichen Core.
keine so gute Idee !Wenn ein Beutzer z.B. ein 4-Core-Prozessor hat, dann wird der Algorithmus einfach 4 mal parallel ausgeführt.
Warum ! Es gibt keinen core der schneller ist als der andere ! Es gibt nur den, der weniger threads ausfuehren muss grad !
Unter gleichen bedingungen sollten die DInger auch gleich schnell sein !
Statt das ding 4 mal zu starten, waer es sinnvoller, fuer einen core optimale bedingungen zu schaffen. Sprich einfach zu schauen, wo Threads laufen, von die dein Thread abhaengig ist, und diesen core nicht zu nehmen, sondern einen wo die anderen threads ruhig "ueberfahren" kannst, und deinen thread einfach mit hoeherer Prio als die anderen laufen zu lassen.
Viel mehr wirst ned rausholen koennen.
In ner ganz anderen richtung wuerd ich auch noch schauen, ob dein Algo ned durch streampiplines effizienter implementiert werden könnte, und das ding bei bedarf in die GPU auslagern ...
Ciao ...
Stimmt, gibts aber anscheinend erst seit Qt4.4Volker75 hat geschrieben:Man kann schon auf mehrere Prozessoren verteilen.
Eventuell über den quit Slot. Wenn der Thread das Signal empfängt räumt er auf und beendet sich dann mit terminateVolker75 hat geschrieben: Von der Idee her müsste ich QtConcurrent aufach auf den ganzen Algorithmus anwenden (und nicht nur auf Teile davon.). Aber wie beende ich dann die anderen Threads korrekt?
Nein. Bitte meine Beschreibung lesen. Ich starte den Algorithmus natürlich immer mit anderen Startbedingungen und dann ist er auch unterschiedlich schnell.RHBaum hat geschrieben:keine so gute Idee !
Warum ! Es gibt keinen core der schneller ist als der andere !
streampiplines sagt mir nicht. Ich versuche mal das zu googlen. Für gute Links bzw. Hinweise bin ich dankbar.RHBaum hat geschrieben:In ner ganz anderen richtung wuerd ich auch noch schauen, ob dein Algo ned durch streampiplines effizienter implementiert werden könnte, und das ding bei bedarf in die GPU auslagern ...
GPU ist nicht akzeptable, da:
1. der Algorithmus von Menschen benutzt wird, die im "Büro" arbeiten und nicht an einer Spielemaschine. Die wie werden sich kaum eine dicke Grafikkarte kaufen.
n der Praxis wird der Algorithmus nur an 1 bis 2 Wochen im Jahr durchgeführt.)2. Unterscheidliche Sprachen (bei Nvidia und AMD)
3. kann auf diesen Algorithmus nicht angewendet werden. (Er besteht zum größten Teil nur as if und goto Anweisungen. Und das ist absicht. Mit Iterationen würde der Algorithmus Jahrtausende zum Lösen brauchen. Durch diese if und goto Pogrammierung konnte die Geschwindigkeit im Optimalfall schon auf wenige Sekunden reduziert werden.
n schlechten Fällen leider immer noch mehrer Stunden.)4. OpenMP habe ich auch schon ausprobiert. Wie gesagt, die Algorithmus läßt sich so nicht mehr optimieren. (Vielleicht mit einem völlig neuem Ansatz. Aber nach über 3 Jahren Arbeit an dem Algorithmus (mit Graphen, evolutionären Algorithmen, Coloring, Backtracking, ...) sind uns die Ideen ausgegangen.
Meine Idee wäre zu sinnvollen Zeitpunkten im Algorthmus einen Check auf eine Variable einzubauen. Diese gibt an, ob ein anderer Thread schon fertig gerechnet hat. Falls ja, so wird der Algorithmus abgebrochen.
Du brauchst dafür eine globale, synchronisierte Variable (bool sollte reichen). Vielleicht muss sie auch nicht synchronisiert sein. Wichtig ist, sie muss halt entsprechend häufig (z.B. alle 5 min) abgefragt werden und dann die Berechnung entsprechend abgebrochen werden.
Alternativ zur Variablen kannst du auch ein Signal an die Klasse schicken, die den Algorithmus implementiert. Als Reaktion wird eine private Instanzvariable auf true gesetzt und diese wird entsprechend häufig bei der Berechnung überprüft.
Dann können alle Threads warten bis sie fertig sind und du kannst normal raus.
Du brauchst dafür eine globale, synchronisierte Variable (bool sollte reichen). Vielleicht muss sie auch nicht synchronisiert sein. Wichtig ist, sie muss halt entsprechend häufig (z.B. alle 5 min) abgefragt werden und dann die Berechnung entsprechend abgebrochen werden.
Alternativ zur Variablen kannst du auch ein Signal an die Klasse schicken, die den Algorithmus implementiert. Als Reaktion wird eine private Instanzvariable auf true gesetzt und diese wird entsprechend häufig bei der Berechnung überprüft.
Dann können alle Threads warten bis sie fertig sind und du kannst normal raus.