Iterative stencilsløjfer - Iterative Stencil Loops

Formen på en 7-punkts 3D von Neumann- stil stencil.

Iterative stencil loops (ISL'er) er en klasse af numerisk databehandlingsløsning, der opdaterer arrayelementer i henhold til et fast mønster, kaldet en stencil. De findes mest i computersimuleringer , fx til beregningsvæskedynamik i forbindelse med videnskabelige og tekniske applikationer. Andre bemærkelsesværdige eksempler inkluderer løsning af delvise differentialligninger , Jacobi- kernen, Gauss-Seidel-metoden , billedbehandling og cellulær automat . Arrangørernes regelmæssige struktur adskiller stencilteknikker fra andre modelleringsmetoder såsom Finite element-metoden . De fleste begrænsede forskellighedskoder, der fungerer på almindelige net, kan formuleres som ISL'er.

Definition

ISL'er udfører en sekvens af fejninger (kaldet timesteps) gennem et givet array. Generelt er dette et 2- eller 3-dimensionelt regulært gitter. Elementerne i arrays kaldes ofte celler. I hvert tidsrum opdateres alle matrixelementer. Ved hjælp af tilstødende matrixelementer i et fast mønster (stencilen) beregnes hver celles nye værdi. I de fleste tilfælde er grænseværdierne uændrede, men i nogle tilfælde (f.eks. LBM-koder ) skal disse også justeres under beregningen. Da stencilen er den samme for hvert element, gentages mønsteret for datatilgang.

Mere formelt kan vi definere ISL'er som en 5-tuple med følgende betydning: ${\ displaystyle (I, S, S_ {0}, s, T)}$

• ${\ displaystyle I = \ prod _ {i = 1} ^ {k} [0, \ ldots, n_ {i}]}$ er indekset. Den definerer arrayets topologi.
• ${\ displaystyle S}$ er det (ikke nødvendigvis endelige) sæt af stater, hvoraf hver celle kan påtage sig et givet tidspunkt.
• ${\ displaystyle S_ {0} \ colon \ mathbb {Z} ^ {k} \ to S}$ definerer systemets starttilstand på tidspunktet 0.
• ${\ displaystyle s \ in \ prod _ {i = 1} ^ {l} \ mathbb {Z} ^ {k}}$ er stencilen selv og beskriver kvarterets faktiske form. Der er elementer i stencilen. ${\ displaystyle l}$
• ${\ displaystyle T \ colon S ^ {l} \ to S}$ er overgangsfunktionen, der bruges til at bestemme en celles nye tilstand, afhængigt af dens naboer.

Da jeg er et k -dimensionelt heltalinterval, vil arrayet altid have topologien for et endeligt regelmæssigt gitter. Arrayet kaldes også simuleringsrum og individuelle celler identificeres ved deres indeks . Stencilen er et ordnet sæt relative koordinater. Vi kan nu for hver celle indhente tuplen for dens naboer ${\ displaystyle c \ i I}$${\ displaystyle l}$${\ displaystyle c}$${\ displaystyle I_ {c}}$

${\ displaystyle I_ {c} = \ {j \ mid \ eksisterer x \ i s: j = c + x \} \,}$

Deres stater gives ved at kortlægge tuplen til den tilsvarende tuple af stater , hvor defineres som følger: ${\ displaystyle I_ {c}}$${\ displaystyle N_ {i} (c)}$${\ displaystyle N_ {i} \ colon I \ til S ^ {l}}$

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

Dette er alt, hvad vi har brug for for at definere systemets tilstand i følgende tidstrin med : ${\ displaystyle S_ {i + 1} \ colon \ mathbb {Z} ^ {k} \ to S}$${\ displaystyle i \ in \ mathbb {N}}$

${\ displaystyle S_ {i + 1} (c) = {\ begin {cases} T (N_ {i} (c)), & c \ i I \\ S_ {i} (c), & c \ i \ mathbb { Z} ^ {k} \ setminus I \ end {cases}}}$

Bemærk, at der er defineret på og ikke kun på, da også randbetingelserne skal indstilles. Undertiden kan elementerne defineres ved hjælp af en vektortilføjelsesmodul til simuleringsrummets dimension for at realisere toroidetopologier: ${\ displaystyle S_ {i}}$${\ displaystyle \ mathbb {Z} ^ {k}}$${\ displaystyle I}$${\ displaystyle I_ {c}}$

${\ displaystyle I_ {c} = \ {j \ mid \ eksisterer x \ i s: j = ((c + x) \ mod (n_ {1}, \ ldots, n_ {k})) \}}$

Dette kan være nyttigt til implementering af periodiske randbetingelser , hvilket forenkler visse fysiske modeller.

Eksempel: 2D Jacobi-iteration

Dataafhængighed for en valgt celle i 2D-arrayet.

For at illustrere den formelle definition vil vi se på, hvordan en todimensional Jacobi- iteration kan defineres. Opdateringsfunktionen beregner det aritmetiske gennemsnit af en celles fire naboer. I dette tilfælde sætter vi afsted med en indledende løsning på 0. Den venstre og højre grænse er fastgjort til 1, mens de øvre og nedre grænser er sat til 0. Efter et tilstrækkeligt antal iterationer konvergerer systemet mod en sadelform.

${\ displaystyle {\ begin {align} I & = [0, \ ldots, 99] ^ {2} \\ S & = \ mathbb {R} \\ S_ {0} &: \ mathbb {Z} ^ {2} \ til \ mathbb {R} \\ S_ {0} ((x, y)) & = {\ begin {cases} 1, & x <0 \\ 0, & 0 \ leq x <100 \\ 1, & x \ geq 100 \ end {cases}} \\ s & = ((0, -1), (- 1,0), (1,0), (0,1)) \\ T & \ colon \ mathbb {R} ^ {4 } \ to \ mathbb {R} \\ T ((x_ {1}, x_ {2}, x_ {3}, x_ {4})) & = 0,25 \ cdot (x_ {1} + x_ {2} + x_ {3} + x_ {4}) \ end {justeret}}}$

${\ displaystyle S_ {0}}$

${\ displaystyle S_ {200}}$

${\ displaystyle S_ {400}}$

${\ displaystyle S_ {600}}$

${\ displaystyle S_ {800}}$

${\ displaystyle S_ {1000}}$

2D Jacobi Iteration on a Array ${\ displaystyle 100 ^ {2}}$

Stencils

Formen på det kvarter, der blev brugt under opdateringerne, afhænger af selve applikationen. De mest almindelige stencils er 2D- eller 3D-versionerne af von Neumann-kvarteret og Moore-kvarteret . Eksemplet ovenfor bruger en 2D von Neumann-stencil, mens LBM-koder generelt bruger dens 3D-variant. Conways Game of Life bruger 2D Moore-kvarteret. Når det er sagt, kan også andre stencils såsom en 25-punkts stencil til seismisk bølgeforplantning findes.

9-punkts 2D stencil

5-punkts 2D stencil

7-punkts 3D-stencil

25-punkts 3D-stencil

Et udvalg af stencils anvendt i forskellige videnskabelige anvendelser.

Implementeringsspørgsmål

Mange simuleringskoder kan formuleres naturligt som ISL'er. Da computertid og hukommelsesforbrug vokser lineært med antallet af array-elementer, er parallelle implementeringer af ISL'er af største vigtighed for forskning. Dette er udfordrende, da beregningerne er tæt koblet (på grund af celleopdateringer afhængigt af naboceller), og de fleste ISL'er er hukommelsesbundne (dvs. forholdet mellem hukommelsesadgang til beregninger er højt). Næsten alle nuværende parallelle arkitekturer er blevet undersøgt for at udføre ISL'er effektivt; i øjeblikket har GPGPU'er vist sig at være mest effektive.

Biblioteker

På grund af både ISL'ers betydning for computersimuleringer og deres høje beregningskrav, er der en række bestræbelser, der sigter mod at skabe genanvendelige biblioteker til at støtte forskere i at udføre stencilbaserede beregninger. Bibliotekerne er for det meste bekymrede over paralleliseringen, men kan også tackle andre udfordringer, såsom IO, styring og kontrolpunkt . De kan klassificeres efter deres API.

Patch-baserede biblioteker

Dette er et traditionelt design. Biblioteket administrerer et sæt n- dimensionelle skalararrays, som brugerprogrammet kan få adgang til for at udføre opdateringer. Biblioteket håndterer synkroniseringen af ​​grænserne (kaldet spøgelseszone eller glorie). Fordelen ved denne grænseflade er, at brugerprogrammet kan løbe over arrays, hvilket gør det let at integrere ældre kode. Ulempen er, at biblioteket ikke kan håndtere cache-blokering (da dette skal gøres inden for sløjferne) eller indpakning af API-opkald til acceleratorer (f.eks. Via CUDA eller OpenCL). Implementeringer inkluderer Cactus , et fysik problemløsning miljø og waLBerla .

Cellebaserede biblioteker

Disse biblioteker flytter grænsefladen til opdatering af enkelt simuleringsceller: kun den aktuelle celle og dens naboer udsættes, f.eks. Via getter / setter-metoder. Fordelen ved denne tilgang er, at biblioteket kan kontrollere nøje, hvilke celler der opdateres i hvilken rækkefølge, hvilket ikke kun er nyttigt til implementering af cache-blokering, men også til at køre den samme kode på multi-kerner og GPU'er. Denne tilgang kræver, at brugeren kompilerer kildekoden sammen med biblioteket. Ellers ville der kræves et funktionsopkald til hver celleopdatering, hvilket alvorligt ville forringe ydeevnen. Dette er kun muligt med teknikker som klasseskabeloner eller metaprogrammering , hvilket også er grunden til, at dette design kun findes i nyere biblioteker. Eksempler er Physis og LibGeoDecomp .

Se også

• Avanceret simuleringsbibliotek
• Endelig forskel metode
• Computersimulering
• Fem-punkts stencil
• Stencilspring
• Stencil (numerisk analyse)

Referencer

eksterne links

• Fyse
• LibGeoDecomp
• waLBerla