反復ステンシルループ

反復ステンシルループ（ISL）またはステンシル計算は、ステンシルと呼ばれる固定パターンに従って配列要素を 更新する数値データ処理ソリューション^[1]の一種です。 ^[2]これらは、科学技術アプリケーションのコンテキストでの数値流体力学などのコンピュータシミュレーション で最も一般的に使用されています 。その他の注目すべき例としては、偏微分方程式の解法^[1]、ヤコビカーネル、ガウス-ザイデル法^[2]、画像処理^[1]、セルオートマトン^[3]などがあります。配列の規則的な構造により、ステンシル手法は有限要素法 などの他のモデリング手法とは一線を画しています。規則的なグリッドで動作するほとんどの有限差分コードは、ISLとして定式化できます。

ISLは、与えられた配列に対して一連のスイープ（タイムステップと呼ばれる）を実行します。^[2]一般的に、これは2次元または3次元の規則的なグリッドです。^[3]配列の要素は、多くの場合セルと呼ばれます。各タイムステップで、すべての配列要素が更新されます。^[2]固定パターン（ステンシル）内の隣接する配列要素を使用して、各セルの新しい値が計算されます。ほとんどの場合、境界値は変更されませんが、場合によっては（LBMコードなど）、計算中に境界値を調整する必要があります。ステンシルは各要素に対して同じであるため、データアクセスのパターンが繰り返されます。^[4]

より正式には、ISLを次の意味を持つ5つの要素から構成される集合として定義することができる。 ^[3]${\displaystyle (I,S,S_{0},s,T)}$

• ${\displaystyle I=\prod _{i=1}^{k}[0,\ldots ,n_{i}]}$インデックス セットです。配列のトポロジを定義します。
• ${\displaystyle S}$状態のセット（必ずしも有限ではない）であり、各セルは任意のタイムステップでその状態のいずれかを取る可能性があります。
• ${\displaystyle S_{0}\colon \mathbb {Z} ^{k}\to S}$時刻 0 におけるシステムの初期状態を定義します。
• ${\displaystyle s\in \prod _{i=1}^{l}\mathbb {Z} ^{k}}$ステンシル自体であり、近隣地域の実際の形状を記述します。ステンシルには要素があります。${\displaystyle l}$
• ${\displaystyle T\colon S^{l}\to S}$セルの隣接セルに応じてセルの新しい状態を決定するために使用される遷移関数です。

I はk次元の整数区間なので、配列は常に有限の規則的なグリッドのトポロジを持ちます。配列はシミュレーション空間とも呼ばれ、個々のセルはインデックスによって識別されます。ステンシルは相対座標の順序付きセットです。各セルについて、隣接するインデックスの組を取得できます。${\displaystyle c\in I}$${\displaystyle l}$${\displaystyle c}$${\displaystyle I_{c}}$

${\displaystyle I_{c}=\{j\mid \exists x\in s:j=c+x\}\,}$

それらの状態は、タプルを対応する状態のタプルにマッピングすることによって与えられます。ここで、は次のように定義されます。 ${\displaystyle I_{c}}$${\displaystyle N_{i}(c)}$${\displaystyle N_{i}\colon I\to S^{l}}$

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

これは、次の時間ステップにおけるシステムの状態を定義するために必要なすべてです。 ${\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\in I\\S_{i}(c),&c\in \mathbb {Z} ^{k}\setminus I\end{cases}}}$

境界条件も設定する必要があるため、 は上で定義され、 上だけでは定義されないことに注意してください。 の要素は、トロイダルトポロジーを実現するために、シミュレーション空間の次元を法とするベクトルの加算によって定義されることがあります。 ${\displaystyle S_{i}}$${\displaystyle \mathbb {Z} ^{k}}$${\displaystyle I}$${\displaystyle I_{c}}$

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

これは、特定の物理モデルを簡素化する周期境界条件を実装するのに役立つ場合があります。

正式な定義を説明するために、2 次元のヤコビ反復法がどのように定義されるかを見てみましょう。更新関数は、セルの 4 つの隣接セルの算術平均を計算します。この場合、初期解は 0 です。左と右の境界は 1 に固定され、上限と下限は 0 に設定されます。十分な回数の反復処理を実行すると、システムは鞍型に収束します。

${\displaystyle {\begin{aligned}I&=[0,\ldots ,99]^{2}\\S&=\mathbb {R} \\S_{0}&:\mathbb {Z} ^{2}\to \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{aligned}}}$

配列上の 2D ヤコビ反復${\displaystyle 100^{2}}$

更新中に使用される近傍の形状は、アプリケーション自体によって異なります。最も一般的なステンシルは、フォン ノイマン近傍とムーア近傍の 2D または 3D バージョンです。上記の例では 2D フォン ノイマン ステンシルを使用していますが、LBM コードでは通常 3D バリアントを使用します。コンウェイのライフ ゲームでは 2D ムーア近傍を使用しています。ただし、地震波伝播用の 25 ポイント ステンシル^[5]など、他のステンシルも見つかります。

多くのシミュレーションコードは、自然にISLとして定式化できます。計算時間とメモリ消費量は配列要素の数に比例して増加するため、ISLの並列実装は研究にとって極めて重要です。^[6] 計算は密結合されており（セルの更新は隣接セルに依存するため）、ほとんどのISLはメモリに縛られている（つまり、計算に対するメモリアクセスの比率が高い）ため、これは困難です。^[7] 事実上、現在のすべての並列アーキテクチャは、ISLを効率的に実行するために研究されてきました。^[8] 現時点では、GPGPUが最も効率的であることが証明されています。^[9]

コンピュータ シミュレーションにおける ISL の重要性と高い計算要件の両方から、ステンシル ベースの計算を実行する科学者をサポートする再利用可能なライブラリの作成を目指す取り組みが数多く行われています。ライブラリは主に並列化に関係していますが、IO、ステアリング、チェックポイントなどの他の課題にも取り組む場合があります。ライブラリは API によって分類できます。

これは伝統的な設計です。ライブラリはn次元のスカラー配列のセットを管理し、ユーザープログラムはこれにアクセスして更新を実行できます。ライブラリは境界 (ゴーストゾーンまたはハローと呼ばれる) の同期を処理します。このインターフェイスの利点は、ユーザープログラムが配列をループできるため、レガシーコード^{[10]を簡単に統合できることです。欠点は、ライブラリがキャッシュブロッキング (ループ内で実行する必要があるため[11]} ) やアクセラレータの API 呼び出しのラッピング (CUDA または OpenCL 経由など) を 処理できないことです。実装には、物理​​学の問題解決環境である Cactus や waLBerla などがあります。

これらのライブラリは、インターフェイスを単一のシミュレーションセルの更新に移動します。つまり、現在のセルとその隣接セルのみが公開されます (getter/setter メソッドなどを介して)。このアプローチの利点は、ライブラリがどのセルをどの順序で更新するかを厳密に制御できることです。これは、キャッシュブロッキングを実装するだけでなく、^[9] 同じコードをマルチコアと GPU で実行する場合にも役立ちます。^[12]このアプローチでは、ユーザーはライブラリと一緒にソースコードを再コンパイルする必要があります。そうしないと、セルの更新ごとに関数呼び出しが必要になり、パフォーマンスが大幅に低下します。これは、クラステンプレートやメタプログラミングなどの手法でのみ実現可能であり、この設計が新しいライブラリにのみ見られるのもこのためです。例としては、Physis や LibGeoDecomp があります。

• 高度なシミュレーションライブラリ
• 差分法
• コンピュータシミュレーション
• 5点ステンシル
• コンパクトステンシル
• 非コンパクトステンシル
• ステンシルジャンプ
• ステンシル（数値解析）

• フィシス
• LibGeoDecomp は 2022-06-25 にWayback Machineにアーカイブされました
• ワルベルラ