समानांतर कलन विधि: 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>कई समांतर एल्गोरिदम को [[समवर्ती कंप्यूटिंग]] निष्पादित किया जाता है - चूंकि सामान्य [[समवर्ती एल्गोरिदम]] में अलग अवधारणा होती है और इस प्रकार इन अवधारणाओं को अधिकांशतः भ्रमित किया जाता है, एल्गोरिदम का कौन सा पहलू समानांतर है और जो समवर्ती है स्पष्ट रूप से अलग नहीं किया जा रहा है। इसके अतिरिक्त, समवर्ती एल्गोरिदम के विपरीत, अ-समानांतर, अ-समवर्ती एल्गोरिदम को अधिकांशतः [[अनुक्रमिक एल्गोरिदम]] के रूप में संदर्भित किया जाता है। | ||
== समानांतरता == | == समानांतरता == | ||
| Line 6: | Line 6: | ||
एल्गोरिथम इस बात में पर्याप्त भिन्न होते हैं कि वे कितने समानांतर हैं, सरलता से समानांतर होने से लेकर पूरी प्रकार से अद्वितीय तक इसके अतिरिक्त, दी गई समस्या अलग-अलग एल्गोरिदम को समायोजित कर सकती है, जो कम या ज्यादा समानांतर हो सकती है। | एल्गोरिथम इस बात में पर्याप्त भिन्न होते हैं कि वे कितने समानांतर हैं, सरलता से समानांतर होने से लेकर पूरी प्रकार से अद्वितीय तक इसके अतिरिक्त, दी गई समस्या अलग-अलग एल्गोरिदम को समायोजित कर सकती है, जो कम या ज्यादा समानांतर हो सकती है। | ||
कुछ समस्याओं को इस प्रकार से टुकड़ों में विभाजित करना सरल | कुछ समस्याओं को इस प्रकार से टुकड़ों में विभाजित करना सरल होता है - इन्हें [[शर्मनाक समानांतर]] समस्याएँ कहा जाता है। उदाहरणों में रुबिक के क्यूब्स को हल करने के लिए कई एल्गोरिदम सम्मलित हैं और उन मूल्यों को ढूंढते हैं जो किसी दिए गए [[साहचर्य सरणी]] में परिणामित होते हैं। | ||
कुछ समस्याओं को समानांतर भागों में विभाजित नहीं किया जा सकता है, क्योंकि उन्हें अगले चरण के साथ प्रभावी ढंग से आगे बढ़ने के लिए पिछले चरण के परिणामों की आवश्यकता होती है - इन्हें कहा जाता है {{visible anchor|स्वाभाविक रूप से धारावाहिक समस्या}}एस। उदाहरणों में पुनरावृत्त [[संख्यात्मक विश्लेषण]] सम्मलित हैं, जैसे कि न्यूटन की विधि, तीन-निकाय समस्या के पुनरावृत्त समाधान और पाई (π) की गणना करने के लिए उपलब्ध अधिकांश एल्गोरिदम। कुछ अनुक्रमिक एल्गोरिदम को स्वचालित समांतरता का उपयोग करके समांतर एल्गोरिदम में परिवर्तित किया जा सकता है।<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|स्वाभाविक रूप से धारावाहिक समस्या}}एस। उदाहरणों में पुनरावृत्त [[संख्यात्मक विश्लेषण]] सम्मलित हैं, जैसे कि न्यूटन की विधि, तीन-निकाय समस्या के पुनरावृत्त समाधान और पाई (π) की गणना करने के लिए उपलब्ध अधिकांश एल्गोरिदम। कुछ अनुक्रमिक एल्गोरिदम को स्वचालित समांतरता का उपयोग करके समांतर एल्गोरिदम में परिवर्तित किया जा सकता है।<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 के अंत तक, एकल -कोर प्रक्रमक का प्रदर्शन [[आवृत्ति स्केलिंग]] के माध्यम से तेजी से बढ़ा और इस प्रकार | [[ बहु | बहु]] प्रणाली में पर्याप्त सुधार और [[बहु कोर]] प्रक्रमक के उदय के कारण 2000 के दशक की प्रारंभिक से व्यक्तिगत उपकरणों पर समानांतर एल्गोरिदम अधिक सामान्य हो गए हैं। 2004 के अंत तक, एकल -कोर प्रक्रमक का प्रदर्शन [[आवृत्ति स्केलिंग]] के माध्यम से तेजी से बढ़ा और इस प्रकार ही [[प्रवाह क्षमता]] के साथ कई धीमे कोर वाले की तुलना में एकल स्थिर कोर के साथ कंप्यूटर बनाना सरल था, इसलिए बहु कोर प्रणाली उपयोग के थे। चूँकि, 2004 के बाद से, आवृत्ति स्केलिंग दीवार से टकराई और इस प्रकार बहु कोर प्रणाली अधिक व्यापक हो गए, जिससे अधिक सामान्य उपयोग के समानांतर एल्गोरिदम बन गए। | ||
== समस्याएँ == | == समस्याएँ == | ||
=== संचार === | === संचार === | ||
सीरियल एल्गोरिदम की लागत या जटिलता का अनुमान अंतरिक्ष (मेमोरी) और समय (प्रक्रमक चक्र) के संदर्भ में लगाया जाता है। समानांतर एल्गोरिदम को | सीरियल एल्गोरिदम की लागत या जटिलता का अनुमान अंतरिक्ष (मेमोरी) और समय (प्रक्रमक चक्र) के संदर्भ में लगाया जाता है। समानांतर एल्गोरिदम को और संसाधन, विभिन्न प्रक्रमक के बीच संचार को अनुकूलित करने की आवश्यकता होती है। दो प्रकार से समानांतर प्रक्रमक संचार, सहभाजी मेमोरी या [[संदेश|संदेश प्रेषण]] कर रहे हैं। | ||
सहभाजी मेमोरी प्रसंस्करण को डेटा के लिए अतिरिक्त लॉक (कंप्यूटर विज्ञान) की आवश्यकता होती है, अतिरिक्त प्रक्रमक और बस चक्रों के ओवरहेड को लागू करता है, और एल्गोरिथम के कुछ हिस्से को क्रमबद्ध भी करता है। | सहभाजी मेमोरी प्रसंस्करण को डेटा के लिए अतिरिक्त लॉक (कंप्यूटर विज्ञान) की आवश्यकता होती है, अतिरिक्त प्रक्रमक और बस चक्रों के ओवरहेड को लागू करता है, और एल्गोरिथम के कुछ हिस्से को क्रमबद्ध भी करता है। | ||
सर्वाधिक | सर्वाधिक संदेश प्रसंस्करण चैनल और संदेश बॉक्स का उपयोग करता है किन्तु यह संचार बस में उपरि स्थानांतरण जोड़ता है, श्रेणी और संदेश बॉक्स के लिए अतिरिक्त मेमोरी की आवश्यकता होती है और संदेशों में विलंबता होती है। समानांतर प्रक्रमक के डिजाइन विशेष [[बस (कंप्यूटिंग)]] जैसे [[क्रॉसबार स्विच]] का उपयोग करते हैं जिससे कि संचार ओवरहेड छोटा हो किन्तु यह समानांतर एल्गोरिदम है जो यातायात की मात्रा तय करता है। | ||
यदि अतिरिक्त प्रक्रमक का संचार ओवरहेड दूसरे प्रक्रमक को जोड़ने के लाभ से अधिक है, तो [[समानांतर मंदी]] का सामना करना पड़ता है। | यदि अतिरिक्त प्रक्रमक का संचार ओवरहेड दूसरे प्रक्रमक को जोड़ने के लाभ से अधिक है, तो [[समानांतर मंदी]] का सामना करना पड़ता है। | ||
| Line 25: | Line 25: | ||
=== भार संतुलन === | === भार संतुलन === | ||
{{main|Load balancing (computing)}} | {{main|Load balancing (computing)}} | ||
समांतर एल्गोरिदम के साथ | समांतर एल्गोरिदम के साथ और समस्या यह सुनिश्चित कर रही है कि इनपुट आकार संतुलित होने के बजाय लोड (समग्र कार्य) संतुलित है, यह सुनिश्चित करके वे उचित रूप से [[लोड संतुलन (कंप्यूटिंग)]] कर रहे हैं। उदाहरण के लिए, से लेकर लाख तक की सभी संख्याओं की जांच प्रक्रमक के बीच विभाजित करना सरल है; चूँकि, यदि संख्याओं को समान रूप से विभाजित किया जाता है (1-1,000, 1,001-2,000, आदि), तो काम की मात्रा असंतुलित हो जाएगी, क्योंकि इस एल्गोरिथम द्वारा छोटी संख्याओं को संसाधित करना सरल होता है (प्राथमिकता के लिए परीक्षण करना आसान), और इस प्रकार कुछ प्रोसेसरों को दूसरों की तुलना में अधिक काम करना होगा, जो लोड किए गए प्रक्रमक के पूर्ण होने तक निष्क्रिय रहेंगे। | ||
== वितरित एल्गोरिदम == | == वितरित एल्गोरिदम == | ||
{{main|Distributed algorithm}} | {{main|Distributed algorithm}} | ||
समानांतर एल्गोरिदम का | समानांतर एल्गोरिदम का उपप्रकार, [[वितरित एल्गोरिदम]], [[क्लस्टर कंप्यूटिंग]] और वितरित कंप्यूटिंग वातावरण में काम करने के लिए डिज़ाइन किए गए एल्गोरिदम हैं, जहां शास्त्रीय समानांतर एल्गोरिदम के दायरे से परे अतिरिक्त चिंताओं को संबोधित करने की आवश्यकता होती है। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 00:47, 10 May 2023
कंप्यूटर विज्ञान में, एक समानांतर कलन विधि , पारंपरिक सीरियल एल्गोरिथम के विपरीत, एल्गोरिथम है जो निश्चित समय में कई कार्य कर सकता है। सार मशीन मॉडल में सीरियल एल्गोरिदम का वर्णन करना कंप्यूटर विज्ञान की परंपरा रही है, जिसे अधिकांशतः रैंडम-एक्सेस मशीन के रूप में जाना जाता है। इसी प्रकार, कई कंप्यूटर विज्ञान शोधकर्ताओं ने तथाकथित समानांतर रैंडम-एक्सेस मशीन (PRAM) का उपयोग समानांतर सार मशीन सहभाजी मैमोरी के रूप में किया है।[1][2]कई समांतर एल्गोरिदम को समवर्ती कंप्यूटिंग निष्पादित किया जाता है - चूंकि सामान्य समवर्ती एल्गोरिदम में अलग अवधारणा होती है और इस प्रकार इन अवधारणाओं को अधिकांशतः भ्रमित किया जाता है, एल्गोरिदम का कौन सा पहलू समानांतर है और जो समवर्ती है स्पष्ट रूप से अलग नहीं किया जा रहा है। इसके अतिरिक्त, समवर्ती एल्गोरिदम के विपरीत, अ-समानांतर, अ-समवर्ती एल्गोरिदम को अधिकांशतः अनुक्रमिक एल्गोरिदम के रूप में संदर्भित किया जाता है।
समानांतरता
एल्गोरिथम इस बात में पर्याप्त भिन्न होते हैं कि वे कितने समानांतर हैं, सरलता से समानांतर होने से लेकर पूरी प्रकार से अद्वितीय तक इसके अतिरिक्त, दी गई समस्या अलग-अलग एल्गोरिदम को समायोजित कर सकती है, जो कम या ज्यादा समानांतर हो सकती है।
कुछ समस्याओं को इस प्रकार से टुकड़ों में विभाजित करना सरल होता है - इन्हें शर्मनाक समानांतर समस्याएँ कहा जाता है। उदाहरणों में रुबिक के क्यूब्स को हल करने के लिए कई एल्गोरिदम सम्मलित हैं और उन मूल्यों को ढूंढते हैं जो किसी दिए गए साहचर्य सरणी में परिणामित होते हैं।
कुछ समस्याओं को समानांतर भागों में विभाजित नहीं किया जा सकता है, क्योंकि उन्हें अगले चरण के साथ प्रभावी ढंग से आगे बढ़ने के लिए पिछले चरण के परिणामों की आवश्यकता होती है - इन्हें कहा जाता है स्वाभाविक रूप से धारावाहिक समस्याएस। उदाहरणों में पुनरावृत्त संख्यात्मक विश्लेषण सम्मलित हैं, जैसे कि न्यूटन की विधि, तीन-निकाय समस्या के पुनरावृत्त समाधान और पाई (π) की गणना करने के लिए उपलब्ध अधिकांश एल्गोरिदम। कुछ अनुक्रमिक एल्गोरिदम को स्वचालित समांतरता का उपयोग करके समांतर एल्गोरिदम में परिवर्तित किया जा सकता है।[3]
प्रेरणा
बहु प्रणाली में पर्याप्त सुधार और बहु कोर प्रक्रमक के उदय के कारण 2000 के दशक की प्रारंभिक से व्यक्तिगत उपकरणों पर समानांतर एल्गोरिदम अधिक सामान्य हो गए हैं। 2004 के अंत तक, एकल -कोर प्रक्रमक का प्रदर्शन आवृत्ति स्केलिंग के माध्यम से तेजी से बढ़ा और इस प्रकार ही प्रवाह क्षमता के साथ कई धीमे कोर वाले की तुलना में एकल स्थिर कोर के साथ कंप्यूटर बनाना सरल था, इसलिए बहु कोर प्रणाली उपयोग के थे। चूँकि, 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 | |
