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

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

japan1.jpg
Рис. 1. Структура типовой агентной модели, тестируемой в ходе исследования

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

japan2.jpg
Рис. 2. Приблизительное время расчетов простой агентной модели в зависимости от количества используемых узлов

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

Оптимизация затрат на передачу данных

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

Пусть: 
A – набор агентов;
C – набор узлов;
jf1.png – подмножество агентов которые принадлежат узлу jf2.png;
jf3.png – количество передач между агентом jf4.png и узлом jf2.png.

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

1. Записываем jf5.png для jf6.png и jf7.png 

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

jf9.png, (1) 

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

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

jf13.png. (2)

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

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

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

jf21.png. (3)

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

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

Для каждого узла данные действия выполняются непрерывно, а объем данных передаваемых между узлами постепенно уменьшается.

Поведение внутри алгоритма

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

1. Простая модель

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

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

japan4.jpg
Рис. 4. Объем передаваемых между двумя узлами данных в простой агентной модели

2. Агентная модель мульти-обмена

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

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

japan6.jpg
Рис. 6. Объем передаваемых между двумя узлами данных в агентной модели мульти-обмена

3. Агентная модель с использованием нескольких узлов

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

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

japan8.jpg
Рис. 8. Объем передаваемых данных в агентной модели с использованием нескольких узлов

4. Модель со случайным блужданием агентов

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

На рис. 9 отображен статус агентов, а на рис. 10 показан объем передаваемых между узлами данных. Как видно, количество передаваемых данных, в конечном счете, остается низким, несмотря на передвижения агентов.

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

japan10.jpg
Рис. 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 без его применения. Таким образом, алгоритм демонстрирует эффективность и для агентных моделей, использующих графы.

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

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

japan13.jpg
Рис. 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
Назад

Статьи
Суперкомпьютерные технологии Транспортные модели пешеходная модель Монография Биомедицина Parallel computing Параллельные вычисления Repast Агент-ориентированные модели Исследования Модель экономики Евросоюза Пространственно-распределенные агентные модели большие данные Axum Russian Supercomputing Days Агент-ориентированный подход Исторические процессы Мониторинг планеты Пространственные модели CUDA SEGMEnT БРИКС Контакты Публикации Экономические процессы FuturICT SSC Междисциплинарное исследование Новости Революция Эксафлопная производительность GPU SWAGES Высокопроизводительные вычисления Методология запуска О проекте Социальная сеть Эпидемия HPABM Social Simulation Conference ГИС Механизм раделяемой памяти Пандемия Ссылки Ядерная атака на США Microsoft POLARIS TSUBAME Демография Моделирование мира Пандора Стратегии распараллеливания автоматическое распараллеливание XAXIS Иерархическая платформа Моделирование эпидемий Суперкомпьютерная Академия агентная модель