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

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

पृष्ठभूमि

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

परिभाषाएँ

मान लीजिए कि गणना एक ऐसी मशीन पर निष्पादित की जाती है जिसमें p संसाधक है। मान लीजिए T_p उस समय को दर्शाता है जो गणना के प्रारम्भ और उसके अंत के बीच समाप्त होता है। गणना के चलने के समय का विश्लेषण निम्नलिखित धारणाओं पर केंद्रित है:

• p संसाधक द्वारा निष्पादित गणना का कार्य संसाधक द्वारा निष्पादित आदिम संचालन की कुल संख्या है। संसाधक को समकालिक करने से संचार शिरोपरि को अनदेखा करना, यह एकल संसाधक पर गणना चलाने के लिए उपयोग किए गए समय के बराबर है, जिसे T₁ दर्शाया गया है।
• मध्यमार्ग या अवधि संचालन की सबसे लंबी श्रृंखला की लंबाई है जिसे डेटा निर्भरता (महत्वपूर्ण पथ) के कारण क्रमिक रूप से निष्पादित करना पड़ता है। गहराई को गणना की महत्वपूर्ण पथ लंबाई भी कहा जा सकता है। समानांतर कलन विधि को अभिकल्पित करने में मध्यमार्ग/अवधि को कम करना महत्वपूर्ण है, क्योंकि मध्यमार्ग/अवधि न्यूनतम संभव निष्पादन समय निर्धारित करता है। वैकल्पिक रूप से, स्पैन को अनंत संख्या में संसाधक के साथ एक आदर्श मशीन का उपयोग करके कंप्यूटिंग में बिताए गए समय T∞ के रूप में परिभाषित किया जा सकता है।
• गणना की लागत मात्रा pT_p है। यह सभी संसाधक द्वारा कंप्यूटिंग और प्रतीक्षा दोनों में खर्च किए गए कुल समय को व्यक्त करता है।

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

• कार्य नियम. लागत हमेशा कम से कम काम की होती है: pT_p ≥ T₁। यह इस तथ्य से पता चलता है कि p संसाधक अधिकतम प्रदर्शन कर सकते हैं।
• स्पैन नियम. एक सीमित संख्या p संसाधक अनंत संख्या से बेहतर प्रदर्शन नहीं कर सकते, इसलिए T_p ≥ T_∞ है।

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

• गति वर्धन अनुक्रमिक निष्पादन की तुलना में समानांतर निष्पादन द्वारा प्राप्त गति में वृद्धि है: Sp = T1 / Tp। जब निविष्ट आकार n (बड़े O अंकन पद्धति का उपयोग करके) के लिए गति वर्धन Ω(n) होता है, तो गति वर्धन रैखिक होता है, जो गणना के सरल प्रतिरूप में इष्टतम होता है क्योंकि कार्य नियम का तात्पर्य है कि T1 / Tp ≤ p (स्मृति पदानुक्रम प्रभावों के कारण अभ्यास में अति-रैखिक गति वर्धन हो सकता है)। स्थिति T₁ / T_p = p को उतम रेखीय गति वर्धन कहा जाता है। एक कलन विधि जो रैखिक गति वर्धन प्रदर्शित करता है उसे मापक्रमणीयता कहा जाता है।
• दक्षता प्रति संसाधक गति वर्धन S_p / p है।
• समानांतरता अनुपात T₁ / T_∞ है। यह किसी भी संख्या में संसाधक पर अधिकतम संभव गति वर्धन का प्रतिनिधित्व करता है। स्पैन नियम के अनुसार, समानता गति को सीमित करती है: यदि p > T₁ / T_∞, तब:
  $${\frac {T_{1}}{T_{p}}}\leq {\frac {T_{1}}{T_{\infty }}}<p.$$
• शिथिलता T₁ / (pT_∞) है। एक से कम शिथिलता का अर्थ है (स्पैन नियम द्वारा) कि पूर्ण रैखिक गति p संसाधक असंभव है।

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

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

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

या, कम सटीक रूप से,

$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_∞ और काम T₁ एक साथ गणना समय पर उचित सीमा प्रदान करते हैं।