Laufzeiten Sequentiell & Parallelisiert

[core]

Howdy,

mich würde mal interessieren, wie eure Laufzeiten so aussehen, um meine eigene Implementierung etwas besser einschätzen zu können.

Anbei meine Werte:

Code: Alles auswählen

pcgris-gc05:~/p4/build> time ./Praktikum4_sequential

[...]

Finished rendering

real    4m37.938s
user    4m37.153s
sys     0m0.126s

Code: Alles auswählen

pcgris-gc05:~/p4/build> time ./Praktikum4_pthreads

Using 10 threads
Processing 20 jobs per thread

[...]

Rendering...

worker[3]: nothing more to do
worker[8]: nothing more to do
worker[9]: nothing more to do
worker[0]: nothing more to do
worker[4]: nothing more to do
worker[5]: nothing more to do
worker[6]: nothing more to do
worker[1]: nothing more to do
worker[2]: nothing more to do
worker[7]: nothing more to do

Finished rendering

real    1m8.732s
user    5m59.142s
sys     4m14.511s

Wenn ich die Aufgabenstellung korrekt lese, leider noch 10 Sekunden zu viel für den vollen Bonus.

Nebenbei gefragt... sehe ich das richtig, dass "user" die akkumulierte Zeit über alle Threads ist?


Viele Grüße
core

[Thomas Huxhorn]

Wenn ich die Aufgabenstellung korrekt lese, leider noch 10 Sekunden zu viel für den vollen Bonus.

Huch? Rechne mal bitte vor.

[core]

Huch? Rechne mal bitte vor.

Die Zahlen (Anzahl Threads, abzuziehende Zeit) habe ich aus diversen Threads hier im Forenbereich.

[danny]

Für die sequentielle Zeit habe ich auch 4:38 gemessen.
Die parallele Variante (10 Threads) liefert:

real 0m50.599s
user 5m57.557s
sys 1m11.554s

Da sind auch keine "Geschwindigkeitstricks" wie Inline Assembler oder C-Spielereien drin, reines C++. Also Vektoren und keine Arrays, new und delete anstatt malloc und free, ...
Eventuell ist deine Parallelisierung zu feingranular? Ich habe zum Beispiel keine 16 neuen Jobs für die 16 AO-Rays erzeugt, sondern nur einen.

[Thomas Huxhorn]

Ahso, jetzt hab ich das verstanden. 6 Sekunden fürs laden/speichern und den Baum erstellen.
Mach mehr Jobs pro Thread. Dann stimmen die Zeiten bestimmt

Hier unsere Zeiten in der ersten unoptimierten Version:

Code: Alles auswählen

threads  time                speedup
    1       5m24.640s
    2       2m51.895s       1.89
    4       1m33.269s       3.48
    8       0m58.038s        5.58
   12       0m51.021s       6.35
   16       0m50.477s       6.4
   24        0m51.381s

Wo ist denn da der Flaschenhals? RAM Geschwindigkeit?

[x539]

Mit 24threads:

Code: Alles auswählen

real    0m23.560s
user    6m13.608s
sys     0m21.061s

Also den ersten Flaschenhals habe ich offensichtlich gefunden und vollständig entfernt (es war nicht die RAM-Geschwindigkeit).

Mit einer handvoll hässlicher Zeilen mehr:

Code: Alles auswählen

real    0m13.429s
user    2m10.803s
sys     0m39.154s

Das ist übrigens beides im Wesentlichen die vorgegebene Implementierung. Ganz ohne Assembler.

[core]

@x539

Beeindruckend.

Das motiviert doch geradezu, sich heute Abend doch noch mal dran zu setzen.

[Thomas Huxhorn]

@x539 Auf deine Lösung bin ich mal gespannt. Ich seh einfach nicht den Flaschenhals. Egal was ich versuche.
Wenn es der Baum nicht ist, dann weiß ich es auch nicht.

[bttf]

Hmm, ich bekam bei der sequenziellen Lösung immer eine Zeit über 5 Minuten... seltsam.

Unsere Lösung brauch im Durchschnitt auch etwa 50 Sekunden. Reicht ja Gott sei Dank dann noch bei sequenzieller Zeit von 4m 37s

13 Sekunden ist aber echt krass Unsere Implementierung ist mit 24 Threads höchstens 2 bis 3 Sekunden schneller als mit 10 Threads. Kein Plan woran das liegt ^^

@x539: Versteckt sich der Flachenhals irgendwo in den zur Verfügung gestellten Funktionen in aosampler, CScene, camera? Die hab ich mir nämlich gar nicht angeguckt XD

[Dennis Albrecht]

Unsere Implementierung ist mit 24 Threads höchstens 2 bis 3 Sekunden schneller als mit 10 Threads. Kein Plan woran das liegt ^^

Ist kein Wunder, da die Rechner ja "nur" mit 12 physischen Kernen ausgerüstet sind und sich bei mehr als 12 Threads nicht mehr viel verändert (wenn ein Thread ruht kann der andere auf dem Kern weitermachen, aber nie beide gleichzeitig; hab ich zumindest so aus dem Forum herausgelesen)

Gruß

[kbraden]

Wir haengen auch bei ~50s (sys hat knapp 9min, schaetze da ist unser locking noch scheisse :s)

Unsere Implementierung ist mit 24 Threads höchstens 2 bis 3 Sekunden schneller als mit 10 Threads. Kein Plan woran das liegt ^^

Ist kein Wunder, da die Rechner ja "nur" mit 12 physischen Kernen ausgerüstet sind und sich bei mehr als 12 Threads nicht mehr viel verändert (wenn ein Thread ruht kann der andere auf dem Kern weitermachen, aber nie beide gleichzeitig; hab ich zumindest so aus dem Forum herausgelesen)

Gruß

Und x539 hat seine Implementierung einfach schneller gezaubert?

Nebenbei gefragt... sehe ich das richtig, dass "user" die akkumulierte Zeit über alle Threads ist?

http://www.d120.de/forum/viewtopic.php? ... 65#p136712

[mw1039]

wenn ein Thread ruht kann der andere auf dem Kern weitermachen, aber nie beide gleichzeitig

Naja, ruhen heisst nicht zwingend, dass ein Thread z.B. gerade auf den Zugriff auf die Queue wartet. Das kann auch bedeuten, dass er gerade Daten aus dem Speicher angefordert hat, die Daten nicht im Cache waren und er deswegen Dutzende oder hunderte Takte warten muss, bis die Daten aus einer der hoeheren Cacheebenen oder aus dem eigentlichen RAM kommen. Dann kann der Kern schnell auf den zweiten Thread umschalten. Das kann schon einen Vorteil bringen. Tut es aber in diesem Anwendungsfall anscheinend nicht.
Ich vermute aber, dass wir mit 24 echt physikalischen auch nicht schneller waeren. Es macht bei vielen Leuten z.B. schon keinen Unterschied, ob man 10 oder 12 Threads anschmeisst. Das kann nicht mit den physikalischen/virtuellen Kernen erklaert werden.

Es scheint uebrigens eine Diskrepanz in den sequentiellen Ausfuehrungszeiten zu geben, die ich mir nicht erklaeren kann.
Wir haben hier fuer 1 Thread eine real time von 332 Sekunden.

Hmm, ich bekam bei der sequenziellen Lösung immer eine Zeit über 5 Minuten... seltsam.

Für die sequentielle Zeit habe ich auch 4:38 gemessen.

Hat jemand eine Idee woran das liegen kann?

[core]

Für die sequentielle Zeit habe ich auch 4:38 gemessen.

Hat jemand eine Idee woran das liegen kann?

4:38 ist die (real-) Laufzeit der Referenzimplementierung (ohne irgendwelche Änderungen) bei komplett unausgelastetem System, ich hab's zwischen 23:00 und 07:00 dutzende Male ausgeführt, das unterscheidet sich zumindest auf der Node 05 nur marginal im 3-4 Sekunden-Bereich.

[Matthias Senker]

Es scheint uebrigens eine Diskrepanz in den sequentiellen Ausfuehrungszeiten zu geben, die ich mir nicht erklaeren kann.
Wir haben hier fuer 1 Thread eine real time von 332 Sekunden.

bttf hat geschrieben:Hmm, ich bekam bei der sequenziellen Lösung immer eine Zeit über 5 Minuten... seltsam.


danny hat geschrieben:Für die sequentielle Zeit habe ich auch 4:38 gemessen.


Hat jemand eine Idee woran das liegen kann?

Scheinbar sind die Rechner unterschiedlich schnell. Auf node05 hab ich auch 4:38 gemessen, bei node08 deutlich über 5 Minuten.
Dieser Geschwindigkeitsunterschied ist mir übrigens auch bei unserer parallelen Implementierung aufgefallen, allerdings ist er dort nur ca. 2-3 Sekunden groß.

Jetzt haben wir folgendes Problem: auf node08 würde unsere Implementierung die Geschwindigkeitsanforderung für die vollen 2 Punkte erfüllen, auf node05 verfehlt sie sie knapp. Können wir uns beim Testat aussuchen, auf welchem der 4 Rechner wir das Programm laufen lassen möchten?

[bttf]

Scheinbar sind die Rechner unterschiedlich schnell. Auf node05 hab ich auch 4:38 gemessen, bei node08 deutlich über 5 Minuten. Dieser Geschwindigkeitsunterschied ist mir übrigens auch bei unserer parallelen Implementierung aufgefallen, allerdings ist er dort nur ca. 2-3 Sekunden groß.

Bei mir das gleiche. Auf node05 ist die parallele Implementierung minimal, auch etwa 2-3 Sekunden schneller als auf node08. Die sequenzielle Implementierung habe ich getestet, als nur node08 erreichbar war, danach nicht mehr und auf node08 hat die Ausführungszeit bei mir zwischen 5m 22s und 5m 49s geschwankt, deshalb war ich auch über die 4m 38s etwas überrascht

Was mich auch etwas verwundert: Ich habe eine Workqueue implementiert, die alle noch abzuarbeitenden Pixel enthält und egal ob die Threads sich 4 Pixel, 16 Pixel oder sogar 512 Pixel zum bearbeiten rausnehmen, die Ausführungszeit beeinflusst das nicht merklich. Die liegt konstant bei etwa 50 Sekunden. Konnte noch jemand so etwas beobachten bei seiner Implementierung???

MfG bttf