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

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

पृष्ठभूमि

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

^[3]

और, ^[4] साथ ही क्लास नोट्स में भी .^[5] नीचे दिए गए अवलोकन से पता चलता है कि डब्ल्यूटी ढांचे का उपयोग अधिक सामान्य समानांतर एल्गोरिदम का विश्लेषण करने के लिए कैसे किया जा सकता है, भले ही उनका विवरण डब्ल्यूटी ढांचे के भीतर उपलब्ध न हो।

परिभाषाएँ

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

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

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

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

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

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

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

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

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

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

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.
↑ ^6.0 ^6.1 ^6.2 ^6.3 ^6.4 ^6.5 Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). समानांतर एल्गोरिदम. CRC Press. p. 10. CiteSeerX 10.1.1.466.8142.
↑ 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.
↑ ^9.0 ^9.1 ^9.2 ^9.3 ^9.4 ^9.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.
↑ 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.

[casanova-6] 6.0 ^6.1 ^6.2 ^6.3 ^6.4 ^6.5 Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). समानांतर एल्गोरिदम. CRC Press. p. 10. CiteSeerX 10.1.1.466.8142.

[cacm-7] 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-8] Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. pp. 4–5.

[clrs-9] 9.0 ^9.1 ^9.2 ^9.3 ^9.4 ^9.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.

[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]

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

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

Namespaces

More

Page actions

Contents

पृष्ठभूमि

परिभाषाएँ

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

पृष्ठभूमि

परिभाषाएँ

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories