Исследователи из автономного университета Барселоны разработали инструмент для распараллеливания агент-ориентированных моделей – 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 partitionig_strip_hybrid :: execute () {
long thread = number_agent / total_number_agents∗number_cores ;
if (abs (num_thread) >=1){
if (abs (thread )==1)
omp_set_num_threads (2);
else if ((abs(thread) >= 2) and (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 можно прочитать здесь.
Партнеры
