В работе ученых Института систем и робототехники Лиссабона (Institute for Systems and Robotics), Университета Вооруженных сил Эквадора (Universidad de las Fuerzas Armadas), Университета Минью (Португалия) рассматривается многопоточное Java приложение, реализующее параллельную версию агент-ориентированной модели «Хищник-жертва» (Predator-Prey for High-Performance Computing Agent-Based Model или PPHPC ABM) с целью оценки производительности приложения в результате применения различных способов его распараллеливания.

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

1. Краткое описание тестируемой модели PPHPC

1.1. Переменные модели

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

Тип агента t принимает значения s или w, относящиеся либо к жертве (в данном случае к овце – sheep) либо к хищнику (волку – wolf). Поведение жертвы определяется необходимостью потребления статичной пищи, а хищника – необходимостью охоты на жертву. Каждый из агентов имеет запас энергии, пополняющийся на величину g^{s,w} при потреблении ресурса, сокращающийся на величину l^{s,w} при движении и уменьшающийся на половину при размножении. Когда запас энергии равен нулю, агент выбывает из симуляции, а в случае достижения этого запаса значения r^{s,w}_T агент может воспроизвести потомство с вероятностью r^{s,w}_P. Переменные X и Y определяют местонахождение агента в решетке, при этом агенты могут взаимодействовать с ресурсами и другими агентами только в случае нахождения в одной и той же ячейке.

Таблица 1

Переменные модели

Программный класс	Переменная (или параметр)	Обозначение	Диапазон значений
Агент	Тип	t	s, w
	Энергия	E	1,2, …
	Позиция в решетке по горизонтали	X	0,1, … , xenv – 1
	Позиция в решетке по вертикали	Y	0,1, … , yenv – 1
	Энергетическая полезность пищи	gs, gw	0,1, …
	Потери энергии от движения	ls, lw	0,1, …
	Предел для размножения	rsT, rwT	1,2, …
	Вероятность размножения	rsP, rwP	0,1, … , 100
Ячейки решетки	Позиция по горизонтали	x	0,1, … , xenv – 1
	Позиция по вертикали	y	0,1, … , yenv – 1
	Переменная для счета ячеек	C	0,1, … , cr
Пространство	Размер по горизонтали	xenv	1,2, …
	Размер по вертикали	yenv	1,2, …
	Переменная для перезагрузки пространства	cr	1,2, …

1.2. Процесс работы

Алгоритм 1 описывает последовательность выполнения симуляции и связанных с ней процессов. Выполнение начинается с процесса инициализации Init (), в рамках которого пространство размерностью x_env×y_env заполняется программными сущностями, причем вероятность появления в ячейке ресурса составляет 50%, а агенты, количество которых задается пользователем, равномерно распределяются по решетке с начальным запасом энергии, определяемым случайным образом в рамках диапазона от 1 и g^{s,w}.

После инициализации модели запускается процесс сбора статистики GetStats (), а затем основной цикл симуляции, в котором каждая итерация состоит из четырех шагов: 1) движение агента; 2) прирост ресурсов в ячейках решетки; 3) действие агента; 4) сбор статистики с данного шага.

На первом шаге агент осуществляет движение в окрестности фон Неймана (т.е. вверх, вниз, влево, вправо или же остается в той же ячейке с одинаковой вероятностью), причем потеря энергии на величину l^{s,w} происходит даже если агент остается на месте. На втором шаге, во время процесса GrowFood () каждая ячейка решетки проверяется на предмет наличия ресурса, а на третьем – инициируется процесс Act (), причем перед выполнением данного шага список агентов модели перемешивается с целью получения произвольного порядка.

---

Алгоритм 1. Основной алгоритм симуляции.

---

1: Init ()

2: GetStats ()

3: i ← 1

4: for i <= m do

5:      for each agent do // в любом порядке

6:                Move ()

7:      end for

8:      for each grid cell do // в любом порядке

9:                GrowFood ()

10:    end for

11:    for each agent do // в произвольном порядке

12:              Act ()

13:    end for

14:    GetStats ()

15: i ← i + 1

16: end for

---

1.3. Параметризация модели

Спецификация модели осуществляется путем настройки параметров и динамических переменных, приведенных в таблице 2. Базовые значения параметров, определяющих размерность модели, составляют: 100×100 для решетки, 400 – численность жертв и 200 – численность хищников. Другие значения, пропорциональные базовым, приведены в таблице 3. Кроме того, для PPHPC предусмотрено два набора значений для переменных, определяющих динамику данной экосистемы. И, наконец, для вычисления стабильных значений выходных переменных модели, число итераций m для каждого прогона составляет 4 000.

Таблица 2

Динамические переменные и параметры пространства

Тип	Переменная (или параметр)	Обозначение
Параметры пространства	Размер пространства	xenv, yenv
	Начальное число агентов	P0s, P0w
	Количество итераций	m
Динамические переменные	Энергетическая полезность пищи	gs, gw
	Потери энергии от движения	ls, lw
	Предел для размножения	rsT, rwT
	Вероятность размножения	rsP, rwP
	Переменная для перезагрузки пространства	cr

Таблица 3

Начальные параметры модели

Размер пространства	xenv × yenv	P0s	P0w
100	100 × 100	400	200
200	200 × 200	1 600	800
400	400 × 400	6 400	3 200
800	800 × 800	25 600	12 800
1 600	1 600 × 1 600	102 400	51 200
3 200	3 200 × 3 200	409 600	204 800
6 400	6 400 × 6 400	1 638 400	819 200
12 800	12 800 × 12 800	6 553 600	3 276 800

Таблица 4

Наборы значений для динамических переменных

Переменная	Обозначение	Набор 1	Набор 2
Энергетическая полезность пищи для жертвы	gs	4	30
Потери энергии жертвы от движения	ls	1	1
Предел для размножения жертвы	rsT	2	2
Вероятность размножения жертвы	rsP	4	10
Энергетическая полезность пищи для хищника	gw	20	10
Потери энергии хищника от движения	lw	1	1
Предел для размножения жертвы	rwT	2	2
Вероятность размножения жертвы	rwP	5	5
Переменная для перезагрузки пространства	cr	10	15

В алгоритме 1 процесс GetStats () осуществляет сбор статистики, заполняя вектор , в котором i – номер текущей итерации,  и  – количество жертв и хищников соответственно,  – количество содержащих ресурсы ячеек,  и  – среднее количество энергии для популяций жертв и хищников.

На рис. 1 показаны результаты симуляции для модели с размерностью пространства равным 400. При масштабировании пространства до 12 800 результаты аналогичны, а графики будут отличаться только размерностью вертикальной шкалы.

 

Рис. 1. Результаты симуляции для пространства размерностью 400: (a) размер популяций для первого набора переменных, (b) среднее количество энергии популяций для первого набора переменных, (c) размер популяций для второго набора переменных, (d) среднее количество энергии популяций для второго набора переменных.

2. Реализация многопоточного Java приложения

2.1. Архитектура

Многопоточная Java реализация PPHPC построена по схеме «Модель-Представление-Контроллер» (Model-View-Controller, MVC), которая предполагает проектирование приложения путем разделения на отдельные компоненты модели интерфейса и механизма взаимодействия с пользователем. За счет этого, модификация одного из компонентов будет оказывать минимальное воздействие на остальные (рис. 2).

 

Рис. 2. UML-схема реализации РPPHPC

Модель, представленная интерфейсом IModel, соотносится с пространством – решеткой (интерфейс ISpace), состоящей из ячеек (интерфейс ICell). В свою очередь ячейки связаны с различным числом агентов (интерфейс IAgent). Процесс симуляции можно отслеживать посредством интерфейса IView, а управлять эти процессом (останавливать, начинать снова и т.д.) – с помощью интерфейса IController. Классы, реализуемые интерфейсом IWorkFactory, позволяют создавать объекты для отслеживания процесса симуляции – контроллеры и поставщики работ (создаваемые с помощью интерфейса IWorkProvider).

Контроллер порождает определенное количество рабочих потоков (экземпляров класса SimWorker), выполняющих алгоритм 1. Ниже приведен алгоритм 2, реализующий основной алгоритм симуляции в классе SimWorker, где вызовы ControllerSync () являются точками синхронизации контроллера.

---

Алгоритм 2. Реализация основного алгоритма симуляции в классе SimWorker.

---

1: ControllerSync (1)

2: CreateCells () // распараллеливание кода

3: ControllerSync (2)

4: SetCellNeighbors () // распараллеливание кода

5: ControllerSync (3)

6: CreatePrey () // распараллеливание кода

7: CreatePredators () // распараллеливание кода

8: ControllerSync (4)

9: GetStats () // распараллеливание кода

10: ControllerSync (5)

11: i ← 1

12: for i <= m do

13:    Move () + GrowFood () // распараллеливание кода

14:    ControllerSync (6)

15:    Act () + GetStats ()// распараллеливание кода

16:    ControllerSync (7)

17:    i ← i + 1

18: end for

19: ControllerSync (8)

---

Как видно, процесс Init () из алгоритма 1 делится на четыре обрабатываемых параллельно этапа: (1) создание и инициализация ячеек решетки (строка 2 алгоритма 2); (2) соединение ячеек со своими соседями (строка 4 алгоритма 2); (3) создание жертв (строка 6 алгоритма 2); (4) создание хищников (линия 7 алгоритма 2).

Строки 5-10 из алгоритма 1, реализующие перемещение агентов и прирост ресурсов в клетках, объединены в алгоритме 2 в единый параллельный цикл (строка 13 алгоритма 2). Распараллеливание этих процессов не влияет на логику выполнения симуляции, поскольку Move () и GrowFood () – независимые процессы. Строки 11-14 из алгоритма 1, реализующие процессы Act () и GetStats () также объединены в единый параллельный цикл (строка 15 алгоритма 2). Отметим, что строки 13 и 15 в алгоритме 2 разделены по шагам с целью синхронизации отдельных действий.

2.2. Стратегии распараллеливания

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

На уровне контроллера есть восемь точек синхронизации. Все рабочие потоки должны уведомлять контроллер при достижении этих точек (вызов ControllerSync () в алгоритме 2). Дальнейшее их прохождение зависит от настройки контроллера, однако есть моменты, когда остановка является обязательной (к примеру, во время каждой итерации все агенты должны быть перемещены и все ресурсы обновлены, и только после этого возможно продолжение работы потоков). Далее будем называть такие остановки (например, точку синхронизации 6 – строку 14 алгоритма 2) барьером (barrier или B).

Что касается поставщика работы и ячеек решетки, то синхронизация на их уровне возможна для двух точек: 1) при инициализации агентов модели (процесс Init()) и 2) при перемещении агентов из других ячеек.

Разработчики предложили пять стратегий распараллеливания программного кода, приведенных в таблице 5 с указанием всех возможных точек синхронизации и способов их обработки, где PS (parallelization strategies) – стратегии распараллеливания, WP (work provider) – поставщик работы, S – предполагает сериализацию доступа без остановки рабочих потоков, а Ŝ аналогичен S, но с возможностью вставки агента (что, конечно же, будет замедлять симуляцию).

Таблица 5

Стратегии распараллеливания и обработка возможных точек синхронизации на уровнях контроллера, поставщика работ и ячеек решетки

PS	Контроллер								WP	Ячейки
	1	2	3	4	5	6	7	8		Init ()	Move ()
ST	–	–	–	–	–	–	–	–	–	–	–
EQ	S	B	S	B	S	B	B	S	–	S	S
EX	S	B	S	B	S	B	B	S	–	Ŝ	Ŝ
ER	S	B	S	B	S	B	B	S	B	Ŝ	–
OD	S	B	S	B	B	B	B	S	S	S	S

Далее рассмотрим различия в стратегиях распараллеливания.

ST (single-thread) – однопоточный режим работы (класс SingleThreadWorkFactory), при котором не происходит распараллеливания и синхронизации, предусмотрен для сравнения с многопоточными режимами.

EQ (Equal) – стратегия (обрабатывается классом EqualWorkFactory), при которой каждый поток всегда выполняет одну и ту же работу, назначенную ему соответствующим поставщиком (экземпляром класса EqualWorkProvider) при начальном распределении. Синхронизация на уровне ячеек решетки нужна для исключения ситуации обработки потоком определенной ячейки при одновременном перемещении на нее агентом. В рамках данной стратегии, агенты модели обрабатываются в произвольном порядке и поэтому симуляции не воспроизводимы.

EX (Equal with repeatability) – стратегия почти аналогичная EQ, но в отличие от нее, агенты обрабатываются в одном и том же порядке. Таким образом, применение данной стратегии позволяет реализовывать воспроизводимые симуляции.

ER (Equal with row synchronization) – стратегия с синхронизацией строк решетки, в которой каждый поток последовательно обрабатывает строки на расстоянии как минимум в 3 строки от другого потока (рис. 3). Такой подход позволяет потокам работать параллельно без необходимости синхронизации на уровне ячеек решетки, поскольку потоки синхронизируются в конце каждой строки на уровне поставщика работ. Отметим, что данная стратегия также позволяет реализовывать воспроизводимые симуляции.

OD (On-demand) – стратегия распараллеливания, направленная на балансировку нагрузки между потоками за счет разбиения объема выполняемых ими работ на более мелкие блоки (b), и перенаправления их по запросу от потоков. Как видно из таблицы 5, эта стратегия похожа на EQ и также не позволяет реализовывать воспроизводимые симуляции.

 

Рис. 3. Пример реализации стратегии ER для трех потоков и девяти параллельно обрабатываемых рядов решетки

3. Результаты расчетов

Ниже приведены параметры для различных вариантов расчетов:

Стратегии распараллеливания: NetLogo (NL) и Java (ST, EQ, EX, ER и OD).

Наборы значений для динамических переменных: 1 и 2.

Размер пространства: 100, 200, 400, 800 и 1600.

Количество потоков (только для Java): 1, 2, 4, 6, 8, 12, 16 и 24.

Размер блока b (для стратегии OD): 20, 50, 100, 200, 500, 1000, 2000 и 5000.

3.1. Сравнение производительности

На рис. 4. показаны результаты расчетов для обоих наборов значений динамических переменных, пяти размерностей пространства и всех стратегий распараллеливания (относительно вариантов реализации модели в высокоуровневой среде агентного моделирования NetLogo и однопоточного режима работы). Производительность каждой стратегии рассчитывается как отношение времени выполнения  для однопоточной версии NetLogo и  для стратегии ST к времени выполнения параллельной версии соответствующей стратегии  для p потоков:

.

Судя по рис. 4, однопоточная версия ST в несколько раз быстрее реализации модели в NetLogo. Разработчики PPHPC отмечают, что хотя NetLogo год от года становится все более эффективным средством построения агентных моделей, использование средств разработок более низкого уровня позволяет создавать приложения с более высокой производительностью. И это при том, что Java менее быстрый, нежели C++ и др.

На рис. 5 приведены результаты расчетов для различных размеров пространства. Как и в предыдущем случае (рис. 4) расчеты проводились для 12 потоков и размером блока b для стратегии OD равным 500.

Производительность стратегий EQ и EX приблизительно одинакова, с небольшим преимуществом у первой из них. Как уже отмечалось, изменение порядка обработки агентов несколько снижает эффективность симуляции. Но с другой стороны, возможность реализовывать воспроизводимые симуляции в данном случае является более весомым преимуществом.

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

 

Рис. 4. Производительность тестируемых стратегий распараллеливания: (a) относительно версии в NetLogo и набора переменных 1; (b) относительно стратегии ST и набора переменных 1; (c) относительно версии в NetLogo и набора переменных 2; (d) относительно стратегии ST и набора переменных 2.

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

 

Рис. 5. Результаты расчетов для различных размеров пространства: (a) набор переменных 1; (b) набор переменных 2.

3.2. Варьирование количеством потоков

На рис. 6. приведены результаты симуляции для описанных выше стратегий распараллеливания, трех вариантов пространства (100, 400 и 1 600) в зависимости от числа потоков. За исключением модели с пространством 100, оптимальным числом потоков является 12, что связано с особенностью используемых аппаратных средств. Общий вывод из проведенных расчетов заключается в том, что для крупных пространственных моделей целесообразно использовать больше потоков. То же справедливо для второго набора переменных, который подразумевает более заметную активность агентов. Верно и обратное – меньшее пространство и меньшее число агентов влечет снижение объема работы потоков и, соответственно, увеличивается доля затрачиваемого на синхронизацию времени (от общего объема).

Что касается стратегии OD, то с ее использованием модель масштабируется наилучшим образом с увеличением числа потоков за счет сокращения времени на ожидание.

 

Рис. 6. Время моделирования в зависимости от числа используемых потоков: (a) размер пространства 100, набор переменных 1; (b) размер пространства 100, набор переменных 2; (c) размер пространства 400, набор переменных 1; (d) размер пространства 400, набор переменных 2; (e) размер пространства 1 600, набор переменных 1; (f) размер пространства 1 600, набор переменных 2.

4. Выводы

В работе были исследованы различные стратегии распараллеливания модели PPHPC, в которой рассмотрены важные пространственные компоненты агентного моделирования – движение агентов и взаимодействие между ними в зависимости от расстояния. По результатам проведенных расчетов можно сделать два основных вывода:

1. Распараллеливание пространственно-распределенных агент-ориентированных моделей может дать ощутимый эффект в производительности при условии применения тщательно выверенной стратегии.

2. Каждая из рассмотренных стратегий обладает своими преимуществами и поэтому выбор конкретной среди них обусловлен характеристиками реализуемой агентной модели (размер пространства, количество агентов и др.), а также требованиями к результатам моделирования (т.е. нужны ли воспроизводимые симуляции или нет).

Более подробно про модель и эксперименты можно прочитать в статье: [Fachada, N., Lopes, V.V., Martins, R.C. et al. (2016): Parallelization Strategies for Spatial Agent-Based Models // International Journal of Parallel Programming. February 2016, Issue 1, Vol 44, pp 1–33. doi:10.1007/s10766-015-0399-9].