Полномасштабная распределенная агент-ориентированная модель эпидемий

23.05.2013

В ходе исследования, включающего в себя реализацию нескольких научно-исследовательских проектов, была разработана агент-ориентированная модель для оценки последствий распространения эпидемий различного характера. В силу последнего свойства она является универсальной по отношению к другим эпидемиологическим моделям. Кроме того, она ориентирована на поддержку двух сред для вычислений: одна среда состоит из кластеров с установленной 64-битной версией Linux, а другая — из серверов с четырехъядерными процессорами и установленной системой Windows (в этой связи в качестве языка программирования был выбран Java, хотя разработчики и не уточняют, какую именно реализацию Java они использовали). Также отметим, что по утверждениям ученых, модель способна поддерживать численность агентов от нескольких сотен миллионов до 6 млрд.

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

Общая схема модели

Авторы исследования отмечают, что модель была реализована на JAVA в первую очередь для поддержки кросс-платформенной компиляции, а также за счет поддержки автоматизированной сериализации и возможности вызова удаленных методов (Remote Method Invocation (RMI)).

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

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

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

Детали синхронизации

В этом пункте более детально рассматриваются вопросы обработки, ожидания и обмена сообщениями между потоками. Итак, для обработки потоков существует определенная очередь с приоритетом (Priority Queuing (PQ)), обеспечивающая приоритет одних потоков над другими. PQ должна поддерживать возможность эффективного удаления случайно выбранной записи в очереди. Как правило, для этого используется операция O(n), поскольку большинство PQ имеет дело либо с кучей, либо с массивом. Для реализации удаления записи из очереди, разработчики добавили метод «removeFirst(key)» к классу java.util.TreeMap, в рамках которого реализуется алгоритм красно-черного дерева. Объединение remove(key) и firstKey() в один метод позволяет значительно увеличить производительность приложения.

В один момент каждый поток на узле останавливается для того, чтобы узел был готов связаться с утилитой – «менеджером сообщений» с тем, чтобы упорядочить события, требующие связи с агентами, выполняющимися на другом узле. В то же время, требующие исполнения другие события, которые не могут выполниться в данный момент из-за приостановки отдельного узла, помещаются в очередь для последующего выполнения. Записи о невыполненных событиях хранятся в накопителе OffNodeContactEvents (ONCE).

Вообще говоря, процесс откладывания выполнения некоторых событий на «потом» может повлечь серьезные проблемы. Вот пример одной из них. Пусть ONCE содержит запись о том, что контакт между двумя агентами должен произойти в момент времени 172. Тем не менее, в процессе работы модели контакт произошел в момент времени 200. Как это может повлиять на работу модели? Разработчики модели указывают, что все зависит от инкубационного периода симулируемой болезни. Если агент был заражен в момент времени x, но при этом не изменил свое поведение и не заражал других агентов в течение следующего времени y, то запись об инфицировании агента не будет отправляться до момента времени (x + y). Максимальное время между периодами для обмена сообщениями между процессами зависит от длительности инкубационного периода. При установлении связи происходит срабатывание двух программных инструкций. Первая из них проверяет, что любой только что зараженный агент был заражен одновременно с созданием ONCE, а не после того как записи из ONCE были исполнены. Вторая инструкция корректирует время заражения инфекцией. К примеру, если в процессе выполнения модели заражение агента произошло в момент времени 188, а согласно записям ONCE должно было произойти в момент 172, то инструкция корректирует соответствующую запись. Такая поправка требует осуществления поиска в PQ специального события, которое зафиксирует начало периода инфекции у агента. Если PQ работает с кучей или массивом, то данная операция поиска может существенно повлиять на производительность всего приложения.

Распределение агентов между аппаратными ресурсами

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

При распределении агентов по аппаратным ресурсам следует учитывать два обстоятельства: 1) производительность узла напрямую зависит от количества инфицированных агентов; 2) контакты, предполагающие передачу сообщений между потоками требуют гораздо больше вычислительных затрат, нежели контакты, ограничивающиеся локальной информацией. Исходя из этого, возможно различное распределение агентов. С одной стороны, можно поделить все рассматриваемое географическое пространство на равные части, количество которых должно соответствовать числу узлов, а затем определить для каждого узла какой-либо географический регион. За счет этого возможна балансировка вычислительной нагрузки между узлами. С другой стороны, возможно закрепить определенную территорию, представляющую собой единую административную единицу, за конкретным узлом. Это может способствовать снижению вычислительной нагрузки за счет снижения числа контактов, требующих передачу сообщений между потоками. Первый способ влечет за собой увеличение вычислительной нагрузки за счет ресурсоемких контактов, но второй способ в ряде случаев несет в себе потенциальную опасность значительного дисбаланса между аппаратными ресурсами. К примеру, в случае вспышки какого-либо заболевания в одном из регионов загрузит один из вычислительных узлов, в то время как некоторые другие будут простаивать.

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

Используя результаты экспериментов различных запусков модели в качестве ориентира, исследователи приступили к разработке стратегии оптимизации распределения агентов по узлам, способ которой зависит от используемых аппаратных ресурсов. К примеру, если модель запускается на 2 узлах, каждый из которых представлен четырехъядерным процессором, то совокупность агентов делится на 8 групп. Т.е. сначала происходит деление на 2 группы (по одной на узел), а затем каждая группа делится на 4 подгруппы.

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

При инициализации модели необходимо вычислить некоторые данные. Для каждого пикселя составляется список агентов, составляющих его население. Далее рассчитывается матрица A размерности n × n, где каждый элемент Aij представляет собой количество контактов между агентов, проживающих в пикселе i и агентов из пикселя j.

Сначала каждому пикселю случайно присваивается один из возможных цветов g, где g – число групп агентов, на которое распределено все население. После этого создается двумерный массив, размерностью «количество пикселей» на «количество групп». Каждый элемент массива содержит информацию о том, как часто пиксель i взаимодействует со всеми пикселями цветовой группы j.

Этот массив вычисляется непосредственно из значений матрицы A, а его постоянная актуализация позволяет существенно повысить производительность модели.

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

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

Процедуры оптимизации алгоритма позволяют уменьшить время, необходимое для удовлетворительного распределения агентов. На скорость работы оптимизационных процедур влияют два фактора – размерность матрицы A и количество групп g.

Исследователи не утверждают, что разработанный алгоритм позволяет свести к минимуму межгрупповые контакты. Более правильным будет сказать, что алгоритм минимизирует межгрупповые взаимодействия, по крайней мере, на 10 процентов.

Приведем теперь результаты оптимизации распределения агентов между двумя узлами, каждый из которых содержит восемь потоков. На рис. 1 показано распределение агентов по двум узлам, а на рис. 2 показано, как каждый узел распределяет агентов по 8 потокам. Пиксели одинакового цвета, разделенные красной линией, между собой не связаны.

Рис. 1. Условно-оптимальное распределение агентов между двумя узлами

Рис. 2. То же самое распределение, как и на рис. 1, но еще и с учетом распределения агентов по 8 потокам

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

Тем не менее, производительность модели с использованием алгоритма возросла. Для сравнения его эффективности были проведены 3 различные симуляции, имитирующие 300-дневную имитацию распространения болезни, особенности которой заключаются в 96-часовом периоде инкубации и 48-часовом периоде заражения. Различия между симуляциями и соответствующие результаты приведены в табл. 1. Один из результатов исследования заключался в том, что распространение заболевания идет на спад после того как 65% людей выздоровели и приобрели иммунитет.

Таблица 1

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

	Затраченное время (ВСЕГО), в мин.	Доля времени, затрачиваемое общение между агентами	Частота общения
Запуск № 1	131,68	14%	каждые 12 часов
Запуск № 2	119,32	15%	каждые 48 часов
Запуск модели без использования оптимизационного алгоритма	161,91	24%	каждые 12 часов

Более подробно про модель можно прочитать в статье: [Parker Jon (2007): A Flexible, Large-Scale, Distributed Agent Based Epidemic Model. Center on Social and Economic Dynamics, Working Paper No. 52.].

rss

Партнеры

Статьи