Каково состояние параллельных методов ODE?

39

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

Есть книга Burrage [1], но ей почти 20 лет, и, следовательно, она не охватывает многие из более современных идей, таких как парареальный алгоритм.

[1] К. Баррейдж, Параллельные и последовательные методы для обыкновенных дифференциальных уравнений, Кларендон Пресс, Оксфорд, 1995

Флориан Брукер
источник

Ответы:

35

Я не знаю ни одной недавней обзорной статьи, но я активно участвую в разработке алгоритма PFASST, поэтому могу поделиться некоторыми мыслями.

Мне известны три широких класса параллельных по времени методов:

  • по методу - независимые этапы РК или интеграторы экстраполяции могут оцениваться параллельно; см. также RIDC (ревизионистский алгоритм интегральной отложенной коррекции)
  • через проблему - релаксация формы волны
  • через временную область - Parareal; PITA (параллельный по времени алгоритм); и PFASST (параллельная схема полного приближения в пространстве и времени).

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

Методы, которые распараллеливают во временной области, включают Parareal, PITA, PFASST. Все эти методы итеративны и состоят из недорогих (но неточных) «грубых» пропагаторов и дорогих (но точных) «тонких» пропагаторов. Они достигают параллельной эффективности, итеративно оценивая точный пропагатор параллельно, чтобы улучшить последовательное решение, полученное с использованием грубого пропагатора.

EE<1/KK

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

Некоторые ссылки (см. Также ссылки, перечисленные в статьях):

Я написал две реализации PFASST, которые доступны в сети: PyPFASST и libpfasst .

Мэтью Эмметт
источник
1
В настоящее время я изучаю парареализм. И я думаю, что это очень помогает мне.
Экстартуп
Это отличный обзор. Однако следует прямо упомянуть, что ODE часто решаются после пространственной дискретизации PDE. Следовательно, параллелизм в методе может обеспечить большую масштабируемость для тысяч ядер, если ваш пространственный домен достаточно велик. Это связано с тем, что подавляющее большинство времени вычислений приходится на вычисления, например, оценок RHS на этапе RK.
NoseKnowsAll
15

Хотя этому посту уже два года, на случай, если кто-то наткнется на него, позвольте мне дать краткое обновление:

Мартин Гандер недавно написал хорошую обзорную статью, в которой дается исторический взгляд на ситуацию и обсуждается множество различных методов PINT: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

В настоящее время существует также веб-сайт сообщества, который перечисляет очень много ссылок и дает описание различных методов: http://www.parallel-in-time.org/

В частности, обсуждение алгоритма параллельного времени Parareal можно найти здесь: https://en.wikipedia.org/wiki/Parareal

Даниил
источник
1
Немного удивлен, что Гандер не говорит о подходе MGRIT, предложенном Falgout и др., Тем более что он, похоже, поддерживается хорошим программным обеспечением (XBraid), но я знаю, что документы MGRIT появились только недавно.
Джефф Оксберри
1
Привет Джефф, я вполне уверен, что Мартин Гандер написал статью до публикации документов MGRIT - хотя обзорный документ должен появиться в 2015 году, я думаю, что препринт появился в сети уже в конце 2013 года.
Даниэль
1
На первый взгляд, похоже, что «параллель по методу» в этом обзоре опущена - например, экстраполяция никогда не упоминается.
Дэвид Кетчон
4

u0u(t)=exp(λt)u0, Reλ>0.

Хуэй Чжан
источник
Как я уже сказал, я уже нашел много статей по отдельным темам. Чего мне не хватает, так это общего обзора подходов.
Флориан Брукер
1
Кстати, алгоритм PFASST демонстрирует очень хорошую сходимость (будет опубликована в ближайшее время) для гамильтоновых систем даже для многих (сотен) временных процессоров. Сказав это, получение ощутимого ускорения зависит (еще раз) от того, чтобы сделать грубые пропагаторы намного дешевле, чем мелкий пропагатор - многополюсное расширение или какой-либо другой мультифизический подход, по-видимому, необходимы для получения хорошего ускорения для систем частиц.
Мэтью Эммет