Warteschlange

hstr
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

Warteschlange

Beitrag von hstr » 19. Dez 2011 13:57

Hi, ich habe auch noch eine Frage zum neuen Praktikum. Es betrifft die Warteschlange.

Wie ist das von den Aufgabenstellern gedacht?
Unsere erste Idee ist es dass sich die Threads jeweils eine Menge an Pixeln rausgreifen, die Farbwerte berechnen und sich anschließend erneut an der Menge der verbliebenen Pixel bedienen.
Wenn das so in Ordnung ist verstehen wir aber nicht wozu die Warteschlange benötigt wird, denn ein gemeinsamer Counter der bis zur Gesamtzahl der Pixel hochgezählt wird reicht da vollkommen.

Aber das geht ja alles irgendwie an der Aufgabenstellung vorbei, oder? Vermutlich sollen in der Warteschlange Rays stehen, aber ich weiß grade nicht inwiefern das sinnvoll ist.

Wir würden uns freuen wenn es nochmal Informationen dazu gäbe was von der Warteschlange gefordert wird.

VG :]

studentabc
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 31. Okt 2011 13:56

Re: Warteschlange

Beitrag von studentabc » 19. Dez 2011 14:40

Ich denke bei der Warteschlange geht es darum die Aufgaben aufteilen zu können. Bei der Version ohne AoS und Supershampling ist es dies nicht nötig. Später für die 1,5 und 2 Punkte Version aber ist die Aufgabenverteilung schon wichtig.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Warteschlange

Beitrag von mw1039 » 19. Dez 2011 14:43

In der Aufgabenstellung steht ja auch, dass beim Auftreffen auf ein Objekt halbkugelfoermig Ambient Occlusion Rays (mit einer kuerzeren Lebenszeit als die normalen Rays) generiert werden sollen. Die passen nicht in das Pixel-Schema und muessen deswegen als Rays in eine Ray-Queue eingefuegt werden.
Die Queue ist eine Datenstruktur in der vorne Strahlen rausgenommen und hinten welche angehaengt werden koennen. Der Zugriff muss geschuetzt werden.

studentabc
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 31. Okt 2011 13:56

Re: Warteschlange

Beitrag von studentabc » 19. Dez 2011 16:41

Meiner Meinung nach ändert sich an der Laufzeit nichts, ob ich einen Laufzeit schwachen Befehl A und einen Laufzeit intensiven Befehl A in einem Thread hinteinander ausführe oder ob ich einen Thread erst A ausführen lasse und einen anderen Thread später B ausführen lasse. Es müsste sogar die Laufzeit leicht erhöhen, da ich ja einen weiteren Mutex-Bereich einführen muss.

Matthias Senker
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 14. Okt 2010 22:42

Re: Warteschlange

Beitrag von Matthias Senker » 19. Dez 2011 17:01

Ich kann ehrlich gesagt auch nicht den Sinn darin erkennen, die ganzen Rays in eine Warteschlange zu setzen. Wenn man das Bild einfach in kleine Intervalle einteilt, die in eine Warteschlange setzt, und dann die einzelnen Threads sich immer das nächste intervall nehmen und dort die Pixel genau so, wie in der sequentiellen Variante verarbeiten, dann müsste das doch schneller gehen oder? Alleine schon, weil man nicht ettliche Rays in eine Warteschlange rein und wieder raus kopiert.

Auf jeden Fall habe ich diese Variante mit den Intervallen mal ausprobiert, (hat gerade mal ca. 30 min gedauert das zu coden, dank Copy-Paste aus der sequentiellen Variante) und es scheint problemlos zu funktionieren und auch noch schnell genug für die 2 Punkte, wobei ich es noch nicht auf dem Cluster testen konnte.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Warteschlange

Beitrag von mw1039 » 19. Dez 2011 17:48

studentabc hat geschrieben:Meiner Meinung nach ändert sich an der Laufzeit nichts, ob ich einen Laufzeit schwachen Befehl A und einen Laufzeit intensiven Befehl A in einem Thread hinteinander ausführe oder ob ich einen Thread erst A ausführen lasse und einen anderen Thread später B ausführen lasse. Es müsste sogar die Laufzeit leicht erhöhen, da ich ja einen weiteren Mutex-Bereich einführen muss.
Das ist eine schwierige Sache. Es kann z.B. sein, dass ein Strahl an einem Punkt auf ein Objekt auftrifft, der von vielen anderen Objekten, die ihn verdecken, umgeben ist. In diesem Falle ist er schnell mit seinen Berechnungen fertig, weil seine Ambient Occlusion Rays alle frueh terminieren. Ein anderer Thread hat vielleicht AO Rays, die nicht verdeckt sind und deren Schnittberechnung deswegen sehr lange dauert. In diesem Fall waere es nett, wenn sich der schnelle Thread schon frueher neue Strahlen nehmen kann. Wenn man jetzt keine Strahlen-, sondern eine Pixelqueue hat und versucht einfach einen neuen Pixel aus der Queue zu holen, kann es sein, dass die Queue gerade durch einen anderen Thread belegt ist und er deswegen warten muss. Da spielen sehr sehr viele Sachen mit rein, u.a. auch (wenn man eine Ray-Queue hat) "Wie viele Rays nehme ich als Thread immer gleichzeitig aus der Queue?" oder (wenn man eine Pixel-Queue hat) "Wie viele Pixel nehme ich immer gleichzeitig aus der Queue?". Die Ray-Queue ist feingranularer und die Pixel-Queue groeber. Was von beidem besser ist, haengt sicher auch davon ab, wievielfach Supersampling man macht und wie viele AO Rays man genau generiert.

Ein anderer Punkt ist die Vergleichbarkeit: Damit alle Studentenloesungen vergleichbar sind, muessen auch alle das gleiche tun. Deswegen muessen wir bei dem bleiben was in der Aufgabenstellung steht: Es muss eine Queue gebastelt werden, diese muss threadsafe sein und in sie muessen Arbeitspaeckchen in Form von Strahlen gelegt und rausgenommen werden koennen.
Wie viele Strahlen man dann immer gleichzeitig aus der Queue nimmt, ist euch ueberlassen.

Benutzeravatar
DB_420
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 24. Nov 2010 15:12

Re: Warteschlange

Beitrag von DB_420 » 19. Dez 2011 22:08

Müssen das zwingend Rays sein? Wir haben uns eine Struktur gebastelt, in der wir noch weitere Informationen mitgeben, die die ganze Bearbeitung erheblich erleichtern - in der Queue werden dann Referenzen auf diese Job-Strukturen gespeichert, Wäre doof, das jetzt noch ändern zu müssen :)
Tutor:
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Warteschlange

Beitrag von mw1039 » 20. Dez 2011 07:31

Also ihr solltet (wie gesagt zwecks Vergleichbarkeit) schon Rays und nicht Pixel als Job betrachten.
Aber zusaetzliche Infos zur Beschleunigung sind denke ich ok.

Lukg
Erstie
Erstie
Beiträge: 11
Registriert: 14. Okt 2010 17:32

Re: Warteschlange

Beitrag von Lukg » 20. Dez 2011 18:13

Aus der Aufgabenstellung:
"Im Sinne der Geschwindigkeit des Programms ist es außerdem sinnvoll, dass sich jeder Thread immer wenn er nach
Arbeit sucht gleich mehrere Strahlen aus der Job-Warteschlange holt. Die Sicherungsmaßnahmen der Warteschlange
erzeugen relativ viel Overhead. Wenn man jeweils mehrere Strahlen aus der Schlange nimmt, ist das Verhältnis zwischen
echter Rechenarbeit und Wartezeit günstiger."

Wir sollen also pro Thread nicht nur ein Ray berechnen, sondern gleich mehrere.
Was hindert uns nun daran die hier genannten "mehreren Strahlen" so zu wählen, dass sie zusammen einen Pixel ergeben?
Dann wären wir doch wieder bei der Pixelqueue.

Habe ich etwas essentiell Wichtiges nicht verstanden? Wie sollen die "Jobs" aussehen?

MfG

Matt
Erstie
Erstie
Beiträge: 18
Registriert: 20. Dez 2011 19:22

Re: Warteschlange

Beitrag von Matt » 20. Dez 2011 19:26

Das heißt es reicht nicht eine auf pthreads basierende Implementierung zu schreiben, die vernünftig skaliert, sondern es werden auch noch irgendwelche Details vorgegeben, wie wir die Arbeit aufzuteilen haben? Zumal diese Vorgabe aller Wahrscheinlichkeit langsamer ist, da wenn mehrere Threads am selben Pixel arbeiten der Zugriff wiederum Atomar geschehen muss (und ja AtomicAddFloat ist langsamer, als ein einfaches unsynchronisiertes Schreiben in ein Array).

Gibt es weitere verbotene Strategien? Wie darf ich die Strahlen über Threads verteilen und wie nicht?
Zuletzt geändert von Matt am 21. Dez 2011 08:22, insgesamt 1-mal geändert.

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Warteschlange

Beitrag von arne.lottmann » 20. Dez 2011 19:40

Matt hat geschrieben:[…]der Zugriff wiederum Atomar geschehen muss (und ja AtomicAddFloat ist langsamer, als ein einfaches unsynchronisiertes Schreiben in ein Array).
Es steht aber nirgendwo geschrieben, dass man AtomicAddFloat benutzen muss, oder? Ich meine, man könnte es auch selbst synchronisieren und so z.B. drei floats auf einmal schreiben.

Matt
Erstie
Erstie
Beiträge: 18
Registriert: 20. Dez 2011 19:22

Re: Warteschlange

Beitrag von Matt » 20. Dez 2011 19:56

arne.lottmann hat geschrieben:
Matt hat geschrieben:[…]der Zugriff wiederum Atomar geschehen muss (und ja AtomicAddFloat ist langsamer, als ein einfaches unsynchronisiertes Schreiben in ein Array).
Es steht aber nirgendwo geschrieben, dass man AtomicAddFloat benutzen muss, oder? Ich meine, man könnte es auch selbst synchronisieren und so z.B. drei floats auf einmal schreiben.
Meine Lösung muss überhaupt nichts synchronisieren (bezogen auf das Schreiben von Ergebnissen). Egal ob atomare Add-Operation, Mutex oder Spinlock, alles ist definitiv langsamer.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Warteschlange

Beitrag von mw1039 » 21. Dez 2011 11:13

Lukg hat geschrieben:Was hindert uns nun daran die hier genannten "mehreren Strahlen" so zu wählen, dass sie zusammen einen Pixel ergeben?
Dann wären wir doch wieder bei der Pixelqueue.
Das stimmt. Dann ist es meinetwegen freigestellt, ob man Strahlen oder Pixel in die Queue tut. Wenn die Queue templatisiert ist, sollte das sowieso schnell austauschbar sein.
Matt hat geschrieben:Das heißt es reicht nicht eine auf pthreads basierende Implementierung zu schreiben, die vernünftig skaliert, sondern es werden auch noch irgendwelche Details vorgegeben, wie wir die Arbeit aufzuteilen haben?
Hast du die Aufgabenstellung gelesen? Falls nicht empfehle ich es. Da steht zum Beispiel
Im Sinne der Geschwindigkeit des Programms ist es außerdem sinnvoll, dass sich jeder Thread immer wenn er nach
Arbeit sucht gleich mehrere Strahlen aus der Job-Warteschlange holt. Die Sicherungsmaßnahmen der Warteschlange
erzeugen relativ viel Overhead. Wenn man jeweils mehrere Strahlen aus der Schlange nimmt, ist das Verhältnis zwischen
echter Rechenarbeit und Wartezeit günstiger.
Da steht nicht, wie ihr die Arbeit aufteilen sollt. Sie muss ueber eine Queue verteilt werden, aber wie viele Jobs man rausholt etc. ist euch freigestellt.
Matt hat geschrieben:Gibt es weitere verbotene Strategien? Wie darf ich die Strahlen über Threads verteilen und wie nicht?
Oh, es gibt noch Millionen verbotene Strategien. Z.B. der Graduate Student Algorithm. Um sie nicht alle aufzaehlen zu muessen, haben wir in der Aufgabenstellung nur geschrieben, was getan werden soll.

Es sollen einfach mit diesem Praktikum gewisse Mechanismen vermittelt werden, bspw. thread safety und locking. Ich weiss, dass es schnellere Loesungen gibt, die auf sie verzichten.

Wir geben noch im Laufe des Tages die Modalitaeten des Speedwettbewerbs bekannt. Ob die Bedingungen an den Code fuer (und nur fuer) den Wettbewerb gelockert werden, weiss ich noch nicht.
arne.lottmann hat geschrieben:(und ja AtomicAddFloat ist langsamer, als ein einfaches unsynchronisiertes Schreiben in ein Array)
Nein, nicht zwingend.
1. kann der Compiler und der Prozessor moeglicherweise den Atomic-Zugriff mit anderen Berechnungen verschraenken. Wenn ein Thread gerade darauf wartet atomic in den Array schreiben zu duerfen, kann eine geschickte Pipeline ihn eigentlich schon die darauf folgenden Operationen durchfuehren lassen und dann atomic reinschreiben, sobald er Zugriff auf diese Position im Array hat. Ich weiss nicht ob das hier (mit den gegebenen Prozessoren, Compilern und Bibliotheken) tatsaechlich gemacht wird, aber in CUDA wird es zumindest gemacht.
2. verbringt der Prozessor ohnehin den Grossteil der Zeit (ich kann keine guten Schaetzungen dazu angeben aber ich vermute deutlich ueber 99%) in anderem Code. Er traversiert ja die ganze Zeit den Strahl durch den Raum (durch die Bounding Volume Hierarchy) rechnet Schnitte, generiert AO-Strahlen, etc. und irgendwann dann ganz am Ende schreiben wir einmal kurz atomic eine Zahl in ein Array. Ich denke nicht, dass das ueberhaupt merkbar ist, dass das atomic stattfindet. Bei so wenig Rechenzeit, die auf den atomic Zugriff entfaellt und nur 24 Threads ist es ueberhaupt sehr unwahrscheinlich, dass zwei Threads gleichzeitig versuchen auf die gleiche Stelle zu schreiben.
Man kann natuerlich trotzdem versuchen ohne den atomic Zugriff auszukommen, aber ich glaube die Kosten dafuer sind vernachlaessigbar.

Matt
Erstie
Erstie
Beiträge: 18
Registriert: 20. Dez 2011 19:22

Re: Warteschlange

Beitrag von Matt » 21. Dez 2011 16:12

mw1039 hat geschrieben:Dann ist es meinetwegen freigestellt, ob man Strahlen oder Pixel in die Queue tut.
Vielen Dank.

ISTler
Erstie
Erstie
Beiträge: 22
Registriert: 3. Mai 2010 12:23

Re: Warteschlange

Beitrag von ISTler » 3. Jan 2012 14:16

Ist es erlaubt zwei Warteschleifen zu implementieren? Eine für die Rays die direkt vom Augpunkt auf die Szene geworfen wird und eine für die Reflexionsrays? Oder ist es zwingend erforderlich beides in eine zu schmeißen.

Antworten

Zurück zu „Archiv“