Séparation efficace des étapes de lecture / calcul / écriture pour le traitement simultané des entités dans les systèmes Entité / Composant

Installer

J'ai une architecture de composant d'entité où les entités peuvent avoir un ensemble d'attributs (qui sont des données pures sans comportement) et il existe des systèmes qui exécutent la logique d'entité qui agissent sur ces données. Essentiellement, dans un peu de pseudo-code:

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

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

Un système qui se déplace le long de toutes les entités à un rythme constant pourrait être

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

Essentiellement, j'essaie de paralléliser update () aussi efficacement que possible. Cela peut être fait en exécutant des systèmes entiers en parallèle ou en donnant à chaque mise à jour () d'un système deux composants afin que différents threads puissent exécuter la mise à jour du même système, mais pour un sous-ensemble différent d'entités enregistrées avec ce système.

Problème

Dans le cas du MovementSystem montré, la parallélisation est triviale. Étant donné que les entités ne dépendent pas les unes des autres et ne modifient pas les données partagées, nous pourrions simplement déplacer toutes les entités en parallèle.

Cependant, ces systèmes nécessitent parfois que les entités interagissent les unes avec les autres (lecture / écriture de données de / vers), parfois au sein du même système, mais souvent entre différents systèmes qui dépendent les uns des autres.

Par exemple, dans un système de physique, les entités peuvent parfois interagir les unes avec les autres. Deux objets entrent en collision, leurs positions, vitesses et autres attributs sont lus à partir d'eux, sont mis à jour, puis les attributs mis à jour sont réécrits dans les deux entités.

Et avant que le système de rendu dans le moteur puisse commencer à rendre des entités, il doit attendre que les autres systèmes terminent l'exécution pour s'assurer que tous les attributs pertinents sont ce dont ils ont besoin.

Si nous essayons de paralléliser aveuglément cela, cela conduira à des conditions de course classiques où différents systèmes peuvent lire et modifier des données en même temps.

Idéalement, il existerait une solution où tous les systèmes pourraient lire les données de toutes les entités qu'ils souhaitent, sans avoir à se soucier que d'autres systèmes modifient ces mêmes données en même temps, et sans que le programmeur se soucie de l'ordre correct de l'exécution et de la parallélisation de ces systèmes manuellement (ce qui n'est parfois même pas possible).

Dans une implémentation de base, cela pourrait être réalisé en plaçant simplement toutes les lectures et écritures de données dans des sections critiques (en les gardant avec des mutex). Mais cela induit une grande quantité de temps d'exécution et n'est probablement pas adapté aux applications sensibles aux performances.

Solution?

À mon avis, une solution possible serait un système où la lecture / la mise à jour et l'écriture des données sont séparées, de sorte que dans une phase coûteuse, les systèmes ne lisent que les données et calculent ce dont ils ont besoin pour calculer, mettent en cache les résultats, puis écrivent tous les données modifiées reviennent aux entités cibles dans une passe d'écriture distincte. Tous les systèmes agiraient sur les données dans l'état où elles se trouvaient au début de la trame, puis avant la fin de la trame, lorsque tous les systèmes ont terminé la mise à jour, une passe d'écriture sérialisée se produit où la mise en cache résulte de tous les différents les systèmes sont itérés et réécrits aux entités cibles.

Ceci est basé sur l'idée (peut-être fausse?) Que la victoire de la parallélisation facile pourrait être suffisamment importante pour surpasser le coût (à la fois en termes de performances d'exécution et de surcharge de code) de la mise en cache des résultats et de la passe d'écriture.

La question

Comment un tel système pourrait-il être mis en œuvre pour obtenir des performances optimales? Quels sont les détails d'implémentation d'un tel système et quelles sont les conditions préalables pour un système Entity-Component qui souhaite utiliser cette solution?

----- (basé sur la question révisée)

Premier point: puisque vous ne mentionnez pas avoir profilé le runtime de votre version et trouvé un besoin spécifique, je vous suggère de le faire dès que possible. À quoi ressemble votre profil, est-ce que vous détruisez les caches avec une mauvaise disposition de la mémoire, est un noyau indexé à 100%, combien de temps relatif est consacré au traitement de votre ECS par rapport au reste de votre moteur, etc.

Lire à partir d'une entité et calculer quelque chose ... et conserver les résultats quelque part dans une zone de stockage intermédiaire jusqu'à plus tard? Je ne pense pas que vous puissiez séparer read + compute + store de la façon dont vous pensez et vous attendre à ce que ce magasin intermédiaire soit tout sauf de la surcharge.

De plus, comme vous effectuez un traitement continu, la règle principale que vous souhaitez suivre est d'avoir un thread par cœur de processeur. Je pense que vous regardez cela dans la mauvaise couche , essayez de regarder des systèmes entiers et non des entités individuelles.

Créez un graphique de dépendance entre vos systèmes, une arborescence des besoins du système résultant du travail d'un système antérieur. Une fois que vous avez cet arbre de dépendance, vous pouvez facilement envoyer des systèmes entiers remplis d'entités à traiter sur un thread.

Supposons donc que votre arbre de dépendance soit bourbier de ronces et de pièges à ours, un problème de conception, mais nous devons travailler avec ce que nous avons. Le meilleur cas ici est qu'à l'intérieur de chaque système, chaque entité ne dépend d'aucun autre résultat à l'intérieur de ce système. Ici, vous subdivisez facilement le traitement entre les threads, 0-99 et 100-199 sur deux threads pour un exemple avec deux cœurs et 200 entités que ce système possède.

Dans les deux cas, à chaque étape, vous devez attendre les résultats dont dépend l'étape suivante. Mais c'est OK car attendre les résultats de dix gros blocs de données en cours de traitement est bien supérieur à la synchronisation mille fois pour les petits blocs.

L'idée derrière la construction d'un graphe de dépendances était de banaliser la tâche apparemment impossible de "Trouver et assembler d'autres systèmes à exécuter en parallèle" en l'automatisant. Si un tel graphique montre des signes d'être bloqué par une attente constante des résultats précédents, la création d'une lecture + modification et d'une écriture différée ne fait que déplacer le blocage et ne supprime pas la nature sérielle du traitement.

Et le traitement en série ne peut être tourné qu'en parallèle entre chaque point de séquence, mais pas globalement. Mais vous vous en rendez compte parce que c'est le cœur de votre problème. Même si vous mettez en cache des lectures à partir de données qui n'ont pas encore été écrites, vous devez toujours attendre ce cache pour devenir disponible.

Si la création d'architectures parallèles était facile ou même possible avec ce genre de contraintes, alors l'informatique n'aurait pas eu de problème avec Bletchley Park.

La seule vraie solution serait de minimiser toutes ces dépendances pour rendre les points de séquence aussi rarement nécessaires que possible. Cela peut impliquer la subdivision des systèmes en étapes de traitement séquentielles où, à l'intérieur de chaque sous-système, aller en parallèle avec les threads devient trivial.

Le mieux que j'ai eu pour ce problème et ce n'est vraiment rien de plus que de recommander que si vous vous frappez la tête sur un mur de briques fait mal, puis le briser en petits murs de briques afin que vous ne frappiez que vos tibias.

J'ai entendu parler d'une solution intéressante à ce problème: L'idée est qu'il y aurait 2 copies des données d'entité (gaspillage, je sais). Une copie serait la copie actuelle et l'autre serait la copie précédente. La copie actuelle est strictement écrite et la copie précédente est strictement en lecture seule. Je suppose que les systèmes ne veulent pas écrire dans les mêmes éléments de données, mais si ce n'est pas le cas, ces systèmes devraient être sur le même thread. Chaque thread aurait un accès en écriture aux copies actuelles des sections mutuellement exclusives des données, et chaque thread a un accès en lecture à toutes les copies précédentes des données, et peut donc mettre à jour les copies actuelles en utilisant les données des copies précédentes sans aucune verrouillage. Entre chaque image, la copie actuelle devient la copie précédente, mais vous souhaitez gérer l'échange de rôles.

Cette méthode supprime également les conditions de concurrence, car tous les systèmes fonctionneront avec un état périmé qui ne changera pas avant / après que le système l'ait traité.

Je connais 3 conceptions logicielles gérant le traitement parallèle des données:

1. Traitez les données séquentiellement : cela peut sembler étrange car nous voulons traiter les données à l'aide de plusieurs threads. Cependant, la plupart des scénarios nécessitent plusieurs threads juste pour que le travail soit terminé pendant que d'autres threads attendent ou effectuent de longues opérations. L'utilisation la plus courante est les threads d'interface utilisateur qui mettent à jour l'interface utilisateur dans un seul thread, tandis que d'autres threads peuvent s'exécuter en arrière-plan, mais ne sont pas autorisés à accéder directement aux éléments d'interface utilisateur. Afin de transmettre les résultats des threads d'arrière-plan, des files d'attente de travaux sont utilisées qui seront traitées par le thread unique à la prochaine opportunité raisonnable.
2. Synchroniser l'accès aux données: c'est la façon la plus courante de gérer plusieurs threads accédant aux mêmes données. La plupart des langages de programmation ont intégré des classes et des outils afin de verrouiller les sections où les données sont lues et / ou écrites simultanément par plusieurs threads. Cependant, il faut faire attention de ne pas bloquer les opérations. D'un autre côté, cette approche coûte beaucoup plus cher dans les applications en temps réel.
3. Ne manipulez les modifications simultanées que lorsqu'elles se produisent: cette approche optimiste peut être mise en œuvre si les collisions se produisent rarement. Les données seront lues et modifiées s'il n'y a pas eu d'accès multiple, mais il existe un mécanisme qui détecte quand les données ont été mises à jour simultanément. Si cela se produit, le calcul unique sera simplement exécuté à nouveau jusqu'au succès.

Voici quelques exemples pour chaque approche pouvant être utilisée dans un système d'entités:

1. Imaginons un CollisionSystemqui lit Positionet RigidBodycomposants et devrait mettre à jour un Velocity. Au lieu de manipuler le Velocitydirectement, le CollisionSystemtestament place plutôt un CollisionEventdans la file d'attente de travail d'un EventSystem. Cet événement sera ensuite traité séquentiellement avec d'autres mises à jour du Velocity.
2. Un EntitySystemdéfinit un ensemble de composants dont il a besoin pour lire et écrire. Pour chacun, Entityil acquiert un verrou de lecture pour chaque composant qu'il souhaite lire, et un verrou d'écriture pour chaque composant qu'il souhaite mettre à jour. Comme cela, tout EntitySystemle monde pourra lire simultanément les composants pendant que les opérations de mise à jour sont synchronisées.
3. En prenant l'exemple de la MovementSystem, le Positioncomposant est immuable et contient un numéro de révision . Le MovementSystemlit savely le Positionet Velocitycomposants et calcule la nouvelle Position, incrémenter la lecture révision numéro et tente mise à jour du Positioncomposant. En cas de modification simultanée, le framework l'indique sur la mise à jour et Entitysera remis dans la liste des entités qui doivent être mises à jour par le MovementSystem.

Selon les systèmes, les entités et les intervalles de mise à jour, chaque approche peut être bonne ou mauvaise. Une structure de système d'entité peut permettre à l'utilisateur de choisir entre ces options pour modifier les performances.

J'espère que je pourrais ajouter quelques idées à la discussion et s'il vous plaît faites le moi savoir s'il y a des nouvelles à ce sujet.