Meinung zu Software Design

[Corrail]

Hallo!

Ich hab vor längerem beschlossen mein 3D Framework neu zu schreiben und damit bis zu EXT_FBO zu warten. Naja, und da FBO nun endlich da ist (naja, wenigstens auf dem Papier ;) ) werd ich ans Werk gehen.
Ich bin derzeit am Überlegen wie ich das ganze aufbaue und habe hier einige Ideen zusammen gefasst zu denen ich um Meinungen bitte. Also eine erste Vorraussetzung für mich war, dass ganze Multithreaded zu machen (um zukünfitge Prozessoren und Multiprozessorsysteme zu unterstützen).

So, nun zu meinem vorläufigem Design:

Ich habe folgende Module:
Output_Renderer, Output_Audio, ...
Input_Periphery, Input_Network, ...
Logic_Physic, Logic_AI, ...


Meine Idee ist es die Daten doppelt im Arbeitsspeicher zu haben. Einmal den letzten aktuellen fertig berechneten Stand für die Output Module, die darauf nur mit read zugreifen. Somit kann ich jedes Output Modul ohne Probleme in einen eigenen Thread hauen. Diese Module sind dann auch unabhängig von anderen Module (sie müssen nicht auf andere Module warten).
Neben der aktuellen Version der Daten gibt es eine Version an der gerade berechnet wird. Sobald die fertig ist wird diese kopiert, die alte aktuelle gelöscht, usw.

Für die anderen Module, die read/write Zugriffe haben, hab ich ein simples Change_Data Modul welches die Daten echt ändert. Die Input und Logic Module ändern nicht direkt die Daten sondern schicken eine Message an das Change_Data Modul wo diese Message dann in einer Queue landet. Das Change_Data Modul arbeitet diese dann sequenziell ab. Wenn alle Module fertig sind und das Change_Data Modul die Queue fertig abgearbeitet hat werden die Daten kopiert, die alten aktuellen Daten gelöscht, usw.

Was haltet ihr von davon?

[Trap]

Die Idee die Daten einfach doppelt zu behalten hatte ich auch. Ob es praktisch effizient funktioniert weiß ich nicht.
Elemente kopieren muss doch nicht sein, wie bei Front- und Backbuffer einfach umschalten welche gültig sind.

Welche Sprache nimmst du? C++?

[Corrail]

Die Idee die Daten einfach doppelt zu behalten hatte ich auch. Ob es praktisch effizient funktioniert weiß ich nicht.
Elemente kopieren muss doch nicht sein, wie bei Front- und Backbuffer einfach umschalten welche gültig sind.

Welche Sprache nimmst du? C++?

Naja, das Problem ist aber wie kann ich sonst gleichzeitig was darstellen und was ändern ohne dass es zu Konflikten kommt. Somit brauche ich IMO sehr wohl 2 Versionen.
Ok, das mim Copy ist nicht unbedingt notwendig, reicht ein Pointer Switch auch. War nur mal theoretisch überlegt.

Ja, C++. So Platform unabhängig wie nur möglich, also OpenGL, SDL, OpenAL, ...

[del_4901]

Hallo!

Ich hab vor längerem beschlossen mein 3D Framework neu zu schreiben und damit bis zu EXT_FBO zu warten. Naja, und da FBO nun endlich da ist (naja, wenigstens auf dem Papier ;) ) werd ich ans Werk gehen.
Ich bin derzeit am Überlegen wie ich das ganze aufbaue und habe hier einige Ideen zusammen gefasst zu denen ich um Meinungen bitte. Also eine erste Vorraussetzung für mich war, dass ganze Multithreaded zu machen (um zukünfitge Prozessoren und Multiprozessorsysteme zu unterstützen).

So, nun zu meinem vorläufigem Design:

Ich habe folgende Module:
Output_Renderer, Output_Audio, ...
Input_Periphery, Input_Network, ...
Logic_Physic, Logic_AI, ...


Meine Idee ist es die Daten doppelt im Arbeitsspeicher zu haben. Einmal den letzten aktuellen fertig berechneten Stand für die Output Module, die darauf nur mit read zugreifen. Somit kann ich jedes Output Modul ohne Probleme in einen eigenen Thread hauen. Diese Module sind dann auch unabhängig von anderen Module (sie müssen nicht auf andere Module warten).
Neben der aktuellen Version der Daten gibt es eine Version an der gerade berechnet wird. Sobald die fertig ist wird diese kopiert, die alte aktuelle gelöscht, usw.

Für die anderen Module, die read/write Zugriffe haben, hab ich ein simples Change_Data Modul welches die Daten echt ändert. Die Input und Logic Module ändern nicht direkt die Daten sondern schicken eine Message an das Change_Data Modul wo diese Message dann in einer Queue landet. Das Change_Data Modul arbeitet diese dann sequenziell ab. Wenn alle Module fertig sind und das Change_Data Modul die Queue fertig abgearbeitet hat werden die Daten kopiert, die alten aktuellen Daten gelöscht, usw.

Was haltet ihr von davon?

So eine Idee in der Art hatte ich auch schon, aber die Syncro könnte sich als schwierig erweisen. Wann willst du denn einen switsch machen? Wenn die Inputs fertig berrechnet sind, oder wenn die Outputs fertig sind mit Rendern? So wartet doch immer Einer auf den Anderen. Und wenn du bei so komplexen Objekten einfach mal zwischendrin switcht, kann es zu ganz üblen Inkonsistenzen kommen. Ich denke du musst das ganze noch kleiner hacken, aber so das die syncro nicht zum Problem wird. Ausserdem kannst du ja nur immer ein Objekt auf einer CPU laufen lassen, nehmen wir mal an du hast 6 Objekte, und 2 DualCore CPUs wo jede noch mal 2 Virtuelle CPUs hat -> sprich 8 CPUs -> dann langweilen sich 2.

[Corrail]

So eine Idee in der Art hatte ich auch schon, aber die Syncro könnte sich als schwierig erweisen. Wann willst du denn einen switsch machen? Wenn die Inputs fertig berrechnet sind, oder wenn die Outputs fertig sind mit Rendern? So wartet doch immer Einer auf den Anderen. Und wenn du bei so komplexen Objekten einfach mal zwischendrin switcht, kann es zu ganz üblen Inkonsistenzen kommen. Ich denke du musst das ganze noch kleiner hacken, aber so das die syncro nicht zum Problem wird. Ausserdem kannst du ja nur immer ein Objekt auf einer CPU laufen lassen, nehmen wir mal an du hast 6 Objekte, und 2 DualCore CPUs wo jede noch mal 2 Virtuelle CPUs hat -> sprich 8 CPUs -> dann langweilen sich 2.

Danke! An das mim Switchen hab ich noch nicht so genau gedacht. Sollte aber auch kein Problem sein wenn man die Daten 3 mal im Speicher ablegt. Also wenn das Change_Data fertig ist und die aktuellen Daten noch gebraucht werden eine dritte Kopie anlegen auf der dann die Input und Logic Module bzw. das Change_Data Modul arbeitet.
Die Frage ist halt ob es sich vom Arbeitsspeicher her vernünftig ausgeht...

[del_4901]

Danke! An das mim Switchen hab ich noch nicht so genau gedacht. Sollte aber auch kein Problem sein wenn man die Daten 3 mal im Speicher ablegt. Also wenn das Change_Data fertig ist und die aktuellen Daten noch gebraucht werden eine dritte Kopie anlegen auf der dann die Input und Logic Module bzw. das Change_Data Modul arbeitet.
Die Frage ist halt ob es sich vom Arbeitsspeicher her vernünftig ausgeht...

Das ändert trotzdem nichts daran das die Last nicht optimal verteilt wird. Irgendwann muss immer einer auf den Anderen warten weil die Objekte zu groß sind.

[Corrail]

Das ändert trotzdem nichts daran das die Last nicht optimal verteilt wird. Irgendwann muss immer einer auf den Anderen warten weil die Objekte zu groß sind.

Aber die Last werd ich nie optimal verteilen können. Ein Physik Modul wird z.B. viel mehr Ressourcen brauchen als ein Input Modul

[Demirug]

Aber die Last werd ich nie optimal verteilen können. Ein Physik Modul wird z.B. viel mehr Ressourcen brauchen als ein Input Modul

Genaus deswegen verteilen wir bei uns nicht auf Modul Ebene sonder auf einem Submodul Level.

Jedes Modul startet beim Einsprung dazu eine Reihe von microJobs mit den dazugehörigen Abhängigkeiten. Der im Hintergrund arbeitende Scheduler kümmert sich dann darum das alle activen Jobs auf die verfügbaren CPUs verteilt und ausgeführt werden. Der Einsprung in ein Modul ist dabei selbst auch wieder ein solcher Microjob der wiederum abhängigkeiten haben kann. Zum Beispiel den Aussprung eines anderen Moduls. Solange man genügend active Microjobs hat hält man die CPUs immer schön unter Last.

[Trap]

Nur den Datendurchsatz optimieren ist kontraproduktiv sobald es auf Kosten der Latenz geht. Wenn man länger wartet hat man natürlich mehr zu erledigende Aufgaben und kann mehr gleichzeitig abarbeiten, nur ist es bei Spielen nicht gut wenn zwischen Ein- und Ausgabe eine größere Verzögerung gibt.

Ich finde es immer wieder absolut grausam, wenn man Sprachen mit nur für Singlethreadanwendungen definierter Semantik Multithreadanwendungen schreibt. Es endet darin, dass man sich selbst eine Semantik ausdenken muss und die dann an 90% der Stellen selbst implementiert und am Rest vergisst oder falsch implementiert.

[Corrail]

Genaus deswegen verteilen wir bei uns nicht auf Modul Ebene sonder auf einem Submodul Level.

Jedes Modul startet beim Einsprung dazu eine Reihe von microJobs mit den dazugehörigen Abhängigkeiten. Der im Hintergrund arbeitende Scheduler kümmert sich dann darum das alle activen Jobs auf die verfügbaren CPUs verteilt und ausgeführt werden. Der Einsprung in ein Modul ist dabei selbst auch wieder ein solcher Microjob der wiederum abhängigkeiten haben kann. Zum Beispiel den Aussprung eines anderen Moduls. Solange man genügend active Microjobs hat hält man die CPUs immer schön unter Last.

hm, lohnt sich der Aufwand hier überhaupt? Ich mein weniger der programmiertechnische Aufwand sondern der Mehr-Aufwand den du mit dem Scheduler usw. hast.
Und darf ich fragen welche Threading Bibliothek du dafür verwendest?

@Trap
Ok, deine Argumente sind einleuchtend. Und ich will das Framework dann für Spiele, ... verwenden. Aber was würdest du mir in dieser Hinsicht empfehlen?

[Demirug]

hm, lohnt sich der Aufwand hier überhaupt? Ich mein weniger der programmiertechnische Aufwand sondern der Mehr-Aufwand den du mit dem Scheduler usw. hast.
Und darf ich fragen welche Threading Bibliothek du dafür verwendest?

Der Scheduler ist ein ganz einfaches Teil der nicht viel mehr macht als eine FIFO Liste zu verwalten. Ich brauche und will ja kein vollständiges Thread Model. So können Jobs wenn sie mal gestartet sind nicht von anderen verdrängt werden sondern laufen immer komplett durch. Ist vom Aufwand daher nicht viel größer als wenn man die Listen mit den zu erledigenden Arbeiten direkt durchlaufen würde.

Da ist keine Threading Bibliothek dahinter. Warum auch? Ich starte für jede CPU einen identischen Thread und die arbeiten die FIFO ab. Diese ist zugleich das einzige Objekt welches Locks benötigt.

[Corrail]

Der Scheduler ist ein ganz einfaches Teil der nicht viel mehr macht als eine FIFO Liste zu verwalten. Ich brauche und will ja kein vollständiges Thread Model. So können Jobs wenn sie mal gestartet sind nicht von anderen verdrängt werden sondern laufen immer komplett durch. Ist vom Aufwand daher nicht viel größer als wenn man die Listen mit den zu erledigenden Arbeiten direkt durchlaufen würde.

Da ist keine Threading Bibliothek dahinter. Warum auch? Ich starte für jede CPU einen identischen Thread und die arbeiten die FIFO ab. Diese ist zugleich das einzige Objekt welches Locks benötigt.

Aso, dann hab ich das vorher falsch verstanden.
Wie teilst du da aber die einzelnen Code der Module in die microJobs? Hardcoded?

[Demirug]

Aso, dann hab ich das vorher falsch verstanden.
Wie teilst du da aber die einzelnen Code der Module in die microJobs? Hardcoded?

Man könnte es als Hardcoded bezeichnen. Das hört sich allerdings komplizierter an als es wirklich ist. Als MicroJobs kann jede Methode mit einer speziellen Struktur (keine Parameter, kein Rückgabewert) ausgeführt werden. Wenn wir der Meinung sind das diese Aufgabe sich gut als Microjob eignet rufen wir an der entsprechenden Stelle im Code die Mode nicht mehr direkt auf sondern sie wird als Parameter einer anderen Funktion übergeben wodurch sie alws Microjob laufen wird. Man kann also klasischen Code sehr schnell anpassen.

[zeckensack]

Man könnte es als Hardcoded bezeichnen. Das hört sich allerdings komplizierter an als es wirklich ist. Als MicroJobs kann jede Methode mit einer speziellen Struktur (keine Parameter, kein Rückgabewert) ausgeführt werden. Wenn wir der Meinung sind das diese Aufgabe sich gut als Microjob eignet rufen wir an der entsprechenden Stelle im Code die Mode nicht mehr direkt auf sondern sie wird als Parameter einer anderen Funktion übergeben wodurch sie alws Microjob laufen wird. Man kann also klasischen Code sehr schnell anpassen.Jobs mit Parametern kann man relativ leicht abarbeiten, indem man mehrere Kommandostrukturen der entsprechenden Größe anlegt, und dann jeweils vor die Struktur einen Header in den FIFO legt, der angibt wie groß das ganze Kommando (inklusive Header) ist. Man muss dabei speziell darauf achten, dass Wraparound funktioniert. Die einfachste Lösung ist ein NOP-Kommando, das (dank des Headers) beliebig groß sein kann, und somit den Platz vor dem Wraparound konsumiert.

Praktisch ist's auch keine blöde Idee, die Kommandos großzügig aufzurunden. Ich mache es zB so dass ein Kommando inklusive Header immer ein ganzzahliges Vielfaches von 32 Byte im FIFO belegt. Die Idee ist dass mehrere CPUs parallel auf den FIFO lesend zugreifen können sollen, und es wäre ziemlich übel wenn sie das innerhalb der gleichen Cache-Line machen. Ein gewisser garantierter Mindestabstand zwischen Produzent und Verbraucher schränkt das ein, obwohl natürlich Bandbreite verschwendet wird (das ist aber sehr sehr wenig, maximal zweistelliger MB/s-Bereich, wenn ich von meinem Fall ausgehe).

Rückgabewerte kann man sich über einen zweiten Rückgabe-FIFO holen, oder bei Kommandos die sowieso warten müssen einfach über den lokalen Stack des Produzenten. Lokale Variable anlegen, Zeiger durch den FIFO schießen. Wenn der Arbeiterthread fertig ist, legt er seinen Rückgabewert dort ab und lässt den Produzenten weiterlaufen.

[Demirug]

Zecki, Parameter sind kein Problem weil ich die Jobs mit Objekten verknüpfen kann. Ein Job enthält also neben dem Verweiss auf die Methode auch noch Optional einen Verweiss auf das Objekt bei dem diese Methode ausgeführt werden soll. Optional ist hier natürlich relative weil man das Objekt immer Angeben muss ausser bei statischen Methoden. Wenn ich Parameter brauche speichere ich die einfach im Objekt selbst oder benutze ein entsprechendes Pattern bei dem ein Hilfsobjekt mit den Parametern die eigentliche Methode aufruft.

Rückgabewerte sind ähnlich organisiert. Diese werden einfach wieder in den Objekten abgelegt. Braucht nun ein andere Job diesen Wert sind zum einen die Objekte verknüpft so das er sich den Rückgabewert holen kann und zum anderen sind die Jobs entsprechend in ein Abhängigkeitsverhältniss gesetzt. Dadurch wird der Job B erst dann freigegeben wenn Job A ausgeführt wurde.

Der wichtige Punkt dabei ist das nur noch über diese Jobs gearbeitet werden darf. Das Programm fügt am Anfang einen initalen Job in das System ein und startet pro CPU einen Thread (kann ich aber verändern). Dann laufen alle Threads in einer Schleife und warten auf Jobs. Der erste Job hat dann die Aufgabe weitere Jobs zu erzeugen. Sobald kein einziger Job mehr im Scheduler ist werden die zusätzlichen Threads beendet und dann das Programm. Das einzige was gefärhlich werden kann sind zirkuläre Abhängigkeiten bei den Jobs die dazu führen das der Scheduler zwar noch Jobs enthält aber keinen zur Ausführung bringen kann weil alle auf das Ende eines anderen warten. Wahrscheinlich werde ich dafür noch einen Watchdog einbauen der sowas erkennt.

[Corrail]

Die Möglichkeit hört sich interessant an!
Ich weiß, ich frag viel... ;)
Aber wie hadhabt ihr die Zugriffe auf Speicher? Also ich hab pro CPU einen Thread laufen wo die Microjobs abgearbeitet werden. Was ist aber wenn 2 Microjobs auf die gleichen Daten zugreifen wollen (min. einer schreibend). Machts ihr das mit normalen Abhängigkeiten oder mit Speichermasken oder so?

[Demirug]

Die Möglichkeit hört sich interessant an!
Ich weiß, ich frag viel... ;)
Aber wie hadhabt ihr die Zugriffe auf Speicher? Also ich hab pro CPU einen Thread laufen wo die Microjobs abgearbeitet werden. Was ist aber wenn 2 Microjobs auf die gleichen Daten zugreifen wollen (min. einer schreibend). Machts ihr das mit normalen Abhängigkeiten oder mit Speichermasken oder so?

Hängt vom genauen Anwendungsfall ab.

Die einzelnen Module sind ja nach wie vor in Serie syncronisiert. Soll heisen wenn die Microjobs für die Verarbeitung laufen kann ich sicher sein das sich die Eingangsdaten nicht mehr verändern. Darum kann ich da direkt lesen ohne befürchten zu müssen das mir ein anderer Job die Eingangsdaten ändert.

kritisch sind nur Fälle in denen Modulglobale Daten verändert werden müssen auf die eine Reihe von Jobs aus dem gleichen Modul zugreifen wollen. Dafür habe ich drei Pattern.

1. Alle Jobs die diese Daten brauchen sind über den Job der sie ändert blockiert. Erst wenn dieser gelaufen ist werden sie freigegeben.

2. Die veränderung wird erst am Ende durchgeführt und der Job startet erst wenn alle Jobs die diese Daten benötigt haben gelaufen sind.

3. Das ist eine Variante von 2. Dabei sind die Arbeitsjobs in zwei Phasen geteilt. Phase 1 holt sich die globalen Daten zum Zwischenspeichern und Phase 2 rechnet dann. Sobald alle Jobs Phase 1 beendet haben wird der Job zum verändern der Globaldaten freigegeben.

[del_4901]

Sagt euch "Single Writer Multiple Reader Protokoll mit Invalidierung und Gruppenzuordnung" was? Das sollte einfach genug zu implementieren sein. Und im falle eines Games effizient genug.

[KiBa]

@demirug
auf welcher ebene habe ich mir solche microjobs vorzustellen?
mir fällt da zum beispiel eine baumtravesierung ein, wo in jedem knoten ein test ausgeführt wird. (z.b. bbox test)
nun könnte man für die wurzel einen solchen node-test-job erzeugen, der wiederum einen bbox-test-job erzeugt, von dem er selbst abhängt. ist dieser bbox-job durchgelaufen, prüft der node-test-job, ob der bbox-test erfolgreich war. ist dies der fall, erzeugt er für jedes seiner kinder einen neuen node-test-job...
wäre das ein geeigneter fall für einen micro-job oder läuft das anders?