23.08.2019

Исследователи из автономного университета Барселоны разработали инструмент для распараллеливания агент-ориентированных моделей – 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). Пользователи решают задачу проектирования модели (в том числе с использованием готовых функциональных элементов управления), а всю работу по распределению агентов по процессорам, синхронизации процессов и т.д. выполняет фреймворк.

 CareHPS1.JPG

Рис. 1. Архитектура Case HPS

Далее расскажем про наиболее важные компоненты Care HPS.

Компоненты агентной модели

Компонент Agent имеет встроенный класс agent, реализующий поведение агента в двух- и трехмерном пространствах с использованием следующих полей:

  1. position – определяет положение агента в пространстве;
  2. velocity – определяет направление агента;
  3. covering radius – определяет радиус взаимодействия агента с окружающей средой и другими агентами;
  4. member – используется для сериализации состояния агента (сериализуемый компонент);
  5. ID – уникальный идентификатор агента;
  6. random_move – определяет, перемещается ли агент случайно;
  7. 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 агентов-рыб с использованием двух процессоров. Трехмерное пространство представляет собой море, а желтая решетка – препятствие, изменившее траекторию движения косяка, который через последовательность шагов проплыл мимо преграды.

 CareHPS2.JPG

Рис. 2. Поведение косяка рыб, избегающих столкновения

Третий эксперимент

С использованием модели муравьиной колонии были проведены расчеты для 1000, 2500, 5000 и 10000 агентов с применением двух стратегий разделения вычислительной нагрузки: чистого разделения с использованием директив MPI и гибридного. На рис. 3 приведены результаты для обеих стратегий, из которых следует, что гибридный механизм существенно эффективнее.

 CareHPS3.JPG

Рис. 3. Общее время выполнения алгоритма для чистого MPI и гибридного разделения нагрузки

Четвертый эксперимент

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

Ни рис. 4 и 5 приведены результаты для 10000 и 50000 агентов соответственно, которые осуществляют 50 000 шагов симуляции и должны приобрести 10 товаров. Как видно, масштабируемость приложения весьма хорошая.

 CareHPS4.JPG

Рис. 4. Масштабируемость модели с 10000 агентами, выполнивших 50000 шагов

 CareHPS5.JPG

Рис. 5. Масштабируемость модели с 50000 агентами, выполнивших 50000 шагов

Далее тестировалась способность Care HPS эффективно работать с моделями большой размерности. На рис. 6 и 7 видно, что для 200000 и 250000 масштабируемость также приемлемая.

 CareHPS6.JPG

Рис. 6. Масштабируемость модели для 50000 шагов, выполненных с использованием 64 ядер

 CareHPS7.JPG

Рис. 7. Масштабируемость модели для 200000, 250000 агентов и 50000 шагов, выполненных с использованием 64, 128, 192 и 256 ядер

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

rss
Назад

Статьи
Суперкомпьютерные технологии METIS Агент-ориентированные модели Транспортные модели Parallel computing Параллельные вычисления пешеходная модель БРИКС Биомедицина Монография Axum SWAGES Высокопроизводительные вычисления Междисциплинарное исследование Новости Революция Эксафлопная производительность CUDA Microsoft Social Simulation Conference ГИС Методология запуска О проекте Социальная сеть Эпидемия Case HPS POLARIS TSUBAME Демография Механизм раделяемой памяти Пандемия Ссылки Ядерная атака на США Cуперкомпьютерные технологии XAXIS Иерархическая платформа Моделирование мира Пандора Стратегии распараллеливания автоматическое распараллеливание D-MASON Repast Исследования Моделирование эпидемий Суперкомпьютерная Академия агентная модель FuturICT Russian Supercomputing Days Агент-ориентированный подход Исторические процессы Модель экономики Евросоюза Пространственно-распределенные агентные модели большие данные GPU SEGMEnT Клеточные автоматы Мониторинг планеты Пространственные модели HPABM SSC Контакты Публикации Экономические процессы