Effizientes Trennen von Lese- / Rechen- / Schreibschritten für die gleichzeitige Verarbeitung von Entitäten in Entitäts- / Komponentensystemen

Installieren

Ich habe eine Entitätskomponentenarchitektur, in der Entitäten eine Reihe von Attributen haben können (die reine Daten ohne Verhalten sind), und es gibt Systeme, die die Entitätslogik ausführen, die auf diese Daten einwirken. Im Wesentlichen in etwas Pseudocode:

Entity
{
    id;
    map<id_type, Attribute> attributes;
}

System
{
    update();
    vector<Entity> entities;
}

Ein System, das sich nur mit einer konstanten Geschwindigkeit entlang aller Entitäten bewegt, könnte es sein

MovementSystem extends System
{
   update()
   {
      for each entity in entities
        position = entity.attributes["position"];
        position += vec3(1,1,1);
   }
}

Im Wesentlichen versuche ich, update () so effizient wie möglich zu parallelisieren. Dies kann erreicht werden, indem ganze Systeme parallel ausgeführt werden oder indem jedem Update () eines Systems mehrere Komponenten zugewiesen werden, damit verschiedene Threads das Update desselben Systems ausführen können, jedoch für eine andere Teilmenge von Entitäten, die bei diesem System registriert sind.

Problem

Im Fall des gezeigten MovementSystems ist die Parallelisierung trivial. Da Entitäten nicht voneinander abhängig sind und keine gemeinsam genutzten Daten ändern, können wir einfach alle Entitäten parallel verschieben.

Diese Systeme erfordern jedoch manchmal, dass Entitäten miteinander interagieren (Daten von / nach lesen / schreiben), manchmal innerhalb desselben Systems, aber häufig zwischen verschiedenen Systemen, die voneinander abhängen.

Beispielsweise können in einem Physiksystem Entitäten manchmal miteinander interagieren. Zwei Objekte kollidieren, ihre Positionen, Geschwindigkeiten und andere Attribute werden von ihnen gelesen, aktualisiert und dann werden die aktualisierten Attribute in beide Entitäten zurückgeschrieben.

Bevor das Rendering-System in der Engine mit dem Rendern von Entitäten beginnen kann, muss es warten, bis andere Systeme die Ausführung abgeschlossen haben, um sicherzustellen, dass alle relevanten Attribute den Anforderungen entsprechen.

Wenn wir versuchen, dies blind zu parallelisieren, führt dies zu klassischen Rennbedingungen, bei denen verschiedene Systeme gleichzeitig Daten lesen und ändern können.

Im Idealfall gibt es eine Lösung, bei der alle Systeme Daten von beliebigen Entitäten lesen können, ohne sich Sorgen machen zu müssen, dass andere Systeme dieselben Daten gleichzeitig ändern, und ohne dass der Programmierer sich um die ordnungsgemäße Anordnung der Ausführung und Parallelisierung von kümmert diese Systeme manuell (was manchmal gar nicht möglich ist).

In einer grundlegenden Implementierung könnte dies erreicht werden, indem einfach alle Datenlesevorgänge und -schreibvorgänge in kritischen Abschnitten abgelegt werden (wobei sie mit Mutexen geschützt werden). Dies führt jedoch zu einem hohen Laufzeitaufwand und ist wahrscheinlich nicht für leistungsempfindliche Anwendungen geeignet.

Lösung?

Meiner Meinung nach wäre eine mögliche Lösung ein System, bei dem das Lesen / Aktualisieren und Schreiben von Daten getrennt ist, sodass Systeme in einer teuren Phase nur Daten lesen und berechnen, was sie zum Berechnen benötigen, die Ergebnisse irgendwie zwischenspeichern und dann alle schreiben Die geänderten Daten werden in einem separaten Schreibdurchlauf an die Zielentitäten zurückgesendet. Alle Systeme würden auf die Daten in dem Zustand reagieren, in dem sie sich am Anfang des Rahmens befanden, und dann vor dem Ende des Rahmens, wenn alle Systeme die Aktualisierung abgeschlossen haben, wird ein serialisierter Schreibdurchlauf durchgeführt, bei dem die zwischengespeicherten Ergebnisse aus allen unterschiedlichen Ergebnissen resultieren Systeme werden durchlaufen und in die Zielentitäten zurückgeschrieben.

Dies basiert auf der (möglicherweise falschen?) Idee, dass der einfache Parallelisierungsgewinn groß genug sein könnte, um die Kosten (sowohl hinsichtlich der Laufzeitleistung als auch des Code-Overheads) für das Zwischenspeichern der Ergebnisse und den Schreibdurchlauf zu übertreffen.

Die Frage

Wie könnte ein solches System implementiert werden, um eine optimale Leistung zu erzielen? Was sind die Implementierungsdetails eines solchen Systems und was sind die Voraussetzungen für ein Entity-Component-System, das diese Lösung verwenden möchte?

----- (basierend auf der überarbeiteten Frage)

Erster Punkt: Da Sie nicht erwähnen, dass Sie Ihre Release-Build-Laufzeit profiliert und einen bestimmten Bedarf festgestellt haben, empfehle ich Ihnen, dies so schnell wie möglich zu tun. Wie sieht Ihr Profil aus, wenn Sie die Caches mit schlechtem Speicherlayout verprügeln, ein Kern zu 100% festgelegt ist, wie viel relative Zeit für die Verarbeitung Ihres ECS im Vergleich zum Rest Ihrer Engine usw. aufgewendet wird?

Lesen Sie aus einer Entität und berechnen Sie etwas ... und behalten Sie die Ergebnisse bis später irgendwo in einem Zwischenspeicherbereich bei? Ich glaube nicht, dass Sie read + compute + store so trennen können, wie Sie denken, und erwarten, dass dieser Zwischenspeicher alles andere als reiner Overhead ist.

Da Sie eine kontinuierliche Verarbeitung durchführen, sollten Sie als Hauptregel einen Thread pro CPU-Kern verwenden. Ich denke, dass Sie dies auf der falschen Ebene betrachten , versuchen Sie, ganze Systeme und nicht einzelne Entitäten zu betrachten.

Erstellen Sie ein Abhängigkeitsdiagramm zwischen Ihren Systemen. Ein Baum der Systemanforderungen ergibt sich aus der Arbeit eines früheren Systems. Sobald Sie diesen Abhängigkeitsbaum haben, können Sie ganz einfach ganze Systeme voller Entitäten zur Verarbeitung in einem Thread senden .

Nehmen wir also an, Ihr Abhängigkeitsbaum besteht aus Brombeersträuchern und Bärenfallen, ein Designproblem, aber wir müssen mit dem arbeiten, was wir haben. Der beste Fall hierbei ist, dass innerhalb jedes Systems jede Entität nicht von einem anderen Ergebnis innerhalb dieses Systems abhängt. Hier können Sie die Verarbeitung einfach auf die Threads 0-99 und 100-199 in zwei Threads unterteilen, um ein Beispiel mit zwei Kernen und 200 Entitäten zu erhalten, die diesem System gehören.

In beiden Fällen müssen Sie in jeder Phase auf Ergebnisse warten, von denen die nächste Phase abhängt. Dies ist jedoch in Ordnung, da das Warten auf die Ergebnisse von zehn großen Datenblöcken, die in großen Mengen verarbeitet werden, der tausendfachen Synchronisierung für kleine Blöcke weit überlegen ist.

Die Idee hinter dem Erstellen eines Abhängigkeitsgraphen bestand darin, die scheinbar unmögliche Aufgabe des "Findens und Zusammenstellens anderer parallel laufender Systeme" durch Automatisierung zu trivialisieren. Wenn ein solches Diagramm Anzeichen einer Blockierung durch ständiges Warten auf vorherige Ergebnisse zeigt, verschiebt das Erstellen eines Lese- + Änderungs- und verzögerten Schreibvorgangs nur die Blockierung und entfernt nicht die serielle Natur der Verarbeitung.

Die serielle Verarbeitung kann nur zwischen den einzelnen Sequenzpunkten parallel geschaltet werden, nicht jedoch insgesamt. Aber Sie erkennen dies, weil es der Kern Ihres Problems ist. Selbst wenn Sie Lesevorgänge aus Daten zwischenspeichern, die noch nicht geschrieben wurden, müssen Sie noch auf diesen Cache warten, um verfügbar zu werden.

Wenn die Erstellung paralleler Architekturen mit solchen Einschränkungen einfach oder sogar möglich gewesen wäre, hätte die Informatik seit Bletchley Park nicht mit dem Problem zu kämpfen gehabt.

Die einzige wirkliche Lösung wäre, alle diese Abhängigkeiten zu minimieren , um die Sequenzpunkte so selten wie möglich zu machen. Dies kann das Unterteilen von Systemen in sequentielle Verarbeitungsschritte umfassen, bei denen es innerhalb jedes Subsystems trivial wird, parallel zu Threads zu arbeiten.

Das Beste, was ich für dieses Problem bekommen habe, und es ist wirklich nichts weiter als zu empfehlen, dass wenn Sie Ihren Kopf gegen eine Mauer schlagen, es weh tut, ihn in kleinere Ziegelwände zu brechen, damit Sie nur Ihre Schienbeine treffen.

Ich habe von einer interessanten Lösung für dieses Problem gehört: Die Idee ist, dass es 2 Kopien der Entitätsdaten geben würde (verschwenderisch, ich weiß). Eine Kopie wäre die gegenwärtige Kopie und die andere wäre die vergangene Kopie. Die vorliegende Kopie ist ausschließlich schreibgeschützt und die frühere Kopie ist ausschließlich schreibgeschützt. Ich gehe davon aus, dass Systeme nicht in dieselben Datenelemente schreiben möchten, aber wenn dies nicht der Fall ist, sollten sich diese Systeme im selben Thread befinden. Jeder Thread hätte Schreibzugriff auf die aktuellen Kopien sich gegenseitig ausschließender Abschnitte der Daten, und jeder Thread hat Lesezugriff auf alle früheren Kopien der Daten und kann somit die aktuellen Kopien unter Verwendung von Daten aus den früheren Kopien mit der Nummer 1 aktualisieren Verriegelung. Zwischen jedem Frame wird die aktuelle Kopie zur letzten Kopie, Sie möchten jedoch den Rollentausch übernehmen.

Diese Methode entfernt auch die Rennbedingungen, da alle Systeme mit einem veralteten Zustand arbeiten, der sich nicht ändert, bevor / nachdem das System ihn verarbeitet hat.

Ich kenne 3 Software-Designs, die die parallele Verarbeitung von Daten handhaben:

1. Daten nacheinander verarbeiten : Dies mag seltsam klingen, da wir die Daten mit mehreren Threads verarbeiten möchten. In den meisten Szenarien sind jedoch mehrere Threads erforderlich, damit die Arbeit abgeschlossen werden kann, während andere Threads warten oder lange laufende Vorgänge ausführen. Am häufigsten werden UI-Threads verwendet, die die Benutzeroberfläche in einem einzelnen Thread aktualisieren, während andere Threads möglicherweise im Hintergrund ausgeführt werden, jedoch nicht direkt auf die UI-Elemente zugreifen dürfen. Um Ergebnisse aus den Hintergrundthreads zu übergeben, werden Jobwarteschlangen verwendet, die von dem einzelnen Thread bei der nächsten angemessenen Gelegenheit verarbeitet werden.
2. Synchronisieren Sie den Datenzugriff: Dies ist die häufigste Methode, um mehrere Threads zu verarbeiten, die auf dieselben Daten zugreifen. Die meisten Programmiersprachen verfügen über integrierte Klassen und Tools, um Abschnitte zu sperren , in denen Daten von mehreren Threads gleichzeitig gelesen und / oder geschrieben werden. Es ist jedoch darauf zu achten, dass Vorgänge nicht blockiert werden. Andererseits kostet dieser Ansatz in Echtzeitanwendungen viel Aufwand.
3. Behandeln Sie gleichzeitige Änderungen nur dann, wenn sie auftreten: Dieser optimistische Ansatz kann durchgeführt werden, wenn Kollisionen selten auftreten. Die Daten werden gelesen und geändert, wenn überhaupt kein Mehrfachzugriff vorhanden war. Es gibt jedoch einen Mechanismus, der erkennt, wann die Daten gleichzeitig aktualisiert wurden. In diesem Fall wird die Einzelberechnung nur bis zum Erfolg erneut ausgeführt.

Hier einige Beispiele für jeden Ansatz, der in einem Entitätssystem verwendet werden kann:

1. Denken wir an a CollisionSystem, das liest Positionund RigidBodyKomponenten enthält und a aktualisieren sollte Velocity. Anstatt das Velocitydirekt zu manipulieren , stellt der CollisionSystemWille stattdessen ein CollisionEventin die Arbeitswarteschlange eines EventSystem. Dieses Ereignis wird dann nacheinander mit anderen Aktualisierungen des verarbeitet Velocity.
2. An EntitySystemdefiniert eine Reihe von Komponenten, die gelesen und geschrieben werden müssen. Für jeden Entitywird es eine aquire Lesesperre für jede Komponente , dass sie lesen möchte, und eine Schreibsperre für jede Komponente , dass sie aktualisieren möchte. Auf diese Weise kann jeder EntitySystemgleichzeitig Komponenten lesen, während Aktualisierungsvorgänge synchronisiert werden.
3. Am Beispiel von MovementSystemist die PositionKomponente unveränderlich und enthält eine Versionsnummer . Die MovementSystemsavely liest die Positionund VelocityKomponente und berechnet die neue Position, die Lese Inkrementieren Revisionsnummer und versucht , die Aktualisierung PositionKomponente. Im Falle einer gleichzeitigen Änderung gibt das Framework dies bei der Aktualisierung an und Entitywird wieder in die Liste der Entitäten aufgenommen, die von der aktualisiert werden müssen MovementSystem.

Abhängig von den Systemen, Entitäten und Aktualisierungsintervallen kann jeder Ansatz gut oder schlecht sein. Ein Entity-System-Framework kann es dem Benutzer ermöglichen, zwischen diesen Optionen zu wählen, um die Leistung zu optimieren.

Ich hoffe, ich konnte der Diskussion einige Ideen hinzufügen und bitte lassen Sie mich wissen, wenn es Neuigkeiten dazu gibt.