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

Парареальный это параллельный алгоритм от численный анализ и использован для решения проблемы начального значения.^[1]Он был представлен в 2001 году Львы, Мадей и Туриничи. С тех пор он стал одним из наиболее широко изучаемых методов интегрирования параллельно во времени.^{[нужна цитата ]}

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

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

История

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

Алгоритм

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

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

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

${\displaystyle {\dot {y}}(t)=f(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}].}$

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

Parareal основан на итеративном применении двух методов для интегрирование обыкновенных дифференциальных уравнений.Один, обычно обозначаемый ${\displaystyle {\mathcal {F}}}$, должен иметь высокую точность и вычислительные затраты, а другой, обычно помеченный ${\displaystyle {\mathcal {G}}}$, должен быть дешевым в вычислительном отношении, но может быть гораздо менее точным. Как правило, как для грубого, так и для точного интегратора выбирается какая-либо форма метода Рунге-Кутта, где ${\displaystyle {\mathcal {G}}}$ может быть более низкого порядка и использовать больший временной шаг, чем ${\displaystyle {\mathcal {F}}}$.Если проблема начального значения возникает из дискретизации УЧП, ${\displaystyle {\mathcal {G}}}$ также можно использовать более грубую пространственную дискретизацию, но это может отрицательно повлиять на сходимость, если не используется интерполяция высокого порядка.^[11]Результат численного интегрирования одним из этих методов по временному интервалу ${\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,}$

где ${\displaystyle k}$ - счетчик итераций. По мере схождения итерации и ${\displaystyle y_{j}^{k+1}-y_{j}^{k}\to 0}$, члены грубого метода отменяются, и Parareal воспроизводит решение, полученное последовательным выполнением только точного метода. Можно показать, что Parareal сходится после максимального ${\displaystyle P}$ итераций.^[6]Однако для того, чтобы Parareal мог обеспечить ускорение, он должен сходиться за количество итераций, значительно меньшее, чем количество временных отрезков, то есть ${\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 можно получить.^[12]Хотя в приложениях эти допущения могут быть слишком ограничительными, модель все же полезна для иллюстрации компромиссов, связанных с получением ускорения с 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\}.}$

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

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

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

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

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

Варианты

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

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

Ранее было признано, что для линейных задач информация, генерируемая точным методом ${\displaystyle {\mathcal {F}}_{\delta t}}$ может использоваться для повышения точности грубого метода ${\displaystyle {\mathcal {G}}_{\Delta t}}$.^[16] Первоначально идея была сформулирована для параллельного неявного интегратора времени PITA,^[18] метод, тесно связанный с Parareal, но с небольшими отличиями в том, как выполняется коррекция. На каждой итерации ${\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.^[19] Обозначим как ${\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)}$.

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

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

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

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

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

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

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

ParaExp

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

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

1. Львов, Жак-Луи; Мадай, Ивон; Туриничи, Габриэль (2015). «Парареальный» в дискретизации по времени УЧП » (PDF). Comptes Rendus de l'Académie des Sciences, Série I. 332 (7): 661–668. Bibcode:2001CRASM.332..661L. Дои:10.1016 / S0764-4442 (00) 01793-6.
2. Джек Донгарра; Джеффри Хиттингер; Джон Белл; Луис Чакон; Роберт Фальгаут; Майкл Эру; Пол Ховланд; Эсмонд Нг; Клейтон Вебстер; Стефан Вильд (март 2014 г.). Прикладные математические исследования для эксафлопсных вычислений (PDF) (Отчет). Министерство энергетики США. Проверено август 2015 г.. Проверить значения даты в: | accessdate = (Помогите)
3. Беррейдж, Кевин (1997). «Параллельные методы для ОДУ». Достижения в вычислительной математике. 7 (1–2): 1–31. Дои:10.1023 / А: 1018997130884.
4. Iserles, A .; Нёрсетт, С. П. (1990-10-01). «К теории параллельных методов Рунге-Кутты». Журнал численного анализа IMA. 10 (4): 463–488. Дои:10.1093 / imanum / 10.4.463. ISSN  0272-4979.
5. Кетчесон, Дэвид; Вахид, Умайр бин (13.06.2014). «Сравнение явных методов Рунге – Кутты высокого порядка, экстраполяции и отложенной коррекции в последовательном и параллельном». Коммуникации в прикладной математике и вычислительной технике. 9 (2): 175–200. arXiv:1305.6165. Дои:10.2140 / camcos.2014.9.175. ISSN  2157-5452.
6. Гандер, Мартин Дж .; Вандевалле, Стефан (2007). «Анализ Парареального метода интеграции времени с параллельным временем». Журнал SIAM по научным вычислениям. 29 (2): 556–578. CiteSeerX  10.1.1.154.6042. Дои:10.1137 / 05064607X.
7. Хакбуш, Вольфганг (1985). Параболические многосеточные методы. Вычислительные методы в прикладных науках и технике, VI. С. 189–197. ISBN  9780444875976. Проверено август 2015 г.. Проверить значения даты в: | дата доступа = (Помогите)
8. Киль, Мартин (1994). «Параллельная многократная съемка для решения начальных задач». Параллельные вычисления. 20 (3): 275–295. Дои:10.1016 / S0167-8191 (06) 80013-X.
9. Гандер, Мартин Дж. (2015). 50 лет интеграции времени с параллельным временем. Вклад в математические и вычислительные науки. 9 (1-е изд.). Издательство Springer International. Дои:10.1007/978-3-319-23321-5. ISBN  978-3-319-23321-5.
10. Нивергельт, Юрг (1964). «Параллельные методы интегрирования обыкновенных дифференциальных уравнений». Коммуникации ACM. 7 (12): 731–733. Дои:10.1145/355588.365137.
11. Рупрехт, Даниэль (2014-12-01). «Конвергенция парареального с пространственным огрублением» (PDF). ПАММ. 14 (1): 1031–1034. Дои:10.1002 / pamm.201410490. ISSN  1617-7061.
12. Миньон, Майкл Л. (2010). «Гибридный метод парареальной спектральной отложенной коррекции». Коммуникации в прикладной математике и вычислительной технике. 5 (2): 265–301. Дои:10.2140 / camcos.2010.5.265.
13. Персонал, Гуннар Андреас; Ренквист, Эйнар М. (01.01.2005). Барт, Тимоти Дж .; Грибель, Майкл; Киз, Дэвид Э .; Nieminen, Risto M .; Руз, Дирк; Шлик, Тамар; Корнхубер, Ральф; Хоппе, Рональд; Перио, Жак (ред.). Устойчивость парареального алгоритма. Конспект лекций по вычислительным наукам и технике. Springer Berlin Heidelberg. С. 449–456. Дои:10.1007/3-540-26825-1_46. ISBN  9783540225232.
14. Штайнер, Йоханнес; Рупрехт, Даниэль; Спек, Роберт; Краузе, Рольф (01.01.2015). Абдулле, Ассир; Депарис, Симона; Кресснер, Дэниел; Нобиле, Фабио; Пикассо, Марко (ред.). Сходимость парареального для уравнений Навье-Стокса в зависимости от числа Рейнольдса. Конспект лекций по вычислительным наукам и технике. Издательство Springer International. С. 195–202. CiteSeerX  10.1.1.764.6242. Дои:10.1007/978-3-319-10705-9_19. ISBN  9783319107042.
15. Дай, X .; Maday, Y. (01.01.2013). "Стабильный парареальный по времени метод для гиперболических систем первого и второго порядков". Журнал SIAM по научным вычислениям. 35 (1): A52 – A78. Дои:10.1137/110861002. ISSN  1064-8275.
16. Фархат, Шарбель; Кортиаль, Жюльен; Дастиллунг, Климен; Бавестрелло, Анри (30.07.2006). «Параллельные времени неявные интеграторы для предсказания линейных структурных динамических реакций в режиме, близком к реальному времени». Международный журнал численных методов в инженерии. 67 (5): 697–724. Bibcode:2006IJNME..67..697F. Дои:10.1002 / nme.1653. ISSN  1097-0207.
17. Чен, Фэн; Hesthaven, Jan S .; Чжу, Сюэюй (01.01.2014). Quarteroni, Alfio; Роцца, Джанлуиджи (ред.). Об использовании сокращенных базисных методов для ускорения и стабилизации парареального метода. MS&A - Моделирование, имитация и приложения. Издательство Springer International. С. 187–214. Дои:10.1007/978-3-319-02090-7_7. ISBN  9783319020891.
18. Фархат, Шарбель; Чандесрис, Марион (07.11.2003). "Разложенные во времени параллельные интеграторы времени: теория и технико-экономические обоснования для приложений жидкости, структуры и жидкости-структуры". Международный журнал численных методов в инженерии. 58 (9): 1397–1434. Bibcode:2003IJNME..58.1397F. Дои:10.1002 / nme.860. ISSN  1097-0207.
19. Гандер, М .; Петку, М. (2008). "Анализ подпространства Крылова расширенного парареального алгоритма для линейных задач". ESAIM: Материалы. 25: 114–129. Дои:10.1051 / proc: 082508.
20. Ruprecht, D .; Краузе, Р. (30 апреля 2012 г.). «Явное интегрирование во времени линейной акустической адвекции». Компьютеры и жидкости. 59: 72–83. arXiv:1510.02237. Дои:10.1016 / j.compfluid.2012.02.015.
21. Датт, Алок; Грингард, Лесли; Рохлин, Владимир (01.06.2000). "Спектральные методы отложенной коррекции обыкновенных дифференциальных уравнений". BIT вычислительная математика. 40 (2): 241–266. Дои:10.1023 / А: 1022338906936. ISSN  0006-3835.
22. Миньон, Майкл (05.01.2011). «Гибридный парареальный метод отложенной спектральной коррекции». Коммуникации в прикладной математике и вычислительной технике. 5 (2): 265–301. Дои:10.2140 / camcos.2010.5.265. ISSN  2157-5452.
23. Эммет, Мэтью; Миньон, Майкл (28.03.2012). «К эффективному методу параллельности по времени для уравнений в частных производных». Коммуникации в прикладной математике и вычислительной технике. 7 (1): 105–132. Дои:10.2140 / camcos.2012.7.105. ISSN  2157-5452.
24. Speck, R .; Ruprecht, D .; Krause, R .; Emmett, M ​​.; Миньон, М .; Винкель, М .; Гиббон, П. (2012-11-01). Решатель N тел с параллельными массивами пространственно-временных. Высокопроизводительные вычисления, сети, хранение и анализ (SC), Международная конференция 2012 г.. С. 1–11. Дои:10.1109 / SC.2012.6. ISBN  978-1-4673-0805-2.
25. Falgout, R .; Friedhoff, S .; Колев, Т .; MacLachlan, S .; Шредер, Дж. (01.01.2014). «Параллельная временная интеграция с многосеткой». Журнал SIAM по научным вычислениям. 36 (6): C635 – C661. CiteSeerX  10.1.1.701.2603. Дои:10.1137/130944230. ISSN  1064-8275.
26. Гандер, М .; Гюттель, С. (1 января 2013 г.). «ПАРАЭКСП: Параллельный интегратор для линейных задач с начальным значением». Журнал SIAM по научным вычислениям. 35 (2): C123 – C142. CiteSeerX  10.1.1.800.5938. Дои:10.1137/110856137. ISSN  1064-8275.

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

• parallel-in-time.org