Эффективное разделение шагов чтения / вычисления / записи для одновременной обработки объектов в системах объектов / компонентов

Настроить

У меня есть объектно-компонентная архитектура, в которой сущности могут иметь набор атрибутов (которые являются чистыми данными без поведения), и существуют системы, которые выполняют логику сущностей, которая воздействует на эти данные. По сути, в некотором псевдокоде:

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

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

Система, которая просто движется по всем объектам с постоянной скоростью, может быть

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

По сути, я пытаюсь распараллелить update () максимально эффективно. Это можно сделать, запустив целые системы параллельно или предоставив каждому update () одной системы пару компонентов, чтобы разные потоки могли выполнять обновление одной и той же системы, но для другого подмножества объектов, зарегистрированных в этой системе.

проблема

В случае показанной MovementSystem распараллеливание тривиально. Поскольку объекты не зависят друг от друга и не изменяют общие данные, мы можем просто переместить все объекты параллельно.

Однако эти системы иногда требуют, чтобы объекты взаимодействовали (считывали / записывали данные из / в) друг с другом, иногда в одной и той же системе, но часто между различными системами, которые зависят друг от друга.

Например, в физической системе иногда сущности могут взаимодействовать друг с другом. Два объекта сталкиваются, их положения, скорости и другие атрибуты считываются из них, обновляются, а затем обновленные атрибуты записываются обратно в оба объекта.

И прежде чем система рендеринга в движке сможет начать рендеринг сущностей, она должна подождать, пока другие системы завершат выполнение, чтобы убедиться, что все соответствующие атрибуты являются такими, какими они должны быть.

Если мы попытаемся слепо распараллелить это, это приведет к классическим гоночным условиям, когда разные системы могут одновременно считывать и изменять данные.

В идеале, должно существовать решение, при котором все системы могут считывать данные из любых сущностей, которые они хотят, не беспокоясь о том, что другие системы изменяют эти же данные одновременно, и не заботясь о том, чтобы программист заботился о правильном порядке выполнения и распараллеливания эти системы вручную (что иногда даже невозможно).

В базовой реализации этого можно достичь, просто поместив все данные для чтения и записи в критические секции (защищая их мьютексами). Но это вызывает большие накладные расходы времени выполнения и, вероятно, не подходит для приложений, чувствительных к производительности.

Решение?

На мой взгляд, возможным решением будет система, в которой чтение / обновление и запись данных разделены, так что на одном дорогостоящем этапе системы только читают данные и вычисляют то, что им нужно для вычисления, каким-то образом кэшируют результаты, а затем записывают все измененные данные возвращаются к целевым объектам в отдельном проходе записи. Все системы будут работать с данными в том состоянии, в котором они находились в начале кадра, а затем до конца кадра, когда все системы завершат обновление, происходит сериализованный этап записи, когда результаты кэширования получаются из всех разных системы повторяются и записываются обратно в целевые объекты.

Это основано на (возможно, неправильной?) Идее, что выигрыш в простом распараллеливании может быть достаточно большим, чтобы превзойти стоимость (как с точки зрения производительности во время выполнения, так и накладных расходов кода) кэширования результатов и прохода записи.

Вопрос

Как такая система может быть реализована для достижения оптимальной производительности? Каковы детали реализации такой системы и каковы предпосылки для системы Entity-Component, которая хочет использовать это решение?

----- (на основании пересмотренного вопроса)

Первый момент: поскольку вы не упомянули, что профилировали среду выполнения сборки релиза и обнаружили конкретную потребность, я предлагаю вам сделать это как можно скорее. Как выглядит ваш профиль, вы крошите кеши с плохой разметкой памяти, одно ядро ​​привязано к 100%, сколько относительного времени уходит на обработку вашего ECS по сравнению с остальной частью вашего движка и т. Д ...

Чтение из сущности и вычисление чего-либо ... и удержание результатов где-то в промежуточной области хранения до позже? Я не думаю, что вы можете разделить чтение + вычисление + хранилище так, как вы думаете, и ожидаете, что это промежуточное хранилище будет чем-то иным, кроме накладных расходов.

Кроме того, поскольку вы выполняете непрерывную обработку, основное правило, которому вы хотите следовать, - это иметь один поток на ядро ​​ЦП. Я думаю, что вы смотрите на это не с того уровня , попробуйте взглянуть на целые системы, а не на отдельные объекты.

Создайте граф зависимостей между вашими системами, дерево того, что нужно системе, является результатом более ранней работы системы. Получив это дерево зависимостей, вы можете легко отправить целые системы, полные сущностей, для обработки в потоке.

Итак, допустим, что ваше дерево зависимостей - это болото ежевики и медвежьих ловушек, проблема дизайна, но мы должны работать с тем, что имеем. Наилучшим случаем здесь является то, что внутри каждой системы каждый объект не зависит от какого-либо другого результата в этой системе. Здесь вы легко поделите обработку между потоками, 0-99 и 100-199 на два потока, например, с двумя ядрами и 200 объектами, которыми владеет эта система.

В любом случае на каждом этапе вам придется ждать результатов, от которых зависит следующий этап. Но это нормально, потому что ожидание результатов обработки десяти больших блоков данных намного лучше, чем тысяча раз синхронизироваться для небольших блоков.

Идея построения графа зависимостей состояла в том, чтобы упростить, казалось бы, невозможную задачу «Поиск и сборка других систем для параллельного запуска», автоматизировав его. Если такой график показывает признаки блокирования из-за постоянного ожидания предыдущих результатов, то создание операций чтения + изменения и отложенной записи только перемещает блокировку и не устраняет последовательный характер обработки.

И последовательная обработка может быть превращена только параллельно между каждой точкой последовательности, но не в целом. Но вы понимаете это, потому что это является ядром вашей проблемы. Даже если вы кешируете чтение из данных, которые еще не были записаны, вам все равно нужно подождать, пока этот кеш станет доступным.

Если бы создание параллельных архитектур было бы легким или даже возможным с такими ограничениями, компьютерная наука не боролась бы с этой проблемой со времен Блетчли Парк.

Единственным реальным решением было бы свести к минимуму все эти зависимости, чтобы сделать точки последовательности как можно реже необходимыми. Это может включать в себя подразделение систем на последовательные этапы обработки, где внутри каждой подсистемы параллельная с потоками становится тривиальной.

Лучшее, что я получил за эту проблему, и это действительно не что иное, как рекомендация, что если ударить головой о кирпичную стену больно, то разбить ее на кирпичные стены меньшего размера, чтобы вы только били себя по голеням.

Я слышал об интересном решении этой проблемы: идея состоит в том, что будет 2 копии данных сущности (я знаю, что это расточительно). Одна копия будет настоящей копией, а другая - прошлой. Настоящая копия предназначена только для записи, а последняя - только для чтения. Я предполагаю, что системы не хотят записывать в одни и те же элементы данных, но если это не так, эти системы должны быть в одном потоке. Каждый поток будет иметь доступ на запись к текущим копиям взаимоисключающих разделов данных, а каждый поток имеет доступ на чтение ко всем прошлым копиям данных и, таким образом, может обновлять существующие копии, используя данные из прошлых копий без замок. Между каждым кадром текущая копия становится прошлой, однако вы хотите справиться с обменом ролями.

Этот метод также удаляет условия гонки, потому что все системы будут работать с устаревшим состоянием, которое не изменится до / после того, как система его обработала.

Я знаю 3 проекта программного обеспечения, обрабатывающих параллельную обработку данных:

1. Последовательная обработка данных : это может показаться странным, поскольку мы хотим обрабатывать данные, используя несколько потоков. Однако в большинстве сценариев требуется несколько потоков только для того, чтобы работа была завершена, в то время как другие потоки ожидают или выполняют длительные операции. Чаще всего используются потоки пользовательского интерфейса, которые обновляют пользовательский интерфейс в одном потоке, в то время как другие потоки могут работать в фоновом режиме, но не имеют прямого доступа к элементам пользовательского интерфейса. Для передачи результатов из фоновых потоков используются очереди заданий , которые будут обрабатываться одним потоком при следующей разумной возможности.
2. Синхронизировать доступ к данным: это наиболее распространенный способ обработки нескольких потоков, обращающихся к одним и тем же данным. Большинство языков программирования имеют встроенные классы и инструменты для блокировки секций, в которых данные считываются и / или записываются несколькими потоками одновременно. Однако следует соблюдать осторожность, чтобы не блокировать операции. С другой стороны, такой подход стоит очень дорого в приложениях реального времени.
3. Обрабатывайте одновременные изменения только тогда, когда они происходят: этот оптимистический подход может быть применен, если столкновения происходят редко. Данные будут считываться и изменяться, если вообще не было множественного доступа, но есть механизм, который определяет, когда данные обновлялись одновременно. Если это произойдет, одиночное вычисление будет просто выполнено снова до успеха.

Вот несколько примеров для каждого подхода, который может использоваться в системе сущностей:

1. Давайте думать о CollisionSystemтом, что читает Positionи RigidBodyкомпоненты и должны обновить Velocity. Вместо того, чтобы манипулировать Velocityнепосредственно, CollisionSystemзавещание вместо этого помещает CollisionEventв рабочую очередь объекта EventSystem. Это событие будет затем обрабатываться последовательно с другими обновлениями Velocity.
2. An EntitySystemопределяет набор компонентов, которые он должен прочитать и записать. Для каждого Entityон получит блокировку чтения для каждого компонента, который он хочет прочитать, и блокировку записи для каждого компонента, который он хочет обновить. Таким образом, каждый EntitySystemсможет одновременно считывать компоненты во время синхронизации операций обновления.
3. Взяв пример MovementSystem, Positionкомпонент является неизменным и содержит номер редакции . MovementSystemСавелий читает Positionи Velocityкомпонент и вычисляет новый Position, увеличивающееся считанные ревизии номера и пытаются обновляемым в Positionкомпонент. В случае одновременного изменения инфраструктура указывает это при обновлении, и оно Entityбудет возвращено в список объектов, которые должны быть обновлены MovementSystem.

В зависимости от систем, объектов и интервалов обновления каждый подход может быть хорошим или плохим. Инфраструктура системы сущностей может позволить пользователю выбирать между этими опциями для настройки производительности.

Я надеюсь, что смогу добавить некоторые идеи к обсуждению и, пожалуйста, дайте мне знать, если есть какие-то новости об этом.