समानांतर एल्गोरिदम और प्रदर्शन

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

Definition

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

Scope

यह विषय समानांतर एल्गोरिदम को डिज़ाइन करने और उनका विश्लेषण करने के लिए मॉडल को शामिल करता है—विशेष रूप से PRAM और इसका कार्य-गहराई विश्लेषण—समानांतर प्रिमिटिव जैसे कि उपसर्ग योग (स्कैन), कमी और सॉर्टिंग का डिज़ाइन, और गति में वृद्धि, दक्षता, लागत-इष्टतमता, समदक्षता, और अम्डाहल और गुस्ताफसन के स्केलिंग नियमों का प्रदर्शन ढांचा। यह सभी प्रोग्रामिंग मॉडलों में समानांतर कार्यक्रमों के बारे में तर्क करने के लिए विश्लेषणात्मक आधार प्रदान करता है।

Core questions

• किसी समस्या की अंतर्निहित समानांतरता को उसके कार्य और गहराई से कैसे चित्रित किया जाता है?
• गति में वृद्धि, दक्षता और स्केलेबिलिटी को कैसे परिभाषित और मापा जाता है?
• किसी समस्या का क्रमिक अंश या वृद्धि उसकी समानांतर स्केलेबिलिटी को कैसे निर्धारित करती है?

Key theories

PRAM और कार्य-गहराई विश्लेषण

PRAM मॉडल साझा मेमोरी और तुल्यकालिक चरणों के साथ एक समानांतर मशीन का आदर्श बनाता है, जो एक एल्गोरिथम के कार्य (कुल संचालन) और गहराई (महत्वपूर्ण-पथ लंबाई) के विश्लेषण का समर्थन करता है, जो मिलकर इसकी प्राप्त करने योग्य समानांतर समय को सीमित करते हैं।

गति में वृद्धि, दक्षता और समदक्षता

गति में वृद्धि यह मापती है कि p प्रोसेसर किसी समस्या को कितनी तेजी से हल करते हैं, दक्षता इसे प्रति प्रोसेसर सामान्य करती है, और समदक्षता यह व्यक्त करती है कि दक्षता को स्थिर रखने के लिए प्रोसेसर गणना के साथ समस्या का आकार कितना बढ़ना चाहिए, जो स्केलेबिलिटी को दर्शाता है।

अम्डाहल और गुस्ताफसन के नियम

अम्डाहल का नियम क्रमिक अंश द्वारा निश्चित-आकार की गति में वृद्धि को सीमित करता है, जबकि गुस्ताफसन का नियम यह देखता है कि मशीन के साथ समस्या को स्केल करने से लगभग-रैखिक गति में वृद्धि होती है, जो मजबूत बनाम कमजोर स्केलिंग को संयुक्त रूप से फ्रेम करता है।

Clinical relevance

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

History

अम्डाहल के 1967 के तर्क और गुस्ताफसन के 1988 के खंडन ने गति में वृद्धि की बहस को आकार दिया; PRAM मॉडल और कार्य-गहराई ढांचा 1980 के दशक में परिपक्व हुए और जाजा के 1992 के पाठ और ग्रामा और सहयोगियों के स्केलेबिलिटी के विश्लेषण में संहिताबद्ध किए गए, जिससे समानांतर कंप्यूटिंग को इसका सैद्धांतिक मूल मिला।

Debates

मजबूत स्केलिंग बनाम कमजोर स्केलिंग

अम्डाहल का मजबूत-स्केलिंग दृष्टिकोण (निश्चित समस्या, अधिक प्रोसेसर) घटते प्रतिफल की भविष्यवाणी करता है, जबकि गुस्ताफसन का कमजोर-स्केलिंग दृष्टिकोण (प्रोसेसर के साथ समस्या को बढ़ाना) निरंतर गति में वृद्धि की भविष्यवाणी करता है; कौन सा सही माप है यह इस बात पर निर्भर करता है कि समस्या का आकार या समाधान का समय निश्चित है।

Key figures

• Joseph JaJa
• Gene Amdahl
• John Gustafson
• Vipin Kumar

Seminal works

• jaja1992
• amdahl1967
• gustafson1988

Frequently asked questions

एक समानांतर एल्गोरिथम के कार्य और गहराई के बीच क्या अंतर है?

कार्य सभी प्रोसेसर में किए गए संचालन की कुल संख्या है, जबकि गहराई (या स्पैन) निर्भर संचालन की सबसे लंबी श्रृंखला की लंबाई है। गहराई सर्वोत्तम संभव समानांतर चलने वाले समय को सीमित करती है, और कार्य-से-गहराई अनुपात यह इंगित करता है कि कितनी समानांतरता उपलब्ध है।