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

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. Рассчитываем

для

следующим образом:

, (1)

т.е.

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

к узлу

3. Рассчитываем

для

следующим образом:

. (2)

4. Добавляем i к

для

, где

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

5. Задаем

для

, где

– количество агентов, пересылаемых от узла

к узлу

. Начальное значение

по отношению к количеству агентов узлов

обычно невелико. В том случае, если число агентов – кандидатов для перемещения

меньше, чем это заданное число, мы устанавливаем

равным

6. Получив число

, далее рассчитываем

для

. (3)

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].

rss

Партнеры

Статьи