Процессы, для моделирования которых был разработан этот алгоритм, отличаются высокой сложностью и постоянным взаимозависимым изменением структуры внутренних элементов. Помимо взрывов и разрушения хрупких материалов при падении или ударе, к таким процессам относятся, например, протекание жидкости через гранулы диоксида урана в активной зоне ядерного реактора или прохождение цунами сквозь прибрежный город. Чтобы понять, как будут развиваться события в этих ситуациях, необходимо использовать суперкомпьютеры. Но если загрузить такой задачей суперкомпьютер, не распределяя особым образом вычисления по его вычислительным узлам, даже самой высокой мощности будет недостаточно, чтобы закончить вычисления за разумное время.
"Если нагрузка распределяется неравномерно, и на какие-то узлы приходится мало вычислительной работы, они заканчивают счет быстрее и начинают ждать, пока посчитают более загруженные узлы. В итоге общее время расчета увеличивается из-за этого ожидания", – объясняет проблемы неоптимальной параллелизации первый автор работы, научный сотрудник ФГУП "Всероссийский научно-исследовательский институт автоматики имени Н.Л. Духова" Мария Егорова.
Чтобы проводить расчеты максимально эффективно, ученые и инженеры используют так называемые параллельные алгоритмы, которые распределяют необходимые вычисления между процессорами, установленными в вычислительных узлах. Но один и тот же процесс можно распределить по вычислительным узлам по-разному в зависимости от того, каким способом ученые представляют среду, в которой происходят описываемые процессы. Самый популярный способ – так называемый сеточный метод, когда среда представляется как набор жестко связанных между собой элементов-ячеек с явно проведенными границами между ними. Но как раз этот метод плохо подходит для процессов, развивающихся под действием экстремальных сил.
"В таких процессах среда все время деформируется по всему объему, границы объектов сильно искажаются, и тогда элементы сетки, если они жестко привязаны к веществу, искажаются тоже. Это нарушает точность расчета, и сетки приходится перестраивать. Если в наших задачах привязать элементы сетки не к веществу, а к пространству, содержимое ячеек оказывается смешанным – например, состоящим из вакуума и материи – и приходится отслеживать, как меняются границы между компонентами содержимого. На это уходит много вычислительной мощности. Мы хотели обойтись без этих затрат", – рассказывает Егорова.
Картинки: перехлест волны через палубу корабля и затопление города водой, смоделированные с использованием алгоритма сглаженных частиц. Источник: Ihmsen M. et al., 2013
Для моделирования подвижных сред используются бессеточные методы, в которых нет фиксированных связей между элементами среды. Это, например, метод молекулярной динамики или метод сглаженных частиц, которые хорошо приспособлены для быстрых перемещений отдельных элементов среды. Но для того чтобы смоделировать взрыв или соударение двух объектов – скажем, при падении метеорита – приходится совмещать сеточные и бессеточные методы. До удара используется сеточный метод, после – бессеточный.
"Мы разработали алгоритм, который позволяет просчитывать все процессы, используя только метод сглаженных частиц. С частицами работа более прозрачна и единообразна, чем с сетками, так как не нужно ничего перестраивать, привлекать сложные многокомпонентные модели в ячейке сетки. Но проблема метода сглаженных частиц заключается в том, что он менее точный, чем сеточные методы. Чтобы повысить точность, нужно вводить в расчет больше частиц. Наш алгоритм позволяет эффективно использовать столько частиц, сколько необходимо" – говорит Мария Егорова.
Для того чтобы разделить среду на отдельные участки, каждый из которых будет обсчитываться на разных процессорах, алгоритм использует разбиение по диаграмме Вороного. Этим термином называют особый способ разделения тела на несколько областей. "Допустим, мы решили разбить некую часть пространства на 10 областей. Для создания разбиения на ней нам сначала нужно выбрать 10 несовпадающих точек. Тогда одна ячейка разбиения будет представлять собой область пространства, любая точка которой ближе к одной из выбранных точек, чем к любой из других девяти выбранных", – объясняет Мария Егорова принцип построения диаграммы Вороного. Наглядно увидеть, как работает диаграмма, можно тут.
В созданном учеными алгоритме количество точек, по которым будет строиться диаграмма Вороного, выбирается равным количеству процессоров. Каждая точка привязывается к конкретному процессору и окружающая ее область, то есть соответствующая ячейка разбиения, рассчитывается этим процессором. Передвигая точки, ученые могут выбирать, какая часть среды будет обрабатываться на каждом процессоре, вовлеченном в расчет, и тем самым регулировать вычислительную нагрузку каждого процессора.
"Такое динамическое разделение среды между процессорами позволяет оптимизировать вычисления за счет того, что граничащие друг с другом области диаграммы Вороного могут обмениваться между собой частицами, – говорит Егорова. – Благодаря этому наш алгоритм позволяет оптимально нагружать все процессоры: если оказывается, что какой-то из них простаивает, он получает от своего более загруженного соседа по диаграмме часть его вещества на расчет. Причем мы изменяем нагрузку на процессоры, ориентируясь именно на время, когда они заняты вычислениями, а не на общее время работы процессора. Это более сложный путь, но зато он обеспечивает лучшую балансировку между узлами суперкомпьютера. До сих пор в нашей области никто не предлагал использовать именно такой подход".
В своей работе исследователи тестировали задачу о взрывающейся проволочке – это явление наблюдается, например, при разрядке конденсатора через проводник ("проволочку"). В момент разрядки проводник очень быстро нагревается до десятков тысяч градусов и переходит в состояние плазмы. При этом происходит множество весьма сложных процессов, в том числе возникновение ударной волны, что существенно осложняет точное описание этого простого с виду явления. По сравнению с традиционным разбиением, когда процессорам отдаются на расчет неподвижные области пространства, разбиение, предложенное авторами новой работы, позволяет увеличить скорость расчета в задаче о взрывающейся проволочке в 3-6 раз при одинаковом количестве процессоров.
"Новый параллельный алгоритм позволит эффективно использовать вычислительные кластеры, состоящие из многих тысяч процессоров, и тем самым существенно расширить возможности моделирования сложных процессов, происходящих под воздействием мощных сил, от воздействия лазеров и взрывов до формирования звезд – поясняет еще один соавтор работы, ведущий научный сотрудник ВНИИ автоматики имени Духова и сотрудник ИТФ имени Ландау Василий Жаховский. – Никакими имеющимися коммерческими программными пакетами такое моделирование осуществить невозможно".
