В исследовании, проведенном в Университете Северной Каролины и Айовском университете (США) рассматривается подход к распараллеливанию ресурсоемких агент-ориентированных моделей, агенты которых обмениваются информацией и имеют пространственную привязку. В рамках проведенных экспериментов тестировалась производительность параллельной версии модели в зависимости от двух фундаментальных свойств пространственных интерактивных систем: (1) размер пространства, связанного с количеством распределенных по нему агентов, участвующих во взаимодействиях (определяет общий объем межагентных взаимодействий) и (2) радиус взаимодействия (определяет максимальное расстояние, на котором пара агентов может связываться). Оценка преимуществ использования многоядерных аппаратных систем для реализации пространственно-распределенных агент-ориентированных моделей осуществлялась путем сравнения производительности параллельной версии модели против ее последовательного аналога.

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

В свою очередь взаимодействия между агентами зависят от их пространственного расположения, т.е. конкретный агент может взаимодействовать с другими в окрестности с определенным радиусом. Вероятность того что агент i выберет для взаимодействия агента j определяется следующей функцией:

,                                                                                   (1)

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

Таблица 1

Зависимость между коэффициентом α и диапазоном взаимодействия (вычислено на основе соотношения (1) для вероятности равной 0.01)

Коэффициент α	Диапазон взаимодействия (количество ячеек)
0.1	2
0.2	3
0.3	4
0.4	6
0.5	10
0.6	16
0.7	25
0.8	40
0.9	63
1.0	100
1.1	158
1.2	251
1.3	398
1.4	631
1.5	1000

После того как для агента будет рассчитан диапазон взаимодействий, запускается стохастический процесс определения направления для выбора другого агента для общения:

,                                                                                         (2)

где  – параметр, определяющий направление, а U – функция, генерирующая случайное число.

Для текущего агента i местоположение агента j, выбранного для общения вычисляется по следующей формуле:

                                                                           (3)

где () – номер ряда для агента i(j), () –столбец для агента i(j), а  – функция округления.

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

                                                  (4)

где  – текущие мнения агентов i и j;  – измененное мнение после процесса обмена информацией;  – скорость обучения агента i;  – порог возможности восприятия стороннего мнения.

По сути, соотношение 4 определяет, будет ли взаимодействие между парой агентов или нет. Далее будем считать взаимодействие успешным, если взаимодействие состоялось и неудачным в противном случае. С точки зрения вычислительного процесса, успешные взаимодействия гораздо более ресурсоемкие по сравнению с неудачными, поскольку первые сопровождаются процедурой обмена мнениями, а вторые – нет. На рис. 1 показана траектория доли неудачных взаимодействий от их общего числа для первых 100 итераций типичного выполнения последовательной версии модели.

 

Рис. 1. Доля неудачных взаимодействий для первых 100 итераций типичного выполнения последовательной версии модели

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

Параллельная версия модели с взаимодействующими в пространстве агентами для многоядерных архитектур

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

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

 

Рис. 2. Декомпозиция пространственно распределенной агентной модели: распределение частей пространства по потокам; межпотоковые и внутрипотоковые взаимодействия; механизм взаимного исключения потоков

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

Реализация модели

Параллельная версия агентной модели была реализована в C++ с использованием интерфейса OpenMP, предназначенного для программирования многопоточных приложений на многопроцессорных системах с общей памятью.

Производительность приложения тестировалась с помощью двух метрик – ускорения и эффективности. Ускорение – это отношение времени выполнения последовательной версии модели к ее параллельной реализации (уравнение 5). В свою очередь эффективность – это отношение ускорения к числу использованных вычислительных узлов (уравнение 6).

                                                                                                         (5)

                                                                                                         (6)

где  – время выполнения последовательной версии алгоритма, а  – время выполнения параллельной версии, использующей N вычислительных узлов.

Эксперименты

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

Также в рамках экспериментов тестировалась эффективность масштабирования модели.

И, наконец, отметим, что каждая ячейка пространства может быть связана только с одним агентом, а спецификация агентов модели осуществляется с помощью параметров, значения которых приведено в таблице 2. Тысяча итераций была выполнена в рамках одной симуляции для отслеживания динамики системы, а учитывая стохастическую природу агентной модели, для одного эксперимента проводилось 30 симуляций.

Таблица 2

Спецификация параметров агентов, обменивающихся мнениями

Параметр	Значение
Коэффициент α	0.1 – 1.5
Параметр обучения	0.2
Порог восприятия мнения	0.3
Значение мнения	0.0 – 1.0

Первая серия экспериментов. Оценка влияния размера пространства

В первой серии экспериментов оценивалось влияние размера пространства на производительность модели и ее масштабируемость. Всего было произведено пять серий расчетов для пространств размерностью от 1 000×1 000 до 5 000×5 000 с шагом 1 000×1 000. Коэффициент α для всех расчетов равен 0.9 и, соответственно, диапазон взаимодействия агентов равен 63 ячейкам (согласно данным табл. 1).

Результаты оценки производительности (ускорения и эффективности) приведены на рис. 3 и 4.

 

Рис. 3. Ускорение параллельной версии агентной модели в зависимости от размера пространства и числа используемых ядер

 

Рис. 4. Эффективность параллельной версии агентной модели в зависимости от размера пространства и числа используемых ядер

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

Что касается размера пространства, то его увеличение снижает показатели эффективности и ускорения для всех расчетов. Разберемся в причинах.

Предположим, что все взаимодействия, произошедшие во время одной итерации, оказались успешными. Тогда количество агентов будет хорошим показателем успешных взаимодействий и напрямую связан с общим объемом вычислений. Следуя сделанному предположению, будем использовать показатели пространства 1 000×1 000 (эталонного пространства) для нормализации результатов, полученных с пространств других размерностей. Отношения количества взаимодействий других пространств к взаимодействиям на эталонном пространстве показывают относительные объемы вычислений для каждой симуляции (таблица 4). Время расчетов последовательной версии модели (с использованием 1 ядра, табл. 3) с эталонным пространством используется для вычисления отношений времени расчетов модели с пространствами более крупных размеров (таблица 4). Было выявлено, что вычисленные отношения не находятся в абсолютно линейной зависимости. Незначительное расхождение нарастает по мере увеличения размера пространства, что противоречит изначальному ожиданию о линейной зависимости.

Таблица 3

Время (в секундах), требующееся для вычислений последовательных и параллельных версий модели с различными размерами пространства и количеством используемых ядер

Размер пространства	1 ядро	2 ядра	4 ядра	8 ядер	16 ядер	32 ядра
1 000×1 000	242.95	144.93	73.62	37.35	19.20	10.02
2 000×2 000	988.51	588.60	300.94	153.84	79.77	42.96
3 000×3 000	2226.45	1352.53	687.56	353.53	185.28	102.27
4 000×4 000	4014.37	2412.23	1242.43	641.84	337.13	200.79
5 000×5 000	6410.12	3843.12	1966.36	1023.43	545.54	321.80

Таблица 4

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

Размер пространства	Количество агентов	Отношение количества взаимодействий к эталонному	Отношение времени вычислений к эталонному
1 000×1 000	1 000 000	1	1
2 000×2 000	4 000 000	4	4.07
3 000×3 000	9 000 000	9	9.16
4 000×4 000	16 000 000	16	16.52
5 000×5 000	25 000 000	25	26.38

Следует отметить, что такое ожидание основано на ранее сделанном предположении об успешности всех взаимодействий. На самом деле это не так, поскольку их успех зависит от используемого в модели порога возможности восприятия стороннего мнения. Таким образом, причина нелинейности заключается в изменении доли успешных взаимодействий. На рис. 5 показана доля неудачных взаимодействий первых 100 итераций симуляции модели для пяти пространств различной размерности. Отметим, что общая тенденция заключается в резком снижении доли неудачных взаимодействий и ее последующей стабилизации.

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

 

Рис. 5. Доля неудачных взаимодействий для первых 100 итераций выполнения последовательной версии модели для пространств различной размерности

Вторая серия экспериментов. Оценка влияния радиуса взаимодействия

Во второй серии экспериментов оценивалось влияние длины радиуса взаимодействия для агентов модели на производительность и масштабируемость приложения. При расчетах менялись значения коэффициента α, влияющего на вероятность выбора соседствующего агента для взаимодействия, от 0.1 до 1.5 с шагом 0.2, а размер пространства для всех симуляций был одинаков (4 000 × 4 000).

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

 

Рис. 6. Ускорение параллельной версии агентной модели в зависимости от радиуса взаимодействия и числа используемых ядер

 

Рис. 7. Эффективность параллельной версии агентной модели в зависимости от радиуса взаимодействия и числа используемых ядер

В таблице 5 приведены результаты расчетов последовательных и параллельных версий модели в зависимости от радиуса взаимодействия агентов и количества используемых ядер. Время вычислений в результате увеличения радиуса также возрастает. На рис. 8. показана доля неудачных взаимодействий первых 100 итераций симуляции последовательной версии модели для значений радиуса взаимодействия агентов из таблицы 5. Кривые демонстрируют, что в симуляциях с более длинными радиусами, стабилизация на низком уровне неудачных взаимодействий достигается гораздо быстрее, чем при коротких радиусах, что вполне естественно.

Таблица 5

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

Coefficient α	1 ядро	2 ядра	4 ядра	8 ядер	16 ядер	32 ядра
0.1	3800.46	2222.69	1130.57	572.03	289.91	149.57
0.3	3837.61	2266.97	1151.68	585.86	298.20	156.64
0.5	3904.54	2300.79	1180.65	601.56	310.09	167.21
0.7	3940.03	2367.83	1206.35	624.11	325.28	181.28
0.9	4014.37	2412.23	1242.43	641.84	337.13	200.79
1.1	4121.25	2480.49	1292.39	665.97	357.64	206.13
1.3	4194.87	2570.83	1325.84	690.59	374.76	219.56
1.5	4270.63	2635.24	1366.83	709.61	386.62	229.62

Рис. 8. Доля неудачных взаимодействий для первых 100 итераций выполнения последовательной версии модели в зависимости от радиуса взаимодействия

На рис. 9 приведен уровень неудачных взаимодействий для последовательной модели с фиксированным размером пространства в зависимости от радиуса взаимодействия. Таким образом, увеличенный радиус взаимодействия открывает больше возможностей для взаимодействия агентов, поиска единомышленников и, как следствие, приводит к более интенсивному обмену мнениями, а, в конечном счете – требует большего времени для вычислений.

Рис. 9. Стабилизационный уровень неудачных взаимодействий для последовательной модели в зависимости от радиуса взаимодействия

Что касается параллельных версий модели, то возрастание количества межпотоковых взаимодействий по мере увеличения числа используемых ядер объясняет снижение эффективности приложения (рис. 7). Это также вполне ожидаемо, поскольку расширяя радиус взаимодействия агентов, мы тем самым увеличиваем вероятность контакта текущего агента с агентами, находящимися в других частях пространства, что приводит к увеличению межпотоковых коммуникаций. Видно, что когда радиус взаимодействия минимальный (0.1, что соответствует 2 клеткам), использование 32 ядер не так сильно снижает эффективность, как при максимальном радиусе (при том же числе ядер).

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

Более подробно: [Gong Z., Tang W., Bennett D.A., and Thill J.C. (2013): Parallel agent-based simulation of individual-level spatial interactions within a multi-core computing environment. International Journal of Geographical Information Science, 27 (6): 1152-1170.]