Парареальный - Parareal

Parareal является параллельным алгоритмом из численного анализа и используются для решения начальных задач . Он был представлен в 2001 году Lions , Maday и Turinici. С тех пор он стал одним из наиболее широко изучаемых методов интегрирования параллельно во времени.

Методы параллельной интеграции

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

История

Parareal может быть получен как многосеточный метод по времени, так и как множественная съемка по оси времени. Обе идеи, многосеточная во времени, а также использование множественной съемки для временной интеграции, восходят к 1980-м и 1990-м годам. Parareal - это широко изученный метод, который использовался и модифицировался для множества различных приложений. Идеи распараллелить решение задач начального значения восходят еще дальше: первая статья, предлагающая метод параллельного во времени интегрирования, появилась в 1964 году.

Алгоритм

Воспроизвести медиа

Визуализация алгоритма Parareal. Здесь промаркирован грубый пропагатор, а вот мелкий .${\ displaystyle {\ bar {\ varphi}}}$${\ displaystyle \ varphi}$

Parareal решает задачу начальной стоимости вида

${\ displaystyle {\ dot {y}} (t) = е (y (t), t), \ quad y (t_ {0}) = y_ {0} \ quad {\ text {with}} \ quad t_ {0} \ leq t \ leq T.}$

Здесь правая часть может соответствовать пространственной дискретизации дифференциального уравнения в частных производных в методе линейного приближения. ${\ displaystyle f}$

Parareal теперь требует декомпозиции временного интервала на так называемые временные срезы , так что ${\ displaystyle [t_ {0}, T]}$${\ displaystyle P}$${\ displaystyle [t_ {j}, t_ {j + 1}]}$

${\ displaystyle [t_ {0}, T] = [t_ {0}, t_ {1}] \ cup [t_ {1}, t_ {2}] \ cup \ ldots \ cup [t_ {P-1}, t_ {P}].}$

Каждый временной интервал назначается одному блоку обработки при распараллеливании алгоритма, так что он равен количеству блоков обработки, используемых для Parareal: например, в коде на основе MPI это будет количество процессов, а в коде на основе OpenMP , будет равно количеству потоков . ${\ displaystyle P}$${\ displaystyle P}$

Parareal основан на итеративном применении двух методов интегрирования обыкновенных дифференциальных уравнений . Один, обычно помеченный , должен обладать высокой точностью и вычислительными затратами, в то время как другой, обычно помеченный , должен быть дешевым в вычислительном отношении, но может быть гораздо менее точным. Как правило, для грубого и точного интегратора выбирается какая-либо форма метода Рунге-Кутта, который может быть более низкого порядка и использовать больший временной шаг, чем . Если проблема начального значения проистекает из дискретизации УЧП, можно также использовать более грубую пространственную дискретизацию, но это может отрицательно повлиять на сходимость, если не используется интерполяция высокого порядка. Результат численного интегрирования одним из этих методов по временному интервалу для некоторого начального значения, заданного в , затем записывается как ${\ Displaystyle {\ mathcal {F}}}$${\ Displaystyle {\ mathcal {G}}}$${\ Displaystyle {\ mathcal {G}}}$${\ Displaystyle {\ mathcal {F}}}$${\ Displaystyle {\ mathcal {G}}}$${\ displaystyle [t_ {j}, t_ {j + 1}]}$${\ displaystyle y_ {j}}$${\ displaystyle t_ {j}}$

${\ displaystyle y = {\ mathcal {F}} (y_ {j}, t_ {j}, t_ {j + 1})}$ или . ${\ displaystyle y = {\ mathcal {G}} (y_ {j}, t_ {j}, t_ {j + 1})}$

Тогда последовательное интегрирование по времени с помощью точного метода будет соответствовать пошаговому вычислению

${\ displaystyle y_ {j + 1} = {\ mathcal {F}} (y_ {j}, t_ {j}, t_ {j + 1}), \ quad j = 0, \ ldots, P-1.}$

Parareal вместо этого использует следующую итерацию

${\ displaystyle y_ {j + 1} ^ {k + 1} = {\ mathcal {G}} (y_ {j} ^ {k + 1}, t_ {j}, t_ {j + 1}) + {\ mathcal {F}} (y_ {j} ^ {k}, t_ {j}, t_ {j + 1}) - {\ mathcal {G}} (y_ {j} ^ {k}, t_ {j}, t_ {j + 1}), \ quad j = 0, \ ldots, P-1, \ quad k = 0, \ ldots, K-1,}$

где - счетчик итераций. По мере того, как итерация сходится и , члены грубого метода сокращаются, и Parareal воспроизводит решение, полученное последовательным выполнением только точного метода. Можно показать, что Parareal сходится после максимального количества итераций. Однако, чтобы Parareal мог обеспечить ускорение, он должен сойтись за несколько итераций, значительно меньших, чем количество временных интервалов, то есть . ${\ displaystyle k}$${\ displaystyle y_ {j} ^ {k + 1} -y_ {j} ^ {k} \ to 0}$${\ displaystyle P}$${\ displaystyle K \ ll P}$

В итерации Parareal вычислительно затратная оценка может выполняться параллельно на процессорах. В противоположность этому , зависимость от средств , что грубая коррекция должна быть вычислена в последовательном порядке. ${\ displaystyle {\ mathcal {F}} (y_ {j} ^ {k}, t_ {j}, t_ {j + 1})}$${\ displaystyle P}$${\ displaystyle y_ {j + 1} ^ {k + 1}}$${\ displaystyle {\ mathcal {G}} (y_ {j} ^ {k + 1}, t_ {j}, t_ {j + 1})}$

Ускорение

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

Во-первых, предположим, что каждый временной интервал состоит ровно из шагов точного интегратора и шагов грубого интегратора. Это включает, в частности, допущение, что все временные интервалы имеют одинаковую длину и что как грубый, так и точный интегратор используют постоянный размер шага на протяжении всей симуляции. Во-вторых, обозначьте и время вычисления, необходимое для одного шага точного и грубого методов, соответственно, и предположите, что оба они постоянны. Обычно это не совсем так, когда используется неявный метод, потому что время выполнения зависит от количества итераций, требуемых итеративным решателем . ${\ displaystyle [t_ {j}, t_ {j + 1}]}$${\ displaystyle N_ {f}}$${\ displaystyle N_ {c}}$${\ displaystyle \ tau _ {f}}$${\ displaystyle \ tau _ {c}}$

При этих двух предположениях время выполнения точного метода, интегрирующего по временным срезам, можно смоделировать как ${\ displaystyle P}$

${\ displaystyle c _ {\ text {fine}} = PN_ {f} \ tau _ {f}.}$

Время выполнения Parareal с использованием блоков обработки и выполнения итераций равно ${\ displaystyle P}$${\ displaystyle K}$

${\ displaystyle c _ {\ text {parareal}} = (K + 1) PN_ {c} \ tau _ {c} + KN_ {f} \ tau _ {f}.}$

Тогда ускорение Parareal

${\ displaystyle S_ {p} = {\ frac {c _ {\ text {fine}}} {c _ {\ text {parareal}}}} = {\ frac {1} {(K + 1) {\ frac {N_ {c}} {N_ {f}}} {\ frac {\ tau _ {c}} {\ tau _ {f}}} + {\ frac {K} {P}}}} \ leq \ min \ left \ {{\ frac {N_ {f} \ tau _ {f}} {N_ {c} \ tau _ {c}}}, {\ frac {P} {K}} \ right \}.}$

Эти две границы иллюстрируют компромисс, который необходимо сделать при выборе грубого метода: с одной стороны, он должен быть дешевым и / или использовать гораздо больший временной шаг, чтобы сделать первую границу как можно большей, с другой стороны. С другой стороны, количество итераций должно быть низким, чтобы вторая граница оставалась большой. В частности, параллельная эффективность Parareal ограничена ${\ displaystyle K}$

${\ displaystyle E_ {p} = {\ frac {S_ {p}} {P}} \ leq {\ frac {1} {K}},}$

то есть числом, обратным количеству требуемых итераций.

Неустойчивость для мнимых собственных значений

В ванильной версии Parareal есть проблемы с мнимыми собственными значениями . Обычно он сходится только к самым последним итерациям, то есть по мере приближения , и ускорение всегда будет меньше единицы. Таким образом, либо количество итераций невелико и Parareal нестабилен, либо, если оно достаточно велико, чтобы сделать Parareal стабильным, ускорение невозможно. Это также означает, что Parareal обычно нестабилен для гиперболических уравнений. Хотя формальный анализ Гандера и Вандевалля охватывает только линейные задачи с постоянными коэффициентами, проблема также возникает, когда Parareal применяется к нелинейным уравнениям Навье – Стокса, когда коэффициент вязкости становится слишком малым, а число Рейнольдса слишком большим. Существуют разные подходы к стабилизации Parareal, один из которых - Parareal, усиленный подпространством Крылова. ${\ displaystyle k}$${\ displaystyle P}$${\ displaystyle S_ {p}}$${\ displaystyle k}$

Варианты

Есть несколько алгоритмов, которые напрямую основаны или, по крайней мере, вдохновлены оригинальным алгоритмом Parareal.

Крылов-подпространство усиленное Parareal

Ранее было признано, что для линейных задач информация, полученная с помощью точного метода, может быть использована для повышения точности грубого метода . Первоначально идея была сформулирована для параллельного неявного интегратора времени PITA, метода, тесно связанного с Parareal, но с небольшими различиями в том, как выполняется коррекция. На каждой итерации результат вычисляется для значений для . На основе этой информации подпространство${\ displaystyle {\ mathcal {F}} _ {\ delta t}}$${\ Displaystyle {\ mathcal {G}} _ {\ Delta t}}$${\ displaystyle k}$${\ displaystyle {\ mathcal {F}} _ {\ delta t} (y_ {j} ^ {k})}$${\ displaystyle u_ {j} ^ {k} \ in \ mathbb {R} ^ {d}}$${\ Displaystyle J = 0, \ ldots, P-1}$

${\ displaystyle S_ {k}: = \ left \ {y_ {j} ^ {k '}: 0 \ leq k' \ leq k, j = 0, \ ldots, P-1 \ right \}}$

определяется и обновляется после каждой итерации Parareal. Обозначим , как в ортогональной проекции от до . Затем замените грубый метод улучшенным интегратором . ${\ displaystyle P_ {k}}$${\ Displaystyle \ mathbb {R} ^ {d}}$${\ displaystyle S_ {k}}$${\ displaystyle {\ mathcal {K}} _ {\ Delta t} (y) = {\ mathcal {F}} _ {\ delta t} (P_ {k} y) + {\ mathcal {G}} _ { \ Delta t} ((I-P_ {k}) y)}$

По мере увеличения количества итераций пространство будет расти, и модифицированный пропагатор станет более точным. Это приведет к более быстрой сходимости. Эта версия Parareal может также стабильно интегрировать линейные гиперболические уравнения в частных производных. Также существует расширение нелинейных задач, основанное на методе редуцированного базиса. ${\ displaystyle S_ {k}}$${\ Displaystyle {\ mathcal {K}} _ {\ Delta t}}$

Гибридные парареальные спектральные отложенные поправки

М. Миньон предложил метод с улучшенной параллельной эффективностью, основанный на комбинации Parareal со спектральными отложенными поправками (SDC). Это ограничивает выбор грубого и точного интегратора до SDC, жертвуя гибкостью ради повышения эффективности параллельной обработки. Вместо предела , предел параллельной эффективности в гибридном методе становится ${\ displaystyle 1 / K}$

${\ displaystyle E_ {p} \ leq {\ frac {K_ {s}} {K_ {p}}}}$

где число итераций базового метода последовательного SDC и обычно большее количество итераций параллельного гибридного метода. Гибрид Parareal-SDC был дополнительно улучшен за счет добавления полной схемы аппроксимации, используемой в нелинейной многосеточной системе . Это привело к разработке схемы параллельной полной аппроксимации в пространстве и времени (PFASST). Производительность PFASST изучалась для PEPC, программы расчета частиц на основе дерева Barnes-Hut, разработанной в суперкомпьютерном центре Juelich . Моделирование с использованием всех 262 144 ядер в системе IBM BlueGene / P JUGENE показало, что PFASST может обеспечить дополнительное ускорение сверх насыщения распараллеливания пространственного дерева. ${\ displaystyle K_ {s}}$${\ displaystyle K_ {p}}$

Многосеточное сокращение времени (MGRIT)

Многосеточный метод сокращения времени (MGRIT) обобщает интерпретацию Parareal как многосеточного алгоритма во времени на несколько уровней с использованием различных сглаживающих устройств. Это более общий подход, но для конкретного выбора параметров он эквивалентен Parareal. Библиотека XBraid, реализующая MGRIT, разрабатывается Ливерморской национальной лабораторией Лоуренса .

ParaExp

ParaExp использует экспоненциальные интеграторы внутри Parareal. Хотя он ограничен линейными задачами, он может обеспечить почти оптимальное параллельное ускорение.

использованная литература

внешние ссылки

• parallel-in-time.org