स्वचालित समानांतरीकरण

From alpha
Jump to navigation Jump to search

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

प्रोग्रामिंग नियंत्रण संरचनाएं जिन पर ऑटोपैरेललाइज़ेशन सबसे अधिक ध्यान केंद्रित करता है, वे नियंत्रण प्रवाह#लूप्स हैं, क्योंकि, सामान्य तौर पर, किसी प्रोग्राम का अधिकांश रन टाइम (प्रोग्राम जीवनचक्र चरण) किसी न किसी प्रकार के लूप के अंदर होता है। लूप के समानांतरीकरण के लिए दो मुख्य दृष्टिकोण हैं: पाइपलाइनयुक्त मल्टी-थ्रेडिंग और चक्रीय मल्टी-थ्रेडिंग।[3]उदाहरण के लिए, एक लूप पर विचार करें जो प्रत्येक पुनरावृत्ति पर सौ ऑपरेशन लागू करता है, और एक हजार पुनरावृत्तियों तक चलता है। इसे 100 स्तंभों और 1000 पंक्तियों के ग्रिड के रूप में सोचा जा सकता है, जिसमें कुल 100,000 ऑपरेशन होंगे। चक्रीय मल्टी-थ्रेडिंग प्रत्येक पंक्ति को एक अलग थ्रेड को निर्दिष्ट करती है। पाइपलाइन मल्टी-थ्रेडिंग प्रत्येक कॉलम को एक अलग थ्रेड को असाइन करती है।

स्वचालित समानांतरीकरण तकनीक

पार्स

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

विश्लेषण

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

अनुसूची

शेड्यूलिंग (कंप्यूटिंग) निष्पादन और प्रारंभ समय के संदर्भ में सभी कार्यों और एक-दूसरे पर उनकी निर्भरता को सूचीबद्ध करेगा। शेड्यूलर उपयोग किए जाने वाले प्रोसेसर की संख्या या एप्लिकेशन के कुल निष्पादन समय के संदर्भ में इष्टतम शेड्यूल तैयार करेगा।

कोड जनरेशन

शेड्यूलिंग (कंप्यूटिंग) सभी कार्यों की एक सूची और उन कोर के विवरण उत्पन्न करेगी जिन पर वे निष्पादित करेंगे, साथ ही उस समय के लिए जिसे वे निष्पादित करेंगे। कोड जेनरेटर कोड में विशेष निर्माण सम्मिलित करेगा जिसे शेड्यूलर द्वारा निष्पादन के दौरान पढ़ा जाएगा। ये निर्माण अनुसूचक को निर्देश देंगे कि प्रारंभ और समाप्ति समय के साथ-साथ किस कोर पर एक विशेष कार्य निष्पादित होगा।

चक्रीय बहु-थ्रेडिंग

एक चक्रीय मल्टी-थ्रेडिंग पैरेललाइजिंग कंपाइलर पाश विभाजन की कोशिश करता है ताकि प्रत्येक पुनरावृत्ति को एक अलग माइक्रोप्रोसेसर पर समवर्ती रूप से निष्पादित किया जा सके।

संकलक समानांतरीकरण विश्लेषण

संकलक आमतौर पर निम्नलिखित निर्धारित करने के लिए वास्तविक समानांतरीकरण से पहले विश्लेषण के दो चरण आयोजित करता है:

  • क्या लूप को समानांतर करना सुरक्षित है? इस प्रश्न का उत्तर देने के लिए सटीक निर्भरता विश्लेषण और उपनाम विश्लेषण की आवश्यकता है
  • क्या इसे समानांतर बनाना सार्थक है? इस उत्तर के लिए प्रोग्राम कार्यभार और समानांतर प्रणाली की क्षमता का विश्वसनीय अनुमान (मॉडलिंग) आवश्यक है।

कंपाइलर का पहला पास यह निर्धारित करने के लिए लूप का निर्भरता विश्लेषण करता है कि क्या लूप के प्रत्येक पुनरावृत्ति को दूसरों से स्वतंत्र रूप से निष्पादित किया जा सकता है। डेटा निर्भरता से कभी-कभी निपटा जा सकता है, लेकिन इसमें संदेश भेजने, साझा मेमोरी के सिंक्रनाइज़ेशन (इंटरप्रोसेस संचार), या प्रोसेसर संचार के किसी अन्य तरीके के रूप में अतिरिक्त ओवरहेड खर्च हो सकता है।

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

उदाहरण

एक लूप को DOALL कहा जाता है यदि किसी दिए गए आह्वान में इसके सभी पुनरावृत्तियों को समवर्ती रूप से निष्पादित किया जा सकता है।

नीचे दिया गया फोरट्रान कोड DOALL है, और इसे कंपाइलर द्वारा ऑटो-समानांतर किया जा सकता है क्योंकि प्रत्येक पुनरावृत्ति दूसरों से स्वतंत्र है, और सरणी का अंतिम परिणाम है z अन्य पुनरावृत्तियों के निष्पादन क्रम की परवाह किए बिना सही होगा। 

   do i = 1, n
     z(i) = x(i) + y(i)
   enddo

ऐसी कई सुखद समानांतर समस्याएं हैं जिनमें ऐसे DOALL लूप हैं। उदाहरण के लिए, जब किरण-अनुरेखित फिल्म को समानांतर रूप से प्रस्तुत किया जाता है, तो फिल्म के प्रत्येक फ्रेम को स्वतंत्र रूप से प्रस्तुत किया जा सकता है, और एकल फ्रेम के प्रत्येक पिक्सेल को स्वतंत्र रूप से प्रस्तुत किया जा सकता है।

दूसरी ओर, निम्नलिखित कोड को स्वतः-समांतर नहीं किया जा सकता, क्योंकि का मान z(i) पिछले पुनरावृत्ति के परिणाम पर निर्भर करता है, z(i - 1). 

   do i = 2, n
     z(i) = z(i - 1)*2
   enddo

इसका मतलब यह नहीं है कि कोड को समानांतर नहीं किया जा सकता है। दरअसल, यह DOALL लूप के बराबर है 

   do i = 2, n
     z(i) = z(1)*2**(i - 1)
   enddo

हालाँकि, वर्तमान समानांतरीकरण कंपाइलर आमतौर पर इन समानताओं को स्वचालित रूप से सामने लाने में सक्षम नहीं हैं, और यह संदिग्ध है कि क्या इस कोड को पहले स्थान पर समानांतरीकरण से लाभ होगा।


पाइपलाइन मल्टी-थ्रेडिंग

Main article: software pipelining

एक पाइपलाइनयुक्त मल्टी-थ्रेडिंग पैरेललाइज़िंग कंपाइलर एक लूप के अंदर संचालन के अनुक्रम को कोड ब्लॉक की एक श्रृंखला में तोड़ने की कोशिश करता है, ताकि प्रत्येक कोड ब्लॉक को अलग-अलग माइक्रोप्रोसेसरों पर समवर्ती रूप से निष्पादित किया जा सके।

ऐसी कई सुखद समानांतर समस्याएं हैं जिनमें ऐसे अपेक्षाकृत स्वतंत्र कोड ब्लॉक होते हैं, विशेष रूप से पाइप और फिल्टर का उपयोग करने वाली प्रणालियों में।

उदाहरण के लिए, लाइव प्रसारण टेलीविजन का उत्पादन करते समय, निम्नलिखित कार्यों को एक सेकंड में कई बार किया जाना चाहिए:

  1. छवि सेंसर से कच्चे पिक्सेल डेटा का एक फ्रेम पढ़ें,
  2. कच्चे डेटा पर एमपीईजी गति क्षतिपूर्ति करें,
  3. एन्ट्रॉपी गति वैक्टर और अन्य डेटा को संपीड़ित करती है,
  4. संपीड़ित डेटा को पैकेट में तोड़ें,
  5. उचित त्रुटि सुधार जोड़ें और डेटा पैकेट को COFDM सिग्नल में बदलने के लिए FFT करें, और
  6. टीवी एंटीना को COFDM सिग्नल भेजें।

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

हालिया शोध जीपीयू की शक्ति का उपयोग करने पर केंद्रित है[4]और मल्टीकोर सिस्टम[5]रनटाइम पर ऐसे स्वतंत्र कोड ब्लॉक (या बस लूप के स्वतंत्र पुनरावृत्तियों) की गणना करने के लिए। एक्सेस की गई मेमोरी (चाहे प्रत्यक्ष या अप्रत्यक्ष) को लूप के विभिन्न पुनरावृत्तियों के लिए आसानी से चिह्नित किया जा सकता है और निर्भरता का पता लगाने के लिए तुलना की जा सकती है। इस जानकारी का उपयोग करते हुए, पुनरावृत्तियों को स्तरों में समूहीकृत किया जाता है जैसे कि समान स्तर से संबंधित पुनरावृत्तियाँ एक दूसरे से स्वतंत्र होती हैं, और समानांतर में निष्पादित की जा सकती हैं।

कठिनाइयाँ

निम्नलिखित कारणों से कंपाइलरों या उपकरणों द्वारा स्वचालित समानांतरीकरण बहुत कठिन है:[6]* अप्रत्यक्ष एड्रेसिंग, पॉइंटर्स, रिकर्सन या अप्रत्यक्ष फ़ंक्शन कॉल का उपयोग करने वाले कोड के लिए निर्भरता विश्लेषण कठिन है क्योंकि संकलन समय पर ऐसी निर्भरता का पता लगाना मुश्किल है;

  • लूप में पुनरावृत्तियों की अज्ञात संख्या होती है;
  • वैश्विक संसाधनों तक पहुंच को मेमोरी आवंटन, I/O और साझा चर के संदर्भ में समन्वयित करना मुश्किल है;
  • अनियमित एल्गोरिदम जो इनपुट-निर्भर अप्रत्यक्षता का उपयोग करते हैं, संकलन-समय विश्लेषण और अनुकूलन में हस्तक्षेप करते हैं।[7]


समाधान

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

कंपाइलर्स और टूल्स को समानांतर बनाना

See also: Automatic parallelization tool

स्वचालित समानांतरीकरण के लिए अधिकांश शोध संकलक फोरट्रान कार्यक्रमों पर विचार करते हैं,[citation needed] क्योंकि फोरट्रान सी (प्रोग्रामिंग भाषा) जैसी भाषाओं की तुलना में अलियासिंग (कंप्यूटिंग) के बारे में अधिक मजबूत गारंटी देता है। विशिष्ट उदाहरण हैं:

यह भी देखें

संदर्भ

  1. ↑ Yehezkael, Rafael (2000). "Experiments in Separating Computational Algorithm from Program Distribution and Communication" (PDF). Applied Parallel Computing. New Paradigms for HPC in Industry and Academia. Lecture Notes in Computer Science. Vol. 1947. Springer Verlag. pp. 268–278. doi:10.1007/3-540-70734-4_32. ISBN 978-3-540-41729-3.
  2. ↑ Fox, Geoffrey; Williams, Roy; Messina, Paul (1994). Parallel Computing Works!. Morgan Kaufmann. pp. 575, 593. ISBN 978-1-55860-253-3.
  3. ↑ Campanoni, Simone; Jones, Timothy; Holloway, Glenn; Wei, Gu-Yeon; Brooks, David (2012). The HELIX Project: Overview and Directions.
  4. ↑ Anantpur, J.; Govindarajan, R. "Runtime dependence computation and execution of loops on heterogeneous systems" (PDF). Archived from the original (PDF) on 6 October 2015. Retrieved 5 October 2015.
  5. ↑ Zhuang, X.; Eichenberger, A. E.; Luo, Y.; O'Brien, Kathryn Kevin, Exploiting Parallelism with Dependence-Aware Scheduling
  6. ↑ "Automatic parallelism and data dependency". Archived from the original on 14 July 2014.
  7. ↑ Rünger, Gudula (2006). "Parallel Programming Models for Irregular Algorithms". Parallel Algorithms and Cluster Computing. Lecture Notes in Computational Science and Engineering. 52: 3–23. doi:10.1007/3-540-33541-2_1. ISBN 978-3-540-33539-9.


अग्रिम पठन

Retrieved from "https://alpha.indicwiki.in/index.php?title=स्वचालित_समानांतरीकरण&oldid=335489"