पैरारियल

पैरारियल संख्यात्मक विश्लेषण से समानांतर एल्गोरिदम है और प्रारंभिक मूल्य समस्याओं के समाधान के लिए उपयोग किया जाता है। इसे 2001 में जैक्स-लुई लायंस, मैडे और टुरिनिसी द्वारा पेश किया गया था। तब से, यह सबसे व्यापक रूप से अध्ययन किए गए समानांतर-इन-टाइम एकीकरण तरीकों में से बन गया है।

पैरारियल में पहले पुनरावृत्ति का चित्रण (मूल संस्करण से अनुकूलित)).

समानांतर-इन-टाइम एकीकरण विधियां

उदाहरण के विपरीत रनगे-कुट्टा विधियां|रंज-कुट्टा या रैखिक मल्टीस्टेप विधि|मल्टी-स्टेप विधियां, पैरारियल में कुछ गणनाएं समानांतर कंप्यूटिंग की जा सकती हैं और पैरारियल इसलिए समानांतर-इन-टाइम एकीकरण विधि का उदाहरण है। जबकि ऐतिहासिक रूप से आंशिक अंतर समीकरणों के संख्यात्मक आंशिक अंतर समीकरणों को समानांतर करने के अधिकांश प्रयास स्थानिक विवेकीकरण पर केंद्रित हैं, एक्सास्केल कंप्यूटिंग की चुनौतियों को देखते हुए, अस्थायी विवेकीकरण के समानांतर तरीकों को संख्यात्मक विश्लेषण सॉफ्टवेयर की सूची में समरूपता बढ़ाने के संभावित तरीके के रूप में पहचाना गया है। क्योंकि पैरारियल समानांतर में कई समय चरणों के लिए संख्यात्मक समाधान की गणना करता है, इसे चरणों में समानांतर विधि के रूप में वर्गीकृत किया गया है। यह समानांतर रनगे-कुट्टा या एक्सट्रपलेशन विधियों जैसी विधि में समानता का उपयोग करने वाले दृष्टिकोणों के विपरीत है, जहां स्वतंत्र चरणों की गणना तरंग रूप विश्राम जैसी सिस्टम विधियों में समानांतर या समानांतर में की जा सकती है।

इतिहास

पैरारियल को समय विधि में मल्टीग्रिड विधि या समय अक्ष के साथ प्रत्यक्ष एकाधिक शूटिंग विधि दोनों के रूप में प्राप्त किया जा सकता है। दोनों विचार, समय में मल्टीग्रिड और साथ ही समय एकीकरण के लिए मल्टीपल शूटिंग को अपनाना, 1980 और 1990 के दशक में वापस चले गए। पैरारियल व्यापक रूप से अध्ययन की जाने वाली विधि है और विभिन्न अनुप्रयोगों के लिए इसका उपयोग और संशोधन किया गया है। प्रारंभिक मूल्य समस्याओं के समाधान को समानांतर करने के विचार और भी पुराने हैं: समानांतर-इन-टाइम एकीकरण विधि का प्रस्ताव करने वाला पहला पेपर 1964 में सामने आया था।

एल्गोरिथम

समस्या

लक्ष्य प्रपत्र की प्रारंभिक मूल्य समस्या को हल करना है

${\frac {\mathrm {d} u}{\mathrm {d} t}}=f(t,u)\quad {\text{over}}\quad t\in [t_{0},T]\quad {\text{with}}\quad u(t_{0})=u^{0}.$ दाहिने हाथ की ओर $f$ इसे सुचारू (संभवतः अरैखिक) फ़ंक्शन माना जाता है। यह रेखा दृष्टिकोण की विधि में आंशिक अंतर समीकरण के स्थानिक विवेक के अनुरूप भी हो सकता है। हम इस समस्या को अस्थायी आधार पर हल करना चाहते हैं $N+1$ समान दूरी वाले बिंदु $(t_{0},t_{1},\ldots ,t_{N})$, कहाँ $t_{j+1}=t_{j}+\Delta T$ और $\Delta T=(T-t_{0})/N$. इस विवेक का पालन करते हुए हमें समय के टुकड़ों से युक्त विभाजित समय अंतराल प्राप्त होता है $[t_{j},t_{j+1}]$ के लिए $j=0,\ldots ,N-1$.

इसका उद्देश्य संख्यात्मक सन्निकटन की गणना करना है $U_{j}$ सटीक समाधान के लिए $u(t_{j})$ सीरियल टाइम-स्टेपिंग विधि (जैसे रनगे-कुट्टा) का उपयोग करना जिसमें उच्च संख्यात्मक सटीकता (और इसलिए उच्च कम्प्यूटेशनल लागत) है। हम इस पद्धति को फाइन सॉल्वर कहते हैं ${\mathcal {F}}$, जो प्रारंभिक मान को प्रसारित करता है $U_{j}$ समय पर $t_{j}$ टर्मिनल मान के लिए $U_{j+1}$ समय पर $t_{j+1}$. लक्ष्य का उपयोग करके समाधान की गणना (उच्च संख्यात्मक सटीकता के साथ) करना है ${\mathcal {F}}$ जैसे कि हम प्राप्त करते हैं

$U_{j+1}={\mathcal {F}}(t_{j},t_{j+1},U_{j}),\quad {\text{where}}\quad U_{0}=u^{0}.$

इस (और सबसे पहले समानांतर में हल करने का प्रयास करने का कारण) समाधान के साथ समस्या यह है कि वास्तविक समय में गणना करना कम्प्यूटेशनल रूप से संभव नहीं है।

यह कैसे काम करता है

प्रारंभिक मूल्य समस्या को हल करने के लिए एकल प्रोसेसर का उपयोग करने के बजाय (जैसा कि शास्त्रीय समय-चरण विधियों के साथ किया जाता है), पैरारियल इसका उपयोग करता है $N$ प्रोसेसर. का उद्देश्य उपयोग करना है $N$ प्रोसेसर को हल करना होगा $N$ समानांतर में छोटी प्रारंभिक मूल्य समस्याएं (प्रत्येक समय स्लाइस पर एक)। उदाहरण के लिए, संदेश पासिंग इंटरफ़ेस आधारित कोड में, $N$ प्रक्रियाओं की संख्या होगी, जबकि ओपनएमपी आधारित कोड में, $N$ थ्रेड (कंप्यूटिंग) की संख्या के बराबर होगी।

पैरारियल इस प्रारंभिक मूल्य समस्या को समानांतर में हल करने के लिए दूसरी टाइम-स्टेपिंग विधि का उपयोग करता है, जिसे मोटे सॉल्वर के रूप में जाना जाता है ${\mathcal {G}}$. मोटे सॉल्वर ठीक सॉल्वर की तरह ही काम करता है, लंबाई के समय अंतराल पर प्रारंभिक मूल्य का प्रसार करता है $\Delta T$हालाँकि, यह इससे कहीं कम संख्यात्मक सटीकता पर ऐसा करता है ${\mathcal {F}}$ (और इसलिए बहुत कम कम्प्यूटेशनल लागत पर)। मोटे सॉल्वर का होना जो कि फाइन सॉल्वर की तुलना में बहुत कम कम्प्यूटेशनल रूप से महंगा है, पैरारियल के साथ समानांतर गति प्राप्त करने की कुंजी है।

अब से, हम समय पर पैरारियल समाधान को निरूपित करेंगे $t_{j}$ और पुनरावृत्ति $k$ द्वारा $U_{j}^{k}$.

शून्य पुनरावृत्ति

सबसे पहले, मोटे सॉल्वर को पूरे समय अंतराल पर क्रमिक रूप से चलाएं $[t_{0},T]$ समाधान के लिए अनुमानित प्रारंभिक अनुमान की गणना करने के लिए:

$U_{j+1}^{0}={\mathcal {G}}(t_{j},t_{j+1},U_{j}^{0}),\quad j=0,\ldots ,N-1.$

अनुवर्ती पुनरावृत्तियाँ

इसके बाद, सबसे अद्यतित समाधान मानों से, समानांतर में, प्रत्येक समय स्लाइस पर बढ़िया सॉल्वर चलाएं:

${\mathcal {F}}(t_{j},t_{j+1},U_{j}^{k-1}),\quad j=0,\ldots ,N-1.$ अब प्रेडिक्टर-करेक्टर का उपयोग करके क्रमिक रूप से पैरारियल समाधान मानों को अपडेट करें:

$U_{j+1}^{k}={\mathcal {G}}(t_{j},t_{j+1},U_{j}^{k})+{\mathcal {F}}(t_{j},t_{j+1},U_{j}^{k-1})-{\mathcal {G}}(t_{j},t_{j+1},U_{j}^{k-1}),\quad j=0,\ldots ,N-1.$ इस स्तर पर, कोई यह निर्धारित करने के लिए स्टॉपिंग मानदंड का उपयोग कर सकता है कि क्या समाधान मान अब प्रत्येक पुनरावृत्ति में नहीं बदल रहे हैं। उदाहरण के लिए, कोई इसकी जांच करके यह जांच सकता है कि क्या

 $|U_{j}^{k}-U_{j}^{k-1}|<\varepsilon \quad \forall \ j\leq N,$

और कुछ सहनशीलता $\varepsilon >0$. यदि यह मानदंड संतुष्ट नहीं है, तो बाद के पुनरावृत्तियों को समानांतर में फाइन सॉल्वर और फिर भविष्यवक्ता-सुधारक को लागू करके चलाया जा सकता है। हालाँकि, बार जब मानदंड संतुष्ट हो जाता है, तो कहा जाता है कि एल्गोरिदम अभिसरण हो गया है $k\leq N$ पुनरावृत्तियाँ ध्यान दें कि अन्य रोक मानदंड मौजूद हैं और पैरारियल में सफलतापूर्वक परीक्षण किया गया है।

टिप्पणियाँ

पैरारियल को उस समाधान को पुन: पेश करना चाहिए जो फाइन सॉल्वर के क्रमिक अनुप्रयोग द्वारा प्राप्त किया जाता है और अधिकतम में परिवर्तित हो जाएगा $N$ पुनरावृत्तियाँहालाँकि, पैरारियल को स्पीडअप प्रदान करने के लिए, इसे समय स्लाइस की संख्या की तुलना में काफी कम संख्या में पुनरावृत्तियों में परिवर्तित करना होगा, अर्थात। $k\ll N$.

पैरारियल पुनरावृत्ति में, कम्प्यूटेशनल रूप से महंगा मूल्यांकन ${\mathcal {F}}(t_{j},t_{j+1},U_{j}^{k-1})$ पर समानांतर में निष्पादित किया जा सकता है $N$ प्रसंस्करण इकाइयाँ। इसके विपरीत, की निर्भरता $U_{j+1}^{k}$ पर ${\mathcal {G}}(t_{j},t_{j+1},U_{j}^{k})$ इसका मतलब है कि मोटे सुधार की गणना क्रमिक क्रम में की जानी है।

आमतौर पर, रंज-कुट्टा विधि का कुछ रूप मोटे और बारीक इंटीग्रेटर दोनों के लिए चुना जाता है, जहां ${\mathcal {G}}$ निम्न क्रम का हो सकता है और इससे बड़े समय के चरण का उपयोग किया जा सकता है ${\mathcal {F}}$. यदि प्रारंभिक मूल्य समस्या पीडीई के विवेकाधिकार से उत्पन्न होती है, ${\mathcal {G}}$ मोटे स्थानिक विवेक का भी उपयोग कर सकते हैं, लेकिन यह अभिसरण पर नकारात्मक प्रभाव डाल सकता है जब तक कि उच्च क्रम के प्रक्षेप का उपयोग नहीं किया जाता है।

पैरारियल एल्गोरिथम का विज़ुअलाइज़ेशन। यहां मोटे प्रचारक को लेबल किया गया है ${\bar {\varphi }}$ जबकि बढ़िया प्रचारक का लेबल लगा हुआ है $\varphi$.

स्पीडअप

कुछ मान्यताओं के तहत, अमदहल के पैरारियल के नियम के लिए सरल सैद्धांतिक मॉडल प्राप्त किया जा सकता है। हालाँकि अनुप्रयोगों में ये धारणाएँ बहुत अधिक प्रतिबंधात्मक हो सकती हैं, फिर भी मॉडल पैरारियल के साथ स्पीडअप प्राप्त करने में शामिल ट्रेडऑफ़ को चित्रित करने के लिए उपयोगी है।

सबसे पहले, मान लें कि हर बार स्लाइस करें $[t_{j},t_{j+1}]$ बिल्कुल शामिल है $N_{f}$ फाइन इंटीग्रेटर और के चरण $N_{c}$ मोटे इंटीग्रेटर के चरण. इसमें विशेष रूप से यह धारणा शामिल है कि सभी समय स्लाइस समान लंबाई के होते हैं और मोटे और बारीक इंटीग्रेटर दोनों पूर्ण सिमुलेशन पर स्थिर चरण आकार का उपयोग करते हैं। दूसरा, द्वारा निरूपित करें $\tau _{f}$ और $\tau _{c}$ क्रमशः बारीक और मोटे तरीकों के चरण के लिए आवश्यक कंप्यूटिंग समय, और मान लें कि दोनों स्थिर हैं। यह आम तौर पर बिल्कुल सच नहीं है जब टेम्पोरल डिस्क्रेटाइजेशन#इम्प्लिसिट टाइम इंटीग्रेशन विधि का उपयोग किया जाता है, क्योंकि तब रनटाइम इटरेटिव विधि द्वारा आवश्यक पुनरावृत्तियों की संख्या के आधार पर भिन्न होता है।

इन दो मान्यताओं के तहत, ठीक विधि को एकीकृत करने का रनटाइम खत्म हो गया है $P$ समय के टुकड़ों को इस प्रकार प्रतिरूपित किया जा सकता है

$c_{\text{fine}}=NN_{f}\tau _{f}.$ पैरारियल का उपयोग करने का रनटाइम $P$ प्रसंस्करण इकाइयाँ और प्रदर्शन $k$ पुनरावृत्तियाँ है

$c_{\text{parareal}}=(k+1)NN_{c}\tau _{c}+kN_{f}\tau _{f}.$ पैरारियल का स्पीडअप तो है

$S_{p}={\frac {c_{\text{fine}}}{c_{\text{parareal}}}}={\frac {1}{(k+1){\frac {N_{c}}{N_{f}}}{\frac {\tau _{c}}{\tau _{f}}}+{\frac {k}{N}}}}\leq \min \left\{{\frac {N_{f}\tau _{f}}{N_{c}\tau _{c}}},{\frac {N}{k}}\right\}.$ ये दो सीमाएँ मोटे तरीके को चुनने में किए जाने वाले व्यापार को दर्शाती हैं: ओर, इसे सस्ता होना होगा और/या पहली सीमा को जितना संभव हो उतना बड़ा बनाने के लिए बहुत बड़े समय के कदम का उपयोग करना होगा, दूसरी ओर पुनरावृत्तियों की संख्या $k$ दूसरे बाउंड को बड़ा रखने के लिए इसे नीचे रखना होगा। विशेष रूप से, स्पीडअप#अतिरिक्त विवरण|पैरारियल की समानांतर दक्षता सीमित है

$E_{p}={\frac {S_{p}}{N}}\leq {\frac {1}{k}},$ यह आवश्यक पुनरावृत्तियों की संख्या के व्युत्क्रम से है।

काल्पनिक eigenvalues ​​​​के लिए अस्थिरता

पैरारियल के वेनिला संस्करण में काल्पनिक आइगेनवैल्यूज़ एवं आइगेनवेक्टर्स के साथ समस्याएं हैं।यह आम तौर पर केवल अंतिम पुनरावृत्तियों की ओर ही परिवर्तित होता है, अर्थात $k$ दृष्टिकोण $N$, और स्पीडअप $S_{p}$ हमेशा से छोटा होगा. तो या तो पुनरावृत्तियों की संख्या छोटी है और पैरारियल अस्थिर है या, यदि $k$ पैरारियल को स्थिर बनाने के लिए पर्याप्त बड़ा है, कोई गति संभव नहीं है। इसका यह भी अर्थ है कि हाइपरबोलिक आंशिक अंतर समीकरण समीकरणों के लिए पैरारियल आमतौर पर अस्थिर है। भले ही गैंडर और वांडेवेले द्वारा औपचारिक विश्लेषण केवल निरंतर गुणांक के साथ रैखिक समस्याओं को कवर करता है, समस्या तब भी उत्पन्न होती है जब पैरारियल को गैर-रेखीय नेवियर-स्टोक्स समीकरणों पर लागू किया जाता है जब चिपचिपाहट गुणांक बहुत छोटा हो जाता है और रेनॉल्ड्स संख्या बहुत बड़ी हो जाती है। पैरारियल को स्थिर करने के लिए विभिन्न दृष्टिकोण मौजूद हैं, इनमें से क्रायलोव-सबस्पेस संवर्धित पैरारियल है।

वेरिएंट

ऐसे कई एल्गोरिदम हैं जो सीधे तौर पर आधारित हैं या कम से कम मूल पैरारियल एल्गोरिदम से प्रेरित हैं।

क्रायलोव-सबस्पेस ने पैरारियल को बढ़ाया

प्रारंभ में ही यह माना गया कि रैखिक समस्याओं के लिए सूचना सूक्ष्म विधि द्वारा उत्पन्न की जाती है ${\mathcal {F}}_{\delta t}$ मोटे तरीके की सटीकता में सुधार के लिए इसका उपयोग किया जा सकता है ${\mathcal {G}}_{\Delta t}$.मूल रूप से, यह विचार समानांतर अंतर्निहित समय-एकीकरणकर्ता PITA के लिए तैयार किया गया था, यह विधि है जो पैरारियल से निकटता से संबंधित है लेकिन सुधार कैसे किया जाता है इसमें थोड़ा अंतर है। प्रत्येक पुनरावृत्ति में $k$ परिणाम ${\mathcal {F}}_{\delta t}(U_{j}^{k})$ मूल्यों के लिए गणना की जाती है $u_{j}^{k}\in \mathbb {R} ^{d}$ के लिए $j=0,\ldots ,N-1$. इस जानकारी के आधार पर, सदिश स्थल

$S_{k}:=\left\{U_{j}^{k'}:0\leq k'\leq k,j=0,\ldots ,N-1\right\}$ प्रत्येक पैरारियल पुनरावृत्ति के बाद परिभाषित और अद्यतन किया जाता है। के रूप में निरूपित करें $P_{k}$ ओर्थोगोनल प्रक्षेपण से $\mathbb {R} ^{d}$ को $S_{k}$. फिर, मोटे तरीके को बेहतर इंटीग्रेटर से बदलें ${\mathcal {K}}_{\Delta t}(u)={\mathcal {F}}_{\delta t}(P_{k}u)+{\mathcal {G}}_{\Delta t}((I-P_{k})u)$.

जैसे-जैसे पुनरावृत्तियों की संख्या बढ़ती है, space $S_{k}$ बढ़ेगा और संशोधित प्रचारक ${\mathcal {K}}_{\Delta t}$ अधिक सटीक हो जाएगा. इससे तेजी से अभिसरण हो सकेगा. पैरारियल का यह संस्करण रैखिक अतिशयोक्तिपूर्ण आंशिक अंतर समीकरणों को भी स्थिर रूप से एकीकृत कर सकता है। कम आधार पद्धति पर आधारित अरेखीय समस्याओं का विस्तार भी मौजूद है।

हाइब्रिड पैरारियल वर्णक्रमीय आस्थगित सुधार

वर्णक्रमीय विलंबित सुधार (एसडीसी) के साथ पैरारियल के संयोजन पर आधारित बेहतर समानांतर दक्षता वाली विधि एम. मिनियन द्वारा प्रस्तावित किया गया है। यह बेहतर समानांतर दक्षता के लिए लचीलेपन का त्याग करते हुए मोटे और बारीक इंटीग्रेटर के विकल्प को एसडीसी तक सीमित कर देता है। की सीमा के बजाय $1/k$, संकर विधि में समानांतर दक्षता पर बाध्य हो जाता है

$E_{p}\leq {\frac {k_{s}}{k_{p}}}$ साथ $k_{s}$ धारावाहिक एसडीसी आधार पद्धति के पुनरावृत्तियों की संख्या और $k_{p}$ आमतौर पर समानांतर संकर विधि के पुनरावृत्तियों की अधिक संख्या। नॉनलाइनियर मल्टीग्रिड विधि में उपयोग की जाने वाली पूर्ण सन्निकटन योजना को जोड़कर पैरारियल-एसडीसी हाइब्रिड को और बेहतर बनाया गया है। इससे अंतरिक्ष और समय में समानांतर पूर्ण सन्निकटन योजना (पीएफएएसएसटी) का विकास हुआ। पीएफएएसएसटी के प्रदर्शन का अध्ययन पीईपीसी के लिए किया गया है, जो जूलिच सुपरकंप्यूटिंग सेंटर में विकसित बार्न्स-हट सिमुलेशन|बार्न्स-हट ट्री कोड आधारित कण सॉल्वर है। IBM ब्लू जीन/पी सिस्टम JUGENE पर सभी 262,144 कोर का उपयोग करके सिमुलेशन से पता चला कि PFASST स्थानिक वृक्ष समानांतरीकरण की संतृप्ति से परे अतिरिक्त गति उत्पन्न कर सकता है।

समय में मल्टीग्रिड कटौती (एमजीआरआईटी)

मल्टीग्रिड रिडक्शन इन टाइम मेथड (एमजीआरआईटी) विभिन्न स्मूथर्स का उपयोग करके कई स्तरों पर मल्टीग्रिड-इन-टाइम एल्गोरिदम के रूप में पैरारियल की व्याख्या को सामान्यीकृत करता है। यह अधिक सामान्य दृष्टिकोण है लेकिन मापदंडों की विशिष्ट पसंद के लिए यह पैरारियल के बराबर है। एमजीआरआईटी को लागू करने वाली XBraid लाइब्रेरी लॉरेंस लिवरमोर राष्ट्रीय प्रयोगशाला द्वारा विकसित की जा रही है।

पैराएक्सप

ParaExp, Parareal के भीतर घातीय इंटीग्रेटर्स का उपयोग करता है। रैखिक समस्याओं तक सीमित रहते हुए, यह लगभग इष्टतम समानांतर गति उत्पन्न कर सकता है।

बाहरी संबंध

• parallel-in-time.org