PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Verkehrssimulation: Ein Thread für alles vs. 1 Thread pro Auto


Verkehrsminister
2011-09-03, 22:23:15
Hallo!

Für die Vorlesung "Simulation" muss ich eine eben solche anfertigen, als Visualisierung durch ein Programm. Habe mich für eine Verkehrssimulation entschieden.
Als ich mit dem Prof das ganze mal besprochen habe meinte er, man könnte ja jedes Fahrzeug durch einen Thread verwalten lassen - klang für mich erst mal logisch, jedes Fahrzeug wäre so eben eine isolierte, selbst rechnende Einheit.
Habe dann aber etwas nachgedacht, vor allem darüber, wie Computerspiele eigentlich funktionieren. Wenn ich mich nicht irre, dann hat man dort doch nur einen Hauptthread mit einer Schleife, bei jedem Durchgang wird alles was berechnet werden muss berechnet und die Schleife beginnt von vorne. Schleifendurchläufe pro Sekunde resultieren ja dann als die bekannten "Frames per Second" (ja ich weiß, man hat Logik-fps und Grafik-fps in modernen Spielen wohl getrennt, aber für solch eine Simulation kann ich sicher beides in einem machen).

Was sind eure Gedanken, wo liegen nicht von mir bedachte pros/cons?

Danke!

Gast
2011-09-03, 22:40:24
Ich würde zuerst mit der einfacheren Variante anfangen, d.h. nur einen "Haupt"-Thread erstellen, der dann nacheinander alle Fahrzeuge abarbeitet. Ein Durchlauf deines "Haupt"-Threads entspricht dann einer Zeiteinheit deiner Simulation (z.B. 100 ms). Dies hat den Vorteil, dass alles "synchron" abläuft und man z.B. Fahrzeug-Kollisionen recht einfach ermitteln kann.

Pro Fahrzeug ein Thread ist dann schon eher die "fortgeschrittenere" Lösung, erfordert aber auch mehr Hintergrundwissen bzgl. nebenläufiger Programmierung (Synchronisation, etc.). Ist halt von der Umsetzung her komplexer, das Ergebnis sollte aber dasselbe sein wie bei der einfacheren Variante. ;)

universaL
2011-09-04, 10:42:12
je nach eingesetzter programmiersprache könnten "threads" auch die anzahl der fahrzeuge dann limitieren ;) davon kann man ja leider auch nur begrenzt viele erstellen.

Senior Sanchez
2011-09-04, 12:00:48
Ich finde die Antwort von Gast schon mal sehr treffend.

Eine weitere Frage ist ja auch, wie viel Fahrzeuge du simulieren willst. Sprechen wir hier von 100 oder 100.000? Für geringe Anzahlen würde ich mir den Stress mit den Threads, zumindest wenn die Berechnungen auch einfach sind, nicht machen. Klar ist das cool und es macht Spaß, wenns schneller läuft, aber man sollte es auch nur machen, wenns wirklich notwendig ist.

Stattdessen würde ich mich an deiner Stelle mehr auf das Simulationsmodell konzentrieren.

Wozu musst du das eigentlich komplett selber implementieren? Es gibt ja auch schon fertige Simulationssprachen und -tools. Die sind wesentlich leistungsfähiger als das, was du in der Zeit schaffst zu implementieren. Da kannst du dann leicht verschiedene Verteilungen und Parameter testen oder auch diagrammartige Visualisierungen durchführen.

Gast
2011-09-04, 12:32:47
Erzähl doch mal ein wenig mehr über die Smulation bzw. was genau du dort umsetzen möchtest. Ich könnte mir vorstellen, dass dies schon umfangreich genug wird (Mehrspurige Straßen, Ampel-Steuerungen, grafische Ausgabe) und dann die Frage, ob Multi-Core-Optimierung durch Threads wirklich notwendig ist, eher eine untergeordnete Rolle spielt.

Gast
2011-09-04, 13:17:00
1.) Threads macht man in erster Linie nicht, um eine Multi Core Optimierung einzubauen, sondern, wenn tatsächlich mehrere Aktionen parallel laufen sollen z.B. ein Webserver, der mehrere Clients gleichzeitig bedient oder ein Hintergrundthread, der das GUI nicht blockieren soll.

2.) Zuerst kommt die Logik, dann kommen allgemeine Optimierungen, nachdem man einmal mit dem Profiler geschaut hat, wo die Performancelücken sind und erst wenn man dann nicht mehr weiter kommt, kann man anfangen, auf mehrere Kerne zu optimieren.

3.) Thread Operationen sind performanceintensiv. Bei 10 Fahrzeugen, die jeweils eine ziemlich komplexe Logik haben, macht es eventuell Sinn, diese als einzelnen Thread laufen zu lassen. Bei 1.000 Fahrzeugen oder mehr mit jeweils einer einfachen, kurzen Logik (wie in einem Computerspiel mit nur 20ms pro Frame), macht es keinen Sinn, besonders wenn man die Anzahl der Fahrzeuge nicht kennt. Hier sollte man mit nur einem Thread anfangen und dann gegebenenfalls auf eine fixe Anzahl (z.B. 4 Threads) aufteilen, wenn man mehrere Kerne ausnutzen will, aber das kommt ganz zum Schluss, wenn die Logik einmal steht.

4.) Werden viele Daten gemeinsam mit sowohl Schreib- als auch Lesezugriffen genutzt. Ist dies der Fall, so sollte man die Multi Thread Geschichten generell bleiben lassen, weil sonst alles nur in einer Menge Arbeit, instabilem Code und weniger Performance endet.

Trap
2011-09-04, 13:27:41
Grundsätzlich gibt es bei Simulationen 2 Ansätze:
a) Diskrete Zeitschritte -> Z_n+1=f(Z_n) mit Z=Zustand
b) Ereignisbasierend -> z.B. Schaltungssimulation, Ereignis "Eingang wechselt Wert" ergibt "Ausgang wechselt wert in X Zeiteinheiten", immer das Ereignis mit kleinster Zeit bearbeiten

Bei diskreten Zeitschritten ist die Parallelisierung trivial (jeder Zeitschritt ist eine einfache Funktion über einen Vektor). Bei Ereignissen hat man das Problem mit dem "immer das Ereignis mit kleinster Zeit bearbeiten" Teil, da ist Parallelisierung schwieriger.

Der ein Thread pro Auto Ansatz ist nur interessant wenn man es als distributed Computing Problem betrachteten möchte und selbst dann ist es nicht unbedingt die beste Idee. Als Übung für Parallelverarbeitung ist es wohl ganz brauchbar ;)

Berni
2011-09-04, 15:32:10
Habe sowas mal selber geschrieben...ich habe das aus Performancegründen in Schleifen durchgeführt. Allerdings wurde die Karte in einzelne Regionen aufgeteilt die in separaten Threads berechnet wurden (25 Schritte pro Sekunde). Somit kann man auch Mutlicoreprozessorsysteme bei größeren Simulationen ausnutzen. Nach den ganzen Berechnungen erfolgt dann jeweils die grafische Ausgabe der aktuellen Situation. Wichtig bei einer Simulation ist im Übrigen auch die Reproduzierbarkeit, d.h. wenn du dasselbe Programm nochmal laufen lässt sollte auch dasselbe rauskommen (oder es sollte zumindest möglich sein; denkbar sind natürlich auch an einigen Stellen Zufallsgeschichten). Mit entsprechenden Schleifen ist das deutlich einfacher zu gewährleisten.

Die Probleme an 1 Thread pro Fahrzeug sind wie die Vorredner schon sagten erst bei großen Mengen relevant. Es kommt dann zu folgenden Dingen:
1. Die Anzahl der Threads kann vom Betriebssystem her limitiert sein.
2. Jeder Thread benötigt etwas RAM für seinen Stack.
3. Das nötige Threadswitching kostet mitunter wahnsinnig Performance wenn man nicht wirklich ein massiv paralleles System hat. Zudem sind die Caches der CPU dann oft falsch gefüllt was weitere Performance kostet

Letztlich muss ich sagen, dass so eine Simulation wahnsinnig aufwändig werden kann und sowas letztlich nie fertig ist weil man immer was dranbauen kann. Schon allein das Bauen des Grundsystems (Laden/Speichern von Karten, evtl. Import aus OpenStreetMap, Routingalgorithmus, die ganze grafische Darstellung) dauert ne ganze Weile. Solltest du vielleicht vorher genau mit dem Professor ausmachen was das Ganze umfassen soll.