Takrorlanuvchi Stencil Looplar

Iterativ Stencil Loops (ISL) yoki Stencil hisoblashlari raqamli maʼlumotlarni qayta ishlash echimlarining sinfidir  Roth, Gerald et al. (1997) 
  Proceedings of SC'97: High Performance Networking and Computing. 
  Compiling Stencils in High Performance Fortran. ular qator elementlarini stensil deb nomlangan muayyan qatʼiy namunasiga muvofiq yangilaydi 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. .. 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, Jacobi yadrovi, Gauss-Seidel usuli, tasvirni qayta ishlash va hujayra avtomatlari kiradi Fey, Dietmar et al. (2010) 
 Grid-Computing: Eine Basistechnologie für Computational Science. 
 Page 439. Publisher: Springer. . 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 
ISLlar maʼlum bir matn orqali sweeps (soʻzlangan vaqt qadamlari) ketma-ketini amalga oshiradi. Odatda 2 yoki 3 oʻlchamli muntazam toʻplamdir. Arraylarning elementlari koʻpincha hujayralar deb ataladi. Har bir vaqt bosqichida barcha matn elementlari yangilanadi. 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  Yang, Laurence T.; Guo, Minyi. (August 12, 2005) 
  High-Performance Computing : Paradigm and Infrastructure. 
  Page 221. Publisher: Wiley-Interscience.  boʻlgani uchun maʼlumotlarga kirish usuli takrorlanadi.

Rasmiyroq aytganda, biz ISLlarni 5-tuple sifatida belgilashimiz mumkin  quyidagi maʼnoda:

  indeks toʻplamidir. U massivning topologiyasini belgilaydi.
  har bir hujayra istalgan vaqt oraligʻida qabul qilishi mumkin boʻlgan holatlar toʻplami (cheklangan boʻlishi shart emas).
  0 vaqtida tizimning dastlabki holatini aniqlaydi.
  trafaretning oʻzi boʻlib, mahallaning haqiqiy shaklini tasvirlaydi. Lar bor  trafaretdagi elementlar.
  – 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  . Stencil buyurtma qilingan toʻplamdir  nisbiy koordinatalar. Endi biz har bir hujayra uchun olishimiz mumkin  qoʻshni indekslar toʻplami 



Ularning holatlari kortejni xaritalash orqali beriladi  tegishli shtatlar toʻplamiga , qayerda  quyidagicha aniqlanadi:



Bu keyingi vaqt bosqichlari uchun tizim holatini aniqlashimiz kerak boʻlgan yagona narsa  bilan  :



Shu esta tutilsinki  da belgilanadi  va nafaqat  chunki chegara shartlarini ham belgilash kerak. Baʼzan elementlar  Toroidal topologiyalarni amalga oshirish uchun simulyatsiya maydonining oʻlchamiga vektor qoʻshish moduli bilan aniqlanishi mumkin:



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

 Misol: 2D Jacobi iteratsiyasi 
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.



 Shablonlar 
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.   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  
   qilib, seysmik toʻlqinlar tarqalishi uchun 25 nuqtali stencil kabi boshqa stencillar ham topilishi mumkin.


 Amalga oshirish masalalari 
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 egaDatta, Kaushik (2009)
  Auto-tuning Stencil Codes for Cache-Based Multicore Platforms , 
  Ph.D. Thesis. 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)  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. Deyarli barcha hozirgi parallel arxitekturalar ISLlarni samarali bajarish uchun qidirib topilgan;  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 hozirgi vaqtda GPGPUlar eng samarali ekanligi isbotlandi Schäfer, Andreas and Fey, Dietmar (2011) 
 High Performance Stencil Code Algorithms for GPGPUs, 
 Proceedings of the International Conference on Computational Science, ICCS 2011.

 Kutubxonalar 
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 
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  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, 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 
Ushbu kutubxonalar interfeysni bitta simulyatsiya hujayralarini yangilashga olib boradi: faqat joriy hujayra va uning qoʻshnilari, masalan, getter/setter usullari orqali aniqlanadi  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 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  kiradi.

 Shuningdek qarang 

 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 

 Tashqi havolalar 

 Fizik
 LibGeoDecomp 
 waLBerla