D-MASON: масштабируемая распределенная среда построения агент-ориентированных моделей

В статье исследователей из университета Салерно (Италия) рассматривается распределенная версия пакета MASON, разработанная в университете Джорджа Мейсона (США) для реализации программного кода агент-ориентированных моделей в распределенной среде – D-MASON. Большинство разработчиков агентных моделей в первую очередь являются специалистами в определенных предметных областях, а их программистские навыки зачастую ограничиваются знаниями специализированных высокоуровневых пакетов, и в этой связи постоянно растет запрос на системы автоматического распараллеливания программного кода без его переработки, сильно упрощающие построение высокопроизводительных приложений. Ранее мы уже описывали подобного рода фреймворки – RepastHPC, Pandora, Polaris и др., а здесь рассмотрим особенности пакета D-MASON, среди которых – эффективное разделение моделируемого пространства (двух и трехмерного), новый механизм согласованности памяти, интеграция с облачными сервисами. Дистрибутив, подробная документация, учебные пособия и прочие материалы можно скачать здесь.

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

Работа D-MASON основана на парадигме master/slave (ведущий-ведомый), при использовании которой главное приложение разделяет моделируемое пространство на части и распределяет рабочую нагрузку по ведомым процессам, каждый из которых задействует один или несколько логических процессоров (Logical Processors, LP) в соответствии с их вычислительными возможностями (рис. 1). Ведущий процесс устанавливает однозначную связь между LP и обслуживаемыми ячейками, при которой каждый LP отвечает за:

• симуляцию агентов, относящихся к соответствующей ячейке;
• обработку события, связанного с миграцией агентов в другие ячейки;
• связь и синхронизацию между соседними ячейками.

Рис. 1. Архитектура пакета D-MASON

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

Распределение работы

Сложной и неоднозначной проблемой при распараллеливании программного кода является декомпозиция общей задачи на отдельные подзадачи и распределение их по всем LP. В случае реализации агент-ориентированной модели, самым простым способом ее решения является равномерное деление агентов по свободным LP. Такой подход, называемый разработчиками как «разделение агентов» (agents partitioning), хотя и обеспечивает сбалансированную нагрузку на процессоры, но создает проблемы при синхронизации в случае высокой степени связности между агентами и необходимости обмена большим количеством сообщений.

Для решения обозначенной проблемы, при разбиении всей совокупности агентов разработчики группируют их в зависимости от набора связей в рамках определенной фиксированной окрестности, называемой «область интересов» (Area of Interest (AOI)) с последующим распределением по LP. Поскольку наиболее интенсивное взаимодействие между агентами происходит в пределах AOI, потери в производительности при синхронизации также снижаются.

Балансировки нагрузки

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

Связь

В D-MASON связь между LP основана на поведенческом шаблоне проектирования передачи сообщений «Издатель/Подписчик» (Publish/Subscribe (P/S)), в котором отправители сообщений напрямую не связаны с подписчиками, равно как и последние c отправителями. В свою очередь сообщения делятся на классы, которые не содержат сведения о подписчиках и издателях.

Первая версия D-MASON была реализована с использованием стандарта Java Message Service (JMS) и сервера Apache ActiveMQ в качестве провайдера JMS. Ниже будет рассмотрено реализованное разработчиками улучшение шаблона с использованием децентрализованной стратегии на базе интерфейса MPI.

Синхронизация

Для корректного выполнения параллельной версии программы по сравнению с ее последовательным аналогом, каждый LP должен непрерывно собирать информацию обо всех связанных с ним ячейках. В D-MASON выполнение программы осуществляется в виде отдельных шагов, каждый из которых состоит из трех этапов: (1) симуляция, (2) связь и (3) синхронизация (рис. 2). В процессе связи LP отправляет своим соседям информацию об агентах, которые мигрируют к ним, а также об агентах, которые могут попасть в AOI соседней ячейки. D-MASON использует механизм консервативной синхронизации для последовательной интеграции распределенных симуляций: сначала локально синхронизируется информация, полученная LP с соседних ячеек на шаге t – 1, а затем наступает следующий шаг симуляции t.

Рис. 2. Синхронизация процессоров LP в пакете D-MASON: два прямоугольника представляют две соседние ячейки, обслуживаемые разными LP; черные точки – агенты модели. После инициализации, каждый шаг модельного времени состоит из трех этапов: (1) симуляция, когда каждый LP работает самостоятельно, (2) связь и (3) синхронизация (обмен сообщениями между LP)

Процесс локальной синхронизации в виде последовательной диаграммы отображен на рис. 3, где две соседние ячейки ([0-0] и [0-1]) непрерывно обмениваются сообщениями о мигрирующих агентах и агентах, находящихся вблизи границы.

Рис. 3. Диаграмма локальной синхронизации в пакете D-MASON

Воспроизводимость

Разработчики D-MASON акцентируют особое внимание на то, что порядок, согласно которому вычисляется код агентов, не влияет на результаты симуляций. Таким образом, если реализуемая имитационная модель является полностью детерминированной, то результаты распределенных симуляций с использованием D-MASON идентичны результатам последовательной версии пакета MASON.

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

Архитектура пакета D-MASON

При разработке архитектуры были установлены следующие требования к пакету D-MASON: (1) эффективность использования аппаратной платформы, (2) возможность разработки с использованием различных парадигм моделирования, (3) удобный для пользователя интерфейс, (4) корректность расчетов. Для удовлетворения этим требованиям, D-MASON включает в себя четыре функциональных блока (уровня), отображенных на рис. 4:

1. Блок управления системой (System Management), предоставляющий удобные средства для регулирования работы симуляций в распределенной системе.
2. Блок визуализации (Visualization), позволяющий разработчикам создавать продвинутые средства отображения результатов работы агентных моделей.
3. Блок, обеспечивающий связь (Communication) с другими блоками (уровнями).
4. Блок распределенного моделирования (Distributed Simulation (DS)), обеспечивающий работу системы на множестве вычислительных узлов.

Рис. 4. Архитектура пакета D-MASON

Блок DS является ядром D-MASON и включает в себя два основных пакета: Engine и Field, первый из которых состоит из трех объектов:

• DistributedState: обеспечивает идентификацию ячеек и миграцию агентов между ними.
• DistributedMultiSchedule: отслеживает время симуляции и процесс синхронизации между этапами симуляции.
• RemoteAgent: представляет абстракцию распределенного объекта Steppable.

В листинге 1 приведен простой пример реализации объекта DistributedState. При инициализации для каждого LP задаются 100 агентов и в двухмерном непрерывном пространстве (DContinuousGrid2D) случайным образом определяются их позиции.

Листинг 1. DSimulation

В листинге 2 показан код для очень простого агента, создаваемого с помощью двух объектов: абстрактным классом RemoteDAgent и реализующем агента классом – DAgent. Эти два объекта являются подклассами RemoteAgent и определяют местонахождение агентов в пространстве и их положение в рамках сетевой структуры (без привязки к географическим координатам).

Листинг 2. DAgent

В листинге 3 приведен пример кода, реализующий экземпляр брокера сообщений Apache ActiveMQ на локальном компьютере. В тестовом примере выполняется 8 LP.

Листинг 3. DTestLocalMachine

Некоторые новые функции D-MASON

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

1. Разделение пространства в D-MASON

D-MASON поддерживает два вида пространств: геометрическое (двух- или трехмерное) и сетевое, в котором агенты распределяются по узлам сети, а отношения между ними описываются ребрами. Для разделения геометрических пространств предлагается два подхода:

• Равномерное разбиение, при котором моделируемое пространство делится на ячейки одинакового размера. На рис. 5 приведен упрощенный пример разделения двухмерного пространства, представляющего США, на 9 ячеек. Желтая, красная и зеленая зоны – это перекрывающиеся области между ячейками AOI, о которых упоминалось выше. К сожалению, такое разбиение не гарантирует сбалансированного разбиения (например, если предположить, что на рис. 5 серые зоны являются территориями с высокой плотностью агентов, то вычислительная нагрузка на LP будет очень неравномерной).

Рис. 5. Равномерное разбиение пространства на 9 ячеек

• Неравномерное разбиение, при котором учитывается пространственное распределение агентов для последующей балансировки нагрузки между LP. Для разделения применяется алгоритм построения дерева квадрантов или квадродерева (Quad-tree), в котором каждая его часть делится на четыре сбалансированные области (квадраты, прямоугольники), а точка разделения – центр скопления агентов, взвешенный в соответствии с их вычислительной сложностью. Пример такого разбиения для 9 LP приведен на рис. 6. Как видно, размер ячейки обратно пропорционален ее вычислительной сложности. Ниже будут приведены результаты, показывающие, что такая стратегия улучшает масштабируемость и снижает нагрузку, связанную с синхронизацией.

Рис. 6. Неравномерное разбиение пространства c использованием квадродерева для расчетов на 9 LP. Насыщенность цвета определяется плотностью распределения агентов

Аналогичным образом в D-MASON разбивается трехмерное пространство, но только усложняется процесс синхронизации. Так, для простого примера, приведенного на рис. 5, в случае добавления третьего измерения в прогрессии увеличивается число соседних ячеек. Для 2D случая их 8, а для 3D – 26.

2. Разделение распределенной сети

Очень часто изучаемая предметная область, рассматриваемая через призму агентного взаимодействия, может быть структурирована в виде семантической сети. В процессе распараллеливания соответствующий модели, задача состоит в том, чтобы разделить сеть на фиксированный набор компонент таким образом, чтобы они имели приблизительно одинаковый размер, но самое главное – количество соединяющих ее узлы элементов, принадлежащих разным компонентам, должно быть сведено к минимуму (рис. 7). Для решения обозначенной задачи в D-MASON реализован алгоритм графовой декомпозиции METIS.

Рис. 7. Разделение сети в пакете D-MASON

3. Механизм согласованности памяти

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

4. Блок, обеспечивающий связь с другими блоками

В D-MASON предусмотрено два вида связи:

Централизованная – используется для архитектур общего назначения с применением JMS и сервера Apache ActiveMQ.

Децентрализованная, которая разработана для экстремально масштабных вычислений (extreme-scale computing) с использованием программного интерфейса MPI.

5. Управление системой

Управление D-MASON осуществляется с использованием контейнера сервлетов Jetty, а для пользовательского интерфейса был использован стиль дизайна приложений, разработанный Google. Для пользователя панель управления предоставляет четыре окна со следующими настройками:

• Окно мониторинга для отслеживания доступных вычислительных ресурсов в сети, с информацией о количестве узлов, их загруженности, доступной памяти и т.д., с возможностью выбора конкретных ресурсов для запуска планируемой симуляции.
• Окно симуляций со списком всех выполняемых в текущий момент симуляций, позволяющее управлять ими (останавливать, перезапускать, отменять).
• Лог системы, содержащий информацию о всех выполненных симуляциях, их параметрах, сгенерированных файлах.
• Окно параметров, в котором можно менять конфигурация системы (IP адрес, номер порта и др.).

6. D-MASON в облаке

В D-MASON реализовано расширение, позволяющее масштабировать агент-ориентированные модели, реализуя среду «Симуляция как услуга» (SIMulation-as-a-Service (SIMaaS)), протестированную на базе облака Amazon Web Services.

Вычислительные эксперименты

В этом разделе будут приведены результаты различных вычислительных экспериментов по оценки масштабируемости D-MASON при реализации классических агент-ориентированных моделей, а также при реализации D-MASON в облачной среде.

Масштабируемость D-MASON для различных агент-ориентированных моделях

В рамках первой серии расчетов оценивалась масштабируемость пакета D-MASON для перечисленных ниже четырех агент-ориентированных моделей, реализованных в 2D-среде:

• Круг (Circle) – модель, в которой рассматривается набор взаимодействующих частиц (притягивающихся и отталкивающихся) в ограниченном пространстве с определенном радиусом. Через некоторое время система приходит в стабильное состояние.
• Боиды (Boids, Flockers) – модель, разработанная Крейгом Райнольдсом в 1986-м году в качестве симулятора перемещения стаи птиц, в основе которой лежит простой набор правил: сплоченность (особи стараются держаться ближе к центру масс), разделение (особи избегают столкновений), выравнивание (особи двигаются в направлении соседних особей).
• Игра «Жизнь» (Game of Life) – клеточный автомат, предложенный Джоном Конвеем в 1970 году. Каждая клетка (особь) может находиться в двух состояниях (быть живой или мертвой), правила перехода клеточного автомата к следующему поколению особей весьма просты и зависят от состояний соседних клеток.
• Муравьиный алгоритм (Ant colony optimization algorithms) – модель, основанная на поведении муравьев, которые в процессе поиска питания прокладывают феромонами тропу между своим гнездом и источником пищи.

На рис. 8 приведены полученные результаты для каждой из четырех моделей с использованием 10⁶ агентов и 1000 шагов симуляции. Левый график показывает зависимость времени расчетов от числа используемых LP, а график справа – ускорение. Как видно, игра «Жизнь» и модель «Боиды» демонстрируют очень хорошие результаты: ускорение составляет ≈ 62 и ≈ 89 раз соответственно.

Рис. 8. Масштабируемость различных агент-ориентированных 2D моделей, реализованных в D-MASON для 10⁶ агентов

Наихудшие показатели у муравьиного алгоритма (≈ 2), поскольку распределение муравьев по пространству в ходе симуляций постоянно меняется.

Помимо расчетов в 2D среде были проведены эксперименты с моделью боидов, реализованной для трехмерного пространства размерностью 10³×10³×10³ с использованием 10⁶ агентов. На рис. 9 приведены результаты симуляций с применением двух видов связи – централизованной и децентрализованной. Как видно, в обоих случаях ускорение очень хорошее (70,7 раз для централизованной и 72,9 раз для децентрализованной связи).

Рис. 9. Масштабируемость 3D модели в D-MASON для 10⁶ агентов (ось абсцисс – число LP, ось ординат – время симуляций в миллисекундах)

D-MASON в облачной среде: оценка производительности и стоимости

В рамках второй серии расчетов оценивалась производительность D-MASON в облаке с использованием модели боидов, реализованной для 2D пространства размерностью 6400×6400 с 10⁶ агентов. Каждая симуляция выполнялась в течение 15 минут, а в качестве результатов рассматривалось количество выполненных шагов за это время, а также стоимость облачного сервиса. Девять стратегий пространственного разделения (4×4, 4×8, 6×8, 8×8, 10×8, 12×8, 14×8, 16×8, 12×12) соответственно определили 16, 32, 48, 64, 80, 96, 112, 128 и 144 ячеек для эквивалентного количества задействованных LP. Для расчетов был использован веб-сервис, предоставляющий вычислительные мощности в облаке – Amazon Elastic Compute Cloud (Amazon EC2) с инстансами (instance) c4.4xlarge со следующими характеристиками: процессор Intel Xeon E5-2666 v3 (Haswell) с 16 vCPU и 30 ГБ памяти. Стоимость сервиса на момент проведения расчетов составляла 0,80 $ в час (по запросу) или 0,14 $ в час (по свободным ресурсам). Полученные результаты, являющиеся усредненными величинами после 10 симуляций для каждой из 9 стратегий, приведены в таблице 1. Как видно, D-MASON в облаке хорошо масштабируется, а затраты на проведение симуляций незначительны для всех рассмотренных случаев.

Таблица1

D-MASON в облачной среде: сравнение производительности и стоимости

Более подробно про эксперименты с D-MASON можно прочитать здесь: [Gennaro Cordasco, Vittorio Scarano, Carmine Spagnuolo (2018): Distributed MASON: A scalable distributed multi-agent simulation environment // Simulation Modelling Practice and Theory, Volume 89, 2018, Pages 15-34, ISSN 1569-190X, https://doi.org/10.1016/j.simpat.2018.09.002].