छोटे शुद्ध समारोह को समानांतर कैसे करें?

Question

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

पहली नज़र में, यह समांतरता के लिए सही उम्मीदवार की तरह लगता है। एकमात्र समस्या यह है कि फ़ंक्शन में केवल 3 माइक्रोसॉन्ड प्रति कॉल होता है, जो एक नया धागा बनाने की विलंबता से नीचे है, और एक कार्य पूल में नौकरी जोड़ने के ऊपरी हिस्से से ऊपर नहीं है (यानी, एक म्यूटेक्स प्राप्त करना, स्मृति आवंटित करना कार्य पूल की कतार आदि के लिए संभावित विवाद से निपटने, कार्य के बारे में जानकारी पकड़ें)। क्या समांतरता का लाभ उठाने का कोई अच्छा तरीका है जो यह बढ़िया है?

Answer 1

कई धागे बनाने के बारे में क्या है जिनके पास अपनी खुद की कतार है? चूंकि कतारों का कोई ओवरलैपिंग नहीं है, इसलिए आपको ताले बनाने की ज़रूरत नहीं है।

Answer 2

अपने कार्यक्रम की संरचना के आधार पर, आप हमेशा कॉल के समूह को एक कार्य में जोड़ सकते हैं। यदि प्रत्येक कार्य 50 फ़ंक्शन कॉल करता है, तो कार्य प्रबंधन के लिए ओवरहेड अब इतना बड़ा कारक नहीं है।

Answer 3

प्रत्येक थ्रेड को एक ही कार्य चलाने के लिए शुरू न करें, फिर इसे बंद करें।

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

जब भी आपके पास कुछ सैकड़ों या हजारों का ब्लॉक होता है आपकी प्रक्रियाओं की गणना करने के लिए, पूरे ब्लॉक को अगले खाली कतार में छोड़ दें।

आप वास्तव में कतारों को खिला रहे एक या अधिक धागे, कतारों से डेटा प्रोसेसिंग थ्रेड का एक समूह, और एक या अधिक पढ़ने और परिणामों से निपटने के साथ समाप्त हो जाएंगे।

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

शायद आप कोर के मुकाबले प्रसंस्करण कर रहे अधिक थ्रेड नहीं चाहते हैं।

संपादित करें: ThreadPoolExecutor जैसे कुछ समवर्ती लाइब्रेरी को भी देखें। समवर्ती लाइब्रेरी को भूलना आसान है (जैसे मैंने अभी किया था), शायद यह वही है जो आप खोज रहे थे (इसलिए जोर)

Answer 4

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

Answer 5

जैसा ऊपर बताया गया है, हर बार जब आप इस फ़ंक्शन में प्रवेश करते हैं तो थ्रेड को लात न करें, और इसके अलावा आंतरिक कार्य के एक ऑपरेशन से अधिक "नौकरी" ग्रैन्युलरिटी हो ताकि नौकरी निर्माण ओवरहेड अच्छी तरह से अमूर्त हो।की तरह कुछ के रूप में अपने मूल दिनचर्या बताते:

void OuterFunction(Thingy inputData[N]) 
{ 
    for (int i = 0 ; i < N ; ++i) 
    InnerFunction(inputData[i]); 
} 

हम से आपकी समस्या का समाधान चाहते हैं (एक नौकरी कतार प्रणाली संभालने मौजूद है):

void JobFunc(Thingy inputData[], int start, int stop) 
{ 
    for (int i = start ; i < stop ; ++i) 
    InnerFunction(inputData[i]); 
} 
void OuterFunction(Thingy inputData[N], int numCores) 
{ 
    int perCore = N/numCores; // assuming N%numCores=0 
           // (omitting edge case for clarity) 
    for (int c = 0 ; c < numCores ; ++c) 
    QueueJob(JobFunc, inputData, c * perCore, (c + 1) * perCore); 
} 

इतने लंबे समय के अपने इनपुट डेटा पूरी तरह से स्वतंत्र है, के रूप में के रूप में आप अपने मूल प्रश्न में कहते हैं, आपको इसे लॉक करने की आवश्यकता नहीं है; सिंक्रनाइज़ेशन केवल तभी जरूरी है जब धागे के बीच निर्भरता हो और यहां कोई भी नहीं है।

इसके अलावा, प्रदर्शन के इस स्तर पर माइक्रोपेटिमाइजेशन प्रासंगिक होने लगते हैं: सबसे महत्वपूर्ण बात यह है कि कैश इलाके। प्रीफेचिंग आपको आश्चर्यजनक रूप से लंबा रास्ता मिल सकता है।

फिर सिम की संभावना पर विचार करें, आप एक ही रजिस्टर के माध्यम से चार इनपुट पॉइंट चलाने के लिए इसे सदिश बना सकते हैं। चार कोर और 4-चौड़े सिम के साथ आप सैद्धांतिक रूप से को 16x स्पीडअप प्राप्त कर सकते हैं, लेकिन यह मानता है कि इनरफंक्शन जो काम कर रहा है वह ज्यादातर एक निश्चित गणितीय फ़ंक्शन है, क्योंकि ब्रांचिंग एसएसई/वीएमएक्स प्रदर्शन लाभ को समाप्त करने के लिए होती है।

Answer 6

क्या मजेदार सवाल है ... जैसा कि आपने देखा है कि आप इसके लिए एक कार्य कतार के लिए पारंपरिक लॉकिंग से जुड़े ओवरहेड को बर्दाश्त नहीं कर पाएंगे। मैं आपको मौजूदा सुगंधित कार्य आधारित प्रोग्रामिंग वातावरणों में से किसी एक का उपयोग करने के लिए प्रोत्साहित करने के लिए प्रोत्साहित करता हूं यदि आप कर सकते हैं ... मैं इस बारे में सोचता हूं कि काम के तीन बाल्टी में:

समस्या का पहला हिस्सा सुरक्षा सुनिश्चित करना है , शुद्धता और समांतरता, और ऐसा लगता है कि आपके पास यह कवर है क्योंकि आपका कार्य शुद्ध है।

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

अंतिम क्षेत्र जो मैं सोचता हूं, यह सुनिश्चित करना है कि आपके प्लेटफ़ॉर्म पर कुशल निष्पादन है और इसमें आपके कोड और शेड्यूलिंग कोड दोनों में ओवरहेड्स और विवाद को कम करना शामिल है और यह सुनिश्चित करना कि कोई भी सीरियल कोड यथासंभव कुशल हो। यदि आप मौजूदा पुस्तकालयों में से किसी एक का उपयोग नहीं कर सकते हैं और अपना खुद का निर्माण करना चाहते हैं, तो मैं आपको work-stealing queue और स्वयं निर्देशित शेड्यूलिंग एल्गोरिदम देखने के लिए प्रोत्साहित करता हूं, जैसा कि आपने देखा है कि आप लाभ का उपयोग करने से लाभ नहीं देख पाएंगे पारंपरिक ताले क्योंकि उनकी लागत आपकी कार्य लागत से अधिक है और आपको शेक्यूलिंग की लागत को कम करने और किसी भी कतार पर किसी कार्य को हटाने के लिए लॉक-फ्री तकनीकों को देखने की आवश्यकता होगी। आपको अपने शेड्यूलिंग एल्गोरिदम के भीतर और अपने फ़ंक्शन के भीतर साझा करने और विवाद के लिए बहुत अधिक ध्यान देना होगा, क्योंकि सामान्य शाखा गलतफहमी और निर्देश थ्रूपुट समस्याओं के अतिरिक्त ग्रैन्युलरिटी के इस स्तर पर, आपको भी देखना होगा shared state and contention even on reads because they can be sources of contention too पर।

मुझे खेद है कि यह सुपर विशिष्ट नहीं था, लेकिन मुझे उम्मीद है कि यह उपयोगी था।

Answer 7

आप की तुलना करें और स्वैप का उपयोग कर अंदर बाहर पाश चालू करने के लिए एक परमाणु ताला मुक्त वेतन वृद्धि प्राप्त करने में सक्षम हो सकता है:

void OuterFunction() 
{ 
    int i = 0, j = 0; 

    void Go() 
    { 
     int k; 
     while((k = atomicInc(*i)) < N) 
     { 
     InnerFunction(k); 

     atomicInc(*j); 
     } 
    } 

    for(int t = 0; t < ThreadCount - 1; t++) Thread.Start(&Go); 

    Go(); // join in 

    while(j < N) Wait(); // let everyone else catch up. 
} 

---

संपादित करें:

void OuterFunction() 
{ 
    for(int i = 0; i < N; i++) 
    InnerFunction(i); 
} 

को जाता है : मेरा थ्रेडिंग जंगली है इसलिए संकलित नहीं होगा क्योंकि नाम सभी गलत हैं

Answer 8

कॉल के बीच कोई डेटा निर्भरता नहीं है, यानी कोई भी कॉल किसी अन्य कॉल से परिणाम का उपयोग नहीं करता है।

parallelisation साथ में मदद मिलेगी कि है, लेकिन पूरी तरह से निश्चित समारोह सब पर कोई दुष्प्रभाव है कि हो सकता है। यदि फ़ंक्शन डेटा संरचना को अद्यतन कर रहा है, तो क्या यह थ्रेड-सुरक्षित है? यदि यह आईओ कर रहा है, तो क्या आप आईओ को केवल एक बाधा बनने के लिए खत्म कर देंगे यदि आप फ़ंक्शन के निष्पादन को समानांतर करते हैं?

यदि उत्तर इन सवालों के लिए "हाँ" है तो पिछले सुझाव ठीक हैं, बस प्रति थ्रेड जितना संभव हो सके फ़ंक्शन के निष्पादन को असाइन करके ऐप की ग्रैन्युलरिटी को अधिकतम करने का प्रयास करें।

फिर भी, आप शायद बड़े पैमाने पर समानांतरवाद से कोई लाभ मिलेगा नहीं, लेकिन शायद कुछ अधिक विनम्र speedup किया जा सकता है ...