反復ステンシルループ
Class of data processing algorithms
7 ポイントの 3Dフォン ノイマンスタイルのステンシルの形状。

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

意味

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

より正式には、ISLを次の意味を持つ5つの要素で定義することができます。 [3] ( I , S , S 0 , s , T ) {\displaystyle (I,S,S_{0},s,T)}

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

Iはk次元の整数区間であるため、配列は常に有限正方格子の位相を持ちます。配列はシミュレーション空間とも呼ばれ、個々のセルはインデックス によって識別されます。ステンシルは相対座標の順序付き集合です。各セルについて、隣接するセルのインデックスの組を取得できます。 c ∈ I {\displaystyle c\in I} l {\displaystyle l} c {\displaystyle c} I c {\displaystyle I_{c}}

I c = { j ∣ ∃ x ∈ s : j = c + x } {\displaystyle I_{c}=\{j\mid \exists x\in s:j=c+x\}\,}

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

N i ( c ) = ( s 1 , … , s l )  with  s j = S i ( I c ( j ) ) {\displaystyle N_{i}(c)=(s_{1},\ldots ,s_{l}){\text{ with }}s_{j}=S_{i}(I_{c}(j))\,}

これは、次のタイムステップでのシステムの状態を定義するために必要なすべてです。 S i + 1 : Z k → S {\displaystyle S_{i+1}\colon \mathbb {Z} ^{k}\to S} i ∈ N {\displaystyle i\in \mathbb {N} }

S i + 1 ( c ) = { T ( N i ( c ) ) , c ∈ I S i ( c ) , c ∈ Z k ∖ I {\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}}}

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

I c = { j ∣ ∃ x ∈ s : j = ( ( c + x ) mod ( n 1 , … , n k ) ) } {\displaystyle I_{c}=\{j\mid \exists x\in s:j=((c+x)\mod (n_{1},\ldots ,n_{k}))\}}

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

例: 2Dヤコビ反復法

2D 配列内の選択されたセルのデータ依存関係。

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

I = [ 0 , … , 99 ] 2 S = R S 0 : Z 2 → R S 0 ( ( x , y ) ) = { 1 , x < 0 0 , 0 ≤ x < 100 1 , x ≥ 100 s = ( ( 0 , − 1 ) , ( − 1 , 0 ) , ( 1 , 0 ) , ( 0 , 1 ) ) T : R 4 → R T ( ( x 1 , x 2 , x 3 , x 4 ) ) = 0.25 ⋅ ( x 1 + x 2 + x 3 + x 4 ) {\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ヤコビ反復法 100 2 {\displaystyle 100^{2}}

ステンシル

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

さまざまな科学的アプリケーションで使用されるステンシルの選択。

実装上の問題

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

図書館

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

パッチベースのライブラリ

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

細胞ベースのライブラリ

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

参考文献

  1. ^ abc Roth, Gerald et al. (1997) Proceedings of SC'97: High Performance Networking and Computing. Compiling Stencils in High Performance Fortran.
  2. ^ abcd Sloot, Peter MA et al. (2002年5月28日) Computational Science – ICCS 2002: International Conference, Amsterdam, the Netherlands, April 21–24, 2002. Proceedings, Part I. Page 843. Publisher: Springer. ISBN 3-540-43591-3。
  3. ^ abc フェイ、ディートマー他。 (2010) グリッド コンピューティング: 計算科学のための基礎技術。ページ 439。出版社: Springer。ISBN 3-540-79746-7
  4. ^ Yang, Laurence T.; Guo, Minyi. (2005年8月12日) High-Performance Computing: Paradigm and Infrastructure. 221ページ. 出版社: Wiley-Interscience. ISBN 0-471-65471-X
  5. ^ Micikevicius, Paulius et al. (2009) CUDAを用いたGPU上での3D差分計算 Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units ISBN 978-1-60558-517-8
  6. ^ Datta, Kaushik (2009) キャッシュベースマルチコアプラットフォーム向けステンシルコードの自動チューニング Archived 2012-10-08 at the Wayback Machine , Ph.D. Thesis
  7. ^ Wellein, G et al. (2009) マルチコア対応ウェーブフロント並列化によるステンシル計算の効率的な時間的ブロッキング、第33回IEEE国際コンピュータソフトウェアおよびアプリケーション会議、COMPSAC 2009
  8. ^ Datta, Kaushik et al. (2008) 最先端のマルチコアアーキテクチャにおけるステンシル計算の最適化と自動チューニング、 SC '08 Proceedings of the 2008 ACM/IEEE conference on Supercomputing
  9. ^ ab Schäfer, Andreas および Fey, Dietmar (2011) GPGPU 向け高性能ステンシルコードアルゴリズム、国際計算科学会議議事録、ICCS 2011
  10. ^ S. Donath、J. Götz、C. Feichtinger、K. Iglberger、U. Rüde (2010) waLBerla: 数千のプロセッサを搭載した Itanium ベースシステムの最適化、科学技術における高性能コンピューティング、ガルヒング/ミュンヘン 2009
  11. ^ Nguyen, Anthony et al. (2010) 3.5-D Blocking Optimization for Stencil Computations on Modern CPUs and GPUs、SC '10 Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis
  12. ^ 丸山直也、野村達夫、佐藤健人、松岡聡 (2011) Physis: 大規模 GPU アクセラレーションスーパーコンピュータにおけるステンシル計算のための暗黙的並列プログラミングモデル、SC '11 Proceedings of the 2011 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis
  • フィシス
  • LibGeoDecomp 2022年6月25日アーカイブ - Wayback Machine
  • ワルベルラ
Retrieved from "https://en.wikipedia.org/w/index.php?title=Iterative_Stencil_Loops&oldid=1322373399"