20.05.2013
Ученые из Токийской исследовательской лаборатории компании IBM (Tokyo Research Laboratory, IBM Research) Т. Такахаси (Toshihiro Takahashi) и Х. Мидзута (Hideyuki Mizuta) построили крупномасштабную агентную модель и адаптировали ее для реализации на суперкомпьютере BlueGene от IBM, а затем, с учетом полученного опыта, разработали методологию запуска агент-ориентированных моделей на суперкомпьютерах.
На рис. 1 представлена структура типовой агентной модели, тестируемой авторами исследования. В ее рамках любой агент представлен набором переменных и функциями, определяющими его поведения. Каждый узел суперкомпьютера обрабатывает определенное множество агентов, и при этом каждый агент общается с агентами своего узла, используя общую память, а с агентами из других узлов посредством сокетов (программных интерфейсов, используемых для обмена данными между процессорами). Естественно, что между этими двумя способами коммуникации существует большая разница в скорости.

Рис. 1. Структура типовой агентной модели, тестируемой в ходе исследования
На рис. 2 приведены оценки временных затрат по запуску агентной модели на суперкомпьютере BlueGene. Один шаг вычислений для агента составляет 2 миллисекунды, а одна единица данных от агента составляет 1 байт за один временной промежуток. Ось абсцисс показывает количество задействованных узлов, а ось ординат – затраченное для вычислений время. Нижняя кривая показывает время для 100 000 агентов, а верхняя – для 3 000 000. В случае одного узла, информация, определяющая межагентное взаимодействие, передается только внутри самого узла. Соответственно, в случае двух узлов, информация передается также и между ними, и, как видно, реализация модели в этом случае наиболее ресурсоемка (даже по сравнению с одним узлом). Далее видно, что увеличение количества использованных узлов увеличивает производительность агентной модели.

Рис. 2. Приблизительное время расчетов простой агентной модели в зависимости от количества используемых узлов
Авторы предположили, что можно значительно уменьшить объем передаваемой между узлами информации, объединив агентов, которые наиболее часто общаются друг с другом.
Оптимизация затрат на передачу данных
Решаемая проблема заключается в минимизации количества передач между узлами. Предлагаемая учеными идея заключается в том, что каждый узел «наблюдает» сколько сообщений передает каждый из обслуживаемых им агентов в другие узлы и, основываясь на данной информации, производит обмен подмножествами агентов с другими узлами.
Пусть:
A – набор агентов;
C – набор узлов;





Тогда процедура для узла k выглядит следующим образом:
1. Записываем
для
и



2. Рассчитываем
для
и
следующим образом:




т.е.
представляет собой разницу количества передач между узлами, в том случае, когда агент i переместился от узла
к узлу
.



3. Рассчитываем
для
следующим образом:



4. Добавляем i к
для
, где
– набор агентов – кандидатов для перемещения в узел
.




5. Задаем
для
, где
– количество агентов, пересылаемых от узла
к узлу
. Начальное значение
по отношению к количеству агентов узлов
и
обычно невелико. В том случае, если число агентов – кандидатов для перемещения
меньше, чем это заданное число, мы устанавливаем
равным
.











6. Получив число
, далее рассчитываем
для
:




7. Перемещаем агентов
из числа агентов-кандидатов
от узла
к
.




8. Получаем агентов от узла
к
.


Для каждого узла данные действия выполняются непрерывно, а объем данных передаваемых между узлами постепенно уменьшается.
Поведение внутри алгоритма
В рамках алгоритма моделируется поведение некоторых типовых агентов, наиболее часто используемых в агентных моделях.
1. Простая модель
Первая экспериментальная модель обладала следующими характеристиками:
- число использованных узлов равно 2;
- 1 000 агентов, равномерно распределенных в двумерном пространстве размерностью [0,1) × [0,1);
- каждый агент может послать сообщения только агентам, находящимся на расстоянии 0.1;
- размер сообщения агента равно 1 байту;
- максимальное число перемещаемых агентов в единицу времени равно 1.
На рис. 3 отображен статус агентов, расположенных в двумерном пространстве. Как видно, в процессе работы модели агенты делятся по двум узлам. На рис. 4 показан объем передаваемых между двумя узлами данных, который сократился с 8997 до 1132 байт. В свою очередь объем данных, передаваемых внутри узла, увеличился с 8964 и 9034 до 15912 и 17816 байт соответственно. Для разделения агентов ушло около 220 шагов.

Рис. 3. Статус агентов в простой модели

Рис. 4. Объем передаваемых между двумя узлами данных в простой агентной модели
2. Агентная модель мульти-обмена
Вторая модель аналогична первой, но максимальное число перемещаемых агентов в единицу времени равно 5. На рис. 5 отображен статус агентов, а на рис. 6 показан объем передаваемых между двумя узлами данных, который уменьшился с 8997 до 1059 байт. На этот раз процесс занял 50 шагов, т.е. он протекал почти в 5 быстрее, чем предыдущий. Таким образом, процесс разделения может быть ускорен за счет увеличение количества перемещаемых агентов в единицу времени.

Рис. 5. Статус агентов в модели мульти-обмена

Рис. 6. Объем передаваемых между двумя узлами данных в агентной модели мульти-обмена
3. Агентная модель с использованием нескольких узлов
Третья модель отличается от предыдущих использованием четырех узлов вместо двух. На рис. 7 отображен статус агентов, а на рис. 8 показан объем передаваемых между узлами данных, который сократился с 2100 до 500 байтов. Как видно, результаты достаточно хорошие.

Рис. 7. Статус агентов в модели с использованием нескольких узлов

Рис. 8. Объем передаваемых данных в агентной модели с использованием нескольких узлов
4. Модель со случайным блужданием агентов
Четвертая модель почти такая же, как и агентная модель мульти-обмена (пункт 2), но здесь агенты на каждом шаге перемещаются на небольшое расстояние в случайном направлении. Кроме того, в процессе симуляций, агенты постепенно меняют своих коммуникационных партнеров.
На рис. 9 отображен статус агентов, а на рис. 10 показан объем передаваемых между узлами данных. Как видно, количество передаваемых данных, в конечном счете, остается низким, несмотря на передвижения агентов.

Рис. 9. Статус агентов в модели со случайным блужданием агентов

Рис. 10. Объем передаваемых данных в агентной модели со случайным блужданием агентов
Модель онлайн-аукциона
Пятая модель – модель онлайн-аукциона, в отличие от предыдущих, приближена к практике и основана на реальных данных. Ее описание приведено в работе [Mizuta, H., and K. Steiglitz. 2000. Agent-Based Simulation of Dynamic On-Line Auctions. Proceedings of the 2000 Winter Simulation Conference]. В рамках исследования она также была протестирована на суперкомпьютере с использованием описанного выше алгоритма. В модели агентами являются как участники торгов, так и сами аукционы. Кроме того, участники торгов могут участвовать одновременно в нескольких аукционах. Для расчетов модели использовалось 2 вычислительных узла.
На рис. 11 показан статус агентов, где прямоугольник это агент-аукцион, а овал – агент – участник торгов, каждый из которых соединен с агентом-аукционом ребром графа. Как видно, некоторые из агентов – участников торгов участвуют в одном аукционе, а некоторые в двух или более. Овал светлого цвета означает, что агент реализуется на первом узле, а агентам, реализуемым на втором узле, соответствует овал темного цвета. Следует отметить что агенты, участвующие в одном и том же аукционе, в конечном счете, обслуживаются одним и тем же узлом. На рис. 12 показан объем передаваемых данных в случае применения алгоритма, а на рис. 13 без его применения. Таким образом, алгоритм демонстрирует эффективность и для агентных моделей, использующих графы.

Рис. 11. Статус агентов в модели онлайн-аукционов

Рис. 12. Объем передаваемых данных в агентной модели онлайн-аукционов (с использованием разработанного алгоритма)

Рис. 13. Объем передаваемых данных в агентной модели онлайн-аукционов (без использования разработанного алгоритма)
Заключение
По результатам апробации можно отметить, что разработанный итерационный алгоритм, несмотря на свою простоту, эффективно снижает объем передаваемых данных и увеличивает производительность агентных моделей. По утверждениям авторов алгоритм является легко масштабируемым для разноразмерных задач, связанных с агентным моделированием.
Более подробно про разработанный алгоритм можно прочитать в статье: [Takahashi T., Mizuta H. (2006): Efficient Agent-Based Simulation Framework for Multi-Node Supercomputers. Proceedings of the 2006 Winter Simulation Conference, Monterey, CA].