Новый алгоритм позволит выяснить, как сталкиваются звезды

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

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

Чтобы проводить расчеты максимально эффективно, ученые и инженеры используют так называемые параллельные алгоритмы, которые распределяют необходимые вычисления между процессорами, установленными в вычислительных узлах. Но один и тот же процесс можно распределить по вычислительным узлам по-разному — в зависимости от того, каким способом ученые представляют среду, в которой происходят описываемые процессы. Самый популярный способ – так называемый сеточный метод, когда среда представляется как набор жестко связанных между собой элементов-ячеек с явно проведенными границами между ними. Но как раз этот метод плохо подходит для процессов, развивающихся под действием экстремальных сил.

Для моделирования подвижных сред используются бессеточные методы, в которых нет фиксированных связей между элементами среды. Это, например, метод молекулярной динамики или метод сглаженных частиц, которые хорошо приспособлены для быстрых перемещений отдельных элементов среды. Но для того чтобы смоделировать взрыв или соударение двух объектов – скажем, при падении метеорита – приходится совмещать сеточные и бессеточные методы. До удара используется сеточный метод, после – бессеточный. «Мы разработали алгоритм, который позволяет просчитывать все процессы, используя только метод сглаженных частиц. С частицами работа более прозрачна и единообразна, чем с сетками, так как не нужно ничего перестраивать, привлекать сложные многокомпонентные модели в ячейке сетки. Но проблема метода сглаженных частиц заключается в том, что он менее точный, чем сеточные методы. Чтобы повысить точность, нужно вводить в расчет больше частиц. Наш алгоритм позволяет эффективно использовать столько частиц, сколько необходимо», – комментирует один из авторов работы, научный сотрудник ВНИИ автоматики имени Н.Л. Духова Мария Егорова.

Для того чтобы разделить среду на отдельные участки, каждый из которых будет обсчитываться на разных процессорах, алгоритм использует разбиение по диаграмме Вороного. Этим термином называют особый способ разделения тела на несколько областей. «Допустим, мы решили разбить некую часть пространства на 10 областей. Для создания разбиения на ней нам сначала нужно выбрать 10 несовпадающих точек. Тогда одна ячейка разбиения будет представлять собой область пространства, любая точка которой ближе к одной из выбранных точек, чем к любой из других девяти выбранных», – объясняет Мария Егорова принцип построения диаграммы Вороного. Наглядно увидеть, как работает диаграмма, можно тут. В созданном учеными алгоритме количество точек, по которым будет строиться диаграмма Вороного, выбирается равным количеству процессоров. Каждая точка привязывается к конкретному процессору и окружающая ее область, то есть соответствующая ячейка разбиения, рассчитывается этим процессором. Передвигая точки, ученые могут выбирать, какая часть среды будет обрабатываться на каждом процессоре, вовлеченном в расчет, и тем самым регулировать вычислительную нагрузку каждого процессора.

«Такое динамическое разделение среды между процессорами позволяет оптимизировать вычисления за счет того, что граничащие друг с другом области диаграммы Вороного могут обмениваться между собой частицами, – говорит Егорова. – Благодаря этому наш алгоритм позволяет оптимально нагружать все процессоры: если оказывается, что какой-то из них простаивает, он получает от своего более загруженного соседа по диаграмме часть его вещества на расчет. Причем мы изменяем нагрузку на процессоры, ориентируясь именно на время, когда они заняты вычислениями, а не на общее время работы процессора. Это более сложный путь, но зато он обеспечивает лучшую балансировку между узлами суперкомпьютера. До сих пор в нашей области никто не предлагал использовать именно такой подход».

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

Пресс-релизы о научных исследованиях, информацию о последних вышедших научных статьях и анонсы конференций, а также данные о выигранных грантах и премиях присылайте на адрес science@indicator.ru.