pthread-Problem

[kristof]

Nimm mal das usleep raus und verwende nur zwei Worker. Das sollte eigentlich die Rechenzeit minimieren. Und ob deine CPU nun für ein paar Sekunden Volldampf gibt oder schläft is doch egal oder nicht?

[Chromanoid]

Normalerweise sollte der Thread durch Aufwecken in einen ausführbaren Zustand kommen. Wahrscheinlich ist das dann meistens der gleiche Zustand wie nach Erstellen eines Threads.

[Krishty]

Omg also nochmal langsam:
Es läuft dann am schnellsten, wenn du 1. So viele Threads wie CPU-KKerne hast und 2. so wenig wie möglich mit Wartezeit verschwendest ...

Das bedeutet:
1. Nicht mehr als ZWEI Worker-Threads
2. Selbst dann nutzt du nur 66 % der CPU-Zeit, weil du noch deinen Haupt-Thread hast, der mit 100 % ununentwegt über alles drüberiteriert um Aufgaben zu verteilen, obwohl die Worker-Threads viel Besseres zu tun haben als 20 mio Mal pro Sekunde neue Pixel abzufragen (der Haupt-Thread wäre DER Kandidat schlechthin für HyperThreading :/ )

Darum musst du
a) Den HAUPT-Thread schlafen legen, bis er damit rechnen kann, dass die Arbeiter ihren Kram fertig haben und was Neues entgegennehmen können
b) Die Wartezeit aus den Arbeitern entfernen, damit die möglichst viel Zeit zum Rechnen benutzen
c) Die Warteschlange verlängern, damit der Haupt-Thread möglichst selten möglichst viele Aufgaben verteilen kann und die Arbeiter schön durchackern können
d) Die Context-Switches und den ganzen Kram kriegst du in den Griff, indem du (wie schon gesagt) in den Arbeitern yieldest/das SwitchToThread-Pendant benutzt (das ist was ANDERES als schhlafen)
e) Wenn es keine Pixel mehr zu berechnen gibt, musst du die Arbeiter schlafenlegen oder zerstören, damit die nicht amok weiterrechnen

Herrgüte Raytracing ist das EINFACHSTE Problem, das man parallelisieren kann. Keine Abhängigkeiten, nichts. Und trotzzdem kommen wir hier nicht weiter. Tut mir das nicht an

[hundvdf]

Nimm mal das usleep raus und verwende nur zwei Worker. Das sollte eigentlich die Rechenzeit minimieren. Und ob deine CPU nun für ein paar Sekunden Volldampf gibt oder schläft is doch egal oder nicht?

Du hast natürlich Recht, die CPU soll natürlich dauerhaft in der Berechnung sein bis das Bild fertig ist, das ist dann wohl das schnellstmögliche. Ich habs mal getestet ohne das usleep in den Workern:
1 Worker-Thread: 30sec
2 Threads: 10sec
4 threads: 9,5sec
und schneller wirds danach auch nicht mehr.

Wenn ich allerdings das usleep drin lasse, dann ist das Minimum bei 8/16 Threads mit ca. 6sec erreicht, also nochmal einiges schneller...

Ich habe im Master-Thread auch noch ein usleep drin falls er keinen arbeitslosen Thread findet. Wenn ich das allerdings rausmache, dann geht gar nix mehr (auch bei nur einem Worker-Thread, was dann ja eigentlich gar kein Problem sein sollte...)

Ich werd das mit den Conditions mal noch ausprobieren, ob das dann noch schneller geht, bzw. mit einem Pixel-Pool pro Thread (was meiner Meinung nach dann am schnellsten gehen sollte). Aber jetzt kommen zuerst noch die Optimierungen des Raytracings dran, bisher lass ich BruteForce jeden Strahl mit jedem Objekt testet, und da baue ich jetzt dann ein Baum ein, damit das schonmal schneller geht.

Nachtrag:

Darum musst du
a) Den HAUPT-Thread schlafen legen, bis er damit rechnen kann, dass die Arbeiter ihren Kram fertig haben und was Neues entgegennehmen können
b) Die Wartezeit aus den Arbeitern entfernen, damit die möglichst viel Zeit zum Rechnen benutzen
c) Die Warteschlange verlängern, damit der Haupt-Thread möglichst selten möglichst viele Aufgaben verteilen kann und die Arbeiter schön durchackern können
d) Die Context-Switches und den ganzen Kram kriegst du in den Griff, indem du in den Arbeitern yieldest/das SwitchToThread-Pendant benutzt (das ist was ANDERES als schhlafen)
e) Wenn es keine Pixel mehr zu berechnen gibt, musst du die Arbeiter schlafenlegen oder zerstören, damit die nicht amok weiterrechnen

Herrgüte Raytracing ist das EINFACHSTE Problem, das man parallelisieren kann. Keine Abhängigkeiten, nichts. Und trotzzdem kommen wir hier nicht weiter. Tut mir das nicht an

a) hab ich gemacht
b) hab ich gemacht
c) das meinte ich oben mit dem Pixel-Pool pro Thread
d) wenn ich c einigermaßen sinnvoll löse und zudem auch nur 2 Worker-Threads habe, brauche ich mich darum ja nichtmehr sonderlich kümmern, oder?
e) das mache ich über den Destruktur

[kimmi]

Hm, lustig. Irgendwie geht hier gerade der Punk ab und ich weiß gar nicht so recht, warum. Die Condition wird von einigen Büchern einem nahegelegt, wenn man einen Threadpool selber baut. Yield nach Ende der Arbeit zu rufen ist natürlich richtig. Warum also regt der krishty sich eigentlich so auf? ;)
Und so wie ich das alles hier lese, ist der Drops längst gelutscht.

Gruß Kimmi

[Krishty]

Ich habs mal getestet ohne das usleep in den Workern:
1 Worker-Thread: 30sec
2 Threads: 10sec
4 threads: 9,5sec
und schneller wirds danach auch nicht mehr.

Wenn ich allerdings das usleep drin lasse, dann ist das Minimum bei 8/16 Threads mit ca. 6sec erreicht, also nochmal einiges schneller...

Zumindest sind wir jetzt doppelt/vierfach so nah am erwarteten Verhalten :)

Ich habe im Master-Thread auch noch ein usleep drin falls er keinen arbeitslosen Thread findet. Wenn ich das allerdings rausmache, dann geht gar nix mehr (auch bei nur einem Worker-Thread, was dann ja eigentlich gar kein Problem sein sollte...)

Das darf nicht sein. Auf keinen Fall. Markier auch gleichzeitig, falls nicht schon geschehen (hat kristof ja schon früher empfohlen), die bool-Flags als volatile. Dieser Minimalfall muss funktionieren!

a) hab ich gemacht

Stand aber nirgends im Text.

d) wenn ich c einigermaßen sinnvoll löse und zudem auch nur 2 Worker-Threads habe, brauche ich mich darum ja nichtmehr sonderlich kümmern, oder?

In einer perfekten Welt ;)

e) das mache ich über den Destruktur

D.h.: Alle Threads laufen noch mindestens so lange, bis der letzte Pixel berechnet ist und das Scope verlassen werden kann? Leg sie lieber schlafen, sobald alle Pixel vergeben sind. Nimmst du die Zeitmessung vor oder nach der Zerstörung der Threads vor?

Warum also regt der krishty sich eigentlich so auf? ;)
Und so wie ich das alles hier lese, ist der Drops längst gelutscht.

Das Programm verhält sich nicht ansatzweise berechenbar. Da sind mehr Würmer drin als in einer Haribofabrik. Da kann man doch nicht einfach so Augen zu- und weitermachen?

[dot]

Seh ich das richtig, du schedulest einzelne Pixel auf deine Worker? Das is vermutlich nicht gerade optimal. Besser wär es wohl dein Bild in Kacheln aufzuteilen (z.B. 32x32 Pixel). Dann erzeugst du soviele Worker Threads wie du Kerne hast und stopfst die Kacheln in eine (evtl. lock-free) Queue. Jeder Worker popped sich dann die nächste Kachel aus der Queue und bearbeitet die, das ganze solange bis keine Kacheln mehr da sind. Damit solltest du relativ nah zum linearen Speedup hinkommen...

[Krishty]

Genau das schwebt mir auch vor … später. Nur, dass ich kleinere Kacheln (4×4 höchstens) nehmen und jeden Thread „seinen“ Abschnitt einer Space Filling Curve (bloß nicht abwechselnd) abarbeiten lassen würde. Aber so lange selbst die Minimalfälle nicht funktionieren, sind das Randdetails und Zukunftsmusik.

Wo ist eigentlich Lord Delvin? Der hat sowas doch auch mal gemacht …

[kimmi]

@Krishty: Dass das Program noch nciht ausgereift war, ist mir klar gewesen. So was kann man auch schlecht in einer Diskussion lösen, da muss man dann im Editor ran.
Aber die zugrunde liegenden Ideen wurden nun schon zum wiederholten Male hier aufgeführt. Wie oft das Master-Worker-Pattern für Partitionen der Surface erwähnt wurde, wage ich schon gar nicht mehr zu zählen...

Gruß Kimmi

[Krishty]

Nagut. Ich habe es mir jedenfalls gerade selber auf die Schnelle nachgebaut – 200×150 durch eine Zählschleife simulierte Pixel auf vier physischen und acht logischen CPU-Kernen:
Anzahl Arbeiter / Gesamtzeit (minimal)–Gesamtzeit (maximal)
 1  9,32– 9,40 s
 2  4,87– 4,90 s
 3  3,09– 3,27 s
 4  2,46– 2,49 s
 5  2,00– 2,07 s
 6  1,73– 1,89 s
 7  1,56– 1,64 s
 8  1,68– 2,63 s
 9  3,96–10,57 s
10  2,11– 6,45 s
11  2,12–10,30 s
12  2,08– 9,76 s
13  1,60– 4,46 s

dia.png (3.25 KiB) 1310 mal betrachtet

(Von allen Zeitangaben könnt ihr 0,1 s Fixkosten für die Ausgabe des Rechenfortschritts abziehen)
Das barg zwar eine kleine Überraschung (die Rechenzeit pro Pixel ist so kurz, dass ein schlafender Haupt-Thread es 10× langsamer macht als ein Yieldender), verhält sich im Großen und Ganzen aber wie erwartet.
Quelltext kann ich posten, sobald hundvdfs Programm glatt läuft.