حلقات الاستنسل المتكررة

تُعدّ حلقات الاستنسل التكرارية (ISLs) أو حسابات الاستنسل فئةً من حلول معالجة البيانات العددية ^{[ 1 ]} التي تُحدّث عناصر المصفوفة وفقًا لنمط ثابت يُسمى الاستنسل. ^{[ 2 ]} وتُستخدم هذه الحلقات بكثرة في عمليات المحاكاة الحاسوبية ، مثل ديناميكيات الموائع الحسابية في التطبيقات العلمية والهندسية. ومن الأمثلة البارزة الأخرى: حلّ المعادلات التفاضلية الجزئية ^{[ 1 ]} ، ونواة جاكوبي ، وطريقة جاوس-سيدل ^{[ 2 ]} ، ومعالجة الصور ^{[ 1 ]،} والأتمتة الخلوية ^{[ 3 ]} . ويُميّز الهيكل المنتظم للمصفوفات تقنيات الاستنسل عن طرق النمذجة الأخرى، مثل طريقة العناصر المحدودة . ويمكن صياغة معظم رموز الفروق المحدودة التي تعمل على الشبكات المنتظمة على شكل حلقات استنسل تكرارية.

تُجري خوارزميات ISL سلسلة من عمليات المسح (تُسمى خطوات زمنية) عبر مصفوفة مُعطاة. ^{[ 2 ]} عادةً ما تكون هذه المصفوفة شبكة منتظمة ثنائية أو ثلاثية الأبعاد. ^{[ 3 ]} تُسمى عناصر المصفوفات غالبًا بالخلايا. في كل خطوة زمنية، يتم تحديث جميع عناصر المصفوفة. ^{[ 2 ]} باستخدام عناصر المصفوفة المتجاورة بنمط ثابت (النمط)، يتم حساب القيمة الجديدة لكل خلية. في معظم الحالات، تبقى قيم الحدود دون تغيير، ولكن في بعض الحالات (مثل أكواد LBM ) يلزم تعديلها أثناء الحساب أيضًا. نظرًا لأن النمط هو نفسه لكل عنصر، يتكرر نمط الوصول إلى البيانات. ^{[ 4 ]}

بصورة أكثر رسمية، يمكننا تعريف ISLs على أنها مجموعة من 5 عناصر${\displaystyle (I,S,S_{0},s,T)}$بالمعنى التالي: ^{[ 3 ]}

• ${\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}))\}}$

قد يكون هذا مفيدًا لتطبيق شروط الحدود الدورية ، مما يبسط بعض النماذج الفيزيائية.

مثال: تكرار جاكوبي ثنائي الأبعاد

لتوضيح التعريف الرسمي، سنلقي نظرة على كيفية تعريف تكرار جاكوبي ثنائي الأبعاد . تحسب دالة التحديث المتوسط ​​الحسابي لأربعة جيران للخلية. في هذه الحالة، نبدأ بحل ابتدائي قيمته صفر. يتم تثبيت الحدين الأيمن والأيسر عند 1، بينما يتم ضبط الحدين العلوي والسفلي على صفر. بعد عدد كافٍ من التكرارات، يتقارب النظام نحو شكل سرجي.

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

${\displaystyle S_{0}}$

${\displaystyle S_{200}}$

${\displaystyle S_{400}}$

${\displaystyle S_{600}}$

${\displaystyle S_{800}}$

${\displaystyle S_{1000}}$

تكرار جاكوبي ثنائي الأبعاد على${\displaystyle 100^{2}}$المصفوفة

يعتمد شكل الجوار المستخدم أثناء التحديثات على التطبيق نفسه. أكثر القوالب شيوعًا هي النسخ ثنائية وثلاثية الأبعاد من جوار فون نيومان وجوران مور . يستخدم المثال أعلاه قالب فون نيومان ثنائي الأبعاد، بينما تستخدم أكواد LBM عمومًا نسخته ثلاثية الأبعاد. تستخدم لعبة كونواي للحياة جوار مور ثنائي الأبعاد. مع ذلك، يمكن أيضًا العثور على قوالب أخرى، مثل قالب 25 نقطة لانتشار الموجات الزلزالية ^{[ 5 ] .}

قالب ثنائي الأبعاد ذو 9 نقاط

قالب ثنائي الأبعاد بخمس نقاط

قالب ثلاثي الأبعاد بسبع نقاط

قالب ثلاثي الأبعاد مكون من 25 نقطة

مجموعة مختارة من القوالب المستخدمة في تطبيقات علمية متنوعة.

يمكن صياغة العديد من أكواد المحاكاة بشكل طبيعي على هيئة سلاسل متداخلة (ISLs). ونظرًا لأن وقت الحساب واستهلاك الذاكرة يزدادان خطيًا مع عدد عناصر المصفوفة، فإن التنفيذ المتوازي لسلاسل المتداخلة يُعدّ ذا أهمية قصوى للبحث العلمي. ^{[ 6 ]} ويُمثل هذا تحديًا نظرًا للترابط الوثيق بين العمليات الحسابية (بسبب اعتماد تحديثات الخلايا على الخلايا المجاورة) ولأن معظم سلاسل المتداخلة مُقيدة بالذاكرة (أي أن نسبة الوصول إلى الذاكرة إلى العمليات الحسابية عالية). ^{[ 7 ]} وقد تم استكشاف جميع البنى المتوازية الحالية تقريبًا لتنفيذ سلاسل المتداخلة بكفاءة؛ ^{[ 8 ]} وفي الوقت الحالي، أثبتت وحدات معالجة الرسومات للأغراض العامة (GPGPUs) أنها الأكثر كفاءة. ^{[ 9 ]}

نظراً لأهمية نماذج الاستنسل في عمليات المحاكاة الحاسوبية ومتطلباتها الحسابية العالية، تُبذل جهودٌ حثيثة لإنشاء مكتبات قابلة لإعادة الاستخدام لدعم العلماء في إجراء الحسابات القائمة على الاستنسل. تُعنى هذه المكتبات في الغالب بالتوازي، ولكنها قد تتناول أيضاً تحديات أخرى، مثل الإدخال والإخراج، والتوجيه ، وحفظ نقاط التفتيش . ويمكن تصنيفها وفقاً لواجهات برمجة التطبيقات (APIs) الخاصة بها.

• فيزيس
• تمت أرشفة LibGeoDecomp بتاريخ 25 يونيو 2022 على موقع Wayback Machine .
• والبرلا