Ученые из Центра прикладной геоинформатики (The Center for Applied Geographic Information Science (CAGIS)) университета Северной Каролины в Шарлотт (University of North Carolina at Charlotte, USA), отмечая актуальность разработки агент-ориентированных моделей, построенных на базе геоинформационных систем с целью более адекватного представления действительности, предложили свой подход к распараллеливанию агентных моделей.

Для апробирования методологии была построена агент-ориентированная модель обмена мнениями (agent-based model of opinion exchange), имитирующая пространственную диффузию мнений на уровне отдельных индивидуумов, с упором на взаимодействие между агентами. Агенты в модели расположены в определенной части пространства и общаются между собой для накопления информации и, в конечном счете, создания новых знаний. Пространство представляет собой двухмерную решетку, где каждая ячейка ассоциирована с конкретным агентом. Процесс общения между агентами включает в себя два шага: на первом шаге идентифицируется агент-сосед, находящийся в пределах доступного и определенного ранее пространства, а на втором собственно происходит обмен мнениями.

Предлагаемый подход заключается в разработке крупноблочного механизма использования разделяемой памяти (coarse-grained shared memory mechanism) для лучшего использования многоядерной архитектуры. Авторы акцентируют внимание на двух важных механизмах распараллеливания, используемых для реализации агентной модели: метод декомпозиции областей (domain decomposition) и взаимное исключение (mutual exclusion (mutex) или мьютекс). Области пространства делятся между узлами суперкомпьютера таким образом, чтобы минимизировать объем пересылаемых между агентами сообщений, обслуживаемых разными процессами. Во время параллельной обработки данных механизм мьютекса обеспечивает исключение одновременного использования потоками общего ресурса, особенно в ситуации, когда агенты модели взаимодействуют с агентами из частей пространства, обрабатываемыми другими процессами.

Техническая реализация

Поиск соседа в рамках доступного пространства

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

                                                                                  (1)

где d_i,j – расстояние между двумя агентами, а α – коэффициент, влияющий на вероятность выбора соседствующего агента.

В модели рассматриваются только те клетки пространства, в которых вероятность быть обнаруженным агентами модели превышает задаваемый пользователем порог pthresh (к примеру, p_thresh = 0.01). На основе уравнения (1) горизонт видимости агента определяется следующим образом

                                                                               (2)

Моделирование процесса обмена мнениями

Отметим, что моделирование данного процесса предполагает моделирование межагентного взаимодействия. Мнение отдельного агента задается числом в интервале [0, 1]. Также каждый агент имеет два параметра, определяющие его поведение в процессе обмена мнениями: 1) «порог» мнения; 2) коэффициент обмена.

В том случае, если мнения агентов не превышают порог отдельного агента, то мнение этого агента будет обновлено следующим образом:

O(i, t) = O(i, t – 1) – u_i·σ_i                                                                            (3)

σ_i = O(i, t – 1) – O(j, t – 1)                                                                         (4)

где

O(i, t), O(i, t – 1) – мнение агента i в момент времени t и t – 1;

O(j, t – 1) – мнение агента j в момент времени t – 1;

u_i – коэффициент обмена мнением для агента i;

σ_i – разница во мнениях у двух агентов по отношению к агенту i.

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

Реализация агент-ориентированной модели.

Разработанная модель была реализована с использованием технологии OpenMP. Для эксперимента был выбран размер решетки 1 000×1 000, т.е. число агентов в модели равно 1 000 000 и при этом, на каждом итерации агент должен завершить обмен мнениями с другим агентом, по крайней мере, один раз.

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

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

Рис. 1. Структура агентной модели

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

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