Quadtree und Fragen dazu

Supermoderator

Wohnort: Graz

07.11.2012, 18:26

Zitat von »Horus«

Ich habe herausgefunden, dass man richtig viele Threads nehmen muss um maximale Leistung zu bekommen. Ich teile die Aufgaben pro Frame in 256 unglaublich kleine Teile.

Das klingt merkwürdig, wie genau hast du das herausgefunden?

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

07.11.2012, 18:38

Naja ich lasse die Zeit pro Update anzeigen, dann ändere ich den Sourcecode, bzw. die Threadanzahl und teste wieder.
Trivialer weise gehe ich bei allen Leistungsoptimierungen so vor.

Diese Grafik zeigt den Schematischen Verlauf der Rechenzeit.
Der Effekt ist bei meinem Laptop mit 8 Cores stärker als bei meinem Tower mit 2 Cores!

Bilder zu meinem Projekt: ParSim

Zum Seitenanfang

Delop

Alter Hase

Beiträge: 610

08.11.2012, 18:13

Mal bisschen Offtopic, sorry.

Kann mir jemand erklären, wieso es unbedingt mit 256 Threads am schnellsten hier geht? Bzw. wieso dieser Graph so verläuft?

Zum Seitenanfang

Supermoderator

Wohnort: Graz

08.11.2012, 18:39

Ich bezweifle, dass wir es hier mit 256 Threads zu tun haben, vermutlich wohl eher 256 WorkItems!?
Zeig bitte mal den Code, den du jetzt verwendest und wie genau du die Zeit misst.

Zum Seitenanfang

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

08.11.2012, 18:44

Kann ich nicht sagen, da Horus' Aussagen sehr bruchstückartig sind und er irgendwie immernoch der Meinung ist, dass *wir* von *ihm* was lernen könnten. Das macht das Zusammenreimen der Vorgänge anstrengend.

Je nachdem, wie die Partikel auf die Threads verteilt werden und wie sie im Speicher angeordnet sind, könnte die Cache Locality ein solches Zeitverhalten auslösen. Man müsste hier auch mal mit einem parallel-tauglichen Profiler rangehen und zum Beispiel herausfinden, ob die Threads wirklich alle beschäftigt sind. Evtl. hängen auch einfach nur viele Threads in irgendwelchen Locks und es braucht so viele Threads, damit überhaupt irgendwer arbeitet. Oder die große Anzahl Threads sorgt einfach nur für eine statistische Streuung der 3ms Wartezeit, so dass zu jedem Zeitpunkt ein paar Threads gerade aktiv sind und Aufgaben entgegennehmen.

Normalerweise verliert man Performance, sobald man mehr logische Threads einsetzt, als die Hardware physikalische Threads besitzt. Ich kann zu solchen Fragen unbedingt die Dokumentation der Intel Threading Building Blocks empfehlen. Selbst wenn man die API dann nicht nutzt (.NET bringt dafür sicher eigene Klassen mit), lernt man da doch eine Menge über die Eigenheiten paralleler Programmierung.

Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

08.11.2012, 19:30

Hi,

ich habe meine eigene Theorie zu dem Phänomen.

Da die Engine erst weiter macht wenn alle Threads fertig sind, ist diejenige zeit in der nur auf einen letzten Thread gewartet wird "verlorene" Zeit.
Je kleiner jeder Thread ist desto kürzer muss auf den letzten gewartet werden. Der Potenziell letzte Thread ist ja winzig, wie alle anderen.

Zitat

Kann ich nicht sagen, da Horus' Aussagen sehr bruchstückartig sind und er irgendwie immernoch der Meinung ist, dass *wir* von *ihm* was lernen könnten.

Hä

Ähm Also ich will mich ja jetzt nicht Zittieren, aber ich habe oft betont dass ich keine Ahnung von dem habe was ich da mache. Ohne XNA kann ich nichtmal Grafik. Das betone ich hier gerne wieder

Ohne Fremde Hilfe aus diesem Forum hätte ich das nie hinbekommen. :thumbsup:

Zitat

Man müsste hier auch mal mit einem parallel-tauglichen Profiler rangehen und zum Beispiel herausfinden, ob die Threads wirklich alle beschäftigt sind

Ich habe die Engine in einer Console App vorab getestet. Es sind je nach CPU "nur so 4-8 Threads gleichzeitig aktiv.

Zitat

Ich bezweifle, dass wir es hier mit 256 Threads zu tun haben, vermutlich wohl eher 256 WorkItems!?
Zeig bitte mal den Code, den du jetzt verwendest und wie genau du die Zeit misst.

Ja es sind natürlich 256 Woritems :pinch:

Sorry.
Die Zeit messe ich in dem XNA Thread, der Update Methode, Die Engine ist ja in einem Separaten Thread.

	C#-Quelltext
1	UpdatingTime = ((0.001f * (float)gameTime.TotalGameTime.Milliseconds)+(float)gameTime.TotalGameTime.Seconds + (60 * (float)gameTime.TotalGameTime.Minutes)) / SimulationEngine.Frame;

Der Engine Thread macht dauernd diese Schleife:

C#-Quelltext

while (RunEngine)
            {
                FinishedThreads = 0;
                for (int i = 0; i < Config.InitThreads; i++)
                    ThreadPool.UnsafeQueueUserWorkItem(PhysicalSimulation, i);
                while (FinishedThreads < Config.InitThreads)//Warten dass alle fertig werden //GEHT SO NICHT 
                    System.Threading.Thread.Sleep(1);


                FinishedThreads = 0;
                for (int i = 0; i < Config.InitThreads; i++)
                    ThreadPool.UnsafeQueueUserWorkItem(CollisionDetection, i);
                while (FinishedThreads < Config.InitThreads)//Warten dass alle fertig werden //GEHT SO NICHT 
                    System.Threading.Thread.Sleep(1);

                FinishedThreads = 0;
                for (int i = 0; i < Config.InitThreads; i++)
                    ThreadPool.UnsafeQueueUserWorkItem(Walls, i);
                while (FinishedThreads < Config.InitThreads)//Warten dass alle fertig werden //GEHT SO NICHT 
                    System.Threading.Thread.Sleep(1);

                Frame++;
}

Config.InitThreads ist auf 256.
FinishedThreads wird am Ende jedes Threads im Threadpool erhöht (interlocked)

Vielleicht nutze ich diesen Moment meine Frage von Vorher erneut zu stellen.

Wie kann ich das umgehen. Es wird unnötig gewartet.

	C#-Quelltext
1 2	while (FinishedThreads < Config.InitThreads)//Warten dass alle fertig werden //GEHT SO NICHT System.Threading.Thread.Sleep(1);

Suspend und Resume kann man nicht aus einem Thread aufrufen

Sie sind zudem Veraltet.

Mutex WaitHandle wäre auch schön aber ich muss dem Thread einen Parameter Übergeben. Dies gelingt nicht!

	C#-Quelltext
1	ThreadPool.UnsafeQueueUserWorkItem(PhysicalSimulation, i);

habe ich mit WaitHandle probiert als

	Quellcode
1	ThreadPool.UnsafeQueueUserWorkItem(new Waithandle (PhysicalSimulation), waitHandle);

für den Parameter i ist kein Platz mehr

Wie soll es aber dann gehen?

LG

Bilder zu meinem Projekt: ParSim

Zum Seitenanfang

Supermoderator

Wohnort: Graz

08.11.2012, 20:43

Anstatt in einer Schleife zu warten (sog. Busy Wait), verwend besser z.B. ein Manual Reset Event. Ein Event ist ein Synchronisationsobjekt, das zwei mögliche Zustände hat: Signaled oder Nonsignaled. Ein Thread kann auf ein Event warten. Wenn das Event Nonsignaled ist, wird der Thread dabei schlafengelegt, sobald das Event in den Signaled Zustand übergeht, werden alle auf dem Event schlafenden Threads aufgeweckt. In C# entspricht das einem EventWaitHandle mit ManualReset. Bevor du die Work Items in die Queue packst, setzt du den Counter z.B. auf 256 und resettest das Event. Der Hauptthread wartet dann auf das Event. Deine Work Items dekrementieren den Counter z.B. per Interlocked.Decrement() und wenn er 0 erreicht, wird das Event gesetzt und der Hauptthread läuft weiter...

Btw: Wenn du z.B. in einem Busy Wait einfach nur die Kontrolle über die CPU an das System zurückgeben willst, dann verwend Thread.Yield() (entspricht unter Windows einem Sleep(0)) anstatt Thread.Sleep(1).

Dieser Beitrag wurde bereits 6 mal editiert, zuletzt von »dot« (08.11.2012, 20:57)

Zum Seitenanfang

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

08.11.2012, 21:07

Mit einer Unterteilung auf 256 Segmente ergibt die Kurve übrigens perfekten Sinn :-) Wenn man die Gesamtarbeit in zu wenige große Segmente unterteilt, kann die Arbeitslast nicht gleichmäßig auf die Threads verteilt werden und die Gesamtzeit steigt. Wenn man die Gesamtarbeit in zuviele kleine Segmente unterteilt, frisst der Arbeitsaufwand für die Zuordnung der Segmente einen Teil des Parallelisierungsgewinns wieder auf.

Das Signalisieren wie von dot vorgeschlagen ist dann der Trick, mit dem man die Latenz loswird, die vergeht, bis ein Arbeitsthread merkt, dass er Arbeit hat, und loslegt. Dot, weißt Du evtl. auch, ob es sowas auch in der C++11-Threadbibliothek gibt? Busy Wait in den Worker Threads funktioniert zwar, ist aber unschön. Und permanentes Yield() der Worker Threads ist eine Katastrophe für die Leistung des Gesamtsystems - da fängt alles an zu ruckeln, selbst der Mauszeiger, weil Windows mit x Millionen Task Switches pro Sekunde beschäftigt ist. Also muss man die Worker Threads irgendwie schlafen legen und per Signal aufwecken, wenn es was zu tun gibt. Und ich habe bisher nichts in C++11 Threads gefunden, um das zu bewerkstelligen.

Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Zum Seitenanfang

Supermoderator

Wohnort: Graz

08.11.2012, 21:18

Events sind Windows Kernel Objects, das .NET EventWaitHandle ist nur ein Wrapper um die entsprechenden Win32 APIs, die du natürlich ganz besonders auch in C++ verwenden kannst. Die C++11 Standardbibliothek hat afaik nichts direkt vergleichbares, Condition Variablen sind Events etwas ähnlich, aber leider immer mit dem Acquiren eines Mutex verbunden. Aber ich glaube, std::async() und futures könnten dir gefallen...