Boucles de pochoir itératives

Les boucles itératives de stencil (ISL), ou calculs de stencil, constituent une classe de solutions de traitement numérique de données qui mettent à jour les éléments d'un tableau selon un motif fixe, appelé stencil . Elles sont fréquemment utilisées dans les simulations informatiques , notamment en dynamique des fluides numérique dans le cadre d'applications scientifiques et d'ingénierie. Parmi les autres exemples notables, citons la résolution d'équations aux dérivées partielles , le noyau de Jacobi , la méthode de Gauss-Seidel , le traitement d'images et les automates cellulaires . La structure régulière des tableaux distingue les techniques de stencil d'autres méthodes de modélisation telles que la méthode des éléments finis . La plupart des codes aux différences finies fonctionnant sur des grilles régulières peuvent être formulés comme des ISL.

Définition

Les ISL effectuent une séquence de balayages (appelés pas de temps) sur un tableau donné. Il s'agit généralement d'une grille régulière à 2 ou 3 dimensions. Les éléments du tableau sont souvent appelés cellules. À chaque pas de temps, tous les éléments du tableau sont mis à jour. En utilisant les éléments voisins du tableau selon un motif fixe (le stencil), la nouvelle valeur de chaque cellule est calculée. Dans la plupart des cas, les valeurs limites restent inchangées, mais dans certains cas (par exemple, pour les codes LBM ), elles doivent également être ajustées pendant le calcul. Le stencil étant identique pour chaque élément, le schéma d'accès aux données est répété.

Plus formellement, nous pouvons définir les ISL comme un quintuplet ${\displaystyle (I,S,S_{0},s,T) <semantics><mrow><mstyle><mo>(</mo><mi>je</mi><mo>,</mo><mi>S</mi><mo>,</mo><msub><mi>S</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mi>s</mi><mo>,</mo><mi>T</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (I,S,S_{0},s,T)}</annotation></semantics></math><img src=$

${\displaystyle I=\prod _{i=1}^{k}[0,\ldots ,n_{i}] <semantics><mrow><mstyle><mi>je</mi><mo>=</mo><munderover><mo>∏</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>k</mi></mrow></munderover><mo>[</mo><mn>0</mn><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>n</mi><mrow><mi>je</mi></mrow></msub><mo>]</mo></mstyle></mrow><annotation>{\displaystyle I=\prod _{i=1}^{k}[0,\ldots ,n_{i}]}</annotation></semantics></math><img src=$
${\displaystyle S <semantics><mrow><mstyle><mi>S</mi></mstyle></mrow><annotation>{\displaystyle S}</annotation></semantics></math><img src=$
${\displaystyle S_{0}\colon \mathbb {Z} ^{k} o S <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mn>0</mn></mrow></msub><mo>:</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>k</mi></mrow></msup><mo>→</mo><mi>S</mi></mstyle></mrow><annotation>{\displaystyle S_{0}\colon \mathbb {Z} ^{k} o S}</annotation></semantics></math><img src=$
${\displaystyle s\in \prod _{i=1}^{l}\mathbb {Z} ^{k <semantics><mrow><mstyle><mi>s</mi><mo>∈</mo><munderover><mo>∏</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>l</mi></mrow></munderover><msup><mrow><mi>Z</mi></mrow><mrow><mi>k</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle s\in \prod _{i=1}^{l}\mathbb {Z} ^{k}}</annotation></semantics></math><img src=$ ${\displaystyle l <semantics><mrow><mstyle><mi>l</mi></mstyle></mrow><annotation>{\displaystyle l}</annotation></semantics></math><img src=$
${\displaystyle T\colon S^{l} o S <semantics><mrow><mstyle><mi>T</mi><mo>:</mo><msup><mi>S</mi><mrow><mi>l</mi></mrow></msup><mo>→</mo><mi>S</mi></mstyle></mrow><annotation>{\displaystyle T\colon S^{l} o S}</annotation></semantics></math><img src=$

Puisque I est un intervalle d'entiers à k dimensions, le tableau aura toujours la topologie d'une grille régulière finie. Ce tableau est également appelé espace de simulation et chaque cellule est identifiée par son indice. ${\displaystyle c\in I <semantics><mrow><mstyle><mi>c</mi><mo>∈</mo><mi>je</mi></mstyle></mrow><annotation>{\displaystyle c\in I}</annotation></semantics></math><img src=$ ${\displaystyle l <semantics><mrow><mstyle><mi>l</mi></mstyle></mrow><annotation>{\displaystyle l}</annotation></semantics></math><img src=$ ${\displaystyle c <semantics><mrow><mstyle><mi>c</mi></mstyle></mrow><annotation>{\displaystyle c}</annotation></semantics></math><img src=$ ${\displaystyle I_{c <semantics><mrow><mstyle><msub><mi>je</mi><mrow><mi>c</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle I_{c}}</annotation></semantics></math><img src=$

{\displaystyle I_{c}=\{j\mid \exists x\in s:j=c+x\}\, <semantics><mrow><mstyle><msub><mi>je</mi><mrow><mi>c</mi></mrow></msub><mo>=</mo><mo>{</mo><mi>j</mi><mo>∣</mo><mi>∃</mi><mi>x</mi><mo>∈</mo><mi>s</mi><mo>:</mo><mi>j</mi><mo>=</mo><mi>c</mi><mo>+</mo><mi>x</mi><mo>}</mo><mspace></mspace></mstyle></mrow><annotation>{\displaystyle I_{c}=\{j\mid \exists x\in s:j=c+x\}\,}</annotation></semantics></math></span><img src=

Leurs états sont donnés par la mise en correspondance du tuple ${\displaystyle I_{c <semantics><mrow><mstyle><msub><mi>je</mi><mrow><mi>c</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle I_{c}}</annotation></semantics></math><img src=$ ${\displaystyle N_{i}(c) <semantics><mrow><mstyle><msub><mi>N</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>c</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle N_{i}(c)}</annotation></semantics></math><img src=$ ${\displaystyle N_{i}\colon I o S^{l <semantics><mrow><mstyle><msub><mi>N</mi><mrow><mi>je</mi></mrow></msub><mo>:</mo><mi>je</mi><mo>→</mo><msup><mi>S</mi><mrow><mi>l</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle N_{i}\colon I o S^{l}}</annotation></semantics></math><img src=$

{\displaystyle N_{i}(c)=(s_{1},\ldots ,s_{l}){ ext{ with }}s_{j}=S_{i}(I_{c}(j))\, <semantics><mrow><mstyle><msub><mi>N</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>c</mi><mo>)</mo><mo>=</mo><mo>(</mo><msub><mi>s</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>s</mi><mrow><mi>l</mi></mrow></msub><mo>)</mo><mrow><mtext> avec </mtext></mrow><msub><mi>s</mi><mrow><mi>j</mi></mrow></msub><mo>=</mo><msub><mi>S</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><msub><mi>je</mi><mrow><mi>c</mi></mrow></msub><mo>(</mo><mi>j</mi><mo>)</mo><mo>)</mo><mspace></mspace></mstyle></mrow><annotation>{\displaystyle N_{i}(c)=(s_{1},\ldots ,s_{l}){ ext{ avec }}s_{j}=S_{i}(I_{c}(j))\,}</annotation></semantics></math></span><img src=

C'est tout ce dont nous avons besoin pour définir l'état du système pour les étapes temporelles suivantes. ${\displaystyle S_{i+1}\colon \mathbb {Z} ^{k} o S <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>:</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>k</mi></mrow></msup><mo>→</mo><mi>S</mi></mstyle></mrow><annotation>{\displaystyle S_{i+1}\colon \mathbb {Z} ^{k} o S}</annotation></semantics></math><img src=$ ${\displaystyle i\in \mathbb {N} <semantics><mrow><mstyle><mi>je</mi><mo>∈</mo><mrow><mi>N</mi></mrow></mstyle></mrow><annotation>{\displaystyle i\in \mathbb {N} }</annotation></semantics></math><img src=$

{\displaystyle S_{i+1}(c)={\begin{cases}T(N_{i}(c)),&c\in I\\S_{i}(c),&c\in \mathbb {Z} ^{k}\setminus I\end{cases <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>(</mo><mi>c</mi><mo>)</mo><mo>=</mo><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mi>T</mi><mo>(</mo><msub><mi>N</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>c</mi><mo>)</mo><mo>)</mo><mo>,</mo></mtd><mtd><mi>c</mi><mo>∈</mo><mi>je</mi></mtd></mtr><mtr><mtd><msub><mi>S</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>c</mi><mo>)</mo><mo>,</mo></mtd><mtd><mi>c</mi><mo>∈</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>k</mi></mrow></msup><mo>∖</mo><mi>je</mi></mtd></mtr></mtable><mo></mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle S_{i+1}(c)={\begin{cases}T(N_{i}(c)),&c\in I\\S_{i}(c),&c\in \mathbb {Z} ^{k}\setminus I\end{cases}}}</annotation></semantics></math></span><img src=

Noter que ${\displaystyle S_{i <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle S_{i}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {Z} ^{k <semantics><mrow><mstyle><msup><mrow><mi>Z</mi></mrow><mrow><mi>k</mi></mrow></msup></mstyle></mrow><annotation>{ displaystyle mathbb {Z} ^ {k}}</annotation></semantics></math><img src=$ ${\displaystyle I <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle Je}</annotation></semantics></math><img src=$ ${\displaystyle I_{c <semantics><mrow><mstyle><msub><mi>je</mi><mrow><mi>c</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle I_{c}}</annotation></semantics></math><img src=$

{\displaystyle I_{c}=\{j\mid \exists x\in s:j=((c+x)\mod (n_{1},\ldots ,n_{k}))\ <semantics><mrow><mstyle><msub><mi>je</mi><mrow><mi>c</mi></mrow></msub><mo>=</mo><mo>{</mo><mi>j</mi><mo>∣</mo><mi>∃</mi><mi>x</mi><mo>∈</mo><mi>s</mi><mo>:</mo><mi>j</mi><mo>=</mo><mo>(</mo><mo>(</mo><mi>c</mi><mo>+</mo><mi>x</mi><mo>)</mo><mspace></mspace><mi>mod</mi><mspace></mspace><mspace></mspace><mo>(</mo><msub><mi>n</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>n</mi><mrow><mi>k</mi></mrow></msub><mo>)</mo><mo>)</mo><mo>}</mo></mstyle></mrow><annotation>{\displaystyle I_{c}=\{j\mid \exists x\in s:j=((c+x)\mod (n_{1},\ldots ,n_{k}))\}}</annotation></semantics></math></span><img src=

Cela peut s'avérer utile pour la mise en œuvre de conditions aux limites périodiques , ce qui simplifie certains modèles physiques.

Exemple : Itération de Jacobi en 2D

Pour illustrer la définition formelle, examinons comment définir une itération de Jacobi bidimensionnelle . La fonction de mise à jour calcule la moyenne arithmétique des quatre voisins d'une cellule. Dans ce cas, la solution initiale est égale à 0. Les bornes gauche et droite sont fixées à 1, tandis que les bornes supérieure et inférieure sont fixées à 0. Après un nombre suffisant d'itérations, le système converge vers un point en forme de selle.

{\displaystyle {\begin{aligned}I&=[0,\ldots ,99]^{2}\\S&=\mathbb {R} \\S_{0}&:\mathbb {Z} ^{2} o \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} o \mathbb {R} \\T((x_{1},x_{2},x_{3},x_{4}))&=0.25\cdot (x_{1}+x_{2}+x_{3}+x_{4})\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>je</mi></mtd><mtd><mi></mi><mo>=</mo><mo>[</mo><mn>0</mn><mo>,</mo><mo>…</mo><mo>,</mo><mn>99</mn><msup><mo>]</mo><mrow><mn>2</mn></mrow></msup></mtd></mtr><mtr><mtd><mi>S</mi></mtd><mtd><mi></mi><mo>=</mo><mrow><mi>R</mi></mrow></mtd></mtr><mtr><mtd><msub><mi>S</mi><mrow><mn>0</mn></mrow></msub></mtd><mtd><mi></mi><mo>:</mo><msup><mrow><mi>Z</mi></mrow><mrow><mn>2</mn></mrow></msup><mo>→</mo><mrow><mi>R</mi></mrow></mtd></mtr><mtr><mtd><msub><mi>S</mi><mrow><mn>0</mn></mrow></msub><mo>(</mo><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>)</mo><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mn>1</mn><mo>,</mo></mtd><mtd><mi>x</mi><mo><</mo><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn><mo>,</mo></mtd><mtd><mn>0</mn><mo>≤</mo><mi>x</mi><mo><</mo><mn>100</mn></mtd></mtr><mtr><mtd><mn>1</mn><mo>,</mo></mtd><mtd><mi>x</mi><mo>≥</mo><mn>100</mn></mtd></mtr></mtable><mo></mo></mrow></mrow></mtd></mtr><mtr><mtd><mi>s</mi></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mo>(</mo><mn>0</mn><mo>,</mo><mo>−</mo><mn>1</mn><mo>)</mo><mo>,</mo><mo>(</mo><mo>−</mo><mn>1</mn><mo>,</mo><mn>0</mn><mo>)</mo><mo>,</mo><mo>(</mo><mn>1</mn><mo>,</mo><mn>0</mn><mo>)</mo><mo>,</mo><mo>(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>)</mo><mo>)</mo></mtd></mtr><mtr><mtd><mi>T</mi></mtd><mtd><mi></mi><mo>:</mo><msup><mrow><mi>R</mi></mrow><mrow><mn>4</mn></mrow></msup><mo>→</mo><mrow><mi>R</mi></mrow></mtd></mtr><mtr><mtd><mi>T</mi><mo>(</mo><mo>(</mo><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mn>4</mn></mrow></msub><mo>)</mo><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mn>0,25</mn><mo>⋅</mo><mo>(</mo><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub><mo>+</mo><msub><mi>x</mi><mrow><mn>3</mn></mrow></msub><mo>+</mo><msub><mi>x</mi><mrow><mn>4</mn></mrow></msub><mo>)</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}I&=[0,\ldots ,99]^{2}\\S&=\mathbb {R} \\S_{0}&:\mathbb {Z} ^{2} o \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} o \mathbb {R} \\T((x_{1},x_{2},x_{3},x_{4}))&=0.25\cdot (x_{1}+x_{2}+x_{3}+x_{4})\end{aligned}}}</annotation></semantics></math></span><img src=

{\displaystyle S_{0 <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mn>0</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle S_{0}}</annotation></semantics></math></span><img src=

{\displaystyle S_{200 <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mn>200</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle S_{200}}</annotation></semantics></math></span><img src=

{\displaystyle S_{400 <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mn>400</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle S_{400}}</annotation></semantics></math></span><img src=

{\displaystyle S_{600 <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mn>600</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle S_{600}}</annotation></semantics></math></span><img src=

{\displaystyle S_{800 <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mn>800</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle S_{800}}</annotation></semantics></math></span><img src=

{\displaystyle S_{1000 <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mn>1000</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle S_{1000}}</annotation></semantics></math></span><img src=

Itération de Jacobi 2D sur un

{\displaystyle 100^{2 <semantics><mrow><mstyle><msup><mn>100</mn><mrow><mn>2</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle 100^{2}}</annotation></semantics></math></span><img src=

Pochoirs

La forme du voisinage utilisé lors des mises à jour dépend de l'application. Les modèles les plus courants sont les versions 2D et 3D des voisinages de von Neumann et de Moore . L'exemple ci-dessus utilise un modèle 2D de von Neumann, tandis que les codes LBM utilisent généralement sa variante 3D. Le Jeu de la Vie de Conway utilise le voisinage 2D de Moore. D'autres modèles existent également , comme un modèle à 25 points pour la propagation des ondes sismiques

Boucles de pochoir itératives

Définition

Exemple : Itération de Jacobi en 2D

Pochoirs

Problèmes de mise en œuvre

Bibliothèques

Bibliothèques basées sur des patchs

Bibliothèques cellulaires