Takrorlanuvchi Stencil Looplar

Iterativ Stencil Loops (ISL) yoki Stencil hisoblashlari raqamli ma'lumotlarni qayta ishlash echimlarining sinfidir^[1] ular qator elementlarini stensil deb nomlangan muayyan qat'iy namunasiga muvofiq yangilaydi.^[2] Ular eng keng tarqalgan hollarda kompyuter simulyatsiyalari, masalan, ilmiy va muhandislik ilovalari kontekstida hisoblash suyuqlik dinamikasi uchun topiladi. Boshqa diqqatga sazovor misollarga qisman differensial tenglamalari hal etish kiradi,^[1] Jacobi yadrovi, Gauss-Seidel usuli,^[2] tasvirni qayta ishlash[1] va hujayra avtomatlari kiradi.^[3] Arraylarning muntazam tuzilishi, cheklangan element usuli kabi boshqa modellash usullaridan stencil texnikasini ajratib qo'yadi. Oddiy tarmoqlarda ishlaydigan cheklangan farq kodlari aksariyati ISL sifatida formulasiya qilinishi mumkin.

Ta'rif[tahrir | manbasini tahrirlash]

ISLlar ma'lum bir matn orqali sweeps (so'zlangan vaqt qadamlari) ketma-ketini amalga oshiradi. ^[2] Odatda ^[3] 2 yoki 3 o'lchamli muntazam to'plamdir. [1] Arraylarning elementlari ko'pincha hujayralar deb ataladi. Har bir vaqt bosqichida barcha matn elementlari yangilanadi.^[2] Qo'shni matraj elementlaridan foydalanib, har bir hujayra uchun yangi qiymat hisoblab chiqiladi. Ko'p hollarda chegara qiymatlari o'zgarmas qoldiriladi, ammo ba'zi hollarda (masalan, LBM kodlari) ularni hisoblash davomida ham o'zgartirish kerak. Har bir element uchun stensil bir xil ^[4]'lgani uchun ma'lumotlarga kirish usuli takrorlanadi. [1]

Rasmiyroq aytganda, biz ISLlarni 5-tuple sifatida belgilashimiz mumkin $(I,S,S_{0},s,T)$ quyidagi ma'noda: ^[3]

$I=\prod _{i=1}^{k}[0,\ldots ,n_{i}]$ indeks to'plamidir. U massivning topologiyasini belgilaydi.
$S$ har bir hujayra istalgan vaqt oralig'ida qabul qilishi mumkin bo'lgan holatlar to'plami (cheklangan bo'lishi shart emas).
$S_{0}\colon \mathbb {Z} ^{k}\to S$ 0 vaqtida tizimning dastlabki holatini aniqlaydi.
$s\in \prod _{i=1}^{l}\mathbb {Z} ^{k}$ trafaretning o'zi bo'lib, mahallaning haqiqiy shaklini tasvirlaydi. Lar bor $l$ trafaretdagi elementlar.
$T\colon S^{l}\to S$ - qo'shnilariga qarab hujayraning yangi holatini aniqlash uchun ishlatiladigan o'tish funktsiyasi.

I k o'lchamli butun son oralig'i bo'lgani uchun massiv har doim chekli muntazam to'r topologiyasiga ega bo'ladi. Massiv simulyatsiya maydoni deb ham ataladi va alohida hujayralar indekslari bilan aniqlanadi $c\in I$ . Stencil buyurtma qilingan to'plamdir $l$ nisbiy koordinatalar. Endi biz har bir hujayra uchun olishimiz mumkin $c$ qo'shni indekslar to'plami $I_{c}$

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

Ularning holatlari kortejni xaritalash orqali beriladi $I_{c}$ tegishli shtatlar to'plamiga $N_{i}(c)$ , qayerda $N_{i}\colon I\to S^{l}$ quyidagicha aniqlanadi:

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

Bu keyingi vaqt bosqichlari uchun tizim holatini aniqlashimiz kerak bo'lgan yagona narsa $S_{i+1}\colon \mathbb {Z} ^{k}\to S$ bilan $i\in \mathbb {N}$ :

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}}

Shu esta tutilsinki $S_{i}$ da belgilanadi $\mathbb {Z} ^{k}$ va nafaqat $I$ chunki chegara shartlarini ham belgilash kerak. Ba'zan elementlar $I_{c}$ Toroidal topologiyalarni amalga oshirish uchun simulyatsiya maydonining o'lchamiga vektor qo'shish moduli bilan aniqlanishi mumkin:

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

Bu davriy chegara shartlarini amalga oshirish uchun foydali bo'lishi mumkin, bu ma'lum jismoniy modellarni soddalashtiradi.

Misol: 2D Jacobi iteratsiyasi[tahrir | manbasini tahrirlash]

Formal ta'rifni ko'rsatish uchun, biz ikki o'lchamli Jekobining takrorlanishini qanday belgilash mumkinligiga e'tibor beramiz. Yangilanish funksiyasi hujayralarning to'rtta qo'shnilarining aritmetik o'rtachasini hisoblaydi. Bu holda biz 0 ning dastlabki echimi bilan boshladik. Chap va o'ng chegaralar 1 ga, yuqori va past chegaralar esa 0 ga o'rnatilgan. Ko'pgina takrorlanishlardan so'ng tizim saddel shakliga qarshi konvergentsiya qiladi.

{\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}}

S_{0}

S_{200}

S_{400}

S_{600}

S_{800}

S_{1000}

2D Jacobi Iteration on a

100^{2}

Array

Shablonlar[tahrir | manbasini tahrirlash]

Yangilanishlar paytida foydalaniladigan mehmonxona shakli dasturning o'ziga bog'liq. Eng keng tarqalgan stensillar von Neumann va Moore mahallalarining 2D yoki 3D versiyalari. Yuqoridagi misol 2D von Neumann stensildan foydalanadi, LBM kodlari esa odatda uning 3D variantidan foydalanadi. Konveyning "O'yin-harakat"ida 2D Moore mahallalaridan foydalanilgan. ^[5] qilib, seysmik to'lqinlar tarqalishi uchun 25 nuqtali stencil kabi boshqa stencillar ham topilishi mumkin.

9-point stencil

9-point 2D stencil

5-point 2D stencil

7-point 3D stencil

25-point 3D stencil

A selection of stencils used in various scientific applications.

Amalga oshirish masalalari[tahrir | manbasini tahrirlash]

Ko'plab simulyatsiya kodlari tabiiy ravishda ISL sifatida formulasiyalangan bo'lishi mumkin. Hisobot vaqti va xotira iste'moli array elementlari soni bilan liniyaviy ravishda o'sib borayotganligi sababli, ISLlarning parallel amalga oshirilishi tadqiqot uchun eng muhim ahamiyatga ega. ^[6] Bu qiyin, chunki hisoblashlar qattiq bog'langan (qo'shni hujayralarga bog'liq hujayra yangilanishlari tufayli) va ko'p ISLlar xotira bog'langan bo'ladi (ya'ni hisob-kitoblarga xotira kirish nisbati yuqori).^[7] Deyarli barcha hozirgi parallel arxitekturalar ISLlarni samarali bajarish uchun qidirib topilgan;^[8] hozirgi vaqtda GPGPUlar eng samarali ekanligi isbotlandi.^[9]

Kutubxonalar[tahrir | manbasini tahrirlash]

ISLlarning kompyuter simulyatsiyalari ahamiyati va ularning yuqori hisoblash talablari sababli, olimlarni stencilga asoslangan hisoblashlarni amalga oshirishda qo'llab-quvvatlash uchun qayta ishlatiladigan kutubxonalar yaratish maqsadida bir qator harakatlar amalga oshirilmoqda. kutubxonalar asosan parallellashtirish bilan shug'ullanadi, ammo ular IO, boshqarish va nazorat qilish kabi boshqa muammolarga ham duch kelishi mumkin. Ular o'zlarining API-lari asosida tasniflanishi mumkin.

Yamoqqa asoslangan kutubxonalar[tahrir | manbasini tahrirlash]

Bu an'anaviy dizayn. kutubxon n-o'lchamli skalar arraylar yig'imini boshqaradi, ular foydalanuvchi dastur tomonidan yangilanishlarni bajarish uchun kirishi mumkin. Kitagoriyo chegaralarning sinxronizatsiyasini (jizgi zona yoki halo deb nomlangan) boshqaradi. Ushbu interfeysning afzalligi shundaki, foydalanuvchi dasturi matrajlar ustidan bo'g'in bo'lishi mumkin, bu esa eski kodni integratsiya qilishni osonlashtiradi ^[10] . ^[11] shundaki, kutubxona cache blokirovka qilish (bu loops ichida amalga oshirilishi kerak) yoki tezlatgichlar uchun API-chaqiruvlarni (masalan, CUDA yoki OpenCL orqali) o'rnatish bilan shug'ullanmaydi. Amalga oshirishlar orasida "Kaktus" (Fizikani hal qiluvchi muhit) va "WALBerla" (WALBerl) mavjud.

Cell-based asoslangan kutubxonalar[tahrir | manbasini tahrirlash]

Ushbu kutubxonalar interfeysni bitta simulyatsiya hujayralarini yangilashga olib boradi: faqat joriy hujayra va uning qo'shnilari, masalan, getter/setter usullari orqali aniqlanadi. ^[12]^[9] yondashuvning afzalligi shundaki, kutubxona qaysi hujayralarni qaysi tartibda yangilashni qat'iy nazorat qilishi mumkin, bu nafaqat cache blokirovka qilish uchun, balki ko'p-qalba va GPU-larda bir xil kodni ishlatish uchun ham foydali bo'ladi. Ushbu yondashuv foydalanuvchidan manba kodini kutubxona bilan birga qayta yig'ishni talab qiladi. Aks holda har bir hujayra yangilanishi uchun funktsiya qo'ng'iroqlari talab qilinadi, bu esa ishlashni jiddiy ravishda pasaytiradi. Bu faqat sinf namunalari yoki metaprogrammalash kabi texnikada amalga oshishi mumkin, bu esa ushbu dizayn faqat yangi kutubxonalarda topilishi sababidir. Misollarga Physis va LibGeoDecomp (Wayback Machine saytida 2022-06-25 sanasida arxivlangan) kiradi.

Shuningdek qarang[tahrir | manbasini tahrirlash]

Avto-simulyatsiya kutubxonasi
Chet farqi usuli
Kompyuter simulyatsiyasi
Besh nuqtali stensil
Yirik shtensil
Kompakt bo'lmagan stensil
Stencildan sakrash
Stencil (hisob jihatidan tahlil)

Ma'lumotnomalar[tahrir | manbasini tahrirlash]

↑ ^1,0 ^1,1 Roth, Gerald et al. (1997) Proceedings of SC'97: High Performance Networking and Computing. Compiling Stencils in High Performance Fortran.
↑ ^2,0 ^2,1 ^2,2 ^2,3 Sloot, Peter M.A. et al. (May 28, 2002) 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,0 ^3,1 ^3,2 Fey, Dietmar et al. (2010) Grid-Computing: Eine Basistechnologie für Computational Science. Page 439. Publisher: Springer. ISBN 3-540-79746-7
↑ Yang, Laurence T.; Guo, Minyi. (August 12, 2005) High-Performance Computing : Paradigm and Infrastructure. Page 221. Publisher: Wiley-Interscience. ISBN 0-471-65471-X
↑ Micikevicius, Paulius et al. (2009) 3D finite difference computation on GPUs using CUDA Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units ISBN 978-1-60558-517-8
↑ Datta, Kaushik (2009) Auto-tuning Stencil Codes for Cache-Based Multicore Platforms Webarxiv andozasida xato: |url= qiymatini tekshiring. Boʻsh., Ph.D. Thesis
↑ Wellein, G et al. (2009) Efficient temporal blocking for stencil computations by multicore-aware wavefront parallelization, 33rd Annual IEEE International Computer Software and Applications Conference, COMPSAC 2009
↑ Datta, Kaushik et al. (2008) Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures, SC '08 Proceedings of the 2008 ACM/IEEE conference on Supercomputing
↑ ^9,0 ^9,1 Schäfer, Andreas and Fey, Dietmar (2011) High Performance Stencil Code Algorithms for GPGPUs, Proceedings of the International Conference on Computational Science, ICCS 2011
↑ S. Donath, J. Götz, C. Feichtinger, K. Iglberger and U. Rüde (2010) waLBerla: Optimization for Itanium-based Systems with Thousands of Processors, High Performance Computing in Science and Engineering, Garching/Munich 2009
↑ 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
↑ Naoya Maruyama, Tatsuo Nomura, Kento Sato, and Satoshi Matsuoka (2011) Physis: An Implicitly Parallel Programming Model for Stencil Computations on Large-Scale GPU-Accelerated Supercomputers, SC '11 Proceedings of the 2011 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis

Tashqi havolalar[tahrir | manbasini tahrirlash]

Fizik
LibGeoDecomp (Wayback Machine saytida 2022-06-25 sanasida arxivlangan)
waLBerla

[Roth-1] 1,0 ^1,1 Roth, Gerald et al. (1997) Proceedings of SC'97: High Performance Networking and Computing. Compiling Stencils in High Performance Fortran.

[Sloot-2] 2,0 ^2,1 ^2,2 ^2,3 Sloot, Peter M.A. et al. (May 28, 2002) 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.

[Fey-3] 3,0 ^3,1 ^3,2 Fey, Dietmar et al. (2010) Grid-Computing: Eine Basistechnologie für Computational Science. Page 439. Publisher: Springer. ISBN 3-540-79746-7

[4] Yang, Laurence T.; Guo, Minyi. (August 12, 2005) High-Performance Computing : Paradigm and Infrastructure. Page 221. Publisher: Wiley-Interscience. ISBN 0-471-65471-X

[5] Micikevicius, Paulius et al. (2009) 3D finite difference computation on GPUs using CUDA Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units ISBN 978-1-60558-517-8

[Datta-6] Datta, Kaushik (2009) Auto-tuning Stencil Codes for Cache-Based Multicore Platforms Webarxiv andozasida xato: |url= qiymatini tekshiring. Boʻsh., Ph.D. Thesis

[Wellein-7] Wellein, G et al. (2009) Efficient temporal blocking for stencil computations by multicore-aware wavefront parallelization, 33rd Annual IEEE International Computer Software and Applications Conference, COMPSAC 2009

[datta2-8] Datta, Kaushik et al. (2008) Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures, SC '08 Proceedings of the 2008 ACM/IEEE conference on Supercomputing

[schaefer-9] 9,0 ^9,1 Schäfer, Andreas and Fey, Dietmar (2011) High Performance Stencil Code Algorithms for GPGPUs, Proceedings of the International Conference on Computational Science, ICCS 2011

[walberla-10] S. Donath, J. Götz, C. Feichtinger, K. Iglberger and U. Rüde (2010) waLBerla: Optimization for Itanium-based Systems with Thousands of Processors, High Performance Computing in Science and Engineering, Garching/Munich 2009

[35dblocking-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

[physis-12] Naoya Maruyama, Tatsuo Nomura, Kento Sato, and Satoshi Matsuoka (2011) Physis: An Implicitly Parallel Programming Model for Stencil Computations on Large-Scale GPU-Accelerated Supercomputers, SC '11 Proceedings of the 2011 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]