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

В работе исследователей из университета Виго (Universidad de Vigo, Испания) и университета Минью (Universidade do Minho, Португалия) рассматривается последовательный и параллельный алгоритмы применительно к трехмерному моделированию отдельных молекул в сложных структурах с использованием агентного подхода. Разработанные подходы позволяют определять расположение молекул с достаточно высокой точностью и, таким образом, выявлять возможные критические состояния изучаемых объектов. Кроме этого, эти подходы реализованы в рамках кроссплатформенного приложения, что обеспечивает возможность построения трехмерных моделей на любой аппаратной платформе и операционной системе. По результатам расчетов, в том числе было выявлено, что параллельные версии моделей демонстрируют высокую производительность при работе с большим числом агентов, а последовательные – для малых и средних групп.

Разработчики отдельно отмечают, что обозначенные подходы могут быть использованы при построении агент-ориентированных моделей для исследования других предметных областей (в частности, социальных и экономических систем).

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

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

Таким образом, в программной среде были формализованы основные законы биохимии и биофизики, к примеру, молекулярная диффузия и столкновение молекул (рис. 1). Иными словами, логика поведения агентов модели хорошо согласуется с известными молекулярными взаимодействиями. Так, правила ферментативной реакции в терминах модели подразумевают, что агент, представляющий фермент (E), взаимодействует с агентом, представляющим субстрат (S) каждый раз, когда S находится вблизи E. В результате каталитической реакции образуется фермент-субстратный комплекс, который затем распадается и при этом уничтожается агент S и создается новый агент P – продукт реакции:

E + S ↔ ES → E + P                                                                             (1)

Отметим, что скорость ферментативной реакции зависит от ряда факторов – концентрации фермента и субстрата, температуры, а также наличия регуляторов, повышающих или понижающих активность ферментов. В модели, связывание фермента и субстрата, а также катализ управляются двумя соответствующими параметрами: K_m (определяет сродство E и S) и K_cat (ускоряет реакцию).

Рис. 1. Пример столкновения двух различных молекул: фермента (A) и субстрата (B). Переменные V_1A и V_1B – вектора скоростей каждой молекулы до столкновения, а V_2A и V_2B – вектора скоростей после столкновения. q – угол между нормальным и фактическим вектором скорости каждого агента

Далее мы рассмотрим разработанные авторами подходы (1.1 – последовательный, 1.2 – параллельный, 1.3 – подход, основанный на разбиении пространства).

1.1. Последовательный (однопоточный) подход

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

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

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

В модели предусмотрено три типа событий: (1) реакции, включающие в себя связывание, уничтожение и создание новых агентов; (2) отскоки, происходящие после столкновения агентов; и (3) движение, являющееся событием по умолчанию, срабатывающим в том случае, если не произошли другие события и при этом новое местоположение агента свободно.

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

Рис. 2. Однопоточная симуляция агентной модели с использованием разработанной программной среды

1.2. Параллельный подход

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

Во время симуляции контроллер управляет общим списком агентов и обеспечивает корректную обработку агентов потоками. Двухшаговый алгоритм работы потока приведен в листинге 1. На первом шаге поток выбирает одного агента из общего списка и для него вычисляются координаты нового местоположения с использованием информации о направлении его движения и скорости диффузии (строка 3). Помимо этого, происходит проверка о возможном срабатывании того или иного события (строка 4). Выше уже говорились, что в модели предусмотрено три типа событий: (1) ферментативная реакция, в процессе которой агент-фермент и соответствующий ему агент-субстрат находятся в достаточной близости, затем вступают в реакцию и, как результат, субстрат уничтожается и создается новый продукт; (2) происходит столкновение агентов, в результате которого агенты отскакивают друг от друга и направления их движения пересчитывается; (3) новое целевое местоположение агентов свободно, остальные события не произошли и агент продолжает движение.

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

При наступлении какого-либо из перечисленных событий происходит следующее: (1) в случае реакции создается новый продукт, который появится в модели на следующей итерации; (2) в случае отскока происходит пересчет направлений движения, но само движение произойдет на следующей итерации; (3) в последнем случае происходит расчет нового местоположения, но само движение также произойдет на следующей итерации.

1.      Перечисляем агентов из общего списка
2.                Выбираем нужного агента
3.                Оцениваем его новое местоположение
4.                Оцениваем результаты от срабатывания событий
5.      Ожидаем значения от других агентов (синхронизация)
6.      Перечисляем агентов из общего списка
7.                Выбираем нужного агента
8.                Выполняем надлежащие действия

Листинг 1. Псевдокод, показывающий список действий для каждого потока, выполняемых в параллельном режиме

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

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

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

Рис. 4. Примеры возможных ситуаций при синхронизации, осуществляемой в рамках параллельного подхода. В данном примере используются 5 агентов и два временных интервала

На рис. 4 приведены примеры синхронизации потоков. В момент времени t (левая часть рисунка) поток 1 блокирует агента 1 (желтого цвета), а поток 2 агента 2 (оранжевого цвета). Когда агент 1 проверяет пространство в доступном ему диапазоне, он обнаруживает, что агент 2 находится в зоне его влияния, и тоже самое обнаруживает агент 2 относительно агента 1. Таким образом, два потока будут претендовать на двух агентов. В рассматриваемом примере конфликтная ситуация разрешается тем, что поток 2 освобождает агента 2, а затем выбирает другого агента из общего списка агентов (конкретно, агента 3 синего цвета). Похожая конфликтная ситуация наблюдается для агентов 4 и 5 (красного и зеленого цветов соответственно). В момент времени t + 1 (правая часть рисунка) видно, что все агенты-молекулы успешно выполнили свои действия: перемещение (для агентов 1, 2 и 3) и отскок (для агентов 4 и 5).

1.3. Подход, основанный на разбиении пространства

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

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

Рис. 5. Симуляция агентной модели в разработанной программной среде с использованием подхода, основанного на разбиении пространства

Агенты, относящиеся к подпространству, обрабатываются почти в автономном режиме (листинг 2). Исключения составляют агенты, расположенные в пограничных областях (переходящие агенты), проверяющие там агентов-соседей и, как следствие, требующие синхронизацию. Таким образом, каждый агент оценивает свое новое местоположение, и если он выходит за пределы подпространства, то помещается в список переходящих агентов. В противном случае агент оценивает результаты от срабатывания событий (строки 3-8).

1.      Перечисляем агентов из списка, относящегося к подпространству
2.                Выбираем нужного агента
3.                Оцениваем его новое местоположение
4.                IF агент переходит за пределы подпространства THEN
5.                     Помещаем агента в список переходящих агентов
6.                ELSE
7.                     Оцениваем результаты от срабатывания событий
8.                ENDIF
9.      Ожидаем значения от других агентов (синхронизация)
10.      Перечисляем агентов из списка переходящих агентов
11.                Выбираем нужного агента
12.                Оцениваем результаты от срабатывания событий
13.      Ожидаем значения от других агентов (синхронизация)
14.      Перечисляем агентов из списка, относящегося к подпространству
15.                Выбираем нужного агента
16.                Выполняем надлежащие действия

Листинг 2. Псевдокод, показывающий список действий для каждого потока, выполняемых в течение временного шага в рамках подхода, основанного на разбиении пространства

Синхронизация необходима для гарантии того, что все агенты проведут проверку о возможном срабатывании того или иного события, прежде чем симуляция продолжится (строки 9 и 13). Как и в предыдущем случае, в рассматриваемом подходе также реализован механизм блокировки агентов и повышения приоритетов потоков (строки 10-12). Таким образом, алгоритм предотвращает конфликтные ситуации, а все агенты выполнят надлежащие действия (строки 14-16).

На рис. 6 показаны различные варианты переходов агентов в четырех подпространствах, каждое из которых обрабатывается отдельным потоком (т.е. T1, T2, T3 и T4). В момент времени t (левая часть рисунка) в соответствующих подпространствах будут рассчитываться последствия какого-либо события (реакция, отскок или движение) для агентов серого цвета, поскольку они не находятся в пограничной области (пунктирная светло-серая линия). В то же время, в подпространствах T1 и T2 имеются агенты в пограничных областях (агент 1 желтого цвета в T1 и агенты 2 и 3 оранжевого и голубого цветов в T2). Как уже говорились, все находящиеся в пограничных областях агенты обрабатываются с использованием механизма повышения приоритетов потоков, а код агентов серого цвета выполняются автономно, в рамках соответствующих подпространств.

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

В момент времени t + 1 (правая часть рисунка) агенты выполняют запланированные события, но самое главное – некоторые из агентов переходят из одного подпространства в другое. Агент 1 (желтого цвета) остается в пограничной области и, соответственно, в следующий момент времени должен снова проверять соседей в подпространствах 1 и 3. В свою очередь два серых агента отскакивают от верхней и правой границ своих подпространств (в T2 и T4 соответственно).

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

2. Результаты расчетов

Для сравнения предлагаемых выше подходов разработчики проводили симуляции ферментативной реакции 2-гидроксимуконата таутомераза (2-hydroxymuconate tautomerase (код фермента, присвоенный комиссией по ферментам EC 5.3.2.6)). Объем моделируемого пространства составлял 0.48 μm³.

В таблице 1 приведены характеристики используемых в расчетах молекул (масса и радиус), их скорость движения (скорость диффузии) и количество (концентрация). У фермента есть дополнительные параметры K_m и K_cat.

С использованием различных вариантов начальных концентраций субстрата, посредством симуляций можно определить, соответствует ли рассчитанная скорость получения продукта теоретическим значениям. На рис. 7 показан процесс симуляции и два графика, сравнивающих полученные результаты с теоретическими значениями. Как видно (рис. 7a), в процессе симуляции участвуют ферменты (желтого цвета), субстраты (зеленого цвета) и продукты реакции (оранжевого цвета). Графики типа «ящик с усами» (box-and-whiskers plot) на рис. 7b показывают значения, полученные с использованием уравнения Михаэлиса-Ментена, рассчитанные с использованием трех подходов и теоретических значений. Для второго и третьего подходов было проведено 20 прогонов модели, после чего были вычислены средние значения и отклонения. Дополнительно, для большего удобства восприятия результатов, исследователи построили график Лайнвивера-Берка (или график двойных обратных величин), показанный на рис. 7c.

Таблица 1

Описание биомолекулярной модели, используемой для расчетов

 2.1. Создание агентов

При создании агентов, наиболее ресурсоемкими вычислениями являются расчеты их начального местоположения. В этой связи, разработчики тестировали производительность симуляции для рассмотренных выше трех подходов во время процедуры создания агентов (во время тестирования число агентов увеличивалось от 0 до 100 000). На рис. 8 видно, что последовательный подход по сравнению с двумя другими более эффективен для малых и средних групп агентов (не более 25 000).

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

2.2. Программная реализация агентов

Далее рассмотрим эффективность подходов в процессе программной реализации кода агентов (симуляции молекулярной диффузии). В ходе экспериментов увеличивалась популяция агентов (от 0 до 100 000), а отслеживалось количество шагов симуляции в секунду. На рис. 9 видно, что производительность последовательного подхода с увеличением числа агентов резко снижается, а параллельные версии второго и третьего подхода ее заметно превосходят (их средний прирост производительности по сравнению с последовательной версией составляет 121% и 189% соответственно).

Рис. 7. Данные, полученные при симуляции биомолекулярной модели, рассматривающей ферментативную реакцию 2-гидроксимуконата таутомераза: (a) процесс симуляции; (b) графики, показывающие средние значения результатов симуляции для трех подходов, построенные с использованием уравнения Михаэлиса – Ментен (Michaelis-Menten), описывающего зависимость скорости реакции, катализируемой ферментом от концентрации субстрата; (c) график Лайнвивера-Берка (график обратных величин уравнения Михаэлиса-Ментена)

Рис. 8. Производительность симуляции во время выполнения процедуры создания агентов

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

2.3. Влияние количества потоков на эффективность предлагаемых подходов

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

Рис. 10. Производительность симуляции в зависимости от количества потоков

2.4. Влияние размерности пространства на эффективность предлагаемых подходов

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

Рис. 11. Влияние размерности пространства на эффективность предлагаемых подходов

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

Более подробно о проведенном исследовании можно прочитать здесь: [Pérez-Rodríguez G., Pérez-Pérez M., Fdez-Riverola F., Lourenço A. (2016): High performance computing for three-dimensional agent-based molecular models // Journal of Molecular Graphics and Modelling, Volume 68, 2016, Pages 68-77].