Математик РУДН совместно с коллегами из Венгрии и Франции разработал алгоритм параллельных вычислений, который позволит быстрее решать прикладные задачи, например электродинамики или гидродинамики. Выигрыш во времени составляет до 50%. Результаты опубликованы в Journal of Computational and Applied Mathematics.
Для расчета на компьютере практических задач физики, инженерии, биологии и других областей часто применяют методы параллельного вычисления. Это означает, что несколько объединенных в сеть процессоров одновременно решают одну задачу — каждый свою небольшую часть. Как именно разделить работу между процессорами и организовать их «общение» между собой, выбирают исходя из особенностей конкретной задачи. Один из возможных методов — декомпозиция. Исследуемую область разбивают на отдельные части — подобласти — по числу процессоров. В основном в таких случаях используются так называемые методы Шварца, в которых подобласти перекрывают друг друга. Это обеспечивает точные результаты, но не подходит, если пересечения областей слишком сложные. Математик РУДН совместно с коллегами из Венгрии и Франции предложил новый алгоритм, который делает декомпозицию проще, — подобласти не перекрывают друг друга, результат остается точным, а времени на вычисления требуется меньше.
«До сих пор почти все исследования по методу декомпозиции исследуемой области были нацелены на методы типа Шварца. Первая и единственная попытка иметь дело с декомпозицией без перекрытий привела к тому, что итерации происходят одновременно на подобластях и на границах между ними. А для этого численная схема вычислений должна быть определена для всей глобальной области», — объясняет Гийом Гбикпи-Бениссан, сотрудник Инженерной академии РУДН.
Математики предложили алгоритм, основный на методе Гаусса — Зейделя. Суть нововведения заключается в том, что алгоритм вычисления запускается не одновременно на всей области, а поочередно на подобластях и границах между ними. В результате получается, что полученные во время каждой итерации значения внутри подобласти можно сразу же использовать для вычислений на границе без дополнительный операций.
Новый алгоритм математики испытали на уравнении Пуассона и уравнении равновесия сплошной среды. Первое используется, например, в электромагнетизме для описания электростатического поля, второе — в гидродинамике, для описания движения жидкостей. Для обоих уравнений новый метод оказался быстрее стандартного. Выигрыш во времени достиг 50% — при разбиении области на 720 подобластей новый алгоритм решает уравнение Пуассона за 84 секунды, а классический — за 170. При этом количество необходимых итераций уменьшается с увеличением числа подобластей.
«Это довольно интересное поведение, которое можно объяснить тем фактом, что частота чередования вычислений на подобластях и на границах увеличивается по мере уменьшения размеров подобластей и появления большего количества границ. Наши результаты открывают дальнейшие возможности и новые перспективные исследования парадигмы асинхронных вычислений», — рассказал Гийом Гбикпи-Бениссан.
Подписывайтесь на InScience.News в социальных сетях: ВКонтакте, Telegram, Одноклассники.
