समानांतर कलन विधि

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

समानांतरता

See also: Analysis of parallel algorithms

एल्गोरिथम इस बात में काफी भिन्न होते हैं कि वे कितने समानांतर हैं, आसानी से समानांतर होने से लेकर पूरी तरह से अद्वितीय तक। इसके अलावा, दी गई समस्या अलग-अलग एल्गोरिदम को समायोजित कर सकती है, जो कम या ज्यादा समानांतर हो सकती है।

कुछ समस्याओं को इस तरह से टुकड़ों में विभाजित करना आसान होता है - इन्हें शर्मनाक समानांतर समस्याएँ कहा जाता है। उदाहरणों में रुबिक के क्यूब्स को हल करने के लिए कई एल्गोरिदम शामिल हैं और उन मूल्यों को ढूंढते हैं जो किसी दिए गए साहचर्य सरणी में परिणामित होते हैं।

कुछ समस्याओं को समानांतर भागों में विभाजित नहीं किया जा सकता है, क्योंकि उन्हें अगले चरण के साथ प्रभावी ढंग से आगे बढ़ने के लिए पिछले चरण के परिणामों की आवश्यकता होती है - इन्हें कहा जाता हैinherently serial problemएस। उदाहरणों में पुनरावृत्त संख्यात्मक विश्लेषण शामिल हैं, जैसे कि न्यूटन की विधि, तीन-निकाय समस्या के पुनरावृत्त समाधान, और पाई (π) की गणना करने के लिए उपलब्ध अधिकांश एल्गोरिदम। कुछ अनुक्रमिक एल्गोरिदम को स्वचालित समांतरता का उपयोग करके समांतर एल्गोरिदम में परिवर्तित किया जा सकता है।

प्रेरणा

बहु सिस्टम में पर्याप्त सुधार और मल्टी कोर प्रोसेसर के उदय के कारण 2000 के दशक की शुरुआत से व्यक्तिगत उपकरणों पर समानांतर एल्गोरिदम अधिक सामान्य हो गए हैं। 2004 के अंत तक, सिंगल-कोर प्रोसेसर का प्रदर्शन आवृत्ति स्केलिंग के माध्यम से तेजी से बढ़ा, और इस प्रकार एक ही THROUGHPUT के साथ कई धीमे कोर वाले एक की तुलना में एक सिंगल फास्ट कोर के साथ एक कंप्यूटर बनाना आसान था, इसलिए मल्टीकोर सिस्टम अधिक सीमित थे उपयोग। हालाँकि, 2004 के बाद से, आवृत्ति स्केलिंग एक दीवार से टकराई, और इस प्रकार मल्टीकोर सिस्टम अधिक व्यापक हो गए, जिससे अधिक सामान्य उपयोग के समानांतर एल्गोरिदम बन गए।

मुद्दे

संचार

सीरियल एल्गोरिदम की लागत या जटिलता का अनुमान अंतरिक्ष (मेमोरी) और समय (प्रोसेसर चक्र) के संदर्भ में लगाया जाता है। समानांतर एल्गोरिदम को एक और संसाधन, विभिन्न प्रोसेसर के बीच संचार को अनुकूलित करने की आवश्यकता होती है। दो तरह से समानांतर प्रोसेसर संचार, साझा स्मृति या संदेश देना कर रहे हैं।

साझा मेमोरी प्रोसेसिंग को डेटा के लिए अतिरिक्त लॉक (कंप्यूटर विज्ञान) की आवश्यकता होती है, अतिरिक्त प्रोसेसर और बस चक्रों के ओवरहेड को लागू करता है, और एल्गोरिथम के कुछ हिस्से को क्रमबद्ध भी करता है।

संदेश पासिंग प्रोसेसिंग चैनल और संदेश बॉक्स का उपयोग करता है लेकिन यह संचार बस में ट्रांसफर ओवरहेड जोड़ता है, कतारों और संदेश बॉक्स के लिए अतिरिक्त मेमोरी की आवश्यकता होती है और संदेशों में विलंबता होती है। समानांतर प्रोसेसर के डिजाइन विशेष बस (कंप्यूटिंग) जैसे क्रॉसबार स्विच का उपयोग करते हैं ताकि संचार ओवरहेड छोटा हो लेकिन यह समानांतर एल्गोरिदम है जो यातायात की मात्रा तय करता है।

यदि अतिरिक्त प्रोसेसर का संचार ओवरहेड दूसरे प्रोसेसर को जोड़ने के लाभ से अधिक है, तो समानांतर मंदी का सामना करना पड़ता है।

भार संतुलन

Main article: Load balancing (computing)

समांतर एल्गोरिदम के साथ एक और समस्या यह सुनिश्चित कर रही है कि इनपुट आकार संतुलित होने के बजाय लोड (समग्र कार्य) संतुलित है, यह सुनिश्चित करके वे उचित रूप से लोड संतुलन (कंप्यूटिंग) कर रहे हैं। उदाहरण के लिए, एक से लेकर एक लाख तक की सभी संख्याओं की जांच प्रोसेसर के बीच विभाजित करना आसान है; हालाँकि, यदि संख्याओं को समान रूप से विभाजित किया जाता है (1-1,000, 1,001-2,000, आदि), तो काम की मात्रा असंतुलित हो जाएगी, क्योंकि इस एल्गोरिथम द्वारा छोटी संख्याओं को संसाधित करना आसान होता है (प्राथमिकता के लिए परीक्षण करना आसान), और इस प्रकार कुछ प्रोसेसरों को दूसरों की तुलना में अधिक काम करना होगा, जो लोड किए गए प्रोसेसर के पूर्ण होने तक निष्क्रिय रहेंगे।

वितरित एल्गोरिदम

Main article: Distributed algorithm

समानांतर एल्गोरिदम का एक उपप्रकार, वितरित एल्गोरिदम, क्लस्टर कंप्यूटिंग और वितरित कंप्यूटिंग वातावरण में काम करने के लिए डिज़ाइन किए गए एल्गोरिदम हैं, जहां शास्त्रीय समानांतर एल्गोरिदम के दायरे से परे अतिरिक्त चिंताओं को संबोधित करने की आवश्यकता होती है।

यह भी देखें

• बहु-एजेंट प्रणाली (एमएएस)
• मैट्रिक्स गुणन के लिए समानांतर एल्गोरिदम
• न्यूनतम फैले हुए पेड़ों के लिए समानांतर एल्गोरिदम
• समानांतर कंप्यूटिंग
• पैरारियल

बाहरी संबंध

• Designing and Building Parallel Programs, US Argonne National Laboratory