Iterativní vzorníkové smyčky - Iterative Stencil Loops

Tvar 7bodového 3D von Neumann stylová šablona.

Iterativní vzorníkové smyčky (ISL) jsou třídou řešení zpracování číselných dat^[1]která aktualizace prvky pole podle nějakého pevného vzoru, který se nazývá vzorník.^[2] Nejčastěji se nacházejí v počítačové simulace, např. pro výpočetní dynamika tekutin v kontextu vědeckých a technických aplikací. Mezi další pozoruhodné příklady patří řešení parciální diferenciální rovnice,^[1] the Jacobi jádro, Gauss – Seidelova metoda,^[2] zpracování obrazu^[1] a mobilní automaty.^[3] Pravidelná struktura polí nastavuje techniky šablony na rozdíl od jiných metod modelování, jako je například Metoda konečných prvků. Většina kódy konečných rozdílů které fungují na běžných sítích, lze formulovat jako ISL.

Definice

ISL provádějí posloupnost rozmítání (nazývaných časové kroky) přes dané pole.^[2] Obecně se jedná o 2- nebo 3-dimenzionální pravidelnou mřížku.^[3] Prvky polí se často označují jako buňky. V každém časovém kroku jsou aktualizovány všechny prvky pole.^[2] Pomocí sousedních prvků pole ve fixním vzoru (vzorníku) se vypočítá nová hodnota každé buňky. Ve většině případů zůstávají hraniční hodnoty beze změny, ale v některých případech (např. Kódy LBM ) ty je třeba upravit i během výpočtu. Protože vzorník je pro každý prvek stejný, vzor přístupu k datům se opakuje.^[4]

Více formálně můžeme definovat ISL jako 5-tice ${displaystyle (I, S, S_ {0}, s, T)}$ s následujícím významem:^[3]

• ${displaystyle I = prod _ {i = 1} ^ {k} [0, ldots, n_ {i}]}$ je sada indexů. Definuje topologii pole.
• ${displaystyle S}$ je (ne nutně konečný) soubor stavů, z nichž jeden může každá buňka nabývat v daném časovém kroku.
• ${displaystyle S_ {0} dvojtečka mathbb {Z} ^ {k} o S}$ definuje počáteční stav systému v čase 0.
• ${displaystyle sin prod _ {i = 1} ^ {l} mathbb {Z} ^ {k}}$ je šablona sama o sobě a popisuje skutečný tvar okolí. Existují ${displaystyle l}$ prvky ve vzorníku.
• ${displaystyle Tcolon S ^ {l} o S}$ je přechodová funkce, která se používá k určení nového stavu buňky v závislosti na jejích sousedech.

Od té doby Já je k-dimenzionální celočíselný interval, pole bude mít vždy topologii konečné pravidelné mřížky. Pole se také nazývá simulační prostor a jednotlivé buňky jsou identifikovány podle indexu ${displaystyle cin I}$. Šablona je uspořádaná sada ${displaystyle l}$ relativní souřadnice. Nyní můžeme získat pro každou buňku ${displaystyle c}$ n-tice indexů jejích sousedů ${displaystyle I_ {c}}$

${displaystyle I_ {c} = {jmid existuje xin s: j = c + x},}$

Jejich stavy jsou dány mapováním n-tice ${displaystyle I_ {c}}$ do odpovídající n-tice států ${displaystyle N_ {i} (c)}$, kde ${displaystyle N_ {i} dvojtečka I o S ^ {l}}$ je definována takto:

${displaystyle N_ {i} (c) = (s_ {1}, ldots, s_ {l}) {ext {with}} s_ {j} = S_ {i} (I_ {c} (j)),}$

To je vše, co potřebujeme k definování stavu systému pro následující časové kroky ${displaystyle S_ {i + 1} dvojtečka mathbb {Z} ^ {k} o S}$ s ${displaystyle iin mathbb {N}}$:

${displaystyle S_ {i + 1} (c) = {egin {cases} T (N_ {i} (c)), & cin I S_ {i} (c), & cin mathbb {Z} ^ {k} setminus Iend {případy}}}$

Všimněte si, že ${displaystyle S_ {i}}$ je definováno na ${displaystyle mathbb {Z} ^ {k}}$ a nejen dál ${displaystyle I}$ protože také je třeba nastavit okrajové podmínky. Někdy prvky ${displaystyle I_ {c}}$ může být definován přidáním vektoru modulo dimenze simulačního prostoru k realizaci toroidních topologií:

${displaystyle I_ {c} = {jmid existuje xin s: j = ((c + x) mod (n_ {1}, ldots, n_ {k}))}}$

To může být užitečné pro implementaci periodické okrajové podmínky, což zjednodušuje určité fyzické modely.

Příklad: 2D Jacobiho iterace

Závislosti dat vybrané buňky ve 2D poli.

Pro ilustraci formální definice se podíváme na to, jak je dvourozměrná Jacobi iteraci lze definovat. Funkce aktualizace spočítá aritmetický průměr čtyř sousedů buňky. V tomto případě jsme vyrazili s počátečním řešením 0. Levá a pravá hranice jsou fixovány na 1, zatímco horní a dolní hranice jsou nastaveny na 0. Po dostatečném počtu iterací systém konverguje proti sedlovému tvaru.

${displaystyle {egin {aligned} I & = [0, ldots, 99] ^ {2} S & = mathbb {R} S_ {0} &: mathbb {Z} ^ {2} o mathbb {R} S_ { 0} ((x, y)) & = {egin {cases} 1, & x <0 0, & 0leq x <100 1, & xgeq 100end {cases}} s & = ((0, -1), (- 1,0), (1,0), (0,1)) T & tlustého střeva mathbb {R} ^ {4} o mathbb {R} T ((x_ {1}, x_ {2}, x_ {3} , x_ {4})) & = 0,25cdot (x_ {1} + x_ {2} + x_ {3} + x_ {4}) konec {zarovnáno}}}$

${displaystyle S_ {0}}$

${displaystyle S_ {200}}$

${displaystyle S_ {400}}$

${displaystyle S_ {600}}$

${displaystyle S_ {800}}$

${displaystyle S_ {1 000}}$

2D Jacobi Iteration na a ${displaystyle 100 ^ {2}}$ Pole

Šablony

Tvar okolí použitý během aktualizací závisí na samotné aplikaci. Nejběžnější šablony jsou 2D nebo 3D verze sousedství von Neumann a Moore sousedství. Výše uvedený příklad používá 2D von Neumannovu šablonu, zatímco kódy LBM obecně používají jeho 3D variantu. Conwayova hra o život používá 2D Moore sousedství. To znamená, že další šablony, například 25bodová šablona pro šíření seismických vln^[5] lze také najít.

9bodový 2D vzorník

5bodový 2D vzorník

7bodový 3D vzorník

25bodový 3D vzorník

Výběr šablon používaných v různých vědeckých aplikacích.

Problémy s implementací

Mnoho simulačních kódů může být formulováno přirozeně jako ISL. Vzhledem k tomu, že výpočetní čas a spotřeba paměti rostou lineárně s počtem prvků pole, má pro výzkum zásadní význam paralelní implementace ISL.^[6] To je náročné, protože výpočty jsou pevně spojeny (kvůli aktualizaci buněk v závislosti na sousedních buňkách) a většina ISL je vázána na paměť (tj. Poměr přístupů k paměti k výpočtům je vysoký).^[7] Pro efektivní provádění ISL byly prozkoumány prakticky všechny současné paralelní architektury;^[8] momentálně GPGPU se ukázaly jako nejúčinnější.^[9]

Knihovny

Kvůli oběma významům ISL pro počítačové simulace a jejich vysoké výpočetní požadavky, existuje řada snah zaměřených na vytvoření opakovaně použitelných knihoven na podporu vědců při provádění výpočtů založených na vzorcích. Knihovny se většinou zabývají paralelizací, ale mohou řešit i další výzvy, jako je IO, řízení a kontrolní bod. Mohou být klasifikovány podle jejich API.

Patchové knihovny

Jedná se o tradiční design. Knihovna spravuje sadu n-dimenzionální skalární pole, ke kterým může uživatelský program přistupovat k provádění aktualizací. Knihovna zpracovává synchronizaci hranic (dabovaná zóna duchů nebo halo). Výhodou tohoto rozhraní je, že uživatelský program může smyčku přes pole, což usnadňuje integraci staršího kódu ^[10]. Nevýhodou je, že knihovna nemůže zpracovat blokování mezipaměti (protože to musí být provedeno v rámci smyček^[11]) nebo zabalení volání API pro akcelerátory (např. prostřednictvím CUDA nebo OpenCL). Mezi implementace patří Kaktus, prostředí pro řešení fyzikálních problémů a waLBerla.

Buněčné knihovny

Tyto knihovny přesouvají rozhraní k aktualizaci jednotlivých simulačních buněk: vystavena je pouze aktuální buňka a její sousedé, např. pomocí metod getter / setter. Výhodou tohoto přístupu je, že knihovna může pevně řídit, které buňky se aktualizují v jakém pořadí, což je užitečné nejen pro implementaci blokování mezipaměti,^[9] ale také ke spuštění stejného kódu na vícejádrových a GPU.^[12] Tento přístup vyžaduje, aby uživatel překompiloval zdrojový kód společně s knihovnou. Jinak by bylo vyžadováno volání funkce pro každou aktualizaci buňky, což by vážně zhoršilo výkon. To je možné pouze u technik, jako jsou šablony tříd nebo metaprogramování, což je také důvod, proč se tento design nachází pouze v novějších knihovnách. Příklady jsou Physis a LibGeoDecomp.

Viz také

• Knihovna Advanced Simulation
• Metoda konečných rozdílů
• Počítačová simulace
• Pětibodová šablona
• Šablona skákání
• Šablona (numerická analýza)

Reference

externí odkazy

• Physis
• LibGeoDecomp
• waLBerla