समानांतर एल्गोरिदम का विश्लेषण: Difference between revisions

Revision as of 15:26, 21 July 2023

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

पृष्ठभूमि

एक तथाकथित कार्य-अवधि (डब्ल्यूटी) (जिसे कभी-कभी कार्य-गहराई या कार्य-अवधि भी कहा जाता है) प्रतिरूप मूल रूप से शिलोच और विश्किन द्वारा समानांतर कलन विधि की अवधारणा और वर्णन के लिए प्रस्तुत किया गया था। ^[1] डब्ल्यूटी प्रतिरूप में, एक समानांतर कलन विधि को सबसे पहले समानांतर वृत्त के संदर्भ में वर्णित किया गया है। प्रत्येक वृत्त के लिए, किए जाने वाले संचालन की विशेषता होती है, लेकिन कई विषयों को दबाया जा सकता है। उदाहरण के लिए, प्रत्येक वृत्त में संचालन की संख्या स्पष्ट होने की आवश्यकता नहीं है, संसाधक का उल्लेख करने की आवश्यकता नहीं है और कोई भी जानकारी जो संसाधक को नौकरियों के समनुदेशन में मदद कर सकती है, उसे ध्यान में रखने की आवश्यकता नहीं है। दूसरा, संदमित जानकारी प्रदान की जाती है। संदमित जानकारी का समावेश ब्रेंट के कारण अनुसूचीकरण प्रमेय के प्रमाण द्वारा निर्देशित होता है, ^[2] जिसे इस लेख में बाद में समझाया गया है। डब्ल्यूटी प्राधार उपयोगी है क्योंकि यह एक समानांतर कलन विधि के प्रारंभिक विवरण को बहुत सरल बना सकता है, लेकिन उस प्रारंभिक विवरण द्वारा दबाए गए विवरणों को सम्मिलित करना प्रायः बहुत कठिन नहीं होता है। उदाहरण के लिए, डब्ल्यूटी प्राधार को समानांतर कलन विधि पुस्तकों (समानांतर रैंडम-एक्सेस मशीन पीआरएएम प्रतिरूप के लिए) में मूल प्रस्तुति प्रतिरूप और,साथ ही क्लास नोट्स के रूप में भी अपनाया गया था। ^[3] ^[4] ^[5] नीचे दिए गए अवलोकन से पता चलता है कि डब्ल्यूटी प्रतिरूप का उपयोग अधिक सामान्य समानांतर कलन विधि का विश्लेषण करने के लिए कैसे किया जा सकता है, भले ही उनका विवरण डब्ल्यूटी प्रतिरूप के भीतर उपलब्ध न हो।

परिभाषाएँ

मान लीजिए कि गणना एक ऐसी मशीन पर निष्पादित की जाती है जिसमें $p$ संसाधक है। मान लीजिए $T p$ उस समय को दर्शाता है जो गणना के प्रारम्भ और उसके अंत के बीच समाप्त होता है। गणना के चलने के समय का विश्लेषण निम्नलिखित धारणाओं पर केंद्रित है:

$p$ संसाधक द्वारा निष्पादित गणना का कार्य संसाधक द्वारा निष्पादित आदिम संचालन की कुल संख्या है। संसाधक को समकालिक करने से संचार शिरोपरि को अनदेखा करना, यह एकल संसाधक पर गणना चलाने के लिए उपयोग किए गए समय के बराबर है, जिसे $T 1$ दर्शाया गया है।
मध्यमार्ग या अवधि संचालन की सबसे लंबी श्रृंखला की लंबाई है जिसे डेटा निर्भरता (महत्वपूर्ण पथ) के कारण क्रमिक रूप से निष्पादित करना पड़ता है। गहराई को गणना की महत्वपूर्ण पथ लंबाई भी कहा जा सकता है। ^[6] समानांतर कलन विधि को अभिकल्पित करने में मध्यमार्ग/अवधि को कम करना महत्वपूर्ण है, क्योंकि मध्यमार्ग/अवधि न्यूनतम संभव निष्पादन समय निर्धारित करता है। ^[7] वैकल्पिक रूप से, स्पैन को अनंत संख्या में संसाधक के साथ एक आदर्श मशीन का उपयोग करके कंप्यूटिंग में बिताए गए समय T∞ के रूप में परिभाषित किया जा सकता है। ^[8]
गणना की लागत मात्रा $pT p$ है। यह सभी संसाधक द्वारा कंप्यूटिंग और प्रतीक्षा दोनों में खर्च किए गए कुल समय को व्यक्त करता है। ^[9]

कार्य, अवधि और लागत की परिभाषाओं से कई उपयोगी परिणाम मिलते हैं:

कार्य नियम. लागत हमेशा कम से कम काम की होती है: $pT p \geq T 1$ । यह इस तथ्य से पता चलता है कि $p$ संसाधक अधिकतम प्रदर्शन कर सकते हैं। ^[9]^[8]
स्पैन नियम. एक सीमित संख्या $p$ संसाधक अनंत संख्या से बेहतर प्रदर्शन नहीं कर सकते, इसलिए $T p \geq T \infty$ है। ^[8]

इन परिभाषाओं और नियमों का उपयोग करके, प्रदर्शन के निम्नलिखित उपाय दिए जा सकते हैं:

गति वर्धन अनुक्रमिक निष्पादन की तुलना में समानांतर निष्पादन द्वारा प्राप्त गति में वृद्धि है: Sp = T1 / Tp। जब निविष्ट आकार n (बड़े O अंकन पद्धति का उपयोग करके) के लिए गति वर्धन Ω(n) होता है, तो गति वर्धन रैखिक होता है, जो गणना के सरल प्रतिरूप में इष्टतम होता है क्योंकि कार्य नियम का तात्पर्य है कि T1 / Tp ≤ p (स्मृति पदानुक्रम प्रभावों के कारण अभ्यास में अति-रैखिक गति वर्धन हो सकता है)। स्थिति $T 1 / T p = p$ को उतम रेखीय गति वर्धन कहा जाता है। ^[8] एक कलन विधि जो रैखिक गति वर्धन प्रदर्शित करता है उसे मापक्रमणीयता कहा जाता है। ^[9]
दक्षता प्रति संसाधक गति वर्धन $S p / p$ है। ^[9]
समानांतरता अनुपात $T 1 / T \infty$ है। यह किसी भी संख्या में संसाधक पर अधिकतम संभव गति वर्धन का प्रतिनिधित्व करता है। स्पैन नियम के अनुसार, समानता गति को सीमित करती है: यदि $p > T 1 / T \infty$ , तब: ^[8] ${\frac {T_{1}}{T_{p}}}\leq {\frac {T_{1}}{T_{\infty }}}<p.$
शिथिलता $T 1 / (pT \infty)$ है। एक से कम शिथिलता का अर्थ है (स्पैन नियम द्वारा) कि पूर्ण रैखिक गति $p$ संसाधक असंभव है। ^[8]

सीमित संख्या में संसाधक पर निष्पादन

समानांतर कलन विधि का विश्लेषण सामान्यतः इस धारणा के अंतर्गत किया जाता है कि असीमित संख्या में संसाधक उपलब्ध हैं।यह अवास्तविक है, लेकिन कोई समस्या नहीं है, क्योंकि कोई भी गणना जो $N$ संसाधक पर समानांतर में चल सकती है, उसे प्रत्येक संसाधक को कार्य की कई इकाइयों को निष्पादित करने की अनुमति देकर $p < N$ संसाधक पर निष्पादित किया जा सकता है। ब्रेंट का नियम नामक एक परिणाम बताता है कि कोई भी समय $T p$ पर ऐसा अनुकरण कर सकता है, निम्न से घिरा है ^[10]

T_{p}\leq T_{N}+{\frac {T_{1}-T_{N}}{p}},

या, कम सटीक रूप से,^[9]

T_{p}=O\left(T_{N}+{\frac {T_{1}}{p}}\right).

नियम की सीमाओं का एक वैकल्पिक कथन $T p$ ऊपर और नीचे द्वारा

{\frac {T_{1}}{p}}\leq T_{p}\leq {\frac {T_{1}}{p}}+T_{\infty }

.

दिखा रहा है कि अवधि (गहराई) $T \infty$ और काम $T 1$ एक साथ गणना समय पर उचित सीमा प्रदान करते हैं। ^[2]

संदर्भ

↑ Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n² log n) parallel max-flow algorithm". Journal of Algorithms. 3 (2): 128–146. doi:10.1016/0196-6774(82)90013-X.
↑ ^2.0 ^2.1 Brent, Richard P. (1974-04-01). "सामान्य अंकगणितीय अभिव्यक्तियों का समानांतर मूल्यांकन". Journal of the ACM. 21 (2): 201–206. CiteSeerX 10.1.1.100.9361. doi:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.
↑ JaJa, Joseph (1992). An Introduction to Parallel Algorithms. Addison-Wesley. ISBN 978-0-201-54856-3.
↑ Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001). Practical PRAM Programming. Wiley-Interscience. ISBN 978-0-471-35351-5.
↑ Vishkin, Uzi (2009). Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages (PDF). Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion.
↑ Blelloch, Guy (1996). "प्रोग्रामिंग समानांतर एल्गोरिदम" (PDF). Communications of the ACM. 39 (3): 85–97. CiteSeerX 10.1.1.141.5884. doi:10.1145/227234.227246. S2CID 12118850.
↑ Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. pp. 4–5.
↑ ^8.0 ^8.1 ^8.2 ^8.3 ^8.4 ^8.5 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 779–784. ISBN 0-262-03384-4.
↑ ^9.0 ^9.1 ^9.2 ^9.3 ^9.4 Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). समानांतर एल्गोरिदम. CRC Press. p. 10. CiteSeerX 10.1.1.466.8142.
↑ Gustafson, John L. (2011). "ब्रेंट का प्रमेय". Encyclopedia of Parallel Computing. pp. 182–185. doi:10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.

[shiloach-1] Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n² log n) parallel max-flow algorithm". Journal of Algorithms. 3 (2): 128–146. doi:10.1016/0196-6774(82)90013-X.

[brent-2] 2.0 ^2.1 Brent, Richard P. (1974-04-01). "सामान्य अंकगणितीय अभिव्यक्तियों का समानांतर मूल्यांकन". Journal of the ACM. 21 (2): 201–206. CiteSeerX 10.1.1.100.9361. doi:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.

[jaja-3] JaJa, Joseph (1992). An Introduction to Parallel Algorithms. Addison-Wesley. ISBN 978-0-201-54856-3.

[kkt-4] Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001). Practical PRAM Programming. Wiley-Interscience. ISBN 978-0-471-35351-5.

[uv-5] Vishkin, Uzi (2009). Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages (PDF). Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion.

[cacm-6] Blelloch, Guy (1996). "प्रोग्रामिंग समानांतर एल्गोरिदम" (PDF). Communications of the ACM. 39 (3): 85–97. CiteSeerX 10.1.1.141.5884. doi:10.1145/227234.227246. S2CID 12118850.

[spp-7] Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. pp. 4–5.

[clrs-8] 8.0 ^8.1 ^8.2 ^8.3 ^8.4 ^8.5 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 779–784. ISBN 0-262-03384-4.

[casanova-9] 9.0 ^9.1 ^9.2 ^9.3 ^9.4 Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). समानांतर एल्गोरिदम. CRC Press. p. 10. CiteSeerX 10.1.1.466.8142.

[10] Gustafson, John L. (2011). "ब्रेंट का प्रमेय". Encyclopedia of Parallel Computing. pp. 182–185. doi:10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 3: / Line 3: @@
 ==पृष्ठभूमि==
-एक तथाकथित कार्य-अवधि (डब्ल्यूटी) (जिसे कभी-कभी कार्य-गहराई या कार्य-अवधि भी कहा जाता है) ढांचा मूल रूप से शिलोच और विश्किन द्वारा समानांतर कलन विधि की अवधारणा और वर्णन के लिए प्रस्तुत किया गया था। <ref name="shiloach">{{cite journal | last1 = Shiloach | first1 = Yossi
+एक तथाकथित कार्य-अवधि (डब्ल्यूटी) (जिसे कभी-कभी कार्य-गहराई या कार्य-अवधि भी कहा जाता है) प्रतिरूप मूल रूप से शिलोच और विश्किन द्वारा समानांतर कलन विधि की अवधारणा और वर्णन के लिए प्रस्तुत किया गया था। <ref name="shiloach">{{cite journal | last1 = Shiloach | first1 = Yossi
 | last2 = Vishkin | first2 = Uzi
 | year = 1982
@@ Line 11: / Line 11: @@
 | issue =2
 | pages = 128–146
-| doi =10.1016/0196-6774(82)90013-X }}</ref> डब्ल्यूटी ढांचे में, एक समानांतर कलन विधि को सबसे पहले समानांतर वृत्त के संदर्भ में वर्णित किया गया है। प्रत्येक दौर के लिए, किए जाने वाले संचालन की विशेषता होती है, लेकिन कई विषयों को दबाया जा सकता है। उदाहरण के लिए, प्रत्येक दौर में संचालन की संख्या स्पष्ट होने की आवश्यकता नहीं है, संसाधक का उल्लेख करने की आवश्यकता नहीं है और कोई भी जानकारी जो संसाधक को नौकरियों के समनुदेशन में मदद कर सकती है, उसे ध्यान में रखने की आवश्यकता नहीं है। दूसरा, संदमित जानकारी प्रदान की जाती है। संदमित जानकारी का समावेश ब्रेंट के कारण अनुसूचीकरण प्रमेय के प्रमाण द्वारा निर्देशित होता है, <ref name="brent">{{Cite journal|last=Brent|first=Richard P.|date=1974-04-01|title=सामान्य अंकगणितीय अभिव्यक्तियों का समानांतर मूल्यांकन|journal=Journal of the ACM|volume=21|issue=2|pages=201–206|doi=10.1145/321812.321815|issn=0004-5411|citeseerx=10.1.1.100.9361|s2cid=16416106}}</ref> जिसे इस लेख में बाद में समझाया गया है। डब्ल्यूटी प्राधार उपयोगी है क्योंकि यह एक समानांतर कलन विधि के प्रारंभिक विवरण को बहुत सरल बना सकता है, लेकिन उस प्रारंभिक विवरण द्वारा दबाए गए विवरणों को सम्मिलित करना प्रायः बहुत मुश्किल नहीं होता है। उदाहरण के लिए, WT प्राधार को समानांतर कलन विधि पुस्तकों ([[समानांतर रैंडम-एक्सेस मशीन]] पीआरएएम प्रतिरूप के लिए) में मूल प्रस्तुति ढांचे और,साथ ही क्लास नोट्स के रूप में भी अपनाया गया था। <ref name="jaja">{{cite book
+| doi =10.1016/0196-6774(82)90013-X }}</ref> डब्ल्यूटी प्रतिरूप में, एक समानांतर कलन विधि को सबसे पहले समानांतर वृत्त के संदर्भ में वर्णित किया गया है। प्रत्येक वृत्त के लिए, किए जाने वाले संचालन की विशेषता होती है, लेकिन कई विषयों को दबाया जा सकता है। उदाहरण के लिए, प्रत्येक वृत्त में संचालन की संख्या स्पष्ट होने की आवश्यकता नहीं है, संसाधक का उल्लेख करने की आवश्यकता नहीं है और कोई भी जानकारी जो संसाधक को नौकरियों के समनुदेशन में मदद कर सकती है, उसे ध्यान में रखने की आवश्यकता नहीं है। दूसरा, संदमित जानकारी प्रदान की जाती है। संदमित जानकारी का समावेश ब्रेंट के कारण अनुसूचीकरण प्रमेय के प्रमाण द्वारा निर्देशित होता है, <ref name="brent">{{Cite journal|last=Brent|first=Richard P.|date=1974-04-01|title=सामान्य अंकगणितीय अभिव्यक्तियों का समानांतर मूल्यांकन|journal=Journal of the ACM|volume=21|issue=2|pages=201–206|doi=10.1145/321812.321815|issn=0004-5411|citeseerx=10.1.1.100.9361|s2cid=16416106}}</ref> जिसे इस लेख में बाद में समझाया गया है। डब्ल्यूटी प्राधार उपयोगी है क्योंकि यह एक समानांतर कलन विधि के प्रारंभिक विवरण को बहुत सरल बना सकता है, लेकिन उस प्रारंभिक विवरण द्वारा दबाए गए विवरणों को सम्मिलित करना प्रायः बहुत कठिन नहीं होता है। उदाहरण के लिए, डब्ल्यूटी प्राधार को समानांतर कलन विधि पुस्तकों ([[समानांतर रैंडम-एक्सेस मशीन]] पीआरएएम प्रतिरूप के लिए) में मूल प्रस्तुति प्रतिरूप और,साथ ही क्लास नोट्स के रूप में भी अपनाया गया था। <ref name="jaja">{{cite book
   | first = Joseph
   | last = JaJa
@@ Line 43: / Line 43: @@
   | isbn =
   | url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf
-  }}</ref> नीचे दिए गए अवलोकन से पता चलता है कि डब्ल्यूटी ढांचे का उपयोग अधिक सामान्य समानांतर कलन विधि का विश्लेषण करने के लिए कैसे किया जा सकता है, भले ही उनका विवरण डब्ल्यूटी ढांचे के भीतर उपलब्ध न हो।
+  }}</ref> नीचे दिए गए अवलोकन से पता चलता है कि डब्ल्यूटी प्रतिरूप का उपयोग अधिक सामान्य समानांतर कलन विधि का विश्लेषण करने के लिए कैसे किया जा सकता है, भले ही उनका विवरण डब्ल्यूटी प्रतिरूप के भीतर उपलब्ध न हो।
 ==परिभाषाएँ==
-मान लीजिए कि गणना एक ऐसी मशीन पर निष्पादित की जाती है जिसमें {{mvar|p}} संसाधक है। मान लीजिए {{mvar|T<sub>p</sub>}} उस समय को दर्शाता है जो गणना की शुरुआत और उसके अंत के बीच समाप्त होता है। गणना के चलने के समय का विश्लेषण निम्नलिखित धारणाओं पर केंद्रित है:
+मान लीजिए कि गणना एक ऐसी मशीन पर निष्पादित की जाती है जिसमें {{mvar|p}} संसाधक है। मान लीजिए {{mvar|T<sub>p</sub>}} उस समय को दर्शाता है जो गणना के प्रारम्भ और उसके अंत के बीच समाप्त होता है। गणना के चलने के समय का विश्लेषण निम्नलिखित धारणाओं पर केंद्रित है:
 * {{mvar|p}} संसाधक द्वारा निष्पादित गणना का कार्य संसाधक द्वारा निष्पादित आदिम संचालन की कुल संख्या है। संसाधक को समकालिक करने से संचार शिरोपरि को अनदेखा करना, यह एकल संसाधक पर गणना चलाने के लिए उपयोग किए गए समय के बराबर है, जिसे {{math|''T''<sub>1</sub>}} दर्शाया गया है।

v t e Parallel computing
General	Distributed computing Parallel computing Massively parallel Cloud computing High-performance computing Multiprocessing Manycore processor GPGPU Computer network Systolic array
Levels	Bit Instruction Thread Task Data Memory Loop Pipeline
Multithreading	Temporal Simultaneous (SMT) Speculative (SpMT) Preemptive Cooperative Clustered multi-thread (CMT) Hardware scout
Theory	PRAM model PEM model Analysis of parallel algorithms Amdahl's law Gustafson's law Cost efficiency Karp–Flatt metric Slowdown Speedup
Elements	Process Thread Fiber Instruction window Array
Coordination	Multiprocessing Memory coherence Cache coherence Cache invalidation Barrier Synchronization Application checkpointing
Programming	Stream processing Dataflow programming Models Implicit parallelism Explicit parallelism Concurrency Non-blocking algorithm
Hardware	Flynn's taxonomy SISD SIMD Array processing (SIMT) Pipelined processing Associative processing MISD MIMD Dataflow architecture Pipelined processor Superscalar processor Vector processor Multiprocessor symmetric asymmetric Memory shared distributed distributed shared UMA NUMA COMA Massively parallel computer Computer cluster Beowulf cluster Grid computer Hardware acceleration
APIs	Ateji PX Boost Chapel HPX Charm++ Cilk Coarray Fortran CUDA Dryad C++ AMP Global Arrays GPUOpen MPI OpenMP OpenCL OpenHMPP OpenACC Parallel Extensions PVM pthreads RaftLib ROCm UPC TBB ZPL
Problems	Automatic parallelization Deadlock Deterministic algorithm Embarrassingly parallel Parallel slowdown Race condition Software lockout Scalability Starvation
Category: Parallel computing

Anonymous

Search

समानांतर एल्गोरिदम का विश्लेषण: Difference between revisions

Namespaces

More

Page actions

Revision as of 15:26, 21 July 2023

Contents

पृष्ठभूमि

परिभाषाएँ

सीमित संख्या में संसाधक पर निष्पादन

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

समानांतर एल्गोरिदम का विश्लेषण: Difference between revisions

Revision as of 15:26, 21 July 2023

पृष्ठभूमि

परिभाषाएँ

सीमित संख्या में संसाधक पर निष्पादन

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories