🤽🏿 👿 🧑🏿‍🤝‍🧑🏼 ज्यामितीय समानता की विधि और MPI के बारे में थोड़ा अधिक 🏟️ 🍎 🦉

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

समस्या का बयान

दो आयामी गर्मी समीकरण समीकरण द्वारा दिया गया है:

साथ ही प्रारंभिक शर्तें:

हम यह भी ध्यान में रखते हैं कि हम अंतरिक्ष के एक सीमित क्षेत्र की गणना करते हैं:

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

यदि हम इस योजना के विवरण में नहीं जाते हैं, तो "कुछ समय परत" पर "क्रॉस" के सभी बिंदुओं के मूल्य से, हम केंद्र बिंदु पर "अगली समय परत" पर मान प्राप्त करते हैं। इसके अलावा, समय और निर्देशांक के चरण सुसंगत होने चाहिए:

(इसके बाद, ग्रिड तय हो गई है और स्थानिक निर्देशांक के कदम एच के बराबर हैं)
मेमोरी को बचाने के लिए, आप X और Y में केवल दो ग्रिड स्टोर कर सकते हैं, एक वर्तमान समय परत के लिए और अगली समय परत के लिए। इस मामले में, अगली समय परत की गणना करने के बाद, यह परत वर्तमान एक हो जाती है, और अगली बार परत के मान अंतिम परत के सरणी को लिखे जाते हैं।

ज्यामितीय समानता विधि

ज्यामितीय समानता का तरीका उन समस्याओं के लिए उपयोग किया जाता है जिसमें आप कुछ ज्यामितीय नियमितता को उजागर कर सकते हैं और इसे प्रोसेसर के बीच काम को विभाजित करने के लिए उपयोग कर सकते हैं। इस समस्या में, सीमित स्थान के लिए ग्रिड को निम्न रूप में दर्शाया जा सकता है:

इस मामले में, समानता को काफी अच्छी तरह से पता लगाया जा सकता है और आप सरणी को कई में विभाजित कर सकते हैं, और इसके निष्पादक के लिए गणना के लिए प्रत्येक नया एक दे सकते हैं।

वास्तव में, सरणी को क्षैतिज पट्टियों में विभाजित करना संभव है, यह विधि के लिए किसी भी मूलभूत अंतर को पेश नहीं करेगा, लेकिन मैं बाद में कार्यान्वयन में अंतर के बारे में बात करूंगा। इस प्रकार, प्रत्येक ठेकेदार केवल सरणी के अपने अनुभाग पर विचार करेगा।

नुकसान

यदि हम अंतर योजना पर लौटते हैं, जिसके अनुसार हम गणना करेंगे, तो यह स्पष्ट हो जाता है कि यह अंत नहीं है। यह आरेख से देखा जा सकता है कि किसी भी मेष तत्व की गणना करने के लिए, हमें पिछली परत पर इसके किनारे के तत्वों को जानना होगा। इसका मतलब है कि हम स्थानिक ग्रिड की चरम परत की गणना नहीं कर सकते हैं (क्योंकि पर्याप्त डेटा नहीं है), लेकिन यदि आप सीमा की स्थितियों को देखते हैं, तो आप देख सकते हैं कि चरम तत्व शर्तों से जाने जाते हैं। लेकिन कलाकारों के क्षेत्रों की सीमा पर तत्वों की गणना करने की समस्या है। यह स्पष्ट है कि इस प्रक्रिया में आपको पड़ोसी कलाकारों के बीच डेटा भेजना होगा। यह एक तत्व पर गुजरने वाले लूप के रूप में किया जा सकता है:

for (int i = 0; i < N; i ++) { MPI_Send(*buf, 1, MPI_DOUBLE, toRank, MESSAGE_ID, MPI_COMM_WORLD); }

(तत्वों द्वारा संचरण के बारे में अधिक विवरण शुरुआत में वर्णित लेखों में पाया जा सकता है)
यह विधि प्रभावी नहीं है क्योंकि आपको कई कनेक्शन स्थापित करने होंगे (इसमें बहुत समय लगता है)। एक कस्टम डेटा प्रकार का निर्माण हमारी आवश्यकताओं को पूरा कर सकता है। कस्टम संरचना बनाने के अलावा, MPI हमें डेटा के लिए कई प्रकार के "मास्क" प्रदान कर सकता है: MPI_Type_contiguous और MPI_Type_vector। उनमें से पहला एक प्रकार बनाता है जो मेमोरी में स्थित एक पंक्ति में कई तत्वों का वर्णन करता है, और दूसरा आपको एक "टेम्पलेट" बनाने की अनुमति देता है जिसके द्वारा "आवश्यक" तत्वों को क्रमिक रूप से मेमोरी में स्थित तत्वों से चुना जाता है, फिर "अनावश्यक" लोगों को छोड़ दिया जाता है और वांछितों को दोहराया जाता है। उनकी संख्या निश्चित है।

 //   -     ,       //   -  ""  //   -   ,       MPI_Datatype USER_Vector; MPI_Type_vector(N, 1, N, MPI_DOUBLE, &USER_Vector); //     ""   MPI_Type_commit(&USER_Vector);

यदि आप इस प्रकार को भेजते हैं, और जैसा कि * buf सरणी की शुरुआत का संकेत देता है, तो आपको मिलता है:
+ ० ०
+ ० ०
+ ० ०
यदि आप सरणी के दूसरे तत्व के रूप में * buf निर्दिष्ट करते हैं, तो हम प्राप्त करते हैं:
० + ०
० + ०
० + ०

तो आप सरणी का केवल एक कॉलम भेज सकते हैं (और प्राप्त कर सकते हैं), और एक कॉल में MPI_SEND:

 MPI_Send(*buf, 1, USER_Vector, (rank + 1), MESSAGE_ID, MPI_COMM_WORLD);

यदि आप कलाकार क्षेत्रों को क्षैतिज रूप से रखते हैं, तो आप MPI_Type_contiguous का उपयोग कर सकते हैं या MPI_Send में तत्वों की आवश्यक संख्या निर्दिष्ट कर सकते हैं, लेकिन यह, मेरी राय में, अधिक सुंदर है।

अब आपको यह समझने की आवश्यकता है कि इन स्तंभों को किस क्रम में आगे बढ़ाना है। सबसे स्पष्ट: कलाकारों को बदले में दाहिने प्राप्तकर्ता को वांछित कॉलम पास करने दें। फिर हमें निम्नलिखित चित्र मिलता है:

हालाँकि चित्रण केवल चार कलाकारों के बीच के आदान-प्रदान को दर्शाता है, यह गणना की जा सकती है कि यदि एक निश्चित SEND_TIME को एक संचरण पर खर्च किया जाता है, तो (2 * N-2) * SEND_TIME को सभी स्तंभों को स्थानांतरित करने के लिए आवश्यक है। यह देखा जा सकता है कि प्रत्येक कॉलम के प्रसारण के दौरान, केवल दो कलाकार "काम" करते हैं, जबकि बाकी बेकार हैं। यह अच्छा नहीं है। थोड़ा संशोधित योजना पर विचार करें: इसमें, कलाकारों को उनकी "समता" संख्या से विभाजित किया जाता है। सबसे पहले, सभी बुराइयाँ एक बड़ी संख्या के साथ कॉलम को पास करती हैं, फिर सभी ख़राबियाँ कम संख्या के साथ कॉलम को पास करती हैं, फिर विषम संख्या वाले कलाकार भी ऐसा ही करते हैं। बेशक, सभी अग्रेषण केवल तभी होते हैं जब कोई ऐसा होता है जिसे इसे अग्रेषित किया जाता है।

 // EVEN_RIGHT, ODD_RIGHT, ODD_LEFT, EVEN_LEFT -      // (  ,      ) const int ROOT = 0; if ((rank % 2) == 0) { if (rank != (size - 1)) MPI_Send(*buf, 1, USER_Vector, (rank + 1), EVEN_RIGHT, MPI_COMM_WORLD); if (rank != ROOT) MPI_Recv(*buf, 1, USER_Vector, (rank - 1), ODD_RIGHT, MPI_COMM_WORLD, &status); if (rank != (size - 1)) MPI_Recv(*buf, 1, USER_Vector, (rank + 1), ODD_LEFT, MPI_COMM_WORLD, &status); if (rank != ROOT) MPI_Send(*buf, 1, USER_Vector, (rank - 1), EVEN_LEFT, MPI_COMM_WORLD); } if ((rank % 2) == 1) { MPI_Recv(*buf, 1, USER_Vector, (rank - 1), EVEN_RIGHT, MPI_COMM_WORLD, &status); if (rank != (size - 1)) MPI_Send(*buf, 1, USER_Vector, (rank + 1), ODD_RIGHT, MPI_COMM_WORLD); MPI_Send(*buf, 1, USER_Vector, (rank - 1), ODD_LEFT, MPI_COMM_WORLD); if (rank != (size - 1)) MPI_Recv(*buf, 1, USER_Vector, (rank + 1), EVEN_LEFT, MPI_COMM_WORLD, &status); }

इस मामले में, स्थानांतरण में 4 * SEND_TIME लगते हैं, भले ही कलाकारों की संख्या कितनी भी हो। कई कलाकारों के साथ सिस्टम पर, यह महत्वपूर्ण श्रेष्ठता रखता है।

(स्थानांतरण के बारे में आंकड़ों में कुछ झूठ है: कलाकारों की संख्या शून्य से शुरू होती है, जैसा कि एक सरणी में है, और आंकड़े में उन्हें "सामान्य" क्रम में गिना जाता है: पहले से शुरू होता है। अर्थात, संख्या में इकाई से संख्या लेते हुए, हम कार्यक्रम में इसकी संख्या प्राप्त करते हैं)

ज्यामितीय समानता की विधि और MPI के बारे में थोड़ा अधिक

समस्या का बयान

ज्यामितीय समानता विधि

नुकसान

More articles: