🧓🏽 👼🏻 🏂 कार्यों का समानांतर होना। "पूर्ण समानता" का मामला। भाग 1 👨‍👨‍👦 🌋 🐭

निर्भरता के बिना कोड समानांतरकरण

परिचय

इस लेख के पहले भाग में हम उन सफल मामलों में छोरों के समानांतर प्रसंस्करण के दृष्टिकोण के बारे में बात करेंगे जब व्यक्तिगत पुनरावृत्तियों के बीच कोई निर्भरता नहीं होती है, और उन्हें समानांतर में सही ढंग से निष्पादित किया जा सकता है। दूसरे भाग में , हम ऐसे तंत्रों पर विचार करेंगे जो इस तरह के समानांतरकरण के प्रबंधन के लिए .NET 4.0 में दिखाई दिए और इन तंत्रों की जटिलताओं को प्रकट करते हैं।

कुछ चक्र पर विचार करें जिसमें डेटा संसाधित किया गया है:

for ( int i = 0 ; i < upperBound ; i ++ ) { // ... }

for ( int i = 0 ; i < upperBound ; i ++ ) { // ... }

for ( int i = 0 ; i < upperBound ; i ++ ) { // ... }

for ( int i = 0 ; i < upperBound ; i ++ ) { // ... }

यदि चक्र के शरीर का तर्क ऐसा है कि किसी विशेष पुनरावृत्ति पर इसकी गणना का परिणाम किसी अन्य पुनरावृत्ति की गणना के परिणाम पर निर्भर नहीं करता है, तो यह चक्र "पूरी तरह से समानांतर" है, क्योंकि इसके सभी पुनरावृत्तियों को समानांतर में किया जा सकता है। इस प्रोसेसर पर कोर।

समान परिभाषा को एक समान फ़ॉरेस्ट लूप पर लागू किया जा सकता है; यह इस प्रकार है कि कंप्यूटिंग पुनरावृत्तियों का क्रम महत्वपूर्ण नहीं है।

समानांतर लूप दृष्टिकोण

चलो समानांतर में चक्र को निष्पादित करने के लिए विधि को लागू करने का प्रयास करें, और देखें कि हम किन कठिनाइयों का सामना करेंगे।

तो, हम इस तरह एक विधि बनाने जा रहे हैं:

सार्वजनिक स्थैतिक शून्य ParallelFor ( int से, int से, क्रिया < int > शरीर ) ;

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

समानता की डिग्री का निर्धारण

एक ध्वनि निर्णय है कि इस मशीन पर प्रोसेसर पर कोर के रूप में कई थ्रेड्स का उपयोग करना तर्कसंगत है। इस निर्णय के साथ, प्रत्येक कोर पूरी तरह से भरी हुई होगी। अधिक थ्रेड्स के साथ, हम उन दोनों के बीच स्विच करने के ओवरहेड में वृद्धि प्राप्त करेंगे, कम के साथ - कुछ कोर निष्क्रिय होंगे।

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

इस प्रकार, यह पता चला है कि यह "एक धागा प्रति कोर" सरल विकल्प के साथ शुरू करने के लायक है, लेकिन अन्य रणनीतियों पर विचार करने के लिए तैयार रहें।

उपलब्ध कोर की संख्या प्राप्त करने के लिए, हम System.Environment.ProcessorCount प्रॉपर्टी का उपयोग कर सकते हैं। यह ध्यान दिया जाना चाहिए कि यह हाइपर-थ्रेडिंग को ध्यान में रखते हुए कोर की संख्या लौटाता है, अर्थात, यदि यह मौजूद है, तो एक "तार्किक", पहले से ही दोगुनी संख्या में कोर वापस आ जाएगा।

पूर्वगामी के आधार पर, यहां एक तार्किक (कुछ हद तक भोली) कार्यान्वयन है:

सार्वजनिक स्थैतिक शून्य ParallelFor ( int से, int से, क्रिया < int > शरीर )
{
// प्रत्येक थ्रेड के लिए थ्रेड्स की संख्या और डेटा ब्लॉक का आकार निर्धारित करें
int size = to - से ;
int numProcs = पर्यावरण। ProcessorCount;
int range = size / numProcs ;
// डेटा को तोड़ें, सभी थ्रेड शुरू करें और पूरा होने की प्रतीक्षा करें
var थ्रेड = नई सूची < थ्रेड > ( numProcs ) ;
( int p = 0 ; p < numProcs ; p ++ )
{
int start = p * range + from ;
int end = ( p == numProcs - 1 ) ?
से : प्रारंभ + सीमा ;
धागे। जोड़ें ( नया सूत्र ) ( ) => {
for ( int i = start ; i < end ; i ++ ) बॉडी ( i ) ;
} ) ) ;
}
foreach ( थ्रेड में थ्रेड ) थ्रेड। प्रारंभ ( ) ;
foreach ( थ्रेड में थ्रेड ) थ्रेड। सम्मिलित हों ( ) ;
}

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

नए धागों के निर्माण से एक और समस्या भी पैदा होती है। मान लीजिए कि शरीर में हमें कुछ कोड दिया गया है जिसमें एक ParallelFor कॉल भी है। इस मामले में, निष्पादन की प्रक्रिया के दौरान, अंकों के थ्रेड्स से अधिक नहीं बनाए जाएंगे, लेकिन दो बार के रूप में कई, और ऐसी स्थिति उत्पन्न हो सकती है जहां थ्रेड्स के बीच स्विच करने की लागत बहुत अधिक होगी ("अत्यधिक मल्टीथ्रेडिंग")।

स्थैतिक Iteration वितरण

इसलिए, मैन्युअल रूप से थ्रेड बनाने के बजाय, हम थ्रेड पूल का उपयोग करना पसंद करते हैं:

सार्वजनिक स्थैतिक शून्य ParallelFor ( int से, int से, क्रिया < int > शरीर )
{
int size = to - से ;
int numProcs = पर्यावरण। ProcessorCount;
int range = size / numProcs ;
int शेष = numProcs ;
// सिंक्रनाइज़ेशन ऑब्जेक्ट, काम पूरा करने का निर्धारण करने के लिए
( ManualResetEvent mre = new ManualResetEvent ( गलत ) ) का उपयोग करना
{
// सभी कार्य बनाएं
( int p = 0 ; p < numProcs ; p ++ )
{
int start = p * range + from ;
int end = ( p == numProcs - 1 ) ? से : प्रारंभ + सीमा ;
ThreadPool। QueueUserWorkItem ( प्रतिनिधि {
for ( int i = start ; मैं < अंत ; मैं ++ )
शरीर ( i ) ;
/ / अगर अंतिम कार्य पूरा हो गया था की जाँच करें
अगर ( इंटरलॉक किया गया। वृद्धि ( शेष शेष ) == 0 )
MRE। सेट ( ) ;
} ;
}
// प्रतीक्षा करें जब तक कि सभी कार्य पूर्ण नहीं हो जाते
MRE। WaitOne ( ) ;
}
}

यह समाधान पहले से ही अत्यधिक मल्टीथ्रेडिंग और थ्रेड बनाने की लागत से मुक्त है। इस स्थिति में और क्या इस चक्र के सबसे तेजी से संभव विकास को रोक सकता है?

यदि सभी पुनरावृत्तियों समय में छोटे हैं और लगभग समान रूप से महंगा हैं, तो उपरोक्त दृष्टिकोण इष्टतम के करीब है।

और अगर हम कल्पना करते हैं कि कुछ पुनरावृत्तियां जल्दी से पूरी होती हैं, और कुछ समय से अधिक समय तक, तो पूल से वह धागा, जो अधिक "लंबे" पुनरावृत्तियों का निष्पादक होने के लिए भाग्यशाली नहीं था, दूसरों की तुलना में कई गुना अधिक समय तक काम करेगा। एक ही समय में, चूंकि पूरे समानांतर ऑपरेशन का संचालन समय उसके सबसे धीमे घटक के ऑपरेटिंग समय से निर्धारित होता है, परिणामस्वरूप, बाकी के धागे बेकार हो जाएंगे, उनके सभी "काम" हो जाएंगे, जबकि एक "अनलकी" सभी को देरी करेगा।

ऐसी स्थिति में न्यूनतम परिचालन समय सुनिश्चित करने के लिए, यह आवश्यक है

या पुनरावृत्तियों की प्रकृति को जानने के लिए, ताकि सभी धागे समान रूप से "लंबे" पुनरावृत्तियों के साथ वितरित हों,
या थ्रेड्स के बीच कार्यों को साझा करने के लिए सामान्य दृष्टिकोण को बदलें।

गतिशील Iteration वितरण

स्थैतिक पृथक्करण से डायनेमिक पर जाना संभव है, अर्थात् प्रत्येक थ्रेड को काम का एक निश्चित "भाग" देना, जो किया जा रहा है, यह अगले भाग को प्राप्त करेगा यदि पूर्ववत काम अभी भी तब तक रहता है।

यह दृष्टिकोण इस कोड के साथ चित्रित किया जा सकता है:

सार्वजनिक स्थैतिक शून्य ParallelFor ( int से, int से, क्रिया < int > शरीर )
{
int numProcs = पर्यावरण। ProcessorCount;
// शेष संख्या
int बचे हुए काम के लिए = numProcs ;
int nextIteration = from ;
( ManualResetEvent mre = new ManualResetEvent ( गलत ) ) का उपयोग करना
{
// कार्य बनाएं
( int p = 0 ; p < numProcs ; p ++ )
{
ThreadPool। QueueUserWorkItem ( प्रतिनिधि)
{
इंट इंडेक्स ;
// प्रति निष्पादन एक तत्व का चयन करें
जबकि ( ( इंडेक्स = इंटरलॉक किया गया। वृद्धि ( रेफ नेक् टरेशन ) - 1 ) < )
{
शरीर ( सूचकांक ) ;
}
अगर ( इंटरलॉक किया गया है। गिरावट ( शेष शेष देखें ) == 0 )
MRE। सेट ( ) ;
} ;
}
// सभी कार्यों के पूरा होने तक प्रतीक्षा करें
MRE। WaitOne ( ) ;
}
}

यह कोड अप्रत्याशित रनटाइम के साथ लंबे पुनरावृत्तियों के लिए अच्छा है, लेकिन तेज़ पुनरावृत्तियों में बहुत अधिक सिंक्रनाइज़ेशन लागतें हैं।

संतुलित दृष्टिकोण

इस प्रकार, हम देखते हैं कि, समानांतर चक्र की प्रकृति के आधार पर, थ्रेड्स और डायनेमिक के बीच कार्यों के स्थैतिक अलगाव की एक रणनीति लाभप्रद हो सकती है। यह मानना तर्कसंगत है कि मध्यवर्ती मामलों के लिए कुछ संतुलित रणनीति सफल हो सकती है।

यहाँ इसके कोड का एक प्रकार है। विचार यह है कि हम एक "भाग" को केवल एक तत्व से कुछ अधिक बनाते हैं, लेकिन एक स्थिर वितरण के मामले में कम।

सार्वजनिक स्थैतिक शून्य ParallelFor ( int से, int से, क्रिया < int > शरीर )
{
int numProcs = पर्यावरण। ProcessorCount;
int बचे हुए काम के लिए = numProcs ;
int nextIteration = from ;
// डेटा के "हिस्से" का आकार
const int बैचसाइज़ = 3 ;
( ManualResetEvent mre = new ManualResetEvent ( गलत ) ) का उपयोग करना
{
( int p = 0 ; p < numProcs ; p ++ )
{
ThreadPool। QueueUserWorkItem ( प्रतिनिधि {
इंट इंडेक्स ;
जबकि ( ( इंडेक्स = इंटरलॉक किया गया। ऐड ( रेफ नेक्स्टइंटरेशन, बैचसाइज़ ) - बैचसाइज़ ) < से )
{
int end = index + batchSize ;
अगर ( अंत > = )
अंत = को ;
for ( int i = index ; मैं < अंत ; i ++ )
शरीर ( i ) ;
}
अगर ( इंटरलॉक किया गया है। गिरावट ( शेष शेष देखें ) == 0 )
MRE। सेट ( ) ;
} ;
}
MRE। WaitOne ( ) ;
}
}

यहां, डेटा भाग का आकार एक स्थिर द्वारा निर्धारित किया जाता है, और इसे बदलते हुए, हम कार्यों के स्थिर और गतिशील वितरण के बीच के स्तर की आवश्यकता का चयन करते हैं।

निष्कर्ष

किसी भी मामले में, किसी विशेष मामले के लिए इष्टतम सेटिंग्स गणना की प्रकृति द्वारा निर्धारित की जाती हैं। लेकिन काम के अधिक या कम बड़े "सर्विंग्स" के गतिशील वितरण के साथ समझौता ज्यादातर स्थितियों के लिए काफी स्वीकार्य हो सकता है। यह कैसे .NET .NET में समानांतर लूप निष्पादन के लिए पुस्तकालय विधियों को लागू किया जाता है, जिस पर लेख के दूसरे भाग में चर्चा की जाएगी।

PS यह लेख " पैराग्राफ ऑफ़ लोकल प्रोग्रेसिंग: अंडरग्राउंडिंग एंड अप्लाईिंग पैलेटेल पैटरएनएस विद द नेट फ्रैमवर्क 4 और विजुअल सी " पुस्तक के प्रभाव में लिखा गया था और इसे प्रोसेसिंग के साथ इसका मुफ्त अनुवाद माना जा सकता है।

______________________

UPD: दूसरा भाग - व्यावहारिक: habrahabr.ru/blogs/net/104103

कार्यों का समानांतर होना। "पूर्ण समानता" का मामला। भाग 1