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

Revision as of 08:42, 21 July 2023

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

पृष्ठभूमि

एक तथाकथित कार्य-अवधि (डब्ल्यूटी) (जिसे कभी-कभी कार्य-गहराई या कार्य-अवधि भी कहा जाता है) ढांचा मूल रूप से शिलोच और विश्किन द्वारा समानांतर कलन विधि की अवधारणा और वर्णन के लिए प्रस्तुत किया गया था। ^[1] डब्ल्यूटी ढांचे में, एक समानांतर कलन विधि को सबसे पहले समानांतर वृत्त के संदर्भ में वर्णित किया गया है। प्रत्येक दौर के लिए, किए जाने वाले संचालन की विशेषता होती है, लेकिन कई विषयों को दबाया जा सकता है। उदाहरण के लिए, प्रत्येक दौर में संचालन की संख्या स्पष्ट होने की आवश्यकता नहीं है, संसाधक का उल्लेख करने की आवश्यकता नहीं है और कोई भी जानकारी जो संसाधक को नौकरियों के समनुदेशन में मदद कर सकती है, उसे ध्यान में रखने की आवश्यकता नहीं है। दूसरा, संदमित जानकारी प्रदान की जाती है। संदमित जानकारी का समावेश ब्रेंट के कारण अनुसूचीकरण प्रमेय के प्रमाण द्वारा निर्देशित होता है, ^[2] जिसे इस लेख में बाद में समझाया गया है। डब्ल्यूटी प्राधार उपयोगी है क्योंकि यह एक समानांतर कलन विधि के प्रारंभिक विवरण को बहुत सरल बना सकता है, लेकिन उस प्रारंभिक विवरण द्वारा दबाए गए विवरणों को सम्मिलित करना प्रायः बहुत मुश्किल नहीं होता है। उदाहरण के लिए, WT प्राधार को समानांतर कलन विधि पुस्तकों (समानांतर रैंडम-एक्सेस मशीन पीआरएएम प्रतिरूप के लिए) में मूल प्रस्तुति ढांचे और,साथ ही क्लास नोट्स के रूप में भी अपनाया गया था। ^[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 1: / Line 1: @@
-कंप्यूटर विज्ञान में, समानांतर [[एल्गोरिदम]] का विश्लेषण समानांतर में निष्पादित एल्गोरिदम की कम्प्यूटेशनल जटिलता को खोजने की प्रक्रिया है - उन्हें निष्पादित करने के लिए आवश्यक समय, भंडारण या अन्य संसाधनों की मात्रा। कई मायनों में, समानांतर [[एल्गोरिदम का विश्लेषण]] एल्गोरिदम के विश्लेषण के समान है, लेकिन आम तौर पर इसमें अधिक शामिल होता है क्योंकि किसी को निष्पादन के कई सहयोगी थ्रेड्स के व्यवहार के बारे में तर्क करना चाहिए। समानांतर विश्लेषण के प्राथमिक लक्ष्यों में से एक यह समझना है कि प्रोसेसर की संख्या बदलने पर समानांतर एल्गोरिदम के संसाधनों (गति, स्थान, आदि) का उपयोग कैसे बदलता है।
+कंप्यूटर विज्ञान में, '''समानांतर [[एल्गोरिदम|कलन विधि]] का विश्लेषण''' समानांतर में निष्पादित कलन विधि की अभिकलनात्मक जटिलता को खोजने की प्रक्रिया है - उन्हें निष्पादित करने के लिए आवश्यक समय, भंडारण या अन्य संसाधनों की मात्रा है। कई मायनों में, समानांतर [[एल्गोरिदम का विश्लेषण|कलन विधि का विश्लेषण]] कलन विधि के विश्लेषण के समान है, लेकिन सामान्यतः इसमें अधिक सम्मिलित होता है क्योंकि किसी को निष्पादन के कई सहयोगी थ्रेड्स के व्यवहार के बारे में तर्क करना चाहिए। समानांतर विश्लेषण के प्राथमिक लक्ष्यों में से एक यह समझना है कि संसाधक की संख्या बदलने पर समानांतर कलन विधि के संसाधनों (गति, स्थान, आदि) का उपयोग कैसे बदलता है।
 ==पृष्ठभूमि==
-एक तथाकथित कार्य-समय (डब्ल्यूटी) (जिसे कभी-कभी कार्य-गहराई या कार्य-अवधि भी कहा जाता है) ढांचा मूल रूप से शिलोच और विश्किन द्वारा पेश किया गया था। <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>
+| 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
-समानांतर एल्गोरिदम की अवधारणा और वर्णन के लिए।
-डब्ल्यूटी ढांचे में, एक समानांतर एल्गोरिदम को सबसे पहले समानांतर राउंड के संदर्भ में वर्णित किया गया है। प्रत्येक दौर के लिए, किए जाने वाले ऑपरेशनों की विशेषता होती है, लेकिन कई मुद्दों को दबाया जा सकता है। उदाहरण के लिए, प्रत्येक दौर में संचालन की संख्या स्पष्ट होने की आवश्यकता नहीं है, प्रोसेसर का उल्लेख करने की आवश्यकता नहीं है और कोई भी जानकारी जो प्रोसेसर को नौकरियों के असाइनमेंट में मदद कर सकती है, उसे ध्यान में रखने की आवश्यकता नहीं है। दूसरा, दबी हुई जानकारी प्रदान की जाती है। दबी हुई जानकारी का समावेश ब्रेंट के कारण शेड्यूलिंग प्रमेय के प्रमाण द्वारा निर्देशित होता है,<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 फ्रेमवर्क को समानांतर एल्गोरिदम पुस्तकों ([[समानांतर रैंडम-एक्सेस मशीन]] PRAM मॉडल के लिए) में मूल प्रस्तुति ढांचे के रूप में अपनाया गया था।
- <ref name="jaja">{{cite book
   | first = Joseph
   | last = JaJa
@@ Line 23: / Line 20: @@
   | isbn = 978-0-201-54856-3
   | title-link = An Introduction to Parallel Algorithms
-  }}</ref>
+  }}</ref>  <ref name="kkt">{{cite book
-और, <ref name="kkt">{{cite book
   | first1 = Jorg
   | last1 = Keller
@@ Line 37: / Line 33: @@
   | isbn = 978-0-471-35351-5
   | title-link = Practical PRAM Programming
-  }}</ref> साथ ही क्लास नोट्स में भी
+  }}</ref> <ref name="uv">{{cite book
-.<ref name="uv">{{cite book
   | authorlink = Uzi Vishkin
   | first = Uzi
@@ Line 48: / 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}}प्रोसेसर प्रोसेसर द्वारा निष्पादित आदिम परिचालनों की कुल संख्या है।<ref name="casanova">{{cite book |title=समानांतर एल्गोरिदम|first1=Henri |last1=Casanova |first2=Arnaud |last2=Legrand |first3=Yves |last3=Robert |publisher=CRC Press |year=2008 |pages=10|citeseerx=10.1.1.466.8142 }}</ref> प्रोसेसर को सिंक्रनाइज़ करने से संचार ओवरहेड को अनदेखा करना, यह एकल प्रोसेसर पर गणना चलाने के लिए उपयोग किए गए समय के बराबर है, जिसे दर्शाया गया है {{math|''T''<sub>1</sub>}}.
+* {{mvar|p}} संसाधक द्वारा निष्पादित गणना का कार्य संसाधक द्वारा निष्पादित आदिम संचालन की कुल संख्या है। संसाधक को समकालिक करने से संचार शिरोपरि को अनदेखा करना, यह एकल संसाधक पर गणना चलाने के लिए उपयोग किए गए समय के बराबर है, जिसे {{math|''T''<sub>1</sub>}} दर्शाया गया है।
-* गहराई या स्पैन संचालन की सबसे लंबी श्रृंखला की लंबाई है जिसे [[डेटा निर्भरता]] (महत्वपूर्ण पथ) के कारण क्रमिक रूप से निष्पादित करना पड़ता है। गहराई को गणना की महत्वपूर्ण पथ लंबाई भी कहा जा सकता है।<ref name="cacm">{{cite journal |first=Guy |last=Blelloch |title=प्रोग्रामिंग समानांतर एल्गोरिदम|journal=[[Communications of the ACM]] |volume=39 |issue=3 |year=1996 |doi=10.1145/227234.227246 |url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf |pages=85–97|citeseerx=10.1.1.141.5884 |s2cid=12118850 }}</ref> समानांतर एल्गोरिदम को डिजाइन करने में गहराई/स्पैन को कम करना महत्वपूर्ण है, क्योंकि गहराई/स्पैन न्यूनतम संभव निष्पादन समय निर्धारित करता है।<ref name="spp">{{cite book |author1=Michael McCool |author2=James Reinders |author3=Arch Robison |title=Structured Parallel Programming: Patterns for Efficient Computation |publisher=Elsevier |year=2013 |pages=4–5}}</ref> वैकल्पिक रूप से, अवधि को समय के रूप में परिभाषित किया जा सकता है {{math|''T''<sub>∞</sub>}} अनंत संख्या में प्रोसेसर वाली एक आदर्श मशीन का उपयोग करके कंप्यूटिंग खर्च की।<ref name="clrs">{{Introduction to Algorithms|3|pages=779–784}}</ref>
+* मध्यमार्ग या अवधि संचालन की सबसे लंबी श्रृंखला की लंबाई है जिसे [[डेटा निर्भरता]] (महत्वपूर्ण पथ) के कारण क्रमिक रूप से निष्पादित करना पड़ता है। गहराई को गणना की महत्वपूर्ण पथ लंबाई भी कहा जा सकता है। <ref name="cacm">{{cite journal |first=Guy |last=Blelloch |title=प्रोग्रामिंग समानांतर एल्गोरिदम|journal=[[Communications of the ACM]] |volume=39 |issue=3 |year=1996 |doi=10.1145/227234.227246 |url=https://www.cs.cmu.edu/afs/cs/Web/People/blelloch/papers/B85.pdf |pages=85–97|citeseerx=10.1.1.141.5884 |s2cid=12118850 }}</ref> समानांतर कलन विधि को अभिकल्पित करने में मध्यमार्ग/अवधि को कम करना महत्वपूर्ण है, क्योंकि मध्यमार्ग/अवधि न्यूनतम संभव निष्पादन समय निर्धारित करता है। <ref name="spp">{{cite book |author1=Michael McCool |author2=James Reinders |author3=Arch Robison |title=Structured Parallel Programming: Patterns for Efficient Computation |publisher=Elsevier |year=2013 |pages=4–5}}</ref> वैकल्पिक रूप से, स्पैन को अनंत संख्या में संसाधक के साथ एक आदर्श मशीन का उपयोग करके कंप्यूटिंग में बिताए गए समय T∞ के रूप में परिभाषित किया जा सकता है। <ref name="clrs">{{Introduction to Algorithms|3|pages=779–784}}</ref>
-* गणना की लागत मात्रा है {{mvar|pT<sub>p</sub>}}. यह सभी प्रोसेसरों द्वारा कंप्यूटिंग और प्रतीक्षा दोनों में खर्च किए गए कुल समय को व्यक्त करता है।<ref name="casanova"/>
+* गणना की लागत मात्रा {{mvar|pT<sub>p</sub>}} है। यह सभी संसाधक द्वारा कंप्यूटिंग और प्रतीक्षा दोनों में खर्च किए गए कुल समय को व्यक्त करता है। <ref name="casanova">{{cite book |title=समानांतर एल्गोरिदम|first1=Henri |last1=Casanova |first2=Arnaud |last2=Legrand |first3=Yves |last3=Robert |publisher=CRC Press |year=2008 |pages=10|citeseerx=10.1.1.466.8142 }}</ref>
 कार्य, अवधि और लागत की परिभाषाओं से कई उपयोगी परिणाम मिलते हैं:
-*कार्य कानून. लागत हमेशा कम से कम काम की होती है: {{math|''pT<sub>p</sub>'' ≥ ''T''<sub>1</sub>}}. यह इस तथ्य से पता चलता है कि {{mvar|p}} प्रोसेसर अधिकतम प्रदर्शन कर सकते हैं {{mvar|p}}समानांतर में संचालन।<ref name="casanova"/><ref name="clrs"/>* स्पैन कानून. एक सीमित संख्या {{mvar|p}} प्रोसेसर अनंत संख्या से बेहतर प्रदर्शन नहीं कर सकते, इसलिए {{math|''T<sub>p</sub>'' ≥ ''T''<sub>∞</sub>}}.<ref name="clrs"/>
+*कार्य नियम. लागत हमेशा कम से कम काम की होती है: {{math|''pT<sub>p</sub>'' ≥ ''T''<sub>1</sub>}}। यह इस तथ्य से पता चलता है कि {{mvar|p}} संसाधक अधिकतम प्रदर्शन कर सकते हैं। <ref name="casanova"/><ref name="clrs"/>
+*स्पैन नियम. एक सीमित संख्या {{mvar|p}} संसाधक अनंत संख्या से बेहतर प्रदर्शन नहीं कर सकते, इसलिए {{math|''T<sub>p</sub>'' ≥ ''T''<sub>∞</sub>}} है। <ref name="clrs" />
-इन परिभाषाओं और कानूनों का उपयोग करके, प्रदर्शन के निम्नलिखित उपाय दिए जा सकते हैं:
+इन परिभाषाओं और नियमों का उपयोग करके, प्रदर्शन के निम्नलिखित उपाय दिए जा सकते हैं:
-* [[ गति बढ़ाना ]] अनुक्रमिक निष्पादन की तुलना में समानांतर निष्पादन द्वारा प्राप्त गति में वृद्धि है: {{math|1=''S<sub>p</sub>'' = ''T''<sub>1</sub> / ''T<sub>p</sub>''}}. जब स्पीडअप होता है {{math|Ω(''n'')}} इनपुट आकार के लिए {{mvar|n}} ([[बड़ा ओ अंकन]] का उपयोग करके), स्पीडअप रैखिक है, जो गणना के सरल मॉडल में इष्टतम है क्योंकि कार्य कानून का तात्पर्य है कि {{math|''T''<sub>1</sub> / ''T<sub>p</sub>'' ≤ ''p''}} (स्पीडअप#सुपर-लीनियर स्पीडअप|सुपर-लीनियर स्पीडअप मेमोरी पदानुक्रम प्रभावों के कारण व्यवहार में हो सकता है)। स्थिति {{math|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''p''}} को परफेक्ट लीनियर स्पीडअप कहा जाता है।<ref name="clrs"/>एक एल्गोरिदम जो रैखिक स्पीडअप प्रदर्शित करता है उसे [[ scalability ]] कहा जाता है।<ref name="casanova"/>* दक्षता प्रति प्रोसेसर स्पीडअप है, {{math|''S<sub>p</sub>'' / ''p''}}.<ref name="casanova"/>*समानांतरता अनुपात है {{math|''T''<sub>1</sub> / ''T''<sub>∞</sub>}}. यह किसी भी संख्या में प्रोसेसर पर अधिकतम संभव स्पीडअप का प्रतिनिधित्व करता है। स्पैन कानून के अनुसार, समानता गति को सीमित करती है: यदि {{math|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, तब:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>
+* [[ गति बढ़ाना |गति वर्धन]] अनुक्रमिक निष्पादन की तुलना में समानांतर निष्पादन द्वारा प्राप्त गति में वृद्धि है: Sp = T1 / Tp। जब  निविष्ट आकार n (बड़े O अंकन पद्धति का उपयोग करके) के लिए गति वर्धन Ω(n) होता है, तो गति वर्धन रैखिक होता है, जो गणना के सरल प्रतिरूप में इष्टतम होता है क्योंकि कार्य नियम का तात्पर्य है कि T1 / Tp ≤ p (स्मृति पदानुक्रम प्रभावों के कारण अभ्यास में अति-रैखिक गति वर्धन हो सकता है)। स्थिति {{math|1=''T''<sub>1</sub> / ''T<sub>p</sub>'' = ''p''}} को उतम रेखीय गति वर्धन कहा जाता है। <ref name="clrs"/> एक कलन विधि जो रैखिक गति वर्धन प्रदर्शित करता है उसे [[ scalability |मापक्रमणीयता]] कहा जाता है। <ref name="casanova"/>
-* ढिलाई है {{math|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}}. एक से कम ढिलाई का अर्थ है (स्पैन कानून द्वारा) कि पूर्ण रैखिक गति असंभव है {{mvar|p}} प्रोसेसर.<ref name="clrs" />
+*दक्षता प्रति संसाधक गति वर्धन {{math|''S<sub>p</sub>'' / ''p''}} है। <ref name="casanova" />
+*समानांतरता अनुपात {{math|''T''<sub>1</sub> / ''T''<sub>∞</sub>}} है। यह किसी भी संख्या में संसाधक पर अधिकतम संभव गति वर्धन का प्रतिनिधित्व करता है। स्पैन नियम के अनुसार, समानता गति को सीमित करती है: यदि {{math|''p'' > ''T''<sub>1</sub> / ''T''<sub>∞</sub>}}, तब: <ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>
+* शिथिलता {{math|''T''<sub>1</sub> / (''pT''<sub>∞</sub>)}} है। एक से कम शिथिलता का अर्थ है (स्पैन नियम द्वारा) कि पूर्ण रैखिक गति {{mvar|p}} संसाधक असंभव है। <ref name="clrs" />
-==सीमित संख्या में प्रोसेसर पर निष्पादन==
+==सीमित संख्या में संसाधक पर निष्पादन==
-समानांतर एल्गोरिदम का विश्लेषण आमतौर पर इस धारणा के तहत किया जाता है कि असीमित संख्या में प्रोसेसर उपलब्ध हैं। यह अवास्तविक है, लेकिन कोई समस्या नहीं है, क्योंकि कोई भी गणना समानांतर में चल सकती है {{mvar|N}} प्रोसेसर पर क्रियान्वित किया जा सकता है {{math|''p'' < ''N''}} प्रत्येक प्रोसेसर को कार्य की एकाधिक इकाइयों को निष्पादित करने की अनुमति देकर प्रोसेसर। ब्रेंट का नियम नामक एक परिणाम बताता है कि कोई भी समय पर ऐसा अनुकरण कर सकता है {{mvar|T<sub>p</sub>}}, से घिरा<ref>{{cite encyclopedia |encyclopedia=Encyclopedia of Parallel Computing |year=2011 |pages=182–185 |title=ब्रेंट का प्रमेय|first=John L. |last=Gustafson |doi=10.1007/978-0-387-09766-4_80 |isbn=978-0-387-09765-7 }}</ref>
+समानांतर कलन विधि का विश्लेषण सामान्यतः इस धारणा के अंतर्गत किया जाता है कि असीमित संख्या में संसाधक उपलब्ध हैं।यह अवास्तविक है, लेकिन कोई समस्या नहीं है, क्योंकि कोई भी गणना जो {{mvar|N}} संसाधक पर समानांतर में चल सकती है, उसे प्रत्येक संसाधक को कार्य की कई इकाइयों को निष्पादित करने की अनुमति देकर {{math|''p'' < ''N''}} संसाधक पर निष्पादित किया जा सकता है। ब्रेंट का नियम नामक एक परिणाम बताता है कि कोई भी समय {{mvar|T<sub>p</sub>}} पर ऐसा अनुकरण कर सकता है, निम्न से घिरा है <ref>{{cite encyclopedia |encyclopedia=Encyclopedia of Parallel Computing |year=2011 |pages=182–185 |title=ब्रेंट का प्रमेय|first=John L. |last=Gustafson |doi=10.1007/978-0-387-09766-4_80 |isbn=978-0-387-09765-7 }}</ref>
 :<math>T_p \leq T_N + \frac{T_1 - T_N}{p},</math>
 या, कम सटीक रूप से,<ref name="casanova"/>
 :<math>T_p = O \left( T_N + \frac{T_1}{p} \right) .</math>
-क़ानून की सीमाओं का एक वैकल्पिक कथन {{mvar|T<sub>p</sub>}} ऊपर और नीचे द्वारा
+नियम की सीमाओं का एक वैकल्पिक कथन {{mvar|T<sub>p</sub>}} ऊपर और नीचे द्वारा
 :<math>\frac{T_1}{p} \leq T_p \leq \frac{T_1}{p} + T_\infty</math>.
-दिखा रहा है कि अवधि (गहराई) {{math|''T''<sub>∞</sub>}} और काम {{math|''T''<sub>1</sub>}} एक साथ गणना समय पर उचित सीमा प्रदान करते हैं।<ref name="brent"/>
+दिखा रहा है कि अवधि (गहराई) {{math|''T''<sub>∞</sub>}} और काम {{math|''T''<sub>1</sub>}} एक साथ गणना समय पर उचित सीमा प्रदान करते हैं। <ref name="brent"/>

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 08:42, 21 July 2023

Contents

पृष्ठभूमि

परिभाषाएँ

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 08:42, 21 July 2023

पृष्ठभूमि

परिभाषाएँ

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories