Исследователи из автономного университета Барселоны разработали инструмент для распараллеливания агент-ориентированных моделей – Care HPS (High Performance Simulation), позволяющий в автоматическом режиме решать задачи распределения выполняемого кода, балансировки вычислительной нагрузки, связи и синхронизации. Ниже кратко описывается предлагаемый фреймворк, а также приводятся результаты экспериментов.
Первая версия Care HPS появилась в 2004 г. как результат развития агент-ориентированной модели для изучения поведения косяков рыб, построенной с использованием технологии MPI и консервативного алгоритма синхронизации. За период 2005-2008 гг. была улучшена масштабируемость приложения, что позволило значительно увеличить число агентов при запуске симуляций. В 2009 г. в Care HPS для выборочной спецификации агентов был реализован механизм нечеткой логики, в 2010-2012 гг. улучшены механизмы распределения выполняемого кода и балансировки вычислительной нагрузки, а в 2013 г. функционал системы был расширен за счет использования массовой синхронной параллели (Bulk Synchronous Parallel). В 2014 г. фреймворк был существенно модернизирован на уровне реализующих агентов классов с целью лучшей масштабируемости в связи с ростом ресурсоемкости задач. Масштабируемость, безусловно, зависит от конкретной задачи, поэтому в Care HPS предлагаются различные механизмы синхронизации.
Архитектура Case HPS
Care HPS поддерживает как интерфейс передачи сообщений MPI, так и технологию OpenMP и содержит в себе несколько компонент, реализованных на языке C++ (рис. 1). Пользователи решают задачу проектирования модели (в том числе с использованием готовых функциональных элементов управления), а всю работу по распределению агентов по процессорам, синхронизации процессов и т.д. выполняет фреймворк.
Рис. 1. Архитектура Case HPS
Далее расскажем про наиболее важные компоненты Care HPS.
Компоненты агентной модели
Компонент Agent имеет встроенный класс agent, реализующий поведение агента в двух- и трехмерном пространствах с использованием следующих полей:
- position – определяет положение агента в пространстве;
- velocity – определяет направление агента;
- covering radius – определяет радиус взаимодействия агента с окружающей средой и другими агентами;
- member – используется для сериализации состояния агента (сериализуемый компонент);
- ID – уникальный идентификатор агента;
- random_move – определяет, перемещается ли агент случайно;
- alive – определяет, жив ли агент.
Моделируемая задача может потребовать дополнительных полей, которые должны быть реализованы внутри базового метода update_agent, выполняемого каждую единицу времени с момента начала симуляции и до ее завершения.
Важным функционалом класса agent является возможность сериализации состояния агента, осуществляемой с использованием компонента member. Это необходимо, поскольку агенты могут мигрировать из одного процесса в другой, с выполнением соответствующих операций удаления и создания, но при этом состояния агентов должны сохраняться.
Компонент Environment позволяет моделировать окружающее агентов пространство внутри модели, а соответствующий программный класс, являющийся контейнером, содержит методы для взаимодействия с агентами модели.
Часто при запуске симуляций требуется сформировать уникальный набор начальных значений для агентов модели. С использованием компонента Random number generation можно определить их посредством нормального, экспоненциального, гамма и равномерного распределений.
Последний компонент Model позволяет производить общую настройку симуляции.
Компоненты, отвечающие за параллельные вычисления и распределение программного кода
На этом уровне присутствуют следующие компоненты:
Logical process – создает распределенные процессы, связанные посредством передачи сообщений, а также контролирует ход их выполнения.
Sync – осуществляет синхронизацию.
Partitioning – определяет наиболее эффективный механизм распределения агентов по процессам и реализует его.
Balancing – осуществляет балансировку вычислительной нагрузки (назначение агентов для конкретных ядер, изменение размера разделов и т.д.).
Разработчики Care HPS сравнили свой продукт с некоторыми наиболее известными аналогами – Flame, D-Mason, Pandora и Repast HPC. Каждый из этих программных средств имеет сильные и слабые стороны, связанные с первоначальными целями их создания.
В Care HPS агенты реализуются путем расширения базового класса Agent, в пакете Flame посредством настройки X-машины, в D-Mason с помощью расширения абстрактного класса RemoteAgent, также позволяющим сериализовать агентов. В Pandora используется общий базовый класс, посредством которого моделируется любая сущность, а в RepastHPC пользователь должен реализовать функционал агентов с помощью методов базового класса и более того, каждый агент должен реализовать интерфейс Agent.
Для синхронизации в Care HPS используется метод обратного вызова, во Flame – «доска сообщений», гарантирующая, что все агенты будут видеть один и тот же набор сообщений, в D-Mason применяется пошаговая локальная синхронизация, в Pandora – система планирования, а в RepastHPC – дискретный планировщик событий.
Care HPS предлагает три стратегии распределения агентов: кластерное, чистое MPI и гибридное, а для экспертов в области высокопроизводительных вычислений возможна реализация других алгоритмов. Во Flame применяется алгоритм распределения нагрузки с использованием перебора и упорядочения агентов по круговому циклу (Round Robin Partitioning). В D-MASON главное приложение разделяет моделируемое пространство на части и распределяет рабочую нагрузку по ведомым процессам, каждый из которых задействует один или несколько логических процессоров в соответствии с их вычислительными возможностями. В Pandora реализовано пространственное разделение, при котором каждый вычислительный узел получает часть моделируемой среды и агентов, расположенных в его границах. Затем каждая часть делится на четыре раздела, обрабатываемых последовательно. RepastHPC реализует разбиение с помощью концепции проекции, в рамках которой пользователь может выбрать один из трех ее типов: решетка, непрерывное пространство и сеть.
Связь между процессами в Care HPS реализуется в следующие моменты: (1) миграция агентов между процессами; (2) синхронизация; (3) инициализация модели; (4) балансировка нагрузки. В свою очередь во Flame связь осуществляется через «доску сообщений», а возможности прямого обмена сообщениями между агентами не существует. В D-MASON связь между процессами основана на поведенческом шаблоне проектирования передачи сообщений «Издатель/Подписчик», в котором отправители сообщений напрямую не связаны с подписчиками, равно как и последние c отправителями. В свою очередь сообщения делятся на классы, которые не содержат сведения о подписчиках и издателях. Pandora использует OpenMP и MPI таким образом, что локальные взаимодействия осуществляются посредством интерфейса OpenMP, а на каждом шаге соседние узлы обмениваются информацией посредством директив MPI.
Приведем два самых простых примера использования Care HPS: (1) агент-ориентированная модель перемещения рыб с препятствиями; (2) расширение возможностей пакета путем использования новой стратегии распределения нагрузки.
Движение рыбы в модели зависит от ее текущего положения и наличия препятствий, а также от поведения соседних рыб. Код в листинге 1 проверяет, происходит ли столкновение, и если да, то агент отталкивается и меняет направление движения.
void fish::check_environment(void) {
vector<object*> obj_env = ENV->getObjects();
for (vector<object*>::iterator ob = obj_env.begin(); ob != obj_env.end(); ob++) {
if ((*ob)->check_collision(
this->get_position(),
this->get_velocity(),
MAXIMUM_VISION_RANGE)) {
this->repulsion(*this);
}
}
}
Листинг 1. Проверка наличия препятствий
Рассмотрим также пример разработки новой стратегии распределения вычислительной нагрузки. На первом этапе создается начальное количество потоков следующим образом: threads = number_agent / total_number_agents ∗ number_cores, где number_agent – количество агентов внутри раздела, total_number_agents – общее количество моделируемых агентов, а number_cores – количество процессов MPI, поделенное на 4 (выбор числа 4 связан с архитектурой используемых ЦП).
На втором этапе потоки создаются динамически, и пример такого автоматического распараллеливания приведен в листинге 2.
void partitioning_strip_hybrid::execute() {
long thread = number_agent / total_number_agents * number_cores;
if (abs(thread) >= 1) {
if (abs(thread) == 1) {
omp_set_num_threads(2);
}
else if ((abs(thread) >= 2) && (abs(thread) <= 8)) {
omp_set_num_threads(abs(thread));
}
else if (abs(thread) > 8) {
omp_set_num_threads(8);
}
#pragma omp parallel default(none) firstprivate(i) shared(_bucket)
{
unsigned long j;
#pragma omp for private(j) schedule(dynamic) nowait
// Для каждого агента выполняется следующее
for (j = 0; j < _bucket->size(); j++) {
_bucket->at(j)->update_agent();
}
}
}
else {
// выполнить цикл
}
}
Листинг 2. Реализация стратегии распределения нагрузки
Результаты вычислительных экспериментов
Ниже описываются результаты четырех экспериментов, проведенных с тремя агент-ориентированными моделями: (1) перемещения рыб, (2) муравьиной колонии и (3) покупателей.
Первый эксперимент
В реализованной модели у агента есть список необходимых к покупке товаров, которые распределены по множеству магазинов. Каждый из магазинов продает только один вид товара, а цель агента – купить весь перечень из списка.
В рамках расчетов было реализовано три сценария: 1) агенты перемещаются случайным образом, чтобы найти магазин для покупки товара из списка, 2) агенты могут видеть магазины в пределах определенного диапазона, 3) некоторые агенты являются «умными», т.е. вычисляют оптимальный маршрут и более того, агенты модели обмениваются информацией об известных им магазинах.
В таблице 1 приведены результаты симуляций в сравнении с версией модели с идентичными параметрами, но реализованной в пакете Netlogo. Как видно, применение алгоритмов Care HPS в случае интенсивного обмена информацией более эффективно.
Таблица 1
Сравнение производительности двух реализаций одной модели для трех сценариев (цифры означают количество шагов симуляций для достижения поставленной цели)
| Сценарий 1 | Сценарий 2 | Сценарий 3 | |
| Netlogo | 14310 | 6983 | 2000 |
| Care HPS | 19082 | 1361 | 348 |
Второй эксперимент
В этом эксперименте имитировалась самоорганизация косяка рыб, возникающая в результате локальных взаимодействий отдельных особей, поведение которых зависит от действий соседей. Ни рис. 2 показан результат симуляций для 8192 агентов-рыб с использованием двух процессоров. Трехмерное пространство представляет собой море, а желтая решетка – препятствие, изменившее траекторию движения косяка, который через последовательность шагов проплыл мимо преграды.
Рис. 2. Поведение косяка рыб, избегающих столкновения
Третий эксперимент
С использованием модели муравьиной колонии были проведены расчеты для 1000, 2500, 5000 и 10000 агентов с применением двух стратегий разделения вычислительной нагрузки: чистого разделения с использованием директив MPI и гибридного. На рис. 3 приведены результаты для обеих стратегий, из которых следует, что гибридный механизм существенно эффективнее.
Рис. 3. Общее время выполнения алгоритма для чистого MPI и гибридного разделения нагрузки
Четвертый эксперимент
В рамках последнего эксперимента оценивалась масштабируемость агент-ориентированной модели покупателей, реализующей третий сценарий первого эксперимента.
Ни рис. 4 и 5 приведены результаты для 10000 и 50000 агентов соответственно, которые осуществляют 50 000 шагов симуляции и должны приобрести 10 товаров. Как видно, масштабируемость приложения весьма хорошая.
Рис. 4. Масштабируемость модели с 10000 агентами, выполнивших 50000 шагов
Рис. 5. Масштабируемость модели с 50000 агентами, выполнивших 50000 шагов
Далее тестировалась способность Care HPS эффективно работать с моделями большой размерности. На рис. 6 и 7 видно, что для 200000 и 250000 масштабируемость также приемлемая.
Рис. 6. Масштабируемость модели для 50000 шагов, выполненных с использованием 64 ядер
Рис. 7. Масштабируемость модели для 200000, 250000 агентов и 50000 шагов, выполненных с использованием 64, 128, 192 и 256 ядер
В настоящее время разработчики Care HPS используют этот фреймворк в проекте, направленном на прогноз распространения лихорадки денге. Более подробно про Care HPS можно прочитать здесь.
