डेटा समानांतरता

अनुक्रमिक बनाम डेटा-समानांतर कार्य निष्पादन

समानांतर कंप्यूटिंग वातावरण में कई प्रोसेसरों में डेटा समानांतरवाद समानांतर है। यह डेटा को विभिन्न नोड्स में वितरित करने पर केंद्रित है, जो समानांतर में डेटा पर काम करते हैं। समानांतर में प्रत्येक तत्व पर काम करके इसे सरणियों और मैट्रिक्स जैसी नियमित डेटा संरचनाओं पर लागू किया जा सकता है। यह समांतरता के दूसरे रूप के रूप में कार्य समानता के विपरीत है।

'एन' तत्वों की एक सरणी पर डेटा समानांतर कार्य को सभी प्रोसेसरों के बीच समान रूप से विभाजित किया जा सकता है। आइए मान लें कि हम दिए गए सरणी के सभी तत्वों को योग करना चाहते हैं और एक अतिरिक्त ऑपरेशन के लिए समय टा टाइम यूनिट है। अनुक्रमिक निष्पादन के मामले में, प्रक्रिया द्वारा लिया जाने वाला समय n×Ta समय इकाइयां होगा क्योंकि यह एक सरणी के सभी तत्वों का योग करता है। दूसरी ओर, यदि हम इस कार्य को 4 प्रोसेसरों पर डेटा समानांतर कार्य के रूप में निष्पादित करते हैं तो लगने वाला समय (n/4)×Ta + मर्जिंग ओवरहेड समय इकाइयों तक कम हो जाएगा। समानांतर निष्पादन के परिणामस्वरूप अनुक्रमिक निष्पादन पर 4 का स्पीडअप होता है। ध्यान देने वाली एक महत्वपूर्ण बात यह है कि डेटा समानांतर प्रोग्रामिंग मॉडल के प्रदर्शन के मूल्यांकन में संदर्भ की लोकैलिटी एक महत्वपूर्ण भूमिका निभाती है। डेटा की स्थानीयता प्रोग्राम द्वारा निष्पादित मेमोरी एक्सेस के साथ-साथ कैश के आकार पर निर्भर करती है।

इतिहास

सोलोमन मशीन के विकास के साथ 1960 के दशक में डेटा समानता की अवधारणा का दोहन शुरू हुआ। सोलोमन मशीन, जिसे वेक्टर प्रोसेसर भी कहा जाता है, को बड़े डेटा ऐरे (लगातार समय के चरणों में कई डेटा पर संचालन) पर काम करके गणितीय कार्यों के प्रदर्शन में तेजी लाने के लिए विकसित किया गया था। एक ही निर्देश का उपयोग करके एक ही समय में कई डेटा पर संचालन करके डेटा संचालन की संगामिति (कंप्यूटर विज्ञान) का भी शोषण किया गया। इन प्रोसेसरों को 'सरणी प्रोसेसर' कहा जाता था। 1980 के दशक में, शब्द पेश किया गया था इस प्रोग्रामिंग शैली का वर्णन करने के लिए, जिसका व्यापक रूप से C* जैसी डेटा समानांतर भाषाओं में कनेक्शन मशीनों को प्रोग्राम करने के लिए उपयोग किया जाता था। आज, ग्राफ़िक्स प्रोसेसिंग युनिट ्स (जीपीयू) में डेटा समानता का सबसे अच्छा उदाहरण है, जो एक ही निर्देश का उपयोग करके अंतरिक्ष और समय में कई डेटा पर संचालन की दोनों तकनीकों का उपयोग करते हैं।

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

विवरण

निर्देशों के एक सेट (SIMD) को निष्पादित करने वाले मल्टीप्रोसेसर सिस्टम में, डेटा समानता तब प्राप्त होती है जब प्रत्येक प्रोसेसर अलग-अलग वितरित डेटा पर समान कार्य करता है। कुछ स्थितियों में, एकल निष्पादन थ्रेड सभी डेटा पर संचालन को नियंत्रित करता है। दूसरों में, अलग-अलग धागे ऑपरेशन को नियंत्रित करते हैं, लेकिन वे एक ही कोड को निष्पादित करते हैं।

उदाहरण के लिए, आव्यूह गुणन और जोड़ को क्रमिक तरीके से विचार करें जैसा कि उदाहरण में चर्चा की गई है।

उदाहरण

नीचे गुणा और दो आव्यूहों के जोड़ के लिए अनुक्रमिक छद्म कोड है जहां परिणाम मैट्रिक्स में संग्रहीत किया जाता है C. गुणा के लिए छद्म कोड दो आव्यूहों के डॉट गुणनफल की गणना करता है A, B और परिणाम को आउटपुट मैट्रिक्स में संग्रहीत करता है C.

यदि निम्नलिखित प्रोग्रामों को क्रमिक रूप से क्रियान्वित किया जाता है, तो परिणाम की गणना करने में लगने वाला समय होगा $O(n^{3})$(पंक्ति की लंबाई मानते हुए और दोनों आव्यूहों की स्तंभ लंबाई n हैं) और $O(n)$क्रमशः गुणा और जोड़ के लिए।

// Matrix multiplication
for (i = 0; i < row_length_A; i++)
{		
    for (k = 0; k < column_length_B; k++)
    {
        sum = 0;
        for (j = 0; j < column_length_A; j++)
        {
            sum += A[i][j] * B[j][k];
        }
        C[i][k] = sum;
    }
}

// Array addition
for (i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
}

हम इसे तेजी से निष्पादित करने के लिए पूर्ववर्ती कोड में डेटा समानता का फायदा उठा सकते हैं क्योंकि अंकगणित लूप स्वतंत्र है। OpenMP का उपयोग करके मैट्रिक्स गुणन कोड का समानांतरकरण प्राप्त किया जाता है। एक OpenMP निर्देश, omp समानांतर के लिए संकलक को समानांतर में लूप के लिए कोड निष्पादित करने का निर्देश देता है। गुणन के लिए, हम मैट्रिक्स ए और बी को क्रमशः पंक्तियों और स्तंभों के साथ ब्लॉक में विभाजित कर सकते हैं। यह हमें मैट्रिक्स सी में प्रत्येक तत्व की व्यक्तिगत रूप से गणना करने की अनुमति देता है जिससे कार्य समानांतर हो जाता है। उदाहरण के लिए: ए [एम एक्स एन] डॉट बी [एन एक्स के] में समाप्त किया जा सकता है $O(n)$ के बजाय $O(m*n*k)$ जब m*k प्रोसेसर का उपयोग करके समानांतर में निष्पादित किया जाता है।

मैट्रिक्स गुणन में डेटा समानता

// Matrix multiplication in parallel
#pragma omp parallel for schedule(dynamic,1) collapse(2)
for (i = 0; i < row_length_A; i++){
    for (k = 0; k < column_length_B; k++){
        sum = 0;
        for (j = 0; j < column_length_A; j++){
            sum += A[i][j] * B[j][k];
        }
        C[i][k] = sum;
    }
}

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

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

प्रोग्राम नीचे स्यूडोकोड में व्यक्त किया गया है—जो कुछ मनमाना ऑपरेशन लागू करता है, foo, सरणी में प्रत्येक तत्व पर d—डेटा समानता दिखाता है: अगर सीपीयू = ए तब

    लोअर_लिमिट: = 1
    अपर_लिमिट: = राउंड (डी.लेंथ / 2)
और अगर सीपीयू = बी तो
    निचला_लिमिट: = गोल (डी.लेंथ / 2) + 1
    अपर_लिमिट: = डी। लंबाई

for i के लिए lower_limit से upper_limit तक 1 do
    फू (डी [i])

2 प्रोसेसर सिस्टम पर निष्पादित एसपीएमडी सिस्टम में, दोनों सीपीयू कोड को निष्पादित करेंगे।

प्रसंस्करण (कार्य समानांतरता) के विपरीत, डेटा समांतरता डेटा की वितरित (समानांतर) प्रकृति पर जोर देती है। अधिकांश वास्तविक कार्यक्रम कार्य समांतरता और डेटा समांतरता के बीच निरंतरता पर कहीं गिर जाते हैं।

समांतरता के लिए कदम

अनुक्रमिक कार्यक्रम को समानांतर करने की प्रक्रिया को चार असतत चरणों में तोड़ा जा सकता है।

Type	Description
Decomposition	The program is broken down into tasks, the smallest exploitable unit of concurrence.
Assignment	Tasks are assigned to processes.
Orchestration	Data access, communication, and synchronization of processes.
Mapping	Processes are bound to processors.

डेटा समानता बनाम कार्य समानता

Data parallelism	Task parallelism
Same operations are performed on different subsets of same data.	Different operations are performed on the same or different data.
Synchronous computation	Asynchronous computation
Speedup is more as there is only one execution thread operating on all sets of data.	Speedup is less as each processor will execute a different thread or process on the same or different set of data.
Amount of parallelization is proportional to the input data size.	Amount of parallelization is proportional to the number of independent tasks to be performed.
Designed for optimum load balance on multi processor system.	Load balancing depends on the availability of the hardware and scheduling algorithms like static and dynamic scheduling.

डेटा समानता बनाम मॉडल समानता

Data parallelism	Model parallelism
Same model is used for every thread but the data given to each of them is divided and shared.	Same data is used for every thread, and model is split among threads.
It is fast for small networks but very slow for large networks since large amounts of data needs to be transferred between processors all at once.	It is slow for small networks and fast for large networks.
Data parallelism is ideally used in array and matrix computations and convolutional neural networks	Model parallelism finds its applications in deep learning

मिश्रित डेटा और कार्य समानता

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

1. मिश्रित डेटा और कार्य समानता वैश्विक जलवायु मॉडलिंग में अनुप्रयोगों को ढूंढती है। बड़े डेटा समानांतर संगणनाएं पृथ्वी के वायुमंडल और महासागरों का प्रतिनिधित्व करने वाले डेटा के ग्रिड बनाकर की जाती हैं और भौतिक प्रक्रियाओं के कार्य और मॉडल को अनुकरण करने के लिए कार्य समानांतरता को नियोजित किया जाता है।
2. टाइमिंग आधारित सर्किट सिमुलेशन में। डेटा को विभिन्न उप-सर्किटों के बीच विभाजित किया जाता है और कार्यों से ऑर्केस्ट्रेशन के साथ समानता हासिल की जाती है।

डेटा समानांतर प्रोग्रामिंग वातावरण

विभिन्न प्रकार के डेटा समानांतर प्रोग्रामिंग वातावरण आज उपलब्ध हैं, जिनमें से सबसे व्यापक रूप से उपयोग किए जाते हैं:

1. संदेश पासिंग इंटरफ़ेस: यह समानांतर कंप्यूटरों के लिए एक क्रॉस-प्लेटफ़ॉर्म संदेश पासिंग प्रोग्रामिंग इंटरफ़ेस है। यह उपयोगकर्ताओं को सी, सी ++ और फोरट्रान में पोर्टेबल संदेश पासिंग प्रोग्राम लिखने की अनुमति देने के लिए पुस्तकालय कार्यों के शब्दार्थ को परिभाषित करता है।
2. ओपन मल्टी प्रोसेसिंग (ओपन एमपी): यह एक एप्लिकेशन प्रोग्रामिंग इंटरफेस (एपीआई) है जो मल्टीप्रोसेसर सिस्टम के कई प्लेटफॉर्म पर साझा मेमोरी प्रोग्रामिंग मॉडल का समर्थन करता है।
3. CUDA और OpenACC: CUDA और OpenACC (क्रमशः) समानांतर कंप्यूटिंग एपीआई प्लेटफॉर्म हैं जो एक सॉफ्टवेयर इंजीनियर को सामान्य प्रयोजन प्रसंस्करण के लिए GPU की कम्प्यूटेशनल इकाइयों का उपयोग करने की अनुमति देने के लिए डिज़ाइन किए गए हैं।
4. थ्रेडिंग बिल्डिंग ब्लॉक्स और राफ्टलिब: दोनों ओपन सोर्स प्रोग्रामिंग वातावरण जो विषम संसाधनों में सी / सी ++ वातावरण में मिश्रित डेटा / कार्य समानता को सक्षम करते हैं।

अनुप्रयोग

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

यह भी देखें

• सक्रिय संदेश
• निर्देश स्तर समानता
• स्केलेबल समानता
• थ्रेड स्तर समानता
• समानांतर प्रोग्रामिंग मॉडल

संदर्भ

• Hillis, W. Daniel and Steele, Guy L., Data Parallel Algorithms Communications of the ACM December 1986
• Blelloch, Guy E, Vector Models for Data-Parallel Computing MIT Press 1990. ISBN 0-262-02313-X