Иерархическая платформа для параллельной реализации пространственно-распределенных агент-ориентированных моделей (A Hierarchical Parallel Simulation Framework for Spatially-explicit Agent-based Models, HPABM).

Разработанная в Национальном центре суперкомпьютерных приложений (National Center for Supercomputing Applications, NCSA) Иллинойского университета иерархическая платформа позволяет реализовывать агент-ориентированные модели, построенные на базе геоинформационных систем с использованием высокопроизводительных вычислительных ресурсов. При расчетах исходная агентная модель декомпозируется на несколько субмоделей, каждая их которых представляет собой отдельный блок для параллельных вычислений, содержащий набор агентов, имеющих географическую привязку.

Соотношение (1) определяет формальную структуру HPABM, а на рисунке 1 в концептуальном виде представлена конструкция HPABM. Каждая агент-ориентированная модель, разработанная с использованием HPABM, содержит в себе наборы субмоделей, агрегированных в группы супермоделей. Субмодель является простой вычислимой единицей, содержащей набор агентов и соответствующую им среду, в то время как супермодели агрегируют информацию от своих субмоделей и организуют ее обмен с другими супермоделями.

                                           (1)

при условиях:
; ;
;
;
;
;

где

 – графы, содержащие супер- и субмодели;

SuperM, SubM – наборы супер- и субмоделей (будут определены позже);
V, E – вершины и ребра графа G, содержащего супермодели;
 – вершины и ребра графа , содержащего субмодели;
 – субграф, содержащий субмодели i-ой супермодели; ;
 – вершины и ребра субграфа ;
;
;
 – матрицы смежности для соответствующих графов;
 – вершины соответствующих графов;
 – супермодели i и j в наборе супермоделей;
 – общее количество супер- и субмоделей;
 – субмодели в i-ой супермодели ;
 – количество субмоделей в i-ой супермодели;
 – субмодели, входящие в набор субмоделей.

Рис. 1. Концептуальное представление агент-ориентированной модели, разработанной в HPABM и реализуемой в параллельном режиме (A – распределение супер- и субмоделей; B – граф, показывающий топологию супермоделей)

Упрощенно каркас HPABM может быть также представлен четырьмя уровнями (с соответствующими графами): модель, субмодель, супермодель, процессор (рисунок 2). Агентам, связям между ними и среде их функционирования соответствует граф, представляющий динамику всей системы. Процессоры могут быть организованы в граф отображающий аппаратную архитектуру, и, в свою очередь супер- и субмодели представляются графами, связывающими агентную модель с вычислительными ресурсами. При использовании решеток для отображения набора субмоделей (см. рис. 1), набор вершин графа субмоделей может быть определен следующим образом:

                (2)

где  – вершина в наборе ;  – субмодель, находящаяся в i-ом ряду и j-ом столбце решетки набора субмоделей, nr(nc) – количество рядов (столбцов) решетки.

Рис. 2. Архитектура HPABM

Супермодели

Каждая супермодель организует порядок вычислений набора субмоделей, а также межпроцессорную связь и обмен информацией с другими супермоделями. Набор супермоделей SuperM (см. соотношение 1) может быть определен таким соотношением:

                              (3)

где  – i-я супермодель, представляющая собой шестикомпонентную структуру,  – общее количество супермоделей, spid – идентификационный номер супермодели, определяемый набор субмоделей . Далее,  обозначает супермоделей, являющихся соседями , а ps хранит информацию о процессоре, с которым супермодель связана. Processors – набор процессоров, используемых для вычисления агентной модели и он может динамически обновляться в процессе расчетов. Buffer^sp является буфером обмена информацией относительно состояния агентов и их среды между супермоделями.

Таким образом, супермодели обеспечивают механизм связывания между процессорами суперкомпьютера и агент-ориентированными моделями. Супермодели могут быть представлены в виде направленного графа (рис. 1), в котором каждая супермодель является вершиной, а отношения между ними – ребрами.

Субмодели
Выше было сказано, что субмодели являются основными вычислимыми единицами HPABM, и при этом соотношение (4) определяет набор субмоделей SubM (упомянутый в соотношении 1). Каждая субмодель связана с соответствующей супермоделью посредством информации model^sp. Используя информацию о своих соседях, хранящуюся в NB^sb, субмодель может сообщить, информация от какой супермодели ей нужна для дальнейшей оптимизации межпроцессорного сообщения.

      (4)

где

 – k-я субмодель из набора субмоделей;

sbid – идентификационный номер субмодели;
AG, EN – наборы агентов и их среда, рассматриваемые в субмодели;
model^sp – супермодель к которой соотносится ;
NB^sb – набор субмоделей, являющихся соседями ;
n^sb – общее количество субмоделей.

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

Рис. 3. Набор субмоделей, разработанных в HPABM (A – распределение субмоделей; B – граф субмоделей, где супермодели дифференцированы по цвету)

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

Рис. 4. Субграф, связывающий суб- и супермодели.

Техническая реализация иерархическая платформа для параллельной реализации агентных моделей.

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

Начало алгоритма
1. Инициализация модели
      1.1. Определение степени необходимой детализации модели
      1.2. Дезагрегирование модели на субмодели
      1.3. Построение топологии субмоделей
      1.4. Присваивание субмоделей к супермоделям
      1.5. Построение топологии супермоделей
2. Выполнение модели
      For на каждой итерации выполняется проверка
             If Is_ReBuild_SuperModel_Topology() == True Then
                     Перепостроение топологии супермоделей
                     Перенос субмоделей между супермоделями
             EndIf
             For супермодели sp, рассчитываемой на процессоре p
                     For каждой субмодели sb, входящей в супермодель sp
                              Обновление субмодели sb
                     End For
             End For
             Синхронизация модели
      End For
3. Получение результатов от супермоделей
4. Окончание работы модели
Окончание алгоритма

Листинг 1. Алгоритм реализации агентной модели, разработанной в HPABM

Пример использования

В качестве примера использования HPABM разработчиками была реализована простая пространственная агентная модель «Хищник-жертва». Пространство задано двухмерной решеткой, ячейки которой содержат различное количество ресурсов, изменяемое в единицу времени. Агенты модели отличаются несколькими характеристиками (размер, возраст и др.), а также правилами поведения, что по-разному влияет на отношения «агент-среда». Представленная на решетке модель разделена на области (содержащие агентов и часть среды), каждая из которых обрабатывается субмоделью. В свою очередь субмодели объединены в супермодели (рисунок 5).

Рис. 5. Реализация простой агентной модели в HPABM (Слева – агенты и среда, справа – супер- и субмодели; размер ландшафта 1 200×1 200, количество агентов – 10 000; пространство субмоделей 8×8, ландшафт, обрабатываемой одной субмоделью 150×150, количество супермоделей – 5).

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

Эксперименты
Для расчетов авторы использовали суперкомпьютер Mercury, расположенный в Национальном центре суперкомпьютерных приложений Иллинойского университета. Платформа HPABM реализована на C с использованием программного интерфейса MPI (Message Passing Interface) для распараллеливания. При проведении экспериментов с упомянутой выше моделью отслеживалось влияние детализации пространства на производительность параллельной версии с использованием двух вычисляемых характеристик – ускорение (S_np, уравнение 5) и эффективность (E_np, уравнение 6).

S_np = T₁/T_n                                                (5)

E_np = S_np / n                                               (6)

где T₁ – время выполнения последовательной версии алгоритма, T_n – время выполнения параллельной версии на n процессорах.

Для оценки влияния детализации пространства были проведены расчеты по четырем сценариям G₁, G₂, G₃, G₄, которые отличаются размером решетки (см. таблицу 1). Размер ландшафта в тестируемой модели 12 800×12 800, количество агентов – 409 600, а количество итераций 200. В рамках каждого сценария модель запускалась с различным числом процессоров от 2 до 16, изменяемым с шагом 2, со средним числом прогонов равным 10 (для получения усредненных оценок). 

В таблице 2 приведено время выполнения агентной модели для четырех сценариев. Как видно, время расчетов уменьшается в зависимости от использования дополнительных процессоров. Отметим, что для последовательной версии модели среднее время вычислений составило 1126,3 секунд. 

Таблица 1

Параметры сценариев для получения оценок производительности

Таблица 2

Время выполнения агентной модели для четырех сценариев, в секундах

На рис. 6 показаны результаты оценок производительности модели, рассчитанные по формулам (5) и (6). Как видно, ускорение увеличивается, а эффективность расчетов снижается в зависимости от прироста числа процессоров.

Рис. 6. Результаты оценки производительности для параллельной версии модели (A: ось абсцисс – число процессора, ось ординат – ускорение; B: ось абсцисс – число процессора, ось ординат – эффективность)

Далее были проведены два эксперимента (Exp₁ и Exp₂) для оценки масштабируемости модели в зависимости от размера пространства и количества агентов. В таблице 3 приведены параметры для экспериментов – для каждого сценария размер решетки для субмоделей составляет 32×32, а количество супермоделей для всей агентной модели – 16. Число прогонов для каждого сценария 10, а количество итераций в рамках каждого прогона 200.

Таблица 3

Параметры для проведения экспериментов

На рис. 7 и 8 показаны результаты расчетов для параллельной версии агентной модели. Как видно, ускорение и эффективность прирастают в зависимости от увеличения ландшафта и снижаются при увеличении числа агентов.

Рис. 7. Оценки производительности агентной модели в зависимости от размера ландшафта

Рис. 8. Оценки производительности агентной модели в зависимости от числа агентов

В таблице 4 приведены результаты оценки производительности модели с размером ландшафта 12 800×12 800, числом агентов 409 600 и размером решетки для субмоделей 16×16 в зависимости от изменения числа процессоров. При этом отслеживаемые величины ведут себя вполне ожидаемо.

Таблица 4

Производительность параллельной версии модели

HPABM также использовалась для агентных моделей большой размерности, техническая реализация которых была аналогична описанной выше и во всех случаях показала свою эффективность. Более подробно про HPABM можно прочитать в публикациях автора – Wenwu Tang.