Separando com eficiência etapas de leitura / computação / gravação para processamento simultâneo de entidades em sistemas de entidade / componente

Configuração

Eu tenho uma arquitetura de componente de entidade em que as entidades podem ter um conjunto de atributos (que são dados puros sem comportamento) e existem sistemas que executam a lógica da entidade que atua sobre esses dados. Essencialmente, em algum pseudocódigo:

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

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

Um sistema que apenas se move ao longo de todas as entidades a uma taxa constante pode ser

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

Essencialmente, estou tentando paralelizar update () da maneira mais eficiente possível. Isso pode ser feito executando sistemas inteiros em paralelo ou fornecendo a cada atualização () de um sistema alguns componentes para que threads diferentes possam executar a atualização do mesmo sistema, mas para um subconjunto diferente de entidades registradas nesse sistema.

Problema

No caso do MovementSystem mostrado, a paralelização é trivial. Como as entidades não dependem umas das outras e não modificam os dados compartilhados, poderíamos simplesmente mover todas as entidades em paralelo.

No entanto, esses sistemas às vezes exigem que as entidades interajam (leiam / gravem dados de / para) umas às outras, às vezes dentro do mesmo sistema, mas geralmente entre sistemas diferentes que dependem uns dos outros.

Por exemplo, em um sistema de física, algumas vezes as entidades podem interagir umas com as outras. Dois objetos colidem, suas posições, velocidades e outros atributos são lidos a partir deles, são atualizados e, em seguida, os atributos atualizados são gravados novamente nas duas entidades.

E antes que o sistema de renderização no mecanismo possa iniciar a renderização de entidades, é necessário aguardar que outros sistemas concluam a execução para garantir que todos os atributos relevantes sejam o que precisam ser.

Se tentarmos paralelizar cegamente isso, isso levará a condições clássicas de corrida, nas quais diferentes sistemas podem ler e modificar dados ao mesmo tempo.

Idealmente, existiria uma solução em que todos os sistemas possam ler dados de qualquer entidade que desejarem, sem ter que se preocupar com outros sistemas modificando esses mesmos dados ao mesmo tempo e sem que o programador se preocupe em ordenar adequadamente a execução e paralelização de esses sistemas manualmente (o que às vezes nem é possível).

Em uma implementação básica, isso pode ser conseguido colocando todas as leituras e gravações de dados em seções críticas (protegendo-as com mutexes). Mas isso induz uma grande quantidade de sobrecarga de tempo de execução e provavelmente não é adequado para aplicativos sensíveis ao desempenho.

Solução?

Em minha opinião, uma solução possível seria um sistema onde a leitura / atualização e gravação de dados são separadas, de modo que, em uma fase cara, os sistemas apenas leiam dados e calculem o que precisam calcular, de alguma forma, armazenem em cache os resultados e depois escrevam todos os dados alterados de volta para as entidades de destino em um passe de gravação separado. Todos os sistemas atuariam com os dados no estado em que estavam no início do quadro e, em seguida, antes do final do quadro, quando todos os sistemas terminassem de atualizar, uma passagem de gravação serializada acontecerá onde o cache resulta de todos os diferentes os sistemas são iterados e gravados de volta para as entidades de destino.

Isso se baseia na (talvez errada?) Idéia de que a vitória fácil da paralelização poderia ser grande o suficiente para superar o custo (tanto em termos de desempenho de tempo de execução quanto de sobrecarga de código) do cache de resultados e da passagem de gravação.

A questão

Como esse sistema pode ser implementado para alcançar o desempenho ideal? Quais são os detalhes de implementação desse sistema e quais são os pré-requisitos para um sistema Entity-Component que deseja usar esta solução?

----- (com base na pergunta revisada)

Primeiro ponto: como você não menciona ter criado um perfil para o seu release, compilou o tempo de execução e encontrou uma necessidade específica, sugiro que você faça isso o mais rápido possível. Como é o seu perfil, você está debulhando os caches com um layout de memória ruim, é um núcleo atrelado a 100%, quanto tempo relativo é gasto no processamento do seu ECS versus o resto do seu mecanismo, etc.

Leia de uma entidade e calcule algo ... e mantenha os resultados em algum lugar de uma área de armazenamento intermediária até mais tarde? Não acho que você possa separar a leitura, a computação e a loja da maneira que pensa e espera que essa loja intermediária seja tudo menos pura sobrecarga.

Além disso, como você está processando continuamente, a regra principal que você deseja seguir é ter um thread por núcleo de CPU. Eu acho que você está olhando isso na camada errada , tente olhar sistemas inteiros e não entidades individuais.

Crie um gráfico de dependência entre seus sistemas, uma árvore do que o sistema precisa resulta do trabalho de um sistema anterior. Depois de ter essa árvore de dependência, você pode facilmente enviar sistemas inteiros cheios de entidades para processar em um encadeamento.

Então, digamos que sua árvore de dependência seja um monte de espinhos e armadilhas, um problema de design, mas temos que trabalhar com o que temos. O melhor caso aqui é que, dentro de cada sistema, cada entidade não depende de nenhum outro resultado dentro desse sistema. Aqui você subdivide facilmente o processamento entre threads, 0-99 e 100-199 em dois threads, por exemplo, com dois núcleos e 200 entidades pertencentes a este sistema.

Em qualquer um dos casos, em cada estágio, é necessário aguardar resultados dos quais o próximo estágio depende. Mas tudo bem, pois aguardar os resultados de dez grandes blocos de dados sendo processados ​​em massa é muito superior à sincronização mil vezes para pequenos blocos.

A idéia por trás da construção de um gráfico de dependência era banalizar a tarefa aparentemente impossível de "Encontrar e montar outros sistemas para executar em paralelo", automatizando-o. Se esse gráfico mostrar sinais de que está sendo bloqueado pela constante espera por resultados anteriores, a criação de uma leitura + modificação e gravação atrasada move apenas o bloqueio e não remove a natureza serial do processamento.

E o processamento serial só pode ser paralelo entre cada ponto de sequência, mas não no geral. Mas você percebe isso porque é o cerne do seu problema. Mesmo que você armazene em cache as leituras de dados que ainda não foram gravados, ainda precisará aguardar que o cache fique disponível.

Se a criação de arquiteturas paralelas fosse fácil ou até possível com esses tipos de restrições, a ciência da computação não estaria lutando com o problema desde Bletchley Park.

A única solução real seria minimizar todas essas dependências para tornar os pontos de sequência tão raramente necessários quanto possível. Isso pode envolver a subdivisão de sistemas em etapas de processamento seqüencial , onde, dentro de cada subsistema, ficar paralelo aos encadeamentos se torna trivial.

O melhor que consegui para esse problema e nada mais é do que recomendar que, se bater com a cabeça em uma parede de tijolos doer, quebre-o em paredes de tijolos menores, para que você só bata nas canelas.

Ouvi falar de uma solução interessante para esse problema: a idéia é que haveria 2 cópias dos dados da entidade (desperdício, eu sei). Uma cópia seria a cópia atual e a outra seria a cópia anterior. A cópia atual é estritamente somente para gravação e a cópia anterior é estritamente somente para leitura. Estou assumindo que os sistemas não desejam gravar nos mesmos elementos de dados, mas se esse não for o caso, esses sistemas deverão estar no mesmo encadeamento. Cada encadeamento teria acesso de gravação às cópias presentes de seções mutuamente exclusivas dos dados, e cada encadeamento terá acesso de leitura a todas as cópias passadas dos dados e, portanto, poderá atualizar as cópias presentes usando os dados das cópias anteriores sem bloqueio. Entre cada quadro, a cópia atual se torna a cópia anterior, no entanto, você deseja lidar com a troca de funções.

Esse método também remove as condições de corrida porque todos os sistemas estarão trabalhando com um estado obsoleto que não será alterado antes / depois que o sistema o processar.

Conheço três projetos de software que lidam com processamento paralelo de dados:

1. Processar os dados sequencialmente : Isso pode parecer estranho, pois queremos processar os dados usando vários threads. No entanto, a maioria dos cenários exige vários encadeamentos apenas para que o trabalho seja concluído enquanto outros encadeamentos aguardam ou executam operações demoradas. O uso mais comum são os threads da UI que atualizam a interface do usuário em um único thread, enquanto outros threads podem ser executados em segundo plano, mas não têm permissão para acessar diretamente os elementos da UI. Para transmitir resultados dos encadeamentos em segundo plano, são utilizadas filas de tarefas que serão processadas pelo encadeamento único na próxima oportunidade razoável.
2. Sincronize o acesso aos dados: esta é a maneira mais comum de lidar com vários threads acessando os mesmos dados. A maioria das linguagens de programação possui classes e ferramentas para bloquear seções nas quais os dados são lidos e / ou gravados por vários threads simultaneamente. No entanto, deve-se ter cuidado para não bloquear operações. Por outro lado, essa abordagem custa muito mais em aplicativos em tempo real.
3. Manipule modificações simultâneas apenas quando elas ocorrerem: essa abordagem otimista pode ser feita se colisões ocorrerem raramente. Os dados serão lidos e modificados se não houver acesso múltiplo, mas existe um mecanismo que detecta quando os dados foram atualizados simultaneamente. Se isso acontecer, o cálculo único será executado novamente até o sucesso.

Aqui estão alguns exemplos para cada abordagem que pode ser usada em um sistema de entidades:

1. Vamos pensar em um CollisionSystemque lê Positione RigidBodycomponentes e deve atualizar a Velocity. Em vez de manipular Velocitydiretamente, o CollisionSystemwill colocará um CollisionEventna fila de trabalho de um EventSystem. Esse evento será processado sequencialmente com outras atualizações no Velocity.
2. Um EntitySystemdefine um conjunto de componentes que ele precisa ler e gravar. Para cada Entityum deles , será gerado um bloqueio de leitura para cada componente que deseja ler e um bloqueio de gravação para cada componente que deseja atualizar. Assim, todos EntitySystempoderão ler componentes simultaneamente enquanto as operações de atualização são sincronizadas.
3. Tomando o exemplo de MovementSystem, o Positioncomponente é imutável e contém um número de revisão . A MovementSystemlê savely o Positione Velocitycomponentes e calcula o novo Position, incrementando a leitura revisão número e tenta atualizar o Positioncomponente. No caso de uma modificação simultânea, a estrutura indica isso na atualização e Entityserá recolocada na lista de entidades que precisam ser atualizadas pelo MovementSystem.

Dependendo dos sistemas, entidades e intervalos de atualização, cada abordagem pode ser boa ou ruim. Uma estrutura de sistema de entidades pode permitir que o usuário escolha entre essas opções para ajustar o desempenho.

Espero poder adicionar algumas idéias à discussão e por favor me avise se houver alguma notícia sobre isso.