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

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

По заверениям разработчиков, EpiFast, за счет применяемых эффективных алгоритмов распараллеливания, работает на порядок быстрее аналогичных программ. К примеру, имитация социальной активности (в течение 180 дней) жителей Большого Лос-Анджелеса (агломерации с населением свыше 16 млн. человек) с 900 млн. связей между людьми на кластере с 224 двухъядерными процессорами POWER5 заняла менее 15 минут. Такая высокая производительность связана с механизмом распараллеливания, предложенного авторами.

1. Концептуальное описание модели

В рамках модели рассматриваются:

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

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

3. меры по борьбе с болезнью.

1.1. Контакты

Контакты между людьми образуют сеть, которая называется социальная сеть контактов, определяемая как G (V, E, w) – направленный граф с взвешенными ребрами. Узлы графа – это люди, ребра – осуществляемые в течение дня контакты, а веса – их продолжительность. Ребро (u, v) с весом w(u, v) означает, что узел (человек) u контактирует с узлом v с продолжительностью w(u, v) и во время взаимодействия возможно заражение с вероятностью p(w(u, v)). В большинстве случаев ребра являются двунаправленными с одинаковыми весами для каждого направления. По предположению разработчиков, сама сеть контактов  во все периоды работы модели t не меняется, но может изменяться при проигрывании различных сценариев карантина для оценки последствий эпидемии.

1.2. Агенты

Каждый агент может находиться в одном из четырех состояний SEIR (S – восприимчивый к болезни (susceptible), E – инкубационный период (exposed), I – инфекционная болезнь (infectious), R – вылечившийся (recovered)). Обозначим θ(v, t) состояние здоровья агента v в момент времени t. Инкубационный период для агента v – , а период болезни – .

Состояние θ(v) агента v в процессе всей эпидемии может быть эквивалентно представлено посредством следующего набора переходов , где  – день, когда для агента наступил инкубационный период,  – день, когда агент заболел, а  – день, когда агент выздоровел. При этом периоды  и  для каждого агента предполагаются известными до начала симуляции. Состояния SEIR приведены на рис. 1. Как видно, переход между состояниями является односторонним и только в виде единственной возможной последовательности.

Рис. 1. SEIR состояния агентов

Внутри социума инфекция распространяется от уже инфицированного к восприимчивому к болезни агенту модели. В любой из дней, если узел u инфицирован, а узел v восприимчив, то болезнь может быть передана с вероятностью , где r – вероятность передачи инфекции в единицу времени во время контакта.

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

Предположим, что для каждого узла  и , а вероятность передачи инфекции между инфицированным узлом (красного цвета) и восприимчивым узлом (зеленого цвета) равняется 0.5. Узел A становится инфицированным при инициализации модели и сразу заражает узел B, но в тоже время узел D не успевает от него заразиться. На следующий день оба узла A и B заражены, причем узел B еще и заражает C, а D заражается от узла A (хотя потенциально мог заразиться от узла B). Других восприимчивых к инфекции агентов больше нет, и рассматриваемый социум окончательно выздоравливает к окончанию четвертого дня.

Рис. 2. Пример распространения инфекции через простую социальную сеть

2. Алгоритм

Ниже приведена концептуальная версия алгоритма EpiFast, предполагающая последовательное исполнение.

---------------------------------------------------------------

Алгоритм EpiFast №1: последовательная версия

---------------------------------------------------------------

Вход: (G, Δτ, A, Λ), где G – социальная сеть, Δτ – продолжительность инкубационного и инфекционного периодов, A – совокупность мероприятий по борьбе с эпидемией, а Λ – набор начальных условий.

Выход: (τ, Π), где τ – количество переходов между состояниями здоровья агентов, а Π – количество агентов, заразивших других людей.

1. инициализация модели
2. for t = 0 to T do
3.         foreach v ∈ V do
4.        обновляется состояние здоровья агента в соответствии с τ(v)
5.        применяются меры по борьбе с эпидемией (A_t), в том числе обновление G
6.        foreach инфицированного узла u ∈ V do
7.                foreach контакта v узла u do
8.                        if v восприимчив к инфекции then
9.                                возможна передача инфекции от u к v с вероятностью p(w(u, v))
10.                        if передача инфекции от u к v произошла then
11.                                обновление τ(v) и π(v)
12. вывод (τ, Π)

---------------------------------------------------------------

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

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

На рис. 3 приведен пример разделения социальной сети из пяти узлов по двум процессорам. Предположим, что агент v отнесен к процессору γ. Тогда разработчики определяют процессор γ в качестве «владельца» агента v, который, в свою очередь, является «локальным» по отношению к γ. Вся информация об агенте v хранится на локальном для него процессоре. На рис. 3 видно, что узлы A и B отнесены к процессору 1, а узлы C, D и E к процессору 2. При этом число обслуживаемых процессорами связей одинаково и равно 7.

Рис. 3. Пример деления социальной сети по двум процессорам

На рис. 4 приведена схема неоптимизированного алгоритма распараллеливания рассматриваемой задачи. Последовательность операций при этом следующая: a) вычисление вероятностей передачи инфекции от локальных узлов; b) обновление τ(v) для локальных узлов; c) передача информации нелокальным процессорам; f) обновление τ(v) для получивших информацию процессоров.

Рис. 4. Схема неоптимизированного алгоритма EpiFast

Данный алгоритм продемонстрировал значительное ухудшение производительности по сравнению с последовательной версией.

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

На рис. 5 приведена схема оптимизированного алгоритма распараллеливания рассматриваемой задачи. Последовательность операций при этом следующая: a) на ведомых процессорах вычисляются вероятности передачи инфекции от локальных узлов; b) на ведомых процессорах происходит обновление τ(v) для локальных узлов; c) ведомые процессоры передают информацию нелокальным процессорам; d) ведущие процессоры проверяют владельцев полученных сообщений; e) ведущие процессоры пересылают информацию (u, v) владельцу v; f) ведомые процессоры обновляют τ(v).

Рис. 5. Схема оптимизированного алгоритма EpiFast

Используя схему оптимизированного алгоритма EpiFast, конвертируем алгоритм № 1 в параллельную версию.

---------------------------------------------------------------

Алгоритм EpiFast №2: параллельная версия

---------------------------------------------------------------

Вход/Выход: аналогичные алгоритму № 1.

1. разделение социальной сети
2. инициализация модели
3. for t = 0 to T do
4.         if процессор ведомый then
5.         foreach v do
6.               обновляется состояние здоровья агента в соответствии с τ(v)
7.               применяются меры по борьбе с эпидемией (A_t) и обновляется
8.               локальный раздел G для каждого узла
9.                  foreach локального инфицированного узла u do
10.                          foreach контакта v узла u do
11.                             (a): передача инфекции от u к v с вероятностью p(w(u, v))
12.                                    if передача инфекции от u к v произошла then
13.                                            if v является локальным к процессору then
14.                                           (b): обновление τ(v) и π(v)
15.                                            else
16.                                           (c): пересылка информации ведущему процессору о передачи инфекции от u к v
17.         if процессор ведущий then
18.               получение информации от ведомых процессоров
19.               (d): проверка отправителей информации
20.               (e): пересылка информации владельцам v
21.        if процессор ведомый then
22.               (f): обновление τ(v) и π(v)
23. вывод (τ, Π)

---------------------------------------------------------------

Алгоритм EpiFast реализован на C++ с использованием MPI.

3. Расчеты.

Первая серия расчетов заключалась в оценке производительности алгоритма, в зависимости от применения различных мер по борьбе с инфекцией. Для сценария без применения мер были использованы следующие настройки: 1) значения инкубационного и инфекционного периодов для каждого человека подбирались с тем, чтобы их средние значения составляли 1.9 и 4.1 суток соответственно; 2) для инициации эпидемии были выбраны случайные 20 человек; 3) эпидемия имеет показатель пораженности (attack rate) 42%, рассчитываемый как отношение людей, которые будут инфицированы к общему числу людей, находящихся в зоне риска.

Для базового сценария, разработчики дополнительно рассмотрели два сценария применения мер:

1. С использованием антивирусных препаратов. Сценарий следующий: с 20 по 39 дни с момента начала распространения вируса, 10% людей применяли препараты на протяжении 20 дней. Эти препараты способны на 87% снизить риск заражения, а если человек уже заражен, то сделать его на 80% безопаснее для окружающих.

2. С использованием ограничений на передвижение. Сценарий запускается в случае, если 0.1% людей уже заразились и предусматривает ограничение на лишние передвижения для 10% населения (т.е. разрешается передвижение только на работу и домой).

Ни рис. 6. приведено время расчетов для базового сценария и двух сценариев с применением описанных мер. Расчеты проводились для социальной сети Большого Лос-Анджелеса (более 16 млн. человек, около 900 млн. социальных связей) на 180 дней. Как видно, производительность алгоритма зависит от того, применяются ли в модели меры по борьбе с инфекцией. Тем не менее, EpiFast продемонстрировал очень высокую скорость – так, средняя скорость одной симуляции менее 15 минут.

Рис. 6.Среднее время компьютерных симуляций для трех модельных сценариев в зависимости от числа использованных процессоров (вычислено на основе 25 запусков для каждого случая)

Далее были проведены расчеты для других социальных сетей (Майами (2.09 млн. чел.), Бостон (4.15 млн. чел.) и Чикаго (9.05 млн. чел.)). На рис. 7 и 8 приведены результаты, полученные с теми же модельными настройками. Как видно, увеличение числа процессоров в 7 раз позволяет увеличить скорость вычислений в среднем до 4 раз, что говорит о хорошей масштабируемости.

Рис. 7.Среднее время компьютерных симуляций для четырех социальных сетей в зависимости от числа использованных процессоров (вычислено на основе 25 запусков для каждого случая)

Рис. 8.Зависимость скорости выполнения симуляций от числа использованных процессоров (вычислено на основе 25 запусков для каждого случая)

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

Более подробно про разработанный алгоритм можно прочитать в статье:

[Keith R. Bisset, Jiangzhuo Chen, Xizhou Feng, V.S. Anil Kumar, Madhav V. Marathe (2009): EpiFast: A Fast Algorithm for Large Scale Realistic Epidemic Simulations on Distributed Memory Systems / Department of Computer Science and Virginia Bioinformatics Institute Virginia Tech, Blacksburg, USA, 2009.]