Parareal - Parareal

Parareal bir paralel algoritma itibaren Sayısal analiz ve çözümü için kullanılır ilk değer problemleri.^[1]Tarafından 2001 yılında tanıtıldı Aslanlar, Maday ve Turinici. O zamandan beri, en çok çalışılan zamanda paralel entegrasyon yöntemlerinden biri haline geldi.^{[kaynak belirtilmeli ]}

Zamanında paralel entegrasyon yöntemleri

Ör. Runge-Kutta veya çok adımlı yöntemler, Parareal'de bazı hesaplamalar yapılabilir paralel ve Parareal bu nedenle bir paralel zaman entegrasyon yöntemi. Tarihsel olarak çoğu çaba sayısal çözüm nın-nin kısmi diferansiyel denklemler Uzamsal ayrıklaştırmaya odaklandı, zorluklar göz önüne alındığında üst düzey hesaplama için paralel yöntemler zamansal ayrıklaştırma eşzamanlılığı artırmanın olası bir yolu olarak tanımlanmıştır sayısal yazılım.^[2]Parareal, birden çok zaman adımı için sayısal çözümü paralel olarak hesapladığından, şu şekilde kategorize edilir: adımlar boyunca paralel yöntem.^[3]Bu, kullanan yaklaşımların aksine yöntem boyunca paralellik paralel Runge-Kutta veya ekstrapolasyon yöntemleri gibi, bağımsız aşamaların paralel olarak hesaplanabildiği veya sistem boyunca paralel dalga formu gevşetme gibi yöntemler.^[4][5]

Tarih

Parareal hem bir multigrid yöntemi zaman yönteminde veya olarak çoklu çekim zaman ekseni boyunca.^[6]Zaman içinde çok aşamalı olmanın yanı sıra zaman entegrasyonu için çoklu çekimi benimseyen her iki fikir de 1980'lere ve 1990'lara geri dönüyor.^[7][8]Parareal, yaygın olarak incelenen bir yöntemdir ve bir dizi farklı uygulama için kullanılmış ve değiştirilmiştir.^[9]İlk değer problemlerinin çözümünü paralelleştirmeye yönelik fikirler daha da geriye gider: Zaman içinde paralel entegrasyon yöntemini öneren ilk makale 1964'te yayınlandı.^[10]

Algoritma

Medya oynatın

Parareal algoritmasının görselleştirilmesi. Buradaki kaba yayıcı etiketlenmiştir ${ displaystyle { bar { varphi}}}$ ince yayıcı etiketlenirken ${ displaystyle varphi}$.

Parareal, formun başlangıç ​​değer problemini çözer

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

Burada sağ taraf ${ displaystyle f}$ bir kısmi diferansiyel denklemin uzamsal ayrıklaşmasına karşılık gelebilir hat yöntemi yaklaşmak.

Parareal artık bir ayrışma zaman aralığının ${ displaystyle [t_ {0}, T]}$ içine ${ displaystyle P}$ sözde zaman dilimleri ${ displaystyle [t_ {j}, t_ {j + 1}]}$ öyle ki

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

Algoritma paralelleştirilirken her bir zaman dilimi bir işlem birimine atanır, böylece ${ displaystyle P}$ Parareal için kullanılan işlem birimlerinin sayısına eşittir: MPI temelli kod, örneğin, bu, bir OpenMP tabanlı kod ${ displaystyle P}$ sayısına eşit olacaktır İş Parçacığı.

Parareal, iki yöntemin yinelemeli uygulamasına dayanır: adi diferansiyel denklemlerin entegrasyonu Biri, yaygın olarak etiketlenmiş ${ displaystyle { mathcal {F}}}$, yüksek doğruluk ve hesaplama maliyetine sahip olmalı, diğeri ise genellikle ${ displaystyle { mathcal {G}}}$, hesaplama açısından ucuz olmalı, ancak çok daha az doğru olabilir. Tipik olarak, hem kaba hem de ince birleştirici için bir çeşit Runge-Kutta yöntemi seçilir, burada ${ displaystyle { mathcal {G}}}$ daha düşük düzeyde olabilir ve daha büyük bir zaman adımı kullanabilir: ${ displaystyle { mathcal {F}}}$Başlangıç ​​değer problemi bir PDE'nin ayrıklaştırılmasından kaynaklanıyorsa, ${ displaystyle { mathcal {G}}}$ daha kaba bir uzamsal ayrıklaştırma da kullanabilir, ancak bu, yüksek dereceli enterpolasyon kullanılmadıkça yakınsamayı olumsuz yönde etkileyebilir.^[11]Bir zaman diliminde bu yöntemlerden biriyle sayısal entegrasyonun sonucu ${ displaystyle [t_ {j}, t_ {j + 1}]}$ bazı başlangıç ​​değerleri için ${ displaystyle y_ {j}}$ verilen ${ displaystyle t_ {j}}$ daha sonra şöyle yazılır

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

İnce yöntemle seri zaman entegrasyonu daha sonra adım adım bir hesaplamaya karşılık gelir.

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

Parareal bunun yerine aşağıdaki yinelemeyi kullanır

${ displaystyle y_ {j + 1} ^ {k + 1} = { mathcal {G}} (y_ {j} ^ {k + 1}, t_ {j}, t_ {j + 1}) + { matematiksel {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,}$

nerede ${ displaystyle k}$ yineleme sayacıdır. Yineleme yakınsarken ve ${ displaystyle y_ {j} ^ {k + 1} -y_ {j} ^ {k} ile 0}$, kaba yöntemdeki terimler birbirini götürür ve Parareal, yalnızca ince yöntemin seri olarak yürütülmesi ile elde edilen çözümü yeniden üretir. Parareal'in maksimum bir süre sonra yakınsadığı gösterilebilir. ${ displaystyle P}$ yinelemeler.^[6]Bununla birlikte, Parareal'in hızlanma sağlaması için, zaman dilimlerinin sayısından önemli ölçüde daha az sayıda yinelemede yakınsaması gerekir, yani ${ displaystyle K ll P}$.

Parareal yinelemede, hesaplama açısından pahalı olan ${ displaystyle { mathcal {F}} (y_ {j} ^ {k}, t_ {j}, t_ {j + 1})}$ paralel olarak yapılabilir ${ displaystyle P}$ işleme birimleri. Buna karşılık, bağımlılık ${ displaystyle y_ {j + 1} ^ {k + 1}}$ açık ${ displaystyle { mathcal {G}} (y_ {j} ^ {k + 1}, t_ {j}, t_ {j + 1})}$ kaba düzeltmenin seri sırayla hesaplanması gerektiği anlamına gelir.

Hızlanma

Bazı varsayımlar altında, basit bir teorik model hızlanma Parareal türetilebilir.^[12]Uygulamalarda bu varsayımlar çok kısıtlayıcı olabilse de, model Parareal ile hızlanma elde etmede yer alan değiş tokuşları göstermek için hala yararlıdır.

İlk olarak, her zaman dilimlemeyi ${ displaystyle [t_ {j}, t_ {j + 1}]}$ tam olarak oluşur ${ displaystyle N_ {f}}$ ince entegratörün ve ${ displaystyle N_ {c}}$ Bu, özellikle tüm zaman dilimlerinin aynı uzunlukta olduğu ve hem kaba hem de ince entegratörün tam simülasyon üzerinde sabit bir adım boyutu kullandığı varsayımını içerir. ${ displaystyle tau _ {f}}$ ve ${ displaystyle tau _ {c}}$ Sırasıyla ince ve kaba yöntemlerin tek bir adımı için gereken hesaplama süresi ve her ikisinin de sabit olduğunu varsayarsak Bu, genellikle tam olarak doğru değildir. örtük yöntem kullanılır, çünkü daha sonra çalışma zamanları, tarafından gereken yineleme sayısına bağlı olarak değişir. yinelemeli çözücü.

Bu iki varsayım altında, ince yöntemin çalışma zamanı, ${ displaystyle P}$ zaman dilimleri şu şekilde modellenebilir:

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

Kullanarak Parareal çalışma zamanı ${ displaystyle P}$ işleme birimleri ve performans ${ displaystyle K}$ yinelemeler

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

Parareal Hızlandırması

${ 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 sol {{ frac {N_ {f} tau _ {f}} {N_ {c} tau _ {c}}}, { frac {P} {K}} sağ }.}$

Bu iki sınır, kaba yöntemi seçerken yapılması gereken değiş tokuşu göstermektedir: bir yandan, ucuz olmalı ve / veya ilk sınırı olabildiğince geniş hale getirmek için çok daha büyük bir zaman adımı kullanmalıdır, diğer yandan yinelemelerin sayısını ver ${ displaystyle K}$ ikinci sınırı büyük tutmak için düşük tutulmalıdır. Parareal'in paralel verimliliği ile sınırlanmıştır

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

bu, gerekli yineleme sayısının tersidir.

Hayali özdeğerler için kararsızlık

Parareal'in vanilya versiyonunun hayali problemlerle ilgili sorunları var. özdeğerler.^[6] Tipik olarak yalnızca en son yinelemelere yakınsar, yani ${ displaystyle k}$ yaklaşımlar ${ displaystyle P}$ve hızlanma ${ displaystyle S_ {p}}$ her zaman birden daha küçük olacaktır. Dolayısıyla, yineleme sayısı azdır ve Parareal kararsızdır veya ${ displaystyle k}$ Parareal'i kararlı hale getirmek için yeterince büyük olduğundan hızlanma mümkün değildir. Bu aynı zamanda Parareal'in tipik olarak hiperbolik denklemler.^[13] Gander ve Vandewalle tarafından yapılan biçimsel analiz yalnızca sabit katsayılara sahip doğrusal problemleri kapsasa da, Parareal doğrusal olmayana uygulandığında da sorun ortaya çıkar. Navier-Stokes denklemleri ne zaman viskozite katsayı çok küçük hale gelir ve Reynolds sayısı çok büyük.^[14] Parareal'i stabilize etmek için farklı yaklaşımlar mevcuttur,^[15][16][17] biri Krylov-alt uzay gelişmiş Parareal'dir.

Varyantlar

Doğrudan temel alan veya en azından orijinal Parareal algoritmasından esinlenen birden fazla algoritma vardır.

Krylov-alt uzay gelişmiş Parareal

Daha önce, lineer problemler için ince yöntemle oluşturulan bilginin ${ displaystyle { mathcal {F}} _ { delta t}}$ kaba yöntemin doğruluğunu artırmak için kullanılabilir ${ displaystyle { mathcal {G}} _ { Delta t}}$.^[16] Başlangıçta, fikir paralel örtük zaman entegratörü PITA için formüle edildi,^[18] Parareal ile yakından ilgili ancak düzeltmenin nasıl yapıldığına dair küçük farklılıklar olan bir yöntem. Her yinelemede ${ displaystyle k}$ sonuç ${ displaystyle { mathcal {F}} _ { delta t} (y_ {j} ^ {k})}$ değerler için hesaplanır ${ displaystyle u_ {j} ^ {k} in mathbb {R} ^ {d}}$ için ${ displaystyle j = 0, ldots, P-1}$. Bu bilgilere dayanarak, alt uzay

${ displaystyle S_ {k}: = sol {y_ {j} ^ {k '}: 0 leq k' leq k, j = 0, ldots, P-1 sağ }}$

her Parareal yinelemeden sonra tanımlanır ve güncellenir.^[19] Olarak belirtin ${ displaystyle P_ {k}}$ dikey projeksiyon itibaren ${ displaystyle mathbb {R} ^ {d}}$ -e ${ displaystyle S_ {k}}$. Ardından, kaba yöntemi iyileştirilmiş entegratörle değiştirin ${ displaystyle { mathcal {K}} _ { Delta t} (y) = { mathcal {F}} _ { delta t} (P_ {k} y) + { mathcal {G}} _ { Delta t} ((I-P_ {k}) y)}$.

Yineleme sayısı arttıkça, alan ${ displaystyle S_ {k}}$ büyüyecek ve değiştirilmiş yayıcı ${ displaystyle { mathcal {K}} _ { Delta t}}$ daha doğru hale gelecektir. Bu, daha hızlı yakınsamaya yol açacaktır. Parareal'in bu versiyonu ayrıca doğrusal hiperbolik kısmi diferansiyel denklemleri kararlı bir şekilde entegre edebilir.^[20] İndirgenmiş temel yöntemine dayalı doğrusal olmayan sorunların bir uzantısı da mevcuttur.^[17]

Hibrit Parareal spektral ertelenmiş düzeltmeler

Spektral ertelenmiş düzeltmelerle (SDC) Parareal kombinasyonuna dayalı, geliştirilmiş paralel verime sahip bir yöntem ^[21] M. Minion tarafından önerilmiştir.^[22] Gelişmiş paralel verimlilik için esneklikten ödün vererek, kaba ve ince entegratör seçimini SDC ile sınırlar. Sınırı yerine ${ displaystyle 1 / K}$, hibrit yöntemde paralel verimlilik sınırı

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

ile ${ displaystyle K_ {s}}$ seri SDC temel yönteminin yineleme sayısı ve ${ displaystyle K_ {p}}$ paralel hibrit yöntemin tipik olarak daha fazla sayıda yinelemesi. Parareal-SDC hibrit, bir tam yaklaşım şeması doğrusal olmayan şekilde kullanıldığı gibi multigrid. Bu, uzay ve zamanda paralel tam yaklaşım şeması (PFASST).^[23] PFASST performansı PEPC için çalışılmıştır. Barnes-Hut ağaç kodu tabanlı parçacık çözücü geliştirildi Juelich Süper Hesaplama Merkezi. IBM'deki 262.144 çekirdeğin tamamını kullanan simülasyonlar BlueGene / P sistemi JUGENE, PFASST'ın uzamsal ağaç paralelleşmesinin doygunluğunun ötesinde ek bir hızlanma üretebileceğini gösterdi.^[24]

Zaman içinde multigrid azaltma (MGRIT)

Zamanında multigrid azaltma yöntemi (MGRIT), Parareal'in bir zaman içinde multigrid-in-time algoritmaları olarak yorumlanmasını farklı düzleştiriciler kullanarak birden çok seviyeye genelleştirir.^[25] Daha genel bir yaklaşımdır ancak belirli bir parametre seçimi için Parareal'e eşdeğerdir. XBraid MGRIT uygulayan kütüphane tarafından geliştirilmektedir Lawrence Livermore Ulusal Laboratuvarı.

ParaExp

ParaExp kullanır üstel integratörler Parareal içinde.^[26] Doğrusal problemlerle sınırlı olsa da, neredeyse optimum paralel hızlanma sağlayabilir.

Referanslar

Dış bağlantılar

• parallel-in-time.org