समानांतर कलन विधि: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[कंप्यूटर विज्ञान]] में, एक समानांतर [[ कलन विधि ]], एक पारंपरिक सीरियल एल्गोरिथम के विपरीत, एक एल्गोरिथम है जो एक निश्चित समय में कई ऑपरेशन कर सकता है। सार मशीन मॉडल में [[सीरियल एल्गोरिदम]] का वर्णन करना कंप्यूटर विज्ञान की एक परंपरा रही है, जिसे अक्सर [[रैंडम-एक्सेस मशीन]] के रूप में जाना जाता है। इसी तरह, कई कंप्यूटर विज्ञान शोधकर्ताओं ने एक तथाकथित [[समानांतर रैंडम-एक्सेस मशीन]] (PRAM) का उपयोग समानांतर सार मशीन (साझा-स्मृति) के रूप में किया है।<ref>{{cite web |title=समानांतर एल्गोरिदम|first1=Guy E. |last1=Blelloch |first2=Bruce M. |last2=Maggs |publisher=School of Computer Science, [[Carnegie Mellon University]] |location=USA |access-date=2015-07-27 |url=https://www.cs.cmu.edu/~guyb/papers/BM04.pdf}}</ref><ref>{{cite web |title=Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages |first=Uzi |last=Vishkin |publisher=Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion |date=2009 |url=http://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf}}</ref> | [[कंप्यूटर विज्ञान]] में, एक समानांतर [[ कलन विधि |कलन विधि]] , एक पारंपरिक सीरियल एल्गोरिथम के विपरीत, एक एल्गोरिथम है जो एक निश्चित समय में कई ऑपरेशन कर सकता है। सार मशीन मॉडल में [[सीरियल एल्गोरिदम]] का वर्णन करना कंप्यूटर विज्ञान की एक परंपरा रही है, जिसे अक्सर [[रैंडम-एक्सेस मशीन]] के रूप में जाना जाता है। इसी तरह, कई कंप्यूटर विज्ञान शोधकर्ताओं ने एक तथाकथित [[समानांतर रैंडम-एक्सेस मशीन]] (PRAM) का उपयोग समानांतर सार मशीन (साझा-स्मृति) के रूप में किया है।<ref>{{cite web |title=समानांतर एल्गोरिदम|first1=Guy E. |last1=Blelloch |first2=Bruce M. |last2=Maggs |publisher=School of Computer Science, [[Carnegie Mellon University]] |location=USA |access-date=2015-07-27 |url=https://www.cs.cmu.edu/~guyb/papers/BM04.pdf}}</ref><ref>{{cite web |title=Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages |first=Uzi |last=Vishkin |publisher=Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion |date=2009 |url=http://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf}}</ref> | ||
कई समांतर एल्गोरिदम को [[समवर्ती कंप्यूटिंग]] निष्पादित किया जाता है - हालांकि सामान्य [[समवर्ती एल्गोरिदम]] में एक अलग अवधारणा होती है - और इस प्रकार इन अवधारणाओं को अक्सर भ्रमित किया जाता है, एल्गोरिदम का कौन सा पहलू समानांतर है और जो समवर्ती है स्पष्ट रूप से अलग नहीं किया जा रहा है। इसके अलावा, समवर्ती एल्गोरिदम के विपरीत, गैर-समानांतर, गैर-समवर्ती एल्गोरिदम को अक्सर [[अनुक्रमिक एल्गोरिदम]] के रूप में संदर्भित किया जाता है। | कई समांतर एल्गोरिदम को [[समवर्ती कंप्यूटिंग]] निष्पादित किया जाता है - हालांकि सामान्य [[समवर्ती एल्गोरिदम]] में एक अलग अवधारणा होती है - और इस प्रकार इन अवधारणाओं को अक्सर भ्रमित किया जाता है, एल्गोरिदम का कौन सा पहलू समानांतर है और जो समवर्ती है स्पष्ट रूप से अलग नहीं किया जा रहा है। इसके अलावा, समवर्ती एल्गोरिदम के विपरीत, गैर-समानांतर, गैर-समवर्ती एल्गोरिदम को अक्सर [[अनुक्रमिक एल्गोरिदम]] के रूप में संदर्भित किया जाता है। | ||
| Line 10: | Line 10: | ||
कुछ समस्याओं को समानांतर भागों में विभाजित नहीं किया जा सकता है, क्योंकि उन्हें अगले चरण के साथ प्रभावी ढंग से आगे बढ़ने के लिए पिछले चरण के परिणामों की आवश्यकता होती है - इन्हें कहा जाता है{{visible anchor|inherently serial problem}}एस। उदाहरणों में पुनरावृत्त [[संख्यात्मक विश्लेषण]] शामिल हैं, जैसे कि न्यूटन की विधि, तीन-निकाय समस्या के पुनरावृत्त समाधान, और पाई (π) की गणना करने के लिए उपलब्ध अधिकांश एल्गोरिदम। कुछ अनुक्रमिक एल्गोरिदम को स्वचालित समांतरता का उपयोग करके समांतर एल्गोरिदम में परिवर्तित किया जा सकता है।<ref name="MXian1997">{{cite book |author1=Megson G M|author2=Chen Xian|title=नियमित संगणनाओं के एक वर्ग के लिए स्वचालित समानांतरकरण|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22|date=4 January 1997|publisher=World Scientific|isbn=978-981-4498-41-8}}</ref> | कुछ समस्याओं को समानांतर भागों में विभाजित नहीं किया जा सकता है, क्योंकि उन्हें अगले चरण के साथ प्रभावी ढंग से आगे बढ़ने के लिए पिछले चरण के परिणामों की आवश्यकता होती है - इन्हें कहा जाता है{{visible anchor|inherently serial problem}}एस। उदाहरणों में पुनरावृत्त [[संख्यात्मक विश्लेषण]] शामिल हैं, जैसे कि न्यूटन की विधि, तीन-निकाय समस्या के पुनरावृत्त समाधान, और पाई (π) की गणना करने के लिए उपलब्ध अधिकांश एल्गोरिदम। कुछ अनुक्रमिक एल्गोरिदम को स्वचालित समांतरता का उपयोग करके समांतर एल्गोरिदम में परिवर्तित किया जा सकता है।<ref name="MXian1997">{{cite book |author1=Megson G M|author2=Chen Xian|title=नियमित संगणनाओं के एक वर्ग के लिए स्वचालित समानांतरकरण|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22|date=4 January 1997|publisher=World Scientific|isbn=978-981-4498-41-8}}</ref> | ||
== प्रेरणा == | == प्रेरणा == | ||
[[ बहु ]] सिस्टम में पर्याप्त सुधार और [[ मल्टी कोर ]] प्रोसेसर के उदय के कारण 2000 के दशक की शुरुआत से व्यक्तिगत उपकरणों पर समानांतर एल्गोरिदम अधिक सामान्य हो गए हैं। 2004 के अंत तक, सिंगल-कोर प्रोसेसर का प्रदर्शन [[आवृत्ति स्केलिंग]] के माध्यम से तेजी से बढ़ा, और इस प्रकार एक ही [[THROUGHPUT]] के साथ कई धीमे कोर वाले एक की तुलना में एक सिंगल फास्ट कोर के साथ एक कंप्यूटर बनाना आसान था, इसलिए मल्टीकोर सिस्टम अधिक सीमित थे उपयोग। हालाँकि, 2004 के बाद से, आवृत्ति स्केलिंग एक दीवार से टकराई, और इस प्रकार मल्टीकोर सिस्टम अधिक व्यापक हो गए, जिससे अधिक सामान्य उपयोग के समानांतर एल्गोरिदम बन गए। | [[ बहु | बहु]] सिस्टम में पर्याप्त सुधार और [[ मल्टी कोर |मल्टी कोर]] प्रोसेसर के उदय के कारण 2000 के दशक की शुरुआत से व्यक्तिगत उपकरणों पर समानांतर एल्गोरिदम अधिक सामान्य हो गए हैं। 2004 के अंत तक, सिंगल-कोर प्रोसेसर का प्रदर्शन [[आवृत्ति स्केलिंग]] के माध्यम से तेजी से बढ़ा, और इस प्रकार एक ही [[THROUGHPUT]] के साथ कई धीमे कोर वाले एक की तुलना में एक सिंगल फास्ट कोर के साथ एक कंप्यूटर बनाना आसान था, इसलिए मल्टीकोर सिस्टम अधिक सीमित थे उपयोग। हालाँकि, 2004 के बाद से, आवृत्ति स्केलिंग एक दीवार से टकराई, और इस प्रकार मल्टीकोर सिस्टम अधिक व्यापक हो गए, जिससे अधिक सामान्य उपयोग के समानांतर एल्गोरिदम बन गए। | ||
== मुद्दे == | == मुद्दे == | ||
| Line 32: | Line 32: | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[ बहु-एजेंट प्रणाली ]] (एमएएस) | * [[ बहु-एजेंट प्रणाली | बहु-एजेंट प्रणाली]] (एमएएस) | ||
* [[मैट्रिक्स गुणन के लिए समानांतर एल्गोरिदम]] | * [[मैट्रिक्स गुणन के लिए समानांतर एल्गोरिदम]] | ||
* न्यूनतम फैले हुए पेड़ों के लिए समानांतर एल्गोरिदम | * न्यूनतम फैले हुए पेड़ों के लिए समानांतर एल्गोरिदम | ||
Revision as of 23:53, 9 May 2023
कंप्यूटर विज्ञान में, एक समानांतर कलन विधि , एक पारंपरिक सीरियल एल्गोरिथम के विपरीत, एक एल्गोरिथम है जो एक निश्चित समय में कई ऑपरेशन कर सकता है। सार मशीन मॉडल में सीरियल एल्गोरिदम का वर्णन करना कंप्यूटर विज्ञान की एक परंपरा रही है, जिसे अक्सर रैंडम-एक्सेस मशीन के रूप में जाना जाता है। इसी तरह, कई कंप्यूटर विज्ञान शोधकर्ताओं ने एक तथाकथित समानांतर रैंडम-एक्सेस मशीन (PRAM) का उपयोग समानांतर सार मशीन (साझा-स्मृति) के रूप में किया है।[1][2] कई समांतर एल्गोरिदम को समवर्ती कंप्यूटिंग निष्पादित किया जाता है - हालांकि सामान्य समवर्ती एल्गोरिदम में एक अलग अवधारणा होती है - और इस प्रकार इन अवधारणाओं को अक्सर भ्रमित किया जाता है, एल्गोरिदम का कौन सा पहलू समानांतर है और जो समवर्ती है स्पष्ट रूप से अलग नहीं किया जा रहा है। इसके अलावा, समवर्ती एल्गोरिदम के विपरीत, गैर-समानांतर, गैर-समवर्ती एल्गोरिदम को अक्सर अनुक्रमिक एल्गोरिदम के रूप में संदर्भित किया जाता है।
समानांतरता
एल्गोरिथम इस बात में काफी भिन्न होते हैं कि वे कितने समानांतर हैं, आसानी से समानांतर होने से लेकर पूरी तरह से अद्वितीय तक। इसके अलावा, दी गई समस्या अलग-अलग एल्गोरिदम को समायोजित कर सकती है, जो कम या ज्यादा समानांतर हो सकती है।
कुछ समस्याओं को इस तरह से टुकड़ों में विभाजित करना आसान होता है - इन्हें शर्मनाक समानांतर समस्याएँ कहा जाता है। उदाहरणों में रुबिक के क्यूब्स को हल करने के लिए कई एल्गोरिदम शामिल हैं और उन मूल्यों को ढूंढते हैं जो किसी दिए गए साहचर्य सरणी में परिणामित होते हैं।
कुछ समस्याओं को समानांतर भागों में विभाजित नहीं किया जा सकता है, क्योंकि उन्हें अगले चरण के साथ प्रभावी ढंग से आगे बढ़ने के लिए पिछले चरण के परिणामों की आवश्यकता होती है - इन्हें कहा जाता हैinherently serial problemएस। उदाहरणों में पुनरावृत्त संख्यात्मक विश्लेषण शामिल हैं, जैसे कि न्यूटन की विधि, तीन-निकाय समस्या के पुनरावृत्त समाधान, और पाई (π) की गणना करने के लिए उपलब्ध अधिकांश एल्गोरिदम। कुछ अनुक्रमिक एल्गोरिदम को स्वचालित समांतरता का उपयोग करके समांतर एल्गोरिदम में परिवर्तित किया जा सकता है।[3]
प्रेरणा
बहु सिस्टम में पर्याप्त सुधार और मल्टी कोर प्रोसेसर के उदय के कारण 2000 के दशक की शुरुआत से व्यक्तिगत उपकरणों पर समानांतर एल्गोरिदम अधिक सामान्य हो गए हैं। 2004 के अंत तक, सिंगल-कोर प्रोसेसर का प्रदर्शन आवृत्ति स्केलिंग के माध्यम से तेजी से बढ़ा, और इस प्रकार एक ही THROUGHPUT के साथ कई धीमे कोर वाले एक की तुलना में एक सिंगल फास्ट कोर के साथ एक कंप्यूटर बनाना आसान था, इसलिए मल्टीकोर सिस्टम अधिक सीमित थे उपयोग। हालाँकि, 2004 के बाद से, आवृत्ति स्केलिंग एक दीवार से टकराई, और इस प्रकार मल्टीकोर सिस्टम अधिक व्यापक हो गए, जिससे अधिक सामान्य उपयोग के समानांतर एल्गोरिदम बन गए।
मुद्दे
संचार
सीरियल एल्गोरिदम की लागत या जटिलता का अनुमान अंतरिक्ष (मेमोरी) और समय (प्रोसेसर चक्र) के संदर्भ में लगाया जाता है। समानांतर एल्गोरिदम को एक और संसाधन, विभिन्न प्रोसेसर के बीच संचार को अनुकूलित करने की आवश्यकता होती है। दो तरह से समानांतर प्रोसेसर संचार, साझा स्मृति या संदेश देना कर रहे हैं।
साझा मेमोरी प्रोसेसिंग को डेटा के लिए अतिरिक्त लॉक (कंप्यूटर विज्ञान) की आवश्यकता होती है, अतिरिक्त प्रोसेसर और बस चक्रों के ओवरहेड को लागू करता है, और एल्गोरिथम के कुछ हिस्से को क्रमबद्ध भी करता है।
संदेश पासिंग प्रोसेसिंग चैनल और संदेश बॉक्स का उपयोग करता है लेकिन यह संचार बस में ट्रांसफर ओवरहेड जोड़ता है, कतारों और संदेश बॉक्स के लिए अतिरिक्त मेमोरी की आवश्यकता होती है और संदेशों में विलंबता होती है। समानांतर प्रोसेसर के डिजाइन विशेष बस (कंप्यूटिंग) जैसे क्रॉसबार स्विच का उपयोग करते हैं ताकि संचार ओवरहेड छोटा हो लेकिन यह समानांतर एल्गोरिदम है जो यातायात की मात्रा तय करता है।
यदि अतिरिक्त प्रोसेसर का संचार ओवरहेड दूसरे प्रोसेसर को जोड़ने के लाभ से अधिक है, तो समानांतर मंदी का सामना करना पड़ता है।
भार संतुलन
समांतर एल्गोरिदम के साथ एक और समस्या यह सुनिश्चित कर रही है कि इनपुट आकार संतुलित होने के बजाय लोड (समग्र कार्य) संतुलित है, यह सुनिश्चित करके वे उचित रूप से लोड संतुलन (कंप्यूटिंग) कर रहे हैं। उदाहरण के लिए, एक से लेकर एक लाख तक की सभी संख्याओं की जांच प्रोसेसर के बीच विभाजित करना आसान है; हालाँकि, यदि संख्याओं को समान रूप से विभाजित किया जाता है (1-1,000, 1,001-2,000, आदि), तो काम की मात्रा असंतुलित हो जाएगी, क्योंकि इस एल्गोरिथम द्वारा छोटी संख्याओं को संसाधित करना आसान होता है (प्राथमिकता के लिए परीक्षण करना आसान), और इस प्रकार कुछ प्रोसेसरों को दूसरों की तुलना में अधिक काम करना होगा, जो लोड किए गए प्रोसेसर के पूर्ण होने तक निष्क्रिय रहेंगे।
वितरित एल्गोरिदम
समानांतर एल्गोरिदम का एक उपप्रकार, वितरित एल्गोरिदम, क्लस्टर कंप्यूटिंग और वितरित कंप्यूटिंग वातावरण में काम करने के लिए डिज़ाइन किए गए एल्गोरिदम हैं, जहां शास्त्रीय समानांतर एल्गोरिदम के दायरे से परे अतिरिक्त चिंताओं को संबोधित करने की आवश्यकता होती है।
यह भी देखें
- बहु-एजेंट प्रणाली (एमएएस)
- मैट्रिक्स गुणन के लिए समानांतर एल्गोरिदम
- न्यूनतम फैले हुए पेड़ों के लिए समानांतर एल्गोरिदम
- समानांतर कंप्यूटिंग
- पैरारियल
संदर्भ
- ↑ Blelloch, Guy E.; Maggs, Bruce M. "समानांतर एल्गोरिदम" (PDF). USA: School of Computer Science, Carnegie Mellon University. Retrieved 2015-07-27.
- ↑ 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.
- ↑ Megson G M; Chen Xian (4 January 1997). नियमित संगणनाओं के एक वर्ग के लिए स्वचालित समानांतरकरण. World Scientific. ISBN 978-981-4498-41-8.
बाहरी संबंध
- Designing and Building Parallel Programs, US Argonne National Laboratory
| General | |
|---|---|
| Levels | |
| Multithreading |
|
| Theory | |
| Elements | |
| Coordination | |
| Programming | |
| Hardware | |
| APIs | |
| Problems | |
